Tag Info

New answers tagged

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 ...


3

This is a very popular heuristic method in machine learning, known as alternating minimization. You can easily find tons of papers using it. Often the setting in which it is used is when $f(x,y)$ is convex in $x$ and $y$ separately (so each minimization step can be done via some variant of gradient descent), but not jointly convex. In this case, as RB notes, ...


1

heres a new notable paper linking evolution/genetics to the Multiplicative Weight Update algorithm, also just profiled by the Simons foundation & includes a coauthor cited in the question (Papadimitriou): Algorithms, games, and evolution Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani Even the most seasoned students of ...


3

If you are looking for a way to name (or alternately characterize) these edges you call "useless" and "necessary," you could refer to them as the edges with betweenness centrality =0 and =1, respectively. Every edge can be classified as having =0, =1 or in(0,1) betweenness measure in time of all-pairs-shortest-paths. This is a well-studied measure of ...



Top 50 recent answers are included