News

Under construction!

Visitors Summer/Fall'21

posted Aug 25, 2021, 9:30 PM by Danupon Nanongkai

It's great to have visitors again!

Maxime Flin, Master student at ENS Paris (June - August'21).
Yuval Efron, PhD student at U Toronto and Columbia U. (July-September'21).
Parinya Chalermsook, Faculty member at Aalto University (October-November'21).

We also welcome our group members from KTH, Joakim and Sagnik.

Jan van den Brand's PhD defense

posted Jun 11, 2021, 7:32 PM by Danupon Nanongkai

On June 9, 2021, Jan van den Brand has successfully defended his PhD thesis. We thank Santosh Vempala for being his opponent, Thore Husfeldt, Barna Saha, and Laszlo Vegh for being the grading committee, and Per Austrin for being the chairman.

Sagnik spoke at Google Research Zurich

posted Apr 22, 2021, 4:28 PM by Danupon Nanongkai [ updated Apr 22, 2021, 4:40 PM ]

Sagnik gave a talk (virtually) titled "A cross-paradigm algorithm for the minimum cut problem" at Google Research Zurich on April 22, 2021.

Jan → Georgia Tech & Berkeley & Sagnik → Sheffield

posted Apr 11, 2021, 10:40 AM by Danupon Nanongkai [ updated May 1, 2021, 2:21 PM ]

Jan van den Brand will join Georgia Tech as an assistant professor in 2022, with a gap year as a Simons postdoc at UC Berkeley. (Jan will defend his thesis in June 2021.)
Sagnik Mukhopadhyay will join the University of Sheffield as a lecturer (the UK) in 2022, after finishing his postdocs at KTH and the University of Copenhagen.

Danupon joins University of Copenhagen

posted Apr 7, 2021, 8:36 PM by Danupon Nanongkai

Danupon joins the University of Copenhagen as a professor on April 1, 2021. See the announcement here: https://barc.ku.dk/news/danupon-nanongkai-joins-barc/.

STOC & SODA 2022 PC

posted Feb 17, 2021, 2:36 PM by Danupon Nanongkai [ updated May 3, 2021, 5:16 PM ]

After a year's pause, it's great to be back doing some committee work for both SODA and STOC 2022. Thanks to the PC chairs of both conferences for allowing PC submissions.

Jan will speak at LSE seminar

posted Feb 14, 2021, 8:59 AM by Danupon Nanongkai [ updated Mar 18, 2021, 11:56 AM ]

On Mar 19, 2021, Jan will speak at the London School of Economics and Political Science. [More detail]

[Publication] 4 STOC'21 papers from our team

posted Feb 6, 2021, 10:00 PM by Danupon Nanongkai [ updated Feb 14, 2021, 9:02 AM ]

In the coming STOC 2021 there will be 4 papers co-authored by our team members. For detail, see publications, team publications, and the list of accepted papers.

Jan received the Google PhD Fellowship

posted Nov 23, 2020, 10:43 AM by Danupon Nanongkai [ updated Nov 23, 2020, 10:51 AM ]

Jan van den Brand received the 2020 Google PhD fellowship in Algorithms, Optimizations and Markets. He is the first student from KTH, and perhaps from Sweden, to receive this fellowship.

Links:

Talks by group members

posted Oct 1, 2020, 1:51 PM by Danupon Nanongkai [ updated Nov 2, 2020, 1:59 PM ]

On October 1, 2020, Sagnik will give a talk at the theory seminar, TCS @ ILLINOIS on "Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms"
On December 2, 2020, Jan will give a talk at Rutgers/DIMACS Theory of Computing Seminar.
On December 9, 2020, Jan will give a talk at Michigan-Purdue Theory Seminar
Also our alumni Thatchaphol will give talks at IGAFIT Colloquia on October 15 and at Rutgers/DIMACS Theory of Computing Seminar on October 21

[Publication] SODA'21 and SOSA'21 papers

posted Oct 1, 2020, 1:41 PM by Danupon Nanongkai [ updated Nov 30, 2020, 10:23 PM ]

The following paper coauthored by Danupon has been accepted to SODA 2021.

Dynamic Set Cover: Improved Amortized and Worst-Case Update Time

with Sayan Bhattacharya, Monika Henzinger, Xiaowei Wu

SODA 2021: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms [link]

Links: 📄arXiv

The following paper by Jan van den Brand has been accepted to SOSA 2021 and received the best paper award.

Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms

SOSA 2021: SIAM Symposium on Simplicity in Algorithms

Acknowledgment: These projects have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No 715672. Nanongkai and Saranurak were also partially supported by the Swedish Research Council (Reg. No. 2015-04659.)

[Publication] 2 FOCS 2020 papers

posted Jul 11, 2020, 1:59 PM by Danupon Nanongkai

The following papers coauthored by the team members have been accepted to FOCS 2020: 61st Annual IEEE Symposium on Foundations of Computer Science [wiki,link]

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

with Jan van den Brand, Yin-Tat Lee, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond

with Julia Chuzhoy, Yu Gao, Jason Li, Richard Peng, Thatchaphol Saranurak

Acknowledgement: These projects have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No 715672. Nanongkai and Saranurak were also partially supported by the Swedish Research Council (Reg. No. 2015-04659.)

[Travel] Jan in Copenhagen

posted Mar 3, 2020, 1:45 PM by Danupon Nanongkai [ updated Mar 4, 2020, 2:42 PM ]

In March 2020, Jan van den Brand is spending two weeks at the University of Copenhagen, Denmark. We thank Mikkel Thorup for hosting and supporting his trip. Jan is giving two talks during this visit: "Dynamic algorithms for algebraic and graph problems" (based on our FOCS'19 papers) and "A Deterministic Linear Program Solver in Current Matrix Multiplication Time" (based on his SODA'20 paper).

[Publication] 2 STOC 2020 papers

posted Feb 6, 2020, 8:50 PM by Danupon Nanongkai

The following papers coauthored by the team members have been accepted to STOC 2020 (52nd ACM Symposium on Theory of Computing)

Solving Tall Dense Linear Programs in Nearly Linear Time

Jan van den Brand (with Yin Tat Lee, Aaron Sidford and Zhao Song)

Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms

Sagnik Mukhopadhyay, Danupon Nanongkai

Acknowledgement: These projects have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No 715672. Nanongkai and Saranurak were also partially supported by the Swedish Research Council (Reg. No. 2015-04659.)

[Travel] Sagnik and Mohit in Shonan meeting, Japan & Jan at FOCS'19 (Baltimore, USA) and U. of Washington (Seattle, USA)

posted Nov 8, 2019, 11:19 AM by Danupon Nanongkai [ updated Jan 29, 2020, 6:43 PM ]

In November 2018:

Sagnik and Mohit attended the Shonan meeting "Distributed Graph Algorithms". This is an invitation-only Dagstuhl-style workshop in Shonan Village, Japan.
Jan presented 3 papers in FOCS'2019 in Baltimore, MA, USA. Afterward, he visited the University of Washington in Seattle, WA, USA, and gave a seminar talk there. We thank Yin-Tat Lee for inviting and supporting the latter trip.

Acknowledgment: Jan van den Brand and Sagnik Mukhopadhyay have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No 715672. Mohit Daga is supported by the Swedish Research Council (Reg. No. 2015-04659.)

[Visitors] Autumn visitors: André Nusser, Thatchaphol Saranurak

posted Oct 15, 2019, 9:39 PM by Danupon Nanongkai [ updated Nov 24, 2019, 10:39 AM ]

In October 2019, we welcomed André Nusser (MPI, Germany) and Thatchaphol Saranurak (TTI-Chicago, USA).

[Publication] 3 SODA 2020 Papers from our team

posted Sep 24, 2019, 5:15 PM by Danupon Nanongkai [ updated Sep 24, 2019, 7:17 PM ]

The following papers coauthored by the team members have been accepted to SODA 2020 (31st Annual ACM-SIAM Symposium on Discrete Algorithms)

Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms

Danupon Nanongkai with Sebastian Forster, Thatchaphol Saranurak, Liu Yang, Sorrachai Yingchareonthawornchai

Coarse-Grained Complexity for Dynamic Algorithms

Danupon Nanongkai with Sayan Bhattacharya, Thatchaphol Saranurak

A Deterministic Linear Program Solver in Current Matrix Multiplication Time

Jan van den Brand

[Publication] 2 papers invited to SICOMP special issue for STOC'19

posted Aug 28, 2019, 8:45 AM by Danupon Nanongkai [ updated Sep 24, 2019, 7:26 PM ]

The following papers co-authored by Danupon are invited to the Siam Journal on Computing (SICOMP) special issue for STOC 2019.

Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme

with Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time

with Aaron Bernstein

Summer Visitors, 2019: Parinya Chalermsook, So-Hyeon (Sophie) Park, Michal Dory, Sorrachai Yingchareonthawornchai

posted Jul 27, 2019, 10:52 AM by Danupon Nanongkai [ updated Nov 24, 2019, 10:39 AM ]

We welcome the following visitors during Summer 2019:

Parinya Chalermsook, Aalto University, Finland (July 2019).
So-Hyeon (Sophie) Park, Yale University, USA (June-July 2019).
Michal Dory, Technion, Israel (August 2019).
Sorrachai Yingchareonthawornchai, Aalto University, Finland (August 2019).

[Award] Alumni Thatchaphol received the best paper award at PODC 2019

posted Jul 19, 2019, 1:56 PM by Danupon Nanongkai

Our alumni, Thatchaphol Saranurak, received the best paper award at PODC 2019 for his paper with Yi-Jun Chang "Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration". As mentioned in the paper, the paper follows the high-level approach in the STOC'17 paper written while Thatchphol was a student here.

6th Swedish Summer School in Computer Science 2019

posted Jul 16, 2019, 9:12 PM by Danupon Nanongkai [ updated Nov 24, 2019, 10:40 AM ]

All of us organized and attended the summer school for a week in July 2019. We thank Madhu Sudan and Luca Trevisan for the great lectures!

https://s3cs.eecs.kth.se/

[Travel, Talk] STOC 2019 in Phoenix

posted Jun 30, 2019, 10:10 AM by Danupon Nanongkai

Mohit presented the following paper in STOC 2019 in Phoenix (as part of the FCRC 2019): Distributed Edge Connectivity in Sublinear Time (Mohit Daga, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak).
Sorrachai (Aalto) presented another paper co-authored by me (Danupon): Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme (Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai)
I (Danupon) thank Thatchaphol Saranurak for presenting the following paper for Aaron and me: Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time (Aaron Bernstein, Danupon Nanongkai).
We thank Oded Goldreich for mentioning two of the above talks.
At the same location, but different conference, my next-door colleague, Philip Haller, received a SIGPLAN award. Congratulations!

[Publication] FOCS 2019

posted Jun 25, 2019, 12:36 AM by Danupon Nanongkai [ updated Jul 1, 2019, 9:57 PM ]

The following papers from our team were accepted to FOCS 2019 - the 60th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]

A New Deterministic Algorithm for Dynamic Set Cover

Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai

Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time

Jan van den Brand, Danupon Nanongkai

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds [📄arXiv]

Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak

Sensitive Distance and Reachability Oracles for Large Batch Updates

Jan van den Brand, Thatchaphol Saranurak

[Travel] Highlights of Algorithms (Copenhagen) & ADS (Bertinoro)

posted Jun 19, 2019, 4:25 PM by Danupon Nanongkai [ updated Jul 4, 2019, 10:10 AM ]

The whole group (Sagnik, Mohit, Jan, Danupon) attanded Highlights of Algorithms (HALG) in June 2019 in Copenhagen, Denmark.

Jan attended 9th Bertinoro Workshop on Algorithms and Data Structures (ADS 2019) in June 2019 in Bertinoro, Italy. He also gave a talk on "Algebraic dynamic graph algorithms and data structures".

[Travel,Talk] Danupon in Wamga(Venice), Padova, Vienna

posted Apr 23, 2019, 11:31 AM by Danupon Nanongkai [ updated Apr 25, 2019, 8:38 AM ]

In April 2019:

I (Danupon) spent 4-5 days in the Workshop on Graph Algorithms 2019 (Wamga) in Venice, Italy, and gave a talk "Distributed Shortest Paths, Exactly". I'd like to thank the organizers from the University of Warwick for the invitation. It's also a pleasure to meet many people, including my ex-student, Thatchaphol Saranurak.
I then spent a few days at the University of Padova. Thanks my ex-postdoc Michele Scquizzato for supporting the trip.
Then I spent a week at the University of Vienna. Thanks my ex-postdoc supervisor Monika Henzinger for supporting the trip, and thank my co-author Sayan Bhattacharya for joining the discussions.

Picture from Wamga in Venice.

[Travel] Sagnik in Paris

posted Apr 23, 2019, 11:16 AM by Danupon Nanongkai

In April, Sagnik visited IRIF in Paris for a week. We thank Sophie Laplante for supporting his trip.

[Travel] Sagnik at STACS'19, Berlin

posted Mar 24, 2019, 9:13 AM by Danupon Nanongkai

In March 2019, Sagnik Mukhopadhyay attended STACS 2019 in Berlin to present his work "Lifting theorems for Equality."

[Travel,Talk] Danupon at Sapienza Università di Roma, Rome

posted Mar 14, 2019, 12:09 AM by Danupon Nanongkai [ updated Apr 25, 2019, 8:38 AM ]

In March 2019, Danupon gave a survey seminar on "Dynamic graph algorithms and complexity" at Sapienza Università di Roma in Rome, Italy. He thanks the research group ARC (Algorithms, Randomisation, Computation) for the invitation and support.

[Travel] Danupon in Paris, February 2019

posted Jan 7, 2019, 8:20 AM by Danupon Nanongkai [ updated Apr 23, 2019, 11:20 AM ]

Danupon spent February 2019 at École normale supérieure (ENS), Paris, and gave the following talks.

"Dynamic graph algorithms and complexity" at ENS on February 13 at 5pm. Click the link for details.
"Distributed Shortest Paths, Exactly" at IRIF on February 19 at 11am. Click the link for details.

(Edit post)

[Talk] Danupon's talk at VISTEC (Thailand)

posted Dec 22, 2018, 5:10 AM by Danupon Nanongkai

In December, Danupon gave a talk "Advances in the Theory of Graph (Network) Algorithms, and a Little Beyond" at Symposium on Frontier Research in Information Science and Technology at VISTEC (Vidyasirimedhi Institute of Science and Technology), Thailand.

[Travel+Visitor] Jan, Mohit, Danupon at FOCS'18 (Paris) + Jason Li's visit

posted Nov 14, 2018, 10:20 AM by Danupon Nanongkai [ updated Dec 24, 2018, 9:53 AM ]

Jan, Mohit, and Danupon attended FOCS'18 in Paris in October 2018. Before that Jason Li (PhD student, CMU) visited us for a couple of days.

In this occasion, our colleague, Johan Hastad received the Knuth prize and gave the Knuth lecture (picture above).

[Travel,Talk] Danupon@Copenhagen Oct'18

posted Oct 27, 2018, 5:57 PM by Danupon Nanongkai [ updated Apr 25, 2019, 8:39 AM ]

In October 2018, Danupon made another visit to Basic Algorithms Research Copenhagen (BARC) is at the University of Copenhagen. This time he gave a talk on distributed algorithms for all-pairs shortest paths.

[Travel] Danupon@Vienna'18

posted Sep 14, 2018, 9:50 PM by Danupon Nanongkai [ updated Sep 14, 2018, 9:50 PM ]

In September 2018, Danupon visited the University of Vienna. Annually meetings in Vienna have played important roles in on-going research projects with Monika Henzinger and Sayan Battacharya.

Thatchaphol's PhD defense

posted Aug 28, 2018, 11:25 AM by Danupon Nanongkai

On Aug. 27, 2018, Thatchaphol has successfully defend his thesis at KTH.

We thank Piotr Sankowski for being Thatchaphol's opponent, Inge Li Gørtz, Thore Husfeldt, and Andrzej Lingas for being on the grading committee, Per Austrin for chairing the event, and Johan Håstad and Jkob Nordström for giving suggestions throughout.

Thatchaphol will start his research assistant professor position at Toyoto Technological Institute at Chicago soon.

Swedish Summer School in Computer Science

posted Aug 11, 2018, 5:33 PM by Danupon Nanongkai [ updated Aug 21, 2018, 5:26 PM ]

In August 2018, we have organized the 5th version of Swedish Summer School in Computer Science (https://s3cs.eecs.kth.se/). Danupon, Mohit, Jan, Thatchaphol were there. It was an amazing week to learn about quantum computing and lattice-based cryptography, and meet smart people from around the world. We thanks Oded Regev and Ronald de Wolf for excellent lectures and all participants for all fun interactions!

[Travel] Thatchaphol and Jan in Warsaw

posted Jul 22, 2018, 11:42 AM by Danupon Nanongkai

In July 2018, Thatchaphol and Jan visited Piotr Sankowski and his research group at the University of Warsaw. We thank Piotr for supporting this trip.

[Travel] Summer School on Algorithms and Lower Bounds — Jul 10, 2018 8:16:10 PM

[Visitors] Summer visiting PhD students — Jun 23, 2018 9:58:40 AM

[Visitors] Aaron Bernstein, He Sun, Kaz Makino, Krikamol Muandet, Parinya Chalermsook — Jun 19, 2018 8:11:03 PM

[Travel] Danupon@Aalto — Jun 12, 2018 6:04:28 PM

[Talk,Travel] Dagstuhl "High-Performance Graph Algorithms" — Jun 12, 2018 5:58:17 PM

Michele's paper accepted to SPAA'18 — Apr 21, 2018 12:20:41 PM

Switzerland: IDSIA, EPFL, Google-Zurich, ETHZ — Apr 18, 2018 8:54:59 PM

Michele and Thatchaphol attended "Algorithms and Optimization" PhD Workshop at Google Zurich. — Apr 13, 2018 7:57:09 PM

Thatchaphol to join TTIC — Apr 3, 2018 4:22:05 AM

[Light article] Mohit Daga — Mar 30, 2018 3:51:34 AM

[Talk] TCS+ — Mar 7, 2018 6:28:57 PM

[Paper,Travel] Thatchaphol's paper (and 3 others from KTH) accepted to STOC'18 — Feb 27, 2018 12:55:26 PM