找回密码
 To register

QQ登录

只需一步,快速开始

扫一扫,访问微社区

Titlebook: Computer Science - Theory and Applications; 8th International Co Andrei A. Bulatov,Arseny M. Shur Conference proceedings 2013 Springer-Verl

[复制链接]
楼主: 要旨
发表于 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 [15], and answering an open problem from [10]. In our second result we prove
发表于 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
发表于 2025-3-23 20:53:31 | 显示全部楼层
发表于 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.
发表于 2025-3-24 07:59:06 | 显示全部楼层
发表于 2025-3-24 13:37:01 | 显示全部楼层
发表于 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.
发表于 2025-3-24 20:22:20 | 显示全部楼层
发表于 2025-3-24 23:56:58 | 显示全部楼层
Lecture Notes in Computer Sciencehttp://image.papertrans.cn/c/image/233827.jpg
 关于派博传思  派博传思旗下网站  友情链接
派博传思介绍 公司地理位置 论文服务流程 影响因子官网 SITEMAP 大讲堂 北京大学 Oxford Uni. Harvard Uni.
发展历史沿革 期刊点评 投稿经验总结 SCIENCEGARD IMPACTFACTOR 派博系数 清华大学 Yale Uni. Stanford Uni.
|Archiver|手机版|小黑屋| 派博传思国际 ( 京公网安备110108008328) GMT+8, 2025-6-28 17:29
Copyright © 2001-2015 派博传思   京公网安备110108008328 版权所有 All rights reserved
快速回复 返回顶部 返回列表