变形
发表于 2025-4-1 01:54:54
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
基因组
发表于 2025-4-1 08:26:44
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
发表于 2025-4-1 10:34:01
http://reply.papertrans.cn/89/8809/880833/880833_63.png
Conclave
发表于 2025-4-1 17:31:42
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.
令人心醉
发表于 2025-4-1 20:19:38
http://reply.papertrans.cn/89/8809/880833/880833_65.png
brachial-plexus
发表于 2025-4-2 02:37:25
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
发表于 2025-4-2 03:41:10
http://reply.papertrans.cn/89/8809/880833/880833_67.png
BIAS
发表于 2025-4-2 07:37:18
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