ITCS 2016
Program
8:30am-9:15am: Breakfast (Media Lab, outside E14-633)
Session 1: Thursday January 14, 2016,
9:15am-10:30am (Media Lab, E14-633)
Chair: Sanjeev Khanna
Can Almost Everybody be Almost Happy? PCP for PPAD and the
Inapproximability of Nash (pdf)
Yakov Babichenko (Technion); Christos Papadimitriou (UC
Berkeley); Aviad Rubinstein (UC Berkeley).
Mechanisms With Costly Knowledge
Atalay M. Ileri (MIT); Silvio Micali (MIT).
On the Computational Complexity of Optimal Simple Mechanisms (pdf)
(Best Student Paper)
Aviad Rubinstein (UC Berkeley)
10:30am-11:00am: Coffee Break
Session 2. Thursday January 14th,
11:00am - 12:40pm (Media Lab, E14-633)
Chair: Madhu Sudan
Permanent v. Determinant: An exponential lower bound
assuming symmetry
(pdf,
slides)
J.M. Landsberg (Texas A&M); Nicolas Ressayre
(University of Lyon I).
On Hardness of Approximating the Parameterized Clique
Problem
(pdf,
slides)
Subhash Khot (NYU); Igor Shinkar (NYU),
The Complexity of DNF of Parities
(pdf,
slides)
Gil Cohen (Caltech); Igor Shinkar (NYU).
Smooth Boolean functions are easy: efficient algorithms for
low sensitivity functions
(pdf,
slides)
Parikshit Gopalan (Microsoft Research); Noam Nisan (Hebrew
U. & Microsoft Research); Rocco Servedio (Columbia);
Kunal Talwar (Google Research); Avi Wigderson (IAS).
12:40pm-2:00pm: Lunch (provided)
Session 3. Thursday January 14th, 2:00pm - 3:40pm
(Media Lab, E14-633)
Chair: Rocco Servedio
Local Algorithms for Block Models with Side Information
(pdf)
Elchanan Mossel (U. Penn & Berkeley); Jiaming Xu (U.
Penn).
Distribution Design
Amos Beimel (Ben Gurion); Ariel Gabizon (Technion);
Yuval Ishai (Technion & UCLA); Eyal Kushilevitz
(Technion).
Sampling Correctors
(pdf,
slides)
Clément Canonne (Columbia University); Themis Gouleakis
(MIT); Ronitt Rubinfeld (MIT & Tel Aviv).
On Being Far from Far and on Dual Problems in Property
Testing
(pdf,
slides)
Roei Tell (Weizmann).
3:40pm-4:10pm: Refreshments
Session 4. Thursday
January 14th, 4:10pm - 5:25pm (Media Lab, E14-633)
Chair: Brendan Juba
Strategic Classification
(pdf)
Moritz Hardt (Google Research); Nimrod Megiddo (IBM
Almaden); Christos Papadimitriou (Berkeley); Mary
Wootters (CMU).
A PAC Approach to Application-Specific Algorithm
Selection
(pdf)
Rishi Gupta (Stanford); Tim Roughgarden (Stanford).
An Axiomatic Approach to Community Detection
(pdf)
Christian Borgs (Microsoft Research); Jennifer
Chayes (Microsoft Research); Adrian Marple
(Stanford); Shang-Hua Teng (USC).
Thursday 6:30pm:
Reception at The Marriott Hotel (note change in location)
8:30am-9:15am: Breakfast (Media Lab, outside E14-633)
Session 5. Friday,
January 15th, 9:15am - 10:30am (Media Lab,
E14-633)
Chair: Yael Kalai
Obfuscating Conjunctions under Entropic Ring LWE
Zvika Brakerski (Weizmann); Vinod Vaikuntanathan
(MIT); Hoeteck Wee (ENS); Daniel Wichs
(Northeastern).
Secure Multiparty Computation with General
Interaction Patterns
(pdf)
Shai Halevi (IBM Research); Yuval Ishai
(Technion); Abhishek Jain (Johns Hopkins); Eyal
Kushilevitz (Technion); Tal Rabin (IBM
Research).
Fully Succinct Garbled RAM
(pdf)
Ran Canetti (Boston U. & Tel Aviv); Justin
Holmgren (MIT)
&
Cryptography for Parallel RAM from
Indistinguishability Obfuscation
(pdf)
Yu-Chi Chen (Academia Sinica); Sherman S.M. Chow (Chinese University of Hong Kong); Kai-Min Chung (Academia Sinica); Russell W.F. Lai (Chinese University of Hong Kong); Wei-Kai Lin (Academia Sinica); Hong-Sheng Zhou (Virginia Commonwealth University)
10:30am-11:00am: Coffee Break
Session 6. Friday, January 15th,
11:00am - 12:40pm (Media Lab, E14-633)
Chair: Yaron Singer
Timeability of Extensive-Form Games
(pdf,
slides)
Sune K. Jakobsen (Queen Mary U.; London);
Troels B. Sørensen (IT-University of
Copenhagen); Vincent Conitzer (Duke
University).
Auction Revenue in the General
Spiteful-Utility Model
(pdf)
Jing Chen (Stony Brook); Silvio Micali
(MIT).
How to Incentivize Data-Driven Collaboration
Among Competing Parties
(pdf)
Pablo Daniel Azar (MIT); Shafi Goldwasser
(MIT & Weizmann); Sunoo Park (MIT).
From Nash equilibria to chain recurrent
sets: Solution concepts and topology
Christos H. Papadimitriou (Berkeley);
Georgios Piliouras (Singapore U. Tech. &
Design).
12:40pm-2:00pm: Lunch (provided)
Session 7.
Friday, January 15th, 2:00pm - 3:40pm
(Media Lab, E14-633)
Chair: Adam Kalai
Rational Proofs with Multiple Provers
(pdf, slides)
Jing Chen (Stony Brook); Samuel McCauley
(Stony Brook); Shikha Singh (Stony
Brook).
Lower bounds: from circuits to QBF proof
systems
(pdf, slides)
Olaf Beyersdorff (University of Leeds);
Ilario Bonacina (Sapienza University
Rome); Leroy Chew (University of Leeds).
Satisfiability on Mixed Instances
(pdf)
Ruiwen Chen (U. Edinburgh); Rahul
Santhanam (U. Edinburgh).
Nondeterministic extensions of the
Strong Exponential Time Hypothesis and
consequences for non-reducibility
Marco L. Carmosino (UCSD); Jiawei Gao
(UCSD); Russell Impagliazzo (UCSD); Ivan
Mikhailin (UCSD); Ramamohan Paturi
(UCSD); Stefan Schneider (UCSD).
3:40pm-4:10pm: Refreshments
Session
8. Friday, January 15th, 4:10pm -
5:25pm (Media Lab, E14-633)
Chair: Madhu Sudan
Coordination Complexity: Small
Information Coordinating Large
Populations
(pdf)
Rachel Cummings (Caltech); Katrina
Ligett (Caltech); Jaikumar
Radhakrishnan (TIFR); Aaron Roth (U.
Penn.); Zhiwei Steven Wu (U. Penn).
On a Natural Dynamics for Linear
Programming
(pdf, slides)
Damian Straszak (EPFL); Nisheeth K.
Vishnoi (EPFL).
On the Space Complexity of Linear
Programming with Preprocessing
(pdf)
Yael Kalai (Microsoft Research); Ran
Raz (Weizmann & IAS); Oded Regev
(NYU).
Friday 6:30pm - Graduating
Bits (Stata Center, Kiva/Patil
Room, 32-G449)
Chair: Boaz Barak
8:30am-9:15am: Breakfast (Stata Center, outside 32-141)
Session
9. Saturday, January 16th,
9:15am - 10:30am (Stata
Center, 32-141)
Chair: Nisheeth Vishnoi
Spectral Embedding of
k-Cliques; Graph
Partitioning and k-Means
Pranjal Awasthi (Princeton);
Moses Charikar (Princeton);
Ravishankar Krishnaswamy
(Microsoft Research); Ali
Kemal Sinop (UC Berkeley).
On Sketching Quadratic Forms
(pdf, slides)
Alexandr Andoni (Columbia);
Jiecao Chen (Indiana U.
Bloomington); Robert
Krauthgamer (Weizmann); Bo
Qin (HKUST); David P.
Woodruff (IBM Almaden); Qin
Zhang (Indiana U.
Bloomington).
Energy-Efficient Algorithms
(slides)
Erik D. Demaine (MIT);
Geronimo J. Mirano (MIT);
Jayson Lynch (MIT); Nirvan
Tyagi (MIT).
10:30am-11:00am: Coffee Break
Session
10. Saturday, January
16th, 11:00am -
12:40pm (Stata Center,
32-141)
Chair: Yael Kalai
How to Bootstrap
Anonymous Communication
(pdf,
slides)
Sune K. Jakobsen (Queen
Mary U.; London);
Claudio Orlandi (Aarhus
U.).
Time-Lock Puzzles from
Randomized Encodings
(pdf)
Nir Bitansky (MIT);
Shafi Goldwasser (MIT
& Weizmann);
Abhishek Jain (Johns
Hopkins); Omer Paneth
(Boston U.); Vinod
Vaikuntanathan (MIT);
Brent Waters (UT
Austin).
Is There an Oblivious
RAM Lower Bound?
(pdf)
Elette Boyle (IDC
Herzliya); Moni Naor
(Weizmann).
Simultaneous Private
Learning of Multiple
Concepts
(pdf, slides)
Mark Bun (Harvard
University); Kobbi
Nissim (Ben-Gurion &
Harvard); Uri Stemmer
(Ben-Gurion University).
12:40pm-2:00pm: Lunch (provided)
Session
11. Saturday,
January 16th,
2:00pm - 3:40pm
(Stata Center,
32-141)
Chair: Thomas Vidick
Information
Complexity Density
and Simulation of
Protocols
(pdf,
slides)
Himanshu Tyagi
(IISc.); Shaileshh
Venkatakrishnan
(UIUC); Pramod
Viswanath (UIUC);
Shun Watanabe (Tokyo
U. Agriculture &
Tech.).
The space "just
above" BQP
(pdf, slides)
Scott Aaronson
(MIT); Adam
Bouland (MIT);
Joseph Fitzsimons
(Singapore U. Tech.
and Design &
National U.
Singapore); Mitchell
Lee (MIT).
On the Computational
Complexity of Limit
Cycles in Dynamical
Systems
(pdf)
Christos H.
Papadimitriou
(Berkeley); Nisheeth
K. Vishnoi (EPFL).
Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
(pdf,
slides)
Alexander Golovnev
(NYU); Alexander S.
Kulikov (Steklov
Institute; St.
Petersburg).
3:40pm:
END