All reports by Author Adam Klivans:

__
TR16-172
| 3rd November 2016
__

William Hoza, Adam Klivans#### Preserving Randomness for Adaptive Algorithms

Revisions: 4

__
TR14-063
| 23rd April 2014
__

Adam Klivans, Pravesh Kothari#### Embedding Hard Learning Problems into Gaussian Space

__
TR13-129
| 17th September 2013
__

Adam Klivans, Pravesh Kothari, Igor Oliveira#### Constructing Hard Functions from Learning Algorithms

Revisions: 1

__
TR13-008
| 7th January 2013
__

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

__
TR12-127
| 3rd October 2012
__

Eshan Chattopadhyay, Adam Klivans, Pravesh Kothari#### An Explicit VC-Theorem for Low-Degree Polynomials

__
TR11-090
| 2nd June 2011
__

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee#### Submodular Functions Are Noise Stable

Revisions: 2

__
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-023
| 23rd February 2010
__

Adam Klivans, Homin Lee, Andrew Wan#### Mansourâ€™s Conjecture is True for Random DNF Formulas

Revisions: 3

__
TR09-144
| 24th December 2009
__

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

__
TR06-057
| 19th April 2006
__

Adam Klivans, Alexander A. Sherstov#### Cryptographic Hardness Results for Learning Intersections of Halfspaces

__
TR05-042
| 15th April 2005
__

Lance Fortnow, Adam Klivans#### Linear Advice for Randomized Logarithmic Space

Revisions: 1

__
TR04-103
| 19th November 2004
__

Lance Fortnow, Adam Klivans#### NP with Small Advice

__
TR98-075
| 9th December 1998
__

Adam Klivans, Dieter van Melkebeek#### Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

William Hoza, Adam Klivans

We introduce the concept of a randomness steward, a tool for saving random bits when executing a randomized estimation algorithm $\mathrm{Est}$ on many adaptively chosen inputs. For each execution, the chosen input to $\mathrm{Est}$ remains hidden from the steward, but the steward chooses the randomness of $\mathrm{Est}$ and, crucially, is ... more >>>

Adam Klivans, Pravesh Kothari

We give the first representation-independent hardness result for agnostically learning halfspaces with respect to the Gaussian distribution. We reduce from the problem of learning sparse parities with noise with respect to the uniform distribution on the hypercube (sparse LPN), a notoriously hard problem in computer science and show that ... more >>>

Adam Klivans, Pravesh Kothari, Igor Oliveira

Fortnow and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class $\mathcal{C} \subseteq P/poly$ of Boolean circuits is exactly learnable with membership and equivalence queries in polynomial-time, then $EXP^{NP} \not \subseteq \mathcal{C}$ (the class $EXP^{NP}$ was subsequently improved to $P$ by Hitchcock and ... 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 >>>

Eshan Chattopadhyay, Adam Klivans, Pravesh Kothari

Let $X \subseteq \mathbb{R}^{n}$ and let ${\mathcal C}$ be a class of functions mapping $\mathbb{R}^{n} \rightarrow \{-1,1\}.$ The famous VC-Theorem states that a random subset $S$ of $X$ of size $O(\frac{d}{\epsilon^{2}} \log \frac{d}{\epsilon})$, where $d$ is the VC-Dimension of ${\mathcal C}$, is (with constant probability) an $\epsilon$-approximation for ${\mathcal C}$ ... more >>>

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee

We show that all non-negative submodular functions have high noise-stability. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to any product distribution on $\{-1,1\}^n$ (for any constant accuracy parameter $\epsilon$ ). Our algorithm also succeeds in the agnostic setting. Previous work on learning submodular ... 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 >>>

Adam Klivans, Homin Lee, Andrew Wan

In 1994, Y. Mansour conjectured that for every DNF formula on $n$ variables with $t$ terms there exists a polynomial $p$ with $t^{O(\log (1/\epsilon))}$ non-zero coefficients such that $\E_{x \in \{0,1\}}[(p(x)-f(x))^2] \leq \epsilon$. We make the first progress on this conjecture and show that it is true for several natural ... 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 >>>

Adam Klivans, Alexander A. Sherstov

We give the first representation-independent hardness results for

PAC learning intersections of halfspaces, a central concept class

in computational learning theory. Our hardness results are derived

from two public-key cryptosystems due to Regev, which are based on the

worst-case hardness of well-studied lattice problems. Specifically, we

prove that a polynomial-time ...
more >>>

Lance Fortnow, Adam Klivans

We show that RL is contained in L/O(n), i.e., any language computable

in randomized logarithmic space can be computed in deterministic

logarithmic space with a linear amount of non-uniform advice. To

prove our result we show how to take an ultra-low space walk on

the Gabber-Galil expander graph.

Lance Fortnow, Adam Klivans

We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP in NP/log if and only if EXP = P^NP|| (polynomial time with non-adaptive queries to SAT). Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in ... more >>>

Adam Klivans, Dieter van Melkebeek

We establish hardness versus randomness trade-offs for a

broad class of randomized procedures. In particular, we create efficient

nondeterministic simulations of bounded round Arthur-Merlin games using

a language in exponential time that cannot be decided by polynomial

size oracle circuits with access to satisfiability. We show that every

language with ...
more >>>