Titlebook: Computer Science – Theory and Applications; 6th International Co Alexander Kulikov,Nikolay Vereshchagin Conference proceedings 2011 Springe

murmur

使苦恼

Learning Read-Constant Polynomials of Constant Degree Modulo Composites,ass .. They are also precisely the functions computable efficiently by . over fixed and finite nilpotent groups. This class is not known to be learnable in any reasonable learning model. In this paper, we provide a deterministic polynomial time algorithm for learning Boolean functions represented by

Harness

On the Arithmetic Complexity of Euler Function,e derandomization of the Identity Testing problem. Specifically, it is shown that (1) if computing the Euler function over a finite field is hard then computing permanent over the integers is also hard, and (2) if computing any factor of the Euler function over a field is hard then the Identity Test

姑姑在炫耀

Pseudo-random Graphs and Bit Probe Schemes with One-Sided Error,a structure that queries of type “. ∈ .?” can be answered very quickly..H. Buhrman, P.B. Miltersen, J. Radhakrishnan, and S. Venkatesh proposed a bit-probe scheme based on expanders. Their scheme needs space of .(.log.) bits, and requires to read only one randomly chosen bit from the memory to answe

Ligament

,Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandosuch objects with better parameters than explicit constructions do. But the probabilistic method does not give “effective” variants of such theorems, i.e. variants for resource-bounded Kolmogorov complexity. We show that a “naive derandomization” approach of replacing these objects by the output of

没花的是打扰

Trochlea

Faster Polynomial Multiplication via Discrete Fourier Transforms,stest algorithms for this problem and obtain faster algorithms for polynomial multiplication over certain fields which do not support DFTs of large smooth orders. We prove that the famous Schönhage-Strassen’s upper bound cannot be improved over the field of rational numbers if we consider only algor

overrule

想象

Almost ,-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs,e fundamental problem of derandomizing space bounded computations. Such constructions have been known only in the case of width 2 and in very restricted cases of bounded width. In our previous work, we have introduced a so-called richness condition which is, in a certain sense, sufficient for a set

粗野