computational complexity
Издатель: Springer Nature · ISSN 1016-3328,1420-8954 · 33 статей
-
Space-bounded quantum state testing via space-efficient quantum singular value transformation
Abstract Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-bounded quantum computation, which encompasses settings with one-sided error (unitary...
-
On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups
Abstract We study the complexity of isomorphism problems for tensors, represented in coordinates by multiway arrays, under natural actions by classical groups such as orthogonal, unitary, and symplectic groups. These problems arise...
-
A Technique for Hardness Amplification Against $$\textsf{AC}^0$$
Abstract To show that a function h is hard to approximate for $$\textsf{AC}^0$$ AC 0 circuits, one method is to (a) design some distribution over random restrictions or random projections, (b) show that $$\textsf{AC}^0$$ AC 0 circuits...
- Special Issue “Computational Complexity Conference 2023” Guest Editors’ Foreword
-
Baby PIH: Parameterized Inapproximability of Min CSP
Abstract The Parameterized Inapproximability Hypothesis (PIH) is the analog of the PCP theorem in the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a satisfiable 2CSP instance from one which is only...
- On the Composition of Randomized Query Complexity and Approximate Degree
-
Tensor reconstruction beyond constant rank
Abstract We give reconstruction algorithms for subclasses of depth-3 arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank and an optimal tensor decomposition as a sum of rank-one tensors,...
- On the Existence of Algebraic Natural Proofs
-
From amortized to worst case delay in enumeration algorithms
Abstract The quality of enumeration algorithms is often measured by their delay, that is, the maximum time spent between the output of two distinct solutions. If the goal is to enumerate t distinct solutions for any given t , another...
-
On Approximate Symmetric Polynomials and Tightness of Homogenization Results
Abstract Motivated by questions concerning the multilinear and homogeneous complexity of the elementary symmetric polynomials, we prove the following results: We first show that by making small modifications to the nonzero coefficients...
- A strong direct sum theorem for distributional query complexity
- Towards Optimal Depth-Reductions for Algebraic Formulas
- Tight Quantum Lower Bound for Approximate Counting with Quantum States
-
Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
Abstract Littlewood-Richardson, Kronecker and plethysm coefficients are fundamental multiplicities of interest in Representation Theory and Algebraic Combinatorics. Determining a combinatorial interpretation for the Kronecker and...
- Pseudo-Deterministic Query Complexity of Search Problems
-
On a Hierarchy of Spectral Isomorphism Invariants
Abstract We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by Fürer (Lin. Alg. Appl. 2010) based on the angles formed by the set of standard basis vectors and their projections onto...
-
Lifting Dichotomies
Abstract Lifting theorems are used to transfer lower bounds between Boolean function complexity measures. Given a lower bound on a complexity measure $$A$$ A for some function $$f$$ f , we compose $$f$$ f with a carefully chosen gadget...
- Separation of the Factorization Norm and Randomized Communication Complexity
-
Quantum Automating TC0-Frege Is LWE-Hard
Abstract We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weakly...
-
Instance-Wise Hardness and Refutation versus Derandomization for Arthur-Merlin Protocols
Abstract A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the...
- An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
-
Derandomizing Logspace With a Small Shared Hard Drive
Abstract We obtain new catalytic algorithms for space-bounded derandomization. In the catalytic computation model introduced by (Buhrman, Cleve, Koucký, Loff, and Speelman STOC 2013), we are given a small worktape, and a larger...
-
Tractable Unordered 3-CNF Games
Abstract The classic TQBF problem can be viewed as a game in which two players alternate turns assigning truth values to a CNF formula's variables in a prescribed order, and the winner is determined by whether the CNF gets satisfied....
-
Quantum state testing beyond the polarizing regime and quantum triangular discrimination
Abstract The complexity class Quantum Statistical Zero-Knowledge captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, deciding whether $$\textrm{T}(\rho_0,\rho_1)$$ T...
- On Efficient Noncommutative Polynomial Factorization via Higman Linearization
-
Hard submatrices for non-negative rank and communication complexity
Abstract Given a non-negative real matrix M of non-negative rank at least r , can we witness this fact by a small submatrix of M ? While Moitra (SIAM J. Comput. 2013) proved that this cannot be achieved exactly, we show that such a...
-
On approximability of Satisfiable $$k$$-CSPs: I
Abstract We consider the $$P$$ P -CSP problem for 3-ary predicates $$P$$ P on satisfiable instances. We show that under certain conditions on $$P$$ P and a $$(1,s)$$ ( 1 , s ) integrality gap instance of the $$P$$ P -CSP problem, it can...
- On Solving Sparse Polynomial Factorization Related Problems
-
Learning algorithms from circuit lower bounds
Abstract We revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds such as distinguishers breaking pseudorandom generators or efficient witnessing algorithms which find...
-
Barriers for rectangular matrix multiplication
Abstract We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give algorithms...