All reports in year 2024:

__
TR24-031
| 22nd February 2024
__

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

__
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

__
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

__
TR24-025
| 13th February 2024
__

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

__
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

__
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

__
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)

__
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

__
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 }

__
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

__
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

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 >>>