Approximate integer programming is the following: For a given convex body
We prove that the Hilbert scheme of
- Award ID(s):
- 2203823
- NSF-PAR ID:
- 10462915
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Communications in Mathematical Physics
- Volume:
- 403
- Issue:
- 2
- ISSN:
- 0010-3616
- Page Range / eLocation ID:
- p. 1005-1068
- 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 We study the structure of the Liouville quantum gravity (LQG) surfaces that are cut out as one explores a conformal loop-ensemble
for$$\hbox {CLE}_{\kappa '}$$ in (4, 8) that is drawn on an independent$$\kappa '$$ -LQG surface for$$\gamma $$ . The results are similar in flavor to the ones from our companion paper dealing with$$\gamma ^2=16/\kappa '$$ for$$\hbox {CLE}_{\kappa }$$ in (8/3, 4), where the loops of the CLE are disjoint and simple. In particular, we encode the combined structure of the LQG surface and the$$\kappa $$ in terms of stable growth-fragmentation trees or their variants, which also appear in the asymptotic study of peeling processes on decorated planar maps. This has consequences for questions that do a priori not involve LQG surfaces: In our paper entitled “$$\hbox {CLE}_{\kappa '}$$ CLE Percolations ” described the law of interfaces obtained when coloring the loops of a independently into two colors with respective probabilities$$\hbox {CLE}_{\kappa '}$$ p and . This description was complete up to one missing parameter$$1-p$$ . The results of the present paper about CLE on LQG allow us to determine its value in terms of$$\rho $$ p and . It shows in particular that$$\kappa '$$ and$$\hbox {CLE}_{\kappa '}$$ are related via a continuum analog of the Edwards-Sokal coupling between$$\hbox {CLE}_{16/\kappa '}$$ percolation and the$$\hbox {FK}_q$$ q -state Potts model (which makes sense even for non-integerq between 1 and 4) if and only if . This provides further evidence for the long-standing belief that$$q=4\cos ^2(4\pi / \kappa ')$$ and$$\hbox {CLE}_{\kappa '}$$ represent the scaling limits of$$\hbox {CLE}_{16/\kappa '}$$ percolation and the$$\hbox {FK}_q$$ q -Potts model whenq and are related in this way. Another consequence of the formula for$$\kappa '$$ is the value of half-plane arm exponents for such divide-and-color models (a.k.a. fuzzy Potts models) that turn out to take a somewhat different form than the usual critical exponents for two-dimensional models.$$\rho (p,\kappa ')$$ -
Abstract We present a proof of concept for a spectrally selective thermal mid-IR source based on nanopatterned graphene (NPG) with a typical mobility of CVD-grown graphene (up to 3000
), ensuring scalability to large areas. For that, we solve the electrostatic problem of a conducting hyperboloid with an elliptical wormhole in the presence of an$$\hbox {cm}^2\,\hbox {V}^{-1}\,\hbox {s}^{-1}$$ in-plane electric field. The localized surface plasmons (LSPs) on the NPG sheet, partially hybridized with graphene phonons and surface phonons of the neighboring materials, allow for the control and tuning of the thermal emission spectrum in the wavelength regime from to 12$$\lambda =3$$ m by adjusting the size of and distance between the circular holes in a hexagonal or square lattice structure. Most importantly, the LSPs along with an optical cavity increase the emittance of graphene from about 2.3% for pristine graphene to 80% for NPG, thereby outperforming state-of-the-art pristine graphene light sources operating in the near-infrared by at least a factor of 100. According to our COMSOL calculations, a maximum emission power per area of$$\upmu$$ W/$$11\times 10^3$$ at$$\hbox {m}^2$$ K for a bias voltage of$$T=2000$$ V is achieved by controlling the temperature of the hot electrons through the Joule heating. By generalizing Planck’s theory to any grey body and deriving the completely general nonlocal fluctuation-dissipation theorem with nonlocal response of surface plasmons in the random phase approximation, we show that the coherence length of the graphene plasmons and the thermally emitted photons can be as large as 13$$V=23$$ m and 150$$\upmu$$ m, respectively, providing the opportunity to create phased arrays made of nanoantennas represented by the holes in NPG. The spatial phase variation of the coherence allows for beamsteering of the thermal emission in the range between$$\upmu$$ and$$12^\circ$$ by tuning the Fermi energy between$$80^\circ$$ eV and$$E_F=1.0$$ eV through the gate voltage. Our analysis of the nonlocal hydrodynamic response leads to the conjecture that the diffusion length and viscosity in graphene are frequency-dependent. Using finite-difference time domain calculations, coupled mode theory, and RPA, we develop the model of a mid-IR light source based on NPG, which will pave the way to graphene-based optical mid-IR communication, mid-IR color displays, mid-IR spectroscopy, and virus detection.$$E_F=0.25$$ -
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 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 $$ with a uniformly rectifiable boundary$$\Omega \subset {\mathbb {R}}^n$$ of dimension$$\Gamma $$ , the now usual distance to the boundary$$d < n-1$$ given by$$D = D_\beta $$ for$$D_\beta (X)^{-\beta } = \int _{\Gamma } |X-y|^{-d-\beta } d\sigma (y)$$ , where$$X \in \Omega $$ and$$\beta >0$$ . In this paper we show that the Green function$$\gamma \in (-1,1)$$ G for , with pole at infinity, is well approximated by multiples of$$L_{\beta ,\gamma }$$ , in the sense that the function$$D^{1-\gamma }$$ satisfies a Carleson measure estimate on$$\big | D\nabla \big (\ln \big ( \frac{G}{D^{1-\gamma }} \big )\big )\big |^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 $$