Stop the war!
Остановите войну!
for scientists:
default search action
Electronic Colloquium on Computational Complexity, Volume 2024
Volume TR24, 2024
- Sam Buss, Neil Thapen:
A Simple Supercritical Tradeoff between Size and Height in Resolution. - Takashi Ishizuka:
PLS is contained in PLC. - Noam Mazor, Rafael Pass:
Search-to-Decision Reductions for Kolmogorov Complexity. TR24-003 - Omkar Baraskar, Agrim Dewan, Chandan Saha:
Testing equivalence to design polynomials. TR24-004 - Daniel Noble, Brett Hemenway, Rafail Ostrovsky:
MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier. TR24-005 - Sabee Grewal, Justin Yirka:
The Entangled Quantum Polynomial Hierarchy Collapses. TR24-006 - Karthik C. S., Pasin Manurangsi:
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results. TR24-007 - Pavel Hrubes:
Hard submatrices for non-negative rank and communication complexity }. TR24-008 - Dmytro Gavinsky:
Unambiguous parity-query complexity. TR24-009 - Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere:
Black-Box PPP is not Turing-Closed. TR24-010 - Paul Beame, Niels Kornerup:
Quantum Time-Space Tradeoffs for Matrix Problems. TR24-011 - Hamed Hatami, Pooya Hatami:
Structure in Communication Complexity and Constant-Cost Complexity Classes. TR24-012 - Oded Goldreich:
On locally-characterized expander graphs (a survey). TR24-013 - Elette Boyle, Ilan Komargodski, Neekon Vafa:
Memory Checking Requires Logarithmic Overhead. TR24-014 - Harpreet Bedi:
Degree 2 lower bound for Permanent in arbitrary characteristic. TR24-015 - Swagato Sanyal:
Randomized query composition and product distributions. TR24-016 - Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun:
On Pigeonhole Principles and Ramsey in TFNP. TR24-017 - Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz:
The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices. TR24-018 - Yotam Dikstein, Irit Dinur, Alexander Lubotzky:
Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs. TR24-019 - Mitali Bafna, Noam Lifshitz, Dor Minzer:
Constant Degree Direct Product Testers with Small Soundness. TR24-020 - Prasad Chaugule, Nutan Limaye:
On the closures of monotone algebraic classes and variants of the determinant. TR24-021 - Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak:
Exponential Separation Between Powers of Regular and General Resolution Over Parities. TR24-022 - Shuichi Hirahara, Naoto Ohsaka:
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems. TR24-023 - Changrui Mu, Shafik Nassar, Ron Rothblum, Prashant Nalini Vasudevan:
Strong Batching for Non-Interactive Statistical Zero-Knowledge. TR24-024 - Mason DiCicco, Vladimir Podolskii, Daniel Reichman:
Nearest Neighbor Complexity and Boolean Circuits. TR24-025 - Pavel Hrubes:
A subquadratic upper bound on sum-of-squares compostion formulas. TR24-026 - Dor Minzer, Kai Zhe Zheng:
Near Optimal Alphabet-Soundness Tradeoff PCPs. TR24-027 - Ashish Dwivedi, Zeyu Guo, Ben Lee Volk:
Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields. TR24-028 - Noel Arteche, Gaia Carenini, Matthew Gray:
Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard. TR24-029 - Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann:
Proof Complexity of Propositional Model Counting. TR24-030 - Daniel M. Kane, Anthony Ostuni, Kewen Wu:
Locality Bounds for Sampling Hamming Slices. TR24-031 - Joshua Cook, Dana Moshkovitz:
Explicit Time and Space Efficient Encoders Exist Only With Random Access. TR24-032 - Sam Buss, Emre Yolcu:
Regular resolution effectively simulates resolution. TR24-033 - Bruno Loff, Alexey Milovanov:
The hardness of decision tree complexity. TR24-034 - Sreejata Kishor Bhattacharya:
Aaronson-Ambainis Conjecture Is True For Random Restrictions. TR24-035 - Tal Yankovitz:
A stronger bound for linear 3-LCC. TR24-036 - Yaroslav Alekseev, Yuval Filmus, Alexander Smal:
Lifting dichotomies. TR24-037 - Olaf Beyersdorff, Kaspar Kasche, Luc Nicolas Spachmann:
Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree. TR24-038 - Shuichi Hirahara, Naoto Ohsaka:
Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration. TR24-039 - Kuan Cheng, Ruiyang Wu:
Randomness Extractors in $\mathrm{AC}^0$ and $\mathrm{NC}^1$: Optimal up to Constant Factors. TR24-040 - Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich:
Launching Identity Testing into (Bounded) Space. TR24-041 - Lisa Jaser, Jacobo Torán:
Pebble Games and Algebraic Proof Systems Meet Again. TR24-042 - Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk:
Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits. TR24-043 - Rohit Gurjar, Taihei Oki, Roshan Raj:
Fractional Linear Matroid Matching is in quasi-NC. TR24-044 - Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria:
Redundancy for MaxSAT. TR24-045 - Sasank Mouli:
Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable. TR24-046 - Oded Goldreich:
On the query complexity of testing local graph properties in the bounded-degree graph model. TR24-047 - Kuan Cheng, Yichuan Wang:
$BPL\subseteq L-AC^1$. TR24-048 - Karthik Gajulapalli, Zeyong Li, Ilya Volkovich:
Oblivious Classes Revisited: Lower Bounds and Hierarchies. TR24-049 - Omri Shmueli:
Quantum Algorithms in a Superposition of Spacetimes. TR24-050 - Yanyi Liu, Rafael Pass:
A Direct PRF Construction from Kolmogorov Complexity. TR24-051 - Justin Yirka:
Even quantum advice is unlikely to solve PP. TR24-052 - Noam Mazor, Rafael Pass:
Gap MCSP is not (Levin) NP-complete in Obfustopia. TR24-053 - Karthik Gajulapalli, Alexander Golovnev, Samuel King:
On the Power of Adaptivity for Function Inversion. TR24-054 - Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass:
Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement. TR24-055 - Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan:
Local Correction of Linear Functions over the Boolean Cube. TR24-056 - Xi Chen, Yuhao Li, Mihalis Yannakakis:
Computing a Fixed Point of Contraction Maps in Polynomial Queries. TR24-057 - Shuichi Hirahara, Nobutaka Shimizu:
Planted Clique Conjectures Are Equivalent. TR24-058
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.