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. A folding preprocess for the max k-cut problem

   https://doi.org/10.1007/s11590-025-02199-0  

   Fakhimi, Ramin; Validi, Hamidreza; Hicks, Illya_V; Terlaky, Tamás; Zuluaga, Luis_F (April 2025, Optimization Letters)

   Abstract Given graph$$G=(V,E)$$ $G=(V,E)$with vertex setVand edge setE, the maxk-cut problem seeks to partition the vertex setVinto at mostksubsets that maximize the weight (number) of edges with endpoints in different parts. This paper proposes a graph folding procedure (i.e., a procedure that reduces the number of the vertices and edges of graphG) for the weighted maxk-cut problem that may help reduce the problem’s dimensionality. While our theoretical results hold for any$$k \ge 2$$ $k\ge 2$, our computational results show the effectiveness of the proposed preprocessonlyfor$$k=2$$ $k=2$and on two sets of instances. Furthermore, we observe that the preprocess improves the performance of a MIP solver on a set of large-scale instances of the max cut problem. 

   more » « less
3. Streaming approximation resistance of every ordering CSP

   https://doi.org/10.1007/s00037-024-00252-5  

   Singer, Noah G; Sudan, Madhu; Velusamy, Santhoshini (June 2024, computational complexity)

   Abstract An ordering constraint satisfaction problem (OCSP) is defined by a family$$\mathcal F$$ $F$of predicates mapping permutations on$$\{1,\ldots,k\}$$ $\{1,\dots ,k\}$to$$\{0,1\}$$ $\{0,1\}$. An instance of ($$\mathcal F$$ $F$) onnvariables consists of a list of constraints, each consisting of a predicate from$$\mathcal F$$ $F$applied onkdistinct variables. The goal is to find an ordering of thenvariables that maximizes the number of constraints for which the induced ordering on thekvariables satisfies the predicate. OCSPs capture well-studied problems including ‘maximum acyclic subgraph’ () and “maximum betweenness”. In this work, we consider the task of approximating the maximum number of satisfiable constraints in the (single-pass) streaming setting, when an instance is presented as a stream of constraints. We show that for every$$\mathcal F$$ $F$, ($$\mathcal F$$ $F$) is approximation-resistant to o(n)-space streaming algorithms, i.e., algorithms using o(n) space cannot distinguish streams where almost every constraint is satisfiable from streams where no ordering beats the random ordering by a noticeable amount. This space bound is tight up to polylogarithmic factors. In the case of , our result shows that for every$$\epsilon>0$$ $ϵ>0$, is not$$(1/2+\epsilon)$$ $(1/2+ϵ)$-approximable in o(n) space. The previous best inapproximability result, due to Guruswami & Tao (2019), only ruled out 3/4-approximations in$$o(\sqrt n)$$ $o\left(\sqrt{n}\right)$space. Our results build on recent works of Chou et al. (2022b, 2024) who provide a tight, linear-space inapproximability theorem for a broad class of “standard” (i.e., non-ordering) constraint satisfaction problems (CSPs) over arbitrary (finite) alphabets. Our results are obtained by building a family of appropriate standard CSPs (one for every alphabet sizeq) from any given OCSP and applying their theorem to this family of CSPs. To convert the resulting hardness results for standard CSPs back to our OCSP, we show that the hard instances from this earlier theorem have the following “partition expansion” property with high probability: For every partition of thenvariables into small blocks, for most of the constraints, all variables are in distinct blocks. 

   more » « less
4. Inexact Fixed-Point Proximity Algorithm for the $$\ell _0$$ Sparse Regularization Problem

   https://doi.org/10.1007/s10915-024-02600-7  

   Fang, Ronglong; Xu, Yuesheng; Yan, Mingsong (July 2024, Journal of Scientific Computing)

   Abstract We studyinexactfixed-point proximity algorithms for solving a class of sparse regularization problems involving the$$\ell _0$$ ${\ell }_0$norm. Specifically, the$$\ell _0$$ ${\ell }_0$model has an objective function that is the sum of a convex fidelity term and a Moreau envelope of the$$\ell _0$$ ${\ell }_0$norm regularization term. Such an$$\ell _0$$ ${\ell }_0$model is non-convex. Existing exact algorithms for solving the problems require the availability of closed-form formulas for the proximity operator of convex functions involved in the objective function. When such formulas are not available, numerical computation of the proximity operator becomes inevitable. This leads to inexact iteration algorithms. We investigate in this paper how the numerical error for every step of the iteration should be controlled to ensure global convergence of the inexact algorithms. We establish a theoretical result that guarantees the sequence generated by the proposed inexact algorithm converges to a local minimizer of the optimization problem. We implement the proposed algorithms for three applications of practical importance in machine learning and image science, which include regression, classification, and image deblurring. The numerical results demonstrate the convergence of the proposed algorithm and confirm that local minimizers of the$$\ell _0$$ ${\ell }_0$models found by the proposed inexact algorithm outperform global minimizers of the corresponding$$\ell _1$$ ${\ell }_1$models, in terms of approximation accuracy and sparsity of the solutions. 

   more » « less
5. $$ \mathcal{N} $$ = 2 JT supergravity and matrix models

   https://doi.org/10.1007/JHEP12(2023)003  

   Turiaci, Gustavo J.; Witten, Edward (December 2023, Journal of High Energy Physics)

   A<sc>bstract</sc> Generalizing previous results for$$ \mathcal{N} $$ $N$= 0 and$$ \mathcal{N} $$ $N$= 1, we analyze$$ \mathcal{N} $$ $N$= 2 JT supergravity on asymptotically AdS₂spaces with arbitrary topology and show that this theory of gravity is dual, in a holographic sense, to a certain random matrix ensemble in which supermultiplets of differentR-charge are statistically independent and each is described by its own$$ \mathcal{N} $$ $N$= 2 random matrix ensemble. We also analyze the case with a time-reversal symmetry, either commuting or anticommuting with theR-charge. In order to compare supergravity to random matrix theory, we develop an$$ \mathcal{N} $$ $N$= 2 analog of the recursion relations for Weil-Petersson volumes originally discovered by Mirzakhani in the bosonic case. 

   more » « less