All reports in year 2024:

__
TR24-125
| 19th July 2024
__

Pavel Hrubes, Pushkar Joglekar#### On read-$k$ projections of the determinant

__
TR24-124
| 26th July 2024
__

Oded Goldreich#### Solving Tree Evaluation in $o(\log n \cdot \log\log n)$ space

__
TR24-123
| 22nd July 2024
__

Vishwas Bhargava, Devansh Shringi#### Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition

__
TR24-122
| 28th June 2024
__

Antoine Joux, Anand Kumar Narayanan#### A high dimensional Cramer's rule connecting homogeneous multilinear equations to hyperdeterminants

__
TR24-121
| 16th July 2024
__

Nader Bshouty#### Approximating the Number of Relevant Variables in a Parity Implies Proper Learning

Revisions: 1

__
TR24-120
| 15th July 2024
__

Halley Goldberg, Valentine Kabanets#### Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity

__
TR24-119
| 14th July 2024
__

Vishwas Bhargava, Anamay Tengse#### Explicit Commutative ROABPs from Partial Derivatives

__
TR24-118
| 9th July 2024
__

Amnon Ta-Shma, Ron Zadiario#### The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced

__
TR24-117
| 12th June 2024
__

Ludmila Glinskih, Artur Riazanov#### Partial Minimum Branching Program Size Problem is ETH-hard

__
TR24-116
| 6th July 2024
__

Lijie Chen, Ron D. Rothblum, Roei Tell#### Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)

__
TR24-115
| 14th July 2024
__

Zhenjian Lu, Igor Oliveira, Hanlin Ren, Rahul Santhanam#### On the Complexity of Avoiding Heavy Elements

__
TR24-114
| 12th July 2024
__

Nir Bitansky, Ron D. Rothblum, Prahladh Harsha, Yuval Ishai, David Wu#### Dot-Product Proofs and Their Applications

__
TR24-113
| 4th July 2024
__

Nikhil Vyas, Ryan Williams#### On Oracles and Algorithmic Methods for Proving Lower Bounds

__
TR24-112
| 3rd July 2024
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### The Rate of Interactive Codes is Bounded Away from 1

__
TR24-111
| 1st July 2024
__

Siddharth Iyer, Anup Rao#### An XOR Lemma for Deterministic Communication Complexity

__
TR24-110
| 1st July 2024
__

Joshua Cook, Dana Moshkovitz#### Time and Space Efficient Deterministic Decoders

__
TR24-109
| 29th June 2024
__

Oded Goldreich#### On the Cook-Mertz Tree Evaluation procedure

Revisions: 1

__
TR24-108
| 28th June 2024
__

Benny Applebaum, Eliran Kachlon#### Stochastic Secret Sharing with $1$-Bit Shares and Applications to MPC

__
TR24-107
| 23rd June 2024
__

Benjamin Rossman#### Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication

__
TR24-106
| 17th June 2024
__

James Cook, Jiatu Li, Ian Mertz, Edward Pyne#### The Structure of Catalytic Space: Capturing Randomness and Time via Compression

__
TR24-105
| 13th June 2024
__

Benny Applebaum, Kaartik Bhushan, Manoj Prabhakaran#### Communication Complexity vs Randomness Complexity in Interactive Proofs

__
TR24-104
| 12th June 2024
__

Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha#### NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials

__
TR24-103
| 11th June 2024
__

Farzan Byramji, Vatsal Jha, Chandrima Kayal, Rajat Mittal#### Relations between monotone complexity measures based on decision tree complexity

__
TR24-102
| 29th May 2024
__

Inbar Ben Yaacov, Yotam Dikstein, Gal Maor#### Sparse High Dimensional Expanders via Local Lifts

Revisions: 1

__
TR24-101
| 21st May 2024
__

Or Keret, Ron Rothblum, Prashant Nalini Vasudevan#### Doubly-Efficient Batch Verification in Statistical Zero-Knowledge

__
TR24-100
| 21st May 2024
__

Changrui Mu, Prashant Nalini Vasudevan#### Instance-Hiding Interactive Proofs

__
TR24-099
| 5th June 2024
__

Pavel Hrubes#### A subquadratic upper bound on Hurwitz's problem and related non-commutative polynomials

__
TR24-098
| 26th May 2024
__

Noga Amit, Orr Paradise, Guy Rothblum, shafi goldwasser#### Models That Prove Their Own Correctness

Revisions: 2

__
TR24-097
| 31st May 2024
__

Zhiyang Xun, David Zuckerman#### Near-Optimal Averaging Samplers

Revisions: 2

__
TR24-096
| 27th May 2024
__

Noga Amit, Guy Rothblum#### Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way Functions

Revisions: 1

__
TR24-095
| 23rd May 2024
__

Yanyi Liu, Noam Mazor, Rafael Pass#### A Note on Zero-Knowledge for NP and One-Way Functions

__
TR24-094
| 19th May 2024
__

Tal Herman, Guy Rothblum#### Interactive Proofs for General Distribution Properties

__
TR24-093
| 16th May 2024
__

Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, Joao Ribeiro#### Low-Degree Polynomials Are Good Extractors

__
TR24-092
| 16th May 2024
__

Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan#### Hilbert Functions and Low-Degree Randomness Extractors

__
TR24-091
| 14th May 2024
__

Dean Doron, Jonathan Mosheiff, Mary Wootters#### When Do Low-Rate Concatenated Codes Approach The Gilbert--Varshamov Bound?

Revisions: 1

__
TR24-090
| 12th May 2024
__

Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz#### A Study of Error Reduction Polynomials

__
TR24-089
| 8th May 2024
__

Gil Cohen, Itay Cohen, Gal Maor#### Tight Bounds for the Zig-Zag Product

__
TR24-088
| 29th April 2024
__

Tamer Mour, Alon Rosen, Ron Rothblum#### Locally Testable Tree Codes

__
TR24-087
| 27th April 2024
__

Renato Ferreira Pinto Jr.#### Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach

__
TR24-086
| 24th April 2024
__

Hao Wu#### A nearly-$4\log n$ depth lower bound for formulas with restriction on top

__
TR24-085
| 25th April 2024
__

Zhenjian Lu, Rahul Santhanam#### Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity

__
TR24-084
| 24th April 2024
__

Vikraman Arvind, Pushkar Joglekar#### A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results

Revisions: 1

__
TR24-083
| 18th April 2024
__

Lijie Chen, Jiatu Li, Igor Carboni Oliveira#### On the Unprovability of Circuit Size Bounds in Intuitionistic $S^1_2$

__
TR24-082
| 17th April 2024
__

Yotam Dikstein, Max Hopkins#### Chernoff Bounds and Reverse Hypercontractivity on HDX

Revisions: 1

__
TR24-081
| 2nd April 2024
__

Sravanthi Chede, Leroy Chew, Anil Shukla#### Circuits, Proofs and Propositional Model Counting

Revisions: 1

__
TR24-080
| 16th April 2024
__

Robert Andrews, Avi Wigderson#### Constant-Depth Arithmetic Circuits for Linear Algebra Problems

__
TR24-079
| 20th April 2024
__

Tuomas Hakoniemi , Nutan Limaye, Iddo Tzameret#### Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers

__
TR24-078
| 19th April 2024
__

Oded Goldreich#### On the relaxed LDC of BGHSV: A survey that corrects the record

Revisions: 1

__
TR24-077
| 19th April 2024
__

Divesh Aggarwal, JinMing Leong, Alexandra Veliche#### Worst-Case to Average-Case Hardness of LWE: A Simple and Practical Perspective

Revisions: 4

__
TR24-076
| 10th April 2024
__

Oliver Korten, Toniann Pitassi#### Strong vs. Weak Range Avoidance and the Linear Ordering Principle

__
TR24-075
| 13th April 2024
__

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu#### Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH

Revisions: 1

__
TR24-074
| 11th April 2024
__

Vaibhav Krishan, Sundar Vishwanathan#### Towards ACC Lower Bounds using Torus Polynomials

__
TR24-073
| 11th April 2024
__

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay#### Trading Determinism for Noncommutativity in Edmonds' Problem

__
TR24-072
| 11th April 2024
__

Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch#### Tropical proof systems

Revisions: 1

__
TR24-071
| 10th April 2024
__

Yahel Manor, Or Meir#### Lifting with Inner Functions of Polynomial Discrepancy

__
TR24-070
| 10th April 2024
__

Xinyu Mao, Guangxu Yang, Jiapeng Zhang#### Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing

__
TR24-069
| 8th April 2024
__

Swastik Kopparty, Amnon Ta-Shma, Kedem Yakirevitch#### Character sums over AG codes

__
TR24-068
| 10th April 2024
__

Pravesh Kothari, Peter Manohar#### Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs

__
TR24-067
| 10th April 2024
__

Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang#### Breaking Square-Root Loss Barriers via Min-Entropy

__
TR24-066
| 29th March 2024
__

Siu On Chan, Hiu Tsun Ng, Sijin Peng#### How Random CSPs Fool Hierarchies

Revisions: 1

__
TR24-065
| 6th April 2024
__

Meghal Gupta, Mihir Singhal, Hongxun Wu#### Optimal quantile estimation: beyond the comparison model

__
TR24-064
| 1st April 2024
__

Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami#### No Complete Problem for Constant-Cost Randomized Communication

__
TR24-063
| 6th April 2024
__

Shuichi Hirahara, Mikito Nanashima#### One-Way Functions and Zero Knowledge

__
TR24-062
| 5th April 2024
__

Omar Alrabiah, Venkatesan Guruswami#### Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

Revisions: 1

__
TR24-061
| 5th April 2024
__

Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi#### Improved Lower Bounds for 3-Query Matching Vector Codes

__
TR24-060
| 4th April 2024
__

Lijie Chen, Jiatu Li, Igor Carboni Oliveira#### Reverse Mathematics of Complexity Lower Bounds

__
TR24-059
| 4th April 2024
__

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor Oliveira#### Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity

__
TR24-058
| 29th March 2024
__

Shuichi Hirahara, Nobutaka Shimizu#### Planted Clique Conjectures Are Equivalent

__
TR24-057
| 28th March 2024
__

Xi Chen, Yuhao Li, Mihalis Yannakakis#### Computing a Fixed Point of Contraction Maps in Polynomial Queries

__
TR24-056
| 29th March 2024
__

Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan#### Local Correction of Linear Functions over the Boolean Cube

Revisions: 1

__
TR24-055
| 12th March 2024
__

Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass#### Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement

__
TR24-054
| 13th March 2024
__

Karthik Gajulapalli, Alexander Golovnev, Samuel King#### On the Power of Adaptivity for Function Inversion

__
TR24-053
| 10th March 2024
__

Noam Mazor, Rafael Pass#### Gap MCSP is not (Levin) NP-complete in Obfustopia

Revisions: 1

__
TR24-052
| 15th March 2024
__

Justin Yirka#### Even quantum advice is unlikely to solve PP

Revisions: 1

__
TR24-051
| 5th March 2024
__

Yanyi Liu, Rafael Pass#### A Direct PRF Construction from Kolmogorov Complexity

__
TR24-050
| 5th March 2024
__

Omri Shmueli#### Quantum Algorithms in a Superposition of Spacetimes

Revisions: 1

__
TR24-049
| 7th March 2024
__

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich#### Oblivious Classes Revisited: Lower Bounds and Hierarchies

__
TR24-048
| 4th March 2024
__

Kuan Cheng, Yichuan Wang#### $BPL\subseteq L-AC^1$

__
TR24-047
| 8th March 2024
__

Oded Goldreich#### On the query complexity of testing local graph properties in the bounded-degree graph model

Revisions: 1

__
TR24-046
| 6th March 2024
__

Sasank Mouli#### Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable

__
TR24-045
| 6th March 2024
__

Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria#### Redundancy for MaxSAT

__
TR24-044
| 28th February 2024
__

Rohit Gurjar, Taihei Oki, Roshan Raj#### Fractional Linear Matroid Matching is in quasi-NC

__
TR24-043
| 4th March 2024
__

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk#### Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits

__
TR24-042
| 22nd February 2024
__

Lisa Jaser, Jacobo Toran#### Pebble Games and Algebraic Proof Systems Meet Again

Comments: 1

__
TR24-041
| 1st March 2024
__

Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich#### Launching Identity Testing into (Bounded) Space

__
TR24-040
| 29th February 2024
__

Kuan Cheng, Ruiyang Wu#### Randomness Extractors in $\mathrm{AC}^0$ and $\mathrm{NC}^1$: Optimal up to Constant Factors

Revisions: 1

__
TR24-039
| 20th February 2024
__

Shuichi Hirahara, Naoto Ohsaka#### Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration

__
TR24-038
| 27th February 2024
__

Olaf Beyersdorff, Kaspar Kasche, Luc Nicolas Spachmann#### Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree

__
TR24-037
| 26th February 2024
__

Yaroslav Alekseev, Yuval Filmus, Alexander Smal#### Lifting dichotomies

Revisions: 1

__
TR24-036
| 21st February 2024
__

Tal Yankovitz#### A stronger bound for linear 3-LCC

Revisions: 2

__
TR24-035
| 20th February 2024
__

Sreejata Bhattacharya#### Aaronson-Ambainis Conjecture Is True For Random Restrictions

Revisions: 1

__
TR24-034
| 19th February 2024
__

Bruno Loff, Alexey Milovanov#### The hardness of decision tree complexity

__
TR24-033
| 24th February 2024
__

Sam Buss, Emre Yolcu#### Regular resolution effectively simulates resolution

__
TR24-032
| 22nd February 2024
__

Joshua Cook, Dana Moshkovitz#### Explicit Time and Space Efficient Encoders Exist Only With Random Access

Revisions: 1

__
TR24-031
| 22nd February 2024
__

Daniel Kane, Anthony Ostuni, Kewen Wu#### Locality Bounds for Sampling Hamming Slices

Revisions: 1

__
TR24-030
| 22nd February 2024
__

Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann#### Proof Complexity of Propositional Model Counting

__
TR24-029
| 16th February 2024
__

Noel Arteche, Gaia Carenini, Matthew Gray#### Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard

Revisions: 1

__
TR24-028
| 19th February 2024
__

Ashish Dwivedi, Zeyu Guo, Ben Lee Volk#### Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields

__
TR24-027
| 18th February 2024
__

Dor Minzer, Kai Zhe Zheng#### Near Optimal Alphabet-Soundness Tradeoff PCPs

__
TR24-026
| 15th February 2024
__

Pavel Hrubes#### A subquadratic upper bound on sum-of-squares compostion formulas

Revisions: 1

__
TR24-025
| 13th February 2024
__

Mason DiCicco, Vladimir Podolskii, Daniel Reichman#### Nearest Neighbor Complexity and Boolean Circuits

Revisions: 1

__
TR24-024
| 14th February 2024
__

Changrui Mu, Shafik Nassar, Ron Rothblum, Prashant Nalini Vasudevan#### Strong Batching for Non-Interactive Statistical Zero-Knowledge

__
TR24-023
| 21st January 2024
__

Shuichi Hirahara, Naoto Ohsaka#### Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

__
TR24-022
| 6th February 2024
__

Sreejata Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak#### Exponential Separation Between Powers of Regular and General Resolution Over Parities

Revisions: 1

__
TR24-021
| 29th January 2024
__

Prasad Chaugule, Nutan Limaye#### On the closures of monotone algebraic classes and variants of the determinant

__
TR24-020
| 2nd February 2024
__

Mitali Bafna, Noam Lifshitz, Dor Minzer#### Constant Degree Direct Product Testers with Small Soundness

Revisions: 1

__
TR24-019
| 2nd February 2024
__

Yotam Dikstein, Irit Dinur, Alexander Lubotzky#### Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

Revisions: 1

__
TR24-018
| 28th January 2024
__

Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz#### The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices

__
TR24-017
| 23rd January 2024
__

Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun#### On Pigeonhole Principles and Ramsey in TFNP

__
TR24-016
| 27th January 2024
__

Swagato Sanyal#### Randomized query composition and product distributions

__
TR24-015
| 9th January 2024
__

Harpreet Bedi#### Degree 2 lower bound for Permanent in arbitrary characteristic

__
TR24-014
| 28th January 2024
__

Elette Boyle, Ilan Komargodski, Neekon Vafa#### Memory Checking Requires Logarithmic Overhead

__
TR24-013
| 26th January 2024
__

Oded Goldreich#### On locally-characterized expander graphs (a survey)

Revisions: 1

__
TR24-012
| 26th January 2024
__

Hamed Hatami, Pooya Hatami#### Structure in Communication Complexity and Constant-Cost Complexity Classes

__
TR24-011
| 24th January 2024
__

Paul Beame, Niels Kornerup#### Quantum Time-Space Tradeoffs for Matrix Problems

Revisions: 1

__
TR24-010
| 19th January 2024
__

Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere#### Black-Box PPP is not Turing-Closed

Revisions: 1

__
TR24-009
| 20th January 2024
__

Dmytro Gavinsky#### Unambiguous parity-query complexity

Comments: 1

__
TR24-008
| 17th January 2024
__

Pavel Hrubes#### Hard submatrices for non-negative rank and communication complexity }

Revisions: 1

__
TR24-007
| 25th December 2023
__

Karthik C. S., Pasin Manurangsi#### On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results

Revisions: 1

__
TR24-006
| 14th January 2024
__

Sabee Grewal, Justin Yirka#### The Entangled Quantum Polynomial Hierarchy Collapses

__
TR24-005
| 4th January 2024
__

Daniel Noble, Brett Hemenway, Rafail Ostrovsky#### MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier

Revisions: 1

__
TR24-004
| 7th January 2024
__

Omkar Baraskar, Agrim Dewan, Chandan Saha#### Testing equivalence to design polynomials

__
TR24-003
| 2nd January 2024
__

Noam Mazor, Rafael Pass#### Search-to-Decision Reductions for Kolmogorov Complexity

Revisions: 1

__
TR24-002
| 4th December 2023
__

Takashi Ishizuka#### PLS is contained in PLC

Revisions: 1

__
TR24-001
| 2nd January 2024
__

Sam Buss, Neil Thapen#### A Simple Supercritical Tradeoff between Size and Height in Resolution

Pavel Hrubes, Pushkar Joglekar

We consider read-$k$ determinantal representations of polynomials and prove some non-expressibility results. A square matrix $M$ whose entries are variables or field elements will be called \emph{read-$k$}, if every variable occurs at most $k$ times in $M$. It will be called a \emph{determinantal representation} of a polynomial $f$ if $f=\det(M)$. ... more >>>

Oded Goldreich

The input to the Tree Evaluation problem is a binary tree of height $h$ in which each internal vertex is associated with a function mapping pairs of $\ell$-bit strings to $\ell$-bit strings,and each leaf is assigned an $\ell$-bit string.

The desired output is the value of the root, where ...
more >>>

Vishwas Bhargava, Devansh Shringi

We present a deterministic $2^{k^{\mathcal{O}(1)}} \text{poly}(n,d)$ time algorithm for decomposing $d$-dimensional, width-$n$ tensors of rank at most $k$ over $\mathbb{R}$ and $\mathbb{C}$. This improves upon the previous randomized algorithm of Peleg, Shpilka, and Volk (ITCS '24) that takes $2^{k^{k^{\mathcal{O}(k)}}} \text{poly}(n,d)$ time and the deterministic $n^{k^k}$ time algorithms of Bhargava, Saraf, ... more >>>

Antoine Joux, Anand Kumar Narayanan

We present a new algorithm for solving homogeneous multilinear equations, which are high dimensional generalisations of solving homogeneous linear equations. First, we present a linear time reduction from solving generic homogeneous multilinear equations to computing hyperdeterminants, via a high dimensional Cramer's rule. Hyperdeterminants are generalisations of determinants, associated with tensors ... more >>>

Nader Bshouty

Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities.

More specifically, let $\gamma:{\mathbb R}^+\to ... more >>>

Halley Goldberg, Valentine Kabanets

A central open question within meta-complexity is that of NP-hardness of problems such as MCSP and MK$^t$P. Despite a large body of work giving consequences of and barriers for NP-hardness of these problems under (restricted) deterministic reductions, very little is known in the setting of randomized reductions. In this work, ... more >>>

Vishwas Bhargava, Anamay Tengse

The dimension of partial derivatives (Nisan and Wigderson, 1997) is a popular measure for proving lower bounds in algebraic complexity. It is used to give strong lower bounds on the Waring decomposition of polynomials (called Waring rank). This naturally leads to an interesting open question: does this measure essentially characterize ... more >>>

Amnon Ta-Shma, Ron Zadiario

Numerous works have studied the probability that a length $t-1$ random walk on an expander is confined to a given rectangle $S_1 \times \ldots \times S_t$, providing both upper and lower bounds for this probability.

However, when the densities of the sets $S_i$ may depend on the walk length (e.g., ...
more >>>

Ludmila Glinskih, Artur Riazanov

We show that assuming the Exponential Time Hypothesis, the Partial Minimum Branching Program Size Problem (MBPSP*) requires superpolynomial time. This result also applies to the partial minimization problems for many interesting subclasses of branching programs, such as read-$k$ branching programs and OBDDs.

Combining these results with our recent result (Glinskih ... more >>>

Lijie Chen, Ron D. Rothblum, Roei Tell

A classical challenge in complexity theory and cryptography is to simulate interactive proof systems by non-interactive proof systems. In this work we leverage approaches from recent works in derandomization to address this challenge, focusing on non-interactive simulations that are sound against uniform adversarial algorithms.

Our results concern fundamental questions in ... more >>>

Zhenjian Lu, Igor Oliveira, Hanlin Ren, Rahul Santhanam

We introduce and study the following natural total search problem, which we call the {\it heavy element avoidance} (Heavy Avoid) problem: for a distribution on $N$ bits specified by a Boolean circuit sampling it, and for some parameter $\delta(N) \ge 1/\poly(N)$ fixed in advance, output an $N$-bit string that has ... more >>>

Nir Bitansky, Ron D. Rothblum, Prahladh Harsha, Yuval Ishai, David Wu

A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement $x$ and the proof ${\pi}$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a single dot-product query $\langle {q},({x} \| {\pi})\rangle$ jointly to ${x}$ and ${\pi}$. A DPP can ... more >>>

Nikhil Vyas, Ryan Williams

This paper studies the interaction of oracles with algorithmic approaches to proving circuit complexity lower bounds, establishing new results on two different kinds of questions.

1. We revisit some prominent open questions in circuit lower bounds, and provide a clean way of viewing them as circuit upper bound questions. Let ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent symbol with probability $\epsilon>0$ independently, with only a $1+\mathcal{O}(\sqrt{\H(\epsilon)})$ blowup to the communication. In particular, this ... more >>>

Siddharth Iyer, Anup Rao

We prove a lower bound on the communication complexity of computing the $n$-fold xor of an arbitrary function $f$, in terms of the communication complexity and rank of $f$. We prove that $D(f^{\oplus n}) \geq n \cdot \Big(\frac{\Omega(D(f))}{\log rk(f)} -\log rk(f)\Big )$, where here $D(f), D(f^{\oplus n})$ represent the ... more >>>

Joshua Cook, Dana Moshkovitz

Time efficient decoding algorithms for error correcting codes often require linear space. However, locally decodable codes yield more efficient randomized decoders that run in time $n^{1+o(1)}$ and space $n^{o(1)}$. In this work we focus on deterministic decoding.

Gronemeier showed that any non-adaptive deterministic decoder for a good code running ...
more >>>

Oded Goldreich

The input to the Tree Evaluation problem is a binary tree of height $h$ in which each internal vertex is associated with a function mapping pairs of $\ell$-bit strings to $\ell$-bit strings, and each leaf is assigned an $\ell$-bit string.

The desired output is the value of the root, ...
more >>>

Benny Applebaum, Eliran Kachlon

The problem of minimizing the share size of threshold secret-sharing schemes is a basic research question that has been extensively studied. Ideally, one strives for schemes in which the share size equals the secret size. While this is achievable for large secrets (Shamir, CACM '79), no similar solutions are known ... more >>>

Benjamin Rossman

We study the formula complexity of Iterated Sub-Permutation Matrix Multiplication, the logspace-complete problem of computing the product of $k$ $n$-by-$n$ Boolean matrices with at most a single $1$ in each row and column. For all $d \le \log k$, this problem is solvable by $n^{O(dk^{1/d})}$ size monotone formulas of two ... more >>>

James Cook, Jiatu Li, Ian Mertz, Edward Pyne

In the catalytic logspace ($CL$) model of (Buhrman et.~al.~STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. This ... more >>>

Benny Applebaum, Kaartik Bhushan, Manoj Prabhakaran

In this note, we study the interplay between the communication from a verifier in a general private-coin interactive protocol and the number of random bits it uses in the protocol. Under worst-case derandomization assumptions, we show that it is possible to transform any $I$-round interactive protocol that uses $\rho$ random ... more >>>

Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha

An $s$-sparse polynomial has at most $s$ monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial $f$ is equivalent to (i.e., in the orbit of) some $s$-sparse polynomial. In other words, given $f \in \mathbb{F}[\mathbf{x}]$ and $s \in \mathbb{N}$, ETsparse ... more >>>

Farzan Byramji, Vatsal Jha, Chandrima Kayal, Rajat Mittal

In a recent result, Knop, Lovett, McGuire and Yuan (STOC 2021) proved the log-rank conjecture for communication complexity, up to $\log n$ factor, for any Boolean function composed with $AND$ function as the inner gadget. One of the main tools in this result was the relationship between monotone analogues of ... more >>>

Inbar Ben Yaacov, Yotam Dikstein, Gal Maor

High dimensional expanders (HDXs) are a hypergraph generalization of expander graphs. They are extensively studied in the math and TCS communities due to their many applications. Like expander graphs, HDXs are especially interesting for applications when they are bounded degree, namely, if the number of edges adjacent to every vertex ... more >>>

Or Keret, Ron Rothblum, Prashant Nalini Vasudevan

A sequence of recent works, concluding with Mu et al. (Eurocrypt, 2024) has shown that every problem $\Pi$ admitting a non-interactive statistical zero-knowledge proof (NISZK) has an efficient zero-knowledge batch verification protocol. Namely, an NISZK protocol for proving that $x_1,\dots,x_k \in \Pi$ with communication that only scales poly-logarithmically with $k$. ... more >>>

Changrui Mu, Prashant Nalini Vasudevan

In an Instance-Hiding Interactive Proof (IHIP) [Beaver et al. CRYPTO 90], an efficient verifier with a _private_ input x interacts with an unbounded prover to determine whether x is contained in a language L. In addition to completeness and soundness, the instance-hiding property requires that the prover should not learn ... more >>>

Pavel Hrubes

For every $n$, we construct a sum-of-squares identity

$ (\sum_{i=1}^n x_i^2) (\sum_{j=1}^n y_j^2)= \sum_{k=1}^s f_k^2$,

where $f_k$ are bilinear forms with complex coefficients and $s= O(n^{1.62})$. Previously, such a construction was known with $s=O(n^2/\log n)$.

The same bound holds over any field of positive characteristic.

As an application to ... more >>>

Noga Amit, Orr Paradise, Guy Rothblum, shafi goldwasser

How can we trust the correctness of a learned model on a particular input of interest? Model accuracy is typically measured $on\ average$ over a distribution of inputs, giving no guarantee for any fixed input. This paper proposes a theoretically-founded solution to this problem: to train $Self$-$Proving\ models$ that prove ... more >>>

Zhiyang Xun, David Zuckerman

We present the first efficient averaging sampler that achieves asymptotically optimal randomness complexity and near-optimal sample complexity for natural parameter choices. Specifically, for any constant $\alpha > 0$, for $\delta > 2^{-\mathrm{poly}(1 / \varepsilon)}$, it uses $m + O(\log (1 / \delta))$ random bits to output $t = O(\log(1 ... more >>>

Noga Amit, Guy Rothblum

What are the minimal cryptographic assumptions that suffice for constructing efficient argument systems, and for which tasks? Recently, Amit and Rothblum [STOC 2023] showed that one-way functions suffice for constructing constant-round arguments for bounded-depth computations. In this work we ask: what other tasks have efficient argument systems based only on ... more >>>

Yanyi Liu, Noam Mazor, Rafael Pass

We present a simple alternative exposition of the the recent result of Hirahara and Nanashima (STOC’24) showing that one-way functions exist if (1) every language in NP has a zero-knowledge proof/argument and (2) ZKA contains non-trivial languages. Our presentation does not rely on meta-complexity and we hope it may be ... more >>>

Tal Herman, Guy Rothblum

Suppose Alice has collected a small number of samples from an unknown distribution, and would like to learn about the distribution. Bob, an untrusted data analyst, claims that he ran a sophisticated data analysis on the distribution, and makes assertions about its properties. Can Alice efficiently verify Bob's claims using ... more >>>

Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, Joao Ribeiro

We prove that random low-degree polynomials (over $\mathbb{F}_2$) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, ... more >>>

Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan

For $S\subseteq \mathbb{F}^n$, consider the linear space of restrictions of degree-$d$ polynomials to $S$. The Hilbert function of $S$, denoted $\mathrm{h}_S(d,\mathbb{F})$, is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets $S$ of arbitrary finite grids in $\mathbb{F}^n$ ... more >>>

Dean Doron, Jonathan Mosheiff, Mary Wootters

The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $\varepsilon^2$ has relative distance at least $\frac{1}{2} - O(\varepsilon)$ with high probability. However, it is a major challenge to construct explicit codes with similar parameters.

One hope to ... more >>>

Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz

Error reduction procedures play a crucial role in constructing weighted PRGs [PV'21, CDRST'21], which are central to many recent advances in space-bounded derandomization. The fundamental method driving error reduction procedures is the Richardson iteration, which is adapted from the literature on fast Laplacian solvers. In the context of space-bounded derandomization, ... more >>>

Gil Cohen, Itay Cohen, Gal Maor

The Zig-Zag product of two graphs, $Z = G \circ H$, was introduced in the seminal work of Reingold, Vadhan, and Wigderson (Ann. of Math. 2002) and has since become a pivotal tool in theoretical computer science. The classical bound, which is used throughout, states that the spectral expansion of ... more >>>

Tamer Mour, Alon Rosen, Ron Rothblum

Tree codes, introduced in the seminal works of Schulman (STOC 93', IEEE Transactions on Information Theory 96') are codes designed for interactive communication. Encoding in a tree code is done in an online manner: the $i$-th codeword symbol depends only on the first $i$ message symbols. Codewords should have good ... more >>>

Renato Ferreira Pinto Jr.

This paper explores the connection between classical isoperimetric inequalities, their directed analogues, and monotonicity testing. We study the setting of real-valued functions $f : [0,1]^d \to \mathbb{R}$ on the solid unit cube, where the goal is to test with respect to the $L^p$ distance. Our goals are twofold: to further ... more >>>

Hao Wu

One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a.k.a, the $\mathbf{P}$ versus $\mathbf{NC^1}$ problem. The current best depth lower bound is $(3-o(1))\cdot \log n$, and it is widely open how to prove a super-$3\log n$ depth lower bound. ... more >>>

Zhenjian Lu, Rahul Santhanam

We develop new characterizations of Impagliazzo's worlds Algorithmica, Heuristica and Pessiland by the intractability of conditional Kolmogorov complexity $\mathrm{K}$ and conditional probabilistic time-bounded Kolmogorov complexity $\mathrm{pK}^t$.

In our first set of results, we show that $\mathrm{NP} \subseteq \mathrm{BPP}$ iff $\mathrm{pK}^t(x \mid y)$ can be computed efficiently in the worst case ... more >>>

Vikraman Arvind, Pushkar Joglekar

We study the \emph{noncommutative rank} problem, $\NCRANK$, of computing the rank of matrices with linear entries in $n$ noncommuting variables and the problem of \emph{noncommutative Rational Identity Testing}, $\RIT$, which is to decide if a given rational formula in $n$ noncommuting variables is zero on its domain of definition.

... more >>>

Lijie Chen, Jiatu Li, Igor Carboni Oliveira

We show that there is a constant $k$ such that Buss's intuitionistic theory $\mathbf{IS}^1_2$ does not prove that SAT requires co-nondeterministic circuits of size at least $n^k$. To our knowledge, this is the first unconditional unprovability result in bounded arithmetic in the context of worst-case fixed-polynomial size circuit lower bounds. ... more >>>

Yotam Dikstein, Max Hopkins

We prove optimal concentration of measure for lifted functions on high dimensional expanders (HDX). Let $X$ be a $k$-dimensional HDX. We show for any $i \leq k$ and function $f: X(i) \to [0,1]$:

\[

\Pr_{s \in X(k)}\left[\left|\underset{{t \subseteq s}}{\mathbb{E}}[f(t)] - \mu \right| \geq \varepsilon \right] \leq \exp\left(-\varepsilon^2 \frac{k}{i}\right).

\]

Using ...
more >>>

Sravanthi Chede, Leroy Chew, Anil Shukla

In this paper we present a new proof system framework CLIP (Cumulation Linear Induction Proposition) for propositional model counting. A CLIP proof firstly involves a circuit, calculating the cumulative function (or running count) of models counted up to a point, and secondly a propositional proof arguing for the correctness of ... more >>>

Robert Andrews, Avi Wigderson

We design polynomial size, constant depth (namely, $AC^0$) arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of the discriminant, resultant, Bézout coefficients, squarefree decomposition, and the inversion of structured matrices like Sylvester and Bézout matrices. Our GCD algorithm extends to any ... more >>>

Tuomas Hakoniemi , Nutan Limaye, Iddo Tzameret

Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi JACM 2018) offer a general model for

deriving polynomials in an ideal and refuting unsatisfiable propositional formulas, subsuming most standard propositional proof systems. A major approach for lower bounding the size of IPS refutations is the Functional Lower Bound ...
more >>>

Oded Goldreich

A locally decodable code (LDC) is an error correcting code that allows for recovery of any desired bit in the message based on a constant number of randomly selected bits in the possibly corrupted codeword.

A relaxed LDC requires correct recovery only in case of actual codewords, while requiring that ...
more >>>

Divesh Aggarwal, JinMing Leong, Alexandra Veliche

In this work, we study the worst-case to average-case hardness of the Learning with Errors problem (LWE) under an alternative measure of hardness - the maximum success probability achievable by a probabilistic polynomial-time (PPT) algorithm. Previous works by Regev (STOC 2005), Peikert (STOC 2009), and Brakerski, Peikert, Langlois, Regev, Stehle ... more >>>

Oliver Korten, Toniann Pitassi

In a pair of recent breakthroughs \cite{CHR,Li} it was shown that the classes $S_2^E, ZPE^{NP}$, and $\Sigma_2^E$ require exponential circuit complexity, giving the first unconditional improvements to a classical result of Kannan. These results were obtained by designing a surprising new algorithm for the total search problem Range Avoidance: given ... more >>>

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

The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts that, there is a constant $\varepsilon> 0$ such that for any computable function $f:\mathbb{N}\to\mathbb{N}$, no $f(k)\cdot n^{O(1)}$-time algorithm can, on input a $k$-variable CSP instance with domain size $n$, find an assignment satisfying ... more >>>

Vaibhav Krishan, Sundar Vishwanathan

The class $ACC$ consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with $AND, NOT$ and $MOD_m$ gates, where $m$ is a natural number. At the frontier of our understanding lies a widely believed conjecture asserting that $MAJORITY$ does not belong to $ACC$. The Boolean ... more >>>

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Let $X=X_1\sqcup X_2\sqcup\ldots\sqcup X_k$ be a partitioned set of variables such that the variables in each part $X_i$ are noncommuting but for any $i\neq j$, the variables $x \in X_i$ commute with the variables $x' \in X_j$. Given as input a square matrix $T$ whose entries are linear forms over ... more >>>

Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch

Propositional proof complexity deals with the lengths of polynomial-time verifiable proofs for Boolean tautologies. An abundance of proof systems is known, including algebraic and semialgebraic systems, which work with polynomial equations and inequalities, respectively. The most basic algebraic proof system is based on Hilbert's Nullstellensatz (Beame et al., 1996). Tropical ... more >>>

Yahel Manor, Or Meir

Lifting theorems are theorems that bound the communication complexity

of a composed function $f\circ g^{n}$ in terms of the query complexity

of $f$ and the communication complexity of $g$. Such theorems

constitute a powerful generalization of direct-sum theorems for $g$,

and have seen numerous applications in recent years.

We prove ... more >>>

Xinyu Mao, Guangxu Yang, Jiapeng Zhang

The notion of query-to-communication lifting theorems is a generic framework to convert query lower bounds into two-party communication lower bounds. Though this framework is very generic and beautiful, it has some inherent limitations such as it only applies to lifted functions. In order to address this issue, we propose gadgetless ... more >>>

Swastik Kopparty, Amnon Ta-Shma, Kedem Yakirevitch

The Stepanov-Bombieri proof of the Hasse-Weil bound also gives non-trivial bounds on the bias of character sums over curves with small genus, for any low-degree function $f$ that is not completely biased. For high genus curves, and in particular for curves used in AG codes over constant size fields, the ... more >>>

Pravesh Kothari, Peter Manohar

We give improved lower bounds for binary $3$-query locally correctable codes (3-LCCs) $C \colon \{0,1\}^k \rightarrow \{0,1\}^n$. Specifically, we prove:

(1) If $C$ is a linear design 3-LCC, then $n \geq 2^{(1 - o(1))\sqrt{k} }$. A design 3-LCC has the additional property that the correcting sets for every ...
more >>>

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

Information complexity is one of the most powerful tools to prove information-theoretical lower bounds, with broad applications in communication complexity and streaming algorithms. A core notion in information complexity analysis is the Shannon entropy. Though it has some convenient properties, such as chain rules, Shannon entropy still has inherent limitations. ... more >>>

Siu On Chan, Hiu Tsun Ng, Sijin Peng

Relaxations for the constraint satisfaction problem (CSP) include bounded width, linear program (LP), semidefinite program (SDP), afinfe integer program (AIP), and the combined LP+AIP of Brakensiek, Guruswami, Wrochna, and Živný (SICOMP 2020). Tightening relaxations systematically leads to hierarchies and stronger algorithms. For the LP+AIP hierarchy, a constant level lower bound ... more >>>

Meghal Gupta, Mihir Singhal, Hongxun Wu

Estimating quantiles is one of the foundational problems of data sketching. Given $n$ elements $x_1, x_2, \dots, x_n$ from some universe of size $U$ arriving in a data stream, a quantile sketch estimates the rank of any element with additive error at most $\varepsilon n$. A low-space algorithm solving this ... more >>>

Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami

We prove that the class of communication problems with public-coin randomized constant-cost protocols, called $BPP^0$, does not contain a complete problem. In other words, there is no randomized constant-cost problem $Q \in BPP^0$, such that all other problems $P \in BPP^0$ can be computed by a constant-cost deterministic protocol with ... more >>>

Shuichi Hirahara, Mikito Nanashima

The fundamental theorem of Goldreich, Micali, and Wigderson (J. ACM 1991) shows that the existence of a one-way function is sufficient for constructing computational zero knowledge ($\mathrm{CZK}$) proofs for all languages in $\mathrm{NP}$. We prove its converse, thereby establishing characterizations of one-way functions based on the worst-case complexities of ... more >>>

Omar Alrabiah, Venkatesan Guruswami

We prove that a binary linear code of block length $n$ that is locally correctable with $3$ queries against a fraction $\delta > 0$ of adversarial errors must have dimension at most $O_{\delta}(\log^2 n \cdot \log \log n)$. This is almost tight in view of quadratic Reed-Muller codes being a ... more >>>

Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi

A Matching Vector ($\mathbf{MV}$) family modulo a positive integer $m \ge 2$ is a pair of ordered lists $\mathcal{U} = (\mathbf{u}_1, \cdots, \mathbf{u}_K)$ and $\mathcal{V} = (\mathbf{v}_1, \cdots, \mathbf{v}_K)$ where $\mathbf{u}_i, \mathbf{v}_j \in \mathbb{Z}_m^n$ with the following property: for any $i \in [K]$, the inner product $\langle \mathbf{u}_i, \mathbf{v}_i \rangle ... more >>>

Lijie Chen, Jiatu Li, Igor Carboni Oliveira

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are necessary to prove a given theorem. In this work, we systematically explore the reverse mathematics of complexity lower bounds. We explore reversals in the setting of bounded arithmetic, with Cook's theory $\mathbf{PV}_1$ as the base ... more >>>

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

A search-to-decision reduction is a procedure that allows one to find a solution to a problem from the mere ability to decide when a solution exists. The existence of a search-to-decision reduction for time-bounded Kolmogorov complexity, i.e., the problem of checking if a string $x$ can be generated by a ... more >>>

Shuichi Hirahara, Nobutaka Shimizu

The planted clique conjecture states that no polynomial-time algorithm can find a hidden clique of size $k \ll \sqrt{n}$ in an $n$-vertex Erd\H{o}s--R\'enyi random graph with a $k$-clique planted. In this paper, we prove the equivalence among many (in fact, \emph{most}) variants of planted clique conjectures, such as search ... more >>>

Xi Chen, Yuhao Li, Mihalis Yannakakis

We give an algorithm for finding an $\epsilon$-fixed point of a contraction map $f:[0,1]^k\rightarrow [0,1]^k$ under the $\ell_\infty$-norm with query complexity $O (k^2\log (1/\epsilon ) )$.

more >>>Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan

We consider the task of locally correcting, and locally list-correcting, multivariate linear functions over the domain $\{0,1\}^n$ over arbitrary fields and more generally Abelian groups. Such functions form error-correcting codes of relative distance $1/2$ and we give local-correction algorithms correcting up to nearly $1/4$-fraction errors making $\widetilde{\mathcal{O}}(\log n)$ queries. This ... more >>>

Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass

Only a handful candidates for computational assumptions that imply secure key-agreement protocols (KA) are known, and even fewer are believed to be quantum safe. In this paper, we present a new hardness assumption---the worst-case hardness of a promise problem related to an interactive version of Kolmogorov Complexity.

Roughly speaking, the ...
more >>>

Karthik Gajulapalli, Alexander Golovnev, Samuel King

We study the problem of function inversion with preprocessing where, given a function $f : [N] \to [N]$ and a point $y$ in its image, the goal is to find an $x$ such that $f(x) = y$ using at most $T$ oracle queries to $f$ and $S$ bits of preprocessed ... more >>>

Noam Mazor, Rafael Pass

We demonstrate that under believable cryptographic hardness assumptions, Gap versions of standard meta-complexity problems, such as the Minimum Circuit Size problem (MCSP) and the Minimum Time-Bounded Kolmogorov Complexity problem (MKTP) are not NP-complete w.r.t. Levin (i.e., witness-preserving many-to-one) reductions.

In more detail:

- Assuming the existence of indistinguishability obfuscation, and ...
more >>>

Justin Yirka

We give a corrected proof that if PP $\subseteq$ BQP/qpoly, then the Counting Hierarchy collapses, as originally claimed by [Aaronson, CCC 2006]. This recovers the related unconditional claim that PP does not have circuits of any fixed size $n^k$ even with quantum advice. We do so by proving that YQP*, ... more >>>

Yanyi Liu, Rafael Pass

While classic result in the 1980s establish that one-way functions (OWFs) imply the existence of pseudorandom generators (PRGs) which in turn imply pseudorandom functions (PRFs), the constructions (most notably the one from OWFs to PRGs) is complicated and inefficient.

Consequently, researchers have developed alternative \emph{direct} constructions of PRFs from various ... more >>>

Omri Shmueli

Quantum computers are expected to revolutionize our ability to process information. The advancement from classical to quantum computing is a product of our advancement from classical to quantum physics -- the more our understanding of the universe grows, so does our ability to use it for computation. A natural question ... more >>>

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich

In this work we study oblivious complexity classes. Among our results:

1) For each $k \in \mathbb{N}$, we construct an explicit language $L_k \in O_2P$ that cannot be computed by circuits of size $n^k$.

2) We prove a hierarchy theorem for $O_2TIME$. In particular, for any function $t:\mathbb{N} \rightarrow \mathbb{N}$ ...
more >>>

Kuan Cheng, Yichuan Wang

Whether $BPL=L$ (which is conjectured to be equal), or even whether $BPL\subseteq NL$, is a big open problem in theoretical computer science. It is well known that $L-NC^1\subseteq L\subseteq NL\subseteq L-AC^1$. In this work we will show that $BPL\subseteq L-AC^1$, which was not known before. Our proof is based on ... more >>>

Oded Goldreich

We consider the query complexity of testing local graph properties in the bounded-degree graph model.

A local property is defined in terms of forbidden subgraphs that are augmented by degree information, where the latter account also for neighbors that are not in the subgraph.

Indeed, this formulation yields a generalized ...
more >>>

Sasank Mouli

For every $n >0$, we show the existence of a CNF tautology over $O(n^2)$ variables of width $O(\log n)$ such that it has a Polynomial Calculus Resolution refutation over $\{0,1\}$ variables of size $O(n^3polylog(n))$ but any Polynomial Calculus refutation over $\{+1,-1\}$ variables requires size $2^{\Omega(n)}$. This shows that Polynomial Calculus ... more >>>

Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria

The concept of redundancy in SAT lead to more expressive and powerful proof search techniques, e.g. able to express various inprocessing techniques, and to interesting hierarchies of proof systems [Heule et.al’20, Buss-Thapen’19].

We propose a general way to integrate redundancy rules in MaxSAT, that is we define MaxSAT variants of ...
more >>>

Rohit Gurjar, Taihei Oki, Roshan Raj

The matching and linear matroid intersection problems are solvable in quasi-NC, meaning that there exist deterministic algorithms that run in polylogarithmic time and use quasi-polynomially many parallel processors. However, such a parallel algorithm is unknown for linear matroid matching, which generalizes both of these problems. In this work, we propose ... more >>>

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk

We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial $f$ computed by a constant-depth circuit over rational numbers, and outputs a list $L$ of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of $f$ computable by constant-depth circuits. This ... more >>>

Lisa Jaser, Jacobo Toran

Analyzing refutations of the well known

pebbling formulas we prove some new strong connections between pebble games and algebraic proof system, showing that

there is a parallelism between the reversible, black and black-white pebbling games on one side, and

the three algebraic proof systems NS, MC and ...
more >>>

Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich

In this work, we initiate the study of the space complexity of the Polynomial Identity Testing problem (PIT).

First, we observe that the majority of the existing (time-)efficient ``blackbox'' PIT algorithms already give rise to space-efficient ``whitebox'' algorithms for the respective classes of arithmetic formulas via a space-efficient ...
more >>>

Kuan Cheng, Ruiyang Wu

We study extractors computable in uniform $\mathrm{AC}^0$ and uniform $\mathrm{NC}^1$.

For the $\mathrm{AC}^0$ setting, we give a construction such that for every $k \ge n/ \mathrm{poly} \log n, \eps \ge 2^{-\mathrm{poly} \log n}$, it can extract $(1-\gamma)k$ randomness from an $(n, k)$ source for an arbitrary constant ...
more >>>

Shuichi Hirahara, Naoto Ohsaka

In the Minmax Set Cover Reconfiguration problem, given a set system $\mathcal{F}$ over a universe and its two covers $\mathcal{C}^\mathrm{start}$ and $\mathcal{C}^\mathrm{goal}$ of size $k$, we wish to transform $\mathcal{C}^\mathrm{start}$ into $\mathcal{C}^\mathrm{goal}$ by repeatedly adding or removing a single set of $\mathcal{F}$ while covering the universe in any intermediate state. ... more >>>

Olaf Beyersdorff, Kaspar Kasche, Luc Nicolas Spachmann

We initiate an in-depth proof-complexity analysis of polynomial calculus (Q-PC) for Quantified Boolean Formulas (QBF). In the course of this we establish a tight proof-size characterisation of Q-PC in terms of a suitable circuit model (polynomial decision lists). Using this correspondence we show a size-degree relation for Q-PC, similar in ... more >>>

Yaroslav Alekseev, Yuval Filmus, Alexander Smal

Lifting theorems are used for transferring lower bounds between Boolean function complexity measures. Given a lower bound on a complexity measure $A$ for some function $f$, we compose $f$ with a carefully chosen gadget function $g$ and get essentially the same lower bound on a complexity measure $B$ for the ... more >>>

Tal Yankovitz

A $q$-locally correctable code (LCC) $C:\{0,1\}^k \to \{0,1\}^n$ is a code in which it is possible to correct every bit of a (not too) corrupted codeword by making at most $q$ queries to the word. The cases in which $q$ is constant are of special interest, and so are the ... more >>>

Sreejata Bhattacharya

In an attempt to show that the acceptance probability of a quantum query algorithm making $q$ queries can be well-approximated almost everywhere by a classical decision tree of depth $\leq \text{poly}(q)$, Aaronson and Ambainis proposed the following conjecture: let $f: \{ \pm 1\}^n \rightarrow [0,1]$ be a degree $d$ polynomial ... more >>>

Bruno Loff, Alexey Milovanov

Let $f$ be a Boolean function given as either a truth table or a circuit. How difficult is it to find the decision tree complexity, also known as deterministic query complexity, of $f$ in both cases? We prove that this problem is $NC$-hard and PSPACE-hard, respectively. The second bound is ... more >>>

Sam Buss, Emre Yolcu

Regular resolution is a refinement of the resolution proof system requiring that no variable be resolved on more than once along any path in the proof. It is known that there exist sequences of formulas that require exponential-size proofs in regular resolution while admitting polynomial-size proofs in resolution. Thus, with ... more >>>

Joshua Cook, Dana Moshkovitz

We give the first explicit constant rate, constant relative distance, linear codes with an encoder that runs in time $n^{1 + o(1)}$ and space $\mathop{polylog}(n)$ provided random access to the message. Prior to this work, the only such codes were non-explicit, for instance repeat accumulate codes [DJM98] and the codes ... more >>>

Daniel Kane, Anthony Ostuni, Kewen Wu

Spurred by the influential work of Viola (Journal of Computing 2012), the past decade has witnessed an active line of research into the complexity of (approximately) sampling distributions, in contrast to the traditional focus on the complexity of computing functions.

We build upon and make explicit earlier implicit results of ... more >>>

Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann

Recently, the proof system MICE for the model counting problem #SAT was introduced by Fichte, Hecher and Roland (SAT’22). As demonstrated by Fichte et al., the system MICE can be used for proof logging for state-of-the-art #SAT solvers.

We perform a proof-complexity study of MICE. For this we first simplify ...
more >>>

Noel Arteche, Gaia Carenini, Matthew Gray

We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weakly automate $\mathbf{TC}^0$-Frege. This extends the line of results of Kraí?ek and Pudlák (Information and Computation, 1998), Bonet, Pitassi, and ... more >>>

Ashish Dwivedi, Zeyu Guo, Ben Lee Volk

We construct explicit pseudorandom generators that fool $n$-variate polynomials of degree at most $d$ over a finite field $\mathbb{F}_q$. The seed length of our generators is $O(d \log n + \log q)$, over fields of size exponential in $d$ and characteristic at least $d(d-1)+1$. Previous constructions such as Bogdanov's (STOC ... more >>>

Dor Minzer, Kai Zhe Zheng

We show that for all $\varepsilon>0$, for sufficiently large prime power $q\in\mathbb{N}$, for all $\delta>0$, it is NP-hard to distinguish whether a $2$-Prover-$1$-Round projection game with alphabet size $q$ has value at least $1-\delta$, or value at most $1/q^{1-\varepsilon}$. This establishes a nearly optimal alphabet-to-soundness tradeoff for $2$-query PCPs ... more >>>

Pavel Hrubes

For every $n$, we construct a sum-of-squares identitity

\[ (\sum_{i=1}^n x_i^2) (\sum_{j=1}^n y_j^2)= \sum_{k=1}^s f_k^2\,,\]

where $f_k$ are bilinear forms with complex coefficients and $s= O(n^{1.62})$. Previously, such a construction was known with $s=O(n^2/\log n)$.

The same bound holds over any field of positive characteristic.

Mason DiCicco, Vladimir Podolskii, Daniel Reichman

A nearest neighbor representation of a Boolean function $f$ is a set of vectors (anchors) labeled by $0$ or $1$ such that $f(x) = 1$ if and only if the closest anchor to $x$ is labeled by $1$. This model was introduced by Hajnal, Liu, and Turán (2022), who studied ... more >>>

Changrui Mu, Shafik Nassar, Ron Rothblum, Prashant Nalini Vasudevan

A zero-knowledge proof enables a prover to convince a verifier that $x \in S$, without revealing anything beyond this fact. By running a zero-knowledge proof $k$ times, it is possible to prove (still in zero-knowledge) that $k$ separate instances $x_1,\dots,x_k$ are all in $S$. However, this increases the communication by ... more >>>

Shuichi Hirahara, Naoto Ohsaka

Motivated by the inapproximability of reconfiguration problems, we present a new PCP-type characterization of PSPACE, which we call a probabilistically checkable reconfiguration proof (PCRP): Any PSPACE computation can be encoded into an exponentially long sequence of polynomially long proofs such that every adjacent pair of the proofs differs in at ... more >>>

Sreejata Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak

Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities, is an outstanding problem that has received a lot of attention after its introduction by Raz and Tzamaret (2008). Very recently, Efremenko, Garlik and Itsykson (2023) proved the first exponential lower bounds ... more >>>

Prasad Chaugule, Nutan Limaye

In this paper we prove the following two results.

* We show that for any $C \in {mVF, mVP, mVNP}$, $C = \overline{C}$. Here, $mVF, mVP$, and $mVNP$ are monotone variants of $VF, VP$, and $VNP$, respectively. For an algebraic complexity class $C$, $\overline{C}$ denotes the closure of $C$. ...
more >>>

Mitali Bafna, Noam Lifshitz, Dor Minzer

Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(\sigma) = (f(\sigma_1), \ldots, f(\sigma_k))$ for each $k$-face $\sigma$. In an effort to simplify components of the PCP theorem, Goldreich ... more >>>

Yotam Dikstein, Irit Dinur, Alexander Lubotzky

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work.

Derandomized direct product ... more >>>

Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz

We study the problem of finding multicollisions, that is, the total search problem in which the input is a function $\mathcal{C} : [A] \to [B]$ (represented as a circuit) and the goal is to find $L \leq \lceil A/B \rceil$ distinct elements $x_1,\ldots, x_L \in A$ such that $\mathcal{C}(x_1) = ... more >>>

Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun

The generalized pigeonhole principle says that if tN + 1 pigeons are put into N holes then there must be a hole containing at least t + 1 pigeons. Let t-PPP denote the class of all total NP-search problems reducible to finding such a t-collision of pigeons. We introduce a ... more >>>

Swagato Sanyal

Let R_eps denote randomized query complexity for error probability eps, and R:=R_{1/3}. In this work we investigate whether a perfect composition theorem R(f o g^n)=Omega(R(f).R(g)) holds for a relation f in {0,1}^n * S and a total inner function g:{0,1}^m \to {0, 1}.

Let D^(prod) denote the maximum distributional query ... more >>>

Harpreet Bedi

An elementary proof of quadratic lower bound for determinantal complexity of the permanent in positive characteristic is stated. This is achieved by constructing a sequence of matrices with zero permanent, but the rank of Hessian is bounded below by a degree two polynomial.

more >>>Elette Boyle, Ilan Komargodski, Neekon Vafa

We study the complexity of memory checkers with computational security and prove the first general tight lower bound.

Memory checkers, first introduced over 30 years ago by Blum, Evans, Gemmel, Kannan, and Naor (FOCS '91, Algorithmica '94), allow a user to store and maintain a large memory on a remote ... more >>>

Oded Goldreich

We consider the notion of a local-characterization of an infinite family of unlabeled bounded-degree graphs.

Such a local-characterization is defined in terms of a finite set of (marked) graphs yielding a generalized notion of subgraph-freeness, which extends the standard notions of induced and non-induced subgraph freeness.

We survey the work ... more >>>

Hamed Hatami, Pooya Hatami

Several theorems and conjectures in communication complexity state or speculate that the complexity of a matrix in a given communication model is controlled by a related analytic or algebraic matrix parameter, e.g., rank, sign-rank, discrepancy, etc. The forward direction is typically easy as the structural implications of small complexity often ... more >>>

Paul Beame, Niels Kornerup

We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems---including matrix-vector product, matrix inversion, matrix multiplication and powering---existing ... more >>>

Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere

The complexity class PPP contains all total search problems many-one reducible to the PIGEON problem, where we are given a succinct encoding of a function mapping n+1 pigeons to n holes, and must output two pigeons that collide in a hole. PPP is one of the “original five” syntactically-defined subclasses ... more >>>

Dmytro Gavinsky

We give a lower bound of ?(?n) on the unambiguous randomised parity-query complexity of the approximate majority problem – that is, on the lowest randomised parity-query complexity of any function over {0,1}? whose value is "0" if the Hamming weight of the input is at most n/3, is "1" if ... more >>>

Pavel Hrubes

Given a non-negative real matrix $M$ of non-negative rank at least $r$, can we witness this fact by a small submatrix of $M$? While Moitra (SIAM J. Comput. 2013) proved that this cannot be achieved exactly, we show that such a witnessing is possible approximately: an $m\times n$ matrix always ... more >>>

Karthik C. S., Pasin Manurangsi

The field of combinatorial reconfiguration studies search problems with a focus on transforming one feasible solution into another.

Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some $\varepsilon>0$ such that given as input a $k$-CSP instance (for some constant $k$) over ... more >>>

Sabee Grewal, Justin Yirka

We introduce the entangled quantum polynomial hierarchy $QEPH$ as the class of problems that are efficiently verifiable given alternating quantum proofs that may be entangled with each other. We prove $QEPH$ collapses to its second level. In fact, we show that a polynomial number of alternations collapses to just two. ... more >>>

Daniel Noble, Brett Hemenway, Rafail Ostrovsky

This paper presents the first Distributed Oblivious RAM (DORAM) protocol that achieves sub-logarithmic communication overhead without computational assumptions.

That is, given $n$ $d$-bit memory locations, we present an information-theoretically secure protocol which requires $o(d \cdot \log(n))$ bits of communication per access (when $d = \Omega(\log^2(n)$).

This comes as a surprise, ... more >>>

Omkar Baraskar, Agrim Dewan, Chandan Saha

An $n$-variate polynomial $g$ of degree $d$ is a $(n,d,t)$ design polynomial if the degree of the gcd of every pair of monomials of $g$ is at most $t-1$. The power symmetric polynomial $\mathrm{PSym}_{n,d} := \sum_{i=1}^{n} x^d_i$ and the sum-product polynomial $\mathrm{SP}_{s,d} := \sum_{i=1}^{s}\prod_{j=1}^{d} x_{i,j}$ are instances of design polynomials ... more >>>

Noam Mazor, Rafael Pass

A long-standing open problem dating back to the 1960s is whether there exists a search-to-decision reduction for the time-bounded Kolmogorov complexity problem - that is, the problem of determining whether the length of the shortest time-$t$ program generating a given string $x$ is at most $s$.

In this work, we ... more >>>

Takashi Ishizuka

Recently, Pasarkar, Papadimitriou, and Yannakakis (ITCS 2023) have introduced the new TFNP subclass called PLC that contains the class PPP; they also have proven that several search problems related to extremal combinatorial principles (e.g., Ramsey’s theorem and the Sunflower lemma) belong to PLC. This short paper shows that the class ... more >>>

Sam Buss, Neil Thapen

We describe CNFs in n variables which, over a range of parameters, have small resolution refutations but are such that any small refutation must have height larger than n (even exponential in n), where the height of a refutation is the length of the longest path in it. This is ... more >>>