All reports in year 2021:

__
TR21-001
| 1st January 2021
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Computation Over the Noisy Broadcast Channel with Malicious Parties

__
TR21-002
| 8th January 2021
__

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell#### Fooling Constant-Depth Threshold Circuits

Revisions: 1

__
TR21-003
| 6th January 2021
__

Lijie Chen, Xin Lyu#### Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma

__
TR21-004
| 10th January 2021
__

Vishnu Iyer, Avishay Tal, Michael Whitmeyer#### Junta Distance Approximation with Sub-Exponential Queries

__
TR21-005
| 13th January 2021
__

Anindya De, Elchanan Mossel, Joe Neeman#### Robust testing of low-dimensional functions

__
TR21-006
| 18th January 2021
__

Susanna de Rezende, Jakob Nordström, Marc Vinyals#### How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)

__
TR21-007
| 14th January 2021
__

Sai Sandeep#### Almost Optimal Inapproximability of Multidimensional Packing Problems

__
TR21-008
| 30th January 2021
__

Akash Kumar, C. Seshadhri, Andrew Stolman#### Random walks and forbidden minors III: poly(d/?)-time partition oracles for minor-free graph classes

Revisions: 3

__
TR21-009
| 1st February 2021
__

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich#### One-way Functions and Partial MCSP

Revisions: 3
,
Comments: 1

__
TR21-010
| 11th February 2021
__

Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle#### Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity

Revisions: 1

__
TR21-011
| 13th February 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy#### Classification of the streaming approximability of Boolean CSPs

Revisions: 3
,
Comments: 1

__
TR21-012
| 9th February 2021
__

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson#### On the Power and Limitations of Branch and Cut

Revisions: 1

__
TR21-013
| 20th January 2021
__

Srinivasan Arunachalam, Penghui Yao#### Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

__
TR21-014
| 15th February 2021
__

Dori Medini, Amir Shpilka#### Hitting Sets and Reconstruction for Dense Orbits in VP$_e$ and $\Sigma\Pi\Sigma$ Circuits

__
TR21-015
| 15th February 2021
__

Chandan Saha, Bhargav Thankey#### Hitting Sets for Orbits of Circuit Classes and Polynomial Families

Revisions: 2

__
TR21-016
| 16th February 2021
__

Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari#### Unambiguous DNFs from Hex

Revisions: 1

__
TR21-017
| 19th February 2021
__

Timothy Gowers, Emanuele Viola#### Mixing in non-quasirandom groups

__
TR21-018
| 20th February 2021
__

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan#### Monotone Branching Programs: Pseudorandomness and Circuit Complexity

Revisions: 1

__
TR21-019
| 17th February 2021
__

Edward Pyne, Salil Vadhan#### Pseudodistributions That Beat All Pseudorandom Generators

Revisions: 1

__
TR21-020
| 15th February 2021
__

Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma#### Error Reduction For Weighted PRGs Against Read Once Branching Programs

__
TR21-021
| 18th February 2021
__

Per Austrin, Kilian Risse#### Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas

Revisions: 1

__
TR21-022
| 20th February 2021
__

Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin#### Depth lower bounds in Stabbing Planes for combinatorial principles

Revisions: 1

__
TR21-023
| 20th February 2021
__

Jiatu Li, Tianqi Yang#### $3.1n - o(n)$ Circuit Lower Bounds for Explicit Functions

__
TR21-024
| 15th February 2021
__

Mika Göös, Gilbert Maystre#### A Majority Lemma for Randomised Query Complexity

__
TR21-025
| 15th February 2021
__

Sivakanth Gopi, Venkatesan Guruswami#### Improved Maximally Recoverable LRCs using Skew Polynomials

__
TR21-026
| 23rd February 2021
__

Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep#### Conditional Dichotomy of Boolean Ordered Promise CSPs

__
TR21-027
| 24th February 2021
__

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu#### Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability

__
TR21-028
| 27th February 2021
__

Anastasia Sofronova, Dmitry Sokolov#### Branching Programs with Bounded Repetitions and $\mathrm{Flow}$ Formulas

__
TR21-029
| 1st March 2021
__

Inbar Kaslasi, Ron Rothblum, Prashant Nalini Vasudevan#### Public-Coin Statistical Zero-Knowledge Batch Verification against Malicious Verifiers

__
TR21-030
| 2nd March 2021
__

Shuichi Hirahara, Rahul Ilango, Bruno Loff#### Hardness of Constant-round Communication Complexity

__
TR21-031
| 3rd March 2021
__

Vaibhav Krishan#### Upper Bound for Torus Polynomials

__
TR21-032
| 5th March 2021
__

Justin Holmgren, Alex Lombardi, Ron Rothblum#### Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge)

__
TR21-033
| 7th March 2021
__

Susanna de Rezende#### Automating Tree-Like Resolution in Time $n^{o(\log n)}$ Is ETH-Hard

__
TR21-034
| 9th March 2021
__

Oded Goldreich#### Robust Self-Ordering versus Local Self-Ordering

__
TR21-035
| 13th March 2021
__

Robert Robere, Jeroen Zuiddam#### Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms

Revisions: 1

__
TR21-036
| 14th March 2021
__

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan#### Ideal-theoretic Explanation of Capacity-achieving Decoding

__
TR21-037
| 1st March 2021
__

Prerona Chatterjee#### Separating ABPs and Some Structured Formulas in the Non-Commutative Setting

__
TR21-038
| 15th March 2021
__

Alessandro Chiesa, Fermi Ma, Nicholas Spooner, Mark Zhandry#### Post-Quantum Succinct Arguments

Revisions: 1

__
TR21-039
| 15th March 2021
__

Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam#### Pseudodeterministic Algorithms and the Structure of Probabilistic Time

__
TR21-040
| 15th March 2021
__

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira#### Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1

__
TR21-041
| 15th March 2021
__

Zhenjian Lu, Igor Carboni Oliveira#### An Efficient Coding Theorem via Probabilistic Representations and its Applications

__
TR21-042
| 16th March 2021
__

Dana Moshkovitz#### Strong Parallel Repetition for Unique Games on Small Set Expanders

Revisions: 1

__
TR21-043
| 15th March 2021
__

Peter Dixon, A. Pavan, N. V. Vinodchandran#### Promise Problems Meet Pseudodeterminism

__
TR21-044
| 14th February 2021
__

Alexander Kulikov, Nikita Slezkin#### SAT-based Circuit Local Improvement

__
TR21-045
| 22nd March 2021
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits

__
TR21-046
| 22nd March 2021
__

Uma Girish, Avishay Tal, Kewen Wu#### Fourier Growth of Parity Decision Trees

__
TR21-047
| 26th March 2021
__

Zander Kelley, Raghu Meka#### Random restrictions and PRGs for PTFs in Gaussian Space

Revisions: 1

__
TR21-048
| 27th March 2021
__

William Hoza#### Better Pseudodistributions and Derandomization for Space-Bounded Computation

Revisions: 1

__
TR21-049
| 1st April 2021
__

Juraj Hromkovic#### Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations

Revisions: 1

__
TR21-050
| 2nd April 2021
__

Marshall Ball, Alper Cakan, Tal Malkin#### Linear Threshold Secret-Sharing with Binary Reconstruction

__
TR21-051
| 8th April 2021
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$)

__
TR21-052
| 12th April 2021
__

Benny Applebaum, Oded Nir#### Upslices, Downslices, and Secret-Sharing with Complexity of $1.5^n$

__
TR21-053
| 13th April 2021
__

Jan Krajicek#### Information in propositional proofs and algorithmic proof search

__
TR21-054
| 14th April 2021
__

James Cook, Ian Mertz#### Encodings and the Tree Evaluation Problem

__
TR21-055
| 20th April 2021
__

Yanyi Liu, Rafael Pass#### Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity

__
TR21-056
| 22nd April 2021
__

Yanyi Liu, Rafael Pass#### On the Possibility of Basing Cryptography on $\EXP \neq \BPP$

__
TR21-057
| 23rd April 2021
__

Hanlin Ren, Rahul Santhanam#### Hardness of KT Characterizes Parallel Cryptography

Revisions: 1

__
TR21-058
| 21st April 2021
__

Shuichi Hirahara#### Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions

__
TR21-059
| 20th April 2021
__

Yanyi Liu, Rafael Pass#### On One-way Functions from NP-Complete Problems

Revisions: 2

__
TR21-060
| 8th April 2021
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Optimal Error Resilience of Adaptive Message Exchange

__
TR21-061
| 29th April 2021
__

Noah Fleming, Toniann Pitassi#### Reflections on Proof Complexity and Counting Principles

__
TR21-062
| 29th April 2021
__

Vishwas Bhargava, Sumanta Ghosh#### Improved Hitting Set for Orbit of ROABPs

Revisions: 2

__
TR21-063
| 3rd May 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy#### Approximability of all finite CSPs in the dynamic streaming setting

Revisions: 3

__
TR21-064
| 5th May 2021
__

Noah Singer, Madhu Sudan, Santhoshini Velusamy#### Streaming approximation resistance of every ordering CSP

Revisions: 2

__
TR21-065
| 5th May 2021
__

Nikhil Mande, Swagato Sanyal#### One-way communication complexity and non-adaptive decision trees

Revisions: 1

__
TR21-066
| 5th May 2021
__

Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami#### Dimension-free Bounds and Structural Results in Communication Complexity

__
TR21-067
| 6th May 2021
__

Zeyu Guo#### Variety Evasive Subspace Families

Revisions: 1

__
TR21-068
| 8th May 2021
__

Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler#### Quantum Proofs of Proximity

__
TR21-069
| 12th May 2021
__

Dominik Scheder#### PPSZ is better than you think

Revisions: 1

__
TR21-070
| 13th May 2021
__

Shuo Pang#### SOS lower bound for exact planted clique

__
TR21-071
| 16th May 2021
__

Samuel Epstein#### On the Algorithmic Content of Quantum Measurements

__
TR21-072
| 23rd May 2021
__

Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu#### Arithmetic Circuit Complexity of Division and Truncation

__
TR21-073
| 3rd June 2021
__

Emanuele Viola#### Lower bounds for samplers and data structures via the cell-probe separator

Revisions: 2

__
TR21-074
| 3rd June 2021
__

Theodoros Papamakarios, Alexander Razborov#### Space characterizations of complexity measures and size-space trade-offs in propositional proof systems

__
TR21-075
| 4th June 2021
__

Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao#### Affine Extractors for Almost Logarithmic Entropy

__
TR21-076
| 4th June 2021
__

Dmitry Sokolov#### Pseudorandom Generators, Resolution and Heavy Width

__
TR21-077
| 6th June 2021
__

Shir Peleg, Amir Shpilka, Ben Lee Volk#### Lower Bounds on Stabilizer Rank

__
TR21-078
| 8th June 2021
__

Rahul Jain, Srijita Kundu#### A direct product theorem for quantum communication complexity with applications to device-independent QKD

__
TR21-079
| 9th June 2021
__

Venkatesan Guruswami, Xiaoyu He, Ray Li#### The zero-rate threshold for adversarial bit-deletions is less than 1/2

__
TR21-080
| 10th June 2021
__

Lijie Chen, Roei Tell#### Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise

__
TR21-081
| 14th June 2021
__

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

Revisions: 1

__
TR21-082
| 16th June 2021
__

Rahul Ilango, Hanlin Ren, Rahul Santhanam#### Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity

__
TR21-083
| 21st June 2021
__

Mark Braverman, Sumegha Garg, Or Zamir#### Tight Space Complexity of the Coin Problem

__
TR21-084
| 21st June 2021
__

Liron Bronfman, Ron Rothblum#### PCPs and Instance Compression from a Cryptographic Lens

__
TR21-085
| 21st June 2021
__

Ilya Volkovich#### The Final Nail in the Coffin of Statistically-Secure Obfuscator.

__
TR21-086
| 22nd June 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy#### Linear Space Streaming Lower Bounds for Approximating CSPs

__
TR21-087
| 22nd June 2021
__

Uma Girish, Ran Raz#### Eliminating Intermediate Measurements using Pseudorandom Generators

Revisions: 1

__
TR21-088
| 23rd June 2021
__

Oded Goldreich#### Open Problems in Property Testing of Graphs

Revisions: 1

__
TR21-089
| 25th June 2021
__

Hanlin Ren, Rahul Santhanam#### A Relativization Perspective on Meta-Complexity

__
TR21-090
| 14th June 2021
__

Divesh Aggarwal, Eldon Chung, Maciej Obremski, Joao Ribeiro#### On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing

__
TR21-091
| 29th June 2021
__

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma#### Expander Random Walks: The General Case and Limitations

__
TR21-092
| 28th June 2021
__

Yanyi Liu, Rafael Pass#### A Note on One-way Functions and Sparse Languages

__
TR21-093
| 1st July 2021
__

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan#### Bounded Indistinguishability for Simple Sources

Revisions: 1

__
TR21-094
| 6th July 2021
__

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### New Non-FPT Lower Bounds for Some Arithmetic Formulas

__
TR21-095
| 8th July 2021
__

Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Oliveira#### LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic

__
TR21-096
| 8th July 2021
__

Boaz Menuhin, Moni Naor#### Keep That Card in Mind: Card Guessing with Limited Memory

__
TR21-097
| 7th July 2021
__

Jacobo Toran, Florian Wörz#### Number of Variables for Graph Identification and the Resolution of GI Formulas

__
TR21-098
| 7th July 2021
__

Srikanth Srinivasan, S Venkitesh#### On the Probabilistic Degree of an $n$-variate Boolean Function

__
TR21-099
| 4th July 2021
__

Louis Golowich#### Improved Product-Based High-Dimensional Expanders

__
TR21-100
| 11th July 2021
__

Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh#### Karchmer-Wigderson Games for Hazard-free Computation

__
TR21-101
| 13th July 2021
__

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan#### A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof

Revisions: 1

__
TR21-102
| 13th July 2021
__

Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff#### Tight bounds on the Fourier growth of bounded functions on the hypercube

Revisions: 1

__
TR21-103
| 18th July 2021
__

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit#### Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields

Revisions: 1

__
TR21-104
| 26th June 2021
__

Sravanthi Chede, Anil Shukla#### Does QRAT simulate IR-calc? QRAT simulation algorithm for $\forall$Exp+Res cannot be lifted to IR-calc

__
TR21-105
| 22nd July 2021
__

Suryajith Chillara#### Functional lower bounds for restricted arithmetic circuits of depth four

__
TR21-106
| 22nd July 2021
__

Eshan Chattopadhyay, Jesse Goodman, David Zuckerman#### The Space Complexity of Sampling

Revisions: 1

__
TR21-107
| 20th July 2021
__

igor razgon#### Classification of OBDD size for monotone 2-CNFs

__
TR21-108
| 22nd July 2021
__

Edward Pyne, Salil Vadhan#### Limitations of the Impagliazzo--Nisan--Wigderson Pseudorandom Generator against Permutation Branching Programs

__
TR21-109
| 20th July 2021
__

Sravanthi Chede, Anil Shukla#### QRAT Polynomially Simulates Merge Resolution.

__
TR21-110
| 22nd July 2021
__

Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco Servedio, Emanuele Viola#### Fourier growth of structured $\mathbb{F}_2$-polynomials and applications

__
TR21-111
| 19th July 2021
__

Aniruddha Biswas, Palash Sarkar#### Influence of a Set of Variables on a Boolean Function

__
TR21-112
| 30th July 2021
__

Vikraman Arvind, Venkatesan Guruswami#### CNF Satisfiability in a Subspace and Related Problems

__
TR21-113
| 25th July 2021
__

Nikhil Mande, Ronald de Wolf#### Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error

__
TR21-114
| 29th July 2021
__

Henning Fernau, Kshitij Gajjar#### The Space Complexity of Sum Labelling

Revisions: 1

__
TR21-115
| 6th August 2021
__

Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming#### On quantum versus classical query complexity

Revisions: 2

__
TR21-116
| 10th August 2021
__

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang#### Quantum Meets the Minimum Circuit Size Problem

Revisions: 1

__
TR21-117
| 11th August 2021
__

Divesh Aggarwal, Bhavana Kanukurthi, SaiLakshmiBhavana Obbattu, Maciej Obremski, Sruthi Sekar#### Simplicity Meets Near-Optimal Rate: Non-malleable Codes and Non-malleable Two-source Extractors via Rate Boosters

Revisions: 2

__
TR21-118
| 11th August 2021
__

Daniel Augot, Sarah Bordage, Jade Nardi#### Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

__
TR21-119
| 13th August 2021
__

Omar Alrabiah, Venkatesan Guruswami#### Visible Rank and Codes with Locality

Revisions: 1

__
TR21-120
| 18th August 2021
__

Roei Tell#### How to Find Water in the Ocean: A Survey on Quantified Derandomization

__
TR21-121
| 21st August 2021
__

Sumanta Ghosh, Rohit Gurjar#### Matroid Intersection: A pseudo-deterministic parallel reduction from search to weighted-decision

__
TR21-122
| 24th August 2021
__

Sabyasachi Basu, Akash Kumar, C. Seshadhri#### The complexity of testing all properties of planar graphs, and the role of isomorphism

__
TR21-123
| 25th August 2021
__

Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani#### On public-coin zero-error randomized communication complexity

Revisions: 1

__
TR21-124
| 17th August 2021
__

Iftach Haitner, Noam Mazor, Jad Silbak, Eliad Tsfadia#### On the Complexity of Two-Party Differential Privacy

Revisions: 1

__
TR21-125
| 23rd August 2021
__

Zhiyuan Fan, Jiatu Li, Tianqi Yang#### The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs

__
TR21-126
| 25th August 2021
__

Yilei Chen, Qipeng Liu, Mark Zhandry#### Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering

Revisions: 1

__
TR21-127
| 30th August 2021
__

Ron D. Rothblum, Michael Ezra#### Small Circuits Imply Efficient Arthur-Merlin Protocols

Revisions: 1

__
TR21-128
| 4th September 2021
__

Xiaotie Deng, Yuhao Li, David Mguni, Jun Wang, Yaodong Yang#### On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games

__
TR21-129
| 6th September 2021
__

Oded Goldreich, Dana Ron#### A Lower Bound on the Complexity of Testing Grained Distributions

__
TR21-130
| 7th September 2021
__

Srinivasan Arunachalam, João F. Doriguello#### Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case

__
TR21-131
| 10th September 2021
__

Olaf Beyersdorff, Benjamin Böhm#### QCDCL with Cube Learning or Pure Literal Elimination - What is best?

__
TR21-132
| 11th September 2021
__

Eric Binnendyk#### Pseudo-random functions and uniform learnability

Revisions: 1

__
TR21-133
| 12th September 2021
__

Oded Goldreich, Dana Ron#### Testing Distributions of Huge Objects

Revisions: 1

__
TR21-134
| 19th August 2021
__

Siddharth Bhaskar#### A refinement of the Meyer-McCreight Union Theorem

__
TR21-135
| 6th September 2021
__

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

__
TR21-136
| 13th September 2021
__

Gil Cohen, Tal Yankovitz#### LCC and LDC: Tailor-made distance amplification and a refined separation

__
TR21-137
| 14th September 2021
__

Xuangui Huang, Peter Ivanov, Emanuele Viola#### Affine extractors and AC0-Parity

Revisions: 1

__
TR21-138
| 23rd September 2021
__

Rahul Santhanam, Iddo Tzameret#### Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity

__
TR21-139
| 24th September 2021
__

Venkatesan Guruswami, Jonathan Mosheiff#### Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity

Revisions: 1

__
TR21-140
| 27th September 2021
__

Nathan Geier#### Tight Computational Indistinguishability Bound of Product Distributions

__
TR21-141
| 28th September 2021
__

Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz#### On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization

__
TR21-142
| 1st October 2021
__

Amey Bhangale, Prahladh Harsha, Sourya Roy#### Mixing of 3-term progressions in Quasirandom Groups

__
TR21-143
| 13th October 2021
__

Edward Pyne#### Hitting Sets For Regular Branching Programs

Revisions: 1

__
TR21-144
| 13th October 2021
__

Leroy Chew, Friedrich Slivovsky#### Towards Uniform Certification in QBF

__
TR21-145
| 19th October 2021
__

Omar Alrabiah, Venkatesan Guruswami#### Revisiting a Lower Bound on the Redundancy of Linear Batch Codes

__
TR21-146
| 19th October 2021
__

Guy Goldberg, Guy Rothblum#### Sample-Based Proofs of Proximity

__
TR21-147
| 22nd October 2021
__

Eshan Chattopadhyay, Jyun-Jie Liao#### Extractors for Sum of Two Sources

Revisions: 1

__
TR21-148
| 3rd November 2021
__

Benjamin Diamond, Amir Yehudayoff#### Explicit Exponential Lower Bounds for Exact Hyperplane Covers

__
TR21-149
| 5th November 2021
__

Sevag Gharibian, Dorian Rudolph#### On polynomially many queries to NP or QMA oracles

__
TR21-150
| 7th November 2021
__

Eldon Chung, Maciej Obremski, Divesh Aggarwal#### Extractors: Low Entropy Requirements Colliding With Non-Malleability

__
TR21-151
| 8th November 2021
__

Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes#### Locally Testable Codes with constant rate, distance, and locality

Revisions: 1

__
TR21-152
| 8th November 2021
__

Gal Arnon, Tomer Grossman#### Min-Entropic Optimality

__
TR21-153
| 9th November 2021
__

Ronen Shaltiel, Emanuele Viola#### On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization

__
TR21-154
| 10th November 2021
__

Inbar Ben Yaacov, Gil Cohen, Tal Yankovitz#### Explicit Binary Tree Codes with Sub-Logarithmic Size Alphabet

__
TR21-155
| 13th November 2021
__

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha#### Learning generalized depth-three arithmetic circuits in the non-degenerate case

__
TR21-156
| 10th November 2021
__

Boris Bukh, Karthik C. S., Bhargav Narayanan#### Applications of Random Algebraic Constructions to Hardness of Approximation

__
TR21-157
| 2nd November 2021
__

Monika Henzinger, Andrea Lincoln, Barna Saha#### The Complexity of Average-Case Dynamic Subgraph Counting

__
TR21-158
| 12th November 2021
__

Noah Fleming, Toniann Pitassi, Robert Robere#### Extremely Deep Proofs

Revisions: 1

__
TR21-159
| 15th November 2021
__

Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams#### Constructive Separations and Their Consequences

__
TR21-160
| 15th November 2021
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Tight Bounds for General Computation in Noisy Broadcast Networks

__
TR21-161
| 16th November 2021
__

Shuichi Hirahara, Mikito Nanashima#### On Worst-Case Learning in Relativized Heuristica

__
TR21-162
| 14th November 2021
__

Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, Chandra Kanta Mohapatra#### Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications

__
TR21-163
| 19th November 2021
__

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, A. Shankar#### Algorithmizing the Multiplicity Schwartz-Zippel Lemma

__
TR21-164
| 19th November 2021
__

Scott Aaronson, DeVon Ingram, William Kretschmer#### The Acrobatics of BQP

__
TR21-165
| 21st November 2021
__

Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams#### Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity

Revisions: 1

__
TR21-166
| 21st November 2021
__

Lijie Chen, Shuichi Hirahara, Neekon Vafa#### Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions

__
TR21-167
| 23rd November 2021
__

Alex Lombardi, Fermi Ma, Nicholas Spooner#### Post-Quantum Zero Knowledge, Revisited (or: How to Do Quantum Rewinding Undetectably)

__
TR21-168
| 17th November 2021
__

Tom Gur, Noam Lifshitz, Siqi Liu#### Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $\epsilon$-Product Spaces

Revisions: 2

__
TR21-169
| 24th November 2021
__

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett#### Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments

__
TR21-170
| 25th November 2021
__

Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda#### Pseudorandom Self-Reductions for NP-Complete Problems

__
TR21-171
| 2nd December 2021
__

Bruno Pasqualotto Cavalar, Zhenjian Lu#### Algorithms and Lower Bounds for Comparator Circuits from Shrinkage

__
TR21-172
| 1st December 2021
__

Robert Andrews, Michael Forbes#### Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals

__
TR21-173
| 5th December 2021
__

Ninad Rajgopal, Rahul Santhanam#### On the Structure of Learnability beyond P/poly

__
TR21-174
| 29th November 2021
__

Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian#### Sublinear quantum algorithms for estimating von Neumann entropy

__
TR21-175
| 6th December 2021
__

Oded Goldreich#### On the Locally Testable Code of Dinur et al. (2021)

Revisions: 1

__
TR21-176
| 30th November 2021
__

Theodoros Papamakarios#### A super-polynomial separation between resolution and cut-free sequent calculus

__
TR21-177
| 22nd November 2021
__

Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee#### Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics

__
TR21-178
| 3rd December 2021
__

Srinivasan Arunachalam, Oded Regev, Penghui Yao#### On the Gaussian surface area of spectrahedra

__
TR21-179
| 8th December 2021
__

tatsuie tsukiji#### Smoothed Complexity of Learning Disjunctive Normal Forms, Inverting Fourier Transforms, and Verifying Small Circuits

Comments: 1

__
TR21-180
| 21st December 2021
__

Noga Ron-Zewi, Ron Rothblum#### Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead

__
TR21-181
| 30th December 2021
__

Oded Goldreich#### The KW Games as a Teaser

__
TR21-182
| 30th December 2021
__

Ilario Bonacina, Maria Luisa Bonet#### On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

We study the $n$-party noisy broadcast channel with a constant fraction of malicious parties. Specifically, we assume that each non-malicious party holds an input bit, and communicates with the others in order to learn the input bits of all non-malicious parties. In each communication round, one of the parties broadcasts ... more >>>

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

We present new constructions of pseudorandom generators (PRGs) for two of the most widely-studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth $d\in\mathbb{N}$ ... more >>>

Lijie Chen, Xin Lyu

In this work we prove that there is a function $f \in \textrm{E}^\textrm{NP}$ such that, for every sufficiently large $n$ and $d = \sqrt{n}/\log n$, $f_n$ ($f$ restricted to $n$-bit inputs) cannot be $(1/2 + 2^{-d})$-approximated by $\textrm{F}_2$-polynomials of degree $d$. We also observe that a minor improvement ...
more >>>

Vishnu Iyer, Avishay Tal, Michael Whitmeyer

Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different results pertaining to the tolerant testing of juntas. Given black-box access to a Boolean function $f:\{\pm1\}^{n} \to \{\pm1\}$ we give a poly$(k, \frac{1}{\varepsilon})$ query algorithm that distinguishes between functions that are $\gamma$-close to $k$-juntas and $(\gamma+\varepsilon)$-far from ... more >>>

Anindya De, Elchanan Mossel, Joe Neeman

A natural problem in high-dimensional inference is to decide if a classifier $f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear directions of its input data. Call a function $g: \mathbb{R}^n \rightarrow \{-1,1\}$, a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. ... more >>>

Susanna de Rezende, Jakob Nordström, Marc Vinyals

We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large ... more >>>

Sai Sandeep

Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. ... more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, for a sufficiently small ? > 0, one removes

?dn ...
more >>>

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence ... more >>>

Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle

A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexity of MCSP hold also for MKTP (the problem of computing the KT ... more >>>

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal ... more >>>

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas -- certain unsatisfiable systems of linear equations mod 2 -- which are canonical ... more >>>

Srinivasan Arunachalam, Penghui Yao

In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary $m$-facet polytopes in $n$ variables with seed length poly-logarithmic in $m,n$, concluding a sequence of works in the last decade, that was started by Diakonikolas, Gopalan, Jaiswal, Servedio, Viola (SICOMP 2010) and Meka, ... more >>>

Dori Medini, Amir Shpilka

In this paper we study polynomials in VP$_e$ (polynomial-sized formulas) and in $\Sigma\Pi\Sigma$ (polynomial-size depth-$3$ circuits) whose orbits, under the action of the affine group GL$^{aff}_n({\mathbb F})$, are dense in their ambient class. We construct hitting sets and interpolating sets for these orbits as well as give reconstruction algorithms.

As ... more >>>

Chandan Saha, Bhargav Thankey

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\mathrm{orb}(f) := \{f(A\mathbf{x}+\mathbf{b}) : A \in \mathrm{GL}(n,\mathbb{F}) \ \mathrm{and} \ \mathbf{b} \in \mathbb{F}^n\}$. This paper studies explicit hitting sets for the orbits of polynomials computable by certain well-studied circuit classes. This version of the hitting set ... more >>>

Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari

We exhibit an unambiguous $k$-DNF formula that requires CNF width $\tilde{\Omega}(k^{1.5})$. Our construction is inspired by the board game Hex and it is vastly simpler than previous ones, which achieved at best an exponent of $1.22$. Our result is known to imply several other improved separations in query and communication ... more >>>

Timothy Gowers, Emanuele Viola

We initiate a systematic study of mixing in non-quasirandom groups.

Let $A$ and $B$ be two independent, high-entropy distributions over

a group $G$. We show that the product distribution $AB$ is statistically

close to the distribution $F(AB)$ for several choices of $G$ and

$F$, including:

(1) $G$ is the affine ... more >>>

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan

We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state.

We prove that constant-width monotone branching programs of ... more >>>

Edward Pyne, Salil Vadhan

A recent paper of Braverman, Cohen, and Garg (STOC 2018) introduced the concept of a pseudorandom pseudodistribution generator (PRPG), which amounts to a pseudorandom generator (PRG) whose outputs are accompanied with real coefficients that scale the acceptance probabilities of any potential distinguisher. They gave an explicit construction of PRPGs for ... more >>>

Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma

Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [BCG20], is a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered rather than a probability mass. Braverman et al. constructed WPRGs against read once branching programs (ROBPs) with near-optimal dependence on the error parameter. Chattopadhyay and ... more >>>

Per Austrin, Kilian Risse

We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree $\Omega(n/\log n)$ in the Polynomial ... more >>>

Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin

We prove logarithmic depth lower bounds in Stabbing Planes for the classes of combinatorial principles known as the Pigeonhole principle and the Tseitin contradictions. The depth lower bounds are new, obtained by giving almost linear length lower bounds which do not depend on the bit-size of the inequalities and in ... more >>>

Jiatu Li, Tianqi Yang

Proving circuit lower bounds has been an important but extremely hard problem for decades. Although one may show that almost every function $f:\mathbb{F}_2^n\to\mathbb{F}_2$ requires circuit of size $\Omega(2^n/n)$ by a simple counting argument, it remains unknown whether there is an explicit function (for example, a function in $NP$) not computable ... more >>>

Mika Göös, Gilbert Maystre

We show that computing the majority of $n$ copies of a boolean function $g$ has randomised query complexity $\mathrm{R}(\mathrm{Maj} \circ g^n) = \Theta(n\cdot \bar{\mathrm{R}}_{1/n}(g))$. In fact, we show that to obtain a similar result for any composed function $f\circ g^n$, it suffices to prove a sufficiently strong form of the ... more >>>

Sivakanth Gopi, Venkatesan Guruswami

An $(n,r,h,a,q)$-Local Reconstruction Code is a linear code over $\mathbb{F}_q$ of length $n$, whose codeword symbols are partitioned into $n/r$ local groups each of size $r$. Each local group satisfies `$a$' local parity checks to recover from `$a$' erasures in that local group and there are further $h$ global parity ... more >>>

Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep

Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be satisfied vs. even the weak form cannot be satisfied. Since their ... more >>>

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu

We give an almost quadratic $n^{2-o(1)}$ lower bound on the space consumption of any $o(\sqrt{\log n})$-pass streaming algorithm solving the (directed) $s$-$t$ reachability problem. This means that any such algorithm must essentially store the entire graph. As corollaries, we obtain almost quadratic space lower bounds for additional fundamental problems, including ... more >>>

Anastasia Sofronova, Dmitry Sokolov

Restricted branching programs capture various complexity measures like space in Turing machines or length of proofs in proof systems. In this paper, we focus on the application in the proof complexity that was discovered by Lovasz et al. '95 who showed the equivalence between regular Resolution and read-once branching programs ... more >>>

Inbar Kaslasi, Ron Rothblum, Prashant Nalini Vasudevan

Suppose that a problem $\Pi$ has a statistical zero-knowledge (SZK) proof with communication complexity $m$. The question of batch verification for SZK asks whether one can prove that $k$ instances $x_1,\ldots,x_k$ all belong to $\Pi$ with a statistical zero-knowledge proof whose communication complexity is better than $k \cdot m$ (which ... more >>>

Shuichi Hirahara, Rahul Ilango, Bruno Loff

How difficult is it to compute the communication complexity of a two-argument total Boolean function $f:[N]\times[N]\to\{0,1\}$, when it is given as an $N\times N$ binary matrix? In 2009, Kushilevitz and Weinreb showed that this problem is cryptographically hard, but it is still open whether it is NP-hard.

In this ... more >>>

Vaibhav Krishan

We prove that all functions that have low degree torus polynomials approximating them with small error also have $MidBit^+$ circuits computing them. This serves as a partial converse to the result that all $ACC$ functions have low degree torus polynomials approximating them with small error, by Bhrushundi, Hosseini, Lovett and ... more >>>

Justin Holmgren, Alex Lombardi, Ron Rothblum

Shortly after the introduction of zero-knowledge proofs, Goldreich, Micali and Wigderson (CRYPTO '86) demonstrated their wide applicability by constructing zero-knowledge proofs for the NP-complete problem of graph 3-coloring. A long-standing open question has been whether parallel repetition of their protocol preserves zero knowledge. In this work, we answer this question ... more >>>

Susanna de Rezende

We show that tree-like resolution is not automatable in time $n^{o(\log n)}$ unless ETH is false. This implies that, under ETH, the algorithm given by Beame and Pitassi (FOCS 1996) that automates tree-like resolution in time $n^{O(\log n)}$ is optimal. We also provide a simpler proof of the result of ... more >>>

Oded Goldreich

We study two notions that refers to asymmetric graphs, which we view as graphs having a unique ordering that can be reconstructed by looking at an unlabeled version of the graph.

A {\em local self-ordering} procedure for a graph $G$ is given oracle access to an arbitrary isomorphic copy of ... more >>>

Robert Robere, Jeroen Zuiddam

We study the amortized circuit complexity of boolean functions.

Given a circuit model $\mathcal{F}$ and a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, the $\mathcal{F}$-amortized circuit complexity is defined to be the size of the smallest circuit that outputs $m$ copies of $f$ (evaluated on the same input), ...
more >>>

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

In this work, we present an abstract framework for some algebraic error-correcting codes with the aim of capturing codes that are list-decodable to capacity, along with their decoding algorithm. In the polynomial ideal framework, a code is specified by some ideals in a polynomial ring, messages are polynomials and their ... more >>>

Prerona Chatterjee

The motivating question for this work is a long standing open problem, posed by Nisan (1991), regarding the relative powers of algebraic branching programs (ABPs) and formulas in the non-commutative setting. Even though the general question continues to remain open, we make some progress towards its resolution. To that effect, ... more >>>

Alessandro Chiesa, Fermi Ma, Nicholas Spooner, Mark Zhandry

We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors).

At the heart of our proof is a new ... more >>>

Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam

We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of $BPTIME$: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows.

1. A new pseudorandom generator and its consequences: We build on techniques developed to ... more >>>

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira

We develop a general framework that characterizes strong average-case lower bounds against circuit classes $\mathcal{C}$ contained in $\mathrm{NC}^1$, such as $\mathrm{AC}^0[\oplus]$ and $\mathrm{ACC}^0$. We apply this framework to show:

- Generic seed reduction: Pseudorandom generators (PRGs) against $\mathcal{C}$ of seed length $\leq n -1$ and error $\varepsilon(n) = n^{-\omega(1)}$ can ... more >>>

Zhenjian Lu, Igor Carboni Oliveira

A probabilistic representation of a string $x \in \{0,1\}^n$ is given by the code of a randomized algorithm that outputs $x$ with high probability [Oliveira, ICALP 2019]. We employ probabilistic representations to establish the first unconditional Coding Theorem in time-bounded Kolmogorov complexity. More precisely, we show that if a distribution ... more >>>

Dana Moshkovitz

We show that NP-hardness of approximating Boolean unique games on small set expanders can be amplified to the full Unique Games Conjecture on small set expanders.

The latter conjecture is known to imply hardness results for problems like Balanced-Separator, Minimum-Linear-Rearrangement and Small-Set-Expansion that are not known under the Unique ...
more >>>

Peter Dixon, A. Pavan, N. V. Vinodchandran

The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high ... more >>>

Alexander Kulikov, Nikita Slezkin

Finding exact circuit size is a notorious optimization problem in practice. Whereas modern computers and algorithmic techniques allow to find a circuit of size seven in blink of an eye, it may take more than a week to search for a circuit of size thirteen. One of the reasons of ... more >>>

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a {\it constant-rank} tensor. ... more >>>

Uma Girish, Avishay Tal, Kewen Wu

We prove that for every parity decision tree of depth $d$ on $n$ variables, the sum of absolute values of Fourier coefficients at level $\ell$ is at most $d^{\ell/2} \cdot O(\ell \cdot \log(n))^\ell$.

Our result is nearly tight for small values of $\ell$ and extends a previous Fourier bound ...
more >>>

Zander Kelley, Raghu Meka

A polynomial threshold function (PTF) $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is a function of the form $f(x) = sign(p(x))$ where $p$ is a polynomial of degree at most $d$. PTFs are a classical and well-studied complexity class with applications across complexity theory, learning theory, approximation theory, quantum complexity and more. We address ... more >>>

William Hoza

Three decades ago, Nisan constructed an explicit pseudorandom generator (PRG) that fools width-$n$ length-$n$ read-once branching programs (ROBPs) with error $\varepsilon$ and seed length $O(\log^2 n + \log n \cdot \log(1/\varepsilon))$ (Combinatorica 1992). Nisan's generator remains the best explicit PRG known for this important model of computation. However, a recent ... more >>>

Juraj Hromkovic

We call any consistent and sufficiently powerful formal theory that enables to algorithmically in polynomial time verify whether a text is a proof \textbf{efficiently verifiable mathematics} (ev-mathematics). We study the question whether nondeterminism is more powerful than determinism for polynomial time computations in the framework of ev-mathematics. Our main results ... more >>>

Marshall Ball, Alper Cakan, Tal Malkin

Motivated in part by applications in lattice-based cryptography, we initiate the study of the size of linear threshold (`$t$-out-of-$n$') secret-sharing where the linear reconstruction function is restricted to coefficients in $\{0,1\}$. We prove upper and lower bounds on the share size of such schemes. One ramification of our results is ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Interactive error correcting codes are codes that encode a two party communication protocol to an error-resilient protocol that succeeds even if a constant fraction of the communicated symbols are adversarially corrupted, at the cost of increasing the communication by a constant factor. What is the largest fraction of corruptions that ... more >>>

Benny Applebaum, Oded Nir

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/unauthorized sets can be captured by a monotone function $f:\{0,1\}^n\rightarrow \{0,1\}$.

more >>>

Jan Krajicek

We study from the proof complexity perspective the (informal) proof search problem:

Is there an optimal way to search for propositional proofs?

We note that for any fixed proof system there exists a time-optimal proof search algorithm. Using classical proof complexity results about reflection principles we prove that a time-optimal ...
more >>>

James Cook, Ian Mertz

We show that the Tree Evaluation Problem with alphabet size $k$ and height $h$ can be solved by branching programs of size $k^{O(h/\log h)} + 2^{O(h)}$. This answers a longstanding challenge of Cook et al. (2009) and gives the first general upper bound since the problem's inception.

more >>>Yanyi Liu, Rafael Pass

Let $\mktp[s]$ be the set of strings $x$ such that $K^t(x) \leq s(|x|)$, where $K^t(x)$ denotes the $t$-bounded Kolmogorov complexity of the truthtable described by $x$. Our main theorem shows that for an appropriate notion of mild average-case hardness, for every $\varepsilon>0$, polynomial $t(n) \geq (1+\varepsilon)n$, and every ``nice'' class ... more >>>

Yanyi Liu, Rafael Pass

Liu and Pass (FOCS'20) recently demonstrated an equivalence between the existence of one-way functions (OWFs) and mild average-case hardness of the time-bounded Kolmogorov complexity problem. In this work, we establish a similar equivalence but to a different form of time-bounded Kolmogorov Complexity---namely, Levin's notion of Kolmogorov Complexity---whose hardness is closely ... more >>>

Hanlin Ren, Rahul Santhanam

A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity K^t is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures:

1. We show, perhaps surprisingly, that the ... more >>>

Shuichi Hirahara

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)exponential worst-case complexity. The difficulty of resolving this ... more >>>

Yanyi Liu, Rafael Pass

We present the first natural $\NP$-complete problem whose average-case hardness w.r.t. the uniform distribution over instances implies the existence of one-way functions (OWF). In fact, we prove that the existence of OWFs is \emph{equivalent} to mild average-case hardness of this $\NP$-complete problem. The problem, which originated in the 1960s, is ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

We study the error resilience of the message exchange task: Two parties, each holding a private input, want to exchange their inputs. However, the channel connecting them is governed by an adversary that may corrupt a constant fraction of the transmissions. What is the maximum fraction of corruptions that still ... more >>>

Noah Fleming, Toniann Pitassi

This paper surveys the development of propositional proof complexity and the seminal contributions of Alasdair Urquhart. We focus on the central role of counting principles, and in particular Tseitin's graph tautologies, to most of the key advances in lower bounds in proof complexity. We reflect on a couple of key ... more >>>

Vishwas Bhargava, Sumanta Ghosh

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\{f(A \mathbf{x} + b)\,\mid\, A\in \mathrm{GL}({n,\mathbb{F}})\mbox{ and }\mathbf{b} \in \mathbb{F}^n\}$, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of ... more >>>

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

A constraint satisfaction problem (CSP), Max-CSP$({\cal F})$, is specified by a finite set of constraints ${\cal F} \subseteq \{[q]^k \to \{0,1\}\}$ for positive integers $q$ and $k$. An instance of the problem on $n$ variables is given by $m$ applications of constraints from ${\cal F}$ to subsequences of the $n$ ... more >>>

Noah Singer, Madhu Sudan, Santhoshini Velusamy

An ordering constraint satisfaction problem (OCSP) is given by a positive integer $k$ and a constraint predicate $\Pi$ mapping permutations on $\{1,\ldots,k\}$ to $\{0,1\}$. Given an instance of OCSP$(\Pi)$ on $n$ variables and $m$ constraints, the goal is to find an ordering of the $n$ variables that maximizes the number ... more >>>

Nikhil Mande, Swagato Sanyal

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. Let $IP$ denote Inner Product on ... more >>>

Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami

The purpose of this article is to initiate a systematic study of dimension-free relations between basic communication and query complexity measures and various matrix norms. In other words, our goal is to obtain inequalities that bound a parameter solely as a function of another parameter. This is in contrast to ... more >>>

Zeyu Guo

We introduce the problem of constructing explicit variety evasive subspace families. Given a family $\mathcal{F}$ of subvarieties of a projective or affine space, a collection $\mathcal{H}$ of projective or affine $k$-subspaces is $(\mathcal{F},\epsilon)$-evasive if for every $\mathcal{V}\in\mathcal{F}$, all but at most $\epsilon$-fraction of $W\in\mathcal{H}$ intersect every irreducible component of $\mathcal{V}$ ... more >>>

Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler

We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property $\Pi$ and reject ... more >>>

Dominik Scheder

PPSZ, for long time the fastest known algorithm for k-SAT, works by going through the variables of the input formula in random order; each variable is then set randomly to 0 or 1, unless the correct value can be inferred by an efficiently implementable rule (like small-width resolution; or being ... more >>>

Shuo Pang

We prove a SOS degree lower bound for the planted clique problem on Erd{\"o}s-R\'enyi random graphs $G(n,1/2)$. The bound we get is degree $d=\Omega(\epsilon^2\log n/\log\log n)$ for clique size $\omega=n^{1/2-\epsilon}$, which is almost tight. This improves the result of \cite{barak2019nearly} on the ``soft'' version of the problem, where the family ... more >>>

Samuel Epstein

We show that given a quantum measurement, for an overwhelming majority of pure states, no meaningful information is produced. This is independent of the number of outcomes of the quantum measurement. Due to conservation inequalities, such random noise cannot be processed into coherent data.

more >>>Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu

Given polynomials $f,g,h\,\in \mathbb{F}[x_1,\ldots,x_n]$ such that $f=g/h$, where both $g$ and $h$ are computable by arithmetic circuits of size $s$, we show that $f$ can be computed by a circuit of size $\poly(s,\deg(h))$. This solves a special case of division elimination for high-degree circuits (Kaltofen'87 \& WACT'16). The result ... more >>>

Emanuele Viola

Suppose that a distribution $S$ can be approximately sampled by an

efficient cell-probe algorithm. It is shown to be possible to restrict

the input to the algorithm so that its output distribution is still

not too far from $S$, and at the same time many output coordinates

are almost pairwise ...
more >>>

Theodoros Papamakarios, Alexander Razborov

We identify two new big clusters of proof complexity measures equivalent up to

polynomial and $\log n$ factors. The first cluster contains, among others,

the logarithm of tree-like resolution size, regularized (that is, multiplied

by the logarithm of proof length) clause and monomial space, and clause

space, both ordinary and ...
more >>>

Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao

We give an explicit construction of an affine extractor (over $\mathbb{F}_2$) that works for affine sources on $n$ bits with min-entropy $k \ge~ \log n \cdot (\log \log n)^{1 + o(1)}$. This improves prior work of Li (FOCS'16) that requires min-entropy at least $\mathrm{poly}(\log n)$.

Our construction is ...
more >>>

Dmitry Sokolov

Following the paper of Alekhnovich, Ben-Sasson, Razborov, Wigderson \cite{ABRW04} we call a pseudorandom generator $\mathrm{PRG}\colon \{0, 1\}^n \to \{0, 1\}^m$ hard for for a propositional proof system $\mathrm{P}$ if $\mathrm{P}$ cannot efficiently prove the (properly encoded) statement $b \notin \mathrm{Im}(\mathrm{PRG})$ for any string $b \in \{0, 1\}^m$.

In \cite{ABRW04} authors ... more >>>

Shir Peleg, Amir Shpilka, Ben Lee Volk

The stabilizer rank of a quantum state $\psi$ is the minimal $r$ such that $\left| \psi \right \rangle = \sum_{j=1}^r c_j \left|\varphi_j \right\rangle$ for $c_j \in \mathbb{C}$ and stabilizer states $\varphi_j$. The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the ... more >>>

Rahul Jain, Srijita Kundu

We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an $l$-player predicate $V$. In particular we show that for a distribution $p$ that is product across the input sets of the $l$ players, the success probability of any entanglement-assisted quantum communication protocol for computing $n$ ... more >>>

Venkatesan Guruswami, Xiaoyu He, Ray Li

We prove that there exists an absolute constant $\delta>0$ such any binary code $C\subset\{0,1\}^N$ tolerating $(1/2-\delta)N$ adversarial deletions must satisfy $|C|\le 2^{\poly\log N}$ and thus have rate asymptotically approaching $0$. This is the first constant fraction improvement over the trivial bound that codes tolerating $N/2$ adversarial deletions must have rate ... more >>>

Lijie Chen, Roei Tell

We propose a new approach to the hardness-to-randomness framework and to the promise-BPP=promise-P conjecture. Classical results rely on non-uniform hardness assumptions to construct derandomization algorithms that work in the worst-case, or rely on uniform hardness assumptions to construct derandomization algorithms that work only in the average-case. In both types of ... more >>>

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

An Algebraic Circuit for a polynomial $P\in F[x_1,\ldots,x_N]$ is a computational model for constructing the polynomial $P$ using only additions and multiplications. It is a \emph{syntactic} model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be easier to ... more >>>

Rahul Ilango, Hanlin Ren, Rahul Santhanam

We show that one-way functions exist if and only if there is some samplable distribution D such that it is hard to approximate the Kolmogorov complexity of a string sampled from D. Thus we characterize the existence of one-way functions by the average-case hardness of a natural \emph{uncomputable} problem on ... more >>>

Mark Braverman, Sumegha Garg, Or Zamir

In the coin problem we are asked to distinguish, with probability at least $2/3$, between $n$ $i.i.d.$ coins which are heads with probability $\frac{1}{2}+\beta$ from ones which are heads with probability $\frac{1}{2}-\beta$. We are interested in the space complexity of the coin problem, corresponding to the width of a read-once ... more >>>

Liron Bronfman, Ron Rothblum

Modern cryptography fundamentally relies on the assumption that the adversary trying to break the scheme is computationally bounded. This assumption lets us construct cryptographic protocols and primitives that are known to be impossible otherwise. In this work we explore the effect of bounding the adversary's power in other information theoretic ... more >>>

Ilya Volkovich

We present an elementary, self-contained proof of the result of Goldwasser and Rothblum [GR07] that the existence of a (perfect) statistically secure obfuscator implies a collapse of the polynomial hierarchy. In fact, we show that an existence of a weaker object implies a somewhat stronger statement. In addition, we extend ... more >>>

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $\Omega(n)$ space even on instances with $O(n)$ constraints. We also identify ... more >>>

Uma Girish, Ran Raz

We show that quantum algorithms of time T and space $S \ge \log T$ with intermediate measurements can be simulated by quantum algorithms of time $T\cdot \mathrm{poly}(S)$ and space $O(S\cdot \log T)$ without intermediate measurements. The best simulations prior to this work required either $\Omega(T)$ space (by the deferred measurement ... more >>>

Oded Goldreich

We briefly discuss a few open problems in the study of various models of testing graph properties, focusing on the query complexity of the various tasks. In the dense graph model, we discuss several open problems, including:

* Determining the complexity of testing triangle-freeness.

* Characterizing the class of properties ...
more >>>

Hanlin Ren, Rahul Santhanam

Meta-complexity studies the complexity of computational problems about complexity theory, such as the Minimum Circuit Size Problem (MCSP) and its variants. We show that a relativization barrier applies to many important open questions in meta-complexity. We give relativized worlds where:

* MCSP can be solved in deterministic polynomial time, but ... more >>>

Divesh Aggarwal, Eldon Chung, Maciej Obremski, Joao Ribeiro

Secret-sharing is one of the most basic and oldest primitives in cryptography, introduced by Shamir and Blakely in the 70s. It allows to strike a meaningful balance between availability and confidentiality of secret information. It has a host of applications most notably in threshold cryptography and multi-party computation. All known ... more >>>

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma

Cohen, Peri and Ta-Shma (STOC'21) considered the following question: Assume the vertices of an expander graph are labelled by $\pm 1$. What "test" functions $f : \{\pm 1\}^t \to \{\pm1 \}$ can or cannot distinguish $t$ independent samples from those obtained by a random walk? [CPTS'21] considered only balanced labelling, ... more >>>

Yanyi Liu, Rafael Pass

We show equivalence between the existence of one-way

functions and the existence of a \emph{sparse} language that is

hard-on-average w.r.t. some efficiently samplable ``high-entropy''

distribution.

In more detail, the following are equivalent:

- The existentence of a $S(\cdot)$-sparse language $L$ that is

hard-on-average with respect to some samplable ...
more >>>

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan

A pair of sources $\mathbf{X},\mathbf{Y}$ over $\{0,1\}^n$ are $k$-indistinguishable if their projections to any $k$ coordinates are identically distributed. Can some $\mathit{AC^0}$ function distinguish between two such sources when $k$ is big, say $k=n^{0.1}$? Braverman's theorem (Commun. ACM 2011) implies a negative answer when $\mathbf{X}$ is uniform, whereas Bogdanov et ... more >>>

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

An Algebraic Formula for a polynomial $P\in F[x_1,\ldots,x_N]$ is an algebraic expression for $P(x_1,\ldots,x_N)$ using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class $\mathrm{NC}^1.$ Proving lower bounds against this model is thus an important problem.

It is known that, to prove ... more >>>

Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Oliveira

We investigate randomized LEARN-uniformity, which captures the power of randomness and equivalence queries (EQ) in the construction of Boolean circuits for an explicit problem. This is an intermediate notion between P-uniformity and non-uniformity motivated by connections to learning, complexity, and logic. Building on a number of techniques, we establish the ... more >>>

Boaz Menuhin, Moni Naor

A card guessing game is played between two players, Guesser and Dealer. At the beginning of the game, the Dealer holds a deck of $n$ cards (labeled $1, ..., n$). For $n$ turns, the Dealer draws a card from the deck, the Guesser guesses which card was drawn, and then ... more >>>

Jacobo Toran, Florian Wörz

We show that the number of variables and the quantifier depth needed to distinguish a pair of graphs by first-order logic sentences exactly match the complexity measures of clause width and positive depth needed to refute the corresponding graph isomorphism formula in propositional narrow resolution.

Using this connection, we ... more >>>

Srikanth Srinivasan, S Venkitesh

Nisan and Szegedy (CC 1994) showed that any Boolean function $f:\{0,1\}^n\to\{0,1\}$ that depends on all its input variables, when represented as a real-valued multivariate polynomial $P(x_1,\ldots,x_n)$, has degree at least $\log n - O(\log \log n)$. This was improved to a tight $(\log n - O(1))$ bound by Chiarelli, Hatami ... more >>>

Louis Golowich

High-dimensional expanders generalize the notion of expander graphs to higher-dimensional simplicial complexes. In contrast to expander graphs, only a handful of high-dimensional expander constructions have been proposed, and no elementary combinatorial construction with near-optimal expansion is known. In this paper, we introduce an improved combinatorial high-dimensional expander construction, by modifying ... more >>>

Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh

We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as a bridge between the existing monotone and general games.

Using this game, we ... more >>>

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the $n$-fold GHZ game is at most $n^{-\Omega(1)}$. This was first established by Holmgren and ... more >>>

Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff

We give tight bounds on the degree $\ell$ homogenous parts $f_\ell$ of a bounded function $f$ on the cube. We show that if $f: \{\pm 1\}^n \rightarrow [-1,1]$ has degree $d$, then $\| f_\ell \|_\infty$ is bounded by $d^\ell/\ell!$, and $\| \hat{f}_\ell \|_1$ is bounded by $d^\ell e^{{\ell+1 \choose 2}} ... more >>>

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit

Over finite fields $F_q$ containing a root of unity of smooth order $n$ (smoothness means $n$ is the product of small primes), the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomial operations, such as multiplication, division, interpolation and multi-point evaluation. These operations can ... more >>>

Sravanthi Chede, Anil Shukla

We show that the QRAT simulation algorithm of $\forall$Exp+Res from [B. Kiesl and M. Seidl, 2019] cannot be lifted to IR-calc.

more >>>Suryajith Chillara

Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit $d^{O(1)}$-variate and degree $d$ polynomial $P_{d} \in VNP$ such that if any depth four circuit $C$ of bounded formal degree $d$ which computes a polynomial of bounded individual degree $O(1)$, that is functionally equivalent to $P_d$, then ... more >>>

Eshan Chattopadhyay, Jesse Goodman, David Zuckerman

Recently, there has been exciting progress in understanding the complexity of distributions. Here, the goal is to quantify the resources required to generate (or sample) a distribution. Proving lower bounds in this new setting is more challenging than in the classical setting, and has yielded interesting new techniques and surprising ... more >>>

igor razgon

We introduce a new graph parameter called linear upper maximum induced

matching width \textsc{lu-mim width}, denoted for a graph $G$ by $lu(G)$.

We prove that the smallest size of the \textsc{obdd} for $\varphi$,

the monotone 2-\textsc{cnf} corresponding to $G$, is sandwiched

between $2^{lu(G)}$ and $n^{O(lu(G))}$.

The upper bound ...
more >>>

Edward Pyne, Salil Vadhan

The classic Impagliazzo--Nisan--Wigderson (INW) psesudorandom generator (PRG) (STOC `94) for space-bounded computation uses a seed of length $O(\log n \cdot \log(nwd/\varepsilon))$ to fool ordered branching programs of length $n$, width $w$, and alphabet size $d$ to within error $\varepsilon$. A series of works have shown that the analysis of the ... more >>>

Sravanthi Chede, Anil Shukla

Merge Resolution (MRes [Beyersdorff et al. J. Autom. Reason.'2021] ) is a refutational proof system for quantified Boolean formulas (QBF). Each line of MRes consists of clauses with only existential literals, together with information of countermodels stored as merge maps. As a result, MRes has strategy extraction by design. The ... more >>>

Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco Servedio, Emanuele Viola

We analyze the Fourier growth, i.e. the $L_1$ Fourier weight at level $k$ (denoted $L_{1,k}$), of various well-studied classes of "structured" $\mathbb{F}_2$-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [CHHL19,CHLT19,CGLSS20] which show that upper bounds on Fourier growth (even at ... more >>>

Aniruddha Biswas, Palash Sarkar

The influence of a set of variables on a Boolean function has three separate definitions in the literature, the first due to Ben-Or and Linial (1989), the second due to Fischer et al. (2002) and Blais (2009) and the third due to Tal (2017). The goal of the present work ... more >>>

Vikraman Arvind, Venkatesan Guruswami

We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace Avoidance (USA) problem), and finding a common zero of a system of ... more >>>

Nikhil Mande, Ronald de Wolf

We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability $\epsilon$, getting the optimal constant factors in the leading terms in a number of different models.

The following are our results in the randomized model:

1) We give a general technique to convert ... more >>>

Henning Fernau, Kshitij Gajjar

A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider ... more >>>

Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming

Aaronson and Ambainis (STOC 2015, SICOMP 2018) claimed that the acceptance probability of every quantum algorithm that makes $q$ queries to an $N$-bit string can be estimated to within $\epsilon$ by a randomized classical algorithm of query complexity $O_q((N/\epsilon^2)^{1-1/2q})$. We describe a flaw in their argument but prove that the ... more >>>

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang

In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory---its hardness is mysterious, and a better understanding of its hardness can have ... more >>>

Divesh Aggarwal, Bhavana Kanukurthi, SaiLakshmiBhavana Obbattu, Maciej Obremski, Sruthi Sekar

At ITCS 2010, Dziembowski, Pietrzak, and Wichs introduced Non-malleable Codes (NMCs). Non-malleability is one of the strongest and most challenging notions of security considered in cryptography and protects against tampering attacks. In the context of coding schemes, non-malleability requires that it be infeasible to tamper the codeword of a message ... more >>>

Daniel Augot, Sarah Bordage, Jade Nardi

We consider the proximity testing problem for error-correcting codes which consist in evaluations of multivariate polynomials either of bounded individual degree or bounded total degree. Namely, given an

oracle function $f : L^m \rightarrow \mathbb F_q$, where $L\subset \mathbb F_q$, a verifier distinguishes whether $f$ is the evaluation of a ...
more >>>

Omar Alrabiah, Venkatesan Guruswami

We propose a framework to study the effect of local recovery requirements of codeword symbols on the dimension of linear codes, based on a combinatorial proxy that we call "visible rank." The locality constraints of a linear code are stipulated by a matrix $H$ of $\star$'s and $0$'s (which we ... more >>>

Roei Tell

The focus of this survey is the question of *quantified derandomization*, which was introduced by Goldreich and Wigderson (2014): Does derandomization of probabilistic algorithms become easier if we only want to derandomize algorithms that err with extremely small probability? How small does this probability need to be in order for ... more >>>

Sumanta Ghosh, Rohit Gurjar

We study the matroid intersection problem from the parallel complexity perspective. Given

two matroids over the same ground set, the problem asks to decide whether they have a common base and its search version asks to find a common base, if one exists. Another widely studied variant is the weighted ...
more >>>

Sabyasachi Basu, Akash Kumar, C. Seshadhri

Consider property testing on bounded degree graphs and let $\varepsilon > 0$ denote the proximity parameter. A remarkable theorem of Newman-Sohler (SICOMP 2013) asserts that all properties of planar graphs (more generally hyperfinite) are testable with query complexity only depending on $\varepsilon$. Recent advances in testing minor-freeness have proven that ... more >>>

Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani

We prove that for every Boolean function, the public-coin zero-error randomized communication complexity and the deterministic communication complexity are polynomially equivalent.

more >>>Iftach Haitner, Noam Mazor, Jad Silbak, Eliad Tsfadia

In distributed differential privacy, the parties perform analysis over their joint data while preserving the privacy for both datasets. Interestingly, for a few fundamental two-party functions such as inner product and Hamming distance, the accuracy of the distributed solution lags way behind what is achievable in the client-server setting. McGregor, ... more >>>

Zhiyuan Fan, Jiatu Li, Tianqi Yang

How much computational resource do we need for cryptography? This is an important question of both theoretical and practical interests. In this paper, we study the problem on pseudorandom functions (PRFs) in the context of circuit complexity. Perhaps surprisingly, we prove extremely tight upper and lower bounds in various circuit ... more >>>

Yilei Chen, Qipeng Liu, Mark Zhandry

We show polynomial-time quantum algorithms for the following problems:

(*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a ...
more >>>

Ron D. Rothblum, Michael Ezra

The inner product function $\langle x,y \rangle = \sum_i x_i y_i \bmod 2$ can be easily computed by a (linear-size) ${AC}^0(\oplus)$ circuit: that is, a constant depth circuit with AND, OR and parity (XOR) gates. But what if we impose the restriction that the parity gates can only be on ... more >>>

Xiaotie Deng, Yuhao Li, David Mguni, Jun Wang, Yaodong Yang

Similar to the role of Markov decision processes in reinforcement learning, Markov Games (also called Stochastic Games)lay down the foundation for the study of multi-agent reinforcement learning (MARL) and sequential agent interactions. In this paper, we introduce the solution concept, approximate Markov Perfect Equilibrium (MPE), to finite-state Stochastic Games repeated ... more >>>

Oded Goldreich, Dana Ron

A distribution is called $m$-grained if each element appears with probability that is an integer multiple of $1/m$.

We prove that, for any constant $c<1$, testing whether a distribution over $[\Theta(m)]$ is $m$-grained requires $\Omega(m^c)$ samples.

Srinivasan Arunachalam, João F. Doriguello

Hypercontractive inequalities for real-valued functions over the Boolean cube play an important role in theoretical computer science. In this work, we prove a hypercontractive inequality for matrix-valued functions defined over large alphabets, generalizing the result of Ben-Aroya, Regev, de Wolf (FOCS'08) for the Boolean alphabet. To obtain our result we ... more >>>

Olaf Beyersdorff, Benjamin Böhm

Quantified conflict-driven clause learning (QCDCL) is one of the main approaches for solving quantified Boolean formulas (QBF). We formalise and investigate several versions of QCDCL that include cube learning and/or pure-literal elimination, and formally compare the resulting solving models via proof complexity techniques. Our results show that almost all of ... more >>>

Eric Binnendyk

Boolean circuits are a model of computation. A class of Boolean circuits is called a polynomial class if the number of nodes is bounded by a polynomial function of the number of input variables. A class $C_n[s(n)]$ of Boolean functions is called learnable if there are algorithms that can approximate ... more >>>

Oded Goldreich, Dana Ron

We initiate a study of a new model of property testing that is a hybrid of testing properties of distributions and testing properties of strings.

Specifically, the new model refers to testing properties of distributions, but these are distributions over huge objects (i.e., very long strings).

Accordingly, the ...
more >>>

Siddharth Bhaskar

For a function $t : 2^\star \to 1^\star$, let $C_t$ be the set of problems decidable on input $x$ in time at most $t(x)$ almost everywhere. The Union Theorem of Meyer and McCreight asserts that any union $\bigcup_{i < \omega} C_{t_i}$ for a uniformly recursive sequence of bounds $t_i$ is ... 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 infinite collection of implication-free DQBF dependency schemes that generalise the reflexive resolution path dependency scheme. We establish soundness of all these schemes, implying that they can be ... more >>>

Gil Cohen, Tal Yankovitz

The Alon-Edmonds-Luby distance amplification procedure (FOCS 1995) is an algorithm that transforms a code with vanishing distance to a code with constant distance. AEL was invoked by Kopparty, Meir, Ron-Zewi, and Saraf (J. ACM 2017) for obtaining their state-of-the-art LDC, LCC and LTC. Cohen and Yankovitz (CCC 2021) devised a ... more >>>

Xuangui Huang, Peter Ivanov, Emanuele Viola

We study a simple and general template for constructing affine extractors by composing a linear transformation with resilient functions. Using this we show that good affine extractors can be computed by non-explicit circuits of various types, including AC0-Xor circuits: AC0 circuits with a layer of parity gates at the input. ... more >>>

Rahul Santhanam, Iddo Tzameret

We propose a diagonalization-based approach to several important questions in proof complexity. We illustrate this approach in the context of the algebraic proof system IPS and in the context of propositional proof systems more generally.

We give an explicit sequence of CNF formulas $\{\phi_n\}$ such that VNP$\neq$VP iff there are ... more >>>

Venkatesan Guruswami, Jonathan Mosheiff

We prove the existence of Reed-Solomon codes of any desired rate $R \in (0,1)$ that are combinatorially list-decodable up to a radius approaching $1-R$, which is the information-theoretic limit. This is established by starting with the full-length $[q,k]_q$ Reed-Solomon code over a field $\mathbb{F}_q$ that is polynomially larger than the ... more >>>

Nathan Geier

Assume that $X_0,X_1$ (respectively $Y_0,Y_1$) are $d_X$ (respectively $d_Y$) indistinguishable for circuits of a given size. It is well known that the product distributions $X_0Y_0,\,X_1Y_1$ are $d_X+d_Y$ indistinguishable for slightly smaller circuits. However, in probability theory where unbounded adversaries are considered through statistical distance, it is folklore knowledge that in ... more >>>

Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

We study a natural and quite general model of branch-and-bound algorithms. In this model, an algorithm attempts to minimize (or maximize) a function $f : D \to \mathbb{R}_{\geq 0}$ by making oracle queries to a heuristic $h_f$ satisfying

\[

\min_{x \in S} f(x) \leq h_f(S) \leq \gamma \cdot ...
more >>>

Amey Bhangale, Prahladh Harsha, Sourya Roy

In this note, we show the mixing of three-term progressions $(x, xg, xg^2)$ in every finite quasirandom group, fully answering a question of Gowers. More precisely, we show that for any $D$-quasirandom group $G$ and any three sets $A_1, A_2, A_3 \subset G$, we have

\[ \left|\Pr_{x,y\sim G}\left[ x \in ...
more >>>

Edward Pyne

We construct an explicit $\varepsilon$-hitting set generator (HSG) for regular ordered branching programs of length $n$ and $\textit{unbounded width}$ with a single accept state that has seed length

\[O(\log(n)(\log\log(n)+\log(1/\varepsilon))).\]

Previously, the best known seed length for regular branching programs of width $w$ with a single accept state was ...
more >>>

Leroy Chew, Friedrich Slivovsky

We pioneer a new technique that allows us to prove a multitude of previously open simulations in QBF proof complexity. In particular, we show that extended QBF Frege p-simulates clausal proof systems such as IR-Calculus, IRM-Calculus, Long-Distance Q-Resolution, and Merge Resolution.

These results are obtained by taking a technique ...
more >>>

Omar Alrabiah, Venkatesan Guruswami

A recent work of Li and Wootters (2021) shows a redundancy lower bound of $\Omega(\sqrt{Nk})$ for systematic linear $k$-batch codes of block length $N$ by looking at the $O(k)$ tensor power of the dual code. In this note, we present an alternate proof of their result via a linear independence ... more >>>

Guy Goldberg, Guy Rothblum

Suppose we have random sampling access to a huge object, such as a graph or a database.

Namely, we can observe the values of \emph{random} locations in the object, say random records in the database or random edges in the graph.

We cannot, however, query locations of our choice. Can ...
more >>>

Eshan Chattopadhyay, Jyun-Jie Liao

We consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An $(n,k,C)$-sumset source $\mathbf{X}$ is a distribution on $\{0,1\}^n$ of the form $\mathbf{X}_1 + \mathbf{X}_2 + \ldots + \mathbf{X}_C$, where $\mathbf{X}_i$'s are independent sources on $n$ bits ... more >>>

Benjamin Diamond, Amir Yehudayoff

We describe an explicit and simple subset of the discrete hypercube which cannot be exactly covered by fewer than exponentially many hyperplanes. The proof exploits a connection to communication complexity, and relies heavily on Razborov's lower bound for disjointness.

more >>>Sevag Gharibian, Dorian Rudolph

We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$ and $P^{QMA}$, respectively.

The former allows one to classify problems more finely than the Polynomial-Time Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate ...
more >>>

Eldon Chung, Maciej Obremski, Divesh Aggarwal

The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories:

(1) Constructions where one source has min-entropy rate about $1/2$, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability.

(2) Constructions where one source is uniform, and the other ...
more >>>

Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes

A locally testable code (LTC) is an error correcting code that has a property-tester. The tester reads $q$ bits that are randomly chosen, and rejects words with probability proportional to their distance from the code. The parameter $q$ is called the locality of the tester.

LTCs were initially studied as ... more >>>

Gal Arnon, Tomer Grossman

We introduce the notion of \emph{Min-Entropic Optimality} thereby providing a framework for arguing that a given algorithm computes a function better than any other algorithm. An algorithm is $k(n)$ Min-Entropic Optimal if for every distribution $D$ with min-entropy at least $k(n)$, its expected running time when its input is drawn ... more >>>

Ronen Shaltiel, Emanuele Viola

The hardness vs.~randomness paradigm aims to explicitly construct pseudorandom generators $G:\{0,1\}^r \to \{0,1\}^m$ that fool circuits of size $m$, assuming the existence of explicit hard functions. A ``high-end PRG'' with seed length $r=O(\log m)$ (implying BPP=P) was achieved in a seminal work of Impagliazzo and Wigderson (STOC 1997), assuming \textsc{the ... more >>>

Inbar Ben Yaacov, Gil Cohen, Tal Yankovitz

Since they were first introduced by Schulman (STOC 1993), the construction of tree codes remained an elusive open problem. The state-of-the-art construction by Cohen, Haeupler and Schulman (STOC 2018) has constant distance and $(\log n)^{e}$ colors for some constant $e > 1$ that depends on the distance, where $n$ is ... more >>>

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha

Consider a homogeneous degree $d$ polynomial $f = T_1 + \cdots + T_s$, $T_i = g_i(\ell_{i,1}, \ldots, \ell_{i, m})$ where $g_i$'s are homogeneous $m$-variate degree $d$ polynomials and $\ell_{i,j}$'s are linear polynomials in $n$ variables. We design a (randomized) learning algorithm that given black-box access to $f$, computes black-boxes for ... more >>>

Boris Bukh, Karthik C. S., Bhargav Narayanan

In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural.

(*) Panchromatic Graphs: For fixed integer k, a k-panchromatic graph is, roughly speaking, a balanced bipartite graph with one partition class equipartitioned into k colour classes in ...
more >>>

Monika Henzinger, Andrea Lincoln, Barna Saha

Statistics of small subgraph counts such as triangles, four-cycles, and $s$-$t$ paths of short lengths reveal important structural properties of the underlying graph. These problems have been widely studied in social network analysis. In most relevant applications, the graphs are not only massive but also change dynamically over time. Most ... more >>>

Noah Fleming, Toniann Pitassi, Robert Robere

We further the study of supercritical tradeoffs in proof and circuit complexity, which is a type of tradeoff between complexity parameters where restricting one complexity parameter forces another to exceed its worst-case upper bound. In particular, we prove a new family of supercritical tradeoffs between depth and size for Resolution, ... more >>>

Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams

For a complexity class $C$ and language $L$, a constructive separation of $L \notin C$ gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every $C$-algorithm attempting to decide $L$. We study the questions: Which lower bounds can be made constructive? What are the consequences ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Let $\Pi$ be a protocol over the $n$-party broadcast channel, where in each round, a pre-specified party broadcasts a symbol to all other parties. We wish to design a scheme that takes such a protocol $\Pi$ as input and outputs a noise resilient protocol $\Pi'$ that simulates $\Pi$ over the ... more >>>

Shuichi Hirahara, Mikito Nanashima

A PAC learning model involves two worst-case requirements: a learner must learn all functions in a class on all example distributions. However, basing the hardness of learning on NP-hardness has remained a key challenge for decades. In fact, recent progress in computational complexity suggests the possibility that a weaker assumption ... more >>>

Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, Chandra Kanta Mohapatra

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem is also closely related to fast algorithms for other natural ... more >>>

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, A. Shankar

The multiplicity Schwartz-Zippel lemma asserts that over a field, a low-degree polynomial cannot vanish with high multiplicity very often on a sufficiently large product set. Since its discovery in a work of Dvir, Kopparty, Saraf and Sudan [DKSS13], the lemma has found nu- merous applications in both math and computer ... more >>>

Scott Aaronson, DeVon Ingram, William Kretschmer

We show that, in the black-box setting, the behavior of quantum polynomial-time (${BQP}$) can be remarkably decoupled from that of classical complexity classes like ${NP}$. Specifically:

-There exists an oracle relative to which ${NP}^{{BQP}}\not \subset {BQP}^{{PH}}$, resolving a 2005 problem of Fortnow. Interpreted another way, we show that ${AC^0}$ circuits ... more >>>

Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams

In a Merlin-Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability $1$, and rejects invalid proofs with probability arbitrarily close to $1$. The running time of such a system is defined to be the length of Merlin's proof plus the running time of Arthur. We ... more >>>

Lijie Chen, Shuichi Hirahara, Neekon Vafa

What is a minimal worst-case complexity assumption that implies non-trivial average-case hardness of NP or PH? This question is well motivated by the theory of fine-grained average-case complexity and fine-grained cryptography. In this paper, we show that several standard worst-case complexity assumptions are sufficient to imply non-trivial average-case hardness ... more >>>

Alex Lombardi, Fermi Ma, Nicholas Spooner

A major difficulty in quantum rewinding is the fact that measurement is destructive: extracting information from a quantum state irreversibly changes it. This is especially problematic in the context of zero-knowledge simulation, where preserving the adversary's state is essential.

In this work, we develop new techniques for ...
more >>>

Tom Gur, Noam Lifshitz, Siqi Liu

We prove hypercontractive inequalities on high dimensional expanders. As in the settings of the p-biased hypercube, the symmetric group, and the Grassmann scheme, our inequalities are effective for global functions, which are functions that are not significantly affected by a restriction of a small set of coordinates. As applications, we ... more >>>

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in extensions to settings like the $p$-biased cube, slice, or Grassmannian, where variants of hypercontractivity have found a number of breakthrough applications including the resolution of ... more >>>

Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda

A language $L$ is random-self-reducible if deciding membership in $L$ can be reduced (in polynomial time) to deciding membership in $L$ for uniformly random instances. It is known that several "number theoretic" languages (such as computing the permanent of a matrix) admit random self-reductions. Feigenbaum and Fortnow showed that NP-complete ... more >>>

Bruno Pasqualotto Cavalar, Zhenjian Lu

Comparator circuits are a natural circuit model for studying bounded fan-out computation whose power sits between nondeterministic branching programs and general circuits. Despite having been studied for nearly three decades, the first superlinear lower bound against comparator circuits was proved only recently by Gál and Robere (ITCS 2020), who established ... more >>>

Robert Andrews, Michael Forbes

We show that any nonzero polynomial in the ideal generated by the $r \times r$ minors of an $n \times n$ matrix $X$ can be used to efficiently approximate the determinant. Specifically, for any nonzero polynomial $f$ in this ideal, we construct a small depth-three $f$-oracle circuit that approximates the ... more >>>

Ninad Rajgopal, Rahul Santhanam

Motivated by the goal of showing stronger structural results about the complexity of learning, we study the learnability of strong concept classes beyond P/poly, such as PSPACE/poly and EXP/poly. We show the following:

1. (Unconditional Lower Bounds for Learning) Building on [KKO13], we prove unconditionally that BPE/poly cannot be weakly ... more >>>

Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian

Entropy is a fundamental property of both classical and quantum systems, spanning myriad theoretical and practical applications in physics and computer science. We study the problem of obtaining estimates to within a multiplicative factor $\gamma>1$ of the Shannon entropy of probability distributions and the von Neumann entropy of mixed quantum ... more >>>

Oded Goldreich

This text provides a high-level description of the locally testable code constructed by Dinur, Evra, Livne, Lubotzky, and Mozes (ECCC, TR21-151).

In particular, the group theoretic aspects are abstracted as much as possible.

Theodoros Papamakarios

We show a quadratic separation between resolution and cut-free sequent calculus width. We use this gap to get, for the first time, first, a super-polynomial separation between resolution and cut-free sequent calculus for refuting CNF formulas, and secondly, a quadratic separation between resolution width and monomial space in polynomial calculus ... more >>>

Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee

k-median and k-means are the two most popular objectives for clustering algorithms. Despite intensive effort, a good understanding of the approximability of these objectives, particularly in $\ell_p$-metrics, remains a major open problem. In this paper, we significantly improve upon the hardness of approximation factors known in literature for these objectives ... more >>>

Srinivasan Arunachalam, Oded Regev, Penghui Yao

We show that for sufficiently large $n\geq 1$ and $d=C n^{3/4}$ for some universal constant $C>0$, a random spectrahedron with matrices drawn from Gaussian orthogonal ensemble has Gaussian surface area $\Theta(n^{1/8})$ with high probability.

more >>>tatsuie tsukiji

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>

Noga Ron-Zewi, Ron Rothblum

Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input $x$ belongs to a language $L \in NP$, with communication that is much shorter than the $NP$ witness. Such arguments, which grew out of the theory literature, are now drawing ... more >>>

Oded Goldreich

This is a purely pedagogical text.

We advocate using KW-games as a teaser (or ``riddle'') for a complexity theoretic course.

In particular, stating the KW-game for a familiar NP-complete problem such as 3-Colorability and asking to prove that it requires more than polylogarithmic communication poses a seemingly tractable question ...
more >>>

Ilario Bonacina, Maria Luisa Bonet

The propositional proof system Sherali-Adams (SA) has polynomial-size proofs of the pigeonhole principle (PHP). Similarly, the Nullstellensatz (NS) proof system has polynomial size proofs of the bijective (i.e. both functional and onto) pigeonhole principle (ofPHP). We characterize the strength of these algebraic proof systems in terms of Boolean proof systems ... more >>>