Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

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

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 >>>

TR14-019 | 14th February 2014
Parikshit Gopalan, Amir Yehudayoff

Inequalities and tail bounds for elementary symmetric polynomials

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 >>>

TR13-114 | 24th August 2013
Parikshit Gopalan, Salil Vadhan, Yuan Zhou

Locally Testable Codes and Cayley Graphs

Revisions: 1

We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$:

\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 >>>

TR13-104 | 20th July 2013
Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin

Explicit Maximally Recoverable Codes with Locality

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 >>>

TR12-123 | 28th September 2012
Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

Better pseudorandom generators from milder pseudorandom restrictions

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 >>>

TR12-060 | 16th May 2012
Parikshit Gopalan, Raghu Meka, Omer Reingold

DNF Sparsification and a Faster Deterministic Counting

Revisions: 2

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 >>>

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

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 >>>

TR11-100 | 20th July 2011
Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin

On the Locality of Codeword Symbols

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 >>>

TR10-176 | 15th November 2010
Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

Pseudorandom Generators for Combinatorial Shapes

Revisions: 1

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 >>>

TR10-133 | 20th August 2010
Parikshit Gopalan, Adam Klivans, Raghu Meka

Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs

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 >>>

TR10-074 | 20th April 2010
Parikshit Gopalan, Rocco Servedio

Learning and Lower Bounds for AC$^0$ with Threshold Gates

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 >>>

TR10-012 | 27th January 2010
Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin

Matching Vector Codes

Revisions: 1

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 >>>

TR10-006 | 11th January 2010
YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan

Fooling functions of halfspaces under product distributions

Revisions: 2

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 >>>

TR09-069 | 2nd September 2009
Parikshit Gopalan

A note on Efremenko's Locally Decodable Codes

Revisions: 1

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 >>>

TR09-048 | 29th May 2009
Parikshit Gopalan, Shachar Lovett, Amir Shpilka

On the Complexity of Boolean Functions in Different Characteristics

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 >>>

TR09-037 | 10th April 2009
Parikshit Gopalan

A Fourier-analytic approach to Reed-Muller decoding

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 >>>

TR09-016 | 21st February 2009
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

Bounded Independence Fools Halfspaces

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 >>>

TR08-105 | 26th November 2008
Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra

List Decoding Tensor Products and Interleaved Codes

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 >>>

TR07-089 | 13th September 2007
Parikshit Gopalan, Venkatesan Guruswami

Deterministic Hardness Amplification via Local GMD Decoding

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 >>>

TR07-073 | 3rd August 2007
Parikshit Gopalan, Subhash Khot, Rishi Saket

Hardness of Reconstructing Multivariate Polynomials over Finite Fields

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 >>>

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

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 >>>

TR06-059 | 3rd May 2006
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

New Results for Learning Noisy Parities and Halfspaces

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 >>>

TR05-143 | 29th November 2005
Parikshit Gopalan

Constructing Ramsey Graphs from Boolean Function Representations

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 >>>

TR04-022 | 31st March 2004
Nayantara Bhatnagar, Parikshit Gopalan

The Degree of Threshold Mod 6 and Diophantine Equations

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 >>>

TR03-047 | 22nd June 2003
Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Symmetric Polynomials over Z_m and Simultaneous Communication Protocols

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 >>>

ISSN 1433-8092 | Imprint