New answers tagged

5

$\beta(E_1)$ is the language $s^nx,s^{n+1}x$. This language is straightforwardly not regular, by the pumping lemma. If we assume that the language is regular, the pumping lemma tells us that there must exist some $p, q$ such that for all $n \ge p$, $s^{n+q}x,s^{n+1}x$ is also in the language. This is false, meaning that the language is not regular. A similar ...


26

There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems. In the $k$-Path problem where we are looking for a simple path of length $k$. Alon, Yuster and Zwick [1] showed that this problem can be solved in $2^{O(k)}\cdot n$ time on $n$-vertex graphs. A weighted version of $k$-Path has ...


4

Type inference for simply typed lambda calculus is complete for polynomial time, as elegantly explained in section 1 of Harry Mairson's Linear lambda calculus and PTIME-completeness. To be a bit more precise, here "type inference" is taken to mean the problem of computing the principal simple type of an untyped lambda term. This is strictly ...


2

In general, composing a threshold function with a function class can arbitrarily increase the Rademacher complexity (so the answer to your question is negative). Let $\Omega$ be a finite set, $|\Omega|=N$, and let $F=[-a,a]^\Omega$ be the set of all functions from $\Omega$ to $[-a,a]$. When $N\gg n$, the Rademacher complexity (either empirical or expected) ...


Top 50 recent answers are included