Name
Abstract | ||
|---|---|---|
We improve the main result of Brody and Verbin from FOCS 2010 on the power of constant-width branching programs to distinguish product distributions. Specifically, we show that a coin must have bias at least O(1/log(n)^{w-2}) to be distinguishable from a fair coin by a width w, length n read-once branching program (for each constant w), which is a tight bound. Our result introduces new techniques, in particular a novel 'interwoven hybrid' technique and a 'program randomization' technique, both of which play crucial roles in our proof. Using the same techniques, we also succeed in giving tight upper bounds on the maximum influence of monotone functions computable by width w read-once branching programs. © 2013 IEEE. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/CCC.2013.33 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
computational indistinguishability,product distributions,read-once branching programs,theorem proving,random variables,product distribution,upper bound,probability distribution,computational complexity,indexes | Discrete mathematics,Combinatorics,Fair coin,Random variable,Computational indistinguishability,Upper and lower bounds,Automated theorem proving,Binary decision diagram,Probability distribution,Monotone polygon,Mathematics | Conference |
Volume | Issue | ISSN |
null | null | 1093-0159 |
Citations | PageRank | References |
5 | 0.45 | 10 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| John P. Steinberger | 1 | 329 | 18.30 |