19 citations · 19 across the 4 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.AI2015★ 19 cited
New Limits for Knowledge Compilation and Applications to Exact Model Counting
Paul Beame, Vincent Liew
We show new limits on the efficiency of using current techniques to make exact probabilistic inference for large classes of natural problems. In particular we show new lower bounds…
cs.CC2015
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…