Title/Authors  Title  Research Artifacts
[?] A research
artifact is any byproduct 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, shellscripts 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 nosignaling proofs Yael Tauman Kalai, Ran Raz, Ron D. Rothblum 
How to delegate computations: the power of nosignaling proofs Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

Blackbox nonblackbox zero knowledge Vipul Goyal, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti 
Blackbox nonblackbox zero knowledge Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

Breaking the minskypapert barrier for constantdepth circuits Alexander A. Sherstov 
Breaking the minskypapert barrier for constantdepth 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 almostoptimally fair threeparty coinflipping protocol Iftach Haitner, Eliad Tsfadia 
An almostoptimally fair threeparty coinflipping protocol Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

The asymptotic kSAT threshold Amin CojaOghlan 
The asymptotic kSAT threshold Details 

Discussion Comments:
0
Verification:
Author has
not verified
information

A characterization of locally testable affineinvariant properties via decomposition theorems Yuichi Yoshida 
A characterization of locally testable affineinvariant 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, Kenichi 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 privacypreserving principal component analysis Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, Li Zhang 
Analyze gauss: optimal bounds for privacypreserving principal component analysis Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

Hitting sets for multilinear readonce algebraic branching programs, in any order Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka 
Hitting sets for multilinear readonce 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 minorfree graphs Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, Kunal Talwar 
Cops, robbers, and threatening skeletons: padded decomposition for minorfree 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 sumofsquares relaxations Boaz Barak, Jonathan A. Kelner, David Steurer 
Rounding sumofsquares 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 randomorder model Thomas Kesselheim, Klaus Radke, Andreas Tönnis, Berthold Vöcking 
Primal beats dual on online packing LPs in the randomorder 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 SiuWing 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 superpolynomial lower bound for regular arithmetic formulas Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi 
A superpolynomial lower bound for regular arithmetic formulas Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

Constant rank bimatrix games are PPADhard Ruta Mehta 
Constant rank bimatrix games are PPADhard 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

Nonmalleable codes from additive combinatorics Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett 
Nonmalleable codes from additive combinatorics Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

Coin flipping of any constant bias implies oneway functions Itay Berman, Iftach Haitner, Aris Tentes 
Coin flipping of any constant bias implies oneway functions Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

Polynomial bounds for the gridminor theorem Chandra Chekuri, Julia Chuzhoy 
Polynomial bounds for the gridminor theorem Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

Pseudorandom generators with optimal seed length for nonboolean polysize circuits Sergei Artemenko, Ronen Shaltiel 
Pseudorandom generators with optimal seed length for nonboolean polysize 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

Superpolynomial lower bounds for depth4 homogeneous arithmetic formulas Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan 
Superpolynomial lower bounds for depth4 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 firstorder properties of nowhere dense graphs Martin Grohe, Stephan Kreutzer, Sebastian Siebertz 
Deciding firstorder properties of nowhere dense graphs Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

Faster allpairs shortest paths via circuit complexity Ryan Williams 
Faster allpairs shortest paths via circuit complexity Details 

Discussion Comments:
0
Verification:
Author has
not verified
information

Efficient deterministic approximate counting for lowdegree polynomial threshold functions Anindya De, Rocco A. Servedio 
Efficient deterministic approximate counting for lowdegree 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: T^{2/3} regret Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres 
Bandits with switching costs: T^{2/3} regret Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region Andreas Galanis, Daniel Stefankovic, Eric Vigoda 
Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness 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 listdecodable code for high noise has abundant nearoptimal rate puncturings Atri Rudra, Mary Wootters 
Every listdecodable code for high noise has abundant nearoptimal 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 fanin Mrinal Kumar, Shubhangi Saraf 
The limits of depth reduction for arithmetic formulas: it's all about the top fanin Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

Zigzag sort: a simple deterministic dataoblivious sorting algorithm running in O(n log n) time Michael T. Goodrich 
Zigzag sort: a simple deterministic dataoblivious 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

Superpolylogarithmic hypergraph coloring hardness via lowdegree long codes Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma 
Superpolylogarithmic hypergraph coloring hardness via lowdegree long codes Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

On the existence of extractable oneway functions Nir Bitansky, Ran Canetti, Omer Paneth, Alon Rosen 
On the existence of extractable oneway functions Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

Solving SDD linear systems in nearly mlog^{1/2}n 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 mlog^{1/2}n 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 lockfree concurrent algorithms practically waitfree? Dan Alistarh, Keren CensorHillel, Nir Shavit 
Are lockfree concurrent algorithms practically waitfree? Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

An excluded halfintegral grid theorem for digraphs and the directed disjoint paths problem Kenichi Kawarabayashi, Yusuke Kobayashi, Stephan Kreutzer 
An excluded halfintegral 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, MariaFlorina 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 Siuon 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 NAESAT Jian Ding, Allan Sly, Nike Sun 
Satisfiability threshold for random regular NAESAT 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 ShalevShwartz 
From average case complexity to improper learning complexity Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information

Breaking the quadratic barrier for 3LCC's over the reals Zeev Dvir, Shubhangi Saraf, Avi Wigderson 
Breaking the quadratic barrier for 3LCC'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 Vempala, Ying Xiao 
Fourier PCA and robust tensor decomposition Details 

Discussion Comments:
0
Verification:
Authors have
not verified
information
