Source author record

Prahladh Harsha

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms Discrete Mathematics Machine Learning Other Computer Science physics.soc-ph Populations and Evolution Quantitative Methods Artificial Intelligence Computational Geometry math.CO math.PR

Catalog footprint

Research overview

19works

12topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Criticality of $\text{AC}^0$ formulae

Rossman [In $\textit{Proc. $34$th Comput. Complexity Conf.}$, 2019] introduced the notion of $\textit{criticality}$ . The criticality of a Boolean function $f : \{0,1\}^n \to \{0,1\}$ is the minimum $λ\geq 1$ such that for all positive integers $t$ , $\Pr_{ρ\sim \mathcal{R}_p}\left[\text{DT}_{\text{depth}}(f|_ρ) \geq t\right] \leq (pλ)^t.$ Hästad's celebrated switching lemma shows that the criticality of any $k$ -DNF is at most $O(k)$ . Subsequent improvements to correlation bounds of $\text{AC}^0$ -circuits against parity showed that the criticality of any $\text{AC}^0$ - $\textit{circuit}$ of size $S$ and depth $d+1$ is at most $O(\log S)^d$ and any $\textit{regular}$ $\text{AC}^0$ - $\textit{formula}$ of size $S$ and depth $d+1$ is at most $O\left(\frac1d \cdot \log S\right)^d$ . We strengthen these results by showing that the criticality of $\textit{any}$ $\text{AC}^0$ -formula (not necessarily regular) of size $S$ and depth $d+1$ is at most $O\left(\frac1d\cdot {\log S}\right)^d$ , resolving a conjecture due to Rossman. This result also implies Rossman's optimal lower bound on the size of any depth- $d$ $\text{AC}^0$ -formula computing parity [ $\textit{Comput. Complexity, 27(2):209--223, 2018.}$ ]. Our result implies tight correlation bounds against parity, tight Fourier concentration results and improved $\#$ SAT algorithm for $\text{AC}^0$ -formulae.

preprint2022arXiv

A note on the elementary construction of High-Dimensional Expanders of Kaufman and Oppenheim

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 Oppenheim [Proc. 50th ACM Symp. on Theory of Computing (STOC), 2018]. As a bonus, this also yields a simple construction and analysis of standard expanders.

preprint2021arXiv

A Characterization of hard-to-cover CSPs

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]. The covering number of a CSP instance $Φ$ is the smallest number of assignments to the variables of $Φ$ , such that each constraint of $Φ$ is satisfied by at least one of the assignments. We show the following results: 1. Assuming a covering variant of the Unique Games Conjecture, introduced by Dinur and Kol, we show that for every non-odd predicate $P$ over any constant-size alphabet and every integer $K$ , it is NP-hard to approximate the covering number within a factor of $K$ . This yields a complete characterization of CSPs over constant-size alphabets that are hard to cover. 2. For a large class of predicates that are contained in the 2k-LIN predicate, we show that it is quasi-NP-hard to distinguish between instances with covering number at most $2$ and those with covering number at least $Ω(\log\log n)$ . This generalizes and improves the 4-LIN covering hardness result of Dinur and Kol.

preprint2020arXiv

A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet

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-distance-separable (MDS) tree codes using totally-non-singular triangular matrices. In this short note, we give a unified and simpler presentation of Pudlák and Cohen-Haeupler-Schulman's constructions.

preprint2020arXiv

City-Scale Agent-Based Simulators for the Study of Non-Pharmaceutical Interventions in the Context of the COVID-19 Epidemic

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 context of the COVID-19 pandemic and demonstrate the power of the simulator via several exploratory case studies in two metropolises, Bengaluru and Mumbai. Such tools become common-place in any city administration's tool kit in our march towards digital health.

preprint2020arXiv

COVID-19 Epidemic Study II: Phased Emergence From the Lockdown in Mumbai

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 Government of India. The extended lockdown has had significant social and economic consequences and `lockdown fatigue' has likely set in. Phased reopening began from 01 June 2020 onwards. Mumbai, one of the most crowded cities in the world, has witnessed both the largest number of cases and deaths among all the cities in India (41986 positive cases and 1368 deaths as of 02 June 2020). Many tough decisions are going to be made on re-opening in the next few days. In an earlier IISc-TIFR Report, we presented an agent-based city-scale simulator(ABCS) to model the progression and spread of the infection in large metropolises like Mumbai and Bengaluru. As discussed in IISc-TIFR Report 1, ABCS is a useful tool to model interactions of city residents at an individual level and to capture the impact of non-pharmaceutical interventions on the infection spread. In this report we focus on Mumbai. Using our simulator, we consider some plausible scenarios for phased emergence of Mumbai from the lockdown, 01 June 2020 onwards. These include phased and gradual opening of the industry, partial opening of public transportation (modelling of infection spread in suburban trains), impact of containment zones on controlling infections, and the role of compliance with respect to various intervention measures including use of masks, case isolation, home quarantine, etc. The main takeaway of our simulation results is that a phased opening of workplaces, say at a conservative attendance level of 20 to 33\%, is a good way to restart economic activity while ensuring that the city's medical care capacity remains adequate to handle the possible rise in the number of COVID-19 patients in June and July.

preprint2020arXiv

Locally testable codes via high-dimensional expanders

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 few (sublinear, typically constant) number of locations. Such codes form the combinatorial backbone of PCPs. A major open problem is whether there exist LTCs with positive rate, constant relative distance and testable with a constant number of queries. In this paper, we present a new approach towards constructing such LTCs using the machinery of high-dimensional expanders. To this end, we consider the Tanner representation of a code, which is specified by a graph and a base code. Informally, our result states that if this graph is part of a high-dimensional expander then the local testability of the code follows from the local testability of the base code. This work unifies and generalizes the known results on testability of the Hadamard, Reed-Muller and lifted codes on the Subspace Complex, all of which are proved via local self correction. However, unlike previous results, constant rounds of self correction do not suffice as the diameter of the underlying test graph can be logarithmically large in a high-dimensional expander and not constant as in all known earlier results. We overcome this technical hurdle by performing iterative self correction with logarithmically many rounds and tightly controlling the error in each iteration using properties of the high-dimensional expander. Given this result, the missing ingredient towards constructing a constant-query LTC with positive rate and constant relative distance is an instantiation of a base code that interacts well with a constant-degree high-dimensional expander.

preprint2018arXiv

On Polynomial Approximations to ${AC}^0$

We make progress on some questions related to polynomial approximations of ${\rm 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 ${\rm AC}^0$ circuit of size $s$ and depth $d$ has an $\varepsilon$ -error probabilistic polynomial over the reals of degree $(\log (s/\varepsilon))^{O(d)}$ . We improve this upper bound to $(\log s)^{O(d)}\cdot \log(1/\varepsilon)$ , which is much better for small values of $\varepsilon$ . We give an application of this result by using it to resolve a question posed by Tal (ECCC 2014): we show that $(\log s)^{O(d)}\cdot \log(1/\varepsilon)$ -wise independence fools ${\rm AC}^0$ , improving on Tal's strengthening of Braverman's theorem (J. ACM, 2010) that $(\log (s/\varepsilon))^{O(d)}$ -wise independence fools ${\rm AC}^0$ . Up to the constant implicit in the $O(d)$ , our result is tight. As far as we know, this is the first PRG construction for ${\rm AC}^0$ that achieves optimal dependence on the error $\varepsilon$ . We also prove lower bounds on the best polynomial approximations to ${\rm AC}^0$ . We show that any polynomial approximating the ${\rm OR}$ function on $n$ bits to a small constant error must have degree at least $\widetildeΩ(\sqrt{\log n})$ . This result improves exponentially on a recent lower bound demonstrated by Meka, Nguyen, and Vu (arXiv 2015).

preprint2018arXiv

Robust Multiplication-based Tests for Reed-Muller Codes

We consider the following multiplication-based tests to check if a given function $f: \mathbb{F}_q^n\to \mathbb{F}_q$ is a codeword of the Reed-Muller code of dimension $n$ and order $d$ over the finite field $\mathbb{F}_q$ for prime $q$ (i.e., $f$ 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 (i.e., is a codeword of the Reed-Muller code of dimension $n$ and order $(d+ek)$ ). We prove the robust soundness of the above tests for large values of $e$ , answering a question of Dinur and Guruswami [Israel Journal of Mathematics, 209:611-649, 2015]. Previous soundness analyses of these tests were known only for the case when either $e=1$ or $k=1$ . Even for the case $k=1$ and $e>1$ , earlier soundness analyses were not robust. We also analyze a derandomized version of this test, where (for example) the polynomials $P_1,\dots,P_k$ can be the same random polynomial $P$ . This generalizes a result of Guruswami et al. [SIAM J. Comput., 46(1):132-159, 2017]. One of the key ingredients that go into the proof of this robust soundness is an extension of the standard Schwartz-Zippel lemma over general finite fields $\mathbb{F}_q$ , which may be of independent interest.

preprint2017arXiv

Multiplayer parallel repetition for expander games

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 with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are connected in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.

preprint2017arXiv

On polynomial approximations over $\mathbb{Z}/2^k\mathbb{Z}$

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)} \pmod {2^k}$ . We consider the fractional agreement (which we refer to as $γ_{d,k}(F)$ ) of $F_k$ with degree $d$ polynomials from $\mathbb{Z}/2^k\mathbb{Z}[x_1,\ldots,x_n]$ . Our results are the following: - Increasing $k$ can help: We observe that as $k$ increases, $γ_{d,k}(F)$ cannot decrease. We give two kinds of examples where $γ_{d,k}(F)$ actually increases. The first is an infinite family of functions $F$ such that $γ_{2d,2}(F) - γ_{3d-1,1}(F) \geq Ω(1)$ . The second is an infinite family of functions $F$ such that $γ_{d,1}(F)\leq\frac{1}{2}+o(1)$ -- as small as possible -- but $γ_{d,3}(F) \geq \frac{1}{2}+Ω(1)$ . - Increasing $k$ doesn't always help: Adapting a proof of Green [Comput. Complexity, 9(1):16-38, 2000], we show that irrespective of the value of $k$ , the Majority function $\mathrm{Maj}_n$ satisfies $γ_{d,k}(\mathrm{Maj}_n) \leq \frac{1}{2}+\frac{O(d)}{\sqrt{n}}$ . In other words, polynomials over $\mathbb{Z}/2^k\mathbb{Z}$ for large $k$ do not approximate the majority function any better than polynomials over $\mathbb{Z}/2\mathbb{Z}$ . We observe that the model we study subsumes the model of non-classical polynomials in the sense that proving bounds in our model implies bounds on the agreement of non-classical polynomials with Boolean functions. In particular, our results answer questions raised by Bhowmick and Lovett [In Proc. 30th Computational Complexity Conf., pages 72-87, 2015] that ask whether non-classical polynomials approximate Boolean functions better than classical polynomials of the same degree.

preprint2016arXiv

Partition bound is quadratically tight for product distributions

Let $f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ be a 2-party function. For every product distribution $μ$ on $\{0,1\}^n \times \{0,1\}^n$ , we show that $\mathsf{CC}^μ_{0.49}(f) = O\left(\left(\log \mathsf{prt}_{1/8}(f) \cdot \log \log \mathsf{prt}_{1/8}(f)\right)^2\right),$ where $\mathsf{CC}^μ_\varepsilon(f)$ is the distributional communication complexity of $f$ with error at most $\varepsilon$ under the distribution $μ$ and $\mathsf{prt}_{1/8}(f)$ is the {\em partition bound} of $f$ , as defined by Jain and Klauck [{\em Proc. 25th CCC}, 2010]. We also prove a similar bound in terms of $\mathsf{IC}_{1/8}(f)$ , the {\em information complexity} of $f$ , namely, $\mathsf{CC}^μ_{0.49}(f) = O\left(\left(\mathsf{IC}_{1/8}(f) \cdot \log \mathsf{IC}_{1/8}(f)\right)^2\right).$ The latter bound was recently and independently established by Kol [{\em Proc. 48th STOC}, 2016] using a different technique. We show a similar result for query complexity under product distributions. Let $g : \{0,1\}^n \rightarrow \{0,1\}$ be a function. For every bit-wise product distribution $μ$ on $\{0,1\}^n$ , we show that $\mathsf{QC}^μ_{0.49}(g) = O\left(\left( \log \mathsf{qprt}_{1/8}(g) \cdot \log \log\mathsf{qprt}_{1/8}(g) \right)^2 \right),$ where $\mathsf{QC}^μ_{\varepsilon}(g)$ is the distributional query complexity of $f$ with error at most $\varepsilon$ under the distribution $μ$ and $\mathsf{qprt}_{1/8}(g))$ is the {\em query partition bound} of the function $g$ . Partition bounds were introduced (in both communication complexity and query complexity models) to provide LP-based lower bounds for randomized communication complexity and randomized query complexity. Our results demonstrate that these lower bounds are polynomially tight for {\em product} distributions.

preprint2015arXiv

Derandomized Graph Product Results using the Low Degree Long Code

In this paper, we address the question of whether the recent derandomization results obtained by the use of the low-degree long code can be extended to other product settings. We consider two settings: (1) the graph product results of Alon, Dinur, Friedgut and Sudakov [GAFA, 2004] and (2) the "majority is stablest" type of result obtained by Dinur, Mossel and Regev [SICOMP, 2009] and Dinur and Shinkar [In Proc. APPROX, 2010] while studying the hardness of approximate graph coloring. In our first result, we show that there exists a considerably smaller subgraph of $K_3^{\otimes R}$ which exhibits the following property (shown for $K_3^{\otimes R}$ by Alon et al.): independent sets close in size to the maximum independent set are well approximated by dictators. The "majority is stablest" type of result of Dinur et al. and Dinur and Shinkar shows that if there exist two sets of vertices $A$ and $B$ in $K_3^{\otimes R}$ with very few edges with one endpoint in $A$ and another in $B$ , then it must be the case that the two sets $A$ and $B$ share a single influential coordinate. In our second result, we show that a similar "majority is stablest" statement holds good for a considerably smaller subgraph of $K_3^{\otimes R}$ . Furthermore using this result, we give a more efficient reduction from Unique Games to the graph coloring problem, leading to improved hardness of approximation results for coloring.

preprint2015arXiv

Embedding approximately low-dimensional $\ell_2^2$ metrics into $\ell_1$

Goemans showed that any $n$ points $x_1, \dotsc x_n$ in $d$ -dimensions satisfying $\ell_2^2$ triangle inequalities can be embedded into $\ell_{1}$ , with worst-case distortion at most $\sqrt{d}$ . We extend this to the case when the points are approximately low-dimensional, albeit with average distortion guarantees. More precisely, we give an $\ell_{2}^{2}$ -to- $\ell_{1}$ embedding with average distortion at most the stable rank, $\mathrm{sr}(M)$ , of the matrix $M$ consisting of columns $\{x_i-x_j\}_{i<j}$ . Average distortion embedding suffices for applications such as the Sparsest Cut problem. Our embedding gives an approximation algorithm for the \sparsestcut problem on low threshold-rank graphs, where earlier work was inspired by Lasserre SDP hierarchy, and improves on a previous result of the first and third author [Deshpande and Venkat, In Proc. 17th APPROX, 2014]. Our ideas give a new perspective on $\ell_{2}^{2}$ metric, an alternate proof of Goemans' theorem, and a simpler proof for average distortion $\sqrt{d}$ . Furthermore, while the seminal result of Arora, Rao and Vazirani giving a $O(\sqrt{\log n})$ guarantee for Uniform Sparsest Cut can be seen to imply Goemans' theorem with average distortion, our work opens up the possibility of proving such a result directly via a Goemans'-like theorem.

preprint2014arXiv

A strong direct product theorem for the tribes function via the smooth-rectangle bound

The main result of this paper is an optimal strong direct product result for the two-party public-coin randomized communication complexity of the Tribes function. This is proved by providing an alternate proof of the optimal lower bound of Ω(n) for the randomised communication complexity of the Tribes function using the so-called smooth-rectangle bound, introduced by Jain and Klauck [JK10]. The optimal Ω(n) lower bound for Tribes was originally proved by Jayram, Kumar and Sivakumar [JKS03], using a more powerful lower bound technique, namely the information complexity bound. The information complexity bound is known to be at least as strong a lower bound method as the smooth-rectangle bound [KLL+12]. On the other hand, we are not aware of any function or relation for which the smooth-rectangle bound is (asymptotically) smaller than its public-coin randomized communication complexity. The optimal direct product for Tribes is obtained by combining our smooth-rectangle bound for tribes with the strong direct product result of Jain and Yao [JY12] in terms of smooth-rectangle bound.

preprint2012arXiv

An Invariance Principle for Polytopes

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 |Pr [X belongs to P] - Pr [Y belongs to P]| < log^{8/5}k * Delta, where Delta is a parameter that is small for polytopes formed by the intersection of "regular" halfspaces (i.e., halfspaces with low influence). The novelty of our invariance principle is the polylogarithmic dependence on k. Previously, only bounds that were at least linear in k were known. We give two important applications of our main result: (1) A polylogarithmic in k bound on the Boolean noise sensitivity of intersections of k "regular" halfspaces (previous work gave bounds linear in k). (2) A pseudorandom generator (PRG) with seed length O((log n)*poly(log k,1/delta)) that delta-fools all polytopes with k faces with respect to the Gaussian distribution. We also obtain PRGs with similar parameters that fool polytopes formed by intersection of regular halfspaces over the hypercube. Using our PRG constructions, we obtain the first deterministic quasi-polynomial time algorithms for approximately counting the number of solutions to a broad class of integer programs, including dense covering problems and contingency tables.

preprint2012arXiv

Complexity of Inference in Graphical Models

It is well-known that inference in graphical models is hard in the worst case, but tractable for models with bounded treewidth. We ask whether treewidth is the only structural criterion of the underlying graph that enables tractable inference. In other words, is there some class of structures with unbounded treewidth in which inference is tractable? Subject to a combinatorial hypothesis due to Robertson et al. (1994), we show that low treewidth is indeed the only structural restriction that can ensure tractability. Thus, even for the "best case" graph structure, there is no inference algorithm with complexity polynomial in the treewidth.

preprint2010arXiv

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

These are the lecture notes for the DIMACS Tutorial "Limits of Approximation Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building, Rutgers University on 20-21 July, 2009. This tutorial was jointly sponsored by the DIMACS Special Focus on Hardness of Approximation, the DIMACS Special Focus on Algorithmic Foundations of the Internet, and the Center for Computational Intractability with support from the National Security Agency and the National Science Foundation. The speakers at the tutorial were Matthew Andrews, Sanjeev Arora, Moses Charikar, Prahladh Harsha, Subhash Khot, Dana Moshkovitz and Lisa Zhang. The sribes were Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard and Gwen Spencer.

preprint2009arXiv

Bounding the Sensitivity of Polynomial Threshold Functions

We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of polynomial threshold functions. More specifically, for a Boolean function f on n variables equal to the sign of a real, multivariate polynomial of total degree d we prove 1) The average sensitivity of f is at most O(n^{1-1/(4d+6)}) (we also give a combinatorial proof of the bound O(n^{1-1/2^d}). 2) The noise sensitivity of f with noise rate δis at most O(δ^{1/(4d+6)}). Previously, only bounds for the linear case were known. Along the way we show new structural theorems about random restrictions of polynomial threshold functions obtained via hypercontractivity. These structural results may be of independent interest as they provide a generic template for transforming problems related to polynomial threshold functions defined on the Boolean hypercube to polynomial threshold functions defined in Gaussian space.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Prahladh Harsha

Research overview

Is this your work?

19 publications

Criticality of $\text{AC}^0$ formulae

A note on the elementary construction of High-Dimensional Expanders of Kaufman and Oppenheim

A Characterization of hard-to-cover CSPs

A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet

City-Scale Agent-Based Simulators for the Study of Non-Pharmaceutical Interventions in the Context of the COVID-19 Epidemic

COVID-19 Epidemic Study II: Phased Emergence From the Lockdown in Mumbai

Locally testable codes via high-dimensional expanders

On Polynomial Approximations to ${AC}^0$

Robust Multiplication-based Tests for Reed-Muller Codes

Multiplayer parallel repetition for expander games

On polynomial approximations over $\mathbb{Z}/2^k\mathbb{Z}$

Partition bound is quadratically tight for product distributions

Derandomized Graph Product Results using the Low Degree Long Code

Embedding approximately low-dimensional $\ell_2^2$ metrics into $\ell_1$

A strong direct product theorem for the tribes function via the smooth-rectangle bound

An Invariance Principle for Polytopes

Complexity of Inference in Graphical Models

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

Bounding the Sensitivity of Polynomial Threshold Functions

See the researcher in context

Building this map preview

Prahladh Harsha

Research overview

Is this your work?

19 publications

Criticality of AC0\text{AC}^0AC0 formulae

A note on the elementary construction of High-Dimensional Expanders of Kaufman and Oppenheim

A Characterization of hard-to-cover CSPs

A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet

City-Scale Agent-Based Simulators for the Study of Non-Pharmaceutical Interventions in the Context of the COVID-19 Epidemic

COVID-19 Epidemic Study II: Phased Emergence From the Lockdown in Mumbai

Locally testable codes via high-dimensional expanders

On Polynomial Approximations to AC0{AC}^0AC0

Robust Multiplication-based Tests for Reed-Muller Codes

Multiplayer parallel repetition for expander games

On polynomial approximations over Z/2kZ\mathbb{Z}/2^k\mathbb{Z}Z/2kZ

Partition bound is quadratically tight for product distributions

Derandomized Graph Product Results using the Low Degree Long Code

Embedding approximately low-dimensional ℓ22\ell_2^2ℓ22​ metrics into ℓ1\ell_1ℓ1​

A strong direct product theorem for the tribes function via the smooth-rectangle bound

An Invariance Principle for Polytopes

Complexity of Inference in Graphical Models

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

Bounding the Sensitivity of Polynomial Threshold Functions

See the researcher in context

Building this map preview

Criticality of $\text{AC}^0$ formulae

On Polynomial Approximations to ${AC}^0$

On polynomial approximations over $\mathbb{Z}/2^k\mathbb{Z}$

Embedding approximately low-dimensional $\ell_2^2$ metrics into $\ell_1$