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-dev.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 200, 36th Computational Complexity Conference (CCC 2021)
Vishnu Iyer, Avishay Tal, and Michael Whitmeyer. Junta Distance Approximation with Sub-Exponential Queries. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 24:1-24:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{iyer_et_al:LIPIcs.CCC.2021.24, author = {Iyer, Vishnu and Tal, Avishay and Whitmeyer, Michael}, title = {{Junta Distance Approximation with Sub-Exponential Queries}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {24:1--24:38}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.24}, URN = {urn:nbn:de:0030-drops-142988}, doi = {10.4230/LIPIcs.CCC.2021.24}, annote = {Keywords: Algorithms, Complexity Theory, Fourier Analysis, Juntas, Normalized Influence, Property Testing, Tolerant Property Testing} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Yuichi Yoshida. Ordered Graph Limits and Their Applications. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2021.42, author = {Ben-Eliezer, Omri and Fischer, Eldar and Levi, Amit and Yoshida, Yuichi}, title = {{Ordered Graph Limits and Their Applications}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {42:1--42:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.42}, URN = {urn:nbn:de:0030-drops-135815}, doi = {10.4230/LIPIcs.ITCS.2021.42}, annote = {Keywords: graph limits, ordered graph, graphon, cut distance, removal lemma} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Erasure-Resilient Sublinear-Time Graph Algorithms. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 80:1-80:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{levi_et_al:LIPIcs.ITCS.2021.80, author = {Levi, Amit and Pallavoor, Ramesh Krishnan S. and Raskhodnikova, Sofya and Varma, Nithin}, title = {{Erasure-Resilient Sublinear-Time Graph Algorithms}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {80:1--80:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.80}, URN = {urn:nbn:de:0030-drops-136192}, doi = {10.4230/LIPIcs.ITCS.2021.80}, annote = {Keywords: Graph property testing, Computing with incomplete information, Approximating graph parameters} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum. Hard Properties with (Very) Short PCPPs and Their Applications. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 9:1-9:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2020.9, author = {Ben-Eliezer, Omri and Fischer, Eldar and Levi, Amit and Rothblum, Ron D.}, title = {{Hard Properties with (Very) Short PCPPs and Their Applications}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {9:1--9:27}, 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.9}, URN = {urn:nbn:de:0030-drops-116949}, doi = {10.4230/LIPIcs.ITCS.2020.9}, annote = {Keywords: PCPP, Property testing, Tolerant testing, Erasure resilient testing, Randomized encoding, Coding theory} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Nathaniel Harms. Universal Communication, Universal Graphs, and Graph Labeling. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 33:1-33:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{harms:LIPIcs.ITCS.2020.33, author = {Harms, Nathaniel}, title = {{Universal Communication, Universal Graphs, and Graph Labeling}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {33:1--33:27}, 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.33}, URN = {urn:nbn:de:0030-drops-117182}, doi = {10.4230/LIPIcs.ITCS.2020.33}, annote = {Keywords: Universal graphs, graph labeling, distance labeling, planar graphs, lattices, hamming distance} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Amit Levi and Erik Waingarten. Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{levi_et_al:LIPIcs.ITCS.2019.52, author = {Levi, Amit and Waingarten, Erik}, title = {{Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {52:1--52: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.52}, URN = {urn:nbn:de:0030-drops-101452}, doi = {10.4230/LIPIcs.ITCS.2019.52}, annote = {Keywords: Property Testing, Juntas, Tolerant Testing, Boolean functions} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Amit Levi and Yuichi Yoshida. Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{levi_et_al:LIPIcs.APPROX-RANDOM.2018.17, author = {Levi, Amit and Yoshida, Yuichi}, title = {{Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {17:1--17:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, 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.2018.17}, URN = {urn:nbn:de:0030-drops-94210}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.17}, annote = {Keywords: Qudratic function minimization, Approximation Algorithms, Matrix spectral decomposition, Graph limits} }
Feedback for Dagstuhl Publishing