Selected Publications of the Theory of Computation Group

• An n! Lower Bound On Formula Size, Micah Adler and N. Immerman, LICS '01, 197-206. (Abstract.html)

• New Protocols for Asymmetric Communication Channels. John Watkinson, Micah Adler, and Faith Fich, in Proceedings of 8th International Colloquium on Structural Information and Communication Complexity (Sirocco) 2001.

• Division is in Uniform TC⁰.William Hesse. Proceedings of the Twenty - Eighth International Colloquium on Automata, Languages and Programming (ICALP 2001).

• Uniform Circuits for Division: Consequences and Problems. Eric Allender, David A. Mix Barrington, William Hesse. Proceedings of the Sixteenth Annual IEEE Conference on Computational Complexity (CCC 2001).

• The Dynamic Complexity of Transitive Closure is in TC⁰. William Hesse, Proceedings of the Eighth International Conference on Database Theory (ICDT 2001).

• Tight Size Bounds for Packet Headers in Narrow Meshes. Micah Adler, Faith Fich, Leslie Ann Goldberg, and Mike Paterson, in Proceedings of 27th International Colloquium on Automata, Languages and Programming (ICALP) 2000.

• Pricing Multicasting in More Practical Network Models. Micah Adler and Dan Rubenstein, in Proceedings of 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2002.

• Tree Layout for Internal Network Characterizations in Multicast Networks Micah Adler, Tian Bu, Ramesh Sitaraman, and Don Towsley, in Proceedings of 3rd International Workshop on Networked Group Communication (NGC) 2001.

• Channelization Problem in Large Scale Data Dissemination Micah Adler, Zihui Ge, James Kurose, Don Towsley, and Stephen Zabele, in Proceedings of the 9th IEEE International Conference on Network Protocols (ICNP) 2001.

• Compression Using Efficient Multicasting Micah Adler and Tom Leighton, in Proceedings of 32nd ACM Symposium on Theory of Computing (STOC) 2000.

• Towards Compressing Web Graphs Micah Adler, Michael Mitzenmacher, in Proceedings of the IEEE Data Compression Conference (DCC), 2001.

• Deadline Fair Scheduling: Bridging the Theory and Practice of Proportionate-Fair Scheduling in Multiprocessor Servers Abhishek Chandra, Micah Adler, and Prashant Shenoy, in Proceedings of IEEE Real-time Technology and Applications Symposium (RTAS), 2001.

• Surplus Fair Scheduling: A Proportional-Share CPU Scheduling Algorithm for Symmetric Multiprocessors Abhishek Chandra, Micah Adler, Pawan Goyal and Prashant Shenoy, in Proceedings of the Fourth Symposium on Operating System Design and Implementation (OSDI) 2000.

• The Crane Beach Conjecture, D.M. Barrington, N. Immerman, Clemens Lautemann, Nicole Schweikardt, and Denis Thérien, LICS '01, 187-196. (Abstract.html)

• On the Unusual Effectiveness of Logic in Computer Science, J. Halpern , R. Harper , N. Immerman, Ph. Kolaitis, M. Vardi, and, V. Vianu, Bulletin of Symbolic Logic. 7(2) (2001), 213-236.

• Number of Variables Is Equivalent To Space, N. Immerman, J. Buss, and D.M. Barrington, Journal of Symbolic Logic, 66(3) (2001), 1217 - 1230. (Abstract.html)

• Embedding Linkages on an Integer Lattice, S. Landau and N. Immerman, to appear in Algorithmica. (Abstract.html)

• "The Complexity of Decentralized Control of Markov Decision Processes", D. Bernstein, S. Zilberstein, and N. Immerman, Proceedings of the Sixteenth International Conference on Uncertainty in Artificial Intelligence. Palo Alto, CA, 2000.

• Reachability Logic: An Efficient Fragment of Transitive Closure Logic, N. Alechina and N. Immerman, Logic Journal of the IGPL 8(3) (2000), 325-338. (Abstract.html)

• Tree Canonization and Transitive Closure, K. Etessami and N. Immerman, Information and Computation 157(1,2) (2000), 2 - 24. A preliminary version appeared in IEEE Logic In Computer Science Symp. (1995), 331-341.

• Descriptive Complexity, N. Immerman, 1999, Graduate Texts in Computer Science, Springer, New York.

• Descriptive Complexity and Finite Models, edited by N. Immerman and Ph. Kolaitis, 1997, American Mathematical Society.

• Model Checking and Transitive Closure Logic, N. Immerman and M. Vardi, CAV'97, 291 - 302. (Abstract.html)

• Dyn-FO: A Parallel, Dynamic Complexity Class, S. Patnaik and N. Immerman, JCSS 55(2) (1997), 199-209. A preliminary version of this paper appeared in PODS (1994).

• A First-Order Isomorphism Theorem, E. Allender, J. Balc\'azar and N. Immerman, SIAM J. Computing 26(2) (1997), 557-567. A preliminary version appeared in Tenth Symp. Theoretical Aspects of Computer Science (1993), 163-174.

• An Optimal Lower Bound on the Number of Variables for Graph Identification, J. Cai, M. Fürer and N. Immerman, Combinatorica 12:4 (1992), 389-410. A preliminary version appeared in 30th IEEE FOCS Symp. (1989), 612-617.

• Nondeterministic Space is Closed Under Complementation, N. Immerman, SIAM J. Comput. 17, No. 5 (Oct., 1988), 935-938. Also appeared in Third Structure in Complexity Theory Symp. (1988), 112-115.

• Languages That Capture Complexity Classes, N. Immerman, SIAM J. of Computing 16:4 (1987), 760-778. A preliminary version appeared in 15th ACM STOC Symp. (1983), 347-354.

• Relational Queries Computable in Polynomial Time, N. Immerman, Information and Control 68 (1986), 86-104. A preliminary version appeared in 14th ACM STOC Symp. (1982), 147-152.

  ---