Algebraic Methods in Query and Proof Complexity
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
Algebraic methods have become a powerful tool for analyzing the complexity of various computational models, including low-depth circuits, algebraic proofs, and quantum query algorithms. In particular, the complexity of computing a function in these models is related to whether or not the function admits a low-degree polynomial approximation. In this thesis, we present two novel applications of algebraic methods in computational complexity theory. In the first part of the thesis, we study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether or not it satisfies some property. In addition to containing the classical query complexity model as a special case, this model also contains "inherently quantum" problems that have no classical analogue. Our main contribution is a generalized polynomial method for analyzing the complexity of unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a subspace, and approximating the entanglement entropy of a state. We also present a candidate problem towards an oracle separation of QMA and QMA(2), a long standing open question in quantum complexity theory. In the second part of the thesis, we study the tensor isomorphism problem (TI), which has recently emerged as having connections to multiple areas of research, including quantum information theory, post-quantum cryptography, and computational algebra. However, the current best upper bound is essentially the brute force algorithm. Being an algebraic problem, the study of tensor isomorphism naturally lends itself to algebraic and semi-algebraic proof systems such as the polynomial calculus (PC) and sum-of-squares (SoS). We show a linear degree lower bound on PC degree or SoS degree for tensor isomorphism and a non-trivial upper bound for testing isomorphism of tensors of bounded rank. Along the way, we also show that PC cannot perform basic linear algebra in sublinear degree, such as comparing the rank of two matrices. We introduce a strictly stronger proof system, called PC + Inv, which enables linear algebra to be done in low degree. We conjecture that even PC + Inv cannot solve TI in polynomial time either, and highlight many other open questions about proof complexity approaches to TI.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.002 | 0.000 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.001 | 0.000 |
| Bibliometrics | 0.001 | 0.002 |
| Science and technology studies | 0.000 | 0.001 |
| Scholarly communication | 0.001 | 0.000 |
| Open science | 0.001 | 0.001 |
| Research integrity | 0.001 | 0.002 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it