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. - Omkar Baraskar, Agrim Dewan, Chandan Saha:
Testing equivalence to design polynomials. - Daniel Noble, Brett Hemenway, Rafail Ostrovsky:
MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier. - Sabee Grewal, Justin Yirka:
The Entangled Quantum Polynomial Hierarchy Collapses. - Karthik C. S., Pasin Manurangsi:
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results. - Pavel Hrubes:
Hard submatrices for non-negative rank and communication complexity }. - Dmytro Gavinsky:
Unambiguous parity-query complexity. - Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere:
Black-Box PPP is not Turing-Closed. - Paul Beame, Niels Kornerup:
Quantum Time-Space Tradeoffs for Matrix Problems. - Hamed Hatami, Pooya Hatami:
Structure in Communication Complexity and Constant-Cost Complexity Classes. - Oded Goldreich:
On locally-characterized expander graphs (a survey). - Elette Boyle, Ilan Komargodski, Neekon Vafa:
Memory Checking Requires Logarithmic Overhead. - Harpreet Bedi:
Degree 2 lower bound for Permanent in arbitrary characteristic. - Swagato Sanyal:
Randomized query composition and product distributions. - Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun:
On Pigeonhole Principles and Ramsey in TFNP. - Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz:
The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices. - Yotam Dikstein, Irit Dinur, Alexander Lubotzky:
Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs. - Mitali Bafna, Noam Lifshitz, Dor Minzer:
Constant Degree Direct Product Testers with Small Soundness. - Prasad Chaugule, Nutan Limaye:
On the closures of monotone algebraic classes and variants of the determinant. - Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak:
Exponential Separation Between Powers of Regular and General Resolution Over Parities. - Shuichi Hirahara, Naoto Ohsaka:
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems. - Changrui Mu, Shafik Nassar, Ron Rothblum, Prashant Nalini Vasudevan:
Strong Batching for Non-Interactive Statistical Zero-Knowledge. - Mason DiCicco, Vladimir Podolskii, Daniel Reichman:
Nearest Neighbor Complexity and Boolean Circuits. - Pavel Hrubes:
A subquadratic upper bound on sum-of-squares compostion formulas. - Dor Minzer, Kai Zhe Zheng:
Near Optimal Alphabet-Soundness Tradeoff PCPs. - Ashish Dwivedi, Zeyu Guo, Ben Lee Volk:
Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields. - Noel Arteche, Gaia Carenini, Matthew Gray:
Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard. - Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann:
Proof Complexity of Propositional Model Counting. - Daniel M. Kane, Anthony Ostuni, Kewen Wu:
Locality Bounds for Sampling Hamming Slices. - Joshua Cook, Dana Moshkovitz:
Explicit Time and Space Efficient Encoders Exist Only With Random Access. - Sam Buss, Emre Yolcu:
Regular resolution effectively simulates resolution. - Bruno Loff, Alexey Milovanov:
The hardness of decision tree complexity. - Sreejata Kishor Bhattacharya:
Aaronson-Ambainis Conjecture Is True For Random Restrictions. - Tal Yankovitz:
A stronger bound for linear 3-LCC. - Yaroslav Alekseev, Yuval Filmus, Alexander Smal:
Lifting dichotomies. - Olaf Beyersdorff, Kaspar Kasche, Luc Nicolas Spachmann:
Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree. - Shuichi Hirahara, Naoto Ohsaka:
Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration. - Kuan Cheng, Ruiyang Wu:
Randomness Extractors in $\mathrm{AC}^0$ and $\mathrm{NC}^1$: Optimal up to Constant Factors. - Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich:
Launching Identity Testing into (Bounded) Space. - Lisa-Marie Jaser, Jacobo Torán:
Pebble Games and Algebraic Proof Systems Meet Again. - Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk:
Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits. - Rohit Gurjar, Taihei Oki, Roshan Raj:
Fractional Linear Matroid Matching is in quasi-NC. - Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria:
Redundancy for MaxSAT. - Sasank Mouli:
Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable. - Oded Goldreich:
On the query complexity of testing local graph properties in the bounded-degree graph model. - Kuan Cheng, Yichuan Wang:
$BPL\subseteq L-AC^1$. - Karthik Gajulapalli, Zeyong Li, Ilya Volkovich:
Oblivious Classes Revisited: Lower Bounds and Hierarchies. - Omri Shmueli:
Quantum Algorithms in a Superposition of Spacetimes. - Yanyi Liu, Rafael Pass:
A Direct PRF Construction from Kolmogorov Complexity. - Justin Yirka:
Even quantum advice is unlikely to solve PP. - Noam Mazor, Rafael Pass:
Gap MCSP is not (Levin) NP-complete in Obfustopia. - Karthik Gajulapalli, Alexander Golovnev, Samuel King:
On the Power of Adaptivity for Function Inversion. - Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass:
Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement. - Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan:
Local Correction of Linear Functions over the Boolean Cube. - Xi Chen, Yuhao Li, Mihalis Yannakakis:
Computing a Fixed Point of Contraction Maps in Polynomial Queries. - Shuichi Hirahara, Nobutaka Shimizu:
Planted Clique Conjectures Are Equivalent. - Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira:
Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity. - Lijie Chen, Jiatu Li, Igor Carboni Oliveira:
Reverse Mathematics of Complexity Lower Bounds. - Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi:
Improved Lower Bounds for 3-Query Matching Vector Codes. - Omar Alrabiah, Venkatesan Guruswami:
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. - Shuichi Hirahara, Mikito Nanashima:
One-Way Functions and Zero Knowledge. - Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami:
No Complete Problem for Constant-Cost Randomized Communication. - Meghal Gupta, Mihir Singhal, Hongxun Wu:
Optimal quantile estimation: beyond the comparison model. - Siu On Chan, Hiu Tsun Ng, Sijin Peng:
How Random CSPs Fool Hierarchies. - Mi-Ying (Miryam) Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang:
Breaking Square-Root Loss Barriers via Min-Entropy. - Pravesh Kothari, Peter Manohar:
Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. - Swastik Kopparty, Amnon Ta-Shma, Kedem Yakirevitch:
Character sums over AG codes. - Xinyu Mao, Guangxu Yang, Jiapeng Zhang:
Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing. - Yahel Manor, Or Meir:
Lifting with Inner Functions of Polynomial Discrepancy. - Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch:
Tropical proof systems. - Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay:
Trading Determinism for Noncommutativity in Edmonds' Problem. - Vaibhav Krishan, Sundar Vishwanathan:
Towards ACC Lower Bounds using Torus Polynomials. - Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu:
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. - Oliver Korten, Toniann Pitassi:
Strong vs. Weak Range Avoidance and the Linear Ordering Principle. - Divesh Aggarwal, Leong Jin Ming, Alexandra Veliche:
Worst-Case to Average-Case Hardness of LWE: A Simple and Practical Perspective. - Oded Goldreich:
On the relaxed LDC of BGHSV: A survey that corrects the record. - Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret:
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers. - Robert Andrews, Avi Wigderson:
Constant-Depth Arithmetic Circuits for Linear Algebra Problems. - Sravanthi Chede, Leroy Chew, Anil Shukla:
Circuits, Proofs and Propositional Model Counting. - Yotam Dikstein, Max Hopkins:
Chernoff Bounds and Reverse Hypercontractivity on HDX. - Lijie Chen, Jiatu Li, Igor Carboni Oliveira:
On the Unprovability of Circuit Size Bounds in Intuitionistic S12. - Vikraman Arvind, Pushkar S. Joglekar:
A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results. - Zhenjian Lu, Rahul Santhanam:
Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity. - Hao Wu:
A nearly-4logn depth lower bound for formulas with restriction on top. - Renato Ferreira Pinto Jr.:
Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach. - Tamer Mour, Alon Rosen, Ron Rothblum:
Locally Testable Tree Codes. - Gil Cohen, Itay Cohen, Gal Maor:
Tight Bounds for the Zig-Zag Product. - Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz:
A Study of Error Reduction Polynomials. - Dean Doron, Jonathan Mosheiff, Mary Wootters:
When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound? - Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan:
Hilbert Functions and Low-Degree Randomness Extractors. - Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, João Ribeiro:
Low-Degree Polynomials Are Good Extractors. - Tal Herman, Guy N. Rothblum:
Interactive Proofs for General Distribution Properties. - Yanyi Liu, Noam Mazor, Rafael Pass:
A Note on Zero-Knowledge for NP and One-Way Functions. - Noga Amit, Guy N. Rothblum:
Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way Functions. - Zhiyang Xun, David Zuckerman:
Near-Optimal Averaging Samplers. - Noga Amit, Orr Paradise, Guy N. Rothblum, Shafi Goldwasser:
Models That Prove Their Own Correctness. - Pavel Hrubes:
A subquadratic upper bound on Hurwitz's problem and related non-commutative polynomials. - Changrui Mu, Prashant Nalini Vasudevan:
Instance-Hiding Interactive Proofs. - Or Keret, Ron Rothblum, Prashant Nalini Vasudevan:
Doubly-Efficient Batch Verification in Statistical Zero-Knowledge. - Inbar Ben Yaacov, Yotam Dikstein, Gal Maor:
Sparse High Dimensional Expanders via Local Lifts. - Farzan Byramji, Vatsal Jha, Chandrima Kayal, Rajat Mittal:
Relations between monotone complexity measures based on decision tree complexity. - Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha:
NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials. - Benny Applebaum, Kaartik Bhushan, Manoj Prabhakaran:
Communication Complexity vs Randomness Complexity in Interactive Proofs. - James Cook, Jiatu Li, Ian Mertz, Edward Pyne:
The Structure of Catalytic Space: Capturing Randomness and Time via Compression. - Benjamin Rossman:
Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication. - Benny Applebaum, Eliran Kachlon:
Stochastic Secret Sharing with $1$-Bit Shares and Applications to MPC. - Oded Goldreich:
On the Cook-Mertz Tree Evaluation procedure. - Joshua Cook, Dana Moshkovitz:
Time and Space Efficient Deterministic Decoders. - Siddharth Iyer, Anup Rao:
An XOR Lemma for Deterministic Communication Complexity. - Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena:
The Rate of Interactive Codes is Bounded Away from 1. - Nikhil Vyas, Ryan Williams:
On Oracles and Algorithmic Methods for Proving Lower Bounds. - Nir Bitansky, Ron D. Rothblum, Prahladh Harsha, Yuval Ishai, David J. Wu:
Dot-Product Proofs and Their Applications. - Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam:
On the Complexity of Avoiding Heavy Elements. - Lijie Chen, Ron D. Rothblum, Roei Tell:
Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?). - Ludmila Glinskih, Artur Riazanov:
Partial Minimum Branching Program Size Problem is ETH-hard. - Amnon Ta-Shma, Ron Zadiario:
The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced. - Vishwas Bhargava, Anamay Tengse:
Explicit Commutative ROABPs from Partial Derivatives. - Halley Goldberg, Valentine Kabanets:
Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity. - Nader H. Bshouty:
Approximating the Number of Relevant Variables in a Parity Implies Proper Learning. - Antoine Joux, Anand Kumar Narayanan:
A high dimensional Cramer's rule connecting homogeneous multilinear equations to hyperdeterminants. - Vishwas Bhargava, Devansh Shringi:
Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition. - Oded Goldreich:
Solving Tree Evaluation in o(log n · log log n) space. - Pavel Hrubes, Pushkar S. Joglekar:
On read-k projections of the determinant. - Takashi Ishizuka:
On the Complexity of Some Restricted Variants of Quotient Pigeon and a Weaker Variant of König. - Bill Fefferman, Soumik Ghosh, Wei Zhan:
Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits. - Yaroslav Alekseev, Dmitry Itsykson:
Lifting to regular resolution over parities via games. - Amey Bhangale, Subhash Khot, Dor Minzer:
On Approximability of Satisfiable k-CSPs: V. - Sabee Grewal, Vinayak Kumar:
Improved Circuit Lower Bounds With Applications to Exponential Separations Between Quantum and Classical Circuits. - Hadar Strauss:
Emulating Computationally Sound Public-Coin IPPs in the Pre-Coordinated Model. - Arkadev Chattopadhyay, Pavel Dvorak:
Super-critical Trade-offs in Resolution over Parities Via Lifting. - Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Yunya Zhao:
Two-Sided Lossless Expanders in the Unbalanced Setting. - Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira:
One-Way Functions and pKt Complexity. - Dean Doron, William Hoza:
Implications of Better PRGs for Permutation Branching Programs. - Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker:
Fully Characterizing Lossy Catalytic Computation. - Jiatu Li, Edward Pyne, Roei Tell:
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness. - Sagar Bisoyi, Krishnamoorthy Dinesh, Bhabya Rai, Jayalal Sarma:
Almost-catalytic Computation. - Tal Herman:
Public Coin Interactive Proofs for Label-Invariant Distribution Properties. - Ryan Williams:
The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds. - Noga Amir, Oded Goldreich, Guy N. Rothblum:
Doubly Sub-linear Interactive Proofs of Proximity. - Dar Gilboa, Siddhartha Jain, Jarrod R. McClean:
Consumable Data via Quantum Communication. - Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira, Dimitrios Tsintsilidas:
Provability of the Circuit Size Hierarchy and Its Consequences. - Zhenjian Lu, Noam Mazor, Igor C. Oliveira, Rafael Pass:
Lower Bounds on the Overhead of Indistinguishability Obfuscation. - Shanthanu S. Rai:
Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields. - Swastik Kopparty, Mrinal Kumar, Harry Sha:
High Rate Multivariate Polynomial Evaluation Codes. - Noor Athamnah, Ron D. Rothblum, Eden Florentz-Konopnicki:
Rate-1 Zero-Knowledge Proofs from One-Way Functions. - Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj:
Characterizing and Testing Principal Minor Equivalence of Matrices. - Vijay Bhattiprolu, Euiwoong Lee:
Inapproximability of Sparsest Vector in a Real Subspace. - Alexander A. Sherstov, Andrey A. Storozhenko:
The Communication Complexity of Approximating Matrix Rank. - Jesse Goodman, Xin Li, David Zuckerman:
Improved Condensers for Chor-Goldreich Sources. - Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima:
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications. - Bruno Pasqualotto Cavalar, Eli Goldin, Matthew Gray, Peter Hall:
A Meta-Complexity Characterization of Quantum Cryptography. - Yupan Liu, Qisheng Wang:
On estimating the trace of quantum state powers. TR24-157 - Xin Li, Songtao Mao:
Improved Explicit Near-Optimal Codes in the High-Noise Regimes. TR24-158 - Dean Doron:
Binary Codes with Distance Close to Half. TR24-159 - Igor Razgon:
The splitting power of branching programs of bounded repetition and CNFs of bounded width. TR24-160 - Oded Goldreich:
On defining PPT-search problems. TR24-161 - Agnes Schleitzer, Olaf Beyersdorff:
Computationally Hard Problems Are Hard for QBF Proof Systems Too. TR24-162 - Roei Tell:
On defining PPT-search problems and PPT-optimization problems. TR24-163 - Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan:
Low Degree Local Correction Over the Boolean Cube. TR24-164 - Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman:
Online Condensing of Unpredictable Sources via Random Walks. TR24-165 - John Bostanci, Yeongwoo Hwang:
Commuting Local Hamiltonians Beyond 2D. TR24-166 - François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang:
Space-bounded quantum interactive proof systems. TR24-167 - Ronen Shaltiel:
Multiplicative Extractors for Samplable Distributions. TR24-168 - Clément L. Canonne, Francis Su, Salil Vadhan:
The Randomness Complexity of Differential Privacy. TR24-169 - Michael Jaber, Shachar Lovett, Anthony Ostuni:
Corners in Quasirandom Groups via Sparse Mixing. TR24-170 - Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach:
Condensing against Online Adversaries. TR24-171 - Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li:
Quantum Communication Advantage in TFNP. TR24-172 - Songhua He, Yuanzhi Li, Periklis A. Papakonstantinou, Xin Yang:
Lower Bounds in the Query-with-Sketch Model and a Barrier in Derandomizing BPL. TR24-173 - Albert Atserias, Iddo Tzameret:
Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets. TR24-174 - Mark Braverman, Or Zamir:
Optimality of Frequency Moment Estimation. TR24-175 - Dean Doron, João Ribeiro:
Nearly-Linear Time Seeded Extractors with Short Seeds. TR24-176 - Swastik Kopparty, Harry Sha:
Small Shadow Partitions. TR24-177 - Noah Fleming, Yuichi Yoshida:
Sensitivity Lower Bounds for Approximaiton Algorithms. TR24-178 - Norbert Blum:
On the approximation method and the P versus NP problem. TR24-179 - Daniel Kane, Anthony Ostuni, Kewen Wu:
Locally Sampleable Uniform Symmetric Distributions. TR24-180 - Tomer Gewirtzman, Ron Rothblum:
Zero-Knowledge in Streaming Interactive Proofs. TR24-181 - Lijie Chen, Jiatu Li, Jingxun Liang:
Maximum Circuit Lower Bounds for Exponential-time Arthur Merlin. TR24-182 - Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan:
Improved PIR Schemes using Matching Vectors and Derivatives. TR24-183 - Fernando Granha Jeronimo, Nir Magrafta, Joseph Slote, Pei Wu:
Coherence in Property Testing: Quantum-Classical Collapses and Separations. TR24-184 - Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, Shuo Pang:
Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman. TR24-185 - Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov:
Supercritical Tradeoffs for Monotone Circuits. TR24-186 - Oliver Janzer, Peter Manohar:
A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs. TR24-187 - Edward Pyne, Nathan S. Sheffield, William Wang:
Catalytic Communication. TR24-188 - Arpon Basu, Jun-Ting Hsieh, Pravesh Kothari, Andrew Lin:
Improved Lower Bounds for all Odd-Query Locally Decodable Codes. TR24-189
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.
last updated on 2024-11-27 20:18 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: