murmur
发表于 2025-3-26 21:55:25
http://reply.papertrans.cn/24/2339/233822/233822_31.png
使苦恼
发表于 2025-3-27 02:05:43
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
发表于 2025-3-27 05:40:12
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
姑姑在炫耀
发表于 2025-3-27 13:20:39
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
发表于 2025-3-27 15:33:49
,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
没花的是打扰
发表于 2025-3-27 20:36:07
http://reply.papertrans.cn/24/2339/233822/233822_36.png
Trochlea
发表于 2025-3-27 22:10:31
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
发表于 2025-3-28 03:04:18
http://reply.papertrans.cn/24/2339/233822/233822_38.png
想象
发表于 2025-3-28 10:11:27
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
粗野
发表于 2025-3-28 11:29:52
http://reply.papertrans.cn/24/2339/233822/233822_40.png