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
Applying
As the use of spectral/
- Award ID(s):
- 1848508
- NSF-PAR ID:
- 10362210
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Journal of Scientific Computing
- Volume:
- 90
- Issue:
- 2
- ISSN:
- 0885-7474
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract $\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$ $\mathcal { C}$ $\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${\mathcal C}$ f (x 1,…,x n ) issparse if it outputs 1 onO (1) values of${\sum }_{i} x_{i}$ f , and for all “typical”$\mathcal { C}$ # SAT algorithms for$\mathcal { C}$ $f \circ \mathcal { C}$ stronger than$\mathcal { C}$ # SAT algorithms forn k -size$\mathcal { C}$ n /n k time (for allk ) implyN E X P does not have$(f \circ \mathcal { C})$ # SAT algorithms for$2^{n^{{\varepsilon }}}$ $\mathcal { C}$ $2^{n-n^{{\varepsilon }}}$ ε > 0) implyQ u a s i -N P does not have$(f \circ \mathcal { C})$ # 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. -
more » « less
Abstract Approximate integer programming is the following: For a given convex body
$$K \subseteq {\mathbb {R}}^n$$ $$K \cap {\mathbb {Z}}^n$$ $$2\cdot (K - c) +c$$ K , scaled by 2 from its center of gravityc . Approximate integer programming can be solved in time$$2^{O(n)}$$ $$2^{O(n)} \cdot n^n$$ $$x^* \in (K \cap {\mathbb {Z}}^n)$$ $$2^{O(n)}$$ remainders of each component$$x_i^* \mod \ell $$ $$\ell \ge 5(n+1)$$ $$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$$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$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$ $$\prod _i O(\log u_i +1)$$ knapsack orsubset-sum problems withpolynomial variable range $$0 \le x_i \le p(n)$$ $$(\log n)^{O(n)}$$ $$n^n \cdot 2^{O(n)}$$ -
more » « less
Abstract In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include:
Certifying that a list of
n integers has no 3-SUM solution can be done in Merlin–Arthur time$$\tilde{O}(n)$$ $$\tilde{O}(n^{1.5})$$ $$\tilde{O}(n^{1.5})$$ $$\tilde{O}(n^{1.5})$$ Counting the number of
k -cliques with total edge weight equal to zero in ann -node graph can be done in Merlin–Arthur time$${\tilde{O}}(n^{\lceil k/2\rceil })$$ $$k\ge 3$$ k , this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm -edge graph can be done in Merlin–Arthur time$${\tilde{O}}(m)$$ k -cliques in unweighted graphs, and had worse running times for smallk .Computing the All-Pairs Shortest Distances matrix for an
n -node graph can be done in Merlin–Arthur time$$\tilde{O}(n^2)$$ $$\Omega (n^2)$$ $$\tilde{O}(n^{2.94})$$ Certifying that an
n -variablek -CNF is unsatisfiable can be done in Merlin–Arthur time$$2^{n/2 - n/O(k)}$$ $$2^{n/2}\cdot \textrm{poly}(n)$$ $$\#$$ k -UNSAT running in$$2^{n/2}/n^{\omega (1)}$$ Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time
$$2^{4n/5}\cdot \textrm{poly}(n)$$ $$2^{2n/3}\cdot \textrm{poly}(n)$$ n integers can be done in Merlin–Arthur time$$2^{n/3}\cdot \textrm{poly}(n)$$ $$2^{0.49991n}\cdot \textrm{poly}(n)$$ -
more » « less
Abstract Let
$$X\rightarrow {{\mathbb {P}}}^1$$ K 3 surface, admitting a sequence$$\omega _{i}$$ V be a holomorphicSU (n ) bundle overX , stable with respect to$$\omega _i$$ $$\Xi _i$$ V , we prove that, ifE is a generic fiber, the restricted sequence$$\Xi _i|_{E}$$ $$A_0$$ $$V|_E$$ $$\oplus _{j=1}^n{\mathcal {O}}_E(q_j-0)$$ n distinct points$$q_j\in E$$ $$A_0$$ -
more » « less
Abstract Finite volume, weighted essentially non-oscillatory (WENO) schemes require the computation of a smoothness indicator. This can be expensive, especially in multiple space dimensions. We consider the use of the simple smoothness indicator
$$\sigma ^{\textrm{S}}= \frac{1}{N_{\textrm{S}}-1}\sum _{j} ({\bar{u}}_{j} - {\bar{u}}_{m})^2$$ $$N_{\textrm{S}}$$ $${\bar{u}}_j$$ j , and indexm gives the target element. Reconstructions utilizing standard WENO weighting fail with this smoothness indicator. We develop a modification of WENO-Z weighting that gives a reliable and accurate reconstruction of adaptive order, which we denote as SWENOZ-AO. We prove that it attains the order of accuracy of the large stencil polynomial approximation when the solution is smooth, and drops to the order of the small stencil polynomial approximations when there is a jump discontinuity in the solution. Numerical examples in one and two space dimensions on general meshes verify the approximation properties of the reconstruction. They also show it to be about 10 times faster in two space dimensions than reconstructions using the classic smoothness indicator. The new reconstruction is applied to define finite volume schemes to approximate the solution of hyperbolic conservation laws. Numerical tests show results of the same quality as standard WENO schemes using the classic smoothness indicator, but with an overall speedup in the computation time of about 3.5–5 times in 2D tests. Moreover, the computational efficiency (CPU time versus error) is noticeably improved.
