| Title/Authors | Title | Research Artifacts
[?] A research
artifact is any by-product of a research project that is not
directly included in the published research paper. In Computer
Science research this is often source code and data sets, but
it could also be media, documentation, inputs to proof
assistants, shell-scripts to run experiments, etc.
|
Details |
|---|
|
Beyond matroids: secretary problem and prophet inequality with general constraints Aviad Rubinstein |
Beyond matroids: secretary problem and prophet inequality with general constraints Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Separations in query complexity based on pointer functions Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs |
Separations in query complexity based on pointer functions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Venkatesan Guruswami, Mary Wootters |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Exact algorithms via monotone local search Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh |
Exact algorithms via monotone local search Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Semidefinite programs on sparse random graphs and their application to community detection Andrea Montanari, Subhabrata Sen |
Semidefinite programs on sparse random graphs and their application to community detection Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Constant-round interactive proofs for delegating computation Omer Reingold, Guy N. Rothblum, Ron D. Rothblum |
Constant-round interactive proofs for delegating computation Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Geometric median in nearly linear time Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, Aaron Sidford |
Geometric median in nearly linear time Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Gilad Asharov, Moni Naor, Gil Segev, Ido Shahaf |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Deterministic and probabilistic binary search in graphs Ehsan Emamjomeh-Zadeh, David Kempe, Vikrant Singhal |
Deterministic and probabilistic binary search in graphs Details |
|
Author Comments:
Discussion Comments:
0
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer |
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors Details |
|
Author Comments:
None of the results claimed in the paper are backed by code. All contributions of the paper are backed by proofs, which are all included in the arXiv version of the paper. The paper includes formal descriptions of all contributed algorithms, at a level of detail sufficient to directly translate to any programming language that has a linear algebra package.
Discussion Comments:
0
Sharing:
Other
Verification:
Authors have
verified
information
|
|
Michael Kapralov |
Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Graph isomorphism in quasipolynomial time [extended abstract] László Babai |
Graph isomorphism in quasipolynomial time [extended abstract] Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Daniel M. Kane, Ryan Williams |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Alina Ene, Gary L. Miller, Jakub Pachocki, Aaron Sidford |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The fourier transform of poisson multinomial distributions and its algorithmic applications Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart |
The fourier transform of poisson multinomial distributions and its algorithmic applications Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Contention resolution with log-logstar channel accesses Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young |
Contention resolution with log-logstar channel accesses Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
How robust are reconstruction thresholds for community detection? Ankur Moitra, William Perry, Alexander S. Wein |
How robust are reconstruction thresholds for community detection? Details |
|
Author Comments:
Discussion Comments:
0
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
Two-source dispersers for polylogarithmic entropy and improved ramsey graphs Gil Cohen |
Two-source dispersers for polylogarithmic entropy and improved ramsey graphs Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Weighted low rank approximations with provable guarantees Ilya P. Razenshteyn, Zhao Song, David P. Woodruff |
Weighted low rank approximations with provable guarantees Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The computational power of optimization in online learning Elad Hazan, Tomer Koren |
The computational power of optimization in online learning Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Enumerating parametric global minimum cuts by random interleaving David R. Karger |
Enumerating parametric global minimum cuts by random interleaving Details |
|
Author Comments:
Discussion Comments:
0
Sharing:
Research produced no artifacts
Verification:
Author has
verified
information
|
|
Improved approximation for node-disjoint paths in planar graphs Julia Chuzhoy, David H. K. Kim, Shi Li |
Improved approximation for node-disjoint paths in planar graphs Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf |
High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Maximizing determinants under partition constraints Aleksandar Nikolov, Mohit Singh |
Maximizing determinants under partition constraints Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Exponential separation of communication and external information Anat Ganor, Gillat Kol, Ran Raz |
Exponential separation of communication and external information Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Watch and learn: optimizing from revealed preferences feedback Aaron Roth, Jonathan Ullman, Zhiwei Steven Wu |
Watch and learn: optimizing from revealed preferences feedback Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Chris Hall, Doron Puder, William F. Sawin |
Details |
|
Author Comments:
Discussion Comments:
0
Sharing:
Not able to share produced artifacts
Verification:
Authors have
verified
information
|
|
A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies Elaine Levey, Thomas Rothvoss |
A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A cost function for similarity-based hierarchical clustering Sanjoy Dasgupta |
A cost function for similarity-based hierarchical clustering Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
The 4/3 additive spanner exponent is tight Amir Abboud, Greg Bodwin |
The 4/3 additive spanner exponent is tight Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Complexity theoretic limitations on learning halfspaces Amit Daniely |
Complexity theoretic limitations on learning halfspaces Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Poly-logarithmic Frege depth lower bounds via an expander switching lemma Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan |
Poly-logarithmic Frege depth lower bounds via an expander switching lemma Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Approximating connectivity domination in weighted bounded-genus graphs Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld |
Approximating connectivity domination in weighted bounded-genus graphs Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Watermarking cryptographic capabilities Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, Daniel Wichs |
Watermarking cryptographic capabilities Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Explicit two-source extractors and resilient functions Eshan Chattopadhyay, David Zuckerman |
Explicit two-source extractors and resilient functions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Separating subadditive euclidean functionals Alan M. Frieze, Wesley Pegden |
Separating subadditive euclidean functionals Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
New deterministic approximation algorithms for fully dynamic matching Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai |
New deterministic approximation algorithms for fully dynamic matching Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Subhash Khot, Dana Moshkovitz |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Base collapse of holographic algorithms Mingji Xia |
Base collapse of holographic algorithms Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Separations in query complexity using cheat sheets Scott Aaronson, Shalev Ben-David, Robin Kothari |
Separations in query complexity using cheat sheets Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Classical verification of quantum proofs Zhengfeng Ji |
Classical verification of quantum proofs Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders Shahar Dobzinski |
Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Bipartite perfect matching is in quasi-NC Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf |
Bipartite perfect matching is in quasi-NC Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Textbook non-malleable commitments Vipul Goyal, Omkant Pandey, Silas Richelson |
Textbook non-malleable commitments Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Streaming algorithms for embedding and computing edit distance in the low distance regime Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký |
Streaming algorithms for embedding and computing edit distance in the low distance regime Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Eshan Chattopadhyay, Xin Li |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Distributed (∆+1)-coloring in sublogarithmic rounds David G. Harris, Johannes Schneider, Hsin-Hao Su |
Distributed (∆+1)-coloring in sublogarithmic rounds Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Justin Hsu, Jamie Morgenstern, Ryan M. Rogers, Aaron Roth, Rakesh Vohra |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Deterministic decremental single source shortest paths: beyond the o(mn) bound Aaron Bernstein, Shiri Chechik |
Deterministic decremental single source shortest paths: beyond the o(mn) bound Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A discrete and bounded envy-free cake cutting protocol for four agents Haris Aziz, Simon Mackenzie |
A discrete and bounded envy-free cake cutting protocol for four agents Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The price of anarchy in large games Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, Vasilis Syrgkanis |
The price of anarchy in large games Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Algebraic attacks against random local functions and their countermeasures Benny Applebaum, Shachar Lovett |
Algebraic attacks against random local functions and their countermeasures Details |
|
Author Comments:
Discussion Comments:
0
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
Efficiently decoding Reed-Muller codes from random errors Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk |
Efficiently decoding Reed-Muller codes from random errors Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Sample-optimal tomography of quantum states Jeongwan Haah, Aram Wettroth Harrow, Zheng-Feng Ji, Xiaodi Wu, Nengkun Yu |
Sample-optimal tomography of quantum states Details |
|
Author Comments:
Discussion Comments:
0
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
Almost tight bounds for eliminating depth cycles in three dimensions Boris Aronov, Micha Sharir |
Almost tight bounds for eliminating depth cycles in three dimensions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Ryan O'Donnell, John Wright |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A lower bound for the distributed Lovász local lemma Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Jara Uitto |
A lower bound for the distributed Lovász local lemma Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Sparsified Cholesky and multigrid solvers for connection laplacians Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman |
Sparsified Cholesky and multigrid solvers for connection laplacians Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Lift-and-round to improve weighted completion time on unrelated machines Nikhil Bansal, Aravind Srinivasan, Ola Svensson |
Lift-and-round to improve weighted completion time on unrelated machines Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Instance optimal learning of discrete distributions Gregory Valiant, Paul Valiant |
Instance optimal learning of discrete distributions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Constant-rate coding for multiparty interactive communication is impossible Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler |
Constant-rate coding for multiparty interactive communication is impossible Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Tight bounds for single-pass streaming complexity of the set cover problem Sepehr Assadi, Sanjeev Khanna, Yang Li |
Tight bounds for single-pass streaming complexity of the set cover problem Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Entangled simultaneity versus classical interactivity in communication complexity Dmitry Gavinsky |
Entangled simultaneity versus classical interactivity in communication complexity Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Online matching: haste makes waste! Yuval Emek, Shay Kutten, Roger Wattenhofer |
Online matching: haste makes waste! Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A size-free CLT for poisson multinomials and its applications Constantinos Daskalakis, Anindya De, Gautam Kamath, Christos Tzamos |
A size-free CLT for poisson multinomials and its applications Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Relating two property testing models for bounded degree directed graphs Artur Czumaj, Pan Peng, Christian Sohler |
Relating two property testing models for bounded degree directed graphs Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Cell-probe lower bounds for dynamic problems via a new communication model Huacheng Yu |
Cell-probe lower bounds for dynamic problems via a new communication model Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Algorithmic Bayesian persuasion Shaddin Dughmi, Haifeng Xu |
Algorithmic Bayesian persuasion Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Matrix rigidity of random toeplitz matrices Oded Goldreich, Avishay Tal |
Matrix rigidity of random toeplitz matrices Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Optimal principal component analysis in distributed and streaming models Christos Boutsidis, David P. Woodruff, Peilin Zhong |
Optimal principal component analysis in distributed and streaming models Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A polynomial lower bound for testing monotonicity Aleksandrs Belovs, Eric Blais |
A polynomial lower bound for testing monotonicity Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
On approximating functions of the singular values in a stream Yi Li, David P. Woodruff |
On approximating functions of the singular values in a stream Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A tight space bound for consensus Leqi Zhu |
A tight space bound for consensus Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx |
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
On the size of homogeneous and of depth four formulas with low individual degree Neeraj Kayal, Chandan Saha, Sébastien Tavenas |
On the size of homogeneous and of depth four formulas with low individual degree Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Non-malleable extractors and codes, with their many tampered extensions Eshan Chattopadhyay, Vipul Goyal, Xin Li |
Non-malleable extractors and codes, with their many tampered extensions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Fault tolerant subgraph for single source reachability: generic and optimal Surender Baswana, Keerti Choudhary, Liam Roditty |
Fault tolerant subgraph for single source reachability: generic and optimal Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Algorithmic stability for adaptive data analysis Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, Jonathan Ullman |
Algorithmic stability for adaptive data analysis Details |
|
Author Comments:
Discussion Comments:
0
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
Parallel algorithms for select and partition with noisy comparisons Mark Braverman, Jieming Mao, S. Matthew Weinberg |
Parallel algorithms for select and partition with noisy comparisons Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Reed-Muller codes achieve capacity on erasure channels Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu, Rüdiger L. Urbanke |
Reed-Muller codes achieve capacity on erasure channels Details |
|
Author Comments:
Discussion Comments:
0
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
The sample complexity of auctions with side information Nikhil R. Devanur, Zhiyi Huang, Christos-Alexandros Psomas |
The sample complexity of auctions with side information Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Beating CountSketch for heavy hitters in insertion streams Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff |
Beating CountSketch for heavy hitters in insertion streams Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Near-optimal small-depth lower bounds for small distance connectivity Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan |
Near-optimal small-depth lower bounds for small distance connectivity Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Basis collapse for holographic algorithms over all domain sizes Sitan Chen |
Basis collapse for holographic algorithms over all domain sizes Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Interactive compression for product distributions Gillat Kol |
Interactive compression for product distributions Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Parallel exhaustive search without coordination Pierre Fraigniaud, Amos Korman, Yoav Rodeh |
Parallel exhaustive search without coordination Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Bounded degree cosystolic expanders of every dimension Shai Evra, Tali Kaufman |
Bounded degree cosystolic expanders of every dimension Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
On the effect of randomness on planted 3-coloring models Roee David, Uriel Feige |
On the effect of randomness on planted 3-coloring models Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A duality based unified approach to Bayesian mechanism design Yang Cai, Nikhil R. Devanur, S. Matthew Weinberg |
A duality based unified approach to Bayesian mechanism design Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|