Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Chin Ho Lee, Edward Pyne, and Salil Vadhan. On the Power of Regular and Permutation Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 44:1-44:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{lee_et_al:LIPIcs.APPROX/RANDOM.2023.44, author = {Lee, Chin Ho and Pyne, Edward and Vadhan, Salil}, title = {{On the Power of Regular and Permutation Branching Programs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {44:1--44:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.44}, URN = {urn:nbn:de:0030-drops-188698}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.44}, annote = {Keywords: Pseudorandomness, Branching Programs} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Sepehr Assadi, Michael Kapralov, and Huacheng Yu. On Constructing Spanners from Random Gaussian Projections. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 57:1-57:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{assadi_et_al:LIPIcs.APPROX/RANDOM.2023.57, author = {Assadi, Sepehr and Kapralov, Michael and Yu, Huacheng}, title = {{On Constructing Spanners from Random Gaussian Projections}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {57:1--57:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.57}, URN = {urn:nbn:de:0030-drops-188821}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.57}, annote = {Keywords: sketching algorithm, lower bound, graph spanner} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng, Jie Gao, and Chen Wang. Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 58:1-58:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ashvinkumar_et_al:LIPIcs.APPROX/RANDOM.2023.58, author = {Ashvinkumar, Vikrant and Assadi, Sepehr and Deng, Chengyuan and Gao, Jie and Wang, Chen}, title = {{Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {58:1--58:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.58}, URN = {urn:nbn:de:0030-drops-188830}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.58}, annote = {Keywords: Streaming algorithms, structural balance, pseudo-randomness generator} }
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Stephen Jaud, Anthony Wirth, and Farhana Choudhury. Maximum Coverage in Sublinear Space, Faster. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 21:1-21:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{jaud_et_al:LIPIcs.SEA.2023.21, author = {Jaud, Stephen and Wirth, Anthony and Choudhury, Farhana}, title = {{Maximum Coverage in Sublinear Space, Faster}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {21:1--21:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.21}, URN = {urn:nbn:de:0030-drops-183715}, doi = {10.4230/LIPIcs.SEA.2023.21}, annote = {Keywords: streaming algorithms, subsampling, maximum set cover, k-wise independent hash functions} }
Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)
Sepehr Assadi, Nirmit Joshi, Milind Prabhu, and Vihan Shah. Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 19:1-19:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{assadi_et_al:LIPIcs.ICDT.2023.19, author = {Assadi, Sepehr and Joshi, Nirmit and Prabhu, Milind and Shah, Vihan}, title = {{Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs}}, booktitle = {26th International Conference on Database Theory (ICDT 2023)}, pages = {19:1--19:19}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.19}, URN = {urn:nbn:de:0030-drops-177618}, doi = {10.4230/LIPIcs.ICDT.2023.19}, annote = {Keywords: Streaming algorithms, Quantile summaries, Rank estimation} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Sepehr Assadi, Aaron Bernstein, and Zachary Langley. All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 7:1-7:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{assadi_et_al:LIPIcs.ITCS.2023.7, author = {Assadi, Sepehr and Bernstein, Aaron and Langley, Zachary}, title = {{All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {7:1--7:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.7}, URN = {urn:nbn:de:0030-drops-175106}, doi = {10.4230/LIPIcs.ITCS.2023.7}, annote = {Keywords: Load Balancing, Semi-Streaming Algorithms, Semi-Matching} }
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 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Sepehr Assadi and Hoai-An Nguyen. Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 48:1-48:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{assadi_et_al:LIPIcs.APPROX/RANDOM.2022.48, author = {Assadi, Sepehr and Nguyen, Hoai-An}, title = {{Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {48:1--48:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.48}, URN = {urn:nbn:de:0030-drops-171708}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.48}, annote = {Keywords: Sublinear time algorithms, h-index, asymptotically optimal bounds, lower bounds, subgraph counting} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Kheeran K. Naidu and Vihan Shah. Space Optimal Vertex Cover in Dynamic Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 53:1-53:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{naidu_et_al:LIPIcs.APPROX/RANDOM.2022.53, author = {Naidu, Kheeran K. and Shah, Vihan}, title = {{Space Optimal Vertex Cover in Dynamic Streams}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {53:1--53:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.53}, URN = {urn:nbn:de:0030-drops-171753}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.53}, annote = {Keywords: Graph Streaming Algorithms, Vertex Cover, Dynamic Streams, Approximation Algorithm} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja. Decremental Matching in General Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 11:1-11:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{assadi_et_al:LIPIcs.ICALP.2022.11, author = {Assadi, Sepehr and Bernstein, Aaron and Dudeja, Aditi}, title = {{Decremental Matching in General Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {11:1--11:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.11}, URN = {urn:nbn:de:0030-drops-163528}, doi = {10.4230/LIPIcs.ICALP.2022.11}, annote = {Keywords: Dynamic algorithms, matching, primal-dual algorithms} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 77:1-77:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{jambulapati_et_al:LIPIcs.ICALP.2022.77, author = {Jambulapati, Arun and Jin, Yujia and Sidford, Aaron and Tian, Kevin}, title = {{Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {77:1--77:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.77}, URN = {urn:nbn:de:0030-drops-164181}, doi = {10.4230/LIPIcs.ICALP.2022.77}, annote = {Keywords: bipartite matching, decremental matching, dynamic algorithms, continuous optimization, box-simplex games, primal-dual method} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Sepehr Assadi and Vihan Shah. An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 9:1-9:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{assadi_et_al:LIPIcs.ITCS.2022.9, author = {Assadi, Sepehr and Shah, Vihan}, title = {{An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {9:1--9: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.9}, URN = {urn:nbn:de:0030-drops-156054}, doi = {10.4230/LIPIcs.ITCS.2022.9}, annote = {Keywords: Graph streaming algorithms, Sketching, Maximum matching} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Sepehr Assadi and Chen Wang. Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 10:1-10:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{assadi_et_al:LIPIcs.ITCS.2022.10, author = {Assadi, Sepehr and Wang, Chen}, title = {{Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {10:1--10:20}, 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.10}, URN = {urn:nbn:de:0030-drops-156067}, doi = {10.4230/LIPIcs.ITCS.2022.10}, annote = {Keywords: Correlation Clustering, Sublinear Algorithms, Semi-streaming Algorithms, Sublinear time Algorithms} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Sepehr Assadi and Aditi Dudeja. Ruling Sets in Random Order and Adversarial Streams. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 6:1-6:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{assadi_et_al:LIPIcs.DISC.2021.6, author = {Assadi, Sepehr and Dudeja, Aditi}, title = {{Ruling Sets in Random Order and Adversarial Streams}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {6:1--6:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.6}, URN = {urn:nbn:de:0030-drops-148086}, doi = {10.4230/LIPIcs.DISC.2021.6}, annote = {Keywords: Symmetry breaking, Ruling sets, Lower bounds, Communication Complexity} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Sepehr Assadi and Soheil Behnezhad. On the Robust Communication Complexity of Bipartite Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 48:1-48:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{assadi_et_al:LIPIcs.APPROX/RANDOM.2021.48, author = {Assadi, Sepehr and Behnezhad, Soheil}, title = {{On the Robust Communication Complexity of Bipartite Matching}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {48:1--48:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.48}, URN = {urn:nbn:de:0030-drops-147411}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.48}, annote = {Keywords: Maximum Matching, Communication Complexity, Random-Order Streaming} }
Feedback for Dagstuhl Publishing