ACM Symposium on Discrete Algorithms, SODA 2016


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

Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields

Jean-François Biasse, Fang Song

Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields

Details
Discussion Comments: 0
Verification: Authors have not verified information

Beyond the Richter-Thomassen Conjecture

János Pach, Natan Rubin, Gábor Tardos

Beyond the Richter-Thomassen Conjecture

Details
Discussion Comments: 0
Verification: Authors have not verified information

Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation

Chandra Chekuri, Vivek Madan

Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Fast Approximation for Maximum Weight Matroid Intersection

Chandra Chekuri, Kent Quanrud

A Fast Approximation for Maximum Weight Matroid Intersection

Details
Discussion Comments: 0
Verification: Authors have not verified information

Jointly Private Convex Programming

Justin Hsu, Zhiyi Huang, Aaron Roth, Zhiwei Steven Wu

Jointly Private Convex Programming

Details
Discussion Comments: 0
Verification: Authors have not verified information

Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky

Timothy M. Chan, Ryan Williams

Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky

Details
Discussion Comments: 0
Verification: Authors have not verified information

Subexponential parameterized algorithm for Interval Completion

Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk

Subexponential parameterized algorithm for Interval Completion

Details
Discussion Comments: 0
Verification: Authors have not verified information

The matching problem has no small symmetric SDP

Gábor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink

The matching problem has no small symmetric SDP

Details
Discussion Comments: 0
Verification: Authors have not verified information

Focused Stochastic Local Search and the Lovász Local Lemma

Dimitris Achlioptas, Fotis Iliopoulos

Focused Stochastic Local Search and the Lovász Local Lemma

Details
Discussion Comments: 0
Verification: Authors have not verified information

Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

Amit Chakrabarti, Anthony Wirth

Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

Details
Discussion Comments: 0
Verification: Authors have not verified information

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

Mahdi Cheraghchi, Piotr Indyk

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

Details
Discussion Comments: 0
Verification: Authors have not verified information

Clustering time series under the Fréchet distance

Anne Driemel, Amer Krivosija, Christian Sohler

Clustering time series under the Fréchet distance

Details
Discussion Comments: 0
Verification: Authors have not verified information

Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture

Guillaume Chapuy, Guillem Perarnau

Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture

Details
Discussion Comments: 0
Verification: Authors have not verified information

Bounds for Random Constraint Satisfaction Problems via Spatial Coupling

Dimitris Achlioptas, Seyed Hamed Hassani, Nicolas Macris, Rüdiger L. Urbanke

Bounds for Random Constraint Satisfaction Problems via Spatial Coupling

Details
Discussion Comments: 0
Verification: Authors have not verified information

Communication Complexity of Permutation-Invariant Functions

Badih Ghazi, Pritish Kamath, Madhu Sudan

Communication Complexity of Permutation-Invariant Functions

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Undirected Graph Exploration with ⊝(log log n) Pebbles

Yann Disser, Jan Hackfeld, Max Klimm

Undirected Graph Exploration with ⊝(log log n) Pebbles

Details
Discussion Comments: 0
Verification: Authors have not verified information

Improved Approximation Algorithms for k-Submodular Function Maximization

Satoru Iwata, Shin-ichi Tanigawa, Yuichi Yoshida

Improved Approximation Algorithms for k-Submodular Function Maximization

Details
Discussion Comments: 0
Verification: Authors have not verified information

How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness

Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Maxwell Young

How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness

Details
Discussion Comments: 0
Verification: Authors have not verified information

On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion

Yair Bartal, Arnold Filtser, Ofer Neiman

On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion

Details
Discussion Comments: 0
Verification: Authors have not verified information

Make-to-Order Integrated Scheduling and Distribution

Yossi Azar, Amir Epstein, Lukasz Jez, Adi Vardi

Make-to-Order Integrated Scheduling and Distribution

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Fast and Simple Algorithm for Computing Approximate Euclidean Minimum Spanning Trees

Sunil Arya, David M. Mount

A Fast and Simple Algorithm for Computing Approximate Euclidean Minimum Spanning Trees

Details
Discussion Comments: 0
Verification: Authors have not verified information

Permutation patterns are hard to count

Scott Garrabrant, Igor Pak

Permutation patterns are hard to count

Details
Discussion Comments: 0
Verification: Authors have not verified information

Characterisation of Strongly Stable Matchings

Adam Kunysz, Katarzyna E. Paluch, Pratik Ghosal

Characterisation of Strongly Stable Matchings

Details
Discussion Comments: 0
Verification: Authors have not verified information

Deterministic Algorithms for Submodular Maximization Problems

Niv Buchbinder, Moran Feldman

Deterministic Algorithms for Submodular Maximization Problems

Details
Discussion Comments: 0
Verification: Authors have not verified information

Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile

Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee

Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile

Details
Discussion Comments: 0
Verification: Authors have not verified information

An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem

Christos Kalaitzis

An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem

Details
Discussion Comments: 0
Verification: Author has not verified information

Algorithms and Adaptivity Gaps for Stochastic Probing

Anupam Gupta, Viswanath Nagarajan, Sahil Singla

Algorithms and Adaptivity Gaps for Stochastic Probing

Details
Discussion Comments: 0
Verification: Authors have not verified information

New directions in nearest neighbor searching with applications to lattice sieving

Anja Becker, Léo Ducas, Nicolas Gama, Thijs Laarhoven

New directions in nearest neighbor searching with applications to lattice sieving

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced artifacts
Verification: Authors have verified information

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs

Andreas Galanis, Leslie Ann Goldberg

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Weak duality for packing edge-disjoint odd (u, v)-trails

Ross Churchley, Bojan Mohar, Hehui Wu

Weak duality for packing edge-disjoint odd (u, v)-trails

Details
Discussion Comments: 0
Verification: Authors have not verified information

Exact and Approximation Algorithms for Weighted Matroid Intersection

Chien-Chung Huang, Naonori Kakimura, Naoyuki Kamiyama

Exact and Approximation Algorithms for Weighted Matroid Intersection

Details
Discussion Comments: 0
Verification: Authors have not verified information

An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra

Robert Hildebrand, Robert Weismantel, Kevin Zemmer

An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sparsity and dimension

Gwenaël Joret, Piotr Micek, Veit Wiechert

Sparsity and dimension

Details
Discussion Comments: 0
Verification: Authors have not verified information

Finding Perfect Matchings in Bipartite Hypergraphs

Chidambaram Annamalai

Finding Perfect Matchings in Bipartite Hypergraphs

Details
Discussion Comments: 0
Verification: Author has not verified information

Nearly Optimal NP-Hardness of Unique Coverage

Venkatesan Guruswami, Euiwoong Lee

Nearly Optimal NP-Hardness of Unique Coverage

Details
Discussion Comments: 0
Verification: Authors have not verified information

Finding a Stable Allocation in Polymatroid Intersection

Satoru Iwata, Yu Yokoi

Finding a Stable Allocation in Polymatroid Intersection

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff

Christian Wulff-Nilsen

Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff

Details
Discussion Comments: 0
Verification: Author has not verified information

The k-mismatch problem revisited

Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, Tatiana A. Starikovskaya

The k-mismatch problem revisited

Details
Discussion Comments: 0
Verification: Authors have not verified information

Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting

Robert Ganian, M. S. Ramanujan, Stefan Szeider

Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximately Efficient Double Auctions with Strong Budget Balance

Riccardo Colini-Baldeschi, Bart de Keijzer, Stefano Leonardi, Stefano Turchetta

Approximately Efficient Double Auctions with Strong Budget Balance

Details
Discussion Comments: 0
Verification: Authors have not verified information

Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee

Shivam Garg, Geevarghese Philip

Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

On the Complexity of Dynamic Mechanism Design

Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein

On the Complexity of Dynamic Mechanism Design

Details
Discussion Comments: 0
Verification: Authors have not verified information

Local-on-Average Distributed Tasks

Merav Parter, David Peleg, Shay Solomon

Local-on-Average Distributed Tasks

Details
Discussion Comments: 0
Verification: Authors have not verified information

Distance in the Forest Fire Model How far are you from Eve?

Varun Kanade, Reut Levi, Zvi Lotker, Frederik Mallmann-Trenn, Claire Mathieu

Distance in the Forest Fire Model How far are you from Eve?

Details
Discussion Comments: 0
Verification: Authors have not verified information

Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching

Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, David P. Woodruff

Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching

Details
Discussion Comments: 0
Verification: Authors have not verified information

Simpler, faster and shorter labels for distances in graphs

Stephen Alstrup, Cyril Gavoille, Esben Bistrup Halvorsen, Holger Petersen

Simpler, faster and shorter labels for distances in graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Balanced Allocation: Patience is not a Virtue

John Augustine, William K. Moses Jr., Amanda Redlich, Eli Upfal

Balanced Allocation: Patience is not a Virtue

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Approximate Undirected Maximum Flows in O(mpolylog(n)) Time

Richard Peng

Approximate Undirected Maximum Flows in O(mpolylog(n)) Time

Details
Discussion Comments: 0
Verification: Author has not verified information

Communication with Contextual Uncertainty

Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan

Communication with Contextual Uncertainty

Details
Discussion Comments: 0
Verification: Authors have not verified information

Computing in continuous space with self-assembling polygonal tiles (extended abstract)

Oscar Gilbert, Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers

Computing in continuous space with self-assembling polygonal tiles (extended abstract)

Details
Discussion Comments: 0
Verification: Authors have not verified information

Improved Deterministic Algorithms for Linear Programming in Low Dimensions

Timothy M. Chan

Improved Deterministic Algorithms for Linear Programming in Low Dimensions

Details
Discussion Comments: 0
Verification: Author has not verified information

On the switch Markov chain for perfect matchings

Martin E. Dyer, Mark Jerrum, Haiko Müller

On the switch Markov chain for perfect matchings

Details
Discussion Comments: 0
Verification: Authors have not verified information

Faster Fully Dynamic Matchings with Small Approximation Ratios

Aaron Bernstein, Cliff Stein

Faster Fully Dynamic Matchings with Small Approximation Ratios

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Restricted Isometry Property of Subsampled Fourier Matrices

Ishay Haviv, Oded Regev

The Restricted Isometry Property of Subsampled Fourier Matrices

Details
Discussion Comments: 0
Verification: Authors have not verified information

Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution

David G. Harris, Aravind Srinivasan

Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution

Details
Discussion Comments: 0
Verification: Authors have not verified information

Obstructions for three-coloring graphs with one forbidden induced subgraph

Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong

Obstructions for three-coloring graphs with one forbidden induced subgraph

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique

Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique

Details
Discussion Comments: 0
Verification: Authors have not verified information

Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions

Mark Braverman, Jieming Mao, S. Matthew Weinberg

Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Locality-sensitive Hashing without False Negatives

Rasmus Pagh

Locality-sensitive Hashing without False Negatives

Details
Discussion Comments: 0
Verification: Author has not verified information

Gowers Norm, Function Limits, and Parameter Estimation

Yuichi Yoshida

Gowers Norm, Function Limits, and Parameter Estimation

Details
Discussion Comments: 0
Verification: Author has not verified information

Towards Optimal Deterministic Coding for Interactive Communication

Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson

Towards Optimal Deterministic Coding for Interactive Communication

Details
Discussion Comments: 0
Verification: Authors have not verified information

Higher Lower Bounds from the 3SUM Conjecture

Tsvi Kopelowitz, Seth Pettie, Ely Porat

Higher Lower Bounds from the 3SUM Conjecture

Details
Discussion Comments: 0
Verification: Authors have not verified information

Improved Approximation for Vector Bin Packing

Nikhil Bansal, Marek Eliás, Arindam Khan

Improved Approximation for Vector Bin Packing

Details
Discussion Comments: 0
Verification: Authors have not verified information

Online Degree-Bounded Steiner Network Design

Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat

Online Degree-Bounded Steiner Network Design

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Online Contention Resolution Schemes

Moran Feldman, Ola Svensson, Rico Zenklusen

Online Contention Resolution Schemes

Details
Discussion Comments: 0
Verification: Authors have not verified information

Algorithmic Complexity of Power Law Networks

Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski

Algorithmic Complexity of Power Law Networks

Details
Discussion Comments: 0
Verification: Authors have not verified information

An O(log m)-Competitive Algorithm for Online Machine Minimization

Lin Chen, Nicole Megow, Kevin Schewior

An O(log m)-Competitive Algorithm for Online Machine Minimization

Details
Discussion Comments: 0
Verification: Authors have not verified information

Better Distance Preservers and Additive Spanners

Greg Bodwin, Virginia Vassilevska Williams

Better Distance Preservers and Additive Spanners

Details
Discussion Comments: 0
Verification: Authors have not verified information

Near-Optimal Light Spanners

Shiri Chechik, Christian Wulff-Nilsen

Near-Optimal Light Spanners

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sparse Approximation via Generating Point Sets

Avrim Blum, Sariel Har-Peled, Benjamin Raichel

Sparse Approximation via Generating Point Sets

Details
Discussion Comments: 0
Verification: Authors have not verified information

Designing Networks with Good Equilibria under Uncertainty

George Christodoulou, Alkmini Sgouritsa

Designing Networks with Good Equilibria under Uncertainty

Details
Discussion Comments: 0
Verification: Authors have not verified information

Weighted dynamic finger in binary search trees

John Iacono, Stefan Langerman

Weighted dynamic finger in binary search trees

Details
Discussion Comments: 0
Verification: Authors have not verified information

Learning and Efficiency in Games with Dynamic Population

Thodoris Lykouris, Vasilis Syrgkanis, Éva Tardos

Learning and Efficiency in Games with Dynamic Population

Details
Discussion Comments: 0
Verification: Authors have not verified information

Discrete Gaussian Sampling Reduces to CVP and SVP

Noah Stephens-Davidowitz

Discrete Gaussian Sampling Reduces to CVP and SVP

Details
Discussion Comments: 0
Verification: Author has not verified information

Weighted SGD for p Regression with Randomized Preconditioning

Jiyan Yang, Yinlam Chow, Christopher Ré, Michael W. Mahoney

Weighted SGD for p Regression with Randomized Preconditioning

Details
Discussion Comments: 0
Verification: Authors have not verified information

Windrose Planarity: Embedding Graphs with Direction-Constrained Edges

Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Valentino Di Donato, Philipp Kindermann, Günter Rote, Ignaz Rutter

Windrose Planarity: Embedding Graphs with Direction-Constrained Edges

Details
Discussion Comments: 0
Verification: Authors have not verified information

Efficient Low-Redundancy Codes for Correcting Multiple Deletions

Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky

Efficient Low-Redundancy Codes for Correcting Multiple Deletions

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems

Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach, Michal Pilipczuk

Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Complexity of All-switches Strategy Improvement

John Fearnley, Rahul Savani

The Complexity of All-switches Strategy Improvement

Details
Discussion Comments: 0
Verification: Authors have not verified information

Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus

Radu Curticapean, Dániel Marx

Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus

Details
Discussion Comments: 0
Verification: Authors have not verified information

Evolutionary Dynamics in Finite Populations Mix Rapidly

Ioannis Panageas, Piyush Srivastava, Nisheeth K. Vishnoi

Evolutionary Dynamics in Finite Populations Mix Rapidly

Details
Discussion Comments: 0
Verification: Authors have not verified information

On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs

Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew V. Goldberg, Renato F. Werneck

On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities

Michael B. Cohen

Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities

Details
Discussion Comments: 0
Verification: Author has not verified information

On the Economic Efficiency of the Combinatorial Clock Auction

Nicolas Bousquet, Yang Cai, Christoph Hunkenschröder, Adrian Vetta

On the Economic Efficiency of the Combinatorial Clock Auction

Details
Discussion Comments: 0
Verification: Authors have not verified information

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

Details
Discussion Comments: 0
Verification: Authors have not verified information

Dynamic DFS in Undirected Graphs: breaking the O(m) barrier

Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, Shahbaz Khan

Dynamic DFS in Undirected Graphs: breaking the O(m) barrier

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions

Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer

Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Stabilizing Consensus with Many Opinions

Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan

Stabilizing Consensus with Many Opinions

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

The Adversarial Noise Threshold for Distributed Protocols

William M. Hoza, Leonard J. Schulman

The Adversarial Noise Threshold for Distributed Protocols

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Independence and Efficient Domination on P6-free Graphs

Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen

Independence and Efficient Domination on P6-free Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut

Mohsen Ghaffari, Bernhard Haeupler

Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut

Details
Discussion Comments: 0
Verification: Authors have not verified information

Time vs. Information Tradeoffs for Leader Election in Anonymous Trees

Christian Glacet, Avery Miller, Andrzej Pelc

Time vs. Information Tradeoffs for Leader Election in Anonymous Trees

Details
Discussion Comments: 0
Verification: Authors have not verified information

Treetopes and their Graphs

David Eppstein

Treetopes and their Graphs

Details
Discussion Comments: 0
Verification: Author has not verified information

The Power of Two Choices with Simple Tabulation

Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup

The Power of Two Choices with Simple Tabulation

Details
Discussion Comments: 0
Verification: Authors have not verified information

Tight Bounds for Graph Homomorphism and Subgraph Isomorphism

Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala

Tight Bounds for Graph Homomorphism and Subgraph Isomorphism

Details
Discussion Comments: 0
Verification: Authors have not verified information

Blocking Optimal k-Arborescences

Attila Bernáth, Tamás Király

Blocking Optimal k-Arborescences

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions

Xi Chen, Jinyu Xie

Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Linear Recognition of Almost Interval Graphs

Yixin Cao

Linear Recognition of Almost Interval Graphs

Details
Discussion Comments: 0
Verification: Author has not verified information

Recovery and Rigidity in a Regular Stochastic Block Model

Gerandy Brito, Ioana Dumitriu, Shirshendu Ganguly, Christopher Hoffman, Linh V. Tran

Recovery and Rigidity in a Regular Stochastic Block Model

Details
Discussion Comments: 0
Verification: Authors have not verified information

Partial Resampling to Approximate Covering Integer Programs

Antares Chen, David G. Harris, Aravind Srinivasan

Partial Resampling to Approximate Covering Integer Programs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Constructive algorithm for path-width of matroids

Jisu Jeong, Eun Jung Kim, Sang-il Oum

Constructive algorithm for path-width of matroids

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximation schemes for machine scheduling with resource (in-)dependent processing times

Klaus Jansen, Marten Maack, Malin Rau

Approximation schemes for machine scheduling with resource (in-)dependent processing times

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Authors have verified information

On approximating strip packing with a better ratio than 3/2

Giorgi Nadiradze, Andreas Wiese

On approximating strip packing with a better ratio than 3/2

Details
Discussion Comments: 0
Verification: Authors have not verified information

Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams

Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, Sofya Vorotnikova

Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams

Details
Discussion Comments: 0
Verification: Authors have not verified information

Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time

Kunal Agrawal, Jing Li, Kefu Lu, Benjamin Moseley

Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time

Details
Discussion Comments: 0
Verification: Authors have not verified information

Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach

David Peleg, Shay Solomon

Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the maximum quartet distance between phylogenetic trees

Noga Alon, Humberto Naves, Benny Sudakov

On the maximum quartet distance between phylogenetic trees

Details
Discussion Comments: 0
Verification: Authors have not verified information

Online Pricing with Impatient Bidders

Marek Cygan, Marcin Mucha, Piotr Sankowski, Qiang Zhang

Online Pricing with Impatient Bidders

Details
Discussion Comments: 0
Verification: Authors have not verified information

Canonical Paths for MCMC: from Art to Science

Lingxiao Huang, Pinyan Lu, Chihao Zhang

Canonical Paths for MCMC: from Art to Science

Details
Discussion Comments: 0
Verification: Authors have not verified information

Error Amplification for Pairwise Spanner Lower Bounds

Amir Abboud, Greg Bodwin

Error Amplification for Pairwise Spanner Lower Bounds

Details
Discussion Comments: 0
Verification: Authors have not verified information

Random-Cluster Dynamics in ℤ2

Antonio Blanca, Alistair Sinclair

Random-Cluster Dynamics in ℤ2

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximation of non-boolean 2CSP

Guy Kindler, Alexandra Kolla, Luca Trevisan

Approximation of non-boolean 2CSP

Details
Discussion Comments: 0
Verification: Authors have not verified information

Multiscale Mapper: Topological Summarization via Codomain Covers

Tamal K. Dey, Facundo Mémoli, Yusu Wang

Multiscale Mapper: Topological Summarization via Codomain Covers

Details
Discussion Comments: 0
Verification: Authors have not verified information

Markovian Hitters and the Complexity of Blind Rendezvous

Sixia Chen, Matthew Dippel, Alexander Russell, Abhishek Samanta, Ravi Sundaram

Markovian Hitters and the Complexity of Blind Rendezvous

Details
Discussion Comments: 0
Verification: Authors have not verified information

Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics

T.-H. Hubert Chan, Shaofeng H.-C. Jiang

Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics

Details
Discussion Comments: 0
Verification: Authors have not verified information

An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles

Pankaj K. Agarwal, Kyle Fox, Oren Salzman

An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles

Details
Discussion Comments: 0
Verification: Authors have not verified information

An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market

Ran Duan, Jugal Garg, Kurt Mehlhorn

An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximating the k-Level in Three-Dimensional Plane Arrangements

Sariel Har-Peled, Haim Kaplan, Micha Sharir

Approximating the k-Level in Three-Dimensional Plane Arrangements

Details
Discussion Comments: 0
Verification: Authors have not verified information

Simple Pricing Schemes For Consumers With Evolving Values

Shuchi Chawla, Nikhil R. Devanur, Anna R. Karlin, Balasubramanian Sivan

Simple Pricing Schemes For Consumers With Evolving Values

Details
Discussion Comments: 0
Verification: Authors have not verified information

Non-convex Compressed Sensing with the Sum-of-Squares Method

Tasuku Soma, Yuichi Yoshida

Non-convex Compressed Sensing with the Sum-of-Squares Method

Details
Discussion Comments: 0
Verification: Authors have not verified information

Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders

Xue Chen

Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders

Details
Discussion Comments: 0
Verification: Author has not verified information

Robust positioning patterns

Ross Berkowitz, Swastik Kopparty

Robust positioning patterns

Details
Discussion Comments: 0
Verification: Authors have not verified information

Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver

Zeyuan Allen Zhu, Yin Tat Lee, Lorenzo Orecchia

Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver

Details
Discussion Comments: 0
Verification: Authors have not verified information

Subtree Isomorphism Revisited

Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir

Subtree Isomorphism Revisited

Details
Discussion Comments: 0
Verification: Authors have not verified information

Directed multicut is W[1]-hard, even for four terminal pairs

Marcin Pilipczuk, Magnus Wahlström

Directed multicut is W[1]-hard, even for four terminal pairs

Details
Discussion Comments: 0
Verification: Authors have not verified information

An improved bound on the fraction of correctable deletions

Boris Bukh, Venkatesan Guruswami

An improved bound on the fraction of correctable deletions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Phase Transitions in Group Testing

Jonathan Scarlett, Volkan Cevher

Phase Transitions in Group Testing

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximating capacitated k-median with (1 + ∊)k open facilities

Shi Li

Approximating capacitated k-median with (1 + ∊)k open facilities

Details
Discussion Comments: 0
Verification: Author has not verified information

Range Predecessor and Lempel-Ziv Parsing

Djamal Belazzougui, Simon J. Puglisi

Range Predecessor and Lempel-Ziv Parsing

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sampling on Lattices with Free Boundary Conditions Using Randomized Extensions

Sarah Cannon, Dana Randall

Sampling on Lattices with Free Boundary Conditions Using Randomized Extensions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Persistent Homology and Nested Dissection

Michael Kerber, Donald R. Sheehy, Primoz Skraba

Persistent Homology and Nested Dissection

Details
Discussion Comments: 0
Verification: Authors have not verified information

Towards Optimal Algorithms for Prediction with Expert Advice

Nick Gravin, Yuval Peres, Balasubramanian Sivan

Towards Optimal Algorithms for Prediction with Expert Advice

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Faster Subquadratic Algorithm for Finding Outlier Correlations

Matti Karppa, Petteri Kaski, Jukka Kohonen

A Faster Subquadratic Algorithm for Finding Outlier Correlations

Details
Discussion Comments: 0
Verification: Authors have not verified information

Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model

Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev

Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs

Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Species Trees from Gene Trees Despite a High Rate of Lateral Genetic Transfer: A Tight Bound (Extended Abstract)

Constantinos Daskalakis, Sebastien Roch

Species Trees from Gene Trees Despite a High Rate of Lateral Genetic Transfer: A Tight Bound (Extended Abstract)

Details
Discussion Comments: 0
Verification: Authors have not verified information

An Improved Distributed Algorithm for Maximal Independent Set

Mohsen Ghaffari

An Improved Distributed Algorithm for Maximal Independent Set

Details
Discussion Comments: 0
Verification: Author has not verified information

Approximating Low-Stretch Spanners

Michael Dinitz, Zeyu Zhang

Approximating Low-Stretch Spanners

Details
Discussion Comments: 0
Verification: Authors have not verified information

Clustering Problems on Sliding Windows

Vladimir Braverman, Harry Lang, Keith Levin, Morteza Monemizadeh

Clustering Problems on Sliding Windows

Details
Discussion Comments: 0
Verification: Authors have not verified information

How to Round Subspaces: A New Spectral Clustering Algorithm

Ali Kemal Sinop

How to Round Subspaces: A New Spectral Clustering Algorithm

Details
Author Comments:
Discussion Comments: 0
Sharing: Research produced no artifacts
Verification: Author has verified information

Packing Small Vectors

Yossi Azar, Ilan Reuven Cohen, Amos Fiat, Alan Roytman

Packing Small Vectors

Details
Discussion Comments: 0
Verification: Authors have not verified information

An Algorithmic Hypergraph Regularity Lemma

Brendan Nagle, Vojtech Rödl, Mathias Schacht

An Algorithmic Hypergraph Regularity Lemma

Details
Discussion Comments: 0
Verification: Authors have not verified information

Expanders via Local Edge Flips

Zeyuan Allen Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab S. Mirrokni, Lorenzo Orecchia

Expanders via Local Edge Flips

Details
Discussion Comments: 0
Verification: Authors have not verified information

Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut

Chandra Chekuri, Vivek Madan

Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut

Details
Discussion Comments: 0
Verification: Authors have not verified information

New Bounds for Approximating Extremal Distances in Undirected Graphs

Massimo Cairo, Roberto Grossi, Romeo Rizzi

New Bounds for Approximating Extremal Distances in Undirected Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Natural Algorithms for Flow Problems

Damian Straszak, Nisheeth K. Vishnoi

Natural Algorithms for Flow Problems

Details
Discussion Comments: 0
Verification: Authors have not verified information