Innovations in Theoretical Computer Science 2018

All talks of the conference (except the graduating bits) will be held at the MIT Bartos Theater, located on the ground floor of the Wiesner Building on MIT campus. The address is 20 Ames Street Building E15, Atrium Level, Cambridge, MA 02139. The conference reception and the poster session will be at the Marriott Hotel in Kendall Square and the graduating bits will be at the Kiva Room at the Stata Center. See here for detailed directions.

The conference proceedings is available at this link.

Day 1: Thursday, January 11, 2018

Breakfast: Provided
Session 1: 9:00 - 10:30 (Chair: Christos Papadimitriou)
Barriers for Rank Methods in Arithmetic Complexity
Klim Efremenko, Ankit Garg, Rafael Oliveira and Avi Wigderson.
Further limitations of the known approaches for matrix multiplication
Josh Alman and Virginia Vassilevska Williams.
Quantum Query Algorithms are Completely Bounded Forms
Srinivasan Arunachalam, Jop Briet and Carlos Palazuelos.
A Complete Characterization of Unitary Quantum Space
Bill Fefferman and Cedric Lin.
Coffee Break
Session 2: 11:00 - 12:30 (Chair: Anna Karlin)
Lattice-Based Locality Sensitive Hashing is Optimal
Karthekeyan Chandrasekaran, Daniel Dadush, Venkata Gandikota and Elena Grigorescu.
Approximate Clustering with Same-Cluster Queries
Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal and Amit Kumar.
Edge Estimation with Independent Set Oracles
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian and Makrand Sinha.
Computing exact minimum cuts without knowing the graph
Aviad Rubinstein, Tselil Schramm and S. Matthew Weinberg.
Lunch: Provided
Session 3: 14:00 - 15:30 (Chair: Guy Rothblum)
Relaxed Locally Correctable Codes
Tom Gur, Govind Ramnarayan and Ron Rothblum.
Local decoding and testing of polynomials over grids
Srikanth Srinivasan and Madhu Sudan.
Proofs of Proximity for Distribution Testing
Alessandro Chiesa and Tom Gur.
Efficient Testing without Efficient Regularity
Asaf Shapira and Lior Gishboliner.
Coffee Break
Session 4: 16:00 - 17:30 (Chair: Aviad Rubinstein)
Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity
Yuqing Kong and Grant Schoenebeck.
Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case
Yuqing Kong and Grant Schoenebeck.
An Axiomatic Study of Scoring Rule Markets
Rafael Frongillo and Bo Waggoner.
On Price versus Quality
Avrim Blum and Yishay Mansour.

Reception: 6-8pm


Poster Session: 6:30-8pm

at the Marriott hotel in Kendall Square

Day 2: Friday, January 12, 2018

Breakfast: Provided
Session 5: 9:00 - 10:30 (Chair: Ronitt Rubinfeld)
Pseudo-Deterministic Proofs
Shafi Goldwasser, Ofer Grossman and Dhiraj Holden.
Simple doubly-efficient interactive proof systems for locally-characterizable sets
Oded Goldreich and Guy Rothblum.
Zero-Knowledge Proofs of Proximity
Itay Berman, Ron Rothblum and Vinod Vaikuntanathan.
Foundations of Homomorphic Secret Sharing
Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin and Stefano Tessaro.
Coffee Break
Session 6: 11:00 - 12:30 (Chair: Christos Papadimitriou)
Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method
Jelena Diakonikolas and Lorenzo Orecchia.
Non-Negative Sparse Regression and Column Subset Selection with L_1 Error
Aditya Bhaskara and Silvio Lattanzi.
Convergence Results for Neural Networks via Electrodynamics
Rina Panigrahy, Ali Rahimi, Sushant Sachdeva and Qiuyi Zhang.
Graph Clustering using Effective Resistance
Vedat Levi Alev, Nima Anari, Lap Chi Lau and Shayan Oveis Gharan.
Lunch: Provided
Session 7: 14:00 - 15:30 (Chair: Bobby Kleinberg)
Scheduling with Explorable Uncertainty
Christoph Dürr, Thomas Erlebach, Nicole Megow and Julie Meissner.
A Local-Search Algorithm for Steiner Forest
Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt and José Verschae.
Selection Problems in the Presence of Implicit Bias
Jon Kleinberg and Manish Raghavan.
Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh and Meirav Zehavi.
Coffee Break
Session 8: 16:00 - 17:30 (Chair: Bobby Kleinberg)
Distance-preserving graph contractions
Frieder Smolny, Karl Däubel, Aaron Bernstein, Max Klimm, Yann Disser and Torsten Mütze.
Making Asynchronous Distributed Computations Robust to Noise
Keren Censor-Hillel, Ran Gelles and Bernhard Haeupler.
Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
Shay Solomon.
Long-term Memory and the Densest K-Subgraph Problem
Robert Legenstein, Wolfgang Maass, Christos Papadimitriou and Santosh Vempala.

Graduating Bits: 6:30pm

at Stata Center, 32G-449 (Kiva)

Day 3: Saturday, January 13, 2018

Breakfast: Provided
Session 9: 9:00 - 10:10 (Chair: Tselil Schramm)
Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs
Olaf Beyersdorff, Joshua Blinkhorn and Luke Hinde.
Stabbing Planes
Noah Fleming, Robert Robere, Paul Beame, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov and Toniann Pitassi.
Towards a Unified Complexity Theory of Total Functions
Paul Goldberg and Christos Papadimitriou.
Coffee Break
Session 10: 10:40 - 12:10 (Chair: Bernard Chazelle)
Matrix Completion and Related Problems via Strong Duality
Maria-Florina Balcan, Yingyu Liang, David P. Woodruff and Hongyang Zhang.
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru and David P. Woodruff.
A Quasi-Random Approach to Matrix Spectral Analysis
Lior Eldar and Michael Ben-Or.
Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory.
Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter and Avi Wigderson.
Lunch: Provided
Session 11: 13:45 - 15:35 (Chair: Yael Kalai)
Differential Privacy on Finite Computers
Victor Balcer and Salil Vadhan.
Finite Sample Differentially Private Confidence Intervals
Vishesh Karwa and Salil Vadhan.
A Candidate for a Strong Separation of Information and Communication
Mark Braverman, Anat Ganor, Gillat Kol and Ran Raz.
Information Value of the Game
Mark Braverman and Young Kun Ko.
Minimum Circuit Size, Graph Isomorphism, and Related Problems
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore and Andrew Morgan.
Coffee Break
Session 12: 16:10 - 17:40 (Chair: Anna Karlin)
A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair and Michael Kowalczyk.
Limits for Rumor Spreading in stochastic populations
Lucas Boczkowski, Ofer Feinerman, Amos Korman and Emanuele Natale.
Toward a Theory of Markov Influence Systems and their Renormalization
Bernard Chazelle.
Learning Dynamics and the Co-Evolution of Competing Sexual Species
Georgios Piliouras and Leonard Schulman.

Day 4: Sunday, January 14, 2018

Breakfast: Provided
Session 13: 9:00 - 10:30 (Chair: Greg Valiant)
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning
Dana Moshkovitz and Michal Moshkovitz.
Pseudorandom Generators for Low Sensitivity Functions
Pooya Hatami and Avishay Tal.
Agnostic Learning by Refuting
Pravesh K Kothari and Roi Livni.
A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma
Greg Yang.
Coffee Break
Session 14: 11:00 - 12:30 (Chair: Ronitt Rubinfeld)
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
Jacob Steinhardt, Moses Charikar and Gregory Valiant.
Recovering Structured Probability Matrices
Qingqing Huang, Sham M. Kakade, Weihao Kong and Gregory Valiant.
Learning Discrete Distributions from Untrusted Batches
Mingda Qiao and Gregory Valiant.
Competing bandits: learning under competition
Yishay Mansour, Aleksandrs Slivkins and Zhiwei Steven Wu.
Lunch: Provided
Session 15: 14:00 - 15:10 (Chair: Greg Valiant)
Fine-grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch and Virginia Williams.
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
Irit Dinur and Pasin Manurangsi.
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
Amir Abboud and Aviad Rubinstein.

End of Conference.