天空
发表于 2025-3-28 18:03:21
Lower Bounds and Hardness Magnification for Sublinear-Time Shrinking Cellular Automata,y a streaming algorithm of similar complexity, and we identify two different aspects in which SCAs are more restricted than streaming algorithms. We also show there is a language which cannot be accepted by any SCA in . time, even though it admits an .-space streaming algorithm with . update time.
愚笨
发表于 2025-3-28 21:17:15
http://reply.papertrans.cn/24/2339/233821/233821_42.png
并置
发表于 2025-3-29 01:53:09
http://reply.papertrans.cn/24/2339/233821/233821_43.png
MODE
发表于 2025-3-29 03:30:02
Lecture Notes in Computer Sciencehttp://image.papertrans.cn/c/image/233821.jpg
性满足
发表于 2025-3-29 09:07:24
The Chemistry of Metal AlkoxidesWe prove a complexity dichotomy theorem for a class of Holant problems on 3-regular bipartite graphs. Given an arbitrary nonnegative weighted symmetric constraint function ., we prove that the bipartite Holant problem . is . computable in polynomial time . #P-hard. The dichotomy criterion on . is explicit.
concert
发表于 2025-3-29 14:51:23
https://doi.org/10.1007/b113856It is shown that there exists . in E. such that for every . matrix . of rank . we have ., whenever . for a sufficiently small ., and . is large enough. This generalizes recent results which bound below the probability by . or apply to constant-depth circuits.
Electrolysis
发表于 2025-3-29 17:15:25
http://reply.papertrans.cn/24/2339/233821/233821_47.png
粗鄙的人
发表于 2025-3-29 20:46:18
http://reply.papertrans.cn/24/2339/233821/233821_48.png
pericardium
发表于 2025-3-30 00:12:38
http://reply.papertrans.cn/24/2339/233821/233821_49.png
无法取消
发表于 2025-3-30 07:05:07
Upper Bound for Torus Polynomials,We prove that all functions that have low degree torus polynomials approximating them with small error also have . circuits computing them. This serves as a partial converse to the result that all . functions have low degree torus polynomials approximating them with small error, by Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019).