More Like this

1. 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 polynomialmore »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.

   « less
2. 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.
3. The structure of the singular set in the thin obstacle problem for degenerate parabolic equations

   https://doi.org/10.1007/s00526-021-01938-2  

   Banerjee, Agnid ; Danielli, Donatella ; Garofalo, Nicola ; Petrosyan, Arshak ( April 2021 , Calculus of Variations and Partial Differential Equations)

   We study the singular set in the thin obstacle problem for degenerate parabolic equations with weight$$|y|^a$$${\left|y\right|}^a$for$$a \in (-1,1)$$$a\in (-1,1)$. Such problem arises as the local extension of the obstacle problem for the fractional heat operator$$(\partial _t - \Delta _x)^s$$${({\partial }_t-{\Delta }_x)}^s$for$$s \in (0,1)$$$s\in (0,1)$. Our main result establishes the complete structure and regularity of the singular set of the free boundary. To achieve it, we prove Almgren-Poon, Weiss, and Monneau type monotonicity formulas which generalize those for the case of the heat equation ($$a=0$$$a=0$).
4. The relativistic Euler equations with a physical vacuum boundary: Hadamard local well-posedness, rough solutions, and continuation criterion

   https://doi.org/10.1007/s00205-022-01783-3  

   Disconzi, Marcelo M. ; Ifrim, Mihaela ; Tataru, Daniel ( May 2022 , Archive for Rational Mechanics and Analysis)

   In this paper we provide a complete local well-posedness theory for the free boundary relativistic Euler equations with a physical vacuum boundary on a Minkowski background. Specifically, we establish the following results: (i) local well-posedness in the Hadamard sense, i.e., local existence, uniqueness, and continuous dependence on the data; (ii) low regularity solutions: our uniqueness result holds at the level of Lipschitz velocity and density, while our rough solutions, obtained as unique limits of smooth solutions, have regularity only a half derivative above scaling; (iii) stability: our uniqueness in fact follows from a more general result, namely, we show that a certain nonlinear functional that tracks the distance between two solutions (in part by measuring the distance between their respective boundaries) is propagated by the flow; (iv) we establish sharp, essentially scale invariant energy estimates for solutions; (v) a sharp continuation criterion, at the level of scaling, showing that solutions can be continued as long as the velocity is in$$L^1_t Lip$$$L_t^{1}Lip$and a suitable weighted version of the density is at the same regularity level. Our entire approach is in Eulerian coordinates and relies on the functional framework developed in the companion work of the second and third authors onmore »corresponding non relativistic problem. All our results are valid for a general equation of state$$p(\varrho )= \varrho ^\gamma $$$p\left(\varrho \right)={\varrho }^{\gamma }$,$$\gamma > 1$$$\gamma >1$.

   « less
5. Sparse representation of vectors in lattices and semigroups

   https://doi.org/10.1007/s10107-021-01657-8  

   Aliev, Iskander ; Averkov, Gennadiy ; De Loera, Jesús A. ; Oertel, Timm ( May 2021 , Mathematical Programming)

   We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the$$\ell _0$$${\ell }_0$-norm of the vector. Our main results are new improved bounds on the minimal$$\ell _0$$${\ell }_0$-norm of solutions to systems$$A\varvec{x}=\varvec{b}$$$Ax=b$, where$$A\in \mathbb {Z}^{m\times n}$$$A\in Z^{m\times n}$,$${\varvec{b}}\in \mathbb {Z}^m$$$b\in Z^m$and$$\varvec{x}$$$x$is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with$$\ell _0$$${\ell }_0$-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$$\mathbb {R}$$$R$, to other subdomains such as$$\mathbb {Z}$$$Z$. We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.