Papers for

complexity theory tool builders

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Deterministic factorization algorithm for constant depth algebraic circuits

Deterministic factorization of constant depth circuits from whitebox PIT

Abstract: We show that over the field of rational numbers, there is a deterministic algorithm for factorization of constant depth circuits that makes calls to a (whitebox or blackbox) PIT algorithm for such circuits. The time complexity of the algorithm (and hence the number of calls to the PIT oracle) is polynomially bounded in the size and degree of the input circuit. Our reduction to PIT is fairly simple and general and applies as it is to other natural classes of algebraic circuits like formulas and algebraic branching programs. Prior to this work, the known deterministic factorization algorithms for constant depth circuits crucially relied on \emph{blackbox} PIT [Bhattacharjee et al.]. Our main technical ingredient is an efficient, deterministic algorithm that, when given access to sufficiently high degree truncations of \emph{all} the power series roots of a constant depth circuit, uses oracle calls to any (whitebox or blackbox) PIT algorithm for these circuits, and partitions the roots into the sets of conjugates; thereby identifying the irreducible factors. For our proof, we rely on a root recombination criterion using logarithmic derivatives [Sasaki et al., Bostan et al., Lecerf] and show that this criterion can be efficiently and deterministically implemented for power series roots of constant depth circuits using access to any PIT oracle. On the way, we discuss an algorithm that may be of independent interest: it takes as input a matrix whose entries are multivariate constant depth circuits over a field $\mathbb{F}$, requires oracle access to any PIT algorithm for these circuits and outputs a basis for the $\mathbb{F}$-kernel of this matrix in polynomial time.

Fri 6 NovComputational Complexity
The gist
Factoring complex math expressions written as constant depth circuits is often challenging, especially when you want a step-by-step, predictable method. The authors found a way to break down such expressions into simpler factors using an existing test that tells if these expressions equal zero, called PIT. Their method works over rational numbers and runs efficiently, making repeated calls to this test. Along the way, they introduce a tool that helps find dependencies in matrices made from these circuits, which may be useful beyond this work.
Open → 2611.09035v1

Parallel repetition causes fast decay in multi player xor games

Parallel Repetition for k-Player XOR Games

Abstract: In a $k$-XOR game $Ψ$ over $\mathbb{F}_p$, a verifier samples challenges $(x_1,\ldots,x_k)\simμ$ where $μ$ is a distribution over $Σ_1\times\ldots\times Σ_k$, sends $x_i$ to player $i$ and receives an answer $f_i(x_i)\in\mathbb{F}_p$, and accepts if and only if $f_1(x_1)+\ldots+f_k(x_k)=t(x_1,\ldots,x_k)$, where $t\colon Σ_1\times\ldots\times Σ_k\to\mathbb{F}_p$ is a fixed map. We show that if $Ψ$ has value strictly less than $1$, then the value of the $n$-fold repeated game $Ψ^{\otimes n}$ is at most $2^{-cn}$ where $c = c(Ψ)>0$ is a fixed constant. This extends a previous result of [Bhangale-Braverman-Khot-Liu-Minzer] showing exponential decay for some $3$-XOR games. Our proof uses a relaxation of the value of games studied in the quantum setting, called the commuting value of a game. We show a transformation that maps a $k$-player game $Ψ$ with value strictly less than $1$ to a $2k$-player game $Ψ'$ with commuting value less than $1$, such that $\mathsf{val}(Ψ^{\otimes n})\leq \mathsf{val}((Ψ')^{\otimes n})$. We prove that $\mathsf{val}(Ψ')<1$ has a direct proof using nothing more than the Cauchy-Schwarz inequality, which we are able to tensorize to get that $\mathsf{val}((Ψ')^{\otimes n})$ vanishes exponentially fast in $n$.

Wed 21 OctComputational Complexity
The gist
This paper studies multiplayer XOR games, where several players try to satisfy a mathematical condition by providing answers based on separate challenges. The authors show that when repeating these games many times in parallel, the chance of winning all rounds drops exponentially if the players cannot win perfectly. They use a new approach that links the original game to a related game easier to analyze with known techniques, leading to a clear proof that the winning probability decays quickly as the number of repetitions grows.
Open → 2610.30455v1

Certifiable near-optimal solutions unify search and refutation in random csp problems

Certifiable Near-Optimality: A Simple Framework for Unifying Search and Refutation for (Semi)random CSPs

Abstract: A classical problem in average-case complexity is the study of random constraint satisfaction problems (CSPs). Random CSPs are traditionally studied in two different settings: refutation, where the instances are uniformly random and thus unsatisfiable with high probability, and search, where the instances are drawn from a planted model so that they are satisfiable. While there is no formal relationship between the refutation and search variants of random CSPs, known algorithms are strikingly similar with near-identical computational thresholds. In this work, we establish a formal relationship between the known algorithms for refutation and search by showing that in either case they achieve a stronger guarantee: they output an assignment $x$ along with a certificate $π$ that the fraction of constraints satisfied by $x$ is within some small $\varepsilon$ of the optimal assignment. We call this guarantee certifiable $\varepsilon$-optimality. As an application, we design new algorithms for a model of semirandom CSPs where the instance hypergraph (or scopes) is random, but the literal negation patterns are adversarially chosen and may depend on the hypergraph. For such CSPs, we give a family of algorithms that output certifiably $\varepsilon$-optimal solutions. We additionally study such semirandom CSPs in the "strong contamination model", where an adversary is allowed to corrupt an $O(δ)$-fraction of constraints after seeing the initial CSP. For such CSPs, we give an algorithm to output a certifiably $O(δ)$-optimal solution.

Tue 29 SeptData Structures and Algorithms
The gist
Constraint satisfaction problems (CSPs) involve finding solutions that satisfy many rules or constraints. The paper studies two types of random CSPs: ones that are usually unsolvable and ones designed to have a hidden solution. The authors show that known algorithms for these problems actually produce solutions with a certificate proving the solution is nearly the best possible. They also design new algorithms that handle cases where some constraints have been tampered with, still ensuring nearly optimal and verifiable solutions.
Open → 2609.38367v1