All reports by Author Parikshit Gopalan:

__
TR16-069
| 25th April 2016
__

Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson#### Degree and Sensitivity: tails of two distributions

__
TR15-131
| 10th August 2015
__

Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson#### Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions

__
TR14-019
| 14th February 2014
__

Parikshit Gopalan, Amir Yehudayoff#### Inequalities and tail bounds for elementary symmetric polynomials

__
TR13-114
| 24th August 2013
__

Parikshit Gopalan, Salil Vadhan, Yuan Zhou#### Locally Testable Codes and Cayley Graphs

Revisions: 1

__
TR13-104
| 20th July 2013
__

Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin#### Explicit Maximally Recoverable Codes with Locality

__
TR12-123
| 28th September 2012
__

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan#### Better pseudorandom generators from milder pseudorandom restrictions

__
TR12-060
| 16th May 2012
__

Parikshit Gopalan, Raghu Meka, Omer Reingold#### DNF Sparsification and a Faster Deterministic Counting

Revisions: 2

__
TR11-142
| 2nd November 2011
__

Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, Prasad Raghavendra, David Steurer#### Making the long code shorter, with applications to the Unique Games Conjecture

Revisions: 1

__
TR11-100
| 20th July 2011
__

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin#### On the Locality of Codeword Symbols

__
TR10-176
| 15th November 2010
__

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman#### Pseudorandom Generators for Combinatorial Shapes

Revisions: 1

__
TR10-133
| 20th August 2010
__

Parikshit Gopalan, Adam Klivans, Raghu Meka#### Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs

__
TR10-074
| 20th April 2010
__

Parikshit Gopalan, Rocco Servedio#### Learning and Lower Bounds for AC$^0$ with Threshold Gates

__
TR10-012
| 27th January 2010
__

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin#### Matching Vector Codes

Revisions: 1

__
TR10-006
| 11th January 2010
__

YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan#### Fooling functions of halfspaces under product distributions

Revisions: 2

__
TR09-069
| 2nd September 2009
__

Parikshit Gopalan#### A note on Efremenko's Locally Decodable Codes

Revisions: 1

__
TR09-048
| 29th May 2009
__

Parikshit Gopalan, Shachar Lovett, Amir Shpilka#### On the Complexity of Boolean Functions in Different Characteristics

__
TR09-037
| 10th April 2009
__

Parikshit Gopalan#### A Fourier-analytic approach to Reed-Muller decoding

__
TR09-016
| 21st February 2009
__

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola#### Bounded Independence Fools Halfspaces

__
TR08-105
| 26th November 2008
__

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra#### List Decoding Tensor Products and Interleaved Codes

__
TR07-089
| 13th September 2007
__

Parikshit Gopalan, Venkatesan Guruswami#### Deterministic Hardness Amplification via Local GMD Decoding

__
TR07-073
| 3rd August 2007
__

Parikshit Gopalan, Subhash Khot, Rishi Saket#### Hardness of Reconstructing Multivariate Polynomials over Finite Fields

__
TR06-094
| 29th July 2006
__

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou#### The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Revisions: 1

__
TR06-059
| 3rd May 2006
__

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami#### New Results for Learning Noisy Parities and Halfspaces

__
TR05-143
| 29th November 2005
__

Parikshit Gopalan#### Constructing Ramsey Graphs from Boolean Function Representations

__
TR04-022
| 31st March 2004
__

Nayantara Bhatnagar, Parikshit Gopalan#### The Degree of Threshold Mod 6 and Diophantine Equations

__
TR03-047
| 22nd June 2003
__

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton#### Symmetric Polynomials over Z_m and Simultaneous Communication Protocols

Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson

The sensitivity of a Boolean function $f$ is the maximum, over all inputs $x$, of the number of sensitive coordinates of $x$ (namely the number of Hamming neighbors of $x$ with different $f$-value). The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-$s$ Boolean function ... more >>>

Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson

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 of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can ... more >>>

Parikshit Gopalan, Amir Yehudayoff

This paper studies the elementary symmetric polynomials $S_k(x)$ for $x \in \mathbb{R}^n$. We show that if $|S_k(x)|,|S_{k+1}(x)|$ are small for some $k>0$ then $|S_\ell(x)|$ is also small for all $\ell > k$. We use this to prove probability tail bounds for the symmetric polynomials when the inputs are only $t$-wise ... more >>>

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 code is equivalent to a Cayley graph over $\F_2^h$ whose set of generators is significantly larger than $h$ and has no short linear dependencies, but yields a ...
more >>>

Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin

Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, while other (heavy) parity symbols may depend on all data symbols. Local parities allow to quickly recover any single symbol when it is erased, while heavy parities provide tolerance to a large number of simultaneous ... more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near optimal seed-length even in ... more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold

Given a DNF formula $f$ 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 can be made narrow. We prove a converse, showing that narrow formulas can be ... more >>>

Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, Prasad Raghavendra, David Steurer

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 ecient, but can still be used in many of these applications.

Using the new code we obtain exponential improvements over several ...
more >>>

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin

Consider a linear $[n,k,d]_q$ code $\mc{C}.$ We say that that $i$-th coordinate of $\mc{C}$ has locality $r,$ if the value at this coordinate can be recovered from accessing some other $r$ coordinates of $\mc{C}.$ Data storage applications require codes with small

redundancy, low locality for information coordinates, large distance, and ...
more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, small-bias spaces, 0/1 halfspaces, and 0/1 modular sums. A function $f:[m]^n \rightarrow \{0,1\}^n$ is an $(m,n)$-combinatorial shape if there exist sets $A_1,\ldots,A_n \subseteq [m]$ and a symmetric function $h:\{0,1\}^n \rightarrow \{0,1\}$ such that $f(x_1,\ldots,x_n) = h(1_{A_1} (x_1),\ldots,1_{A_n}(x_n))$. Our ... more >>>

Parikshit Gopalan, Adam Klivans, Raghu Meka

We give a deterministic, polynomial-time algorithm for approximately counting the number of {0,1}-solutions to any instance of the knapsack problem. On an instance of length n with total weight W and accuracy parameter eps, our algorithm produces a (1 + eps)-multiplicative approximation in time poly(n,log W,1/eps). We also give algorithms ... more >>>

Parikshit Gopalan, Rocco Servedio

In 2002 Jackson et al. [JKS02] asked whether AC0 circuits augmented with a threshold gate at the output can be efficiently learned from uniform random examples. We answer this question affirmatively by showing that such circuits have fairly strong Fourier concentration; hence the low-degree algorithm of Linial, Mansour and Nisan ... more >>>

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin

An $(r,\delta,\epsilon)$-locally decodable code encodes a $k$-bit message $x$ to an $N$-bit codeword $C(x),$ such that for every $i\in [k],$ the $i$-th message bit can be recovered with probability $1-\epsilon,$ by a randomized decoding procedure that reads only $r$ bits, even if the codeword $C(x)$ is corrupted in up to ... more >>>

YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan

We construct pseudorandom generators that fool functions of halfspaces (threshold functions) under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes ... more >>>

Parikshit Gopalan

Building on work of Yekhanin and Raghavendra, Efremenko recently gave an elegant construction of 3-query LDCs which achieve sub-exponential length unconditionally.In this note, we observe that this construction can be viewed in the framework of Reed-Muller codes.

more >>>Parikshit Gopalan, Shachar Lovett, Amir Shpilka

Every Boolean function on $n$ variables can be expressed as a unique multivariate polynomial modulo $p$ for every prime $p$. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree ... more >>>

Parikshit Gopalan

We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals $1 - 2/q$ over any field $F_q$ where $q > 2$. This confirms a conjecture due to Gopalan, Klivans and Zuckerman for degree $2$. Previously, tight bounds ... more >>>

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

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 matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). Using standard constructions of k-wise ... more >>>

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes.

1)We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one ... more >>>

Parikshit Gopalan, Venkatesan Guruswami

We study the average-case hardness of the class NP against

deterministic polynomial time algorithms. We prove that there exists

some constant $\mu > 0$ such that if there is some language in NP

for which no deterministic polynomial time algorithm can decide L

correctly on a $1- (log n)^{-\mu}$ fraction ...
more >>>

Parikshit Gopalan, Subhash Khot, Rishi Saket

We study the polynomial reconstruction problem for low-degree

multivariate polynomials over finite fields. In the GF[2] version of this problem, we are given a set of points on the hypercube and target values $f(x)$ for each of these points, with the promise that there is a polynomial over GF[2] of ...
more >>>

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions ... more >>>

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise.

Learning of parities under the uniform distribution with random classification noise,also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding ... more >>>

Parikshit Gopalan

Explicit construction of Ramsey graphs or graphs with no large clique or independent set has remained a challenging open problem for a long time. While Erdos's probabilistic argument shows the existence of graphs on 2^n vertices with no clique or independent set of size 2n, the best known explicit constructions ... more >>>

Nayantara Bhatnagar, Parikshit Gopalan

We continue the study of the degree of polynomials representing threshold functions modulo 6 initiated by Barrington, Beigel and Rudich. We use the framework established by the authors relating representations by symmetric polynomials to simultaneous protocols. We show that proving bounds on the degree of Threshold functions is equivalent to ... more >>>

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

We study the problem of representing symmetric Boolean functions as symmetric polynomials over Z_m. We show an equivalence between such

representations and simultaneous communication protocols. Computing a function with a polynomial of degree d modulo m=pq is equivalent to a two player protocol where one player is given the first ...
more >>>