default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2020
Volume TR20, 2020
- Or Meir, Jakob Nordström, Robert Robere, Susanna F. de Rezende:
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. - Sophie Laplante, Reza Naserasr, Anupa Sunny:
Sensitivity lower bounds from linear dependencies. - Giuseppe Persiano, Kevin Yeo:
Tight Static Lower Bounds for Non-Adaptive Data Structures. - Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný:
The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs. - Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan:
Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution. - Anup Rao, Amir Yehudayoff:
The Communication Complexity of the Exact Gap-Hamming Problem. - Claude Crépeau, Arnaud Massenet, Louis Salvail, Lucas Stinchcombe, Nan Yang:
Practical Relativistic Zero-Knowledge for NP. - Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter:
Better Secret-Sharing via Robust Conditional Disclosure of Secrets. - Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
:
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. - Lijie Chen, Hanlin Ren:
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization. - Dominik Scheder, Navid Talebanfard:
Super Strong ETH is true for strong PPSZ. - Dmitry Sokolov:
(Semi)Algebraic Proofs over ±1 Variables. - Noga Ron-Zewi, Mary Wootters, Gilles Zémor:
Linear-time Erasure List-decoding of Expander Codes. - Gil Cohen, Shahar Samocha:
Palette-Alternating Tree Codes. - Emanuele Viola:
New lower bounds for probabilistic degree and AC0 with parity gates. - Kuan Cheng, William Hoza:
Hitting Sets Give Two-Sided Derandomization of Small Space. - Alexander Kozachinskiy, Vladimir V. Podolskii:
Multiparty Karchmer-Wigderson Games and Threshold Circuits. - Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira:
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates. - Siddharth Bhandari, Prahladh Harsha:
A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet. - Nikhil S. Mande, Justin Thaler, Shuchen Zhu:
Improved Approximate Degree Bounds For $k$-distinctness. - Rahul Ilango, Bruno Loff, Igor Carboni Oliveira:
NP-Hardness of Circuit Minimization for Multi-Output Functions. - Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Interactive Error Resilience Beyond 2/7. - Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan:
Non-Malleability against Polynomial Tampering. - Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari:
Randomized and Symmetric Catalytic Computation. - Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari:
Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs. - Dean Doron, Jack Murtagh, Salil P. Vadhan, David Zuckerman:
Spectral Sparsification via Bounded-Independence Sampling. - Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan:
The Power of Many Samples in Query Complexity. - Nikhil Gupta, Chandan Saha, Bhargav Thankey:
A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits. - Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam:
Geometric Rank of Tensors and Subrank of Matrix Multiplication. - Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam:
Barriers for Rectangular Matrix Multiplication. - Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh:
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. - Suryajith Chillara:
On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits. - Suryajith Chillara:
New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree. - Erfan Khaniki:
On Proof complexity of Resolution over Polynomial Calculus. - Justin Holmgren:
No-Signaling MIPs and Faster-Than-Light Communication, Revisited. - Olaf Beyersdorff, Joshua Blinkhorn, Tomás Peitl:
Strong (D)QBF Dependency Schemes via Tautology-free Resolution Paths. - Michal Garlík:
Failure of Feasible Disjunction Property for $k$-DNF Resolution and NP-hardness of Automating It. - Ofer Grossman, Justin Holmgren:
Error Correcting Codes for Uncompressed Messages. - Pranjal Dutta, Nitin Saxena, Thomas Thierauf:
Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT. - Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný:
Topology and adjunction in promise constraint satisfaction. - Mrinal Kumar, Ben Lee Volk:
A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits. - Pranav Bisht, Nitin Saxena:
Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs. - Dorit Aharonov, Alex Bredariol Grilo:
A combinatorial MA-complete problem. - Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Nalini Vasudevan:
Cryptography from Information Loss. - Ankit Garg, Neeraj Kayal, Chandan Saha:
Learning sums of powers of low-degree polynomials in the non-degenerate case. - Srikanth Srinivasan:
A Robust Version of Hegedűs's Lemma, with Applications. - Ronen Shaltiel, Jad Silbak:
Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity. - Shachar Lovett, Raghu Meka, Jiapeng Zhang:
Improved lifting theorems via robust sunflowers. - Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi:
Automating Cutting Planes is NP-Hard. - Shuichi Hirahara:
Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions. - Rafael Pass, Muthuramakrishnan Venkitasubramaniam:
Is it Easier to Prove Theorems that are Guaranteed to be True? - Yanyi Liu, Rafael Pass:
On One-way Functions and Kolmogorov Complexity. - Olaf Beyersdorff, Benjamin Böhm:
Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution. - Marshall Ball, Oded Goldreich, Tal Malkin:
Communication Complexity with Defective Randomness. - Ashutosh Kumar, Raghu Meka, David Zuckerman:
Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing. - James Cook, Ian Mertz:
Catalytic Approaches to the Tree Evaluation Problem. - Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein:
Polynomial Data Structure Lower Bounds in the Group Model. - Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, Amir Yehudayoff:
Interactive Proofs for Verifying Machine Learning. - Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma:
Pr-ZSUBEXP is not contained in Pr-RP. - Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li:
Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols. - Deepanshu Kush, Benjamin Rossman:
Tree-depth and the Formula Complexity of Subgraph Isomorphism. - Clément L. Canonne, Karl Wimmer:
Testing Data Binnings. - Prerona Chatterjee, Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, Anamay Tengse:
On the Existence of Algebraically Natural Proofs. - Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna F. de Rezende:
Automating Algebraic Proof Systems is NP-Hard. - Lijie Chen, Ce Jin, R. Ryan Williams:
Sharp Threshold Results for Computational Complexity. - Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal:
Quantum Implications of Huang's Sensitivity Theorem. - Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin:
Computational and proof complexity of partial string avoidability. - Oded Goldreich, Dana Ron:
One-Sided Error Testing of Monomials and Affine Subspaces. - Eshan Chattopadhyay, Jyun-Jie Liao:
Optimal Error Pseudodistributions for Read-Once Branching Programs. - Ben Lund, Aditya Potukuchi:
On the list recoverability of randomly punctured codes. - Iftach Haitner, Yonatan Karidi-Heller:
A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip. - Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi:
Locally testable codes via high-dimensional expanders. - Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov:
Lower Bounds on OBDD Proofs with Several Orders. - Eric Allender, Archit Chauhan, Samir Datta:
Depth-First Search in Directed Graphs, Revisited. - Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal:
Rigid Matrices From Rectangular PCPs. - Benny Applebaum, Eliran Kachlon, Arpita Patra:
The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency. - Amit Sinhababu, Thomas Thierauf:
Factorization of Polynomials Given by Arithmetic Branching Programs. - Eric Allender:
The New Complexity Landscape around Circuit Minimization. - Hermann Gruber, Markus Holzer, Simon Wolfsteiner:
On Minimizing Regular Expressions Without Kleene Star. - Joan Bruna, Oded Regev, Min Jae Song, Yi Tang:
Continuous LWE. - Robert Andrews:
Algebraic Hardness versus Randomness in Low Characteristic. - Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals:
MaxSAT Resolution and Subcube Sums. - Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf:
Proximity Gaps for Reed-Solomon Codes. - Gil Cohen, Tal Yankovitz:
Rate Amplification and Query-Efficient Distance Amplification for Locally Decodable Codes. - Gal Vardi, Ohad Shamir:
Neural Networks with Small Weights and Depth-Separation Barriers. - Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi:
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. - Uma Girish, Ran Raz, Wei Zhan:
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. - Bill Fefferman, Zachary Remscrim:
Eliminating Intermediate Measurements in Space-Bounded Quantum Computation. - Dror Chawin, Iftach Haitner, Noam Mazor:
Lower Bounds on the Time/Memory Tradeoff of Function Inversion. - Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian:
Tight Quantum Time-Space Tradeoffs for Function Inversion. - Janaky Murthy, Vineet Nair, Chandan Saha:
Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests. - Ashish Dwivedi, Nitin Saxena:
Computing Igusa's local zeta function of univariates in deterministic polynomial-time. - Ronen Eldan, Dana Moshkovitz:
Reduction From Non-Unique Games To Boolean Unique Games. - Ronen Shaltiel:
Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? - Mikito Nanashima:
On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions. - Igor Sergeev:
On the asymptotic complexity of sorting. - Md Lutfar Rahman, Thomas Watson:
6-Uniform Maker-Breaker Game Is PSPACE-Complete. - Manindra Agrawal, Rohit Gurjar, Thomas Thierauf:
Impossibility of Derandomizing the Isolation Lemma for all Families. - Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere:
KRW Composition Theorems via Lifting. - Amit Chakrabarti, Prantar Ghosh, Justin Thaler:
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. - Uma Girish, Ran Raz, Wei Zhan:
Lower Bounds for XOR of Forrelations. - Stasys Jukna:
Notes on Hazard-Free Circuits. - Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida:
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP. - Oded Goldreich:
On Counting $t$-Cliques Mod 2. - Zoë Bell:
Automating Regular or Ordered Resolution is NP-Hard. - Eshan Chattopadhyay, Jesse Goodman:
Explicit Extremal Designs and Applications to Extractors. - Lior Gishboliner, Asaf Shapira, Henrique Stagni:
Testing linear inequalities of subgraph statistics. - Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar:
Query Complexity of Global Minimum Cut. - Oded Goldreich:
On Testing Hamiltonicity in the Bounded Degree Graph Model. - Leonid Gurvits, Jonathan Leake:
Capacity Lower Bounds via Productization. - Ian Mertz, Toniann Pitassi:
Lifting: As Easy As 1, 2, 3. - Joshua Blinkhorn:
Simulating DQBF Preprocessing Techniques with Resolution Asymmetric Tautologies. - Alessandro Chiesa, Tom Gur, Igor Shinkar:
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. - Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar:
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond. - Scott Aaronson:
The Busy Beaver Frontier. - Ivan Mihajlin, Alexander Smal:
Toward better depth lower bounds: the XOR-KRW conjecture. - Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov:
New bounds on the half-duplex communication complexity. - Oded Goldreich:
On Testing Asymmetry in the Bounded Degree Graph Model. - Nikhil S. Mande, Swagato Sanyal:
On parity decision trees for Fourier-sparse Boolean functions. - Justin Holmgren, Ran Raz:
A Parallel Repetition Theorem for the GHZ Game. - Eshan Chattopadhyay, Jason Gaitonde, Abhishek Shetty:
Fractional Pseudorandom Generators from the $k$th Fourier Level. - Joshua Cook:
Size Bounds on Low Depth Circuits for Promise Majority. - Nader H. Bshouty:
An Optimal Tester for k-Linear. - Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu:
A Strong XOR Lemma for Randomized Query Complexity. - Gaurav Sinha:
Efficient reconstruction of depth three circuits with top fan-in two. - Aayush Jain, Huijia Lin, Amit Sahai:
Indistinguishability Obfuscation from Well-Founded Assumptions. - Nikhil Bansal, Makrand Sinha:
$k$-Forrelation Optimally Separates Quantum and Classical Query Complexity. - Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu:
An Optimal Separation of Randomized and Quantum Query Complexity. - Mrinal Kumar, Ben Lee Volk:
A Lower Bound on Determinantal Complexity. - Amey Bhangale, Subhash Khot:
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups. - Rahul Jain, Srijita Kundu:
A Direct Product Theorem for One-Way Quantum Communication. - Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif:
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture. - Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma:
Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists).