All reports by Author Falk Unger:

__
TR10-164
| 4th November 2010
__

Falk Unger#### Better gates can make fault-tolerant computation impossible

Revisions: 1

__
TR10-163
| 3rd November 2010
__

Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin#### Sparse Selfreducible Sets and Nonuniform Lower Bounds

__
TR09-078
| 16th September 2009
__

Falk Unger#### A Probabilistic Inequality with Applications to Threshold Direct-product Theorems

Falk Unger

We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with ... more >>>

Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin

It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in $EXP^{NP}$, or even ... more >>>

Falk Unger

We prove a simple concentration inequality, which is an extension of the Chernoff bound and Hoeffding's inequality for binary random variables. Instead of assuming independence of the variables we use a slightly weaker condition, namely bounds on the co-moments.

This inequality allows us to simplify and strengthen several known ... more >>>