|
Inapproximability of Nash Equilibrium
Aviad Rubinstein
|
Inapproximability of Nash Equilibrium
Details
|
|
Verification:
Author has
not verified
information
|
|
Preserving Statistical Validity in Adaptive Data Analysis
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Leon Roth
|
Preserving Statistical Validity in Adaptive Data Analysis
Details
|
|
Verification:
Authors have
not verified
information
|
|
FPTAS for #BIS with Degree Bounds on One Side
Jingcheng Liu, Pinyan Lu
|
FPTAS for #BIS with Degree Bounds on One Side
Details
|
|
Verification:
Authors have
not verified
information
|
|
Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract
Xiaorui Sun, John Wilmes
|
Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract
Details
|
|
Verification:
Authors have
not verified
information
|
|
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu
|
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
Details
|
|
Verification:
Authors have
not verified
information
|
|
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
Amit Daniely, Michael Schapira, Gal Shahaf
|
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
Details
|
|
Verification:
Authors have
not verified
information
|
|
Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
Zeyuan Allen Zhu, Zhenyu Liao, Lorenzo Orecchia
|
Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
Details
|
|
Verification:
Authors have
not verified
information
|
|
Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
Venkata Koppula, Allison Bishop Lewko, Brent Waters
|
Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
Details
|
|
Verification:
Authors have
not verified
information
|
|
Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev
|
Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
Details
|
|
Verification:
Authors have
not verified
information
|
|
Hardness of Graph Pricing Through Generalized Max-Dicut
Euiwoong Lee
|
Hardness of Graph Pricing Through Generalized Max-Dicut
Details
|
|
Verification:
Author has
not verified
information
|
|
Consistency Thresholds for the Planted Bisection Model
Elchanan Mossel, Joe Neeman, Allan Sly
|
Consistency Thresholds for the Planted Bisection Model
Details
|
|
Verification:
Authors have
not verified
information
|
|
Beyond the Euler Characteristic: Approximating the Genus of General Graphs
Ken-ichi Kawarabayashi, Anastasios Sidiropoulos
|
Beyond the Euler Characteristic: Approximating the Genus of General Graphs
Details
|
|
Verification:
Authors have
not verified
information
|
|
A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds
Amirali Abdullah, Suresh Venkatasubramanian
|
A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds
Details
|
|
Verification:
Authors have
not verified
information
|
|
Tight Bounds for Learning a Mixture of Two Gaussians
Moritz Hardt, Eric Price
|
Tight Bounds for Learning a Mixture of Two Gaussians
Details
|
|
Verification:
Authors have
not verified
information
|
|
Leveled Fully Homomorphic Signatures from Standard Lattices
Sergey Gorbunov, Vinod Vaikuntanathan, Daniel Wichs
|
Leveled Fully Homomorphic Signatures from Standard Lattices
Details
|
|
Verification:
Authors have
not verified
information
|
|
Exponential Separation of Information and Communication for Boolean Functions
Anat Ganor, Gillat Kol, Ran Raz
|
Exponential Separation of Information and Communication for Boolean Functions
Details
|
|
Verification:
Authors have
not verified
information
|
|
Sum of Squares Lower Bounds from Pairwise Independence
Boaz Barak, Siu On Chan, Pravesh K. Kothari
|
Sum of Squares Lower Bounds from Pairwise Independence
Details
|
|
Verification:
Authors have
not verified
information
|
|
Local, Private, Efficient Protocols for Succinct Histograms
Raef Bassily, Adam D. Smith
|
Local, Private, Efficient Protocols for Succinct Histograms
Details
|
|
Verification:
Authors have
not verified
information
|
|
The Directed Grid Theorem
Ken-ichi Kawarabayashi, Stephan Kreutzer
|
The Directed Grid Theorem
Details
|
|
Verification:
Authors have
not verified
information
|
|
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Boaz Barak, Jonathan A. Kelner, David Steurer
|
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Details
|
|
Verification:
Authors have
not verified
information
|
|
Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
Ankur Moitra
|
Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
Details
|
|
Verification:
Author has
not verified
information
|
|
Quantum Information Complexity
Dave Touchette
|
Quantum Information Complexity
Details
|
|
Verification:
Author has
not verified
information
|
|
Lower Bounds on the Size of Semidefinite Programming Relaxations
James R. Lee, Prasad Raghavendra, David Steurer
|
Lower Bounds on the Size of Semidefinite Programming Relaxations
Details
|
|
Verification:
Authors have
not verified
information
|
|
Lp Row Sampling by Lewis Weights
Michael B. Cohen, Richard Peng
|
Lp Row Sampling by Lewis Weights
Details
|
|
Verification:
Authors have
not verified
information
|
|
On the Complexity of Random Satisfiability Problems with Planted Solutions
Vitaly Feldman, Will Perkins, Santosh S. Vempala
|
On the Complexity of Random Satisfiability Problems with Planted Solutions
Details
|
|
Verification:
Authors have
not verified
information
|
|
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Charalampos E. Tsourakakis
|
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
Details
|
|
Verification:
Authors have
not verified
information
|
|
Sum-of-squares Lower Bounds for Planted Clique
Raghu Meka, Aaron Potechin, Avi Wigderson
|
Sum-of-squares Lower Bounds for Planted Clique
Details
|
|
Verification:
Authors have
not verified
information
|
|
Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract
Pravesh K. Kothari, Raghu Meka
|
Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract
Details
|
|
Verification:
Authors have
not verified
information
|
|
Sketching and Embedding are Equivalent for Norms
Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn
|
Sketching and Embedding are Equivalent for Norms
Details
|
|
Verification:
Authors have
not verified
information
|
|
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
Scott Aaronson, Andris Ambainis
|
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
Details
|
|
Verification:
Authors have
not verified
information
|
|
Greedy Algorithms for Steiner Forest
Anupam Gupta, Amit Kumar
|
Greedy Algorithms for Steiner Forest
Details
|
|
Verification:
Authors have
not verified
information
|
|
Computing with Tangles
Martin Grohe, Pascal Schweitzer
|
Computing with Tangles
Details
|
|
Verification:
Authors have
not verified
information
|
|
The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
Jakub Lacki, Jakub Ocwieja, Marcin Pilipczuk, Piotr Sankowski, Anna Zych
|
The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
Details
|
|
Verification:
Authors have
not verified
information
|
|
Non-malleable Reductions and Applications
Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, Maciej Obremski
|
Non-malleable Reductions and Applications
Details
|
|
Verification:
Authors have
not verified
information
|
|
Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm
Benjamin Cousins, Santosh S. Vempala
|
Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm
Details
|
|
Verification:
Authors have
not verified
information
|
|
Randomized Rounding for the Largest Simplex Problem
Aleksandar Nikolov
|
Randomized Rounding for the Largest Simplex Problem
Details
|
|
Verification:
Author has
not verified
information
|
|
Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyên
|
Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms
Details
|
|
Verification:
Authors have
not verified
information
|
|
Approximate k-flat Nearest Neighbor Search
Wolfgang Mulzer, Huy L. Nguyên, Paul Seiferth, Yannik Stein
|
Approximate k-flat Nearest Neighbor Search
Details
|
|
Verification:
Authors have
not verified
information
|
|
Adjacency Labeling Schemes and Induced-Universal Graphs
Stephen Alstrup, Haim Kaplan, Mikkel Thorup, Uri Zwick
|
Adjacency Labeling Schemes and Induced-Universal Graphs
Details
|
|
Verification:
Authors have
not verified
information
|
|
The communication complexity of interleaved group products
Timothy Gowers, Emanuele Viola
|
The communication complexity of interleaved group products
Details
|
|
Verification:
Authors have
not verified
information
|
|
Succinct Randomized Encodings and their Applications
Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, Sidharth Telang
|
Succinct Randomized Encodings and their Applications
Details
|
|
Verification:
Authors have
not verified
information
|
|
Prioritized Metric Structures and Embedding
Michael Elkin, Arnold Filtser, Ofer Neiman
|
Prioritized Metric Structures and Embedding
Details
|
|
Verification:
Authors have
not verified
information
|
|
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak
|
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Details
|
|
Verification:
Authors have
not verified
information
|
|
Optimal Data-Dependent Hashing for Approximate Near Neighbors
Alexandr Andoni, Ilya P. Razenshteyn
|
Optimal Data-Dependent Hashing for Approximate Near Neighbors
Details
|
|
Verification:
Authors have
not verified
information
|
|
Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
Siddharth Barman
|
Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
Details
|
|
Verification:
Author has
not verified
information
|
|
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu
|
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Details
|
|
Verification:
Authors have
not verified
information
|
|
The List Decoding Radius of Reed-Muller Codes over Small Fields
Abhishek Bhowmick, Shachar Lovett
|
The List Decoding Radius of Reed-Muller Codes over Small Fields
Details
|
|
Verification:
Authors have
not verified
information
|
|
Excluded Grid Theorem: Improved and Simplified
Julia Chuzhoy
|
Excluded Grid Theorem: Improved and Simplified
Details
|
|
Verification:
Author has
not verified
information
|
|
Succinct Garbling and Indistinguishability Obfuscation for RAM Programs
Ran Canetti, Justin Holmgren, Abhishek Jain, Vinod Vaikuntanathan
|
Succinct Garbling and Indistinguishability Obfuscation for RAM Programs
Details
|
|
Verification:
Authors have
not verified
information
|
|
Approximate Distance Oracles with Improved Bounds
Shiri Chechik
|
Approximate Distance Oracles with Improved Bounds
Details
|
|
Verification:
Author has
not verified
information
|
|
Efficiently Learning Ising Models on Arbitrary Graphs
Guy Bresler
|
Efficiently Learning Ising Models on Arbitrary Graphs
Details
|
|
Verification:
Author has
not verified
information
|
|
Quantum Spectrum Testing
Ryan O'Donnell, John Wright
|
Quantum Spectrum Testing
Details
|
|
Verification:
Authors have
not verified
information
|
|
On the Lovász Theta function for Independent Sets in Sparse Graphs
Nikhil Bansal, Anupam Gupta, Guru Guruganesh
|
On the Lovász Theta function for Independent Sets in Sparse Graphs
Details
|
|
Verification:
Authors have
not verified
information
|
|
Garbled RAM From One-Way Functions
Sanjam Garg, Steve Lu, Rafail Ostrovsky, Alessandra Scafuro
|
Garbled RAM From One-Way Functions
Details
|
|
Verification:
Authors have
not verified
information
|
|
On the Complexity of Nash Equilibria in Anonymous Games
Xi Chen, David Durfee, Anthi Orfanou
|
On the Complexity of Nash Equilibria in Anonymous Games
Details
|
|
Verification:
Authors have
not verified
information
|
|
Clustered Integer 3SUM via Additive Combinatorics
Timothy M. Chan, Moshe Lewenstein
|
Clustered Integer 3SUM via Additive Combinatorics
Details
|
|
Verification:
Authors have
not verified
information
|
|
The Complexity of the Simplex Method
John Fearnley, Rahul Savani
|
The Complexity of the Simplex Method
Details
|
|
Verification:
Authors have
not verified
information
|
|
Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
Ken-ichi Kawarabayashi, Mikkel Thorup
|
Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
Details
|
|
Verification:
Authors have
not verified
information
|
|
Small Value Parallel Repetition for General Games
Mark Braverman, Ankit Garg
|
Small Value Parallel Repetition for General Games
Details
|
|
Verification:
Authors have
not verified
information
|
|
Inapproximability of Combinatorial Problems via Small LPs and SDPs
Gábor Braun, Sebastian Pokutta, Daniel Zink
|
Inapproximability of Combinatorial Problems via Small LPs and SDPs
Details
|
|
Verification:
Authors have
not verified
information
|
|
Minimizing Flow-Time on Unrelated Machines
Nikhil Bansal, Janardhan Kulkarni
|
Minimizing Flow-Time on Unrelated Machines
Details
|
|
Verification:
Authors have
not verified
information
|
|
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
Arturs Backurs, Piotr Indyk
|
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
Details
|
|
Verification:
Authors have
not verified
information
|
|
Learning Mixtures of Gaussians in High Dimensions
Rong Ge, Qingqing Huang, Sham M. Kakade
|
Learning Mixtures of Gaussians in High Dimensions
Details
|
|
Verification:
Authors have
not verified
information
|
|
2-Server PIR with Sub-Polynomial Communication
Zeev Dvir, Sivakanth Gopi
|
2-Server PIR with Sub-Polynomial Communication
Details
|
|
Verification:
Authors have
not verified
information
|
|
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
Irit Dinur, Prahladh Harsha, Guy Kindler
|
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
Details
|
|
Verification:
Authors have
not verified
information
|
|
Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries
Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan
|
Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries
Details
|
|
Verification:
Authors have
not verified
information
|
|
Testing Cluster Structure of Graphs
Artur Czumaj, Pan Peng, Christian Sohler
|
Testing Cluster Structure of Graphs
Details
|
|
Verification:
Authors have
not verified
information
|
|
Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
Nitish Korula, Vahab S. Mirrokni, Morteza Zadimoghaddam
|
Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
Details
|
|
Verification:
Authors have
not verified
information
|
|
Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions
Shachar Lovett, Jiapeng Zhang
|
Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions
Details
|
|
Verification:
Authors have
not verified
information
|
|
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method
Andris Ambainis, Yuval Filmus, François Le Gall
|
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method
Details
|
|
Verification:
Authors have
not verified
information
|
|
Rectangles Are Nonnegative Juntas
Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman
|
Rectangles Are Nonnegative Juntas
Details
|
|
Verification:
Authors have
not verified
information
|
|
Sparse Quantum Codes from Quantum Circuits
Dave Bacon, Steven T. Flammia, Aram Wettroth Harrow, Jonathan Shi
|
Sparse Quantum Codes from Quantum Circuits
Details
|
|
Verification:
Authors have
not verified
information
|
|
A Characterization of the Capacity of Online (causal) Binary Channels
Zitan Chen, Sidharth Jaggi, Michael Langberg
|
A Characterization of the Capacity of Online (causal) Binary Channels
Details
|
|
Verification:
Authors have
not verified
information
|
|
Reed-Muller Codes for Random Erasures and Errors
Emmanuel Abbe, Amir Shpilka, Avi Wigderson
|
Reed-Muller Codes for Random Erasures and Errors
Details
|
|
Verification:
Authors have
not verified
information
|
|
An Interactive Information Odometer and Applications
Mark Braverman, Omri Weinstein
|
An Interactive Information Odometer and Applications
Details
|
|
Verification:
Authors have
not verified
information
|
|
From Independence to Expansion and Back Again
Tobias Christiani, Rasmus Pagh, Mikkel Thorup
|
From Independence to Expansion and Back Again
Details
|
|
Verification:
Authors have
not verified
information
|
|
Test-and-Set in Optimal Space
George Giakkoupis, Maryam Helmi, Lisa Higham, Philipp Woelfel
|
Test-and-Set in Optimal Space
Details
|
|
Verification:
Authors have
not verified
information
|
|
Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space
Jean Bourgain, Sjoerd Dirksen, Jelani Nelson
|
Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space
Details
|
|
Verification:
Authors have
not verified
information
|
|
Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian Sampling: Extended Abstract
Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
|
Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian Sampling: Extended Abstract
Details
|
|
Verification:
Authors have
not verified
information
|
|
Randomized Composable Core-sets for Distributed Submodular Maximization
Vahab S. Mirrokni, Morteza Zadimoghaddam
|
Randomized Composable Core-sets for Distributed Submodular Maximization
Details
|
|
Verification:
Authors have
not verified
information
|
|
Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
Zeyuan Allen Zhu, Lorenzo Orecchia
|
Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
Details
|
|
Verification:
Authors have
not verified
information
|
|
High Parallel Complexity Graphs and Memory-Hard Functions
Joël Alwen, Vladimir Serbinenko
|
High Parallel Complexity Graphs and Memory-Hard Functions
Details
|
|
Verification:
Authors have
not verified
information
|
|
Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
Anand Louis
|
Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
Details
|
|
Verification:
Author has
not verified
information
|
|
Analysis of a Classical Matrix Preconditioning Algorithm
Leonard J. Schulman, Alistair Sinclair
|
Analysis of a Classical Matrix Preconditioning Algorithm
Details
|
|
Verification:
Authors have
not verified
information
|
|
Random Permutations using Switching Networks
Artur Czumaj
|
Random Permutations using Switching Networks
Details
|
|
Verification:
Author has
not verified
information
|
|
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
Thomas Dueholm Hansen, Uri Zwick
|
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
Details
|
|
Verification:
Authors have
not verified
information
|
|
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
Kyle Fox, Philip N. Klein, Shay Mozes
|
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
Details
|
|
Author Comments:
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
Approximating the Nash Social Welfare with Indivisible Items
Richard Cole, Vasilis Gkatzelis
|
Approximating the Nash Social Welfare with Indivisible Items
Details
|
|
Verification:
Authors have
not verified
information
|
|
Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity
Ittai Abraham, Danny Dolev
|
Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity
Details
|
|
Verification:
Authors have
not verified
information
|
|
Proof of the Satisfiability Conjecture for Large k
Jian Ding, Allan Sly, Nike Sun
|
Proof of the Satisfiability Conjecture for Large k
Details
|
|
Verification:
Authors have
not verified
information
|
|
Secretary Problems with Non-Uniform Arrival Order
Thomas Kesselheim, Robert D. Kleinberg, Rad Niazadeh
|
Secretary Problems with Non-Uniform Arrival Order
Details
|
|
Verification:
Authors have
not verified
information
|