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...
“Mirror, mirror, on the wall, who is the fairest of them all?”
The Evil Queen
What is a fair way to assign rooms to several housemates and divide the rent between them? This is not just a theoretical...
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...
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...