Schloss Dagstuhl – Leibniz Center for Informatics
DROPS Dagstuhl Research Online Publication ServerNot a member yet
23028 research outputs found
Sort by
Unifying Boolean and Algebraic Descriptive Complexity
Full text linkWe introduce ultrarings, which simultaneously generalize commutative rings and Boolean lextensive categories. As such, they allow to blend together standard algebraic notions (from commutative algebra) and logical notions (from categorical logic), providing a unifying descriptive framework in which complexity classes over arbitrary rings (as in the Blum, Schub, Smale model) and usual, Boolean complexity classes may be captured in a uniform way
Engineering Insights into Biclique Partitions and Fractional Binary Ranks of Matrices
Full text linkWe investigate structural properties of the binary rank of Kronecker powers of binary matrices, equivalently, the biclique partition numbers of the corresponding bipartite graphs. To this end, we engineer a Column Generation approach to solve linear optimization problems for the fractional biclique partition number of bipartite graphs, specifically examining the Domino graph and its Kronecker powers. We address the challenges posed by the double exponential growth of the number of bicliques in increasing Kronecker powers. We discuss various strategies to generate suitable initial sets of bicliques, including an inductive method for increasing Kronecker powers. We show how to manage the number of active bicliques to improve running time and to stay within memory limits. Our computational results reveal that the fractional binary rank is not multiplicative with respect to the Kronecker product. Hence, there are binary matrices, and bipartite graphs, respectively, such as the Domino, where the asymptotic fractional binary rank is strictly smaller than the fractional binary rank. While we used our algorithm to reduce the upper bound, we formally prove that the fractional biclique cover number is a lower bound, which is at least as good as the widely used isolating (or fooling set) bound. For the Domino, we obtain that the asymptotic fractional binary rank lies in the interval [2,2.373]. Since our computational resources are not sufficient to further reduce the upper bound, we encourage further exploration using more substantial computing resources or further mathematical engineering techniques to narrow the gap and advance our understanding of biclique partitions, particularly, to settle the open question whether binary rank and biclique partition number are multiplicative with respect to the Kronecker product
LIPIcs, Volume 339, CCC 2025, Complete Volume
No full textLIPIcs, Volume 339, CCC 2025, Complete Volum
List Decoding Quotient Reed-Muller Codes
No full textReed-Muller codes consist of evaluations of n-variate polynomials over a finite field with degree at most d. Much like every linear code, Reed-Muller codes can be characterized by constraints, where a codeword is valid if and only if it satisfies all degree-d constraints.
For a subset X̃ ⊆ ⁿ, we introduce the notion of X̃-quotient Reed-Muller code. A function F:X̃ → is a valid codeword in the quotient code if it satisfies all the constraints of degree-d polynomials lying in X̃. This gives rise to a novel phenomenon: a quotient codeword may have many extensions to original codewords. This weakens the connection between original codewords and quotient codewords which introduces a richer range of behaviors along with substantial new challenges.
Our goal is to answer the following question: what properties of X̃ will imply that the quotient code inherits its distance and list-decoding radius from the original code? We address this question using techniques developed by Bhowmick and Lovett [Abhishek Bhowmick and Shachar Lovett, 2014], identifying key properties of ⁿ used in their proof and extending them to general subsets X̃ ⊆ ⁿ. By introducing a new tool, we overcome the novel challenge in analyzing the quotient code that arises from the weak connection between original and quotient codewords. This enables us to apply known results from additive combinatorics and algebraic geometry [David Kazhdan and Tamar Ziegler, 2018; David Kazhdan and Tamar Ziegler, 2019; Amichai Lampert and Tamar Ziegler, 2021] to show that when X̃ is a high rank variety, X̃-quotient Reed-Muller codes inherit the distance and list-decoding parameters from the original Reed-Muller codes
Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks
No full textThis paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection (PostBQP = PostBPP), (ii) any one of several quantum sampling experiments (BosonSampling, IQP, DQC1) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment’s hardness conjectures hold, then quantum computers can implement functions classical computers cannot (FBQP≠ FBPP) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case.
The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to ZPP^NP
Algebraic Pseudorandomness in VNC⁰
No full textWe study the arithmetic complexity of hitting set generators, which are pseudorandom objects used for derandomization of the polynomial identity testing problem. We give new explicit constructions of hitting set generators whose outputs are computable in VNC⁰, i.e., can be computed by arithmetic formulas of constant size. Unconditionally, we construct a VNC⁰-computable generator that hits arithmetic circuits of constant depth and polynomial size. We also give conditional constructions, under strong but plausible hardness assumptions, of VNC⁰-computable generators that hit arithmetic formulas and arithmetic branching programs of polynomial size, respectively. As a corollary of our constructions, we derive lower bounds for subsystems of the Geometric Ideal Proof System of Grochow and Pitassi.
Constructions of such generators are implicit in prior work of Kayal on lower bounds for the degree of annihilating polynomials. Our main contribution is a construction whose correctness relies on circuit complexity lower bounds rather than degree lower bounds
Quantum LDPC Codes of Almost Linear Distance via Iterated Homological Products
No full textThe first linear-distance quantum LDPC codes were recently constructed by a line of breakthrough works (culminating in the result of Panteleev & Kalachev, 2021). All such constructions, even when allowing for almost-linear distance, are based on an operation called a balanced (or lifted) product, which is used in a one-shot manner to combine a pair of large classical codes possessing a group symmetry.
We present a new construction of almost-linear distance quantum LDPC codes that is iterative in nature. Our construction is based on a more basic and widely used product, namely the homological product (i.e. the tensor product of chain complexes).
Specifically, for every ε > 0, we obtain a family of [[N,N^{1-ε},N^{1-ε}]] (subsystem) quantum LDPC codes via repeated homological products of a constant-sized quantum locally testable code. Our key idea is to remove certain low-weight codewords using subsystem codes (while still maintaining constant stabilizer weight), in order to circumvent a particular obstruction that limited the distance of many prior homological product code constructions to at most Õ(√N)