STOC - RankMe – RankMe

114 papers

Year	Title / Authors
2020	(Semi)Algebraic proofs over ±1 variables. Dmitry Sokolov
2020	A lower bound for parallel submodular minimization. Eric Balkanski, Yaron Singer
2020	A phase transition and a quadratic time unbiased estimator for network reliability. David R. Karger
2020	A polynomial lower bound on adaptive complexity of submodular maximization. Wenzheng Li, Paul Liu, Jan Vondrák
2020	A robust version of Hegedus's lemma, with applications. Srikanth Srinivasan
2020	A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix. Daniel Dadush, Sophie Huiberts, Bento Natura, László A. Végh
2020	A spectral approach to network design. Lap Chi Lau, Hong Zhou
2020	AND testing and robust judgement aggregation. Yuval Filmus, Noam Lifshitz, Dor Minzer, Elchanan Mossel
2020	Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond. Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni
2020	All non-trivial variants of 3-LDT are equivalent. Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya
2020	An exponential time parameterized algorithm for planar disjoint paths. Daniel Lokshtanov, Pranabendu Misra, Michal Pilipczuk, Saket Saurabh, Meirav Zehavi
2020	An improved approximation algorithm for ATSP. Vera Traub, Jens Vygen
2020	An improved approximation algorithm for TSP in the half integral case. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
2020	An improved cutting plane method for convex optimization, convex-concave games, and its applications. Haotian Jiang, Yin Tat Lee, Zhao Song, Sam Chiu-wai Wong
2020	Approximately stable committee selection. Zhihao Jiang, Kamesh Munagala, Kangning Wang
2020	Approximating text-to-pattern Hamming distances. Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat
2020	Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity. Venkatesan Guruswami, Andrii Riazanov, Min Ye
2020	Automating cutting planes is NP-hard. Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi
2020	Bare quantum simultaneity versus classical interactivity in communication complexity. Dmitry Gavinsky
2020	Better secret sharing via robust conditional disclosure of secrets. Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter
2020	Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication. Jesper Nederlof
2020	Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. Jaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli
2020	Caching with time windows. Anupam Gupta, Amit Kumar, Debmalya Panigrahi
2020	Catalytic approaches to the tree evaluation problem. James Cook, Ian Mertz
2020	Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. Aram W. Harrow, Saeed Mehraban, Mehdi Soleimanifar
2020	Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius. Chong Shangguan, Itzhak Tamo
2020	Computations with greater quantum depth are strictly more powerful (relative to an oracle). Matthew Coudron, Sanketh Menda
2020	Concentration on the Boolean hypercube via pathwise stochastic analysis. Ronen Eldan, Renan Gross
2020	Constant factor approximations to edit distance on far input pairs in nearly linear time. Michal Koucký, Michael E. Saks
2020	Constant girth approximation for directed graphs in subquadratic time. Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford
2020	Constant-factor approximation of near-linear edit distance in near-linear time. Joshua Brakensiek, Aviad Rubinstein
2020	Contention resolution without collision detection. Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie
2020	Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal. Lingxiao Huang, Nisheeth K. Vishnoi
2020	Data structures meet cryptography: 3SUM with preprocessing. Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, Vinod Vaikuntanathan
2020	Decision list compression by mild random restrictions. Shachar Lovett, Kewen Wu, Jiapeng Zhang
2020	Detecting and counting small patterns in planar graphs in subexponential parameterized time. Jesper Nederlof
2020	Distance sensitivity oracles with subcubic preprocessing time and fast query time. Shiri Chechik, Sarel Cohen
2020	Does learning require memorization? a short tale about a long tail. Vitaly Feldman
2020	Does preprocessing help in fast sequence comparisons? Elazar Goldenberg, Aviad Rubinstein, Barna Saha
2020	Dynamic algorithms for LIS and distance to monotonicity. Michael Mitzenmacher, Saeed Seddighin
2020	Efficient construction of directed hopsets and parallel approximate shortest paths. Nairen Cao, Jeremy T. Fineman, Katina Russell
2020	Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures. Christian Borgs, Jennifer T. Chayes, Tyler Helmuth, Will Perkins, Prasad Tetali
2020	Efficiently learning structured distributions from untrusted batches. Sitan Chen, Jerry Li, Ankur Moitra
2020	Entanglement subvolume law for 2d frustration-free spin systems. Anurag Anshu, Itai Arad, David Gosset
2020	Estimating normalizing constants for log-concave distributions: algorithms and lower bounds. Rong Ge, Holden Lee, Jianfeng Lu
2020	Explicit near-Ramanujan graphs of every degree. Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
2020	Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits. Sepehr Assadi, Chen Wang
2020	Extractors for adversarial sources via extremal hypergraphs. Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li
2020	Fast hashing with strong concentration bounds. Anders Aamand, Jakob Bæk Tejs Knudsen, Mathias Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen, Mikkel Thorup
2020	Fast sampling and counting k-SAT solutions in the local lemma regime. Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang
2020	Faster energy maximization for faster maximum flow. Yang P. Liu, Aaron Sidford
2020	Faster parallel algorithm for approximate shortest path. Jason Li
2020	Fooling Gaussian PTFs via local hyperconcentration. Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2020	Fully-dynamic planarity testing in polylogarithmic time. Jacob Holm, Eva Rotenberg
2020	Hitting topological minors is FPT. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi
2020	How to lose at Monte Carlo: a simple dynamical system whose typical statistical behavior is non-computable. Cristobal Rojas, Michael Yampolsky
2020	Implementing geometric complexity theory: on the separation of orbit closures via symmetries. Christian Ikenmeyer, Umangathan Kandasamy
2020	Improved analysis of higher order random walks and applications. Vedat Levi Alev, Lap Chi Lau
2020	Improved bounds for perfect sampling of k-colorings in graphs. Siddharth Bhandari, Sayantan Chakraborty
2020	Improved bounds for the sunflower lemma. Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang
2020	Interaction is necessary for distributed learning with privacy or communication constraints. Yuval Dagan, Vitaly Feldman
2020	Interactive error resilience beyond 2/7. Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
2020	Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond. Daniel Grier, Luke Schaeffer
2020	Learning mixtures of linear regressions in subexponential time via Fourier moments. Sitan Chen, Jerry Li, Zhao Song
2020	Lifting sum-of-squares lower bounds: degree-2 to degree-4. Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu
2020	Lower bound for succinct range minimum query. Mingmou Liu, Huacheng Yu
2020	Near-optimal fully dynamic densest subgraph. Saurabh Sawlani, Junxing Wang
2020	Nearly optimal static Las Vegas succinct dictionary. Huacheng Yu
2020	New algorithms and hardness for incremental single-source shortest paths in directed graphs. Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
2020	New hardness results for planar graph problems in p and an algorithm for sparsest cut. Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
2020	Non-adaptive adaptive sampling on turnstile streams. Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou
2020	Non-signaling proofs with o(√ log n) provers are in PSPACE. Dhiraj Holden, Yael Tauman Kalai
2020	On the Nisan-Ronen conjecture for submodular valuations. George Christodoulou, Elias Koutsoupias, Annamária Kovács
2020	On the computability of continuous maximum entropy distributions with applications. Jonathan Leake, Nisheeth K. Vishnoi
2020	On the need for large quantum depth. Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai
2020	One-shot signatures and applications to hybrid quantum/classical authentication. Ryan Amos, Marios Georgiou, Aggelos Kiayias, Mark Zhandry
2020	Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue. Zhiyi Huang, Qiankun Zhang
2020	Online vector balancing and geometric discrepancy. Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha
2020	Optimal time and space leader election in population protocols. Petra Berenbrink, George Giakkoupis, Peter Kling
2020	Optimally resilient codes for list-decoding from insertions and deletions. Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi
2020	Parallel approximate undirected shortest paths via low hop emulators. Alexandr Andoni, Clifford Stein, Peilin Zhong
2020	Polylogarithmic-time deterministic network decomposition and distributed derandomization. Václav Rozhon, Mohsen Ghaffari
2020	Positive semidefinite programming: mixed, parallel, and width-independent. Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, Kevin Tian
2020	Post-quantum zero knowledge in constant rounds. Nir Bitansky, Omri Shmueli
2020	Private stochastic convex optimization: optimal rates in linear time. Vitaly Feldman, Tomer Koren, Kunal Talwar
2020	Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
2020	QCSP monsters and the demise of the chen conjecture. Dmitriy Zhuk, Barnaby Martin
2020	Quadratic speedup for finding marked vertices by quantum walks. Andris Ambainis, András Gilyén, Stacey Jeffery, Martins Kokainis
2020	Reducing path TSP to TSP. Vera Traub, Jens Vygen, Rico Zenklusen
2020	Rounding dynamic matchings against an adaptive adversary. David Wajc
2020	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, Chunhao Wang
2020	Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative? Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret
2020	Separating the communication complexity of truthful and non-truthful combinatorial auctions. Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg
2020	Separations and equivalences between turnstile streaming and linear sketching. John Kallaugher, Eric Price
2020	Sharp threshold results for computational complexity. Lijie Chen, Ce Jin, R. Ryan Williams
2020	Smoothed complexity of local max-cut and binary max-CSP. Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang
2020	Solving tall dense linear programs in nearly linear time. Jan van den Brand, Yin Tat Lee, Aaron Sidford, Zhao Song
2020	Stochastic matching with few queries: (1-ε) approximation. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi
2020	Strong average-case lower bounds from non-trivial derandomization. Lijie Chen, Hanlin Ren
2020	Strong self-concordance and sampling. Aditi Laddha, Yin Tat Lee, Santosh S. Vempala
2020	Testing noisy linear functions for sparsity. Xue Chen, Anindya De, Rocco A. Servedio
2020	The Karger-Stein algorithm is optimal for k-cut. Anupam Gupta, Euiwoong Lee, Jason Li
2020	The impossibility of efficient quantum weak coin flipping. Carl A. Miller
2020	The one-way communication complexity of submodular maximization with applications to streaming and robustness. Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, Rico Zenklusen
2020	The power of factorization mechanisms in local and central differential privacy. Alexander Edmonds, Aleksandar Nikolov, Jonathan R. Ullman
2020	The program-size complexity of self-assembled paths. Pierre-Étienne Meunier, Damien Regnault, Damien Woods
2020	Three-in-a-tree in near linear time. Kai-Yuan Lai, Hsueh-I Lu, Mikkel Thorup
2020	Top-k-convolution and the quest for near-linear output-sensitive subset sum. Karl Bringmann, Vasileios Nakos
2020	Towards a better understanding of randomized greedy matching. Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang
2020	Unbounded lower bound for k-server against weak adversaries. Marcin Bienkowski, Jaroslaw Byrka, Christian Coester, Lukasz Jez
2020	Unexpected hardness results for Kolmogorov complexity under uniform reductions. Shuichi Hirahara
2020	Walking randomly, massively, and efficiently. Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski
2020	Weighted min-cut: sequential, cut-query, and streaming algorithms. Sagnik Mukhopadhyay, Danupon Nanongkai
2020	XOR lemmas for resilient functions against polynomials. Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman