Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Falk Unger:

TR10-164 | 4th November 2010
Falk Unger

Better gates can make fault-tolerant computation impossible

Revisions: 1

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 >>>

TR10-163 | 3rd November 2010
Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin

Sparse Selfreducible Sets and Nonuniform Lower Bounds

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 >>>

TR09-078 | 16th September 2009
Falk Unger

A Probabilistic Inequality with Applications to Threshold Direct-product Theorems

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 >>>

ISSN 1433-8092 | Imprint