291 citations · 310 across the 4 of their papers we have counts for
5 papers
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions
Paul Beame, Shayan Oveis Gharan, Xin Yang
We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where…
Worst-Case Optimal Algorithms for Parallel Query Processing
Paul Beame, Paraschos Koutris, Dan Suciu
In this paper, we study the communication complexity for the problem of computing a conjunctive query on a large database in a parallel setting with servers. In contrast to pre…
Finding the Median (Obliviously) with Bounded Space
Paul Beame, Vincent Liew, Mihai Pǎtraşcu
We prove that any oblivious algorithm using space to find the median of a list of integers from requires time . This bound also applies to…
Towards Understanding and Harnessing the Potential of Clause Learning
P. Beame, H. Kautz, A. Sabharwal
Efficient implementations of DPLL with the addition of clause learning are the fastest complete Boolean satisfiability solvers and can handle many significant real-world problems,…
Longest Common Subsequences in Sets of Permutations
Paul Beame, Eric Blais, Dang-Trinh Huynh-Ngoc
The sequence a_1,...,a_m is a common subsequence in the set of permutations S = {p_1,...,p_k} on [n] if it is a subsequence of p_i(1),...,p_i(n) and p_j(1),...,p_j(n) for some dist…