default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic 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.
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-08 20:35 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:
