Titlebook: Studies in Complexity and Cryptography; Miscellanea on the I Oded Goldreich Book 2011 Springer-Verlag GmbH Berlin Heidelberg 2011 coding th

变形

Simplified Derandomization of BPP Using a Hitting Set Generatore by a small circuit. A polynomial time hitting-set generator readily implies ., but it is not apparent what this implies for .. Nevertheless, Andreev et al. (ICALP’96, and JACM 1998) showed that a polynomial-time hitting-set generator implies the seemingly stronger conclusion .. We simplify and imp

基因组

On Testing Expansion in Bounded-Degree Graphs eigenvalue bounded above by a given threshold or is far from any graph with such (or related) property..We present a natural algorithm aimed towards achieving the foregoing task. The algorithm is given a (normalized) eigenvalue bound . < 1, oracle access to a bounded-degree .-vertex graph, and two

SOB

Conclave

Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphsresults are inferior to known results (by Trevisan (2001) and Holmerin (2001)), but they are derived using much simpler proofs. Furthermore, these proofs demonstrate the applicability of the FGLSS-reduction in the context of reductions among combinatorial optimization problems.

令人心醉

brachial-plexus

From Logarithmic Advice to Single-Bit Adviceased on an implicit translation technique, which allow to translate separation results for short (say logarithmic) advice (as shown by Barak) into separations for a single-bit advice. In this note, we make this technique explicit, by introducing an adequate translation lemma.

definition

BIAS

A Candidate Counterexample to the Easy Cylinders Conjecture09-019). Loosely speaking, the conjecture asserts that any 1-1 function in .poly can be decomposed into “cylinders” of sub-exponential size that can each be inverted by some polynomial-size circuit. Although all popular one-way functions have such easy (to invert) cylinders, we suggest a possible co