Theory of Computation (TOC) Seminars

	Exponential Separation of Information and Communication Tuesday, December 2, 2014 - 4:15pm to 5:15pm Abstract: In profoundly influential works, Shannon and Huffman show that if Alice wants to send a message X to Bob, it's sufficient for her to send roughly H(X) bits (in expectation), where H denotes Shannon's entropy function.
	Tilting at Windmills: The Economic Efficiency of Large Games Tuesday, November 18, 2014 - 4:15pm to 5:15pm Abstract:
	3SUM is Subquadratic Tuesday, November 4, 2014 - 4:15pm to 5:15pm Abstract: The 3SUM problem is to decide, given a set of N real numbers, whether any three of them sum to zero. A simple algorithm solves 3SUM in O(N^2) time and it has long been conjectured that this is the best possible.
	Computing Elementary Statistics: Time-Space Tradeoffs and Sliding Windows Tuesday, October 28, 2014 - 4:15pm to 5:15pm Abstract: We consider the complexity of computing element distinctness, frequency moments, and order statistics with limited space, as well as computing these statistics over "sliding windows" in a single longer data sequence, a natural requirement for time-series data.
	Zeev Dvir, Private Information Retrieval with 2-Servers and sub-polynomial communication Tuesday, October 7, 2014 - 4:15pm to 5:15pm

Pages