DePaul CTI

Theory Seminar

The Theoretical Computer Science Group runs a seminar on topics in theoretical computer science, with emphasis on computation and complexity theory, discrete mathematics, and algorithms. The seminar is open to anyone interested, including advanced undergraduates, master's students and PhD students. If you would like to get announcements of seminar talks, please email Ljubomir Perkovic at lperkovic@cs.depaul.edu.

The seminar will usually meet in the 7th floor faculty lounge (CTI 742) of the CTI building.

Spring 2005/6 Schedule

Date Time Room Speaker Title/Abstract
Friday, June 2nd 3:30pm CTI 742 Ian Sutherland Nonstandard Analysis, II
Friday, May 26th 3:30pm CTI 742 Ian Sutherland Nonstandard Analysis, I
Friday, May 12th 3:30pm CTI 742 Robbie Schweller Complexities for the Design of Self-Assembly Systems
Friday, May 5th 3:30pm CTI 742 Iyad Improved Stretch Factor for Bounded-Degree Planar Power Spanners of Wireless Ad-Hoc Networks
Friday, April 28th 3:30pm CTI 742 Ljubomir Group-theoretic algorithms for matrix multiplication, II
Friday, April 21st cancelled
Friday, April 7th 3:30pm CTI 742 Ljubomir Group-theoretic algorithms for matrix multiplication

Winter 2005/6 Schedule

Date Time Room Speaker Title/Abstract
Friday, March 10th 3:30pm CTI 742 John How do I know that this sudoku puzzle has only solution?
Friday, March 3rd cancelled
Friday, February 10th 3:30pm CTI 742 Marcus Simultaneous Graph Drawing
Friday, January 27th 3:30pm CTI 742 Iyad On Feedback Vertex Set Problems
Friday, January 20th 3:30pm CTI 742 Lou Online graph coloring of graphs with bounded pathwidth or bounded treewidth

Fall 2005 Schedule

Date Time Room Speaker Title/Abstract
Friday, November 11th 2:30pm CTI 742 Ljubomir Linear Programming, Polyhedra, and The Simplex Algorithm, II
Friday, October  28th 3:30pm CTI 742 Ljubomir Linear Programming, Polyhedra, and The Simplex Algorithm, II
Friday, October  21st 3:30pm CTI 742 Ljubomir Linear Programming, Polyhedra, and The Simplex Algorithm
Friday, October 14th cancelled
Friday, October 7th cancelled
Friday, September 30th 3:30pm CTI 742 Dave Angulo Algorithms to Analyze Mass Spectra Data
Friday, September 16th 3:30pm CTI 742 John Rogers Making the polynomial hierarchy look like the arithmetical hierarchy

Spring 2005 Schedule

Date Time Room Speaker Title/Abstract
Friday, April 22nd 3:30pm CTI 723 Ivona Bezakova (UofC) Improved Simulated Annealing Algorithm for the Permanent and Combinatorial Counting Problems

 

Winter 2005 Schedule

Date Time Room Speaker Title/Abstract
Friday, March 4th 3:30pm CTI 742 Ljubomir Approximate Counting via Dynamic Programming
Friday, February 18th 3:30pm CTI 742 Gruia Calinescu (IIT) Bounding the payment of approximate truthful mechanisms
Friday, February 11th 3:30pm CTI 742 Wen-Zhan Song (IIT) Topology Control in Wireless Ad hoc Networks
Friday, January 21st 3:30pm CTI 742 Will Marrero Deciding CTL using BDDs

 

Fall 2004 Schedule

Date Time Room Speaker Title/Abstract
Friday, November 12th 3:30pm CTI 742 Michael Pelsmajer Nonrepetitive coloring of graphs
Friday, November 5th 3:30pm CTI 742 Peter Hui Paired Pointset Traversal
Friday, October 29th 3:30pm CTI 742 Raffaella Propagating evidence in Bayesian Networks is NP-Hard, IId
Friday, October 22nd 3:30pm CTI 742 Raffaella Propagating evidence in Bayesian Networks is NP-Hard
Friday, October 15th cancelled
Friday, October 8th 3:00pm CTI 742 Marty Axiom of Choice
Friday, September 24th 3:30pm CTI 742 Marcus Train Tracks and Confluent Drawings

Spring 2004 Schedule

Date Time Room Speaker Title/Abstract
Friday, May 28th 3:30pm CTI 742 John Rogers Three-coloring triangle-free planar graphs
Friday, May 7th 4:00pm CTI 742 Massimo Overview of Modern Quantum Physics II
Friday, April 30th 3:30pm CTI 742 Massimo Overview of Modern Quantum Physics
Friday, April 23rd 3:30pm CTI 742 Iyad Strong Computational Lower Bounds via Parameterized Complexity II
Friday, April 16th 3:30pm CTI 742 Iyad Strong Computational Lower Bounds via Parameterized Complexity

Winter 2004 Schedule

Date Time Room Speaker Title/Abstract
Friday, March 5th 3:30pm CTI 742 John Rogers Why won't degrees collapse?
Friday, February 13th 3:30pm CTI 742 Marcus Undecidability of Lachlan's enumeration games
Friday, February 6th 3:30pm CTI 742 Michael Pelsmajer Reliable Single Message Transmission
Friday, January 23rd 3:30pm cancelled
Friday, January 16th 3:30pm CTI 742 Michael Fries Independence in Set Theory and the Continuum Hypothesis, IV

Fall 2003 Schedule

Date Time Room Speaker Title/Abstract
Friday, November 14th 3:30pm cancelled
Friday, November 7th 3:30pm CTI 742 Gruia Calinescu Network Lifetime and Power Assignment in Ad-Hoc Wireless Networks
Friday, October 31st 3:30pm CTI 742 Michael Fries Independence in Set Theory and the Continuum Hypothesis, III
Friday, October 24th rescheduled
Friday, October 17th 3:30pm CTI 742 Michael Fries Independence in Set Theory and the Continuum Hypothesis, II
Friday, October 10th 3:30pm CTI 742 Michael Fries Independence in Set Theory and the Continuum Hypothesis, I
Friday, October 3rd rescheduled
Friday, September 26th 3:30pm CTI 742 Michael Pelsmajer Equitably k-Choosable Graphs
Friday, September 19th 3:30pm CTI 742 Daniel Stefankovic Locally Testable Cyclic Codes

 

Spring 2003 Schedule

Date Time Room Speaker Title/Abstract
Friday, June 6th 3:30pm CTI 742 John Rogers ZPPNP and S2
Friday, May 30th 3:30pm CTI 742 cancelled
Friday, May 23rd 3:30pm CTI 742 cancelled
Friday, May 16th 3:30pm CTI 742 rescheduled
Friday, May 9th 3:30pm CTI 742 Michael Pelsmajer A short proof of a characterization of strongly chordal graphs
Friday, May 2nd cancelled (colloquium talk)
Friday, April 11th 3:30pm CTI 742 Lou A fully dynamic algorithm for recognizing interval graphs using the train tree

Winter 2003 Schedule

Date Time Room Speaker Title/Abstract
Friday, March 7th will be rescheduled
Friday, February 14th 3:30pm CTI 742 Iyad Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-hard Problems, Part II
Friday, February 7th 4:00pm CTI 742 Iyad Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-hard Problems
Friday, January 31st 3:30pm CTI 742 Louis The Clique-Separator Graph for Chordal Graphs and its Subclasses
Friday, January 24th 3:30pm CTI 742 Ljubomir The Strong Perfect Graph Theorem, Part II
Friday, January 17th 3:30pm CTI 742 Ljubomir The Strong Perfect Graph Theorem, Part I

Fall 2002 Schedule

Date Time Room Speaker Title/Abstract
Friday, November 1st 3:30pm CTI 742 Michael Goldwasser An Optimal Algorithm for Finding Length-Constrained, Maximum-Density Segments of a Sequence with Applications to Bioinformatics
Friday, October 25th 3:30pm CTI 742 Marty Wittgenstein on Mathematics 
Friday, October 18th 3:30pm CTI 742 Ian Primes in P
Friday, October 11th cancelled
Friday, October 4th 3:30pm CTI 742 Louis Ibarra Continuation: A dynamic algorithm for maintaining the modular decomposition of a graph 
Friday, September  27th 3:30pm CTI 742 Louis Ibarra A dynamic algorithm for maintaining the modular decomposition of a graph 

Spring 2002 Schedule

Date Time Room Speaker Title/Abstract
Friday, June 7th 4pm CTI 742 Gian-Mario An algebraic geometer's view of multiple-views-geometry in computer vision Part II 
Friday, May 24th 4pm CTI 742 Marty will be rescheduled
Friday, May 17th 4pm CTI 742 cancelled
Friday, May 10th 4pm CTI 742 Gian-Mario An algebraic geometer's view of multiple-views-geometry in computer vision
Friday, May 3rd 4pm CTI 742 Yakov Graph-based algorithms for image segmentation
Friday, April 12th 4pm CTI 742 Iyad Improved Exact Algorithms for Max-Sat

Winter 2002 Schedule

Date Time Room Speaker Title/Abstract
Friday, March 1st 4pm CTI 742 Ljubomir Approximation Algorithms via Semidefinite Programming
Friday, February 22nd 4pm CTI 742 Marcus Beigel's Cardinality Conjecture
Friday, January 25th 4pm CTI 742 Iyad Kanj Using Nondeterminism to Design Efficient Deterministic Algorithms
Friday, February 1st 4pm CTI 742 Frank Stephan Mathematical Boundaries of Learning.

Fall 2002 Schedule

Date Time Room Speaker Title/Abstract
Friday, September 21st 4pm CTI 742 Ljubomir Perkovic Two cute list coloring results
Friday, September 28th 4pm CTI 742 Ljubomir, Eric, Marcus Three Theorems
Friday, October 5th 3pm CTI 742 Eric Schwabe Algorithms for constructing data layouts for disk arrays
Friday, October 12th 4pm CTI 742 Ian Agol, UIC Computational Complexity of Knot Genus
Friday, October 19th cancelled
Friday, November 2nd 3pm CTI 742 Eric Schwabe Algorithms for constructing data layouts for disk arrays, part 2
Friday, November 9th 4pm CTI 742 Marcus, Daniel Stefankovic Recognizing String Graphs in NP

Spring 2001 Schedule

Date Time Room Speaker Title/Abstract
Friday, April 6th 4pm CTI 742 Ian Sutherland Evasiveness of Graph Properties
Friday, April 13th no seminar (Good Friday)
Friday, April 20th 4pm CTI 742 Martin Kalin Quine's Philosophy of Science: An Overview
Friday, April 27th 4pm CTI 742 Ian Sutherland Evasiveness of Graph Properties II
Friday, May 4th no seminar
Friday, May 11th 4pm CTI 742 Marcus Schaefer Minimal Indices
Friday, May 18th 4pm CTI 742 Rahul Santhanam Relationships among Time and Space Complexity Classes

Winter 2001 Schedule

Date Time Room Speaker Title/Abstract
Friday, January 19th 4pm CTI 742 Marcus Schaefer Intro to Parameterized Complexity
Friday, January 26th 4pm CTI 742 Martin Grohe, UIC Computing crossing numbers in quadratic time
Friday, February 9th 4pm 436A Daniel Stefankovic Decidability of String Graphs
Friday, February 16th cancelled
Friday, February 23rd 4pm CTI 742 John Rogers Expressive Completeness of Constructive Logic
Friday, March 2nd cancelled
Friday, March 9th 4pm CTI 742 Ljubomir Perkovic Hilton's conjecture, and edge coloring in polynomial time (on average)
Friday, March 16th 4pm CTI 742 Amber Settle Beyond exhaustive search? A proposal for lower bounds on the firing synchronization problem.

Fall 2001 Schedule

The seminar will usually meet in the 7th floor faculty lounge of the CTI building.
Date Time Room Speaker Title/Abstract
Friday, November 10th 4pm 7th floor lounge Marcus Schaefer A History of Post's Problem Abstract
Friday, November 3rd 4pm 7th floor lounge Sophie Laplante Lower Bound for Collision Problems
Friday, October 27th cancelled
Friday, October 13th 3pm 7th floor lounge Ljubomir Perkovic Continuation of Inexpensive d-dimensional matchings(Abstract)
Friday, October 6th 4pm 7th floor lounge Ljubomir Perkovic Inexpensive d-dimensional matchings(Abstract)
Friday, September 29 3pm 7th floor lounge cancelled

 

Spring 2000 Schedule

Date Time Place Speaker Title/Abstract
Friday, June 2 4pm CST 436A John Rogers Three-coloring triangle-free planar graphs (Abstract)
Friday, May 12 4pm CST 436A Ian Sutherland Computability and Complexity with Inexact Real Arithmetic, Part II (Abstract for Part II)
Friday, May 5 4pm CST 436 Ian Sutherland Computability and Complexity with Inexact Real Arithmetic (Abstract)
Friday, April 28       Conflict with faculty meeting, so no talk this week.
Friday, April 21       Good Friday, university closed.
Friday, April 14 4pm CST 436A Marcus Schaefer Solvability of Graph Inequalities, continued. Marcus will finish presenting the results of the paper from last week.
Friday, April 7 4pm CST 436A Marcus Schaefer Solvability of Graph Inequalities (Abstract)


Page maintained by Marcus Schaefer.