default search action
Electronic Colloquium on Computational Complexity, 2022
Volume TR22, 2022
- Yogesh Dahiya, Meena Mahajan:
On (Simple) Decision Tree Rank. - Sravanthi Chede, Anil Shukla:
Extending Merge Resolution to a Family of Proof Systems. - Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere:
On Semi-Algebraic Proofs and Algorithms. - Silas Richelson
, Sourya Roy:
Analyzing Ta-Shma's Code via the Expander Mixing Lemma. - Anup Rao:
Sunflowers: from soil to oil. - Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi:
Secret Sharing, Slice Formulas, and Monotone Real Circuits. - Halley Goldberg, Valentine Kabanets:
A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information. - Gil Cohen, Dean Doron, Ori Sberlo:
Approximating Large Powers of Stochastic Matrices in Small Space. - C. Ramya, Anamay Tengse:
On Finer Separations between Subclasses of Read-once Oblivious ABPs. - Marshall Ball
(Nondeterministic) Hardness vs. Non-Malleability. - Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen:
Public-Key Encryption from Continuous LWE. - Anup Rao, Oscar Sprumont:
On List Decoding Transitive Codes From Random Errors. - Nader H. Bshouty, Oded Goldreich:
On properties that are non-trivial to test. - Joshua Cook, Dana Moshkovitz:
Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE. - Mika Göös, Stefan Kiefer, Weiqiang Yuan:
Lower Bounds for Unambiguous Automata via Communication Complexity. - Artur Ignatiev, Ivan Mihajlin, Alexander Smal:
Super-cubic lower bound for generalized Karchmer-Wigderson games. - Ron D. Rothblum, Prashant Nalini Vasudevan:
Collision-Resistance from Multi-Collision-Resistance. - Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao:
Further Collapses in TFNP. - Guangxu Yang, Jiapeng Zhang:
Simulation Methods in Communication Lower Bounds, Revisited. - Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar:
Worst-Case to Average-Case Reductions via Additive Combinatorics. - Xin Lyu:
Improved Pseudorandom Generators for AC0 Circuits. - Vikraman Arvind, Pushkar S. Joglekar:
On Efficient Noncommutative Polynomial Factorization via Higman Linearization. - Erfan Khaniki:
Nisan-Wigderson generators in Proof Complexity: New lower bounds. - Louis Golowich, Salil P. Vadhan:
Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs. - Oliver Korten:
Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle. - James Cook, Ian Mertz:
Trading Time and Space in Catalytic Branching Programs. - Guy Blanc, Dean Doron:
New Near-Linear Time Decodable Codes Closer to the GV Bound. - Dan Karliner, Roie Salama, Amnon Ta-Shma:
The plane test is a local tester for Multiplicity Codes. - Anthony Leverrier, Gilles Zémor:
Quantum Tanner codes. - Aniruddha Biswas, Palash Sarkar:
On The "Majority is Least Stable" Conjecture. - Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse:
Transparency Beyond VNP in the Monotone Setting. - Iftach Haitner, Noam Mazor, Jad Silbak:
Incompressiblity and Next-Block Pseudoentropy. - Ivan Mihajlin, Anastasia Sofronova:
A better-than-3logn depth lower bound for De Morgan formulas with restrictions on top gates. - Chin Ho Lee, Edward Pyne, Salil P. Vadhan:
Fourier Growth of Regular Branching Programs. - Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff:
A Characterization of Multiclass Learnability. - Agnes Schleitzer, Olaf Beyersdorff:
Classes of Hard Formulas for QBF Resolution. - Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta:
Robust Radical Sylvester-Gallai Theorem for Quadratics. - Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
Lower bounds for Polynomial Calculus with extension variables over finite fields. - Uma Girish, Justin Holmgren
Parallel Repetition For All 3-Player Games Over Binary Alphabet. - Benjamin Böhm, Tomás Peitl, Olaf Beyersdorff:
Should decisions in QCDCL follow prefix order? - TsunMing Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein:
Boolean functions with small approximate spectral norm. - Vikraman Arvind, Pushkar S. Joglekar:
Matrix Polynomial Factorization via Higman Linearization. - Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan:
Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs. - Meghal Gupta, Naren Manoj:
An Optimal Algorithm for Certifying Monotone Functions. - Gil Cohen, Tal Yankovitz:
Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring. - Dmitry Itsykson, Artur Riazanov:
Automating OBDD proofs is NP-hard. - Manik Dhar, Zeev Dvir:
Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds. - Hanlin Ren, Rahul Santhanam, Zhikun Wang:
On the Range Avoidance Problem for Circuits. - Xinyu Mao, Noam Mazor, Jiapeng Zhang:
Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions. - Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena:
Circuits Resilient to Short-Circuit Errors. - Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida:
Low Degree Testing over the Reals. - Tal Herman, Guy N. Rothblum:
Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties. - Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap:
On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs. - Anastasia Sofronova, Dmitry Sokolov:
A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion. - Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret:
Simple Hard Instances for Low-Depth Algebraic Proofs. - Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand:
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. - Lijie Chen, Roei Tell:
When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems. - Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao:
Separations in Proof Complexity and TFNP. - Siddhesh Chaubal, Anna Gál:
Diameter versus Certificate Complexity of Boolean Functions. - Nikolay K. Vereshchagin:
How much randomness is needed to convert MA protocols to AM protocols? - Amey Bhangale, Subhash Khot, Dor Minzer:
On Approximability of Satisfiable k-CSPs: I. - Paolo Liberatore:
Superredundancy: A tool for Boolean formula minimization complexity analysis. - Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans:
Fast Multivariate Multipoint Evaluation Over All Finite Fields. - Deepanshu Kush, Shubhangi Saraf:
Improved Low-Depth Set-Multilinear Circuit Lower Bounds. - Madhu Sudan:
Streaming and Sketching Complexity of CSPs: A survey. - Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy:
On sketching approximations for symmetric Boolean CSPs. - Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay:
Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time. - Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy:
Sketching Approximability of (Weak) Monarchy Predicates. - Silas Richelson
List-Decoding Random Walk XOR Codes Near the Johnson Bound. - Pranav Bisht, Ilya Volkovich:
On Solving Sparse Polynomial Factorization Related Problems. - Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay:
Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product. - Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira:
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. - Itay Kalev, Amnon Ta-Shma:
Unbalanced Expanders from Multiplicity Codes. - Michael E. Saks, Rahul Santhanam:
On Randomized Reductions to the Random Strings. - Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan:
Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes. - Hunter Monroe:
Average-Case Hardness of Proving Tautologies and Theorems. - Max Hopkins, Ting-Chun Lin:
Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares. - Dan Karliner, Amnon Ta-Shma:
Improved local testing for multiplicity codes. - Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao:
Lower Bound Methods for Sign-rank and their Limitations. - Meena Mahajan, Gaurav Sood:
QBF Merge Resolution is powerful but unnatural. - Zhenjian Lu, Igor C. Oliveira:
Theory and Applications of Probabilistic Kolmogorov Complexity. - Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro:
Low-Degree Polynomials Extract from Local Sources. - Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie:
Hardness of Maximum Likelihood Learning of DPPs. - Yanyi Liu, Rafael Pass:
Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity. - Andrzej Lingas:
A Note on Lower Bounds for Monotone Multilinear Boolean Circuits. - Lijie Chen, Jiatu Li, Tianqi Yang:
Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs. - Pooya Hatami, William Hoza, Avishay Tal, Roei Tell:
Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees. - Anthony Leverrier, Gilles Zémor:
Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes. - Ilario Bonacina, Neil Thapen:
A separation of PLS from PPP. - Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas:
On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. - Harm Derksen, Emanuele Viola:
Quasirandom groups enjoy interleaved mixing. - Peter Ivanov, Liam Pavlovic, Emanuele Viola:
On correlation bounds against polynomials. - Joshua Cook:
More Verifier Efficient Interactive Protocols For Bounded Space. - Stasys Jukna:
Notes on Monotone Read-k Circuits. - Meghal Gupta, Rachel Yun Zhang:
Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel. - Mika Göös, Siddhartha Jain:
Communication Complexity of Collision. - Lijie Chen, Ron D. Rothblum, Roei Tell:
Unstructured Hardness to Average-Case Randomness. - Nader H. Bshouty:
Non-Adaptive Proper Learning Polynomials. - Nikhil Gupta, Chandan Saha, Bhargav Thankey:
Equivalence Test for Read-Once Arithmetic Formulas. - Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming complexity of CSPs with randomly ordered constraints. - Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar:
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. - Venkatesan Guruswami, Xin Lyu, Xiuhan Wang:
Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness. - Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman:
Almost Chor-Goldreich Sources and Adversarial Random Walks. - Nader H. Bshouty:
On One-Sided Testing Affine Subspaces. - Ilario Bonacina, Nicola Galesi, Massimo Lauria:
On vanishing sums of roots of unity in polynomial calculus and sum-of-squares. - Suryajith Chillara, Coral Grichener, Amir Shpilka:
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts. - Shachar Lovett, Jiapeng Zhang:
Fractional certificates for bounded functions. - Shuichi Hirahara, Nobutaka Shimizu:
Hardness Self-Amplification from Feasible Hard-Core Sets. - Siddharth Iyer, Michael Whitmeyer:
Searching for Regularity in Bounded Functions. - Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit:
Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves. - Robert Andrews:
On Matrix Multiplication and Polynomial Identity Testing. - Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre:
Randomised Composition and Small-Bias Minimax. - Yanyi Liu, Rafael Pass:
Leakage-Resilient Hardness v.s. Randomness. - Hao Wu:
Direct Sum Theorems From Fortification. - Dieter van Melkebeek, Andrew Morgan:
Polynomial Identity Testing via Evaluation of Rational Functions. - Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii:
Constant-Depth Sorting Networks. - Ronen Shaltiel, Jad Silbak:
Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits. - Huacheng Yu:
Strong XOR Lemma for Communication with Bounded Rounds. - Shuichi Hirahara:
NP-Hardness of Learning Programs and Partial MCSP. - Jan Krajícek:
On the existence of strong proof complexity generators. - William Hoza:
Recent Progress on Derandomizing Space-Bounded Computation. - Young Kun-Ko:
Efficient Linearization Implies the Multiphase Conjecture. - Alexander A. Sherstov:
The Approximate Degree of DNF and CNF Formulas. - Oded Goldreich, Guy N. Rothblum, Tal Skverer:
On Interactive Proofs of Proximity with Proof-Oblivious Queries. - Shir Peleg, Amir Shpilka, Ben Lee Volk:
Tensor Reconstruction Beyond Constant Rank. - Andrei A. Krokhin, Jakub Oprsal:
An Invitation to the Promise Constraint Satisfaction Problem. - Eric Allender, Shuichi Hirahara, Harsha Tirumala:
Kolmogorov Complexity Characterizes Statistical Zero Knowledge. - Romain Bourneuf, Lukás Folwarczný, Pavel Hubácek, Alon Rosen, Nikolaj I. Schwartzbach:
PPP-Completeness and Extremal Combinatorics. - Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang:
Binary Codes with Resilience Beyond 1/4 via Interaction. - Hamed Hatami, Kaave Hosseini, Xiang Meng:
A Borsuk-Ulam lower bound for sign-rank and its application. - Rafael Mendes de Oliveira, Akash Sengupta:
Radical Sylvester-Gallai for Cubics. - Harm Derksen, Emanuele Viola:
Fooling polynomials using invariant theory. - Prahladh Harsha, Daniel Mitropolsky, Alon Rosen:
Downward Self-Reducibility in TFNP. - Greg McLellan, Alexey Milovanov:
Some Games on Turing Machines and Power from Random Strings. - Rahul Chugh, Supartha Podder, Swagato Sanyal:
Decision Tree Complexity versus Block Sensitivity and Degree. - Sepehr Assadi, Gillat Kol, Zhijun Zhang:
Rounds vs Communication Tradeoffs for Maximal Independent Sets. - Daniel Avraham, Amir Yehudayoff:
On blocky ranks of matrices. - Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang:
Robustness for Space-Bounded Statistical Zero Knowledge. - Radu Curticapean, Nutan Limaye, Srikanth Srinivasan:
On the VNP-hardness of Some Monomial Symmetric Polynomials. - Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry:
Commitments to Quantum States. - Sam Buss, Noah Fleming, Russell Impagliazzo:
TFNP Characterizations of Proof Systems and Monotone Circuits. - Emanuele Viola:
Correlation bounds against polynomials. - Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny:
Certificate games. - Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming beyond sketching for Maximum Directed Cut. - Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz:
Revisiting Time-Space Tradeoffs for Function Inversion. - Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai:
Interactive Coding with Small Memory. - Samir Datta, Chetan Gupta:
Evaluating Monotone Circuits on Surfaces. - Peter Ivanov, Raghu Meka, Emanuele Viola:
Efficient resilient functions. - Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma:
Approximating Iterated Multiplication of Stochastic Matrices in Small Space. - Aaron (Louie) Putterman, Edward Pyne:
Near-Optimal Derandomization of Medium-Width Branching Programs. - Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey:
Low-depth arithmetic circuit lower bounds via shifted partials. - Toniann Pitassi, Morgan Shirley, Adi Shraibman:
The Strength of Equality Oracles in Communication. - Eshan Chattopadhyay, Jyun-Jie Liao:
Hardness against Linear Branching Programs and More. - Gil Cohen, Itay Cohen:
Spectral Expanding Expanders. - Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen:
Testing of Index-Invariant Properties in the Huge Object Model. - Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro:
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓp Norms. - Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov:
Border complexity via elementary symmetric polynomials. - Ivan Hu, Andrew Morgan, Dieter van Melkebeek:
Query Complexity of Inversion Minimization on Trees. - Songhua He, Periklis A. Papakonstantinou:
Deep Neural Networks: The Missing Complexity Parameter. - Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, N. V. Vinodchandran:
The Geometry of Rounding. - Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu:
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. - Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\widetilde{O}(n\sqrt{d})$ Monotonicity Tester. - Gil Cohen, Gal Maor:
Random Walks on Rotating Expanders. - Shuichi Hirahara, Mikito Nanashima:
Learning versus Pseudorandom Generators in Constant Parallel Time. - TsunMing Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley:
Separation of the factorization norm and randomized communication complexity. - Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu:
Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly. - Mark Braverman, Subhash Khot, Dor Minzer:
Parallel Repetition for the GHZ Game: Exponential Decay. - Zubayir Kazi:
A Proof of the Generalized Union-Closed Set Conjecture assuming the Union-Closed Set Conjecture. - Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman:
Extractors for Images of Varieties. - Huck Bennett:
The Complexity of the Shortest Vector Problem. - Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif:
Lifting to Parity Decision Trees Via Stifling. - Paul Beame, Sajin Koroth:
On Disperser/Lifting Properties of the Index and Inner-Product Functions. - Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena:
Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds. - Samuel Epstein:
Derandomization Under Different Resource Constraints. - Yaroslav Alekseev, Edward A. Hirsch:
The power of the Binary Value Principle. - Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian:
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. - Ilias Diakonikolas, Christos Tzamos, Daniel Kane:
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning. - Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang:
Round-vs-Resilience Tradeoffs for Binary Feedback Channels. - Aniruddha Biswas, Palash Sarkar:
A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture. - Louis Golowich:
A New Berry-Esseen Theorem for Expander Walks. - Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar:
Criticality of AC0-Formulae. - Lijie Chen:
New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method. - Oded Goldreich, Laliv Tauber:
Testing in the bounded-degree graph model with degree bound two. - Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal:
Randomized versus Deterministic Decision Tree Size. - Prashanth Amireddy, Sai Jayasurya, Jayalal Sarma:
Power of Decision Trees with Monotone Queries.
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-22 19:33 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: