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)

   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$$\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
2. Abelian varieties of prescribed order over finite fields

   https://doi.org/10.1007/s00208-024-03084-4  

   van_Bommel, Raymond; Costa, Edgar; Li, Wanlin; Poonen, Bjorn; Smith, Alexander (March 2025, Mathematische Annalen)

   Abstract Given a prime powerqand$$n \gg 1$$ $n\gg 1$, we prove that every integer in a large subinterval of the Hasse–Weil interval$$[(\sqrt{q}-1)^{2n},(\sqrt{q}+1)^{2n}]$$ $[{(\sqrt{q}-1)}^{2n},{(\sqrt{q}+1)}^{2n}]$is$$\#A({\mathbb {F}}_q)$$ $\#A\left(F_q\right)$for some ordinary geometrically simple principally polarized abelian varietyAof dimensionnover$${\mathbb {F}}_q$$ $F_q$. As a consequence, we generalize a result of Howe and Kedlaya for$${\mathbb {F}}_2$$ $F_2$to show that for each prime powerq, every sufficiently large positive integer is realizable, i.e.,$$\#A({\mathbb {F}}_q)$$ $\#A\left(F_q\right)$for some abelian varietyAover$${\mathbb {F}}_q$$ $F_q$. Our result also improves upon the best known constructions of sequences of simple abelian varieties with point counts towards the extremes of the Hasse–Weil interval. A separate argument determines, for fixedn, the largest subinterval of the Hasse–Weil interval consisting of realizable integers, asymptotically as$$q \rightarrow \infty $$ $q\to \infty$; this gives an asymptotically optimal improvement of a 1998 theorem of DiPippo and Howe. Our methods are effective: We prove that if$$q \le 5$$ $q\le 5$, then every positive integer is realizable, and for arbitraryq, every positive integer$$\ge q^{3 \sqrt{q} \log q}$$ $\ge q^{3\sqrt{q}logq}$is realizable. 

   more » « less
3. L-Systems and the Lovász Number

   https://doi.org/10.1007/s00493-025-00136-4  

   Linz, William (April 2025, Combinatorica)

   Abstract Given integers$$n> k > 0$$ $n>k>0$, and a set of integers$$L \subset [0, k-1]$$ $L\subset [0,k-1]$, anL-systemis a family of sets$$\mathcal {F}\subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) $$ $F\subset \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$such that$$|F \cap F'| \in L$$ $|F\cap F^{\prime }|\in L$for distinct$$F, F'\in \mathcal {F}$$ $F,F^{\prime }\in F$.L-systems correspond to independent sets in a certain generalized Johnson graphG(n, k, L), so that the maximum size of anL-system is equivalent to finding the independence number of the graphG(n, k, L). TheLovász number$$\vartheta (G)$$ $\vartheta \left(G\right)$is a semidefinite programming approximation of the independence number$$\alpha $$ $\alpha$of a graphG. In this paper, we determine the leading order term of$$\vartheta (G(n, k, L))$$ $\vartheta \left(G\right(n,k,L\left)\right)$of any generalized Johnson graph withkandLfixed and$$n\rightarrow \infty $$ $n\to \infty$. As an application of this theorem, we give an explicit construction of a graphGonnvertices with a large gap between the Lovász number and the Shannon capacityc(G). Specifically, we prove that for any$$\epsilon > 0$$ $ϵ>0$, for infinitely manynthere is a generalized Johnson graphGonnvertices which has ratio$$\vartheta (G)/c(G) = \Omega (n^{1-\epsilon })$$ $\vartheta \left(G\right)/c\left(G\right)=\Omega \left(n^{1-ϵ}\right)$, which improves on all known constructions. The graphGa fortiorialso has ratio$$\vartheta (G)/\alpha (G) = \Omega (n^{1-\epsilon })$$ $\vartheta \left(G\right)/\alpha \left(G\right)=\Omega \left(n^{1-ϵ}\right)$, which greatly improves on the best known explicit construction. 

   more » « less
4. Surface Houghton groups

   https://doi.org/10.1007/s00208-023-02751-2  

   Aramayona, Javier; Bux, Kai-Uwe; Kim, Heejoung; Leininger, Christopher J. (November 2023, Mathematische Annalen)

   Abstract For every$$n\ge 2$$ $n\ge 2$, thesurface Houghton group$${\mathcal {B}}_n$$ $B_n$is defined as the asymptotically rigid mapping class group of a surface with exactlynends, all of them non-planar. The groups$${\mathcal {B}}_n$$ $B_n$are analogous to, and in fact contain, the braided Houghton groups. These groups also arise naturally in topology: every monodromy homeomorphism of a fibered component of a depth-1 foliation of closed 3-manifold is conjugate into some$${\mathcal {B}}_n$$ $B_n$. As countable mapping class groups of infinite type surfaces, the groups$$\mathcal {B}_n$$ $B_n$lie somewhere between classical mapping class groups and big mapping class groups. We initiate the study of surface Houghton groups proving, among other things, that$$\mathcal {B}_n$$ $B_n$is of type$$\text {F}_{n-1}$$ ${\text{F}}_{n-1}$, but not of type$$\text {FP}_{n}$$ ${\text{FP}}_n$, analogous to the braided Houghton groups. 

   more » « less
5. An Efficient ZK Compiler from SIMD Circuits to General Circuits

   https://doi.org/10.1007/s00145-024-09531-4  

   Bui, Dung; Chu, Haotian; Couteau, Geoffroy; Wang, Xiao; Weng, Chenkai; Yang, Kang; Yu, Yu (January 2025, Journal of Cryptology)

   Abstract We propose a generic compiler that can convert any zero-knowledge (ZK) proof for SIMD circuits to general circuits efficiently, and an extension that can preserve the space complexity of the proof systems. Our compiler can immediately produce new results improving upon state of the art.By plugging in our compiler to Antman, an interactive sublinear-communication protocol, we improve the overall communication complexity for general circuits from$$\mathcal {O}(C^{3/4})$$ $O\left(C^{3/4}\right)$to$$\mathcal {O}(C^{1/2})$$ $O\left(C^{1/2}\right)$. Our implementation shows that for a circuit of size$$2^{27}$$ $2^{27}$, it achieves up to$$83.6\times $$ $83.6\times$improvement on communication compared to the state-of-the-art implementation. Its end-to-end running time is at least$$70\%$$ $70\%$faster in a 10Mbps network.Using the recent results on compressed$$\varSigma $$ $\Sigma$-protocol theory, we obtain a discrete-log-based constant-round zero-knowledge argument with$$\mathcal {O}(C^{1/2})$$ $O\left(C^{1/2}\right)$communication and common random string length, improving over the state of the art that has linear-size common random string and requires heavier computation.We improve the communication of a designatedn-verifier zero-knowledge proof from$$\mathcal {O}(nC/B+n^2B^2)$$ $O(nC/B+n^2{B}^2)$to$$\mathcal {O}(nC/B+n^2)$$ $O(nC/B+n^2)$.To demonstrate the scalability of our compilers, we were able to extract a commit-and-prove SIMD ZK from Ligero and cast it in our framework. We also give one instantiation derived from LegoSNARK, demonstrating that the idea of CP-SNARK also fits in our methodology. 

   more » « less