Innovations in Theoretical Computer Science 2018

Graduating Bits

ITCS has had a long tradition of holding a "graduating bits" event where graduating students and postdocs give a short presentation about their work.

When: Friday, January 12 at 6:30pm
Where: Stata Center, 32G-449 (Kiva)
Pizza and drinks will be served.

Gautam "G" Kamath, MIT
Gautam Kamath is a final-year graduate student at MIT, advised by Constantinos Daskalakis. His research focuses on theoretically principled approaches for statistical data science, particularly settings which are of key importance in modern data analytics. Some considerations include high-dimensional data, robustness, and privacy, in classical problems including hypothesis testing and distribution estimation.
Jacob Steinhardt, Stanford
I am interested in designing machine learning systems that are secure against attackers and reliable even in the face of unexpected inputs. When such worst-case reliability is important, theoretical guidance is necessary for designing good algorithms, because past empirical performance cannot be relied on to indicate future success. My research focuses on building conceptual frameworks to formalize challenges in reliability, developing new theory to address these challenges, and then using this newfound perspective to develop better methods. Website:
Michal Moshkovitz,
Hebrew University
I am a final year PhD student at the hebrew university of Jerusalem. My research is in the intersection of theoretical computer science, machine learning, and neuroscience. I received my MSc in theoretical computer science from Tel-Aviv University. In my PhD I proved one of the first lower bound for unlearnability with bounded-memory.
Bo Waggoner, UPenn
Much of my work focuses on systems for learning from data or information when strategic agents are involved. Examples include prediction markets or algorithms for learning when data is provided by strategic agents. I also enjoy differential privacy, online learning, and foundations of eliciting information from strategic agents.
Prabhanjan Ananth, MIT
I am postdoc at CSAIL, MIT, hosted by Vinod Vaikuntanathan. My research focus is on program obfuscation, that has two seemingly contradictory requirements: making software code unintelligible while still preserving its original functionality. In particular, I am interested in understanding whether program obfuscation can be based upon cryptographic assumptions that has stood the test of time.
Frederik Mallmann-Trenn,
Frederik Mallmann-Trenn is a postdoc at MIT. He has completed his PhD with Claire Mathieu at ENS and Petra Berenbrink at Simon Fraser University. He has general interest in randomized processes, distributed computing, random walks, and other random topics (in both senses of the word).
Yun Kuen (Marco) Cheung,
Max Planck Insitut
My general research interests span over Theoretical Computer Science, Discrete Mathematics / Combinatorics and Algorithm Design/Analysis. Currently, I have one of my foci on Computational Economics / Algorithmic Game Theory / Mechanism Design, and the other on Graph Sparsification and Decomposition. Motivated by the study of price updates in markets using outdated information, one of my key research projects is Asynchronous Coordinate Descent, a fundamental problem in optimization; see arXiv 1612.09171 for details. Another interesting recent paper is about Spanning Tree Congestion.


Makrand Sinha,
University of Washington
Makrand Sinha is a PhD student at University of Washington advised by Anup Rao. His research interests lie in Complexity theory, in particular, in Communication Complexity, Lower Bounds for Linear Programs and Derandomization. He is also interested in applications of information theoretic tools to other areas. He expects to graduate in July 2018.
Young Kun Ko, Princeton
I am a PhD student at Princeton University advised by Mark Braverman. My main focus is on complexity theory via hardness amplification using information theoretic toolkits. Currently I am interested in (i) understanding limits and powers of various models of parallel repetitions; (ii) using techniques from direct sum to understand Data Structure Lower Bounds.
Tom Gur, Berkeley
Tom Gur is a postdoc in the EECS department at UC Berkeley. He received his Ph.D. from the Weizmann Institute of Science, where his advisor was Oded Goldreich. His research focuses on sublinear algorithms and verifiable computing, as well as in their interplay with coding theory, complexity theory, cryptography, and combinatorics.
Cyrus Rashtchian,
University of Washington
I am a final-year PhD student in the Theory and MISL groups at the University of Washington, advised by Paul Beame. My research revolves around large-scale similarity search and statistical estimation problems. This past year, I have worked on computational challenges associated with storing digital data in synthetic DNA. Overall, I enjoy exploring connections between modern massive data problems and classical theoretical computer science and combinatorics areas.
Yuqing Kong, Michigan
I am Yuqing, a phd candidate in the computer science department at University of Michigan. My research is driven by the desire to effectively collect massive amounts of information from disparate sources and aggregate the possibly unreliable information to solve large scale tasks. In the last four years, my research has developed an information theoretic approach to quantify, evaluate, and price unreliable information such that the crowds will be incentivized to invest efforts and provide high quality data, even if the data cannot be verified. In the future, I am planning to attack the information aggregation problem by leveraging the information theoretic techniques and insights from the design of the information elicitation mechanisms.
Samson Zhou, Purdue
Samson is a PhD candidate in the Department of Computer Science at Purdue University, under the supervision of Greg Frederickson and Elena Grigorescu. He received his undergraduate education at MIT, where he obtained a Bachelor's in math and computer science, as well as a Master's in computer science. He is a member of the Theory Group at Purdue, and his current research interests are sublinear and approximation algorithms, with an emphasis on streaming algorithms and graph pebbling.
Lin F. Yang, Princeton
I work in the area of sublinear algorithms. I obtained my Ph.D. degree from Johns Hopkins University. My research is to understand the capability of the streaming/sketching model, design sublinear time and space algorithms for data mining and machine learning.
Saad Quader, UConn
I love to understand the mathematics that underpins computer science. In particular, I have been using probabilistic tools to analyze randomized algorithms. "Chernoff bounds," "Boolean hypercube," "Gaussian distribution," "Fourier transform," and "Linear operators" are some of the keywords that I deal with in a daily basis. My projects involve coding theory, discrete geometry, optimization, and cryptography.
Sign-up Instructions: If you are interested in participating, please send the ITCS organizers an e-mail at with the following information by January 8.

  • Name, Current Affiliation and Status (postdoc/student)
  • Your Photo
  • A short paragraph (3-4 sentences) about yourself and your research
  • Homepage URL
  • Your presentation: at most 4 slides in PDF format of which the first slide should be a title slide