More Like this

1. From approximate to exact integer programming

   https://doi.org/10.1007/s10107-024-02084-1  

   Dadush, Daniel ; Eisenbrand, Friedrich ; Rothvoss, Thomas ( April 2024 , Mathematical Programming)

   Approximate integer programming is the following: For a given convex body$$K \subseteq {\mathbb {R}}^n$$$K\subseteq R^n$, either determine whether$$K \cap {\mathbb {Z}}^n$$$K\cap Z^n$is empty, or find an integer point in the convex body$$2\cdot (K - c) +c$$$2·(K-c)+c$which isK, scaled by 2 from its center of gravityc. Approximate integer programming can be solved in time$$2^{O(n)}$$$2^{O\left(n\right)}$while the fastest known methods for exact integer programming run in time$$2^{O(n)} \cdot n^n$$$2^{O\left(n\right)}·n^n$. 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$$x^* \in (K \cap {\mathbb {Z}}^n)$$$x^{\ast }\in (K\cap Z^n)$can be found in time$$2^{O(n)}$$$2^{O\left(n\right)}$, provided that theremaindersof each component$$x_i^* \mod \ell $$$x_i^{\ast }mod\ell$for some arbitrarily fixed$$\ell \ge 5(n+1)$$$\ell \ge 5(n+1)$of$$x^*$$$x^{\ast }$are given. The algorithm is based on acutting-plane 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$$2^{O(n)}n^n$$$2^{O\left(n\right)}{n}^n$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 newasymmetric approximate Carathéodory theoremthat might be of interest on its own. Our second method concerns integer programming problems in equation-standard form$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$$Ax=b,0\le x\le u,x\in Z^n$. Such a problem can be reduced to the solution of$$\prod _i O(\log u_i +1)$$${\prod }_{i}O(log{u}_i+1)$approximate integer programming problems. This implies, for example thatknapsackorsubset-sumproblems withpolynomial variable range$$0 \le x_i \le p(n)$$$0\le x_i\le p\left(n\right)$can be solved in time$$(\log n)^{O(n)}$$${(logn)}^{O\left(n\right)}$. For these problems, the best running time so far was$$n^n \cdot 2^{O(n)}$$$n^n·2^{O\left(n\right)}$.

    

   more » « less
2. On the rigorous derivation of the incompressible Euler equation from Newton’s second law

   https://doi.org/10.1007/s11005-023-01630-w  

   Rosenzweig, Matthew ( January 2023 , Letters in Mathematical Physics)

   A long-standing problem in mathematical physics is the rigorous derivation of the incompressible Euler equation from Newtonian mechanics. Recently, Han-Kwan and Iacobelli (Proc Am Math Soc 149:3045–3061, 2021) showed that in the monokinetic regime, one can directly obtain the Euler equation from a system ofNparticles interacting in$${\mathbb {T}}^d$$$T^d$,$$d\ge 2$$$d\ge 2$, via Newton’s second law through asupercritical mean-field limit. Namely, the coupling constant$$\lambda $$$\lambda$in front of the pair potential, which is Coulombic, scales like$$N^{-\theta }$$$N^{-\theta }$for some$$\theta \in (0,1)$$$\theta \in (0,1)$, in contrast to the usual mean-field scaling$$\lambda \sim N^{-1}$$$\lambda \sim N^{-1}$. Assuming$$\theta \in (1-\frac{2}{d(d+1)},1)$$$\theta \in (1-\frac{2}{d(d+1)},1)$, they showed that the empirical measure of the system is effectively described by the solution to the Euler equation as$$N\rightarrow \infty $$$N\to \infty$. Han-Kwan and Iacobelli asked if their range for$$\theta $$$\theta$was optimal. We answer this question in the negative by showing the validity of the incompressible Euler equation in the limit$$N\rightarrow \infty $$$N\to \infty$for$$\theta \in (1-\frac{2}{d},1)$$$\theta \in (1-\frac{2}{d},1)$. Our proof is based on Serfaty’s modulated-energy method, but compared to that of Han-Kwan and Iacobelli, crucially uses an improved “renormalized commutator” estimate to obtain the larger range for$$\theta $$$\theta$. Additionally, we show that for$$\theta \le 1-\frac{2}{d}$$$\theta \le 1-\frac{2}{d}$, one cannot, in general, expect convergence in the modulated energy notion of distance.

    

   more » « less
3. Finding solutions with distinct variables to systems of linear equations over $$\mathbb {F}_p$$

   https://doi.org/10.1007/s00208-022-02391-y  

   Sauermann, Lisa ( April 2022 , Mathematische Annalen)

   Let us fix a primepand a homogeneous system ofmlinear equations$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$$a_{j,1}{x}_1+\cdots +a_{j,k}{x}_k=0$for$$j=1,\dots ,m$$$j=1,\cdots ,m$with coefficients$$a_{j,i}\in \mathbb {F}_p$$$a_{j,i}\in F_p$. Suppose that$$k\ge 3m$$$k\ge 3m$, that$$a_{j,1}+\dots +a_{j,k}=0$$$a_{j,1}+\cdots +a_{j,k}=0$for$$j=1,\dots ,m$$$j=1,\cdots ,m$and that every$$m\times m$$$m\times m$minor of the$$m\times k$$$m\times k$matrix$$(a_{j,i})_{j,i}$$${\left(a_{j,i}\right)}_{j,i}$is non-singular. Then we prove that for any (large)n, any subset$$A\subseteq \mathbb {F}_p^n$$$A\subseteq F_p^n$of size$$|A|> C\cdot \Gamma ^n$$$\left|A\right|>C·{\Gamma }^n$contains a solution$$(x_1,\dots ,x_k)\in A^k$$$(x_1,\cdots ,x_k)\in A^k$to the given system of equations such that the vectors$$x_1,\dots ,x_k\in A$$$x_1,\cdots ,x_k\in A$are all distinct. Here,Cand$$\Gamma $$$\Gamma$are constants only depending onp,mandksuch that$$\Gamma $\Gamma <p$. The crucial point here is the condition for the vectors$$x_1,\dots ,x_k$$$x_1,\cdots ,x_k$in the solution$$(x_1,\dots ,x_k)\in A^k$$$(x_1,\cdots ,x_k)\in A^k$to be distinct. If we relax this condition and only demand that$$x_1,\dots ,x_k$$$x_1,\cdots ,x_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 non-diagonal tensor in combination with combinatorial and probabilistic arguments.

    

   more » « less
4. Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms

   https://doi.org/10.1007/s00224-022-10106-8  

   Vyas, Nikhil ; Williams, R. Ryan ( November 2022 , Theory of Computing Systems)

   We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$$\mathrm{Quasi}-\mathrm{NP}=\mathrm{NTIME}\left[n^{{\left(\log n\right)}^{O\left(1\right)}}\right]$and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathcal { C}$$C$, by showing that$\mathcal { C}$$C$admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class${\mathcal C}$$C$. Say that a symmetric Boolean functionf(x₁,…,x_n) issparseif it outputs 1 onO(1) values of${\sum }_{i} x_{i}$${\sum }_i{x}_i$. We show that for every sparsef, and for all “typical”$\mathcal { C}$$C$, faster#SAT algorithms for$\mathcal { C}$$C$circuits imply lower bounds against the circuit class$f \circ \mathcal { C}$$f\circ C$, which may bestrongerthan$\mathcal { C}$$C$itself. In particular:

   #SAT algorithms forn^k-size$\mathcal { C}$$C$-circuits running in 2ⁿ/n^ktime (for allk) implyNEXPdoes not have$(f \circ \mathcal { C})$$(f\circ C)$-circuits of polynomial size.

   #SAT algorithms for$2^{n^{{\varepsilon }}}$$2^{n^{\epsilon }}$-size$\mathcal { C}$$C$-circuits running in$2^{n-n^{{\varepsilon }}}$$2^{n-n^{\epsilon }}$time (for someε> 0) implyQuasi-NPdoes not have$(f \circ \mathcal { C})$$(f\circ C)$-circuits of polynomial size.

   Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJ∘ACC⁰∘THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC⁰[Williams JACM’14] andACC⁰∘THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.

    

   more » « less
5. Generalized Parking Function Polytopes

   https://doi.org/10.1007/s00026-023-00671-1  

   Hanada, Mitsuki ; Lentfer, John ; Vindas-Meléndez, Andrés R. ( November 2023 , Annals of Combinatorics)

   A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$$(a_1,a_2,\dots ,a_n)$whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$$b_1\le b_2\le \cdots \le b_n$satisfies$$b_i \le i$$$b_i\le i$. The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$$R^n$, which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$$x$-parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$$x=(a,b,\cdots ,b)$, which we refer to as$${\textbf{x}}$$$x$-parking function polytopes. We explore connections between these$${\textbf{x}}$$$x$-parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$$x$-parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary.

    

   more » « less