STOC 2017 – Author Index

A B C D E F G H I J K L M N O P R S T U V W X Y Z

	Aaronson, Scott	STOC '17: "The Computational Complexity ..." The Computational Complexity of Ball Permutations Scott Aaronson, Adam Bouland, Greg Kuperberg, and Saeed Mehraban (University of Texas at Austin, USA; Massachusetts Institute of Technology, USA; University of California at Davis, USA) @InProceedings{STOC17p345, author = {Scott Aaronson and Adam Bouland and Greg Kuperberg and Saeed Mehraban}, title = {The Computational Complexity of Ball Permutations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {345-344}, doi = {}, year = {2017}, }
	Abolhassani, Melika	STOC '17: "Beating 1-1/e for Ordered ..." Beating 1-1/e for Ordered Prophets Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi HajiAghayi, Robert Kleinberg, and Brendan Lucier (University of Maryland at College Park, USA; Cornell University, USA; Microsoft Research, USA) @InProceedings{STOC17p65, author = {Melika Abolhassani and Soheil Ehsani and Hossein Esfandiari and MohammadTaghi HajiAghayi and Robert Kleinberg and Brendan Lucier}, title = {Beating 1-1/e for Ordered Prophets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {65-64}, doi = {}, year = {2017}, }
	Agarwal, Naman	STOC '17: "Finding Approximate Local ..." Finding Approximate Local Minima Faster than Gradient Descent Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma (Princeton University, USA; IAS, USA) @InProceedings{STOC17p1339, author = {Naman Agarwal and Zeyuan Allen-Zhu and Brian Bullins and Elad Hazan and Tengyu Ma}, title = {Finding Approximate Local Minima Faster than Gradient Descent}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1339-1338}, doi = {}, year = {2017}, }
	Allen-Zhu, Zeyuan	STOC '17: "Finding Approximate Local ..." Finding Approximate Local Minima Faster than Gradient Descent Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma (Princeton University, USA; IAS, USA) @InProceedings{STOC17p1339, author = {Naman Agarwal and Zeyuan Allen-Zhu and Brian Bullins and Elad Hazan and Tengyu Ma}, title = {Finding Approximate Local Minima Faster than Gradient Descent}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1339-1338}, doi = {}, year = {2017}, } STOC '17: "Katyusha: The First Direct ..." Katyusha: The First Direct Acceleration of Stochastic Gradient Methods Zeyuan Allen-Zhu (IAS, USA; Princeton University, USA) @InProceedings{STOC17p1353, author = {Zeyuan Allen-Zhu}, title = {Katyusha: The First Direct Acceleration of Stochastic Gradient Methods}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1353-1352}, doi = {}, year = {2017}, }
	Alman, Josh	STOC '17: "Probabilistic Rank and Matrix ..." Probabilistic Rank and Matrix Rigidity Josh Alman and Ryan Williams (Massachusetts Institute of Technology, USA) @InProceedings{STOC17p709, author = {Josh Alman and Ryan Williams}, title = {Probabilistic Rank and Matrix Rigidity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {709-708}, doi = {}, year = {2017}, }
	Ambainis, Andris	STOC '17: "Quantum Algorithm for Tree ..." Quantum Algorithm for Tree Size Estimation, with Applications to Backtracking and 2-Player Games Andris Ambainis and Martins Kokainis (University of Latvia, Latvia) @InProceedings{STOC17p1101, author = {Andris Ambainis and Martins Kokainis}, title = {Quantum Algorithm for Tree Size Estimation, with Applications to Backtracking and 2-Player Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1101-1100}, doi = {}, year = {2017}, }
	Anari, Nima	STOC '17: "A Generalization of Permanent ..." A Generalization of Permanent Inequalities and Applications in Counting and Optimization Nima Anari and Shayan Oveis Gharan (Stanford University, USA; University of Washington, USA) @InProceedings{STOC17p415, author = {Nima Anari and Shayan Oveis Gharan}, title = {A Generalization of Permanent Inequalities and Applications in Counting and Optimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {415-414}, doi = {}, year = {2017}, }
	Andoni, Alexandr	STOC '17: "Approximate Near Neighbors ..." Approximate Near Neighbors for General Symmetric Norms Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten (Columbia University, USA; Northeastern University, USA; University of Toronto, Canada; Massachusetts Institute of Technology, USA) @InProceedings{STOC17p1003, author = {Alexandr Andoni and Huy L. Nguyen and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten}, title = {Approximate Near Neighbors for General Symmetric Norms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1003-1002}, doi = {}, year = {2017}, }
	Angel, Omer	STOC '17: "Local Max-Cut in Smoothed ..." Local Max-Cut in Smoothed Polynomial Time Omer Angel, Sébastien Bubeck, Yuval Peres, and Fan Wei (University of British Columbia, Canada; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC17p471, author = {Omer Angel and Sébastien Bubeck and Yuval Peres and Fan Wei}, title = {Local Max-Cut in Smoothed Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {471-470}, doi = {}, year = {2017}, }
	Angelidakis, Haris	STOC '17: "Algorithms for Stable and ..." Algorithms for Stable and Perturbation-Resilient Problems Haris Angelidakis, Konstantin Makarychev, and Yury Makarychev (Toyota Technological Institute at Chicago, USA; Northwestern University, USA) @InProceedings{STOC17p485, author = {Haris Angelidakis and Konstantin Makarychev and Yury Makarychev}, title = {Algorithms for Stable and Perturbation-Resilient Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {485-484}, doi = {}, year = {2017}, }
	Anshu, Anurag	STOC '17: "Exponential Separation of ..." Exponential Separation of Quantum Communication and Classical Information Anurag Anshu, Dave Touchette, Penghui Yao, and Nengkun Yu (National University of Singapore, Singapore; University of Waterloo, Canada; Perimeter Institute for Theoretical Physics, Canada; University of Maryland, USA; University of Technology Sydney, Australia) @InProceedings{STOC17p303, author = {Anurag Anshu and Dave Touchette and Penghui Yao and Nengkun Yu}, title = {Exponential Separation of Quantum Communication and Classical Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {303-302}, doi = {}, year = {2017}, }
	Arora, Sanjeev	STOC '17: "Provable Learning of Noisy-or ..." Provable Learning of Noisy-or Networks Sanjeev Arora, Rong Ge, Tengyu Ma, and Andrej Risteski (Princeton University, USA; Duke University, USA) @InProceedings{STOC17p1185, author = {Sanjeev Arora and Rong Ge and Tengyu Ma and Andrej Risteski}, title = {Provable Learning of Noisy-or Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1185-1184}, doi = {}, year = {2017}, }
	Artmann, Stephan	STOC '17: "A Strongly Polynomial Algorithm ..." A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming Stephan Artmann, Robert Weismantel, and Rico Zenklusen (ETH Zurich, Switzerland) @InProceedings{STOC17p1367, author = {Stephan Artmann and Robert Weismantel and Rico Zenklusen}, title = {A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1367-1366}, doi = {}, year = {2017}, }
	Arvind, V.	STOC '17: "Randomized Polynomial Time ..." Randomized Polynomial Time Identity Testing for Noncommutative Circuits V. Arvind, Pushkar S Joglekar, Partha Mukhopadhyay, and S. Raja (Institute of Mathematical Sciences, India; Vishwakarma Institute of Technology Pune, India; Chennai Mathematical Institute, India) @InProceedings{STOC17p919, author = {V. Arvind and Pushkar S Joglekar and Partha Mukhopadhyay and S. Raja}, title = {Randomized Polynomial Time Identity Testing for Noncommutative Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {919-918}, doi = {}, year = {2017}, }
	Azar, Yossi	STOC '17: "Online Service with Delay ..." Online Service with Delay Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi (Tel Aviv University, Israel; Duke University, USA) @InProceedings{STOC17p611, author = {Yossi Azar and Arun Ganesh and Rong Ge and Debmalya Panigrahi}, title = {Online Service with Delay}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {611-610}, doi = {}, year = {2017}, }
	Babaioff, Moshe	STOC '17: "The Menu-Size Complexity of ..." The Menu-Size Complexity of Revenue Approximation Moshe Babaioff, Yannai A. Gonczarowski, and Noam Nisan (Microsoft Research, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC17p961, author = {Moshe Babaioff and Yannai A. Gonczarowski and Noam Nisan}, title = {The Menu-Size Complexity of Revenue Approximation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {961-960}, doi = {}, year = {2017}, }
	Babichenko, Yakov	STOC '17: "Communication Complexity of ..." Communication Complexity of Approximate Nash Equilibria Yakov Babichenko and Aviad Rubinstein (Technion, Israel; University of California at Berkeley, USA) @InProceedings{STOC17p975, author = {Yakov Babichenko and Aviad Rubinstein}, title = {Communication Complexity of Approximate Nash Equilibria}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {975-974}, doi = {}, year = {2017}, }
	Balkanski, Eric	STOC '17: "The Limitations of Optimization ..." The Limitations of Optimization from Samples Eric Balkanski, Aviad Rubinstein, and Yaron Singer (Harvard University, USA; University of California at Berkeley, USA) @InProceedings{STOC17p1129, author = {Eric Balkanski and Aviad Rubinstein and Yaron Singer}, title = {The Limitations of Optimization from Samples}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1129-1128}, doi = {}, year = {2017}, }
	Ball, Marshall	STOC '17: "Average-Case Fine-Grained ..." Average-Case Fine-Grained Hardness Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan (Columbia University, USA; IDC Herzliya, Israel; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC17p541, author = {Marshall Ball and Alon Rosen and Manuel Sabin and Prashant Nalini Vasudevan}, title = {Average-Case Fine-Grained Hardness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {541-540}, doi = {}, year = {2017}, }
	Bansal, Nikhil	STOC '17: "Algorithmic Discrepancy Beyond ..." Algorithmic Discrepancy Beyond Partial Coloring Nikhil Bansal and Shashwat Garg (Eindhoven University of Technology, Netherlands) @InProceedings{STOC17p1017, author = {Nikhil Bansal and Shashwat Garg}, title = {Algorithmic Discrepancy Beyond Partial Coloring}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1017-1016}, doi = {}, year = {2017}, } STOC '17: "Faster Space-Efficient Algorithms ..." Faster Space-Efficient Algorithms for Subset Sum and k-Sum Nikhil Bansal, Shashwat Garg, Jesper Nederlof, and Nikhil Vyas (Eindhoven University of Technology, Netherlands; IIT Bombay, India) @InProceedings{STOC17p219, author = {Nikhil Bansal and Shashwat Garg and Jesper Nederlof and Nikhil Vyas}, title = {Faster Space-Efficient Algorithms for Subset Sum and k-Sum}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {219-218}, doi = {}, year = {2017}, }
	Barak, Boaz	STOC '17: "Quantum Entanglement, Sum ..." Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture Boaz Barak, Pravesh K. Kothari, and David Steurer (Harvard University, USA; Princeton University, USA; IAS, USA; Cornell University, USA) @InProceedings{STOC17p1087, author = {Boaz Barak and Pravesh K. Kothari and David Steurer}, title = {Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1087-1086}, doi = {}, year = {2017}, }
	Bavarian, Mohammad	STOC '17: "Hardness Amplification for ..." Hardness Amplification for Entangled Games via Anchoring Mohammad Bavarian, Thomas Vidick, and Henry Yuen (Massachusetts Institute of Technology, USA; California Institute of Technology, USA; University of California at Berkeley, USA) @InProceedings{STOC17p331, author = {Mohammad Bavarian and Thomas Vidick and Henry Yuen}, title = {Hardness Amplification for Entangled Games via Anchoring}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {331-330}, doi = {}, year = {2017}, }
	Ben-Aroya, Avraham	STOC '17: "An Efficient Reduction from ..." An Efficient Reduction from Two-Source to Non-malleable Extractors: Achieving Near-Logarithmic Min-entropy Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma (Tel Aviv University, Israel) @InProceedings{STOC17p1325, author = {Avraham Ben-Aroya and Dean Doron and Amnon Ta-Shma}, title = {An Efficient Reduction from Two-Source to Non-malleable Extractors: Achieving Near-Logarithmic Min-entropy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1325-1324}, doi = {}, year = {2017}, }
	Błasiok, Jarosław	STOC '17: "Streaming Symmetric Norms ..." Streaming Symmetric Norms via Measure Concentration Jarosław Błasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang (Harvard University, USA; Johns Hopkins University, USA; ETH Zurich, Switzerland; Weizmann Institute of Science, Israel) @InProceedings{STOC17p793, author = {Jarosław Błasiok and Vladimir Braverman and Stephen R. Chestnut and Robert Krauthgamer and Lin F. Yang}, title = {Streaming Symmetric Norms via Measure Concentration}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {793-792}, doi = {}, year = {2017}, }
	Bouland, Adam	STOC '17: "The Computational Complexity ..." The Computational Complexity of Ball Permutations Scott Aaronson, Adam Bouland, Greg Kuperberg, and Saeed Mehraban (University of Texas at Austin, USA; Massachusetts Institute of Technology, USA; University of California at Davis, USA) @InProceedings{STOC17p345, author = {Scott Aaronson and Adam Bouland and Greg Kuperberg and Saeed Mehraban}, title = {The Computational Complexity of Ball Permutations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {345-344}, doi = {}, year = {2017}, }
	Brakerski, Zvika	STOC '17: "Non-interactive Delegation ..." Non-interactive Delegation and Batch NP Verification from Standard Computational Assumptions Zvika Brakerski, Justin Holmgren, and Yael Kalai (Weizmann Institute of Science, Israel; Massachusetts Institute of Technology, USA; Microsoft Research, USA) @InProceedings{STOC17p527, author = {Zvika Brakerski and Justin Holmgren and Yael Kalai}, title = {Non-interactive Delegation and Batch NP Verification from Standard Computational Assumptions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {527-526}, doi = {}, year = {2017}, }
	Braverman, Vladimir	STOC '17: "Streaming Symmetric Norms ..." Streaming Symmetric Norms via Measure Concentration Jarosław Błasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang (Harvard University, USA; Johns Hopkins University, USA; ETH Zurich, Switzerland; Weizmann Institute of Science, Israel) @InProceedings{STOC17p793, author = {Jarosław Błasiok and Vladimir Braverman and Stephen R. Chestnut and Robert Krauthgamer and Lin F. Yang}, title = {Streaming Symmetric Norms via Measure Concentration}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {793-792}, doi = {}, year = {2017}, }
	Bubeck, Sébastien	STOC '17: "Local Max-Cut in Smoothed ..." Local Max-Cut in Smoothed Polynomial Time Omer Angel, Sébastien Bubeck, Yuval Peres, and Fan Wei (University of British Columbia, Canada; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC17p471, author = {Omer Angel and Sébastien Bubeck and Yuval Peres and Fan Wei}, title = {Local Max-Cut in Smoothed Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {471-470}, doi = {}, year = {2017}, } STOC '17: "Kernel-Based Methods for Bandit ..." Kernel-Based Methods for Bandit Convex Optimization Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan (Microsoft Research, USA; Weizmann Institute of Science, Israel) @InProceedings{STOC17p79, author = {Sébastien Bubeck and Yin Tat Lee and Ronen Eldan}, title = {Kernel-Based Methods for Bandit Convex Optimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {79-78}, doi = {}, year = {2017}, }
	Bullins, Brian	STOC '17: "Finding Approximate Local ..." Finding Approximate Local Minima Faster than Gradient Descent Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma (Princeton University, USA; IAS, USA) @InProceedings{STOC17p1339, author = {Naman Agarwal and Zeyuan Allen-Zhu and Brian Bullins and Elad Hazan and Tengyu Ma}, title = {Finding Approximate Local Minima Faster than Gradient Descent}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1339-1338}, doi = {}, year = {2017}, }
	Cai, Jin-Yi	STOC '17: "Holographic Algorithm with ..." Holographic Algorithm with Matchgates Is Universal for Planar #CSP over Boolean Domain Jin-Yi Cai and Zhiguo Fu (University of Wisconsin-Madison, USA; Jilin University, China) @InProceedings{STOC17p933, author = {Jin-Yi Cai and Zhiguo Fu}, title = {Holographic Algorithm with Matchgates Is Universal for Planar #CSP over Boolean Domain}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {933-932}, doi = {}, year = {2017}, }
	Cai, Yang	STOC '17: "Simple Mechanisms for Subadditive ..." Simple Mechanisms for Subadditive Buyers via Duality Yang Cai and Mingfei Zhao (McGill University, Canada) @InProceedings{STOC17p191, author = {Yang Cai and Mingfei Zhao}, title = {Simple Mechanisms for Subadditive Buyers via Duality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {191-190}, doi = {}, year = {2017}, }
	Calude, Cristian S.	STOC '17: "Deciding Parity Games in Quasipolynomial ..." Deciding Parity Games in Quasipolynomial Time Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan (University of Auckland, New Zealand; National University of Singapore, Singapore) @InProceedings{STOC17p275, author = {Cristian S. Calude and Sanjay Jain and Bakhadyr Khoussainov and Wei Li and Frank Stephan}, title = {Deciding Parity Games in Quasipolynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {275-274}, doi = {}, year = {2017}, }
	Canetti, Ran	STOC '17: "Equivocating Yao: Constant-Round ..." Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model Ran Canetti, Oxana Poburinnaya, and Muthuramakrishnan Venkitasubramaniam (Boston University, USA; Tel Aviv University, Israel; University of Rochester, USA) @InProceedings{STOC17p555, author = {Ran Canetti and Oxana Poburinnaya and Muthuramakrishnan Venkitasubramaniam}, title = {Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {555-554}, doi = {}, year = {2017}, }
	Cevher, Volkan	STOC '17: "An Adaptive Sublinear-Time ..." An Adaptive Sublinear-Time Block Sparse Fourier Transform Volkan Cevher, Michael Kapralov, Jonathan Scarlett, and Amir Zandieh (EPFL, Switzerland) @InProceedings{STOC17p779, author = {Volkan Cevher and Michael Kapralov and Jonathan Scarlett and Amir Zandieh}, title = {An Adaptive Sublinear-Time Block Sparse Fourier Transform}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {779-778}, doi = {}, year = {2017}, }
	Chakrabarty, Deeparnab	STOC '17: "Subquadratic Submodular Function ..." Subquadratic Submodular Function Minimization Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong (Dartmouth College, USA; Microsoft Research, USA; Stanford University, USA; University of California at Berkeley, USA) @InProceedings{STOC17p1381, author = {Deeparnab Chakrabarty and Yin Tat Lee and Aaron Sidford and Sam Chiu-wai Wong}, title = {Subquadratic Submodular Function Minimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1381-1380}, doi = {}, year = {2017}, }
	Chang, Yi-Jun	STOC '17: "Exponential Separations in ..." Exponential Separations in the Energy Complexity of Leader Election Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, and Wei Zhan (University of Michigan, USA; Tsinghua University, China) @InProceedings{STOC17p849, author = {Yi-Jun Chang and Tsvi Kopelowitz and Seth Pettie and Ruosong Wang and Wei Zhan}, title = {Exponential Separations in the Energy Complexity of Leader Election}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {849-848}, doi = {}, year = {2017}, }
	Charikar, Moses	STOC '17: "Learning from Untrusted Data ..." Learning from Untrusted Data Moses Charikar, Jacob Steinhardt, and Gregory Valiant (Stanford University, USA) @InProceedings{STOC17p51, author = {Moses Charikar and Jacob Steinhardt and Gregory Valiant}, title = {Learning from Untrusted Data}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {51-50}, doi = {}, year = {2017}, }
	Chattopadhyay, Eshan	STOC '17: "Non-malleable Codes and Extractors ..." Non-malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions Eshan Chattopadhyay and Xin Li (IAS, USA; Johns Hopkins University, USA) @InProceedings{STOC17p1311, author = {Eshan Chattopadhyay and Xin Li}, title = {Non-malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1311-1310}, doi = {}, year = {2017}, }
	Chawla, Shuchi	STOC '17: "Stability of Service under ..." Stability of Service under Time-of-Use Pricing Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James B. Martin, and Balasubramanian Sivan (University of Wisconsin-Madison, USA; Microsoft Research, USA; University of Washington, USA; University of Oxford, UK; Google Research, USA) @InProceedings{STOC17p205, author = {Shuchi Chawla and Nikhil R. Devanur and Alexander E. Holroyd and Anna R. Karlin and James B. Martin and Balasubramanian Sivan}, title = {Stability of Service under Time-of-Use Pricing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {205-204}, doi = {}, year = {2017}, }
	Chen, Xi	STOC '17: "Addition Is Exponentially ..." Addition Is Exponentially Harder Than Counting for Shallow Monotone Circuits Xi Chen, Igor C. Oliveira, and Rocco A. Servedio (Columbia University, USA; Charles University in Prague, Czechia) @InProceedings{STOC17p1395, author = {Xi Chen and Igor C. Oliveira and Rocco A. Servedio}, title = {Addition Is Exponentially Harder Than Counting for Shallow Monotone Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1395-1394}, doi = {}, year = {2017}, } STOC '17: "Beyond Talagrand Functions: ..." Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness Xi Chen, Erik Waingarten, and Jinyu Xie (Columbia University, USA) @InProceedings{STOC17p583, author = {Xi Chen and Erik Waingarten and Jinyu Xie}, title = {Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {583-582}, doi = {}, year = {2017}, }
	Chestnut, Stephen R.	STOC '17: "Streaming Symmetric Norms ..." Streaming Symmetric Norms via Measure Concentration Jarosław Błasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang (Harvard University, USA; Johns Hopkins University, USA; ETH Zurich, Switzerland; Weizmann Institute of Science, Israel) @InProceedings{STOC17p793, author = {Jarosław Błasiok and Vladimir Braverman and Stephen R. Chestnut and Robert Krauthgamer and Lin F. Yang}, title = {Streaming Symmetric Norms via Measure Concentration}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {793-792}, doi = {}, year = {2017}, }
	Christiani, Tobias	STOC '17: "Set Similarity Search Beyond ..." Set Similarity Search Beyond MinHash Tobias Christiani and Rasmus Pagh (IT University of Copenhagen, Denmark) @InProceedings{STOC17p1227, author = {Tobias Christiani and Rasmus Pagh}, title = {Set Similarity Search Beyond MinHash}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1227-1226}, doi = {}, year = {2017}, }
	Chuzhoy, Julia	STOC '17: "New Hardness Results for Routing ..." New Hardness Results for Routing on Disjoint Paths Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat (Toyota Technological Institute at Chicago, USA; University of Chicago, USA) @InProceedings{STOC17p93, author = {Julia Chuzhoy and David H. K. Kim and Rachit Nimavat}, title = {New Hardness Results for Routing on Disjoint Paths}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {93-92}, doi = {}, year = {2017}, }
	Cohen, Gil	STOC '17: "Towards Optimal Two-Source ..." Towards Optimal Two-Source Extractors and Ramsey Graphs Gil Cohen (Princeton University, USA) @InProceedings{STOC17p1297, author = {Gil Cohen}, title = {Towards Optimal Two-Source Extractors and Ramsey Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1297-1296}, doi = {}, year = {2017}, }
	Cohen, Michael B.	STOC '17: "Almost-Linear-Time Algorithms ..." Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu (Massachusetts Institute of Technology, USA; Georgia Institute of Technology, USA; Stanford University, USA) @InProceedings{STOC17p443, author = {Michael B. Cohen and Jonathan Kelner and John Peebles and Richard Peng and Anup B. Rao and Aaron Sidford and Adrian Vladu}, title = {Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {443-442}, doi = {}, year = {2017}, }
	Coja-Oghlan, Amin	STOC '17: "Information-Theoretic Thresholds ..." Information-Theoretic Thresholds from the Cavity Method Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborova (Goethe University Frankfurt, Germany; CNRS, France; PSL Research University, France; ENS, France; UPMC, France; University of Birmingham, UK; CEA, France; University of Paris-Saclay, France) @InProceedings{STOC17p163, author = {Amin Coja-Oghlan and Florent Krzakala and Will Perkins and Lenka Zdeborova}, title = {Information-Theoretic Thresholds from the Cavity Method}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {163-162}, doi = {}, year = {2017}, }
	Curticapean, Radu	STOC '17: "Homomorphisms Are a Good Basis ..." Homomorphisms Are a Good Basis for Counting Small Subgraphs Radu Curticapean, Holger Dell, and Dániel Marx (Hungarian Academy of Sciences, Hungary; Saarland University, Germany) @InProceedings{STOC17p233, author = {Radu Curticapean and Holger Dell and Dániel Marx}, title = {Homomorphisms Are a Good Basis for Counting Small Subgraphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {233-232}, doi = {}, year = {2017}, }
	Dagan, Yuval	STOC '17: "Twenty (Simple) Questions ..." Twenty (Simple) Questions Yuval Dagan, Yuval Filmus, Ariel Gabizon, and Shay Moran (Technion, Israel; Zerocoin Electronic Coin, USA; University of California at San Diego, USA; Simons Institute for the Theory of Computing Berkeley, USA) @InProceedings{STOC17p9, author = {Yuval Dagan and Yuval Filmus and Ariel Gabizon and Shay Moran}, title = {Twenty (Simple) Questions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {9-8}, doi = {}, year = {2017}, }
	Dahlgaard, Søren	STOC '17: "Finding Even Cycles Faster ..." Finding Even Cycles Faster via Capped k-Walks Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Morten Stöckel (University of Copenhagen, Denmark) @InProceedings{STOC17p121, author = {Søren Dahlgaard and Mathias Bæk Tejs Knudsen and Morten Stöckel}, title = {Finding Even Cycles Faster via Capped k-Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {121-120}, doi = {}, year = {2017}, }
	De, Anindya	STOC '17: "Optimal Mean-Based Algorithms ..." Optimal Mean-Based Algorithms for Trace Reconstruction Anindya De, Ryan O'Donnell, and Rocco A. Servedio (Northwestern University, USA; Carnegie Mellon University, USA; Columbia University, USA) @InProceedings{STOC17p1171, author = {Anindya De and Ryan O'Donnell and Rocco A. Servedio}, title = {Optimal Mean-Based Algorithms for Trace Reconstruction}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1171-1170}, doi = {}, year = {2017}, }
	Dell, Holger	STOC '17: "Homomorphisms Are a Good Basis ..." Homomorphisms Are a Good Basis for Counting Small Subgraphs Radu Curticapean, Holger Dell, and Dániel Marx (Hungarian Academy of Sciences, Hungary; Saarland University, Germany) @InProceedings{STOC17p233, author = {Radu Curticapean and Holger Dell and Dániel Marx}, title = {Homomorphisms Are a Good Basis for Counting Small Subgraphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {233-232}, doi = {}, year = {2017}, }
	Devanur, Nikhil R.	STOC '17: "Stability of Service under ..." Stability of Service under Time-of-Use Pricing Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James B. Martin, and Balasubramanian Sivan (University of Wisconsin-Madison, USA; Microsoft Research, USA; University of Washington, USA; University of Oxford, UK; Google Research, USA) @InProceedings{STOC17p205, author = {Shuchi Chawla and Nikhil R. Devanur and Alexander E. Holroyd and Anna R. Karlin and James B. Martin and Balasubramanian Sivan}, title = {Stability of Service under Time-of-Use Pricing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {205-204}, doi = {}, year = {2017}, }
	Doron, Dean	STOC '17: "An Efficient Reduction from ..." An Efficient Reduction from Two-Source to Non-malleable Extractors: Achieving Near-Logarithmic Min-entropy Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma (Tel Aviv University, Israel) @InProceedings{STOC17p1325, author = {Avraham Ben-Aroya and Dean Doron and Amnon Ta-Shma}, title = {An Efficient Reduction from Two-Source to Non-malleable Extractors: Achieving Near-Logarithmic Min-entropy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1325-1324}, doi = {}, year = {2017}, }
	Dughmi, Shaddin	STOC '17: "Bernoulli Factories and Black-Box ..." Bernoulli Factories and Black-Box Reductions in Mechanism Design Shaddin Dughmi, Jason D. Hartline, Robert Kleinberg, and Rad Niazadeh (University of Southern California, USA; Northwestern University, USA; Cornell University, USA) @InProceedings{STOC17p177, author = {Shaddin Dughmi and Jason D. Hartline and Robert Kleinberg and Rad Niazadeh}, title = {Bernoulli Factories and Black-Box Reductions in Mechanism Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {177-176}, doi = {}, year = {2017}, }
	Durfee, David	STOC '17: "Sampling Random Spanning Trees ..." Sampling Random Spanning Trees Faster Than Matrix Multiplication David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva (Georgia Institute of Technology, USA; Yale University, USA; Massachusetts Institute of Technology, USA; Google, USA) @InProceedings{STOC17p807, author = {David Durfee and Rasmus Kyng and John Peebles and Anup B. Rao and Sushant Sachdeva}, title = {Sampling Random Spanning Trees Faster Than Matrix Multiplication}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {807-806}, doi = {}, year = {2017}, }
	Eenberg, Kasper	STOC '17: "DecreaseKeys Are Expensive ..." DecreaseKeys Are Expensive for External Memory Priority Queues Kasper Eenberg, Kasper Green Larsen, and Huacheng Yu (Aarhus University, Denmark; Stanford University, USA) @InProceedings{STOC17p1213, author = {Kasper Eenberg and Kasper Green Larsen and Huacheng Yu}, title = {DecreaseKeys Are Expensive for External Memory Priority Queues}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1213-1212}, doi = {}, year = {2017}, }
	Ehsani, Soheil	STOC '17: "Beating 1-1/e for Ordered ..." Beating 1-1/e for Ordered Prophets Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi HajiAghayi, Robert Kleinberg, and Brendan Lucier (University of Maryland at College Park, USA; Cornell University, USA; Microsoft Research, USA) @InProceedings{STOC17p65, author = {Melika Abolhassani and Soheil Ehsani and Hossein Esfandiari and MohammadTaghi HajiAghayi and Robert Kleinberg and Brendan Lucier}, title = {Beating 1-1/e for Ordered Prophets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {65-64}, doi = {}, year = {2017}, }
	Eldan, Ronen	STOC '17: "Kernel-Based Methods for Bandit ..." Kernel-Based Methods for Bandit Convex Optimization Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan (Microsoft Research, USA; Weizmann Institute of Science, Israel) @InProceedings{STOC17p79, author = {Sébastien Bubeck and Yin Tat Lee and Ronen Eldan}, title = {Kernel-Based Methods for Bandit Convex Optimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {79-78}, doi = {}, year = {2017}, }
	Elkin, Michael	STOC '17: "Distributed Exact Shortest ..." Distributed Exact Shortest Paths in Sublinear Time Michael Elkin (Ben-Gurion University of the Negev, Israel) @InProceedings{STOC17p835, author = {Michael Elkin}, title = {Distributed Exact Shortest Paths in Sublinear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {835-834}, doi = {}, year = {2017}, }
	Esfandiari, Hossein	STOC '17: "Beating 1-1/e for Ordered ..." Beating 1-1/e for Ordered Prophets Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi HajiAghayi, Robert Kleinberg, and Brendan Lucier (University of Maryland at College Park, USA; Cornell University, USA; Microsoft Research, USA) @InProceedings{STOC17p65, author = {Melika Abolhassani and Soheil Ehsani and Hossein Esfandiari and MohammadTaghi HajiAghayi and Robert Kleinberg and Brendan Lucier}, title = {Beating 1-1/e for Ordered Prophets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {65-64}, doi = {}, year = {2017}, }
	Fan, Zhou	STOC '17: "How Well Do Local Algorithms ..." How Well Do Local Algorithms Solve Semidefinite Programs? Zhou Fan and Andrea Montanari (Stanford University, USA) @InProceedings{STOC17p667, author = {Zhou Fan and Andrea Montanari}, title = {How Well Do Local Algorithms Solve Semidefinite Programs?}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {667-666}, doi = {}, year = {2017}, }
	Feige, Uriel	STOC '17: "Approximate Modularity Revisited ..." Approximate Modularity Revisited Uriel Feige, Michal Feldman, and Inbal Talgam-Cohen (Weizmann Institute of Science, Israel; Microsoft Research, Israel; Tel Aviv University, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC17p1143, author = {Uriel Feige and Michal Feldman and Inbal Talgam-Cohen}, title = {Approximate Modularity Revisited}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1143-1142}, doi = {}, year = {2017}, }
	Feldman, Michal	STOC '17: "Approximate Modularity Revisited ..." Approximate Modularity Revisited Uriel Feige, Michal Feldman, and Inbal Talgam-Cohen (Weizmann Institute of Science, Israel; Microsoft Research, Israel; Tel Aviv University, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC17p1143, author = {Uriel Feige and Michal Feldman and Inbal Talgam-Cohen}, title = {Approximate Modularity Revisited}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1143-1142}, doi = {}, year = {2017}, }
	Filmus, Yuval	STOC '17: "Twenty (Simple) Questions ..." Twenty (Simple) Questions Yuval Dagan, Yuval Filmus, Ariel Gabizon, and Shay Moran (Technion, Israel; Zerocoin Electronic Coin, USA; University of California at San Diego, USA; Simons Institute for the Theory of Computing Berkeley, USA) @InProceedings{STOC17p9, author = {Yuval Dagan and Yuval Filmus and Ariel Gabizon and Shay Moran}, title = {Twenty (Simple) Questions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {9-8}, doi = {}, year = {2017}, }
	Forbes, Michael A.	STOC '17: "Succinct Hitting Sets and ..." Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds Michael A. Forbes, Amir Shpilka, and Ben Lee Volk (Simons Institute for the Theory of Computing Berkeley, USA; Tel Aviv University, Israel) @InProceedings{STOC17p723, author = {Michael A. Forbes and Amir Shpilka and Ben Lee Volk}, title = {Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {723-722}, doi = {}, year = {2017}, }
	Foster, Nate	STOC '17: "The Next 700 Network Programming ..." The Next 700 Network Programming Languages (Invited Talk) Nate Foster (Cornell University, USA) @InProceedings{STOC17p7, author = {Nate Foster}, title = {The Next 700 Network Programming Languages (Invited Talk)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {7-6}, doi = {}, year = {2017}, }
	Fu, Zhiguo	STOC '17: "Holographic Algorithm with ..." Holographic Algorithm with Matchgates Is Universal for Planar #CSP over Boolean Domain Jin-Yi Cai and Zhiguo Fu (University of Wisconsin-Madison, USA; Jilin University, China) @InProceedings{STOC17p933, author = {Jin-Yi Cai and Zhiguo Fu}, title = {Holographic Algorithm with Matchgates Is Universal for Planar #CSP over Boolean Domain}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {933-932}, doi = {}, year = {2017}, }
	Gabizon, Ariel	STOC '17: "Twenty (Simple) Questions ..." Twenty (Simple) Questions Yuval Dagan, Yuval Filmus, Ariel Gabizon, and Shay Moran (Technion, Israel; Zerocoin Electronic Coin, USA; University of California at San Diego, USA; Simons Institute for the Theory of Computing Berkeley, USA) @InProceedings{STOC17p9, author = {Yuval Dagan and Yuval Filmus and Ariel Gabizon and Shay Moran}, title = {Twenty (Simple) Questions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {9-8}, doi = {}, year = {2017}, }
	Ganesh, Arun	STOC '17: "Online Service with Delay ..." Online Service with Delay Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi (Tel Aviv University, Israel; Duke University, USA) @InProceedings{STOC17p611, author = {Yossi Azar and Arun Ganesh and Rong Ge and Debmalya Panigrahi}, title = {Online Service with Delay}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {611-610}, doi = {}, year = {2017}, }
	Garg, Ankit	STOC '17: "Algorithmic and Optimization ..." Algorithmic and Optimization Aspects of Brascamp-Lieb Inequalities, via Operator Scaling Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson (Microsoft Research, USA; City College of New York, USA; Princeton University, USA; IAS, USA) @InProceedings{STOC17p429, author = {Ankit Garg and Leonid Gurvits and Rafael Oliveira and Avi Wigderson}, title = {Algorithmic and Optimization Aspects of Brascamp-Lieb Inequalities, via Operator Scaling}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {429-428}, doi = {}, year = {2017}, }
	Garg, Jugal	STOC '17: "Settling the Complexity of ..." Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod (University of Illinois at Urbana-Champaign, USA; Georgia Institute of Technology, USA) @InProceedings{STOC17p989, author = {Jugal Garg and Ruta Mehta and Vijay V. Vazirani and Sadra Yazdanbod}, title = {Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {989-988}, doi = {}, year = {2017}, }
	Garg, Shashwat	STOC '17: "Algorithmic Discrepancy Beyond ..." Algorithmic Discrepancy Beyond Partial Coloring Nikhil Bansal and Shashwat Garg (Eindhoven University of Technology, Netherlands) @InProceedings{STOC17p1017, author = {Nikhil Bansal and Shashwat Garg}, title = {Algorithmic Discrepancy Beyond Partial Coloring}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1017-1016}, doi = {}, year = {2017}, } STOC '17: "Faster Space-Efficient Algorithms ..." Faster Space-Efficient Algorithms for Subset Sum and k-Sum Nikhil Bansal, Shashwat Garg, Jesper Nederlof, and Nikhil Vyas (Eindhoven University of Technology, Netherlands; IIT Bombay, India) @InProceedings{STOC17p219, author = {Nikhil Bansal and Shashwat Garg and Jesper Nederlof and Nikhil Vyas}, title = {Faster Space-Efficient Algorithms for Subset Sum and k-Sum}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {219-218}, doi = {}, year = {2017}, }
	Ge, Rong	STOC '17: "Provable Learning of Noisy-or ..." Provable Learning of Noisy-or Networks Sanjeev Arora, Rong Ge, Tengyu Ma, and Andrej Risteski (Princeton University, USA; Duke University, USA) @InProceedings{STOC17p1185, author = {Sanjeev Arora and Rong Ge and Tengyu Ma and Andrej Risteski}, title = {Provable Learning of Noisy-or Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1185-1184}, doi = {}, year = {2017}, } STOC '17: "Online Service with Delay ..." Online Service with Delay Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi (Tel Aviv University, Israel; Duke University, USA) @InProceedings{STOC17p611, author = {Yossi Azar and Arun Ganesh and Rong Ge and Debmalya Panigrahi}, title = {Online Service with Delay}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {611-610}, doi = {}, year = {2017}, }
	Ghaffari, Mohsen	STOC '17: "On the Complexity of Local ..." On the Complexity of Local Distributed Graph Problems Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus (ETH Zurich, Switzerland; University of Freiburg, Germany) @InProceedings{STOC17p863, author = {Mohsen Ghaffari and Fabian Kuhn and Yannic Maus}, title = {On the Complexity of Local Distributed Graph Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {863-862}, doi = {}, year = {2017}, }
	Gharan, Shayan Oveis	STOC '17: "A Generalization of Permanent ..." A Generalization of Permanent Inequalities and Applications in Counting and Optimization Nima Anari and Shayan Oveis Gharan (Stanford University, USA; University of Washington, USA) @InProceedings{STOC17p415, author = {Nima Anari and Shayan Oveis Gharan}, title = {A Generalization of Permanent Inequalities and Applications in Counting and Optimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {415-414}, doi = {}, year = {2017}, }
	Gishboliner, Lior	STOC '17: "Removal Lemmas with Polynomial ..." Removal Lemmas with Polynomial Bounds Lior Gishboliner and Asaf Shapira (Tel Aviv University, Israel) @InProceedings{STOC17p569, author = {Lior Gishboliner and Asaf Shapira}, title = {Removal Lemmas with Polynomial Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {569-568}, doi = {}, year = {2017}, }
	Gonczarowski, Yannai A.	STOC '17: "Efficient Empirical Revenue ..." Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments Yannai A. Gonczarowski and Noam Nisan (Hebrew University of Jerusalem, Israel; Microsoft Research, Israel) @InProceedings{STOC17p947, author = {Yannai A. Gonczarowski and Noam Nisan}, title = {Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {947-946}, doi = {}, year = {2017}, } STOC '17: "The Menu-Size Complexity of ..." The Menu-Size Complexity of Revenue Approximation Moshe Babaioff, Yannai A. Gonczarowski, and Noam Nisan (Microsoft Research, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC17p961, author = {Moshe Babaioff and Yannai A. Gonczarowski and Noam Nisan}, title = {The Menu-Size Complexity of Revenue Approximation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {961-960}, doi = {}, year = {2017}, }
	Grandoni, Fabrizio	STOC '17: "Surviving in Directed Graphs: ..." Surviving in Directed Graphs: A Quasi-Polynomial-Time Polylogarithmic Approximation for Two-Connected Directed Steiner Tree Fabrizio Grandoni and Bundit Laekhanukit (IDSIA, Switzerland; University of Lugano, Switzerland; Weizmann Institute of Science, Israel) @InProceedings{STOC17p457, author = {Fabrizio Grandoni and Bundit Laekhanukit}, title = {Surviving in Directed Graphs: A Quasi-Polynomial-Time Polylogarithmic Approximation for Two-Connected Directed Steiner Tree}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {457-456}, doi = {}, year = {2017}, }
	Guo, Heng	STOC '17: "Uniform Sampling through the ..." Uniform Sampling through the Lovász Local Lemma Heng Guo, Mark Jerrum, and Jingcheng Liu (Queen Mary University of London, UK; University of California at Berkeley, USA) @InProceedings{STOC17p373, author = {Heng Guo and Mark Jerrum and Jingcheng Liu}, title = {Uniform Sampling through the Lovász Local Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {373-372}, doi = {}, year = {2017}, }
	Gupta, Anupam	STOC '17: "Online and Dynamic Algorithms ..." Online and Dynamic Algorithms for Set Cover Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi (Carnegie Mellon University, USA; Microsoft Research, India; IIT Delhi, India; Duke University, USA) @InProceedings{STOC17p597, author = {Anupam Gupta and Ravishankar Krishnaswamy and Amit Kumar and Debmalya Panigrahi}, title = {Online and Dynamic Algorithms for Set Cover}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {597-596}, doi = {}, year = {2017}, }
	Gurjar, Rohit	STOC '17: "Linear Matroid Intersection ..." Linear Matroid Intersection Is in Quasi-NC Rohit Gurjar and Thomas Thierauf (Tel Aviv University, Israel; Aalen University, Germany) @InProceedings{STOC17p905, author = {Rohit Gurjar and Thomas Thierauf}, title = {Linear Matroid Intersection Is in Quasi-NC}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {905-904}, doi = {}, year = {2017}, }
	Gurvits, Leonid	STOC '17: "Algorithmic and Optimization ..." Algorithmic and Optimization Aspects of Brascamp-Lieb Inequalities, via Operator Scaling Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson (Microsoft Research, USA; City College of New York, USA; Princeton University, USA; IAS, USA) @InProceedings{STOC17p429, author = {Ankit Garg and Leonid Gurvits and Rafael Oliveira and Avi Wigderson}, title = {Algorithmic and Optimization Aspects of Brascamp-Lieb Inequalities, via Operator Scaling}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {429-428}, doi = {}, year = {2017}, }
	Haeupler, Bernhard	STOC '17: "Synchronization Strings: Codes ..." Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound Bernhard Haeupler and Amirbehshad Shahrasbi (Carnegie Mellon University, USA) @InProceedings{STOC17p37, author = {Bernhard Haeupler and Amirbehshad Shahrasbi}, title = {Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {37-36}, doi = {}, year = {2017}, }
	HajiAghayi, MohammadTaghi	STOC '17: "Beating 1-1/e for Ordered ..." Beating 1-1/e for Ordered Prophets Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi HajiAghayi, Robert Kleinberg, and Brendan Lucier (University of Maryland at College Park, USA; Cornell University, USA; Microsoft Research, USA) @InProceedings{STOC17p65, author = {Melika Abolhassani and Soheil Ehsani and Hossein Esfandiari and MohammadTaghi HajiAghayi and Robert Kleinberg and Brendan Lucier}, title = {Beating 1-1/e for Ordered Prophets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {65-64}, doi = {}, year = {2017}, }
	Hartline, Jason D.	STOC '17: "Bernoulli Factories and Black-Box ..." Bernoulli Factories and Black-Box Reductions in Mechanism Design Shaddin Dughmi, Jason D. Hartline, Robert Kleinberg, and Rad Niazadeh (University of Southern California, USA; Northwestern University, USA; Cornell University, USA) @InProceedings{STOC17p177, author = {Shaddin Dughmi and Jason D. Hartline and Robert Kleinberg and Rad Niazadeh}, title = {Bernoulli Factories and Black-Box Reductions in Mechanism Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {177-176}, doi = {}, year = {2017}, }
	Hazan, Elad	STOC '17: "Finding Approximate Local ..." Finding Approximate Local Minima Faster than Gradient Descent Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma (Princeton University, USA; IAS, USA) @InProceedings{STOC17p1339, author = {Naman Agarwal and Zeyuan Allen-Zhu and Brian Bullins and Elad Hazan and Tengyu Ma}, title = {Finding Approximate Local Minima Faster than Gradient Descent}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1339-1338}, doi = {}, year = {2017}, }
	Holmgren, Justin	STOC '17: "Non-interactive Delegation ..." Non-interactive Delegation and Batch NP Verification from Standard Computational Assumptions Zvika Brakerski, Justin Holmgren, and Yael Kalai (Weizmann Institute of Science, Israel; Massachusetts Institute of Technology, USA; Microsoft Research, USA) @InProceedings{STOC17p527, author = {Zvika Brakerski and Justin Holmgren and Yael Kalai}, title = {Non-interactive Delegation and Batch NP Verification from Standard Computational Assumptions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {527-526}, doi = {}, year = {2017}, }
	Holroyd, Alexander E.	STOC '17: "Stability of Service under ..." Stability of Service under Time-of-Use Pricing Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James B. Martin, and Balasubramanian Sivan (University of Wisconsin-Madison, USA; Microsoft Research, USA; University of Washington, USA; University of Oxford, UK; Google Research, USA) @InProceedings{STOC17p205, author = {Shuchi Chawla and Nikhil R. Devanur and Alexander E. Holroyd and Anna R. Karlin and James B. Martin and Balasubramanian Sivan}, title = {Stability of Service under Time-of-Use Pricing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {205-204}, doi = {}, year = {2017}, }
	Hoza, William M.	STOC '17: "Targeted Pseudorandom Generators, ..." Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace William M. Hoza and Chris Umans (University of Texas at Austin, USA; California Institute of Technology, USA) @InProceedings{STOC17p695, author = {William M. Hoza and Chris Umans}, title = {Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {695-694}, doi = {}, year = {2017}, }
	Im, Sungjin	STOC '17: "Efficient Massively Parallel ..." Efficient Massively Parallel Methods for Dynamic Programming Sungjin Im, Benjamin Moseley, and Xiaorui Sun (University of California at Merced, USA; Washington University at St. Louis, USA; Simons Institute for the Theory of Computing Berkeley, USA) @InProceedings{STOC17p877, author = {Sungjin Im and Benjamin Moseley and Xiaorui Sun}, title = {Efficient Massively Parallel Methods for Dynamic Programming}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {877-876}, doi = {}, year = {2017}, }
	Italiano, Giuseppe F.	STOC '17: "Decremental Single-Source ..." Decremental Single-Source Reachability in Planar Digraphs Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, and Piotr Sankowski (University of Rome Tor Vergata, Italy; University of Warsaw, Poland; Google Research, USA) @InProceedings{STOC17p1241, author = {Giuseppe F. Italiano and Adam Karczmarz and Jakub Łącki and Piotr Sankowski}, title = {Decremental Single-Source Reachability in Planar Digraphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1241-1240}, doi = {}, year = {2017}, }
	Iwata, Satoru	STOC '17: "A Weighted Linear Matroid ..." A Weighted Linear Matroid Parity Algorithm Satoru Iwata and Yusuke Kobayashi (University of Tokyo, Japan; University of Tsukuba, Japan) @InProceedings{STOC17p289, author = {Satoru Iwata and Yusuke Kobayashi}, title = {A Weighted Linear Matroid Parity Algorithm}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {289-288}, doi = {}, year = {2017}, }
	Jain, Sanjay	STOC '17: "Deciding Parity Games in Quasipolynomial ..." Deciding Parity Games in Quasipolynomial Time Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan (University of Auckland, New Zealand; National University of Singapore, Singapore) @InProceedings{STOC17p275, author = {Cristian S. Calude and Sanjay Jain and Bakhadyr Khoussainov and Wei Li and Frank Stephan}, title = {Deciding Parity Games in Quasipolynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {275-274}, doi = {}, year = {2017}, }
	Jerrum, Mark	STOC '17: "Uniform Sampling through the ..." Uniform Sampling through the Lovász Local Lemma Heng Guo, Mark Jerrum, and Jingcheng Liu (Queen Mary University of London, UK; University of California at Berkeley, USA) @InProceedings{STOC17p373, author = {Heng Guo and Mark Jerrum and Jingcheng Liu}, title = {Uniform Sampling through the Lovász Local Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {373-372}, doi = {}, year = {2017}, }
	Ji, Zhengfeng	STOC '17: "Compression of Quantum Multi-prover ..." Compression of Quantum Multi-prover Interactive Proofs Zhengfeng Ji (University of Technology Sydney, Australia) @InProceedings{STOC17p317, author = {Zhengfeng Ji}, title = {Compression of Quantum Multi-prover Interactive Proofs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {317-316}, doi = {}, year = {2017}, }
	Joglekar, Pushkar S	STOC '17: "Randomized Polynomial Time ..." Randomized Polynomial Time Identity Testing for Noncommutative Circuits V. Arvind, Pushkar S Joglekar, Partha Mukhopadhyay, and S. Raja (Institute of Mathematical Sciences, India; Vishwakarma Institute of Technology Pune, India; Chennai Mathematical Institute, India) @InProceedings{STOC17p919, author = {V. Arvind and Pushkar S Joglekar and Partha Mukhopadhyay and S. Raja}, title = {Randomized Polynomial Time Identity Testing for Noncommutative Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {919-918}, doi = {}, year = {2017}, }
	Kabanets, Valentine	STOC '17: "A Polynomial Restriction Lemma ..." A Polynomial Restriction Lemma with Applications Valentine Kabanets, Daniel M. Kane, and Zhenjian Lu (Simon Fraser University, Canada; University of California at San Diego, USA) @InProceedings{STOC17p681, author = {Valentine Kabanets and Daniel M. Kane and Zhenjian Lu}, title = {A Polynomial Restriction Lemma with Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {681-680}, doi = {}, year = {2017}, }
	Kalai, Yael	STOC '17: "Non-interactive Delegation ..." Non-interactive Delegation and Batch NP Verification from Standard Computational Assumptions Zvika Brakerski, Justin Holmgren, and Yael Kalai (Weizmann Institute of Science, Israel; Massachusetts Institute of Technology, USA; Microsoft Research, USA) @InProceedings{STOC17p527, author = {Zvika Brakerski and Justin Holmgren and Yael Kalai}, title = {Non-interactive Delegation and Batch NP Verification from Standard Computational Assumptions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {527-526}, doi = {}, year = {2017}, }
	Kane, Daniel M.	STOC '17: "A Polynomial Restriction Lemma ..." A Polynomial Restriction Lemma with Applications Valentine Kabanets, Daniel M. Kane, and Zhenjian Lu (Simon Fraser University, Canada; University of California at San Diego, USA) @InProceedings{STOC17p681, author = {Valentine Kabanets and Daniel M. Kane and Zhenjian Lu}, title = {A Polynomial Restriction Lemma with Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {681-680}, doi = {}, year = {2017}, }
	Kapralov, Michael	STOC '17: "An Adaptive Sublinear-Time ..." An Adaptive Sublinear-Time Block Sparse Fourier Transform Volkan Cevher, Michael Kapralov, Jonathan Scarlett, and Amir Zandieh (EPFL, Switzerland) @InProceedings{STOC17p779, author = {Volkan Cevher and Michael Kapralov and Jonathan Scarlett and Amir Zandieh}, title = {An Adaptive Sublinear-Time Block Sparse Fourier Transform}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {779-778}, doi = {}, year = {2017}, }
	Karczmarz, Adam	STOC '17: "Decremental Single-Source ..." Decremental Single-Source Reachability in Planar Digraphs Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, and Piotr Sankowski (University of Rome Tor Vergata, Italy; University of Warsaw, Poland; Google Research, USA) @InProceedings{STOC17p1241, author = {Giuseppe F. Italiano and Adam Karczmarz and Jakub Łącki and Piotr Sankowski}, title = {Decremental Single-Source Reachability in Planar Digraphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1241-1240}, doi = {}, year = {2017}, }
	Karlin, Anna R.	STOC '17: "Stability of Service under ..." Stability of Service under Time-of-Use Pricing Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James B. Martin, and Balasubramanian Sivan (University of Wisconsin-Madison, USA; Microsoft Research, USA; University of Washington, USA; University of Oxford, UK; Google Research, USA) @InProceedings{STOC17p205, author = {Shuchi Chawla and Nikhil R. Devanur and Alexander E. Holroyd and Anna R. Karlin and James B. Martin and Balasubramanian Sivan}, title = {Stability of Service under Time-of-Use Pricing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {205-204}, doi = {}, year = {2017}, }
	Kelner, Jonathan	STOC '17: "Almost-Linear-Time Algorithms ..." Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu (Massachusetts Institute of Technology, USA; Georgia Institute of Technology, USA; Stanford University, USA) @InProceedings{STOC17p443, author = {Michael B. Cohen and Jonathan Kelner and John Peebles and Richard Peng and Anup B. Rao and Aaron Sidford and Adrian Vladu}, title = {Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {443-442}, doi = {}, year = {2017}, }
	Khot, Subhash	STOC '17: "On Independent Sets, 2-to-2 ..." On Independent Sets, 2-to-2 Games, and Grassmann Graphs Subhash Khot, Dor Minzer, and Muli Safra (New York University, USA; Tel Aviv University, Israel) @InProceedings{STOC17p639, author = {Subhash Khot and Dor Minzer and Muli Safra}, title = {On Independent Sets, 2-to-2 Games, and Grassmann Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {639-638}, doi = {}, year = {2017}, }
	Khoussainov, Bakhadyr	STOC '17: "Deciding Parity Games in Quasipolynomial ..." Deciding Parity Games in Quasipolynomial Time Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan (University of Auckland, New Zealand; National University of Singapore, Singapore) @InProceedings{STOC17p275, author = {Cristian S. Calude and Sanjay Jain and Bakhadyr Khoussainov and Wei Li and Frank Stephan}, title = {Deciding Parity Games in Quasipolynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {275-274}, doi = {}, year = {2017}, }
	Kim, David H. K.	STOC '17: "New Hardness Results for Routing ..." New Hardness Results for Routing on Disjoint Paths Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat (Toyota Technological Institute at Chicago, USA; University of Chicago, USA) @InProceedings{STOC17p93, author = {Julia Chuzhoy and David H. K. Kim and Rachit Nimavat}, title = {New Hardness Results for Routing on Disjoint Paths}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {93-92}, doi = {}, year = {2017}, }
	Kleinberg, Robert	STOC '17: "Bernoulli Factories and Black-Box ..." Bernoulli Factories and Black-Box Reductions in Mechanism Design Shaddin Dughmi, Jason D. Hartline, Robert Kleinberg, and Rad Niazadeh (University of Southern California, USA; Northwestern University, USA; Cornell University, USA) @InProceedings{STOC17p177, author = {Shaddin Dughmi and Jason D. Hartline and Robert Kleinberg and Rad Niazadeh}, title = {Bernoulli Factories and Black-Box Reductions in Mechanism Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {177-176}, doi = {}, year = {2017}, } STOC '17: "Beating 1-1/e for Ordered ..." Beating 1-1/e for Ordered Prophets Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi HajiAghayi, Robert Kleinberg, and Brendan Lucier (University of Maryland at College Park, USA; Cornell University, USA; Microsoft Research, USA) @InProceedings{STOC17p65, author = {Melika Abolhassani and Soheil Ehsani and Hossein Esfandiari and MohammadTaghi HajiAghayi and Robert Kleinberg and Brendan Lucier}, title = {Beating 1-1/e for Ordered Prophets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {65-64}, doi = {}, year = {2017}, }
	Knudsen, Mathias Bæk Tejs	STOC '17: "Finding Even Cycles Faster ..." Finding Even Cycles Faster via Capped k-Walks Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Morten Stöckel (University of Copenhagen, Denmark) @InProceedings{STOC17p121, author = {Søren Dahlgaard and Mathias Bæk Tejs Knudsen and Morten Stöckel}, title = {Finding Even Cycles Faster via Capped k-Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {121-120}, doi = {}, year = {2017}, }
	Kobayashi, Yusuke	STOC '17: "A Weighted Linear Matroid ..." A Weighted Linear Matroid Parity Algorithm Satoru Iwata and Yusuke Kobayashi (University of Tokyo, Japan; University of Tsukuba, Japan) @InProceedings{STOC17p289, author = {Satoru Iwata and Yusuke Kobayashi}, title = {A Weighted Linear Matroid Parity Algorithm}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {289-288}, doi = {}, year = {2017}, }
	Kokainis, Martins	STOC '17: "Quantum Algorithm for Tree ..." Quantum Algorithm for Tree Size Estimation, with Applications to Backtracking and 2-Player Games Andris Ambainis and Martins Kokainis (University of Latvia, Latvia) @InProceedings{STOC17p1101, author = {Andris Ambainis and Martins Kokainis}, title = {Quantum Algorithm for Tree Size Estimation, with Applications to Backtracking and 2-Player Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1101-1100}, doi = {}, year = {2017}, }
	Kol, Gillat	STOC '17: "Time-Space Hardness of Learning ..." Time-Space Hardness of Learning Sparse Parities Gillat Kol, Ran Raz, and Avishay Tal (Princeton University, USA; IAS, USA) @InProceedings{STOC17p1199, author = {Gillat Kol and Ran Raz and Avishay Tal}, title = {Time-Space Hardness of Learning Sparse Parities}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1199-1198}, doi = {}, year = {2017}, }
	Kopelowitz, Tsvi	STOC '17: "Exponential Separations in ..." Exponential Separations in the Energy Complexity of Leader Election Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, and Wei Zhan (University of Michigan, USA; Tsinghua University, China) @InProceedings{STOC17p849, author = {Yi-Jun Chang and Tsvi Kopelowitz and Seth Pettie and Ruosong Wang and Wei Zhan}, title = {Exponential Separations in the Energy Complexity of Leader Election}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {849-848}, doi = {}, year = {2017}, }
	Kothari, Pravesh K.	STOC '17: "Quantum Entanglement, Sum ..." Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture Boaz Barak, Pravesh K. Kothari, and David Steurer (Harvard University, USA; Princeton University, USA; IAS, USA; Cornell University, USA) @InProceedings{STOC17p1087, author = {Boaz Barak and Pravesh K. Kothari and David Steurer}, title = {Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1087-1086}, doi = {}, year = {2017}, } STOC '17: "Sum of Squares Lower Bounds ..." Sum of Squares Lower Bounds for Refuting any CSP Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer (Princeton University, USA; IAS, USA; Tokyo Institute of Technology, Japan; Carnegie Mellon University, USA) @InProceedings{STOC17p149, author = {Pravesh K. Kothari and Ryuhei Mori and Ryan O'Donnell and David Witmer}, title = {Sum of Squares Lower Bounds for Refuting any CSP}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {149-148}, doi = {}, year = {2017}, } STOC '17: "Approximating Rectangles by ..." Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra (Princeton University, USA; IAS, USA; University of California at Los Angeles, USA; University of California at Berkeley, USA) @InProceedings{STOC17p653, author = {Pravesh K. Kothari and Raghu Meka and Prasad Raghavendra}, title = {Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {653-652}, doi = {}, year = {2017}, }
	Krauthgamer, Robert	STOC '17: "Streaming Symmetric Norms ..." Streaming Symmetric Norms via Measure Concentration Jarosław Błasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang (Harvard University, USA; Johns Hopkins University, USA; ETH Zurich, Switzerland; Weizmann Institute of Science, Israel) @InProceedings{STOC17p793, author = {Jarosław Błasiok and Vladimir Braverman and Stephen R. Chestnut and Robert Krauthgamer and Lin F. Yang}, title = {Streaming Symmetric Norms via Measure Concentration}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {793-792}, doi = {}, year = {2017}, }
	Krishnaswamy, Ravishankar	STOC '17: "Online and Dynamic Algorithms ..." Online and Dynamic Algorithms for Set Cover Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi (Carnegie Mellon University, USA; Microsoft Research, India; IIT Delhi, India; Duke University, USA) @InProceedings{STOC17p597, author = {Anupam Gupta and Ravishankar Krishnaswamy and Amit Kumar and Debmalya Panigrahi}, title = {Online and Dynamic Algorithms for Set Cover}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {597-596}, doi = {}, year = {2017}, }
	Krzakala, Florent	STOC '17: "Information-Theoretic Thresholds ..." Information-Theoretic Thresholds from the Cavity Method Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborova (Goethe University Frankfurt, Germany; CNRS, France; PSL Research University, France; ENS, France; UPMC, France; University of Birmingham, UK; CEA, France; University of Paris-Saclay, France) @InProceedings{STOC17p163, author = {Amin Coja-Oghlan and Florent Krzakala and Will Perkins and Lenka Zdeborova}, title = {Information-Theoretic Thresholds from the Cavity Method}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {163-162}, doi = {}, year = {2017}, }
	Kuhn, Fabian	STOC '17: "On the Complexity of Local ..." On the Complexity of Local Distributed Graph Problems Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus (ETH Zurich, Switzerland; University of Freiburg, Germany) @InProceedings{STOC17p863, author = {Mohsen Ghaffari and Fabian Kuhn and Yannic Maus}, title = {On the Complexity of Local Distributed Graph Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {863-862}, doi = {}, year = {2017}, }
	Kumar, Amit	STOC '17: "Online and Dynamic Algorithms ..." Online and Dynamic Algorithms for Set Cover Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi (Carnegie Mellon University, USA; Microsoft Research, India; IIT Delhi, India; Duke University, USA) @InProceedings{STOC17p597, author = {Anupam Gupta and Ravishankar Krishnaswamy and Amit Kumar and Debmalya Panigrahi}, title = {Online and Dynamic Algorithms for Set Cover}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {597-596}, doi = {}, year = {2017}, }
	Kuperberg, Greg	STOC '17: "The Computational Complexity ..." The Computational Complexity of Ball Permutations Scott Aaronson, Adam Bouland, Greg Kuperberg, and Saeed Mehraban (University of Texas at Austin, USA; Massachusetts Institute of Technology, USA; University of California at Davis, USA) @InProceedings{STOC17p345, author = {Scott Aaronson and Adam Bouland and Greg Kuperberg and Saeed Mehraban}, title = {The Computational Complexity of Ball Permutations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {345-344}, doi = {}, year = {2017}, }
	Kupferman, Orna	STOC '17: "Examining Classical Graph-Theory ..." Examining Classical Graph-Theory Problems from the Viewpoint of Formal-Verification Methods (Invited Talk) Orna Kupferman (Hebrew University of Jerusalem, Israel) @InProceedings{STOC17p6, author = {Orna Kupferman}, title = {Examining Classical Graph-Theory Problems from the Viewpoint of Formal-Verification Methods (Invited Talk)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {6-5}, doi = {}, year = {2017}, }
	Kyng, Rasmus	STOC '17: "Sampling Random Spanning Trees ..." Sampling Random Spanning Trees Faster Than Matrix Multiplication David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva (Georgia Institute of Technology, USA; Yale University, USA; Massachusetts Institute of Technology, USA; Google, USA) @InProceedings{STOC17p807, author = {David Durfee and Rasmus Kyng and John Peebles and Anup B. Rao and Sushant Sachdeva}, title = {Sampling Random Spanning Trees Faster Than Matrix Multiplication}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {807-806}, doi = {}, year = {2017}, }
	Łącki, Jakub	STOC '17: "Decremental Single-Source ..." Decremental Single-Source Reachability in Planar Digraphs Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, and Piotr Sankowski (University of Rome Tor Vergata, Italy; University of Warsaw, Poland; Google Research, USA) @InProceedings{STOC17p1241, author = {Giuseppe F. Italiano and Adam Karczmarz and Jakub Łącki and Piotr Sankowski}, title = {Decremental Single-Source Reachability in Planar Digraphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1241-1240}, doi = {}, year = {2017}, }
	Laekhanukit, Bundit	STOC '17: "Surviving in Directed Graphs: ..." Surviving in Directed Graphs: A Quasi-Polynomial-Time Polylogarithmic Approximation for Two-Connected Directed Steiner Tree Fabrizio Grandoni and Bundit Laekhanukit (IDSIA, Switzerland; University of Lugano, Switzerland; Weizmann Institute of Science, Israel) @InProceedings{STOC17p457, author = {Fabrizio Grandoni and Bundit Laekhanukit}, title = {Surviving in Directed Graphs: A Quasi-Polynomial-Time Polylogarithmic Approximation for Two-Connected Directed Steiner Tree}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {457-456}, doi = {}, year = {2017}, }
	Larsen, Kasper Green	STOC '17: "DecreaseKeys Are Expensive ..." DecreaseKeys Are Expensive for External Memory Priority Queues Kasper Eenberg, Kasper Green Larsen, and Huacheng Yu (Aarhus University, Denmark; Stanford University, USA) @InProceedings{STOC17p1213, author = {Kasper Eenberg and Kasper Green Larsen and Huacheng Yu}, title = {DecreaseKeys Are Expensive for External Memory Priority Queues}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1213-1212}, doi = {}, year = {2017}, }
	Lee, Yin Tat	STOC '17: "Geodesic Walks in Polytopes ..." Geodesic Walks in Polytopes Yin Tat Lee and Santosh S. Vempala (Microsoft Research, USA; University of Washington, USA; Georgia Institute of Technology, USA) @InProceedings{STOC17p1031, author = {Yin Tat Lee and Santosh S. Vempala}, title = {Geodesic Walks in Polytopes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1031-1030}, doi = {}, year = {2017}, } STOC '17: "Subquadratic Submodular Function ..." Subquadratic Submodular Function Minimization Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong (Dartmouth College, USA; Microsoft Research, USA; Stanford University, USA; University of California at Berkeley, USA) @InProceedings{STOC17p1381, author = {Deeparnab Chakrabarty and Yin Tat Lee and Aaron Sidford and Sam Chiu-wai Wong}, title = {Subquadratic Submodular Function Minimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1381-1380}, doi = {}, year = {2017}, } STOC '17: "An SDP-Based Algorithm for ..." An SDP-Based Algorithm for Linear-Sized Spectral Sparsification Yin Tat Lee and He Sun (Microsoft Research, USA; University of Bristol, UK) @InProceedings{STOC17p751, author = {Yin Tat Lee and He Sun}, title = {An SDP-Based Algorithm for Linear-Sized Spectral Sparsification}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {751-750}, doi = {}, year = {2017}, } STOC '17: "Kernel-Based Methods for Bandit ..." Kernel-Based Methods for Bandit Convex Optimization Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan (Microsoft Research, USA; Weizmann Institute of Science, Israel) @InProceedings{STOC17p79, author = {Sébastien Bubeck and Yin Tat Lee and Ronen Eldan}, title = {Kernel-Based Methods for Bandit Convex Optimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {79-78}, doi = {}, year = {2017}, }
	Li, Wei	STOC '17: "Deciding Parity Games in Quasipolynomial ..." Deciding Parity Games in Quasipolynomial Time Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan (University of Auckland, New Zealand; National University of Singapore, Singapore) @InProceedings{STOC17p275, author = {Cristian S. Calude and Sanjay Jain and Bakhadyr Khoussainov and Wei Li and Frank Stephan}, title = {Deciding Parity Games in Quasipolynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {275-274}, doi = {}, year = {2017}, }
	Li, Xin	STOC '17: "Improved Non-malleable Extractors, ..." Improved Non-malleable Extractors, Non-malleable Codes and Independent Source Extractors Xin Li (Johns Hopkins University, USA) @InProceedings{STOC17p1283, author = {Xin Li}, title = {Improved Non-malleable Extractors, Non-malleable Codes and Independent Source Extractors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1283-1282}, doi = {}, year = {2017}, } STOC '17: "Non-malleable Codes and Extractors ..." Non-malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions Eshan Chattopadhyay and Xin Li (IAS, USA; Johns Hopkins University, USA) @InProceedings{STOC17p1311, author = {Eshan Chattopadhyay and Xin Li}, title = {Non-malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1311-1310}, doi = {}, year = {2017}, }
	Liu, Jingcheng	STOC '17: "Uniform Sampling through the ..." Uniform Sampling through the Lovász Local Lemma Heng Guo, Mark Jerrum, and Jingcheng Liu (Queen Mary University of London, UK; University of California at Berkeley, USA) @InProceedings{STOC17p373, author = {Heng Guo and Mark Jerrum and Jingcheng Liu}, title = {Uniform Sampling through the Lovász Local Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {373-372}, doi = {}, year = {2017}, }
	Lokshtanov, Daniel	STOC '17: "Lossy Kernelization ..." Lossy Kernelization Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh (University of Bergen, Norway; Vienna University of Technology, Austria; Institute of Mathematical Sciences, India) @InProceedings{STOC17p247, author = {Daniel Lokshtanov and Fahad Panolan and M. S. Ramanujan and Saket Saurabh}, title = {Lossy Kernelization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {247-246}, doi = {}, year = {2017}, }
	Lu, Zhenjian	STOC '17: "A Polynomial Restriction Lemma ..." A Polynomial Restriction Lemma with Applications Valentine Kabanets, Daniel M. Kane, and Zhenjian Lu (Simon Fraser University, Canada; University of California at San Diego, USA) @InProceedings{STOC17p681, author = {Valentine Kabanets and Daniel M. Kane and Zhenjian Lu}, title = {A Polynomial Restriction Lemma with Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {681-680}, doi = {}, year = {2017}, }
	Lucier, Brendan	STOC '17: "Beating 1-1/e for Ordered ..." Beating 1-1/e for Ordered Prophets Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi HajiAghayi, Robert Kleinberg, and Brendan Lucier (University of Maryland at College Park, USA; Cornell University, USA; Microsoft Research, USA) @InProceedings{STOC17p65, author = {Melika Abolhassani and Soheil Ehsani and Hossein Esfandiari and MohammadTaghi HajiAghayi and Robert Kleinberg and Brendan Lucier}, title = {Beating 1-1/e for Ordered Prophets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {65-64}, doi = {}, year = {2017}, }
	Ma, Tengyu	STOC '17: "Provable Learning of Noisy-or ..." Provable Learning of Noisy-or Networks Sanjeev Arora, Rong Ge, Tengyu Ma, and Andrej Risteski (Princeton University, USA; Duke University, USA) @InProceedings{STOC17p1185, author = {Sanjeev Arora and Rong Ge and Tengyu Ma and Andrej Risteski}, title = {Provable Learning of Noisy-or Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1185-1184}, doi = {}, year = {2017}, } STOC '17: "Finding Approximate Local ..." Finding Approximate Local Minima Faster than Gradient Descent Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma (Princeton University, USA; IAS, USA) @InProceedings{STOC17p1339, author = {Naman Agarwal and Zeyuan Allen-Zhu and Brian Bullins and Elad Hazan and Tengyu Ma}, title = {Finding Approximate Local Minima Faster than Gradient Descent}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1339-1338}, doi = {}, year = {2017}, }
	Makarychev, Konstantin	STOC '17: "Algorithms for Stable and ..." Algorithms for Stable and Perturbation-Resilient Problems Haris Angelidakis, Konstantin Makarychev, and Yury Makarychev (Toyota Technological Institute at Chicago, USA; Northwestern University, USA) @InProceedings{STOC17p485, author = {Haris Angelidakis and Konstantin Makarychev and Yury Makarychev}, title = {Algorithms for Stable and Perturbation-Resilient Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {485-484}, doi = {}, year = {2017}, }
	Makarychev, Yury	STOC '17: "Algorithms for Stable and ..." Algorithms for Stable and Perturbation-Resilient Problems Haris Angelidakis, Konstantin Makarychev, and Yury Makarychev (Toyota Technological Institute at Chicago, USA; Northwestern University, USA) @InProceedings{STOC17p485, author = {Haris Angelidakis and Konstantin Makarychev and Yury Makarychev}, title = {Algorithms for Stable and Perturbation-Resilient Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {485-484}, doi = {}, year = {2017}, }
	Manurangsi, Pasin	STOC '17: "Almost-Polynomial Ratio ETH-Hardness ..." Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph Pasin Manurangsi (University of California at Berkeley, USA) @InProceedings{STOC17p1059, author = {Pasin Manurangsi}, title = {Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1059-1058}, doi = {}, year = {2017}, }
	Martens, Wim	STOC '17: "Optimizing Tree Pattern Queries: ..." Optimizing Tree Pattern Queries: Why Cutting Is Not Enough (Invited Talk) Wim Martens (University of Bayreuth, Germany) @InProceedings{STOC17p3, author = {Wim Martens}, title = {Optimizing Tree Pattern Queries: Why Cutting Is Not Enough (Invited Talk)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {3-2}, doi = {}, year = {2017}, }
	Martin, James B.	STOC '17: "Stability of Service under ..." Stability of Service under Time-of-Use Pricing Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James B. Martin, and Balasubramanian Sivan (University of Wisconsin-Madison, USA; Microsoft Research, USA; University of Washington, USA; University of Oxford, UK; Google Research, USA) @InProceedings{STOC17p205, author = {Shuchi Chawla and Nikhil R. Devanur and Alexander E. Holroyd and Anna R. Karlin and James B. Martin and Balasubramanian Sivan}, title = {Stability of Service under Time-of-Use Pricing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {205-204}, doi = {}, year = {2017}, }
	Marx, Dániel	STOC '17: "Homomorphisms Are a Good Basis ..." Homomorphisms Are a Good Basis for Counting Small Subgraphs Radu Curticapean, Holger Dell, and Dániel Marx (Hungarian Academy of Sciences, Hungary; Saarland University, Germany) @InProceedings{STOC17p233, author = {Radu Curticapean and Holger Dell and Dániel Marx}, title = {Homomorphisms Are a Good Basis for Counting Small Subgraphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {233-232}, doi = {}, year = {2017}, }
	Maus, Yannic	STOC '17: "On the Complexity of Local ..." On the Complexity of Local Distributed Graph Problems Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus (ETH Zurich, Switzerland; University of Freiburg, Germany) @InProceedings{STOC17p863, author = {Mohsen Ghaffari and Fabian Kuhn and Yannic Maus}, title = {On the Complexity of Local Distributed Graph Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {863-862}, doi = {}, year = {2017}, }
	Mehraban, Saeed	STOC '17: "The Computational Complexity ..." The Computational Complexity of Ball Permutations Scott Aaronson, Adam Bouland, Greg Kuperberg, and Saeed Mehraban (University of Texas at Austin, USA; Massachusetts Institute of Technology, USA; University of California at Davis, USA) @InProceedings{STOC17p345, author = {Scott Aaronson and Adam Bouland and Greg Kuperberg and Saeed Mehraban}, title = {The Computational Complexity of Ball Permutations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {345-344}, doi = {}, year = {2017}, }
	Mehta, Ruta	STOC '17: "Settling the Complexity of ..." Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod (University of Illinois at Urbana-Champaign, USA; Georgia Institute of Technology, USA) @InProceedings{STOC17p989, author = {Jugal Garg and Ruta Mehta and Vijay V. Vazirani and Sadra Yazdanbod}, title = {Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {989-988}, doi = {}, year = {2017}, }
	Meka, Raghu	STOC '17: "Approximating Rectangles by ..." Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra (Princeton University, USA; IAS, USA; University of California at Los Angeles, USA; University of California at Berkeley, USA) @InProceedings{STOC17p653, author = {Pravesh K. Kothari and Raghu Meka and Prasad Raghavendra}, title = {Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {653-652}, doi = {}, year = {2017}, }
	Meunier, Pierre-Étienne	STOC '17: "The Non-cooperative Tile Assembly ..." The Non-cooperative Tile Assembly Model Is Not Intrinsically Universal or Capable of Bounded Turing Machine Simulation Pierre-Étienne Meunier and Damien Woods (Inria, France) @InProceedings{STOC17p359, author = {Pierre-Étienne Meunier and Damien Woods}, title = {The Non-cooperative Tile Assembly Model Is Not Intrinsically Universal or Capable of Bounded Turing Machine Simulation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {359-358}, doi = {}, year = {2017}, }
	Minzer, Dor	STOC '17: "On Independent Sets, 2-to-2 ..." On Independent Sets, 2-to-2 Games, and Grassmann Graphs Subhash Khot, Dor Minzer, and Muli Safra (New York University, USA; Tel Aviv University, Israel) @InProceedings{STOC17p639, author = {Subhash Khot and Dor Minzer and Muli Safra}, title = {On Independent Sets, 2-to-2 Games, and Grassmann Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {639-638}, doi = {}, year = {2017}, }
	Moitra, Ankur	STOC '17: "Approximate Counting, the ..." Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models Ankur Moitra (Massachusetts Institute of Technology, USA) @InProceedings{STOC17p387, author = {Ankur Moitra}, title = {Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {387-386}, doi = {}, year = {2017}, }
	Montanari, Andrea	STOC '17: "How Well Do Local Algorithms ..." How Well Do Local Algorithms Solve Semidefinite Programs? Zhou Fan and Andrea Montanari (Stanford University, USA) @InProceedings{STOC17p667, author = {Zhou Fan and Andrea Montanari}, title = {How Well Do Local Algorithms Solve Semidefinite Programs?}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {667-666}, doi = {}, year = {2017}, }
	Moran, Shay	STOC '17: "Twenty (Simple) Questions ..." Twenty (Simple) Questions Yuval Dagan, Yuval Filmus, Ariel Gabizon, and Shay Moran (Technion, Israel; Zerocoin Electronic Coin, USA; University of California at San Diego, USA; Simons Institute for the Theory of Computing Berkeley, USA) @InProceedings{STOC17p9, author = {Yuval Dagan and Yuval Filmus and Ariel Gabizon and Shay Moran}, title = {Twenty (Simple) Questions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {9-8}, doi = {}, year = {2017}, }
	Mori, Ryuhei	STOC '17: "Sum of Squares Lower Bounds ..." Sum of Squares Lower Bounds for Refuting any CSP Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer (Princeton University, USA; IAS, USA; Tokyo Institute of Technology, Japan; Carnegie Mellon University, USA) @InProceedings{STOC17p149, author = {Pravesh K. Kothari and Ryuhei Mori and Ryan O'Donnell and David Witmer}, title = {Sum of Squares Lower Bounds for Refuting any CSP}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {149-148}, doi = {}, year = {2017}, }
	Moseley, Benjamin	STOC '17: "Efficient Massively Parallel ..." Efficient Massively Parallel Methods for Dynamic Programming Sungjin Im, Benjamin Moseley, and Xiaorui Sun (University of California at Merced, USA; Washington University at St. Louis, USA; Simons Institute for the Theory of Computing Berkeley, USA) @InProceedings{STOC17p877, author = {Sungjin Im and Benjamin Moseley and Xiaorui Sun}, title = {Efficient Massively Parallel Methods for Dynamic Programming}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {877-876}, doi = {}, year = {2017}, }
	Mukhopadhyay, Partha	STOC '17: "Randomized Polynomial Time ..." Randomized Polynomial Time Identity Testing for Noncommutative Circuits V. Arvind, Pushkar S Joglekar, Partha Mukhopadhyay, and S. Raja (Institute of Mathematical Sciences, India; Vishwakarma Institute of Technology Pune, India; Chennai Mathematical Institute, India) @InProceedings{STOC17p919, author = {V. Arvind and Pushkar S Joglekar and Partha Mukhopadhyay and S. Raja}, title = {Randomized Polynomial Time Identity Testing for Noncommutative Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {919-918}, doi = {}, year = {2017}, }
	Nanongkai, Danupon	STOC '17: "Dynamic Spanning Forest with ..." Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n1/2 - ε)-Time Danupon Nanongkai and Thatchaphol Saranurak (KTH, Sweden) @InProceedings{STOC17p1255, author = {Danupon Nanongkai and Thatchaphol Saranurak}, title = {Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n<sup>1/2 - ε</sup>)-Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1255-1254}, doi = {}, year = {2017}, }
	Naor, Assaf	STOC '17: "The Integrality Gap of the ..." The Integrality Gap of the Goemans-Linial SDP Relaxation for Sparsest Cut Is at Least a Constant Multiple of √log n Assaf Naor and Robert Young (Princeton University, USA; New York University, USA) @InProceedings{STOC17p625, author = {Assaf Naor and Robert Young}, title = {The Integrality Gap of the Goemans-Linial SDP Relaxation for Sparsest Cut Is at Least a Constant Multiple of √log n}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {625-624}, doi = {}, year = {2017}, }
	Natarajan, Anand	STOC '17: "A Quantum Linearity Test for ..." A Quantum Linearity Test for Robustly Verifying Entanglement Anand Natarajan and Thomas Vidick (Massachusetts Institute of Technology, USA; California Institute of Technology, USA) @InProceedings{STOC17p1115, author = {Anand Natarajan and Thomas Vidick}, title = {A Quantum Linearity Test for Robustly Verifying Entanglement}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1115-1114}, doi = {}, year = {2017}, }
	Nazarov, Fedor	STOC '17: "Trace Reconstruction with ..." Trace Reconstruction with exp(O(n1/3)) Samples Fedor Nazarov and Yuval Peres (Kent State University, USA; Microsoft Research, USA) @InProceedings{STOC17p1157, author = {Fedor Nazarov and Yuval Peres}, title = {Trace Reconstruction with exp(O(n<sup>1/3</sup>)) Samples}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1157-1156}, doi = {}, year = {2017}, }
	Nederlof, Jesper	STOC '17: "Faster Space-Efficient Algorithms ..." Faster Space-Efficient Algorithms for Subset Sum and k-Sum Nikhil Bansal, Shashwat Garg, Jesper Nederlof, and Nikhil Vyas (Eindhoven University of Technology, Netherlands; IIT Bombay, India) @InProceedings{STOC17p219, author = {Nikhil Bansal and Shashwat Garg and Jesper Nederlof and Nikhil Vyas}, title = {Faster Space-Efficient Algorithms for Subset Sum and k-Sum}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {219-218}, doi = {}, year = {2017}, }
	Nguyen, Danny	STOC '17: "Complexity of Short Presburger ..." Complexity of Short Presburger Arithmetic Danny Nguyen and Igor Pak (University of California at Los Angeles, USA) @InProceedings{STOC17p891, author = {Danny Nguyen and Igor Pak}, title = {Complexity of Short Presburger Arithmetic}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {891-890}, doi = {}, year = {2017}, }
	Nguyen, Huy L.	STOC '17: "Approximate Near Neighbors ..." Approximate Near Neighbors for General Symmetric Norms Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten (Columbia University, USA; Northeastern University, USA; University of Toronto, Canada; Massachusetts Institute of Technology, USA) @InProceedings{STOC17p1003, author = {Alexandr Andoni and Huy L. Nguyen and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten}, title = {Approximate Near Neighbors for General Symmetric Norms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1003-1002}, doi = {}, year = {2017}, }
	Niazadeh, Rad	STOC '17: "Bernoulli Factories and Black-Box ..." Bernoulli Factories and Black-Box Reductions in Mechanism Design Shaddin Dughmi, Jason D. Hartline, Robert Kleinberg, and Rad Niazadeh (University of Southern California, USA; Northwestern University, USA; Cornell University, USA) @InProceedings{STOC17p177, author = {Shaddin Dughmi and Jason D. Hartline and Robert Kleinberg and Rad Niazadeh}, title = {Bernoulli Factories and Black-Box Reductions in Mechanism Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {177-176}, doi = {}, year = {2017}, }
	Nikolaenko, Valeria	STOC '17: "Practical Post-quantum Key ..." Practical Post-quantum Key Agreement from Generic Lattices (Invited Talk) Valeria Nikolaenko (Stanford University, USA) @InProceedings{STOC17p8, author = {Valeria Nikolaenko}, title = {Practical Post-quantum Key Agreement from Generic Lattices (Invited Talk)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {8-7}, doi = {}, year = {2017}, }
	Nikolov, Aleksandar	STOC '17: "Approximate Near Neighbors ..." Approximate Near Neighbors for General Symmetric Norms Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten (Columbia University, USA; Northeastern University, USA; University of Toronto, Canada; Massachusetts Institute of Technology, USA) @InProceedings{STOC17p1003, author = {Alexandr Andoni and Huy L. Nguyen and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten}, title = {Approximate Near Neighbors for General Symmetric Norms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1003-1002}, doi = {}, year = {2017}, }
	Nimavat, Rachit	STOC '17: "New Hardness Results for Routing ..." New Hardness Results for Routing on Disjoint Paths Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat (Toyota Technological Institute at Chicago, USA; University of Chicago, USA) @InProceedings{STOC17p93, author = {Julia Chuzhoy and David H. K. Kim and Rachit Nimavat}, title = {New Hardness Results for Routing on Disjoint Paths}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {93-92}, doi = {}, year = {2017}, }
	Nisan, Noam	STOC '17: "Efficient Empirical Revenue ..." Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments Yannai A. Gonczarowski and Noam Nisan (Hebrew University of Jerusalem, Israel; Microsoft Research, Israel) @InProceedings{STOC17p947, author = {Yannai A. Gonczarowski and Noam Nisan}, title = {Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {947-946}, doi = {}, year = {2017}, } STOC '17: "The Menu-Size Complexity of ..." The Menu-Size Complexity of Revenue Approximation Moshe Babaioff, Yannai A. Gonczarowski, and Noam Nisan (Microsoft Research, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC17p961, author = {Moshe Babaioff and Yannai A. Gonczarowski and Noam Nisan}, title = {The Menu-Size Complexity of Revenue Approximation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {961-960}, doi = {}, year = {2017}, }
	O'Donnell, Ryan	STOC '17: "Efficient Quantum Tomography ..." Efficient Quantum Tomography II Ryan O'Donnell and John Wright (Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC17p1073, author = {Ryan O'Donnell and John Wright}, title = {Efficient Quantum Tomography II}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1073-1072}, doi = {}, year = {2017}, } STOC '17: "Optimal Mean-Based Algorithms ..." Optimal Mean-Based Algorithms for Trace Reconstruction Anindya De, Ryan O'Donnell, and Rocco A. Servedio (Northwestern University, USA; Carnegie Mellon University, USA; Columbia University, USA) @InProceedings{STOC17p1171, author = {Anindya De and Ryan O'Donnell and Rocco A. Servedio}, title = {Optimal Mean-Based Algorithms for Trace Reconstruction}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1171-1170}, doi = {}, year = {2017}, } STOC '17: "Sum of Squares Lower Bounds ..." Sum of Squares Lower Bounds for Refuting any CSP Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer (Princeton University, USA; IAS, USA; Tokyo Institute of Technology, Japan; Carnegie Mellon University, USA) @InProceedings{STOC17p149, author = {Pravesh K. Kothari and Ryuhei Mori and Ryan O'Donnell and David Witmer}, title = {Sum of Squares Lower Bounds for Refuting any CSP}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {149-148}, doi = {}, year = {2017}, }
	Oliveira, Igor C.	STOC '17: "Addition Is Exponentially ..." Addition Is Exponentially Harder Than Counting for Shallow Monotone Circuits Xi Chen, Igor C. Oliveira, and Rocco A. Servedio (Columbia University, USA; Charles University in Prague, Czechia) @InProceedings{STOC17p1395, author = {Xi Chen and Igor C. Oliveira and Rocco A. Servedio}, title = {Addition Is Exponentially Harder Than Counting for Shallow Monotone Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1395-1394}, doi = {}, year = {2017}, } STOC '17: "Pseudodeterministic Constructions ..." Pseudodeterministic Constructions in Subexponential Time Igor C. Oliveira and Rahul Santhanam (Charles University in Prague, Czechia; University of Oxford, UK) @InProceedings{STOC17p737, author = {Igor C. Oliveira and Rahul Santhanam}, title = {Pseudodeterministic Constructions in Subexponential Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {737-736}, doi = {}, year = {2017}, }
	Oliveira, Rafael	STOC '17: "Algorithmic and Optimization ..." Algorithmic and Optimization Aspects of Brascamp-Lieb Inequalities, via Operator Scaling Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson (Microsoft Research, USA; City College of New York, USA; Princeton University, USA; IAS, USA) @InProceedings{STOC17p429, author = {Ankit Garg and Leonid Gurvits and Rafael Oliveira and Avi Wigderson}, title = {Algorithmic and Optimization Aspects of Brascamp-Lieb Inequalities, via Operator Scaling}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {429-428}, doi = {}, year = {2017}, }
	Olver, Neil	STOC '17: "A Simpler and Faster Strongly ..." A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization Neil Olver and László A. Végh (VU University Amsterdam, Netherlands; CWI, Netherlands; London School of Economics, UK) @InProceedings{STOC17p107, author = {Neil Olver and László A. Végh}, title = {A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {107-106}, doi = {}, year = {2017}, }
	Pagh, Rasmus	STOC '17: "Set Similarity Search Beyond ..." Set Similarity Search Beyond MinHash Tobias Christiani and Rasmus Pagh (IT University of Copenhagen, Denmark) @InProceedings{STOC17p1227, author = {Tobias Christiani and Rasmus Pagh}, title = {Set Similarity Search Beyond MinHash}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1227-1226}, doi = {}, year = {2017}, }
	Pak, Igor	STOC '17: "Complexity of Short Presburger ..." Complexity of Short Presburger Arithmetic Danny Nguyen and Igor Pak (University of California at Los Angeles, USA) @InProceedings{STOC17p891, author = {Danny Nguyen and Igor Pak}, title = {Complexity of Short Presburger Arithmetic}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {891-890}, doi = {}, year = {2017}, }
	Pandurangan, Gopal	STOC '17: "A Time- and Message-Optimal ..." A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees Gopal Pandurangan, Peter Robinson, and Michele Scquizzato (University of Houston, USA; Royal Holloway University of London, UK) @InProceedings{STOC17p821, author = {Gopal Pandurangan and Peter Robinson and Michele Scquizzato}, title = {A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {821-820}, doi = {}, year = {2017}, }
	Panigrahi, Debmalya	STOC '17: "Online and Dynamic Algorithms ..." Online and Dynamic Algorithms for Set Cover Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi (Carnegie Mellon University, USA; Microsoft Research, India; IIT Delhi, India; Duke University, USA) @InProceedings{STOC17p597, author = {Anupam Gupta and Ravishankar Krishnaswamy and Amit Kumar and Debmalya Panigrahi}, title = {Online and Dynamic Algorithms for Set Cover}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {597-596}, doi = {}, year = {2017}, } STOC '17: "Online Service with Delay ..." Online Service with Delay Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi (Tel Aviv University, Israel; Duke University, USA) @InProceedings{STOC17p611, author = {Yossi Azar and Arun Ganesh and Rong Ge and Debmalya Panigrahi}, title = {Online Service with Delay}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {611-610}, doi = {}, year = {2017}, }
	Panolan, Fahad	STOC '17: "Lossy Kernelization ..." Lossy Kernelization Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh (University of Bergen, Norway; Vienna University of Technology, Austria; Institute of Mathematical Sciences, India) @InProceedings{STOC17p247, author = {Daniel Lokshtanov and Fahad Panolan and M. S. Ramanujan and Saket Saurabh}, title = {Lossy Kernelization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {247-246}, doi = {}, year = {2017}, }
	Peebles, John	STOC '17: "Almost-Linear-Time Algorithms ..." Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu (Massachusetts Institute of Technology, USA; Georgia Institute of Technology, USA; Stanford University, USA) @InProceedings{STOC17p443, author = {Michael B. Cohen and Jonathan Kelner and John Peebles and Richard Peng and Anup B. Rao and Aaron Sidford and Adrian Vladu}, title = {Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {443-442}, doi = {}, year = {2017}, } STOC '17: "Sampling Random Spanning Trees ..." Sampling Random Spanning Trees Faster Than Matrix Multiplication David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva (Georgia Institute of Technology, USA; Yale University, USA; Massachusetts Institute of Technology, USA; Google, USA) @InProceedings{STOC17p807, author = {David Durfee and Rasmus Kyng and John Peebles and Anup B. Rao and Sushant Sachdeva}, title = {Sampling Random Spanning Trees Faster Than Matrix Multiplication}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {807-806}, doi = {}, year = {2017}, }
	Peikert, Chris	STOC '17: "Pseudorandomness of Ring-LWE ..." Pseudorandomness of Ring-LWE for Any Ring and Modulus Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz (University of Michigan, USA; New York University, USA) @InProceedings{STOC17p513, author = {Chris Peikert and Oded Regev and Noah Stephens-Davidowitz}, title = {Pseudorandomness of Ring-LWE for Any Ring and Modulus}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {513-512}, doi = {}, year = {2017}, }
	Peng, Richard	STOC '17: "Almost-Linear-Time Algorithms ..." Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu (Massachusetts Institute of Technology, USA; Georgia Institute of Technology, USA; Stanford University, USA) @InProceedings{STOC17p443, author = {Michael B. Cohen and Jonathan Kelner and John Peebles and Richard Peng and Anup B. Rao and Aaron Sidford and Adrian Vladu}, title = {Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {443-442}, doi = {}, year = {2017}, }
	Peres, Yuval	STOC '17: "Trace Reconstruction with ..." Trace Reconstruction with exp(O(n1/3)) Samples Fedor Nazarov and Yuval Peres (Kent State University, USA; Microsoft Research, USA) @InProceedings{STOC17p1157, author = {Fedor Nazarov and Yuval Peres}, title = {Trace Reconstruction with exp(O(n<sup>1/3</sup>)) Samples}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1157-1156}, doi = {}, year = {2017}, } STOC '17: "Local Max-Cut in Smoothed ..." Local Max-Cut in Smoothed Polynomial Time Omer Angel, Sébastien Bubeck, Yuval Peres, and Fan Wei (University of British Columbia, Canada; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC17p471, author = {Omer Angel and Sébastien Bubeck and Yuval Peres and Fan Wei}, title = {Local Max-Cut in Smoothed Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {471-470}, doi = {}, year = {2017}, }
	Perkins, Will	STOC '17: "Information-Theoretic Thresholds ..." Information-Theoretic Thresholds from the Cavity Method Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborova (Goethe University Frankfurt, Germany; CNRS, France; PSL Research University, France; ENS, France; UPMC, France; University of Birmingham, UK; CEA, France; University of Paris-Saclay, France) @InProceedings{STOC17p163, author = {Amin Coja-Oghlan and Florent Krzakala and Will Perkins and Lenka Zdeborova}, title = {Information-Theoretic Thresholds from the Cavity Method}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {163-162}, doi = {}, year = {2017}, }
	Pettie, Seth	STOC '17: "Exponential Separations in ..." Exponential Separations in the Energy Complexity of Leader Election Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, and Wei Zhan (University of Michigan, USA; Tsinghua University, China) @InProceedings{STOC17p849, author = {Yi-Jun Chang and Tsvi Kopelowitz and Seth Pettie and Ruosong Wang and Wei Zhan}, title = {Exponential Separations in the Energy Complexity of Leader Election}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {849-848}, doi = {}, year = {2017}, }
	Pitassi, Toniann	STOC '17: "Strongly Exponential Lower ..." Strongly Exponential Lower Bounds for Monotone Computation Toniann Pitassi and Robert Robere (University of Toronto, Canada) @InProceedings{STOC17p1409, author = {Toniann Pitassi and Robert Robere}, title = {Strongly Exponential Lower Bounds for Monotone Computation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1409-1408}, doi = {}, year = {2017}, }
	Poburinnaya, Oxana	STOC '17: "Equivocating Yao: Constant-Round ..." Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model Ran Canetti, Oxana Poburinnaya, and Muthuramakrishnan Venkitasubramaniam (Boston University, USA; Tel Aviv University, Israel; University of Rochester, USA) @InProceedings{STOC17p555, author = {Ran Canetti and Oxana Poburinnaya and Muthuramakrishnan Venkitasubramaniam}, title = {Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {555-554}, doi = {}, year = {2017}, }
	Raghavendra, Prasad	STOC '17: "Strongly Refuting Random CSPs ..." Strongly Refuting Random CSPs Below the Spectral Threshold Prasad Raghavendra, Satish Rao, and Tselil Schramm (University of California at Berkeley, USA) @InProceedings{STOC17p135, author = {Prasad Raghavendra and Satish Rao and Tselil Schramm}, title = {Strongly Refuting Random CSPs Below the Spectral Threshold}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {135-134}, doi = {}, year = {2017}, } STOC '17: "Approximating Rectangles by ..." Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra (Princeton University, USA; IAS, USA; University of California at Los Angeles, USA; University of California at Berkeley, USA) @InProceedings{STOC17p653, author = {Pravesh K. Kothari and Raghu Meka and Prasad Raghavendra}, title = {Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {653-652}, doi = {}, year = {2017}, }
	Raja, S.	STOC '17: "Randomized Polynomial Time ..." Randomized Polynomial Time Identity Testing for Noncommutative Circuits V. Arvind, Pushkar S Joglekar, Partha Mukhopadhyay, and S. Raja (Institute of Mathematical Sciences, India; Vishwakarma Institute of Technology Pune, India; Chennai Mathematical Institute, India) @InProceedings{STOC17p919, author = {V. Arvind and Pushkar S Joglekar and Partha Mukhopadhyay and S. Raja}, title = {Randomized Polynomial Time Identity Testing for Noncommutative Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {919-918}, doi = {}, year = {2017}, }
	Ramanujan, M. S.	STOC '17: "Lossy Kernelization ..." Lossy Kernelization Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh (University of Bergen, Norway; Vienna University of Technology, Austria; Institute of Mathematical Sciences, India) @InProceedings{STOC17p247, author = {Daniel Lokshtanov and Fahad Panolan and M. S. Ramanujan and Saket Saurabh}, title = {Lossy Kernelization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {247-246}, doi = {}, year = {2017}, }
	Rao, Anup B.	STOC '17: "Almost-Linear-Time Algorithms ..." Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu (Massachusetts Institute of Technology, USA; Georgia Institute of Technology, USA; Stanford University, USA) @InProceedings{STOC17p443, author = {Michael B. Cohen and Jonathan Kelner and John Peebles and Richard Peng and Anup B. Rao and Aaron Sidford and Adrian Vladu}, title = {Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {443-442}, doi = {}, year = {2017}, } STOC '17: "Sampling Random Spanning Trees ..." Sampling Random Spanning Trees Faster Than Matrix Multiplication David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva (Georgia Institute of Technology, USA; Yale University, USA; Massachusetts Institute of Technology, USA; Google, USA) @InProceedings{STOC17p807, author = {David Durfee and Rasmus Kyng and John Peebles and Anup B. Rao and Sushant Sachdeva}, title = {Sampling Random Spanning Trees Faster Than Matrix Multiplication}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {807-806}, doi = {}, year = {2017}, }
	Rao, Satish	STOC '17: "Strongly Refuting Random CSPs ..." Strongly Refuting Random CSPs Below the Spectral Threshold Prasad Raghavendra, Satish Rao, and Tselil Schramm (University of California at Berkeley, USA) @InProceedings{STOC17p135, author = {Prasad Raghavendra and Satish Rao and Tselil Schramm}, title = {Strongly Refuting Random CSPs Below the Spectral Threshold}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {135-134}, doi = {}, year = {2017}, }
	Raz, Ran	STOC '17: "Time-Space Hardness of Learning ..." Time-Space Hardness of Learning Sparse Parities Gillat Kol, Ran Raz, and Avishay Tal (Princeton University, USA; IAS, USA) @InProceedings{STOC17p1199, author = {Gillat Kol and Ran Raz and Avishay Tal}, title = {Time-Space Hardness of Learning Sparse Parities}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1199-1198}, doi = {}, year = {2017}, }
	Razenshteyn, Ilya	STOC '17: "Approximate Near Neighbors ..." Approximate Near Neighbors for General Symmetric Norms Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten (Columbia University, USA; Northeastern University, USA; University of Toronto, Canada; Massachusetts Institute of Technology, USA) @InProceedings{STOC17p1003, author = {Alexandr Andoni and Huy L. Nguyen and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten}, title = {Approximate Near Neighbors for General Symmetric Norms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1003-1002}, doi = {}, year = {2017}, }
	Regev, Oded	STOC '17: "A Reverse Minkowski Theorem ..." A Reverse Minkowski Theorem Oded Regev and Noah Stephens-Davidowitz (New York University, USA) @InProceedings{STOC17p1045, author = {Oded Regev and Noah Stephens-Davidowitz}, title = {A Reverse Minkowski Theorem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1045-1044}, doi = {}, year = {2017}, } STOC '17: "Pseudorandomness of Ring-LWE ..." Pseudorandomness of Ring-LWE for Any Ring and Modulus Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz (University of Michigan, USA; New York University, USA) @InProceedings{STOC17p513, author = {Chris Peikert and Oded Regev and Noah Stephens-Davidowitz}, title = {Pseudorandomness of Ring-LWE for Any Ring and Modulus}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {513-512}, doi = {}, year = {2017}, }
	Risteski, Andrej	STOC '17: "Provable Learning of Noisy-or ..." Provable Learning of Noisy-or Networks Sanjeev Arora, Rong Ge, Tengyu Ma, and Andrej Risteski (Princeton University, USA; Duke University, USA) @InProceedings{STOC17p1185, author = {Sanjeev Arora and Rong Ge and Tengyu Ma and Andrej Risteski}, title = {Provable Learning of Noisy-or Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1185-1184}, doi = {}, year = {2017}, }
	Robere, Robert	STOC '17: "Strongly Exponential Lower ..." Strongly Exponential Lower Bounds for Monotone Computation Toniann Pitassi and Robert Robere (University of Toronto, Canada) @InProceedings{STOC17p1409, author = {Toniann Pitassi and Robert Robere}, title = {Strongly Exponential Lower Bounds for Monotone Computation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1409-1408}, doi = {}, year = {2017}, }
	Robinson, Peter	STOC '17: "A Time- and Message-Optimal ..." A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees Gopal Pandurangan, Peter Robinson, and Michele Scquizzato (University of Houston, USA; Royal Holloway University of London, UK) @InProceedings{STOC17p821, author = {Gopal Pandurangan and Peter Robinson and Michele Scquizzato}, title = {A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {821-820}, doi = {}, year = {2017}, }
	Rosen, Alon	STOC '17: "Average-Case Fine-Grained ..." Average-Case Fine-Grained Hardness Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan (Columbia University, USA; IDC Herzliya, Israel; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC17p541, author = {Marshall Ball and Alon Rosen and Manuel Sabin and Prashant Nalini Vasudevan}, title = {Average-Case Fine-Grained Hardness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {541-540}, doi = {}, year = {2017}, }
	Roughgarden, Tim	STOC '17: "Why Prices Need Algorithms ..." Why Prices Need Algorithms (Invited Talk) Tim Roughgarden and Inbal Talgam-Cohen (Stanford University, USA; Hebrew University of Jerusalem, Israel) @InProceedings{STOC17p2, author = {Tim Roughgarden and Inbal Talgam-Cohen}, title = {Why Prices Need Algorithms (Invited Talk)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2-1}, doi = {}, year = {2017}, }
	Rubinstein, Aviad	STOC '17: "The Limitations of Optimization ..." The Limitations of Optimization from Samples Eric Balkanski, Aviad Rubinstein, and Yaron Singer (Harvard University, USA; University of California at Berkeley, USA) @InProceedings{STOC17p1129, author = {Eric Balkanski and Aviad Rubinstein and Yaron Singer}, title = {The Limitations of Optimization from Samples}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1129-1128}, doi = {}, year = {2017}, } STOC '17: "Communication Complexity of ..." Communication Complexity of Approximate Nash Equilibria Yakov Babichenko and Aviad Rubinstein (Technion, Israel; University of California at Berkeley, USA) @InProceedings{STOC17p975, author = {Yakov Babichenko and Aviad Rubinstein}, title = {Communication Complexity of Approximate Nash Equilibria}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {975-974}, doi = {}, year = {2017}, }
	Rudra, Atri	STOC '17: "Answering FAQs in CSPs, Probabilistic ..." Answering FAQs in CSPs, Probabilistic Graphical Models, Databases, Logic and Matrix Operations (Invited Talk) Atri Rudra (SUNY Buffalo, USA) @InProceedings{STOC17p4, author = {Atri Rudra}, title = {Answering FAQs in CSPs, Probabilistic Graphical Models, Databases, Logic and Matrix Operations (Invited Talk)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {4-3}, doi = {}, year = {2017}, }
	Sabin, Manuel	STOC '17: "Average-Case Fine-Grained ..." Average-Case Fine-Grained Hardness Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan (Columbia University, USA; IDC Herzliya, Israel; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC17p541, author = {Marshall Ball and Alon Rosen and Manuel Sabin and Prashant Nalini Vasudevan}, title = {Average-Case Fine-Grained Hardness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {541-540}, doi = {}, year = {2017}, }
	Sachdeva, Sushant	STOC '17: "Sampling Random Spanning Trees ..." Sampling Random Spanning Trees Faster Than Matrix Multiplication David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva (Georgia Institute of Technology, USA; Yale University, USA; Massachusetts Institute of Technology, USA; Google, USA) @InProceedings{STOC17p807, author = {David Durfee and Rasmus Kyng and John Peebles and Anup B. Rao and Sushant Sachdeva}, title = {Sampling Random Spanning Trees Faster Than Matrix Multiplication}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {807-806}, doi = {}, year = {2017}, }
	Safra, Muli	STOC '17: "On Independent Sets, 2-to-2 ..." On Independent Sets, 2-to-2 Games, and Grassmann Graphs Subhash Khot, Dor Minzer, and Muli Safra (New York University, USA; Tel Aviv University, Israel) @InProceedings{STOC17p639, author = {Subhash Khot and Dor Minzer and Muli Safra}, title = {On Independent Sets, 2-to-2 Games, and Grassmann Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {639-638}, doi = {}, year = {2017}, }
	Sankowski, Piotr	STOC '17: "Decremental Single-Source ..." Decremental Single-Source Reachability in Planar Digraphs Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, and Piotr Sankowski (University of Rome Tor Vergata, Italy; University of Warsaw, Poland; Google Research, USA) @InProceedings{STOC17p1241, author = {Giuseppe F. Italiano and Adam Karczmarz and Jakub Łącki and Piotr Sankowski}, title = {Decremental Single-Source Reachability in Planar Digraphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1241-1240}, doi = {}, year = {2017}, }
	Santhanam, Rahul	STOC '17: "Pseudodeterministic Constructions ..." Pseudodeterministic Constructions in Subexponential Time Igor C. Oliveira and Rahul Santhanam (Charles University in Prague, Czechia; University of Oxford, UK) @InProceedings{STOC17p737, author = {Igor C. Oliveira and Rahul Santhanam}, title = {Pseudodeterministic Constructions in Subexponential Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {737-736}, doi = {}, year = {2017}, }
	Saranurak, Thatchaphol	STOC '17: "Dynamic Spanning Forest with ..." Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n1/2 - ε)-Time Danupon Nanongkai and Thatchaphol Saranurak (KTH, Sweden) @InProceedings{STOC17p1255, author = {Danupon Nanongkai and Thatchaphol Saranurak}, title = {Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n<sup>1/2 - ε</sup>)-Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1255-1254}, doi = {}, year = {2017}, }
	Saurabh, Saket	STOC '17: "Lossy Kernelization ..." Lossy Kernelization Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh (University of Bergen, Norway; Vienna University of Technology, Austria; Institute of Mathematical Sciences, India) @InProceedings{STOC17p247, author = {Daniel Lokshtanov and Fahad Panolan and M. S. Ramanujan and Saket Saurabh}, title = {Lossy Kernelization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {247-246}, doi = {}, year = {2017}, }
	Scarlett, Jonathan	STOC '17: "An Adaptive Sublinear-Time ..." An Adaptive Sublinear-Time Block Sparse Fourier Transform Volkan Cevher, Michael Kapralov, Jonathan Scarlett, and Amir Zandieh (EPFL, Switzerland) @InProceedings{STOC17p779, author = {Volkan Cevher and Michael Kapralov and Jonathan Scarlett and Amir Zandieh}, title = {An Adaptive Sublinear-Time Block Sparse Fourier Transform}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {779-778}, doi = {}, year = {2017}, }
	Schramm, Tselil	STOC '17: "Strongly Refuting Random CSPs ..." Strongly Refuting Random CSPs Below the Spectral Threshold Prasad Raghavendra, Satish Rao, and Tselil Schramm (University of California at Berkeley, USA) @InProceedings{STOC17p135, author = {Prasad Raghavendra and Satish Rao and Tselil Schramm}, title = {Strongly Refuting Random CSPs Below the Spectral Threshold}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {135-134}, doi = {}, year = {2017}, }
	Scquizzato, Michele	STOC '17: "A Time- and Message-Optimal ..." A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees Gopal Pandurangan, Peter Robinson, and Michele Scquizzato (University of Houston, USA; Royal Holloway University of London, UK) @InProceedings{STOC17p821, author = {Gopal Pandurangan and Peter Robinson and Michele Scquizzato}, title = {A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {821-820}, doi = {}, year = {2017}, }
	Servedio, Rocco A.	STOC '17: "Optimal Mean-Based Algorithms ..." Optimal Mean-Based Algorithms for Trace Reconstruction Anindya De, Ryan O'Donnell, and Rocco A. Servedio (Northwestern University, USA; Carnegie Mellon University, USA; Columbia University, USA) @InProceedings{STOC17p1171, author = {Anindya De and Ryan O'Donnell and Rocco A. Servedio}, title = {Optimal Mean-Based Algorithms for Trace Reconstruction}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1171-1170}, doi = {}, year = {2017}, } STOC '17: "Addition Is Exponentially ..." Addition Is Exponentially Harder Than Counting for Shallow Monotone Circuits Xi Chen, Igor C. Oliveira, and Rocco A. Servedio (Columbia University, USA; Charles University in Prague, Czechia) @InProceedings{STOC17p1395, author = {Xi Chen and Igor C. Oliveira and Rocco A. Servedio}, title = {Addition Is Exponentially Harder Than Counting for Shallow Monotone Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1395-1394}, doi = {}, year = {2017}, }
	Shahrasbi, Amirbehshad	STOC '17: "Synchronization Strings: Codes ..." Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound Bernhard Haeupler and Amirbehshad Shahrasbi (Carnegie Mellon University, USA) @InProceedings{STOC17p37, author = {Bernhard Haeupler and Amirbehshad Shahrasbi}, title = {Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {37-36}, doi = {}, year = {2017}, }
	Shapira, Asaf	STOC '17: "Removal Lemmas with Polynomial ..." Removal Lemmas with Polynomial Bounds Lior Gishboliner and Asaf Shapira (Tel Aviv University, Israel) @InProceedings{STOC17p569, author = {Lior Gishboliner and Asaf Shapira}, title = {Removal Lemmas with Polynomial Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {569-568}, doi = {}, year = {2017}, }
	Sherman, Jonah	STOC '17: "Area-Convexity, ℓ∞ ..." Area-Convexity, ℓ∞ Regularization, and Undirected Multicommodity Flow Jonah Sherman (University of California at Berkeley, USA) @InProceedings{STOC17p499, author = {Jonah Sherman}, title = {Area-Convexity, ℓ<sub>∞</sub> Regularization, and Undirected Multicommodity Flow}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {499-498}, doi = {}, year = {2017}, }
	Shpilka, Amir	STOC '17: "Succinct Hitting Sets and ..." Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds Michael A. Forbes, Amir Shpilka, and Ben Lee Volk (Simons Institute for the Theory of Computing Berkeley, USA; Tel Aviv University, Israel) @InProceedings{STOC17p723, author = {Michael A. Forbes and Amir Shpilka and Ben Lee Volk}, title = {Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {723-722}, doi = {}, year = {2017}, }
	Sidford, Aaron	STOC '17: "Subquadratic Submodular Function ..." Subquadratic Submodular Function Minimization Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong (Dartmouth College, USA; Microsoft Research, USA; Stanford University, USA; University of California at Berkeley, USA) @InProceedings{STOC17p1381, author = {Deeparnab Chakrabarty and Yin Tat Lee and Aaron Sidford and Sam Chiu-wai Wong}, title = {Subquadratic Submodular Function Minimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1381-1380}, doi = {}, year = {2017}, } STOC '17: "Almost-Linear-Time Algorithms ..." Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu (Massachusetts Institute of Technology, USA; Georgia Institute of Technology, USA; Stanford University, USA) @InProceedings{STOC17p443, author = {Michael B. Cohen and Jonathan Kelner and John Peebles and Richard Peng and Anup B. Rao and Aaron Sidford and Adrian Vladu}, title = {Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {443-442}, doi = {}, year = {2017}, }
	Singer, Yaron	STOC '17: "The Limitations of Optimization ..." The Limitations of Optimization from Samples Eric Balkanski, Aviad Rubinstein, and Yaron Singer (Harvard University, USA; University of California at Berkeley, USA) @InProceedings{STOC17p1129, author = {Eric Balkanski and Aviad Rubinstein and Yaron Singer}, title = {The Limitations of Optimization from Samples}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1129-1128}, doi = {}, year = {2017}, }
	Sivan, Balasubramanian	STOC '17: "Stability of Service under ..." Stability of Service under Time-of-Use Pricing Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James B. Martin, and Balasubramanian Sivan (University of Wisconsin-Madison, USA; Microsoft Research, USA; University of Washington, USA; University of Oxford, UK; Google Research, USA) @InProceedings{STOC17p205, author = {Shuchi Chawla and Nikhil R. Devanur and Alexander E. Holroyd and Anna R. Karlin and James B. Martin and Balasubramanian Sivan}, title = {Stability of Service under Time-of-Use Pricing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {205-204}, doi = {}, year = {2017}, }
	Song, Zhao	STOC '17: "Low Rank Approximation with ..." Low Rank Approximation with Entrywise ℓ₁-Norm Error Zhao Song, David P. Woodruff, and Peilin Zhong (University of Texas at Austin, USA; IBM Research, USA; Columbia University, USA) @InProceedings{STOC17p765, author = {Zhao Song and David P. Woodruff and Peilin Zhong}, title = {Low Rank Approximation with Entrywise ℓ₁-Norm Error}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {765-764}, doi = {}, year = {2017}, }
	Steinhardt, Jacob	STOC '17: "Learning from Untrusted Data ..." Learning from Untrusted Data Moses Charikar, Jacob Steinhardt, and Gregory Valiant (Stanford University, USA) @InProceedings{STOC17p51, author = {Moses Charikar and Jacob Steinhardt and Gregory Valiant}, title = {Learning from Untrusted Data}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {51-50}, doi = {}, year = {2017}, }
	Stephan, Frank	STOC '17: "Deciding Parity Games in Quasipolynomial ..." Deciding Parity Games in Quasipolynomial Time Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan (University of Auckland, New Zealand; National University of Singapore, Singapore) @InProceedings{STOC17p275, author = {Cristian S. Calude and Sanjay Jain and Bakhadyr Khoussainov and Wei Li and Frank Stephan}, title = {Deciding Parity Games in Quasipolynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {275-274}, doi = {}, year = {2017}, }
	Stephens-Davidowitz, Noah	STOC '17: "A Reverse Minkowski Theorem ..." A Reverse Minkowski Theorem Oded Regev and Noah Stephens-Davidowitz (New York University, USA) @InProceedings{STOC17p1045, author = {Oded Regev and Noah Stephens-Davidowitz}, title = {A Reverse Minkowski Theorem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1045-1044}, doi = {}, year = {2017}, } STOC '17: "Pseudorandomness of Ring-LWE ..." Pseudorandomness of Ring-LWE for Any Ring and Modulus Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz (University of Michigan, USA; New York University, USA) @InProceedings{STOC17p513, author = {Chris Peikert and Oded Regev and Noah Stephens-Davidowitz}, title = {Pseudorandomness of Ring-LWE for Any Ring and Modulus}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {513-512}, doi = {}, year = {2017}, }
	Steurer, David	STOC '17: "Quantum Entanglement, Sum ..." Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture Boaz Barak, Pravesh K. Kothari, and David Steurer (Harvard University, USA; Princeton University, USA; IAS, USA; Cornell University, USA) @InProceedings{STOC17p1087, author = {Boaz Barak and Pravesh K. Kothari and David Steurer}, title = {Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1087-1086}, doi = {}, year = {2017}, }
	Stöckel, Morten	STOC '17: "Finding Even Cycles Faster ..." Finding Even Cycles Faster via Capped k-Walks Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Morten Stöckel (University of Copenhagen, Denmark) @InProceedings{STOC17p121, author = {Søren Dahlgaard and Mathias Bæk Tejs Knudsen and Morten Stöckel}, title = {Finding Even Cycles Faster via Capped k-Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {121-120}, doi = {}, year = {2017}, }
	Straszak, Damian	STOC '17: "Real Stable Polynomials and ..." Real Stable Polynomials and Matroids: Optimization and Counting Damian Straszak and Nisheeth K. Vishnoi (EPFL, Switzerland) @InProceedings{STOC17p401, author = {Damian Straszak and Nisheeth K. Vishnoi}, title = {Real Stable Polynomials and Matroids: Optimization and Counting}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {401-400}, doi = {}, year = {2017}, }
	Sun, He	STOC '17: "An SDP-Based Algorithm for ..." An SDP-Based Algorithm for Linear-Sized Spectral Sparsification Yin Tat Lee and He Sun (Microsoft Research, USA; University of Bristol, UK) @InProceedings{STOC17p751, author = {Yin Tat Lee and He Sun}, title = {An SDP-Based Algorithm for Linear-Sized Spectral Sparsification}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {751-750}, doi = {}, year = {2017}, }
	Sun, Xiaorui	STOC '17: "Efficient Massively Parallel ..." Efficient Massively Parallel Methods for Dynamic Programming Sungjin Im, Benjamin Moseley, and Xiaorui Sun (University of California at Merced, USA; Washington University at St. Louis, USA; Simons Institute for the Theory of Computing Berkeley, USA) @InProceedings{STOC17p877, author = {Sungjin Im and Benjamin Moseley and Xiaorui Sun}, title = {Efficient Massively Parallel Methods for Dynamic Programming}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {877-876}, doi = {}, year = {2017}, }
	Syrgkanis, Vasilis	STOC '17: "Fast Convergence of Learning ..." Fast Convergence of Learning in Games (Invited Talk) Vasilis Syrgkanis (Microsoft Research, USA) @InProceedings{STOC17p5, author = {Vasilis Syrgkanis}, title = {Fast Convergence of Learning in Games (Invited Talk)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {5-4}, doi = {}, year = {2017}, }
	Tal, Avishay	STOC '17: "Time-Space Hardness of Learning ..." Time-Space Hardness of Learning Sparse Parities Gillat Kol, Ran Raz, and Avishay Tal (Princeton University, USA; IAS, USA) @InProceedings{STOC17p1199, author = {Gillat Kol and Ran Raz and Avishay Tal}, title = {Time-Space Hardness of Learning Sparse Parities}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1199-1198}, doi = {}, year = {2017}, } STOC '17: "Formula Lower Bounds via the ..." Formula Lower Bounds via the Quantum Method Avishay Tal (IAS, USA) @InProceedings{STOC17p1423, author = {Avishay Tal}, title = {Formula Lower Bounds via the Quantum Method}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1423-1422}, doi = {}, year = {2017}, }
	Talgam-Cohen, Inbal	STOC '17: "Why Prices Need Algorithms ..." Why Prices Need Algorithms (Invited Talk) Tim Roughgarden and Inbal Talgam-Cohen (Stanford University, USA; Hebrew University of Jerusalem, Israel) @InProceedings{STOC17p2, author = {Tim Roughgarden and Inbal Talgam-Cohen}, title = {Why Prices Need Algorithms (Invited Talk)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {2-1}, doi = {}, year = {2017}, } STOC '17: "Approximate Modularity Revisited ..." Approximate Modularity Revisited Uriel Feige, Michal Feldman, and Inbal Talgam-Cohen (Weizmann Institute of Science, Israel; Microsoft Research, Israel; Tel Aviv University, Israel; Hebrew University of Jerusalem, Israel) @InProceedings{STOC17p1143, author = {Uriel Feige and Michal Feldman and Inbal Talgam-Cohen}, title = {Approximate Modularity Revisited}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1143-1142}, doi = {}, year = {2017}, }
	Ta-Shma, Amnon	STOC '17: "An Efficient Reduction from ..." An Efficient Reduction from Two-Source to Non-malleable Extractors: Achieving Near-Logarithmic Min-entropy Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma (Tel Aviv University, Israel) @InProceedings{STOC17p1325, author = {Avraham Ben-Aroya and Dean Doron and Amnon Ta-Shma}, title = {An Efficient Reduction from Two-Source to Non-malleable Extractors: Achieving Near-Logarithmic Min-entropy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1325-1324}, doi = {}, year = {2017}, } STOC '17: "Explicit, Almost Optimal, ..." Explicit, Almost Optimal, Epsilon-Balanced Codes Amnon Ta-Shma (Tel Aviv University, Israel) @InProceedings{STOC17p261, author = {Amnon Ta-Shma}, title = {Explicit, Almost Optimal, Epsilon-Balanced Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {261-260}, doi = {}, year = {2017}, }
	Thierauf, Thomas	STOC '17: "Linear Matroid Intersection ..." Linear Matroid Intersection Is in Quasi-NC Rohit Gurjar and Thomas Thierauf (Tel Aviv University, Israel; Aalen University, Germany) @InProceedings{STOC17p905, author = {Rohit Gurjar and Thomas Thierauf}, title = {Linear Matroid Intersection Is in Quasi-NC}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {905-904}, doi = {}, year = {2017}, }
	Touchette, Dave	STOC '17: "Exponential Separation of ..." Exponential Separation of Quantum Communication and Classical Information Anurag Anshu, Dave Touchette, Penghui Yao, and Nengkun Yu (National University of Singapore, Singapore; University of Waterloo, Canada; Perimeter Institute for Theoretical Physics, Canada; University of Maryland, USA; University of Technology Sydney, Australia) @InProceedings{STOC17p303, author = {Anurag Anshu and Dave Touchette and Penghui Yao and Nengkun Yu}, title = {Exponential Separation of Quantum Communication and Classical Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {303-302}, doi = {}, year = {2017}, }
	Umans, Chris	STOC '17: "Targeted Pseudorandom Generators, ..." Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace William M. Hoza and Chris Umans (University of Texas at Austin, USA; California Institute of Technology, USA) @InProceedings{STOC17p695, author = {William M. Hoza and Chris Umans}, title = {Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {695-694}, doi = {}, year = {2017}, }
	Valiant, Gregory	STOC '17: "Learning from Untrusted Data ..." Learning from Untrusted Data Moses Charikar, Jacob Steinhardt, and Gregory Valiant (Stanford University, USA) @InProceedings{STOC17p51, author = {Moses Charikar and Jacob Steinhardt and Gregory Valiant}, title = {Learning from Untrusted Data}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {51-50}, doi = {}, year = {2017}, }
	Vasudevan, Prashant Nalini	STOC '17: "Average-Case Fine-Grained ..." Average-Case Fine-Grained Hardness Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan (Columbia University, USA; IDC Herzliya, Israel; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC17p541, author = {Marshall Ball and Alon Rosen and Manuel Sabin and Prashant Nalini Vasudevan}, title = {Average-Case Fine-Grained Hardness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {541-540}, doi = {}, year = {2017}, }
	Vazirani, Vijay V.	STOC '17: "Settling the Complexity of ..." Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod (University of Illinois at Urbana-Champaign, USA; Georgia Institute of Technology, USA) @InProceedings{STOC17p989, author = {Jugal Garg and Ruta Mehta and Vijay V. Vazirani and Sadra Yazdanbod}, title = {Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {989-988}, doi = {}, year = {2017}, }
	Végh, László A.	STOC '17: "A Simpler and Faster Strongly ..." A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization Neil Olver and László A. Végh (VU University Amsterdam, Netherlands; CWI, Netherlands; London School of Economics, UK) @InProceedings{STOC17p107, author = {Neil Olver and László A. Végh}, title = {A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {107-106}, doi = {}, year = {2017}, }
	Vempala, Santosh S.	STOC '17: "Geodesic Walks in Polytopes ..." Geodesic Walks in Polytopes Yin Tat Lee and Santosh S. Vempala (Microsoft Research, USA; University of Washington, USA; Georgia Institute of Technology, USA) @InProceedings{STOC17p1031, author = {Yin Tat Lee and Santosh S. Vempala}, title = {Geodesic Walks in Polytopes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1031-1030}, doi = {}, year = {2017}, }
	Venkitasubramaniam, Muthuramakrishnan	STOC '17: "Equivocating Yao: Constant-Round ..." Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model Ran Canetti, Oxana Poburinnaya, and Muthuramakrishnan Venkitasubramaniam (Boston University, USA; Tel Aviv University, Israel; University of Rochester, USA) @InProceedings{STOC17p555, author = {Ran Canetti and Oxana Poburinnaya and Muthuramakrishnan Venkitasubramaniam}, title = {Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {555-554}, doi = {}, year = {2017}, }
	Vidick, Thomas	STOC '17: "A Quantum Linearity Test for ..." A Quantum Linearity Test for Robustly Verifying Entanglement Anand Natarajan and Thomas Vidick (Massachusetts Institute of Technology, USA; California Institute of Technology, USA) @InProceedings{STOC17p1115, author = {Anand Natarajan and Thomas Vidick}, title = {A Quantum Linearity Test for Robustly Verifying Entanglement}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1115-1114}, doi = {}, year = {2017}, } STOC '17: "Hardness Amplification for ..." Hardness Amplification for Entangled Games via Anchoring Mohammad Bavarian, Thomas Vidick, and Henry Yuen (Massachusetts Institute of Technology, USA; California Institute of Technology, USA; University of California at Berkeley, USA) @InProceedings{STOC17p331, author = {Mohammad Bavarian and Thomas Vidick and Henry Yuen}, title = {Hardness Amplification for Entangled Games via Anchoring}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {331-330}, doi = {}, year = {2017}, }
	Vishnoi, Nisheeth K.	STOC '17: "Real Stable Polynomials and ..." Real Stable Polynomials and Matroids: Optimization and Counting Damian Straszak and Nisheeth K. Vishnoi (EPFL, Switzerland) @InProceedings{STOC17p401, author = {Damian Straszak and Nisheeth K. Vishnoi}, title = {Real Stable Polynomials and Matroids: Optimization and Counting}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {401-400}, doi = {}, year = {2017}, }
	Vladu, Adrian	STOC '17: "Almost-Linear-Time Algorithms ..." Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu (Massachusetts Institute of Technology, USA; Georgia Institute of Technology, USA; Stanford University, USA) @InProceedings{STOC17p443, author = {Michael B. Cohen and Jonathan Kelner and John Peebles and Richard Peng and Anup B. Rao and Aaron Sidford and Adrian Vladu}, title = {Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {443-442}, doi = {}, year = {2017}, }
	Volk, Ben Lee	STOC '17: "Succinct Hitting Sets and ..." Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds Michael A. Forbes, Amir Shpilka, and Ben Lee Volk (Simons Institute for the Theory of Computing Berkeley, USA; Tel Aviv University, Israel) @InProceedings{STOC17p723, author = {Michael A. Forbes and Amir Shpilka and Ben Lee Volk}, title = {Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {723-722}, doi = {}, year = {2017}, }
	Vyas, Nikhil	STOC '17: "Faster Space-Efficient Algorithms ..." Faster Space-Efficient Algorithms for Subset Sum and k-Sum Nikhil Bansal, Shashwat Garg, Jesper Nederlof, and Nikhil Vyas (Eindhoven University of Technology, Netherlands; IIT Bombay, India) @InProceedings{STOC17p219, author = {Nikhil Bansal and Shashwat Garg and Jesper Nederlof and Nikhil Vyas}, title = {Faster Space-Efficient Algorithms for Subset Sum and k-Sum}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {219-218}, doi = {}, year = {2017}, }
	Waingarten, Erik	STOC '17: "Approximate Near Neighbors ..." Approximate Near Neighbors for General Symmetric Norms Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten (Columbia University, USA; Northeastern University, USA; University of Toronto, Canada; Massachusetts Institute of Technology, USA) @InProceedings{STOC17p1003, author = {Alexandr Andoni and Huy L. Nguyen and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten}, title = {Approximate Near Neighbors for General Symmetric Norms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1003-1002}, doi = {}, year = {2017}, } STOC '17: "Beyond Talagrand Functions: ..." Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness Xi Chen, Erik Waingarten, and Jinyu Xie (Columbia University, USA) @InProceedings{STOC17p583, author = {Xi Chen and Erik Waingarten and Jinyu Xie}, title = {Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {583-582}, doi = {}, year = {2017}, }
	Wang, Ruosong	STOC '17: "Exponential Separations in ..." Exponential Separations in the Energy Complexity of Leader Election Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, and Wei Zhan (University of Michigan, USA; Tsinghua University, China) @InProceedings{STOC17p849, author = {Yi-Jun Chang and Tsvi Kopelowitz and Seth Pettie and Ruosong Wang and Wei Zhan}, title = {Exponential Separations in the Energy Complexity of Leader Election}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {849-848}, doi = {}, year = {2017}, }
	Wei, Fan	STOC '17: "Local Max-Cut in Smoothed ..." Local Max-Cut in Smoothed Polynomial Time Omer Angel, Sébastien Bubeck, Yuval Peres, and Fan Wei (University of British Columbia, Canada; Microsoft Research, USA; Stanford University, USA) @InProceedings{STOC17p471, author = {Omer Angel and Sébastien Bubeck and Yuval Peres and Fan Wei}, title = {Local Max-Cut in Smoothed Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {471-470}, doi = {}, year = {2017}, }
	Weismantel, Robert	STOC '17: "A Strongly Polynomial Algorithm ..." A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming Stephan Artmann, Robert Weismantel, and Rico Zenklusen (ETH Zurich, Switzerland) @InProceedings{STOC17p1367, author = {Stephan Artmann and Robert Weismantel and Rico Zenklusen}, title = {A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1367-1366}, doi = {}, year = {2017}, }
	Wigderson, Avi	STOC '17: "Algorithmic and Optimization ..." Algorithmic and Optimization Aspects of Brascamp-Lieb Inequalities, via Operator Scaling Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson (Microsoft Research, USA; City College of New York, USA; Princeton University, USA; IAS, USA) @InProceedings{STOC17p429, author = {Ankit Garg and Leonid Gurvits and Rafael Oliveira and Avi Wigderson}, title = {Algorithmic and Optimization Aspects of Brascamp-Lieb Inequalities, via Operator Scaling}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {429-428}, doi = {}, year = {2017}, }
	Williams, Ryan	STOC '17: "Probabilistic Rank and Matrix ..." Probabilistic Rank and Matrix Rigidity Josh Alman and Ryan Williams (Massachusetts Institute of Technology, USA) @InProceedings{STOC17p709, author = {Josh Alman and Ryan Williams}, title = {Probabilistic Rank and Matrix Rigidity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {709-708}, doi = {}, year = {2017}, }
	Witmer, David	STOC '17: "Sum of Squares Lower Bounds ..." Sum of Squares Lower Bounds for Refuting any CSP Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer (Princeton University, USA; IAS, USA; Tokyo Institute of Technology, Japan; Carnegie Mellon University, USA) @InProceedings{STOC17p149, author = {Pravesh K. Kothari and Ryuhei Mori and Ryan O'Donnell and David Witmer}, title = {Sum of Squares Lower Bounds for Refuting any CSP}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {149-148}, doi = {}, year = {2017}, }
	Wong, Sam Chiu-wai	STOC '17: "Subquadratic Submodular Function ..." Subquadratic Submodular Function Minimization Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong (Dartmouth College, USA; Microsoft Research, USA; Stanford University, USA; University of California at Berkeley, USA) @InProceedings{STOC17p1381, author = {Deeparnab Chakrabarty and Yin Tat Lee and Aaron Sidford and Sam Chiu-wai Wong}, title = {Subquadratic Submodular Function Minimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1381-1380}, doi = {}, year = {2017}, }
	Woodruff, David P.	STOC '17: "Low Rank Approximation with ..." Low Rank Approximation with Entrywise ℓ₁-Norm Error Zhao Song, David P. Woodruff, and Peilin Zhong (University of Texas at Austin, USA; IBM Research, USA; Columbia University, USA) @InProceedings{STOC17p765, author = {Zhao Song and David P. Woodruff and Peilin Zhong}, title = {Low Rank Approximation with Entrywise ℓ₁-Norm Error}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {765-764}, doi = {}, year = {2017}, }
	Woods, Damien	STOC '17: "The Non-cooperative Tile Assembly ..." The Non-cooperative Tile Assembly Model Is Not Intrinsically Universal or Capable of Bounded Turing Machine Simulation Pierre-Étienne Meunier and Damien Woods (Inria, France) @InProceedings{STOC17p359, author = {Pierre-Étienne Meunier and Damien Woods}, title = {The Non-cooperative Tile Assembly Model Is Not Intrinsically Universal or Capable of Bounded Turing Machine Simulation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {359-358}, doi = {}, year = {2017}, }
	Wright, John	STOC '17: "Efficient Quantum Tomography ..." Efficient Quantum Tomography II Ryan O'Donnell and John Wright (Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA) @InProceedings{STOC17p1073, author = {Ryan O'Donnell and John Wright}, title = {Efficient Quantum Tomography II}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1073-1072}, doi = {}, year = {2017}, }
	Wulff-Nilsen, Christian	STOC '17: "Fully-Dynamic Minimum Spanning ..." Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time Christian Wulff-Nilsen (University of Copenhagen, Denmark) @InProceedings{STOC17p1269, author = {Christian Wulff-Nilsen}, title = {Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1269-1268}, doi = {}, year = {2017}, }
	Xie, Jinyu	STOC '17: "Beyond Talagrand Functions: ..." Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness Xi Chen, Erik Waingarten, and Jinyu Xie (Columbia University, USA) @InProceedings{STOC17p583, author = {Xi Chen and Erik Waingarten and Jinyu Xie}, title = {Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {583-582}, doi = {}, year = {2017}, }
	Yang, Lin F.	STOC '17: "Streaming Symmetric Norms ..." Streaming Symmetric Norms via Measure Concentration Jarosław Błasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang (Harvard University, USA; Johns Hopkins University, USA; ETH Zurich, Switzerland; Weizmann Institute of Science, Israel) @InProceedings{STOC17p793, author = {Jarosław Błasiok and Vladimir Braverman and Stephen R. Chestnut and Robert Krauthgamer and Lin F. Yang}, title = {Streaming Symmetric Norms via Measure Concentration}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {793-792}, doi = {}, year = {2017}, }
	Yao, Penghui	STOC '17: "Exponential Separation of ..." Exponential Separation of Quantum Communication and Classical Information Anurag Anshu, Dave Touchette, Penghui Yao, and Nengkun Yu (National University of Singapore, Singapore; University of Waterloo, Canada; Perimeter Institute for Theoretical Physics, Canada; University of Maryland, USA; University of Technology Sydney, Australia) @InProceedings{STOC17p303, author = {Anurag Anshu and Dave Touchette and Penghui Yao and Nengkun Yu}, title = {Exponential Separation of Quantum Communication and Classical Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {303-302}, doi = {}, year = {2017}, }
	Yazdanbod, Sadra	STOC '17: "Settling the Complexity of ..." Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod (University of Illinois at Urbana-Champaign, USA; Georgia Institute of Technology, USA) @InProceedings{STOC17p989, author = {Jugal Garg and Ruta Mehta and Vijay V. Vazirani and Sadra Yazdanbod}, title = {Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {989-988}, doi = {}, year = {2017}, }
	Young, Robert	STOC '17: "The Integrality Gap of the ..." The Integrality Gap of the Goemans-Linial SDP Relaxation for Sparsest Cut Is at Least a Constant Multiple of √log n Assaf Naor and Robert Young (Princeton University, USA; New York University, USA) @InProceedings{STOC17p625, author = {Assaf Naor and Robert Young}, title = {The Integrality Gap of the Goemans-Linial SDP Relaxation for Sparsest Cut Is at Least a Constant Multiple of √log n}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {625-624}, doi = {}, year = {2017}, }
	Yu, Huacheng	STOC '17: "DecreaseKeys Are Expensive ..." DecreaseKeys Are Expensive for External Memory Priority Queues Kasper Eenberg, Kasper Green Larsen, and Huacheng Yu (Aarhus University, Denmark; Stanford University, USA) @InProceedings{STOC17p1213, author = {Kasper Eenberg and Kasper Green Larsen and Huacheng Yu}, title = {DecreaseKeys Are Expensive for External Memory Priority Queues}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1213-1212}, doi = {}, year = {2017}, }
	Yu, Nengkun	STOC '17: "Exponential Separation of ..." Exponential Separation of Quantum Communication and Classical Information Anurag Anshu, Dave Touchette, Penghui Yao, and Nengkun Yu (National University of Singapore, Singapore; University of Waterloo, Canada; Perimeter Institute for Theoretical Physics, Canada; University of Maryland, USA; University of Technology Sydney, Australia) @InProceedings{STOC17p303, author = {Anurag Anshu and Dave Touchette and Penghui Yao and Nengkun Yu}, title = {Exponential Separation of Quantum Communication and Classical Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {303-302}, doi = {}, year = {2017}, }
	Yuen, Henry	STOC '17: "Hardness Amplification for ..." Hardness Amplification for Entangled Games via Anchoring Mohammad Bavarian, Thomas Vidick, and Henry Yuen (Massachusetts Institute of Technology, USA; California Institute of Technology, USA; University of California at Berkeley, USA) @InProceedings{STOC17p331, author = {Mohammad Bavarian and Thomas Vidick and Henry Yuen}, title = {Hardness Amplification for Entangled Games via Anchoring}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {331-330}, doi = {}, year = {2017}, }
	Zandieh, Amir	STOC '17: "An Adaptive Sublinear-Time ..." An Adaptive Sublinear-Time Block Sparse Fourier Transform Volkan Cevher, Michael Kapralov, Jonathan Scarlett, and Amir Zandieh (EPFL, Switzerland) @InProceedings{STOC17p779, author = {Volkan Cevher and Michael Kapralov and Jonathan Scarlett and Amir Zandieh}, title = {An Adaptive Sublinear-Time Block Sparse Fourier Transform}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {779-778}, doi = {}, year = {2017}, }
	Zdeborova, Lenka	STOC '17: "Information-Theoretic Thresholds ..." Information-Theoretic Thresholds from the Cavity Method Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborova (Goethe University Frankfurt, Germany; CNRS, France; PSL Research University, France; ENS, France; UPMC, France; University of Birmingham, UK; CEA, France; University of Paris-Saclay, France) @InProceedings{STOC17p163, author = {Amin Coja-Oghlan and Florent Krzakala and Will Perkins and Lenka Zdeborova}, title = {Information-Theoretic Thresholds from the Cavity Method}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {163-162}, doi = {}, year = {2017}, }
	Zenklusen, Rico	STOC '17: "A Strongly Polynomial Algorithm ..." A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming Stephan Artmann, Robert Weismantel, and Rico Zenklusen (ETH Zurich, Switzerland) @InProceedings{STOC17p1367, author = {Stephan Artmann and Robert Weismantel and Rico Zenklusen}, title = {A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1367-1366}, doi = {}, year = {2017}, }
	Zhan, Wei	STOC '17: "Exponential Separations in ..." Exponential Separations in the Energy Complexity of Leader Election Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, and Wei Zhan (University of Michigan, USA; Tsinghua University, China) @InProceedings{STOC17p849, author = {Yi-Jun Chang and Tsvi Kopelowitz and Seth Pettie and Ruosong Wang and Wei Zhan}, title = {Exponential Separations in the Energy Complexity of Leader Election}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {849-848}, doi = {}, year = {2017}, }
	Zhao, Mingfei	STOC '17: "Simple Mechanisms for Subadditive ..." Simple Mechanisms for Subadditive Buyers via Duality Yang Cai and Mingfei Zhao (McGill University, Canada) @InProceedings{STOC17p191, author = {Yang Cai and Mingfei Zhao}, title = {Simple Mechanisms for Subadditive Buyers via Duality}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {191-190}, doi = {}, year = {2017}, }
	Zhong, Peilin	STOC '17: "Low Rank Approximation with ..." Low Rank Approximation with Entrywise ℓ₁-Norm Error Zhao Song, David P. Woodruff, and Peilin Zhong (University of Texas at Austin, USA; IBM Research, USA; Columbia University, USA) @InProceedings{STOC17p765, author = {Zhao Song and David P. Woodruff and Peilin Zhong}, title = {Low Rank Approximation with Entrywise ℓ₁-Norm Error}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {765-764}, doi = {}, year = {2017}, }
	Zimand, Marius	STOC '17: "Kolmogorov Complexity Version ..." Kolmogorov Complexity Version of Slepian-Wolf Coding Marius Zimand (Towson University, USA) @InProceedings{STOC17p23, author = {Marius Zimand}, title = {Kolmogorov Complexity Version of Slepian-Wolf Coding}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {23-22}, doi = {}, year = {2017}, }
	Zohar, Aviv	STOC '17: "Recent Trends in Decentralized ..." Recent Trends in Decentralized Cryptocurrencies (Invited Talk) Aviv Zohar (Hebrew University of Jerusalem, Israel) @InProceedings{STOC17p1, author = {Aviv Zohar}, title = {Recent Trends in Decentralized Cryptocurrencies (Invited Talk)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1-0}, doi = {}, year = {2017}, }