|
Indistinguishability Obfuscation from Functional Encryption
Nir Bitansky, Vinod Vaikuntanathan
|
Indistinguishability Obfuscation from Functional Encryption
Details
|
|
Verification:
Authors have
not verified
information
|
|
Symbolic Integration and the Complexity of Computing Averages
Leonard J. Schulman, Alistair Sinclair, Piyush Srivastava
|
Symbolic Integration and the Complexity of Computing Averages
Details
|
|
Verification:
Authors have
not verified
information
|
|
How to Refute a Random CSP
Sarah R. Allen, Ryan O'Donnell, David Witmer
|
How to Refute a Random CSP
Details
|
|
Author Comments:
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
Lower Bounds for Clique vs. Independent Set
Mika Göös
|
Lower Bounds for Clique vs. Independent Set
Details
|
|
Verification:
Author has
not verified
information
|
|
Heavy-Tailed Independent Component Analysis
Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher
|
Heavy-Tailed Independent Component Analysis
Details
|
|
Verification:
Authors have
not verified
information
|
|
Competitive Flow Time Algorithms for Polyhedral Scheduling
Sungjin Im, Janardhan Kulkarni, Kamesh Munagala
|
Competitive Flow Time Algorithms for Polyhedral Scheduling
Details
|
|
Verification:
Authors have
not verified
information
|
|
The Power of Asymmetry in Constant-Depth Circuits
Alexander A. Sherstov
|
The Power of Asymmetry in Constant-Depth Circuits
Details
|
|
Verification:
Author has
not verified
information
|
|
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
Yin Tat Lee, He Sun
|
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
Details
|
|
Verification:
Authors have
not verified
information
|
|
Online Buy-at-Bulk Network Design
Alina Ene, Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Debmalya Panigrahi
|
Online Buy-at-Bulk Network Design
Details
|
|
Verification:
Authors have
not verified
information
|
|
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
|
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
Details
|
|
Verification:
Authors have
not verified
information
|
|
The Submodular Secretary Problem Goes Linear
Moran Feldman, Rico Zenklusen
|
The Submodular Secretary Problem Goes Linear
Details
|
|
Verification:
Authors have
not verified
information
|
|
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong
|
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
Details
|
|
Verification:
Authors have
not verified
information
|
|
Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions
Vitaly Feldman, Jan Vondrák
|
Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions
Details
|
|
Verification:
Authors have
not verified
information
|
|
Approximately Counting Triangles in Sublinear Time
Talya Eden, Amit Levi, Dana Ron, C. Seshadhri
|
Approximately Counting Triangles in Sublinear Time
Details
|
|
Verification:
Authors have
not verified
information
|
|
Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption
Craig Gentry, Allison Bishop Lewko, Amit Sahai, Brent Waters
|
Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption
Details
|
|
Verification:
Authors have
not verified
information
|
|
Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems
Barna Saha
|
Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems
Details
|
|
Verification:
Author has
not verified
information
|
|
On Monotonicity Testing and Boolean Isoperimetric Type Theorems
Subhash Khot, Dor Minzer, Muli Safra
|
On Monotonicity Testing and Boolean Isoperimetric Type Theorems
Details
|
|
Verification:
Authors have
not verified
information
|
|
Quantum Expander Codes
Anthony Leverrier, Jean-Pierre Tillich, Gilles Zémor
|
Quantum Expander Codes
Details
|
|
Verification:
Authors have
not verified
information
|
|
On the Structure, Covering, and Learning of Poisson Multinomial Distributions
Constantinos Daskalakis, Gautam Kamath, Christos Tzamos
|
On the Structure, Covering, and Learning of Poisson Multinomial Distributions
Details
|
|
Verification:
Authors have
not verified
information
|
|
Compressing and Teaching for Low VC-Dimension
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff
|
Compressing and Teaching for Low VC-Dimension
Details
|
|
Author Comments:
Sharing:
Research produced no artifacts
Verification:
Authors have
verified
information
|
|
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
Karl Bringmann, Marvin Künnemann
|
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
Details
|
|
Verification:
Authors have
not verified
information
|
|
Tight Hardness of the Non-commutative Grothendieck Problem
Jop Briët, Oded Regev, Rishi Saket
|
Tight Hardness of the Non-commutative Grothendieck Problem
Details
|
|
Verification:
Authors have
not verified
information
|
|
Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs
Charles Bordenave, Marc Lelarge, Laurent Massoulié
|
Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs
Details
|
|
Verification:
Authors have
not verified
information
|
|
A Light Metric Spanner
Lee-Ad Gottlieb
|
A Light Metric Spanner
Details
|
|
Verification:
Author has
not verified
information
|
|
Optimal Induced Universal Graphs and Adjacency Labeling for Trees
Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen
|
Optimal Induced Universal Graphs and Adjacency Labeling for Trees
Details
|
|
Verification:
Authors have
not verified
information
|
|
Probabilistic Polynomials and Hamming Nearest Neighbors
Josh Alman, Ryan Williams
|
Probabilistic Polynomials and Hamming Nearest Neighbors
Details
|
|
Verification:
Authors have
not verified
information
|
|
An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles
Nicholas J. A. Harvey, Jan Vondrák
|
An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles
Details
|
|
Verification:
Authors have
not verified
information
|
|
Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable
Helmut Seidl, Sebastian Maneth, Gregor Kemper
|
Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable
Details
|
|
Verification:
Authors have
not verified
information
|
|
Robust Traceability from Trace Amounts
Cynthia Dwork, Adam D. Smith, Thomas Steinke, Jonathan Ullman, Salil P. Vadhan
|
Robust Traceability from Trace Amounts
Details
|
|
Verification:
Authors have
not verified
information
|
|
Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
Adam W. Marcus, Daniel A. Spielman, Nikhil Srivastava
|
Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
Details
|
|
Verification:
Authors have
not verified
information
|
|
Tight Bounds for Online Vector Scheduling
Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi
|
Tight Bounds for Online Vector Scheduling
Details
|
|
Verification:
Authors have
not verified
information
|
|
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms
Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
|
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms
Details
|
|
Verification:
Authors have
not verified
information
|
|
Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k
Radu Curticapean, Mingji Xia
|
Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k
Details
|
|
Verification:
Authors have
not verified
information
|
|
Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem
F. Bruce Shepherd, Adrian Vetta, Gordon T. Wilfong
|
Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem
Details
|
|
Verification:
Authors have
not verified
information
|
|
Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery
Emmanuel Abbe, Colin Sandon
|
Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery
Details
|
|
Verification:
Authors have
not verified
information
|
|
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
Nima Anari, Shayan Oveis Gharan
|
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
Details
|
|
Verification:
Authors have
not verified
information
|
|
Three-Source Extractors for Polylogarithmic Min-Entropy
Xin Li
|
Three-Source Extractors for Polylogarithmic Min-Entropy
Details
|
|
Verification:
Author has
not verified
information
|
|
Planar Reachability in Linear Space and Constant Time
Jacob Holm, Eva Rotenberg, Mikkel Thorup
|
Planar Reachability in Linear Space and Constant Time
Details
|
|
Verification:
Authors have
not verified
information
|
|
Pseudorandomness via the Discrete Fourier Transform
Parikshit Gopalan, Daniel M. Kane, Raghu Meka
|
Pseudorandomness via the Discrete Fourier Transform
Details
|
|
Verification:
Authors have
not verified
information
|
|
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters
Dominic W. Berry, Andrew M. Childs, Robin Kothari
|
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters
Details
|
|
Verification:
Authors have
not verified
information
|
|
Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks
John Augustine, Gopal Pandurangan, Peter Robinson, Scott T. Roche, Eli Upfal
|
Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks
Details
|
|
Verification:
Authors have
not verified
information
|
|
Efficient Inverse Maintenance and Faster Algorithms for Linear Programming
Yin Tat Lee, Aaron Sidford
|
Efficient Inverse Maintenance and Faster Algorithms for Linear Programming
Details
|
|
Verification:
Authors have
not verified
information
|
|
A Robust Sparse Fourier Transform in the Continuous Setting
Eric Price, Zhao Song
|
A Robust Sparse Fourier Transform in the Continuous Setting
Details
|
|
Verification:
Authors have
not verified
information
|
|
A Holant Dichotomy: Is the FKT Algorithm Universal?
Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams
|
A Holant Dichotomy: Is the FKT Algorithm Universal?
Details
|
|
Verification:
Authors have
not verified
information
|
|
Differentially Private Release and Learning of Threshold Functions
Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan
|
Differentially Private Release and Learning of Threshold Functions
Details
|
|
Verification:
Authors have
not verified
information
|
|
An O(1)-Approximation for Minimum Spanning Tree Interdiction
Rico Zenklusen
|
An O(1)-Approximation for Minimum Spanning Tree Interdiction
Details
|
|
Verification:
Author has
not verified
information
|
|
Sample (x) = (a*x<=t) is a Distinguisher with Probability 1/8
Mikkel Thorup
|
Sample (x) = (a*x<=t) is a Distinguisher with Probability 1/8
Details
|
|
Verification:
Author has
not verified
information
|
|
The Complexity of General-Valued CSPs
Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolinek
|
The Complexity of General-Valued CSPs
Details
|
|
Verification:
Authors have
not verified
information
|
|
Deterministic Communication vs. Partition Number
Mika Göös, Toniann Pitassi, Thomas Watson
|
Deterministic Communication vs. Partition Number
Details
|
|
Verification:
Authors have
not verified
information
|
|
Pattern-Avoiding Access in Binary Search Trees
Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak
|
Pattern-Avoiding Access in Binary Search Trees
Details
|
|
Verification:
Authors have
not verified
information
|
|
Approximate Modularity
Flavio Chierichetti, Abhimanyu Das, Anirban Dasgupta, Ravi Kumar
|
Approximate Modularity
Details
|
|
Verification:
Authors have
not verified
information
|
|
Mixture Selection, Mechanism Design, and Signaling
Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng
|
Mixture Selection, Mechanism Design, and Signaling
Details
|
|
Verification:
Authors have
not verified
information
|
|
No Small Linear Program Approximates Vertex Cover within a Factor 2 - e
Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, Ola Svensson
|
No Small Linear Program Approximates Vertex Cover within a Factor 2 - e
Details
|
|
Verification:
Authors have
not verified
information
|
|
Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums
Anindya De
|
Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums
Details
|
|
Verification:
Author has
not verified
information
|
|
Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!
Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz
|
Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!
Details
|
|
Verification:
Authors have
not verified
information
|
|
The Average Sensitivity of Bounded-Depth Formulas
Benjamin Rossman
|
The Average Sensitivity of Bounded-Depth Formulas
Details
|
|
Verification:
Author has
not verified
information
|
|
New Unconditional Hardness Results for Dynamic and Online Problems
Raphaël Clifford, Allan Grønlund, Kasper Green Larsen
|
New Unconditional Hardness Results for Dynamic and Online Problems
Details
|
|
Verification:
Authors have
not verified
information
|
|
Towards an Optimal Method for Dynamic Planar Point Location
Timothy M. Chan, Yakov Nekrich
|
Towards an Optimal Method for Dynamic Planar Point Location
Details
|
|
Verification:
Authors have
not verified
information
|
|
Black-Box Garbled RAM
Sanjam Garg, Steve Lu, Rafail Ostrovsky
|
Black-Box Garbled RAM
Details
|
|
Verification:
Authors have
not verified
information
|
|
Optimal Auctions vs. Anonymous Pricing
Saeed Alaei, Jason D. Hartline, Rad Niazadeh, Emmanouil Pountourakis, Yang Yuan
|
Optimal Auctions vs. Anonymous Pricing
Details
|
|
Verification:
Authors have
not verified
information
|
|
Input Sparsity and Hardness for Robust Subspace Approximation
Kenneth L. Clarkson, David P. Woodruff
|
Input Sparsity and Hardness for Robust Subspace Approximation
Details
|
|
Verification:
Authors have
not verified
information
|
|
Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable
Konstantin Makarychev, Yury Makarychev, Yuan Zhou
|
Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable
Details
|
|
Verification:
Authors have
not verified
information
|
|
Guaranteed Matrix Completion via Nonconvex Factorization
Ruoyu Sun, Zhi-Quan Luo
|
Guaranteed Matrix Completion via Nonconvex Factorization
Details
|
|
Verification:
Authors have
not verified
information
|
|
Uniform Generation of Random Regular Graphs
Pu Gao, Nicholas C. Wormald
|
Uniform Generation of Random Regular Graphs
Details
|
|
Verification:
Authors have
not verified
information
|
|
The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication
Erez Kantor, Zvi Lotker, Merav Parter, David Peleg
|
The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication
Details
|
|
Verification:
Authors have
not verified
information
|
|
Isomorphism Testing for Graphs of Bounded Rank Width
Martin Grohe, Pascal Schweitzer
|
Isomorphism Testing for Graphs of Bounded Rank Width
Details
|
|
Verification:
Authors have
not verified
information
|
|
Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness
Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette
|
Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness
Details
|
|
Verification:
Authors have
not verified
information
|
|
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
|
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
Details
|
|
Verification:
Authors have
not verified
information
|
|
Talagrand's Convolution Conjecture on Gaussian Space
Ronen Eldan, James R. Lee
|
Talagrand's Convolution Conjecture on Gaussian Space
Details
|
|
Verification:
Authors have
not verified
information
|
|
FO Model Checking on Posets of Bounded Width
Jakub Gajarský, Petr Hlinený, Daniel Lokshtanov, Jan Obdrzálek, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh
|
FO Model Checking on Posets of Bounded Width
Details
|
|
Verification:
Authors have
not verified
information
|
|
Random Matrices: l1 Concentration and Dictionary Learning with Few Samples
Kyle Luh, Van Vu
|
Random Matrices: l1 Concentration and Dictionary Learning with Few Samples
Details
|
|
Verification:
Authors have
not verified
information
|
|
Incidences between Points and Lines in R^4
Micha Sharir, Noam Solomon
|
Incidences between Points and Lines in R^4
Details
|
|
Verification:
Authors have
not verified
information
|
|
Breaking the Variance: Approximating the Hamming Distance in 1/ε Time Per Alignment
Tsvi Kopelowitz, Ely Porat
|
Breaking the Variance: Approximating the Hamming Distance in 1/ε Time Per Alignment
Details
|
|
Verification:
Authors have
not verified
information
|
|
Hashing for Statistics over K-Partitions
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup
|
Hashing for Statistics over K-Partitions
Details
|
|
Verification:
Authors have
not verified
information
|
|
Approximating ATSP by Relaxing Connectivity
Ola Svensson
|
Approximating ATSP by Relaxing Connectivity
Details
|
|
Verification:
Author has
not verified
information
|
|
Deterministic Divisibility Testing via Shifted Partial Derivatives
Michael A. Forbes
|
Deterministic Divisibility Testing via Shifted Partial Derivatives
Details
|
|
Verification:
Author has
not verified
information
|
|
Local Correlation Breakers and Applications to Three-Source Extractors and Mergers
Gil Cohen
|
Local Correlation Breakers and Applications to Three-Source Extractors and Mergers
Details
|
|
Verification:
Author has
not verified
information
|
|
Welfare Maximization with Limited Interaction
Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein
|
Welfare Maximization with Limited Interaction
Details
|
|
Verification:
Authors have
not verified
information
|
|
Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability
Eldar Fischer, Oded Lachish, Yadu Vasudev
|
Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability
Details
|
|
Verification:
Authors have
not verified
information
|
|
Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line
Amir Nayyeri, Benjamin Raichel
|
Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line
Details
|
|
Verification:
Authors have
not verified
information
|
|
If the Current Clique Algorithms are Optimal, So is Valiant's Parser
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
|
If the Current Clique Algorithms are Optimal, So is Valiant's Parser
Details
|
|
Verification:
Authors have
not verified
information
|
|
Limits on the Power of Indistinguishability Obfuscation and Functional Encryption
Gilad Asharov, Gil Segev
|
Limits on the Power of Indistinguishability Obfuscation and Functional Encryption
Details
|
|
Verification:
Authors have
not verified
information
|
|
On the Cryptographic Hardness of Finding a Nash Equilibrium
Nir Bitansky, Omer Paneth, Alon Rosen
|
On the Cryptographic Hardness of Finding a Nash Equilibrium
Details
|
|
Verification:
Authors have
not verified
information
|
|
Tight Hardness Results for LCS and Other Sequence Similarity Measures
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
|
Tight Hardness Results for LCS and Other Sequence Similarity Measures
Details
|
|
Verification:
Authors have
not verified
information
|
|
Robust Testing of Lifted Codes with Applications to Low-Degree Testing
Alan Guo, Elad Haramaty, Madhu Sudan
|
Robust Testing of Lifted Codes with Applications to Low-Degree Testing
Details
|
|
Verification:
Authors have
not verified
information
|
|
Hardness of Approximation in PSPACE and Separation Results for Pebble Games
Siu Man Chan, Massimo Lauria, Jakob Nordström, Marc Vinyals
|
Hardness of Approximation in PSPACE and Separation Results for Pebble Games
Details
|
|
Verification:
Authors have
not verified
information
|