Vital-Signs
发表于 2025-3-23 13:44:55
0302-9743 Computer Science Symposium in Russia, CSR 2011, held in St. Petersburg, Russia, in June 2011. The 29 papers presented were carefully reviewed and selected from 76 submissions. The scope of topics of the symposium was quite broad and covered basically all areas of the foundations of theoretical compu
确保
发表于 2025-3-23 16:30:59
Conference proceedings 2011 2011. The 29 papers presented were carefully reviewed and selected from 76 submissions. The scope of topics of the symposium was quite broad and covered basically all areas of the foundations of theoretical computer science.
SPER
发表于 2025-3-23 20:10:53
http://reply.papertrans.cn/24/2339/233822/233822_13.png
贞洁
发表于 2025-3-24 00:31:42
Christa Fest,Karl-Julius Schmidtnalogue of Muchnik’s conditional complexity theorem. I.e., for all . and . there exists a program . of least possible length that transforms . to . and is simple conditional on .. Here all programs work in polynomial space and all complexities are measured with logarithmic accuracy instead of polylogarithmic one in the previous work.
一再遛
发表于 2025-3-24 05:17:37
http://reply.papertrans.cn/24/2339/233822/233822_15.png
FOR
发表于 2025-3-24 07:12:19
http://reply.papertrans.cn/24/2339/233822/233822_16.png
Etching
发表于 2025-3-24 12:14:05
http://reply.papertrans.cn/24/2339/233822/233822_17.png
删减
发表于 2025-3-24 17:28:24
A. Patchornik,M. Fridkin,E. Katchalskimples where the latter parameter is bounded whereas the former is not. As main result we show that permanents of matrices of bounded triangular tree-width are efficiently computable. This result holds as well for the Hamiltonian Cycle problem.
fluffy
发表于 2025-3-24 22:13:10
The Equivalence of Sampling and Searching, version. What makes this nontrivial is that the same .. works for every ...As an application, we prove the surprising result that . = ... = .. In other words, classical computers can efficiently sample the output distribution of every quantum circuit, if and only if they can efficiently solve every search problem that quantum computers can solve.
HEED
发表于 2025-3-25 00:02:38
http://reply.papertrans.cn/24/2339/233822/233822_20.png