ACM Symposium on Discrete Algorithms, SODA 2014


The information below was collected semi-automatically. The authors have not yet been given the opportunity to verify the data.
[?] We ask all authors to verify the information we have about their papers, in particular the location of any supporting artifacts. We send out emails to authors asking them to update or verify this information incrementally, one conference at a time. For conferences where these emails have yet to be sent out we present the information in gray text.
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

Cutting corners cheaply, or how to remove Steiner points

Lior Kamma, Robert Krauthgamer, Huy L. Nguyen

Cutting corners cheaply, or how to remove Steiner points

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

Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles

Thomas Dueholm Hansen, Haim Kaplan, Uri Zwick

Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles

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

Making Octants Colorful and Related Covering Decomposition Problems

Jean Cardinal, Kolja B. Knauer, Piotr Micek, Torsten Ueckerdt

Making Octants Colorful and Related Covering Decomposition Problems

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

Approximating Local Homology from Samples

Primoz Skraba, Bei Wang

Approximating Local Homology from Samples

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

MCMC sampling colourings and independent sets of G(n, d/n) near uniqueness threshold

Charilaos Efthymiou

MCMC sampling colourings and independent sets of G(n, d/n) near uniqueness threshold

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

Dynamic Task Allocation in Asynchronous Shared Memory

Dan Alistarh, James Aspnes, Michael A. Bender, Rati Gelashvili, Seth Gilbert

Dynamic Task Allocation in Asynchronous Shared Memory

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

Approximating Minimum Cost Connectivity Orientation and Augmentation

Mohit Singh, László A. Végh

Approximating Minimum Cost Connectivity Orientation and Augmentation

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

Implicit Manifold Reconstruction

Siu-Wing Cheng, Man-Kwun Chiu

Implicit Manifold Reconstruction

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

Better Approximation Algorithms for the Graph Diameter

Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, Virginia Vassilevska Williams

Better Approximation Algorithms for the Graph Diameter

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

Clustering and Mixing Times for Segregation Models on ℤ2

Prateek Bhakta, Sarah Miracle, Dana Randall

Clustering and Mixing Times for Segregation Models on ℤ2

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

Faster Agreement via a Spectral Method for Detecting Malicious Behavior

Valerie King, Jared Saia

Faster Agreement via a Spectral Method for Detecting Malicious Behavior

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

First Come First Served for Online Slot Allocation and Huffman Coding

Monik Khare, Claire Mathieu, Neal E. Young

First Come First Served for Online Slot Allocation and Huffman Coding

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

Interval Deletion is Fixed-Parameter Tractable

Yixin Cao, Dániel Marx

Interval Deletion is Fixed-Parameter Tractable

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

Finding small patterns in permutations in linear time

Sylvain Guillemot, Dániel Marx

Finding small patterns in permutations in linear time

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

A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage

Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio

A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage

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

Testing Surface Area

Pravesh Kothari, Amir Nayyeri, Ryan O'Donnell, Chenggang Wu

Testing Surface Area

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

Constrained Signaling in Auction Design

Shaddin Dughmi, Nicole Immorlica, Aaron Roth

Constrained Signaling in Auction Design

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

Hereditary properties of permutations are strongly testable

Tereza Klimosova, Daniel Král'

Hereditary properties of permutations are strongly testable

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

A Simple FPTAS for Counting Edge Covers

Chengyu Lin, Jingcheng Liu, Pinyan Lu

A Simple FPTAS for Counting Edge Covers

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

A constructive algorithm for the Lovász Local Lemma on permutations

David G. Harris, Aravind Srinivasan

A constructive algorithm for the Lovász Local Lemma on permutations

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

Maintaining Assignments Online: Matching, Scheduling, and Flows

Anupam Gupta, Amit Kumar, Cliff Stein

Maintaining Assignments Online: Matching, Scheduling, and Flows

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

Improved Concentration Bounds for Count-Sketch

Gregory T. Minton, Eric Price

Improved Concentration Bounds for Count-Sketch

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

Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)

Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx

Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)

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

Model-based Sketching and Recovery with Expanders

Bubacarr Bah, Luca Baldassarre, Volkan Cevher

Model-based Sketching and Recovery with Expanders

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

Competitive Analysis via Regularization

Niv Buchbinder, Shahar Chen, Joseph Naor

Competitive Analysis via Regularization

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

Optimal Deterministic Shallow Cuttings for 3D Dominance Ranges

Peyman Afshani, Konstantinos Tsakalidis

Optimal Deterministic Shallow Cuttings for 3D Dominance Ranges

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

Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach

Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, Shi Li

Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach

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

Computing Cut-Based Hierarchical Decompositions in Almost Linear Time

Harald Räcke, Chintan Shah, Hanjo Täubig

Computing Cut-Based Hierarchical Decompositions in Almost Linear Time

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

Optimal Algorithms for Testing Closeness of Discrete Distributions

Siu-on Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant

Optimal Algorithms for Testing Closeness of Discrete Distributions

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

Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract

Will Ma

Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract

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

Disjoint Set Union with Randomized Linking

Ashish Goel, Sanjeev Khanna, Daniel H. Larkin, Robert Endre Tarjan

Disjoint Set Union with Randomized Linking

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

Beyond Locality-Sensitive Hashing

Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya P. Razenshteyn

Beyond Locality-Sensitive Hashing

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

Learning Entangled Single-Sample Gaussians

Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi

Learning Entangled Single-Sample Gaussians

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

The Complexity of Optimal Multidimensional Pricing

Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis

The Complexity of Optimal Multidimensional Pricing

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

A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median

MohammadTaghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha

A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median

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

Arboricity and spanning-tree packing in random graphs with an application to load balancing

Pu Gao, Xavier Pérez-Giménez, Cristiane M. Sato

Arboricity and spanning-tree packing in random graphs with an application to load balancing

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

Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids

Martin Dietzfelbinger, Philipp Woelfel

Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids

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

Non-Uniform Graph Partitioning

Robert Krauthgamer, Joseph Naor, Roy Schwartz, Kunal Talwar

Non-Uniform Graph Partitioning

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

Large induced subgraphs via triangulations and CMSO

Fedor V. Fomin, Ioan Todinca, Yngve Villanger

Large induced subgraphs via triangulations and CMSO

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

Approximating matching size from random streams

Michael Kapralov, Sanjeev Khanna, Madhu Sudan

Approximating matching size from random streams

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

Efficient quantum protocols for XOR functions

Shengyu Zhang

Efficient quantum protocols for XOR functions

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

A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension

Esther Ezra

A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension

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

Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms

Nikhil R. Devanur, Zhiyi Huang

Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms

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

Partitioning into Expanders

Shayan Oveis Gharan, Luca Trevisan

Partitioning into Expanders

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

Tight Bounds for Rumor Spreading with Vertex Expansion

George Giakkoupis

Tight Bounds for Rumor Spreading with Vertex Expansion

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

Better Approximation Bounds for the Joint Replenishment Problem

Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Dorian Nogneng, Jirí Sgall

Better Approximation Bounds for the Joint Replenishment Problem

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

Approximation Algorithm for Sparsest k-Partitioning

Anand Louis, Konstantin Makarychev

Approximation Algorithm for Sparsest k-Partitioning

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

On the compatibility of quartet trees

Noga Alon, Sagi Snir, Raphael Yuster

On the compatibility of quartet trees

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

Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball

Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Richard Peng, Noel Walkington

Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball

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

Robust Satisfiability of Systems of Equations

Peter Franek, Marek Krcál

Robust Satisfiability of Systems of Equations

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

An Optimal Lower Bound for Distinct Elements in the Message Passing Model

David P. Woodruff, Qin Zhang

An Optimal Lower Bound for Distinct Elements in the Message Passing Model

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

(Nearly) Sample-Optimal Sparse Fourier Transform

Piotr Indyk, Michael Kapralov, Eric Price

(Nearly) Sample-Optimal Sparse Fourier Transform

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

Hallucination Helps: Energy Efficient Virtual Circuit Routing

Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein

Hallucination Helps: Energy Efficient Virtual Circuit Routing

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

Approximation-Tolerant Model-Based Compressive Sensing

Chinmay Hegde, Piotr Indyk, Ludwig Schmidt

Approximation-Tolerant Model-Based Compressive Sensing

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

Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets

Venkatesan Guruswami, Chaoping Xing

Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets

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

Bicriteria data compression

Andrea Farruggia, Paolo Ferragina, Antonio Frangioni, Rossano Venturini

Bicriteria data compression

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

Learning Sparse Polynomial Functions

Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang

Learning Sparse Polynomial Functions

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

Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut

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

Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems

Samir Khuller, Manish Purohit, Kanthi K. Sarpatwar

Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems

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

Selection and Sorting in the "Restore" Model

Timothy M. Chan, J. Ian Munro, Venkatesh Raman

Selection and Sorting in the "Restore" Model

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

Influence Maximization in Undirected Networks

Sanjeev Khanna, Brendan Lucier

Influence Maximization in Undirected Networks

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

The Complexity of Optimal Mechanism Design

Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos

The Complexity of Optimal Mechanism Design

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

A New Perspective on Vertex Connectivity

Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn

A New Perspective on Vertex Connectivity

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

Fast Computation of Output-Sensitive Maxima in a Word RAM

Peyman Afshani

Fast Computation of Output-Sensitive Maxima in a Word RAM

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

Space complexity of list H-colouring: a dichotomy

László Egri, Pavol Hell, Benoit Larose, Arash Rafiey

Space complexity of list H-colouring: a dichotomy

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

Improved bounds and algorithms for graph cuts and network reliability

David G. Harris, Aravind Srinivasan

Improved bounds and algorithms for graph cuts and network reliability

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

A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices

Anna Adamaszek, Andreas Wiese

A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices

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

Improved Approximation Algorithm for Two-Dimensional Bin Packing

Nikhil Bansal, Arindam Khan

Improved Approximation Algorithm for Two-Dimensional Bin Packing

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

On Sketching Matrix Norms and the Top Singular Vector

Yi Li, Huy L. Nguyen, David P. Woodruff

On Sketching Matrix Norms and the Top Singular Vector

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

Fault Tolerant Approximate BFS Structures

Merav Parter, David Peleg

Fault Tolerant Approximate BFS Structures

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

Maximizing Bisubmodular and k-Submodular Functions

Justin Ward, Stanislav Zivny

Maximizing Bisubmodular and k-Submodular Functions

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

A Cubic Algorithm for Computing Gaussian Volume

Ben Cousins, Santosh Vempala

A Cubic Algorithm for Computing Gaussian Volume

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

On the Lattice Isomorphism Problem

Ishay Haviv, Oded Regev

On the Lattice Isomorphism Problem

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

Positivity Problems for Low-Order Linear Recurrence Sequences

Joël Ouaknine, James Worrell

Positivity Problems for Low-Order Linear Recurrence Sequences

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

Testing equivalence between distributions using conditional samples

Clément L. Canonne, Dana Ron, Rocco A. Servedio

Testing equivalence between distributions using conditional samples

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

Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs

Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou

Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs

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

Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh

Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms

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

Polynomiality for Bin Packing with a Constant Number of Item Types

Michel X. Goemans, Thomas Rothvoß

Polynomiality for Bin Packing with a Constant Number of Item Types

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

Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity

Yutaro Yamaguchi

Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity

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

Causal Erasure Channels

Raef Bassily, Adam D. Smith

Causal Erasure Channels

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

Annotations for Sparse Data Streams

Amit Chakrabarti, Graham Cormode, Navin Goyal, Justin Thaler

Annotations for Sparse Data Streams

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

Point Line Cover: The Easy Kernel is Essentially Tight

Stefan Kratsch, Geevarghese Philip, Saurabh Ray

Point Line Cover: The Easy Kernel is Essentially Tight

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

Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time

Andreas Björklund, Petteri Kaski, Lukasz Kowalik

Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time

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

Towards (1 + )-Approximate Flow Sparsifiers

Alexandr Andoni, Anupam Gupta, Robert Krauthgamer

Towards (1 + )-Approximate Flow Sparsifiers

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

An Excluded Grid Theorem for Digraphs with Forbidden Minors

Ken-ichi Kawarabayashi, Stephan Kreutzer

An Excluded Grid Theorem for Digraphs with Forbidden Minors

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

Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b-Matching Problems in Nonbipartite Graphs

Kook Jin Ahn, Sudipto Guha

Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b-Matching Problems in Nonbipartite Graphs

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

Finding orthogonal vectors in discrete structures

Ryan Williams, Huacheng Yu

Finding orthogonal vectors in discrete structures

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

Cache-Adaptive Algorithms

Michael A. Bender, Roozbeh Ebrahimi, Jeremy T. Fineman, Golnaz Ghasemiesfeh, Rob Johnson, Samuel McCauley

Cache-Adaptive Algorithms

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

Near-optimal labeling schemes for nearest common ancestors

Stephen Alstrup, Esben Bistrup Halvorsen, Kasper Green Larsen

Near-optimal labeling schemes for nearest common ancestors

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

Submodular Maximization with Cardinality Constraints

Niv Buchbinder, Moran Feldman, Joseph Naor, Roy Schwartz

Submodular Maximization with Cardinality Constraints

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

An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations

Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, Aaron Sidford

An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations

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

Pipage Rounding, Pessimistic Estimators and Matrix Concentration

Nicholas J. A. Harvey, Neil Olver

Pipage Rounding, Pessimistic Estimators and Matrix Concentration

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

On the optimality of approximation schemes for the classical scheduling problem

Lin Chen, Klaus Jansen, Guochuan Zhang

On the optimality of approximation schemes for the classical scheduling problem

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

The Generalized Terminal Backup Problem

Attila Bernáth, Yusuke Kobayashi

The Generalized Terminal Backup Problem

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

A Mazing 2+ Approximation for Unsplittable Flow on a Path

Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, Andreas Wiese

A Mazing 2+ Approximation for Unsplittable Flow on a Path

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

Fast algorithms for maximizing submodular functions

Ashwinkumar Badanidiyuru, Jan Vondrák

Fast algorithms for maximizing submodular functions

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

Intrinsic universality in tile self-assembly requires cooperation

Pierre-Etienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, Damien Woods

Intrinsic universality in tile self-assembly requires cooperation

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

The Complexity of Order Type Isomorphism

Greg Aloupis, John Iacono, Stefan Langerman, Özgür Özkan, Stefanie Wuhrer

The Complexity of Order Type Isomorphism

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

Maximizing Social Influence in Nearly Optimal Time

Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Brendan Lucier

Maximizing Social Influence in Nearly Optimal Time

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

Exploiting Metric Structure for Efficient Private Query Release

Zhiyi Huang, Aaron Roth

Exploiting Metric Structure for Efficient Private Query Release

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

Half-integrality, LP-branching and FPT Algorithms

Magnus Wahlström

Half-integrality, LP-branching and FPT Algorithms

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

Concurrent Range Reporting in Two-Dimensional Space

Peyman Afshani, Cheng Sheng, Yufei Tao, Bryan T. Wilkinson

Concurrent Range Reporting in Two-Dimensional Space

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

Minimum d-dimensional arrangement with fixed points

Anupam Gupta, Anastasios Sidiropoulos

Minimum d-dimensional arrangement with fixed points

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

A Near-Optimal Planarization Algorithm

Bart M. P. Jansen, Daniel Lokshtanov, Saket Saurabh

A Near-Optimal Planarization Algorithm

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

New constructions of RIP matrices with fast multiplication and fewer rows

Jelani Nelson, Eric Price, Mary Wootters

New constructions of RIP matrices with fast multiplication and fewer rows

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

Uniform random sampling of simple branched coverings of the sphere by itself

Enrica Duchi, Dominique Poulalhon, Gilles Schaeffer

Uniform random sampling of simple branched coverings of the sphere by itself

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

Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover

Amol Deshpande, Lisa Hellerstein, Devorah Kletenik

Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover

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

Flow-Based Algorithms for Local Graph Clustering

Lorenzo Orecchia, Zeyuan Allen Zhu

Flow-Based Algorithms for Local Graph Clustering

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

Smoothed Analysis of Local Search for the Maximum-Cut Problem

Michael Etscheid, Heiko Röglin

Smoothed Analysis of Local Search for the Maximum-Cut Problem

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

Online Steiner Tree with Deletions

Anupam Gupta, Amit Kumar

Online Steiner Tree with Deletions

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

Integer quadratic programming in the plane

Alberto Del Pia, Robert Weismantel

Integer quadratic programming in the plane

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

On Computability of Equilibria in Markets with Production

Jugal Garg, Vijay V. Vazirani

On Computability of Equilibria in Markets with Production

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

Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints

T.-H. Hubert Chan, Fei Chen, Xiaowei Wu, Zhichao Zhao

Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints

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

New Approximations for Reordering Buffer Management

Sungjin Im, Benjamin Moseley

New Approximations for Reordering Buffer Management

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

Improved upper bounds for Random-Edge and Random-Jump on abstract cubes

Thomas Dueholm Hansen, Mike Paterson, Uri Zwick

Improved upper bounds for Random-Edge and Random-Jump on abstract cubes

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

Streaming Balanced Graph Partitioning Algorithms for Random Graphs

Isabelle Stanton

Streaming Balanced Graph Partitioning Algorithms for Random Graphs

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

A subexponential parameterized algorithm for Subset TSP on planar graphs

Philip N. Klein, Dániel Marx

A subexponential parameterized algorithm for Subset TSP on planar graphs

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

Independent Set in P5-Free Graphs in Polynomial Time

Daniel Lokshantov, Martin Vatshelle, Yngve Villanger

Independent Set in P5-Free Graphs in Polynomial Time

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

Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs

Wang Chi Cheung, Michel X. Goemans, Sam Chiu-wai Wong

Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs

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

Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs

Subhash Khot, Rishi Saket

Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs

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

Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems

Bundit Laekhanukit

Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems

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

Polynomial Solvability of Variants of the Trust-Region Subproblem

Daniel Bienstock, Alexander Michalka

Polynomial Solvability of Variants of the Trust-Region Subproblem

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

Broadcast Throughput in Radio Networks: Routing vs. Network Coding

Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian

Broadcast Throughput in Radio Networks: Routing vs. Network Coding

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

Prophet Inequalities with Limited Information

Pablo Daniel Azar, Robert Kleinberg, S. Matthew Weinberg

Prophet Inequalities with Limited Information

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

Optimization Despite Chaos: Convex Relaxations to Complex Limit Sets via Poincaré Recurrence

Georgios Piliouras, Jeff S. Shamma

Optimization Despite Chaos: Convex Relaxations to Complex Limit Sets via Poincaré Recurrence

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

Timing in chemical reaction networks

David Doty

Timing in chemical reaction networks

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

Four Soviets Walk the Dog - with an Application to Alt's Conjecture

Kevin Buchin, Maike Buchin, Wouter Meulemans, Wolfgang Mulzer

Four Soviets Walk the Dog - with an Application to Alt's Conjecture

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

Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts

M. S. Ramanujan, Saket Saurabh

Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts

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

A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths

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

Hypercontractive inequalities via SOS, and the Frankl-Rödl graph

Manuel Kauers, Ryan O'Donnell, Li-Yang Tan, Yuan Zhou

Hypercontractive inequalities via SOS, and the Frankl-Rödl graph

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

Approximating k-center in planar graphs

David Eisenstat, Philip N. Klein, Claire Mathieu

Approximating k-center in planar graphs

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

Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable

Laurent Bulteau, Christian Komusiewicz

Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable

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

Linear-Time FPT Algorithms via Network Flow

Yoichi Iwata, Keigo Oka, Yuichi Yoshida

Linear-Time FPT Algorithms via Network Flow

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

Polynomial time approximation schemes for the traveling repairman and other minimum latency problems

René Sitters

Polynomial time approximation schemes for the traveling repairman and other minimum latency problems

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

Relative Errors for Deterministic Low-Rank Matrix Approximations

Mina Ghashami, Jeff M. Phillips

Relative Errors for Deterministic Low-Rank Matrix Approximations

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

On the Computational Complexity of Betti Numbers: Reductions from Matrix Rank

Herbert Edelsbrunner, Salman Parsa

On the Computational Complexity of Betti Numbers: Reductions from Matrix Rank

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