Approximate integer programming is the following: For a given convex body
We give sharp conditions for the large time asymptotic simplification of aggregation-diffusion equations with linear diffusion. As soon as the interaction potential is bounded and its first and second derivatives decay fast enough at infinity, then the linear diffusion overcomes its effect, either attractive or repulsive, for large times independently of the initial data, and solutions behave like the fundamental solution of the heat equation with some rate. The potential
- Award ID(s):
- 1900083
- NSF-PAR ID:
- 10394542
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Archive for Rational Mechanics and Analysis
- Volume:
- 247
- Issue:
- 1
- ISSN:
- 0003-9527
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Abstract , either determine whether$$K \subseteq {\mathbb {R}}^n$$ is empty, or find an integer point in the convex body$$K \cap {\mathbb {Z}}^n$$ which is$$2\cdot (K - c) +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)}$$ . 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$$ can be found in time$$x^* \in (K \cap {\mathbb {Z}}^n)$$ , provided that the$$2^{O(n)}$$ remainders of each component for some arbitrarily fixed$$x_i^* \mod \ell $$ of$$\ell \ge 5(n+1)$$ are given. The algorithm is based on a$$x^*$$ cutting-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 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$$ asymmetric approximate Carathéodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equation-standard form . Such a problem can be reduced to the solution of$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$ approximate integer programming problems. This implies, for example that$$\prod _i O(\log u_i +1)$$ knapsack orsubset-sum problems withpolynomial variable range can be solved in time$$0 \le x_i \le p(n)$$ . For these problems, the best running time so far was$$(\log n)^{O(n)}$$ .$$n^n \cdot 2^{O(n)}$$ -
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$$ with coefficients$$j=1,\dots ,m$$ . Suppose that$$a_{j,i}\in \mathbb {F}_p$$ , that$$k\ge 3m$$ for$$a_{j,1}+\dots +a_{j,k}=0$$ and that every$$j=1,\dots ,m$$ minor of the$$m\times m$$ matrix$$m\times k$$ is non-singular. Then we prove that for any (large)$$(a_{j,i})_{j,i}$$ n , any subset of size$$A\subseteq \mathbb {F}_p^n$$ contains a solution$$|A|> C\cdot \Gamma ^n$$ to the given system of equations such that the vectors$$(x_1,\dots ,x_k)\in A^k$$ are all distinct. Here,$$x_1,\dots ,x_k\in A$$ C and are constants only depending on$$\Gamma $$ p ,m andk such that . The crucial point here is the condition for the vectors$$\Gamma in the solution$$x_1,\dots ,x_k$$ to be distinct. If we relax this condition and only demand that$$(x_1,\dots ,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 non-diagonal tensor in combination with combinatorial and probabilistic arguments.$$x_1,\dots ,x_k$$ -
Abstract The free multiplicative Brownian motion
is the large-$$b_{t}$$ N limit of the Brownian motion on in the sense of$$\mathsf {GL}(N;\mathbb {C}),$$ -distributions. The natural candidate for the large-$$*$$ N limit of the empirical distribution of eigenvalues is thus the Brown measure of . In previous work, the second and third authors showed that this Brown measure is supported in the closure of a region$$b_{t}$$ that appeared in the work of Biane. In the present paper, we compute the Brown measure completely. It has a continuous density$$\Sigma _{t}$$ on$$W_{t}$$ which is strictly positive and real analytic on$$\overline{\Sigma }_{t},$$ . This density has a simple form in polar coordinates:$$\Sigma _{t}$$ where$$\begin{aligned} W_{t}(r,\theta )=\frac{1}{r^{2}}w_{t}(\theta ), \end{aligned}$$ is an analytic function determined by the geometry of the region$$w_{t}$$ . We show also that the spectral measure of free unitary Brownian motion$$\Sigma _{t}$$ is a “shadow” of the Brown measure of$$u_{t}$$ , precisely mirroring the relationship between the circular and semicircular laws. We develop several new methods, based on stochastic differential equations and PDE, to prove these results.$$b_{t}$$ -
Abstract A study of possible superconducting phases of graphene has been constructed in detail. A realistic tight binding model, fit to ab initio calculations, accounts for the Li-decoration of graphene with broken lattice symmetry, and includes
s andd symmetry Bloch character that influences the gap symmetries that can arise. The resulting seven hybridized Li-C orbitals that support nine possible bond pairing amplitudes. The gap equation is solved for all possible gap symmetries. One band is weakly dispersive near the Fermi energy along Γ →M where its Bloch wave function has linear combination of and$${d}_{{x}^{2}-{y}^{2}}$$ d xy character, and is responsible for and$${d}_{{x}^{2}-{y}^{2}}$$ d xy pairing with lowest pairing energy in our model. These symmetries almost preserve properties from a two band model of pristine graphene. Another part of this band, alongK → Γ, is nearly degenerate with uppers band that favors extendeds wave pairing which is not found in two band model. Upon electron doping to a critical chemical potentialμ 1 = 0.22eV the pairing potential decreases, then increases until a second critical valueμ 2 = 1.3 eV at which a phase transition to a distorteds -wave occurs. The distortion ofd - or s-wave phases are a consequence of decoration which is not appear in two band pristine model. In the pristine graphene these phases convert to usuald -wave or extendeds -wave pairing. -
Abstract 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
and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$ , by showing that$\mathcal { C}$ admits non-trivial satisfiability and/or$\mathcal { C}$ # 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 . Say that a symmetric Boolean function${\mathcal C}$ f (x 1,…,x n ) issparse if it outputs 1 onO (1) values of . We show that for every sparse${\sum }_{i} x_{i}$ f , and for all “typical” , faster$\mathcal { C}$ # SAT algorithms for circuits imply lower bounds against the circuit class$\mathcal { C}$ , which may be$f \circ \mathcal { C}$ stronger than itself. In particular:$\mathcal { C}$ # SAT algorithms forn k -size -circuits running in 2$\mathcal { C}$ n /n k time (for allk ) implyN E X P does not have -circuits of polynomial size.$(f \circ \mathcal { C})$ # SAT algorithms for -size$2^{n^{{\varepsilon }}}$ -circuits running in$\mathcal { C}$ time (for some$2^{n-n^{{\varepsilon }}}$ ε > 0) implyQ u a s i -N P does not have -circuits of polynomial size.$(f \circ \mathcal { C})$ Applying
# SAT algorithms from the literature, one immediate corollary of our results is thatQ u a s i -N P does not haveE M A J ∘A C C 0∘T H R circuits of polynomial size, whereE M A J is the “exact majority” function, improving previous lower bounds againstA C C 0[Williams JACM’14] andA C C 0∘T H R [Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.