Current Year

%0 Conference Proceedings %A Abboud, Amir %A Bringmann, Karl %A Fischer, Nick %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics : %G eng %U http://hdl.handle.net/21.11116/0000-000C-8C13-1 %D 2023 %B 55th Annual ACM Symposium on Theory of Computing %Z date of event: 2023-06-20 - 2023-06-23 %C Orlando, FL, USA %B Proceedings of the 55th Annual ACM Symposium on Theory of Computing %I ACM

%0 Conference Proceedings %A Ardra, P. S. %A Krithika, R. %A Saurabh, Saket %A Sharma, Roohani %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Balanced Substructures in Bicolored Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1D8F-4 %R 10.1007/978-3-031-23101-8_12 %D 2023 %B 48th International Conference on Current Trends in Theory and Practice of Computer Science %Z date of event: 2023-01-15 - 2023-01-18 %C Nový Smokovec, Slovakia %B SOFSEM 2023: Theory and Practice of Computer Science %E Gąsieniec, Leszek %P 177 - 191 %I Springer %@ 978-3-031-23100-1 %B Lecture Notes in Computer Science %N 13878 %U https://rdcu.be/c2Gfk

%0 Conference Proceedings %A Beck, Moritz %A Spoerhase, Joachim %A Storandt, Sabine %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Mind the Gap: Edge Facility Location Problems in Theory and Practice : %G eng %U http://hdl.handle.net/21.11116/0000-000C-992D-6 %R 10.1007/978-3-031-25211-2_25 %D 2023 %B 9th International Conference on Algorithms and Discrete Applied Mathematics %Z date of event: 2023-02-09 - 2023-02-11 %C Gandhinagar, India %B Algorithms and Discrete Applied Mathematics %E Bagchi, Amitabha; Muthu, Rahul %P 321 - 334 %I Springer %@ 978-3-031-25210-5 %B Lecture Notes in Computer Science %N 13947 %U https://rdcu.be/c5J8c

%0 Conference Proceedings %A Bhattacharya, Sayan %A Kiss, Peter %A Saranurak, Thatchaphol %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Sublinear Algorithms for (1.5+Epsilon)-Approximate Matching : %G eng %U http://hdl.handle.net/21.11116/0000-000C-9BA1-F %D 2023 %B 55th Annual ACM Symposium on Theory of Computing %Z date of event: 2023-06-20 - 2023-06-23 %C Orlando, FL, USA %B Proceedings of the 55th Annual ACM Symposium on Theory of Computing %I ACM

%0 Report %A Bhattacharya, Sayan %A Kiss, Peter %A Saranurak, Thatchaphol %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Dynamic (1.5+Epsilon)-Approximate Matching Size in Truly Sublinear Update Time : %G eng %U http://hdl.handle.net/21.11116/0000-000C-9BA8-8 %U https://arxiv.org/abs/2302.05030 %D 2023 %X We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate<br>\emph{size} of maximum matching of the graph with $n$ vertices and $m$ edges<br>using $m^{0.5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial<br>improvement over the long-standing $O(n)$ update time, which can be trivially<br>obtained by periodic recomputation. Thus, we resolve the value version of a<br>major open question of the dynamic graph algorithms literature (see, e.g.,<br>[Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16],[Behnezhad and Khanna<br>SODA'22]).<br> Our key technical component is the first sublinear algorithm for $(1,\epsilon<br>n)$-approximate maximum matching with sublinear running time on dense graphs.<br>All previous algorithms suffered a multiplicative approximation factor of at<br>least $1.499$ or assumed that the graph has a very small maximum degree.<br> %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Conference Proceedings %A Bhattacharya, Sayan %A Kiss, Peter %A Saranurak, Thatchaphol %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight : %G eng %U http://hdl.handle.net/21.11116/0000-000C-4333-F %R 10.1137/1.9781611977554.ch1 %D 2023 %B Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2023-01-22 - 2023-01-25 %C Florence, Italy %B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms %E Bansal, Nikhil; Nagarajan, Viswanath %P 1 - 47 %I SIAM %@ 978-1-61197-755-4

%0 Conference Proceedings %A Bhattacharya, Sayan %A Kiss, Peter %A Saranurak, Thatchaphol %A Wajc, David %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time : %G eng %U http://hdl.handle.net/21.11116/0000-000C-4336-C %R 10.1137/1.9781611977554.ch5 %D 2023 %B Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2023-01-22 - 2023-01-25 %C Florence, Italy %B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms %E Bansal, Nikhil; Nagarajan, Viswanath %P 100 - 128 %I SIAM %@ 978-1-61197-755-4

%0 Conference Proceedings %A Blikstad, Joakim %A Tu, Ta-Wei %A Nanongkai, Danupon %A Mukhopadhyay, Sagnik %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Fast Algorithms via Dynamic-Oracle Matroids : %G eng %U http://hdl.handle.net/21.11116/0000-000C-8C18-C %D 2023 %B 55th Annual ACM Symposium on Theory of Computing %Z date of event: 2023-06-20 - 2023-06-23 %C Orlando, FL, USA %B Proceedings of the 55th Annual ACM Symposium on Theory of Computing %I ACM

%0 Report %A Blikstad, Joakim %A Kiss, Peter %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Incremental (1 - &#949;)-approximate dynamic matching in O(poly(1/&#949;)) update time : %G eng %U http://hdl.handle.net/21.11116/0000-000C-A006-8 %U https://arxiv.org/abs/2302.08432 %D 2023 %X In the dynamic approximate maximum bipartite matching problem we are given<br>bipartite graph $G$ undergoing updates and our goal is to maintain a matching<br>of $G$ which is large compared the maximum matching size $\mu(G)$. We define a<br>dynamic matching algorithm to be $\alpha$ (respectively $(\alpha,<br>\beta)$)-approximate if it maintains matching $M$ such that at all times $|M |<br>\geq \mu(G) \cdot \alpha$ (respectively $|M| \geq \mu(G) \cdot \alpha -<br>\beta$).<br> We present the first deterministic $(1-\epsilon )$-approximate dynamic<br>matching algorithm with $O(poly(\epsilon ^{-1}))$ amortized update time for<br>graphs undergoing edge insertions. Previous solutions either required<br>super-constant [Gupta FSTTCS'14, Bhattacharya-Kiss-Saranurak SODA'23] or<br>exponential in $1/\epsilon $<br>[Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA'19] update time. Our<br>implementation is arguably simpler than the mentioned algorithms and its<br>description is self contained. Moreover, we show that if we allow for additive<br>$(1, \epsilon \cdot n)$-approximation our algorithm seamlessly extends to also<br>handle vertex deletions, on top of edge insertions. This makes our algorithm<br>one of the few small update time algorithms for $(1-\epsilon )$-approximate<br>dynamic matching allowing for updates both increasing and decreasing the<br>maximum matching size of $G$ in a fully dynamic manner.<br> %K Computer Science, Data Structures and Algorithms, cs.DS

%0 Journal Article %A Bria&#324;ski, Marcin %A Joret, Gwena&#235;l %A Majewski, Konrad %A Micek, Piotr %A Seweryn, Micha&#322; T. %A Sharma, Roohani %+ External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Treedepth Vs Circumference : %G eng %U http://hdl.handle.net/21.11116/0000-000C-8E4E-E %D 2023 %J Combinatorica %I Springer %C Heidelberg %@ false

%0 Conference Proceedings %A Bringmann, Karl %A Kapralov, Michael %A Makarov, Mikhail %A Nakos, Vasileios %A Yagudin, Amir %A Zandieh, Amir %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms : %G eng %U http://hdl.handle.net/21.11116/0000-000C-26DB-3 %R 10.1137/1.9781611977554.ch177 %D 2023 %B Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2023-01-22 - 2023-01-25 %C Florence, Italy %B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms %E Bansal, Nikhil; Nagarajan, Viswanath %P 4768 - 4845 %I SIAM %@ 978-1-61197-755-4

%0 Journal Article %A Bringmann, Karl %A Cohen-Addad, Vincent %A Das, Debarati %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T A Linear-Time n0.4-Approximation for Longest Common Subsequence : %G eng %U http://hdl.handle.net/21.11116/0000-000C-A7EC-E %R 10.1145/3568398 %7 2023 %D 2023 %J ACM Transactions on Algorithms %V 19 %N 1 %& 1 %P 1 - 24 %Z sequence number: 9 %I ACM %C New York, NY %@ false

%0 Conference Proceedings %A Coupette, Corinna %A Dalleiger, Sebastian %A Rieck, Bastian %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework : %G eng %U http://hdl.handle.net/21.11116/0000-000C-10CD-B %D 2023 %B Eleventh International Conference on Learning Representations %Z date of event: 2023-05-01 - 2023-05-05 %C Kigali, Rwanda %X Bridging geometry and topology, curvature is a powerful and expressive invariant. While the utility of curvature has been theoretically and empirically confirmed in the context of manifolds and graphs, its generalization to the emerging domain of hypergraphs has remained largely unexplored. On graphs, Ollivier-Ricci curvature measures differences between random walks via Wasserstein distances, thus grounding a geometric concept in ideas from probability and optimal transport. We develop ORCHID, a flexible framework generalizing Ollivier-Ricci curvature to hypergraphs, and prove that the resulting curvatures have favorable theoretical properties. Through extensive experiments on synthetic and real-world hypergraphs from different domains, we demonstrate that ORCHID curvatures are both scalable and useful to perform a variety of hypergraph tasks in practice. %K Computer Science, Learning, cs.LG,cs.SI,Statistics, Machine Learning, stat.ML %B Eleventh International Conference on Learning Representations %I OpenReview.net %U https://openreview.net/forum?id=sPCKNl5qDps

%0 Conference Proceedings %A Das, Debarati %A Gilbert, Jacob %A Hajiaghayi, MohammadTaghi %A Kociumaka, Tomasz %A Saha, Barna %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Weighted Edit Distance Computation: Strings, Trees, and Dyck : %G eng %U http://hdl.handle.net/21.11116/0000-000C-8B20-3 %D 2023 %B 55th Annual ACM Symposium on Theory of Computing %Z date of event: 2023-06-20 - 2023-06-23 %C Orlando, FL, USA %B Proceedings of the 55th Annual ACM Symposium on Theory of Computing %I ACM

%0 Conference Proceedings %A Dross, Fran&#231;ois %A Fleszar, Krzysztof %A W&#281;grzycki, Karol %A Zych-Pawlewicz, Anna %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1F6C-A %R 10.1137/1.9781611977554.ch52 %D 2023 %B Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2023-01-22 - 2023-01-25 %C Florence, Italy %B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms %E Bansal, Nikhil; Nagarajan, Viswanath %P 1433 - 1463 %I SIAM %@ 978-1-61197-755-4

%0 Journal Article %A Fallat, Shaun %A Kirkpatrick, David %A Simon, Hans U. %A Soltani, Abolghasem %A Zilles, Sandra %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T On Batch Teaching Without Collusion : %G eng %U http://hdl.handle.net/21.11116/0000-000C-7CCF-1 %U http://jmlr.org/papers/v24/22-0330.html %7 2023 %D 2023 %J Journal of Machine Learning Research %V 24 %& 1 %P 1 - 33 %I Microtome Publishing %C Brookline, MA %@ false

%0 Conference Proceedings %A Focke, Jacob %A Marx, D&#225;niel %A Inerney, Fionn Mc %A Neuen, Daniel %A Sankar, Govind S. %A Schepper, Philipp %A Wellnitz, Philip %+ External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1EA4-A %R 10.1137/1.9781611977554.ch140 %D 2023 %B Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2023-01-22 - 2023-01-25 %C Florence, Italy %B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms %E Bansal, Nikhil; Nagarajan, Viswanath %P 3664 - 3683 %I SIAM %@ 978-1-61197-755-4

%0 Report %A Gao, Yuan %A Kyng, Rasmus %A Spielman, Daniel A. %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Robust and Practical Solution of Laplacian Equations by Approximate Elimination : %G eng %U http://hdl.handle.net/21.11116/0000-000C-B1C8-A %U https://arxiv.org/abs/2303.00709 %D 2023 %X We introduce a new algorithm and software for solving linear equations in<br>symmetric diagonally dominant matrices with non-positive off-diagonal entries<br>(SDDM matrices), including Laplacian matrices. We use pre-conditioned conjugate<br>gradient (PCG) to solve the system of linear equations. Our preconditioner is a<br>variant of the Approximate Cholesky factorization of Kyng and Sachdeva (FOCS<br>2016). Our factorization approach is simple: we eliminate matrix rows/columns<br>one at a time and update the remaining matrix using sampling to approximate the<br>outcome of complete Cholesky factorization. Unlike earlier approaches, our<br>sampling always maintains a connectivity in the remaining non-zero structure.<br>Our algorithm comes with a tuning parameter that upper bounds the number of<br>samples made per original entry. We implement our algorithm in Julia, providing<br>two versions, AC and AC2, that respectively use 1 and 2 samples per original<br>entry. We compare their single-threaded performance to that of current<br>state-of-the-art solvers Combinatorial Multigrid (CMG),<br>BoomerAMG-preconditioned Krylov solvers from HyPre and PETSc, Lean Algebraic<br>Multigrid (LAMG), and MATLAB's with Incomplete Cholesky Factorization (ICC).<br>Our evaluation uses a broad class of problems, including all large SDDM<br>matrices from the SuiteSparse collection and diverse programmatically generated<br>instances. Our experiments suggest that our algorithm attains a level of<br>robustness and reliability not seen before in SDDM solvers, while retaining<br>good performance across all instances. Our code and data are public, and we<br>provide a tutorial on how to replicate our tests. We hope that others will<br>adopt this suite of tests as a benchmark, which we refer to as SDDM2023. Our<br>solver code is available at: https://github.com/danspielman/Laplacians.jl/ Our<br>benchmarking data and tutorial are available at:<br>https://rjkyng.github.io/SDDM2023/<br> %K Mathematics, Numerical Analysis, math.NA,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Mathematical Software, cs.MS,Computer Science, Numerical Analysis, cs.NA

%0 Conference Proceedings %A Gionis, Aristides %A Khodamoradi, Kamyar %A Ordozgoiti, Bruno %A Riegel, Benedikt %A Spoerhase, Joachim %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Constant-Factor Approximation Algorithm for Reconciliation k-Median : %G eng %U http://hdl.handle.net/21.11116/0000-000C-739D-2 %D 2023 %B 26th International Conference on Artificial Intelligence and Statistics %Z date of event: 2023-04-25 - 2023-04-27 %C Valencia, Spain %B Proceedings of the 26th International Conference on Artificial Intelligence and Statistics %I PMLR %B Proceedings of the Machine Learning Research

%0 Conference Proceedings %A Goldenberg, Elazar %A Kociumaka, Tomasz %A Krauthgamer, Robert %A Saha, Barna %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T An Algorithmic Bridge Between Hamming and Levenshtein Distances : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1588-3 %R 10.4230/LIPIcs.ITCS.2023.58 %U urn:nbn:de:0030-drops-175615 %D 2023 %B 14th Innovations in Theoretical Computer Science Conference %Z date of event: 2023-01-10 - 2023-01-13 %C Cambridge, MA, USA %B 14th Innovations in Theoretical Computer Science Conference %E Tauman Kalai, Yael %P 1 - 23 %Z sequence number: 58 %I Schloss Dagstuhl %@ 978-3-95977-263-1 %B Leibniz International Proceedings in Informatics %U https://drops.dagstuhl.de/opus/volltexte/2023/17561/

%0 Conference Proceedings %A Goranci, Gramoz %A Henzinger, Monika %A Nanongkai, Danupon %A Saranurak, Thatchaphol %A Thorup, Mikkel %A Wulff, Christian %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Fully Dynamic Exact Edge Connectivity in Sublinear Time : %G eng %U http://hdl.handle.net/21.11116/0000-000C-9383-9 %R 10.1137/1.9781611977554.ch3 %D 2023 %B Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2023-01-22 - 2023-01-25 %C Florence, Italy %B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms %E Bansal, Nikhil; Nagarajan, Viswanath %P 70 - 86 %I SIAM %@ 978-1-61197-755-4 %U https://epubs.siam.org/doi/reader/10.1137/1.9781611977554.ch3

%0 Conference Proceedings %A Gouleakis, Themis %A Lakis, Konstantinos %A Shahkarami, Golnoosh %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Learning-Augmented Algorithms for Online TSP on the Line : %G eng %U http://hdl.handle.net/21.11116/0000-000C-466C-D %D 2023 %B 37th AAAI Conference on Artificial Intelligence %Z date of event: 2023-02-07 - 2023-02-14 %C Washington, DC, USA %B Proceedings of the 37th AAAI Conference on Artificial Intelligence %I AAAI

%0 Conference Proceedings %A Gutowski, Grzegorz %A Mittelst&#228;dt, Florian %A Rutter, Ignaz %A Spoerhase, Joachim %A Wolff, Alexander %A Zink, Johannes %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Coloring Mixed and Directional Interval Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000C-26A4-0 %R 10.1007/978-3-031-22203-0_30 %D 2023 %B 30th International Symposium on Graph Drawing and Network Visualization %Z date of event: 2022-09-13 - 2022-09-16 %C Tokyo, Japan %B Graph Drawing and Network Visualization %E Angelini, Patrizio; von Hanxleden, Reinhard %P 418 - 431 %I Springer %@ 978-3-031-22202-3 %B Lecture Notes in Computer Science %N 13764

%0 Conference Proceedings %A Hatzel, Meike %A Jaffke, Lars %A Lima, Paloma T. %A Masa&#345;&#237;k, Tom&#225;&#353; %A Pilipczuk, Marcin %A Sharma, Roohani %A Sorge, Manuel %+ External Organizations External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parameterized by the Size of the Cutset: Twin-width Meets Flow-Augmentation : %G eng %U http://hdl.handle.net/21.11116/0000-000C-8E4C-0 %R 10.1137/1.9781611977554.ch123 %D 2023 %B Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2023-01-22 - 2023-01-25 %C Florence, Italy %B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms %E Bansal, Nikhil; Nagarajan, Viswanath %P 3229 - 3244 %I SIAM %@ 978-1-61197-755-4

%0 Conference Proceedings %A Jiang, Yonggang %A Mukhopadhyay, Sagnik %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Finding a Small Vertex Cut on Distributed Networks : %G eng %U http://hdl.handle.net/21.11116/0000-000C-947A-4 %D 2023 %B 55th Annual ACM Symposium on Theory of Computing %Z date of event: 2023-06-20 - 2023-06-23 %C Orlando, FL, USA %B Proceedings of the 55th Annual ACM Symposium on Theory of Computing %I ACM

%0 Conference Proceedings %A Kempa, Dominik %A Kociumaka, Tomasz %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays : %G eng %U http://hdl.handle.net/21.11116/0000-000C-158F-C %R 10.1137/1.9781611977554.ch187 %D 2023 %B Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2023-01-22 - 2023-01-25 %C Florence, Italy %B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms %E Bansal, Nikhil; Nagarajan, Viswanath %P 5122 - 5202 %I SIAM %@ 978-1-61197-755-4

%0 Journal Article %A Kleer, Pieter %A Simon, Hans U. %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Primal and Dual Combinatorial Dimensions : %G eng %U http://hdl.handle.net/21.11116/0000-000C-15FE-F %R 10.1016/j.dam.2022.11.010 %7 2023 %D 2023 %J Discrete Applied Mathematics %V 327 %& 185 %P 185 - 196 %I Elsevier %C Amsterdam %@ false

%0 Conference Proceedings %A Li, Jason %A Nanongkai, Danupon %A Panigrahi, Debmalya %A Saranurak, Thatchaphol %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Near-Linear Time Approximations for Cut Problems via Fair Cuts : %G eng %U http://hdl.handle.net/21.11116/0000-000C-9381-B %R 10.1137/1.9781611977554.ch10 %D 2023 %B Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2023-01-22 - 2023-01-25 %C Florence, Italy %B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms %E Bansal, Nikhil; Nagarajan, Viswanath %P 240 - 257 %I SIAM %@ 978-1-61197-755-4 %U https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch10?download=true

%0 Conference Proceedings %A Mazowiecki, Filip %A Sinclair-Banks, Henry %A W&#281;grzycki, Karol %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Coverability in 2-VASS with One Unary Counter is in NP : Coverability in 2-{VASS} with One Unary Counter is in {NP} %G eng %U http://hdl.handle.net/21.11116/0000-000C-4678-F %D 2023 %B 26th International Conference on Foundations of Software Science and Computation Structures %Z date of event: 2023-04-22 - 2023-04-27 %C Paris, France %B 26th International Conference on Foundations of Software Science and Computation Structures %I Springer

%0 Journal Article %A Misra, Pranabendu %A Saket, Saurabh %A Sharma, Roohani %A Zehavi, Meirav %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number : %G eng %U http://hdl.handle.net/21.11116/0000-000C-9037-3 %R 10.1007/s00453-022-01093-w %7 2023 %D 2023 %J Algorithmica %I Springer-Verlag %C New York %@ false

%0 Conference Proceedings %A Olkowski, J&#281;drzej %A Pilipczuk, Micha&#322; %A Rychlicki, Mateusz %A W&#281;grzycki, Karol %A Zych-Pawlewicz, Anna %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Dynamic Data Structures for Parameterized String Problems : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1F0E-4 %R 10.4230/LIPIcs.STACS.2023.50 %U urn:nbn:de:0030-drops-177026 %D 2023 %B 40th International Symposium on Theoretical Aspects of Computer Science %Z date of event: 2023-03-07 - 2023-03-09 %C Hamburg, Germany %B 40th International Symposium on Theoretical Aspects of Computer Science %E Berenbrink, Petra; Bouyer, Patricia; Dawar, Anuj; Kant&#233;, Mamadou Moustapha %P 1 - 22 %Z sequence number: 50 %I Schloss Dagstuhl %@ 978-3-95977-266-2 %B Leibniz International Proceedings in Informatics %N 254 %@ false

%0 Conference Proceedings %A Simon, Hans U. %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Tournaments, Johnson Graphs, and NC-Teaching : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1606-5 %D 2023 %B The 34th International Conference on Algorithmic Learning Theory %Z date of event: 2023-02-20 - 2023-02-23 %C Singapore, Singapore %B Proceedings of the 34th International Conference on Algorithmic Learning Theory %E Agrawal, Shipra; Orabona, Francesco %P 1411 - 1428 %I PMLR %B Proceedings of the Machine Learning Research %N 201

%0 Report %A Zandieh, Amir %A Han, Insu %A Daliri, Majid %A Karbasi, Amin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T KDEformer: Accelerating Transformers via Kernel Density Estimation : %G eng %U http://hdl.handle.net/21.11116/0000-000C-90F7-A %U https://arxiv.org/abs/2302.02451 %D 2023 %X Dot-product attention mechanism plays a crucial role in modern deep<br>architectures (e.g., Transformer) for sequence modeling, however, na\"ive exact<br>computation of this model incurs quadratic time and memory complexities in<br>sequence length, hindering the training of long-sequence models. Critical<br>bottlenecks are due to the computation of partition functions in the<br>denominator of softmax function as well as the multiplication of the softmax<br>matrix with the matrix of values. Our key observation is that the former can be<br>reduced to a variant of the kernel density estimation (KDE) problem, and an<br>efficient KDE solver can be further utilized to accelerate the latter via<br>subsampling-based fast matrix products. Our proposed KDEformer can approximate<br>the attention in sub-quadratic time with provable spectral norm bounds, while<br>all prior results merely provide entry-wise error bounds. Empirically, we<br>verify that KDEformer outperforms other attention approximations in terms of<br>accuracy, memory, and runtime on various pre-trained models. On BigGAN image<br>generation, we achieve better generative scores than the exact computation with<br>over $4\times$ speedup. For ImageNet classification with T2T-ViT, KDEformer<br>shows over $18\times$ speedup while the accuracy drop is less than $0.5\%$.<br> %K Computer Science, Learning, cs.LG,Computer Science, Computer Vision and Pattern Recognition, cs.CV,Computer Science, Data Structures and Algorithms, cs.DS