Midwest Theory Day

University of Wisconsin - Milwaukee 

A u t u m n   2 0 0 5

The 51st Midwest Theory Day will be hosted by the Department of Electronic Engineering & Computer Science, at University of Wisconsin - Milwaukee on Saturday, December 10th, 2005. Links to some recent Theory Days can be found here.

The meeting will take place in room S101 in  Lapham Hall, which is located at 3209 N. Maryland Ave. in West Quad of campus (close to the intersection of N. Maryland Ave. and E. Kenwood Blvd.) in Milwaukee. Make a note of the room change!


The 52nd Midwest Theory Day will be held on May 6, 2006 on the Bloomington campus of Indiana University.


Midwest Theory Day (MTD) is a conference held twice a year, usually on a Saturday in April and a Saturday in December, hosted by a school in the Midwest.  Anyone interested in theoretical computer science is welcome to attend.  The talks are tightly scheduled, so it is possible to come, attend all of the talks, and return on the same day.  Registration is free and lunch is provided.  For those wishing to stay into the evening, arrangements are made for dinner at a local restaurant, with each person paying for his or her own meal.

There are usually around ten contributed talks and sometimes (like this time!) an invited talk.  There is no program committee and there are no proceedings.  Usually, anyone interested in giving a talk is able to do so.  The atmosphere is relaxed and informal.  It is an excellent forum for graduate students to gain experience in giving a presentation.




10:00 - 10:20


Coffee break
10:20 - 10:40

Scott Diehl      

University of Wisconsin-Madison

Time-space lower bounds for the polynomial-time hierarchy on randomized machines
10:40 - 11:00

Robert  Schweller

Northwestern University

Reducing tile complexity for self-assembly through temperature programming
11:00 - 11:20

David  Bunde

University of Illinois at Urbana-Champaign

Power-aware scheduling for makespan and flow
11:20 - 11:40


Coffee break
11:40 - 12:30

JŠnos Pach  (Invited Lecture)

Crossing numbers of graphs
12:30 - 2:00


2:00 - 2:20

Michael  Pelsmajer

Illinois Institute of Technology - Chicago

Removing even crossings
2:20 - 2:40

Adrian  German

Indiana University

On the high information content of a class of objects with low algorithmic complexity
2:40 - 3:00

Dan  Cranston

University of Illinois at Urbana-Champaign

Edge-list-colorability of planar graphs with no two adjacent triangles
3:00 - 3:20


Coffee break
3:20 - 3:40

John  Fischer

University of Illinois at Urbana-Champaign

Dynamic well-separated pair decomposition made easy
3:40 - 4:00

Andrew Shallue

University of Wisconsin-Madison

Finding points on characteristic 2 elliptic curves with applications to message embedding
4:00 - 4:20

Bhim  Upadhyaya

Maharishi Univ. of Management, Iowa

Towards a theoretical foundation for software components
4:20 - 4:40


 Coffee break
4:40 - 5:00

Manan  Sanghi

Northwestern University

Flexible word design and graph labelling
5:00 - 5:20

Mark  Pedigo

Saint Louis University

An online scheduling algorithm for non-preemptive, equal-length jobs using two identical machines
5:20 - 5:40

James  Pierce

Illinois Institute of Technology - Chicago

A linear time algorithm for finding a p-center of a tree






 We  have 20 minutes for each talk (17 minutes for the presentation, 3 minutes for questions and change-over to next talk)


Invited Lecture

Speaker:   JŠnos Pach  (City College, CUNY and Courant Institute, NYU)

Title: Crossing Numbers of Graphs


For those who are interested, we will be having dinner at a local restaurant at about 6 p.m. Each person will be paying for his or her own meal. An announcement about the dinner will be made during the conference.

Directions and parking

If you are driving, you can take I-94 from west, or I-43 from north or south. Then exit at 74 and merge onto E. Locust St. You can park in the parking lot in the front of EMS building with a permit card which you can pick up in the conference room upon your arrival. If you are flying into Milwaukee General Mitchell International Airport, you will need approximately 20 minutes to get to UWM campus by driving. 

For more information, please email Adrian Dumitrescu at ad(at)cs(dot)uwm(dot)edu.


Last updated on January 6, 2006.