# Tag Info

5

"Foundations of Data Science" (pdf) by Hopcroft and Kannan. The text was discussed by Lipton on his blog. As the title implies, the emphasis of the text seems to be applications and issues related to Big Data and Learning problems. It seems to have grown out of this course.

1

There is also Elements of the Theory of Computation by H.Lewis and C.Papadimitriou. It's a well written introduction to automata theory.

2

I'm pretty sure you can find this in the book Bounded Queries in Recursion Theory by Martin and Gasarch, but I don't have access to a copy now to check. (Your statement gives an upper bound of $2^f$; most of that book is about lower bounding such quantities, so the upper bound must be in there somewhere, probably very near the beginning.) PS - I agree ...

1

The website of Computability and Complexity in Analysis Network has extensive bibliography. See their page for books. For computability, see Klaus Weihrauch, "Computable Analysis", 2010. It also has a chpater on complexity. See also PhD theses of Jens Blanc and Andrej Bauer. Another interesting paper is Viggo Stoltenberg-Hansen and John Tucker, ...

2

There are some good books - 1. Computable Analysis - Pour-El and Richards (an older reference) 2. Computable Analysis - Weihrauch There's also the Blum-Shub-Smale Model, which is the model explored in "Complexity and Real Computation". The complexity theory of computability of reals is explored in 1. Computational Complexity of real functions - ...

10

The time is essentially the same as that for sorting numbers in the range $1,\dots M$. Graham scan (in the version where the points are sorted by their x-coordinates (with ties broken by y coordinates) rather than the one the textbooks unaccountably use in which they are sorted radially) can find convex hulls in linear time after the sorting step. So for ...

3

Isn't the conjecture in the paper that the number of $(k+1)$-cliques in this case is at least $c^{k-1}$? That's the number you get by adding a single edge to the Turan-graph. I think it's proved in 1969-10. Also relevant: 1983-28. Recently, there has been significant progress on bounding the number of cliques as a function of the quadratic term of the number ...

0

I enjoy the following lecture notes by Jarkko Kari: http://users.utu.fi/jkari/automata/ Brief course outline: Regular languages Finite automata, regular expressions Kleene theorem Pumping lemma Closure properties and decision algorithms State minimization, Myhill-Nerode theorem Context-free languages Grammars, parsing Normal ...

0

Understanding Computation From Simple Machines to Impossible Programs It does cover a lot of stuff, which includes automata theory. The examples are presented in Ruby, and they are pretty easy to understand. You may need another book if you want to delve deeper into theory, but this one is great to learn the basics.

-2

Have a look at work by Holger Hoos

2

The problem is NP-complete. The reduction is from the Set cover problem. Let one user has all the files $F$. Then our only hope is to achieve $\mathcal{F}(G_2)= \mathcal{F}(G_1)$. So the question is, from given $2k-1$ sets, are there $k$ that cover the ground set? This easily reduces to the decision version of the Set cover problem after adding a few dummy ...

4

There are two new papers on graphs without cycle having exactly one chord. Both mainly deal with coloring these graphs: http://arxiv.org/abs/1309.2749 and http://arxiv.org/abs/1311.1928. The later also gives an $O(m^2n)$ recognition algorithm. But a faster one in time $O(mn)$ is already provided in the paper by Trotignon and Vuskovic (cited in answer by ...

2

There's no agreed upon "bible" for CT for computer science in the same way as for mathematicians (Mac Lane), probably because the field is younger and a bit broader. It really depends on whether you want to understand . Here are a few computer science concepts with category theory counterparts: Simple types (which correspond to Cartesian Closed Categories) ...

14

I think there are lot of similar problems. Here are two in vertex version and one in edge version: 1) Does a given graph have an independent feedback vertex set? (we don't care about the size of the set). This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in Garey, Johnson & Stockmeyer. 2) Does a given graph have a ...

2

Another example is the efficient dominating set problem also known as 1-perfect code in graphs. The problem is to determine the existence of a dominating set $C$ in undirected graph such that the shortest path between any two nodes in the dominating set $C$ is at least 3 (edges). The problem was proven to be $NP$-complete independently by many researchers. ...

1

An $NP$-complete structural problem is to decide the existence of odd (even) hole in directed graphs. Anna Lubiw proved the $NP$-completeness of the above two problems. A hole is chordless cycle of length greater than three. A cycle in directed graph is chordless if its length is greater than 3 and no two of its vertices are joined by an edge of the ...

5

I think the answer to your first question is also $\widetilde O(n^3 \log( \|A\| + \|b\|))$ due to the following arguments: Edmonds' paper does not describe a variant of Gaussian elimination but it proves that any number computed in a step of the algorithm is a determinant of some submatrix of A. By Schrijver's book on Theory of Linear and Integer Programming ...

0

I am not an expert on this at all, but I would like to get a constructive discussion started. Here is an attempt, based on the math.stackexchange.com question Count the number of positive solutions for a linear diophantine equation. The stuff is related to Erhart polynomials, which I know nothing about, and I think also to @SashoNikolov's comments above. ...

-4

a very challenging/advanced/provocative question; following, a brief/sketchy/tentative answer [maybe/hopefully better than none] considering geometry in QM computing in general & a few refs/leads. geometry is used in a variety of ways in QM in general, and it appears to be somewhat of an open question and challenging work-in-progress how to determine a ...

Top 50 recent answers are included