STOC 2020
52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020)
Powered by
Conference Publishing Consulting

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), June 22–26, 2020, Chicago, IL, USA

STOC 2020 – Preliminary Table of Contents

Contents - Abstracts - Authors

Frontmatter

Title Page
Message from the Chairs
Committees
Sponsors

Papers

Concentration on the Boolean Hypercube via Pathwise Stochastic Analysis
Ronen Eldan and Renan Gross
(Weizmann Institute of Science, Israel)
Article Search
Explicit Near-Ramanujan Graphs of Every Degree
Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes
(University of California at Berkeley, USA; Carnegie Mellon University, USA)
Article Search
QCSP Monsters and the Demise of the Chen Conjecture
Dmitriy Zhuk and Barnaby Martin
(Lomonosov Moscow State University, Russia; Durham University, UK)
Article Search
An Improved Approximation Algorithm for ATSP
Vera Traub and Jens Vygen
(University of Bonn, Germany)
Article Search
Improved Bounds for the Sunflower Lemma
Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang
(Princeton University, USA; University of California at San Diego, USA; Peking University, China; Harvard University, USA)
Article Search
Three-in-a-Tree in Near Linear Time
Kai-Yuan Lai, Hsueh-I Lu, and Mikkel Thorup
(National Taiwan University, Taiwan; University of Copenhagen, Denmark)
Article Search
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
Maximilian Probst, Virginia Vassilevska Williams, and Nicole Wein
(University of Copenhagen, Denmark; Massachusetts Institute of Technology, USA)
Article Search
How to Lose at Monte Carlo: A Simple Dynamical System Whose Typical Statistical Behavior Is Non-computable
Cristobal Rojas and Michael Yampolsky
(Andrés Bello National University, Chile; University of Toronto, Canada)
Article Search
Approximately Stable Committee Selection
Zhihao Jiang, Kamesh Munagala, and Kangning Wang
(Tsinghua University, China; Duke University, USA)
Article Search
Testing Noisy Linear Functions for Sparsity
Xue Chen, Anindya De, and Rocco A. Servedio
(Northwestern University, USA; University of Pennsylvania, USA; Columbia University, USA)
Article Search
Dynamic Algorithms for LIS and Distance to Monotonicity
Michael Mitzenmacher and Saeed Seddighin
(Harvard University, USA)
Article Search
Decision List Compression by Mild Random Restrictions
Shachar Lovett, Kewen Wu, and Jiapeng Zhang
(University of California at San Diego, USA; Peking University, China; Harvard University, USA)
Article Search
XOR Lemmas for Resilient Functions against Polynomials
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman
(Cornell University, USA; Ohio State University, USA; Carnegie Mellon University, USA; University of California at San Diego, USA; University of Texas at Austin, USA)
Article Search
Bare Quantum Simultaneity versus Classical Interactivity in Communication Complexity
Dmitry Gavinsky
(Czech Academy of Sciences, Czechia)
Article Search
Improved Bounds for Perfect Sampling of k-Colorings in Graphs
Siddharth Bhandari and Sayantan Chakraborty
(Tata Institute of Fundamental Research, India)
Article Search
Semi-algebraic Proofs, IPS Lower Bounds, and the τ-Conjecture: Can a Natural Number Be Negative?
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, and Iddo Tzameret
(Steklov Institute of Mathematics at St. Petersburg, Russia; St. Petersburg State University, Russia; CNRS, France; University of Lille, France; Royal Holloway University of London, UK)
Article Search
No-Signaling Proofs with O(sqrt(log n)) Provers Is in PSPACE
Dhiraj Holden and Yael Tauman Kalai
(Massachusetts Institute of Technology, USA; Microsoft Research, n.n.)
Article Search
Faster Energy Maximization for Faster Maximum Flow
Yang P. Liu and Aaron Sidford
(Stanford University, USA)
Article Search
Automating Cutting Planes Is NP-Hard
Mika Goos, Sajin Koroth, Ian Mertz, and Toniann Pitassi
(Stanford University, USA; Simon Fraser University, Canada; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)
Article Search
Fully-Dynamic Planarity Testing in Polylogarithmic Time
Jacob Holm and Eva Rotenberg
(University of Copenhagen, Denmark; DTU, Denmark)
Article Search
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
Daniel Lokshtanov, Pranabendu Misra, Michał Pilipczuk, Saket Saurabh, and Meirav Zehavi
(University of California at Santa Barbara, USA; Max Planck Institute for Informatics, Germany; University of Warsaw, Poland; Institute of Mathematical Sciences at Chennai, India; Ben-Gurion University of the Negev, Israel)
Article Search
Unexpected Hardness Results for Kolmogorov Complexity under Uniform Reductions
Shuichi Hirahara
(National Institute of Informatics, Japan)
Article Search
Quadratic Speedup for Finding Marked Vertices by Quantum WSalks
Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis
(University of Latvia, Latvia; California Institute of Technology, USA; CWI, Netherlands)
Article Search
Distance Sensitivity Oracles with Subcubic Preprocessing Time and Fast Query Time
Sarel Cohen and Shiri Chechik
(Tel Aviv University, Israel)
Article Search
AND Testing and Robust Judgement Aggregation
Yuval Filmus, Noam Lifshitz, Dor Minzer, and Elchanan Mossel
(Technion, Israel; Hebrew University of Jerusalem, Israel; Institute of Advanced Study, n.n.; Massachusetts Institute of Technology, USA)
Article Search
Fast Sampling and Counting k-SAT Solutions in the Local Lemma Regime
Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang
(Nanjing University, China; University of Edinburgh, UK; Shanghai Jiao Tong University, China)
Article Search
Reducing Path TSP to TSP
Vera Traub, Jens Vygen, and Rico Zenklusen
(University of Bonn, Germany; ETH Zurich, Switzerland)
Article Search
Implementing Geometric Complexity Theory: On the Separation of Orbit Closures via Symmetries
Christian Ikenmeyer and Umangathan Kandasamy
(University of Liverpool, UK; Saarland University, Germany)
Article Search
Rounding Dynamic Matchings against an Adaptive Adversary
David Wajc
(Carnegie Mellon University, USA)
Article Search
Fast Hashing with Strong Concentration Bounds
Anders Aamand, Jakob Bæk Tejs Knudsen, Mathias Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen, and Mikkel Thorup
(University of Copenhagen, Denmark; SupWiz, n.n.)
Article Search
Lower Bound for Succinct Range Minimum Query
Mingmou Liu and Huacheng Yu
(Nanjing University, China; Princeton University, USA)
Article Search
Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time
Jesper Nederlof
(Utrecht University, Netherlands)
Article Search
Optimally Resilient Codes for List-Decoding from Insertions and Deletions
Venkatesan Guruswami, Bernhard Haeupler, and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA)
Article Search
The Program-Size Complexity of Self-Assembled Paths
Pierre-Étienne Meunier, Damien Regnault, and Damien Woods
(Maynooth University, Irland; University of Évry, France; University of Paris-Saclay, France)
Article Search
Bipartite TSP in O(1.9999^n) Time, Assuming Quadratic Time Matrix Multiplication
Jesper Nederlof
(Utrecht University, Netherlands)
Article Search
Towards a Better Understanding of Randomized Greedy Matching
Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang
(Shanghai University of Finance and Economics, China; University of Vienna, Austria; University of Hong Kong, China)
Article Search
Approximating Text-to-Pattern Hamming Distances
Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat
(University of Illinois at Urbana-Champaign, USA; Bar-Ilan University, Israel)
Article Search
Separating the Communication Complexity of Truthful and Non-truthful Combinatorial Auctions
Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, and S. Matthew Weinberg
(Rutgers University, USA; Princeton University, USA)
Article Search
Faster Parallel Algorithm for Approximate Shortest Path
Jason Li
(Carnegie Mellon University, USA)
Article Search
Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
Matthew Coudron and Sanketh Menda
(University of Waterloo, Canada; University of Maryland, USA; NIST, n.n.)
Article Search
Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths
Nairen Cao, Jeremy T. Fineman, and Katina Russell
(Georgetown University, USA)
Article Search
Efficient Sampling and Counting Algorithms for the Potts Model on \mathbb Z^d at all Temperatures
Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, and Prasad Tetali
(Microsoft Research, n.n.; University of Bristol, UK; University of Illinois at Chicago, USA; Georgia Institute of Technology, USA)
Article Search
Strong Self-Concordance and Sampling
Aditi Laddha, Yin Tat Lee, and Santosh Vempala
(Georgia Institute of Technology, USA; University of Washington, USA)
Article Search
An Improved Approximation Algorithm for TSP in the Half Integral Case
Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan
(University of Washington, USA)
Article Search
Nearly Optimal Static Las Vegas Succinct Dictionary
Huacheng Yu
(Princeton University, USA)
Article Search
All Non-trivial Variants of 3-LDT Are Equivalent
Bartłomiej Dudek, Paweł Gawrychowski, and Tatiana Starikovskaya
(University of Wrocław, Poland; Ecole Normale Superieure, n.n.)
Article Search
The Impossibility of Efficient Quantum Weak Coin Flipping
Carl A. Miller
(NIST, n.n.; University of Maryland, USA)
Article Search
Caching with Time Windows
Anupam Gupta, Amit Kumar, and Debmalya Panigrahi
(Carnegie Mellon University, USA; IIT Delhi, India; Duke University, USA)
Article Search
Separations and Equivalences between Turnstile Streaming and Linear Sketching
John Kallaugher and Eric Price
(University of Texas at Austin, USA)
Article Search
Strong Average-Case Lower Bounds from Non-trivial Derandomization
Lijie Chen and Hanlin Ren
(Massachusetts Institute of Technology, USA; Tsinghua University, China)
Article Search
Online Vector Balancing and Geometric Discrepancy
Nikhil Bansal, Haotian Jiang, Sahil Singla, and Makrand Sinha
(Eindhoven University of Technology, Netherlands; CWI, Netherlands; University of Washington, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)
Article Search
Fooling Gaussian PTFs via Local Hyperconcentration
Ryan O'Donnell, Rocco A. Servedio, and Li-Yang Tan
(Carnegie Mellon University, USA; Columbia University, USA; Stanford University, USA)
Article Search
Constant-Factor Approximation of Near-Linear Edit Distance in Near-Linear Time
Joshua Brakensiek and Aviad Rubinstein
(Stanford University, USA)
Article Search
Sharp Threshold Results for Computational Complexity
Lijie Chen, Ce Jin, and R. Ryan Williams
(Massachusetts Institute of Technology, USA; Tsinghua University, China)
Article Search
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games, and Its Applications
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Wong
(University of Washington, USA; Microsoft Research, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)
Article Search
The Karger-Stein Algorithm Is Optimal for k-Cut
Anupam Gupta, Euiwoong Lee, and Jason Li
(Carnegie Mellon University, USA; New York University, USA)
Article Search
The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen
(University of Haifa, Israel; Google Research, Switzerland; EPFL, Switzerland; ETH Zurich, Switzerland)
Article Search
A Lower Bound for Parallel Submodular Minimization
Eric Balkanski and Yaron Singer
(Harvard University, USA)
Article Search
(Semi)Algebraic Proofs over \{\pm 1\} Variables
Dmitry Sokolov
(Lund University, Sweden; University of Copenhagen, Denmark)
Article Search
Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
Rong Ge, Holden Lee, and Jianfeng Lu
(Duke University, USA)
Article Search
Does Learning Require Memorization? A Short Tale about a Long Tail
Vitaly Feldman
(Google Research, n.n.)
Article Search
On the Need for Large Quantum Depth
Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai
(University of Texas at Austin, USA; Academia Sinica, Taiwan; National Chiao Tung University, Taiwan)
Article Search
Entanglement Subvolume Law for 2D Frustration-Free Spin Systems
Anurag Anshu, Itai Arad, and David Gosset
(University of Waterloo, Canada; Technion, Israel)
Article Search
Better Secret Sharing via Robust Conditional Disclosure of Secrets
Benny Applebaum, Amos Beimel, Oded Nir, and Naty Peter
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel)
Article Search
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue
Zhiyi Huang and Qiankun Zhang
(University of Hong Kong, China)
Article Search
Combinatorial List-Decoding of Reed-Solomon Codes beyond the Johnson Radius
Chong Shangguan and Itzhak Tamo
(Tel Aviv University, Israel)
Article Search
Coresets for Clustering in Euclidean Spaces: Importance Sampling Is Nearly Optimal
Lingxiao Huang and Nisheeth K. Vishnoi
(Yale University, USA)
Article Search
The Power of Factorization Mechanisms in Local and Central Differential Privacy
Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman
(University of Toronto, Canada; Northeastern University, USA)
Article Search
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Vaclav Rozhon and Mohsen Ghaffari
(ETH Zurich, Switzerland)
Article Search
On the Nisan-Ronen Conjecture for Submodular Valuations
Giorgos Christodoulou, Elias Koutsoupias, and Annamaria Kovacs
(University of Liverpool, UK; University of Oxford, UK; Goethe University Frankfurt, Germany)
Article Search
Does Preprocessing Help in Fast Sequence Comparisons?
Elazar Goldenberg, Aviad Rubinstein, and Barna Saha
(Academic College of Tel Aviv-Yaffo, Israel; Stanford University, USA; University of California at Berkeley, USA)
Article Search
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
Jarosław Byrka, Fabrizio Grandoni, and Afrouz Jabal Ameli
(University of Wrocław, Poland; IDSIA, Switzerland)
Article Search
On the Computability of Continuous Maximum Entropy Distributions with Applications
Jonathan Leake and Nisheeth K. Vishnoi
(KTH, Sweden; Yale University, USA)
Article Search
Walking Randomly, Massively, and Efficiently
Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(Google Research, USA; Massachusetts Institute of Technology, USA; IBM Research, USA; University of Warsaw, Poland)
Article Search
One-Shot Signatures and Applications to Hybrid Quantum/Classical Authentication
Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry
(Princeton University, USA; City University of New York, USA; University of Edinburgh, UK)
Article Search
Contention Resolution without Collision Detection
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, and Seth Pettie
(Stony Brook University, USA; Bar-Ilan University, Israel; Massachusetts Institute of Technology, USA; University of Michigan, USA)
Article Search
Unbounded Lower Bound for k-Server against Weak Adversaries
Marcin Bienkowski, Jarosław Byrka, Christian Coester, and Łukasz Jez
(University of Wrocław, Poland; CWI, Netherlands)
Article Search
Constant Factor Approximations to Edit Distance on Far Input Pairs in Nearly Linear Time
Michal Koucký and Michael Saks
(Charles University in Prague, Czechia; Rutgers University, USA)
Article Search
Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
Karl Bringmann and Vasileios Nakos
(Max Planck Institute for Informatics, Germany; National Technical University of Athens, Greece)
Article Search
Solving Tall Dense Linear Programs in Nearly Linear Time
Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song
(KTH, Sweden; Microsoft Research, n.n.; Stanford University, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)
Article Search
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut
Amir Abboud, Vincent Cohen-Addad, and Philip N. Klein
(IBM Almaden Research Center, n.n.; CNRS, France; UPMC, France; Brown University, USA)
Article Search
A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization
Wenzheng Li, Paul Liu, and Jan Vondrak
(Stanford University, USA)
Article Search
Optimal Time and Space Leader Election in Population Protocols
Petra Berenbrink, George Giakkoupis, and Peter Kling
(University of Hamburg, Germany; Inria, France)
Article Search
A Spectral Approach to Network Design
Lap Chi Lau and Hong Zhou
(University of Waterloo, Canada)
Article Search
Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang
(University of Texas at Austin, USA; California Institute of Technology, USA; University of Maryland, USA; University of Washington, USA)
Article Search
Interaction Is Necessary for Distributed Learning with Privacy or Communication Constraints
Yuval Dagan and Vitaly Feldman
(Massachusetts Institute of Technology, USA; Google Research, n.n.)
Article Search
Catalytic Approaches to the Tree Evaluation Problem
Ian Mertz and James Cook
(University of Toronto, Canada)
Article Search
Improved Analysis of Higher Order Random Walks and Applications
Vedat Levi Alev and Lap Chi Lau
(University of Waterloo, Canada)
Article Search
Hitting Topological Minors is FPT
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi
(University of Bergen, Norway; University of California at Santa Barbara, USA; IIT Hyderabad, India; IMSc, n.n.; Ben-Gurion University of the Negev, Israel)
Article Search
Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4
Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu
(University of California at Berkeley, USA)
Article Search
Interactive Error Resilience beyond \frac{2}{7}
Klim Efremenko, Gillat Kol, and Raghuvansh R. Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)
Article Search
Parallel Approximate Undirected Shortest Paths via Low Hop Emulators
Alexandr Andoni, Clifford Stein, and Peilin Zhong
(Columbia University, USA)
Article Search
Classical Algorithms, Correlation Decay, and Complex Zeros of Partition Functions of Quantum Many-Body Systems
Aram W. Harrow, Saeed Mehraban, and Mehdi Soleimanifar
(Massachusetts Institute of Technology, USA; California Institute of Technology, USA)
Article Search
Arikan Meets Shannon: Polar Codes with Near-Optimal Convergence to Channel Capacity
Venkatesan Guruswami, Andrii Riazanov, and Min Ye
(Carnegie Mellon University, USA; Tsinghua-Berkeley Shenzhen Institute, USA)
Article Search
Post-quantum Zero Knowledge in Constant Rounds
Omri Shmueli and Nir Bitansky
(Tel Aviv University, Israel)
Article Search
Smoothed Complexity of Local Max-Cut and Binary Max-CSP
Emmanouil-Vasileios Vlatakis-Gkaragkounis, Xi Chen, Chenghao Guo, Mihalis Yannakakis, and Xinzhi Zhang
(Columbia University, USA; Tsinghua University, China)
Article Search
A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix
Daniel Dadush, Sophie Huiberts, Bento Natura, and László A. Végh
(CWI, Netherlands; London School of Economics and Political Science, UK)
Article Search
Near-Optimal Fully Dynamic Densest Subgraph
Saurabh Sawlani and Junxing Wang
(Georgia Institute of Technology, USA; Carnegie Mellon University, USA)
Article Search
A Robust Version of Hegedus's Lemma, with Applications
Srikanth Srinivasan
(IIT Bombay, India)
Article Search
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Sam Hopkins, Tarun Kathuria, Prasad Raghavendra, and Nilesh Tripuraneni
(University of California at Berkeley, USA)
Article Search
Constant Girth Approximation for Directed Graphs in Subquadratic Time
Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford
(Tel Aviv University, Israel; Stanford University, USA)
Article Search
Non-adaptive Adaptive Sampling on Turnstile Streams
Sepideh Mahabadi, Ilya Razenshteyn, David P. Woodruff, and Samson Zhou
(Toyota Technological Institute at Chicago, USA; Microsoft Research, n.n.; Carnegie Mellon University, USA)
Article Search
Interactive Shallow Clifford Circuits: Quantum Advantage against NC^1 and Beyond
Daniel Grier and Luke Schaeffer
(University of Waterloo, Canada)
Article Search
Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
Sitan Chen, Jerry Li, and Zhao Song
(Massachusetts Institute of Technology, USA; Microsoft Research, n.n.; University of Texas at Austin, USA)
Article Search
Weighted Min-Cut: Sequential, Cut-Query, and Streaming Algorithms
Sagnik Mukhopadhyay and Danupon Nanongkai
(KTH, Sweden)
Article Search
Private Stochastic Convex Optimization: Optimal Rates in Linear Time
Vitaly Feldman, Tomer Koren, and Kunal Talwar
(Google Research, n.n.)
Article Search
A Phase Transition and Quadratic Time Estimator for Network Reliability
David R. Karger
(Massachusetts Institute of Technology, USA)
Article Search
Efficiently Learning Structured Distributions from Untrusted Batches
Sitan Chen, Jerry Li, and Ankur Moitra
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)
Article Search
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian
(Stanford University, USA; University of Washington, USA; Microsoft Research, USA)
Article Search
Extractors for Adversarial Sources via Extremal Hypergraphs
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, and Xin Li
(Cornell University, USA; Carnegie Mellon University, USA; Johns Hopkins University, USA)
Article Search
Stochastic Matching with Few Queries: (1-ε) Approximation
Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi
(University of Maryland, USA)
Article Search
Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-armed Bandits
Sepehr Assadi and Chen Wang
(Rutgers University, USA)
Article Search
Data Structures Meet Cryptography: 3SUM with Preprocessing
Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikuntanathan
(Harvard University, USA; New York University Shanghai, China; Massachusetts Institute of Technology, USA)
Article Search

proc time: 9.46