Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)
C. Seshadhri. Some Vignettes on Subgraph Counting Using Graph Orientations (Invited Talk). In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 3:1-3:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{seshadhri:LIPIcs.ICDT.2023.3, author = {Seshadhri, C.}, title = {{Some Vignettes on Subgraph Counting Using Graph Orientations}}, booktitle = {26th International Conference on Database Theory (ICDT 2023)}, pages = {3:1--3:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-270-9}, ISSN = {1868-8969}, year = {2023}, volume = {255}, editor = {Geerts, Floris and Vandevoort, Brecht}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.3}, URN = {urn:nbn:de:0030-drops-177454}, doi = {10.4230/LIPIcs.ICDT.2023.3}, annote = {Keywords: subgraph counting, graph degeneracy, homomorphism counting, graph algorithms} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Ronitt Rubinfeld, and Slobodan Mitrović. Massively Parallel Algorithms for Small Subgraph Counting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 39:1-39:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{biswas_et_al:LIPIcs.APPROX/RANDOM.2022.39, author = {Biswas, Amartya Shankha and Eden, Talya and Liu, Quanquan C. and Rubinfeld, Ronitt and Mitrovi\'{c}, Slobodan}, title = {{Massively Parallel Algorithms for Small Subgraph Counting}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {39:1--39:28}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.39}, URN = {urn:nbn:de:0030-drops-171619}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.39}, annote = {Keywords: triangle counting, massively parallel computation, clique counting, approximation algorithms, subgraph counting} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Balaram Behera, Edin Husić, Shweta Jain, Tim Roughgarden, and C. Seshadhri. FPT Algorithms for Finding Near-Cliques in c-Closed Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 17:1-17:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{behera_et_al:LIPIcs.ITCS.2022.17, author = {Behera, Balaram and Husi\'{c}, Edin and Jain, Shweta and Roughgarden, Tim and Seshadhri, C.}, title = {{FPT Algorithms for Finding Near-Cliques in c-Closed Graphs}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {17:1--17:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.17}, URN = {urn:nbn:de:0030-drops-156130}, doi = {10.4230/LIPIcs.ITCS.2022.17}, annote = {Keywords: c-closed graph, dense subgraphs, FPT algorithm, enumeration algorithm, k-plex, Moon-Moser theorem} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
François Le Gall and Saeed Seddighin. Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 97:1-97:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{legall_et_al:LIPIcs.ITCS.2022.97, author = {Le Gall, Fran\c{c}ois and Seddighin, Saeed}, title = {{Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {97:1--97:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.97}, URN = {urn:nbn:de:0030-drops-156934}, doi = {10.4230/LIPIcs.ITCS.2022.97}, annote = {Keywords: Longest common substring, Longest palindrome substring, Quantum algorithms, Sublinear algorithms} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Suman K. Bera, Noujan Pashanasangi, and C. Seshadhri. Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bera_et_al:LIPIcs.ITCS.2020.38, author = {Bera, Suman K. and Pashanasangi, Noujan and Seshadhri, C.}, title = {{Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {38:1--38:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.38}, URN = {urn:nbn:de:0030-drops-117239}, doi = {10.4230/LIPIcs.ITCS.2020.38}, annote = {Keywords: Subgraph counting, bounded degeneracy graphs, fine-grained complexity} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Aris Anagnostopoulos, Ilan R. Cohen, Stefano Leonardi, and Jakub Łącki. Stochastic Graph Exploration. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 136:1-136:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{anagnostopoulos_et_al:LIPIcs.ICALP.2019.136, author = {Anagnostopoulos, Aris and Cohen, Ilan R. and Leonardi, Stefano and {\L}\k{a}cki, Jakub}, title = {{Stochastic Graph Exploration}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {136:1--136:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.136}, URN = {urn:nbn:de:0030-drops-107122}, doi = {10.4230/LIPIcs.ICALP.2019.136}, annote = {Keywords: stochastic optimization, graph exploration, approximation algorithms} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Deeparnab Chakrabarty and C. Seshadhri. Adaptive Boolean Monotonicity Testing in Total Influence Time. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 20:1-20:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chakrabarty_et_al:LIPIcs.ITCS.2019.20, author = {Chakrabarty, Deeparnab and Seshadhri, C.}, title = {{Adaptive Boolean Monotonicity Testing in Total Influence Time}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {20:1--20:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.20}, URN = {urn:nbn:de:0030-drops-101133}, doi = {10.4230/LIPIcs.ITCS.2019.20}, annote = {Keywords: Property Testing, Monotonicity Testing, Influence of Boolean Functions} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein. Finding Cliques in Social Networks: A New Distribution-Free Model. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{fox_et_al:LIPIcs.ICALP.2018.55, author = {Fox, Jacob and Roughgarden, Tim and Seshadhri, C. and Wei, Fan and Wein, Nicole}, title = {{Finding Cliques in Social Networks: A New Distribution-Free Model}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {55:1--55:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.55}, URN = {urn:nbn:de:0030-drops-90596}, doi = {10.4230/LIPIcs.ICALP.2018.55}, annote = {Keywords: Graph algorithms, social networks, fixed-parameter tractability} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri. Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{baleshzar_et_al:LIPIcs.ICALP.2017.5, author = {Baleshzar, Roksana and Chakrabarty, Deeparnab and Pallavoor, Ramesh Krishnan S. and Raskhodnikova, Sofya and Seshadhri, C.}, title = {{Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {5:1--5:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.5}, URN = {urn:nbn:de:0030-drops-74844}, doi = {10.4230/LIPIcs.ICALP.2017.5}, annote = {Keywords: Property testing, unate and monotone functions} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Talya Eden, Dana Ron, and C. Seshadhri. Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{eden_et_al:LIPIcs.ICALP.2017.7, author = {Eden, Talya and Ron, Dana and Seshadhri, C.}, title = {{Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {7:1--7:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.7}, URN = {urn:nbn:de:0030-drops-73747}, doi = {10.4230/LIPIcs.ICALP.2017.7}, annote = {Keywords: Sublinear algorithms, Degree distribution, Graph moments} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Benjamin Raichel and C. Seshadhri. Avoiding the Global Sort: A Faster Contour Tree Algorithm. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{raichel_et_al:LIPIcs.SoCG.2016.57, author = {Raichel, Benjamin and Seshadhri, C.}, title = {{Avoiding the Global Sort: A Faster Contour Tree Algorithm}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {57:1--57:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.57}, URN = {urn:nbn:de:0030-drops-59490}, doi = {10.4230/LIPIcs.SoCG.2016.57}, annote = {Keywords: contour trees, computational topology, computational geometry} }
Feedback for Dagstuhl Publishing