| 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 |
|---|
|
Alina Ene, Ali Vakilian |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
How to delegate computations: the power of no-signaling proofs Yael Tauman Kalai, Ran Raz, Ron D. Rothblum |
How to delegate computations: the power of no-signaling proofs Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Black-box non-black-box zero knowledge Vipul Goyal, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti |
Black-box non-black-box zero knowledge Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Breaking the minsky-papert barrier for constant-depth circuits Alexander A. Sherstov |
Breaking the minsky-papert barrier for constant-depth circuits Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
An almost-optimally fair three-party coin-flipping protocol Iftach Haitner, Eliad Tsfadia |
An almost-optimally fair three-party coin-flipping protocol Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The asymptotic k-SAT threshold Amin Coja-Oghlan |
The asymptotic k-SAT threshold Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
A characterization of locally testable affine-invariant properties via decomposition theorems Yuichi Yoshida |
A characterization of locally testable affine-invariant properties via decomposition theorems Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Embedding and canonizing graphs of bounded genus in logspace Michael Elberfeld, Ken-ichi Kawarabayashi |
Embedding and canonizing graphs of bounded genus in logspace Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Jugal Garg, Ruta Mehta, Vijay V. Vazirani |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Minimum bisection is fixed parameter tractable Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh |
Minimum bisection is fixed parameter tractable Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Analyze gauss: optimal bounds for privacy-preserving principal component analysis Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, Li Zhang |
Analyze gauss: optimal bounds for privacy-preserving principal component analysis Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Hitting sets for multilinear read-once algebraic branching programs, in any order Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka |
Hitting sets for multilinear read-once algebraic branching programs, in any order Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Circuits resilient to additive attacks with applications to secure computation Daniel Genkin, Yuval Ishai, Manoj Prabhakaran, Amit Sahai, Eran Tromer |
Circuits resilient to additive attacks with applications to secure computation Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, Kunal Talwar |
Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Lower bounds for depth 4 formulas computing iterated matrix multiplication Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan |
Lower bounds for depth 4 formulas computing iterated matrix multiplication Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
An efficient parallel solver for SDD linear systems Richard Peng, Daniel A. Spielman |
An efficient parallel solver for SDD linear systems Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Query complexity of approximate nash equilibria Yakov Babichenko |
Query complexity of approximate nash equilibria Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Parallel algorithms for geometric graph problems Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev |
Parallel algorithms for geometric graph problems Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Rounding sum-of-squares relaxations Boaz Barak, Jonathan A. Kelner, David Steurer |
Rounding sum-of-squares relaxations Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A quantum algorithm for computing the unit group of an arbitrary degree number field Kirsten Eisenträger, Sean Hallgren, Alexei Y. Kitaev, Fang Song |
A quantum algorithm for computing the unit group of an arbitrary degree number field Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
On derandomizing algorithms that err extremely rarely Oded Goldreich, Avi Wigderson |
On derandomizing algorithms that err extremely rarely Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Fingerprinting codes and the price of approximate differential privacy Mark Bun, Jonathan Ullman, Salil P. Vadhan |
Fingerprinting codes and the price of approximate differential privacy Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Economic efficiency requires interaction Shahar Dobzinski, Noam Nisan, Sigal Oren |
Economic efficiency requires interaction Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Primal beats dual on online packing LPs in the random-order model Thomas Kesselheim, Klaus Radke, Andreas Tönnis, Berthold Vöcking |
Primal beats dual on online packing LPs in the random-order model Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Analytical approach to parallel repetition Irit Dinur, David Steurer |
Analytical approach to parallel repetition Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Testing surface area with arbitrary accuracy Joe Neeman |
Testing surface area with arbitrary accuracy Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Shortest paths on polyhedral surfaces and terrains Siu-Wing Cheng, Jiongxin Jin |
Shortest paths on polyhedral surfaces and terrains Details |
|
Author Comments:
Discussion Comments:
0
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
Private matchings and allocations Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, Zhiwei Steven Wu |
Private matchings and allocations Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A super-polynomial lower bound for regular arithmetic formulas Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi |
A super-polynomial lower bound for regular arithmetic formulas Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Constant rank bimatrix games are PPAD-hard Ruta Mehta |
Constant rank bimatrix games are PPAD-hard Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Entropy, optimization and counting Mohit Singh, Nisheeth K. Vishnoi |
Entropy, optimization and counting Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A strongly polynomial algorithm for generalized flow maximization László A. Végh |
A strongly polynomial algorithm for generalized flow maximization Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Formulas vs. circuits for small distance connectivity Benjamin Rossman |
Formulas vs. circuits for small distance connectivity Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Non-malleable codes from additive combinatorics Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett |
Non-malleable codes from additive combinatorics Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Coin flipping of any constant bias implies one-way functions Itay Berman, Iftach Haitner, Aris Tentes |
Coin flipping of any constant bias implies one-way functions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Polynomial bounds for the grid-minor theorem Chandra Chekuri, Julia Chuzhoy |
Polynomial bounds for the grid-minor theorem Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Pseudorandom generators with optimal seed length for non-boolean poly-size circuits Sergei Artemenko, Ronen Shaltiel |
Pseudorandom generators with optimal seed length for non-boolean poly-size circuits Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Communication lower bounds via critical block sensitivity Mika Göös, Toniann Pitassi |
Communication lower bounds via critical block sensitivity Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Distributed approximation algorithms for weighted shortest paths Danupon Nanongkai |
Distributed approximation algorithms for weighted shortest paths Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan |
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Exponential improvement in precision for simulating sparse Hamiltonians Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma |
Exponential improvement in precision for simulating sparse Hamiltonians Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Ning Chen, Nick Gravin, Pinyan Lu |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Constant factor approximation for balanced cut in the PIE model Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
Constant factor approximation for balanced cut in the PIE model Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Community detection thresholds and the weak Ramanujan property Laurent Massoulié |
Community detection thresholds and the weak Ramanujan property Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Linear time construction of compressed text indices in compact space Djamal Belazzougui |
Linear time construction of compressed text indices in compact space Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Carl A. Miller, Yaoyun Shi |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Deciding first-order properties of nowhere dense graphs Martin Grohe, Stephan Kreutzer, Sebastian Siebertz |
Deciding first-order properties of nowhere dense graphs Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Faster all-pairs shortest paths via circuit complexity Ryan Williams |
Faster all-pairs shortest paths via circuit complexity Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Efficient deterministic approximate counting for low-degree polynomial threshold functions Anindya De, Rocco A. Servedio |
Efficient deterministic approximate counting for low-degree polynomial threshold functions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The sample complexity of revenue maximization Richard Cole, Tim Roughgarden |
The sample complexity of revenue maximization Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The average sensitivity of an intersection of half spaces Daniel M. Kane |
The average sensitivity of an intersection of half spaces Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Bandits with switching costs: T2/3 regret Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres |
Bandits with switching costs: T2/3 regret Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region Andreas Galanis, Daniel Stefankovic, Eric Vigoda |
Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Communication is bounded by root of rank Shachar Lovett |
Communication is bounded by root of rank Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Every list-decodable code for high noise has abundant near-optimal rate puncturings Atri Rudra, Mary Wootters |
Every list-decodable code for high noise has abundant near-optimal rate puncturings Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Zachary Friggstad, Chaitanya Swamy |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Computing with a full memory: catalytic space Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman |
Computing with a full memory: catalytic space Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Approximate distance oracles with constant query time Shiri Chechik |
Approximate distance oracles with constant query time Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
New algorithms and lower bounds for circuits with linear threshold gates Ryan Williams |
New algorithms and lower bounds for circuits with linear threshold gates Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
The limits of depth reduction for arithmetic formulas: it's all about the top fan-in Mrinal Kumar, Shubhangi Saraf |
The limits of depth reduction for arithmetic formulas: it's all about the top fan-in Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time Michael T. Goodrich |
Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Shay Solomon |
Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Sungjin Im, Janardhan Kulkarni, Kamesh Munagala |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Infinite randomness expansion with a constant number of devices Matthew Coudron, Henry Yuen |
Infinite randomness expansion with a constant number of devices Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
How to use indistinguishability obfuscation: deniable encryption, and more Amit Sahai, Brent Waters |
How to use indistinguishability obfuscation: deniable encryption, and more Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Smoothed analysis of tensor decompositions Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan |
Smoothed analysis of tensor decompositions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Sergey Bravyi, Matthew B. Hastings |
Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma |
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
On the existence of extractable one-way functions Nir Bitansky, Ran Canetti, Omer Paneth, Alon Rosen |
On the existence of extractable one-way functions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Solving SDD linear systems in nearly mlog1/2n time Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, Shen Chen Xu |
Solving SDD linear systems in nearly mlog1/2n time Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The matching polytope has exponential extension complexity Thomas Rothvoß |
The matching polytope has exponential extension complexity Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Optimal CUR matrix decompositions Christos Boutsidis, David P. Woodruff |
Optimal CUR matrix decompositions Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
A characterization of strong approximation resistance Subhash Khot, Madhur Tulsiani, Pratik Worah |
A characterization of strong approximation resistance Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Distributed computability in Byzantine asynchronous systems Hammurabi Mendes, Christine Tasson, Maurice Herlihy |
Distributed computability in Byzantine asynchronous systems Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Turnstile streaming algorithms might as well be linear sketches Yi Li, Huy L. Nguyen, David P. Woodruff |
Turnstile streaming algorithms might as well be linear sketches Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Multiway cut, pairwise realizable distributions, and descending thresholds Ankit Sharma, Jan Vondrák |
Multiway cut, pairwise realizable distributions, and descending thresholds Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Are lock-free concurrent algorithms practically wait-free? Dan Alistarh, Keren Censor-Hillel, Nir Shavit |
Are lock-free concurrent algorithms practically wait-free? Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem Ken-ichi Kawarabayashi, Yusuke Kobayashi, Stephan Kreutzer |
An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
The power of localization for efficiently learning linear separators with noise Pranjal Awasthi, Maria-Florina Balcan, Philip M. Long |
The power of localization for efficiently learning linear separators with noise Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Efficient density estimation via piecewise polynomial approximation Siu-on Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun |
Efficient density estimation via piecewise polynomial approximation Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Online local learning via semidefinite programming Paul Christiano |
Online local learning via semidefinite programming Details |
|
Discussion Comments:
0
Verification:
Author has
not verified
information
|
|
Satisfiability threshold for random regular NAE-SAT Jian Ding, Allan Sly, Nike Sun |
Satisfiability threshold for random regular NAE-SAT Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Approximation algorithms for bipartite matching with metric and geometric costs Pankaj K. Agarwal, R. Sharathkumar |
Approximation algorithms for bipartite matching with metric and geometric costs Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
From average case complexity to improper learning complexity Amit Daniely, Nati Linial, Shai Shalev-Shwartz |
From average case complexity to improper learning complexity Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Breaking the quadratic barrier for 3-LCC's over the reals Zeev Dvir, Shubhangi Saraf, Avi Wigderson |
Breaking the quadratic barrier for 3-LCC's over the reals Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Optimal error rates for interactive coding I: adaptivity and other settings Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan |
Optimal error rates for interactive coding I: adaptivity and other settings Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|
|
Fourier PCA and robust tensor decomposition Navin Goyal, Santosh S. Vempala, Ying Xiao |
Fourier PCA and robust tensor decomposition Details |
|
Discussion Comments:
0
Verification:
Authors have
not verified
information
|