Benjamin Sach

According to our database, Benjamin Sach authored at least 31 papers between 2007 and 2019.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2019

Time Bounds for Streaming Problems.

Raphaël Clifford, Markus Jalsenius, Benjamin Sach

Theory Comput., 2019

2017

Fingerprints in compressed strings.

Philip Bille, Inge Li Gørtz, Patrick Hagge Cording, Benjamin Sach, Hjalte Wedel Vildhøj, Søren Vind

J. Comput. Syst. Sci., 2017

2016

Sparse Text Indexing in Small Space.

Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj

ACM Trans. Algorithms, 2016

SuMoTED: An intuitive edit distance between rooted unordered uniquely-labelled trees.

Matt McVicar, Benjamin Sach, Cédric Mesnage, Jefrey Lijffijt, Eirini Spyropoulou, Tijl De Bie

Pattern Recognit. Lett., 2016

How low can you go? Using side-channel data to enhance brute-force key recovery.

Jake Longo, Daniel P. Martin, Luke Mather, Elisabeth Oswald, Benjamin Sach, Martijn Stam

IACR Cryptol. ePrint Arch., 2016

The <i>k</i>-mismatch problem revisited.

Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, Tatiana Starikovskaya

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Cell-Probe Lower Bounds for Bit Stream Computation.

Raphaël Clifford, Markus Jalsenius, Benjamin Sach

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

The complexity of computation in bit streams.

Raphaël Clifford, Markus Jalsenius, Benjamin Sach

CoRR, 2015

The k-mismatch problem revisited.

Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, Tatiana Starikovskaya

CoRR, 2015

Computing the Longest Unbordered Substring.

Pawel Gawrychowski, Gregory Kucherov, Benjamin Sach, Tatiana Starikovskaya

Proceedings of the String Processing and Information Retrieval, 2015

Cell-probe bounds for online edit distance and other pattern matching problems.

Raphaël Clifford, Markus Jalsenius, Benjamin Sach

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Dictionary Matching in a Stream.

Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, Tatiana Starikovskaya

Proceedings of the Algorithms - ESA 2015, 2015

2014

Time-space trade-offs for longest common extensions.

Philip Bille, Inge Li Gørtz, Benjamin Sach, Hjalte Wedel Vildhøj

J. Discrete Algorithms, 2014

2013

Space lower bounds for online pattern matching.

Raphaël Clifford, Markus Jalsenius, Ely Porat, Benjamin Sach

Theor. Comput. Sci., 2013

Pattern Matching under Polynomial Transformation.

Ayelet Butman, Peter Clifford, Raphaël Clifford, Markus Jalsenius, Noa Lewenstein, Benny Porat, Ely Porat, Benjamin Sach

SIAM J. Comput., 2013

Parameterized Matching in the Streaming Model.

Markus Jalsenius, Benny Porat, Benjamin Sach

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Tight Cell-Probe Bounds for Online Hamming Distance Computation.

Raphaël Clifford, Markus Jalsenius, Benjamin Sach

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Sparse Suffix Tree Construction in Small Space.

Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

The Complexity of Flood Filling Games.

Raphaël Clifford, Markus Jalsenius, Ashley Montanaro, Benjamin Sach

Theory Comput. Syst., 2012

Sparse Suffix Tree Construction with Small Space

Philip Bille, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj

CoRR, 2012

Pattern Matching in Multiple Streams.

Raphaël Clifford, Markus Jalsenius, Ely Porat, Benjamin Sach

Proceedings of the Combinatorial Pattern Matching - 23rd Annual Symposium, 2012

2011

Pattern matching in pseudo real-time.

Raphaël Clifford, Benjamin Sach

J. Discrete Algorithms, 2011

Streaming Pattern Matching with Relabelling

Raphaël Clifford, Markus Jalsenius, Benjamin Sach

CoRR, 2011

2010

Approximate and pseudo real-time pattern matching.

Benjamin Sach

PhD thesis, 2010

Permuted function matching.

Raphaël Clifford, Benjamin Sach

Inf. Process. Lett., 2010

The Complexity of Flood Filling Games.

David Arthur, Raphaël Clifford, Markus Jalsenius, Ashley Montanaro, Benjamin Sach

Proceedings of the Fun with Algorithms, 5th International Conference, 2010

Pseudo-realtime Pattern Matching: Closing the Gap.

Raphaël Clifford, Benjamin Sach

Proceedings of the Combinatorial Pattern Matching, 21st Annual Symposium, 2010

2009

Generalised Matching.

Raphaël Clifford, Aram W. Harrow, Alexandru Popa, Benjamin Sach

Proceedings of the String Processing and Information Retrieval, 2009

Online Approximate Matching with Non-local Distances.

Raphaël Clifford, Benjamin Sach

Proceedings of the Combinatorial Pattern Matching, 20th Annual Symposium, 2009

2008

An Empirical Study of Cache-Oblivious Priority Queues and their Application to the Shortest Path Problem

Benjamin Sach, Raphaël Clifford

CoRR, 2008

2007

Fast Approximate Point Set Matching for Information Retrieval.

Raphaël Clifford, Benjamin Sach

Proceedings of the SOFSEM 2007: Theory and Practice of Computer Science, 2007