Approximate integer programming is the following: For a given convex body
We investigate the properties of a special class of singular solutions for a selfgravitating perfect fluid in general relativity: the singular isothermal sphere. For arbitrary constant equationofstate parameter
 NSFPAR ID:
 10307773
 Publisher / Repository:
 Springer Science + Business Media
 Date Published:
 Journal Name:
 General Relativity and Gravitation
 Volume:
 53
 Issue:
 11
 ISSN:
 00017701
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract , either determine whether$$K \subseteq {\mathbb {R}}^n$$ $K\subseteq {R}^{n}$ is empty, or find an integer point in the convex body$$K \cap {\mathbb {Z}}^n$$ $K\cap {Z}^{n}$ which is$$2\cdot (K  c) +c$$ $2\xb7(Kc)+c$K , scaled by 2 from its center of gravityc . Approximate integer programming can be solved in time while the fastest known methods for exact integer programming run in time$$2^{O(n)}$$ ${2}^{O\left(n\right)}$ . So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$2^{O(n)} \cdot n^n$$ ${2}^{O\left(n\right)}\xb7{n}^{n}$ can be found in time$$x^* \in (K \cap {\mathbb {Z}}^n)$$ ${x}^{\ast}\in (K\cap {Z}^{n})$ , provided that the$$2^{O(n)}$$ ${2}^{O\left(n\right)}$remainders of each component for some arbitrarily fixed$$x_i^* \mod \ell $$ ${x}_{i}^{\ast}\phantom{\rule{0ex}{0ex}}mod\phantom{\rule{0ex}{0ex}}\ell $ of$$\ell \ge 5(n+1)$$ $\ell \ge 5(n+1)$ are given. The algorithm is based on a$$x^*$$ ${x}^{\ast}$cuttingplane technique , iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a new$$2^{O(n)}n^n$$ ${2}^{O\left(n\right)}{n}^{n}$asymmetric approximate Carathéodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equationstandard form . Such a problem can be reduced to the solution of$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$ $Ax=b,0\le x\le u,\phantom{\rule{0ex}{0ex}}x\in {Z}^{n}$ approximate integer programming problems. This implies, for example that$$\prod _i O(\log u_i +1)$$ ${\prod}_{i}O(log{u}_{i}+1)$knapsack orsubsetsum problems withpolynomial variable range can be solved in time$$0 \le x_i \le p(n)$$ $0\le {x}_{i}\le p\left(n\right)$ . For these problems, the best running time so far was$$(\log n)^{O(n)}$$ ${(logn)}^{O\left(n\right)}$ .$$n^n \cdot 2^{O(n)}$$ ${n}^{n}\xb7{2}^{O\left(n\right)}$ 
Abstract Given a suitable solution
V (t ,x ) to the Korteweg–de Vries equation on the real line, we prove global wellposedness for initial data . Our conditions on$$u(0,x) \in V(0,x) + H^{1}(\mathbb {R})$$ $u(0,x)\in V(0,x)+{H}^{1}\left(R\right)$V do include regularity but do not impose any assumptions on spatial asymptotics. We show that periodic profiles satisfy our hypotheses. In particular, we can treat localized perturbations of the muchstudied periodic traveling wave solutions (cnoidal waves) of KdV. In the companion paper Laurens (Nonlinearity. 35(1):343–387, 2022.$$V(0,x)\in H^5(\mathbb {R}/\mathbb {Z})$$ $V(0,x)\in {H}^{5}(R/Z)$https://doi.org/10.1088/13616544/ac37f5 ) we show that smooth steplike initial data also satisfy our hypotheses. We employ the method of commuting flows introduced in Killip and Vişan (Ann. Math. (2) 190(1):249–305, 2019.https://doi.org/10.4007/annals.2019.190.1.4 ) where . In that setting, it is known that$$V\equiv 0$$ $V\equiv 0$ is sharp in the class of$$H^{1}(\mathbb {R})$$ ${H}^{1}\left(R\right)$ spaces.$$H^s(\mathbb {R})$$ ${H}^{s}\left(R\right)$ 
Abstract It has been recently established in David and Mayboroda (Approximation of green functions and domains with uniformly rectifiable boundaries of all dimensions.
arXiv:2010.09793 ) that on uniformly rectifiable sets the Green function is almost affine in the weak sense, and moreover, in some scenarios such Green function estimates are equivalent to the uniform rectifiability of a set. The present paper tackles a strong analogue of these results, starting with the “flagship degenerate operators on sets with lower dimensional boundaries. We consider the elliptic operators associated to a domain$$L_{\beta ,\gamma } = {\text {div}}D^{d+1+\gamma n} \nabla $$ ${L}_{\beta ,\gamma}=\text{div}{D}^{d+1+\gamma n}\nabla $ with a uniformly rectifiable boundary$$\Omega \subset {\mathbb {R}}^n$$ $\Omega \subset {R}^{n}$ of dimension$$\Gamma $$ $\Gamma $ , the now usual distance to the boundary$$d < n1$$ $d<n1$ given by$$D = D_\beta $$ $D={D}_{\beta}$ for$$D_\beta (X)^{\beta } = \int _{\Gamma } Xy^{d\beta } d\sigma (y)$$ ${D}_{\beta}{\left(X\right)}^{\beta}={\int}_{\Gamma}{Xy}^{d\beta}d\sigma \left(y\right)$ , where$$X \in \Omega $$ $X\in \Omega $ and$$\beta >0$$ $\beta >0$ . In this paper we show that the Green function$$\gamma \in (1,1)$$ $\gamma \in (1,1)$G for , with pole at infinity, is well approximated by multiples of$$L_{\beta ,\gamma }$$ ${L}_{\beta ,\gamma}$ , in the sense that the function$$D^{1\gamma }$$ ${D}^{1\gamma}$ satisfies a Carleson measure estimate on$$\big  D\nabla \big (\ln \big ( \frac{G}{D^{1\gamma }} \big )\big )\big ^2$$ $D\nabla (ln(\frac{G}{{D}^{1\gamma}})){}^{2}$ . We underline that the strong and the weak results are different in nature and, of course, at the level of the proofs: the latter extensively used compactness arguments, while the present paper relies on some intricate integration by parts and the properties of the “magical distance function from David et al. (Duke Math J, to appear).$$\Omega $$ $\Omega $ 
Abstract Let us fix a prime
p and a homogeneous system ofm linear equations for$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$ ${a}_{j,1}{x}_{1}+\cdots +{a}_{j,k}{x}_{k}=0$ with coefficients$$j=1,\dots ,m$$ $j=1,\cdots ,m$ . Suppose that$$a_{j,i}\in \mathbb {F}_p$$ ${a}_{j,i}\in {F}_{p}$ , that$$k\ge 3m$$ $k\ge 3m$ for$$a_{j,1}+\dots +a_{j,k}=0$$ ${a}_{j,1}+\cdots +{a}_{j,k}=0$ and that every$$j=1,\dots ,m$$ $j=1,\cdots ,m$ minor of the$$m\times m$$ $m\times m$ matrix$$m\times k$$ $m\times k$ is nonsingular. Then we prove that for any (large)$$(a_{j,i})_{j,i}$$ ${\left({a}_{j,i}\right)}_{j,i}$n , any subset of size$$A\subseteq \mathbb {F}_p^n$$ $A\subseteq {F}_{p}^{n}$ contains a solution$$A> C\cdot \Gamma ^n$$ $\leftA\right>C\xb7{\Gamma}^{n}$ to the given system of equations such that the vectors$$(x_1,\dots ,x_k)\in A^k$$ $({x}_{1},\cdots ,{x}_{k})\in {A}^{k}$ are all distinct. Here,$$x_1,\dots ,x_k\in A$$ ${x}_{1},\cdots ,{x}_{k}\in A$C and are constants only depending on$$\Gamma $$ $\Gamma $p ,m andk such that . The crucial point here is the condition for the vectors$$\Gamma $\Gamma <p$
in the solution$$x_1,\dots ,x_k$$ ${x}_{1},\cdots ,{x}_{k}$ to be distinct. If we relax this condition and only demand that$$(x_1,\dots ,x_k)\in A^k$$ $({x}_{1},\cdots ,{x}_{k})\in {A}^{k}$ are not all equal, then the statement would follow easily from Tao’s slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a nondiagonal tensor in combination with combinatorial and probabilistic arguments.$$x_1,\dots ,x_k$$ ${x}_{1},\cdots ,{x}_{k}$ 
Abstract We study the sparsity of the solutions to systems of linear Diophantine equations with and without nonnegativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the
norm of the vector. Our main results are new improved bounds on the minimal$$\ell _0$$ ${\ell}_{0}$ norm of solutions to systems$$\ell _0$$ ${\ell}_{0}$ , where$$A\varvec{x}=\varvec{b}$$ $Ax=b$ ,$$A\in \mathbb {Z}^{m\times n}$$ $A\in {Z}^{m\times n}$ and$${\varvec{b}}\in \mathbb {Z}^m$$ $b\in {Z}^{m}$ is either a general integer vector (lattice case) or a nonnegative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with$$\varvec{x}$$ $x$ norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over$$\ell _0$$ ${\ell}_{0}$ , to other subdomains such as$$\mathbb {R}$$ $R$ . We show that these new ranklike functions are all NPhard to compute in general, but polynomialtime computable for fixed number of variables.$$\mathbb {Z}$$ $Z$