More Like this

1. Extremely Deep Proofs

   https://doi.org/10.4230/LIPIcs.ITCS.2022.70  

   Fleming, Noah and (January 2022, Leibniz international proceedings in informatics)

   Braverman, Mark (Ed.)

   We further the study of supercritical tradeoffs in proof and circuit complexity, which is a type of tradeoff between complexity parameters where restricting one complexity parameter forces another to exceed its worst-case upper bound. In particular, we prove a new family of supercritical tradeoffs between depth and size for Resolution, Res(k), and Cutting Planes proofs. For each of these proof systems we construct, for each c ≤ n^{1-ε}, a formula with n^{O(c)} clauses and n variables that has a proof of size n^{O(c)} but in which any proof of size no more than roughly exponential in n^{1-ε}/c must necessarily have depth ≈ n^c. By setting c = o(n^{1-ε}) we therefore obtain exponential lower bounds on proof depth; this far exceeds the trivial worst-case upper bound of n. In doing so we give a simplified proof of a supercritical depth/width tradeoff for tree-like Resolution from [Alexander A. Razborov, 2016]. Finally, we outline several conjectures that would imply similar supercritical tradeoffs between size and depth in circuit complexity via lifting theorems. 

   more » « less
2. A Tight Bound for Stochastic Submodular Cover

   https://doi.org/10.1613/jair.1.12368  

   Hellerstein, Lisa; Kletenik, Devorah; Parthasarathy, Srinivasan (May 2021, Journal of Artificial Intelligence Research)

   null (Ed.)

   We show that the Adaptive Greedy algorithm of Golovin and Krause achieves an approximation bound of (ln(Q/η)+1) for Stochastic Submodular Cover: here Q is the “goal value” and η is the minimum gap between Q and any attainable utility value Q' 

   more » « less
3. Simple Analysis of Priority Sampling

   Daliri, Majid; Freire, Juliana; Musco, Christopher; Santos, Aécio; Zhang, Haoxiang (January 2024, SIAM Symposium on Simplicity in Algorithms)

   We prove a tight upper bound on the variance of the priority sampling method (aka sequential Poisson sampling). Our proof is significantly shorter and simpler than the original proof given by Mario Szegedy at STOC 2006, which resolved a conjecture by Duffield, Lund, and Thorup. 

   more » « less
4. Existence and analyticity of the Lei-Lin solution of the Navier-Stokes equations on the torus

   https://doi.org/10.1090/proc/16615  

   Ambrose, David; Lopes Filho, Milton; Nussenzveig Lopes, Helena (November 2023, Proceedings of the American Mathematical Society)

   Lei and Lin [Comm. Pure Appl. Math. 64 (2011), pp. 1297–1304] have recently given a proof of a global mild solution of the three-dimensional Navier-Stokes equations in function spaces based on the Wiener algebra. An alternative proof of existence of these solutions was then developed by Bae [Proc. Amer. Math. Soc. 143 (2015), pp. 2887–2892], and this new proof allowed for an estimate of the radius of analyticity of the solutions at positive times. We adapt the Bae proof to prove existence of the Lei-Lin solution in the spatially periodic setting, finding an improved bound for the radius of analyticity in this case. 

   more » « less
5. Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints

   https://doi.org/10.1145/3725233  

   Im, Sungjin; Moseley, Benjamin; Ngo, Hung; Pruhs, Kirk (June 2025, Proceedings of the ACM on Management of Data)

   Cardinality estimation and conjunctive query evaluation are two of the most fundamental problems in database query processing. Recent work proposed, studied, and implemented a robust and practical information-theoretic cardinality estimation framework. In this framework, the estimator is the cardinality upper bound of a conjunctive query subject to ''degree-constraints'', which model a rich set of input data statistics. For general degree constraints, computing this bound is computationally hard. Researchers have naturally sought efficiently computable relaxed upper bounds that are as tight as possible. The polymatroid bound is the tightest among those relaxed upper bounds. While it is an open question whether the polymatroid bound can be computed in polynomial-time in general, it is known to be computable in polynomial-time for some classes of degree constraints. Our focus is on a common class of degree constraints called simple degree constraints. Researchers had not previously determined how to compute the polymatroid bound in polynomial time for this class of constraints. Our first main result is a polynomial time algorithm to compute the polymatroid bound given simple degree constraints. Our second main result is a polynomial-time algorithm to compute a ''proof sequence'' establishing this bound. This proof sequence can then be incorporated in the PANDA-framework to give a faster algorithm to evaluate a conjunctive query. In addition, we show computational limitations to extending our results to broader classes of degree constraints. Finally, our technique leads naturally to a new relaxed upper bound called theflow bound,which is computationally tractable. 

   more » « less