Professorship Chalermsook Parinya

Research output

Research output per year 2017 2020

• 23 Conference contribution
• 5 Article
• 1 Conference article
• 1 Review Article
• 1 More
  • 1 Working paper

Research output per year

Research output per year

Search results

• 2020

  A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs

  Beyer, S., Chimani, M. & Spoerhase, J., 1 Jan 2020, Computing and Combinatorics - 26th International Conference, COCOON 2020, Proceedings. Kim, D., Uma, R. N., Cai, Z. & Lee, D. H. (eds.). p. 347-359 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12273 LNCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  • Primal-dual Algorithm
  • Spanning Subgraph
  • Approximation algorithms
  • Approximation Algorithms
  • Network Design

• Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms

  Forster, S., Nanongkai, D., Yang, L., Saranurak, T. & Yingchareonthawornchai, S., 1 Jan 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). ACM, p. 2046-2065 20 p.

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  • Query
  • Connectivity
  • Linear Time
  • Testing
  • Computing
  1 Citation (Scopus)

• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more

  Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D. & Trevisan, L., 2020, In: SIAM JOURNAL ON COMPUTING. 49, 4, p. 772-810 39 p.

  Research output: Contribution to journal › Article › Scientific › peer-review

  Open Access

  File
  81 Downloads (Pure)

• How Many Zeros of a Random Sparse Polynomial Are Real?

  Jindal, G., Pandey, A., Shukla, H. & Zisopoulos, C., 21 Jul 2020, ISSAC 2020 - Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation. Mantzaflaris, A. (ed.). ACM, p. 273-280 8 p.

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  • Number of Real Zeros
  • Sparse Polynomials
  • Random Polynomials
  • Standard Normal distribution
  • Zero

• Improved learning of k-parities

  Bhattacharyya, A., Gadekar, A. & Rajgopal, N., 6 Nov 2020, In: Theoretical Computer Science. 840, p. 249-256 8 p.

  Research output: Contribution to journal › Article › Scientific › peer-review

  • Parity
  • Learning
  • Time Complexity
  • Hamming Weight
  • Trade-offs

• Multi-transversals for Triangles and the Tuza's Conjecture

  Chalermsook, P., Khuller, S., Sukprasert, P. & Uniyal, S., 2020, PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20). p. 1955-1974 20 p.

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  • Vertical
  • Triangle
  • Triangle-free
  • Multiset
  • Subset

• New binary search tree bounds via geometric inversions

  Chalermsook, P. & Jiamjitrak, W. P., 1 Aug 2020, 28th Annual European Symposium on Algorithms, ESA 2020. Grandoni, F., Herman, G. & Sanders, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 16 p. 28. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 173).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  File

  • Embeddings (Algorithms)
  • Costs
  6 Downloads (Pure)

• On Finding Balanced Bicliques via Matchings

  Chalermsook, P., Jiamjitrak, W. P. & Orgo, L., 2020, Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Revised Selected Papers. Adler, I. & Müller, H. (eds.). p. 238-247 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12301 LNCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  File

  • Bicliques
  • Approximation algorithms
  • Computational complexity
  • Approximation Algorithms
  • Subgraph
  40 Downloads (Pure)

• Pinning down the strong wilber 1 bound for binary search trees

  Chalermsook, P., Chuzhoy, J. & Saranurak, T., 1 Aug 2020, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020. Byrka, J. & Meka, R. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 21 p. 33. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 176).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  File

  • Approximation algorithms
  • Data structures
  • Costs
  6 Downloads (Pure)

• PTAS for Steiner Tree on Map Graphs

  Byrka, J., Lewandowski, M., Meesum, S. M., Spoerhase, J. & Uniyal, S., 2020, LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. Kohayakawa, Y. & Miyazawa, F. K. (eds.). p. 3-14 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12118 LNCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  • Steiner Tree
  • Steiner Tree Problem
  • Spanner
  • Vertex of a graph
  • Graph in graph theory

• Worst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting

  Yingchareonthawornchai, S., Roy, P. C., Laekhanukit, B., Torng, E. & Deb, K., 8 Jul 2020, GECCO 2020 Companion - Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion. ACM, p. 185-186 2 p.

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  File

  • Sorting
  • Hardness
  • Fast Algorithm
  • Multiobjective Optimization Problems
  • Complexity Theory
  71 Downloads (Pure)
• 2019

  A deterministic PTAS for the algebraic rank of bounded degree polynomials

  Bhargava, V., Bläser, M., Jindal, G. & Pandey, A., 1 Jan 2019, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 647-661 15 p.

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  File

  • Polynomial Time Approximation Scheme
  • Polynomials
  • Polynomial
  • Computing
  • Circuit Complexity
  121 Downloads (Pure)

• An optimal O(nm) algorithm for enumerating all walks common to all closed edge-covering walks of a graph

  Cairo, M., Medvedev, P., Acosta, N. O., Rizzi, R. & Tomescu, A. I., 1 Jul 2019, In: ACM Transactions on Algorithms. 15, 4, p. 1-17 48.

  Research output: Contribution to journal › Article › Scientific › peer-review

  Open Access

  File

  • Walk
  • Covering
  • Closed
  • Genome
  • Graph in graph theory
  1 Citation (Scopus)

  49 Downloads (Pure)

• A tight approximation for submodular maximization with mixed packing and covering constraints

  Mizrachi, E., Schwartz, R., Spoerhase, J. & Uniyal, S., 1 Jul 2019, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Chatzigiannakis, I., Baier, C., Leonardi, S. & Flocchini, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 85. (Leibniz international proceedings in informatics; vol. 132).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  File

  • Approximation algorithms
  • Dynamic programming
  • Machine learning
  13 Downloads (Pure)

• A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs

  Chalermsook, P., Schmid, A. & Uniyal, S., 2019, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-14 14 p. 19. (Leibniz international proceedings in informatics; vol. 126).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  File

  • Cactus
  • Planar graph
  • Approximation Algorithms
  • Subgraph
  • Local Search
  4 Downloads (Pure)

• Breaking quadratic time for small vertex connectivity and an approximation scheme

  Nanongkai, D., Saranurak, T. & Yingchareonthawornchai, S., 23 Jun 2019, STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Charikar, M. & Cohen, E. (eds.). ACM, p. 241-252 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  File

  • Separators
  • Directed graphs
  • Approximation algorithms
  • Seed
  • Networks (circuits)
  3 Citations (Scopus)

  98 Downloads (Pure)

• On the complexity of Compact Set r-Packing

  Gadekar, A., 24 Nov 2019, (Submitted).

  Research output: Working paper › Scientific

  • Packing
  • Compact Set
  • Set Packing
  • Packing Problem
  • Exponential time

• On the complexity of symmetric polynomials

  Bläser, M. & Jindal, G., 1 Jan 2019, 10th Innovations in Theoretical Computer Science, ITCS 2019. Blum, A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-14 47. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 124).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  File

  • Polynomials
  • Boolean functions
  • Testing
  • Networks (circuits)
  1 Citation (Scopus)

  69 Downloads (Pure)

• Zip Trees

  Jiamjitrak, W., 2019, (Accepted/In press) In: ACM Transactions on Algorithms.

  Research output: Contribution to journal › Review Article › peer-review
• 2018

  Approximating node-weighted k-MST on planar graphs

  Byrka, J., Lewandowski, M. & Spoerhase, J., 1 Jan 2018, Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Revised Selected Papers. Epstein, L. & Erlebach, T. (eds.). p. 87-101 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11312 LNCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  • Minimum Spanning Tree
  • Lagrangian multiplier
  • Planar graph
  • Vertex of a graph
  • Lagrangian Relaxation

• Approximation schemes for geometric coverage problems

  Chaplick, S., De, M., Ravsky, A. & Spoerhase, J., 1 Aug 2018, In: Leibniz international proceedings in informatics. 112, p. 1-15

  Research output: Contribution to journal › Conference article › Scientific › peer-review

  Open Access

  File

  • Separators
  • Color
  2 Citations (Scopus)

  14 Downloads (Pure)

• Improved learning of k-parities

  Bhattacharyya, A., Gadekar, A. & Rajgopal, N., 1 Jan 2018, Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings. p. 542-553 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10976 LNCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  • Parity
  • Learning
  • Time Complexity
  • Hamming Weight
  • Trade-offs
  1 Citation (Scopus)

• Multi-finger binary search trees

  Chalermsook, P., Goswami, M., Kozma, L., Mehlhorn, K. & Saranurak, T., 2018, 29th International Symposium on Algorithms and Computation (ISAAC 2018). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-26 (Leibniz International Proceedings in Informatics (LIPIcs)).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  File
  27 Downloads (Pure)

• New Tools and Connections for Exponential-Time Approximation

  Bansal, N., Chalermsook, P., Laekhanukit, B., Nanongkai, D. & Nederlof, J., 2018, In: Algorithmica.

  Research output: Contribution to journal › Article › Scientific › peer-review

  Open Access

  File

  • Exponential time
  • Approximation algorithms
  • Approximation
  • Approximation Algorithms
  • Maximum Independent Set
  4 Citations (Scopus)

  121 Downloads (Pure)

• Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity

  Chan, T. M., Dijk, T. C. V., Fleszar, K., Spoerhase, J. & Wolff, A., 2018, 29th International Symposium on Algorithms and Computation (ISAAC 2018). p. 1-13 62. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 123).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  File

  • Decomposition
  • Set theory
  • Resource allocation
  3 Downloads (Pure)

• Submodular unsplittable flow on trees

  Adamaszek, A., Chalermsook, P., Ene, A. & Wiese, A., Nov 2018, In: Mathematical Programming. 172, 1-2, p. 565–589

  Research output: Contribution to journal › Article › Scientific › peer-review

  Open Access

  File

  • Path
  • Approximation algorithms
  • Pathwidth
  • Submodular Function
  • Objective function
  1 Citation (Scopus)

  166 Downloads (Pure)

• Survivable network design for group connectivity in low-treewidth graphs

  Chalermsook, P., Das, S., Even, G., Laekhanukit, B. & Vaz, D., 1 Aug 2018, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 8. (Leibniz International Proceedings in Informatics; vol. 116).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  Open Access

  File

  • Approximation algorithms
  • Labels
  • Hardness
  • Costs
  22 Downloads (Pure)
• 2017

  Beyond metric embedding: Approximating group steiner trees on bounded treewidth graphs

  Chalermsook, P., Das, S., Laekhanukit, B. & Vaz, D., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. ACM, p. 737-751 15 p.

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  • Metric Embeddings
  • Steiner Tree
  • Bounded Treewidth
  • Approximation algorithms
  • Polynomials
  3 Citations (Scopus)

• Finding triangles for maximum planar subgraphs

  Chalermsook, P. & Schmid, A., 2017, WALCOM: Algorithms and Computation - 11th International Conference and Workshops, WALCOM 2017, Proceedings. p. 373-384 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10167 LNCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  • Approximation algorithms
  • Triangle
  • Subgraph
  • Byproducts
  • Greedy Algorithm
  4 Citations (Scopus)

• From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

  Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D. & Trevisan, L., 2017, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. p. 743-754 12 p. (Annual Symposium on Foundations of Computer Science).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  • Approximation algorithms
  37 Citations (Scopus)

• New integrality gap results for the firefighters problem on trees

  Chalermsook, P. & Vaz, D., 2017, Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers. Vol. 10138 LNCS. p. 65-77 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10138 LNCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

  • Integrality
  • Fires
  • LP Rounding
  • LP Relaxation
  • Viruses
  3 Citations (Scopus)