-
Notifications
You must be signed in to change notification settings - Fork 0
/
finegrained.html
65 lines (65 loc) · 2.78 KB
/
finegrained.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
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<link rel="shortcut icon" type="image/x-icon" href="img/favicon.ico">
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>finegrained</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
div.columns{display: flex; gap: min(4vw, 1.5em);}
div.column{flex: auto; overflow-x: auto;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
ul.task-list{list-style: none;}
ul.task-list li input[type="checkbox"] {
width: 0.8em;
margin: 0 0.8em 0.2em -1.6em;
vertical-align: middle;
}
</style>
<link rel="stylesheet" href="main.css" />
<script
src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml-full.js"
type="text/javascript"></script>
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1
id="fine-grained-complexity-an-advertisement-work-in-progress">Fine-grained
complexity, an advertisement (work in progress)</h1>
<p>In a recent icebreaker game, my prompt to tell my game partner about
my coolest memory. My response was basically that there’s this really
cool part of complexity theory that looks at the hardness of
computational problems in much finer detail than usual.<a href="#fn1"
class="footnote-ref" id="fnref1" role="doc-noteref"><sup>1</sup></a> In
fine-grained vomplexity, the usual light microscope that doesn’t really
notice differences below something like the polynomial time reduction
scale gets replaced by the electron microscope that quite often sees
complexity differences of just <span
class="math inline">\(n^{0.0001}\)</span>.</p>
<p>Anyway, while then telling my interlocutor about one particularly
cool result from fine-grained complexity, I realized that I had
forgotten the details of its proof, which is not a fine state of affairs
at all (though the forgotten details were at a resolution too fine to
significantly affect the conversation). This post will rectify this.</p>
<h2 id="ov-the-problem">OV, the problem</h2>
<h2 id="fine-grained-complexity-of-sat">Fine-grained complexity of
SAT</h2>
<h2
id="what-the-fine-grained-complexity-of-sat-tells-us-about-that-of-ov">What
the fine-grained complexity of SAT tells us about that of OV</h2>
<section id="footnotes" class="footnotes footnotes-end-of-document"
role="doc-endnotes">
<hr />
<ol>
<li id="fn1"><p>To clarify, I’m enough of an empath to realize that this
is an out-of-envisioned-distribution answer for the given prompt.<a
href="#fnref1" class="footnote-back" role="doc-backlink">↩︎</a></p></li>
</ol>
</section>
</body>
</html>