Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Graham Cormode, Hossein Jowhari, Morteza Monemizadeh, and S. Muthukrishnan. The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{cormode_et_al:LIPIcs.ESA.2017.29, author = {Cormode, Graham and Jowhari, Hossein and Monemizadeh, Morteza and Muthukrishnan, S.}, title = {{The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {29:1--29:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.29}, URN = {urn:nbn:de:0030-drops-78499}, doi = {10.4230/LIPIcs.ESA.2017.29}, annote = {Keywords: streaming algorithms, matching size} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, and Christian Sohler. Testable Bounded Degree Graph Properties Are Random Order Streamable. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 131:1-131:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{monemizadeh_et_al:LIPIcs.ICALP.2017.131, author = {Monemizadeh, Morteza and Muthukrishnan, S. and Peng, Pan and Sohler, Christian}, title = {{Testable Bounded Degree Graph Properties Are Random Order Streamable}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {131:1--131: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.131}, URN = {urn:nbn:de:0030-drops-74782}, doi = {10.4230/LIPIcs.ICALP.2017.131}, annote = {Keywords: Graph streaming algorithms, graph property testing, constant-time approximation algorithms} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
André Madeira and S. Muthukrishnan. Functionally Private Approximations of Negligibly-Biased Estimators. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 323-334, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{madeira_et_al:LIPIcs.FSTTCS.2009.2329, author = {Madeira, Andr\'{e} and Muthukrishnan, S.}, title = {{Functionally Private Approximations of Negligibly-Biased Estimators}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {323--334}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2329}, URN = {urn:nbn:de:0030-drops-23298}, doi = {10.4230/LIPIcs.FSTTCS.2009.2329}, annote = {Keywords: Functional privacy, privacy, data streams, #P-complete} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Gianni Franceschini, Roberto Grossi, and S. Muthukrishnan. Optimal Cache-Aware Suffix Selection. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 457-468, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{franceschini_et_al:LIPIcs.STACS.2009.1845, author = {Franceschini, Gianni and Grossi, Roberto and Muthukrishnan, S.}, title = {{Optimal Cache-Aware Suffix Selection}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {457--468}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1845}, URN = {urn:nbn:de:0030-drops-18452}, doi = {10.4230/LIPIcs.STACS.2009.1845}, annote = {Keywords: } }
Published in: Dagstuhl Seminar Proceedings, Volume 8341, Sublinear Algorithms (2008)
Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, and Christian Sohler. 08341 Abstracts Collection – Sublinear Algorithms. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 8341, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{czumaj_et_al:DagSemProc.08341.1, author = {Czumaj, Artur and Muthukrishnan, S. Muthu and Rubinfeld, Ronitt and Sohler, Christian}, title = {{08341 Abstracts Collection – Sublinear Algorithms}}, booktitle = {Sublinear Algorithms}, pages = {1--19}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8341}, editor = {Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08341.1}, URN = {urn:nbn:de:0030-drops-16981}, doi = {10.4230/DagSemProc.08341.1}, annote = {Keywords: Sublinear algorithms, property testing, data streaming, graph algorithms, approximation algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 8341, Sublinear Algorithms (2008)
Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, and Christian Sohler. 08341 Executive Summary – Sublinear Algorithms. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 8341, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{czumaj_et_al:DagSemProc.08341.2, author = {Czumaj, Artur and Muthukrishnan, S. Muthu and Rubinfeld, Ronitt and Sohler, Christian}, title = {{08341 Executive Summary – Sublinear Algorithms}}, booktitle = {Sublinear Algorithms}, pages = {1--2}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8341}, editor = {Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08341.2}, URN = {urn:nbn:de:0030-drops-16964}, doi = {10.4230/DagSemProc.08341.2}, annote = {Keywords: Sublinear algorithms, property testing, data streaming, graph algorithms, approximation algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 8341, Sublinear Algorithms (2008)
Tali Kaufman, Simon Litsyn, and Ning Xie. Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2). In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 8341, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{kaufman_et_al:DagSemProc.08341.3, author = {Kaufman, Tali and Litsyn, Simon and Xie, Ning}, title = {{Breaking the \$\backslashepsilon\$-Soundness Bound of the Linearity Test over GF(2)}}, booktitle = {Sublinear Algorithms}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8341}, editor = {Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08341.3}, URN = {urn:nbn:de:0030-drops-16971}, doi = {10.4230/DagSemProc.08341.3}, annote = {Keywords: Linearity test, Fourier analysis, coding theory} }
Published in: Dagstuhl Seminar Proceedings, Volume 8341, Sublinear Algorithms (2008)
Sumit Ganguly. Lower bound for estimating frequency for update data streams. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 8341, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{ganguly:DagSemProc.08341.4, author = {Ganguly, Sumit}, title = {{Lower bound for estimating frequency for update data streams}}, booktitle = {Sublinear Algorithms}, pages = {1--15}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8341}, editor = {Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08341.4}, URN = {urn:nbn:de:0030-drops-16959}, doi = {10.4230/DagSemProc.08341.4}, annote = {Keywords: Data stream, lower bound, frequency estimation, stream automata, linear map} }
Published in: Dagstuhl Seminar Proceedings, Volume 5291, Sublinear Algorithms (2006)
Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, and Christian Sohler. 05291 Abstracts Collection – Sublinear Algorithms. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 5291, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{czumaj_et_al:DagSemProc.05291.1, author = {Czumaj, Artur and Muthukrishnan, S. Muthu and Rubinfeld, Ronitt and Sohler, Christian}, title = {{05291 Abstracts Collection – Sublinear Algorithms}}, booktitle = {Sublinear Algorithms}, pages = {1--18}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {5291}, editor = {Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05291.1}, URN = {urn:nbn:de:0030-drops-6814}, doi = {10.4230/DagSemProc.05291.1}, annote = {Keywords: Property testing, sublinear time approximation algorithms, data streaming algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 5291, Sublinear Algorithms (2006)
Oded Goldreich and Dana Ron. Approximating Average Parameters of Graphs. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 5291, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{goldreich_et_al:DagSemProc.05291.2, author = {Goldreich, Oded and Ron, Dana}, title = {{Approximating Average Parameters of Graphs}}, booktitle = {Sublinear Algorithms}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {5291}, editor = {Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05291.2}, URN = {urn:nbn:de:0030-drops-5531}, doi = {10.4230/DagSemProc.05291.2}, annote = {Keywords: Graph parameters, degree, distance} }
Published in: Dagstuhl Seminar Proceedings, Volume 5291, Sublinear Algorithms (2006)
Oded Goldreich. Contemplations on Testing Graph Properties. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 5291, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{goldreich:DagSemProc.05291.3, author = {Goldreich, Oded}, title = {{Contemplations on Testing Graph Properties}}, booktitle = {Sublinear Algorithms}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {5291}, editor = {Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05291.3}, URN = {urn:nbn:de:0030-drops-5552}, doi = {10.4230/DagSemProc.05291.3}, annote = {Keywords: Property testing, graph properties} }
Published in: Dagstuhl Seminar Proceedings, Volume 5291, Sublinear Algorithms (2006)
Bernard Chazelle, Ding Liu, and Avner Magen. Sublinear Geometric Algorithms. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 5291, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{chazelle_et_al:DagSemProc.05291.4, author = {Chazelle, Bernard and Liu, Ding and Magen, Avner}, title = {{Sublinear Geometric Algorithms}}, booktitle = {Sublinear Algorithms}, pages = {1--18}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {5291}, editor = {Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05291.4}, URN = {urn:nbn:de:0030-drops-5548}, doi = {10.4230/DagSemProc.05291.4}, annote = {Keywords: Sublinear algorithms, computational geometry} }
Feedback for Dagstuhl Publishing