Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Yu Chen, Sanjeev Khanna, and Zihan Tan. Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 37:1-37:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.ICALP.2023.37, author = {Chen, Yu and Khanna, Sanjeev and Tan, Zihan}, title = {{Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {37:1--37:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.37}, URN = {urn:nbn:de:0030-drops-180892}, doi = {10.4230/LIPIcs.ICALP.2023.37}, annote = {Keywords: Minimum spanning tree, travelling salesman problem, streaming algorithms} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Sepehr Assadi. Graph Coloring, Palette Sparsification, and Beyond (Invited Talk). In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{assadi:LIPIcs.DISC.2022.1, author = {Assadi, Sepehr}, title = {{Graph Coloring, Palette Sparsification, and Beyond}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.1}, URN = {urn:nbn:de:0030-drops-171920}, doi = {10.4230/LIPIcs.DISC.2022.1}, annote = {Keywords: Graph coloring, Palette Sparsification, Sublinear Algorithms} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Sanjeev Khanna and Christian Konrad. Optimal Bounds for Dominating Set in Graph Streams. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 93:1-93:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{khanna_et_al:LIPIcs.ITCS.2022.93, author = {Khanna, Sanjeev and Konrad, Christian}, title = {{Optimal Bounds for Dominating Set in Graph Streams}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {93:1--93: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.93}, URN = {urn:nbn:de:0030-drops-156894}, doi = {10.4230/LIPIcs.ITCS.2022.93}, annote = {Keywords: Streaming algorithms, communication complexity, information complexity, dominating set} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Sepehr Assadi, Deeparnab Chakrabarty, and Sanjeev Khanna. Graph Connectivity and Single Element Recovery via Linear and OR Queries. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 7:1-7:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{assadi_et_al:LIPIcs.ESA.2021.7, author = {Assadi, Sepehr and Chakrabarty, Deeparnab and Khanna, Sanjeev}, title = {{Graph Connectivity and Single Element Recovery via Linear and OR Queries}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {7:1--7:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.7}, URN = {urn:nbn:de:0030-drops-145880}, doi = {10.4230/LIPIcs.ESA.2021.7}, annote = {Keywords: Query Models, Graph Connectivity, Group Testing, Duality} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Yu Chen, Sanjeev Khanna, and Ansh Nagda. Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 53:1-53:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen_et_al:LIPIcs.ICALP.2021.53, author = {Chen, Yu and Khanna, Sanjeev and Nagda, Ansh}, title = {{Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {53:1--53:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.53}, URN = {urn:nbn:de:0030-drops-141227}, doi = {10.4230/LIPIcs.ICALP.2021.53}, annote = {Keywords: hypergraphs, graph sparsification, cut queries} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal, and Amit Kumar. On Sampling Based Algorithms for k-Means. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 13:1-13:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{bhattacharya_et_al:LIPIcs.FSTTCS.2020.13, author = {Bhattacharya, Anup and Goyal, Dishant and Jaiswal, Ragesh and Kumar, Amit}, title = {{On Sampling Based Algorithms for k-Means}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {13:1--13:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.13}, URN = {urn:nbn:de:0030-drops-132549}, doi = {10.4230/LIPIcs.FSTTCS.2020.13}, annote = {Keywords: k-means, low rank approximation} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Noga Alon and Sepehr Assadi. Palette Sparsification Beyond (Δ+1) Vertex Coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 6:1-6:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{alon_et_al:LIPIcs.APPROX/RANDOM.2020.6, author = {Alon, Noga and Assadi, Sepehr}, title = {{Palette Sparsification Beyond (\Delta+1) Vertex Coloring}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {6:1--6:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.6}, URN = {urn:nbn:de:0030-drops-126096}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.6}, annote = {Keywords: Graph coloring, palette sparsification, sublinear algorithms, list-coloring} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Yu Chen, Sampath Kannan, and Sanjeev Khanna. Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 30:1-30:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chen_et_al:LIPIcs.ICALP.2020.30, author = {Chen, Yu and Kannan, Sampath and Khanna, Sanjeev}, title = {{Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {30:1--30:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.30}, URN = {urn:nbn:de:0030-drops-124372}, doi = {10.4230/LIPIcs.ICALP.2020.30}, annote = {Keywords: sublinear algorithms, TSP, streaming algorithms, query complexity} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Anindya De, Sanjeev Khanna, Huan Li, and Hesam Nikpey. An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 37:1-37:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{de_et_al:LIPIcs.ICALP.2020.37, author = {De, Anindya and Khanna, Sanjeev and Li, Huan and Nikpey, Hesam}, title = {{An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {37:1--37:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.37}, URN = {urn:nbn:de:0030-drops-124449}, doi = {10.4230/LIPIcs.ICALP.2020.37}, annote = {Keywords: Efficient PTAS, Makespan Minimization, Scheduling, Stochastic Load Balancing, Poisson Distribution} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 6:1-6:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{assadi_et_al:LIPIcs.ITCS.2019.6, author = {Assadi, Sepehr and Kapralov, Michael and Khanna, Sanjeev}, title = {{A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {6:1--6:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.6}, URN = {urn:nbn:de:0030-drops-100996}, doi = {10.4230/LIPIcs.ITCS.2019.6}, annote = {Keywords: Sublinear-time algorithms, Subgraph counting, AGM bound} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Deeparnab Chakrabarty and Sanjeev Khanna. Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 4:1-4:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{chakrabarty_et_al:OASIcs.SOSA.2018.4, author = {Chakrabarty, Deeparnab and Khanna, Sanjeev}, title = {{Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {4:1--4:11}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.4}, URN = {urn:nbn:de:0030-drops-83045}, doi = {10.4230/OASIcs.SOSA.2018.4}, annote = {Keywords: Matrix Scaling, Entropy Minimization, KL Divergence Inequalities} }
Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)
Sepehr Assadi, Sanjeev Khanna, Yang Li, and Val Tannen. Algorithms for Provisioning Queries and Analytics. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 18:1-18:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{assadi_et_al:LIPIcs.ICDT.2016.18, author = {Assadi, Sepehr and Khanna, Sanjeev and Li, Yang and Tannen, Val}, title = {{Algorithms for Provisioning Queries and Analytics}}, booktitle = {19th International Conference on Database Theory (ICDT 2016)}, pages = {18:1--18:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-002-6}, ISSN = {1868-8969}, year = {2016}, volume = {48}, editor = {Martens, Wim and Zeume, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.18}, URN = {urn:nbn:de:0030-drops-57877}, doi = {10.4230/LIPIcs.ICDT.2016.18}, annote = {Keywords: What-if Analysis, Provisioning, Data Compression, Approximate Query Answering} }
Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Sepehr Assadi, Sanjeev Khanna, Yang Li, and Val Tannen. Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 52-68, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{assadi_et_al:LIPIcs.FSTTCS.2015.52, author = {Assadi, Sepehr and Khanna, Sanjeev and Li, Yang and Tannen, Val}, title = {{Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {52--68}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.52}, URN = {urn:nbn:de:0030-drops-56361}, doi = {10.4230/LIPIcs.FSTTCS.2015.52}, annote = {Keywords: Small-space Algorithms, Maximum Matchings, Vertex Sparsifiers} }
Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Madhu Sudan. Physical limits of Communication (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 4-5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
@InProceedings{sudan:LIPIcs.FSTTCS.2011.4, author = {Sudan, Madhu}, title = {{Physical limits of Communication}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)}, pages = {4--5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-34-7}, ISSN = {1868-8969}, year = {2011}, volume = {13}, editor = {Chakraborty, Supratik and Kumar, Amit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.4}, URN = {urn:nbn:de:0030-drops-33392}, doi = {10.4230/LIPIcs.FSTTCS.2011.4}, annote = {Keywords: Analog signals, information capacity, delays} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
Sampath Kannan, Sanjeev Khanna, and Sudeepa Roy. STCON in Directed Unique-Path Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 256-267, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)
@InProceedings{kannan_et_al:LIPIcs.FSTTCS.2008.1758, author = {Kannan, Sampath and Khanna, Sanjeev and Roy, Sudeepa}, title = {{STCON in Directed Unique-Path Graphs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {256--267}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-08-8}, ISSN = {1868-8969}, year = {2008}, volume = {2}, editor = {Hariharan, Ramesh and Mukund, Madhavan and Vinay, V}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1758}, URN = {urn:nbn:de:0030-drops-17589}, doi = {10.4230/LIPIcs.FSTTCS.2008.1758}, annote = {Keywords: Algorithm, complexity, st-connectivity} }
Feedback for Dagstuhl Publishing