Sarah R. Allen

activity

20122016

most citedHow to refute a random CSP

8 citations · 18 across the 3 of their papers we have counts for

collaborators

Showing cs.CCShow all

2 papers · 1 filter

cs.CC2015★ 8 cited

How to refute a random CSP

Sarah R. Allen, Ryan O'Donnell, David Witmer

Let $P$ be a $k$ -ary predicate over a finite alphabet. Consider a random CSP $(P)$ instance $I$ over $n$ variables with $m$ constraints. When $m ≫ n$ the instance $I$ will be unsa…

cs.CC2013★ 5 cited

Evaluation of DNF Formulas

Sarah R. Allen, Lisa Hellerstein, Devorah Kletenik +1

Stochastic Boolean Function Evaluation (SBFE) is the problem of determining the value of a given Boolean function $f$ on an unknown input $x$ , when each bit of $x_{i}$ of $x$ can onl…