Mon Jan 23	Samson Zhou Purdue	(part of Crypto seminar) Title: On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling HAAS 111, 3pm Abstract: Joint work with Jeremiah Blocki
Mon Jan 30	Venkata Gandikota Purdue	(part of Crypto seminar) Title: Local Testing of Lattices HAAS 111, 3pm Abstract: Joint work with Karthik Chandrasekaran, Mahdi Cheraghchi, Elena Grigorescu.
Mon Jan 31	Jeremiah Blocki Purdue	LWSN 3102, 12:30-1:30 Title: Towards Human-Computable Passwords Abstract: Joint work with Manuel Blum, Anupam Datta and Santosh Vempala
Wed Feb 9	Samson Zhou Purdue	Title: Streaming for Aibohphobes: Longest Near-Palindrome under Hamming Distance 1 pm in LWSN 3133 Abstract: Palindromes are strings which read the same backwards and forwards, such as "racecar". Given a metric and an integer d>0, a d-near-palindrome is a string of distance at most d from its reverse. This talk will cover the problem of identifying the longest d-near-palindrome in data streams under the Hamming distance. The problem is relevant to the analysis of DNA databases, and to the task of repairing recursive structures in documents such as XML and JSON. We present the first streaming algorithm for the longest d-near-palindrome problem, which returns a d-near-palindrome whose length is within a multiplicative (1+c)-factor of the longest d-near-palindrome, for "small" d. We present additional streaming algorithms which return a d-near-palindrome whose length is within an additive E*sqrt(n)-factor of the longest d-near-palindrome in one-pass, as well as the longest length d-near-palindrome in two passes. Finally, we provide lower bounds for the space necessary to approximate the longest d-near-palindrome. Joint work with Elena Grigorescu and Erfan Sadeqi Azer.
Wed April 19	Andrej Bogdanov CUHK	Title: On the complexity and efficiency of secret sharing schemes 2 pm in LWSN 3102. CS COLLOQUIUM TALK. Abstract: A secret sharing scheme is a mechanism for dividing up a secret among several parties so that unqualified subsets of the parties do not learn any information about the secret, while qualified subsets can recover the secret. Such schemes were introduced by Shamir and Blakley in 1979 and have become an indispensable component in the architecture of secure communication and computation protocols. This talk will address the following foundational aspects of secret sharing and reconstruction: 1. Most secret sharing schemes are based on codes or polynomials. Is the use of linear algebra a necessity in this context or merely a convenience? What are “non-algebraic” schemes good for? What would be the consequences of the non-existence of such schemes? 2. In known secret sharing schemes, the shares are sometimes substantially larger than the secret. Is this loss in information efficiency a necessary price to pay for security? Our methods (from joint works with Siyao Guo, Yuval Ishai, Ilan Komargodski, Emanuele Viola, and Christopher Williamson) expose new connections between secret sharing, approximation theory, and game theory. Bio: Andrej Bogdanov is associate professor of Computer Science and co-director of the Institute of Theoretical Computer Science and Communications at the Chinese University of Hong Kong. He obtained his B.Sc. and M.Eng. degrees from MIT and his Ph.D. from UC Berkeley. He has worked as a postdoctoral researcher at the Institute for Advanced Study in Princeton, at DIMACS (Rutgers University), and at ITCS (Tsinghua University), and as a visiting professor at the Tokyo Institute of Technology. He is currently a long-term participant in the pseudorandomness program at the UC Berkeley Simons Institute for the Theory of Computing. His research interests are in computational complexity and the foundations of cryptography.

Link to schedule for Fall 2016, Sprinig 2016, Fall 2015, Spring 2015, Fall 2014. Spring 2014, Fall 2013. Spring 2013. Fall 2012.