All reports in year 2020:

__
TR20-001
| 31st December 2019
__

Or Meir, Jakob Nordström, Robert Robere, Susanna de Rezende#### Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

Revisions: 2

__
TR20-002
| 6th January 2020
__

Sophie Laplante, Reza Naserasr, Anupa Sunny#### Sensitivity lower bounds from linear dependencies

__
TR20-003
| 15th January 2020
__

Giuseppe Persiano, Kevin Yeo#### Tight Static Lower Bounds for Non-Adaptive Data Structures

Revisions: 1

__
TR20-004
| 17th January 2020
__

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny#### The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs

Revisions: 1

__
TR20-005
| 17th January 2020
__

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan#### Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution

Revisions: 1

__
TR20-006
| 22nd January 2020
__

Anup Rao, Amir Yehudayoff#### The Communication Complexity of the Exact Gap-Hamming Problem

__
TR20-007
| 19th December 2019
__

Claude Crépeau, Arnaud Massenet, Louis Salvail, Lucas Stinchcombe, Nan Yang#### Practical Relativistic Zero-Knowledge for NP

__
TR20-008
| 26th January 2020
__

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter#### Better Secret-Sharing via Robust Conditional Disclosure of Secrets

Revisions: 1

__
TR20-009
| 6th February 2020
__

Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality

__
TR20-010
| 12th February 2020
__

Lijie Chen, Hanlin Ren#### Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

Revisions: 1

__
TR20-011
| 9th February 2020
__

Dominik Scheder, Navid Talebanfard#### Super Strong ETH is true for strong PPSZ

__
TR20-012
| 14th February 2020
__

Dmitry Sokolov#### (Semi)Algebraic Proofs over $\{\pm 1\}$ Variables

__
TR20-013
| 17th February 2020
__

Noga Ron-Zewi, Mary Wootters, Gilles Z\'{e}mor#### Linear-time Erasure List-decoding of Expander Codes

Revisions: 1

__
TR20-014
| 16th February 2020
__

Gil Cohen, Shahar Samocha#### Palette-Alternating Tree Codes

__
TR20-015
| 18th February 2020
__

Emanuele Viola#### New lower bounds for probabilistic degree and AC0 with parity gates

Revisions: 5

__
TR20-016
| 17th February 2020
__

Kuan Cheng, William Hoza#### Hitting Sets Give Two-Sided Derandomization of Small Space

Revisions: 1

__
TR20-017
| 18th February 2020
__

Alexander Kozachinskiy, Vladimir Podolskii#### Multiparty Karchmer-Wigderson Games and Threshold Circuits

Revisions: 1

__
TR20-018
| 18th February 2020
__

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira#### Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

__
TR20-019
| 19th February 2020
__

Siddharth Bhandari, Prahladh Harsha#### A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet

__
TR20-020
| 21st February 2020
__

Nikhil Mande, Justin Thaler, Shuchen Zhu#### Improved Approximate Degree Bounds For $k$-distinctness

__
TR20-021
| 21st February 2020
__

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira#### NP-Hardness of Circuit Minimization for Multi-Output Functions

__
TR20-022
| 19th February 2020
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Interactive Error Resilience Beyond $\frac{2}{7}$

Revisions: 1

__
TR20-023
| 10th February 2020
__

Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan#### Non-Malleability against Polynomial Tampering

Revisions: 1

__
TR20-024
| 20th February 2020
__

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari#### Randomized and Symmetric Catalytic Computation

__
TR20-025
| 20th February 2020
__

Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari#### Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

__
TR20-026
| 25th February 2020
__

Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman#### Spectral Sparsification via Bounded-Independence Sampling

Revisions: 1

__
TR20-027
| 26th February 2020
__

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan#### The Power of Many Samples in Query Complexity

__
TR20-028
| 27th February 2020
__

Nikhil Gupta, Chandan Saha, Bhargav Thankey#### A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits

__
TR20-029
| 6th March 2020
__

Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam#### Geometric Rank of Tensors and Subrank of Matrix Multiplication

__
TR20-030
| 9th March 2020
__

Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam#### Barriers for Rectangular Matrix Multiplication

__
TR20-031
| 10th March 2020
__

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh#### Algebraic Branching Programs, Border Complexity, and Tangent Spaces

__
TR20-032
| 12th March 2020
__

Suryajith Chillara#### On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits

Revisions: 2

__
TR20-033
| 12th March 2020
__

Suryajith Chillara#### New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree

Revisions: 2

__
TR20-034
| 12th March 2020
__

Erfan Khaniki#### On Proof complexity of Resolution over Polynomial Calculus

Revisions: 3

__
TR20-035
| 23rd February 2020
__

Justin Holmgren#### No-Signaling MIPs and Faster-Than-Light Communication, Revisited

__
TR20-036
| 9th March 2020
__

Olaf Beyersdorff, Joshua Blinkhorn, Tomáš Peitl#### Strong (D)QBF Dependency Schemes via Tautology-free Resolution Paths

__
TR20-037
| 18th March 2020
__

Michal Garlik#### Failure of Feasible Disjunction Property for $k$-DNF Resolution and NP-hardness of Automating It

__
TR20-038
| 15th March 2020
__

Ofer Grossman, Justin Holmgren#### Error Correcting Codes for Uncompressed Messages

__
TR20-039
| 25th March 2020
__

Pranjal Dutta, Nitin Saxena, Thomas Thierauf#### Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT

__
TR20-040
| 25th March 2020
__

Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny#### Topology and adjunction in promise constraint satisfaction

Revisions: 1

__
TR20-041
| 29th March 2020
__

Mrinal Kumar, Ben Lee Volk#### A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits

Revisions: 2

__
TR20-042
| 31st March 2020
__

Pranav Bisht, Nitin Saxena#### Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs

__
TR20-043
| 29th March 2020
__

Dorit Aharonov, Alex Bredariol Grilo#### A combinatorial MA-complete problem

Revisions: 2

__
TR20-044
| 8th April 2020
__

Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan#### Cryptography from Information Loss

Revisions: 1

__
TR20-045
| 15th April 2020
__

Ankit Garg, Neeraj Kayal, Chandan Saha#### Learning sums of powers of low-degree polynomials in the non-degenerate case

Revisions: 1

__
TR20-046
| 13th April 2020
__

Srikanth Srinivasan#### A Robust Version of Heged\H{u}s's Lemma, with Applications

__
TR20-047
| 16th April 2020
__

Ronen Shaltiel, Jad Silbak#### Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity

Revisions: 2

__
TR20-048
| 16th April 2020
__

Shachar Lovett, Raghu Meka, Jiapeng Zhang#### Improved lifting theorems via robust sunflowers

__
TR20-049
| 17th April 2020
__

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi#### Automating Cutting Planes is NP-Hard

__
TR20-050
| 18th April 2020
__

Shuichi Hirahara#### Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions

__
TR20-051
| 15th April 2020
__

Rafael Pass, Muthuramakrishnan Venkitasubramaniam#### Is it Easier to Prove Theorems that are Guaranteed to be True?

__
TR20-052
| 14th April 2020
__

Yanyi Liu, Rafael Pass#### On One-way Functions and Kolmogorov Complexity

Revisions: 2

__
TR20-053
| 16th April 2020
__

Olaf Beyersdorff, Benjamin Böhm#### Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution

__
TR20-054
| 22nd April 2020
__

Marshall Ball, Oded Goldreich, Tal Malkin#### Communication Complexity with Defective Randomness

Revisions: 3

__
TR20-055
| 22nd April 2020
__

Ashutosh Kumar, Raghu Meka, David Zuckerman#### Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing

__
TR20-056
| 17th April 2020
__

James Cook, Ian Mertz#### Catalytic Approaches to the Tree Evaluation Problem

__
TR20-057
| 20th April 2020
__

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein#### Polynomial Data Structure Lower Bounds in the Group Model

__
TR20-058
| 24th April 2020
__

Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff#### Interactive Proofs for Verifying Machine Learning

Revisions: 1

__
TR20-059
| 16th April 2020
__

Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma#### Pr-ZSUBEXP is not contained in Pr-RP

Revisions: 1

__
TR20-060
| 23rd April 2020
__

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li#### Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols

__
TR20-061
| 28th April 2020
__

Deepanshu Kush, Benjamin Rossman#### Tree-depth and the Formula Complexity of Subgraph Isomorphism

__
TR20-062
| 29th April 2020
__

Clement Canonne, Karl Wimmer#### Testing Data Binnings

__
TR20-063
| 29th April 2020
__

Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse#### On the Existence of Algebraically Natural Proofs

Revisions: 1

__
TR20-064
| 2nd May 2020
__

Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna de Rezende#### Automating Algebraic Proof Systems is NP-Hard

Revisions: 1

__
TR20-065
| 2nd May 2020
__

Lijie Chen, Ce Jin, Ryan Williams#### Sharp Threshold Results for Computational Complexity

__
TR20-066
| 28th April 2020
__

Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal#### Quantum Implications of Huang's Sensitivity Theorem

__
TR20-067
| 30th April 2020
__

Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin#### Computational and proof complexity of partial string avoidability

__
TR20-068
| 3rd May 2020
__

Oded Goldreich, Dana Ron#### One-Sided Error Testing of Monomials and Affine Subspaces

Revisions: 1

__
TR20-069
| 4th May 2020
__

Eshan Chattopadhyay, Jyun-Jie Liao#### Optimal Error Pseudodistributions for Read-Once Branching Programs

Revisions: 1

__
TR20-070
| 4th May 2020
__

Ben Lund, Aditya Potukuchi#### On the list recoverability of randomly punctured codes

Revisions: 1

__
TR20-071
| 4th May 2020
__

Iftach Haitner, Yonatan Karidi-Heller#### A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip

Revisions: 1

__
TR20-072
| 5th May 2020
__

Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi#### Locally testable codes via high-dimensional expanders

__
TR20-073
| 5th May 2020
__

Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov#### Lower Bounds on OBDD Proofs with Several Orders

__
TR20-074
| 6th May 2020
__

Eric Allender, Archit Chauhan, Samir Datta#### Depth-First Search in Directed Graphs, Revisited

Revisions: 2
,
Comments: 1

__
TR20-075
| 6th May 2020
__

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal#### Rigid Matrices From Rectangular PCPs

Revisions: 2

__
TR20-076
| 17th May 2020
__

Benny Applebaum, Eliran Kachlon, Arpita Patra#### The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency

__
TR20-077
| 19th May 2020
__

Amit Sinhababu, Thomas Thierauf#### Factorization of Polynomials Given by Arithmetic Branching Programs

__
TR20-078
| 21st May 2020
__

Eric Allender#### The New Complexity Landscape around Circuit Minimization

__
TR20-079
| 15th May 2020
__

Hermann Gruber , Markus Holzer, Simon Wolfsteiner#### On Minimizing Regular Expressions Without Kleene Star

__
TR20-080
| 19th May 2020
__

Joan Bruna, Oded Regev, Min Jae Song, Yi Tang#### Continuous LWE

Revisions: 1

__
TR20-081
| 21st May 2020
__

Robert Andrews#### Algebraic Hardness versus Randomness in Low Characteristic

__
TR20-082
| 23rd May 2020
__

Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals#### MaxSAT Resolution and Subcube Sums

Revisions: 1

__
TR20-083
| 30th May 2020
__

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf#### Proximity Gaps for Reed-Solomon Codes

Revisions: 3

__
TR20-084
| 31st May 2020
__

Gil Cohen, Tal Yankovitz#### Rate Amplification and Query-Efficient Distance Amplification for Locally Decodable Codes

Revisions: 1

__
TR20-085
| 5th June 2020
__

Gal Vardi, Ohad Shamir#### Neural Networks with Small Weights and Depth-Separation Barriers

__
TR20-086
| 5th June 2020
__

Andreas Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi#### A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

__
TR20-087
| 8th June 2020
__

Uma Girish, Ran Raz, Wei Zhan#### Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

Revisions: 2

__
TR20-088
| 9th June 2020
__

Bill Fefferman, Zachary Remscrim#### Eliminating Intermediate Measurements in Space-Bounded Quantum Computation

__
TR20-089
| 8th June 2020
__

Dror Chawin, Iftach Haitner, Noam Mazor#### Lower Bounds on the Time/Memory Tradeoff of Function Inversion

Revisions: 1

__
TR20-090
| 10th June 2020
__

Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian#### Tight Quantum Time-Space Tradeoffs for Function Inversion

Revisions: 1

__
TR20-091
| 14th June 2020
__

Janaky Murthy, vineet nair, Chandan Saha#### Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests

__
TR20-092
| 16th June 2020
__

Ashish Dwivedi, Nitin Saxena#### Computing Igusa's local zeta function of univariates in deterministic polynomial-time

__
TR20-093
| 23rd June 2020
__

Ronen Eldan, Dana Moshkovitz#### Reduction From Non-Unique Games To Boolean Unique Games

Revisions: 1

__
TR20-094
| 24th June 2020
__

Ronen Shaltiel#### Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?

__
TR20-095
| 24th June 2020
__

Mikito Nanashima#### On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions

Revisions: 1

__
TR20-096
| 22nd June 2020
__

Igor Sergeev#### On the asymptotic complexity of sorting

__
TR20-097
| 30th June 2020
__

Md Lutfar Rahman, Thomas Watson#### 6-Uniform Maker-Breaker Game Is PSPACE-Complete

__
TR20-098
| 4th July 2020
__

Manindra Agrawal, Rohit Gurjar, Thomas Thierauf#### Impossibility of Derandomizing the Isolation Lemma for all Families

__
TR20-099
| 6th July 2020
__

Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere#### KRW Composition Theorems via Lifting

Revisions: 1

__
TR20-100
| 6th July 2020
__

Amit Chakrabarti, Prantar Ghosh, Justin Thaler#### Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches

__
TR20-101
| 7th July 2020
__

Uma Girish, Ran Raz, Wei Zhan#### Lower Bounds for XOR of Forrelations

__
TR20-102
| 9th July 2020
__

Stasys Jukna#### Notes on Hazard-Free Circuits

Revisions: 2

__
TR20-103
| 9th July 2020
__

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida#### One-Tape Turing Machine and Branching Program Lower Bounds for MCSP

Revisions: 1

__
TR20-104
| 12th July 2020
__

Oded Goldreich#### On Counting $t$-Cliques Mod 2

Revisions: 3

__
TR20-105
| 14th July 2020
__

Zoë Bell#### Automating Regular or Ordered Resolution is NP-Hard

__
TR20-106
| 15th July 2020
__

Eshan Chattopadhyay, Jesse Goodman#### Explicit Extremal Designs and Applications to Extractors

Revisions: 5

__
TR20-107
| 19th July 2020
__

Lior Gishboliner, Asaf Shapira, Henrique Stagni#### Testing linear inequalities of subgraph statistics

__
TR20-108
| 19th July 2020
__

Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar#### Query Complexity of Global Minimum Cut

Revisions: 1

__
TR20-109
| 19th July 2020
__

Oded Goldreich#### On Testing Hamiltonicity in the Bounded Degree Graph Model

Revisions: 2

__
TR20-110
| 22nd July 2020
__

Leonid Gurvits, Jonathan Leake#### Capacity Lower Bounds via Productization

Revisions: 1

__
TR20-111
| 24th July 2020
__

Ian Mertz, Toniann Pitassi#### Lifting: As Easy As 1,2,3

Revisions: 1

__
TR20-112
| 8th June 2020
__

Joshua Blinkhorn#### Simulating DQBF Preprocessing Techniques with Resolution Asymmetric Tautologies

__
TR20-113
| 27th July 2020
__

Alessandro Chiesa, Tom Gur, Igor Shinkar#### Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity

__
TR20-114
| 22nd July 2020
__

Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar#### Disjointness through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond

__
TR20-115
| 1st August 2020
__

Scott Aaronson#### The Busy Beaver Frontier

__
TR20-116
| 1st August 2020
__

Ivan Mihajlin, Alexander Smal#### Toward better depth lower bounds: the XOR-KRW conjecture

Revisions: 2

__
TR20-117
| 4th August 2020
__

Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov#### New bounds on the half-duplex communication complexity

Revisions: 3

__
TR20-118
| 5th August 2020
__

Oded Goldreich#### On Testing Asymmetry in the Bounded Degree Graph Model

Revisions: 4

__
TR20-119
| 1st August 2020
__

Nikhil Mande, Swagato Sanyal#### On parity decision trees for Fourier-sparse Boolean functions

__
TR20-120
| 12th August 2020
__

Justin Holmgren, Ran Raz#### A Parallel Repetition Theorem for the GHZ Game

__
TR20-121
| 3rd August 2020
__

Eshan Chattopadhyay, Jason Gaitonde, Abhishek Shetty#### Fractional Pseudorandom Generators from the $k$th Fourier Level

Revisions: 2

__
TR20-122
| 8th August 2020
__

Joshua Cook#### Size Bounds on Low Depth Circuits for Promise Majority

Revisions: 3

__
TR20-123
| 17th August 2020
__

Nader Bshouty#### An Optimal Tester for k-Linear

__
TR20-124
| 3rd August 2020
__

Joshua Brody, JaeTak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu#### A Strong XOR Lemma for Randomized Query Complexity

__
TR20-125
| 17th August 2020
__

Gaurav Sinha#### Efficient reconstruction of depth three circuits with top fan-in two

Revisions: 2

__
TR20-126
| 19th August 2020
__

Aayush Jain, Huijia Lin, Amit Sahai#### Indistinguishability Obfuscation from Well-Founded Assumptions

__
TR20-127
| 21st August 2020
__

Nikhil Bansal, Makrand Sinha#### $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity

Revisions: 2

__
TR20-128
| 3rd September 2020
__

Alexander A. Sherstov, Andrey Storozhenko, Pei Wu#### An Optimal Separation of Randomized and Quantum Query Complexity

Revisions: 1

__
TR20-129
| 5th September 2020
__

Mrinal Kumar, Ben Lee Volk#### A Lower Bound on Determinantal Complexity

__
TR20-130
| 30th August 2020
__

Amey Bhangale, Subhash Khot#### Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups

__
TR20-131
| 20th August 2020
__

Rahul Jain, Srijita Kundu#### A Direct Product Theorem for One-Way Quantum Communication

__
TR20-132
| 7th September 2020
__

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif#### Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

__
TR20-133
| 8th September 2020
__

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)

__
TR20-134
| 9th September 2020
__

Siddhesh Chaubal, Anna Gal#### Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions

__
TR20-135
| 9th September 2020
__

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen#### Estimation of Graph Isomorphism Distance in the Query World

Revisions: 2

__
TR20-136
| 11th September 2020
__

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani#### Explicit and structured sum of squares lower bounds from high dimensional expanders

__
TR20-137
| 11th September 2020
__

Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena#### Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes

__
TR20-138
| 9th September 2020
__

William Hoza, Edward Pyne, Salil Vadhan#### Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

Revisions: 1

__
TR20-139
| 11th September 2020
__

Mark Braverman, Sumegha Garg, David Woodruff#### The Coin Problem with Applications to Data Streams

__
TR20-140
| 14th September 2020
__

Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, Eric Price#### Optimal Testing of Discrete Distributions with High Probability

__
TR20-141
| 11th September 2020
__

Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan#### Candidate Tree Codes via Pascal Determinant Cubes

__
TR20-142
| 15th September 2020
__

Vahid Reza Asadi, Igor Shinkar#### Relaxed Locally Correctable Codes with Improved Parameters

__
TR20-143
| 16th September 2020
__

Shuichi Hirahara#### Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity

__
TR20-144
| 7th September 2020
__

Mohammad Jahanara, Sajin Koroth, Igor Shinkar#### Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

__
TR20-145
| 23rd September 2020
__

Andrew Drucker#### An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature

__
TR20-146
| 24th September 2020
__

Scott Aaronson, Yosi Atia, Leonard Susskind#### On the Hardness of Detecting Macroscopic Superpositions

__
TR20-147
| 24th September 2020
__

Inbar Kaslasi, Prashant Nalini Vasudevan, Guy Rothblum, Ron Rothblum, Adam Sealfon#### Batch Verification for Statistical Zero Knowledge Proofs

Revisions: 1

__
TR20-148
| 28th September 2020
__

Lijie Chen, Roei Tell#### Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost

Revisions: 1

__
TR20-149
| 29th September 2020
__

Oded Goldreich, Avi Wigderson#### Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

Revisions: 2

__
TR20-150
| 7th October 2020
__

Lijie Chen, Xin Lyu, Ryan Williams#### Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

__
TR20-151
| 8th October 2020
__

Venkatesan Guruswami, Vinayak Kumar#### Pseudobinomiality of the Sticky Random Walk

__
TR20-152
| 7th October 2020
__

Prasad Chaugule, Nutan Limaye, Shourya Pandey#### Variants of the Determinant polynomial and VP-completeness

__
TR20-153
| 6th October 2020
__

Robert Kleinberg, Daniel Mitropolsky, Christos Papadimitriou#### Total Functions in the Polynomial Hierarchy

__
TR20-154
| 10th October 2020
__

Marcel Dall'Agnol, Tom Gur, Oded Lachish#### A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy

__
TR20-155
| 18th October 2020
__

Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan#### Log-rank and lifting for AND-functions

Revisions: 1

__
TR20-156
| 22nd October 2020
__

Sankeerth Rao Karingula, Shachar Lovett#### Codes over integers, and the singularity of random matrices with large entries

Revisions: 1

__
TR20-157
| 21st October 2020
__

Guy Rothblum, Ron Rothblum#### Batch Verification and Proofs of Proximity with Polylog Overhead

__
TR20-158
| 26th October 2020
__

Eric Allender, Azucena Garvia Bosshard, Amulya Musipatla#### A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity

__
TR20-159
| 9th October 2020
__

Leroy Chew, Marijn Heule#### Relating existing powerful proof systems for QBF

__
TR20-160
| 2nd November 2020
__

Oded Goldreich, Avi Wigderson#### Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model

Revisions: 3

__
TR20-161
| 5th November 2020
__

Gil Cohen, Dean Doron, Shahar Samocha#### Seed Protecting Extractors

__
TR20-162
| 7th November 2020
__

Dean Doron, Mary Wootters#### High-Probability List-Recovery, and Applications to Heavy Hitters

Revisions: 2

__
TR20-163
| 5th November 2020
__

Gil Cohen, Noam Peri, Amnon Ta-Shma#### Expander Random Walks: A Fourier-Analytic Approach

__
TR20-164
| 9th November 2020
__

Andrej Bogdanov, Gautam Prakriya#### Direct Sum and Partitionability Testing over General Groups

Revisions: 1

__
TR20-165
| 6th November 2020
__

Sarah Bordage, Jade Nardi#### Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes

Revisions: 2

__
TR20-166
| 9th November 2020
__

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay#### Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity

Revisions: 1

__
TR20-167
| 9th November 2020
__

Venkatesan Guruswami, Sai Sandeep#### Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture

__
TR20-168
| 11th November 2020
__

Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters#### Improved List-Decodability of Reed–Solomon Codes via Tree Packings

__
TR20-169
| 11th November 2020
__

Zeyu Guo, Noga Ron-Zewi#### Efficient List-Decoding with Constant Alphabet and List Sizes

Revisions: 1

__
TR20-170
| 9th November 2020
__

Max Hopkins, Tali Kaufman, Shachar Lovett#### High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games

Revisions: 1

__
TR20-171
| 12th November 2020
__

Russell Impagliazzo, Sam McGuire#### Comparing computational entropies below majority (or: When is the dense model theorem false?)

__
TR20-172
| 13th November 2020
__

Venkatesan Guruswami, Chaoping Xing#### Optimal rate list decoding over bounded alphabets using algebraic-geometric codes

__
TR20-173
| 18th November 2020
__

Kunal Mittal, Ran Raz#### Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines

Revisions: 1

__
TR20-174
| 18th November 2020
__

Hadley Black, Iden Kalemaj, Sofya Raskhodnikova#### Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

__
TR20-175
| 24th November 2020
__

Emanuele Viola#### Fourier conjectures, correlation bounds, and Majority

Revisions: 2

__
TR20-176
| 26th November 2020
__

Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona#### Outcome Indistinguishability

__
TR20-177
| 12th October 2020
__

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira#### Counting Subgraphs in Degenerate Graphs

__
TR20-178
| 30th November 2020
__

Stasys Jukna, Hannes Seiwert, Igor Sergeev#### Reciprocal Inputs in Arithmetic and Tropical Circuits

__
TR20-179
| 2nd December 2020
__

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan#### Decoding Multivariate Multiplicity Codes on Product Sets

__
TR20-180
| 2nd December 2020
__

Yuval Filmus, Or Meir, Avishay Tal#### Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathbf{AC}^0$

Revisions: 2

__
TR20-181
| 4th December 2020
__

Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman#### Monotone Circuit Lower Bounds from Robust Sunflowers

Revisions: 1

__
TR20-182
| 3rd December 2020
__

Zander Kelley#### An Improved Derandomization of the Switching Lemma

Revisions: 1

__
TR20-183
| 6th December 2020
__

Rahul Ilango#### Constant Depth Formula and Partial Function Versions of MCSP are Hard

__
TR20-184
| 10th December 2020
__

Dmitry Itsykson, Artur Riazanov#### Proof complexity of natural formulas via communication arguments

__
TR20-185
| 1st December 2020
__

Srinivasan Arunachalam, Alex Grilo, Tom Gur, Igor Oliveira, Aarthi Sundaram#### Quantum learning algorithms imply circuit lower bounds

__
TR20-186
| 9th December 2020
__

Benjamin Rossman#### Shrinkage of Decision Lists and DNF Formulas

Revisions: 1

__
TR20-187
| 13th December 2020
__

Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse#### If VNP is hard, then so are equations for it

__
TR20-188
| 12th December 2020
__

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomáš Peitl, Gaurav Sood#### Hard QBFs for Merge Resolution

__
TR20-189
| 24th December 2020
__

Pavel Hrubes, Amir Yehudayoff#### Shadows of Newton polytopes

__
TR20-190
| 29th November 2020
__

Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma#### Erasure-Resilient Sublinear-Time Graph Algorithms

__
TR20-191
| 27th December 2020
__

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay#### Negations Provide Strongly Exponential Savings

__
TR20-192
| 27th December 2020
__

Oded Goldreich, Avi Wigderson#### Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network

__
TR20-193
| 29th December 2020
__

Xuangui Huang, Emanuele Viola#### Average-case rigidity lower bounds

Revisions: 1

Or Meir, Jakob Nordström, Robert Robere, Susanna de Rezende

We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph $G$ can be reversibly pebbled in time $t$ and space $s$ if and only if there is a Nullstellensatz refutation of the pebbling formula over $G$ in size $t+1$ ... more >>>

Sophie Laplante, Reza Naserasr, Anupa Sunny

Recently, using spectral techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least the square root of n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we ... more >>>

Giuseppe Persiano, Kevin Yeo

In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m=n^{1+\Omega(1)}$ points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend ... more >>>

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny

In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not ... more >>>

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

We provide a tight characterisation of proof size in resolution for quantified Boolean formulas (QBF) by circuit complexity. Such a characterisation was previously obtained for a hierarchy of QBF Frege systems (Beyersdorff & Pich, LICS 2016), but leaving open the most important case of QBF resolution. Different from the Frege ... more >>>

Anup Rao, Amir Yehudayoff

We prove a sharp lower bound on the distributional communication complexity of the exact gap-hamming problem.

more >>>Claude Crépeau, Arnaud Massenet, Louis Salvail, Lucas Stinchcombe, Nan Yang

In this work we consider the following problem: in a Multi-Prover environment, how close can we get to prove the validity of an NP statement in Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the 3-COLorability problem that use two (local) provers or three (entangled) provers ... more >>>

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about $s$. The collection of authorized sets is called the access structure. For over 30 years, it was ... more >>>

Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL

Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. We follow a

new approach: looking at the first Fourier level of the function after a suitable random restriction and

applying the Log-Sobolev ...
more >>>

Lijie Chen, Hanlin Ren

We prove that for all constants a, NQP = NTIME[n^{polylog(n)}] cannot be (1/2 + 2^{-log^a n})-approximated by 2^{log^a n}-size ACC^0 of THR circuits (ACC^0 circuits with a bottom layer of THR gates). Previously, it was even open whether E^NP can be (1/2+1/sqrt{n})-approximated by AC^0[2] circuits. As a straightforward application, ... more >>>

Dominik Scheder, Navid Talebanfard

We construct $k$-CNFs with $m$ variables on which the strong version of PPSZ $k$-SAT algorithm, which uses bounded width resolution, has success probability at most $2^{-(1 - (1 + \epsilon)2/k)m}$ for every $\epsilon > 0$. Previously such a bound was known only for the weak PPSZ algorithm which exhaustively searches ... more >>>

Dmitry Sokolov

One of the major open problems in proof complexity is to prove lower bounds on $AC_0[p]$-Frege proof

systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested to prove

lower bounds on the size for Polynomial Calculus over the $\{\pm 1\}$ basis. In this ...
more >>>

Noga Ron-Zewi, Mary Wootters, Gilles Z\'{e}mor

We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let $r > 0$ be any integer. Given an inner code $\cC_0$ of length $d$, and a $d$-regular bipartite expander graph $G$ with $n$ vertices on each side, we give an algorithm to list-decode the expander code $\cC ... more >>>

Gil Cohen, Shahar Samocha

A tree code is an edge-coloring of the complete infinite binary tree such that every two nodes of equal depth have a fraction--bounded away from $0$--of mismatched colors between the corresponding paths to their least common ancestor. Tree codes were introduced in a seminal work by Schulman (STOC 1993) and ... more >>>

Emanuele Viola

We prove new lower bounds for computing some functions $f:\{0,1\}^{n}\to\{0,1\}$ in $E^{NP}$ by polynomials modulo $2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results include:

(1) $\Omega(n/\log^{2}n)$ lower bounds probabilistic degree. This is optimal up to a factor $O(\log^{2}n)$. The previous best lower bound was $\Omega(\sqrt{n})$ proved in ... more >>>

Kuan Cheng, William Hoza

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if ... more >>>

Alexander Kozachinskiy, Vladimir Podolskii

We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of threshold gates. This allows us to obtain new explicit constructions of such circuits for several functions. In particular, we provide an explicit (polynomial-time computable) log-depth monotone ... more >>>

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira

The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be ... more >>>

Siddharth Bhandari, Prahladh Harsha

Recently, Cohen, Haeupler and Schulman gave an explicit construction of binary tree codes over polylogarithmic-sized output alphabet based on Pudl\'{a}k's construction of maximum-distance-separable (MDS) tree codes using totally-non-singular triangular matrices. In this short note, we give a unified and simpler presentation of Pudl\'{a}k and Cohen-Haeupler-Schulman's constructions.

more >>>Nikhil Mande, Justin Thaler, Shuchen Zhu

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the $k$-distinctness function on inputs of size $N$. While the case of $k=2$ (also called Element Distinctness) is well-understood, there is a polynomial gap between ... more >>>

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira

Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Interactive error correcting codes can protect interactive communication protocols against a constant fraction of adversarial errors, while incurring only a constant multiplicative overhead in the total communication. What is the maximum fraction of errors that such codes can protect against?

For the non-adaptive channel, where the parties must agree ... more >>>

Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan

We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials.

Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable ... more >>>

Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape which is initially filled with arbitrary content; the machine can read or write on auxiliary tape during the computation but when it halts auxiliary tape’s initial content must ... more >>>

Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari

We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight perfect matching in the graph is unique, if one exists.

As a consequence, we obtain that deciding whether the ... more >>>

Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman

We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $k\leq \log n$ and an error parameter $\varepsilon > 0$, our algorithm runs in space $\tilde{O}(k\log (N\cdot ... more >>>

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan

The randomized query complexity $R(f)$ of a boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution $D_0$ over $0$-inputs from a distribution $D_1$ over $1$-inputs, maximized over all pairs $(D_0,D_1)$. We ask: Does this task become easier if we ... more >>>

Nikhil Gupta, Chandan Saha, Bhargav Thankey

We show an $\widetilde{\Omega}(n^{2.5})$ lower bound for general depth four arithmetic circuits computing an explicit $n$-variate degree $\Theta(n)$ multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey by Shpilka and Yehudayoff (FnT-TCS, 2010), no super-quadratic lower bound was known for depth four ... more >>>

Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam

Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. We prove that the geometric rank is an upper bound on the ... more >>>

Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam

We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously ... more >>>

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most $k$ is Zariski-closed, an important property in ... more >>>

Suryajith Chillara

In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of $r$ (referred to as multi-$r$-ic circuits). The goal of this study is to make progress towards proving ... more >>>

Suryajith Chillara

Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all large enough integers $n$ and $d$ such that $d\geq \omega(\log{n})$, any syntactic depth four circuit of bounded individual degree $\delta = o(d)$ that computes the Iterated Matrix Multiplication polynomial ($IMM_{n,d}$) must have size $n^{\Omega\left(\sqrt{d/\delta}\right)}$. Unfortunately, this bound ... more >>>

Erfan Khaniki

The refutation system ${Res}_R({PC}_d)$ is a natural extension of resolution refutation system such that it operates with disjunctions of degree $d$ polynomials over ring $R$ with boolean variables. For $d=1$, this system is called ${Res}_R({lin})$. Based on properties of $R$, ${Res}_R({lin})$ systems can be too strong to prove lower ... more >>>

Justin Holmgren

We revisit one original motivation for the study of no-signaling multi-prover

interactive proofs (NS-MIPs): specifically, that two spatially separated

provers are guaranteed to be no-signaling by the physical principle that

information cannot travel from one point to another faster than light.

We observe that with ... more >>>

Olaf Beyersdorff, Joshua Blinkhorn, Tomáš Peitl

We suggest a general framework to study dependency schemes for dependency quantified Boolean formulas (DQBF). As our main contribution, we exhibit a new tautology-free DQBF dependency scheme that generalises the reflexive resolution path dependency scheme. We establish soundness of the tautology-free scheme, implying that it can be used in any ... more >>>

Michal Garlik

We show that for every integer $k \geq 2$, the Res($k$) propositional proof system does not have the weak feasible disjunction property. Next, we generalize a recent result of Atserias and Müller [FOCS, 2019] to Res($k$). We show that if NP is not included in P (resp. QP, SUBEXP) then ... more >>>

Ofer Grossman, Justin Holmgren

Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed.

We ... more >>>

Pranjal Dutta, Nitin Saxena, Thomas Thierauf

We consider the univariate polynomial $f_d:=(x+1)^d$ when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is $\Omega(d)$ for $f_d$.

We show a stunning connection of the conjecture to the two main problems in algebraic ... more >>>

Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny

The approximate graph colouring problem concerns colouring a $k$-colourable

graph with $c$ colours, where $c\geq k$. This problem naturally generalises

to promise graph homomorphism and further to promise constraint satisfaction

problems. Complexity analysis of all these problems is notoriously difficult.

In this paper, we introduce ...
more >>>

Mrinal Kumar, Ben Lee Volk

We show that there is a defining equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field $\mathbb{F}$, there is a non-zero $n^2$-variate polynomial $P \in \mathbb{F}(x_{1, 1}, \ldots, x_{n, n})$ of degree ... more >>>

Pranav Bisht, Nitin Saxena

Blackbox polynomial identity testing (PIT) affords 'extreme variable-bootstrapping' (Agrawal et al, STOC'18; PNAS'19; Guo et al, FOCS'19). This motivates us to study log-variate read-once oblivious algebraic branching programs (ROABP). We restrict width of ROABP to a constant and study the more general sum-of-ROABPs model. We give the first poly($s$)-time blackbox ... more >>>

Dorit Aharonov, Alex Bredariol Grilo

Despite the interest in the complexity class MA, the randomized analog of NP, there is just a couple of known natural (promise-)MA-complete problems, the first due to Bravyi and Terhal (SIAM Journal of Computing 2009) and the second due to Bravyi (Quantum Information and Computation 2015). Surprisingly, both problems are ... more >>>

Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan

Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is ``lossy'' reductions, where the reduction loses some information about the input ... more >>>

Ankit Garg, Neeraj Kayal, Chandan Saha

We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an $n$-variate degree-$d$ polynomial $f$ which can be written as

$$f = c_1Q_1^{m} + \ldots + c_s Q_s^{m},$$

where each $c_i\in \mathbb{F}^{\times}$, $Q_i$ is a homogeneous polynomial of degree $t$, and $t m = ...
more >>>

Srikanth Srinivasan

Heged\H{u}s's lemma is the following combinatorial statement regarding polynomials over finite fields. Over a field $\mathbb{F}$ of characteristic $p > 0$ and for $q$ a power of $p$, the lemma says that any multilinear polynomial $P\in \mathbb{F}[x_1,\ldots,x_n]$ of degree less than $q$ that vanishes at all points in $\{0,1\}^n$ of ... more >>>

Ronen Shaltiel, Jad Silbak

We consider codes for space bounded channels. This is a model for communication under noise that was introduced by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in ... more >>>

Shachar Lovett, Raghu Meka, Jiapeng Zhang

Lifting theorems are a generic way to lift lower bounds in query complexity to lower bounds in communication complexity, with applications in diverse areas, such as combinatorial optimization, proof complexity, game theory. Lifting theorems rely on a gadget, where smaller gadgets give stronger lower bounds. However, existing proof techniques are ... more >>>

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi

We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula $F$,

(1) it is NP-hard to find a CP refutation of $F$ in time polynomial in the length of the shortest such refutation; and

(2) unless Gap-Hitting-Set admits a nontrivial algorithm, one cannot find a ... more >>>

Shuichi Hirahara

Hardness of computing the Kolmogorov complexity of a given string is closely tied to a security proof of hitting set generators, and thus understanding hardness of Kolmogorov complexity is one of the central questions in complexity theory. In this paper, we develop new proof techniques for showing hardness of computing ... more >>>

Rafael Pass, Muthuramakrishnan Venkitasubramaniam

Consider the following two fundamental open problems in complexity theory: (a) Does a hard-on-average language in $\NP$ imply the existence of one-way functions?, or (b) Does a hard-on-average language in NP imply a hard-on-average problem in TFNP (i.e., the class of total NP search problem)? Our main result is that ... more >>>

Yanyi Liu, Rafael Pass

We prove the equivalence of two fundamental problems in the theory of computation:

- Existence of one-way functions: the existence of one-way functions (which in turn are equivalent to pseudorandom generators, pseudorandom functions, private-key encryption schemes, digital signatures, commitment schemes, and more).

- Mild average-case hardness of $K^{poly}$-complexity: ...
more >>>

Olaf Beyersdorff, Benjamin Böhm

QBF solvers implementing the QCDCL paradigm are powerful algorithms that

successfully tackle many computationally complex applications. However, our

theoretical understanding of the strength and limitations of these QCDCL

solvers is very limited.

In this paper we suggest to formally model QCDCL solvers as proof systems. We

define different policies that ...
more >>>

Marshall Ball, Oded Goldreich, Tal Malkin

Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness.

Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over $\ell$ bit ...
more >>>

Ashutosh Kumar, Raghu Meka, David Zuckerman

In this work we study bounded collusion protocols (BCPs) recently introduced in the context of secret sharing by Kumar, Meka, and Sahai (FOCS 2019). These are multi-party communication protocols on $n$ parties where in each round a subset of $p$-parties (the collusion bound) collude together and write a function of ... more >>>

James Cook, Ian Mertz

The study of branching programs for the Tree Evaluation Problem, introduced by S. Cook et al. (TOCT 2012), remains one of the most promising approaches to separating L from P. Given a label in $[k]$ at each leaf of a complete binary tree and an explicit function in $[k]^2 \to ... more >>>

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein

Proving super-logarithmic data structure lower bounds in the static \emph{group model} has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of $n^3$ convex polygons in $\R^2$ (each with $n^{\tilde{O}(1)}$ facets/semialgebraic-complexity), against linear storage arithmetic ... more >>>

Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff

We consider the following question: using a source of labeled data and interaction with an untrusted prover, what is the complexity of verifying that a given hypothesis is "approximately correct"? We study interactive proof systems for PAC verification, where a verifier that interacts with a prover is required to accept ... more >>>

Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma

We unconditionally prove there exists a promise problem in promise ZSUBEXP that cannot be solved in promise RP.

The proof technique builds upon Kabanets' easy witness method [Kab01] as implemented by Impagliazzo et. al [IKW02], with a separate diagonalization carried out on each of the two alternatives in the ...
more >>>

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li

In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs), in which $N$ parties wish to compute some joint function $f:(\{0,1\}^n)^N\to\{0,1\}$ using a public blackboard, but such that only $p$ parties may collude at a time. This generalizes well studied models in ... more >>>

Deepanshu Kush, Benjamin Rossman

For a fixed "pattern" graph $G$, the $\textit{colored}$ $G\textit{-subgraph isomorphism problem}$ (denoted $\mathrm{SUB}(G)$) asks, given an $n$-vertex graph $H$ and a coloring $V(H) \to V(G)$, whether $H$ contains a properly colored copy of $G$. The complexity of this problem is tied to parameterized versions of $\mathit{P}$ ${=}?$ $\mathit{NP}$ and $\mathit{L}$ ... more >>>

Clement Canonne, Karl Wimmer

Motivated by the question of data quantization and "binning," we revisit the problem of identity testing of discrete probability distributions. Identity testing (a.k.a. one-sample testing), a fundamental and by now well-understood problem in distribution testing, asks, given a reference distribution (model) $\mathbf{q}$ and samples from an unknown distribution $\mathbf{p}$, both ... more >>>

Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

For every constant c > 0, we show that there is a family {P_{N,c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, and that satisfies the following properties:

* For every family {f_n} of polynomials in VP, where f_n is an n ...
more >>>

Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna de Rezende

We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula $F$, it is NP-hard to find a refutation of $F$ in the Nullstellensatz, Polynomial Calculus, or Sherali--Adams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a ... more >>>

Lijie Chen, Ce Jin, Ryan Williams

We establish several ``sharp threshold'' results for computational complexity. For certain tasks, we can prove a resource lower bound of $n^c$ for $c \geq 1$ (or obtain an efficient circuit-analysis algorithm for $n^c$ size), there is strong intuition that a similar result can be proved for larger functions of $n$, ... more >>>

Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, ... more >>>

Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin

The partial string avoidability problem is stated as follows: given a finite set of strings with possible ``holes'' (wildcard symbols), determine whether there exists a two-sided infinite string containing no substrings from this set, assuming that a hole matches every symbol. The problem is known to be NP-hard and in ... more >>>

Oded Goldreich, Dana Ron

We consider the query complexity of three versions of the problem of testing monomials and affine (and linear) subspaces with one-sided error, and obtain the following results:

\begin{itemize}

\item The general problem, in which the arity of the monomial (resp., co-dimension of the subspace) is not specified, has ...
more >>>

Eshan Chattopadhyay, Jyun-Jie Liao

In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$ and width $w$ read-once branching programs with seed length $O(\log n\cdot \log(nw)+\log n\cdot\log(1/\varepsilon))$ and error $\varepsilon$. It remains a central question to reduce the seed length to $O(\log (nw/\varepsilon))$, which would prove that $\mathbf{BPL}=\mathbf{L}$. However, there has ... more >>>

Ben Lund, Aditya Potukuchi

We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound.

In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound.

It was previously known that there are Reed-Solomon codes that do not have this ...
more >>>

Iftach Haitner, Yonatan Karidi-Heller

In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems '83],

the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS '85], the parties communicate ...
more >>>

Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi

Locally testable codes (LTC) are error-correcting codes that have a local tester which can distinguish valid codewords from words that are far from all codewords, by probing a given word only at a very small (sublinear, typically constant) number of locations. Such codes form the combinatorial backbone of PCPs. ...
more >>>

Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov

This paper is motivated by seeking lower bounds on OBDD($\land$, weakening, reordering) refutations, namely OBDD refutations that allow weakening and arbitrary reorderings. We first work with 1-NBP($\land$) refutations based on read-once nondeterministic branching programs. These generalize OBDD($\land$, reordering) refutations. There are polynomial size 1-NBP($\land$) refutations of the pigeonhole principle, hence ... more >>>

Eric Allender, Archit Chauhan, Samir Datta

We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class UL, which is contained in nondeterministic logspace NL, which in turn lies in NC^2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm ... more >>>

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

We introduce a variant of PCPs, that we refer to as *rectangular* PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the *row* of each query and the other determining the *column*.

We ... more >>>

Benny Applebaum, Eliran Kachlon, Arpita Patra

In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with perfect (information-theoretic and error-free) security at the presence of an active (aka Byzantine) rushing adversary that controls up to $n/3$ of ... more >>>

Amit Sinhababu, Thomas Thierauf

Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size $s$, we show that all its factors can be computed by arithmetic branching programs of size $\text{poly}(s)$. Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was ... more >>>

Eric Allender

We survey recent developments related to the Minimum Circuit Size Problem

more >>>Hermann Gruber , Markus Holzer, Simon Wolfsteiner

Finite languages lie at the heart of literally every regular expression. Therefore, we investigate the approximation complexity of minimizing regular expressions without Kleene star, or, equivalently, regular expressions describing finite languages. On the side of approximation hardness, given such an expression of size~$s$, we prove that it is impossible to ... more >>>

Joan Bruna, Oded Regev, Min Jae Song, Yi Tang

We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE. Alternatively, our result can also be seen as opening new avenues ... more >>>

Robert Andrews

We show that lower bounds for explicit constant-variate polynomials over fields of characteristic $p > 0$ are sufficient to derandomize polynomial identity testing over fields of characteristic $p$. In this setting, existing work on hardness-randomness tradeoffs for polynomial identity testing requires either the characteristic to be sufficiently large or the ... more >>>

Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals

We study the MaxRes rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weakening (the system MaxResW), p-simulates tree-like resolution. In devising a lower bound technique specific to MaxRes (and not merely inheriting lower bounds from ... more >>>

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are $\delta$-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are $\delta$-close to the property. In particular, no set ... more >>>

Gil Cohen, Tal Yankovitz

In a seminal work, Kopparty et al. (J. ACM 2017) constructed asymptotically good $n$-bit locally decodable codes (LDC) with $2^{\widetilde{O}(\sqrt{\log{n}})}$ queries. A key ingredient in their construction is a distance amplification procedure by Alon et al. (FOCS 1995) which amplifies the distance $\delta$ of a code to a constant at ... more >>>

Gal Vardi, Ohad Shamir

In studying the expressiveness of neural networks, an important question is whether there are functions which can only be approximated by sufficiently deep networks, assuming their size is bounded. However, for constant depths, existing results are limited to depths $2$ and $3$, and achieving results for higher depths has been ... more >>>

Andreas Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi

Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.

more >>>Uma Girish, Ran Raz, Wei Zhan

We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary $n\times n$ contraction matrix $A$, and a parameter $T \leq poly(n)$ and outputs the entries of $A^T$, up to (arbitrary) polynomially small additive ... more >>>

Bill Fefferman, Zachary Remscrim

A foundational result in the theory of quantum computation known as the ``principle of safe storage'' shows that it is always possible to take a quantum circuit and produce an equivalent circuit that makes all measurements at the end of the computation. While this procedure is time efficient, meaning that ... more >>>

Dror Chawin, Iftach Haitner, Noam Mazor

We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an $s$-bit advice for a randomly chosen function $f\colon [n] \mapsto [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$ (i.e., to find $x$ such that $f(x)=y$). ... more >>>

Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian

In function inversion, we are given a function $f: [N] \mapsto [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower ... more >>>

Janaky Murthy, vineet nair, Chandan Saha

Equivalence testing for a polynomial family $\{g_m\}_{m \in \mathbb{N}}$ over a field F is the following problem: Given black-box access to an $n$-variate polynomial $f(\mathbb{x})$, where $n$ is the number of variables in $g_m$ for some $m \in \mathbb{N}$, check if there exists an $A \in \text{GL}(n,\text{F})$ such that $f(\mathbb{x}) ... more >>>

Ashish Dwivedi, Nitin Saxena

Igusa's local zeta function $Z_{f,p}(s)$ is the generating function that counts the number of integral roots, $N_{k}(f)$, of $f(\mathbf x) \bmod p^k$, for all $k$. It is a famous result, in analytic number theory, that $Z_{f,p}$ is a rational function in $\mathbb{Q}(p^s)$. We give an elementary proof of this fact ... more >>>

Ronen Eldan, Dana Moshkovitz

We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap $1-\delta$ vs. $1-C\delta$, for any $C> 1$, and sufficiently small $\delta>0$) to the problem of proving a PCP Theorem for a certain non-unique game.

In a previous work, Khot and Moshkovitz suggested an inefficient candidate reduction (i.e., ...
more >>>

Ronen Shaltiel

Yao's XOR lemma states that for every function $f:\set{0,1}^k \ar \set{0,1}$, if $f$ has hardness $2/3$ for $P/poly$ (meaning that for every circuit $C$ in $P/poly$, $\Pr[C(X)=f(X)] \le 2/3$ on a uniform input $X$), then the task of computing $f(X_1) \oplus \ldots \oplus f(X_t)$ for sufficiently large $t$ has hardness ... more >>>

Mikito Nanashima

A black-box (BB) reduction is a central proof technique in theoretical computer science. However, the limitations on BB reductions have been revealed for several decades, and the series of previous work gives strong evidence that we should avoid a nonadaptive BB reduction to base cryptography on NP-hardness (e.g., Akavia et ... more >>>

Igor Sergeev

We investigate the number of pairwise comparisons sufficient to sort $n$ elements chosen from a linearly ordered set. This number is shown to be $\log_2(n!) + o(n)$ thus improving over the previously known upper bounds of the form $\log_2(n!) + \Theta(n)$. The new bound is achieved by the proposed group ... more >>>

Md Lutfar Rahman, Thomas Watson

In a STOC 1976 paper, Schaefer proved that it is PSPACE-complete to determine the winner of the so-called Maker-Breaker game on a given set system, even when every set has size at most 11. Since then, there has been no improvement on this result. We prove that the game remains ... more >>>

Manindra Agrawal, Rohit Gurjar, Thomas Thierauf

The Isolation Lemma states that when random weights are assigned to the elements of a finite set $E$, then in any given family of subsets of $E$, exactly one set has the minimum weight, with high probability. In this note, we present two proofs for the fact that it is ... more >>>

Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions $f ... more >>>

Amit Chakrabarti, Prantar Ghosh, Justin Thaler

We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that ... more >>>

Uma Girish, Ran Raz, Wei Zhan

The Forrelation problem, first introduced by Aaronson [AA10] and Aaronson and Ambainis [AA15], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [AA15]; the first separation between ... more >>>

Stasys Jukna

The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design. Recently, Ikenmeyer et al. [J. ACM, 66:4 (2019), Article 25] have shown that the hazard-free circuit complexity of any Boolean function $f(x)$ is lower-bounded by the ... more >>>

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida

For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{0,1\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A ... more >>>

Oded Goldreich

For a constant integer $t$, we consider the problem of counting the number of $t$-cliques $\bmod 2$ in a given graph.

We show that this problem is not easier than determining whether a given graph contains a $t$-clique, and present a simple worst-case to average-case reduction for it. The ...
more >>>

Zoë Bell

We show that is hard to find regular or even ordered (also known as Davis-Putnam) Resolution proofs, extending the breakthrough result for general Resolution from Atserias and Müller to these restricted forms. Namely, regular and ordered Resolution are automatable if and only if P = NP. Specifically, for a CNF ... more >>>

Eshan Chattopadhyay, Jesse Goodman

An $(n,r,s)$-design, or $(n,r,s)$-partial Steiner system, is an $r$-uniform hypergraph over $n$ vertices with pairwise hyperedge intersections of size $0$, we extract from $(N,K,n,k)$-adversarial sources of locality $0$, where $K\geq N^\delta$ and $k\geq\text{polylog }n$. The previous best result (Chattopadhyay et al., STOC 2020) required $K\geq N^{1/2+o(1)}$. As a result, we ... more >>>

Lior Gishboliner, Asaf Shapira, Henrique Stagni

Property testers are fast randomized algorithms whose task is to distinguish between inputs satisfying some predetermined property ${\cal P}$ and those that are far from satisfying it. Since these algorithms operate by inspecting a small randomly selected portion of the input, the most natural property one would like to be ... more >>>

Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, where the graph can be accessed through local queries like \textsc{Degree}, \textsc{Neighbor}, and \textsc{Adjacency} queries.

Given $\epsilon \in (0,1)$, ... more >>>

Oded Goldreich

We show that testing Hamiltonicity in the bounded-degree graph model requires a linear number of queries. This refers to both the path and the cycle versions of the problem, and similar results hold also for the directed analogues.

In addition, we present an alternative proof for the known fact that ...
more >>>

Leonid Gurvits, Jonathan Leake

The purpose of this note is to state and prove a lower bound on the capacity of a real stable polynomial $p(x)$ which is based only on its value and gradient at $x=1$. This result implies a sharp improvement to a similar inequality proved by Linial-Samorodnitsky-Wigderson in 2000. Such inequalities ... more >>>

Ian Mertz, Toniann Pitassi

Query-to-communication lifting theorems translate lower bounds on query complexity to lower bounds for the corresponding communication model. In this paper, we give a simplified proof of deterministic lifting (in both the tree-like and dag-like settings). Whereas previous proofs used sophisticated Fourier analytic techniques, our proof uses elementary counting together with ... more >>>

Joshua Blinkhorn

Dependency quantified Boolean formulas (DQBF) describe an NEXPTIME-complete generalisation of QBF, which in turn generalises SAT. QRAT is a recently proposed proof system for quantified Boolean formulas (QBF), which simulates the full suite of QBF preprocessing techniques and thus forms a uniform proof checking format for solver verification.

In this ... more >>>

Alessandro Chiesa, Tom Gur, Igor Shinkar

Locally correctable codes (LCCs) are error correcting codes C : \Sigma^k \to \Sigma^n which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. This notion is stronger than that of locally decodable codes (LDCs), where the goal is to only recover ... more >>>

Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

The disjointness problem - where Alice and Bob are given two subsets of $\{1, \dots, n\}$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be ... more >>>

Scott Aaronson

The Busy Beaver function, with its incomprehensibly rapid growth, has captivated generations of computer scientists, mathematicians, and hobbyists. In this survey, I offer a personal view of the BB function 58 years after its introduction, emphasizing lesser-known insights, recent progress, and especially favorite open problems. Examples of such problems include: ... more >>>

Ivan Mihajlin, Alexander Smal

In this paper, we propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture [KRW95]. This relaxation is still strong enough to imply $\mathbf{P} \not\subseteq \mathbf{NC}^1$ if proven. We also present a weaker version of this conjecture that might be used for breaking $n^3$ lower ... more >>>

Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov

In this work, we continue the research started in [HIMS18], where the authors suggested to study the half-duplex communication complexity. Unlike the classical model of communication complexity introduced by Yao, in the half-duplex model, Alice and Bob can speak or listen simultaneously, as if they were talking using a walkie-talkie. ... more >>>

Oded Goldreich

We consider the problem of testing asymmetry in the bounded-degree graph model, where a graph is called asymmetric if the identity permutation is its only automorphism. Seeking to determine the query complexity of this testing problem, we provide partial results. Considering the special case of $n$-vertex graphs with connected components ... more >>>

Nikhil Mande, Swagato Sanyal

We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Our contributions are as follows. Let $f : \mathbb{F}_2^n \to \{-1, 1\}$ be a Boolean function with Fourier support ... more >>>

Justin Holmgren, Ran Raz

We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel $t$ times is at most $t^{-\Omega(1)}$. Previously, only a bound of $\approx \frac{1}{\alpha(t)}$, where $\alpha$ is the inverse Ackermann ... more >>>

Eshan Chattopadhyay, Jason Gaitonde, Abhishek Shetty

In recent work by Chattopadhyay et al.[CHHL19,CHLT19], the authors exhibit a simple and flexible construction of pseudorandom generators for classes of Boolean functions that satisfy $L_1$ Fourier bounds. [CHHL19] show that if a class satisfies such tail bounds at all levels, this implies a PRG whose seed length depends on ... more >>>

Joshua Cook

We give two results on the size of AC0 circuits computing promise majority. $\epsilon$-promise majority is majority promised that either at most an $\epsilon$ fraction of the input bits are 1, or at most $\epsilon$ are 0.

First, we show super quadratic lower bounds on both monotone and general depth ... more >>>

Nader Bshouty

A Boolean function $f:\{0,1\}^n\to \{0,1\}$ is $k$-linear if it returns the sum (over the binary field $F_2$) of $k$ coordinates of the input. In this paper, we study property testing of the classes $k$-Linear, the class of all $k$-linear functions, and $k$-Linear$^*$, the class $\cup_{j=0}^kj$-Linear.

We give a non-adaptive distribution-free ...
more >>>

Joshua Brody, JaeTak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu

We give a strong direct sum theorem for computing $XOR \circ g$. Specifically, we show that the randomized query complexity of computing the XOR of $k$ instances of $g$ satisfies $\bar{R}_\varepsilon(XOR \circ g)=\Theta(\bar{R}_{\varepsilon/k}(g))$. This matches the naive success amplification bound and answers a question of Blais and Brody.

As a ... more >>>

Gaurav Sinha

In this paper we develop efficient randomized algorithms to solve the black-box reconstruction problem for polynomials(over finite fields) computable by depth three arithmetic circuits with alternating addition/multiplication gates, such that top(output) gate is an addition gate with in-degree $2$. Such circuits naturally compute polynomials of the form $G\times(T_1 + T_2)$, ... more >>>

Aayush Jain, Huijia Lin, Amit Sahai

In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove:

Let $\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)$ be arbitrary constants. Assume sub-exponential security of the following assumptions, where $\lambda$ is a security parameter, and the parameters $\ell,k,n$ below ... more >>>

Nikhil Bansal, Makrand Sinha

Aaronson and Ambainis (SICOMP '18) showed that any partial function on $N$ bits that can be computed with an advantage $\delta$ over a random guess by making $q$ quantum queries, can also be computed classically with an advantage $\delta/2$ by a randomized decision tree making ${O}_q(N^{1-\frac{1}{2q}}\delta^{-2})$ queries. Moreover, they conjectured ... more >>>

Alexander A. Sherstov, Andrey Storozhenko, Pei Wu

We prove that for every decision tree, the absolute values of the Fourier coefficients of given order $\ell\geq1$ sum to at most $c^{\ell}\sqrt{{d\choose\ell}(1+\log n)^{\ell-1}},$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant. This bound is essentially tight and settles a ... more >>>

Mrinal Kumar, Ben Lee Volk

The determinantal complexity of a polynomial $P \in \mathbb{F}[x_1, \ldots, x_n]$ over a field $\mathbb{F}$ is the dimension of the smallest matrix $M$ whose entries are affine functions in $\mathbb{F}[x_1, \ldots, x_n]$ such that $P = Det(M)$. We prove that the determinantal complexity of the polynomial $\sum_{i = 1}^n x_i^n$ ... more >>>

Amey Bhangale, Subhash Khot

A seminal result of H\r{a}stad [J. ACM, 48(4):798–859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of the constraints, for any constant ... more >>>

Rahul Jain, Srijita Kundu

We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. For any $\varepsilon, \zeta > 0$ and any $k\geq1$, we show that

\[ \mathrm{Q}^1_{1-(1-\varepsilon)^{\Omega(\zeta^6k/\log|\mathcal{Z}|)}}(f^k) = \Omega\left(k\left(\zeta^5\cdot\mathrm{Q}^1_{\varepsilon + 12\zeta}(f) - \log\log(1/\zeta)\right)\right),\]

where $\mathrm{Q}^1_{\varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with ...
more >>>

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $\Theta(n)$. This improves upon the ... more >>>

Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma

A binary code $\text{Enc}:\{0,1\}^k \rightarrow \{0,1\}^n$ is $(\frac{1}{2}-\varepsilon,L)$-list decodable if for every $w \in \{0,1\}^n$, there exists a set $\text{List}(w)$ of size at most $L$, containing all messages $m \in \{0,1\}^k$ such that the relative Hamming distance between $\text{Enc}(m)$ and $w$ is at most $\frac{1}{2}-\varepsilon$.

A $q$-query local list-decoder is ...
more >>>

Siddhesh Chaubal, Anna Gal

Nisan and Szegedy conjectured that block sensitivity is at most

polynomial in sensitivity for any Boolean function.

Until a recent breakthrough of Huang, the conjecture had been

wide open in the general case,

and was proved only for a few special classes

of Boolean functions.

Huang's result implies that block ...
more >>>

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

The graph isomorphism distance between two graphs $G_u$ and $G_k$ is the fraction of entries in the adjacency matrix that has to be changed to make $G_u$ isomorphic to $G_k$. We study the problem of estimating, up to a constant additive factor, the graph isomorphism distance between two graphs in ... more >>>

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

We construct an explicit family of 3XOR instances which is hard for Omega(sqrt(log n)) levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time.

Our construction is based on the high-dimensional expanders devised by Lubotzky, ...
more >>>

Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena

The field of Interactive Coding studies how an interactive protocol can be made resilient to channel errors. Even though this field has received abundant attention since Schulman's seminal paper (FOCS 92), constructing interactive coding schemes that are both deterministic and efficient, and at the same time resilient to adversarial errors ... more >>>

William Hoza, Edward Pyne, Salil Vadhan

We prove that the Impagliazzo-Nisan-Wigderson (STOC 1994) pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of $\widetilde{O}(\log d + \log n \cdot \log(1/\varepsilon))$, assuming the program has only one accepting vertex in the final layer. Here, $n$ is the length of the ... more >>>

Mark Braverman, Sumegha Garg, David Woodruff

Consider the problem of computing the majority of a stream of $n$ i.i.d. uniformly random bits. This problem, known as the {\it coin problem}, is central to a number of counting problems in different data stream models. We show that any streaming algorithm for solving this problem with large constant ... more >>>

Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, Eric Price

We study the problem of testing discrete distributions with a focus on the high probability regime.

Specifically, given samples from one or more discrete distributions, a property $\mathcal{P}$, and

parameters $0< \epsilon, \delta <1$, we want to distinguish {\em with probability at least $1-\delta$}

whether these distributions satisfy $\mathcal{P}$ ...
more >>>

Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan

Tree codes are combinatorial structures introduced by Schulman (STOC 1993) as key ingredients in interactive coding schemes. Asymptotically-good tree codes are long known to exist, yet their explicit construction remains a notoriously hard open problem. Even proposing a plausible construction, without the burden of proof, is difficult and the defining ... more >>>

Vahid Reza Asadi, Igor Shinkar

Locally decodable codes (LDCs) are error-correcting codes $C : \Sigma^k \to \Sigma^n$ that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. An important question in this line of research is to understand the optimal trade-off ... more >>>

Shuichi Hirahara

We exactly characterize the average-case complexity of the polynomial-time hierarchy (PH) by the worst-case (meta-)complexity of GapMINKT(PH), i.e., an approximation version of the problem of determining if a given string can be compressed to a short PH-oracle efficient program. Specifically, we establish the following equivalence:

DistPH is contained in ... more >>>

Mohammad Jahanara, Sajin Koroth, Igor Shinkar

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is ... more >>>

Andrew Drucker

"Games against Nature" [Papadimitriou '85] are two-player games of perfect information, in which one player's moves are made randomly (here, uniformly); the final payoff to the non-random player is given by some $[0, 1]$-valued function of the move history. Estimating the value of such games under optimal play, and computing ... more >>>

Scott Aaronson, Yosi Atia, Leonard Susskind

When is decoherence "effectively irreversible"? Here we examine this central question of quantum foundations using the tools of quantum computational complexity. We prove that, if one had a quantum circuit to determine if a system was in an equal superposition of two orthogonal states (for example, the $|$Alive$\rangle$ and $|$Dead$\rangle$ ... more >>>

Inbar Kaslasi, Prashant Nalini Vasudevan, Guy Rothblum, Ron Rothblum, Adam Sealfon

A statistical zero-knowledge proof (SZK) for a problem $\Pi$ enables a computationally unbounded prover to convince a polynomial-time verifier that $x \in \Pi$ without revealing any additional information about $x$ to the verifier, in a strong information-theoretic sense.

Suppose, however, that the prover wishes to convince the verifier that $k$ ... more >>>

Lijie Chen, Roei Tell

Extending the classical ``hardness-to-randomness'' line-of-works, Doron et al. (FOCS 2020) recently proved that derandomization with near-quadratic time overhead is possible, under the assumption that there exists a function in $\mathcal{DTIME}[2^n]$ that cannot be computed by randomized SVN circuits of size $2^{(1-\epsilon)\cdot n}$ for a small $\epsilon$.

In this work we ... more >>>

Oded Goldreich, Avi Wigderson

A graph $G$ is called {\em self-ordered}\/ (a.k.a asymmetric) if the identity permutation is its only automorphism.

Equivalently, there is a unique isomorphism from $G$ to any graph that is isomorphic to $G$.

We say that $G=(V,E)$ is {\em robustly self-ordered}\/ if the size of the symmetric difference ...
more >>>

Lijie Chen, Xin Lyu, Ryan Williams

In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether $\mathrm{NEXP} \subset \mathrm{i.o.-}\mathrm{NP}$; that is, it is open whether nondeterministic exponential time computations can be simulated on infinitely ... more >>>

Venkatesan Guruswami, Vinayak Kumar

Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number $M$ of marked vertices visited in a long $n$-step random walk strongly concentrates around the ... more >>>

Prasad Chaugule, Nutan Limaye, Shourya Pandey

The determinant is a canonical VBP-complete polynomial in the algebraic complexity setting. In this work, we introduce two variants of the determinant polynomial which we call $StackDet_n(X)$ and $CountDet_n(X)$ and show that they are VP and VNP complete respectively under $p$-projections. The definitions of the polynomials are inspired by a ... more >>>

Robert Kleinberg, Daniel Mitropolsky, Christos Papadimitriou

We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string ... more >>>

Marcel Dall'Agnol, Tom Gur, Oded Lachish

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes $q$ adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with $n^{1- 1/O(q^2 ... more >>>

Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan

Let $f: \{0,1\}^n \to \{0, 1\}$ be a boolean function, and let $f_\land (x, y) = f(x \land y)$ denote the AND-function of $f$, where $x \land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_\land$ and show that, up to a $\log n$ factor, it is ... more >>>

Sankeerth Rao Karingula, Shachar Lovett

The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be ... more >>>

Guy Rothblum, Ron Rothblum

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication (without making cryptographic assumptions or bounding the computational power of a malicious Alice)? ... more >>>

Eric Allender, Azucena Garvia Bosshard, Amulya Musipatla

This paper focuses on a variant of the circuit minimization problem (MCSP), denoted MKTP, which studies resource-bounded Kolmogorov complexity in place of circuit size. MCSP is not known to be hard for any complexity class under any kind of m-reducibility, but recently MKTP was shown to be hard for DET ... more >>>

Leroy Chew, Marijn Heule

We advance the theory of QBF proof systems by showing the first simulation of the universal checking format QRAT by a theory-friendly system. We show that the sequent system G fully p-simulates QRAT, including the Extended Universal Reduction (EUR) rule which was recently used to show QRAT does not ... more >>>

Oded Goldreich, Avi Wigderson

We study the relation between the query complexity of adaptive and non-adaptive testers in the dense graph model.

It has been known for a couple of decades that the query complexity of non-adaptive testers is at most quadratic in the query complexity of adaptive testers.

We show that ...
more >>>

Gil Cohen, Dean Doron, Shahar Samocha

We introduce a new type of seeded extractors we dub seed protecting extractors. Informally, a seeded extractor is seed protecting against a class of functions $C$, mappings seeds to seeds, if the seed $Y$ remains close to uniform even after observing the output $\mathrm{Ext}(X,A(Y))$ for every choice of $A \in ... more >>>

Dean Doron, Mary Wootters

An error correcting code $\mathcal{C} \colon \Sigma^k \to \Sigma^n$ is list-recoverable from input list size $\ell$ if for any sets $\mathcal{L}_1, \ldots, \mathcal{L}_n \subseteq \Sigma$ of size at most $\ell$, one can efficiently recover the list $\mathcal{L} = \{ x \in \Sigma^k : \forall j \in [n], \mathcal{C}(x)_j \in \mathcal{L}_j ... more >>>

Gil Cohen, Noam Peri, Amnon Ta-Shma

In this work we ask the following basic question: assume the vertices of an expander graph are labelled by $0,1$. What "test" functions $f : \{ 0,1\}^t \to \{0,1\}$ cannot distinguish $t$ independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and ... more >>>

Andrej Bogdanov, Gautam Prakriya

A function $f(x_1, \dots, x_n)$ from a product domain $\mathcal{D}_1 \times \cdots \times \mathcal{D}_n$ to an abelian group $\mathcal{G}$ is a direct sum if it is of the form $f_1(x_1) + \cdots + f_n(x_n)$. We present a new 4-query direct sum test with optimal (up to constant factors) soundness error. ... more >>>

Sarah Bordage, Jade Nardi

In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code $C = C(\mathcal C, \mathcal P, D)$ is a vector space associated to evaluations on $\mathcal P$ of functions in the Riemann-Roch space $L_\mathcal C(D)$. The problem of testing proximity to an ... more >>>

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of polynomials $P_n$ in $n$ variables, each of its monomials has positive coefficient, such that $P_n$ can be computed ... more >>>

Venkatesan Guruswami, Sai Sandeep

A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib who proposed a hypergraph version of this ... more >>>

Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters

This paper shows that there exist Reed--Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any $\epsilon\in (0,1]$ there exist RS codes with rate $\Omega(\frac{\epsilon}{\log(1/\epsilon)+1})$ that are list-decodable from radius of ... more >>>

Zeyu Guo, Noga Ron-Zewi

We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any $R \in (0,1)$ and $\epsilon>0$, we give an algebraic construction of an infinite family of error-correcting codes of rate $R$, over an alphabet of size ... more >>>

Max Hopkins, Tali Kaufman, Shachar Lovett

Higher order random walks (HD-walks) on high dimensional expanders have played a crucial role in a number of recent breakthroughs in theoretical computer science, perhaps most famously in the recent resolution of the Mihail-Vazirani conjecture (Anari et al. STOC 2019), which focuses on HD-walks on one-sided local-spectral expanders. In this ... more >>>

Russell Impagliazzo, Sam McGuire

Computational pseudorandomness studies the extent to which a random variable $\bf{Z}$ looks like the uniform distribution according to a class of tests $\cal{F}$. Computational entropy generalizes computational pseudorandomness by studying the extent which a random variable looks like a \emph{high entropy} distribution. There are different formal definitions of computational entropy ... more >>>

Venkatesan Guruswami, Chaoping Xing

We construct two classes of algebraic code families which are efficiently list decodable with small output list size from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The alphabet size depends only on $\epsilon$ and is nearly-optimal.

The ... more >>>

Kunal Mittal, Ran Raz

We prove that a sufficiently strong parallel repetition theorem for a special case of multiplayer (multiprover) games implies super-linear lower bounds for multi-tape Turing machines with advice. To the best of our knowledge, this is the first connection between parallel repetition and lower bounds for time complexity and the first ... more >>>

Hadley Black, Iden Kalemaj, Sofya Raskhodnikova

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real-valued functions $f \colon \{0,1\}^d\to\mathbb{R}$. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real-valued function $f$ over an arbitrary partially ... more >>>

Emanuele Viola

Recently several conjectures were made regarding the Fourier spectrum of low-degree polynomials. We show that these conjectures imply new correlation bounds for functions related to Majority. Then we prove several new results on correlation bounds which aim to, but don't, resolve the conjectures. In particular, we prove several new results ... more >>>

Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona

Prediction algorithms assign numbers to individuals that are popularly understood as individual ``probabilities''---what is the probability of 5-year survival after cancer diagnosis?---and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are ... more >>>

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

We consider the problem of counting the number of copies of a fixed graph $H$ within an input graph $G$. This is one of the most well-studied algorithmic graph problems, with many theoretical and practical applications. We focus on solving this problem when the input $G$ has {\em bounded degeneracy}. ... more >>>

Stasys Jukna, Hannes Seiwert, Igor Sergeev

It is known that the size of monotone arithmetic $(+,\ast)$ circuits can be exponentially decreased by allowing just one division "at the very end," at the output gate. A natural question is: can the size of $(+,\ast)$ circuits be substantially reduced if we allow divisions "at the very beginning," that ... more >>>

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these ... more >>>

Yuval Filmus, Or Meir, Avishay Tal

Håstad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of $O(p^{2})$ under a random restriction that leaves each variable alive independently with probability $p$ [SICOMP, 1998]. Using this result, he gave an $\widetilde{\Omega}(n^{3})$ formula size lower bound for the Andreev function, ... more >>>

Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman

Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity, DNF sparsification, randomness extractors, and recent advances on the Erd\H{o}s-Rado sunflower conjecture. The recent breakthrough of Alweiss, Lovett, Wu and Zhang gives an improved bound on the maximum size of a $w$-set system that excludes ... more >>>

Zander Kelley

We prove a new derandomization of Håstad's switching lemma, showing how to efficiently generate restrictions satisfying the switching lemma for DNF or CNF formulas of size $m$ using only $\widetilde{O}(\log m)$ random bits. Derandomizations of the switching lemma have been useful in many works as a key building-block for constructing ... more >>>

Rahul Ilango

Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions.

While ... more >>>

Dmitry Itsykson, Artur Riazanov

A canonical communication problem ${\rm Search}(\phi)$ is defined for every unsatisfiable CNF $\phi$: an assignment to the variables of $\phi$ is distributed among the communicating parties, they are to find a clause of $\phi$ falsified by this assignment. Lower bounds on the randomized $k$-party communication complexity of ${\rm Search}(\phi)$ in ... more >>>

Srinivasan Arunachalam, Alex Grilo, Tom Gur, Igor Oliveira, Aarthi Sundaram

We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let $\mathrm{C}$ be a class of polynomial-size concepts, and suppose that $\mathrm{C}$ can be PAC-learned with membership queries under the uniform distribution with error $1/2 - \gamma$ by a time $T$ quantum algorithm. ... more >>>

Benjamin Rossman

We establish nearly tight bounds on the expected shrinkage of decision lists and DNF formulas under the $p$-random restriction $\mathbf R_p$ for all values of $p \in [0,1]$. For a function $f$ with domain $\{0,1\}^n$, let $\mathrm{DL}(f)$ denote the minimum size of a decision list that computes $f$. We show ... more >>>

Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP *does not* have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size.

In a ... more >>>

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomáš Peitl, Gaurav Sood

We prove the first proof size lower bounds for the proof system Merge Resolution (MRes [Olaf Beyersdorff et al., 2020]), a refutational proof system for prenex quantified Boolean formulas (QBF) with a CNF matrix. Unlike most QBF resolution systems in the literature, proofs in MRes consist of resolution steps together ... more >>>

Pavel Hrubes, Amir Yehudayoff

We define the shadow complexity of a polytope P as the maximum number of vertices in a linear projection of $P$ to the plane. We describe connections to algebraic complexity and to parametrized optimization. We also provide several basic examples and constructions, and develop tools for bounding shadow complexity.

Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

We investigate sublinear-time algorithms that take partially erased graphs represented by adjacency lists as input. Our algorithms make degree and neighbor queries to the input graph and work with a specified fraction of adversarial erasures in adjacency entries. We focus on two computational tasks: testing if a graph is connected ... more >>>

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

We show that there is a family of monotone multilinear polynomials over $n$ variables in VP, such that any monotone arithmetic circuit for it would be of size $2^{\Omega(n)}$. Before our result, strongly exponential lower bounds on the size of monotone circuits were known only for computing explicit polynomials in ... more >>>

Oded Goldreich, Avi Wigderson

We consider the problem of efficiently constructing an as large as possible family of permutations such that each pair of permutations are far part (i.e., disagree on a constant fraction of their inputs).

Specifically, for every $n\in\N$, we present a collection of $N=N(n)=(n!)^{\Omega(1)}$ pairwise far apart permutations $\{\pi_i:[n]\to[n]\}_{i\in[N]}$ and ...
more >>>

Xuangui Huang, Emanuele Viola

It is shown that there exists $f : \{0,1\}^{n/2} \times \{0,1\}^{n/2} \to \{0,1\}$ in E$^\mathbf{NP}$ such that for every $2^{n/2} \times 2^{n/2}$ matrix $M$ of rank $\le \rho$ we have $\P_{x,y}[f(x,y)\ne M_{x,y}] \ge 1/2-2^{-\Omega(k)}$, where $k \leq \Theta(\sqrt{n})$ and $\log \rho \leq \delta n/k(\log n + k)$ for a sufficiently ... more >>>