STOC 2017
49th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2017)
Powered by
Conference Publishing Consulting

49th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2017), June 19–23, 2017, Montreal, Canada

STOC 2017 – Proceedings

Contents - Abstracts - Authors

Frontmatter

Title Page
Message from the Chairs
STOC 2017 Conference Organization
Sponsors

Invited Talks

Recent Trends in Decentralized Cryptocurrencies (Invited Talk)
Aviv Zohar
(Hebrew University of Jerusalem, Israel)
Publisher's Version Article Search
Why Prices Need Algorithms (Invited Talk)
Tim Roughgarden and Inbal Talgam-Cohen
(Stanford University, USA; Hebrew University of Jerusalem, Israel)
Publisher's Version Article Search
Optimizing Tree Pattern Queries: Why Cutting Is Not Enough (Invited Talk)
Wim Martens
(University of Bayreuth, Germany)
Publisher's Version Article Search
Answering FAQs in CSPs, Probabilistic Graphical Models, Databases, Logic and Matrix Operations (Invited Talk)
Atri Rudra
(SUNY Buffalo, USA)
Publisher's Version Article Search
Fast Convergence of Learning in Games (Invited Talk)
Vasilis Syrgkanis
(Microsoft Research, USA)
Publisher's Version Article Search
Examining Classical Graph-Theory Problems from the Viewpoint of Formal-Verification Methods (Invited Talk)
Orna Kupferman
(Hebrew University of Jerusalem, Israel)
Publisher's Version Article Search
The Next 700 Network Programming Languages (Invited Talk)
Nate Foster
(Cornell University, USA)
Publisher's Version Article Search
Practical Post-quantum Key Agreement from Generic Lattices (Invited Talk)
Valeria Nikolaenko
(Stanford University, USA)
Publisher's Version Article Search

Papers

Session 1A

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)
Publisher's Version Article Search
Kolmogorov Complexity Version of Slepian-Wolf Coding
Marius Zimand
(Towson University, USA)
Publisher's Version Article Search
Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
Bernhard Haeupler and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA)
Publisher's Version Article Search

Session 1B

Learning from Untrusted Data
Moses Charikar, Jacob Steinhardt, and Gregory Valiant
(Stanford University, USA)
Publisher's Version Article Search
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)
Publisher's Version Article Search
Kernel-Based Methods for Bandit Convex Optimization
Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan
(Microsoft Research, USA; Weizmann Institute of Science, Israel)
Publisher's Version Article Search Video Info

Session 1C

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)
Publisher's Version Article Search
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)
Publisher's Version Article Search
Finding Even Cycles Faster via Capped k-Walks
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Morten Stöckel
(University of Copenhagen, Denmark)
Publisher's Version Article Search

Session 2A

Strongly Refuting Random CSPs Below the Spectral Threshold
Prasad Raghavendra, Satish Rao, and Tselil Schramm
(University of California at Berkeley, USA)
Publisher's Version Article Search
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)
Publisher's Version Article Search Info
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)
Publisher's Version Article Search

Session 2B

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)
Publisher's Version Article Search
Simple Mechanisms for Subadditive Buyers via Duality
Yang Cai and Mingfei Zhao
(McGill University, Canada)
Publisher's Version Article Search
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)
Publisher's Version Article Search

Session 2C

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)
Publisher's Version Article Search
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)
Publisher's Version Article Search
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)
Publisher's Version Article Search

Session 3: STOC Best Papers

Explicit, Almost Optimal, Epsilon-Balanced Codes
Amnon Ta-Shma
(Tel Aviv University, Israel)
Publisher's Version Article Search
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)
Publisher's Version Article Search
A Weighted Linear Matroid Parity Algorithm
Satoru Iwata and Yusuke Kobayashi
(University of Tokyo, Japan; University of Tsukuba, Japan)
Publisher's Version Article Search

Session 4A

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)
Publisher's Version Article Search
Compression of Quantum Multi-prover Interactive Proofs
Zhengfeng Ji
(University of Technology Sydney, Australia)
Publisher's Version Article Search
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)
Publisher's Version Article Search
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)
Publisher's Version Article Search
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)
Publisher's Version Article Search

Session 4B

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)
Publisher's Version Article Search
Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models
Ankur Moitra
(Massachusetts Institute of Technology, USA)
Publisher's Version Article Search
Real Stable Polynomials and Matroids: Optimization and Counting
Damian Straszak and Nisheeth K. Vishnoi
(EPFL, Switzerland)
Publisher's Version Article Search
A Generalization of Permanent Inequalities and Applications in Counting and Optimization
Nima Anari and Shayan Oveis Gharan
(Stanford University, USA; University of Washington, USA)
Publisher's Version Article Search
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)
Publisher's Version Article Search

Session 4C

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)
Publisher's Version Article Search
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)
Publisher's Version Article Search
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)
Publisher's Version Article Search
Algorithms for Stable and Perturbation-Resilient Problems
Haris Angelidakis, Konstantin Makarychev, and Yury Makarychev
(Toyota Technological Institute at Chicago, USA; Northwestern University, USA)
Publisher's Version Article Search
Area-Convexity, ℓ Regularization, and Undirected Multicommodity Flow
Jonah Sherman
(University of California at Berkeley, USA)
Publisher's Version Article Search

Session 5A

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)
Publisher's Version Article Search
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)
Publisher's Version Article Search
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)
Publisher's Version Article Search
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)
Publisher's Version Article Search Info

Session 5B

Removal Lemmas with Polynomial Bounds
Lior Gishboliner and Asaf Shapira
(Tel Aviv University, Israel)
Publisher's Version Article Search
Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness
Xi Chen, Erik Waingarten, and Jinyu Xie
(Columbia University, USA)
Publisher's Version Article Search
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)
Publisher's Version Article Search
Online Service with Delay
Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi
(Tel Aviv University, Israel; Duke University, USA)
Publisher's Version Article Search

Session 5C

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)
Publisher's Version Article Search
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)
Publisher's Version Article Search
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)
Publisher's Version Article Search
How Well Do Local Algorithms Solve Semidefinite Programs?
Zhou Fan and Andrea Montanari
(Stanford University, USA)
Publisher's Version Article Search

Session 6A

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)
Publisher's Version Article Search
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)
Publisher's Version Article Search
Probabilistic Rank and Matrix Rigidity
Josh Alman and Ryan Williams
(Massachusetts Institute of Technology, USA)
Publisher's Version Article Search
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)
Publisher's Version Article Search
Pseudodeterministic Constructions in Subexponential Time
Igor C. Oliveira and Rahul Santhanam
(Charles University in Prague, Czechia; University of Oxford, UK)
Publisher's Version Article Search

Session 6B

An SDP-Based Algorithm for Linear-Sized Spectral Sparsification
Yin Tat Lee and He Sun
(Microsoft Research, USA; University of Bristol, UK)
Publisher's Version Article Search
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)
Publisher's Version Article Search Info
An Adaptive Sublinear-Time Block Sparse Fourier Transform
Volkan Cevher, Michael Kapralov, Jonathan Scarlett, and Amir Zandieh
(EPFL, Switzerland)
Publisher's Version Article Search
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)
Publisher's Version Article Search
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)
Publisher's Version Article Search Info

Session 6C

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)
Publisher's Version Article Search
Distributed Exact Shortest Paths in Sublinear Time
Michael Elkin
(Ben-Gurion University of the Negev, Israel)
Publisher's Version Article Search
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)
Publisher's Version Article Search
On the Complexity of Local Distributed Graph Problems
Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus
(ETH Zurich, Switzerland; University of Freiburg, Germany)
Publisher's Version Article Search
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)
Publisher's Version Article Search

Session 7A

Complexity of Short Presburger Arithmetic
Danny Nguyen and Igor Pak
(University of California at Los Angeles, USA)
Publisher's Version Article Search
Linear Matroid Intersection Is in Quasi-NC
Rohit Gurjar and Thomas Thierauf
(Tel Aviv University, Israel; Aalen University, Germany)
Publisher's Version Article Search
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)
Publisher's Version Article Search
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)
Publisher's Version Article Search

Session 7B

Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments
Yannai A. Gonczarowski and Noam Nisan
(Hebrew University of Jerusalem, Israel; Microsoft Research, Israel)
Publisher's Version Article Search
The Menu-Size Complexity of Revenue Approximation
Moshe Babaioff, Yannai A. Gonczarowski, and Noam Nisan
(Microsoft Research, Israel; Hebrew University of Jerusalem, Israel)
Publisher's Version Article Search
Communication Complexity of Approximate Nash Equilibria
Yakov Babichenko and Aviad Rubinstein
(Technion, Israel; University of California at Berkeley, USA)
Publisher's Version Article Search
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)
Publisher's Version Article Search

Session 7C

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)
Publisher's Version Article Search
Algorithmic Discrepancy Beyond Partial Coloring
Nikhil Bansal and Shashwat Garg
(Eindhoven University of Technology, Netherlands)
Publisher's Version Article Search
Geodesic Walks in Polytopes
Yin Tat Lee and Santosh S. Vempala
(Microsoft Research, USA; University of Washington, USA; Georgia Institute of Technology, USA)
Publisher's Version Article Search
A Reverse Minkowski Theorem
Oded Regev and Noah Stephens-Davidowitz
(New York University, USA)
Publisher's Version Article Search

Session 8: Danny Lewin Prize STOC Best Student Paper

Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph
Pasin Manurangsi
(University of California at Berkeley, USA)
Publisher's Version Article Search

Session 9A

Efficient Quantum Tomography II
Ryan O'Donnell and John Wright
(Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version Article Search
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)
Publisher's Version Article Search
Quantum Algorithm for Tree Size Estimation, with Applications to Backtracking and 2-Player Games
Andris Ambainis and Martins Kokainis
(University of Latvia, Latvia)
Publisher's Version Article Search
A Quantum Linearity Test for Robustly Verifying Entanglement
Anand Natarajan and Thomas Vidick
(Massachusetts Institute of Technology, USA; California Institute of Technology, USA)
Publisher's Version Article Search

Session 9B

The Limitations of Optimization from Samples
Eric Balkanski, Aviad Rubinstein, and Yaron Singer
(Harvard University, USA; University of California at Berkeley, USA)
Publisher's Version Article Search
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)
Publisher's Version Article Search
Trace Reconstruction with exp(O(n1/3)) Samples
Fedor Nazarov and Yuval Peres
(Kent State University, USA; Microsoft Research, USA)
Publisher's Version Article Search
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)
Publisher's Version Article Search
Provable Learning of Noisy-or Networks
Sanjeev Arora, Rong Ge, Tengyu Ma, and Andrej Risteski
(Princeton University, USA; Duke University, USA)
Publisher's Version Article Search
Time-Space Hardness of Learning Sparse Parities
Gillat Kol, Ran Raz, and Avishay Tal
(Princeton University, USA; IAS, USA)
Publisher's Version Article Search

Session 9C

DecreaseKeys Are Expensive for External Memory Priority Queues
Kasper Eenberg, Kasper Green Larsen, and Huacheng Yu
(Aarhus University, Denmark; Stanford University, USA)
Publisher's Version Article Search
Set Similarity Search Beyond MinHash
Tobias Christiani and Rasmus Pagh
(IT University of Copenhagen, Denmark)
Publisher's Version Article Search
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)
Publisher's Version Article Search
Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n1/2 - ε)-Time
Danupon Nanongkai and Thatchaphol Saranurak
(KTH, Sweden)
Publisher's Version Article Search
Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time
Christian Wulff-Nilsen
(University of Copenhagen, Denmark)
Publisher's Version Article Search

Session 10A

Improved Non-malleable Extractors, Non-malleable Codes and Independent Source Extractors
Xin Li
(Johns Hopkins University, USA)
Publisher's Version Article Search
Towards Optimal Two-Source Extractors and Ramsey Graphs
Gil Cohen
(Princeton University, USA)
Publisher's Version Article Search
Non-malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions
Eshan Chattopadhyay and Xin Li
(IAS, USA; Johns Hopkins University, USA)
Publisher's Version Article Search Video
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)
Publisher's Version Article Search

Session 10B

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)
Publisher's Version Article Search
Katyusha: The First Direct Acceleration of Stochastic Gradient Methods
Zeyuan Allen-Zhu
(IAS, USA; Princeton University, USA)
Publisher's Version Article Search
A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming
Stephan Artmann, Robert Weismantel, and Rico Zenklusen
(ETH Zurich, Switzerland)
Publisher's Version Article Search
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)
Publisher's Version Article Search

Session 10C

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)
Publisher's Version Article Search
Strongly Exponential Lower Bounds for Monotone Computation
Toniann Pitassi and Robert Robere
(University of Toronto, Canada)
Publisher's Version Article Search
Formula Lower Bounds via the Quantum Method
Avishay Tal
(IAS, USA)
Publisher's Version Article Search

proc time: 1.79