Randomness Complexity
How many random bits a protocol or circuit needs, as a resource to be minimized in its own right.
| Status | Problem | Tags |
|---|---|---|
|
Sources vs Randomness Blowup Conjecture 13 of the source. Its companion question – how many parties must be able to toss coins – is settled exactly by the same paper: \(t\) sources for deterministic functionalities, \(t+1\) for randomized ones, even though the adversary may corrupt all of them. What the count costs is not settled. Both halves of the \(\Theta\) are open. 5 open |
Random SourcesRandomness Complexitytight-bound | |
|
Randomness Complexity of XOR The source proves an \(\Omega(t^2)\) lower bound, matching Kushilevitz and Mansour’s non-explicit \(O(t^2\log(n/t))\) upper bound up to a logarithmic factor, and up to a constant factor when \(t=\Omega(n)\). It also gives an explicit protocol at \(O(t^2\log^2 n)\). It states it leaves the remaining polylogarithmic gaps open. 4 open |
Limited IndependenceRandomness Complexitytight-bound |
No matching items