SHIYU ZHOU Department of Computer and Information Science University of Pennsylvania

---

Research

• Design and Analysis of Data Structures and Algorithms
• Computational Complexity
• Information Theory

Selected Publication

• "An O(log^{4/3}n) Space Algorithm for (s,t)-Connectivity in Undirected Graphs"
  with R. Armoni, A. Ta-Shma, A. Wigderson
  Journal of ACM, 47(2), pp. 294-311, 2000.

• "On Indexed Data Broadcast"
  with S. Khanna
  Journal of Computer and System Sciences, Vol. 60, pp. 575-591, 2000.

• "Linear Time Binary Codes Correcting Localized Erasures"
  with A. Barg
  IEEE Transactions on Information Theory, Vol. 45, No. 7, pp. 2547-2552, November 1999.

• "BP_HSPACE(S) is in DSPACE(S^{3/2})"
  with M. Saks
  Journal of Computer and System Sciences, Vol. 58, No. 2, pp. 376-403, April 1999.

• "Isolation, Matching, and Counting--Uniform and Nonuniform Upper Bounds"
  with E. Allender, K. Reinhardt
  Journal of Computer and System Sciences, Vol. 59, No. 2, pp. 164-181, October 1999.

• "Explicit OR-Dispersers with Polylogarithmic Degree"
  with M. Saks, A. Srinivasan
  Journal of ACM, 45(1), pp. 123 - 154, January, 1998.

• "Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols"
  with M. Saks
  Algorithmica, 30, pp. 418-431, 2001.

• "Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles"
  with R. Armoni, M. Saks, A. Wigderson
  Proc. 37th Symposium on Foundations of Computer Sciencei (FOCS), pp. 412 - 421, 1996.