Midwest Theory Day F A L L   2 0 0 1

• November 24: The schedule of talks and an invitation to the MTD are now online.
• November 22: Abstracts are now available; a correction made in the overall schedule.
• November 19: A list of talks and tentative schedule are now available.
• Deadline for submitting titles and abstracts: November 16 (Friday)!
• October 4: Call for speakers.

The forty-fourth Midwest Theory Day will be hosted by the Department of Computer Science of the University of Illinois at Urbana-Champaign on Saturday, December 1, 2001.

The Midwest Theory Day (MTD) is a one-day conference on topics in theoretical computer science. It is held twice a year, once each during the spring and fall semesters, and is hosted by a school in the midwest. The atmosphere is relaxed and informal. The usual format is to have 6-8 contributed talks and an invited talk. If you are a graduate student, you are especially encouraged to give a talk on your original research. Generally, whoever is interested in giving a talk will be able to do so. There is no registration fee and no proceedings are published. Anybody interested in theoretical computer science is welcome to attend.

The schedule of talks is such that it should be possible to travel to the venue, attend all the talks, and return, all in one day. A free lunch (and coffee!) is provided, and participants usually get together afterwards over dinner at their own expense.

To link to this page, please use the URL http://www.uiuc.edu/~thite/mtd.

Date: December 1, 2001 (Saturday)
Time: 10:30am -- 5:30pm
Venue: 1310 Digital Computer Laboratory

View all abstracts. View a separate printable version of the schedule.

Time	Speaker(s)	Title and Abstract
Session M (10:30 am -- noon)
10:30	Prof. Marc Snir, Head of Computer Science, UIUC	Welcome to attendees
10:30 -- 11:00	Ashutosh Garg, UIUC	Generalization Bounds for Linear Learning Algorithms
11:00 -- 11:30	Daniel Stefankovic, U. Chicago Marcus Schaefer, DePaul	Recognizing String Graphs in NP
11:30 -- noon	Chandra N. Sekharan, Loyola	New Themes in the All-Pairs Shortest Path (APSP) Problem: A Survey
noon -- 1:30	Lunch break (Lunch will be provided to attendees free of charge.)
Session A1 (1:30 -- 3:00 pm)
1:30 -- 2:00	Thomas P. Hayes, U. Chicago	Separating the Multiparty Communication Hierarchy
2:00 -- 2:30	Ken Takata, U. Illinois, Chicago	On the complexity of listing minimal hitting sets
2:30 -- 3:00	Denis Charles, U. Wisconsin, Madison	The distribution of Squarefree Smooth integers in Short Intervals
3:00 -- 3:15 pm	Coffee break
Session A2 (3:15 -- 4:45 pm)
3:15 -- 3:45	Tanya Berger-Wolf, UIUC	Multichannel Communication and Vertex Labeling of Graph Products
3:45 -- 4:15	Venkatesan Chakaravarthy, U. Wisconsin, Madison	Some Karp-Lipton-Type theorems based on S_2
CANCELLED	Teo Chung-Piaw, Northwestern University and National University of Singapore	A Polynomial Time Algorithm for Bistable Roommates Problem
4:15 -- 4:45	Andy Poe, Northern Michigan U.	Load Balancing Multiweight Geometric Problems
4:45 -- 5:00 pm	Coffee break
Session A3 (5:00 -- 5:30 pm)
5:00 -- 5:30	Predrag Tosic, UIUC	Phase Space Properties of Synchronous and Sequential Dynamical Systems

• Maps and directions
  • All campus map
  • North campus map (including DCL)
  • Travel directions to UIUC campus
  • Traveling to campus
• Visitor information
• Visitors guide
• Campus tours
• Champaign-Urbana Mass Transit District (local bus service)
• About Champaign-Urbana
  • CUOut.com
  • ChampaignUrbana.net
  • ShampooBanana.com
  • The Daily Illini / Buzz
  • The Octopus
• Weather
  • Weather Underground
  • Live Weather Camera
• Arts
  • Krannert Center
  • School of Music
• Sports & Events
  • Fighting Illini
  • Assembly Hall

Number	Date	Host	Contact
45	April 2002	IIT, Chicago	Gruia Calinescu
44	December 1, 2001	UIUC	Jeff Erickson
43	April 21, 2001	U. Wisconsin, Madison	Jin-Yi Cai
42	December 2000	DePaul U., Chicago	John Rogers
	April 2000	NONE
41	December 4, 1999	U. Chicago	Simon
40	April 1999	U. Wisconsin, Madison	Eric Bach
39	December 5, 1998	DePaul U., Chicago	Schwabe
38	April 1998	U. Kentucky, Lexington	Goldsmith
37	December 1997	Loyola U., Chicago	Lokam
36	April 1997	Indiana	Purdom
35	December 1996	U. Illinois, Chicago	Sloan
34	April 1996	Washington U., St. Louis	Goldman
33	December 1995	DePaul U., Chicago	Rogers
32	April 1995	UIUC	Brown
31	December 1994	U. Chicago	Fortnow
30	April 1994	Butler U., Indianapolis	Sorenson
29	December 1993	Northwestern U., Chicago	Schwabe
28	April 1993	U. Notre Dame	Chen
27	December 1992	Northwestern U., Chicago	Hellerstein
26	April 1992	Indiana	Shannon
25	December 1991	U. Chicago	Simon
24	April 1991	U. Wisconsin, Madison	Eric Bach
23	December 1990	Northwestern U., Chicago	Sarrafzadeh/Lee
22	April 1990	Purdue	Hambrusch (?)
21	December 1989	Andersen Consulting	Hornick/Maddila
20	April 1989	UIUC	Lenny Pitt
19	December 1988	U. Chicago	Karloff
18	April 1988	Indiana	Purdom
17	December 1987	Northwestern	Sarrafzadeh/Lee
16	April 1987	UIUC	Edelsbrunner
15	December 1986	U. Chicago	O'Donnell
14	April 1986	Purdue	Atallah
13	December 1985	Northwestern	Lee
12	April 1985	UIUC	Ramachandran
11	December 1984	UI/Chicago	Manacher
10	April 1984	Wash. U. St. Louis	Turner
9	December 1983	IIT	Makedon
8	April 1983	Indiana	Purdom
7	December 1982	UIUC	Kruskal
6	September 1982	Purdue	Berman/Cuny
5	April 1982	IUPUI	Richards (Free lunches begin)
4	December 1981	Northwestern	Sudborough
3	September 1981	UIUC	Loui
2	April 1981	Indiana	Robertson
1	December 1980	Purdue	Brown/Berman