Preliminary Program SODA 2018 (obsolete – official program
is available on SODA 2018 web page – please refer to it now)
http://www.siam.org/meetings/da18/
January
7 – 10, 2018,
Astor Crowne Plaza – New Orleans
French Quarter
8:30 – 9:00 Continental breakfast
9:00 – 11:05
Session A (5 talks; 20 minutes
each, with 5 minutes time between the talks for questions, etc)
Session B (5 talks)
Session C (5 talks)
11:05 – 11:30 Coffee break
11:30 – 12:30 Plenary talk
12:30 – 2:00pm Lunch
2:00pm – 4:05pm
Session A (5 talks)
Session B (5 talks)
Session C (5 talks)
4:05pm – 4:30pm Coffee break
4:30pm – 6:35pm
Session A (5 talks)
Session B (5 talks)
Session C (5 talks)
8:30 –
9:00 Continental breakfast
9:00 –
11:05
Session 1A
·
Sayan Bhattacharya, Deeparnab
Chakrabarty, Monika Henzinger
and Danupon Nanongkai.
o
Dynamic Algorithms for Graph Coloring.
·
Aaron Bernstein and Shiri Chechik.
o
Incremental Topological Sort and Cycle Detection in Õ(m √n) Expected Total
Time.
·
Jacob Holm, Eva Rotenberg and Mikkel
Thorup.
o
Dynamic Bridge-Finding in Õ(log²
n) Amortized Time.
·
Surender Baswana, Ayush Goel and Shahbaz Khan.
o
Incremental DFS Algorithms: A Theoretical and
Experimental Study.
·
Adam Karczmarz.
o
Decremental Transitive
Closure and Shortest Paths for Planar Digraphs and Beyond.
Session 1B
·
Andrei Asinowski, Gill Barequet and Yufei Zheng.
o
Polycubes with Small Perimeter Defect.
·
Sharath Raghvendra and Mariëtte C. Wessels.
o
A Grid-Based Approximation Algorithm for the Minimum
Weight Triangulation Problem.
·
Hsien-Chih Chang, Jeff
Erickson, David Letscher, Arnaud de Mesmay, Saul Schleimer, Eric
Sedgwick, Dylan Thurston and Stephan Tillmann.
o
Minimizing Intersections of Curves on Surfaces via
Local Moves.
·
Mateus De Oliveira Oliveira.
o
A Near-Quadratic Lower Bound for the Size of Quantum
Circuits of Constant Treewidth.
·
Peter Clifford and Raphael Clifford.
o
The Classical Complexity of Boson Sampling.
Session 1C
·
Kunal Agrawal, Joseph Devietti,
Jeremy Fineman, I-Ting Angelina Lee, Robert Utterback and Changming Xu.
o
Race Detection and Reachability in Nearly
Series-Parallel DAGs.
·
Daniel Gonçalves, Lucas Isenmann and Claire Pennarun.
o
Planar Graphs as L-intersection or L-Contact Graphs.
·
Daniel Lokshtanov and Amer Mouawad.
o
The Complexity of Independent Set Reconfiguration on
Bipartite Graphs.
·
Chenglin Fan, Benjamin Raichel and Gregory Van Buskirk.
o
Metric Violation Distance: Hardness and Approximation.
·
Ross Churchley and Bojan Mohar.
o
A Submodular Measure and Approximate Gomory-Hu Theorem for Packing Odd Trails.
11:05 –
11:30
11:30 –
12:30 Plenary talk
Cynthia Dwork,
Harvard University, USA
12:30 –
2:00pm Lunch
2:00pm
– 4:05pm
Session 2A
·
Nikola Yolov.
o
Minor-Matching Hypertree Width.
·
Ken-Ichi Kawarabayashi
and Benjamin Rossman.
o
A Polynomial Excluded-Minor Approximation of Treedepth.
·
Daniel Lokshtanov, Ivan Mihajlin, Ramamohan Paturi and Pavel Pudlák.
o
Beating Brute Force for (Quantified) Satisfiability of
Circuits of Bounded Treewidth.
·
Petr Golovach, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi.
o
Cliquewidth III: The Odd Case
of Graph Coloring Parameterized by Cliquewidth.
·
Hugo Akitaya, Radoslav Fulek and Csaba Toth.
o
Recognizing Weak Embeddings
of Graphs.
Session 2B
·
Takanori Maehara and Yutaro Yamaguchi.
o
Stochastic Packing Integer Program with Few Queries.
·
Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan
and Pan Xu.
o
Algorithms to Approximate Column-Sparse Packing
Problems.
·
Tien-Nam Le, Daniel Lokshtanov,
Saket Saurabh, Stephan Thomasse
and Meirav Zehavi.
o
Subquadratic Kernels for
Implicit 3-Hitting Set and 3-Set Packing Problems.
·
Zhiyi Huang and Xue Zhu.
o
Near Optimal Jointly Private Packing Algorithms via
Dual Multiplicative Weight Update.
·
Chandra Chekuri and Kent Quanrud.
o
Randomized MWU for Positive LPs.
Session 2C
·
Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn
and Claire Mathieu.
o
Hierarchical Clustering: Objective Functions and
Algorithms.
·
Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour and Mohammad Salavatipour.
o
Approximation Schemes for Clustering Problems with
Outliers.
·
Ehsan Emamjomeh-Zadeh and
David Kempe.
o
Adaptive Hierarchical Clustering Using Ordinal
Queries.
·
Vincent Cohen-Addad.
o
A Fast Approximation Scheme for Low-Dimensional k-Means.
·
Vincent Cohen-Addad, Arnaud
de Mesmay, Eva Rotenberg and Alan Roytman.
o
The Bane of Low-Dimensionality Clustering.
4:05pm
– 4:30pm Coffee break
4:30pm
– 6:35pm
Session 3A
·
Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn
and Sharath Raghvendra.
o
A Faster Algorithm for the Minimum-Cost Bipartite
Perfect Matching in Planar Graphs.
·
Shay Mozes, Cyril Nikolaev, Yahav Nussbaum and Oren
Weimann.
o
Minimum Cut of Directed Planar Graphs in O(n loglogn) Time.
·
Pawel Gawrychowski, Haim
Kaplan, Shay Mozes, Micha Sharir
and Oren Weimann.
o
Voronoi Diagrams on Planar Graphs, and Computing the
Diameter in Deterministic Õ(n5/3) Time.
·
Paweł Gawrychowski, Shay Mozes, Oren Weimann and Christian Wulff-Nilsen.
o
Better Tradeoffs for Exact
Distance Oracle in Planar Graphs.
·
Amir Abboud, Pawel Gawrychowski, Shay Mozes and Oren
Weimann.
o
Near-Optimal Compression for the Planar Graph Metric.
Session 3B
·
J. Ian Munro and Corwin Sinnamon.
o
Time and Space Efficient Representations of
Distributive Lattices.
·
Joe Sawada and Aaron Williams.
o
A Hamilton Path for the Sigma-Tau Problem.
·
Flavio Chierichetti, Ravi
Kumar and Andrew Tomkins.
o
Discrete Choice, Permutations, and Reconstruction.
·
Vahab Mirrokni, Mikkel Thorup and Morteza Zadimoghaddam.
o
Consistent Hashing with Bounded Loads.
·
David Durfee, Matthew Fahrbach, Yu Gao and Tao Xiao.
o
Nearly Tight Bounds for Sandpile
Transience on the Grid.
Session 3C
·
Venkatesan Guruswami and Ray Li.
o
Coding Against Deletions in Oblivious and Online Models.
·
Atri Rudra and Mary Wootters.
o
Average-radius List-recoverability of Random Linear Codes.
·
Pooya Hatami and Madhur Tulsiani.
o
Approximate Local Decoding of Cubic Reed-Muller Codes
Beyond the List Decoding Radius.
·
Swastik Kopparty and Aditya
Potukuchi.
o
Syndrome Decoding of Reed-Muller Codes and Tensor
Decompositions over Finite Fields.
·
Brynmor Chapman.
o
The Gotsman-Linial
Conjecture is False.
8:30 –
9:00 Continental breakfast
9:00 –
11:05
Session 4A
·
Soheil Ehsani, Mohammadtaghi Hajiaghayi, Thomas Kesselheim and Sahil Singla.
o
Prophet Secretary for Combinatorial Auctions and Matroids.
·
José A. Soto, Victor Verdugo
and Abner Turkieltaub.
o
Strong Algorithms for the Ordinal Matroid
Secretary Problem.
·
Moran Feldman, Ola Svensson
and Rico Zenklusen.
o
A Framework for the Secretary Problem on the
Intersection of Matroids.
·
Nikhil R. Devanur, Balasubramanian Sivan and Vasilis Syrgkanis.
o
Truthful Multi-Parameter Auctions with Online Supply:
an Impossible Combination.
·
Aaron Sidford, Mengdi Wang, Xian Wu and Yinyu
Ye.
o
Variance Reduced Value Iteration and Faster Algorithms
for Solving Markov Decision Processes.
Session 4B
·
Alfonso Cevallos, Stefan Weltge and Rico Zenklusen.
o
Lifting Linear Extension Complexity Bounds to the
Mixed-Integer Setting.
·
Friedrich Eisenbrand and
Robert Weismantel.
o
Proximity Results and Faster Algorithms for Integer
Programming using the Steinitz Lemma.
·
Samuel Fiorini, Martin Groß, Jochen Koenemann
and Laura Sanita.
o
Approximating Weighted Tree Augmentation via Chvátal-Gomory Cuts.
·
Daniel Dadush, László A. Végh and Giacomo Zambelli.
o
Geometric Rescaling Algorithms for Submodular Function
Minimization.
·
Martin Nägele, Benny Sudakov and Rico Zenklusen.
o
Submodular Minimization Under
Congruency Constraints.
Session 4C
·
Mathias Bæk Tejs Knudsen and Mikkel Thorup.
o
The Entropy of Backwards Analysis.
·
Timothy M. Chan.
o
More Logarithmic-Factor Speedups for 3SUM, (median,+)-Convolution, and Some Geometric 3SUM-Hard Problems.
·
Anne Driemel and Peyman Afshani.
o
On the Complexity of Range Searching Among Curves.
·
Mitchell Jones and Sariel Har-Peled.
o
On Separating Points by Lines.
·
Louigi Addario-Berry, Omer Angel, Guillaume Chapuy, Eric Fusy and Christina
Goldschmidt.
o
Voronoi Tessellations in the CRT and Continuum Random
Maps of Finite Excess.
11:05 –
11:30
11:30 –
12:30 Plenary talk
Mikkel Thorup, University of Copenhagen, Denmark
12:30 –
2:00pm Lunch
2:00pm
– 4:05pm
Session 5A
·
Aaron Bernstein, Jacob Holm and Eva Rotenberg.
o
Online Bipartite Matching with Amortized O(log2 n) Replacements.
·
Ilan R. Cohen and David Wajc.
o
Randomized Online Matching in Regular Graphs.
·
Yossi Azar, Ilan Cohen and Debmalya Panigrahi.
o
Randomized Algorithms for Online Vector Load
Balancing.
·
Nikhil Bansal, Marek Elias, Grigorios
Koumoutsos and Jesper Nederlof.
o
Competitive Algorithms for Generalized k-Server in
Uniform Metrics.
·
Harry Lang.
o
Online Facility Location against a t-Bounded Adversary.
Session 5B
·
Nima Anari, Shayan Oveis Gharan,
Amin Saberi and Nikhil Srivastava.
o
Approximating the Largest Root and Applications to
Interlacing Families.
·
François Le Gall and Florent
Urrutia.
o
Improved Rectangular Matrix Multiplication using
Powers of the Coppersmith-Winograd Tensor.
·
Chloe Ching-Yun Hsu and Chris Umans.
o
A Fast Generalized DFT for Finite Groups of Lie Type.
·
Christopher De Sa, Albert Gu, Rohan Puttagunta, Christopher
Re and Atri Rudra.
o
A Two-pronged Progress in Structured Dense Matrix
Vector Multiplication.
·
Radu Curticapean, Jesper Nederlof and Nathan Lindzey.
o
Tight Lower Bounds for Counting Hamiltonian Cycles via
Matrix Rank.
Session 5C
·
Don Sheehy.
o
Frechet-Stable Signatures Using Persistence Homology.
·
Amir Nayyeri and Hanzhong Xu.
o
On the Decidability of the Frechet
Distance between Surfaces.
·
Erin Wolf Chambers, Arnaud de Mesmay
and Tim Ophelders.
o
On the Complexity of Optimal Homotopies.
·
Peter Franek, Marek Filakovský,
Stephan Zhechev and Uli
Wagner.
o
Computing Simplicial Representatives of Homotopy Group Elements.
·
Samir Chowdhury and Facundo Memoli.
o
Persistent Path Homology of Directed Networks.
4:05pm
– 4:30pm Coffee break
4:30pm
– 6:35pm
Session 6A
·
Soheil Ehsani, Mohammad Ghodsi, Mohammadtaghi Hajiaghayi, Mahdi Safarnejad-Boroujeni
and Saeed Seddighin.
o
Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce.
·
Karl Bringmann, Pawel Gawrychowski, Shay Mozes and Oren
Weimann.
o
Tree Edit Distance Cannot be
Computed in Strongly Subcubic Time (unless APSP can).
·
Ryan Williams.
o
On the Complexity of Furthest, Closest, and Orthogonal
Pairs in Low Dimensions.
·
Karl Bringmann and Marvin Künnemann.
o
Multivariate Fine-Grained Complexity of Longest Common
Subsequence.
·
Andrea Lincoln, Virginia Vassilevska
Williams and Ryan Williams.
o
Tight Hardness for Shortest Cycles and Paths in Sparse
Graphs.
Session 6B
·
Nikhil Bansal, Martin Böhm,
Marek Elias, Grigorios Koumoutsos
and Seeun William Umboh.
o
Nested Convex Bodies Are Chaseable.
·
Clifford Stein and Mingxian Zhong.
o
Scheduling When You Don't Know the Number of Machines.
·
Anupam Gupta, Amit Kumar, Viswanath
Nagarajan and Xiangkun
Shen.
o
Stochastic Load Balancing on Unrelated Machines.
·
Anindya De.
o
Boolean Function Analysis Meets Stochastic
Optimization: An Approximation Scheme for Stochastic Knapsack.
·
Nikhil Srivastava and Luca Trevisan.
o
An Alon-Boppana Type Bound
for Weighted Graphs and Lower Bounds for Spectral Sparsification.
Session 6C
·
Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick and
Martin Tancer.
o
Embeddability in R3
is NP-hard.
·
Daniel Dadush, Cristobal
Guzman and Neil Olver.
o
Fast, Deterministic and Sparse Dimensionality
Reduction.
·
Assaf Naor, Gilles Pisier and Gideon Schechtman.
o
Impossibility of Dimension Reduction in the Nuclear Norm.
·
Yun Kuen Cheung.
o
Steiner Point Removal – Distant Terminals Don't
(Really) Bother.
·
Arnold Filtser.
o
Steiner Point Removal with Distortion O(log k).
6:45pm
– SODA Business Meeting
8:30 –
9:00 Continental breakfast
9:00 –
11:05
Session 7A
·
Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov and Virginia Vassilevska
Williams.
o
Approximating Cycles in Directed Graphs.
·
Kristof Berczi, Karthekeyan Chandrasekaran, Tamas Kiraly and Vivek Madan.
o
A tight √2-approximation for
Linear 3-Cut.
·
Amey Bhangale, Subhash Khot, Swastik
Kopparty, Sushant Sachdeva
and Devanathan Thiruvenkatachari.
o
Near-optimal Approximation Algorithm for Simultaneous
Max-Cut.
·
Karthekeyan Chandrasekaran, Chao Xu and Xilin
Yu.
o
Hypergraph k-Cut
in Randomized Polynomial Time.
·
Vincent Cohen-Addad, Éric Colin de Verdière and Arnaud
de Mesmay.
o
A Near-linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals.
Session 7B
·
Travis Gagie, Gonzalo
Navarro and Nicola Prezza.
o
Optimal-Time Text Indexing in BWT-runs Bounded Space.
·
Guillaume Lagarde and
Sylvain Perifel.
o
Lempel-Ziv: A "One-bit Catastrophe" but not
a Tragedy.
·
Nicola Prezza.
o
In-Place Sparse Suffix Sorting.
·
Pawel Gawrychowski, Adam Karczmarz, Tomasz Kociumaka,
Jakub Łącki and Piotr Sankowski.
o
Optimal Dynamic Strings.
·
Eldar Fischer, Frederic Magniez
and Tatiana Starikovskaya.
o
Improved Bounds for Testing Dyck
Languages.
Session 7C
·
Sankeerth Rao Karingula, Shachar Lovett and Alexander Vardy.
o
Probabilistic Existence of Large Sets of Designs.
·
Nicholas Harvey, Piyush
Srivastava and Jan Vondrak.
o
Computing the Independence Polynomial: from the Tree
Threshold down to the Roots.
·
Satish Rao, Nikhil Srivastava and Aaron Schild.
o
Localization of Electrical Flows.
·
Makrand Sinha.
o
Lower Bounds for Approximating the Matching Polytope.
·
Cameron Musco, Christopher Musco and Aaron Sidford.
o
Stability of the Lanczos
Method for Matrix Function Approximation.
11:05 –
11:30
11:30 –
12:30 Plenary talk
Anupam
Gupta, Carnegie Mellon University, USA
12:30 –
2:00pm Lunch
2:00pm
– 4:05pm
Session 8A
·
David Kempe, Leonard J. Schulman and Omer Tamuz.
o
Quasi-regular Sequences and Optimal Schedules for
Security Games.
·
Stephen Alstrup, Agelos Georgakopoulos, Eva
Rotenberg and Carsten Thomassen.
o
A Hamiltonian Cycle in the Square of a 2-connected
Graph in Linear Time.
·
Ittai Abraham, Shiri Chechik,
Michael Elkin, Arnold Filtser and Ofer
Neiman.
o
Ramsey Spanning Trees and their Applications.
·
Eun Jung Kim and O-Joung
Kwon.
o
Erdos-Posa Property of Chordless Cycles and its Applications.
·
Zdenek Dvorak.
o
Thin Graph Classes and Polynomial-time Approximation Schemes.
Session 8B
·
Anna Ben-Hamou, Roberto I.
Oliveira and Yuval Peres.
o
Estimating Graph Parameters via Random Walks with Restarts.
·
Petra Berenbrink, George Giakkoupis and Peter Kling.
o
Tight Bounds for Coalescing Branching Random Walks on
Regular Graphs.
·
Anna Ben-Hamou, Eyal Lubetzky and Yuval Peres.
o
Comparing Mixing times on Sparse Random Graphs.
·
Pu Gao and Nicholas Wormald.
o
Uniform Generation of Random Graphs with Power-Law
Degree Sequences.
·
Charilaos Efthymiou, Thomas
Hayes, Daniel Stefankovic and Eric Vigoda.
o
Sampling Random Colorings of
Sparse Random Graphs.
Session 8C
·
Jacob Focke, Leslie Ann
Goldberg and Stanislav Živný.
o
The Complexity of Counting Surjective Homomorphisms and Compactions.
·
Joshua Brakensiek and Venkatesan Guruswami.
o
Promise Constraint Satisfaction: Structure Theory and
a Symmetric Boolean Dichotomy.
·
Jin-Yi Cai,
Pinyan Lu and Mingji Xia.
o
Dichotomy for Real Holant^c
Problems.
·
Shachar Lovett, Avishay Tal and Jiapeng
Zhang.
o
The Robust Sensitivity of Boolean Functions.
·
Badih Ghazi and T.S. Jayram.
o
Resource-Efficient Common Randomness and Secret-Key
Schemes.
4:05pm
– 4:30pm Coffee break
4:30pm
– 6:35pm
Session 9A
·
Vera Traub and Jens Vygen.
o
Approaching 3/2 for the s-t-Path TSP.
·
Amir Abboud and Greg Bodwin.
o
Reachability Sparsifiers:
New Extremal Bounds and Approximation Algorithms.
·
Greg Bodwin, Michael Dinitz, Merav Parter
and Virginia Vassilevska Williams.
o
Optimal Vertex Fault Tolerant Spanners (for fixed
stretch).
·
Keerti Choudhary, Surender Baswana, Moazzam Hussain and Liam Roditty.
o
Approximate Single Source Fault Tolerant Shortest
Path.
·
Ramanujan M. S., Daniel Lokshtanov
and Saket Saurabh.
o
When Recursion is Better than
Iteration: A Linear-Time Algorithm for Acyclicity
with Few Error Vertices.
Session 9B
·
Nobutaka Shimizu.
o
The Diameter of Dense Random Regular Graphs.
·
Fang-Yi Yu and Grant Schoenebeck.
o
Consensus of Interacting Particle Systems on Erdos-Renyi Graphs.
·
Antonio Blanca, Pietro Caputo, Alistair Sinclair and
Eric Vigoda.
o
Spatial Mixing and Non-local Markov Chains.
·
Reza Gheissari, Eyal Lubetzky and Yuval Peres.
o
Exponentially Slow Mixing in the Mean-Field Swendsen-Wang Dynamics.
·
Constantinos Daskalakis, Nishanth Dikkala and Gautam Kamath.
o
Testing Ising Models.
Session 9C
·
Siqi Liu and Christos-Alexandros Psomas.
o
On the Competition Complexity of Dynamic Mechanism
Design.
·
S. Matthew Weinberg, Raghuvansh
R. Saxena and Ariel Schvartzman.
o
The Menu Complexity of One-and-a-Half-Dimensional
Mechanism Design.
·
Xi Chen, George Matikas,
Dimitris Paparas and Mihalis
Yannakakis.
o
On the Complexity of Simple and Optimal Deterministic
Mechanisms for an Additive Buyer.
·
Shuchi Chawla, Kira Goldner,
J. Benjamin Miller and Emmanouil Pountourakis.
o
Aversion to Uncertainty and Its Implications for
Revenue Maximization.
·
Nikolai Gravin and Pinyan Lu.
o
Separation in Correlation-Robust Monopolist Problem
with Budget.
8:30 –
9:00 Continental breakfast
9:00 –
11:05
Session 10A
·
Talya Eden, Reut Levi and
Dana Ron.
o
Testing Bounded Arboricity.
·
Omri Ben-Eliezer and Clément Canonne.
o
Improved Bounds for Testing Forbidden Order Patterns.
·
Eric Blais, Clément Canonne, Talya Eden, Amit Levi
and Dana Ron.
o
Tolerant Junta Testing and the Connection to
Submodular Optimization and Function Isomorphism.
·
T-H. Hubert Chan, Yue Guo,
Wei-Kai Lin and Elaine Shi.
o
Cache-Oblivious and Data-Oblivious Sorting and
Applications.
·
Hadley Black, Deeparnab Chakrabarty and C. Seshadhri.
o
A o(d)polylog
n Monotonicity Tester for Boolean Functions over the Hypergrid
[n]d.
Session 10B
·
Manuela Fischer and Andreas Noever.
o
Tight Analysis of Parallel Randomized Greedy MIS.
·
David Harris.
o
Derandomized Concentration
Bounds for Polynomials, and Hypergraph Maximal Independent Set.
·
Abishek Sankararaman and
François Baccelli.
o
Community Detection on Euclidean Random Graphs.
·
Dan Alistarh, James Aspnes and Rati Gelashvili.
o
Space-Optimal Majority in Population Protocols.
·
Mohit Singh and Weijun Xie.
o
Approximate Positive Correlated Distributions and
Approximation Algorithms for D-optimal
Design.
Session 10C
·
Mark Braverman, Jieming Mao and S. Matthew Weinberg.
o
On Simultaneous Two-player Combinatorial Auctions.
·
Nima Anari, Tung Mai, Shayan Oveis Gharan
and Vijay Vazirani.
o
Nash Social Welfare for Indivisible Items under
Separable, Piecewise-Linear Concave Utilities.
·
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammadtaghi Hajiaghayi, Mohammad Mahdian,
Christos H. Papadimitriou, Ronald L. Rivest, Saeed Seddighin and Philip B. Stark.
o
From Battlefields to Elections: Winning Strategies of
Blotto and Auditing Games.
·
Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay Vazirani and Sadra Yazdanbod.
o
A New Class of Combinatorial Markets with Covering
Constraints: Algorithms and Applications.
·
Jugal Garg, Martin Hoefer
and Kurt Mehlhorn.
o
Approximating the Nash Social Welfare with
Budget-Additive Valuations.
11:05 –
11:30
11:30 –
12:30 Plenary talk
Virginia Vassilevska
Williams, Massachusetts Institute of Technology, USA
12:30 –
2:00pm Lunch
2:00pm
– 4:05pm
Session 11A
·
Krishnendu Chatterjee,
Wolfgang Dvořák, Monika Henzinger
and Veronika Loitzenbauer.
o
Lower Bounds for Symbolic Computation on Graphs:
Strongly Connected Components, Liveness, Safety, and Diameter.
·
Gábor Ivanyos and Youming Qiao.
o
Algorithms
Based on *-Algebras, and their Applications to Isomorphism of Polynomials with
One Secret, Group Isomorphism, and Polynomial Identity Testing.
·
Huan Li and Zhongzhi
Zhang.
o
Kirchhoff Index as a Measure of Edge Centrality in
Weighted Networks: Nearly Linear Time Algorithms.
·
Chaya Keller and Shakhar Smorodinsky.
o
Conflict-Free Coloring of
Intersection Graphs of Geometric Objects.
·
Sepehr Assadi and Sanjeev
Khanna.
o
Tight Bounds on the Round Complexity of the
Distributed Maximum Coverage Problem.
Session 11B
·
Jaroslaw Blasiok.
o
Optimal streaming and tracking distinct elements with
high probability.
·
Pan Peng and Christian Sohler.
o
Estimating Graph Parameters from Random Order Streams.
·
Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian and Anak Yodpinyanee.
o
Set Cover in Sub-linear Time.
·
Arun Jambulapati and
Aaron Sidford.
o
Efficient Õ(n/e) Spectral
Sketches for the Laplacian and its Pseudoinverse.
·
Xi Chen, Yuanzhi Li and Jieming Mao.
o
An Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit
Model.
Session 11C
·
Sahil Singla.
o
The Price of Information in Combinatorial
Optimization.
·
Hu Fu, Chris Liaw, Pinyan Lu and Zhihao Gavin Tang.
o
The Value of Information Concealment.
·
Ashwinkumar Badanidiyuru, Kshipra Bhawalkar and Haifeng Xu.
o
Targeting and Signaling in
Ad Auctions.
·
Sina Dehghani, Alireza Farhadi, Mohammadtaghi Hajiaghayi and Hadi Yami.
o
Envy-free Chore Division for An Arbitrary Number of
Agents.
·
Benjamin Plaut and Tim Roughgarden.
o
Almost Envy-Freeness with General Valuations.
4:05pm
– 4:30pm Coffee break
4:30pm
– 6:35pm
Session 12A
·
Pawel Gawrychowski, Fabian
Kuhn, Jakub Lopuszanski, Konstantinos Panagiotou and Pascal Su.
o
Labeling Schemes for Nearest Common Ancestors through
Minor-Universal Trees.
·
Krzysztof Nowicki and Tomasz
Jurdzinski.
o
MST in O(1) Rounds of
Congested Clique.
·
Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie and Jara
Uitto.
o
The Complexity of Distributed Edge Coloring
with Small Palettes.
·
Leszek Gasieniec and Grzegorz Stachowiak.
o
Fast Space Optimal Leader Election in Population
Protocols.
·
Adrian Kosowski and Przemysław Uznański.
o
Ergodic Effects in Token Circulation.
Session 12B
·
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra and Alistair
Stewart.
o
Robustly Learning a Gaussian: Getting Optimal Error,
Efficiently.
·
Panayotis Mertikopoulos,
Christos Papadimitriou and Georgios Piliouras.
o
Cycles in Adversarial Regularized Learning.
·
Wai Ming Tai and Jeff Phillips.
o
Improved Coresets for Kernel
Density Estimates.
·
Anindya De, Elchanan Mossel and Joe Neeman.
o
Non Interactive Simulation of Correlated Distributions
is Decidable.
·
Constantinos Daskalakis, Gautam Kamath and
John Wright.
o
Which Distribution Distances are
Sublinearly Testable?
Session 12C
· David Coudert, Guillaume Ducoffe and Alexandru Popa.
o Fully Polynomial FPT Algorithms for some classes of Bounded Clique-width Graphs.
· Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma and Meirav Zehavi.
o Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms.
· Lin Chen and Dániel Marx.
o Covering a Tree with Rooted Subtrees – Parameterized and Approximation Algorithms.
· Anupam Gupta, Euiwoong Lee and Jason Li.
o An FPT Algorithm Beating 2-Approximation for k-Cut.
· Joergen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Pranabendu Misra, Ramanujan M. S., Saket Saurabh and Meirav Zehavi.
o Parameterized Algorithms for Survivable Network Design with Uniform Demands.