ACM Symposium on Discrete Algorithms, SODA 2015


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

Testing Identity of Structured Distributions

Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin

Testing Identity of Structured Distributions

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

Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter

Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams

Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter

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

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Chidambaram Annamalai, Christos Kalaitzis, Ola Svensson

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

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

The Polyhedron-Hitting Problem

Ventsislav Chonev, Joël Ouaknine, James Worrell

The Polyhedron-Hitting Problem

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

The optimal absolute ratio for online bin packing

János Balogh, József Békési, György Dósa, Jirí Sgall, Rob van Stee

The optimal absolute ratio for online bin packing

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

On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves

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

On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves

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

Sperner's Colorings, Hypergraph Labeling Problems and Fair Division

Maryam Mirzakhani, Jan Vondrák

Sperner's Colorings, Hypergraph Labeling Problems and Fair Division

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

A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs

Michael Elkin, Seth Pettie

A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs

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

The Speed of Evolution

Nisheeth K. Vishnoi

The Speed of Evolution

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

Zigzag Persistence via Reflections and Transpositions

Clément Maria, Steve Y. Oudot

Zigzag Persistence via Reflections and Transpositions

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

On largest volume simplices and sub-determinants

Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, Carsten Moldenhauer

On largest volume simplices and sub-determinants

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

Welfare Maximization with Production Costs: A Primal Dual Approach

Zhiyi Huang, Anthony Kim

Welfare Maximization with Production Costs: A Primal Dual Approach

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

Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovász Local Lemma

David G. Harris

Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovász Local Lemma

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

Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels

Bart M. P. Jansen, Dániel Marx

Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels

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

The amortized cost of finding the minimum

Haim Kaplan, Or Zamir, Uri Zwick

The amortized cost of finding the minimum

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

Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms

Constantinos Daskalakis, S. Matthew Weinberg

Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms

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

Parameterized Streaming: Maximal Matching and Vertex Cover

Rajesh Hemant Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, Morteza Monemizadeh

Parameterized Streaming: Maximal Matching and Vertex Cover

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

Tight lower bound for the channel assignment problem

Arkadiusz Socala

Tight lower bound for the channel assignment problem

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

Tight Bounds on Vertex Connectivity Under Vertex Sampling

Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn

Tight Bounds on Vertex Connectivity Under Vertex Sampling

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

The size of the core in assignment markets

Yash Kanoria, Daniela Sabán, Jay Sethuraman

The size of the core in assignment markets

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

Four terminal planar Delta-Wye reducibility via rooted K2, 4 minors

Lino Demasi, Bojan Mohar

Four terminal planar Delta-Wye reducibility via rooted K2, 4 minors

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

Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading

Zeyu Guo, He Sun

Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading

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

A dynamic model of barter exchange

Ross Anderson, Itai Ashlagi, David Gamarnik, Yash Kanoria

A dynamic model of barter exchange

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

Approximate resilience, monotonicity, and the complexity of agnostic learning

Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, Karl Wimmer

Approximate resilience, monotonicity, and the complexity of agnostic learning

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

Streaming Lower Bounds for Approximating MAX-CUT

Michael Kapralov, Sanjeev Khanna, Madhu Sudan

Streaming Lower Bounds for Approximating MAX-CUT

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

Geometric k Shortest Paths

Sylvester David Eriksson-Bique, John Hershberger, Valentin Polishchuk, Bettina Speckmann, Subhash Suri, Topi Talvitie, Kevin Verbeek, Hakan Yildiz

Geometric k Shortest Paths

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

Robust randomized matchings

Jannik Matuschke, Martin Skutella, José A. Soto

Robust randomized matchings

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

Compatible Connectivity-Augmentation of Planar Disconnected Graphs

Greg Aloupis, Luis Barba, Paz Carmi, Vida Dujmovic, Fabrizio Frati, Pat Morin

Compatible Connectivity-Augmentation of Planar Disconnected Graphs

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

On (1, )-Restricted Assignment Makespan Minimization

Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li

On (1, )-Restricted Assignment Makespan Minimization

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

A Unified Framework for Clustering Constrained Data without Locality Property

Hu Ding, Jinhui Xu

A Unified Framework for Clustering Constrained Data without Locality Property

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

Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

Venkatesan Guruswami, Euiwoong Lee

Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

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

An algorithmic framework for obtaining lower bounds for random Ramsey problems extended abstract

Rajko Nenadov, Nemanja Skoric, Angelika Steger

An algorithmic framework for obtaining lower bounds for random Ramsey problems extended abstract

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

On the Quickest Flow Problem in Dynamic Networks - A Parametric Min-Cost Flow Approach

Maokai Lin, Patrick Jaillet

On the Quickest Flow Problem in Dynamic Networks - A Parametric Min-Cost Flow Approach

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

Surprise probabilities in Markov chains

James Norris, Yuval Peres, Alex Zhai

Surprise probabilities in Markov chains

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

Spider covers for prize-collecting network activation problem

Takuro Fukunaga

Spider covers for prize-collecting network activation problem

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

New Approximations for Broadcast Scheduling via Variants of α-point Rounding

Sungjin Im, Maxim Sviridenko

New Approximations for Broadcast Scheduling via Variants of α-point Rounding

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

Internal Pattern Matching Queries in a Text and Applications

Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen

Internal Pattern Matching Queries in a Text and Applications

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

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

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

An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization

Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, Khoa Trinh

An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization

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

Approximating Hereditary Discrepancy via Small Width Ellipsoids

Aleksandar Nikolov, Kunal Talwar

Approximating Hereditary Discrepancy via Small Width Ellipsoids

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

Plurality Consensus in the Gossip Model

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

Plurality Consensus in the Gossip Model

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

Fast Generation of Random Spanning Trees and the Effective Resistance Metric

Aleksander Madry, Damian Straszak, Jakub Tarnawski

Fast Generation of Random Spanning Trees and the Effective Resistance Metric

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

Distributed Computation of Large-scale Graph Problems

Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson

Distributed Computation of Large-scale Graph Problems

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

The Complexity of Estimating Rényi Entropy

Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, Himanshu Tyagi

The Complexity of Estimating Rényi Entropy

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

Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel

Julian Shun, Yan Gu, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons

Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel

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

Rejecting jobs to Minimize Load and Maximum Flow-time

Anamitra Roy Choudhury, Syamantak Das, Naveen Garg, Amit Kumar

Rejecting jobs to Minimize Load and Maximum Flow-time

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

Tighter Low-rank Approximation via Sampling the Leveraged Element

Srinadh Bhojanapalli, Prateek Jain, Sujay Sanghavi

Tighter Low-rank Approximation via Sampling the Leveraged Element

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

On the Complexity of Computing an Equilibrium in Combinatorial Auctions

Shahar Dobzinski, Hu Fu, Robert D. Kleinberg

On the Complexity of Computing an Equilibrium in Combinatorial Auctions

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

Speeding up the Four Russians Algorithm by About One More Logarithmic Factor

Timothy M. Chan

Speeding up the Four Russians Algorithm by About One More Logarithmic Factor

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

Optimal detection of intersections between convex polyhedra

Luis Barba, Stefan Langerman

Optimal detection of intersections between convex polyhedra

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

Approximate Nearest Line Search in High Dimensions

Sepideh Mahabadi

Approximate Nearest Line Search in High Dimensions

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

More Applications of the Polynomial Method to Algorithm Design

Amir Abboud, Richard Ryan Williams, Huacheng Yu

More Applications of the Polynomial Method to Algorithm Design

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

The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games

Krishnendu Chatterjee, Rasmus Ibsen-Jensen

The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games

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

Phase Transitions in Random Dyadic Tilings and Rectangular Dissections

Sarah Cannon, Sarah Miracle, Dana Randall

Phase Transitions in Random Dyadic Tilings and Rectangular Dissections

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

Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy)

Sampath Kannan, Jamie Morgenstern, Aaron Roth, Zhiwei Steven Wu

Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy)

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

Degree-3 Treewidth Sparsifiers

Chandra Chekuri, Julia Chuzhoy

Degree-3 Treewidth Sparsifiers

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

A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem

Anna Adamaszek, Andreas Wiese

A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem

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

New Approximation Schemes for Unsplittable Flow on a Path

Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, Andreas Wiese

New Approximation Schemes for Unsplittable Flow on a Path

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

Combinatorial Auctions via Posted Prices

Michal Feldman, Nick Gravin, Brendan Lucier

Combinatorial Auctions via Posted Prices

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

Pricing Online Decisions: Beyond Auctions

Ilan Reuven Cohen, Alon Eden, Amos Fiat, Lukasz Jez

Pricing Online Decisions: Beyond Auctions

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

Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties

Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri

Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties

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

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching

Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching

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

Triangulation Refinement and Approximate Shortest Paths in Weighted Regions

Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron

Triangulation Refinement and Approximate Shortest Paths in Weighted Regions

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

An exact characterization of tractable demand patterns for maximum disjoint path problems

Dániel Marx, Paul Wollan

An exact characterization of tractable demand patterns for maximum disjoint path problems

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

Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond

Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, Krzysztof Onak

Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond

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

A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem

Moran Feldman, Ola Svensson, Rico Zenklusen

A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem

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

Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems

Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, Joachim Spoerhase

Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems

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

The matching polytope does not admit fully-polynomial size relaxation schemes

Gábor Braun, Sebastian Pokutta

The matching polytope does not admit fully-polynomial size relaxation schemes

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

Improved Bounds for Orthogonal Point Enclosure Query and Point Location in Orthogonal Subdivisions in ℝ3

Saladi Rahul

Improved Bounds for Orthogonal Point Enclosure Query and Point Location in Orthogonal Subdivisions in ℝ3

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

On Survivable Set Connectivity

Parinya Chalermsook, Fabrizio Grandoni, Bundit Laekhanukit

On Survivable Set Connectivity

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

Minors and Dimension

Bartosz Walczak

Minors and Dimension

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

Online Stochastic Matching with Unequal Probabilities

Aranyak Mehta, Bo Waggoner, Morteza Zadimoghaddam

Online Stochastic Matching with Unequal Probabilities

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

Robust Probabilistic Inference

Yishay Mansour, Aviad Rubinstein, Moshe Tennenholtz

Robust Probabilistic Inference

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

Online Principal Components Analysis

Christos Boutsidis, Dan Garber, Zohar Shay Karnin, Edo Liberty

Online Principal Components Analysis

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

A note on the ring loading problem

Martin Skutella

A note on the ring loading problem

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

Sketching for M-Estimators: A Unified Approach to Robust Regression

Kenneth L. Clarkson, David P. Woodruff

Sketching for M-Estimators: A Unified Approach to Robust Regression

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

Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation

Sayan Bandyapadhyay, Santanu Bhowmick, Kasturi R. Varadarajan

Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation

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

Spatial mixing and the connective constant: Optimal bounds

Alistair Sinclair, Piyush Srivastava, Daniel Stefankovic, Yitong Yin

Spatial mixing and the connective constant: Optimal bounds

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

Fast Algorithms for Online Stochastic Convex Programming

Shipra Agrawal, Nikhil R. Devanur

Fast Algorithms for Online Stochastic Convex Programming

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

Approximate Range Emptiness in Constant Time and Optimal Space

Mayank Goswami, Allan Grønlund Jørgensen, Kasper Green Larsen, Rasmus Pagh

Approximate Range Emptiness in Constant Time and Optimal Space

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

Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order

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

Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order

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

Robust hamiltonicity of random directed graphs extended abstract

Asaf Ferber, Rajko Nenadov, Ueli Peter, Andreas Noever, Nemanja Skoric

Robust hamiltonicity of random directed graphs extended abstract

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

The Simplex Algorithm is NP-mighty

Yann Disser, Martin Skutella

The Simplex Algorithm is NP-mighty

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

Online Network Design Algorithms via Hierarchical Decompositions

Seeun Umboh

Online Network Design Algorithms via Hierarchical Decompositions

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

Fast Lattice Point Enumeration with Minimal Overhead

Daniele Micciancio, Michael Walter

Fast Lattice Point Enumeration with Minimal Overhead

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

(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting

Michael Elkin, Seth Pettie, Hsin-Hao Su

(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting

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

Dynamic Facility Location via Exponential Clocks

Hyung-Chan An, Ashkan Norouzi-Fard, Ola Svensson

Dynamic Facility Location via Exponential Clocks

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

Cell-probe bounds for online edit distance and other pattern matching problems

Raphaël Clifford, Markus Jalsenius, Benjamin Sach

Cell-probe bounds for online edit distance and other pattern matching problems

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

Testing Poisson Binomial Distributions

Jayadev Acharya, Constantinos Daskalakis

Testing Poisson Binomial Distributions

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

Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (Extended Abstract)

Ian Post, Chaitanya Swamy

Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (Extended Abstract)

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

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis

Mark Braverman, Young Kun-Ko, Omri Weinstein

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis

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

FPTAS for Counting Monotone CNF

Jingcheng Liu, Pinyan Lu

FPTAS for Counting Monotone CNF

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

Approximating independent sets in sparse graphs

Nikhil Bansal

Approximating independent sets in sparse graphs

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

Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly

Sándor P. Fekete, Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller

Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly

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

Towards a Characterization of Constant-Factor Approximable Min CSPs

Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran

Towards a Characterization of Constant-Factor Approximable Min CSPs

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

Detecting Weakly Simple Polygons

Hsien-Chih Chang, Jeff Erickson, Chao Xu

Detecting Weakly Simple Polygons

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

A Stable Marriage Requires Communication

Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, Will Rosenbaum

A Stable Marriage Requires Communication

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

Density and regularity theorems for semi-algebraic hypergraphs

Jacob Fox, János Pach, Andrew Suk

Density and regularity theorems for semi-algebraic hypergraphs

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

LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes

Badih Ghazi, Euiwoong Lee

LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes

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

Perfect Bayesian Equilibria in Repeated Sales

Nikhil R. Devanur, Yuval Peres, Balasubramanian Sivan

Perfect Bayesian Equilibria in Repeated Sales

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

Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing

Daniel Dadush, Nicolas Bonifas

Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing

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

Efficient and Robust Persistent Homology for Measures

Mickaël Buchet, Frédéric Chazal, Steve Y. Oudot, Donald Sheehy

Efficient and Robust Persistent Homology for Measures

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

Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization

Niv Buchbinder, Moran Feldman, Roy Schwartz

Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization

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

Algorithmic regularity for polynomials and applications

Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani

Algorithmic regularity for polynomials and applications

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

Online Submodular Maximization with Preemption

Niv Buchbinder, Moran Feldman, Roy Schwartz

Online Submodular Maximization with Preemption

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

Decomposing a Graph Into Expanding Subgraphs

Guy Moshkovitz, Asaf Shapira

Decomposing a Graph Into Expanding Subgraphs

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

A new characterization of maximal repetitions by Lyndon trees

Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta

A new characterization of maximal repetitions by Lyndon trees

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

Solving d-SAT via Backdoors to Small Treewidth

Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, Saket Saurabh

Solving d-SAT via Backdoors to Small Treewidth

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

Capacity of Interactive Communication over Erasure Channels and Channels with Feedback

Ran Gelles, Bernhard Haeupler

Capacity of Interactive Communication over Erasure Channels and Channels with Feedback

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

Learning from satisfying assignments

Anindya De, Ilias Diakonikolas, Rocco A. Servedio

Learning from satisfying assignments

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

On Uniform Capacitated k-Median Beyond the Natural LP Relaxation

Shi Li

On Uniform Capacitated k-Median Beyond the Natural LP Relaxation

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

Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm

Mathew C. Francis, Pavol Hell, Juraj Stacho

Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm

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

Sharp Bounds on Formation-free Sequences

Seth Pettie

Sharp Bounds on Formation-free Sequences

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

Set membership with a few bit probes

Mohit Garg, Jaikumar Radhakrishnan

Set membership with a few bit probes

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

Improved Bounds for the Flat Wall Theorem

Julia Chuzhoy

Improved Bounds for the Flat Wall Theorem

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

The switch Markov chain for sampling irregular graphs (Extended Abstract)

Catherine S. Greenhill

The switch Markov chain for sampling irregular graphs (Extended Abstract)

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

Finding Four-Node Subgraphs in Triangle Time

Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, Huacheng Yu

Finding Four-Node Subgraphs in Triangle Time

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

On Termination of Integer Linear Loops

Joël Ouaknine, João Sousa Pinto, James Worrell

On Termination of Integer Linear Loops

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

Characterization of cutoff for reversible Markov chains

Riddhipratim Basu, Jonathan Hermon, Yuval Peres

Characterization of cutoff for reversible Markov chains

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

A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract]

Sungjin Im, Shi Li, Benjamin Moseley, Eric Torng

A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract]

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

Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel

Zeyuan Allen Zhu, Lorenzo Orecchia

Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel

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

Improved Region-Growing and Combinatorial Algorithms for k-Route Cut Problems (Extended Abstract)

Guru Guruganesh, Laura Sanità, Chaitanya Swamy

Improved Region-Growing and Combinatorial Algorithms for k-Route Cut Problems (Extended Abstract)

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

A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity

Timothy Naumovitz, Michael E. Saks

A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity

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

2-Edge Connectivity in Directed Graphs

Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, Nikos Parotsidis

2-Edge Connectivity in Directed Graphs

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

The Parameterized Complexity of k-Biclique

Bingkai Lin

The Parameterized Complexity of k-Biclique

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

Optimal approximation for submodular and supermodular optimization with bounded curvature

Maxim Sviridenko, Jan Vondrák, Justin Ward

Optimal approximation for submodular and supermodular optimization with bounded curvature

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

Minimum Forcing Sets for Miura Folding Patterns

Brad Ballinger, Mirela Damian, David Eppstein, Robin Y. Flatland, Jessica Ginepro, Thomas C. Hull

Minimum Forcing Sets for Miura Folding Patterns

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

A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State

Antonios Antoniadis, Chien-Chung Huang, Sebastian Ott

A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State

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

Learning Privately with Labeled and Unlabeled Examples

Amos Beimel, Kobbi Nissim, Uri Stemmer

Learning Privately with Labeled and Unlabeled Examples

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

Wavelet Trees Meet Suffix Trees

Maxim A. Babenko, Pawel Gawrychowski, Tomasz Kociumaka, Tatiana A. Starikovskaya

Wavelet Trees Meet Suffix Trees

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

Connectivity in Random Forests and Credit Networks

Ashish Goel, Sanjeev Khanna, Sharath Raghvendra, Hongyang Zhang

Connectivity in Random Forests and Credit Networks

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

Contagious Sets in Expanders

Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, Daniel Reichman

Contagious Sets in Expanders

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

Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity

Rahul Santhanam, Richard Ryan Williams

Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity

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

An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications

Andrew Chi-Chih Yao

An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications

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

Robust Price of Anarchy Bounds via LP and Fenchel Duality

Janardhan Kulkarni, Vahab S. Mirrokni

Robust Price of Anarchy Bounds via LP and Fenchel Duality

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