笨重
发表于 2025-3-23 10:42:20
Information Lower Bounds via Self-reducibility: Gap Hamming Distance (GHD) and Inner Product (IP). In our first result we affirm the conjecture that the information cost of GHD : is linear even under the .distribution, which strengthens the Ω(.) bound recently shown by , and answering an open problem from . In our second result we prove
overshadow
发表于 2025-3-23 16:34:31
On the Encoding Invariance of Polynomial Time Computable Distribution Ensemblesness, which is more convenient than previously used polynomial time computable distributions (PComp). The notion of a PISamp distribution is encoding invariant, while PComp distributions are not, if one-way permutations exist. Here we prove that PComp distributions are not encoding invariant under a
Left-Atrium
发表于 2025-3-23 20:53:31
http://reply.papertrans.cn/24/2339/233827/233827_13.png
moratorium
发表于 2025-3-23 23:40:05
Amortized Communication Complexity of an Equality Predicate complexity of this problem is equal to .(.); the computational complexity of the proposed protocol is polynomial in the size of inputs. Our protocol improves the result achieved in 1991 by Feder et al. Our construction is based on two techniques: Nisan’s pseudorandom generator (1992, Nisan) and Smi
是突袭
发表于 2025-3-24 05:26:03
Careful Synchronization of Partial Automata with Restricted Alphabetse finite automata. We obtain a lower bound for the length of the shortest carefully synchronizing words of an automaton with a fixed number of states and a fixed number of letters. In particular, we consider this bound for automata over a binary alphabet. Our results improve previously known bounds.
forthy
发表于 2025-3-24 07:59:06
http://reply.papertrans.cn/24/2339/233827/233827_16.png
1FAWN
发表于 2025-3-24 13:37:01
http://reply.papertrans.cn/24/2339/233827/233827_17.png
FLINT
发表于 2025-3-24 18:38:59
Conference proceedings 2013013. The 29 full papers presented in this volume were carefully reviewed and selected from 52 submissions. In addition the book contains 8 invited lectures. The papers are organized in topical sections on: algorithms; automata; logic and proof complexity; complexity; words and languages; and logic and automata.
Infirm
发表于 2025-3-24 20:22:20
http://reply.papertrans.cn/24/2339/233827/233827_19.png
培养
发表于 2025-3-24 23:56:58
Lecture Notes in Computer Sciencehttp://image.papertrans.cn/c/image/233827.jpg