Midwest Theory Day
November 13, 2011, 9.30am-5:30pm
Wieboldt Hall, Northwestern U., 340 E Superior St., Chicago, IL.
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"|
|Talk:||Paolo Codenotti||"Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups"|
|Talk:||Tyson Williams||"Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy"|
|Talk:||Matthew Anderson||"Locality from Circuit Lower Bounds"|
|11:00-12:00||Invited||Yael Tauman Kalai||"Cryptography Resilient to Physical Attacks"|
|Talk:||Sariel Har-Peled||"Down the Rabbit Hole - Robust Proximity Search in Sublinear Space"|
|Talk:||Ben Moseley||"Fast Clustering Using Map-Reduce"|
|Talk:||Alina Ene||"Approximation Algorithms for Submodular Multiway Partition"|
|Talk:||Ben Raichel||"Geometric Packing under Non-Uniform Constraints"|
|Talk:||Aaron Sterling||"Self-Assembly of General Colored Shapes"|
|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"|
|Talk:||Junghwan Shin||"A Fair Min-Max Flow in a Network with Homogenous Delay Functions"|
|Talk:||Guru Devanla||"Quantum Algorithms for Community Detection in Social Networks"|
|Talk:||Siddharth Barman||"Traffic-Redundancy Aware Network Design"|
|Talk:||Xiaohua Xu||"Wireless Coverage with Disparate Ranges"|
|17:50-18:00||Closing Remarks||Nicole Immorlica|
Speaker: Yael Tauman Kalai (Microsoft Research New England, Cambridge, MA.)
Title: Cryptography Resilient to Physical Attacks
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.
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
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
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.
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 firstname.lastname@example.org 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 Immorlica||Northwestern U.|
|John Rogers||DePaul U.|