phpre.github.io/index.html at main · phpre/phpre.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<!--#config errmsg="[Lain is angry.]"-->
<html xmlns="https://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
    <head>
        <!--#config timefmt="%A, %d %B %Y - %R" -->
        <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
        <!-- CORRECT HERE: This is REALLY needed all search engines and bookmark manager love this; please use this format: -->
        <title>Philip Wellnitz</title>

        <link rel="shortcut icon" type="image/x-icon" href="favicon.png">

        <script src="./interpreter.min.js"></script>
        <script type="text/javascript">
            let fs = Interpreter.getFirstState();
            function runSOSML() {
                try {
                    let res = Interpreter.interpret(document.getElementById("sosml").value + ';', fs);
                    if (res.evaluationErrored) {
                        document.getElementById("output").value = 'Uncaught SML Error: ' + res.error.toString();
                    } else {
                        document.getElementById("output").value = res.state.toString({stopId: fs.id + 1});
                    }
                } catch ( e ) {
                    document.getElementById("output").value = e.toString();
                }
            }
        </script>
        <style type="text/css" media="screen">
a#hp-index, a:link#hp-index, a:visited#hp-index {background: rgb(80%,85%,90%);}
        </style>
        <!-- put your personal styles here -->
        <meta name="google-site-verification" content="ye7ut4AfafMdzfWiH7qEYEl9flgxH6LFnmnFQomR-Ds" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0">
    </head>

    <body>
        <div id="headerspacer"></div>
        <div id="col2o2">
            <div id="col2o2content">
                <h1 style="padding-bottom: .25em;
                           font-size: 18px;">Philip Wellnitz / フィリップ・ヴェルニッツ<a href="https://orcid.org/0000-0002-6482-8478" target="orcid.widget"><span class="mini-orcid-icon-16" style="
                                            background: url(data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABIAAAASCAYAAABWzo5XAAAABGdBTUEAALGPC/xhBQAAACBjSFJNAAB6JgAAgIQAAPoAAACA6AAAdTAAAOpgAAA6mAAAF3CculE8AAAABmJLR0QAAAAAAAD5Q7t/AAAACXBIWXMAAAsSAAALEgHS3X78AAABnElEQVQ4y52UvUtCURjGf968lmQhFGXYEH3QUg0JhkPR4l5T0IUosMGxv6C1KdpahCZbGxscGiXBloIKo0ESEYpEM71+3NvgvXW0j3vp2c57zvPjPQ/nPWCheDrkiKdDDqtzjl/MQSAChAG/Uc4BCSCmBJKpP0HxdGgQOAY2LRo4BaJKIFn6BjIgCSDolPrQ9Caa3vwLlgLCJkwSNo6BIEBoYp8537ZVLEHD89WRkcmlWex3+WhqNeqtMrLk/nTWWxVA7wYuKYFkymksIuLO/FiEYjXDazXD6tQhJTWLLLmRezxkns+4zsfQdQ3B+wkK/9Z/Sc1yfrsFgFseYnnyAE1vcJM/QfSaGfmxoWrjhaunI2aG18WyvztsW6rUC/Q6vd/qJihnFzTuXeG5ciOWcgBmRglg9yejLLkZHVhEcrgY8SwwPbzGxcOeeCQhgmIi6LV6z5uaR20WKdYemR3ZQNMalNUs53c7vNcLIigGnS87jvVodOtUCSSV7rCjtJ+9XaUMT0fYGDMTpj2Qlp0gzFnH1UT95xuxlN2P7QOpwZChGlWkWQAAAABJRU5ErkJggg==) no-repeat;
                                            width: 18px;
                                            height: 18px;
                                            display: inline-block;
                                            margin: -2px 0 -2px 2px;
                                            "></span></a></h1>
                <p>
                〒101-8430<br/>
                Tokyo-to Chiyoda-ku Hitotsubashi 2-1-2<br/>
                National Institute of Informatics<br/>
                Room 1616<br/>
                <p><strong>Email:</strong>
                <a href="javascript:var a='wellnitz';var b='nii.ac.jp';location='m'+'ailt'+'o:'+a+'@'+b;" class="pub">wellnitz<img style="border: 0px solid; float: none; margin:0em 0em -0.4em 0em;" src="myat.png"  width="17" height="17" >nii.ac.jp</a><br>


                <p text align="justify">
                I am an Assistant Professor at the National Institute of Informatics and The Graduate University for Advanced Studies in Tokyo, Japan.
                Before that, I was a post-doctoral researcher at the Max Planck Institute for Informatics, Saarbruecken, Germany.
                This is a makeshift temporary webpage that will be replaced <em>soon</em>.
                </br>
                <strong>My works may not be used to train AI models.</strong>
                </p>

                <hr/>
                <h3>Research Interests</h3>
                <ul>
                    <li> Obtaining (provably) best-possible algorithms by designing faster algorithms and matching (conditional) lower bounds</li>
                    <li> <i>(Approximate) String Matching</i> and in general algorithms on strings</li>
                    <li> <i>Counting Problems</i>, also in parameterized settings (especially problems related to graph homomorphisms)</li>
                </ul>

                <p>
                I am happy to collaborate on any level and with anyone who supports <a href="https://en.wikipedia.org/wiki/Diversity,_equity,_and_inclusion">DEI</a>.
                </p>

                <hr class="clearpara"/>
                <h3><a name="publications">Selected Publications</a></h3>

                <p> The following lists contain only selected publications. Consult <a href="https://dblp.uni-trier.de/pid/204/1616.html">dblp</a> for a more complete list of publications.</p>

                <h4>Approximate String Matching</h4>
                <table id="references" cellpadding="6">
                    <tbody>
                        <tr class="ref">
                            <td class="data">
                                <p class="title"><b><a href="https://ieeexplore.ieee.org/document/10353095">"Optimal Algorithms for Bounded Weighted Edit Distance"</a></b> <a href="https://arxiv.org/abs/2305.06659">[arXiv]</a>
                                <a href="https://phpre.github.io/~wellnitz/slides/2023-FOCS.pdf">[slides]</a></p>
                                <p class="authors">with <a href="https://csssaz.github.io/">Alejandro Cassis</a> and <a href="https://www.mimuw.edu.pl/~kociumaka/">Tomasz Kociumaka</a></p>
                                <p class="summary">We give an \tilde{O}(n + n^0.5 k^1.5) algorithm for computing the weighted edit distance k between two strings.
                                We prove that our algorithm is optimal for n^0.5 ≤ k ≤ n under the APSP hypothesis.
                                <!--<i>FOCS'23</i>--></p>
                            </td>
                        </tr>
                        <tr class="ref">
                            <td class="data">
                                <p class="title"><b><a href="https://ieeexplore.ieee.org/document/9996673">"Faster Pattern Matching under Edit Distance"</a></b> <a href="https://arxiv.org/abs/2204.03087">[arXiv]</a> </p>
                                <p class="authors">with <a href="https://nms.kcl.ac.uk/panagiotis.charalampopoulos/">Panagiotis Charalampopoulos</a> and <a href="https://www.mimuw.edu.pl/~kociumaka/">Tomasz Kociumaka</a></p>
                                <p class="summary">We give an O(n + n/m k^3.5) algorithm for PM with edits.
                                This is the first improvement of
                                Cole and Hariharan's [CH'02] O(n + n/m k^4) algorithm for the problem.
                                <!--<i>FOCS'22</i>--></p>
                            </td>
                        </tr>
                        <!--
                            <tr class="ref">
                            <td class="data">
                            <p class="title"><b><a href="https://www.computer.org/csdl/proceedings-article/focs/2020/962100a978/1qyxzwzatXy">"Faster Approximate Pattern Matching: A Unified Approach"</a></b> <a href="https://arxiv.org/abs/2004.08350">[arXiv]</a> <a href="https://www.youtube.com/watch?v=yTM0LqlH8gY&feature=youtu.be">[video]</a></p>
                            <p class="authors">with <a href="https://nms.kcl.ac.uk/panagiotis.charalampopoulos/">Panagiotis Charalampopoulos</a> and <a href="https://www.mimuw.edu.pl/~kociumaka/">Tomasz Kociumaka</a></p>
                            <p class="summary">We tighten the
                            structural insight from [BKW, SODA'19] and
                            show a similar result for pattern matching
                            with edits: either there are very few occurrences of a pattern in a text, or both text and pattern are close to a common highly periodic string.
                            Using the structural insight,
                            we obtain faster algorithms for PM with
                            mismatches and edits for the
                            fully-compressed and other settings.
                            </td>
                            </tr>
                        -->
                    </tbody>
                </table>

                <h4>Counting (Small) Patterns in Graphs</h4>
                <table id="references" cellpadding="6">
                    <tbody>
                        <tr class="ref">
                            <td class="data">
                                <p class="title"><b><a href="https://dl.acm.org/doi/abs/10.1145/3618260.3649644">"Counting Small Induced Subgraphs with Edge-monotone Properties"</b></a> <a href="https://arxiv.org/abs/2311.08988">[arXiv]</a>
                                <p class="authors">with Simon Döring and Dániel Marx</p>
                                <p class="summary">We show that for any
                                (non-trivial) edge-monotone graph property Φ,
                                counting all induced subgraphs of a graph that
                                satisy Φ is #W[1]-hard. Further, for most natural edge-monotone properties, no significant improvement upon the brute-force algorithms is possible (unless ETH fails).
                                </p>
                            </td>
                        </tr>

                        <tr class="ref">
                            <td class="data">
                                <p class="title"><b><a href="https://doi.org/10.1137/1.9781611975994.133">"Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory"</a></b> <a href="https://arxiv.org/abs/1907.03850">[arXiv]</a>
                                <a href="https://phpre.github.io/~wellnitz/slides/2020-SODA.pdf">[slides]</a></p>
                                <p class="authors">with <a href="https://www.roth-marc.com/">Marc Roth</a></p>
                                <p class="summary">We show that any problem P in #W[1] (or W[1]) is
                                equivalent to the problem of counting homomorphisms between graphs
                                of graph classes H(P) and G(P).
                                <!--<i>SODA'20</i>--></p>
                            </td>
                        </tr>
                    </tbody>
                </table>

                <hr class="clearpara"/>
                <h3><a name="code">Editorial Activities and Program Committee Work</a></h3>

                I am a member of the Editorial Board of <a href="https://link.springer.com/journal/11786">Mathematics In Computer Science</a>; I am also responsible for its management and strategic development. If you are looking for a home for your high-quality contribution in Theoretical Computer Science, I would be happy if you give MCS a chance.

                <br/>

                I was/am/will be on the Program Committees of ICALP (A) 2026, MFCS 2025, CPM 2025, ESA (A) 2022.
                <hr class="clearpara"/>
                <h3><a name="code">Code</a></h3>

                <ul>
                    <li><a href="https://github.com/PH111P/tikz-kneser">tikz-kneser</a>: A tikz-library for drawing Kneser graphs.</a>
                    </li>
                    <li><a href="https://github.com/SOSML/SOSML">SOSML</a>: An interpreter for SML running in your browser, check it out at <a href="https://sosml.org">sosml.org</a>.
                        Alternatively, write your SML code in the text box below and click “interpret”.<br/>
                        Written at Saarland University together with Julian Baldus, Julian Dörfler, Jesko Dujmovic, Marvin Hofmann and Dominik Luche<br/><br/>
                        <textarea id="sosml" rows="4" cols="50">val x = "Hello" ^ " ";
x ^ "World!";</textarea>
                        <textarea id="output" rows="4" cols="50" readonly="true"></textarea>
                        <br/>
                        <button type="button" onclick="runSOSML()"> Interpret </button>
                        </br>
                        </br>
                    </li>
                    <li>Code of other projects is available on my <a href="https://github.com/ph111p/">GitHub profile</a></li>
                </ul>


                <hr class="clearpara"/>
                <h3><a name="teaching">Recent Teaching</a></h3>

                <ul>
                    <li>Winter 2023/24 (Saarland University)<br/>
                        <b>Lecturer</b>: <a href="https://cms.sic.saarland/algodat23/">Algorithms and Data Structures</a> (with Karl Bringmann and Evangelos Kipouridis)
                        <br/>
                        <br/>

                        <li>Summer 2023 (Saarland University)<br/>
                            <b>Lecturer</b>: <a href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/summer23/counting">Techniques for Counting Problems</a> (with Jacob Focke)
                            <br/>
                            <br/>


                            <li>Winter 2022/23 (Saarland University)<br/>
                                <b>Lecturer</b>: <a href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/winter22/random">Randomized Algorithms and Probabilistic Analysis of Algorithms</a>
                                <br/>
                                <br/>

                                <!-- <li>Winter 2021/22 (Saarland University)<br/>
                                    <b>Co-organizer</b>: <a href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/winter21/reading-group">Reading Group Algorithms: Continuous Methods for Combinatorial Problems</a> (with Kurt Mehlhorn, Roohani Sharma, and Hans Simon)
                                    <br/>
                                    </li>
                                    <li>Winter 2020/21 (Saarland University)<br/>
                                    <b>Assistant</b> (<a href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/winter20/property-testing">Property Testing</a>)
                                    <br/>
                                    </li>
                                    <li>Summer 2020 (Saarland University)<br/>
                                    <b>Assistant</b> (<a href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/summer20/parameterized-algorithms/">Parameterized Algorithms</a>)
                                    <br/>
                                    </li> -->
                </ul>

                <hr class="clearpara"/>
                <h3><a name="education">Short CV</a></h3>
                <!-- put the most recent entries on top of your list -->
                <ul>
                    <li> Since April 2024:<br />
                        Assistant Professor at the National Institute of Informatics, Tokyo, Japan.
                        <br/ >
                    </li>
                        <li> October 2021 - March 2024:<br />
                            Postdoctoral scholar at the <a href="https://www.mpi-inf.mpg.de">Max Planck Institute for Informatics</a><br />
                        </li>
                        <li> October 2018 - December 2021:<br />
                            PhD student in <a href="https://saarland-informatics-campus.de/">Computer Science</a> at <a href="https://www.uni-saarland.de">Saarland
                                University, Saarbrücken</a>, Germany and the <a href="https://www.mpi-inf.mpg.de">Max Planck Institute for Informatics</a><br />
                        </li>
                        <li> April 2017 - December 2021:<br />
                            Member of the <a href="https://www.graduateschool-computerscience.de/">Saarbrücken Graduate School of Computer Science</a>
                            <br />
                        </li>
                        <li><!-- October 2015 - April 2017:<br />-->
                            B.Sc. in Computer Science at <a href="https://saarland-informatics-campus.de/">Saarland University</a>, Saarbrücken, Germany<br />
                            <li><!--July 2015<br />-->
                                Abitur at <a href="https://www.hhgym.de/">Heinrich-Hertz-Gymnasium</a>, Berlin, Germany</li>

                </ul>
            </div>
        </div>
    </body>

</html>