291 citations · 445 across the 25 of their papers we have counts for
4 papers · 1 filter
Model Counting of Query Expressions: Limitations of Propositional Methods
Paul Beame, Jerry Li, Sudeepa Roy +1
Query evaluation in tuple-independent probabilistic databases is the problem of computing the probability of an answer to a query given independent probabilities of the individual…
Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases
Paul Beame, Jerry Li, Sudeepa Roy +1
The best current methods for exactly computing the number of satisfying assignments, or the satisfying probability, of Boolean formulas can be seen, either directly or indirectly,…
Element Distinctness, Frequency Moments, and Sliding Windows
Paul Beame, Raphael Clifford, Widad Machmouchi
We derive new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistic…
Communication Steps for Parallel Query Processing
Paul Beame, Paraschos Koutris, Dan Suciu
We consider the problem of computing a relational query on a large input database of size , using a large number of servers. The computation is performed in rounds, and…