All reports by Author Raghu Meka:

__
TR21-018
| 20th February 2021
__

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan#### Monotone Branching Programs: Pseudorandomness and Circuit Complexity

Revisions: 1

__
TR20-048
| 16th April 2020
__

Shachar Lovett, Raghu Meka, Jiapeng Zhang#### Improved lifting theorems via robust sunflowers

__
TR18-112
| 5th June 2018
__

Raghu Meka, Omer Reingold, Avishay Tal#### Pseudorandom Generators for Width-3 Branching Programs

Revisions: 1

__
TR15-144
| 1st September 2015
__

Raghu Meka#### Explicit resilient functions matching Ajtai-Linial

Revisions: 1

__
TR14-153
| 14th November 2014
__

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan#### Communication with Imperfectly Shared Randomness

Revisions: 2

__
TR14-147
| 6th November 2014
__

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman#### Rectangles Are Nonnegative Juntas

Revisions: 1

__
TR13-105
| 29th July 2013
__

Raghu Meka, Avi Wigderson#### Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique

Revisions: 1

__
TR13-008
| 7th January 2013
__

Adam Klivans, Raghu Meka#### Moment-Matching Polynomials

__
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

__
TR12-057
| 7th May 2012
__

Russell Impagliazzo, Raghu Meka, David Zuckerman#### Pseudorandomness from Shrinkage

Revisions: 2

__
TR11-142
| 2nd November 2011
__

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

Revisions: 1

__
TR10-183
| 29th November 2010
__

Raghu Meka#### Almost Optimal Explicit Johnson-Lindenstrauss Transformations

Revisions: 2

__
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

__
TR09-144
| 24th December 2009
__

Prahladh Harsha, Adam Klivans, Raghu Meka#### An Invariance Principle for Polytopes

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan

We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state.

We prove that constant-width monotone branching programs of ... more >>>

Shachar Lovett, Raghu Meka, Jiapeng Zhang

Lifting theorems are a generic way to lift lower bounds in query complexity to lower bounds in communication complexity, with applications in diverse areas, such as combinatorial optimization, proof complexity, game theory. Lifting theorems rely on a gadget, where smaller gadgets give stronger lower bounds. However, existing proof techniques are ... more >>>

Raghu Meka, Omer Reingold, Avishay Tal

We construct pseudorandom generators of seed length $\tilde{O}(\log(n)\cdot \log(1/\epsilon))$ that $\epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $\tilde{O}(\log(n) \cdot \mathrm{poly}(1/\epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work ... more >>>

Raghu Meka

A Boolean function on n variables is q-resilient if for any subset of at most q variables, the function is very likely to be determined by a uniformly random assignment to the remaining n-q variables; in other words, no coalition of at most q variables has significant influence on the ... more >>>

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

The communication complexity of many fundamental problems reduces greatly

when the communicating parties share randomness that is independent of the

inputs to the communication task. Natural communication processes (say between

humans) however often involve large amounts of shared correlations among the

communicating players, but rarely allow for perfect sharing of ...
more >>>

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman

We develop a new method to prove communication lower bounds for composed functions of the form $f\circ g^n$ where $f$ is any boolean function on $n$ inputs and $g$ is a sufficiently ``hard'' two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of $f \circ ... more >>>

Raghu Meka, Avi Wigderson

Finding cliques in random graphs and the closely related ``planted'' clique variant, where a clique of size t is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for t = ... more >>>

Adam Klivans, Raghu Meka

We give a new framework for proving the existence of low-degree, polynomial approximators for Boolean functions with respect to broad classes of non-product distributions. Our proofs use techniques related to the classical moment problem and deviate significantly from known Fourier-based methods, which require the underlying distribution to have some product ... 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 >>>

Russell Impagliazzo, Raghu Meka, David Zuckerman

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models ... more >>>

Boaz Barak, Parikshit Gopalan, Johan Håstad, 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 >>>

Raghu Meka

The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms in high dimensional geometry. Most known constructions of linear embeddings that satisfy the Johnson-Lindenstrauss property involve randomness. We address the question of explicitly constructing such embedding families and provide a construction ... 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 >>>

Prahladh Harsha, Adam Klivans, Raghu Meka

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

$$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k ...
more >>>