CAREER: Explicit Combinatorial Constructions, Indexed Data Scheduling, and Their Applications

摘要随机计算自20世纪70年代末出现以来，已成为计算机科学的主要研究领域之一。尽管它看起来增强了能力，但据我们所知，随机性可能不会比决定论提供任何计算优势（超过一个多项式因素）。该项目的第一个目标是研究通过显式组合结构减少计算随机性的问题。本文主要研究空间有界计算中的非随机化问题，重点研究伪随机生成器的构造。特别地，伪随机生成器的构造为恒定宽度-一次分支程序，和差异集的组合矩形将被检查。我们将进一步研究无向图连通性问题的非随机化随机化对数空间算法。同时，我们还将研究树结构有向图模型中连通性问题的一个变体，希望这可以更好地理解非确定性和确定性计算之间的关系。一门关于显式组合结构及其应用的高级主题课程（研究生或本科生）将被设计。本课程的目标是使学生对显式构造的数学基础，以及它们在算法设计和计算复杂性方面的应用有扎实的了解。近年来，无线信道上的移动计算已经成为一项快速发展的技术，并引起了广泛的关注。在这种情况下，通信环境的高度不对称性质给信息传播和检索问题带来了许多新的挑战。索引数据调度是设计数据广播方案，使客户端在空中检索信息时的平均等待时间和能量消耗最小化。该项目的另一个目标是探讨将索引数据调度思想应用于无线移动通信网络中多媒体应用通信协议设计的可能性。

PI: Shiyu ZhouProposal Number: 9985310Institution: U of PennsylvaniaAbstractRandomized computation has become one of the major research fieldsin Computer Science since its emergence in the late 1970's.In spite of its seemingly enhanced power, as far as we know,randomness may not provide any computational advantage (by more than a polynomial factor) over determinism.The first objective of this project is to investigate the issue ofreducing randomness in computation via explicit combinatorial constructions.Derandomization in space-bounded computation is the major subject tostudy here, with the focus on pseudorandom generator constructions.In particular, the constructions of pseudorandom generators for constant-widthread-once branching programs, and of discrepancy sets for combinatorialrectangles are to be examined.Derandomizing the well-known randomized log-space algorithm for undirected graph connectivity problem will be investigated further.In the meantime, a variant of the connectivity problemin the model of directed graphs with tree structures will also be examined,hoping this can provide a better understanding of the relationship between non-deterministic and deterministic computations.An advanced topic course (graduate or undergraduate) on explicitcombinatorial constructions and their applications will be designed.The goal of the course is to enable the students to attain a solidunderstanding of the mathematical foundation of explicitconstructions as well as their applications to algorithm designand computational complexity.Mobile computing over wireless channels has emerged as a rapidly growingtechnology and gained a large amount of attention in recent years.The highly asymmetric nature of the communication environmentin this context gives rise to many new challenges concerning theissues of information dissemination and retrieval. Indexed datascheduling is to design data broadcast schemes thatminimize both the average waiting time and energy consumptionof the clients in retrieving information on air.Another objective of this project is to investigate the possibility of applying the ideas from indexed data schedulingto the design of communication protocols for multimedia applicationsin wireless mobile communication networks.