New answers tagged reference-request
8
Let me first try to summarize what is known about the Greedy Conjecture.
Blum, Jiang, Li, Tromp, Yannakakis prove that the Greedy Algorithm gives a 4-approximation, and Kaplan and Shafrir show that it gives a 3.5-approximation for the Shortest Common Superstring problem.
A version of the greedy algorithm is known to give a 3-approximation (Blum, Jiang, Li, ...
6
Upon the suggestion of Louis Esperet, I contacted Philippe Gambette and Christophe Paul, who confirmed promptly. Paul designed this graph for his Habilitation thesis. When they created a Wikipedia page for modular decomposition, they used this graph. Maybe it's the beginning of its wide adaption. It's also featured in the well known survey of Michel Habib ...
12
Concerning Question 1, there have mainly been two lines of work to find tractable restrictions of SAT.
The first one that you are already familiar with is to restrict the types of the clauses that you are allowed to use. For example, in 2-SAT, you are only allowed to use size two clauses. In Horn-SAT, you only allow Horn clauses etc. The tractable ...
0
More on the obscure side: My second order heirarchy theorem for fixed point logics in finite model theory. See Yet Another Hierarchy Theorem.
2
This is usually a classical University textbook: Artificial Intelligence: a modern approach by Stuart Russel and Peter Norvig.
The book covers the problem of soft and hard AI, how to think about intelligent agents, the inference problem and a wide variety of techniques for both supervised and unsupervised learning. In my opinion it's the best book to dive ...
3
I suggest
Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal. Probability is at the foundation of machine learning and it's one of the weakest points for many beginners, in my experience.
1
In 2004 D. A. Turner argued in an easy to read article Total Functional Programming that non termination is a problem with interpreting languages like Haskell purely mathematically, but that to resolve it one needed to add codata types.
A pure functional language where no function was non-terminating (resolved to ⊥) would enable clear reasononing about the ...
7
Non-termination can be considered an algebraic effect up to a point. It's an exception that cannot be handled. More precisely, we may introduce a nullary operation (constant) $\bot$ which signifies non-termination, but then we disallow handling it, as that would allow us to implement the Halting oracle.
Such treatment of non-termination is a bit naive. A ...
2
You may be interested in this paper. It describes things in terms of monads, but the idea is that you define an 'effect' of making a recursive call. Then appropriately typed functions can be interpreted as recursive definitions. Note for instance on page two where he refers to the, "generic effect," which is something you'll see in work on algebraic effects. ...
Top 50 recent answers are included
