85 citations · 294 across the 35 of their papers we have counts for
31 papers · 1 filter
Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi
Understanding the limits of list-decodability of Reed-Solomon codes has been one of the most important open problems in algebraic coding theory. Recently, Brakensiek, Chen, Putterm…
Deterministic list decoding of Reed-Solomon codes
Soham Chatterjee, Prahladh Harsha, Mrinal Kumar
We show that Reed-Solomon codes of dimension and block length over any finite field can be deterministically list decoded from agreement in tim…
An exposition of recent list-size bounds of FRS Codes
Abhibhav Garg, Prahladh Harsha, Mrinal Kumar +2
In the last year, there have been some remarkable improvements in the combinatorial list-size bounds of Folded Reed Solomon codes and multiplicity codes. Starting from the work on…
An Improved Line-Point Low-Degree Test
Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi +1
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 ``loc…
Criticality of formulae
Prahladh Harsha, Tulasi mohan Molli, Ashutosh Shankar
Rossman [In $\textit{Proc. $34$th Comput. Complexity Conf.}$, 2019] introduced the notion of . The criticality of a Boolean function $f : \{0,1\}^n \to \{0,1\…
Downward Self-Reducibility in TFNP
Prahladh Harsha, Daniel Mitropolsky, Alon Rosen
A problem is \emph{downward self-reducible} if it can be solved efficiently given an oracle that returns solutions for strictly smaller instances. In the decisional landscape, down…
Algorithmizing the Multiplicity Schwartz-Zippel Lemma
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar +1
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…
Explicit SoS lower bounds from high-dimensional expanders
Irit Dinur, Yuval Filmus, Prahladh Harsha +1
We construct an explicit family of 3XOR instances which is hard for levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a…
Locally testable codes via high-dimensional expanders
Yotam Dikstein, Irit Dinur, Prahladh Harsha +1
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 giv…
Rigid Matrices From Rectangular PCPs
Amey Bhangale, Prahladh Harsha, Orr Paradise +1
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…
A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet
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ák's construction of maximum-dista…
On the Probabilistic Degree of OR over the Reals
Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli +1
We study the probabilistic degree over reals of the OR function on variables. For an error parameter in (0,1/3), the -error probabilistic degree of any Boolean function…
List Decoding with Double Samplers
Irit Dinur, Prahladh Harsha, Tali Kaufman +2
We strengthen the notion of "double samplers", first introduced by Dinur and Kaufman [Proc. 58th FOCS, 2017], which are samplers with additional combinatorial properties, and whose…
On Multilinear Forms: Bias, Correlation, and Tensor Rank
Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami +2
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 $G…
Boolean functions on high-dimensional expanders
Yotam Dikstein, Irit Dinur, Yuval Filmus +1
We initiate the study of Boolean function analysis on high-dimensional expanders. We give a random-walk based definition of high-dimensional expansion, which coincides with the ear…
Sparse juntas on the biased hypercube
Irit Dinur, Yuval Filmus, Prahladh Harsha
We give a structure theorem for Boolean functions on the -biased hypercube which are -close to degree in , showing that they are close to sparse juntas. Our structur…
Agreement tests on graphs and hypergraphs
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 agreemen…
On polynomial approximations over
Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan
We study approximation of Boolean functions by low-degree polynomials over the ring . More precisely, given a Boolean function $F:\{0,1\}^n \rightarrow \{…
Robust Multiplication-based Tests for Reed-Muller Codes
Prahladh Harsha, Srikanth Srinivasan
We consider the following multiplication-based tests to check if a given function is a codeword of the Reed-Muller code of dimension and ord…
Multiplayer parallel repetition for expander games
Irit Dinur, Prahladh Harsha, Rakesh Venkat +1
We investigate the value of parallel repetition of one-round games with any number of players . It has been an open question whether an analogue of Raz's Parallel Repetitio…
On Polynomial Approximations to
Prahladh Harsha, Srikanth Srinivasan
We make progress on some questions related to polynomial approximations of . It is known, by works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spiel…
Partition bound is quadratically tight for product distributions
Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan
Let be a 2-party function. For every product distribution on , we show that $$\mathsf{CC}^μ_{0.…
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
Irit Dinur, Prahladh Harsha, Guy Kindler
We show that every language in NP has a PCP verifier that tosses random coins, has perfect completeness, and a soundness error of at most , while maki…
A Characterization of hard-to-cover CSPs
Amey Bhangale, Prahladh Harsha, Girish Varma
We continue the study of the covering complexity of constraint satisfaction problems (CSPs) initiated by Guruswami, Håstad and Sudan [SIAM J. Comp. 2002] and Dinur and Kol [CCC'13]…