Midwest Theory Day
November 13, 2011, 9.30am-5:30pm
Wieboldt Hall, Northwestern U., 340 E Superior St., Chicago, IL.

[Synopsis] [Registration] [Schedule] [Invited Talks] [Organizers]


The 62nd Midwest Theory Day will be hosted by the Theory Group in Electrical Engineering and Computer Science Department at Northwestern University, Chicago campus, on Sunday, November 13th. There will be a number of contributed talks and invited talks. Anyone interested in theoretical computer science is welcome to attend. There is no registration fee, lunch is provided, and the talks are scheduled so that from many locations in the Midwest it is often possible to come, attend all of the talks, and return home all in a day.

Next Meeting: Nov. 13, 2011, 9.00am-6:00pm, Wieboldt Hall, Northwestern U., 340 E Superior St., Chicago, IL.


Pre-registration is now closed. Please come at 9am on Sunday, November 13th, to register on-site. There is no cost for attending.


09:00-09:40 Arrivals Coffee and Registration
09:30-09:40 Welcome Remarks Nicole Immorlica
09:40-10:00 Talk: Sungjin Im "Minimum Latency Submodular Cover in Metrics"
10:00-10:20 Talk: Paolo Codenotti "Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups"
10:20-10:40 Talk: Tyson Williams "Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy"
10:40-11:00 Talk: Matthew Anderson "Locality from Circuit Lower Bounds"
11:00-12:00 Invited Yael Tauman Kalai "Cryptography Resilient to Physical Attacks"
12:00-13:00 Lunch Buffet
13:00-13:20 Talk: Sariel Har-Peled "Down the Rabbit Hole - Robust Proximity Search in Sublinear Space"
13:20-13:40 Talk: Ben Moseley "Fast Clustering Using Map-Reduce"
13:40-14:00 Talk: Alina Ene "Approximation Algorithms for Submodular Multiway Partition"
14:00-14:20 Talk: Ben Raichel "Geometric Packing under Non-Uniform Constraints"
14:20-14:40 Talk: Aaron Sterling "Self-Assembly of General Colored Shapes"
14:40-15:00 Talk: Bach Ha "Mechanism Design via Consensus Estimates, Cross Checking, and Profit Extraction"
15:00-15:30 Break Coffee and Snacks
15:30-16:30 Invited Adam Tauman Kalai "Common Ground in Coding: Compression with Differing Priors"
16:30-16:50 Talk: Junghwan Shin "A Fair Min-Max Flow in a Network with Homogenous Delay Functions"
16:50-17:10 Talk: Guru Devanla "Quantum Algorithms for Community Detection in Social Networks"
17:10-17:30 Talk: Siddharth Barman "Traffic-Redundancy Aware Network Design"
17:30-17:50 Talk: Xiaohua Xu "Wireless Coverage with Disparate Ranges"
17:50-18:00 Closing Remarks Nicole Immorlica

Invited Talks


Speaker: Yael Tauman Kalai (Microsoft Research New England, Cambridge, MA.)

Title: Cryptography Resilient to Physical Attacks

Abstract: Traditionally, cryptographers assume that the secret keys are completely hidden from the adversary, and that the cryptographic algorithms are error-free. However, in reality there are various real-world physical attacks which adversaries use to break cryptographic systems. These include timing, power, and acoustic attacks, which allow an adversary to (continually) leak information about the secret keys, as well as various tampering attacks, such as heat and EM radiation attacks, which allow an adversary to (continually) tamper with system.

Recently, there has been a vast and growing body of work, which try to secure cryptographic systems against such physical attacks. In this talk I will explain some of these results.

Bio: Yael Tauman Kalai received her BA (1997) from the Hebrew University in Jerusalem, MA (2001) under the supervision of Adi Shamir at the Weizmann Institute, and PhD (2006) under the supervision of Shafi Goldwasser at MIT. After postdoctoral positions at Microsoft Research and the Weizmann Institute, she is now a Researcher at Microsoft Research New England. Her honors include an outstanding master's thesis prize, a Sprowl's award (cowinner) for best PhD Thesis at MIT. Her research focuses on cryptography.


Speaker: Adam Tauman Kalai (Microsoft Research New England, Cambridge, MA.)

Title: Common Ground in Coding: Compression with Differing Priors

Abstract: Digital compression schemes rely upon perfect synchronization between compression and decompression algorithms. In order to take advantage of a good prior distribution over messages (so likely messages can be shorter), both parties must agree on the same prior distribution. Human communication is much more robust, e.g., it generally suffices for the author of an article to know roughly who the target audience is in order to be understood. We use ideas based on principles from human communication to design codes that can capture prior knowledge of the distribution over messages, but where the two parties can have differing prior distributions. In this sense, the compression scheme more closely resmembles human communication and we are performing "biomimicry."

Joint work with Brendan Juba, Sanjeev Khanna, and Madhu Sudan.

Bio: Adam Tauman Kalai received his BA (1996) from Harvard, and MA (1998) and PhD (2001) under the supervision of Avrim Blum from CMU. After an NSF postdoctoral fellowship at M.I.T. with Santosh Vempala, he served as an assistant professor at the Toyota Technological Institute at Chicago and then at Georgia Tech. He is now a Senior Researcher at Microsoft Research New England. His honors include an NSF CAREER award, and an Alfred P. Sloan fellowship. His research focuses on computational learning theory, human computation, and algorithms.

Local Information

The 62nd Midwest Theory Day will be held in Wieboldt Hall at Northwestern U.'s downtown Chicago campus.

View Mid-West Theory Day in a larger map

Parking: The workshop venue is easily accessible by public transit, but should participants plan to drive there is a parking lot at 222 E. Huron. Please email midwest.theory@gmail.com with a subject line of PARKING for a discount parking pass by Oct. 31st. The projected cost of discount parking is $20 per day (with advance registration).


Nicole ImmorlicaNorthwestern U.
John RogersDePaul U.