24 citations · 87 across the 36 of their papers we have counts for
12 papers · 1 filter
The communication complexity of distributed estimation
Parikshit Gopalan, Raghu Meka, Prasad Raghavendra +2
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions and over domains and , respectively. Their…
Degree and Sensitivity: tails of two distributions
Parikshit Gopalan, Rocco Servedio, Avishay Tal +1
The sensitivity of a Boolean function f is the maximum over all inputs x, of the number of sensitive coordinates of x. The well-known sensitivity conjecture of Nisan (see also Nisa…
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
Parikshit Gopalan, Noam Nisan, Rocco A. Servedio +2
A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure…
Pseudorandomness via the discrete Fourier transform
Parikshit Gopalan, Daniel Kane, Raghu Meka
We present a new approach to constructing unconditional pseudorandom generators against classes of functions that involve computing a linear function of the inputs. We give an expl…
Pseudorandomness for concentration bounds and signed majorities
Parikshit Gopalan, Daniel Kane, Raghu Meka
The problem of constructing pseudorandom generators that fool halfspaces has been studied intensively in recent times. For fooling halfspaces over the hypercube with polynomially s…
Inequalities and tail bounds for elementary symmetric polynomial with applications
Parikshit Gopalan, Amir Yehudayoff
We study the extent of independence needed to approximate the product of bounded random variables in expectation, a natural question that has applications in pseudorandomness and m…
Locally Testable Codes and Cayley Graphs
Parikshit Gopalan, Salil Vadhan, Yuan Zhou
We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$: \begin{enumerate} \item A locally testable cod…
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Parikshit Gopalan, Raghu Meka, Omer Reingold +2
We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pse…
DNF Sparsification and a Faster Deterministic Counting Algorithm
Parikshit Gopala, Raghu Meka, Omer Reingold
Given a DNF formula on n variables, the two natural size measures are the number of terms or size s(f), and the maximum width of a term w(f). It is folklore that short DNF formulas…
Making the long code shorter, with applications to the Unique Games Conjecture
Boaz Barak, Parikshit Gopalan, Johan Hastad +3
The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more eff…
Bounded Independence Fools Halfspaces
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal +2
We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps) /\eps^2). Up to logarithmic factors, our result…
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva +1
Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisf…