forked from chaoxu/chaoxu.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
233 lines (233 loc) · 17.1 KB
/
index.html
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Ke Shi</title>
<meta name="description" content="The personal webpage of Ke Shi.">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/normalize.min.css" crossorigin="anonymous">
<!-- Do not remove katex render. Index page is a idpage -->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css" integrity="sha384-Xi8rHCmBmhbuyyhbI88391ZKP2dmfnOl4rT9ZfRI7mLTdk1wblIUnrIq35nqwEvC" crossorigin="anonymous">
<!-- The loading of KaTeX is deferred to speed up page rendering -->
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.js" integrity="sha384-X/XCfMm41VSsqRNQgDerQczD69XqmjOOOwYQvr/uuC+j4OPoNhVgjdGFwhvN02Ja" crossorigin="anonymous"></script>
<script>
document.addEventListener("DOMContentLoaded", function() {
var macros={
"\\C":"\\mathbb{C}",
"\\F":"\\mathbb{F}",
"\\e": "\\varepsilon",
"\\eps": "\\varepsilon",
"\\mex": "\\mathop{\\operatorname{mex}}",
"\\lcm": "\\mathop{\\operatorname{lcm}}",
"\\dist": "\\mathop{\\operatorname{dist}}",
"\\bigtriangleright": "{\\mathop{\\Large \\triangleright}}",
"\\bigtriangleleft": "{\\mathop{\\Large \\triangleleft}}",
'\\set':'\\left\\{ #1 \\right\\}',
'\\floor':'\\left\\lfloor #1 \\right\\rfloor',
'\\ceil':'\\left\\lceil #1 \\right\\rceil',
'\\abs':'\\left\\| #1 \\right\\|'
}
var mathElements = document.getElementsByClassName("math");
for (var i = 0; i < mathElements.length; i++) {
var texText = mathElements[i].firstChild;
if (mathElements[i].tagName == "SPAN") { katex.render(texText.data, mathElements[i], { displayMode: mathElements[i].classList.contains("display"), throwOnError: false, macros:macros} );
}}});
</script>
<!-- toggle selected publications -->
<script>
function togglePublication() {
var x = document.getElementsByClassName("cv-non-selected");
for (var i = x.length - 1; i >= 0; --i)
x[i].classList.remove("cv-non-selected");
x = document.getElementById("pub-toggle");
x.style.display = "none";
}
</script>
<link href="https://fonts.googleapis.com/icon?family=Material+Icons" rel="stylesheet">
<link rel="shortcut icon" type="image/x-icon" href="/files/pictures/terminal.512.png" />
<link rel="stylesheet" href="/css/default.css" crossorigin="anonymous">
<link rel="stylesheet" href="/css/homepage.css?v=20220803" crossorigin="anonymous">
</head>
<body onload="togglePublication()">
<div class="container">
<div class="person" itemscope="" itemtype="http://schema.org/Person">
<meta itemprop="gender" content="Male">
<!-- <meta itemprop="birthDate" content="September 12, 1989">
<meta itemprop="honorificPrefix" content="Dr">
<meta itemprop="honorificSuffix" content="PhD"> -->
<meta itemprop="url" content="https://keshi.pro">
<div class="row" style="display:block"><h1 id="site-title"><span itemprop="givenName">Ke</span> <span itemprop="familyName">Shi</span> <wbr>|<wbr>
<ruby><rb>史</rb><rp>(</rp><rt>shǐ</rt><rp>)</rp></ruby>
<ruby><rb>可</rb><rp>(</rp><rt>kě</rt><rp>)</rp></ruby>
</h1></div>
<div class="row">
<div class="intro-left" itemprop="image" itemscope itemtype="http://schema.org/ImageObject">
<meta itemprop="representativeOfPage" content="True">
<img width="270" height="270" src="/files/pictures/ahh.png" style="border-radius:50%;max-width:95%" title="ahh" alt="a photo" itemprop="contentUrl"/>
</div>
<div class="intro-right">
<p>
I am a Master's student at <a href="https://ustc.edu/">USTC</a>, currently under the guidance of <a href="http://staff.ustc.edu.cn/~wwwucuc/">Shuai Shao</a>.
</p>
<p>
Prior to this, I earned my Bachelor's degree in Computer Science from <a href="https://www.uestc.edu.cn/">UESTC</a> while conducting theoretical computer science research under the guidance of <a href="https://chaoxu.prof">Chao Xu</a>.
</p>
<p>
My research interests revolve around algorithms and combinatorial optimization. Recently, my focus has been directed towards approximate counting algorithms and their correlations with the phenomenon of phase transitions in statistical physics.
<!-- You can find my CV <a href="files/cv.pdf">here</a> -->
</p>
<p>You can contact me through email <a href="mailto:[email protected]"><samp itemprop="email">[email protected]</samp></a> or
<a href="mailto:[email protected]"><samp itemprop="email">[email protected]</samp></a>.</p>
</div>
</div>
</div>
<div class="row pubtypeheader" id="pub-toggle">
<span>Selected Publications<br /><span style="font-size:0.6em" onclick="togglePublication()"><em><a>See all publications.</a></em></span></span>
</div>
<div class="cv-non-selected row pubtypeheader">Conference Publications</div>
<!-- A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function -->
<div class="cv-selected row cv-entry" id="sub4part">
<input type="checkbox" class="abstract-guard" id="sub4part-toggle">
<div class="cv-left">
<label class="showmore material-icons" for="sub4part-toggle"></label>
<a href="files/papers/sub4part.pdf"><i class="material-icons">description</i></a>
<a href="files/presentations/sub4part.pdf"><i class="material-icons">airplay</i></a>
</div>
<div class="cv-right">
<cite class="paper-title">A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function</cite>
<ul class="coauthor-list">
<li>
Tsuyoshi Hirayama</li><li>
<a href="https://yhliu126.github.io/">Yuhao Liu</a></li><li>
<a href="https://www.kurims.kyoto-u.ac.jp/en/list/makino.html">Kazuhisa Makino</a></li><li>
<a href="https://keshi.pro/">Ke Shi</a></li><li>
<a href="https://chaoxu.prof">Chao Xu</a></li></ul>
<p><em>
<abbr title="ACM-SIAM Symposium on Discrete Algorithms">SODA</abbr> <time>2023</time>.
</em><p>
<aside class="cv-non-selected note">The <a href="/files/papers/sub4part-journal.pdf">journal version</a> was serialized in Mathematical Programming.</aside>
</div>
<div class="abstract">
<p>In this paper, we study the minimum <span class="math">k</span>-partition problem of submodular functions, i.e., given a finite set <span class="math">V</span> and a submodular function <span class="math">f:2^V\to \R</span>, computing a <span class="math">k</span>-partition <span class="math"> \{ V_1, \ldots, V_k \}</span> of <span class="math">V</span> with minimum <span class="math">\sum_{i=1}^k f(V_i)</span>. The problem is a natural generalization of the minimum <span class="math">k</span>-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general <span class="math">k</span>, and solvable in polynomial time for <span class="math">k \leq 3</span>. In this paper, we construct the first polynomial-time algorithm for the minimum <span class="math">4</span>-partition problem.</p>
</div>
</div>
<!-- Almost optimum <span class="math">\ell</span>-covering of <span class="math">\Z_n</span> -->
<div class="cv-non-selected row cv-entry" id="cyclic-cover">
<input type="checkbox" class="abstract-guard" id="cyclic-cover-toggle">
<div class="cv-left">
<label class="showmore material-icons" for="cyclic-cover-toggle"></label>
<a href="files/papers/cyclic-cover.pdf"><i class="material-icons">description</i></a>
<i class="material-icons disabled">airplay</i>
</div>
<div class="cv-right">
<cite class="paper-title">Almost optimum <span class="math">\ell</span>-covering of <span class="math">\Z_n</span></cite>
<ul class="coauthor-list">
<li>
<a href="https://keshi.pro/">Ke Shi</a></li><li>
<a href="https://chaoxu.prof">Chao Xu</a></li></ul>
<p><em>
<abbr title="International Computing and Combinatorics Conference">COCOON</abbr> <time>2024</time>.
</em><p>
</div>
<div class="abstract">
<p>A subset <span class="math">B</span> of ring <span class="math">\Z_n</span> is called a <span class="math">\ell</span>-covering set if <span class="math">\{ ab \pmod n \mid 0\leq a \leq \ell, b\in B\} = \Z_n</span>. We show there exists a <span class="math">\ell</span>-covering set of <span class="math">\Z_n</span> of size <span class="math">O(\frac{n}{\ell}\log n)</span> for all <span class="math">n</span> and <span class="math">\ell</span>, and how to construct such set. We also show examples where any <span class="math">\ell</span>-covering set must have size <span class="math">\Omega(\frac{n}{\ell}\frac{\log n}{\log \log n})</span>. The proof uses a refined bound for relative totient function obtained through sieve theory, and existence of a large divisor with linear divisor sum.</p>
</div>
</div>
<div class="cv-non-selected row pubtypeheader">Journal Publications</div>
<!-- A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function -->
<div class="cv-selected row cv-entry" id="sub4part-journal">
<input type="checkbox" class="abstract-guard" id="sub4part-journal-toggle">
<div class="cv-left">
<label class="showmore material-icons" for="sub4part-journal-toggle"></label>
<a href="files/papers/sub4part-journal.pdf"><i class="material-icons">description</i></a>
<i class="material-icons disabled">airplay</i>
</div>
<div class="cv-right">
<cite class="paper-title">A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function</cite>
<ul class="coauthor-list">
<li>
Tsuyoshi Hirayama</li><li>
<a href="https://yhliu126.github.io/">Yuhao Liu</a></li><li>
<a href="https://www.kurims.kyoto-u.ac.jp/en/list/makino.html">Kazuhisa Makino</a></li><li>
<a href="https://keshi.pro/">Ke Shi</a></li><li>
<a href="https://chaoxu.prof">Chao Xu</a></li></ul>
<p><em>
Mathematical Programming <time>2023</time>.
</em><p>
<aside class="cv-non-selected note">An <a href="/files/papers/sub4part.pdf">extended abstract</a> of this work appeared in SODA 2023.</aside>
</div>
<div class="abstract">
<p>In this paper, we study the minimum <span class="math">k</span>-partition problem of submodular functions, i.e., given a finite set <span class="math">V</span> and a submodular function <span class="math">f:2^V\to \R</span>, computing a <span class="math">k</span>-partition <span class="math"> \{ V_1, \ldots, V_k \}</span> of <span class="math">V</span> with minimum <span class="math">\sum_{i=1}^k f(V_i)</span>. The problem is a natural generalization of the minimum <span class="math">k</span>-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general <span class="math">k</span>, and solvable in polynomial time for <span class="math">k \leq 3</span>. In this paper, we construct the first polynomial-time algorithm for the minimum <span class="math">4</span>-partition problem.</p>
</div>
</div>
<div class="cv-non-selected row pubtypeheader"><span>Manuscripts<br /><span style="font-size:0.6em"><em>Some manuscripts are available upon request.</em></span></span></div>
<!-- Strong spatial mixing for the matching polynomial: A simple proof via Heilmann-Lieb Theorem -->
<div class="cv-non-selected row cv-entry" id="matching-ssm">
<input type="checkbox" class="abstract-guard" id="matching-ssm-toggle">
<div class="cv-left">
<label class="showmore material-icons" for="matching-ssm-toggle"></label>
<a href="files/papers/matching-ssm.pdf"><i class="material-icons">description</i></a>
<i class="material-icons disabled">airplay</i>
</div>
<div class="cv-right">
<cite class="paper-title">Strong spatial mixing for the matching polynomial: A simple proof via Heilmann-Lieb Theorem</cite>
<ul class="coauthor-list">
<li>
<a href="http://staff.ustc.edu.cn/~wwwucuc/">Shuai Shao</a></li><li>
<a href="https://keshi.pro/">Ke Shi</a></li></ul>
<p><em>
2024, Submitted.
</em><p>
</div>
<div class="abstract">
<p>We study the connections between strong spatial mixing and zero-freeness, the two main notions used to devise deterministic approximation algorithms for counting problems. Following a recent framework introduced by [Regts, G. (2023). Absence of zeros implies strong spatial mixing. Probability Theory and Related Fields, 186(1), 621-641.] for the vertex model, we show that the implication from zero-freeness of the partition function to strong spatial mixing also works for the matching polynomial, a typical counting problem in the edge model. Based on Heilmann and Lieb's results, a zero-free region <span class="math">C_\Delta=\C \backslash (-\infty,-\frac{1}{4(\Delta-1)}]</span> of the partition function and a Christoffel--Darboux type identity, we give a very simple proof for strong spatial mixing of the matching polynomial on graphs of degree bounded by <span class="math">\Delta</span> with any complex edge parameter <span class="math">z \in C_\Delta</span>. This proof does not rely on the tree recursion which is commonly used for proving strong spatial mixing in previous results.</p>
</div>
</div>
<!-- Strong Spatial Mixing for Ferromagnetic Ising Models: A Novel Perspective from Edge Activity -->
<div class="cv-non-selected row cv-entry" id="ising-edge-ssm">
<input type="checkbox" class="abstract-guard" id="ising-edge-ssm-toggle">
<div class="cv-left">
<label class="showmore material-icons" for="ising-edge-ssm-toggle"></label>
<a href="files/papers/ising-edge-ssm.pdf"><i class="material-icons">description</i></a>
<i class="material-icons disabled">airplay</i>
</div>
<div class="cv-right">
<cite class="paper-title">Strong Spatial Mixing for Ferromagnetic Ising Models: A Novel Perspective from Edge Activity</cite>
<ul class="coauthor-list">
<li>
<a href="http://staff.ustc.edu.cn/~wwwucuc/">Shuai Shao</a></li><li>
<a href="https://keshi.pro/">Ke Shi</a></li></ul>
<p><em>
2024, Submitted.
</em><p>
</div>
<div class="abstract">
<p>We prove a totally novel form of strong spatial mixing (SSM) for the ferromagnetic Ising model in terms of edge activities. This SSM property holds for the entire zero-free region of Lee--Yang Theorem, i.e., <span class="math">\beta>1</span> and <span class="math">|\lambda|<1</span> or symmetrically <span class="math">|\lambda|>1</span>. We also prove a form of SSM in terms of external fields in a smaller region <span class="math">\beta>1</span> and <span class="math">|\lambda|<1/\beta</span> or symmetrically <span class="math">|\lambda|>\beta</span>. These SSM properties can be exploited to devise FPTASes via Weitz's and Barvinok's algorithms. Our proof is based on the framework introduced by [Regts, G. (2023). Absence of zeros implies strong spatial mixing. Probability Theory and Related Fields, 186(1), 621-641.], namely local dependence of coefficients (LDC) and a uniform bound implies SSM. In order to establish LDC, we prove a division relation for the 2-spin system on general graphs.</p>
</div>
</div>
<!-- An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies -->
<div class="cv-non-selected row cv-entry" id="scp">
<input type="checkbox" class="abstract-guard" id="scp-toggle">
<div class="cv-left">
<label class="showmore material-icons" for="scp-toggle"></label>
<a href="files/papers/scp.pdf"><i class="material-icons">description</i></a>
<i class="material-icons disabled">airplay</i>
</div>
<div class="cv-right">
<cite class="paper-title">An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies</cite>
<ul class="coauthor-list">
<li>
<a href="https://stargazer-cyk.github.io/">Yike Chen</a></li><li>
<a href="https://keshi.pro/">Ke Shi</a></li><li>
<a href="https://chaoxu.prof">Chao Xu</a></li></ul>
<p><em>
2024, Submitted.
</em><p>
</div>
<div class="abstract">
<p>The Stacker Crane Problem (SCP) is a variant of the Traveling Salesman Problem. In SCP, pairs of pickup and delivery points are designated on a graph, and a crane must visit these points to move objects from each pickup location to its respective delivery point. The goal is to minimize the total distance traveled. SCP is known to be NP-hard, even on tree structures. The only positive results, in terms of polynomial-time solvability, apply to graphs that are topologically equivalent to a path or a cycle. We propose an algorithm that is optimal for each fixed topology, running in near-linear time. This is achieved by demonstrating that the problem is fixed-parameter tractable (FPT) when parameterized by both the cycle rank and the number of branch vertices.</p>
</div>
</div>
</div>
</body>
</html>