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

Papers

Session 1A
Mon, Jun 19, 11:30 - 12:30, Grand Salon A (Chair: Valerie King)

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

Session 1B
Mon, Jun 19, 11:30 - 12:30, Grand Salon B (Chair: Eric Price)

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

Session 1C
Mon, Jun 19, 11:30 - 12:30, Grand Salon C (Chair: Mohit Singh)

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

Session 2A
Mon, Jun 19, 14:30 - 15:30, Grand Salon A (Chair: Hamed Hatami)

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

Session 2B
Mon, Jun 19, 14:30 - 15:30, Grand Salon B (Chair: Allan Borodin)

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

Session 2C
Mon, Jun 19, 14:30 - 15:30, Grand Salon C (Chair: Nick Harvey)

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)
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)
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)

Session 3: STOC Best Papers
Mon, Jun 19, 16:00 - 17:30, Grand Salon ABC (Chair: Jelani Nelson, Artur Czumaj, Mohit Singh)

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

Session 4A
Tue, Jun 20, 10:20 - 12:00, Grand Salon A (Chair: Pierre McKenzie)

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

Session 4B
Tue, Jun 20, 10:20 - 12:00, Grand Salon B (Chair: Nick Harvey)

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

Session 4C
Tue, Jun 20, 10:20 - 12:00, Grand Salon C (Chair: Jelani Nelson)

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

Session 5A
Tue, Jun 20, 14:00 - 15:20, Grand Salon A (Chair: Russell Impagliazzo)

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)
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)
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)
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)

Session 5B
Tue, Jun 20, 14:00 - 15:20, Grand Salon B (Chair: Artur Czumaj)

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

Session 5C
Tue, Jun 20, 14:00 - 15:20, Grand Salon C (Chair: Allan Borodin)

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

Session 6A
Wed, Jun 21, 10:20 - 12:00, Grand Salon A (Chair: Hamed Hatami)

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

Session 6B
Wed, Jun 21, 10:20 - 12:00, Grand Salon B (Chair: Aleksander Mądry)

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

Session 6C
Wed, Jun 21, 10:20 - 12:00, Grand Salon C (Chair: Valerie King)

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

Session 7A
Wed, Jun 21, 14:00 - 15:20, Grand Salon A (Chair: Russell Impagliazzo)

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

Session 7B
Wed, Jun 21, 14:00 - 15:20, Grand Salon B (Chair: Artur Czumaj)

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

Session 7C
Wed, Jun 21, 14:00 - 15:20, Grand Salon C (Chair: Jelani Nelson)

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

Session 8: Danny Lewin Prize STOC Best Student Paper
Wed, Jun 21, 15:50 - 16:15, Grand Salon ABC (Chair: Russell Impagliazzo)

Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph
Pasin Manurangsi
(University of California at Berkeley, USA)

Session 9A
Thu, Jun 22, 10:20 - 12:00, Grand Salon A (Chair: Aleksander Mądry)

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

Session 9B
Thu, Jun 22, 10:20 - 12:00, Grand Salon B (Chair: Eric Price)

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

Session 9C
Thu, Jun 22, 10:20 - 12:00, Grand Salon C (Chair: Valerie King)

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

Session 10A
Thu, Jun 22, 14:00 - 15:20, Grand Salon A (Chair: Russell Impagliazzo)

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

Session 10B
Thu, Jun 22, 14:00 - 15:20, Grand Salon B (Chair: Mohit Singh)

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

Session 10C
Thu, Jun 22, 14:00 - 15:20, Grand Salon C (Chair: Pierre McKenzie)

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

proc time: 0.89