default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2021
Volume TR21, 2021
- Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena:
Computation Over the Noisy Broadcast Channel with Malicious Parties. - Pooya Hatami, William Hoza, Avishay Tal, Roei Tell:
Fooling Constant-Depth Threshold Circuits. - Lijie Chen, Xin Lyu:
Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma. - Vishnu Iyer, Avishay Tal, Michael Whitmeyer:
Junta Distance Approximation with Sub-Exponential Queries. - Anindya De, Elchanan Mossel, Joe Neeman:
Robust testing of low-dimensional functions. - Susanna F. de Rezende, Jakob Nordström, Marc Vinyals:
How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity). - Sai Sandeep:
Almost Optimal Inapproximability of Multidimensional Packing Problems. - Akash Kumar, C. Seshadhri, Andrew Stolman:
Random walks and forbidden minors III: poly(d/?)-time partition oracles for minor-free graph classes. - Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich:
One-way Functions and Partial MCSP. - Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle:
Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity. - Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy:
Classification of the streaming approximability of Boolean CSPs. - Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson:
On the Power and Limitations of Branch and Cut. - Srinivasan Arunachalam, Penghui Yao:
Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators. - Dori Medini, Amir Shpilka:
Hitting Sets and Reconstruction for Dense Orbits in VP$_e$ and $\Sigma\Pi\Sigma$ Circuits. - Chandan Saha, Bhargav Thankey:
Hitting Sets for Orbits of Circuit Classes and Polynomial Families. - Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari:
Unambiguous DNFs from Hex. - Timothy Gowers, Emanuele Viola:
Mixing in non-quasirandom groups. - Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan:
Monotone Branching Programs: Pseudorandomness and Circuit Complexity. - Edward Pyne, Salil P. Vadhan:
Pseudodistributions That Beat All Pseudorandom Generators. - Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma:
Error Reduction For Weighted PRGs Against Read Once Branching Programs. - Per Austrin, Kilian Risse:
Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas. - Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin:
Depth lower bounds in Stabbing Planes for combinatorial principles. - Jiatu Li, Tianqi Yang
:
3.1n - o(n) Circuit Lower Bounds for Explicit Functions. - Mika Göös, Gilbert Maystre:
A Majority Lemma for Randomised Query Complexity. - Sivakanth Gopi, Venkatesan Guruswami:
Improved Maximally Recoverable LRCs using Skew Polynomials. - Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
Conditional Dichotomy of Boolean Ordered Promise CSPs. - Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu:
Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability. - Anastasia Sofronova, Dmitry Sokolov:
Branching Programs with Bounded Repetitions and Flow Formulas. - Inbar Kaslasi, Ron Rothblum, Prashant Nalini Vasudevan:
Public-Coin Statistical Zero-Knowledge Batch Verification against Malicious Verifiers. - Shuichi Hirahara, Rahul Ilango, Bruno Loff:
Hardness of Constant-round Communication Complexity. - Vaibhav Krishan:
Upper Bound for Torus Polynomials. - Justin Holmgren, Alex Lombardi, Ron Rothblum:
Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge). - Susanna F. de Rezende:
Automating Tree-Like Resolution in Time no(log n) Is ETH-Hard. - Oded Goldreich:
Robust Self-Ordering versus Local Self-Ordering. - Robert Robere, Jeroen Zuiddam:
Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms. - Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan:
Ideal-theoretic Explanation of Capacity-achieving Decoding. - Prerona Chatterjee:
Separating ABPs and Some Structured Formulas in the Non-Commutative Setting. - Alessandro Chiesa, Fermi Ma, Nicholas Spooner, Mark Zhandry:
Post-Quantum Succinct Arguments. - Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam:
Pseudodeterministic Algorithms and the Structure of Probabilistic Time. - Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira:
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1. - Zhenjian Lu, Igor Carboni Oliveira:
An Efficient Coding Theorem via Probabilistic Representations and its Applications. - Dana Moshkovitz:
Strong Parallel Repetition for Unique Games on Small Set Expanders. - Peter Dixon, Aduri Pavan, N. V. Vinodchandran:
Promise Problems Meet Pseudodeterminism. - Alexander S. Kulikov, Nikita Slezkin:
SAT-based Circuit Local Improvement. - Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich:
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits. - Uma Girish, Avishay Tal, Kewen Wu:
Fourier Growth of Parity Decision Trees. - Zander Kelley, Raghu Meka:
Random restrictions and PRGs for PTFs in Gaussian Space. - William Hoza:
Better Pseudodistributions and Derandomization for Space-Bounded Computation. - Juraj Hromkovic:
Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations. - Marshall Ball, Alper Çakan, Tal Malkin:
Linear Threshold Secret-Sharing with Binary Reconstruction. - Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$). - Benny Applebaum, Oded Nir:
Upslices, Downslices, and Secret-Sharing with Complexity of $1.5^n$. - Jan Krajícek:
Information in propositional proofs and algorithmic proof search. - James Cook, Ian Mertz:
Encodings and the Tree Evaluation Problem. - Yanyi Liu, Rafael Pass:
Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity. - Yanyi Liu, Rafael Pass:
On the Possibility of Basing Cryptography on $\EXP \neq \BPP$. - Hanlin Ren, Rahul Santhanam:
Hardness of KT Characterizes Parallel Cryptography. - Shuichi Hirahara:
Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions. - Yanyi Liu, Rafael Pass:
On One-way Functions from NP-Complete Problems. - Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Optimal Error Resilience of Adaptive Message Exchange. - Noah Fleming, Toniann Pitassi:
Reflections on Proof Complexity and Counting Principles. - Vishwas Bhargava, Sumanta Ghosh:
Improved Hitting Set for Orbit of ROABPs. - Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy:
Approximability of all finite CSPs in the dynamic streaming setting. - Noah Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming approximation resistance of every ordering CSP. - Nikhil S. Mande, Swagato Sanyal:
One-way communication complexity and non-adaptive decision trees. - Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami:
Dimension-free Bounds and Structural Results in Communication Complexity. - Zeyu Guo:
Variety Evasive Subspace Families. - Marcel de Sena Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler:
Quantum Proofs of Proximity. - Dominik Scheder:
PPSZ is better than you think. - Shuo Pang:
SOS lower bound for exact planted clique. - Samuel Epstein:
On the Algorithmic Content of Quantum Measurements. - Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu:
Arithmetic Circuit Complexity of Division and Truncation. - Emanuele Viola:
Lower bounds for samplers and data structures via the cell-probe separator. - Theodoros Papamakarios, Alexander A. Razborov:
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems. - Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao:
Affine Extractors for Almost Logarithmic Entropy. - Dmitry Sokolov:
Pseudorandom Generators, Resolution and Heavy Width. - Shir Peleg, Amir Shpilka, Ben Lee Volk:
Lower Bounds on Stabilizer Rank. - Rahul Jain, Srijita Kundu:
A direct product theorem for quantum communication complexity with applications to device-independent QKD. - Venkatesan Guruswami, Xiaoyu He, Ray Li:
The zero-rate threshold for adversarial bit-deletions is less than 1/2. - Lijie Chen, Roei Tell:
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. - Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas:
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. - Rahul Ilango, Hanlin Ren, Rahul Santhanam:
Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity. - Mark Braverman, Sumegha Garg, Or Zamir:
Tight Space Complexity of the Coin Problem. - Liron Bronfman, Ron Rothblum:
PCPs and Instance Compression from a Cryptographic Lens. - Ilya Volkovich:
The Final Nail in the Coffin of Statistically-Secure Obfuscator. - Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy:
Linear Space Streaming Lower Bounds for Approximating CSPs. - Uma Girish, Ran Raz:
Eliminating Intermediate Measurements using Pseudorandom Generators. - Oded Goldreich:
Open Problems in Property Testing of Graphs. - Hanlin Ren, Rahul Santhanam:
A Relativization Perspective on Meta-Complexity. - Divesh Aggarwal, Eldon Chung, Maciej Obremski, João Ribeiro:
On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing. - Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma:
Expander Random Walks: The General Case and Limitations. - Yanyi Liu, Rafael Pass:
A Note on One-way Functions and Sparse Languages. - Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan:
Bounded Indistinguishability for Simple Sources. - Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas:
New Non-FPT Lower Bounds for Some Arithmetic Formulas. - Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira:
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. - Boaz Menuhin, Moni Naor:
Keep That Card in Mind: Card Guessing with Limited Memory. - Jacobo Torán, Florian Wörz:
Number of Variables for Graph Identification and the Resolution of GI Formulas. - Srikanth Srinivasan, S. Venkitesh:
On the Probabilistic Degree of an $n$-variate Boolean Function. - Louis Golowich:
Improved Product-Based High-Dimensional Expanders. - Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh:
Karchmer-Wigderson Games for Hazard-free Computation. - Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan:
A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof. - Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff:
Tight bounds on the Fourier growth of bounded functions on the hypercube. - Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit:
Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields. - Sravanthi Chede, Anil Shukla:
Does QRAT simulate IR-calc? QRAT simulation algorithm for $\forall$Exp+Res cannot be lifted to IR-calc. - Suryajith Chillara:
Functional lower bounds for restricted arithmetic circuits of depth four. - Eshan Chattopadhyay, Jesse Goodman, David Zuckerman:
The Space Complexity of Sampling. - Igor Razgon:
Classification of OBDD size for monotone 2-CNFs. - Edward Pyne, Salil P. Vadhan:
Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator against Permutation Branching Programs. - Sravanthi Chede, Anil Shukla:
QRAT Polynomially Simulates Merge Resolution. - Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola:
Fourier growth of structured 𝔽2-polynomials and applications. - Aniruddha Biswas, Palash Sarkar:
Influence of a Set of Variables on a Boolean Function. - Vikraman Arvind, Venkatesan Guruswami:
CNF Satisfiability in a Subspace and Related Problems. - Nikhil S. Mande, Ronald de Wolf:
Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error. - Henning Fernau, Kshitij Gajjar:
The Space Complexity of Sum Labelling. - Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Tsun Ming Cheung:
On quantum versus classical query complexity. - Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang:
Quantum Meets the Minimum Circuit Size Problem. - Divesh Aggarwal, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Maciej Obremski, Sruthi Sekar:
Simplicity Meets Near-Optimal Rate: Non-malleable Codes and Non-malleable Two-source Extractors via Rate Boosters. - Daniel Augot, Sarah Bordage, Jade Nardi:
Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes. - Omar Alrabiah, Venkatesan Guruswami:
Visible Rank and Codes with Locality. - Roei Tell:
How to Find Water in the Ocean: A Survey on Quantified Derandomization. - Sumanta Ghosh, Rohit Gurjar:
Matroid Intersection: A pseudo-deterministic parallel reduction from search to weighted-decision. - Sabyasachi Basu, Akash Kumar, C. Seshadhri:
The complexity of testing all properties of planar graphs, and the role of isomorphism. - Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani:
On public-coin zero-error randomized communication complexity. - Iftach Haitner, Noam Mazor, Jad Silbak, Eliad Tsfadia:
On the Complexity of Two-Party Differential Privacy. - Zhiyuan Fan, Jiatu Li, Tianqi Yang:
The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs. - Yilei Chen, Qipeng Liu, Mark Zhandry:
Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering. - Ron D. Rothblum, Michael Ezra:
Small Circuits Imply Efficient Arthur-Merlin Protocols. - Xiaotie Deng, Yuhao Li, David Mguni, Jun Wang, Yaodong Yang:
On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games. - Oded Goldreich, Dana Ron:
A Lower Bound on the Complexity of Testing Grained Distributions. - Srinivasan Arunachalam, João F. Doriguello:
Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case. - Olaf Beyersdorff, Benjamin Böhm:
QCDCL with Cube Learning or Pure Literal Elimination - What is best? - Eric Binnendyk:
Pseudo-random functions and uniform learnability. - Oded Goldreich, Dana Ron:
Testing Distributions of Huge Objects.