default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDPawel Gawrychowski
Person information
- affiliation: University of Wroclaw, Poland
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j35]Pawel Gawrychowski, Shay Mozes, Oren Weimann
:
Minimum Cut in O(mlog 2 n) Time. Theory Comput. Syst. 68(4): 814-834 (2024)- [j34]Bartlomiej Dudek, Pawel Gawrychowski:
Slowing down top trees for better worst-case compression. Theor. Comput. Sci. 1015: 114764 (2024) - [c132]Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Simon R. Tarnow:
Faster Sliding Window String Indexing in Streams. CPM 2024: 8:1-8:14 - [c131]Bartlomiej Dudek, Pawel Gawrychowski:
Online Context-Free Recognition in OMv Time. CPM 2024: 13:1-13:9 - [c130]Pawel Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, Teresa Anna Steiner:
Compressed Consecutive Pattern Matching†. DCC 2024: 163-172 - [c129]Pawel Gawrychowski, Mateusz Wasylkiewicz:
Finding Perfect Matchings in Bridgeless Cubic Multigraphs Without Dynamic (2-)connectivity. ESA 2024: 59:1-59:14 - [c128]Panagiotis Charalampopoulos, Pawel Gawrychowski, Samah Ghazawi:
Optimal Bounds for Distinct Quartics. ICALP 2024: 39:1-39:17 - [c127]Duncan Adamson, Pawel Gawrychowski, Florin Manea:
Enumerating m-Length Walks in Directed Graphs with Constant Delay. LATIN (1) 2024: 35-50 - [c126]Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya:
Sorting Signed Permutations by Reversals in Nearly-Linear Time. SOSA 2024: 199-214 - [i104]Duncan Adamson, Pawel Gawrychowski, Florin Manea:
Enumerating m-Length Walks in Directed Graphs with Constant Delay. CoRR abs/2401.02163 (2024) - [i103]Panagiotis Charalampopoulos, Pawel Gawrychowski, Samah Ghazawi:
Optimal Bounds for Distinct Quartics. CoRR abs/2403.06667 (2024) - [i102]Pawel Gawrychowski, Mateusz Wasylkiewicz:
Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity. CoRR abs/2405.03856 (2024) - [i101]Pawel Gawrychowski, Wojciech Janczewski:
Optimal Distance Labeling for Permutation Graphs. CoRR abs/2407.12147 (2024) - [i100]Pawel Gawrychowski, Egor Gorbachev, Tomasz Kociumaka:
Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications. CoRR abs/2408.04613 (2024) - 2023
- [j33]Pawel Gawrychowski, Przemyslaw Uznanski:
Better Distance Labeling for Unweighted Planar Graphs. Algorithmica 85(6): 1805-1823 (2023) - [j32]Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen:
Tight Bound for the Number of Distinct Palindromes in a Tree. Electron. J. Comb. 30(2) (2023) - [j31]Panagiotis Charalampopoulos, Pawel Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Oren Weimann, Christian Wulff-Nilsen:
Almost Optimal Exact Distance Oracles for Planar Graphs. J. ACM 70(2): 12:1-12:50 (2023) - [c125]Panagiotis Charalampopoulos, Bartlomiej Dudek, Pawel Gawrychowski, Karol Pokorski:
Optimal Near-Linear Space Heaviest Induced Ancestors. CPM 2023: 8:1-8:18 - [c124]Pawel Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, Teresa Anna Steiner:
Compressed Indexing for Consecutive Occurrences. CPM 2023: 12:1-12:22 - [c123]Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau:
Order-Preserving Squares in Strings. CPM 2023: 13:1-13:19 - [c122]Giulia Bernardini, Gabriele Fici, Pawel Gawrychowski, Solon P. Pissis:
Substring Complexity in Sublinear Space. ISAAC 2023: 12:1-12:19 - [c121]Jonas Ellert, Pawel Gawrychowski, Garance Gourdel:
Optimal Square Detection Over General Alphabets. SODA 2023: 5220-5242 - [c120]Pawel Gawrychowski, Maria Kosche, Florin Manea:
On the Number of Factors in the LZ-End Factorization. SPIRE 2023: 253-259 - [i99]Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau:
Order-Preserving Squares in Strings. CoRR abs/2302.00724 (2023) - [i98]Panagiotis Charalampopoulos, Bartlomiej Dudek, Pawel Gawrychowski, Karol Pokorski:
Optimal Heaviest Induced Ancestors. CoRR abs/2302.01373 (2023) - [i97]Jonas Ellert, Pawel Gawrychowski, Garance Gourdel:
Optimal Square Detection Over General Alphabets. CoRR abs/2303.07229 (2023) - [i96]Pawel Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, Teresa Anna Steiner:
Compressed Indexing for Consecutive Occurrences. CoRR abs/2304.00887 (2023) - [i95]Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya:
Sorting Signed Permutations by Reversals in Nearly-Linear Time. CoRR abs/2308.15928 (2023) - 2022
- [j30]Pawel Gawrychowski, Tatiana Starikovskaya:
Streaming Dictionary Matching with Mismatches. Algorithmica 84(4): 896-916 (2022) - [j29]Pawel Gawrychowski, Florin Manea, Radoslaw Serafin:
Fast and Longest Rollercoasters. Algorithmica 84(4): 1081-1106 (2022) - [j28]Thomas Colcombet, Nathanaël Fijalkow, Pawel Gawrychowski, Pierre Ohlmann:
The Theory of Universal Graphs for Infinite Duration Games. Log. Methods Comput. Sci. 18(3) (2022) - [j27]Giulia Bernardini, Pawel Gawrychowski, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone:
Elastic-Degenerate String Matching via Fast Matrix Multiplication. SIAM J. Comput. 51(3): 549-576 (2022) - [j26]Aviv Bar-Natan, Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Fault-tolerant distance labeling for planar graphs. Theor. Comput. Sci. 918: 48-59 (2022) - [c119]Simon Apers, Pawel Gawrychowski, Troy Lee:
Finding the KT Partition of a Weighted Graph in Near-Linear Time. APPROX/RANDOM 2022: 32:1-32:14 - [c118]Raphaël Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski:
The Dynamic k-Mismatch Problem. CPM 2022: 18:1-18:15 - [c117]Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai:
Cut Query Algorithms with Star Contraction. FOCS 2022: 507-518 - [c116]Pawel Gawrychowski, Karol Pokorski:
Sublinear Dynamic Interval Scheduling (On One or Multiple Machines). ICALP 2022: 67:1-67:19 - [c115]Bartlomiej Dudek, Pawel Gawrychowski, Garance Gourdel, Tatiana Starikovskaya:
Streaming Regular Expression Membership and Pattern Matching. SODA 2022: 670-694 - [c114]Moses Ganardi, Pawel Gawrychowski:
Pattern Matching on Grammar-Compressed Strings in Linear Time. SODA 2022: 2833-2846 - [c113]Pawel Gawrychowski, Wojciech Janczewski:
Simpler Adjacency Labeling for Planar Graphs with B-Trees. SOSA 2022: 24-36 - [c112]Pawel Gawrychowski, Mateusz Rzepecki:
Faster Exponential Algorithm for Permutation Pattern Matching. SOSA 2022: 279-284 - [c111]Pawel Gawrychowski, Florin Manea, Stefan Siemer:
Matching Patterns with Variables Under Edit Distance. SPIRE 2022: 275-289 - [c110]Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
On the Hardness of Computing the Edit Distance of Shallow Trees. SPIRE 2022: 290-302 - [i94]Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai:
Cut query algorithms with star contraction. CoRR abs/2201.05674 (2022) - [i93]Pawel Gawrychowski, Karol Pokorski:
Sublinear Dynamic Interval Scheduling (on one or multiple machines). CoRR abs/2203.14310 (2022) - [i92]Pawel Gawrychowski, Florin Manea, Stefan Siemer:
Matching Patterns with Variables Under Edit Distance. CoRR abs/2207.07477 (2022) - 2021
- [j25]Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Gad M. Landau, Oren Weimann:
Top Tree Compression of Tries. Algorithmica 83(12): 3602-3628 (2021) - [j24]Djamal Belazzougui, Manuel Cáceres, Travis Gagie, Pawel Gawrychowski, Juha Kärkkäinen, Gonzalo Navarro, Alberto Ordóñez Pereira, Simon J. Puglisi, Yasuo Tabei:
Block trees. J. Comput. Syst. Sci. 117: 1-22 (2021) - [j23]Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, Oren Weimann:
Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ(n5/3) Time. SIAM J. Comput. 50(2): 509-554 (2021) - [j22]Golnaz Badkobeh, Pawel Gawrychowski, Juha Kärkkäinen, Simon J. Puglisi, Bella Zhukova:
Tight upper and lower bounds on suffix tree breadth. Theor. Comput. Sci. 854: 63-67 (2021) - [c109]Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
An Almost Optimal Edit Distance Oracle. ICALP 2021: 48:1-48:20 - [c108]Pawel Gawrychowski, Florin Manea, Stefan Siemer:
Matching Patterns with Variables Under Hamming Distance. MFCS 2021: 48:1-48:24 - [c107]Aviv Bar-Natan, Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Fault-Tolerant Distance Labeling for Planar Graphs. SIROCCO 2021: 315-333 - [c106]Pawel Gawrychowski, Wojciech Janczewski, Jakub Lopuszanski:
Shorter Labels for Routing in Trees. SODA 2021: 2174-2193 - [c105]Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Planar Negative k-Cycle. SODA 2021: 2717-2724 - [c104]Pawel Gawrychowski, Shay Mozes, Oren Weimann:
A Note on a Recent Algorithm for Minimum Cut. SOSA 2021: 74-79 - [c103]Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau:
Lower Bounds for the Number of Repetitions in 2D Strings. SPIRE 2021: 179-192 - [c102]Pawel Gawrychowski, Maria Kosche, Tore Koß, Florin Manea, Stefan Siemer:
Efficiently Testing Simon's Congruence. STACS 2021: 34:1-34:18 - [c101]Pawel Gawrychowski, Wojciech Janczewski:
Fully dynamic approximation of LIS in polylogarithmic time. STOC 2021: 654-667 - [c100]Giulia Bernardini, Paola Bonizzoni, Pawel Gawrychowski:
Incomplete Directed Perfect Phylogeny in Linear Time. WADS 2021: 172-185 - [c99]Bartlomiej Dudek, Pawel Gawrychowski, Karol Pokorski:
Strictly In-Place Algorithms for Permuting and Inverting Permutations. WADS 2021: 329-342 - [c98]Pawel Gawrychowski, Przemyslaw Uznanski:
Better Distance Labeling for Unweighted Planar Graphs. WADS 2021: 428-441 - [e1]Pawel Gawrychowski, Tatiana Starikovskaya:
32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, July 5-7, 2021, Wrocław, Poland. LIPIcs 191, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2021, ISBN 978-3-95977-186-3 [contents] - [i91]Bartlomiej Dudek, Pawel Gawrychowski, Karol Pokorski:
Strictly In-Place Algorithms for Permuting and Inverting Permutations. CoRR abs/2101.03978 (2021) - [i90]Aviv Bar-Natan, Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Fault-Tolerant Distance Labeling for Planar Graphs. CoRR abs/2102.07154 (2021) - [i89]Pawel Gawrychowski, Wojciech Janczewski:
Conditional Lower Bounds for Variants of Dynamic LIS. CoRR abs/2102.11797 (2021) - [i88]Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
An Almost Optimal Edit Distance Oracle. CoRR abs/2103.03294 (2021) - [i87]Thomas Colcombet, Nathanaël Fijalkow, Pawel Gawrychowski, Pierre Ohlmann:
The Theory of Universal Graphs for Infinite Duration Games. CoRR abs/2104.05262 (2021) - [i86]Raphaël Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski:
The Dynamic k-Mismatch Problem. CoRR abs/2105.06166 (2021) - [i85]Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau:
Lower Bounds for the Number of Repetitions in 2D Strings. CoRR abs/2105.14903 (2021) - [i84]Pawel Gawrychowski, Florin Manea, Stefan Siemer:
Matching Patterns with Variables under Hamming Distance. CoRR abs/2106.06249 (2021) - [i83]Pawel Gawrychowski, Mateusz Rzepecki:
Faster Exponential Algorithm for Permutation Pattern Matching. CoRR abs/2108.11475 (2021) - [i82]Simon Apers, Pawel Gawrychowski, Troy Lee:
Finding the KT partition of a weighted graph in near-linear time. CoRR abs/2111.01378 (2021) - [i81]Moses Ganardi, Pawel Gawrychowski:
Pattern Matching on Grammar-Compressed Strings in Linear Time. CoRR abs/2111.05016 (2021) - 2020
- [j21]Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Submatrix Maximum Queries in Monge and Partial Monge Matrices Are Equivalent to Predecessor Search. ACM Trans. Algorithms 16(2): 16:1-16:24 (2020) - [j20]Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can). ACM Trans. Algorithms 16(4): 48:1-48:22 (2020) - [j19]Pawel Gawrychowski, Seungbum Jo, Shay Mozes, Oren Weimann:
Compressed range minimum queries. Theor. Comput. Sci. 812: 39-48 (2020) - [j18]Pawel Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen:
Universal reconstruction of a string. Theor. Comput. Sci. 812: 174-186 (2020) - [c97]Giulia Bernardini, Paola Bonizzoni, Pawel Gawrychowski:
On Two Measures of Distance Between Fully-Labelled Trees. CPM 2020: 6:1-6:16 - [c96]Pawel Gawrychowski, Samah Ghazawi, Gad M. Landau:
On Indeterminate Strings Matching. CPM 2020: 14:1-14:14 - [c95]Panagiotis Charalampopoulos, Pawel Gawrychowski, Karol Pokorski:
Dynamic Longest Common Substring in Polylogarithmic Time. ICALP 2020: 27:1-27:19 - [c94]Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Minimum Cut in O(m log² n) Time. ICALP 2020: 57:1-57:15 - [c93]Anadi Agrawal, Pawel Gawrychowski:
A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem. ISAAC 2020: 4:1-4:12 - [c92]Bartlomiej Dudek, Pawel Gawrychowski:
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs. ISAAC 2020: 23:1-23:18 - [c91]Maciej Duleba, Pawel Gawrychowski, Wojciech Janczewski:
Efficient Labeling for Reachability in Directed Acyclic Graphs. ISAAC 2020: 27:1-27:14 - [c90]Nathanaël Fijalkow, Pawel Gawrychowski, Pierre Ohlmann:
Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games. MFCS 2020: 34:1-34:15 - [c89]Pawel Gawrychowski, Martin Lange, Narad Rampersad, Jeffrey O. Shallit, Marek Szykula:
Existential Length Universality. STACS 2020: 16:1-16:14 - [c88]Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya:
Generalised Pattern Matching Revisited. STACS 2020: 18:1-18:18 - [c87]Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya:
All non-trivial variants of 3-LDT are equivalent. STOC 2020: 974-981 - [i80]Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya:
All non-trivial variants of 3-LDT are equivalent. CoRR abs/2001.01289 (2020) - [i79]Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya:
Generalised Pattern Matching Revisited. CoRR abs/2001.05976 (2020) - [i78]Giulia Bernardini, Paola Bonizzoni, Pawel Gawrychowski:
On Two Measures of Distance between Fully-Labelled Trees. CoRR abs/2002.05600 (2020) - [i77]Pawel Gawrychowski, Wojciech Janczewski, Jakub Lopuszanski:
Shorter Labels for Routing in Trees. CoRR abs/2003.06691 (2020) - [i76]Anadi Agrawal, Pawel Gawrychowski:
A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem. CoRR abs/2003.13589 (2020) - [i75]Pawel Gawrychowski, Maria Kosche, Tore Koss, Florin Manea, Stefan Siemer:
Efficiently Testing Simon's Congruence. CoRR abs/2005.01112 (2020) - [i74]Panagiotis Charalampopoulos, Pawel Gawrychowski, Karol Pokorski:
Dynamic Longest Common Substring in Polylogarithmic Time. CoRR abs/2006.02408 (2020) - [i73]Maciej Duleba, Pawel Gawrychowski, Wojciech Janczewski:
Efficient Labeling for Reachability in Digraphs. CoRR abs/2007.06105 (2020) - [i72]Giulia Bernardini, Gabriele Fici, Pawel Gawrychowski, Solon P. Pissis:
Substring Complexity in Sublinear Space. CoRR abs/2007.08357 (2020) - [i71]Pawel Gawrychowski, Shay Mozes, Oren Weimann:
A Note on a Recent Algorithm for Minimum Cut. CoRR abs/2008.02060 (2020) - [i70]Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen:
Tight Bound for the Number of Distinct Palindromes in a Tree. CoRR abs/2008.13209 (2020) - [i69]Bartlomiej Dudek, Pawel Gawrychowski:
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs. CoRR abs/2010.00348 (2020) - [i68]Giulia Bernardini, Paola Bonizzoni, Pawel Gawrychowski:
Incomplete Directed Perfect Phylogeny in Linear Time. CoRR abs/2010.05644 (2020) - [i67]Pawel Gawrychowski, Wojciech Janczewski:
Fully Dynamic Approximation of LIS in Polylogarithmic Time. CoRR abs/2011.09761 (2020)
2010 – 2019
- 2019
- [j17]Pawel Gawrychowski, Oleg Merkurev, Arseny M. Shur, Przemyslaw Uznanski:
Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams. Algorithmica 81(9): 3630-3654 (2019) - [j16]Pawel Gawrychowski, Florin Manea, Robert Mercas, Dirk Nowotka:
Hide and seek with repetitions. J. Comput. Syst. Sci. 101: 42-67 (2019) - [c86]Pawel Gawrychowski:
How to Exploit Periodicity (Invited Talk). CPM 2019: 1:1-1:1 - [c85]Pawel Gawrychowski, Tatiana Starikovskaya:
Streaming Dictionary Matching with Mismatches. CPM 2019: 21:1-21:15 - [c84]Pawel Gawrychowski, Jakub Radoszewski, Tatiana Starikovskaya:
Quasi-Periodicity in Streams. CPM 2019: 22:1-22:14 - [c83]Giulia Bernardini, Pawel Gawrychowski, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone:
Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication. ICALP 2019: 21:1-21:15 - [c82]Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Gad M. Landau, Oren Weimann:
Top Tree Compression of Tries. ISAAC 2019: 4:1-4:18 - [c81]Raphaël Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski:
RLE Edit Distance in Near Optimal Time. MFCS 2019: 66:1-66:13 - [c80]Gabriele Fici, Pawel Gawrychowski:
Minimal Absent Words in Rooted and Unrooted Trees. SPIRE 2019: 152-161 - [c79]Pawel Gawrychowski, Florin Manea, Radoslaw Serafin:
Fast and Longest Rollercoasters. STACS 2019: 30:1-30:17 - [c78]Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Almost optimal distance oracles for planar graphs. STOC 2019: 138-151 - [c77]Bartlomiej Dudek, Pawel Gawrychowski:
Computing quartet distance is equivalent to counting 4-cycles. STOC 2019: 733-743 - [i66]Philip Bille, Inge Li Gørtz, Pawel Gawrychowski, Gad M. Landau, Oren Weimann:
Top Tree Compression of Tries. CoRR abs/1902.02187 (2019) - [i65]Pawel Gawrychowski, Seungbum Jo, Shay Mozes, Oren Weimann:
Compressed Range Minimum Queries. CoRR abs/1902.04427 (2019) - [i64]Raphaël Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski:
RLE edit distance in near optimal time. CoRR abs/1905.01254 (2019) - [i63]Giulia Bernardini, Pawel Gawrychowski, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone:
Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication. CoRR abs/1905.02298 (2019) - [i62]Gabriele Fici, Pawel Gawrychowski:
Minimal Absent Words in Rooted and Unrooted Trees. CoRR abs/1907.12034 (2019) - [i61]Pawel Gawrychowski, Shay Mozes, Oren Weimann:
Minimum Cut in O(m log2n) Time. CoRR abs/1911.01145 (2019) - 2018
- [j15]