Program for ITCS 2015 January 11-13 (flyer, rollup poster)
All events are at the Lopatie Conference Center, except dinner on Monday
SUNDAY January 11th 2015
SESSION 1 (9-10:45)
Interactive Coding for Multiparty Protocols
Abhishek Jain; Yael Tauman
Kalai; Allison Lewko
Maximal Noise in Interactive Communication over
Erasure Channels and Channels with Feedback
Klim Efremenko; Ran Gelles; Bernhard Haeupler
Simulating Noisy Channel Interaction
Mark Braverman; Jieming Mao
Deterministic Rateless
Codes for BSC
Benny Applebaum; Liron David; Guy Even
COFFEE (10:45-11:10)
SESSION 2 (11:10-12:55)
Homophily and the Glass Ceiling Effect in Social Networks
Chen Avin; Barbara
Keller; Zvi Lotker; Claire
Mathieu; David Peleg; Yvonne-Anne Pignolet
Dynamic Models of Reputation and Competition in
Job-Market Matching
Jon Kleinberg; Sigal
Oren
Voting with Coarse
Beliefs
Samantha Leung; Edward Lui;
Rafael Pass
Complex Contagions in Kleinberg's Small World
Model
Roozbeh Ebrahimi; Jie Gao; Golnaz
Ghasemiesfeh; Grant Schoenebeck
LUNCH (12:55-2:15)
SESSION 3 (2:15-4)
Natural Selection as an Inhibitor of Genetic
Diversity
Ruta Mehta; Ioannis Panageas; Georgios Piliouras
Fractal structures in Adversarial Prediction
Rina Panigrahy; Preyas Popat
On Learning Mixture Models for Permutations
Flavio Chierichetti; Anirban Dasgupta; Ravi Kumar;
Silvio Lattanzi
Restricted Distribution Automatizability
in PAC-Semantics
Brendan Juba
COFFEE (4-4:25)
SESSION 4 (4:25-6:10)
An entangled-prover
interactive proof system for the local Hamiltonian problem
Joseph Fitzsimons; Thomas Vidick
Zero-Information Protocols and Unambiguity in
Arthur-Merlin Communication
Mika Goos; Toniann Pitassi; Thomas Watson
Information Causality, Szemeredi-Trotter
and algebraic variants of CHSH
Mohammad Bavarian; Peter W. Shor
Non-Interactive Proofs of Proximity
Tom Gur; Ron D Rothblum
Dinner (6:10-7:30)
Meet the new
Innovators (7:30-9:30)
MONDAY January 12th 2015
SESSION 5 (9-10:45)
Arithmetic Cryptography
Benny Applebaum;
Jonathan Avron; Christina Brzuska
The Hidden Communication Graph Model: Communication
Locality and Optimal Resiliency with Adaptive Faults
Nishanth Chandran; Wutichai Chongchitmate; Juan A. Garay; Shafi Goldwasser;
Rafail Ostrovsky; Vassilis Zikas
On The Communication Complexity of Secure
Function Evaluation with Long Output
Pavel Hubacek; Daniel Wichs
Privacy-Preserving Public Information for
Sequential Games
Avrim Blum; Jamie Morgenstern; Ankit Sharma; Adam
Smith
COFFEE (10:45-11:10)
SESSION 6 (11:10-12:55)
Uniform Sampling for Matrix Approximation
Michael B. Cohen; Yin Tat Lee; Cameron Musco; Christopher Musco; Richard
Peng; Aaron Sidford
Relax, no need to round: integrality of
clustering formulations
Pranjal Awasthi; Afonso S. Bandeira; Moses Charikar; Ravishankar Krishnaswamy; Soledad Villar;
Rachel Ward
On Multiplicative Weight Updates for Concave and
Submodular Function Maximization
Chandra Chekuri; T.S. Jayram; Jan Vondrak
Robust Hierarchical $k$-Center Clustering
Silvio Lattanzi;
Stefano Leonardi; Vahab Mirrokni; Ilya Razenshteyn
LUNCH (12:55-2)
SESSION 7: CRAIG GENTRY KEYNOTE (2-3)
Computing on the edge of chaos: structure and randomness
in
encrypted computation
COFFEE (3-3:20)
SESSION 8 (3:20-4:40)
The Computational Benefit of Correlated
Instances
Irit Dinur; Shafi Goldwasser; Huijia Lin
Why are images smooth?
Uriel Feige
A Physically Universal Cellular Automaton
Luke Schaeffer
BRIEF BREAK (4:40-4:50)
SESSION 9 (4:50-6:10)
A New Approach to the Sensitivity Conjecture
Justin Gilmer; Michal Koucky;
Michael Saks
Standard Simplices and
Pluralities are Not the Most Noise Stable
Steven Heilman; Elchanan Mossel; Joe Neeman
Communication with Imperfectly Shared Randomness
Clement Louis Canonne;
Venkatesan Guruswami; Raghu
Meka; Madhu Sudan
Dinner at Cassis, 132 Kedem
Street, Tel Aviv-Yaffo (Givat
Aliyah
Beach). Phone 03-575-3745. Busses leave at 7:15:
one bus from
Lopatie and one from Leonardo Hotel
TUESDAY January 13th 2015
SESSION 10 (9-10:45)
The Circuit-Input Game, Natural Proofs, and
Testing Circuits With Data
Brynmor Chapman; Ryan Williams
Separation between Estimation and Approximation
Uriel Feige; Shlomo Jozeph
Deterministic Extractors for Additive Sources
Abhishek Bhowmick;
Ariel Gabizon; Thai Hoang Le; David Zuckerman
It'll probably work out: improved list-decoding
through random operations
Atri Rudra; Mary Wootters
COFFEE (10:45-11:10)
SESSION 11 (11:10-12:55)
Verifiably Truthful Mechanisms
Simina Branzei; Ariel D. Procaccia
Mechanism Design with Strategic Mediators
Moshe Babaioff; Moran
Feldman; Moshe Tennenholtz
Accuracy for Sale: Aggregating Data with a
Variance Constraint
Rachel Cummings; Katrina Ligett;
Aaron Roth; Zhiwei Steven Wu; Juba Ziani
Better Outcomes from More Rationality
Jing Chen; Silvio Micali;
Rafael Pass
LUNCH (12:55-2:15)
SESSION 12 (2:15-4)
Direct Sum Testing
Roee David; Irit Dinur; Elazar Goldenberg; Guy Kindler; Igor Shinkar
On Sample-Based Testers
Oded Goldreich; Dana Ron
lp Testing and Learning of Discrete Distributions
Bo Waggoner
Sunflowers and Testing Triangle-Freeness of
Functions
Ishay Haviv; Ning Xie
COFFEE (4-4:25)
SESSION 13 (4:25-5:45)
Sketching Cuts in Graphs and Hypergraphs
Dmitry Kogan; Robert Krauthgamer
Very sparse additive spanners and emulators
Greg Bodwin; Virginia Vassilevska Williams
Any monotone property of $k$-uniform hypergraphs
is weakly evasive
Timothy J. F. Black
Conference adjourns