Theoretical Computer Science Group

College of CDM, DePaul University

Welcome to the home page of the Theory Group in the School of Computer Science, Telecommunications, and Information Systems at DePaul University.  Members of the group are active in many areas of theoretical computer science, including Complexity Theory, Parallel and Distributed Algorithms, and Quantum Computation. 

Theory Group Faculty: 

• André Berthiaume: (CTI 746, x25325)

  • Classical and quantum algorithms, quantum information theory, classical and quantum cryptography, information technology education 

• Louis Ibarra: (CTI 455, x25934)
  • Dynamic graph algorithms, parallel algorithms, data structures, computational biology.

• Richard Johnsonbaugh (emeritus): (CTI 461, x28728)
  • Discrete mathematics, especially combinatorics and algorithms, pattern recognition.

• Iyad Kanj: (CTI 710, x25558)
  • Combinatorial optimization, parameterized computation, graph algorithms.

• Ljubomir Perkovic: (CTI 713, x28337)
  • Graph theory and algorithms, combinatorial optimization, probabilistic methods in the design and analysis of algorithms, distributed algorithms.

• John Rogers: (CTI 747, x28334)
  • Structural complexity theory, quantum computation, kolmogorov complexity, constructive logic, graph theory.

• Marcus Schaefer: (CTI 749, x25244) 
  • Computability, complexity, combinatorics, graph theory.

• Eric Schwabe: (CTI 739, x25943)
  • Parallel algorithms and architectures, interconnection networks, disk arrays, algorithms, graph theory, combinatorics.

• Eric Sedgwick: (CTI 827, x25184)
  • Computational topology.

• Amber Settle: (CTI 748, x25324)

  • Distributed algorithms, cellular automata, applications of reasoning about knowledge to distributed systems, information retrieval, information systems and computer science education.
     

Recent/Upcoming Events and News:

• CTI Theory Seminar, Friday afternoons at DePaul (to resume September 2006).

• Midwest Theory Day, December 2006 meeting at Purdue University.

Recent Publications:

• "Simultaneous Graph Embeddings with Fixed Edges". Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz.
   Zaik Technical Report, zaik2006-507, 2006. (link)
• "Improved Stretch Factor for Bounded-Degree Planar Power Spanners of Wireless Ad-Hoc Networks".  I. Kanj, L. Perkovic.  To appear in Proceedings of the 2nd International Workshop on Algorithmic Aspects of Wireless Sensor Networks, 2006.
• "A Case for Application-Aware Grid Services". G. Garzoglio, A. Baranovski, P. Mhashilkar, L. Perkovic, A. Rajendra.  Proceedings of Computing in High Energy Physics (CHEP06), 2006.
• "Inverting Onto Functions Might Not Be Hard". H. Buhrman, L. Fortnow, M. Koucky, J. Rogers, N. Vereshchagin). ECCC TR06-024, 2006. (link)
• "Sweepouts of Amalgamated 3-Manifolds". D. Bachman, S. Schleimer, E. Sedgwick. To appear in Algebraic and Geometric Topology, 2006.
• "Heegaard splittings of the form H+nK". Y. Moriah, S. Schleimer, E. Sedgwick. Communications in Analysis and Geometry, 2006.
• "Crossing Number of Graphs with Rotation Systems". Michael Pelsmajer, Marcus Schaefer, Daniel Štefankovič. DePaul University Technical Report, TR 05-017, 2005. (link)
• "Removing Even Crossings". Michael Pelsmajer, Marcus Schaefer, Daniel Štefankovič.  EuroComb, 2005. (link)
• "Odd Crossing Number Is Not Crossing Number". Michael Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Graph Drawing, 2005. (link)
• "Train Tracks and Confluent Drawings". Peter Hui, Michael Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Graph Drawing, 2004. (link)
• "Paired Pointset Traversal". Peter Hui, Marcus Schaefer. ISAAC, 2004. (link)
• "Bounding the Firing Synchronization Problem on a Ring". A. Berthiaume, T. Bittner, L. Perkovic, A. Settle, and J. Simon. Theoretical Computer Science, 2004.
• "Closed Essential Surfaces and Weakly Reducible Heegaard Splittings in Manifolds with Boundary". Y. Moriah, E. Sedgwick.  Journal of Knot Theory and its Ramifications, 2004.
• "Effiicient Data Mappings for Parity-Declustered Disk Arrays". Eric J. Schwabe and Ian M. Sutherland. Theoretical Computer Science, 2004.
• "Generating and characterizing the perfect elimination orderings of a chordal graph". L. S. Chandran, L. Ibarra, F. Ruskey, J. Sawada. Theoretical Computer Science, 2003.

Eric J. Schwabe - 06/23/06