All reports in year 2023:

__
TR23-001
| 5th January 2023
__

Prerona Chatterjee, Pavel Hrubes#### New Lower Bounds against Homogeneous Non-Commutative Circuits

__
TR23-002
| 5th January 2023
__

Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran#### Diagonalization Games

Revisions: 2

__
TR23-003
| 11th January 2023
__

Shachar Lovett, Jiapeng Zhang#### Streaming Lower Bounds and Asymmetric Set-Disjointness

__
TR23-004
| 13th January 2023
__

Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang#### On linear-algebraic notions of expansion

__
TR23-005
| 13th January 2023
__

Paul Beame, Niels Kornerup#### Cumulative Memory Lower Bounds for Randomized and Quantum Computation

Revisions: 2

__
TR23-006
| 20th January 2023
__

Nader Bshouty#### Superpolynomial Lower Bounds for Learning Monotone Classes

Revisions: 1

__
TR23-007
| 3rd February 2023
__

Jan Krajicek#### Extended Nullstellensatz proof systems

__
TR23-008
| 2nd February 2023
__

Ond?ej Ježil#### Limits of structures and Total NP Search Problems

__
TR23-009
| 14th February 2023
__

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas#### Towards Optimal Depth-Reductions for Algebraic Formulas

__
TR23-010
| 13th February 2023
__

Per Austrin, Kilian Risse#### Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem

__
TR23-011
| 13th February 2023
__

Mikhail Dektiarev, Nikolay Vereshchagin#### Half-duplex communication complexity with adversary? can be less than the classical communication complexity

__
TR23-012
| 16th February 2023
__

Yogesh Dahiya, Vignesh K, Meena Mahajan, Karteek Sreenivasaiah#### Linear threshold functions in decision lists, decision trees, and depth-2 circuits

__
TR23-013
| 7th February 2023
__

Noam Mazor#### A Lower Bound on the Share Size in Evolving Secret Sharing

Revisions: 1

__
TR23-014
| 16th February 2023
__

Tameem Choudhury, Karteek Sreenivasaiah#### Depth-3 Circuit Lower Bounds for k-OV

Revisions: 3

__
TR23-015
| 20th February 2023
__

Scott Aaronson, Harry Buhrman, William Kretschmer#### A Qubit, a Coin, and an Advice String Walk Into a Relational Problem

Revisions: 1

__
TR23-016
| 22nd February 2023
__

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals#### Proving Unsatisfiability with Hitting Formulas

__
TR23-017
| 21st February 2023
__

Deepanshu Kush, Shubhangi Saraf#### Near-Optimal Set-Multilinear Formula Lower Bounds

__
TR23-018
| 1st March 2023
__

Qipeng Liu, Ran Raz, Wei Zhan#### Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory

__
TR23-019
| 2nd March 2023
__

Pooya Hatami, William Hoza#### Theory of Unconditional Pseudorandom Generators

Revisions: 2

__
TR23-020
| 3rd March 2023
__

Scott Aaronson, Shih-Han Hung#### Certified Randomness from Quantum Supremacy

__
TR23-021
| 9th March 2023
__

Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi#### Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms

Revisions: 2

__
TR23-022
| 11th March 2023
__

Jiatu Li, Igor Carboni Oliveira#### Unprovability of strong complexity lower bounds in bounded arithmetic

__
TR23-023
| 13th March 2023
__

Xin Li#### Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More

Revisions: 1

__
TR23-024
| 9th March 2023
__

Mark Bun, Nadezhda Voronova#### Approximate degree lower bounds for oracle identification problems

Revisions: 1

__
TR23-025
| 10th March 2023
__

Vikraman Arvind, Pushkar Joglekar#### Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization

__
TR23-026
| 15th March 2023
__

Shuichi Hirahara, Nobutaka Shimizu#### Hardness Self-Amplification: Simplified, Optimized, and Unified

__
TR23-027
| 8th March 2023
__

Joseph Zalewski#### Some Lower Bounds Related to the Missing String Problem

__
TR23-028
| 15th March 2023
__

Rahul Santhanam#### An Algorithmic Approach to Uniform Lower Bounds

__
TR23-029
| 18th March 2023
__

Nicollas Sdroievski, Dieter van Melkebeek#### Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols

__
TR23-030
| 21st March 2023
__

Jan Krajicek#### A proof complexity conjecture and the Incompleteness theorem

__
TR23-031
| 23rd March 2023
__

Benny Applebaum, Eliran Kachlon, Arpita Patra#### The Round Complexity of Statistical MPC with Optimal Resiliency

__
TR23-032
| 24th March 2023
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Linear Independence, Alternants and Applications

__
TR23-033
| 24th March 2023
__

Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi#### Fast Numerical Multivariate Multipoint Evaluation

Revisions: 1

__
TR23-034
| 24th March 2023
__

Oded Goldreich#### On teaching the approximation method for circuit lower bounds

Revisions: 1

__
TR23-035
| 22nd March 2023
__

Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira#### A Duality Between One-Way Functions and Average-Case Symmetry of Information

__
TR23-036
| 27th March 2023
__

Dean Doron, Roei Tell#### Derandomization with Minimal Memory Footprint

__
TR23-037
| 28th March 2023
__

Shuichi Hirahara#### Capturing One-Way Functions via NP-Hardness of Meta-Complexity

__
TR23-038
| 28th March 2023
__

Rahul Ilango, Jiatu Li, Ryan Williams#### Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

__
TR23-039
| 28th March 2023
__

Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan#### Query Complexity of Search Problems

Revisions: 1

__
TR23-040
| 28th March 2023
__

Edward Pyne, Ran Raz, Wei Zhan#### Certified Hardness vs. Randomness for Log-Space

__
TR23-041
| 1st April 2023
__

Lila Fontes, Sophie Laplante, Mathieu Lauriere, Alexandre Nolin#### The communication complexity of functions with large outputs

__
TR23-042
| 3rd April 2023
__

Johan Håstad#### On small-depth Frege proofs for PHP

__
TR23-043
| 9th April 2023
__

Yotam Dikstein, Irit Dinur#### Coboundary and cosystolic expansion without dependence on dimension or degree

__
TR23-044
| 28th March 2023
__

Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar#### Separations between Combinatorial Measures for Transitive Functions

__
TR23-045
| 13th April 2023
__

Vinayak Kumar#### Tight Correlation Bounds for Circuits Between AC0 and TC0

Revisions: 1

__
TR23-046
| 13th April 2023
__

Yizhi Huang, Rahul Ilango, Hanlin Ren#### NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

__
TR23-047
| 2nd April 2023
__

Hunter Monroe#### Ruling Out Short Proofs of Unprovable Sentences is Hard

__
TR23-048
| 4th April 2023
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids

__
TR23-049
| 17th April 2023
__

Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov#### Top-Down Lower Bounds for Depth-Four Circuits

Revisions: 1

__
TR23-050
| 18th April 2023
__

Manasseh Ahmed, Tsun-Ming Cheung, Hamed Hatami, Kusha Sareen#### Communication complexity of half-plane membership

Revisions: 1

__
TR23-051
| 18th April 2023
__

Benjamin Böhm, Olaf Beyersdorff#### QCDCL vs QBF Resolution: Further Insights

__
TR23-052
| 19th April 2023
__

Noah Fleming, Vijay Ganesh, Antonina Kolokolova, Chunxiao Li, Marc Vinyals#### Limits of CDCL Learning via Merge Resolution

__
TR23-053
| 19th April 2023
__

Leroy Chew#### Proof Simulation via Round-based Strategy Extraction for QBF

__
TR23-054
| 20th April 2023
__

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

__
TR23-055
| 20th April 2023
__

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

Revisions: 1

__
TR23-056
| 26th April 2023
__

Geoffrey Mon, Dana Moshkovitz, Justin Oh#### Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate

__
TR23-057
| 27th April 2023
__

Iddo Tzameret, Luming Zhang#### Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness

__
TR23-058
| 23rd April 2023
__

Xin Li, Yan Zhong#### Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs

__
TR23-060
| 17th April 2023
__

Sagnik Saha, Nikolaj Schwartzbach, Prashant Nalini Vasudevan#### The Planted $k$-SUM Problem: Algorithms, Lower Bounds, Hardness Amplification, and Cryptography

Revisions: 1

__
TR23-061
| 2nd May 2023
__

Abhimanyu Choudhury, Meena Mahajan#### Dependency schemes in CDCL-based QBF solving: a proof-theoretic study

__
TR23-062
| 2nd May 2023
__

Benny Applebaum, Eliran Kachlon#### Conflict Checkable and Decodable Codes and Their Applications

__
TR23-063
| 2nd May 2023
__

Jacobo Toran, Florian Wörz#### Cutting Planes Width and the Complexity of Graph Isomorphism Refutations

__
TR23-064
| 3rd May 2023
__

Oded Goldreich#### On the Lower Bound on the Length of Relaxed Locally Decodable Codes

__
TR23-065
| 4th May 2023
__

Louis Golowich#### From Grassmannian to Simplicial High-Dimensional Expanders

Revisions: 1

__
TR23-066
| 4th May 2023
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Protecting Single-Hop Radio Networks from Message Drops

__
TR23-067
| 7th May 2023
__

Guy Goldberg#### Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error

Revisions: 2

__
TR23-068
| 10th May 2023
__

Ben Davis, Robert Robere#### Colourful TFNP and Propositional Proofs

Revisions: 1

__
TR23-069
| 11th May 2023
__

Bruno Pasqualotto Cavalar, Igor Carboni Oliveira#### Constant-depth circuits vs. monotone circuits

__
TR23-070
| 9th May 2023
__

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren#### Bounded Relativization

__
TR23-071
| 8th May 2023
__

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov#### Sampling and Certifying Symmetric Functions

__
TR23-072
| 18th May 2023
__

Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren#### Range Avoidance, Remote Point, and Hard Partial Truth Tables via Satisfying-Pairs Algorithms

__
TR23-073
| 15th May 2023
__

Xi Chen, Yuhao Li, Mihalis Yannakakis#### Reducing Tarski to Unique Tarski (in the Black-box Model)

__
TR23-074
| 14th May 2023
__

Abhibhav Garg, Rafael Mendes de Oliveira, Shir Peleg, Akash Sengupta#### Radical Sylvester-Gallai Theorem for Tuples of Quadratics

__
TR23-075
| 17th May 2023
__

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj#### Border Complexity of Symbolic Determinant under Rank One Restriction

__
TR23-076
| 24th May 2023
__

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam#### Polynomial-Time Pseudodeterministic Construction of Primes

__
TR23-077
| 25th May 2023
__

Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, Prashant Nalini Vasudevan#### Batch Proofs are Statistically Hiding

Revisions: 4

__
TR23-078
| 30th May 2023
__

Or Meir#### Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition

Revisions: 3

__
TR23-079
| 31st May 2023
__

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich#### Mutual Empowerment between Circuit Obfuscation and Circuit Minimization

__
TR23-080
| 1st June 2023
__

Halley Goldberg, Valentine Kabanets#### Improved Learning from Kolmogorov Complexity

__
TR23-081
| 1st June 2023
__

Noga Amit, Guy Rothblum#### Constant-Round Arguments from One-Way Functions

Revisions: 1

__
TR23-082
| 1st June 2023
__

Ryan Williams#### Self-Improvement for Circuit-Analysis Problems

Revisions: 1

__
TR23-083
| 2nd June 2023
__

Srinivasan A, Uma Girish#### Trade-offs between Entanglement and Communication

__
TR23-084
| 31st May 2023
__

Itai Dinur#### Time-Space Lower Bounds for Bounded-Error Computation in the Random-Query Model

Revisions: 1

__
TR23-085
| 4th June 2023
__

Ari Karchmer#### Average-Case PAC-Learning from Nisan's Natural Proofs

Revisions: 2

__
TR23-086
| 8th June 2023
__

Dmitry Sokolov#### Random $(\log n)$-CNF are Hard for Cutting Planes (Again)

__
TR23-087
| 9th June 2023
__

Benny Applebaum, Oded Nir, Benny Pinkas#### How to Recover a Secret with $O(n)$ Additions

Revisions: 1

__
TR23-088
| 1st June 2023
__

Parker Newton, Silas Richelson, Chase Wilson#### A High Dimensional Goldreich-Levin Theorem

__
TR23-089
| 15th June 2023
__

Louis Golowich#### New Explicit Constant-Degree Lossless Expanders

Revisions: 1

__
TR23-090
| 15th June 2023
__

Itay Cohen, Roy Roth, Amnon Ta-Shma#### HDX Condensers

__
TR23-091
| 18th June 2023
__

Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan#### Succinct Computational Secret Sharing

__
TR23-092
| 28th June 2023
__

Swastik Kopparty, Vishvajeet N#### Extracting Mergers and Projections of Partitions

__
TR23-093
| 29th June 2023
__

Vinayak Kumar, Geoffrey Mon#### Relaxed Local Correctability from Local Testing

Revisions: 1

__
TR23-094
| 29th June 2023
__

Lijie Chen, Roei Tell#### New ways of studying the BPP = P conjecture

__
TR23-095
| 21st June 2023
__

David Heath, Vladimir Kolesnikov, Rafail Ostrovsky#### Tri-State Circuits: A Circuit Model that Captures RAM

__
TR23-096
| 28th June 2023
__

Huacheng Yu, Wei Zhan#### Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions

__
TR23-097
| 2nd July 2023
__

Joshua Cook, Ron D. Rothblum#### Efficient Interactive Proofs for Non-Deterministic Bounded Space

Revisions: 1

__
TR23-098
| 5th July 2023
__

Andrej Bogdanov, Pravesh Kothari, Alon Rosen#### Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

__
TR23-099
| 8th July 2023
__

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh#### On the Composition of Randomized Query Complexity and Approximate Degree

Revisions: 1

__
TR23-100
| 6th July 2023
__

Shuichi Hirahara, Mikito Nanashima#### Learning in Pessiland via Inductive Inference

__
TR23-101
| 5th July 2023
__

Renato Ferreira Pinto Jr.#### Directed Poincaré Inequalities and $L^1$ Monotonicity Testing of Lipschitz Functions

__
TR23-102
| 13th July 2023
__

Chin Ho Lee, Edward Pyne, Salil Vadhan#### On the Power of Regular and Permutation Branching Programs

__
TR23-103
| 12th July 2023
__

Yanyi Liu, Rafael Pass#### On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity

Revisions: 1

__
TR23-104
| 14th July 2023
__

Meghal Gupta, Rachel Zhang#### A Noise Resilient Transformation for Streaming Algorithms

__
TR23-105
| 13th July 2023
__

Lijie Chen, Roei Tell, Ryan Williams#### Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization

__
TR23-106
| 17th July 2023
__

Mika Göös, Ziyi Guan, Tiberiu Mosnoi#### Depth-3 Circuits for Inner Product

__
TR23-107
| 20th July 2023
__

Uma Girish, Ran Raz, Wei Zhan#### Quantum Logspace Computations are Verifiable

__
TR23-108
| 21st July 2023
__

Andrej Bogdanov, Tsun-Ming Cheung, Krishnamoorthy Dinesh, John C.S. Lui#### Classical simulation of one-query quantum distinguishers

__
TR23-109
| 21st July 2023
__

Pranav Bisht, Nikhil Gupta, Ilya Volkovich#### Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae

__
TR23-110
| 25th July 2023
__

Gil Cohen, Tal Yankovitz#### Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries

__
TR23-111
| 29th July 2023
__

Vaibhav Krishan#### $\mathit{MidBit}^+$, Torus Polynomials and Non-classical Polynomials: Equivalences for $\mathit{ACC}$ Lower Bounds

__
TR23-112
| 30th July 2023
__

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

__
TR23-113
| 8th August 2023
__

Justin Holmgren, Ron Rothblum#### Linear-Size Boolean Circuits for Multiselection

__
TR23-114
| 8th August 2023
__

Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu#### Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting

__
TR23-115
| 8th August 2023
__

Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk#### Determinants vs. Algebraic Branching Programs

Revisions: 1

__
TR23-116
| 12th August 2023
__

Amey Bhangale, Subhash Khot, Dor Minzer#### Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$

__
TR23-117
| 9th August 2023
__

François Le Gall, Yupan Liu, Qisheng Wang#### Space-bounded quantum state testing via space-efficient quantum singular value transformation

__
TR23-118
| 17th August 2023
__

Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum#### Distribution-Free Proofs of Proximity

Revisions: 2

__
TR23-119
| 18th August 2023
__

Yotam Dikstein, Irit Dinur#### Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers

Revisions: 1

__
TR23-120
| 18th August 2023
__

Mitali Bafna, Dor Minzer#### Characterizing Direct Product Testing via Coboundary Expansion

__
TR23-121
| 19th August 2023
__

Theodoros Papamakarios#### Depth d Frege systems are not automatable unless P=NP

Revisions: 1

__
TR23-122
| 9th August 2023
__

Vikraman Arvind, Abhranil Chatterjee#### On Lifting Lower Bounds for Noncommutative Circuits using Automata

__
TR23-123
| 21st August 2023
__

Noam Mazor#### Key-Agreement with Perfect Completeness from Random Oracles

__
TR23-124
| 24th August 2023
__

Zander Kelley, Shachar Lovett, Raghu Meka#### Explicit separations between randomized and deterministic Number-on-Forehead communication

Revisions: 1

__
TR23-125
| 25th August 2023
__

Omar Alrabiah, Venkatesan Guruswami, Ray Li#### Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields

__
TR23-126
| 25th August 2023
__

Omar Alrabiah, Venkatesan Guruswami, Ray Li#### AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets

__
TR23-127
| 30th August 2023
__

Irit Dinur, Siqi Liu, Rachel Zhang#### New Codes on High Dimensional Expanders

__
TR23-128
| 30th August 2023
__

Xue Chen, Kuan Cheng, Xin Li, Songtao Mao#### Random Shortening of Linear Codes and Application

__
TR23-129
| 21st August 2023
__

Sravanthi Chede, Leroy Chew, Balesh Kumar, Anil Shukla#### Understanding Nullstellensatz for QBFs

__
TR23-130
| 8th September 2023
__

Eshan Chattopadhyay, Jyun-Jie Liao#### Recursive Error Reduction for Regular Branching Programs

Revisions: 1

__
TR23-131
| 8th September 2023
__

Meghal Gupta, Rachel Zhang#### On Interactive Coding Schemes with Adaptive Termination

__
TR23-132
| 12th September 2023
__

Yogesh Dahiya, Meena Mahajan, Sasank Mouli#### New lower bounds for Polynomial Calculus over non-Boolean bases

Revisions: 1

__
TR23-133
| 13th September 2023
__

David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer#### Product mixing in compact Lie groups

Revisions: 2

__
TR23-134
| 14th September 2023
__

Oded Goldreich#### On the complexity of enumerating ordered sets

__
TR23-135
| 14th September 2023
__

Prerona Chatterjee, Anamay Tengse#### On Annihilators of Explicit Polynomial Maps

__
TR23-136
| 14th September 2023
__

Benny Applebaum, Oded Nir#### Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography

__
TR23-137
| 10th September 2023
__

Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang#### Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments

__
TR23-138
| 12th September 2023
__

Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman#### An improved protocol for ExactlyN with more than 3 players

__
TR23-139
| 18th September 2023
__

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi#### Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits

__
TR23-140
| 20th September 2023
__

Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani#### Extractors for Polynomial Sources over $\mathbb{F}_2$

Revisions: 1

__
TR23-141
| 19th September 2023
__

Nader Bshouty, Gergely Harcos#### A Tight Lower Bound of $\Omega(\log n)$ for the Estimation of the Number of Defective Items

__
TR23-142
| 21st September 2023
__

Tom Gur, Wilfred Salmon, Sergii Strelchuk#### Provable Advantage in Quantum PAC Learning

__
TR23-143
| 22nd September 2023
__

Noam Mazor, Rafael Pass#### Counting Unpredictable Bits: A Simple PRG from One-way Functions

Revisions: 1

__
TR23-144
| 22nd September 2023
__

Lijie Chen, Shuichi Hirahara, Hanlin Ren#### Symmetric Exponential Time Requires Near-Maximum Circuit Size

__
TR23-145
| 20th September 2023
__

Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran#### Total Variation Distance Estimation Is as Easy as Probabilistic Inference

__
TR23-146
| 27th September 2023
__

Oded Goldreich, Laliv Tauber#### On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model

Revisions: 1

__
TR23-147
| 27th September 2023
__

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay#### Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time

Revisions: 5
,
Comments: 1

__
TR23-148
| 3rd October 2023
__

Srinivasan Arunachalam, Uma Girish, Noam Lifshitz#### One Clean Qubit Suffices for Quantum Communication Advantage

__
TR23-149
| 5th October 2023
__

Ronen Shaltiel, Jad Silbak#### Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions

Revisions: 1

__
TR23-150
| 5th October 2023
__

Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse#### Monotone Classes Beyond VNP

__
TR23-151
| 11th October 2023
__

Hao Wu#### An Improved Composition Theorem of a Universal Relation and Most Functions via Effective Restriction

Revisions: 1

__
TR23-152
| 14th October 2023
__

Yanyi Liu, Rafael Pass#### One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions

__
TR23-153
| 19th October 2023
__

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii#### Towards Simpler Sorting Networks and Monotone Circuits for Majority

__
TR23-154
| 12th October 2023
__

Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer#### On the Rational Degree of Boolean Functions and Applications

__
TR23-155
| 25th October 2023
__

Venkatesan Guruswami, Xuandi Ren, Sai Sandeep#### Baby PIH: Parameterized Inapproximability of Min CSP

Revisions: 1

__
TR23-156
| 26th October 2023
__

Zeyong Li#### Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform

Revisions: 1

__
TR23-157
| 31st October 2023
__

Vladimir Podolskii, Dmitrii Sluch#### One-Way Communication Complexity of Partial XOR Functions

__
TR23-158
| 1st November 2023
__

Oded Goldreich#### On coarse and fine approximate counting of $t$-cliques

__
TR23-159
| 31st October 2023
__

Guangxu Yang, Jiapeng Zhang#### Communication Lower Bounds for Collision Problems via Density Increment Arguments

__
TR23-160
| 29th October 2023
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf#### Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes

Revisions: 1

__
TR23-161
| 1st November 2023
__

Tal Herman, Guy Rothblum#### Doubly-Efficient Interactive Proofs for Distribution Properties

Revisions: 1

__
TR23-162
| 1st November 2023
__

Pravesh Kothari, Peter Manohar#### An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

__
TR23-163
| 30th October 2023
__

Nikhil Balaji, Samir Datta#### USSR is in P/poly

__
TR23-164
| 5th November 2023
__

Shuo Wang, Guangxu Yang, Jiapeng Zhang#### Communication Complexity of Set-Intersection Problems and Its Applications

__
TR23-165
| 5th November 2023
__

Rahul Ilango#### SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle

__
TR23-166
| 5th November 2023
__

Dmytro Gavinsky#### Patterned non-determinism in communication complexity

__
TR23-167
| 13th November 2023
__

Marshall Ball, Ronen Shaltiel, Jad Silbak#### Non-malleable codes with optimal rate for poly-size circuits

__
TR23-168
| 13th November 2023
__

Edward Pyne#### Time-Space Tradeoffs for BPL via Catalytic Computation

Revisions: 2

__
TR23-169
| 14th November 2023
__

Marshall Ball, Dana Dachman-Soled, Eli Goldin, Saachi Mutreja#### Extracting Randomness from Samplable Distributions, Revisited

__
TR23-170
| 13th November 2023
__

Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha#### Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning

__
TR23-171
| 15th November 2023
__

Shuichi Hirahara, Rahul Ilango, Ryan Williams#### Beating Brute Force for Compression Problems

__
TR23-172
| 14th November 2023
__

Meghal Gupta#### Constant Query Local Decoding Against Deletions Is Impossible

__
TR23-173
| 15th November 2023
__

Louis Golowich, Venkatesan Guruswami#### Quantum Locally Recoverable Codes

__
TR23-174
| 15th November 2023
__

James Cook, Ian Mertz#### Tree Evaluation is in Space O(log n · log log n)

__
TR23-175
| 15th November 2023
__

Noam Mazor, Rafael Pass#### The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False

__
TR23-176
| 15th November 2023
__

William Hoza#### A Technique for Hardness Amplification Against $\mathrm{AC}^0$

Revisions: 2

__
TR23-177
| 18th November 2023
__

Kiran Kedlaya, Swastik Kopparty#### On the degree of polynomials computing square roots mod p

Revisions: 1

__
TR23-178
| 16th November 2023
__

Louis Golowich, Tali Kaufman#### NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes

__
TR23-179
| 18th November 2023
__

Ian Mertz#### Reusing Space: Techniques and Open Problems

__
TR23-180
| 17th November 2023
__

Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka#### New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

__
TR23-181
| 20th November 2023
__

Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov#### Hardness Condensation by Restriction

Revisions: 1

__
TR23-182
| 21st November 2023
__

Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan#### An Improved Line-Point Low-Degree Test

__
TR23-183
| 24th November 2023
__

Gil Cohen, Itay Cohen, Gal Maor, Yuval Peled#### Derandomized Squaring: An Analytical Insight into Its True Behavior

__
TR23-184
| 22nd November 2023
__

Gabriel Bathie, Ryan Williams#### Towards Stronger Depth Lower Bounds

__
TR23-185
| 27th November 2023
__

Rohan Goyal, Prahladh Harsha, Mrinal Kumar, A. Shankar#### Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes

Revisions: 3

__
TR23-186
| 28th November 2023
__

Ce Jin, Ryan Williams, Nathaniel Young#### A VLSI Circuit Model Accounting For Wire Delay

__
TR23-187
| 27th November 2023
__

Klim Efremenko, Michal Garlik, Dmitry Itsykson#### Lower bounds for regular resolution over parities

__
TR23-188
| 28th November 2023
__

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu#### Parameterized Inapproximability Hypothesis under ETH

__
TR23-189
| 28th November 2023
__

John Kallaugher, Ojas Parekh, Nadezhda Voronova#### Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model

__
TR23-190
| 15th November 2023
__

Leonid Gurvits, Nathan Klein, Jonathan Leake#### From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP

Revisions: 1

__
TR23-191
| 2nd December 2023
__

Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### On the Power of Homogeneous Algebraic Formulas

__
TR23-192
| 28th November 2023
__

Noam Mazor, Rafael Pass#### A Note On the Universality of Black-box MKtP Solvers

Revisions: 1

__
TR23-193
| 3rd December 2023
__

Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz#### On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity

__
TR23-194
| 5th December 2023
__

Siddharth Iyer, Anup Rao#### XOR Lemmas for Communication via Marginal Information

__
TR23-195
| 6th December 2023
__

Shai Evra, Shay Gadot, Ohad Klein, Ilan Komargodski#### Verifying Groups in Linear Time

__
TR23-196
| 7th December 2023
__

Huacheng Yu, Wei Zhan#### Sampling, Flowers and Communication

__
TR23-197
| 7th December 2023
__

Sepehr Assadi, Gillat Kol, Zhijun Zhang#### Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams

__
TR23-198
| 8th December 2023
__

Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer#### Parallel Repetition of k-Player Projection Games

__
TR23-199
| 9th December 2023
__

Ján Pich, Rahul Santhanam#### Towards P $\neq$ NP from Extended Frege Lower Bounds

__
TR23-200
| 6th December 2023
__

Joseph Shunia#### An Efficient Deterministic Primality Test

Revisions: 1
,
Comments: 4

__
TR23-201
| 16th October 2023
__

Alexander Shekhovtsov, Georgii Zakharov#### Enumerating Complexity Revisited

__
TR23-202
| 15th December 2023
__

C Ramya, Pratik Shastri#### Lower Bounds for Planar Arithmetic Circuits

__
TR23-203
| 15th December 2023
__

Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni#### Refuting approaches to the log-rank conjecture for XOR functions

__
TR23-204
| 17th November 2023
__

John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen#### An efficient quantum parallel repetition theorem and applications

Revisions: 1

__
TR23-205
| 21st December 2023
__

Marshall Ball, Dana Dachman-Soled#### (Inefficient Prover) ZAPs from Hard-to-Invert Functions

__
TR23-206
| 9th December 2023
__

Yilei Chen, Jiatu Li#### Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography

Revisions: 1

__
TR23-207
| 13th December 2023
__

Omri Ben-Eliezer, Tomer Grossman, Moni Naor#### Does Prior Knowledge Help Detect Collisions?

__
TR23-208
| 21st December 2023
__

Dean Doron, Edward Pyne, Roei Tell#### Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL

__
TR23-209
| 23rd December 2023
__

Yotam Dikstein, Irit Dinur#### Swap cosystolic expansion

Revisions: 1

__
TR23-210
| 22nd December 2023
__

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach#### On the Existence of Seedless Condensers: Exploring the Terrain

Revisions: 1

__
TR23-211
| 23rd December 2023
__

Rafael Pass, Oren Renard#### Characterizing the Power of (Persistent) Randomness in Log-space

__
TR23-212
| 26th December 2023
__

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka#### Exponential Lower Bounds Against Sums of ROABPs

Revisions: 2

__
TR23-213
| 31st December 2023
__

Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai#### Hard Languages in $\text{NP}\cap\text{coNP}$ and NIZK Proofs from Unstructured Hardness

__
TR23-214
| 31st December 2023
__

Oded Goldreich, Laliv Tauber#### On Testing Group Properties

Revisions: 1

Prerona Chatterjee, Pavel Hrubes

We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree $d$ which requires homogeneous non-commutative circuit of size $\Omega(d/\log d)$. For an $n$-variate polynomial with $n>1$, the result can be improved to $\Omega(nd)$, if $d\leq n$, or $\Omega(nd \frac{\log ... more >>>

Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran

We study several variants of a combinatorial game which is based on Cantor's diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor's arguments about the infinite, and even ... more >>>

Shachar Lovett, Jiapeng Zhang

Frequency estimation in data streams is one of the classical problems in streaming algorithms. Following much research, there are now almost matching upper and lower bounds for the trade-off needed between the number of samples and the space complexity of the algorithm, when the data streams are adversarial. However, in ... more >>>

Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang

A fundamental fact about bounded-degree graph expanders is that three notions of expansion---vertex expansion, edge expansion, and spectral expansion---are all equivalent. In this paper, we study to what extent such a statement is true for linear-algebraic notions of expansion.

There are two well-studied notions of linear-algebraic expansion, namely dimension expansion ... more >>>

Paul Beame, Niels Kornerup

Cumulative memory---the sum of space used over the steps of a computation---is a fine-grained measure of time-space complexity that is a more accurate measure of cost for algorithms with infrequent spikes in memory usage in the context of technologies such as cloud computing that allow dynamic allocation and de-allocation of ... more >>>

Nader Bshouty

Koch, Strassle, and Tan [SODA 2023], show that, under the randomized exponential time hypothesis, there is no distribution-free PAC-learning algorithm that runs in time $n^{\tilde O(\log\log s)}$ for the classes of $n$-variable size-$s$ DNF, size-$s$ Decision Tree, and $\log s$-Junta by DNF (that returns a DNF hypothesis). Assuming a natural ... more >>>

Jan Krajicek

For a finite set $\cal F$ of polynomials over a fixed finite prime field of size $p$ containing all polynomials $x^2 - x$, a Nullstellensatz proof of the unsolvability of the system

$$

f = 0\ ,\ \mbox{ all } f \in {\cal F}

$$

is a linear combination ...
more >>>

Ond?ej Ježil

For a class of finite graphs, we define a limit object relative to some computationally restricted class of functions. The properties of the limit object then reflect how a computationally restricted viewer "sees" a generic instance from the class. The construction uses Krají?ek's forcing with random variables [7]. We prove ... more >>>

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas

Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s) with only a polynomial blow-up in size. In this paper, we consider a fine-grained version of this result ... more >>>

Per Austrin, Kilian Risse

We prove lower bounds for the Minimum Circuit Size Problem (MCSP) in the Sum-of-Squares (SoS) proof system. Our main result is that for every Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$, SoS requires degree $\Omega(s^{1-\epsilon})$ to prove that $f$ does not have circuits of size $s$ (for any $s > \text{poly}(n)$). ... more >>>

Mikhail Dektiarev, Nikolay Vereshchagin

Half-duplex communication complexity with adversary was defined in [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Half-duplex communication protocols generalize classical protocols defined by Andrew Yao in [Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report), STOC 1979]. It has been ... more >>>

Yogesh Dahiya, Vignesh K, Meena Mahajan, Karteek Sreenivasaiah

We show that polynomial-size constant-rank linear decision trees (LDTs) can be converted to polynomial-size depth-2 threshold circuits LTF$\circ$LTF. An intermediate construct is polynomial-size decision lists that query a conjunction of a constant number of linear threshold functions (LTFs); we show that these are equivalent to polynomial-size exact linear decision lists ... more >>>

Noam Mazor

Secret sharing schemes allow sharing a secret between a set of parties in a way that ensures that only authorized subsets of the parties learn the secret. Evolving secret sharing schemes (Komargodski, Naor, and Yogev [TCC ’16]) allow achieving this end in a scenario where the parties arrive in an ... more >>>

Tameem Choudhury, Karteek Sreenivasaiah

The 2-Orthogonal Vectors (2-OV) problem is the following: given two tuples $A$ and $B$ of $n$ vectors each of dimension $d$, decide if there exists a vector $u\in A$, and $v\in B$ such that $u$ and $v$ are orthogonal. This problem, and its generalization $k$-OV defined analogously for $k$ tuples, ... more >>>

Scott Aaronson, Harry Buhrman, William Kretschmer

Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for ... more >>>

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals

Hitting formulas have been studied in many different contexts at least since [Iwama 1989]. A hitting formula is a set of Boolean clauses such that any two of the clauses cannot be simultaneously falsified. [Peitl and Szeider 2022] conjectured that the family of unsatisfiable hitting formulas should contain the hardest ... more >>>

Deepanshu Kush, Shubhangi Saraf

The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential avenue for obtaining lower bounds for general algebraic formulas, via strong enough lower bounds for set-multilinear formulas.

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

Qipeng Liu, Ran Raz, Wei Zhan

In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on $n$ bits requires either $\Omega(n^2)$ bits of classical memory or an exponential number (in~$n$) of random samples. A line of recent works continued that research direction and showed that for ... more >>>

Pooya Hatami, William Hoza

This is a survey of unconditional *pseudorandom generators* (PRGs). A PRG uses a short, truly random seed to generate a long, "pseudorandom" sequence of bits. To be more specific, for each restricted model of computation (e.g., bounded-depth circuits or read-once branching programs), we would like to design a PRG that ... more >>>

Scott Aaronson, Shih-Han Hung

We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the ... more >>>

Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi

Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit $C\colon\{0,1\}^n\to\{0,1\}^m$, $m>n$, the task is to find a $y\in\{0,1\}^m$ outside the range of $C$. For an integer $k\geq 2$, $NC^0_k$-AVOID is a special case of AVOID where each output bit of $C$ depends on at most $k$ ... more >>>

Jiatu Li, Igor Carboni Oliveira

While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Jerabek's theory $\textbf{APC}_1$ (2007) and of higher levels of Buss's hierarchy $\textbf{S}^i_2$ (1986) has been a more elusive task. Even in the more restricted setting of Cook's theory ... more >>>

Xin Li

A long line of work in the past two decades or so established close connections between several different pseudorandom objects and applications, including seeded or seedless non-malleable extractors, two source extractors, (bipartite) Ramsey graphs, privacy amplification protocols with an active adversary, non-malleable codes and many more. These connections essentially show ... more >>>

Mark Bun, Nadezhda Voronova

The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function.

We ... more >>>

Vikraman Arvind, Pushkar Joglekar

Based on a theorem of Bergman we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, we show the following:

(1) In the white-box setting, given an n-variate noncommutative polynomial f in F over a field F (either a ... more >>>

Shuichi Hirahara, Nobutaka Shimizu

Strong (resp. weak) average-case hardness refers to the properties of a computational problem in which a large (resp. small) fraction of instances are hard to solve. We develop a general framework for proving hardness self-amplification, that is, the equivalence between strong and weak average-case hardness. Using this framework, we prove ... more >>>

Joseph Zalewski

We prove that a $O(k \log k)$-probe local algorithm for $k$-Missing String presented by Vyas and Williams is asymptotically optimal among a certain class of algorithms for this problem. The best lower bound we are aware of for the general case is still $\Omega(k)$.

more >>>Rahul Santhanam

We propose a new family of circuit-based sampling tasks, such that non-trivial algorithmic solutions to certain tasks from this family imply frontier uniform lower bounds such as ``NP is not in uniform ACC^0" and ``NP does not have uniform polynomial-size depth-two threshold circuits". Indeed, the most general versions of our ... more >>>

Nicollas Sdroievski, Dieter van Melkebeek

A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive proofs asks whether Arthur-Merlin protocols can be simulated nondeterministically with a small overhead in time (the ... more >>>

Jan Krajicek

Given a sound first-order p-time theory $T$ capable of formalizing syntax of

first-order logic we define a p-time function $g_T$ that stretches all inputs by one

bit and we use its properties to show that $T$ must be incomplete. We leave it as an

open problem whether ...
more >>>

Benny Applebaum, Eliran Kachlon, Arpita Patra

In STOC 1989, Rabin and Ben-Or (RB) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with statistical (information-theoretic) security in the presence of an active (aka Byzantine) rushing adversary that controls up to half of the parties. We ... more >>>

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a \emph{Small Witness for Linear Independence} (SWLI) lemma which states the following.

If the polynomials $f_1,f_2, \ldots, f_k \in \F[X]$ over $X=\{x_1, \ldots, x_n\}$ are $\F$-linearly independent then there exists ...
more >>>

Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi

We design nearly-linear time numerical algorithms for the problem of multivariate multipoint evaluation over the fields of rational, real and complex numbers. We consider both \emph{exact} and \emph{approximate} versions of the algorithm. The input to the algorithms are (1) coefficients of an $m$-variate polynomial $f$ with degree $d$ in each ... more >>>

Oded Goldreich

This text provides a basic presentation of the the approximation method of Razborov (Matematicheskie Zametki, 1987) and its application by Smolensky (19th STOC, 1987) for proving lower bounds on the size of ${\cal AC}^0[p]$-circuits that compute sums mod~$q$ (for primes $q\neq p$).

The textbook presentations of the latter result ...
more >>>

Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira

Symmetry of Information (SoI) is a fundamental property of Kolmogorov complexity that relates the complexity of a pair of strings and their conditional complexities. Understanding if this property holds in the time-bounded setting is a longstanding open problem. In the nineties, Longpré and Mocas (1993) and Longpré and Watanabe (1995) ... more >>>

Dean Doron, Roei Tell

Existing proofs that deduce BPL=L from circuit lower bounds convert randomized algorithms into deterministic algorithms with large constant overhead in space. We study space-bounded derandomization with minimal footprint, and ask what is the minimal possible space overhead for derandomization.

We show that $BPSPACE[S] \subseteq DSPACE[c \cdot S]$ for $c \approx ...
more >>>

Shuichi Hirahara

A one-way function is a function that is easy to compute but hard to invert *on average*. We establish the first characterization of a one-way function by *worst-case* hardness assumptions, by introducing a natural meta-computational problem whose NP-hardness (and the worst-case hardness of NP) characterizes the existence of a one-way ... more >>>

Rahul Ilango, Jiatu Li, Ryan Williams

The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit $C:\{0,1\}^n\to\{0,1\}^m$, where $m>n$. Although at least half of the strings of length $m$ are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS'21) ... more >>>

Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan

We relate various complexity measures like sensitivity, block sensitivity, certificate complexity for multi-output functions to the query complexities of such functions. Using these relations, we improve upon the known relationship between pseudo-deterministic query complexity and deterministic query complexity for total search problems: We show that pseudo-deterministic query complexity is at ... more >>>

Edward Pyne, Ran Raz, Wei Zhan

Let $\mathcal{L}$ be a language that can be decided in linear space and let $\epsilon >0$ be any constant. Let $\mathcal{A}$ be the exponential hardness assumption that for every $n$, membership in $\mathcal{L}$ for inputs of length~$n$ cannot be decided by circuits of size smaller than $2^{\epsilon n}$.

We ...
more >>>

Lila Fontes, Sophie Laplante, Mathieu Lauriere, Alexandre Nolin

We study the two-party communication complexity of functions with large outputs, and show that the communication complexity can greatly vary depending on what output model is considered. We study a variety of output models, ranging from the open model, in which an external observer can compute the outcome, to the ... more >>>

Johan Håstad

We study Frege proofs for the one-to-one graph Pigeon Hole Principle

defined on the $n\times n$ grid where $n$ is odd.

We are interested in the case where each formula

in the proof is a depth $d$ formula in the basis given by

$\land$, $\lor$, and $\neg$. We prove that ...
more >>>

Yotam Dikstein, Irit Dinur

We give new bounds on the cosystolic expansion constants of several families of high dimensional expanders, and the known coboundary expansion constants of order complexes of homogeneous geometric lattices, including the spherical building of $SL_n(F_q)$. The improvement applies to the high dimensional expanders constructed by Lubotzky, Samuels and Vishne, and ... more >>>

Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar

The role of symmetry in Boolean functions $f:\{0,1\}^n \to \{0,1\}$ has been extensively studied in complexity theory.

For example, symmetric functions, that is, functions that are invariant under the action of $S_n$ is an important class of functions in the study of Boolean functions.

A function $f:\{0,1\}^n \to \{0,1\}$ ...
more >>>

Vinayak Kumar

We initiate the study of generalized $AC^0$ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight $\ge k$ (up to negations of the input bits), which we denote $GC^0(k)$. The gate set of this class includes biased LTFs like the $k$-$OR$ ... more >>>

Yizhi Huang, Rahul Ilango, Hanlin Ren

It is a long-standing open problem whether the Minimum Circuit Size Problem ($\mathrm{MCSP}$) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation.

In this work, we prove NP-hardness of approximating meta-complexity with ... more >>>

Hunter Monroe

If no optimal propositional proof system exists, we (and independently Pudlák) prove that ruling out length $t$ proofs of any unprovable sentence is hard. This mapping from unprovable to hard-to-prove sentences powerfully translates facts about noncomputability into complexity theory. For instance, because proving string $x$ is Kolmogorov random ($x{\in}R$) is ... more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Monotonicity testing of Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary $n$, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity $\widetilde{O}(\varepsilon^{-4/3}d^{5/6})$. This complexity is independent of $n$, but ... more >>>

Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

We present a top-down lower-bound method for depth-$4$ boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth-$4$ circuits of size exponential in $n^{1/3}$. Our proof is an application of robust sunflowers and block unpredictability.

more >>>Manasseh Ahmed, Tsun-Ming Cheung, Hamed Hatami, Kusha Sareen

We study the randomized communication complexity of the following problem. Alice receives the integer coordinates of a point in the plane, and Bob receives the integer parameters of a half-plane, and their goal is to determine whether Alice's point belongs to Bob's half-plane.

This communication task corresponds to determining ... more >>>

Benjamin Böhm, Olaf Beyersdorff

We continue the investigation on the relations of QCDCL and QBF resolution systems. In particular, we introduce QCDCL versions that tightly characterise QU-Resolution and (a slight variant of) long-distance Q-Resolution. We show that most QCDCL variants - parameterised by different policies for decisions, unit propagations and reductions -- lead to ... more >>>

Noah Fleming, Vijay Ganesh, Antonina Kolokolova, Chunxiao Li, Marc Vinyals

In their seminal work, Atserias et al. and independently Pipatsrisawat and Darwiche in 2009 showed that CDCL solvers can simulate resolution proofs with polynomial overhead. However, previous work does not address the tightness of the simulation, i.e., the question of how large this overhead needs to be. In this paper, ... more >>>

Leroy Chew

The proof complexity of Quantified Boolean Formulas (QBF) relates to both QBF solving and OBF certification. One method to p-simulate a QBF proof system is by formalising the soundness of its strategy extraction in propositional logic. In this work we illustrate how to use extended QBF Frege to simulate LD-Q(Drrs)-Res, ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

In this paper we study functions on the Boolean hypercube that have the property that after applying certain random restrictions, the restricted function is correlated to a linear function with non-negligible probability. If the given function is correlated with a linear function then this property clearly holds. Furthermore, the property ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

Let $\Sigma$ be an alphabet and $\mu$ be a distribution on $\Sigma^k$ for some $k \geq 2$. Let $\alpha > 0$ be the minimum probability of a tuple in the support of $\mu$ (denoted by $supp(\mu)$). Here, the support of $\mu$ is the set of all tuples in $\Sigma^k$ that ... more >>>

Geoffrey Mon, Dana Moshkovitz, Justin Oh

We present simple constructions of good approximate locally decodable codes (ALDCs) in the presence of a $\delta$-fraction of errors for $\delta<1/2$. In a standard locally decodable code $C \colon \Sigma_1^k \to \Sigma_2^n$, there is a decoder $M$ that on input $i \in [k]$ correctly outputs the $i$-th symbol of a ... more >>>

Iddo Tzameret, Luming Zhang

We develop the theory of cryptographic nondeterministic-secure pseudorandomness beyond the point reached by Rudich's original work (Rudich 1997), and apply it to draw new consequences in average-case complexity and proof complexity. Specifically, we show the following:

?*Demi-bit stretch*: Super-bits and demi-bits are variants of cryptographic pseudorandom generators which are ... more >>>

Xin Li, Yan Zhong

Affine extractors give some of the best-known lower bounds for various computational models, such as AC$^0$ circuits, parity decision trees, and general Boolean circuits. However, they are not known to give strong lower bounds for read-once branching programs (ROBPs). In a recent work, Gryaznov, Pudl\'{a}k, and Talebanfard (CCC' 22) introduced ... more >>>

Sagnik Saha, Nikolaj Schwartzbach, Prashant Nalini Vasudevan

In the average-case $k$-SUM problem, given $r$ integers chosen uniformly at random from $\{0,\ldots,M-1\}$, the objective is to find a set of $k$ numbers that sum to $0$ modulo $M$ (this set is called a ``solution''). In the related $k$-XOR problem, given $k$ uniformly random Boolean vectors of length $\log{M}$, ... more >>>

Abhimanyu Choudhury, Meena Mahajan

We formalize the notion of proof systems obtained by adding normal dependency schemes into the QCDCL proof system underlying algorithms for solving Quantified Boolean Formulas, by exploring the addition of the dependency schemes via two approaches: one as a preprocessing tool, and second in propagation and learnings in the QCDCL ... more >>>

Benny Applebaum, Eliran Kachlon

Let $C$ be an error-correcting code over a large alphabet $q$ of block length $n$, and assume that, a possibly corrupted, codeword $c$ is distributively stored among $n$ servers where the $i$th entry is being held by the $i$th server. Suppose that every pair of servers publicly announce whether the ... more >>>

Jacobo Toran, Florian Wörz

The width complexity measure plays a central role in Resolution and other propositional proof systems like Polynomial Calculus (under the name of degree). The study of width lower bounds is the most extended method for proving size lower bounds, and it is known that for these systems, proofs with small ... more >>>

Oded Goldreich

We revisit the known proof of the lower bound on the length of relaxed locally decodable codes, providing an arguably simpler exposition that yields a slightly better lower bound for the non-adaptive case and a weaker bound in the general case.

Recall that a locally decodable code is an error ... more >>>

Louis Golowich

In this paper, we present a new construction of simplicial complexes of subpolynomial degree with arbitrarily good local spectral expansion. Previously, the only known high-dimensional expanders (HDXs) with arbitrarily good expansion and less than polynomial degree were based on one of two constructions, namely Ramanujan complexes and coset complexes. ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Single-hop radio networks (SHRN) are a well studied abstraction of communication over a wireless channel. In this model, in every round, each of the $n$ participating parties may decide to broadcast a message to all the others, potentially causing collisions. We consider the SHRN model in the presence of stochastic ... more >>>

Guy Goldberg

Relaxed locally decodable codes (RLDCs) are error-correcting codes in which individual bits of the message can be recovered by querying only a few bits from a noisy codeword.

Unlike standard (non-relaxed) decoders, a relaxed one is allowed to output a ``rejection'' symbol, indicating that the decoding failed.

To prevent the ...
more >>>

Ben Davis, Robert Robere

Recent work has shown that many of the standard TFNP classes — such as PLS, PPADS, PPAD, SOPL, and EOPL — have corresponding proof systems in propositional proof complexity, in the sense that a total search problem is in the class if and only if the totality of the problem ... more >>>

Bruno Pasqualotto Cavalar, Igor Carboni Oliveira

We establish new separations between the power of monotone and general (non-monotone) Boolean circuits:

- For every $k \geq 1$, there is a monotone function in ${\rm AC^0}$ (constant-depth poly-size circuits) that requires monotone circuits of depth $\Omega(\log^k n)$. This significantly extends a classical result of Okol'nishnikova (1982) and Ajtai ... more >>>

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called *bounded relativization*. For a complexity class $C$, we say that a statement is *$C$-relativizing* if the statement holds relative ... more >>>

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov

A circuit $\mathcal{C}$ samples a distribution $\mathbf{X}$ with an error $\epsilon$ if the statistical distance between the output of $\mathcal{C}$ on the uniform input and $\mathbf{X}$ is $\epsilon$. We study the hardness of sampling a uniform distribution over the set of $n$-bit strings of Hamming weight $k$ denoted by $\mathbf{U}^n_k$ ... more >>>

Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren

The *range avoidance problem*, denoted as $\mathcal{C}$-$\rm Avoid$, asks to find a non-output of a given $\mathcal{C}$-circuit $C:\{0,1\}^n\to\{0,1\}^\ell$ with stretch $\ell>n$. This problem has recently received much attention in complexity theory for its connections with circuit lower bounds and other explicit construction problems. Inspired by the Algorithmic Method for circuit ... more >>>

Xi Chen, Yuhao Li, Mihalis Yannakakis

We study the problem of finding a Tarski fixed point over the $k$-dimensional grid $[n]^k$. We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique ... more >>>

Abhibhav Garg, Rafael Mendes de Oliveira, Shir Peleg, Akash Sengupta

We prove a higher codimensional radical Sylvester-Gallai type theorem for quadratic polynomials, simultaneously generalizing [Han65, Shp20]. Hansen's theorem is a high-dimensional version of the classical Sylvester-Gallai theorem in which the incidence condition is given by high-dimensional flats instead of lines. We generalize Hansen's theorem to the setting of quadratic forms ... more >>>

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj

VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form $A_0 + \sum_{i=1}^n A_ix_i$ where the size of each $A_i$ is polynomial in the number of variables (equivalently, computable by polynomial-sized algebraic branching programs (ABP)). A major open problem ... more >>>

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam

A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time.

... more >>>Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, Prashant Nalini Vasudevan

Batch proofs are proof systems that convince a verifier that $x_1,\dots, x_t \in L$, for some $NP$ language $L$, with communication that is much shorter than sending the $t$ witnesses. In the case of statistical soundness (where the cheating prover is unbounded but honest prover is efficient), interactive batch proofs ... more >>>

Or Meir

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

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

We study close connections between Indistinguishability Obfuscation ($IO$) and the Minimum Circuit Size Problem ($MCSP$), and argue that algorithms for one of $MCSP$ or $IO$ would empower the other one. Some of our main results are:

\begin{itemize}

\item If there exists a perfect (imperfect) $IO$ that is computationally secure ...
more >>>

Halley Goldberg, Valentine Kabanets

Carmosino, Impagliazzo, Kabanets, and Kolokolova (CCC, 2016) showed that the existence of natural properties in the sense of Razborov and Rudich (JCSS, 1997) implies PAC learning algorithms in the sense of Valiant (Comm. ACM, 1984), for boolean functions in $\P/\poly$, under the uniform distribution and with membership queries. It is ... more >>>

Noga Amit, Guy Rothblum

We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of $\mathbf{P}$, such as depth-bounded computations.

Kilian's celebrated work [STOC 1992] provides such 4-message arguments for $\mathbf{P}$ (actually, for $\mathbf{NP}$) using collision-resistant hash ...
more >>>

Ryan Williams

Many results in fine-grained complexity reveal intriguing consequences from solving various SAT problems even slightly faster than exhaustive search. We prove a ``self-improving'' (or ``bootstrapping'') theorem for Circuit-SAT, $\#$Circuit-SAT, and its fully-quantified version: solving one of these problems faster for ``large'' circuit sizes implies a significant speed-up for ``smaller'' circuit ... more >>>

Srinivasan A, Uma Girish

We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on $n$ bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. ... more >>>

Itai Dinur

The random-query model was introduced by Raz and Zhan at ITCS 2020 as a new model of space-bounded computation. In this model, a branching program of length $T$ and width $2^{S}$ attempts to compute a function $f:\{0,1\}^n \rightarrow \{0,1 \}$. However, instead of receiving direct access to the input bits ... more >>>

Ari Karchmer

Carmosino et al. (2016) demonstrated that natural proofs of circuit lower bounds imply algorithms for learning circuits with membership queries over the uniform distribution. Indeed, they exercised this implication to obtain a quasi-polynomial time learning algorithm for ${AC}^0[p]$ circuits, for any prime $p$, by leveraging the existing natural proofs from ... more >>>

Dmitry Sokolov

The random $\Delta$-CNF model is one of the most important distribution over $\Delta\text{-}\mathrm{SAT}$ instances. It is closely connected to various areas of computer science, statistical physics, and is a benchmark for satisfiability algorithms. Fleming, Pankratov, Pitassi, and Robere and independently Hrubes and Pudlak showed that when $\Delta = \Theta(\log n)$, ... more >>>

Benny Applebaum, Oded Nir, Benny Pinkas

Threshold cryptography is typically based on the idea of secret-sharing a private-key $s\in F$ ``in the exponent'' of some cryptographic group $G$, or more generally, encoding $s$ in some linearly homomorphic domain. In each invocation of the threshold system (e.g., for signing or decrypting) an ``encoding'' of the secret is ... more >>>

Parker Newton, Silas Richelson, Chase Wilson

In this work we prove a high dimensional analogue of the beloved Goldreich-Levin theorem (STOC 1989). We consider the following algorithmic problem: given oracle access to a function $f:\mathbb{Z}_q^m\rightarrow\mathbb{Z}_q^n$ such that ${\rm Prob}_{{\bf x}\sim\mathbb{Z}_q^m}\bigl[f({\bf x})={\bf Ax}\bigr]\geq\varepsilon$ for some ${\bf A}\in\mathbb{Z}_q^{n\times m}$ and $\varepsilon>0$, recover ${\bf A}$ (or a list of ... more >>>

Louis Golowich

We present a new explicit construction of onesided bipartite lossless expanders of constant degree, with arbitrary constant ratio between the sizes of the two vertex sets. Our construction is simpler to state and analyze than the prior construction of Capalbo, Reingold, Vadhan, and Wigderson (2002).

We construct our ... more >>>

Itay Cohen, Roy Roth, Amnon Ta-Shma

More than twenty years ago, Capalbo, Reingold, Vadhan and Wigderson gave the first (and up to date only) explicit construction of a bipartite expander with almost full combinatorial expansion. The construction incorporates zig-zag ideas together with extractor technology, and is rather complicated. We give an alternative construction that builds upon ... more >>>

Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan

A secret-sharing scheme enables a dealer to share a secret $s$ among $n$ parties such that only authorized subsets of parties, specified by a monotone access structure $f:\{0,1\}^n\to\{0,1\}$, can reconstruct $s$ from their shares. Other subsets of parties learn nothing about $s$.

The question of minimizing the (largest) share size ... more >>>

Swastik Kopparty, Vishvajeet N

We study the problem of extracting randomness from somewhere random sources, and related combinatorial phenomena: partition analogues of Shearer's lemma on projections.

A somewhere-random source is a tuple $(X_1, \ldots, X_t)$ of (possibly correlated) $\{0,1\}^n$-valued random variables $X_i$ where for some unknown $i \in [t]$, $X_i$ is guaranteed to be ... more >>>

Vinayak Kumar, Geoffrey Mon

We cement the intuitive connection between relaxed local correctability and local testing by presenting a concrete framework for building a relaxed locally correctable code from any family of linear locally testable codes with sufficiently high rate. When instantiated using the locally testable codes of Dinur et al. (STOC 2022), this ... more >>>

Lijie Chen, Roei Tell

What's new in the world of derandomization? Questions about pseudorandomness and derandomization have been driving progress in complexity theory for many decades. In this survey we will describe new approaches to the $\mathcal{BPP}=\mathcal{P}$ conjecture from recent years, as well as new questions, algorithmic approaches, and ways of thinking. For example: ... more >>>

David Heath, Vladimir Kolesnikov, Rafail Ostrovsky

We introduce tri-state circuits (TSCs). TSCs form a natural model of computation that, to our knowledge, has not been considered by theorists. The model captures a surprising combination of simplicity and power. TSCs are simple in that they allow only three wire values ($0$,$1$, and undefined – $Z$) and three ... more >>>

Huacheng Yu, Wei Zhan

We prove the first polynomial separation between randomized and deterministic time-space tradeoffs of multi-output functions. In particular, we present a total function that on the input of $n$ elements in $[n]$, outputs $O(n)$ elements, such that:

- There exists a randomized oblivious algorithm with space $O(\log n)$, time $O(n\log n)$ ... more >>>

Joshua Cook, Ron D. Rothblum

The celebrated $\mathbf{IP}=\mathbf{PSPACE}$ Theorem gives an efficient interactive proof for any bounded-space algorithm. In this work we study interactive proofs for non-deterministic bounded space computations. While Savitch's Theorem shows that nondeterministic bounded-space algorithms can be simulated by deterministic bounded-space algorithms, this simulation has a quadratic overhead. We give interactive protocols ... more >>>

Andrej Bogdanov, Pravesh Kothari, Alon Rosen

The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics.

We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis ... more >>>

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh

For any Boolean functions $f$ and $g$, the question whether $\text{R}(f\circ g) = \tilde{\Theta}(\text{R}(f) \cdot \text{R}(g))$, is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether $\widetilde{\text{deg}}(f\circ g) = \tilde{\Theta}(\widetilde{\text{deg}}(f)\cdot\widetilde{\text{deg}}(g))$. These questions are two of the most important and ... more >>>

Shuichi Hirahara, Mikito Nanashima

Pessiland is one of Impagliazzo's five possible worlds in which NP is hard on average, yet no one-way function exists. This world is considered the most pessimistic because it offers neither algorithmic nor cryptographic benefits.

In this paper, we develop a unified framework for constructing strong learning algorithms ... more >>>

Renato Ferreira Pinto Jr.

We study the connection between directed isoperimetric inequalities and monotonicity testing. In recent years, this connection has unlocked breakthroughs for testing monotonicity of functions defined on discrete domains. Inspired the rich history of isoperimetric inequalities in continuous settings, we propose that studying the relationship between directed isoperimetry and monotonicity in ... more >>>

Chin Ho Lee, Edward Pyne, Salil Vadhan

We give new upper and lower bounds on the power of several restricted classes of arbitrary-order read-once branching programs (ROBPs) and standard-order ROBPs (SOBPs) that have received significant attention in the literature on pseudorandomness for space-bounded computation.

Regular SOBPs of length $n$ and width $\lfloor w(n+1)/2\rfloor$ can exactly simulate general ... more >>>

Yanyi Liu, Rafael Pass

Whether one-way functions (OWF) exist is arguably the most important

problem in Cryptography, and beyond. While lots of candidate

constructions of one-way functions are known, and recently also

problems whose average-case hardness characterize the existence of

OWFs have been demonstrated, the question of

whether there exists some \emph{worst-case hard problem} ...
more >>>

Meghal Gupta, Rachel Zhang

In a streaming algorithm, Bob receives an input $x \in \{0,1\}^n$ via a stream and must compute a function $f$ in low space. However, this function may be fragile to errors in the input stream. In this work, we investigate what happens when the input stream is corrupted. Our main ... more >>>

Lijie Chen, Roei Tell, Ryan Williams

We establish an equivalence between two algorithmic tasks: *derandomization*, the deterministic simulation of probabilistic algorithms; and *refutation*, the deterministic construction of inputs on which a given probabilistic algorithm fails to compute a certain hard function.

We prove that refuting low-space probabilistic streaming algorithms that try to compute functions $f\in\mathcal{FP}$ ... more >>>

Mika Göös, Ziyi Guan, Tiberiu Mosnoi

What is the $\Sigma_3^2$-circuit complexity (depth 3, bottom-fanin 2) of the $2n$-bit inner product function? The complexity is known to be exponential $2^{\alpha_n n}$ for some $\alpha_n=\Omega(1)$. We show that the limiting constant $\alpha=\limsup \alpha_n$ satisfies

\[

0.847... ~\leq~ \alpha ~\leq~ 0.965...\ .

\]

Determining $\alpha$ is one of the ...
more >>>

Uma Girish, Ran Raz, Wei Zhan

In this note, we observe that quantum logspace computations are verifiable by classical logspace algorithms, with unconditional security. More precisely, every language in BQL has an information-theoretically secure) streaming proof with a quantum logspace prover and a classical logspace verifier. The prover provides a polynomial-length proof that is streamed to ... more >>>

Andrej Bogdanov, Tsun-Ming Cheung, Krishnamoorthy Dinesh, John C.S. Lui

We study the relative advantage of classical and quantum distinguishers of bounded query complexity over $n$-bit strings, focusing on the case of a single quantum query. A construction of Aaronson and Ambainis (STOC 2015) yields a pair of distributions that is $\epsilon$-distinguishable by a one-query quantum algorithm, but $O(\epsilon k/\sqrt{n})$-indistinguishable ... more >>>

Pranav Bisht, Nikhil Gupta, Ilya Volkovich

An arithmetic formula is an arithmetic circuit where each gate has fan-out one. An \emph{arithmetic read-once formula} (ROF in short) is an arithmetic formula where each input variable labels at most one leaf. In this paper we present several efficient blackbox \emph{polynomial identity testing} (PIT) algorithms for some classes of ... more >>>

Gil Cohen, Tal Yankovitz

Recently, Kumar and Mon reached a significant milestone by constructing asymptotically good relaxed locally correctable codes (RLCCs) with poly-logarithmic query complexity. Specifically, they constructed $n$-bit RLCCs with $O(\log^{69}n)$ queries. This significant advancement relies on a clever reduction to locally testable codes (LTCs), capitalizing on recent breakthrough works in LTCs.

With ... more >>>

Vaibhav Krishan

We give a conversion from non-classical polynomials to $\mathit{MidBit}^+$ circuits and vice-versa. This conversion, along with previously known results, shows that torus polynomials, non-classical polynomials and $\mathit{MidBit}^+$ circuits can all be converted to each other. Therefore lower bounds against any of these models lead to lower bounds against all three ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

We prove a stability result for general $3$-wise correlations over distributions satisfying mild connectivity properties. More concretely, we show that if $\Sigma,\Gamma$ and $\Phi$ are alphabets of constant size, and $\mu$ is a pairwise connected distribution over $\Sigma\times\Gamma\times\Phi$ with no $(\mathbb{Z},+)$ embeddings in which the probability of each atom is ... more >>>

Justin Holmgren, Ron Rothblum

We study the circuit complexity of the multiselection problem: given an input string $x \in \{0,1\}^n$ along with indices $i_1,\dots,i_q \in [n]$, output $(x_{i_1},\dots,x_{i_q})$. A trivial lower bound for the circuit size is the input length $n + q \cdot \log(n)$, but the straightforward construction has size $\Theta(q \cdot n)$.

... more >>>Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. We present new explicit constructions of WPRGs that fool certain classes of standard-order read-once branching programs. In particular, our WPRGs ... more >>>

Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk

We show that for every homogeneous polynomial of degree $d$, if it has determinantal complexity at most $s$, then it can be computed by a homogeneous algebraic branching program (ABP) of size at most $O(d^5s)$. Moreover, we show that for \textit{most} homogeneous polynomials, the width of the resulting homogeneous ABP ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

For a prime $p$, a restricted arithmetic progression in $\mathbb{F}_p^n$ is a triplet of vectors $x, x+a, x+2a$ in which the common difference $a$ is a non-zero element from $\{0,1,2\}^n$. What is the size of the largest $A\subseteq \mathbb{F}_p^n$ that is free of restricted arithmetic progressions? We show that the ... more >>>

François Le Gall, Yupan Liu, Qisheng Wang

Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-bounded quantum computation, which encompasses settings with one-sided error (unitary coRQL) and two-sided error (BQL), approached from a quantum (mixed) state testing perspective:

- The first family of natural ...
more >>>

Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum

Motivated by the fact that input distributions are often unknown in advance, distribution-free property testing considers a setting in which the algorithmic task is to accept functions $f : [n] \to \{0,1\}$ having a certain property $\Pi$ and reject functions that are $\varepsilon$-far from $\Pi$, where the distance is measured ... more >>>

Yotam Dikstein, Irit Dinur

Given a family X of subsets of [n] and an ensemble of local functions $\{f_s:s\to\Sigma \;|\; s\in X\}$, an agreement test is a randomized property tester that is supposed to test whether there is some global function $G:[n]\to\Sigma$ such that $f_s=G|_s$ for many sets $s$. For example, the V-test chooses ... more >>>

Mitali Bafna, Dor Minzer

A $d$-dimensional simplicial complex $X$ is said to support a direct product tester if any locally consistent function defined on its $k$-faces (where $k\ll d$) necessarily come from a function over its vertices. More precisely, a direct product tester has a distribution $\mu$ over pairs of $k$-faces $(A,A')$, and given ... more >>>

Theodoros Papamakarios

We show that for any integer $d>0$, depth $d$ Frege systems are NP-hard to automate. Namely, given a set $S$ of depth $d$ formulas, it is NP-hard to find a depth $d$ Frege refutation of $S$ in time polynomial in the size of the shortest such a refutation. This extends ... more >>>

Vikraman Arvind, Abhranil Chatterjee

We revisit the main result of Carmosino et al \cite{CILM18} which shows that an $\Omega(n^{\omega/2+\epsilon})$ size noncommutative arithmetic circuit size lower bound (where $\omega$ is the matrix multiplication exponent) for a constant-degree $n$-variate polynomial family $(g_n)_n$, where each $g_n$ is a noncommutative polynomial, can be ``lifted'' to an exponential size ... more >>>

Noam Mazor

In the Random Oracle Model (ROM) all parties have oracle access to a common random function, and the parties are limited in the number of queries they can make to the oracle. The Merkle’s Puzzles protocol, introduced by Merkle [CACM ’78], is a key-agreement protocol in the ROM with a ... more >>>

Zander Kelley, Shachar Lovett, Raghu Meka

We study the power of randomness in the Number-on-Forehead (NOF) model in communication complexity. We construct an explicit 3-player function $f:[N]^3 \to \{0,1\}$, such that: (i) there exist a randomized NOF protocol computing it that sends a constant number of bits; but (ii) any deterministic or nondeterministic NOF protocol computing ... more >>>

Omar Alrabiah, Venkatesan Guruswami, Ray Li

Reed-Solomon codes are a classic family of error-correcting codes consisting of evaluations of low-degree polynomials over a finite field on some sequence of distinct field elements. They are widely known for their optimal unique-decoding capabilities, but their list-decoding capabilities are not fully understood. Given the prevalence of Reed-Solomon codes, a ... more >>>

Omar Alrabiah, Venkatesan Guruswami, Ray Li

A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate $R$ codes are not list-decodable using list-size $L$ beyond an error fraction $\frac{L}{L+1} (1-R)$ (the Singleton bound being the case of $L=1$, i.e., unique decoding). We prove that in order to approach this bound for ... more >>>

Irit Dinur, Siqi Liu, Rachel Zhang

We describe a new family of symmetric error-correcting codes with low-density parity-check matrices (LDPC).

Our codes can be described in two seemingly different ways. First, in relation to Reed-Muller codes: our codes are functions on a subset of $\mathbb{F}^n$ whose restrictions to a prescribed set of affine lines has low ... more >>>

Xue Chen, Kuan Cheng, Xin Li, Songtao Mao

Random linear codes (RLCs) are well known to have nice combinatorial properties and near-optimal parameters in many different settings. However, getting explicit constructions matching the parameters of RLCs is challenging, and RLCs are hard to decode efficiently. This motivated several previous works to study the problem of partially derandomizing RLCs, ... more >>>

Sravanthi Chede, Leroy Chew, Balesh Kumar, Anil Shukla

QBF proof systems are routinely adapted from propositional logic along with adjustments for the new quantifications. Existing are two main successful frameworks, the reduction and expansion frameworks, inspired by QCDCL [Zhang et al. ICCAD.'2002] and CEGAR solving [Janota et al. Artif. Intell.'2016] respectively. However, the reduction framework, while immensely useful ... more >>>

Eshan Chattopadhyay, Jyun-Jie Liao

In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular read-once branching programs (ROBPs). Their result is based on a clever modification to the inverse Laplacian perspective of space-bounded derandomization, which was originally introduced by Ahmadinejad, Kelner, ... more >>>

Meghal Gupta, Rachel Zhang

In interactive coding, Alice and Bob wish to compute some function $f$ of their individual private inputs $x$ and $y$. They do this by engaging in an interactive protocol to jointly compute $f(x,y)$. The goal is to do this in an error-resilient way, such that even given some fraction of ... more >>>

Yogesh Dahiya, Meena Mahajan, Sasank Mouli

In this paper, we obtain new size lower bounds for proofs in the

Polynomial Calculus (PC) proof system, in two different settings.

1. When the Boolean variables are encoded using $\pm 1$ (as opposed

to $0,1$): We establish a lifting theorem using an asymmetric gadget

$G$, showing ...
more >>>

David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer

If $G$ is a group, we say a subset $S$ of $G$ is product-free if the equation $xy=z$ has no solutions with $x,y,z \in S$. For $D \in \mathbb{N}$, a group $G$ is said to be $D$-quasirandom if the minimal dimension of a nontrivial complex irreducible representation of $G$ is ... more >>>

Oded Goldreich

We consider the complexity of enumerating ordered sets, defined as solving the following type of a computational problem: For a predetermined ordered set, given $i\in\N$, one is required to answer with the $i^{th}$ member of the set (according to the predetermined order).

Our focus is on countable sets such as ... more >>>

Prerona Chatterjee, Anamay Tengse

We study the algebraic complexity of annihilators of polynomials maps. In particular, when a polynomial map is `encoded by' a small algebraic circuit, we show that the coefficients of an annihilator of the map can be computed in PSPACE. Even when the underlying field is that of reals or complex ... more >>>

Benny Applebaum, Oded Nir

A major open problem in information-theoretic cryptography is to obtain a super-polynomial lower bound for the communication complexity of basic cryptographic tasks. This question is wide open even for very powerful non-interactive primitives such as private information retrieval (or locally-decodable codes), general secret sharing schemes, conditional disclosure of secrets, and ... more >>>

Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang

Constructing key-agreement protocols in the random oracle model (ROM) is a viable method to assess the feasibility of developing public-key cryptography within Minicrypt. Unfortunately, as shown by Impagliazzo and Rudich (STOC 1989) and Barak and Mahmoody (Crypto 2009), such protocols can only guarantee limited security: any $\ell$-query protocol can be ... more >>>

Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman

The ExactlyN problem in the number-on-forehead (NOF) communication setting asks $k$ players, each of whom can see every input but their own, if the $k$ input numbers add up to $N$. Introduced by Chandra, Furst and Lipton in 1983, ExactlyN is important for its role in understanding the strength of ... more >>>

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi

For every constant $d$, we design a subexponential time deterministic algorithm that takes as input a multivariate polynomial $f$ given as a constant depth algebraic circuit over the field of rational numbers, and outputs all irreducible factors of $f$ of degree at most $d$ together with their respective multiplicities. Moreover, ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani

We explicitly construct the first nontrivial extractors for degree $d \ge 2$ polynomial sources over $\mathbb{F}_2^n$. Our extractor requires min-entropy $k\geq n - \frac{\sqrt{\log n}}{(d\log \log n)^{d/2}}$. Previously, no constructions were known, even for min-entropy $k\geq n-1$. A key ingredient in our construction is an input reduction lemma, which allows ... more >>>

Nader Bshouty, Gergely Harcos

Let $X$ be a set of items of size $n$ , which may contain some defective items denoted by $I$, where $I \subseteq X$. In group testing, a {\it test} refers to a subset of items $Q \subset X$. The test outcome is $1$ (positive) if $Q$ contains at least ... more >>>

Tom Gur, Wilfred Salmon, Sergii Strelchuk

We revisit the problem of characterising the complexity of Quantum PAC learning, as introduced by Bshouty and Jackson [SIAM J. Comput.

1998, 28, 1136–1153]. Several quantum advantages have been demonstrated in this setting, however, none are generic: they apply to particular concept classes and typically only work when the distribution ...
more >>>

Noam Mazor, Rafael Pass

A central result in the theory of Cryptography, by Hastad, Imagliazzo, Luby and Levin [SICOMP’99], demonstrates that the existence one-way functions (OWF) implies the existence of pseudo-random generators (PRGs). Despite the fundamental importance of this result, and several elegant improvements/simplifications, analyses of constructions of PRGs from OWFs remain complex (both ... more >>>

Lijie Chen, Shuichi Hirahara, Hanlin Ren

We show that there is a language in $\mathrm{S}_2\mathrm{E}/_1$ (symmetric exponential time with one bit of advice) with circuit complexity at least $2^n/n$. In particular, the above also implies the same near-maximum circuit lower bounds for the classes $\Sigma_2\mathrm{E}$, $(\Sigma_2\mathrm{E}\cap\Pi_2\mathrm{E})/_1$, and $\mathrm{ZPE}^{\mathrm{NP}}/_1$. Previously, only "half-exponential" circuit lower bounds for these ... more >>>

Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran

In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabilistic inference over directed graphical models. This reduction leads to a fully polynomial randomized approximation scheme (FPRAS) for ... more >>>

Oded Goldreich, Laliv Tauber

We consider the problem of testing isomorphism to a fixed graph in the bounded-degree graph model. Our main result is that, for almost all $d$-regular $n$-vertex graphs $H$,

testing isomorphism to $H$ can be done using $\tildeO({\sqrt n})$ queries.

This result is shown to be optimal (up to ...
more >>>

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Rational Identity Testing (RIT) is the decision problem of determining whether or not a given noncommutative rational formula computes zero in the free skew field. It admits a deterministic polynomial-time white-box algorithm [Garg et al., 2016; Ivanyos et al., 2018; Hamada and Hirai, 2021], and a randomized polynomial-time black-box algorithm ... more >>>

Srinivasan Arunachalam, Uma Girish, Noam Lifshitz

We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost $O(\log N)$ in this model, however, every interactive randomized protocol has cost $\Omega(\sqrt{N})$, settling a ... 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.

The goal ... more >>>

Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse

In this work, we study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat 2008, Koiran & Perifel 2009, Malod 2011, Mahajan & Rao 2013) that is believed to be larger than VNP. We observe that these monotone analogues are not equivalent unlike their ... more >>>

Hao Wu

One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, to tackle this problem Karchmer, Raz and Wigderson proposed the KRW conjecture about composition of two functions. While this conjecture seems out of our current reach, some relaxed conjectures are ... more >>>

Yanyi Liu, Rafael Pass

Consider the recently introduced notion of \emph{probabilistic

time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al,

CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k.

We show the equivalence of the following:

- MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable

distribution $\D$;

- ...
more >>>

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii

In this paper, we study the problem of computing the majority function by low-depth monotone circuits and a related problem of constructing low-depth sorting networks. We consider both the classical setting with elementary operations of arity $2$ and the generalized setting with operations of arity $k$, where $k$ is a ... more >>>

Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer

We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions $f$, it is conjectured that $\mathrm{rdeg}(f)$ is polynomially related to $\mathrm{deg}(f)$, where $\mathrm{deg}(f)$ is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least $\mathrm{deg}(f)/2$ and ... more >>>

Venkatesan Guruswami, Xuandi Ren, Sai Sandeep

The Parameterized Inapproximability Hypothesis (PIH) is the analog of the PCP theorem in the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a satisfiable 2CSP instance from one which is only $(1-\varepsilon)$-satisfiable (where the parameter is the number of variables) for some constant $0<\varepsilon<1$.

We ... more >>>

Zeyong Li

In a recent breakthrough, Chen, Hirahara and Ren prove that S$_2$E/$_1 \not\subset$ SIZE$[2^n/n]$ by giving a single-valued FS$_2$P algorithm for the Range Avoidance Problem (Avoid) that works for infinitely many input size $n$.

Building on their work, we present a simple single-valued FS$_2$P algorithm for Avoid that works for all ... more >>>

Vladimir Podolskii, Dmitrii Sluch

Boolean function $F(x,y)$ for $x,y \in \{0,1\}^n$ is an XOR function if $F(x,y) = f(x\oplus y)$ for some function $f$ on $n$ input bits, where $\oplus$ is a bit-wise XOR. XOR functions are relevant in communication complexity, partially for allowing Fourier analytic technique. For total XOR functions it is known ... more >>>

Oded Goldreich

For any fixed $t$, we present two fine-grained reductions of the problem of approximately counting the number of $t$-cliques in a graph to the problem of detecting a $t$-clique in a graph.

One of our reductions is slightly better than the prior reduction of Dell, Lapinskas, and Meeks (SODA20) and ...
more >>>

Guangxu Yang, Jiapeng Zhang

Collision problems are important problems in complexity theory and cryptography with diverse applications. Previous fruitful works have mainly focused on query models. Driven by various applications, several works by Bauer, Farshim and Mazaheri (CRYPTO 2018), Itsykson and Riazanov (CCC 2021), Göös and Jain (RANDOM 2022) independently proposed the communication version ... more >>>

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

In this note, we give very simple constructions of unique neighbor expander graphs starting from spectral or combinatorial expander graphs of mild expansion. These constructions and their analysis are simple variants of the constructions of LDPC error-correcting codes from expanders, given by

Sipser-Spielman~\cite{SS96} (and Tanner~\cite{Tanner81}), and their analysis. We also ...
more >>>

Tal Herman, Guy Rothblum

Suppose we have access to a small number of samples from an unknown distribution, and would like learn facts about the distribution.

An untrusted data server claims to have studied the distribution and makes assertions about its properties. Can the untrusted data server prove that its assertions are approximately correct? ...
more >>>

Pravesh Kothari, Peter Manohar

We prove that the blocklength $n$ of a linear $3$-query locally correctable code (LCC) $\mathcal{L} \colon \mathbb{F}^k \to \mathbb{F}^n$ with distance $\delta$ must be at least $n \geq 2^{\Omega\left(\left(\frac{\delta^2 k}{(|\mathbb{F}|-1)^2}\right)^{1/8}\right)}$. In particular, the blocklength of a linear $3$-query LCC with constant distance over any small field grows exponentially with $k$. ... more >>>

Nikhil Balaji, Samir Datta

The Sum of Square Roots (SSR) problem is the following computational problem: Given positive integers $a_1, \dots, a_k$, and signs $\delta_1, \dots, \delta_k \in \{-1, 1\}$, check if $\sum_{i=1}^k \delta_i \sqrt{a_i} > 0$. The problem is known to have a polynomial time algorithm on the real RAM model of computation, ... more >>>

Shuo Wang, Guangxu Yang, Jiapeng Zhang

Set-disjointness is one of the most fundamental and widely studied problems in the area of communication complexity. In this problem, each party $i$ receives a set $S_i\subseteq [N]$. The goal is to determine whether $\bigcap S_i$ is empty via communication between players. The decision version simply asks if the common ... more >>>

Rahul Ilango

The Minimum Circuit Size Problem (MCSP) asks, given the truth table of a Boolean function $f$ and an integer $s$, if there is a circuit computing $f$ of size at most $s.$ It has been an open question since Levin's seminal work on NP-completeness whether MCSP is NP-complete. This question ... more >>>

Dmytro Gavinsky

We define and study the model of patterned non-determinism in bipartite communication complexity, denoted by $PNP^{X\leftrightarrow Y}$.

It generalises the known models $UP^{X\leftrightarrow Y}$ and $FewP^{X\leftrightarrow Y}$ through relaxing the constraints on the witnessing structure of the underlying $NP^{X\leftrightarrow Y}$-protocol.

It is shown that for the case of total functions ...
more >>>

Marshall Ball, Ronen Shaltiel, Jad Silbak

We give an explicit construction of non-malleable codes with rate $1-o(1)$ for the tampering class of poly-size circuits. This rate is optimal, and improves upon the previous explicit construction of Ball, Dachman-Soled and Loss (CRYPTO 2022) which achieves a rate smaller than $\frac{1}{n}$. Our codes are based on the same ... more >>>

Edward Pyne

We prove that for every $\alpha \in [1,1.5]$,

$$

\text{BPSPACE}[S]\subseteq \text{TISP}[2^{S^{\alpha}},S^{3-\alpha}]

$$

where $\text{BPSPACE}[S]$ corresponds to randomized space $O(S)$ computation, and $\text{TISP}[T,S]$ to time $poly(T)$, space $O(S)$ computation. Our result smoothly interpolates between the results of (Nisan STOC 1992) and (Saks and Zhou FOCS 1995), which prove $\text{BPSPACE}[S]$ is contained ...
more >>>

Marshall Ball, Dana Dachman-Soled, Eli Goldin, Saachi Mutreja

Randomness extractors provide a generic way of converting sources of randomness that are

merely unpredictable into almost uniformly random bits. While in general, deterministic randomness

extraction is impossible, it is possible if the source has some structural constraints.

While much of the literature on deterministic extraction has focused on sources ...
more >>>

Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha

We present a general framework for designing efficient algorithms for unsupervised learning problems, such as mixtures of Gaussians and subspace clustering. Our framework is based on a meta algorithm that learns arithmetic circuits in the presence of noise, using lower bounds. This builds upon the recent work of Garg, Kayal ... more >>>

Shuichi Hirahara, Rahul Ilango, Ryan Williams

A compression problem is defined with respect to an efficient encoding function $f$; given a string $x$, our task is to find the shortest $y$ such that $f(y) = x$. The obvious brute-force algorithm for solving this compression task on $n$-bit strings runs in time $O(2^{\ell} \cdot t(n))$, where $\ell$ ... more >>>

Meghal Gupta

Locally decodable codes (LDC's) are error-correcting codes that allow recovery of individual message indices by accessing only a constant number of codeword indices. For substitution errors, it is evident that LDC's exist -- Hadamard codes are examples of $2$-query LDC's. Research on this front has focused on finding the optimal ... more >>>

Louis Golowich, Venkatesan Guruswami

Classical locally recoverable codes, which permit highly efficient recovery from localized errors as well as global recovery from larger errors, provide some of the most useful codes for distributed data storage in practice. In this paper, we initiate the study of quantum locally recoverable codes (qLRCs). In the long ... more >>>

James Cook, Ian Mertz

The Tree Evaluation Problem ($TreeEval$) (Cook et al. 2009) is a central candidate for separating polynomial time ($P$) from logarithmic space ($L$) via composition. While space lower bounds of $\Omega(\log^2 n)$ are known for multiple restricted models, it was recently shown by Cook and Mertz (2020) that TreeEval can be ... more >>>

Noam Mazor, Rafael Pass

The Perebor (Russian for “brute-force search”) conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP ? = P conjecture (which they predate) and state that for “meta-complexity” problems, such as the Time-bounded ... more >>>

William Hoza

We study hardness amplification in the context of two well-known "moderate" average-case hardness results for $\mathrm{AC}^0$ circuits. First, we investigate the extent to which $\mathrm{AC}^0$ circuits of depth $d$ can approximate $\mathrm{AC}^0$ circuits of some larger depth $d + k$. The case $k = 1$ is resolved by Håstad, Rossman, ... more >>>

Kiran Kedlaya, Swastik Kopparty

For an odd prime $p$, we say $f(X) \in {\mathbb F}_p[X]$ computes square roots in $\mathbb F_p$ if, for all nonzero perfect squares $a \in \mathbb F_p$, we have $f(a)^2 = a$.

When $p \equiv 3$ mod $4$, it is well known that $f(X) = X^{(p+1)/4}$ computes square ...
more >>>

Louis Golowich, Tali Kaufman

Recent constructions of the first asymptotically good quantum LDPC (qLDPC) codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit lower bounds against a linear number of levels of the Sum-of-Squares (SoS) hierarchy (Hopkins and Lin, FOCS'22).

In ... more >>>

Ian Mertz

In the world of space-bounded complexity, there is a strain of results showing that space can, somewhat paradoxically, be used for multiple purposes at once. Touchstone results include Barrington’s Theorem and the recent line of work on catalytic computing. We refer to such techniques, in contrast to the usual notion ... more >>>

Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka

We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM can be solved in truly subcubic $O(n^\omega)$ time, where $\omega<3$; much work has gone into bringing $\omega$ closer to $2$. Since then, a ... more >>>

Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov

Can every $n$-bit boolean function with deterministic query complexity $k\ll n$ be restricted to $O(k)$ variables such that the query complexity remains $\Omega(k)$? That is, can query complexity be condensed via restriction? We study such hardness condensation questions in both query and communication complexity, proving two main results.

$\bullet~$ $\mathbf{Negative}$: ... more >>>

Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan

We prove that the most natural low-degree test for polynomials over finite fields is ``robust'' in the high-error regime for linear-sized fields. Specifically we consider the ``local'' agreement of a function $f\colon \mathbb{F}_q^m \to \mathbb{F}_q$ from the space of degree-$d$ polynomials, i.e., the expected agreement of the function from univariate ... more >>>

Gil Cohen, Itay Cohen, Gal Maor, Yuval Peled

The notion of the derandomized square of two graphs, denoted as $G \circ H$, was introduced by Rozenman and Vadhan as they rederived Reingold's Theorem, $\mathbf{SL} = \mathbf{L}$. This pseudorandom primitive, closely related to the Zig-Zag product, plays a crucial role in recent advancements on space-bounded derandomization. For this and ... more >>>

Gabriel Bathie, Ryan Williams

A fundamental problem in circuit complexity is to find explicit functions that require large depth to compute. When considering the natural DeMorgan basis of $\{\text{OR},\text{AND}\}$, where negations incur no cost, the best known depth lower bounds for an explicit function in NP have the form $(3-o(1))\log_2 n$, established by H{\aa}stad ... more >>>

Rohan Goyal, Prahladh Harsha, Mrinal Kumar, A. Shankar

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in nearly-linear time. This yields, to the best of our knowledge, the first known family of codes that can be decoded (and encoded) in nearly linear time, even as they ... more >>>

Ce Jin, Ryan Williams, Nathaniel Young

Given the need for ever higher performance, and the failure of CPUs to keep providing single-threaded performance gains, engineers are increasingly turning to highly-parallel custom VLSI chips to implement expensive computations. In VLSI design, the gates and wires of a logical circuit are placed on a 2-dimensional chip with a ... more >>>

Klim Efremenko, Michal Garlik, Dmitry Itsykson

The proof system resolution over parities (Res($\oplus$)) operates with disjunctions of linear equations (linear clauses) over $\mathbb{F}_2$; it extends the resolution proof system by incorporating linear algebra over $\mathbb{F}_2$. Over the years, several exponential lower bounds on the size of tree-like Res($\oplus$) refutations have been established. However, proving a superpolynomial ... more >>>

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an $\varepsilon$ fraction of constraints for some absolute constant $\varepsilon > 0$. PIH plays the role of ... more >>>

John Kallaugher, Ojas Parekh, Nadezhda Voronova

While the search for quantum advantage typically focuses on speedups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data stream problems, in which elements arrive and must be processed sequentially without random access, but these have been ... more >>>

Leonid Gurvits, Nathan Klein, Jonathan Leake

We give simply exponential lower bounds on the probabilities of a given strongly Rayleigh distribution, depending only on its expectation. This resolves a weak version of a problem left open by Karlin-Klein-Oveis Gharan in their recent breakthrough work on metric TSP, and this resolution leads to a minor improvement of ... more >>>

Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Proving explicit lower bounds on the size of algebraic formulas is a long-standing open problem in the area of algebraic complexity theory. Recent results in the area (e.g. a lower bound against constant-depth algebraic formulas due to Limaye, Srinivasan, and Tavenas (FOCS 2021)) have indicated a way forward for attacking ... more >>>

Noam Mazor, Rafael Pass

The relationships between various meta-complexity problems are not well understood in the worst-case regime, including whether the search version is harder than the decision version, whether the hardness scales with the ``threshold", and how the hardness of different meta-complexity problems relate to one another, and to the task of function ... more >>>

Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz

We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$, and the goal is to find a $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. We are interested in the randomized complexity of this problem, i.e., in ... more >>>

Siddharth Iyer, Anup Rao

We define the marginal information of a communication protocol, and use it to prove XOR lemmas for communication complexity. We show that if every $C$-bit protocol has bounded advantage for computing a Boolean function $f$, then every $\tilde \Omega(C \sqrt{n})$-bit protocol has advantage $\exp(-\Omega(n))$ for computing the $n$-fold xor $f^{\oplus ... more >>>

Shai Evra, Shay Gadot, Ohad Klein, Ilan Komargodski

We consider the following problem: Given an $n \times n$ multiplication table, decide whether it is a Cayley multiplication table of a group. Among deterministic algorithms for this problem, the best known algorithm is implied by F. W. Light's associativity test (1949) and has running time of $O(n^2 \log n)$. ... more >>>

Huacheng Yu, Wei Zhan

Given a distribution over $[n]^n$ such that any $k$ coordinates need $k/\log^{O(1)}n$ bits of communication to sample, we prove that any map that samples this distribution from uniform cells requires locality $\Omega(\log(n/k)/\log\log(n/k))$. In particular, we show that for any constant $\delta>0$, there exists $\varepsilon=2^{-\Omega(n^{1-\delta})}$ such that $\Omega(\log n/\log\log n)$ non-adaptive ... more >>>

Sepehr Assadi, Gillat Kol, Zhijun Zhang

The seminal work of Ahn, Guha, and McGregor in 2012 introduced the graph sketching technique and used it to present the first streaming algorithms for various graph problems over dynamic streams with both insertions and deletions of edges. This includes algorithms for cut sparsification, spanners, matchings, and minimum spanning trees ... more >>>

Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer

We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection games with value less than 1.

more >>>Ján Pich, Rahul Santhanam

We give a new approach to the fundamental question of whether proof complexity lower bounds for concrete propositional proof systems imply super-polynomial Boolean circuit lower bounds.

For any poly-time computable function $f$, we define the witnessing formulas $w_n^k(f)$, which are propositional formulas stating that for any circuit $C$ of size ... more >>>

Joseph Shunia

A deterministic primality test with a polynomial time complexity of $\tilde{O}(\log^3(n))$ is presented. The test posits that an integer $n$ satisfying the conditions of the main theorem is prime. Combining elements of number theory and combinatorics, the proof operates on the basis of simultaneous modular congruences relating to binomial transforms ... more >>>

Alexander Shekhovtsov, Georgii Zakharov

We reduce the best-known upper bound on the length of a program that enumerates a set in terms of the probability of it being enumerated by a random program. We prove a general result that any linear upper bound for finite sets implies the same linear bound for infinite sets.

... more >>>C Ramya, Pratik Shastri

Arithmetic circuits are a natural well-studied model for computing multivariate polynomials over a field. In this paper, we study planar arithmetic circuits. These are circuits whose underlying graph is planar. In particular, we prove an $\Omega(n\log n)$ lower bound on the size of planar arithmetic circuits computing explicit bilinear forms ... more >>>

Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni

The log-rank conjecture, a longstanding problem in communication complexity, has persistently eluded resolution for decades. Consequently, some recent efforts have focused on potential approaches for establishing the conjecture in the special case of XOR functions, where the communication matrix is lifted from a boolean function, and the rank of ... more >>>

John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen

We prove a tight parallel repetition theorem for 3-message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We also prove under plausible assumptions that the security of 4-message computationally secure protocols does not generally decrease under parallel repetition. These mirror the classical results of Bellare, Impagliazzo, ... more >>>

Marshall Ball, Dana Dachman-Soled

A ZAP is a witness-indistinguishable two-message public-coin interactive proof with the following simple structure: the verifier sends a uniformly random string, the prover responds, and the verifier decides in polynomial time whether to accept or reject.

We show that one-way functions imply the existence of ...
more >>>

Yilei Chen, Jiatu Li

A recent line of research has introduced a systematic approach to explore the complexity of explicit construction problems through the use of meta problems, namely, the range avoidance problem (abbrev. Avoid) and the remote point problem (abbrev. RPP). The upper and lower bounds for these meta problems provide a unified ... more >>>

Omri Ben-Eliezer, Tomer Grossman, Moni Naor

Suppose you are given a function $f\colon [n] \to [n]$ via (black-box) query access to the function. You are looking to find something local, like a collision (a pair $x \neq y$ s.t.\ $f(x)=f(y)$). The question is whether knowing the `shape' of the function helps you or not (by shape ... more >>>

Dean Doron, Edward Pyne, Roei Tell

We provide compelling evidence for the potential of hardness-vs.-randomness approaches to make progress on the long-standing problem of derandomizing space-bounded computation.

Our first contribution is a derandomization of bounded-space machines from hardness assumptions for classes of uniform deterministic algorithms, for which strong (but non-matching) lower bounds can be unconditionally proved. ... more >>>

Yotam Dikstein, Irit Dinur

We introduce and study swap cosystolic expansion, a new expansion property of simplicial complexes. We prove lower bounds for swap coboundary expansion of spherical buildings and use them to lower bound swap cosystolic expansion of the LSV Ramanujan complexes. Our motivation is the recent work (in a companion paper) showing ... more >>>

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach

While the existence of randomness extractors, both seeded and seedless, has been thoroughly studied for many sources of randomness, currently, very little is known regarding the existence of seedless condensers in many settings. Here, we prove several new results for seedless condensers in the context of three related classes of ... more >>>

Rafael Pass, Oren Renard

We study the problem of whether \emph{persistent} randomness is helpful for polynomial-time algorithms that only use \emph{logarithmic} space. In more detail, we consider the class $\searchBPLs$, of \emph{search}-problems that are solvable by a polynomial-time Probabilistic Logspace TMs with \emph{2-way} access (i.e., with multiple, as opposed to one-time, access) to a ... more >>>

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka

In this paper, we prove the first super-polynomial and, in fact, exponential lower bound for the model of sum of read-once oblivious algebraic branching programs (ROABPs). In particular, we give an explicit polynomial such that any sum of ROABPs

(equivalently, sum of *ordered* set-multilinear branching programs, each with a ...
more >>>

Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai

The existence of "unstructured" hard languages in $\text{NP}\cap\text{coNP}$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $\text{P}$ is separated from $\text{NP}\cap\text{coNP}$ relative to a random oracle, a question that remained open ever since. While a hard language in $\text{NP}\cap\text{coNP}$ can be constructed in a black-box way ... more >>>

Oded Goldreich, Laliv Tauber

Following Ergun et al. (JCSS 2000), we consider testing group properties and focus on the problem of testing whether a binary operation is a group operation.

That is, given a finite set $S$ and oracle access to a function $f:S\times S \to S$, we wish to distinguish the case that ...
more >>>