The SOSA 2018 proceedings are now available.

​

Wednesday, January 10, 2018

 

Session 9:00 AM – 11:05 AM

9:00–9:20 A Naive Algorithm for Feedback Vertex Set

Yixin Cao, Hong Kong Polytechnic University, China

​

9:25–9:45 A note on iterated rounding for the Survivable Network Design Problem

Chandra Chekuri, University of Illinois, USA

Thapanapong Rukkanchanunt, Chiang May University, Thailand

​

9:50–10:10 Congestion minimization for multipath routing via multiroute flows

Chandra Chekuri, University of Illinois, USA

Mark Idleman, University of Illinois, USA

​

10:15–10:35 Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling

Deeparnab Chakrabarty, Dartmouth College, USA

Sanjeev Khanna, University of Pennsylvania, USA

​

10:40–11:00 Approximation Schemes for 0-1 Knapsack

Timothy M. Chan, University of Illinois, USA

​

Session 2:00 PM – 4:05 PM

2:00–2:20 Counting Solutions to Polynomial Systems via Reductions

Ryan Williams, MIT, USA

​

2:25–2:45 On Sampling Edges Almost Uniformly

Talya Eden, Tel Aviv University, Israel

Will Rosenbaum, Tel Aviv University, Israel

​

2:50–3:10 A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version

Allan Borodin, University of Toronto, Canada

Denis Pankratov, University of Toronto, Canada

Amirali Salehi-Abari, University of Toronto, Canada

​

3:15–3:35 Simple and Efficient Leader Election

Petra Berenbrink, Universität Hamburg, Germany

Dominik Kaaser, Universität Hamburg, Germany

Peter Kling, Universität Hamburg, Germany  

Lena Otterbach, Universität Hamburg, Germany

 

3:40–4:00 A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance

Tsvi Kopelowitz, University of Waterloo, Canada

Ely Porat, Bar-Ilan University, Israel

 

Session 4:30 PM -- 6:35 PM

4:30–4:50 Compact LP Relaxations for Allocation Problems

Klaus Jansen, Christian-Albrechts-Universität Kiel, Germany

Lars Rohwedder, Christian-Albrechts-Universität Kiel, Germany

 

4:55–5:15 Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP)

Divesh Aggarwal, National University of Singapore, Singapore

Noah Stephens-Davidowitz, New York University, USA

 

5:20–5:40 Complex Semidefinite Programming and Max-k-Cut

Alantha Newman, CNRS-Université Grenoble Alpes, France

 

5:45–6:05 A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs

Andrew McGregor, University of Massachusetts, USA

Sofya Vorotnikova, University of Massachusetts, USA

 

6:10–6:30 Simple analyses of the Sparse Johnson-Lindenstrauss Transform

Michael B. Cohen, MIT, USA

T.S. Jayram, IBM Almaden Research Center, USA

Jelani Nelson, Harvard University, USA