All reports in year 2022:

__
TR22-170
| 15th November 2022
__

Huck Bennett#### The Complexity of the Shortest Vector Problem

__
TR22-169
| 26th November 2022
__

Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman#### Extractors for Images of Varieties

__
TR22-168
| 23rd November 2022
__

Zubayir Kazi#### A Proof of the Generalized Union-Closed Set Conjecture assuming the Union-Closed Set Conjecture

Revisions: 2

__
TR22-167
| 23rd November 2022
__

Mark Braverman, Subhash Khot, Dor Minzer#### Parallel Repetition for the GHZ Game: Exponential Decay

__
TR22-166
| 23rd November 2022
__

Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu#### Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

__
TR22-165
| 22nd November 2022
__

TsunMing Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley#### Separation of the factorization norm and randomized communication complexity

__
TR22-164
| 20th November 2022
__

Shuichi Hirahara, Mikito Nanashima#### Learning versus Pseudorandom Generators in Constant Parallel Time

__
TR22-163
| 16th November 2022
__

Gil Cohen, Gal Maor#### Random Walks on Rotating Expanders

__
TR22-162
| 10th November 2022
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\widetilde{O}(n\sqrt{d})$ Monotonicity Tester

__
TR22-161
| 9th November 2022
__

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu#### Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut

__
TR22-160
| 31st October 2022
__

Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, N. V. Vinodchandran#### The Geometry of Rounding

__
TR22-159
| 18th November 2022
__

Songhua He, Periklis Papakonstantinou#### Deep Neural Networks: The Missing Complexity Parameter

__
TR22-158
| 18th November 2022
__

Ivan Hu, Andrew Morgan, Dieter van Melkebeek#### Query Complexity of Inversion Minimization on Trees

__
TR22-157
| 16th November 2022
__

Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov#### Border complexity via elementary symmetric polynomials

__
TR22-156
| 15th November 2022
__

Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joao Ribeiro#### Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms

__
TR22-155
| 15th November 2022
__

Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen#### Testing of Index-Invariant Properties in the Huge Object Model

__
TR22-154
| 6th November 2022
__

Gil Cohen, Itay Cohen#### Spectral Expanding Expanders

__
TR22-153
| 8th November 2022
__

Eshan Chattopadhyay, Jyun-Jie Liao#### Hardness against Linear Branching Programs and More

__
TR22-152
| 10th November 2022
__

Toniann Pitassi, Morgan Shirley, Adi Shraibman#### The Strength of Equality Oracles in Communication

__
TR22-151
| 12th November 2022
__

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey#### Low-depth arithmetic circuit lower bounds via shifted partials

__
TR22-150
| 7th November 2022
__

Aaron (Louie) Putterman, Edward Pyne#### Near-Optimal Derandomization of Medium-Width Branching Programs

__
TR22-149
| 7th November 2022
__

Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma#### Approximating Iterated Multiplication of Stochastic Matrices in Small Space

__
TR22-148
| 11th November 2022
__

Peter Ivanov, Raghu Meka, Emanuele Viola#### Efficient resilient functions

__
TR22-147
| 10th November 2022
__

Samir Datta, Chetan Gupta#### Evaluating Monotone Circuits on Surfaces

Revisions: 3

__
TR22-146
| 9th November 2022
__

Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai#### Interactive Coding with Small Memory

__
TR22-145
| 4th November 2022
__

Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz#### Revisiting Time-Space Tradeoffs for Function Inversion

__
TR22-144
| 7th November 2022
__

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy#### Streaming beyond sketching for Maximum Directed Cut

__
TR22-143
| 7th November 2022
__

Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny#### Certificate games

Revisions: 1

__
TR22-142
| 3rd November 2022
__

Emanuele Viola#### Correlation bounds against polynomials

__
TR22-141
| 20th October 2022
__

Sam Buss, Noah Fleming, Russell Impagliazzo#### TFNP Characterizations of Proof Systems and Monotone Circuits

Revisions: 2

__
TR22-140
| 10th October 2022
__

Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry#### Commitments to Quantum States

Revisions: 1

__
TR22-139
| 15th October 2022
__

Radu Curticapean, Nutan Limaye, Srikanth Srinivasan#### On the VNP-hardness of Some Monomial Symmetric Polynomials

__
TR22-138
| 5th October 2022
__

Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang#### Robustness for Space-Bounded Statistical Zero Knowledge

__
TR22-137
| 26th September 2022
__

Daniel Avraham , Amir Yehudayoff#### On blocky ranks of matrices

__
TR22-136
| 21st September 2022
__

Sepehr Assadi, Gillat Kol, Zhijun Zhang#### Rounds vs Communication Tradeoffs for Maximal Independent Sets

__
TR22-135
| 18th September 2022
__

Rahul Chugh, Supartha Poddar, Swagato Sanyal#### Decision Tree Complexity versus Block Sensitivity and Degree

Comments: 1

__
TR22-134
| 23rd September 2022
__

Greg McLellan, Alexey Milovanov#### Some Games on Turing Machines and Power from Random Strings

Revisions: 1

__
TR22-133
| 20th September 2022
__

Prahladh Harsha, Daniel Mitropolsky, Alon Rosen#### Downward Self-Reducibility in TFNP

Revisions: 1
,
Comments: 1

__
TR22-132
| 18th September 2022
__

Harm Derksen, Emanuele Viola#### Fooling polynomials using invariant theory

__
TR22-131
| 18th September 2022
__

Rafael Mendes de Oliveira, Akash Sengupta#### Radical Sylvester-Gallai for Cubics

__
TR22-130
| 15th September 2022
__

Hamed Hatami, Kaave Hosseini, Xiang Meng#### A Borsuk-Ulam lower bound for sign-rank and its application

__
TR22-129
| 15th September 2022
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang#### Binary Codes with Resilience Beyond 1/4 via Interaction

__
TR22-128
| 11th September 2022
__

Romain Bourneuf, Lukáš Folwarczný, Pavel Hubacek, Alon Rosen, Nikolaj Schwartzbach#### PPP-Completeness and Extremal Combinatorics

__
TR22-127
| 12th September 2022
__

Eric Allender, Shuichi Hirahara, Harsha Tirumala#### Kolmogorov Complexity Characterizes Statistical Zero Knowledge

Revisions: 1

__
TR22-126
| 12th September 2022
__

Andrei Krokhin, Jakub Opršal#### An Invitation to the Promise Constraint Satisfaction Problem

__
TR22-125
| 9th September 2022
__

Shir Peleg, Amir Shpilka, Ben Lee Volk#### Tensor Reconstruction Beyond Constant Rank

__
TR22-124
| 9th September 2022
__

Oded Goldreich, Guy Rothblum, Tal Skverer#### On Interactive Proofs of Proximity with Proof-Oblivious Queries

Revisions: 3

__
TR22-123
| 4th September 2022
__

Alexander A. Sherstov#### The Approximate Degree of DNF and CNF Formulas

__
TR22-122
| 29th August 2022
__

Young Kun Ko#### Efficient Linearization Implies the Multiphase Conjecture

__
TR22-121
| 27th August 2022
__

William Hoza#### Recent Progress on Derandomizing Space-Bounded Computation

Revisions: 1

__
TR22-120
| 24th August 2022
__

Jan Krajicek#### On the existence of strong proof complexity generators

Comments: 1

__
TR22-119
| 24th August 2022
__

Shuichi Hirahara#### NP-Hardness of Learning Programs and Partial MCSP

__
TR22-118
| 23rd August 2022
__

Huacheng Yu#### Strong XOR Lemma for Communication with Bounded Rounds

__
TR22-117
| 23rd August 2022
__

Ronen Shaltiel, Jad Silbak#### Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits

__
TR22-116
| 17th August 2022
__

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii#### Constant-Depth Sorting Networks

__
TR22-115
| 17th August 2022
__

Dieter van Melkebeek, Andrew Morgan#### Polynomial Identity Testing via Evaluation of Rational Functions

__
TR22-114
| 16th August 2022
__

Hao Wu#### Direct Sum Theorems From Fortification

__
TR22-113
| 11th August 2022
__

Yanyi Liu, Rafael Pass#### Leakage-Resilient Hardness v.s. Randomness

__
TR22-112
| 12th August 2022
__

Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre#### Randomised Composition and Small-Bias Minimax

__
TR22-111
| 1st August 2022
__

Robert Andrews#### On Matrix Multiplication and Polynomial Identity Testing

__
TR22-110
| 1st August 2022
__

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit#### Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves

__
TR22-109
| 27th July 2022
__

Siddharth Iyer, Michael Whitmeyer#### Searching for Regularity in Bounded Functions

__
TR22-108
| 18th July 2022
__

Shuichi Hirahara, Nobutaka Shimizu#### Hardness Self-Amplification from Feasible Hard-Core Sets

__
TR22-107
| 20th July 2022
__

Shachar Lovett, Jiapeng Zhang#### Fractional certificates for bounded functions

__
TR22-106
| 21st July 2022
__

Suryajith Chillara, Coral Grichener, Amir Shpilka#### On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts

__
TR22-105
| 18th July 2022
__

Ilario Bonacina, Nicola Galesi, Massimo Lauria#### On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

__
TR22-104
| 18th July 2022
__

Nader Bshouty#### On One-Sided Testing Affine Subspaces

Revisions: 1

__
TR22-103
| 15th July 2022
__

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman#### Almost Chor--Goldreich Sources and Adversarial Random Walks

Revisions: 1

__
TR22-102
| 15th July 2022
__

Venkatesan Guruswami, Xin Lyu, Xiuhan Wang#### Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness

__
TR22-101
| 15th July 2022
__

Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar#### A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

__
TR22-100
| 14th July 2022
__

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy#### Streaming complexity of CSPs with randomly ordered constraints

__
TR22-099
| 14th July 2022
__

Nikhil Gupta, Chandan Saha, Bhargav Thankey#### Equivalence Test for Read-Once Arithmetic Formulas

__
TR22-098
| 12th July 2022
__

Nader Bshouty#### Non-Adaptive Proper Learning Polynomials

__
TR22-097
| 3rd July 2022
__

Lijie Chen, Ron D. Rothblum, Roei Tell#### Unstructured Hardness to Average-Case Randomness

__
TR22-096
| 8th July 2022
__

Mika Göös, Siddhartha Jain#### Communication Complexity of Collision

__
TR22-095
| 5th July 2022
__

Meghal Gupta, Rachel Zhang#### Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel

__
TR22-094
| 3rd July 2022
__

Stasys Jukna#### Notes on Monotone Read-k Circuits

Revisions: 1

__
TR22-093
| 28th June 2022
__

Joshua Cook#### More Verifier Efficient Interactive Protocols For Bounded Space

Revisions: 3

__
TR22-092
| 2nd July 2022
__

Peter Ivanov, Liam Pavlovic, Emanuele Viola#### On correlation bounds against polynomials

__
TR22-091
| 2nd July 2022
__

Harm Derksen, Emanuele Viola#### Quasirandom groups enjoy interleaved mixing

__
TR22-090
| 24th June 2022
__

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials

__
TR22-089
| 18th June 2022
__

Ilario Bonacina, Neil Thapen#### A separation of PLS from PPP

__
TR22-088
| 15th June 2022
__

Anthony Leverrier, Gilles Zémor#### Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes

Revisions: 1

__
TR22-087
| 8th June 2022
__

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell#### Depth-$d$ Threshold Circuits vs. Depth-$(d + 1)$ AND-OR Trees

Revisions: 1

__
TR22-086
| 9th June 2022
__

Lijie Chen, Jiatu Li, Tianqi Yang#### Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs

Revisions: 1

__
TR22-085
| 8th June 2022
__

Andrzej Lingas#### A Note on Lower Bounds for Monotone Multilinear Boolean Circuits

__
TR22-084
| 2nd June 2022
__

Yanyi Liu, Rafael Pass#### Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity

__
TR22-083
| 2nd June 2022
__

Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie#### Hardness of Maximum Likelihood Learning of DPPs

__
TR22-082
| 27th May 2022
__

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro#### Low-Degree Polynomials Extract from Local Sources

__
TR22-081
| 26th May 2022
__

Zhenjian Lu, Igor Oliveira#### Theory and Applications of Probabilistic Kolmogorov Complexity

__
TR22-080
| 25th May 2022
__

Meena Mahajan, Gaurav Sood#### QBF Merge Resolution is powerful but unnatural

__
TR22-079
| 25th May 2022
__

Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao#### Lower Bound Methods for Sign-rank and their Limitations

__
TR22-078
| 8th May 2022
__

Dan Karliner, Amnon Ta-Shma#### Improved local testing for multiplicity codes

__
TR22-077
| 13th May 2022
__

Max Hopkins, Ting-Chun Lin#### Explicit Lower Bounds Against $\Omega(n)$-Rounds of Sum-of-Squares

__
TR22-076
| 16th May 2022
__

Hunter Monroe#### Average-Case Hardness of Proving Tautologies and Theorems

__
TR22-075
| 21st May 2022
__

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan#### Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes

Revisions: 1

__
TR22-074
| 20th May 2022
__

Michael Saks, Rahul Santhanam#### On Randomized Reductions to the Random Strings

__
TR22-073
| 18th May 2022
__

Itay Kalev, Amnon Ta-Shma#### Unbalanced Expanders from Multiplicity Codes

__
TR22-072
| 15th May 2022
__

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira#### Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

__
TR22-071
| 13th May 2022
__

Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay#### Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product

__
TR22-070
| 8th May 2022
__

Pranav Bisht, Ilya Volkovich#### On Solving Sparse Polynomial Factorization Related Problems

Revisions: 6

__
TR22-069
| 28th April 2022
__

Silas Richelson, Sourya Roy#### List-Decoding Random Walk XOR Codes Near the Johnson Bound

Revisions: 1

__
TR22-068
| 5th May 2022
__

Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy#### Sketching Approximability of (Weak) Monarchy Predicates

Revisions: 1

__
TR22-067
| 4th May 2022
__

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay#### Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time

__
TR22-066
| 4th May 2022
__

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy#### On sketching approximations for symmetric Boolean CSPs

__
TR22-065
| 3rd May 2022
__

Madhu Sudan#### Streaming and Sketching Complexity of CSPs: A survey

Revisions: 1

__
TR22-064
| 2nd May 2022
__

Deepanshu Kush, Shubhangi Saraf#### Improved Low-Depth Set-Multilinear Circuit Lower Bounds

__
TR22-063
| 30th April 2022
__

Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans#### Fast Multivariate Multipoint Evaluation Over All Finite Fields

__
TR22-062
| 2nd May 2022
__

Paolo Liberatore#### Superredundancy: A tool for Boolean formula minimization complexity analysis

__
TR22-061
| 30th April 2022
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable $k$-CSPs: I

__
TR22-060
| 27th April 2022
__

Nikolay Vereshchagin#### How much randomness is needed to convert MA protocols to AM protocols?

__
TR22-059
| 27th April 2022
__

Siddhesh Chaubal, Anna Gal#### Diameter versus Certificate Complexity of Boolean Functions

__
TR22-058
| 26th April 2022
__

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao#### Separations in Proof Complexity and TFNP

Revisions: 1

__
TR22-057
| 25th April 2022
__

Lijie Chen, Roei Tell#### When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems

Revisions: 2

__
TR22-056
| 18th April 2022
__

Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand#### Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

__
TR22-055
| 23rd April 2022
__

Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret#### Simple Hard Instances for Low-Depth Algebraic Proofs

__
TR22-054
| 21st April 2022
__

Anastasia Sofronova, Dmitry Sokolov#### A Lower Bound for $k$-DNF Resolution on Random CNF Formulas via Expansion

__
TR22-053
| 24th April 2022
__

Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap#### On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs

Revisions: 2
,
Comments: 1

__
TR22-052
| 18th April 2022
__

Tal Herman, Guy Rothblum#### Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties

__
TR22-051
| 18th April 2022
__

Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida#### Low Degree Testing over the Reals

__
TR22-050
| 12th April 2022
__

Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena#### Circuits Resilient to Short-Circuit Errors

__
TR22-049
| 4th April 2022
__

Xinyu Mao, Noam Mazor, Jiapeng Zhang#### Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions

Revisions: 1

__
TR22-048
| 4th April 2022
__

Hanlin Ren, Rahul Santhanam, Zhikun Wang#### On the Range Avoidance Problem for Circuits

__
TR22-047
| 4th April 2022
__

Manik Dhar, Zeev Dvir#### Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds

Revisions: 1

__
TR22-046
| 4th April 2022
__

Dmitry Itsykson, Artur Riazanov#### Automating OBDD proofs is NP-hard

__
TR22-045
| 4th April 2022
__

Gil Cohen, Tal Yankovitz#### Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

Revisions: 1

__
TR22-044
| 4th April 2022
__

Meghal Gupta, Naren Manoj#### An Optimal Algorithm for Certifying Monotone Functions

__
TR22-043
| 2nd April 2022
__

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan#### Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs

__
TR22-042
| 31st March 2022
__

Vikraman Arvind, Pushkar Joglekar#### Matrix Polynomial Factorization via Higman Linearization

__
TR22-041
| 23rd March 2022
__

TsunMing Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein#### Boolean functions with small approximate spectral norm

__
TR22-040
| 10th March 2022
__

Benjamin Böhm, Tomáš Peitl, Olaf Beyersdorff#### Should decisions in QCDCL follow prefix order?

__
TR22-039
| 14th March 2022
__

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan#### Parallel Repetition For All 3-Player Games Over Binary Alphabet

__
TR22-038
| 13th March 2022
__

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi#### Lower bounds for Polynomial Calculus with extension variables over finite fields

Revisions: 1

__
TR22-037
| 10th March 2022
__

Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta#### Robust Radical Sylvester-Gallai Theorem for Quadratics

__
TR22-036
| 10th March 2022
__

Agnes Schleitzer, Olaf Beyersdorff#### Classes of Hard Formulas for QBF Resolution

Revisions: 1

__
TR22-035
| 7th March 2022
__

Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff#### A Characterization of Multiclass Learnability

__
TR22-034
| 3rd March 2022
__

Chin Ho Lee, Edward Pyne, Salil Vadhan#### Fourier Growth of Regular Branching Programs

__
TR22-033
| 1st March 2022
__

Ivan Mihajlin, Anastasia Sofronova#### A better-than-$3\log{n}$ depth lower bound for De Morgan formulas with restrictions on top gates

Comments: 2

__
TR22-032
| 1st March 2022
__

Iftach Haitner, Noam Mazor, Jad Silbak#### Incompressiblity and Next-Block Pseudoentropy

__
TR22-031
| 16th February 2022
__

Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse#### Transparency Beyond VNP in the Monotone Setting

Revisions: 4

__
TR22-030
| 18th February 2022
__

Aniruddha Biswas, Palash Sarkar#### On The ''Majority is Least Stable'' Conjecture.

Revisions: 1

__
TR22-029
| 27th February 2022
__

Anthony Leverrier, Gilles Zémor#### Quantum Tanner codes

Revisions: 2

__
TR22-028
| 23rd February 2022
__

Dan Karliner, Roie Salama, Amnon Ta-Shma#### The plane test is a local tester for Multiplicity Codes

__
TR22-027
| 22nd February 2022
__

Guy Blanc, Dean Doron#### New Near-Linear Time Decodable Codes Closer to the GV Bound

Revisions: 1

__
TR22-026
| 17th February 2022
__

James Cook, Ian Mertz#### Trading Time and Space in Catalytic Branching Programs

__
TR22-025
| 15th February 2022
__

Oliver Korten#### Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle

Revisions: 3

__
TR22-024
| 17th February 2022
__

Louis Golowich, Salil Vadhan#### Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs

Revisions: 1

__
TR22-023
| 19th February 2022
__

Erfan Khaniki#### Nisan--Wigderson generators in Proof Complexity: New lower bounds

__
TR22-022
| 18th February 2022
__

Vikraman Arvind, Pushkar Joglekar#### On Efficient Noncommutative Polynomial Factorization via Higman Linearization

Revisions: 3

__
TR22-021
| 19th February 2022
__

Xin Lyu#### Improved Pseudorandom Generators for $\mathrm{AC}^0$ Circuits

__
TR22-020
| 18th February 2022
__

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar#### Worst-Case to Average-Case Reductions via Additive Combinatorics

__
TR22-019
| 17th February 2022
__

Guangxu Yang, Jiapeng Zhang#### Simulation Methods in Communication Lower Bounds, Revisited

__
TR22-018
| 15th February 2022
__

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao#### Further Collapses in TFNP

__
TR22-017
| 15th February 2022
__

Ron D. Rothblum, Prashant Nalini Vasudevan#### Collision-Resistance from Multi-Collision-Resistance

Revisions: 2

__
TR22-016
| 15th February 2022
__

Artur Ignatiev, Ivan Mihajlin, Alexander Smal#### Super-cubic lower bound for generalized Karchmer-Wigderson games

__
TR22-015
| 12th February 2022
__

Mika Göös, Stefan Kiefer, Weiqiang Yuan#### Lower Bounds for Unambiguous Automata via Communication Complexity

__
TR22-014
| 8th February 2022
__

Joshua Cook, Dana Moshkovitz#### Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE

Revisions: 1

__
TR22-013
| 5th February 2022
__

Nader Bshouty, Oded Goldreich#### On properties that are non-trivial to test

__
TR22-012
| 2nd February 2022
__

Anup Rao, Oscar Sprumont#### On List Decoding Transitive Codes From Random Errors

__
TR22-011
| 25th January 2022
__

Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen#### Public-Key Encryption from Continuous LWE

__
TR22-010
| 18th January 2022
__

Marshall Ball, Dana Dachman-Soled, Julian Loss#### (Nondeterministic) Hardness vs. Non-Malleability

__
TR22-009
| 17th January 2022
__

C. Ramya, Anamay Tengse#### On Finer Separations between Subclasses of Read-once Oblivious ABPs

__
TR22-008
| 14th January 2022
__

Gil Cohen, Dean Doron, Ori Sberlo#### Approximating Large Powers of Stochastic Matrices in Small Space

Comments: 1

__
TR22-007
| 14th January 2022
__

Halley Goldberg, Valentine Kabanets#### A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information

__
TR22-006
| 12th January 2022
__

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi#### Secret Sharing, Slice Formulas, and Monotone Real Circuits

__
TR22-005
| 11th January 2022
__

Anup Rao#### Sunflowers: from soil to oil

Revisions: 3

__
TR22-004
| 3rd January 2022
__

Silas Richelson, Sourya Roy#### Analyzing Ta-Shma’s Code via the Expander Mixing Lemma

__
TR22-003
| 4th January 2022
__

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere#### On Semi-Algebraic Proofs and Algorithms

Revisions: 1

__
TR22-002
| 11th December 2021
__

Sravanthi Chede, Anil Shukla#### Extending Merge Resolution to a Family of Proof Systems

__
TR22-001
| 28th December 2021
__

Yogesh Dahiya, Meena Mahajan#### On (Simple) Decision Tree Rank

Revisions: 1

Huck Bennett

Computational problems on point lattices play a central role in many areas of computer science including integer programming, coding theory, cryptanalysis, and especially the design of secure cryptosystems. In this survey, we present known results and open questions related to the complexity of the most important of these problems, the ... more >>>

Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman

We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map $f : \mathbb{F}_q^r \to \mathbb{F}_q^n$ to an element sampled uniformly at random from a $k$-dimensional variety $V \subseteq \mathbb{F}_q^r$. This class of sources generalizes both polynomial sources, studied by Dvir, ... more >>>

Zubayir Kazi

Abstract The Union Closed Set Conjecture states that if a set system X\subseteq\mathcal{P}([n]) is closed under pairwise unions, then there exists a\in[n] in at least half of the sets of X. We show that there is a very natural generalization of the union closed set conjecture which gives a lower ... more >>>

Mark Braverman, Subhash Khot, Dor Minzer

We show that the value of the $n$-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

more >>>Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu

We study boolean constraint satisfaction problems (CSPs) $\mathrm{Max}\text{-}\mathrm{CSP}^f_n$ for all predicates $f: \{ 0, 1 \} ^k \to \{ 0, 1 \}$. In these problems, given an integer $v$ and a list of constraints over $n$ boolean variables, each obtained by applying $f$ to a sequence of literals, we wish ... more >>>

TsunMing Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley

In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate $\gamma_2$-factorization norm is a lower bound for these parameters and asked whether a stronger ... more >>>

Shuichi Hirahara, Mikito Nanashima

A polynomial-stretch pseudorandom generator (PPRG) in NC$^0$ (i.e., constant parallel time) is one of the most important cryptographic primitives, especially for constructing highly efficient cryptography and indistinguishability obfuscation. The celebrated work (Applebaum, Ishai, and Kushilevitz, SIAM Journal on Computing, 2006) on randomized encodings yields the characterization of sublinear-stretch pseudorandom generators ... more >>>

Gil Cohen, Gal Maor

Random walks on expanders are a powerful tool which found applications in many areas of theoretical computer science, and beyond. However, they come with an inherent cost -- the spectral expansion of the corresponding power graph deteriorates at a rate that is exponential in the length of the walk. As ... more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

The problem of testing monotonicity for Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$ is a classic topic in property testing. When $n=2$, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making $\widetilde{O}(\varepsilon^{-2}\sqrt{d})$ queries. Up to polylog ... more >>>

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

We consider the Max-Cut problem, asking how much space is needed by a streaming algorithm in order to estimate the value of the maximum cut in a graph. This problem has been extensively studied over the last decade, and we now have a near-optimal lower bound for one-pass streaming algorithms, ... more >>>

Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, N. V. Vinodchandran

Rounding has proven to be a fundamental tool in theoretical computer science. By observing that rounding and partitioning of $\mathbb{R}^d$ are equivalent, we introduce the following natural partition problem which we call the secluded hypercube partition problem: Given $k\in\mathbb{N}$ (ideally small) and $\epsilon>0$ (ideally large), is there a partition of ... more >>>

Songhua He, Periklis Papakonstantinou

Deep neural networks are the dominant machine learning model. We show that this model is missing a crucial complexity parameter. Today, the standard neural network (NN) model is a circuit whose gates (neurons) are ReLU units. The complexity of a NN is quantified by the depth (number of layers) and ... more >>>

Ivan Hu, Andrew Morgan, Dieter van Melkebeek

We consider the following computational problem: Given a rooted tree and a ranking of its leaves, what is the minimum number of inversions of the leaves that can be attained by ordering the tree? This variation of the well-known problem of counting inversions in arrays originated in mathematical psychology. It ... more >>>

Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

In (ToCT’20) Kumar surprisingly proved that every polynomial can be approximated as a sum of a constant and a product of linear polynomials. In this work, we prove the converse of Kumar's result which ramifies in a surprising new formulation of Waring rank and border Waring rank. From this conclusion, ... more >>>

Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joao Ribeiro

We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices. Specifically, we prove that ... more >>>

Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

The study of distribution testing has become ubiquitous in the area of property testing, both for its theoretical appeal, as well as for its applications in other fields of Computer Science, and in various real-life statistical tasks.

The original distribution testing model relies on samples drawn independently from the distribution ... more >>>

Gil Cohen, Itay Cohen

Dinitz, Schapira, and Valadarsky (Algorithmica 2017) introduced the intriguing notion of expanding expanders -- a family of expander graphs with the property that every two consecutive graphs in the family differ only on a small number of edges. Such a family allows one to add and remove vertices with only ... more >>>

Eshan Chattopadhyay, Jyun-Jie Liao

In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once

branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is

a branching program where each node is allowed to make $\mathbb{F}_2$-linear queries, and are read-once in the ...
more >>>

Toniann Pitassi, Morgan Shirley, Adi Shraibman

It is well-known that randomized communication protocols are more powerful than deterministic protocols. In particular the Equality function requires $\Omega(n)$ deterministic communication complexity but has efficient randomized protocols. Previous work of Chattopadhyay, Lovett and Vinyals shows that randomized communication is strictly stronger than what can be solved by deterministic protocols ... more >>>

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey

We prove super-polynomial lower bounds for low-depth arithmetic circuits using the shifted partials measure [Gupta-Kamath-Kayal-Saptharishi, CCC 2013], [Kayal, ECCC 2012] and the affine projections of partials measure [Garg-Kayal-Saha, FOCS 2020], [Kayal-Nair-Saha, STACS 2016]. The recent breakthrough work of Limaye, Srinivasan and Tavenas [FOCS 2021] proved these lower bounds by proving ... more >>>

Aaron (Louie) Putterman, Edward Pyne

We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length $n$ and width $w$ in space

$$\tilde{O}\left(\log n+\sqrt{\log n}\cdot\log w\right).$$

In particular, we obtain an almost optimal space $\tilde{O}(\log n)$ derandomization of programs up to width $w=2^{\sqrt{\log n}}$.

Previously, ...
more >>>

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

Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem's space complexity as it constitutes the main route towards resolving the $\mathbf{BPL}$ vs. $\mathbf{L}$ problem. The seminal work by Saks and Zhou (FOCS 1995) ... more >>>

Peter Ivanov, Raghu Meka, Emanuele Viola

An $n$-bit boolean function is resilient to coalitions of size $q$

if no fixed set of $q$ bits is likely to influence the value of the

function when the other $n-q$ bits are chosen uniformly at random,

even though the function is nearly balanced. We construct explicit

functions resilient to ...
more >>>

Samir Datta, Chetan Gupta

In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly many faces. We show that this problem can be ... more >>>

Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai

In this work, we design an interactive coding scheme that converts any two party interactive protocol $\Pi$ into another interactive protocol $\Pi'$, such that even if errors are introduced during the execution of $\Pi'$, the parties are able to determine what the outcome of running $\Pi$ would be in an ... more >>>

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

We study the black-box function inversion problem, which is the problem of finding $x \in [N]$ such that $f(x) = y$, given as input some challenge point $y$ in the image of a function $f : [N] \to [N]$, using $T$ oracle queries to $f$ and preprocessed advice $\sigma \in ... more >>>

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

We give an $\widetilde{O}(\sqrt{n})$-space single-pass $0.483$-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on $n$ vertices. This improves over an $O(\log n)$-space $4/9 < 0.45$ approximation algorithm due to Chou, Golovnev, Velusamy (FOCS 2020), which was known to be optimal for $o(\sqrt{n})$-space algorithms.

... more >>>Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny

We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting.

We give upper and lower ... more >>>

Emanuele Viola

A survey on correlation bounds against polynomials.

more >>>Sam Buss, Noah Fleming, Russell Impagliazzo

Connections between proof complexity and circuit complexity have become major tools for obtaining lower bounds in both areas. These connections -- which take the form of interpolation theorems and query-to-communication lifting theorems -- translate efficient proofs into small circuits, and vice versa, allowing tools from one area to be applied ... more >>>

Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry

What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the ... more >>>

Radu Curticapean, Nutan Limaye, Srikanth Srinivasan

A polynomial $P\in F[x_1,\ldots,x_n]$ is said to be symmetric if it is invariant under any permutation of its input variables. The study of symmetric polynomials is a classical topic in mathematics, specifically in algebraic combinatorics and representation theory. More recently, they have been studied in several works in computer science, ... more >>>

Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang

We show that the space-bounded Statistical Zero Knowledge classes SZK_L and NISZK_L are surprisingly robust, in that the power of the verifier and simulator can be strengthened or weakened without affecting the resulting class. Coupled with other recent characterizations of these classes, this can be viewed as lending support to ... more >>>

Daniel Avraham , Amir Yehudayoff

A matrix is blocky if it is a blowup of a permutation matrix. The blocky rank of a matrix M is the minimum number of blocky matrices that linearly span M. Hambardzumyan, Hatami and Hatami defined blocky rank and showed that it is connected to communication complexity and operator theory. ... more >>>

Sepehr Assadi, Gillat Kol, Zhijun Zhang

We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex -- this way, each edge is known by both ... more >>>

Rahul Chugh, Supartha Poddar, Swagato Sanyal

Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. While decision tree complexity is long known to be polynomially related with many other measures, the optimal exponents of many of these relations are not known. It ... more >>>

Greg McLellan, Alexey Milovanov

Denote by $R$ the set of strings with high Kolmogorov complexity. In [E. Allender, H. Buhrman, M. Kouck\'y, D. van Melkebeek, and D. Ronneburger.

Power from random strings.

\emph{SIAM Journal on Computing}, 35:1467--1493, 2006.] the idea of using $R$ as an oracle for resource-bounded computation models was presented. This idea ...
more >>>

Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

A problem is downward self-reducible if it can be solved efficiently given an oracle that returns

solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is

well studied and it is known that all downward self-reducible problems are in PSPACE. In this

paper, we initiate the study of ...
more >>>

Harm Derksen, Emanuele Viola

We revisit the problem of constructing explicit pseudorandom generators

that fool with error $\epsilon$ degree-$d$ polynomials in $n$ variables

over the field $F_q$, in the case of large $q$. Previous constructions

either have seed length at least $2^{d}\log q$, and thus are only non-trivial

when the degree is less than ...
more >>>

Rafael Mendes de Oliveira, Akash Sengupta

Let $\mathcal{F} = \{F_1, \ldots, F_m\}$ be a finite set of irreducible homogeneous multivariate polynomials of degree at most $3$ such that $F_i$ does not divide $F_j$ for $i\neq j$.

We say that $\mathcal{F}$ is a cubic radical Sylvester-Gallai configuration if for any two distinct $F_i,F_j$ there exists a ...
more >>>

Hamed Hatami, Kaave Hosseini, Xiang Meng

We introduce a new topological argument based on the Borsuk-Ulam theorem to prove a lower bound on sign-rank.

This result implies the strongest possible separation between randomized and unbounded-error communication complexity. More precisely, we show that for a particular range of parameters, the randomized communication complexity of ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

In the reliable transmission problem, a sender, Alice, wishes to transmit a bit-string x to a remote receiver, Bob, over a binary channel with adversarial noise. The solution to this problem is to encode x using an error correcting code. As it is long known that the distance of binary ... more >>>

Romain Bourneuf, Lukáš Folwarczný, Pavel Hubacek, Alon Rosen, Nikolaj Schwartzbach

Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on monochromatic subgraphs and the Erdos-Rado sunflower lemma. Implicit versions of the corresponding total search problems are known to be PWPP-hard; here "implicit" means that the collection is represented ... more >>>

Eric Allender, Shuichi Hirahara, Harsha Tirumala

We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to ... more >>>

Andrei Krokhin, Jakub Opršal

The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and Zhuk.

At about ... more >>>

Shir Peleg, Amir Shpilka, Ben Lee Volk

We give reconstruction algorithms for subclasses of depth-$3$ arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank, and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. Specifically, we obtain the following results:

1. ... more >>>

Oded Goldreich, Guy Rothblum, Tal Skverer

Interactive proofs of proximity (IPPs) offer ultra-fast

approximate verification of assertions regarding their input,

where ultra-fast means that only a small portion of the input is read

and approximate verification is analogous to the notion of

approximate decision that underlies property testing.

Specifically, in an IPP, the prover can make ...
more >>>

Alexander A. Sherstov

The approximate degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that approximates $f$ pointwise: $|f(x)-p(x)|\leq1/3$ for all $x\in\{0,1\}^n.$ For every $\delta>0,$ we construct CNF and DNF formulas of polynomial size with approximate degree $\Omega(n^{1-\delta}),$ essentially matching the trivial upper bound of $n.$ This ... more >>>

Young Kun Ko

The main motivation for studying linear data structures and circuits is the intuition that non-linear advice cannot help in computing a linear operator. Jukna and Schnitger formalized this as a conjecture which states that all circuits computing a linear operator can be ``linearized," with only a constant size blow-up. We ... more >>>

William Hoza

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In the past few years (say, from 2017 to 2022), there has been some exciting ... more >>>

Jan Krajicek

The working conjecture from K'04 that there is a proof complexity generator hard for all

proof systems can be equivalently formulated (for p-time generators) without a reference to proof complexity notions

as follows:

\begin{itemize}

\item There exist a p-time function $g$ extending each input by one bit such that its ...
more >>>

Shuichi Hirahara

A long-standing open question in computational learning theory is to prove NP-hardness of learning efficient programs, the setting of which is in between proper learning and improper learning. Ko (COLT'90, SICOMP'91) explicitly raised this open question and demonstrated its difficulty by proving that there exists no relativizing proof of NP-hardness ... more >>>

Huacheng Yu

In this paper, we prove a strong XOR lemma for bounded-round two-player randomized communication. For a function $f:\mathcal{X}\times \mathcal{Y}\rightarrow\{0,1\}$, the $n$-fold XOR function $f^{\oplus n}:\mathcal{X}^n\times \mathcal{Y}^n\rightarrow\{0,1\}$ maps $n$ input pairs $(X_1,\ldots,X_n,Y_1,\ldots,Y_n)$ to the XOR of the $n$ output bits $f(X_1,Y_1)\oplus \cdots \oplus f(X_n, Y_n)$. We prove that if every ... more >>>

Ronen Shaltiel, Jad Silbak

Guruswami and Smith (J. ACM 2016) considered codes for channels that are poly-size circuits which modify at most a $p$-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon's binary symmetric channel (BSC), but weaker than Hamming's channels which are computationally unbounded.

Guruswami and ...
more >>>

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii

In this paper, we address sorting networks that are constructed from comparators of arity $k > 2$. That is, in our setting the arity of the comparators -- or, in other words, the number of inputs that can be sorted at the unit cost -- is a parameter. We study ... more >>>

Dieter van Melkebeek, Andrew Morgan

We introduce a hitting set generator for Polynomial Identity Testing

based on evaluations of low-degree univariate rational functions at

abscissas associated with the variables. Despite the univariate

nature, we establish an equivalence up to rescaling with a generator

introduced by Shpilka and Volkovich, which has a similar structure but

uses ...
more >>>

Hao Wu

We revisit the direct sum theorems in communication complexity which askes whether the resource to solve $n$ communication problems together is (approximately) the sum of resources to solve these problems separately. Our work starts with the observation that Meir and Dinur's fortification lemma for protocol size over rectangles can be ... more >>>

Yanyi Liu, Rafael Pass

A central open problem in complexity theory concerns the question of

whether all efficient randomized algorithms can be simulated by

efficient deterministic algorithms. The celebrated ``hardness

v.s. randomness” paradigm pioneered by Blum-Micali (SIAM JoC’84),

Yao (FOCS’84) and Nisan-Wigderson (JCSS’94) presents hardness

assumptions under which $\prBPP = \prP$, but these hardness ...
more >>>

Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre

We prove two results about randomised query complexity $\mathrm{R}(f)$. First, we introduce a linearised complexity measure $\mathrm{LR}$ and show that it satisfies an inner-optimal composition theorem: $\mathrm{R}(f\circ g) \geq \Omega(\mathrm{R}(f) \mathrm{LR}(g))$ for all partial $f$ and $g$, and moreover, $\mathrm{LR}$ is the largest possible measure with this property. In particular, ... more >>>

Robert Andrews

We show that lower bounds on the border rank of matrix multiplication can be used to non-trivially derandomize polynomial identity testing for small algebraic circuits. Letting $\underline{R}(n)$ denote the border rank of $n \times n \times n$ matrix multiplication, we construct a hitting set generator with seed length $O(\sqrt{n} \cdot ... more >>>

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

Concretely efficient interactive oracle proofs (IOPs) are of interest due to their applications to scaling blockchains, their minimal security assumptions, and their potential future-proof resistance to quantum attacks.

Scalable IOPs, in which prover time scales quasilinearly with the computation size and verifier time scales poly-logarithmically with it, have been known ... more >>>

Siddharth Iyer, Michael Whitmeyer

Given a function $f:\mathbb F_2^n \to [-1,1]$, this work seeks to find a large affine subspace $\mathcal U$ such that $f$, when restricted to $\mathcal U$, has small nontrivial Fourier coefficients.

We show that for any function $f:\mathbb F_2^n \to [-1,1]$ with Fourier degree $d$, there exists an affine subspace ... more >>>

Shuichi Hirahara, Nobutaka Shimizu

We consider the question of hardness self-amplification: Given a Boolean function $f$ that is hard to compute on a $o(1)$-fraction of inputs drawn from some distribution, can we prove that $f$ is hard to compute on a $(\frac{1}{2} - o(1))$-fraction of inputs drawn from the same distribution? We prove hardness ... more >>>

Shachar Lovett, Jiapeng Zhang

A folklore conjecture in quantum computing is that the acceptance probability of a quantum query algorithm can be approximated by a classical decision tree, with only a polynomial increase in the number of queries. Motivated by this conjecture, Aaronson and Ambainis (Theory of Computing, 2014) conjectured that this should hold ... more >>>

Suryajith Chillara, Coral Grichener, Amir Shpilka

We say that two given polynomials $f, g \in R[x_1, \ldots, x_n]$, over a ring $R$, are equivalent under shifts if there exists a vector $(a_1, \ldots, a_n)\in R^n$ such that $f(x_1+a_1, \ldots, x_n+a_n) = g(x_1, \ldots, x_n)$. This is a special variant of the polynomial projection problem in Algebraic ... more >>>

Ilario Bonacina, Nicola Galesi, Massimo Lauria

Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size.

more >>>Nader Bshouty

We study the query complexity of one-sided $\epsilon$-testing the class of Boolean functions $f:F^n\to \{0,1\}$ that describe affine subspaces and Boolean functions that describe axis-parallel affine subspaces, where $F$ is any finite field. We give a polynomial-time $\epsilon$-testers that ask $\tilde O(1/\epsilon)$ queries. This improves the query complexity $\tilde O(|F|/\epsilon)$ ... more >>>

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically ... more >>>

Venkatesan Guruswami, Xin Lyu, Xiuhan Wang

In the range avoidance problem, the input is a multi-output Boolean circuit with more outputs than inputs, and the goal is to find a string outside its range (which is guaranteed to exist). We show that well-known explicit construction questions such as finding binary linear codes achieving the Gilbert-Varshamov bound ... more >>>

Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar

A code $C \colon \{0,1\}^k \to \{0,1\}^n$ is a $q$-locally decodable code ($q$-LDC) if one can recover any chosen bit $b_i$ of the message $b \in \{0,1\}^k$ with good confidence by randomly querying the encoding $x = C(b)$ on at most $q$ coordinates. Existing constructions of $2$-LDCs achieve $n = ... more >>>

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely Max-DICUT, for which random ordering makes a provable difference. Whereas a $4/9 \approx 0.445$ approximation of DICUT requires $\Omega(\sqrt{n})$ space with ... more >>>

Nikhil Gupta, Chandan Saha, Bhargav Thankey

We study the polynomial equivalence problem for orbits of read-once arithmetic formulas (ROFs). Read-once formulas have received considerable attention in both algebraic and Boolean complexity and have served as a testbed for developing effective tools and techniques for analyzing circuits. Two $n$-variate polynomials $f, g \in \mathbb{F}[\mathbf{x}]$ are equivalent, denoted ... more >>>

Nader Bshouty

We give the first polynomial-time *non-adaptive* proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. Our algorithm, for $s$-sparse polynomial over $n$ variables, makes $q=(s/\epsilon)^{\gamma(s,\epsilon)}\log n$ queries where $2.66\le \gamma(s,\epsilon)\le 6.922$ and runs in $\tilde O(n)\cdot poly(s,1/\epsilon)$ time. We also show that for any $\epsilon=1/s^{O(1)}$ any non-adaptive ... more >>>

Lijie Chen, Ron D. Rothblum, Roei Tell

The leading technical approach in uniform hardness-to-randomness in the last two decades faced several well-known barriers that caused results to rely on overly strong hardness assumptions, and yet still yield suboptimal conclusions.

In this work we show uniform hardness-to-randomness results that *simultaneously break through all of the known barriers*. Specifically, ... more >>>

Mika Göös, Siddhartha Jain

The Collision problem is to decide whether a given list of numbers $(x_1,\ldots,x_n)\in[n]^n$ is $1$-to-$1$ or $2$-to-$1$ when promised one of them is the case. We show an $n^{\Omega(1)}$ randomised communication lower bound for the natural two-party version of Collision where Alice holds the first half of the bits of ... more >>>

Meghal Gupta, Rachel Zhang

Given a noiseless protocol $\pi_0$ computing a function $f(x, y)$ of Alice and Bob's private inputs $x, y$, the goal of interactive coding is to construct an error-resilient protocol $\pi$ computing $f$ such that even if some fraction of the communication is adversarially corrupted, both parties still learn $f(x, y)$. ... more >>>

Stasys Jukna

A monotone Boolean $(\lor,\land)$ circuit $F$ computing a Boolean function $f$ is a read-$k$ circuit if the polynomial produced (purely syntactically) by the arithmetic $(+,\times)$ version of $F$ has the property that for every prime implicant of $f$, the polynomial contains a monomial with the same set of variables, each ... more >>>

Joshua Cook

Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$, and $\mathbf{CoNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$. ... more >>>

Peter Ivanov, Liam Pavlovic, Emanuele Viola

We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over $\mathbb{F}_{2}$. Our main contributions include:

1. In STOC 2020, CHHLZ introduced a new technique to prove correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their ... more >>>

Harm Derksen, Emanuele Viola

Let $G$ be a group such that any non-trivial representation has dimension

at least $d$. Let $X=(X_{1},X_{2},\ldots,X_{t})$ and $Y=(Y_{1},Y_{2},\ldots,Y_{t})$

be distributions over $G^{t}$. Suppose that $X$ is independent from

$Y$. We show that for any $g\in G$ we have

\[

\left|\mathbb{P}[X_{1}Y_{1}X_{2}Y_{2}\cdots X_{t}Y_{t}=g]-1/|G|\right|\le\frac{|G|^{2t-1}}{d^{t-1}}\sqrt{\mathbb{E}_{h\in G^{t}}X(h)^{2}}\sqrt{\mathbb{E}_{h\in G^{t}}Y(h)^{2}}.

\]

Our results generalize, improve, and ...
more >>>

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits.

More specifically, our previous work applied the well-known partial derivative method in a new setting, that of 'lopsided' set-multilinear polynomials. A ... more >>>

Ilario Bonacina, Neil Thapen

Recently it was shown that PLS is not contained in PPADS (ECCC report TR22-058). We show that this separation already implies that PLS is not contained in PPP. These separations are shown for the decision tree model of TFNP and imply similar separations in the type-2, relativized model.

Important note. ... more >>>

Anthony Leverrier, Gilles Zémor

We introduce and analyse an efficient decoder for the quantum Tanner codes that can correct adversarial errors of linear weight. Previous decoders for quantum low-density parity-check codes could only handle adversarial errors of weight $O(\sqrt{n \log n})$. We also work on the link between quantum Tanner codes and the Lifted ... more >>>

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

For $n \in \mathbb{N}$ and $d = o(\log \log n)$, we prove that there is a Boolean function $F$ on $n$ bits and a value $\gamma = 2^{-\Theta(d)}$ such that $F$ can be computed by a uniform depth-$(d + 1)$ $\text{AC}^0$ circuit with $O(n)$ wires, but $F$ cannot be computed ... more >>>

Lijie Chen, Jiatu Li, Tianqi Yang

In a recent work, Fan, Li, and Yang (STOC 2022) constructed a family of almost-universal hash functions such that each function in the family is computable by $(2n + o(n))$-gate circuits of fan-in $2$ over the $B_2$ basis. Applying this family, they established the existence of pseudorandom functions computable by ... more >>>

Andrzej Lingas

A monotone Boolean circuit is a restriction of a Boolean circuit

allowing for the use of disjunctions, conjunctions, the Boolean

constants, and the input variables. A monotone Boolean circuit is

multilinear if for any AND gate the two input functions have no

variable in common. We ...
more >>>

Yanyi Liu, Rafael Pass

A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. We consider this problem in the context of promise problems (i.e,. the $\prBPP$ v.s. $\prP$ problem) and show that for all sufficiently large constants $c$, the following ... more >>>

Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

Determinantal Point Processes (DPPs) are a widely used probabilistic model for negatively correlated sets. DPPs have been successfully employed in Machine Learning applications to select a diverse, yet representative subset of data. In these applications, the parameters of the DPP need to be fitted to match the data; typically, we ... more >>>

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro

We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, ... more >>>

Zhenjian Lu, Igor Oliveira

Diverse applications of Kolmogorov complexity to learning [CIKK16], circuit complexity [OPS19], cryptography [LP20], average-case complexity [Hir21], and proof search [Kra22] have been discovered in recent years. Since the running time of algorithms is a key resource in these fields, it is crucial in the corresponding arguments to consider time-bounded variants ... more >>>

Meena Mahajan, Gaurav Sood

The Merge Resolution proof system (M-Res) for QBFs, proposed by Beyersdorff et al. in 2019, explicitly builds partial strategies inside refutations. The original motivation for this approach was to overcome the limitations encountered in long-distance Q-Resolution proof system (LD-Q-Res), where the syntactic side-conditions, while prohibiting all unsound resolutions, also end ... more >>>

Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao

The sign-rank of a matrix $A$ with $\pm 1$ entries is the smallest rank of a real matrix with the same sign pattern as $A$. To the best of our knowledge, there are only three known methods for proving lower bounds on the sign-rank of explicit matrices: (i) Sign-rank is ... more >>>

Dan Karliner, Amnon Ta-Shma

Multiplicity codes are a generalization of Reed-Muller codes which include derivatives as well as the values of low degree polynomials, evaluated in every point in $\mathbb{F}_p^m$.

Similarly to Reed-Muller codes, multiplicity codes have a local nature that allows for local correction and local testing.

Recently, the authors and ...
more >>>

Max Hopkins, Ting-Chun Lin

We construct an explicit family of 3-XOR instances hard for $\Omega(n)$-levels of the Sum-of-Squares (SoS) semi-definite programming hierarchy. Not only is this the first explicit construction to beat brute force search (beyond low-order improvements (Tulsiani 2021, Pratt 2021)), combined with standard gap amplification techniques it also matches the (optimal) hardness ... more >>>

Hunter Monroe

We consolidate two widely believed conjectures about tautologies---no optimal proof system exists, and most require superpolynomial size proofs in any system---into a $p$-isomorphism-invariant condition satisfied by all paddable $\textbf{coNP}$-complete languages or none. The condition is: for any Turing machine (TM) $M$ accepting the language, $\textbf{P}$-uniform input families requiring superpolynomial time ... more >>>

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan

We study the following natural question on random sets of points in $\mathbb{F}_2^m$:

Given a random set of $k$ points $Z=\{z_1, z_2, \dots, z_k\} \subseteq \mathbb{F}_2^m$, what is the dimension of the space of degree at most $r$ multilinear polynomials that vanish on all points in $Z$?

We ... more >>>

Michael Saks, Rahul Santhanam

We study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants.

As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language $L$ that has a randomized ... more >>>

Itay Kalev, Amnon Ta-Shma

In 2007 Guruswami, Umans and Vadhan gave an explicit construction of a lossless condenser based on Parvaresh-Vardy codes. This lossless condenser is a basic building block in many constructions, and, in particular, is behind the state of the art extractor constructions.

We give an alternative construction that is based on ... more >>>

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

Understanding the relationship between the worst-case and average-case complexities of $\mathrm{NP}$ and of other subclasses of $\mathrm{PH}$ is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the ... more >>>

Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay

We establish an $\epsilon$-sensitive hierarchy separation for monotone arithmetic computations. The notion of $\epsilon$-sensitive monotone lower bounds was recently introduced by Hrubes [Computational Complexity'20]. We show the following:

(1) There exists a monotone polynomial over $n$ variables in VNP that cannot be computed by $2^{o(n)}$ size monotone ...
more >>>

Pranav Bisht, Ilya Volkovich

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most $s$ terms and individual degree bounded by $d$ can itself have at most $s^{O(d^2\log ... more >>>

Silas Richelson, Sourya Roy

In a breakthrough result, Ta-Shma described an explicit construction of an almost optimal binary code (STOC 2017). Ta-Shma's code has distance $\frac{1-\varepsilon}{2}$ and rate $\Omega\bigl(\varepsilon^{2+o(1)}\bigr)$ and thus it almost achieves the Gilbert-Varshamov bound, except for the $o(1)$ term in the exponent. The prior best list-decoding algorithm for (a variant of) ... more >>>

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

We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first ... more >>>

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Hrube\v{s} and Wigderson (2015) initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the white-box setting, deterministic polynomial-time algorithms are known for this problem ... more >>>

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy

A Boolean maximum constraint satisfaction problem, Max-CSP\((f)\), is specified by a predicate \(f:\{-1,1\}^k\to\{0,1\}\). An \(n\)-variable instance of Max-CSP\((f)\) consists of a list of constraints, each of which applies \(f\) to \(k\) distinct literals drawn from the \(n\) variables. For \(k=2\), Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios ... more >>>

Madhu Sudan

In this survey we describe progress over the last decade or so in understanding the complexity of solving constraint satisfaction problems (CSPs) approximately in the streaming and sketching models of computation. After surveying some of the results we give some sketches of the proofs and in particular try to explain ... more >>>

Deepanshu Kush, Shubhangi Saraf

In this paper, we prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial $f$ in VNP defined over $n^2$ variables, and of degree $n$, such that any product-depth $\Delta$ set-multilinear formula computing $f$ has size at least $n^{\Omega ... more >>>

Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field $\mathbb{F}$ that outputs the evaluations of an $m$-variate polynomial of ... more >>>

Paolo Liberatore

A superredundant clause is a clause that is redundant in the resolution closure of a formula. The converse concept of superirredundancy ensures membership of the clause in all minimal CNF formulae that are equivalent to the given one. This allows for building formulae where some clauses are fixed when minimizing ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

We consider the $P$-CSP problem for $3$-ary predicates $P$ on satisfiable instances. We show that under certain conditions on $P$ and a $(1,s)$ integrality gap instance of the $P$-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness $s+\varepsilon$, for every constant $\varepsilon>0$. ... more >>>

Nikolay Vereshchagin

The Merlin-Arthur class of languages MA is included into Arthur-Merlin class AM, and into PP. For a standard transformation of a given MA protocol with Arthur's message (= random string) of length $a$ and Merlin's message of length $m$ to a PP machine, the latter needs $O(ma)$ random bits. The ... more >>>

Siddhesh Chaubal, Anna Gal

In this paper, we introduce a measure of Boolean functions we call diameter, that captures the relationship between certificate complexity and several other measures of Boolean functions. Our measure can be viewed as a variation on alternating number, but while alternating number can be exponentially larger than certificate complexity, we ... more >>>

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: Resolution cannot be efficiently simulated by SA when the coefficients are written in unary. We also show that Reversible Resolution (a variant of MaxSAT ... more >>>

Lijie Chen, Roei Tell

What is the actual cost of derandomization? And can we get it for free? These questions were recently raised by Doron et. al (FOCS 2020) and have been attracting considerable interest. In this work we extend the study of these questions to the setting of *derandomizing interactive proofs systems*.

... more >>>Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand

The classical coding theorem in Kolmogorov complexity states that if an $n$-bit string $x$ is sampled with probability $\delta$ by an algorithm with prefix-free domain then K$(x) \leq \log(1/\delta) + O(1)$. In a recent work, Lu and Oliveira [LO21] established an unconditional time-bounded version of this result, by showing that ... more >>>

Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret

We prove super-polynomial lower bounds on the size of propositional proof systems operating with constant-depth algebraic circuits over fields of zero characteristic. Specifically, we show that the subset-sum variant $\sum_{i,j,k,l\in[n]} z_{ijkl}x_ix_jx_kx_l-\beta = 0$, for Boolean variables, does not have polynomial-size IPS refutations where the refutations are multilinear and written as ... more >>>

Anastasia Sofronova, Dmitry Sokolov

Random $\Delta$-CNF formulas are one of the few candidates that are expected to be hard to refute in any proof system. One of the frontiers in the direction of proving lower bounds on these formulas is the $k$-DNF Resolution proof system (aka $\mathrm{Res}(k)$). Assume we sample $m$ clauses over $n$ ... more >>>

Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

We investigate the complexity of languages that correspond to algebraic real numbers, and we present improved upper bounds on the complexity of these languages. Our key technical contribution is the presentation of improved uniform TC^0 circuits

for division, matrix powering, and related problems, where the improvement is in terms of ...
more >>>

Tal Herman, Guy Rothblum

Given i.i.d. samples from an unknown distribution over a large domain $[N]$, approximating several basic quantities, including the distribution's support size, its entropy, and its distance from the uniform distribution, requires $\Theta(N / \log N)$ samples [Valiant and Valiant, STOC 2011].

Suppose, however, that we can interact with a powerful ... more >>>

Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida

We study the problem of testing whether a function $f: \mathbb{R}^n \to \mathbb{R}$ is a polynomial of degree at most $d$ in the distribution-free testing model. Here, the distance between functions is measured with respect to an unknown distribution $\mathcal{D}$ over $\mathbb{R}^n$ from which we can draw samples. In contrast ... more >>>

Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena

Given a Boolean circuit $C$, we wish to convert it to a circuit $C'$ that computes the same function as $C$ even if some of its gates suffer from adversarial short circuit errors, i.e., their output is replaced by the value of one of their inputs [KLM97]. Can we ... more >>>

Xinyu Mao, Noam Mazor, Jiapeng Zhang

Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). The three major efficiency measures of these primitives are: seed length, number of calls to the one-way function, and adaptivity of these calls. Although a long ... more >>>

Hanlin Ren, Rahul Santhanam, Zhikun Wang

We consider the range avoidance problem (called Avoid): given the description of a circuit $C:\{0, 1\}^n \to \{0, 1\}^\ell$ (where $\ell > n$), find a string $y\in\{0, 1\}^\ell$ that is not in the range of $C$. This problem is complete for the class APEPP that corresponds to explicit constructions of ... more >>>

Manik Dhar, Zeev Dvir

We show that a randomly chosen linear map over a finite field gives a good hash function in the $\ell_\infty$ sense. More concretely, consider a set $S \subset \mathbb{F}_q^n$ and a randomly chosen linear map $L : \mathbb{F}_q^n \to \mathbb{F}_q^t$ with $q^t$ taken to be sufficiently smaller than $|S|$. Let ... more >>>

Dmitry Itsykson, Artur Riazanov

We prove that the proof system OBDD(and, weakening) is not automatable unless P = NP. The proof is based upon the celebrated result of Atserias and Muller [FOCS 2019] about the hardness of automatability for resolution. The heart of the proof is lifting with a multi-output indexing gadget from resolution ... more >>>

Gil Cohen, Tal Yankovitz

In their highly influential paper, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004) introduced the notion of a relaxed locally decodable code (RLDC). Similarly to a locally decodable code (Katz-Trevisan; STOC 2000), the former admits access to any desired message symbol with only a few queries to a possibly corrupted ... more >>>

Meghal Gupta, Naren Manoj

Given query access to a monotone function $f\colon\{0,1\}^n\to\{0,1\}$ with certificate complexity $C(f)$ and an input $x^{\star}$, we design an algorithm that outputs a size-$C(f)$ subset of $x^{\star}$ certifying the value of $f(x^{\star})$. Our algorithm makes $O(C(f) \cdot \log n)$ queries to $f$, which matches the information-theoretic lower bound for this ... more >>>

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan

We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition $\mathcal G^{\otimes n}$ decays polynomially fast to zero; that is, there ... more >>>

Vikraman Arvind, Pushkar Joglekar

In continuation to our recent work on noncommutative

polynomial factorization, we consider the factorization problem for

matrices of polynomials and show the following results.

\begin{itemize}

\item Given as input a full rank $d\times d$ matrix $M$ whose entries

$M_{ij}$ are polynomials in the free noncommutative ring

more >>>

TsunMing Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein

The sum of the absolute values of the Fourier coefficients of a function $f:\mathbb{F}_2^n \to \mathbb{R}$ is called the spectral norm of $f$. Green and Sanders' quantitative version of Cohen's idempotent theorem states that if the spectral norm of $f:\mathbb{F}_2^n \to \{0,1\}$ is at most $M$, then the support of ... more >>>

Benjamin Böhm, Tomáš Peitl, Olaf Beyersdorff

Quantified conflict-driven clause learning (QCDCL) is one of the main solving approaches for quantified Boolean formulas (QBF). One of the differences between QCDCL and propositional CDCL is that QCDCL typically follows the prefix order of the QBF for making decisions.

We investigate an alternative model for QCDCL solving where decisions ...
more >>>

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

We prove that for every 3-player (3-prover) game, with binary questions and answers and value less than $1$, the value of the $n$-fold parallel repetition of the game decays polynomially fast to $0$. That is, for every such game, there exists a constant $c>0$, such that the value of the ... more >>>

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

For every prime p > 0, every n > 0 and ? = O(logn), we show the existence

of an unsatisfiable system of polynomial equations over O(n log n) variables of degree O(log n) such that any Polynomial Calculus refutation over F_p with M extension variables, each depending on at ...
more >>>

Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta

We prove a robust generalization of a Sylvester-Gallai type theorem for quadratic polynomials, generalizing the result in [S'20].

More precisely, given a parameter $0 < \delta \leq 1$ and a finite collection $\mathcal{F}$ of irreducible and pairwise independent polynomials of degree at most 2, we say that $\mathcal{F}$ is a ...
more >>>

Agnes Schleitzer, Olaf Beyersdorff

To date, we know only a few handcrafted quantified Boolean formulas (QBFs) that are hard for central QBF resolution systems such as Q and QU, and only one specific QBF family to separate Q and QU.

Here we provide a general method to construct hard formulas for Q and ... more >>>

Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff

A seminal result in learning theory characterizes the PAC learnability of binary classes through the Vapnik-Chervonenkis dimension. Extending this characterization to the general multiclass setting has been open since the pioneering works on multiclass PAC learning in the late 1980s. This work resolves this problem: we characterize multiclass PAC learnability ... more >>>

Chin Ho Lee, Edward Pyne, Salil Vadhan

We analyze the Fourier growth, i.e. the $L_1$ Fourier weight at level $k$ (denoted $L_{1,k}$), of read-once regular branching programs.

We prove that every read-once regular branching program $B$ of width $w \in [1,\infty]$ with $s$ accepting states on $n$-bit inputs must have its $L_{1,k}$ bounded by

$$

\min\left\{ ...
more >>>

Ivan Mihajlin, Anastasia Sofronova

We prove that a modification of Andreev's function is not computable by $(3 + \alpha - \varepsilon) \log{n}$ depth De Morgan formula with $(2\alpha - \varepsilon)\log{n}$ layers of AND gates at the top for any $1/5 > \alpha > 0$ and any constant $\varepsilon > 0$. In order to do ... more >>>

Iftach Haitner, Noam Mazor, Jad Silbak

A distribution is k-incompressible, Yao [FOCS ’82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy, Hastad, Impagliazzo, Levin, and Luby [SICOMP 99], and to other cryptographic hardness assumptions, was unclear.

... more >>>Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse

Recently Hrubes and Yehudayoff (2021) showed a connection between the monotone algebraic circuit complexity of \emph{transparent} polynomials and a geometric complexity measure of their Newton polytope. They then used this connection to prove lower bounds against monotone VP (mVP). We extend their work by showing that their technique can be ... more >>>

Aniruddha Biswas, Palash Sarkar

We show that the ''majority is least stable'' conjecture is true for $n=1$ and $3$ and false for all odd $n\geq 5$.

more >>>Anthony Leverrier, Gilles Zémor

Tanner codes are long error correcting codes obtained from short codes and a graph, with bits on the edges and parity-check constraints from the short codes enforced at the vertices of the graph. Combining good short codes together with a spectral expander graph yields the celebrated expander codes of Sipser ... more >>>

Dan Karliner, Roie Salama, Amnon Ta-Shma

Multiplicity codes are a generalization of RS and RM codes where for each evaluation point we output the evaluation of a low-degree polynomial and all of its directional derivatives up to order $s$. Multi-variate multiplicity codes are locally decodable with the natural local decoding algorithm that reads values on a ... more >>>

Guy Blanc, Dean Doron

We construct a family of binary codes of relative distance $\frac{1}{2}-\varepsilon$ and rate $\varepsilon^{2} \cdot 2^{-\log^{\alpha}(1/\varepsilon)}$ for $\alpha \approx \frac{1}{2}$ that are decodable, probabilistically, in near linear time. This improves upon the rate of the state-of-the-art near-linear time decoding near the GV bound due to Jeronimo, Srivastava, and Tulsiani, who ... more >>>

James Cook, Ian Mertz

An $m$-catalytic branching program (Girard, Koucky, McKenzie 2015) is a set of $m$ distinct branching programs for $f$ which are permitted to share internal (i.e. non-source non-sink) nodes. While originally introduced as a non-uniform analogue to catalytic space, this also gives a natural notion of amortized non-uniform space complexity for ... more >>>

Oliver Korten

A recurring challenge in the theory of pseudorandomness and circuit complexity is the explicit construction of ``incompressible strings,'' i.e. finite objects which lack a specific type of structure or simplicity. In most cases, there is an associated NP search problem which we call the ``compression problem,'' where we are given ... more >>>

Louis Golowich, Salil Vadhan

We study the pseudorandomness of random walks on expander graphs against tests computed by symmetric functions and permutation branching programs. These questions are motivated by applications of expander walks in the coding theory and derandomization literatures. We show that expander walks fool symmetric functions up to a $O(\lambda)$ error in ... more >>>

Erfan Khaniki

A map $g:\{0,1\}^n\to\{0,1\}^m$ ($m>n$) is a hard proof complexity generator for a proof system $P$ iff for every string $b\in\{0,1\}^m\setminus Rng(g)$, formula $\tau_b(g)$ naturally expressing $b\not\in Rng(g)$ requires superpolynomial size $P$-proofs. One of the well-studied maps in the theory of proof complexity generators is Nisan--Wigderson generator. Razborov (Annals of Mathematics ... more >>>

Vikraman Arvind, Pushkar Joglekar

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result:

Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where ... more >>>

Xin Lyu

We give PRG for depth-$d$, size-$m$ $\mathrm{AC}^0$ circuits with seed length $O(\log^{d-1}(m)\log(m/\varepsilon)\log\log(m))$. Our PRG improves on previous work [TX13, ST19, Kel21] from various aspects. It has optimal dependence on $\frac{1}{\varepsilon}$ and is only one “$\log\log(m)$” away from the lower bound barrier. For the case of $d=2$, the seed length tightly ... more >>>

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar

We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time $T$ that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time $\widetilde{O}(T)$ that are correct on ... more >>>

Guangxu Yang, Jiapeng Zhang

The notion of lifting theorems is a generic method to lift hardness of one-party functions to two-party lower bounds in communication model. It has many applications in different areas such as proof complexity, game theory, combinatorial optimization. Among many lifting results, a central idea is called Raz-McKenize simulation (FOCS 1997). ... more >>>

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

We show $\text{EOPL}=\text{PLS}\cap\text{PPAD}$. Here the class $\text{EOPL}$ consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubacek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse ... more >>>

Ron D. Rothblum, Prashant Nalini Vasudevan

Collision-resistant hash functions (CRH) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of CRH called t-way multi-collision-resistant hash functions (t-MCRH). These are families of functions for which it is computationally hard to find a t-way collision, even though such collisions are abundant (and even ... more >>>

Artur Ignatiev, Ivan Mihajlin, Alexander Smal

In this paper, we prove a super-cubic lower bound on the size of a communication protocol for generalized Karchmer-Wigderson game for some explicit function $f: \{0,1\}^n\to \{0,1\}^{\log n}$. Lower bounds for original Karchmer-Wigderson games correspond to De Morgan formula lower bounds, thus the best known size lower bound is cubic. ... more >>>

Mika Göös, Stefan Kiefer, Weiqiang Yuan

We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results.

$\textbf{Complement:}$ There is a language $L$ recognised by an $n$-state UFA such that the complement language $\overline{L}$ requires NFAs with $n^{\tilde{\Omega}(\log n)}$ states. This improves on ... more >>>

Joshua Cook, Dana Moshkovitz

We prove for some constant $a > 1$, for all $k \leq a$,

$$\mathbf{MATIME}[n^{k + o(1)}] / 1 \not \subset \mathbf{SIZE}[O(n^{k})],$$

for some specific $o(1)$ function. This improves on the Santhanam lower bound, which says there exists constant $c$ such that for all $k > 1$:

$$\mathbf{MATIME}[n^{c k}] / 1 ...
more >>>

Nader Bshouty, Oded Goldreich

In this note we show that all sets that are neither finite nor too dense are non-trivial to test in the sense that, for every $\epsilon>0$, distinguishing between strings in the set and strings that are $\epsilon$-far from the set requires $\Omega(1/\epsilon)$ queries.

Specifically, we show that if, for ...
more >>>

Anup Rao, Oscar Sprumont

We study the error resilience of transitive linear codes over $F_2$. We give tight bounds on the weight distribution of every such code $C$, and we show how these bounds can be used to infer bounds on the error rates that $C$ can tolerate on the binary symmetric channel. Using ... more >>>

Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen

The continuous learning with errors (CLWE) problem was recently introduced by Bruna

et al. (STOC 2021). They showed that its hardness implies infeasibility of learning Gaussian

mixture models, while its tractability implies efficient Discrete Gaussian Sampling and thus

asymptotic improvements in worst-case lattice algorithms. No reduction between CLWE and

LWE ...
more >>>

Marshall Ball, Dana Dachman-Soled, Julian Loss

We present the first truly explicit constructions of \emph{non-malleable codes} against tampering by bounded polynomial size circuits. These objects imply unproven circuit lower bounds and our construction is secure provided E requires exponential size nondeterministic circuits, an assumption from the derandomization literature.

Prior works on NMC ...
more >>>

C. Ramya, Anamay Tengse

Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand the landscape of algebraic complexity classes surrounding ROABPs, we study classes of ROABPs based on the algebraic structure of these coefficient matrices. We study connections between polynomials ... more >>>

Gil Cohen, Dean Doron, Ori Sberlo

We give a deterministic space-efficient algorithm for approximating powers of stochastic matrices. On input a $w \times w$ stochastic matrix $A$, our algorithm approximates $A^{n}$ in space $\widetilde{O}(\log n + \sqrt{\log n}\cdot \log w)$ to within high accuracy. This improves upon the seminal work by Saks and Zhou (FOCS'95), that ... more >>>

Halley Goldberg, Valentine Kabanets

We give a simplified proof of Hirahara's STOC'21 result showing that $DistPH \subseteq AvgP$ would imply $PH \subseteq DTIME[2^{O(n/\log n)}]$. The argument relies on a proof of the new result: Symmetry of Information for time-bounded Kolmogorov complexity under the assumption that $NP$ is easy on average, which is interesting in ... more >>>

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi

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$. For over 30 years, it was known that any (monotone) collection of authorized sets can be ... more >>>

Anup Rao

A \emph{sunflower} is a collection of sets whose pairwise intersections are identical. In this article, we shall go sunflower-picking. We find sunflowers in several seemingly unrelated fields, before turning to discuss recent progress on the famous sunflower conjecture of Erd\H{o}s and Rado, made by Alweiss, Lovett, Wu and Zhang.

more >>>Silas Richelson, Sourya Roy

Random walks in expander graphs and their various derandomizations (e.g., replacement/zigzag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used s-wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma’s original analysis was entirely linear algebraic, and subsequent developments have ... more >>>

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere

We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-$d$ Sherali-Adams refutation of an unsatisfiable CNF formula $C$ if and only if there is an $\varepsilon > 0$ and a degree-$d$ conical junta $J$ such that $viol_C(x) - \varepsilon = J$, where $viol_C(x)$ counts ... more >>>

Sravanthi Chede, Anil Shukla

Merge Resolution (MRes [Beyersdorff et al. J. Autom. Reason.'2021]) is a recently introduced proof system for false QBFs. Unlike other known QBF proof systems, it builds winning strategies for the universal player within the proofs. Every line of this proof system consists of existential clauses along with countermodels. MRes stores ... more >>>

Yogesh Dahiya, Meena Mahajan

In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and size corresponds to storage space. The depth measure is the most well-studied one, and is known to be polynomially related to several non-computational complexity measures of functions such as certificate complexity. The size measure ... more >>>