85 citations · 294 across the 35 of their papers we have counts for
45 papers
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…
Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
Rohan Goyal, Prahladh Harsha, Mrinal Kumar +1
A recent work of Goyal, Harsha, Kumar and Shankar gave nearly linear time algorithms for the list decoding of Folded Reed-Solomon codes (FRS) and univariate multiplicity codes up t…
Optimal Online Bipartite Matching in Degree-2 Graphs
Amey Bhangale, Arghya Chakraborty, Prahladh Harsha
Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same c…
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…
Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
Rohan Goyal, Prahladh Harsha, Mrinal Kumar +1
We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon codes can be made to run in time. Univariate multiplicity codes a…
Fast Numerical Multivariate Multipoint Evaluation
Sumanta Ghosh, Prahladh Harsha, Simão Herdade +2
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 \emp…
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…
Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes
Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi +1
We study the following natural question on random sets of points in : Given a random set of points , what i…
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…
Mixing of 3-term progressions in Quasirandom Groups
Amey Bhangale, Prahladh Harsha, Sourya Roy
In this note, we show the mixing of three-term progressions in every finite quasirandom groups, fully answering a question of Gowers. More precisely, we show that f…
Ideal-theoretic Explanation of Capacity-achieving Decoding
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar +1
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 decod…
Decoding Multivariate Multiplicity Codes on Product Sets
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar +1
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 Koppart…
COVID-19 Epidemic in Mumbai: Projections, full economic opening, and containment zones versus contact tracing and testing: An Update
Prahladh Harsha, Sandeep Juneja, Daksh Mittal +1
Mumbai, amongst the most densely populated cities in the world, has witnessed the fourth largest number of cases and the largest number of deaths among all the cities in India (as…
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…
City-Scale Agent-Based Simulators for the Study of Non-Pharmaceutical Interventions in the Context of the COVID-19 Epidemic
Shubhada Agrawal, Siddharth Bhandari, Anirban Bhattacharjee +14
We highlight the usefulness of city-scale agent-based simulators in studying various non-pharmaceutical interventions to manage an evolving pandemic. We ground our studies in the c…
COVID-19 Epidemic Study II: Phased Emergence From the Lockdown in Mumbai
Prahladh Harsha, Sandeep Juneja, Preetam Patil +7
The nation-wide lockdown starting 25 March 2020, aimed at suppressing the spread of the COVID-19 disease, was extended until 31 May 2020 in three subsequent orders by the Governmen…
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…
A note on the elementary construction of High-Dimensional Expanders of Kaufman and Oppenheim
Prahladh Harsha, Ramprasad Saptharishi
In this note, we give a self-contained and elementary proof of the elementary construction of spectral high-dimensional expanders using elementary matrices due to Kaufman and Oppen…
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…