All reports by Author Prahladh Harsha:

__
TR24-114
| 12th July 2024
__

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

__
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-182
| 21st November 2023
__

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

__
TR23-033
| 24th March 2023
__

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

Revisions: 1

__
TR22-182
| 16th December 2022
__

Prahladh Harsha, Tulasi mohan Molli, A. Shankar#### Criticality of AC0-Formulae

Revisions: 1

__
TR22-133
| 20th September 2022
__

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

Revisions: 1
,
Comments: 1

__
TR22-075
| 21st May 2022
__

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

Revisions: 1

__
TR21-163
| 19th November 2021
__

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

Revisions: 1

__
TR21-142
| 1st October 2021
__

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

__
TR21-036
| 14th March 2021
__

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

Revisions: 1

__
TR20-179
| 2nd December 2020
__

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan#### Decoding Multivariate Multiplicity Codes on Product Sets

__
TR20-136
| 11th September 2020
__

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani#### Explicit and structured sum of squares lower bounds from high dimensional expanders

__
TR20-075
| 6th May 2020
__

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal#### Rigid Matrices From Rectangular PCPs

Revisions: 2

__
TR20-072
| 5th May 2020
__

Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi#### Locally testable codes via high-dimensional expanders

__
TR20-019
| 19th February 2020
__

Siddharth Bhandari, Prahladh Harsha#### A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet

__
TR19-093
| 15th July 2019
__

Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari#### Improved 3LIN Hardness via Linear Label Cover

__
TR18-207
| 5th December 2018
__

Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan#### On the Probabilistic Degree of OR over the Reals

__
TR18-136
| 1st August 2018
__

Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma#### List Decoding with Double Samplers

Revisions: 1

__
TR18-081
| 20th April 2018
__

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar#### On Multilinear Forms: Bias, Correlation, and Tensor Rank

Revisions: 1

__
TR18-075
| 23rd April 2018
__

Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha#### Boolean function analysis on high-dimensional expanders

Revisions: 4

__
TR17-181
| 26th November 2017
__

Irit Dinur, Yuval Filmus, Prahladh Harsha#### Agreement tests on graphs and hypergraphs

Revisions: 1

__
TR17-180
| 26th November 2017
__

Irit Dinur, Yuval Filmus, Prahladh Harsha#### Low degree almost Boolean functions are sparse juntas

Revisions: 3

__
TR17-013
| 23rd January 2017
__

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan#### On polynomial approximations over $\mathbb{Z}/2^k\mathbb{Z}$

__
TR16-204
| 20th December 2016
__

Prahladh Harsha, Srikanth Srinivasan#### Robust Multiplication-based Tests for Reed-Muller Codes

__
TR16-160
| 26th October 2016
__

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen#### Multiplayer parallel repetition for expander games

Revisions: 1

__
TR16-068
| 28th April 2016
__

Prahladh Harsha, Srikanth Srinivasan#### On Polynomial Approximations to $\mathrm{AC}^0$

Revisions: 1

__
TR15-199
| 7th December 2015
__

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan#### Relaxed partition bound is quadratically tight for product distributions

__
TR15-085
| 23rd May 2015
__

Irit Dinur, Prahladh Harsha, Guy Kindler#### Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition

__
TR13-167
| 28th November 2013
__

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma#### Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

__
TR09-144
| 24th December 2009
__

Prahladh Harsha, Adam Klivans, Raghu Meka#### An Invariance Principle for Polytopes

__
TR09-042
| 5th May 2009
__

Irit Dinur, Prahladh Harsha#### Composition of low-error 2-query PCPs using decodable PCPs

__
TR07-127
| 22nd November 2007
__

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish#### Sound 3-query PCPPs are Long

__
TR06-151
| 10th December 2006
__

Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan#### The communication complexity of correlation

__
TR04-021
| 23rd March 2004
__

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan#### Robust PCPs of Proximity, Shorter PCPs and Applications to Coding

__
TR03-006
| 23rd January 2003
__

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova#### 3CNF Properties are Hard to Test

__
TR03-004
| 24th December 2002
__

Eli Ben-Sasson, Prahladh Harsha#### Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games

__
TR00-061
| 14th August 2000
__

Prahladh Harsha, Madhu Sudan#### Small PCPs with low query complexity

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

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

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

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

Prahladh Harsha, Tulasi mohan Molli, A. Shankar

Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the notion of criticality. The criticality of a Boolean function $f : \{0, 1\}^n\to \{0, 1\}$ is the minimum $\lambda \geq 1$ such that for all positive integers $t$,

\[Pr_{\rho\sim R_p} [\text{DT}_{\text{depth}}(f|_\rho) \geq t] \leq (p\lambda)^t.\]

.

Håstad’s celebrated switching lemma ...
more >>>

Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

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

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

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

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

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan

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

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

We ... more >>>

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

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

Amey Bhangale, Prahladh Harsha, Sourya Roy

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

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

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

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

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these ... more >>>

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

We construct an explicit family of 3XOR instances which is hard for Omega(sqrt(log n)) levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time.

Our construction is based on the high-dimensional expanders devised by Lubotzky, ...
more >>>

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

We introduce a variant of PCPs, that we refer to as *rectangular* PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the *row* of each query and the other determining the *column*.

We ... more >>>

Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi

Locally testable codes (LTC) are error-correcting codes that have a local tester which can distinguish valid codewords from words that are far from all codewords, by probing a given word only at a very small (sublinear, typically constant) number of locations. Such codes form the combinatorial backbone of PCPs. ...
more >>>

Siddharth Bhandari, Prahladh Harsha

Recently, Cohen, Haeupler and Schulman gave an explicit construction of binary tree codes over polylogarithmic-sized output alphabet based on Pudl\'{a}k's construction of maximum-distance-separable (MDS) tree codes using totally-non-singular triangular matrices. In this short note, we give a unified and simpler presentation of Pudl\'{a}k and Cohen-Haeupler-Schulman's constructions.

more >>>Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari

We prove that for every constant $c$ and $\epsilon = (\log n)^{-c}$, there is no polynomial time algorithm that when given an instance of 3LIN with $n$ variables where an $(1 - \epsilon)$-fraction of the clauses are satisfiable, finds an assignment that satisfies at least $(\frac{1}{2} + \epsilon)$-fraction of clauses ... more >>>

Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan

We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $\epsilon$ in (0,1/3), the $\epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials ... more >>>

Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma

We develop the notion of double samplers, first introduced by Dinur and Kaufman [Proc. 58th FOCS, 2017], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders.

We show how double samplers give a generic way of amplifying distance in a way that enables ... more >>>

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

In this paper, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over $GF(2)= \{0,1\}$. We show the following results for multilinear forms and tensors.

1. Correlation bounds : We show that a random $d$-linear ... more >>>

Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha

We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders.

Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse ... more >>>

Irit Dinur, Yuval Filmus, Prahladh Harsha

Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most PCP constructions. In an agreement test, a function is given by an ensemble of local restrictions. The agreement test checks that the restrictions agree when they overlap, and the ... more >>>

Irit Dinur, Yuval Filmus, Prahladh Harsha

Nisan and Szegedy showed that low degree Boolean functions are juntas. Kindler and Safra showed that low degree functions which are *almost* Boolean are close to juntas. Their result holds with respect to $\mu_p$ for every *constant* $p$. When $p$ is allowed to be very small, new phenomena emerge. ... more >>>

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan

We study approximation of Boolean functions by low-degree polynomials over the ring $\mathbb{Z}/2^k\mathbb{Z}$. More precisely, given a Boolean function F$:\{0,1\}^n \rightarrow \{0,1\}$, define its $k$-lift to be F$_k:\{0,1\}^n \rightarrow \{0,2^{k-1}\}$ by $F_k(x) = 2^{k-F(x)}$ (mod $2^k$). We consider the fractional agreement (which we refer to as $\gamma_{d,k}(F)$) of $F_k$ with ... more >>>

Prahladh Harsha, Srikanth Srinivasan

We consider the following multiplication-based tests to check if a given function $f: \mathbb{F}_q^n\to \mathbb{F}_q$ is the evaluation of a degree-$d$ polynomial over $\mathbb{F}_q$ for $q$ prime.

* $\mathrm{Test}_{e,k}$: Pick $P_1,\ldots,P_k$ independent random degree-$e$ polynomials and accept iff the function $fP_1\cdots P_k$ is the evaluation of a degree-$(d+ek)$ polynomial.

... more >>>Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

We investigate the value of parallel repetition of one-round games with any number of players $k\ge 2$. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially ... more >>>

Prahladh Harsha, Srikanth Srinivasan

We make progress on some questions related to polynomial approximations of $\mathrm{AC}^0$. It is known, by works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. $6$th CCC 1991), that any $\mathrm{AC}^0$ circuit of size $s$ and depth $d$ has an $\varepsilon$-error probabilistic polynomial over the reals ... more >>>

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Let $f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ be a 2-party function. For every product distribution $\mu$ on $\{0,1\}^n \times \{0,1\}^n$, we show that $${{CC}}^\mu_{0.49}(f) = O\left(\left(\log {{rprt}}_{1/4}(f) \cdot \log \log {{rprt}}_{1/4}(f)\right)^2\right),$$ where ${{CC}^\mu_\varepsilon(f)$ is the distributional communication complexity with error at most $\varepsilon$ under the distribution $\mu$ and ... more >>>

Irit Dinur, Prahladh Harsha, Guy Kindler

We show that every language in NP has a PCP verifier that tosses $O(\log n)$ random coins, has perfect completeness, and a soundness error of at most $1/poly(n)$, while making at most $O(poly\log\log n)$ queries into a proof over an alphabet of size at most $n^{1/poly\log\log n}$. Previous constructions that ... more >>>

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the “short code” of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results.

In particular, we prove quasi-NP-hardness of the following problems on ... more >>>

Prahladh Harsha, Adam Klivans, Raghu Meka

Let $X$ be randomly chosen from $\{-1,1\}^n$, and let $Y$ be randomly

chosen from the standard spherical Gaussian on $\R^n$. For any (possibly unbounded) polytope $P$

formed by the intersection of $k$ halfspaces, we prove that

$$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k ...
more >>>

Irit Dinur, Prahladh Harsha

The main result of this paper is a simple, yet generic, composition theorem for low error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well-understood only in the constant error regime. Existing composition methods in the low error regime were non-modular (i.e., very much tailored ... more >>>

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

We initiate the study of the tradeoff between the {\em length} of a

probabilistically checkable proof of proximity (PCPP) and the

maximal {\em soundness} that can be guaranteed by a $3$-query

verifier with oracle access to the proof. Our main observation is

that a verifier limited to querying a short ...
more >>>

Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan

We examine the communication required for generating random variables

remotely. One party Alice will be given a distribution D, and she

has to send a message to Bob, who is then required to generate a

value with distribution exactly D. Alice and Bob are allowed

to share random bits generated ...
more >>>

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

We continue the study of the trade-off between the length of PCPs

and their query complexity, establishing the following main results

(which refer to proofs of satisfiability of circuits of size $n$):

We present PCPs of length $\exp(\tildeO(\log\log n)^2)\cdot n$

that can be verified by making $o(\log\log n)$ Boolean queries.

more >>>

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

For a boolean formula \phi on n variables, the associated property

P_\phi is the collection of n-bit strings that satisfy \phi. We prove

that there are 3CNF properties that require a linear number of queries,

even for adaptive tests. This contrasts with 2CNF properties

that are testable with O(\sqrt{n}) ...
more >>>

Eli Ben-Sasson, Prahladh Harsha

We present a simple proof of the bounded-depth Frege lower bounds of

Pitassi et. al. and Krajicek et. al. for the pigeonhole

principle. Our method uses the interpretation of proofs as two player

games given by Pudlak and Buss. Our lower bound is conceptually

simpler than previous ones, and relies ...
more >>>

Prahladh Harsha, Madhu Sudan

Most known constructions of probabilistically checkable proofs (PCPs)

either blow up the proof size by a large polynomial, or have a high

(though constant) query complexity. In this paper we give a

transformation with slightly-super-cubic blowup in proof size, with a

low query complexity. Specifically, the verifier probes the proof ...
more >>>