- Does the class of constant-degree expanders have polynomially-long induced paths?
- Planar embedding conjecture — Can every planar graph equipped with an arbitrary shortest-path metric be embedded into L1 with only a constant distortion? Anastasios Sidiropoulos solves the case when the metric has non-positive curvature; Chekuri et al. proves the case when the graph is O(1)-outerplanar; Chakrabarti et al. proves a natural analogous case when the graph is (K5-e)-free.
- Barnette conjecture (not the one about Hamiltonian cycle) — There is always non-null-homotopic separating simple cycle on every triangulation of an orientable surface of genus g greater than 3.
- “Tight lower bound for the channel assignment problem” by Arkadiusz Socała: No time algorithm to the channel assignment problem assuming ETH.
- “Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph” by Viktor Kiss and Lilla Tothmeresz: Computing the rank of a divisor on a graph is NP-hard.
- “3SUM Hardness in (Dynamic) Data Structures” by Tsvi Kopelowitz, Seth Pettie, and Ely Porat.
- “Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles” by Christian Wulff-Nilsen.
- “Social choice, computational complexity, Gaussian geometry, and Boolean functions” by Ryan O’Donnell.
Directed reachability problem on surface graphs can be solved in poly-time and sub-linear space (!). See the survey by Vinodchandran Variyam.
Hindman’s theorem (a special case). Suppose we color the natural numbers using k colors. Then there exists a color c and an infinite set S, all colored with c, such that every finite sum of over S has color c as well.
Also, this theorem is claimed to be rather unpleasant to prove if we insist on not using ultrafilters.
最近花了許多時間讀資格考, 寫了不少筆記, 沒有時間寫網誌… 難得有新聞來寫一下!
Again the exponent for the fastest matrix multiplication algorithm is improved. This time the magical number is 2.3728639, 0.0000630 better than Williams’ 2.3729269. (Last time it goes from the famous CW bound 2.3754770 to Stothers’ 2.3736898 then to Williams’, a 0.0025501 improvement.)
Powers of Tensors and Fast Matrix Multiplication, François Le Gall, 2014.
* Results related to Pumping Lemma
Theorem. A language accepted by a DFA of states is
- nonempty if and only if accepts a sentence of length less lean .
- infinite if and only if accepts a sentence of length with .
The union of the following languages, , is non-regular, but nevertheless it cannot be proven using pumping lemma.
and either , , or
and precisely of symbols in are 3’s
* Regular languages are precisely constant-space languages
Theorem. A regular language can be recognized by a two-way read-only Turing machine.
Proof sketch. Record the configuration of each time we first visit the -th cell. Define a finite automaton to simulate the same behavior.
Theorem. is the same as , both are the class of regular languages. That is, having an algorithm that uses -space is equal to not using any space.
Proof sketch. If a Turing machine uses space, there are possible configurations and possible crossing sequences. If then there are two crossing sequences that are the same, and we can further shorten a shortest string accepted by the machine by the following lemma:
Lemma. Let be a machine and be the input. Suppose two crossing sequence and are equal; then by removing the substring of from index to (assume ), we get another string that is accepted by the machine .
This is a contradiction.
The following language is non-regular but can be decided in space:
where is the binary representation of .
* Generating function of regular language
For a given language ,
is the generating function of . Using analytic combinatorics we can prove the following useful facts.
Theorem. For a regular language , the generating function is rational.
Theorem. Let be a finite automaton of a language . Then the generating function of is the following rational function determined under matrix form
where number of different labels between and ; and as characteristic vectors.
* Minimizing finite automata
Brzozowski’s algorithm use only power set construction and edge reversal . One can observe that reversing edges of a DFA gives an NFA of the reverse language. Then the power set construction gives a minimum DFA. This algorithm takes exponential time in the worst case.
Hopcroft’s algorithm is the fastest algorithm known; runs in time. Try to partition the states using the Myhill-Nerode equivalence relation.
* Relation with
Theorem. and are incomparable.
Proof. Parity is not in . Palindrome/addition/ are not regular.
Kleene-Buchi Theorem. For a language L, the following are equivalent:
(1) L is recognized by a finite automaton,
(2) L is defined by a regular expression,
(3) L is definable in Monadic second order logic,
(4) L is recognized by a finite monoid.
The syntactic monoid is defined by the equivalence with
if and only if for every .
Myhill Theorem. A language is regular if and only if the syntactic monoid is finite.
If we define another equivalence relation with
if and only if for every ,
may not be a monoid in general, but we have the following:
Myhill-Nerode Theorem. A language can be recognized by a finite automaton with states if and only if the relation has index ; that is, has classes.