Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Xi Chen, Yaonan Jin, Tim Randolph, and Rocco A. Servedio. Subset Sum in Time 2^{n/2} / poly(n). In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2023.39, author = {Chen, Xi and Jin, Yaonan and Randolph, Tim and Servedio, Rocco A.}, title = {{Subset Sum in Time 2^\{n/2\} / poly(n)}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {39:1--39: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.39}, URN = {urn:nbn:de:0030-drops-188641}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.39}, annote = {Keywords: Exact algorithms, subset sum, log shaving} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Martin Dietzfelbinger. On Hashing by (Random) Equations (Invited Talk). In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dietzfelbinger:LIPIcs.ESA.2023.1, author = {Dietzfelbinger, Martin}, title = {{On Hashing by (Random) Equations}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.1}, URN = {urn:nbn:de:0030-drops-186545}, doi = {10.4230/LIPIcs.ESA.2023.1}, annote = {Keywords: Hashing, Retrieval, Linear equations, Randomness} }
Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)
Jens Keppeler, Thomas Schwentick, and Christopher Spinrath. Work-Efficient Query Evaluation with PRAMs. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{keppeler_et_al:LIPIcs.ICDT.2023.16, author = {Keppeler, Jens and Schwentick, Thomas and Spinrath, Christopher}, title = {{Work-Efficient Query Evaluation with PRAMs}}, booktitle = {26th International Conference on Database Theory (ICDT 2023)}, pages = {16:1--16:20}, 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.16}, URN = {urn:nbn:de:0030-drops-177589}, doi = {10.4230/LIPIcs.ICDT.2023.16}, annote = {Keywords: PRAM, query evaluation, work-efficient, parallel, acyclic queries, free-connex queries} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Stefan Walzer. Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 87:1-87:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{walzer:LIPIcs.ESA.2022.87, author = {Walzer, Stefan}, title = {{Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {87:1--87:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.87}, URN = {urn:nbn:de:0030-drops-170250}, doi = {10.4230/LIPIcs.ESA.2022.87}, annote = {Keywords: Cuckoo Hashing, Random Walk, Random Hypergraph, Peeling, Cores} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Martin Dietzfelbinger and Stefan Walzer. Dense Peelable Random Uniform Hypergraphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dietzfelbinger_et_al:LIPIcs.ESA.2019.38, author = {Dietzfelbinger, Martin and Walzer, Stefan}, title = {{Dense Peelable Random Uniform Hypergraphs}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {38:1--38:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.38}, URN = {urn:nbn:de:0030-drops-111599}, doi = {10.4230/LIPIcs.ESA.2019.38}, annote = {Keywords: Random Hypergraphs, Peeling Threshold, 2-Core, Hashing, Retrieval, Succinct Data Structure} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Martin Dietzfelbinger and Stefan Walzer. Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row, with Applications. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dietzfelbinger_et_al:LIPIcs.ESA.2019.39, author = {Dietzfelbinger, Martin and Walzer, Stefan}, title = {{Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row, with Applications}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {39:1--39:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.39}, URN = {urn:nbn:de:0030-drops-111602}, doi = {10.4230/LIPIcs.ESA.2019.39}, annote = {Keywords: Random Band Matrix, Gauss Elimination, Retrieval, Hashing, Succinct Data Structure, Randomised Data Structure, Robin Hood Hashing, Bloom Filter} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Martin Dietzfelbinger and Stefan Walzer. Constant-Time Retrieval with O(log m) Extra Bits. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dietzfelbinger_et_al:LIPIcs.STACS.2019.24, author = {Dietzfelbinger, Martin and Walzer, Stefan}, title = {{Constant-Time Retrieval with O(log m) Extra Bits}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {24:1--24:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.24}, URN = {urn:nbn:de:0030-drops-102639}, doi = {10.4230/LIPIcs.STACS.2019.24}, annote = {Keywords: Retrieval, Hashing, Succinct Data Structure, Randomised Data Structure, Structured Gaussian Elimination, Method of Four Russians} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Martin Dietzfelbinger, Philipp Schlag, and Stefan Walzer. A Subquadratic Algorithm for 3XOR. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dietzfelbinger_et_al:LIPIcs.MFCS.2018.59, author = {Dietzfelbinger, Martin and Schlag, Philipp and Walzer, Stefan}, title = {{A Subquadratic Algorithm for 3XOR}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {59:1--59:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.59}, URN = {urn:nbn:de:0030-drops-96417}, doi = {10.4230/LIPIcs.MFCS.2018.59}, annote = {Keywords: 3SUM, 3XOR, Randomized Algorithms, Reductions, Conditional Lower Time Bounds} }
Published in: Dagstuhl Reports, Volume 7, Issue 5 (2018)
Martin Dietzfelbinger, Michael Mitzenmacher, Rasmus Pagh, David P. Woodruff, and Martin Aumüller. Theory and Applications of Hashing (Dagstuhl Seminar 17181). In Dagstuhl Reports, Volume 7, Issue 5, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Article{dietzfelbinger_et_al:DagRep.7.5.1, author = {Dietzfelbinger, Martin and Mitzenmacher, Michael and Pagh, Rasmus and Woodruff, David P. and Aum\"{u}ller, Martin}, title = {{Theory and Applications of Hashing (Dagstuhl Seminar 17181)}}, pages = {1--21}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {7}, number = {5}, editor = {Dietzfelbinger, Martin and Mitzenmacher, Michael and Pagh, Rasmus and Woodruff, David P. and Aum\"{u}ller, Martin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.5.1}, URN = {urn:nbn:de:0030-drops-82788}, doi = {10.4230/DagRep.7.5.1}, annote = {Keywords: connections to complexity theory, data streaming applications, hash function construction and analysis, hashing primitives, information retrieval applications, locality-sensitive hashing, machine learning applications} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Martin Dietzfelbinger. On Randomness in Hash Functions (Invited Talk). In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 25-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{dietzfelbinger:LIPIcs.STACS.2012.25, author = {Dietzfelbinger, Martin}, title = {{On Randomness in Hash Functions}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {25--28}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.25}, URN = {urn:nbn:de:0030-drops-33884}, doi = {10.4230/LIPIcs.STACS.2012.25}, annote = {Keywords: Algorithms, hash functions, randomized algorithms, data structures, graphs, hypergraphs} }
Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, and Philipp Woelfel. Tight Bounds for Blind Search on the Integers. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 241-252, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{dietzfelbinger_et_al:LIPIcs.STACS.2008.1348, author = {Dietzfelbinger, Martin and Rowe, Jonathan E. and Wegener, Ingo and Woelfel, Philipp}, title = {{Tight Bounds for Blind Search on the Integers}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {241--252}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1348}, URN = {urn:nbn:de:0030-drops-13486}, doi = {10.4230/LIPIcs.STACS.2008.1348}, annote = {Keywords: } }
Published in: Dagstuhl Seminar Proceedings, Volume 7391, Probabilistic Methods in the Design and Analysis of Algorithms (2007)
Martin Dietzfelbinger, Shang-Hua Teng, Eli Upfal, and Berthold Vöcking. 07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms. In Probabilistic Methods in the Design and Analysis of Algorithms. Dagstuhl Seminar Proceedings, Volume 7391, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{dietzfelbinger_et_al:DagSemProc.07391.1, author = {Dietzfelbinger, Martin and Teng, Shang-Hua and Upfal, Eli and V\"{o}cking, Berthold}, title = {{07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms}}, booktitle = {Probabilistic Methods in the Design and Analysis of Algorithms}, pages = {1--18}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7391}, editor = {Martin Dietzfelbinger and Shang-Hua Teng and Eli Upfal and Berthold V\"{o}cking}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07391.1}, URN = {urn:nbn:de:0030-drops-12915}, doi = {10.4230/DagSemProc.07391.1}, annote = {Keywords: Algorithms, Randomization, Probabilistic analysis, Complexity} }
Published in: Dagstuhl Seminar Proceedings, Volume 7391, Probabilistic Methods in the Design and Analysis of Algorithms (2007)
Chaitanya Swamy and David Shmoys. Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization. In Probabilistic Methods in the Design and Analysis of Algorithms. Dagstuhl Seminar Proceedings, Volume 7391, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{swamy_et_al:DagSemProc.07391.2, author = {Swamy, Chaitanya and Shmoys, David}, title = {{Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization}}, booktitle = {Probabilistic Methods in the Design and Analysis of Algorithms}, pages = {1--24}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7391}, editor = {Martin Dietzfelbinger and Shang-Hua Teng and Eli Upfal and Berthold V\"{o}cking}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07391.2}, URN = {urn:nbn:de:0030-drops-12906}, doi = {10.4230/DagSemProc.07391.2}, annote = {Keywords: Stochastic optimization, approximation algorithms, randomized algorithms, linear programming} }
Published in: Dagstuhl Seminar Proceedings, Volume 7391, Probabilistic Methods in the Design and Analysis of Algorithms (2007)
Bodo Manthey and Till Tantau. Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise. In Probabilistic Methods in the Design and Analysis of Algorithms. Dagstuhl Seminar Proceedings, Volume 7391, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{manthey_et_al:DagSemProc.07391.3, author = {Manthey, Bodo and Tantau, Till}, title = {{Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise}}, booktitle = {Probabilistic Methods in the Design and Analysis of Algorithms}, pages = {1--19}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7391}, editor = {Martin Dietzfelbinger and Shang-Hua Teng and Eli Upfal and Berthold V\"{o}cking}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07391.3}, URN = {urn:nbn:de:0030-drops-12893}, doi = {10.4230/DagSemProc.07391.3}, annote = {Keywords: Smoothed Analysis, Binary Search Trees, Quicksort, Left-to-right Maxima} }
Feedback for Dagstuhl Publishing