Preliminary Program SODA 2018 (obsolete – official program is available on SODA 2018 web page – please refer to it now)

January 7 – 10, 2018, Astor Crowne Plaza – New Orleans French Quarter



Daily schedule (template)


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)


Sunday, January 7, 2018


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.




Monday, January 8, 2018


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



Tuesday, January 9, 2018


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.


Wednesday, January 10, 2018


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.