ITCS 2015 ACCEPTED PAPERS (in order of submission)

Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication
Mika Goos; Toniann Pitassi; Thomas Watson

Why are images smooth?
Uriel Feige

Standard Simplices and Pluralities are Not the Most Noise Stable
Steven Heilman; Elchanan Mossel; Joe Neeman

Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback
Klim Efremenko; Ran Gelles; Bernhard Haeupler

Direct Sum Testing
Roee David; Irit Dinur; Elazar Goldenberg; Guy Kindler; Igor Shinkar

Non-Interactive Proofs of Proximity
Tom Gur; Ron D Rothblum

On Sample-Based Testers
Oded Goldreich; Dana Ron

Mechanism Design with Strategic Mediators
Moshe Babaioff; Moran Feldman; Moshe Tennenholtz

The Computational Benefit of Correlated Instances
Irit Dinur; Shafi Goldwasser; Huijia Lin

Better Outcomes from More Rationality
Jing Chen; Silvio Micali; Rafael Pass

Sunflowers and Testing Triangle-Freeness of Functions
Ishay Haviv; Ning Xie

Any monotone property of $k$-uniform hypergraphs is weakly evasive
Timothy J. F. Black

On Multiplicative Weight Updates for Concave and Submodular Function Maximization
Chandra Chekuri; T.S. Jayram; Jan Vondrak

Simulating Noisy Channel Interaction
Mark Braverman; Jieming Mao

Fractal structures in Adversarial Prediction
Rina Panigrahy; Preyas Popat

Voting with Coarse Beliefs
Samantha Leung; Edward Lui; Rafael Pass

Deterministic Extractors for Additive Sources
Abhishek Bhowmick; Ariel Gabizon; Thai Hoang Le; David Zuckerman

Dynamic Models of Reputation and Competition in Job-Market Matching
Jon Kleinberg; Sigal Oren

It'll probably work out: improved list-decoding through random operations
Atri Rudra; Mary Wootters

Sketching Cuts in Graphs and Hypergraphs
Dmitry Kogan; Robert Krauthgamer

An entangled-prover interactive proof system for the local Hamiltonian problem
Joseph Fitzsimons; Thomas Vidick

lp Testing and Learning of Discrete Distributions
Bo Waggoner

A New Approach to the Sensitivity Conjecture
Justin Gilmer; Michal Koucký; Michael Saks

Homophily and the Glass Ceiling Effect in Social Networks
Chen Avin; Barbara Keller; Zvi Lotker; Claire Mathieu; David Peleg; Yvonne-Anne Pignolet

Verifiably Truthful Mechanisms
Simina Brânzei; Ariel D. Procaccia

Communication with Imperfectly Shared Randomness
Clement Louis Canonne; Venkatesan Guruswami; Raghu Meka; Madhu Sudan

Privacy-Preserving Public Information for Sequential Games
Avrim Blum; Jamie Morgenstern; Ankit Sharma; Adam Smith

Separation between Estimation and Approximation
Uriel Feige; Shlomo Jozeph

Optimally Resilient and Adaptively Secure Multi-Party Computation with Low Communication Locality
Nishanth Chandran; Wutichai Chongchitmate; Juan A. Garay; Shafi Goldwasser; Rafail Ostrovsky; Vassilis Zikas

Very sparse additive spanners and emulators
Greg Bodwin; Virginia Vassilevska Williams

Robust Hierarchical $k$-Center Clustering
Silvio Lattanzi; Stefano Leonardi; Vahab Mirrokni; Ilya Razenshteyn

On The Communication Complexity of Secure Function Evaluation with Long Output
Pavel Hubacek; Daniel Wichs

Accuracy for Sale: Aggregating Data with a Variance Constraint
Rachel Cummings; Katrina Ligett; Aaron Roth; Zhiwei Steven Wu; Juba Ziani

A Physically Universal Cellular Automaton
Luke Schaeffer

Restricted Distribution Automatizability in PAC-Semantics
Brendan Juba

Interactive Coding for Multiparty Protocols
Abhishek Jain; Yael Tauman Kalai; Allison Lewko

Complex Contagions in Kleinberg's Small World Model
Roozbeh Ebrahimi; Jie Gao; Golnaz Ghasemiesfeh; Grant Schoenebeck

On Learning Mixture Models for Permutations
Flavio Chierichetti; Anirban Dasgupta; Ravi Kumar; Silvio Lattanzi

Information Causality, Szemeredi-Trotter and algebraic variants of CHSH
Mohammad Bavarian; Peter W. Shor

Uniform Sampling for Matrix Approximation
Michael B. Cohen; Yin Tat Lee; Cameron Musco; Christopher Musco; Richard Peng; Aaron Sidford

Arithmetic Cryptography
Benny Applebaum; Jonathan Avron; Christina Brzuska

The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data
Brynmor Chapman; Ryan Williams

Relax, no need to round: integrality of clustering formulations
Pranjal Awasthi; Afonso S. Bandeira; Moses Charikar; Ravishanker Krishnaswamy; Soledad Villar; Rachel Ward

Deterministic Rateless Codes for BSC
Benny Applebaum; Liron David; Guy Even

Natural Selection as an Inhibitor of Genetic Diversity
Ruta Mehta; Ioannis Panageas; Georgios Piliouras