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}, } Article: stoc17main-main233-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main359-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main289-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main289-p (type: Full Paper) doi: 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}, } Article: stoc17main-main216-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main367-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main200-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main299-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main83-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main17-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main371-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main11-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main365-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main328-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main192-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main339-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main117-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main33-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main32-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main291-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main398-p (type: Full Paper) doi: 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}, } Article: stoc17main-main293-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main382-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main160-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main101-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main107-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main233-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main436-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main107-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main17-p (type: Full Paper) doi: 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}, } Article: stoc17main-main18-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main289-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main27-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main290-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main36-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main426-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main282-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main84-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main362-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main405-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main366-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main251-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main115-p (type: Full Paper) doi: 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}, } Article: stoc17main-main280-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main107-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main196-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main54-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main128-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main284-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main87-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main457-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main99-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main278-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main220-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main457-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main251-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main101-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main409-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main442-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main179-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main359-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main18-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main224-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main359-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main221-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main351-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main351-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main99-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main434-p (type: Full Paper) doi:
	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}, } Article: stoc17key-key7-p (type: Invited Talk Abstract (1 page)) doi:
	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}, } Article: stoc17main-main27-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main99-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main339-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main276-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main331-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main398-p (type: Full Paper) doi: 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}, } Article: stoc17main-main293-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main365-p (type: Full Paper) doi: 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}, } Article: stoc17main-main339-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main305-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main299-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main19-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main118-p (type: Full Paper) doi: 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}, } Article: stoc17main-main117-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main202-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main53-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main419-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main186-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main276-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main437-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main359-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main409-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main289-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main436-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main251-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main67-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main279-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main360-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main177-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main36-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main53-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main189-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main192-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main304-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main436-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main304-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main282-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main360-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main251-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main284-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main147-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main36-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main54-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main409-p (type: Full Paper) doi: 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}, } Article: stoc17main-main359-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main278-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main177-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main200-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main133-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main362-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main382-p (type: Full Paper) doi: 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}, } Article: stoc17main-main368-p (type: Full Paper) doi: 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}, } Article: stoc17main-main180-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main107-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main419-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main87-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main305-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main419-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main233-p (type: Full Paper) doi:
	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}, } Article: stoc17key-key3-p (type: Invited Talk Abstract (1 page)) doi:
	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}, } Article: stoc17main-main442-p (type: Full Paper) doi:
	Łą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}, } Article: stoc17main-main360-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main202-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main179-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main77-p (type: Full Paper) doi: 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}, } Article: stoc17main-main84-p (type: Full Paper) doi: 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}, } Article: stoc17main-main354-p (type: Full Paper) doi: 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}, } Article: stoc17main-main18-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main36-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main370-p (type: Full Paper) doi: 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}, } Article: stoc17main-main366-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main53-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main268-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main304-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main359-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main365-p (type: Full Paper) doi: 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}, } Article: stoc17main-main289-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main371-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main371-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main60-p (type: Full Paper) doi:
	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}, } Article: stoc17key-key4-p (type: Invited Talk Abstract (1 page)) doi:
	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}, } Article: stoc17main-main251-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main457-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main305-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main233-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main331-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main180-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main203-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main147-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main123-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main221-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main99-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main368-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main279-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main192-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main212-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main66-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main294-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main422-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main293-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main170-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main83-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main409-p (type: Full Paper) doi:
	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}, } Article: stoc17key-key6-p (type: Invited Talk Abstract (1 page)) doi:
	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}, } Article: stoc17main-main83-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main54-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main118-p (type: Full Paper) doi: 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}, } Article: stoc17main-main117-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main241-p (type: Full Paper) doi: 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}, } Article: stoc17main-main220-p (type: Full Paper) doi: 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}, } Article: stoc17main-main368-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main115-p (type: Full Paper) doi: 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}, } Article: stoc17main-main449-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main276-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main181-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main196-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main170-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main218-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main419-p (type: Full Paper) doi: 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}, } Article: stoc17main-main339-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main268-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main284-p (type: Full Paper) doi: 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}, } Article: stoc17main-main442-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main383-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main284-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main422-p (type: Full Paper) doi: 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}, } Article: stoc17main-main17-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main87-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main362-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main358-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main426-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main78-p (type: Full Paper) doi: 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}, } Article: stoc17main-main180-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main192-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main268-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main284-p (type: Full Paper) doi: 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}, } Article: stoc17main-main442-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main78-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main133-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main83-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main161-p (type: Full Paper) doi: 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}, } Article: stoc17main-main383-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main365-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main358-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main218-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main291-p (type: Full Paper) doi:
	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}, } Article: stoc17key-key5-p (type: Invited Talk Abstract (1 page)) doi:
	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}, } Article: stoc17main-main32-p (type: Full Paper) doi: 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}, } Article: stoc17main-main33-p (type: Full Paper) doi:
	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}, } Article: stoc17key-key1-p (type: Invited Talk Abstract (1 page)) doi:
	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}, } Article: stoc17main-main291-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main442-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main147-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main360-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main449-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main212-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main268-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main282-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main78-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main218-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main220-p (type: Full Paper) doi: 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}, } Article: stoc17main-main115-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main437-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main19-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main450-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main434-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main84-p (type: Full Paper) doi: 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}, } Article: stoc17main-main284-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main32-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main251-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main142-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main405-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main36-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main161-p (type: Full Paper) doi: 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}, } Article: stoc17main-main383-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main382-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main278-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main272-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main354-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main279-p (type: Full Paper) doi:
	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}, } Article: stoc17key-key8-p (type: Invited Talk Abstract (1 page)) doi:
	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}, } Article: stoc17main-main133-p (type: Full Paper) doi: 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}, } Article: stoc17main-main309-p (type: Full Paper) doi:
	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}, } Article: stoc17key-key5-p (type: Invited Talk Abstract (1 page)) doi: 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}, } Article: stoc17main-main351-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main101-p (type: Full Paper) doi: 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}, } Article: stoc17main-main34-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main186-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main11-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main67-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main405-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main291-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main331-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main181-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main77-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main426-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main294-p (type: Full Paper) doi: 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}, } Article: stoc17main-main160-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main272-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main284-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main434-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main293-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main83-p (type: Full Paper) doi: 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}, } Article: stoc17main-main280-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main362-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main17-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main328-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main276-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main367-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main368-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main84-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main142-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main203-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main241-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main76-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main280-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main107-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main11-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main331-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main66-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main179-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main11-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main160-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main282-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main87-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main328-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main362-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main290-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main142-p (type: Full Paper) doi:
	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}, } Article: stoc17main-main92-p (type: Full Paper) doi:
	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}, } Article: stoc17key-key2-p (type: Invited Talk Abstract (1 page)) doi: