| 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 |
|---|
|
Robust Estimators in High Dimensions without the Computational Intractability Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart |
Robust Estimators in High Dimensions without the Computational Intractability Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Commutativity in the Algorithmic Lovász Local Lemma Vladimir Kolmogorov |
Commutativity in the Algorithmic Lovász Local Lemma Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Extension Complexity of Independent Set Polytopes Mika Göös, Rahul Jain, Thomas Watson |
Extension Complexity of Independent Set Polytopes Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A New Framework for Distributed Submodular Maximization Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, Justin Ward |
A New Framework for Distributed Submodular Maximization Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Optimizing Star-Convex Functions Jasper C. H. Lee, Paul Valiant |
Optimizing Star-Convex Functions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Amit Chakrabarti, Sagar Kale |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Simulated Quaotum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing Elizabeth Crosson, Aram Wettroth Harrow |
Simulated Quaotum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Compressing Interactive Communication under Product Distributions Alexander A. Sherstov |
Compressing Interactive Communication under Product Distributions Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Agnostic Estimation of Mean and Covariance Kevin A. Lai, Anup B. Rao, Santosh S. Vempala |
Agnostic Estimation of Mean and Covariance Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Yiling Chen, Bo Waggoner |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A PTAS for the Steiner Forest Problem in Doubling Metrics T.-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang |
A PTAS for the Steiner Forest Problem in Doubling Metrics Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Learning in Auctions: Regret is Hard, Envy is Easy Constantinos Daskalakis, Vasilis Syrgkanis |
Learning in Auctions: Regret is Hard, Envy is Easy Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
An Average-Case Depth Hierarchy Theorem for Higher Depth Johan Håstad |
An Average-Case Depth Hierarchy Theorem for Higher Depth Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Sungjin Im, Shi Li |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Noisy Population Recovery in Polynomial Time Anindya De, Michael E. Saks, Sijian Tang |
Noisy Population Recovery in Polynomial Time Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Knuth Prize Lecture: Complexity of Communication in Markets Noam Nisan |
Knuth Prize Lecture: Complexity of Communication in Markets Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Eshan Chattopadhyay, Xin Li |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Structure of Protocols for XOR Functions Hamed Hatami, Kaave Hosseini, Shachar Lovett |
Structure of Protocols for XOR Functions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda, Yitong Yin |
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Decidability of Non-interactive Simulation of Joint Distributions Badih Ghazi, Pritish Kamath, Madhu Sudan |
Decidability of Non-interactive Simulation of Joint Distributions Details |
|
Author Comments:
Discussion Comments:
0
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
Susanna F. de Rezende, Jakob Nordström, Marc Vinyals |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Zero-Knowledge Proof Systems for QMA Anne Broadbent, Zhengfeng Ji, Fang Song, John Watrous |
Zero-Knowledge Proof Systems for QMA Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Constrained Submodular Maximization: Beyond 1/e Alina Ene, Huy L. Nguyen |
Constrained Submodular Maximization: Beyond 1/e Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The Multiparty Communication Complexity of Interleaved Group Products W. T. Gowers, Emanuele Viola |
The Multiparty Communication Complexity of Interleaved Group Products Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu |
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Extractors for Near Logarithmic Min-Entropy Gil Cohen, Leonard J. Schulman |
Extractors for Near Logarithmic Min-Entropy Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Local Search Yields a PTAS for k-Means in Doubling Metrics Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour |
Local Search Yields a PTAS for k-Means in Doubling Metrics Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Accelerated Newton Iteration for Roots of Black Box Polynomials Anand Louis, Santosh S. Vempala |
Accelerated Newton Iteration for Roots of Black Box Polynomials Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Bounded-Communication Leakage Resilience via Parity-Resilient Circuits Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, Alexander A. Sherstov |
Bounded-Communication Leakage Resilience via Parity-Resilient Circuits Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Settling the Complexity of Computing Approximate Two-Player Nash Equilibria Aviad Rubinstein |
Settling the Complexity of Computing Approximate Two-Player Nash Equilibria Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Online Algorithms for Covering and Packing Problems with Convex Objectives Yossi Azar, Niv Buchbinder, T.-H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, Debmalya Panigrahi |
Online Algorithms for Covering and Packing Problems with Convex Objectives Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound Nikhil Bansal, Daniel Dadush, Shashwat Garg |
An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
How to Determine if a Random Graph with a Fixed Degree Sequence Has a Giant Component Felix Joos, Guillem Perarnau, Dieter Rautenbach, Bruce A. Reed |
How to Determine if a Random Graph with a Fixed Degree Sequence Has a Giant Component Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents Haris Aziz, Simon Mackenzie |
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
No Occurrence Obstructions in Geometric Complexity Theory Peter Bürgisser, Christian Ikenmeyer, Greta Panova |
No Occurrence Obstructions in Geometric Complexity Theory Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Max-Information, Differential Privacy, and Post-selection Hypothesis Testing Ryan M. Rogers, Aaron Roth, Adam D. Smith, Om Thakkar |
Max-Information, Differential Privacy, and Post-selection Hypothesis Testing Details |
|
Author Comments:
Discussion Comments:
0
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism Sofya Raskhodnikova, Adam D. Smith |
Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Depth-Reduction for Composites Shiteng Chen, Periklis A. Papakonstantinou |
Depth-Reduction for Composites Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Breaking the Three Round Barrier for Non-malleable Commitments Vipul Goyal, Dakshita Khurana, Amit Sahai |
Breaking the Three Round Barrier for Non-malleable Commitments Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin |
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The Number of Solutions for Random Regular NAE-SAT Allan Sly, Nike Sun, Yumeng Zhang |
The Number of Solutions for Random Regular NAE-SAT Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Towards Strong Reverse Minkowski-Type Inequalities for Lattices Daniel Dadush, Oded Regev |
Towards Strong Reverse Minkowski-Type Inequalities for Lattices Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The Constant Inapproximability of the Parameterized Dominating Set Problem Yijia Chen, Bingkai Lin |
The Constant Inapproximability of the Parameterized Dominating Set Problem Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication Omri Weinstein, Huacheng Yu |
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory Christian Ikenmeyer, Greta Panova |
Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Edit Distance: Sketching, Streaming, and Document Exchange Djamal Belazzougui, Qin Zhang |
Edit Distance: Sketching, Streaming, and Document Exchange Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A New Approach for Testing Properties of Discrete Distributions Ilias Diakonikolas, Daniel M. Kane |
A New Approach for Testing Properties of Discrete Distributions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple Rasmus Kyng, Sushant Sachdeva |
Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Separations in Communication Complexity Using Cheat Sheets and Information Complexity Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha |
Separations in Communication Complexity Using Cheat Sheets and Information Complexity Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Exponential Lower Bounds for Monotone Span Programs Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook |
Exponential Lower Bounds for Monotone Span Programs Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms Amir Abboud, Søren Dahlgaard |
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy Xin Li |
Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Polynomial Representations of Threshold Functions and Algorithmic Applications Josh Alman, Timothy M. Chan, R. Ryan Williams |
Polynomial Representations of Threshold Functions and Algorithmic Applications Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Polynomial-Time Tensor Decompositions with Sum-of-Squares Tengyu Ma, Jonathan Shi, David Steurer |
Polynomial-Time Tensor Decompositions with Sum-of-Squares Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Optimal Quantile Approximation in Streams Zohar S. Karnin, Kevin J. Lang, Edo Liberty |
Optimal Quantile Approximation in Streams Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning Ran Raz |
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
On the Communication Complexity of Approximate Fixed Points Tim Roughgarden, Omri Weinstein |
On the Communication Complexity of Approximate Fixed Points Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths Michael Elkin, Ofer Neiman |
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Which Regular Expression Patterns Are Hard to Match? Arturs Backurs, Piotr Indyk |
Which Regular Expression Patterns Are Hard to Match? Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A Fast and Simple Unbiased Estimator for Network (Un)reliability David R. Karger |
A Fast and Simple Unbiased Estimator for Network (Un)reliability Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Computational Efficiency Requires Simple Taxation Shahar Dobzinski |
Computational Efficiency Requires Simple Taxation Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Computing Maximum Flow with Augmenting Electrical Flows Aleksander Madry |
Computing Maximum Flow with Augmenting Electrical Flows Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Robust Fourier and Polynomial Curve Fitting Venkatesan Guruswami, David Zuckerman |
Robust Fourier and Polynomial Curve Fitting Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Heavy Hitters via Cluster-Preserving Clustering Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup |
Heavy Hitters via Cluster-Preserving Clustering Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Testing Assignments to Constraint Satisfaction Problems Hubie Chen, Matthew Valeriote, Yuichi Yoshida |
Testing Assignments to Constraint Satisfaction Problems Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Fourier-Sparse Interpolation without a Frequency Gap Xue Chen, Daniel M. Kane, Eric Price, Zhao Song |
Fourier-Sparse Interpolation without a Frequency Gap Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem Venkata Gandikota, Badih Ghazi, Elena Grigorescu |
NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers |
Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
On Fully Dynamic Graph Sparsifiers Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, Richard Peng |
On Fully Dynamic Graph Sparsifiers Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie |
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Fully Dynamic Maximal Matching in Constant Update Time Shay Solomon |
Fully Dynamic Maximal Matching in Constant Update Time Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Mathias Bæk Tejs Knudsen |
Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Amplification and Derandomization without Slowdown Ofer Grossman, Dana Moshkovitz |
Amplification and Derandomization without Slowdown Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
On Approximating Maximum Independent Set of Rectangles Julia Chuzhoy, Alina Ene |
On Approximating Maximum Independent Set of Rectangles Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Ramanujan Graphs in Polynomial Time Michael B. Cohen |
Ramanujan Graphs in Polynomial Time Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Lacki, Nikos Parotsidis |
Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time Details |
|
Author Comments:
Discussion Comments:
0
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
Making the Most of Advice: New Correlation Breakers and Their Applications Gil Cohen |
Making the Most of Advice: New Correlation Breakers and Their Applications Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings Huijia Lin, Vinod Vaikuntanathan |
Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov |
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson |
A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The Salesman's Improved Paths: A 3/2+1/34 Approximation András Sebö, Anke van Zuylen |
The Salesman's Improved Paths: A 3/2+1/34 Approximation Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling Zachary Remscrim |
The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|