ERC ALGOCom
(2018-2024)
Overview
The overarching goal of ALGOCom is to explore the transfer of techniques between algorithms and combinatorics, e.g., how combinatorics perspectives can be used in approaching long-standing open problems in algorithms, or how algorithmic techniques can lead to progresses or inspire new research questions in combinatorics. We look at problems from various domains of theoretical computer science including data structures, approximation and parameterized algorithms, and online algorithms. Broadly speaking, we aim at two concrete objectives:
To develop algorithmic techniques that connect various areas of algorithms (e.g., parameterized and approximation algorithms), and
To make concrete progresses on long-standing open problems (e.g., the dynamic optimality conjecture for binary search trees).
The "combinatorics lens" is central in our study.
Project Members
Parinya Chalermsook, PI
Joachim Spoerhase, Research fellow
Gorav Jindal, Postdoc
Kamyar Khodamoradi, Postdoc
Ameet Gadekar, PhD student
Wanchote Jiamjitrak, PhD student
Ly Orgo, PhD student
Sorrachai Yingchareonthawornchai, PhD student
(Aalto distinguished dissertation award, Simons-Berkeley research fellow, Nokia scholarship)
Max Franck, Research assistant
Publications (partially) funded by the project
2024
The Group Access Bounds for Binary Search Trees
P. Chalermsook, M. Gupta, W. Jiamjitrak, A. Pareek, S. Yingchareonthawornchai
ICALP 2024
Parameterized Approximation for Robust Clustering in Geometric Spaces
F. Abbassi, S. Banerjee, J. Byrka, P. Chalermsook, A. Gadekar, K. Khodamoradi, D. Marx, R. Sharma, J. Spoerhase
ICALP 2024
Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
P. Chalermsook, S. Pettie, S. Yingchareonthawornchai
SODA 2024
Approximating Sparsest Cuts in Low-Treewidth Graphs via Combinatorial Diameter
P. Chalermsook, M. Kaul, M. Mnich, J. Spoerhase, S. Uniyal, D. Vaz
ACM Transaction on Algorithms (TALG) 2024
An FPTAS for Connectivity Interdiction
C. Huang, N. Obscura Acosta, S. Yingchareonthawornchai
IPCO 2024
2023
Independent Set in k-Claw-Free Graphs: Conditional Chi-Boundedness and The Power of LP/SDP Relaxations
P. Chalermsook, A. Gadekar, K. Khodamoradi, J. Spoerhase
WAOA 2023
On the parameterized complexity of Compact Set Packing
A. Gadekar
WALCOM 2023 (best student paper)
Polynomial-time Approximation of Independent Set Parameterized by Treewidth
P. Chalermsook, F. Fomin, T. Hamm, T. Korhonen, J. Nederlof, L. Orgo
ESA 2023
Parameterized Approximation Schemes for Clustering with General Norm Objectives
F. Abbassi, S. Banerjee, J. Byrka, P. Chalermsook, A. Gadekar, K. Khodamoradi, D. Marx, R. Sharma, J. Spoerhase
FOCS 2023
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
P. Chalermsook, M. Gupta, W. Jiamjitrak, N. Obscura Acosta, A. Pareek, S. Yingchareonthawornchai
SODA 2023
2022
Approximating k-Edge Connected Spanning Subgraphs via a Near-Linear Time LP Solver
P. Chalermsook, C. Huang, D. Nanongkai, T. Saranurak, P. Sukprasert, S. Yingchareonthawornchai
ICALP 2022
Deterministic Small Vertex Connectivity in Almost Linear Time
T. Saranurak, S. Yingchareonthawornchai
FOCS 2022
Clustering with fair-center representation: Parameterized approximation algorithms and heuristics
S. Thejaswi, A. Gadekar, B. Ordozgoiti, M. Osadnik
KDD 2022
2021
Vertex Connectivity in Poly-logarithmic Max-flows
J. Li, D. Nanongkai, D. Panigrahi, T. Saranurak, S. Yingchareonthawornchai
STOC 2021 (invited to special issues)
On Minimum Generalized Manhattan Connections
A. Antoniadis, M. Capretto, P. Chalermsook, C. Damerius, P. Kling, L. Nölke, N. Obscura Acosta and J. Spoerhase
WADS 2021
Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity
M. Franck, S. Yingchareonthawornchai
SEA 2021
Coloring and Maximum Weight Independent Set of Rectangles
P. Chalermsook and B. Walczak
SODA 2021 (invited to special issues)
Vertex Sparsification for Edge Connectivity
P. Chalermsook, S. Das, B. Laekhanukit, Y. Kook, YP Liu, R. Peng, M. Sellke, D. Vaz
SODA 2021
2020
From Gap-ETH to FPT Inapproximability: Cliques, Dominating Set, and More.
P. Chalermsook, M. Cygan, G. Kortsarz, B. Laekhanukit, P. Manurangsi, D. Nanongkai, L. Trevisan.
FOCS 2017 & SIAM JOURNAL ON COMPUTING (2020)
New Binary Search Tree Bounds via Geometric Inversions
P. Chalermsook, W. Jiamjitrak
ESA 2020
Pinning Down the Strong Wilber 1 Bound for Binary Search Trees
P. Chalermsook, J. Chuzhoy, T. Saranurak
APPROX 2020 (invited to special issues)
Multi-transversal for Triangles and the Tuza conjecture
P. Chalermsook, S. Khuller, P. Sukprasert, S. Uniyal
SODA 2020
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
S. Forster, D. Nanongkai, L. Yang, T. Saranurak, S. Yingchareonthawornchai
SODA 2020
On Finding Balanced Bicliques via Matchings
P.Chalermsook, W. Jiamjitrak, L. Orgo
WG 2020
How Many Zeros of a Random Sparse Polynomial Are Real?
Gorav Jindal, Anurag Pandey, Himanshu Shukla, and Charilaos Zisopoulos
ISSAC 2020
2019
A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials
V. Bhargava, M. Bläser, G. Jindal, and A. Pandey
SODA 2019
On the Complexity of Symmetric Polynomials
M. Bläser, G. Jindal
ITCS 2019
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints.
E. Mizrachi, R. Schwarz, J. Spoerhase, S. Uniyal
ICALP 2019
A Tight Extremal Bound on the Lovasz Cactus Number in Planar Graphs
P. Chalermsook, A. Schmid, S. Uniyal
STACS 2019
New Tools and Connections for Exponential-Time Approximation
N.Bansal, P.Chalermsook, B. Laekhanukit, D. Nanongkai, J. Nederlof
Algorithmica, 2019
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
D. Nanongkai, T. Saranurak, S. Yingchareonthawornchai
STOC 2019 (invited to special issues)
2018
Multi-finger Binary Search Trees
P. Chalermsook, M. Goswami, L. Kozma, K. Mehlhorn, T. Saranurak
ISAAC 2018
Survivable Network Design for Group Connectivity in Low-Treewidth Graphs
P. Chalermsook, G. Even, S. Das, B. Laekhanukit, D. Vaz
APPROX 2018