All reports by Author Paul Valiant:

__
TR16-078
| 9th May 2016
__

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

__
TR13-111
| 17th August 2013
__

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

__
TR11-089
| 7th June 2011
__

Paul Valiant#### Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions

Revisions: 1

__
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

__
TR10-027
| 28th February 2010
__

Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant#### Testing monotonicity of distributions over general partial orders

__
TR07-135
| 26th December 2007
__

Paul Valiant, Paul Valiant#### Testing Symmetric Properties of Distributions

__
TR07-135
| 26th December 2007
__

Paul Valiant, Paul Valiant#### Testing Symmetric Properties of Distributions

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

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

Paul Valiant

We formulate a notion of evolvability for functions with domain and range that are real-valued vectors, a compelling way of expressing many natural biological processes. We show that linear and fixed degree polynomial functions are evolvable in the following dually robust sense: There is a single evolution algorithm that for ... 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 >>>

Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant

We investigate the number of samples required for testing the monotonicity of a distribution with respect to an arbitrary underlying partially ordered set. Our first result is a nearly linear lower bound for the sample complexity of testing monotonicity with respect to the poset consisting of a directed perfect matching. ... more >>>

Paul Valiant, Paul Valiant

We introduce the notion of a Canonical Tester for a class of properties, that is, a tester strong and

general enough that ``a property is testable if and only if the

Canonical Tester tests it''. We construct a Canonical Tester

for the class of symmetric properties of one or two

more >>>

Paul Valiant, Paul Valiant

general enough that ``a property is testable if and only if the

Canonical Tester tests it''. We construct a Canonical Tester

for the class of symmetric properties of one or two

more >>>