Article
Computer Science, Theory & Methods
Ben Lee Volk, Mrinal Kumar
Summary: The study addresses the construction of explicit families of matrices that cannot be expressed as a product of sparse matrices, presenting a deterministic construction method and improving lower bounds at the cost of increased time complexity. This work demonstrates the potential for achieving asymptotically optimal quadratic lower bounds for certain natural cases.
COMPUTATIONAL COMPLEXITY
(2021)
Article
Computer Science, Software Engineering
Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, Blake Woodworth
Summary: In this work, we establish lower bounds on the complexity of finding epsilon-stationary points using stochastic first-order methods. We prove that any algorithm accessing smooth, potentially non-convex functions through queries to an unbiased stochastic gradient oracle with bounded variance requires at least epsilon(-4) queries to find an epsilon-stationary point in the worst case. The tightness of the lower bound establishes the minimax optimality of stochastic gradient descent in this model. In a stricter model where the noisy gradient estimates satisfy a mean-squared smoothness property, we further prove a lower bound of epsilon(-3) queries, establishing the optimality of recently proposed variance reduction techniques.
MATHEMATICAL PROGRAMMING
(2023)
Article
Mathematics
Benjamin E. Diamond, Amir Yehudayoff
Summary: We describe an explicit and simple subset of the discrete hypercube that cannot be exactly covered by a number of hyperplanes that is less than exponential. The proof exploits a connection to communication complexity and heavily relies on Razborov's lower bound for disjointness.
DISCRETE MATHEMATICS
(2022)
Article
Quantum Science & Technology
Abderraman Amr, Ignacio Villanueva
Summary: This work provides an example of exponential separation between quantum and classical resources in XOR games assisted with communication. Specifically, it shows that O(n) bits of two-way classical communication are required to achieve the same value as can be attained with log n qubits of one-way communication in a XOR game. It also characterizes the value of a XOR game assisted with limited two-way communication in terms of tensor norms of normed spaces.
QUANTUM INFORMATION PROCESSING
(2021)
Article
Automation & Control Systems
Rishabh Dudeja, Daniel Hsu
Summary: In the study of the Tensor PCA problem within the Statistical Query model, a sharp analysis was conducted on the optimal sample complexity. It was found that for symmetric even-order tensors, it is possible to test if ET1 = 0 or ET1 ≠ 0 with polynomially many queries, but not estimate ET1.
JOURNAL OF MACHINE LEARNING RESEARCH
(2021)
Article
Computer Science, Theory & Methods
Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan
Summary: This work explores the conditional disclosure of secrets problem and introduces CDS manipulation techniques, yielding both positive and negative results. These include the concept of closure by transforming a CDS for a predicate into its complement, and amplification to reduce privacy and correctness error of a CDS. Additionally, the notion of amortization is introduced to linearly increase communication complexity per secret bit with input length.
SIAM JOURNAL ON COMPUTING
(2021)
Article
Mathematics
Gioacchino Antonelli, Enrico Pasqualetto, Marco Pozzetta, Daniele Semola
Summary: This paper studies sharp and rigid isoperimetric comparison theorems and asymptotic isoperimetric properties for small and large volumes on N-dimensional RCD(K, N) spaces (X, d, H-N). Moreover, we obtain almost regularity theorems formulated in terms of the isoperimetric profile and enhanced consequences at the level of several functional inequalities. Most of our statements seem to be new even in the classical setting of smooth, non compact manifolds with lower Ricci curvature bounds. The synthetic theory plays a key role via compactness and stability arguments.
MATHEMATISCHE ANNALEN
(2023)
Article
Computer Science, Theory & Methods
Alexander A. Sherstov, Pei Wu
Summary: The threshold degree and sign-rank of Boolean functions and matrices are important open problems with various applications. This study provides a significant breakthrough by introducing an optimal solution for determining the maximum threshold degree and sign-rank achievable by constant-depth circuits. The results improve upon previous lower bounds and subsume previous work on related quantities.
SIAM JOURNAL ON COMPUTING
(2023)
Article
Computer Science, Theory & Methods
Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
Summary: This study shows that weakly exponential size linear programming relaxations for constraint satisfaction problems (CSPs) are as powerful as the explicit linear program of the Sherali-Adams linear programming hierarchy. By combining with known lower bounds, subexponential size lower bounds for linear programming relaxations are obtained, which surpass random guessing for many CSPs.
SIAM JOURNAL ON COMPUTING
(2022)
Article
Mathematics, Applied
Gioacchino Antonelli, Enrico Pasqualetto, Marco Pozzetta
Summary: This paper studies the regularity and topological properties of volume constrained minimizers of quasi-perimeters in RCD spaces. The authors prove that under certain conditions, the minimizers of quasi-perimeters have specific geometric and topological properties, such as being open bounded sets with a specific boundary.
NONLINEAR ANALYSIS-THEORY METHODS & APPLICATIONS
(2022)
Article
Computer Science, Software Engineering
Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman
Summary: This paper introduces the applications and recent advances of robust sunflowers, and obtains lower bounds on the circuit size of monotone functions using these results.
Article
Computer Science, Theory & Methods
Aicke Hinrichs, David Krieg, Erich Novak, Jan Vybiral
Summary: Function values are almost as informative as general linear information for L2-approximation of functions, and this paper mainly focuses on proving new lower bounds for this behavior. It is shown that sampling numbers can behave worse than approximation numbers, especially for Sobolev spaces with low smoothness. Additionally, new lower bounds for the integration problem are proven.
JOURNAL OF COMPLEXITY
(2022)
Article
Computer Science, Software Engineering
Yuyuan Ouyang, Yangyang Xu
Summary: This paper explores the lower complexity bounds of first-order methods on large-scale convex-concave bilinear saddle-point problems (SPP). The study shows that first-order methods on affinely constrained problems generally cannot be accelerated to a higher convergence rate than O(1/t) for convex problems, and O(1/t²) is the best possible convergence rate for strongly convex problems. The lower complexity bounds match with established upper complexity bounds in the literature, indicating the optimality of existing first-order methods.
MATHEMATICAL PROGRAMMING
(2021)
Article
Mathematics, Applied
Anton Freund, Ulrich Kohlenbach
Summary: We extract quantitative information from a proof by Kazuo Kobayasi and Isao Miyadera, which demonstrates strong convergence for Cesaro means of non-expansive maps on Banach spaces.
ERGODIC THEORY AND DYNAMICAL SYSTEMS
(2023)
Article
Computer Science, Theory & Methods
Aicke Hinrichs, David Krieg, Erich Novak, Jan Vybiral
Summary: We investigate the lower bounds for the worst case error of quadrature formulas using given sample points, focusing on optimal point sets and independently and uniformly distributed points. By utilizing recent results on the positive semi-definiteness of certain matrices related to the product theorem of Schur by Vybiral, our new technique extends to spaces of analytic functions where traditional methods are not applicable.
JOURNAL OF COMPLEXITY
(2021)