# Tag Info

2

Note that in optimization, "convergence rate" usually means asymptotic behavior. That is, the rate only applies to the neighborhood of optimal solutions. In that sense, Luo & Tseng did prove linear convergence rates for some non-strongly convex objective functions in the paper "On the convergence of the coordinate descent method for convex differentiable ...

4

Rather than computing the VC dimension of a particular function class, it's usually more interesting to understand how generic properties of a function class relate to its VC dimension. For example, function spaces with linear dimension $d$ have VC-dim at most $d$. You can also bound the VC-dim of a function class realized by circuits with bounded ...

3

Here is a copy of the 1965 paper by Moon and Moser: http://users.monash.edu.au/~davidwo/MoonMoser65.pdf Note that the result was actually first proved in 1960 by Miller and Muller: http://users.monash.edu.au/~davidwo/MillerMuller-NumberMaximalCliques.pdf

6

There are lots of overlaps between small world and scale-free, but I think much less so between those two and expanders. The terms "small world" and "scale-free" are often used informally, but formal definitions are often along the lines of: Small-world means short average (or maximum) path length (typically $O(\log n)$, with $n$ vertices) and highly ...

7

The massive tome of Burgisser-Clausen-Shokrollahi is the standard reference for algebraic complexity theory (and I'm not really sure there are others from the complexity point of view, though there are definitely others about algebraic algorithms), but doesn't do much of PIT. The surveys of Chen-Kayal-Wigderson (freely available from Wigderon's webpage) ...

0

" Formal Languages And Automata Theory " by A.A. Puntambekar is the best book for solved examples. Most of the book contains only solved examples and little theory. Its good to pass the exams.

6

A proof that uses closure properties: DCF languages are not closed under union, so take, $L_1, L_2 \in DCF$ s.t. $L = L_1 \cup L_2 \notin DCF$ Add three new symbols $\{\alpha, \beta, \#\}$ to the original alphabet $\Sigma$ and build the languages: $L'_1 = \{ \alpha \# w \mid w \in L_1\}$ $L'_2 = \{ \beta \# w \mid w \in L_1\}$ We have $L'_1, L'_2$, but ...

2

Consider $Outf(\{a^n b x b c^n\} \cup \{a^n b y b c^{2n}\}) \cap a^{\ast} b b c^{\ast}$ over alphabet $\{a,b,c,x,y\}$.

5

Every context free language over a one letter alphabet (or equivalently every langauge recognized by unary PDAs, unary DPDAs or 1 counter machines) is regular. See: S. Ginsburg, H. Rice: "Two families of languages related to ALGOL", Journal of the ACM, 9: 350–371, 1962. For what regards PDAs with bounded stack reversals they are equivalent to bounded ...

Top 50 recent answers are included