Jakub Łącki

Last updated September 2015.

Current occupation

Research scientist at Google Research, New York

Education

PhD studies in Informatics at University of Warsaw

• PhD in Computer Science (2015)
  • Thesis title: Dynamic graph algorithms for connectivity problems

Double Degree Program in Computer Science and Mathematics at University of Warsaw

• Master of Science in Computer Science (2010)
  • Thesis title: Dynamic algorithms for transitive closure and strongly connected components
• Bachelor of Science in Mathematics (2010)
  • Thesis title: Degree distribution in a Barabási-Albert model with edge deletion

Work experience

• Postdoctoral researcher at Sapienza University of Rome
  • 2015 — 2016
• Google, Mountain View
  • February 2013 — May 2013, software engineering intern
• Scientific assistant at University of Warsaw
  • 2010 — 2012
• Google, New York
  • April 2009 — July 2009, software engineering intern
• Teaching assistant intern at University of Warsaw
  • 2008 — 2010

Awards

• Google European Doctoral Fellowship in Graph Algorithms (2012)
• Symposium on Discrete Algorithms 2011, San Francisco
  • Best Student Paper Award for paper Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components
• Ministry of Science and Higher Education Scholarship (2010)

Other activities

• International Olympiad in Informatics
  • 2014 — 2016, international scientific committee member (elected), chair of the committee for 2016
• International Olympiad in Informatics
  • 2011, 2012, 2013 — team leader
• Algorithmic Engagements algorithmic contest
  • 2009, 2010, 2011, 2012, 2013 — scientific secretary, responsible for task selection
• Antoni Kreczmar's scientific and training camp (IOI preparation camp for high school students)
  • 2006, 2007, 2008, 2009, 2010, 2011, 2012 — organizer
• Polish ACM ICPC Subregional contest
  • 2011, 2012, 2013, 2014 — judge
• Maratona de Programação (ACM ICPC preparation camp for South American students), Campinas, Brazil
  • 2014 — lecturer
• Polish Olympiad in Informatics
  • jury member since 2008
• Baltic Olympiad in Informatics
  • 2008 — scientific commitee member
  • 2010 — problem setter
• Central European Olympiad in Informatics
  • 2011 — problem setter and scientific committee member

Selected papers

• Decremental Single-Source Reachability and Strongly Connected Components in O(m sqrt(n log n)) Total Update Time
  • Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Łącki, Nikos Parotsidis, FOCS 2016
• Algorithmic Complexity of Power Law Networks
  • Paweł Brach, Marek Cygan, Jakub Łącki, Piotr Sankowski, SODA 2016
• The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
  • Jakub Łącki, Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski, Anna Zych, STOC 2015
• Optimal Decremental Connectivity in Planar Graphs
  • Jakub Łącki, Piotr Sankowski, STACS 2015 and Theory of Computing Systems
• Single Source - All Sinks Max Flows in Planar Digraphs
  • Jakub Łącki, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen, FOCS 2012
• Min-Cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time
  • Jakub Łącki, Piotr Sankowski, ESA 2011
• Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components
  • Jakub Łącki, SODA 2011 and ACM Transactions on Algorithms

Achievements in algorithmic and programming competitions

• ACM-ICPC Regional Contest
  • November 2009, Wrocław, Poland — 4^th place
  • November 2008, Wrocław, Poland — 2^nd place
  • November 2007, Prague, Czech Republic — 5^th place
  • November 2006, Budapest, Hungary — 2^nd place
  • November 2005, Budapest, Hungary — 8^th place
• Polish Academic Collegiate Programming Contest
  • November 2009, Poznań — WINNER
  • November 2008, Poznań — WINNER
  • November 2007, Poznań — 2^nd place
  • November 2006, Kraków — 2^nd place
  • October 2005, Kraków — 4^th place
• Poznań Open Team Programming Contest
  • December 2007, Poznań — WINNER
  • December 2006, Poznań — WINNER
  • December 2005, Poznań — 2^nd place
• International Olympiad in Informatics
  • August 2005, Nowy Sącz, Poland — GOLD MEDAL (external contestant)
  • August 2004, Athens, Greece — silver medal
• Central European Olympiad in Informatics
  • July 2004, Rzeszów, Poland — silver medal
• Baltic Olympiad in Informatics
  • April 2004, Ventspils, Latvia — GOLD MEDAL
• Polish Olympiad in Informatics
  • April 2005, Sopot — silver medal
  • April 2004, Sopot — silver medal
  • April 2003, Sopot — finalist