CINXE.COM
<!DOCTYPE html> <html> <head> <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css"> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1"> <link rel="stylesheet" href="http://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css"> <link rel="stylesheet" type="text/css" href="../style.css"> <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.12.4/jquery.min.js"></script> <script src="http://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/js/bootstrap.min.js"></script> <script src="//code.jquery.com/jquery-1.10.2.js"></script> <script> $(function(){ $("#header").load("../header.html"); $("#footer").load("../footer.html"); }); </script> </head> <body class> <div id="header"></div> <div id="pg-wrapper"> <div class="container-fluid" id="all-but-header"> <div class="row"> <div class="col-md-11"> <h3>ITCS 2017 Accepted Papers</h3> <hr> <div> <a href="http://theory.epfl.ch/straszak/" target="_blank">Damian Straszak</a> and <a href="http://theory.epfl.ch/vishnoi/Home.html" target="_blank">Nisheeth K. Vishnoi</a>. IRLS and Slime Mold: Equivalence and Convergence </div> <div> Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz and Vinod Vaikuntanathan. Low-Complexity Cryptographic Hash Functions</div> <div><span><a href="http://www.cse.psu.edu/%7Efurer" target="_blank">Martin F眉rer</a>. </span><span>Multi-Clique-Width</span></div> <div><span><a href="http://www.cse.wustl.edu/%7Ebjuba/" target="_blank">Brendan Juba</a>. </span><span>Conditional Sparse Linear Regression</span></div> <div><span><span><a href="http://www.sztaki.hu/%7Eivanyos" target="_blank">Gabor Ivanyos</a>, <a href="http://sites.google.com/site/jimmyqiao86/" target="_blank">Youming Qiao</a> and K. V. Subrahmanyam</span>. </span><span>Constructive non-commutative rank computation is in deterministic polynomial time</span></div> <div><span><span>Jon Schneider, Ariel Schvartzman and S. Matthew Weinberg</span>. </span><span>Condorcet-Consistent and Approximately Strategyproof Tournament Rules</span></div> <div><span><span><a href="http://www.cs.columbia.edu/%7Erocco" target="_blank">Rocco Servedio</a> and <a href="http://www.cs.columbia.edu/%7Eliyang/" target="_blank">Li-Yang Tan</a></span>. </span><span>What circuit classes can be learned with non-trivial savings?</span></div> <div><span><span>Mark Braverman, Sumegha Garg and Ariel Schvartzman</span>. </span><span>Network coding in undirected graphs is either very helpful or not helpful at all</span></div> <div><span><span><a href="http://www.cs.purdue.edu/homes/jblocki" target="_blank">Jeremiah Blocki</a>, Manuel Blum, Anupam Datta and Santosh Vempala</span>. </span><span>Towards Human Computable Passwords</span></div> <div><span><a href="http://www.cs.cmu.edu/" target="_blank">Ryan O'Donnell</a>. </span><span>SOS is not obviously automatizable, even approximately</span></div> <div><span>Matthew Hastings. </span><span>Quantum Codes from High-Dimensional Manifolds</span></div> <div><span><span>Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi and Erisa Terolli</span>. </span><span>The Distortion of Locality Sensitive Hashing</span></div> <div><span><span><a href="http://users.cms.caltech.edu/%7Eschulman/index.html" target="_blank">Leonard J. Schulman</a> and Umesh Vazirani</span>. </span><span>The Duality Gap for Two-Team Zero-Sum Games</span></div> <div><span><span>Bernard Chazelle and Chu Wang</span>. </span><span>Self-Sustaining Iterated Learning</span></div> <div><span><span>Daniel Stubbs and Virginia Vassilevska Williams</span>. </span><span>Metatheorems for dynamic weighted matching</span></div> <div><span><span>David Mass and Tali Kaufman</span>. </span><span>High Dimensional Random Walks and Colorful Expansion</span></div> <div><span><span>Ran Gelles and Yael Kalai</span>. </span><span>Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks</span></div> <div><span><span><a href="http://www.cs.columbia.edu/%7Eccanonne/" target="_blank">Cl茅ment Canonne</a>, <a href="http://www.cs.purdue.edu/homes/egrigore/" target="_blank">Elena Grigorescu</a>, Siyao Guo, Akash Kumar and Karl Wimmer</span>. </span><span>Testing k-Monotonicity</span></div> <div><span><span>Harry Buhrman, Matthias Christandl and <a href="http://homepages.cwi.nl/%7Ejzuiddam/" target="_blank">Jeroen Zuiddam</a></span>. </span><span>Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication</span></div> <div><span><span>Shafi Goldwasser and Dhiraj Holden</span>. </span><span>The Complexity of Problems in P Given Correlated Instances</span></div> <div><span><span>Iordanis Kerenidis and Anupam Prakash</span>. </span><span>Quantum Recommendation Systems </span></div> <div><span><span><a href="http://www.arpitaghosh.com/" target="_blank">Arpita Ghosh</a> and <a href="http://www.cs.cornell.edu/%7Erdk/" target="_blank">Robert Kleinberg</a></span>. </span><span>Inferential Privacy Guarantees for Differentially Private Mechanisms</span></div> <div><span><span><a href="http://www.scottaaronson.com/" target="_blank">Scott Aaronson</a>, Daniel Grier and Luke Schaeffer</span>. </span><span>The Classification of Reversible Bit Operations</span></div> <div><span><a href="http://people.csail.mit.edu/zeyuan" target="_blank">Zeyuan Allen-Zhu</a> and Lorenzo Orecchia. </span><span>Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent</span></div> <div><span><span><a href="http://www.wisdom.weizmann.ac.il/%7Ezvikab" target="_blank">Zvika Brakerski</a>, Nishanth Chandran, Vipul Goyal, Aayush Jain, Amit Sahai and <a href="http://www.cs.huji.ac.il/%7Esegev" target="_blank">Gil Segev</a></span>. </span><span>Hierarchical Functional Encryption</span></div> <div><span><span>Sam Buss, Valentine Kabanets, Antonina Kolokolova and <a href="http://http/www.math.cas.cz/%7Ekoucky" target="_blank">Michal Koucky</a></span>. </span><span>Expander Construction in VNC^1</span></div> <div><span><span>Xi Chen, Yu Cheng and Bo Tang</span>. </span><span>Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games</span></div> <div><span><span><a href="http://ie.technion.ac.il/Home/Users/yakovbab.html" target="_blank">Yakov Babichenko</a> and <a href="http://drona.csa.iisc.ernet.in/%7Ebarman/" target="_blank">Siddharth Barman</a></span>. </span><span>Algorithmic Aspects of Private Bayesian Persuasion</span></div> <div><span><span>Lennart Gulikers, Marc Lelarge and Laurent Massouli茅</span>. </span><span>Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models</span></div> <div><span><span>Pavel Hubacek, <a href="http://www.wisdom.weizmann.ac.il/%7Enaor/" target="_blank">Moni Naor</a> and Eylon Yogev</span>. </span><span>The Journey from NP to TFNP Hardness</span></div> <div><span><span>Amey Bhangale, Irit Dinur and Inbal Rachel Livni Navon</span>. </span><span>Cube vs Cube Low Degree Test</span></div> <div><span><span>Christopher Kennedy and Rachel Ward</span>. </span><span>Fast Cross-Polytope Locality-Sensitive Hashing</span></div> <div><span><span><a href="http://www.wisdom.weizmann.ac.il/%7Etom/" target="_blank">Tom Gur</a> and <a href="http://people.csail.mit.edu/ronr/" target="_blank">Ron Rothblum</a></span>. </span><span>A Hierarchy Theorem for Interactive Proofs of Proximity</span></div> <div><span><span><a href="http://www.cs.princeton.edu/%7Esgopi" target="_blank">Sivakanth Gopi</a>, <a href="http://www.cs.princeton.edu/%7Ezdvir" target="_blank">Zeev Dvir</a> and <a href="http://homepages.cwi.nl/%7Ejop/" target="_blank">Jop Briet</a></span>. </span><span>Outlaw distributions and locally decodable codes</span></div> <div><span><span><a href="https://bavarian.mit.edu/" target="_blank">Mohammad Bavarian</a>, Thomas Vidick and Henry Yuen</span>. </span><span>Parallel repetition via fortification: analytic view and the quantum case</span></div> <div><span><span>Jon Kleinberg, Sendhil Mullainathan and Manish Raghavan</span>. </span><span>Inherent Trade-Offs in the Fair Determination of Risk Scores</span></div> <div><span><span><a href="http://www.cs.jhu.edu/%7Emdinitz/" target="_blank">Michael Dinitz</a> and Zeyu Zhang</span>. </span><span>Approximating Approximate Distance Oracles</span></div> <div><span>Aviad Rubinstein. </span><span>Detecting communities is hard... and counting them is even harder!</span></div> <div><span><span>Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali and Vijay Vazirani</span>. </span><span>Mutation, Sexual Reproduction and Survival in Dynamic Environments</span></div> <div><span><span>Aaron Bernstein, <a href="https://sites.google.com/site/kopelot/" target="_blank">Tsvi Kopelowitz</a>, <a href="http://www.eecs.umich.edu/%7Epettie" target="_blank">Seth Pettie</a>, <a href="http://www.cs.biu.ac.il/%7Eporately/" target="_blank">Ely Porat</a> and Clifford Stein</span>. </span><span>Simultaneously Load Balancing for Every $p$-norm, With Reassignments</span></div> <div><span><span><a href="http://people.csail.mit.edu/badih/" target="_blank">Badih Ghazi</a>, <a href="http://www.mycademic.com/view/home.jsp?uid=8001" target="_blank">Elad Haramaty</a>, Pritish Kamath and <a href="http://madhu.seas.harvard.edu/" target="_blank">Madhu Sudan</a></span>. </span><span>Compression in a Distributed Setting</span></div> <div><span><span>Abhinav Bommireddi and Eric Blais</span>. </span><span>Testing submodularity and other properties of valuation functions</span></div> <div><span><a href="http://www.cs.washington.edu/homes/jrl/" target="_blank">James Lee</a>. </span><span>Separators in region intersection graphs</span></div> <div><span><span>Monika Henzinger, Andrea Lincoln, Stefan Neumann and Virginia Vassilevska Williams</span>. </span><span>Conditional Hardness for Sensitivity Problems</span></div> <div><span><span>Yuval Peres, <a href="http://research.microsoft.com/en-us/um/people/mohits/" target="_blank">Mohit Singh</a> and Nisheeth Vishnoi</span>. </span><span>Random Walks in Polytopes and Negative Dependence</span></div> <div><span><span>Rui Chao, <a href="http://www-bcf.usc.edu/%7Ebreichar/" target="_blank">Ben Reichardt</a>, Chris Sutherland and <a href="http://users.cms.caltech.edu/%7Evidick/" target="_blank">Thomas Vidick</a></span>. </span><span>Overlapping qubits</span></div> <div><span><span>Irit Dinur, Prahladh Harsha, Rakesh Venkat and <a href="http://www.henryyuen.net/" target="_blank">Henry Yuen</a></span>. </span><span>Multiplayer parallel repetition for expander games</span></div> <div><span><span><a href="http://www.cameronmusco.com/" target="_blank">Cameron Musco</a>, Nancy Lynch and Merav Parter</span>. </span><span>Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks</span></div> <div><span>Silvio Micali. </span><span>Fast and Furious Byzantine Agreement</span></div> <div><span><span>Mathieu Lauri猫re and Dave Touchette</span>. </span><span>The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting</span></div> <div><span><span><a href="http://researcher.watson.ibm.com/researcher/view.php?person=us-vitaly" target="_blank">Vitaly Feldman</a> and <a href="http://people.csail.mit.edu/badih/" target="_blank">Badih Ghazi</a></span>. </span><span>On the Power of Learning from k-Wise Queries</span></div> <div><span><span>Shalev Ben-David, Pooya Hatami and Avishay Tal</span>. </span><span>Low-Sensitivity Functions from Unambiguous Certificates</span></div> <div><span><span><a href="http://www.cse.psu.edu/%7Erxp271/" target="_blank">Ramesh Krishnan S. Pallavoor</a>, <a href="http://www.cse.psu.edu/%7Esxr48/" target="_blank">Sofya Raskhodnikova</a> and <a href="http://www.cse.psu.edu/%7Enzm154/" target="_blank">Nithin Varma</a></span>. </span><span>Parameterized Property Testing of Functions</span></div> <div><span><span>Nima Anari, <a href="http://homes.cs.washington.edu/%7Eshayan/" target="_blank">Shayan Oveis Gharan</a>, Amin Saberi and Mohit Singh</span>. </span><span>Nash Social Welfare, Matrix Permanent, and Stable Polynomials</span></div> <div><span><span>Ioannis Panageas and Georgios Piliouras</span>. </span><span>Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions</span></div> <div><span><span><a href="http://www.ifi.uzh.ch/en/ce/people/schuldenzucker.html" target="_blank">Steffen Schuldenzucker</a>, <a href="http://www.ifi.uzh.ch/en/ce/people/seuken.html" target="_blank">Sven Seuken</a> and <a href="http://www.bf.uzh.ch/cms/en/battiston.stefano.html" target="_blank">Stefano Battiston</a></span>. </span><span>Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-hard</span></div> <div><span><span>Prasad Raghavendra, Nicholas Ryder and Nikhil Srivastava</span>. </span><span>Real-Stability Testing</span></div> <div><span>Benjamin Rossman. </span><span>An Improved Homomorphism Preservation Theorem from Lower Bounds in Circuit Complexity</span></div> <div><span><span><a href="http://www.cs.berkeley.edu/" target="_blank">Itai Arad</a>, Zeph Landau, Umesh Vazirani and Thomas Vidick</span>. </span><span>Rigorous RG algorithms and area laws for low energy eigenstates in 1D</span></div> <div><span><span><a href="https://sites.google.com/site/amirabboud/" target="_blank">Amir Abboud</a> and <a href="http://www.mit.edu/%7Ebackurs/" target="_blank">Arturs Backurs</a></span>. </span><span>Towards Hardness of Approximation for Polynomial Time Problems</span></div> <div><span><span>Jo毛l Alwen, <a href="http://www.csc.kth.se/%7Esfdr/" target="_blank">Susanna F. de Rezende</a>, <a href="http://www.csc.kth.se/%7Ejakobn/" target="_blank">Jakob Nordstr枚m</a> and <a href="http://www.csc.kth.se/%7Evinyals/" target="_blank">Marc Vinyals</a></span>. </span><span>Cumulative Space in Black-White Pebbling and Resolution</span></div> </div> <br> </div> </div> </div> </div> <div id="footer"></div> </body> </html>