- Prerona Chatterjee
, Mrinal Kumar, Adrian She, Ben Lee Volk:
Quadratic Lower Bounds for Algebraic Branching Programs and Formulas. Comput. Complex. 31(2): 8 (2022) - Austin Conner, Fulvio Gesmundo, Joseph M. Landsberg, Emanuele Ventura:
Rank and border rank of Kronecker powers of tensors and Strassen's laser method. Comput. Complex. 31(1): 1 (2022) - Dean Doron, Amnon Ta-Shma, Roei Tell:
On Hitting-Set Generators for Polynomials that Vanish Rarely. Comput. Complex. 31(2): 16 (2022) - Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos:
The complexity of approximating the complex-valued Potts model. Comput. Complex. 31(1): 2 (2022) - Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka:
Quantum generalizations of the polynomial hierarchy with applications to QMA(2). Comput. Complex. 31(2): 13 (2022) - Uma Girish, Ran Raz, Avishay Tal:
Quantum versus Randomized Communication Complexity, with Efficient Players. Comput. Complex. 31(2): 17 (2022) - Oded Goldreich:
Improved bounds on the AN-complexity of O(1)-linear functions. Comput. Complex. 31(2): 7 (2022) - Paul Görlach, Yue Ren, Leon Zhang:
Computing zero-dimensional tropical varieties via projections. Comput. Complex. 31(1): 5 (2022) - Ishay Haviv:
The Complexity of Finding Fair Independent Sets in Cycles. Comput. Complex. 31(2): 14 (2022) - Hiroshi Hirai, Motoki Ikeda:
A cost-scaling algorithm for computing the degree of determinants. Comput. Complex. 31(2): 10 (2022) - Mrinal Kumar, Ben Lee Volk:
A Lower Bound on Determinantal Complexity. Comput. Complex. 31(2): 12 (2022) - Igor C. Oliveira, Rahul Santhanam, Roei Tell:
Expander-Based Cryptography Meets Natural Proofs. Comput. Complex. 31(1): 4 (2022) - Adrien Poteaux, Martin Weimann:
A quasi-linear irreducibility test in 핂[[x]][y]. Comput. Complex. 31(1): 6 (2022) - Thomas Watson:
Amplification with One NP Oracle Query. Comput. Complex. 31(1): 3 (2022) - 2021
- Pranav Bisht, Nitin Saxena:
Blackbox identity testing for sum of special ROABPs and its border class. Comput. Complex. 30(1): 8 (2021) - Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre:
Lower Bounds for Arithmetic Circuits via the Hankel Matrix. Comput. Complex. 30(2): 14 (2021) - Mark Giesbrecht, Armin Jamshidpey, Éric Schost:
Subquadratic-Time Algorithms for Normal Bases. Comput. Complex. 30(1): 5 (2021) - Tom Gur, Yang P. Liu, Ron D. Rothblum:
An Exponential Separation Between MA and AM Proofs of Proximity. Comput. Complex. 30(2): 12 (2021) - Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov:
Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs. Comput. Complex. 30(2): 13 (2021) - Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov:
Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs. Comput. Complex. 30(2): 16 (2021) - Orr Paradise:
Smooth and Strong PCPs. Comput. Complex. 30(1): 1 (2021) - Orr Paradise:
Correction to: Smooth and Strong PCPs. Comput. Complex. 30(1): 9 (2021) - Fedor Part, Iddo Tzameret:
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli. Comput. Complex. 30(1): 2 (2021) - Toniann Pitassi, Morgan Shirley, Thomas Watson:
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. Comput. Complex. 30(2): 10 (2021) - Susanna F. de Rezende, Or Meir, Jakob Nordström, Robert Robere:
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. Comput. Complex. 30(1): 4 (2021) - Ronen Shaltiel, Jad Silbak:
Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels. Comput. Complex. 30(1): 3 (2021) - Alexander A. Sherstov:
The hardest halfspace. Comput. Complex. 30(2): 11 (2021) - Amit Sinhababu, Thomas Thierauf:
Factorization of Polynomials Given by Arithmetic Branching Programs. Comput. Complex. 30(2): 15 (2021) - Jacobo Torán, Florian Wörz:
Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space. Comput. Complex. 30(1): 7 (2021) - Ben Lee Volk, Mrinal Kumar:
Lower Bounds for Matrix Factorization. Comput. Complex. 30(1): 6 (2021)
