Paweł Gawrychowski

1. Minimum Cut in O(mlog² n) Time
   2019/11/04 by Paweł Gawrychowski, Shay Mozes, Gawrychowski, Paweł +3 · 1 voice · 2 citations
   #cs.DS
2. Cut query algorithms with star contraction
   2022/01/14 by Simon Apers, Apers, Simon, Yuval Efron +9 · 7 citations
   Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Stochastic Gradient Optimization Techniques
3. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless\n APSP can)
   2017/03/27 by Karl Bringmann, Paweł Gawrychowski, Bringmann, Karl +5 · 3 citations
   Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization
4. Weighted ancestors in suffix trees
   2014/06/30 by Paweł Gawrychowski, Gawrychowski, Pawel, Moshe Lewenstein +3 · 2 citations
   Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
5. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in\n Streams
   2016/10/10 by Paweł Gawrychowski, Oleg Merkurev, Gawrychowski, Paweł +5 · 2 citations
   Computer Science · #Stochastic Gradient Optimization Techniques #Complexity and Algorithms in Graphs #Machine Learning and Algorithms
6. Optimal Dynamic Strings
   2015/11/09 by Paweł Gawrychowski, Gawrychowski, Paweł, Adam Karczmarz +7 · 2 citations
   Computer Science · #68P05 #68W32 #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Natural Language Processing Techniques #Network Packet Processing and Optimization
7. Faster Exponential Algorithm for Permutation Pattern Matching
   2021/08/25 by Paweł Gawrychowski, Gawrychowski, Pawel, Mateusz Rzepecki +1 · 2 citations
   Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #Genomic variations and chromosomal abnormalities
8. Alphabet-Dependent String Searching with Wexponential Search Trees
   2013/02/14 by Johannes Fischer, Fischer, Johannes, Paweł Gawrychowski +1 · 1 citation
   Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization
9. Pattern Matching on Grammar-Compressed Strings in Linear Time
   2021/11/09 by Moses Ganardi, Ganardi, Moses, Paweł Gawrychowski +1 · 2 citations
   Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization
10. Elastic-Degenerate String Matching via Fast Matrix Multiplication
    2019/05/06 by Giulia Bernardini, Paweł Gawrychowski, Bernardini, Giulia +7 · 1 citation
    Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Natural Language Processing Techniques #Network Packet Processing and Optimization
11. A Faster Subquadratic Algorithm for the Longest Common Increasing\n Subsequence Problem
    2020/03/30 by Anadi Agrawal, Agrawal, Anadi, Paweł Gawrychowski +1 · 1 citation
    Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Coding theory and cryptography #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
12. Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles\n in Graphs
    2020/10/01 by Bartłomiej Dudek, Paweł Gawrychowski, Dudek, Bartłomiej +1 · 1 citation
    Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #graph theory and CDMA systems
13. Strong inapproximability of the shortest reset word
    2014/08/22 by Paweł Gawrychowski, Damian Straszak, Gawrychowski, Pawel +1 · 1 citation
    Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #semigroups and automata theory
14. Faster two-dimensional pattern matching with k mismatches
    2024/10/29 by Jonas Ellert, Paweł Gawrychowski, Ellert, Jonas +5 · 1 citation
    Computer Science · #Music and Audio Processing #Video Analysis and Summarization #Handwritten Text Recognition Techniques
15. Random Access to LZ-End: Faster and Deterministic
    2026/07/16 by Itai Boneh, Paweł Gawrychowski
    #cs.DS
16. String Matching in (Block) Graphs: A Full Classification by Walk Length
    2026/07/30 by Sebastian Angrick, Ben Bals, Paweł Gawrychowski +2
    Computer Science · #cs.DS