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) Lopatie Conference Center


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)



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


Main Page For ITCS 2015 Local Information For ITCS 2015