enter search term and/or author name
Estimating the Unseen: Improved Estimators for Entropy and Other Properties
Gregory Valiant, Paul Valiant
Article No.: 37
We show that a class of statistical properties of distributions, which includes such practically relevant properties as entropy, the number of distinct elements, and distance metrics between pairs of distributions, can be estimated given a...
Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length
Olivier Bournez, Daniel S. Graça, Amaury Pouly
Article No.: 38
The outcomes of this article are twofold.
Implicit complexity. We provide an implicit characterization of polynomial time computation in terms of ordinary differential equations: we characterize the class P of languages computable in...
The Matching Polytope has Exponential Extension Complexity
Article No.: 41
A popular method in combinatorial optimization is to express polytopes P, which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a...
Communication Steps for Parallel Query Processing
Paul Beame, Paraschos Koutris, Dan Suciu
Article No.: 40
We study the problem of computing conjunctive queries over large databases on parallel architectures without shared storage. Using the structure of such a query q and the skew in the data, we study tradeoffs between the number of...