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 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. Algorithms for covering multiple submodular constraints and applications

   https://doi.org/10.1007/s10878-022-00874-x  

   Chekuri, Chandra ; Inamdar, Tanmay ; Quanrud, Kent ; Varadarajan, Kasturi ; Zhang, Zhao ( June 2022 , Journal of Combinatorial Optimization)

   We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$$w:N\to R_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$$f_1,f_2,\dots ,f_r$overNand requirements$$k_1,k_2,\ldots ,k_r$$$k_1,k_2,\dots ,k_r$the goal is to find a minimum weight subset$$S \subseteq N$$$S\subseteq N$such that$$f_i(S) \ge k_i$$$f_i\left(S\right)\ge k_i$for$$1 \le i \le r$$$1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$$r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$$O(log(kr\left)\right)$approximation where$$k = \sum _i k_i$$$k={\sum }_i{k}_i$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$$(1-1/e-\epsilon )$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$$O(\frac{1}{ϵ}logr)$in the cost. Second, we consider the special case when each$$f_i$$$f_i$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems.

    

   more » « less
3. On the rigorous derivation of the incompressible Euler equation from Newton’s second law

   https://doi.org/10.1007/s11005-023-01630-w  

   Rosenzweig, Matthew ( January 2023 , Letters in Mathematical Physics)

   A long-standing problem in mathematical physics is the rigorous derivation of the incompressible Euler equation from Newtonian mechanics. Recently, Han-Kwan and Iacobelli (Proc Am Math Soc 149:3045–3061, 2021) showed that in the monokinetic regime, one can directly obtain the Euler equation from a system ofNparticles interacting in$${\mathbb {T}}^d$$$T^d$,$$d\ge 2$$$d\ge 2$, via Newton’s second law through asupercritical mean-field limit. Namely, the coupling constant$$\lambda $$$\lambda$in front of the pair potential, which is Coulombic, scales like$$N^{-\theta }$$$N^{-\theta }$for some$$\theta \in (0,1)$$$\theta \in (0,1)$, in contrast to the usual mean-field scaling$$\lambda \sim N^{-1}$$$\lambda \sim N^{-1}$. Assuming$$\theta \in (1-\frac{2}{d(d+1)},1)$$$\theta \in (1-\frac{2}{d(d+1)},1)$, they showed that the empirical measure of the system is effectively described by the solution to the Euler equation as$$N\rightarrow \infty $$$N\to \infty$. Han-Kwan and Iacobelli asked if their range for$$\theta $$$\theta$was optimal. We answer this question in the negative by showing the validity of the incompressible Euler equation in the limit$$N\rightarrow \infty $$$N\to \infty$for$$\theta \in (1-\frac{2}{d},1)$$$\theta \in (1-\frac{2}{d},1)$. Our proof is based on Serfaty’s modulated-energy method, but compared to that of Han-Kwan and Iacobelli, crucially uses an improved “renormalized commutator” estimate to obtain the larger range for$$\theta $$$\theta$. Additionally, we show that for$$\theta \le 1-\frac{2}{d}$$$\theta \le 1-\frac{2}{d}$, one cannot, in general, expect convergence in the modulated energy notion of distance.

    

   more » « less
4. The Brown measure of the free multiplicative Brownian motion

   https://doi.org/10.1007/s00440-022-01142-z  

   Driver, Bruce K. ; Hall, Brian ; Kemp, Todd ( October 2022 , Probability Theory and Related Fields)

   The free multiplicative Brownian motion$$b_{t}$$$b_t$is the large-Nlimit of the Brownian motion on$$\mathsf {GL}(N;\mathbb {C}),$$$\mathrm{GL}(N;C),$in the sense of$$*$$$\ast$-distributions. The natural candidate for the large-Nlimit of the empirical distribution of eigenvalues is thus the Brown measure of$$b_{t}$$$b_t$. In previous work, the second and third authors showed that this Brown measure is supported in the closure of a region$$\Sigma _{t}$$${\Sigma }_t$that appeared in the work of Biane. In the present paper, we compute the Brown measure completely. It has a continuous density$$W_{t}$$$W_t$on$$\overline{\Sigma }_{t},$$${\overline{\Sigma }}_t,$which is strictly positive and real analytic on$$\Sigma _{t}$$${\Sigma }_t$. This density has a simple form in polar coordinates:$$\begin{aligned} W_{t}(r,\theta )=\frac{1}{r^{2}}w_{t}(\theta ), \end{aligned}$$$\begin{array}{c}{W}_t(r,\theta )=\frac{1}{r^2}{w}_t\left(\theta \right),\end{array}$where$$w_{t}$$$w_t$is an analytic function determined by the geometry of the region$$\Sigma _{t}$$${\Sigma }_t$. We show also that the spectral measure of free unitary Brownian motion$$u_{t}$$$u_t$is a “shadow” of the Brown measure of$$b_{t}$$$b_t$, precisely mirroring the relationship between the circular and semicircular laws. We develop several new methods, based on stochastic differential equations and PDE, to prove these results.

    

   more » « less
5. Softmax policy gradient methods can take exponential time to converge

   https://doi.org/10.1007/s10107-022-01920-6  

   Li, Gen ; Wei, Yuting ; Chi, Yuejie ; Chen, Yuxin ( January 2023 , Mathematical Programming)

   The softmax policy gradient (PG) method, which performs gradient ascent under softmax policy parameterization, is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. For$$\gamma $$$\gamma$-discounted infinite-horizon tabular Markov decision processes (MDPs), remarkable progress has recently been achieved towards establishing global convergence of softmax PG methods in finding a near-optimal policy. However, prior results fall short of delineating clear dependencies of convergence rates on salient parameters such as the cardinality of the state space$${\mathcal {S}}$$$S$and the effective horizon$$\frac{1}{1-\gamma }$$$\frac{1}{1-\gamma }$, both of which could be excessively large. In this paper, we deliver a pessimistic message regarding the iteration complexity of softmax PG methods, despite assuming access to exact gradient computation. Specifically, we demonstrate that the softmax PG method with stepsize$$\eta $$$\eta$can take$$\begin{aligned} \frac{1}{\eta } |{\mathcal {S}}|^{2^{\Omega \big (\frac{1}{1-\gamma }\big )}} ~\text {iterations} \end{aligned}$$$\begin{array}{c}\frac{1}{\eta }{\left|S\right|}^{2^{\Omega (\frac{1}{1-\gamma })}}\text{iterations}\end{array}$to converge, even in the presence of a benign policy initialization and an initial state distribution amenable to exploration (so that the distribution mismatch coefficient is not exceedingly large). This is accomplished by characterizing the algorithmic dynamics over a carefully-constructed MDP containing only three actions. Our exponential lower bound hints at the necessity of carefully adjusting update rules or enforcing proper regularization in accelerating PG methods.

    

   more » « less