# Theoretical CS Reading Group

The reading group meets once a week
usually, Monday 1:30-2:30pm to discuss
a particular paper or topic.
Please join our mailing list to get notifications about the weekly meetings and discussions. You might also be interested in the Theory Seminar. |

Fall 2017 Spring 2017 Fall 2016 Spring & Summer 2016 Fall 2015 Spring & Summer 2015 Fall 2014 Spring 2014 Summer & Fall 2013 |

# Spring 2017

** Friday, 20th January 2017** —
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff

Beating CountSketch for Heavy Hitters in Insertion Streams

**Presenter:** Samson Zhou

** Monday, 23rd January 2017**

Locally Decodable Codes

**Presenter:** GV

** Tuesday, 31st January 2017** —
Theory Seminar - Prof. Jeremiah Blocki, Purdue University

Towards Human Computable Passwords

**Click to view Abstract**

An interesting challenge for the cryptography community is to design authentication protocols that are so simple that a human can execute them without relying on a fully trusted computer. We propose several candidate authentication protocols for a setting in which the human user can only receive assistance from a semi-trusted computer---a computer that stores information and performs computations correctly but does not provide confidentiality. Our schemes use a semi-trusted computer to store and display public challenges $C_i\in[n]^k$. The human user memorizes a random secret mapping $\sigma:[n]\rightarrow \mathbb{Z}_d$ and authenticates by computing responses $f(\sigma(C_i))$ to a sequence of public challenges where $f:\mathbb{Z}_d^k\rightarrow \mathbb{Z}_d$ is a function that is easy for the human to evaluate. We prove that any statistical adversary needs to sample $m=\tilde{\Omega}\paren{n^{s(f)}}$ challenge-response pairs to recover $\sigma$, for a security parameter $s(f)$ that depends on two key properties of $f$. Our lower bound generalizes recent results of Feldman et al. \cite{feldman2013complexity} who proved analogous results for the special case $d=2$. To obtain our results, we apply the general hypercontractivity theorem \cite{o2007analysis} to lower bound the {\em statistical dimension } of the distribution over challenge-response pairs induced by $f$ and $\sigma$. Our {\em statistical dimension} lower bounds apply to arbitrary functions $f:\mathbb{Z}_d^k\rightarrow \mathbb{Z}_d$ (not just to functions that are easy for a human to evaluate). As an application, we propose a family of human computable password functions $f_{k_1,k_2}$ in which the user needs to perform $2k_1+2k_2+1$ primitive operations (e.g., adding two digits or remembering a secret value $\sigma(i)$), and we show that $s(f) = \min\{k_1+1, (k_2+1)/2\}$. For these schemes, we prove that forging passwords is equivalent to recovering the secret mapping. Thus, our human computable password schemes can maintain strong security guarantees even after an adversary has observed the user login to many different accounts. Joint work with Manuel Blum, Anupam Datta, Santosh Vempala.

** Monday, 6th February 2017**

Certifying Algorithms

**Presenter:** Nima Darivandpour

** Thursday, 9th February 2017** —
Theory Seminar - Samson Zhou, Purdue University

Streaming for Aibohphobes: Longest Near-Palindrome under Hamming Distance

**Click to view 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 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.

** Wednesday, 15th February 2017**

Holant problems and Holographic transformations

**Presenter:** Minshen Zhu

** Wednesday, 22nd February 2017** —
Theory Seminar - Hai Nguyen, Purdue University

Secure Computation based on Leaky Correlations: High Resilience Setting

** Wednesday, 1st March 2017** —
Guruswami et. al.

On Profit-Maximization Envy-Free Pricing

**Presenter:** Young-San Lin

** Wednesday, 8th March 2017**

An Introduction to Sum of Squares

**Presenter:** Negin Karisani

** Wednesday, 29th March 2017** —
TCS+ Talk - Noah Stephens-Davidowitz, NYU

A Reverse Minkowski Theorem

** Thursday, 6th April 2017**

Dependent Random Choice

**Presenters:** Akash Kumar

** Wednesday, 19th April 2017** —
Theory Seminar - Andrej Bogdanov, CUHK

On the complexity and efficiency of secret sharing schemes

**Click to view 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.

** Wednesday, 26th April 2017** —
TCS+ Talk - Santosh Vempala, Georgia Tech

Sampling Polytopes: from Euclid to Riemann