All reports by Author Gregory Valiant:

__
TR16-078
| 9th May 2016
__

Gregory Valiant, Paul Valiant#### Information Theoretically Secure Databases

__
TR15-126
| 27th July 2015
__

Jacob Steinhardt, Gregory Valiant, Stefan Wager#### Memory, Communication, and Statistical Queries

Revisions: 1

__
TR13-111
| 17th August 2013
__

Gregory Valiant, Paul Valiant#### Instance-by-instance optimal identity testing

__
TR12-006
| 21st January 2012
__

Gregory Valiant#### Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise

Revisions: 2

__
TR10-180
| 18th November 2010
__

Gregory Valiant, Paul Valiant#### Estimating the unseen: A sublinear-sample canonical estimator of distributions

__
TR10-179
| 18th November 2010
__

Gregory Valiant, Paul Valiant#### A CLT and tight lower bounds for estimating entropy

Revisions: 1

Gregory Valiant, Paul Valiant

We introduce the notion of a database system that is information theoretically "secure in between accesses"--a database system with the properties that 1) users can efficiently access their data, and 2) while a user is not accessing their data, the user's information is information theoretically secure to malicious agents, provided ... more >>>

Jacob Steinhardt, Gregory Valiant, Stefan Wager

If a concept class can be represented with a certain amount of memory, can it be efficiently learned with the same amount of memory? What concepts can be efficiently learned by algorithms that extract only a few bits of information from each example? We introduce a formal framework for studying ... more >>>

Gregory Valiant, Paul Valiant

We consider the problem of verifying the identity of a distribution: Given the description of a distribution over a discrete support $p=(p_1,p_2,\ldots,p_n)$, how many samples (independent draws) must one obtain from an unknown distribution, $q$, to distinguish, with high probability, the case that $p=q$ from the case that the total ... more >>>

Gregory Valiant

Given a set of $n$ random $d$-dimensional boolean vectors with the promise that two of them are $\rho$-correlated with each other, how quickly can one find the two correlated vectors? We present a surprising and simple algorithm which, for any constant $\epsilon>0$ runs in (expected) time $d n^{\frac{3 \omega}{4}+\epsilon} poly(\frac{1}{\rho})< ... more >>>

Gregory Valiant, Paul Valiant

We introduce a new approach to characterizing the unobserved portion of a distribution, which provides sublinear-sample additive estimators for a class of properties that includes entropy and distribution support size. Together with the lower bounds proven in the companion paper [29], this settles the longstanding question of the sample complexities ... more >>>

Gregory Valiant, Paul Valiant

We prove two new multivariate central limit theorems; the first relates the sum of independent distributions to the multivariate Gaussian of corresponding mean and covariance, under the earthmover distance matric (also known as the Wasserstein metric). We leverage this central limit theorem to prove a stronger but more specific central ... more >>>