Why is "topological sorting" topological? Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why is it not called "dependency sort" or something else? Why "topological"? I admit I'm mystified.

The earliest reference I could find for topological sort is from [Lasser61]:

  A network of directed line segments free of circular elements is assumed. The lines are identified by their terminal nodes and the nodes are assumed to be numbered by a non-topological system. Given a list of these lines in numeric order, a simple technique can be used to create at high speed a list in topological order.

I don't have access to this article right now but I would wager that the "topology" in "topological sort" does not come from the mathematical notion of topology (e.g.: open sets, compactness, etc...) but rather from the "network topology" sense.

[Lasser61] Lasser, Daniel J. "Topological ordering of a list of randomly-numbered elements of a network." Communications of the ACM 4, no. 4 (1961): 167-168.


Confusing running time analysis for the Divide & Conquer algorithm of Hamiltonian Path problem In the Hamiltonian Path problem we are given a graph $G=(V,E)$ and two distinct vertices $\{s,t\}$ and we ask if there is a path from $s$ to $t$ which traverses all other vertices exactly once. Clearly, the brute-force algorithm enumerates all possible vertex orderings and runs in $O(n!)$.

There is a elegant D&C (divide & conquer) style algorithm in Gurevich1987 which is stated to run in $O(2^{2n}\times2^{O(l)})$ with $l=\log_2 n$. But after checking several times the proof and performing an analysis in a different way, I would believe that the correct running time is rather $O(2^{2n}\times n^{O(l)})$. Interestingly, in that paper, this expression also appeared once, perhaps it's a typo, but it makes things really confusing for me.

In the following, I first provide some pointers then put the main idea of D&C and my own analysis.

The paper: expected computation time for hamiltonian path problem
The algorithm is called HPA3 on page 499 and 500.
P499, 3rd line from the bottom: ...run-time...$2^{2n}$ times a polynomial in $n$
P500, point (b), $T(n)=2^{2n}\times n^{O(l)}$ (which is a contradiction)
P500, ...choose a $c$ such that $T(n)=2^{2n+cl}$....

Main idea of D&C
Very simple, guess the middle vertex (note $m$) in the path $(s,t)$, then try all possible subset $A\subset V$, $|A|=(n-3)/2$, assuming the the path is somehow like $s,A,m,(V-A),t$. This divides the input instance into two half-size instances, and it yields a recurrence relation: $T(n)\leq (n-2)2^{n-3}T((n-3)/2)$, with $b$ some unknown constant.

My analysis
To be simpler, note $n$ as the number of vertices except $\{s,t\}$. Then $T(n)\leq n2^nT(n/2)\\ = 2^{n(1+1/2+1/4...1/n)}\times (n*n/2*n/4*...*1)\\
\leq 2^{2n}\times n^{\log n} \ (2^{1+2+...+\log n}) \\
= 2^{2n}\times n^{(\log n)/2}$

The author uses induction to prove, but for me it's wrong. Could anyone make a judgement?

[edit 07/19]: I realized that asymptotically $n^{\log n}<2^n$ but the lhs is greater than a polynomial in $n$ anyway no?

[edit 07/20]:as the comments and answers stated, we can basically conclude that there exists some issue in that paper and the correct complexity is $O(4^nn^{log n})$. However this can be also viewed as "$O((4\times\epsilon)^n)$ for any $\epsilon>1$", so let's say the complexity is infinitely close to $4^n$ from above.

P.S. for any constant positive $c>1$, $n^{\log n}=c^{(\log_c n)\log n}\leq \max(c^{\log^2 n},c^{\log_c^2 n})<c^n$ (asymptotically)

Just a note: the $n^{\log n}$ factor can be replaced by a polynomial, without much trouble. Here's one way to do it, not at all optimized...

Imagine there is a global graph $G$ with vertex set $[n]$, and a current induced subgraph $G' = (V',E')$ of $G$, with $n'=|V'|$. Instead of guessing the middle vertex along with each of the ${n' \choose \lfloor n'/2\rfloor}$ subset choices for $S \subseteq V'$, one can recurse only on the choice of $S$. Assume the recursive calls return $n \times n$ matrices $A_S$ and $A_{V'-S}$ such that:

 $A_S[i,j]$ equals the minimum cost of a Hamiltonian tour that starts with some vertex $i \in V$ (not necessarily in $S$), traverses only through vertices in $S$, then ends with some vertex $j \in V$ (not necessarily in $S$).  $A_{V'-S}[i,j]$ is defined similarly.

The algorithm should then return the $n\times n$ matrix $A_{G'}$, where for all $i,j=1,\ldots,n$, $A_{G'}[i,j] = \min_{S \subseteq V'} \min_{k\in V'} (A_S[i,k]+ A_{V'-S}[k,j])$.  Note that we do not have to store all these matrices; we could for example maintain $O(1)$ matrices per recursion layer (and the recursion depth is $O(n)$). After we compute the matrix product $A'[i,j] = \min_k (A_S[i,k]+ A_{V'-S}[k,j])$, we can simply take the MIN of $A'[i,j]$ with the current $A_{G'}[i,j]$ over all $i,j$, then erase $A_S$ and $A_{V'-S}$ before going to the next subset $S$. Thus the space usage is $poly(n)$.

Now the time recurrence is $T(n',n) = {n' \choose \lfloor n'/2\rfloor} \cdot (T(\lfloor n'/2\rfloor,n) + T(\lceil n'/2\rceil,n) + poly(n))$ for all $n' \leq n$ and $T(1,n) = poly(n)$, which yields $T(n',n) \leq 4^{n'} \cdot n^k$ for some $k \geq 1$. To verify this, note that the RHS of the recurrence is upper bounded by

$2^{n'+1} T(n'/2,n) + 2^{n'} \cdot poly(n) \leq 2^{n'+1} \cdot (4^{n'/2} (n/2)^k) + 2^{n'} n^k$
$= 2 \cdot 4^{n'} (n/2)^k + 2^{n'} n^k
\leq 4^{n'} n^k/2^{k-1} + 2^{n'} n^k$,

which is $\leq 4^{n'} n^k$ for $k \geq 3$ (for example).


What is the Complexity Status of Arbitarily Weighted Planar Max Cut? If you search on the internet for the Complexity Status of Arbitarily Weighted Planar Max Cut you seem to get conflicting answers.

On one hand, there are references that Barahona solved this problem in the 1980's.

On the other there is this paper:
NP-completeness of maximum-cut and cycle-covering problems for planar graphs
http://www.springerlink.com/content/xj7238374871347j/

My question is what is the Complexity Status of Arbitarily Weighted Planar Max Cut?

After reading the paper you mentioned, it seems that the reduction stated in the paper is incomplete, therefore the result may not be correct.

In the paper the author gave a reduction from 3SAT to a problem called planar max-cycle-covering (although it is not consistent with the usual sense of a covering in graph theory, it is more like max-edge-disjoint-cycles problem), and proving that the max-cycle-covering problem and max-cut problem are dual to each other on planar graphs. While the second implication is correct, the reduction part mimics a proof to the NP-hardness of planar Hamiltonian cycle problem, and there may be a flaw in it.

In that proof one need a gadget for XOR-in-series (See Fig. 3 in the Hamiltonian paper); although the construction works in the Hamiltonian ones, I see no evidence that a similar construction is possible for cycle-covering, and there are no explanations in the paper. (And we need such a gadget in the NP-hardness proof of cycle-covering, see Fig. 6 in the max-cut paper.) The main problem is that for Hamiltonian cycle we can always be sure that the middle edge C must be passed though, hence we can "transfer" the XOR by the presence of the middle edge; but in cycle-covering we cannot guarantee that edge C must be passed though unless it is within a cycle passing though a heavy-weighted edge, and this is not the case here. (In fact we cannot enforce the edge being passed though, since in Fig. 6 if an edge C is passed though then the corresponding literal in the clause is true.)

My guessing is that planar max-cycle-covering cannot simulate 3-fan-in OR function, which is required in 3SAT. Supported with the answer by @turkistany, one should believe that planar max-cut problem is polynomial time solvable.


When polynomial GI implies polynomial (edge) colored GI? Crossposted from MO.

(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).

There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge colored GI the simplest
is to replace colored edge by a GI preserving gadget encoding
the color (subdividing edge enough times is the simplest case).
For vertex colored GI, attach some gadget to a vertex.

Suppose GI is polynomial for some graph class $C$.

  Q1 For which $C$ polynomial GI implies polynomial
  (edge) colored GI?

Using a reduction with gadgets might make the graphs
not members of $C$.

On the other hand certain gadgets/transformations
might make the graphs members of some other polynomial
GI class.

Example of edge colored reduction $ G \to G'$.

Make a clique of $V(G)$. Color edges in $E(G)$ with $1$
and non-edges with $0$.  It is the coloring function
that preserves $G$ and to recover $G$ from $G'$ just
take the edges colored $1$. $G'$ is clique, cograph,
permutation graph and almost sure in many other nice
classes. Subdividing the edges odd number of times
(distinct for $0,1$ removes the colors and makes $G'$
perfect bipartite graph, preserving isomorphism).

Maybe another approach is to take the line graph
of $G'$ and add pendant (universal) vertices connected
to vertices corresponding to $E(G')$.

  Q2 Are there nice gadgets/transformations for similar
  constructions?

Thought about planarizing $G'$ by choosing some
universal drawing of the clique and replacing
edge crossing by planar gadgets preserving colors
say $C_4,C_6$ for equal colors and something else
for distinct colors. Don't know if this preserves
isomorphism.

Another possible approach might be automorphism
preserving coloring or subdivide every edge of
$K_n$, use 3 colors ${0,1,2}$ for vertices $V(G),E(G),E(\overline{G})$
and try to recognize self complementary graphs by
automorphism exchanging $E(G)$ and $E(\overline{G})$.

  Q3 Is the automorphism group of the subdivision of $K_n$
  tractable to compute?

The orders after the few initial terms are $12 , 24 , 120 , 720 , 5040 , 40320 , 362880$
which is A052565

Dima suggests this might be easy for $n$ large enough and the initial
terms are exceptions.

  Q4 Given vertex colored subdivision of $K_n$ for $n > 4$ and its automorphism group
  where the high degree vertices are colored $0$, some degree $2$
  are $1$ and the other are $2$, what is the complexity to find
  automorphism exchanging $1$ and $2$?

Added The paper On Recognizing Cayley Graphs p 86 claims:

  Given a class C of Cayley graphs, and given an edge-colored
  graph G of n vertices and m edges, we are interested in the problem of
  checking whether there exists an isomorphism φ preserving the colors
  such that G is isomorphic by φ to a graph in C colored by the elements
  of its generating set. In this paper, we give an O(m log n)-time algorithm
  to check whether G is color-isomorphic to a Cayley graph.

This appears close to the question, is it relevant?

Q2: a nice example is the graph labeling gadget used to prove that:

Theorem: Planar 3-connected colored GI $\leq_T^L$ planar 3-connected GI

See Thomas Thierauf, Fabian Wagner: The Isomorphism Problem for Planar 3-Connected Graphs Is in Unambiguous Logspace. Theory Comput. Syst. 47(3): 655-673 (2010)

The "labeling gadget" used preserves the 3-connectedness and planarity constraints.


Why isn't it possible to recover/resume after an Exception? I know that Exceptions as a means of flow-control is generally frowned upon.

But in my opinion, Exceptions have little value short of the flow-control aspect - after all, if you didn't want the program to continue, you could just output an error-message an terminate the program.

Exceptions, on the other hand, provide a means of reporting errors "locally", allowing a service/component to fail, and a consumer to handle the failure - and regardless of how you look at that, it is a means of controlling the flow of the program.

So here's my question - over the years, I have frequently wondered, why isn't it possible to resume execution after an exception is thrown?

Now, you wouldn't want to allow any consumer to resume after an Exception thrown by any other component, as that component was probably not designed to resume after a throw-statement, which would lead to unpredictable results.

So let's say there's a supertype of Exception called Interrupt, that allows this behavior. An Interrupt would behave just like an Exception in every respect, except that by throwing an Interrupt, you indicate that the component is ready and able to resume execution after the throw-statement, and that the stack needs to be preserved either until (A) the Interrupt has been handled, or (B) the program exits with an error-message.

Let's say we add a new "resume" statement to the language, to be used inside a traditional "catch" block - if you catch an Interrupt, and issue a "resume" statement, control would return to the point from where the Interrupt was originally thrown, and execution would continue from the next statement.

I've presented this idea in other circles, and I'm met with a lot of resistance, but no clear argument as to why this is not a good idea.

To me, it seems like a natural extension of the idea of exceptions - there are plenty of cases where this could be useful, for example while enumerating a sequence, e.g. in a function that "yields" one result at a time; an unexpected condition could occur while producing one of these results, and you may want the calling code to decide whether or not it makes sense to continue producing more results.

An exception does not allow for that.

Let's say this function throws an interrupt instead - if so, the calling code now has a chance to look at that and decide whether to resume execution (as if the exception never occurred) and produce more results, perhaps log the condition and then resume, or perhaps throw an exception, or perhaps re-throw the interrupt in case it can be handled up-stream.

I'm sure I'm not the first person to have this idea, but I would like to understand why this isn't feasible or why it's not a good idea.

(PS: I'm a programmer, not a scientist, so go easy on me.)

"Resumable exceptions" are indeed a well-known idea in some programming language circles. In particular, Common Lisp has had resumable exceptions for a long time (so they are really not confined to research language; Common Lisp could be considered "mainstream", it has been widely available and relatively widely used for a long time).

For a discussion of resumable (or "restartable") exceptions, see for example this blog post by Manuel Simoni, which links to this dylan mailing-list post by Chris Double and the following Lambda-the-Ultimate discussion: Common Lisp exception handling.

You made the insightful guess, that resumable exceptions are not a good idea in all contexts. They can make resource handling harder and more generally anything related to side-effects must be considered very carefully when you add new control-flow entry points to a block of code.

It is possible for the exception raising code to decide on whether it should be resumable or not. This is natural if you see resumable exceptions as a combination of usual exceptions and continuations: you raise an exception and, in the attached data, decide whether or not to include a continuation to the rest of the computation; the handler then decide whether or not to invoke that continuation, that is "resume" the exception.

Effect handlers (try..catch block, using-like resource handler assuming lexical lifetime) can get confused if you re-enter the computation. Combining handlers and rich control flow is difficult and gave way to a lot of different approaches in the Lisp/Scheme communities (keywords: dynamic-wind, unwind-protect). You are certainly adding non-trivial complexity to the language.

I speak of "effect handlers" because, once you have such rich forms of control flow, you get very close to the ability of presenting arbitrary effects (exceptions, backtracking, but also logging, mutable state and input/output) on top of it. See for example Andrej Bauer and Matija Pretnar's work on Eff a language based on such "effect handlers".


Cryptographic systems that don't leak linear combinations of encrypted bits Various encryption schemes would be considered broken if an adversary could have a non-negligible edge in predicting the first (or any) bit of an encrypted message.  I am looking for a slightly stronger guarantee.

In particular, does any cryptographic system or crypto assumption (that relies on keys, not a one time pad) guarantee that any linear combination of the encrypted bits cannot be predicted after an adversary sees only a polynomial number of messages (possibly of his choosing)?

Note -- I am not at all an expert in cryptography, and this may be considered trivial.

Yes, if the encryption algorithm achieves IND-CPA security (semantic security), this implies that an adversary cannot predict any linear combination of encrypted bits better than random guessing.

The easiest way to see this is to note that IND-CPA (left-or-right indistinguishability) implies real-or-random indistinguishability under chosen-plaintext attack: an attacker cannot distinguish the encryption of messages $M_1,\dots,M_n$ (chosen by the attacker) from the encryption of random strings $R_1,\dots,R_n$ (chosen randomly and not revealed to the attacker).  This fact is proven in Bellare & Rogaway's lecture notes, or is easy to derive yourself via a hybrid argument.

Now your result follows.  Let $\ell$ be any linear function of the message.  Then it follows that no attacker can predict $\ell(M_i)$ better than random guessing.  Why?  $\ell(R_i)$ is a random bit.  So, if knowledge of $E_k(M_i)$ lets you distinguish $\ell(M_i)$ from random (i.e., distinguish $\ell(M_i)$ from $\ell(R_i)$), then it would also let you distinguish $E_k(M_i)$ from $E_k(R_i)$, which would violate semantic security.


Testing low degree bivariate polynomials Let $d,q \in \mathbb{N}$, and let $f:\mathrm{GF}(q) \to \mathrm{GF}(q)$ be a univariate polynomial. In this case, it is possible to test whether $f$ is of degree at most $d$ (or whether $f$ is at least $\epsilon$ from it) using the algorithm of (RS96). The testing algorithm works by simply trying to interpolate the function $f$ on $\Theta(1/\epsilon)$ collections of $d + 2$ uniformly selected points, and checking whether the resulting functions are all polynomial of degree at most $d$.

Is there an extension of this result that allows to test whether a bivariate polynomial $g:\mathrm{GF}(q)^2 \to \mathrm{GF}(q)$ is of degree at most $d$ in the first variable, using $O(\epsilon^{-1} \cdot d)$ queries?

If you only care about the first variable, then I believe the following simple test should work: pick a random value $\beta \in \rm{GF}(q)$ and check that $f(\cdot, \beta)$ is a univariate polynomial of degree at most $d$ - say, by choosing few collections of $d+2$ points of the form $(\cdot,\beta)$ and interpolating them.

The analysis of this test should be trivial: If the function is far from being of degree $d$ in the first variable, it must be far from a univariate polynomial of degree $\le d$ for many values of $\beta$.

If you wish to test that $f$ is of degree $\le d$ in both variables, you can use the (highly non-trivial) result of Polischuk and Spielman from 1994, which is proved in Sections 2-5 in the following paper (see Theorem 9):
http://cs-www.cs.yale.edu/homes/spielman/Research/holographic.html


Representing bound variables with a function from uses to binders The problem of representing bound variables in syntax, and in particular that of capture-avoiding substitution, is well-known and has a number of solutions: named variables with alpha-equivalence, de Bruijn indices, locally namelessness, nominal sets, etc.

But there seems to be another fairly obvious approach, which I have nevertheless not seen used anywhere.  Namely, in the basic syntax we have only one "variable" term, written say $\bullet$, and then separately we give a function that maps each variable to a binder in whose scope it lies.  So a $\lambda$-term like

$$ \lambda x. (\lambda y. x y)$$

would be written $\lambda. (\lambda. \bullet\bullet)$, and the function would map the first $\bullet$ to the first $\lambda$ and the second $\bullet$ to the second $\lambda$.  So it's kind of like de Bruijn indices, only instead of having to "count $\lambda$s" as you back out of the term to find the corresponding binder, you just evaluate a function.  (If representing this as a data structure in an implementation, I would think of equipping each variable-term object with a simple pointer/reference to the corresponding binder-term object.)

Obviously this is not sensible for writing syntax on a page for humans to read, but then neither are de Bruijn indices.  It seems to me that it makes perfect sense mathematically, and in particular it makes capture-avoiding substitution very easy: just drop in the term you are substituting and take the union of the binding functions.  It's true that it doesn't have a notion of "free variable", but then (again) neither do de Bruijn indices really; in either case a term containing free variables is represented a term with a list of "context" binders in front.

Am I missing something and there is some reason this representation doesn't work?  Are there problems that make it so much worse than the others that it's not worth considering?  (The only problem I can think of right now is that the set of terms (together with their binding functions) is not inductively defined, but that doesn't seem insurmountable.)  Or are there actually places where it has been used?

Andrej's and Łukasz's answers make good points, but I wanted to add additional comments.

To echo what Damiano said, this way of representing binding using pointers is the one suggested by proof-nets, but the earliest place where I saw it for lambda terms was in an old essay by Knuth:

Donald Knuth (1970). Examples of formal semantics. In Symposium on Semantics of Algorithmic Languages, E. Engeler (ed.), Lecture Notes in Mathematics 188, Springer.

On page 234, he drew the following diagram (which he called an "information structure") representing the term $(\lambda y.\lambda z.yz)x$:

This kind of graphical representation of lambda terms was also studied independently (and more deeply) in two theses in the early 1970s, both by Christopher Wadsworth (1971, Semantics and Pragmatics of the Lambda-Calculus) and by Richard Statman (1974, Structural Complexity of Proofs). Nowadays, such diagrams are often referred to as "λ-graphs" (see for example this paper).

Observe that the term in Knuth's diagram is linear, in the sense that every free or bound variable occurs exactly once -- as others have mentioned, there are non-trivial issues and choices to be made in trying to extend this kind of representation to non-linear terms.

On the other hand, for linear terms I think it's great! Linearity precludes the need for copying, and so you get both $\alpha$-equivalence and substitution "for free". These are the same advantages as HOAS, and I actually agree with Rodolphe Lepigre that there is a connection (if not exactly an equivalence) between the two forms of representation: there is a sense in which these graphical structures may be naturally interpreted as string diagrams, representing endomorphisms of a reflexive object in a compact closed bicategory (I gave a brief explanation of that here).


Are all computational models of quantum computing equivalent? So the question was inspired by a seminar which presented the following models of quantum computing:

Quantum Computing with Photons
Quantum Computing with Rydberg atoms
Quantum Computing with trapped ions
Quantum Computing with Josephson Junction

Are these computational models completely equivalent to one another i.e the complexity of every problem is equivalent in all these models ?
I am asking here because the answers I got from Physicists were not very rigorous (I am a Physicist).

Now you've clarified your question, I can answer it. Assuming that the seminar was talking about universal quantum computational models (and there are universal computational models for all of these physical systems), then anything in BQP (quantum polynomial time w/ randomness) for one of these models is in BQP for all of these models. They might differ by smaller factors (e.g., since only nearby Josephson junctions can talk to each other, you might have to multiply run times by the diameter of the chip — but it won't be worse than that, and for many problems you can do much better).
There are non-universal models being considered for Rydberg atoms and for photons. The non-universal Rydberg atom models would be very good for simulating certain physical systems. This has been called analog quantum computation; you make the Rydberg atoms interact with the same dynamics as the system you're trying to simulate. Then even though you can't address Rydberg atoms individually, they still behave the same way as an interesting physical system, maybe even one that doesn't quite exist in nature. Systems like this may actually yield the first scientifically interesting results of quantum computation.
For photons, it's very hard to get two photons to interact, which means that there are proposals for building quantum computers that use photons to demonstrate quantum supremacy (i.e., that you can use quantum mechanics to solve a problem that a classical computer can't) without actually being able to use them for a universal quantum computer. It's not clear to me that these proposals will actually work in real life, because as far as I am aware, these proposals have only been proved to work in the case where the noise levels are very low (i.e., the optical components and photodetectors work almost perfectly). There are also proposals for universal quantum computation that use non-interacting photons, but these also have the problem that you need extremely good (but still finite) accuracy for all the optical components and photodetectors in your computer. You can't make universal quantum computation with linear optics,  but you can do it with single photon sources, linear quantum gates, and photodetectors — photodetectors and single photon sources aren't linear in this sense.


Simple balanced trees with O(1) concat? In Purely Functional Worst Case Constant Time Catenable Sorted Lists, Brodal et al. present purely functional balanced trees with O(1) concatenate and O(lg n) insert, delete, and find. The data structure is somewhat complicated.

Is there a simpler balanced search tree with O(1) concatenate, functional or not?

You can trivially make a data structure with O(1) amortized concatenation time, by just reinserting everything from one tree on the other on concatenation (which has O(n log n) cost, exactly the same as was used in constructing that tree in the first place, so the overall time is still O(n log n)), but this is cheating.

For worst-case O(1) time, the authors claim it was an open problem for any data structure, so I don't think you're going to find an easy answer.


Partition graph into 2 or more claw-free subgraphs Is it NP-hard to partition the vertex set of graph G into k subsets so that they induce k claw-free subgraphs of G?

It is NP-hard, even for $k=2$.

This is a special case of a theorem by Farrugia (Alastair Farrugia, Vertex-partitioning into fixed additive
induced-hereditary properties is NP-hard, The electronic journal of combinatorics 11 (2004), #R46),
stating that it is NP-complete to test if the vertex set a graph can be partitioned into two subsets
A and B such that G(A) belongs to the graph class P and G(B) belongs to the graph class Q, provided
P and Q are closed under taking vertex-disjoint unions and talking induced subgraphs, and at least
one of P and Q is non-trivial (meaning not all graphs in the class are edgeless).


A maximization problem containing summation and multiplication Are the following two problems NP-hard?

Problem 1

Given $n$ ordered pairs of integers $S=\{(a_i,b_i)\}$, $1\leq i \leq n$, and an integer $k$.

Find a subset $A$ of $S$ with $k$ elements, such that $\sum_{(a,b) \in A}a+\prod_{(a,b) \in A}b$ is maximized.

Problem 2

Given $n$ ordered pairs of real numbers $S=\{(a_i,b_i)| 0 \leq a_i \leq 1, 1 - a_i \leq b_i \leq 1\}$, $1\leq i \leq n$, and an integer $k$.

Find a subset $A$ of $S$ with $k$ elements, such that $\sum_{(a,b) \in A}a-\prod_{(a,b) \in A} b$ is maximized.

Or, equivalently:

Given $n$ ordered pairs of real numbers $S=\{(a_i,c_i)| 0 \leq a_i, c_i, \leq 1\}$, $1\leq i \leq n$, and an integer $k$, find a subset $A$ of $S$ with $k$ elements, such that $\sum_{(a,c) \in A}a-\prod_{(a,c) \in A}(1-ac)$ is maximized.

The objectives can be taken as set functions defined on $2^S$. The objective of the second problem is submodular.

Any hint, reference to a book, a paper or related problems is appreciated.
I have tried finding a reduction from knapsack and set cover, but no luck so far.

I think both of your problems are in P.  Here's an algorithm that works in P without any restriction on the $(a_i,b_i)$ pairs.

Formulate your problem as the problem of choosing $x\in\{0,1\}^n$ subject to $\sum_i x_i = k$ so as to maximize
$$\textstyle f(x) = \pi(x) + \sum_i x_i a_i$$
where $\pi(x)=\prod_i \exp( x_i \beta_i)$ and $\beta_i = \ln b_i$.  Relax the problem to allow $x\in[0,1]^n$.

For intuition, note that the function $f(x)$ is convex, so it is maximized over $x\in[0,1]^n$ at some $x\in\{0,1\}^n$. (To see the latter, note that any $x\in [0,1]^n$ with $\sum_i x_i = k$ is the weighted average of integer points $x'$ in $\{0,1\}^n$ with $\sum_i x'_i = k$, and $f(x)$ is at most the corresponding weighted average of $f(x')$ over those integer points, so one of those integer points $x'$ has $f(x') \ge f(x)$.)

Anyhow, find an optimal integer solution $x$ in polynomial time as follows.
The first derivative of $f$ with respect to $x_i$ is
$$\textstyle a_i + b_i\, \pi(x),$$
so (given the constraint $\sum_i x_i = k$), there exists $\lambda$ such that for the optimal $x\in[0,1]^n$,
$$x_i = \begin{cases}
0 & \text{ if } a_i + b_i \pi(x) < \lambda \\
1 & \text{ if } a_i + b_i \pi(x) > \lambda \\
? & \text{ if } a_i + b_i \pi(x) = \lambda.
\end{cases}$$

Furthermore, WLOG there are at most two indices $i$ that are undetermined by the above condition (because otherwise three pairs $(a_i,b_i)$ lie on a single line, a condition that can be broken by an insignificant perturbation of the input).

Given any $x$ and two such indices $i$ and $j$, consider the neighboring points $x'$ and $x''$ obtained by raising $x_i$ to $1$ and lowering $x_j$ to 0, or vice versa.  Since $f$ is convex, one of these points is as good as $x$, that is, $\max\{f(x'),f(x'')\} \ge f(x)$.

Finally, to find the best $S$ in polynomial time, determine the $n\choose 2$ breakpoints $\pi$ such that $a_i + b_i\pi = a_j  + b_j \pi$ for some $i$ and $j\ne i$.  For each such $\pi$, order the indices $i$ by $a_i + b_i \pi$, and take $S$ to contain the first $k$ indices in the order (if there is a tie for the $k$th, there are at most two indices that are tied; try both, giving two sets $S$ for that $\pi$).  Take whichever of these at most $2{n\choose 2}$ sets $S$ gives the largest $f(S)$.


How difficult is it to work on mathematics problems as a computer science graduate student? I am interested in problems typically tackled in theoretical computer science departments as well as seperate problems found in mathematics departments. Both would be more proof based. Is it easy to move from one to the other?

Example: Say I would like to work on proofs under the theory of computation (on the CS side) as well as geometric and topological proofs coming from problems in particle theory (maybe more on the mathematical physics side). Should I be in TCS or a math department, or would I be free enough to move around? Might I have more room to move in a mathematics department versus a TCS department?

It's very common to move from maths to CS: for example, in my office of four people in CS, one is doing a PhD in CS after doing an undergraduate maths degree and another is a postdoc who just finished a PhD in maths. Moving from CS to maths seems much less common.

When you say "graduate student" it's unclear whether you mean master's or PhD. It sounds like you're interested in lots of areas of mathematics (you've mentioned geometry, topology, quantum mechanics and string theory in this and your other question), which doesn't seem focused enough for a PhD: for that, you need to pick one, fairly narrow area.  From what little I know about you, it seems that a master's in maths would be more appropriate, perhaps followed by a PhD in either maths or computer science if you find a particular subject whose computational aspects interest you.


Are there perceptrons that maximize the average margin, rather than the minimum? A perceptron is a linear classifier.    The standard method for training a perceptron involves maximizing the minimum margin.  That is, we are trying to find:

$x^* = \text{argmax}_{x\in \text{unit vectors}} \min_{i \in 1..n} A_i x $

where $x$ is a normal vector to the separating hyperplane, $A$ is the $n\times d$ matrix of input values, $n$ is the number of input data points, $d$ is their diminsion, and $A_i x$ is the dot product between $x$ and the $i$th data point.

My question is: has there been any work on perceptrons whose hyperplane maximizes the average margin?  That is,

$x'^* = \text{argmax}_{x\in \text{unit vectors}} \sum_{i \in 1..n} A_i x $

This is a much easier quantity to calculate because it does not require gradient descent.  The problem is that it is not guaranteed to find separating hyperplanes even when they do exist---the points with low margin aren't given enough weight to do this.

This is what a soft-margin SVM is already doing, except that the average has a min on the inside: $\sum_i min(h,d(x_i,c_i,w))$ where $d(x_i,c_i,w)$ is the distance of the point $x_i$ from the classification hyperplane, signed with a positive sign if it is on the correct side as determined by the target $c_i$, and $h$ is the maximum distance on the correct side you're willing to give "credit" for.  If you set $h$ to a large enough value, this is what you have above.  And, this is precisely a soft-margin linear SVM.


Find the best path between two strings I don't know if CS theory is the best place for this, sorry if it's not.

I'm not a computer scientist so I don't know complex maths, but I have a theoretical problem in an application I'm working on that I can't wrap my head around. I would appreciate any help.

I need to find the best or correct string to fit between two other strings.

Given the strings strA and strB the function should analyse a database and return a string that looks like:

strA strC strD strE strB The number of strings in between can vary in number.

I have a database in place that looks something like this:

strA strC
strA strD
strA strB

strB strA
strB strC

strC strA

This basically says that in the final string strC can come after strB but strD cannot come after strB.

I also have a secondary database which describes which strings can come before which strings. So for example...

strA strC
strA strD
strA strB

strB strA
strB strC

strC strA

But this database states that strC can come before strB, but not strD.

I have a function which, only given the beginning string can find all the strings which would fit after it in the correct order. But I need to also include an ending string and have it find the correct path between the start and finish.

I've thought about it over and over again and I don't even know where to start with this. I hope my explanation is not too convoluted. I would greatly appreciate any ideas.

This is technically not in scope for this site, but we're friendly people here :), and your question is relatively well-formed.

It sounds like what you have is a directed graph where the strings are your vertices, and your two tables are storing the "forward edges" (a -> b) and the backward edges (a <- b). The question you're asking is whether there's a way to go from one vertex in this graph to another.

The answer is to do a graph traversal (breadth-first or depth-first) on this graph. Any basic textbook on algorithms (like this one) should help.


Pattern matching with don't cares: multiple patterns Kalai's 2-page SODA paper gives a simple and efficient algorithm for pattern matching with don't cares (wildcards that match one character). In essence, it is as easy as convolution.

But what happens if we are searching for multiple patterns with don't cares? Can we still somehow solve it with e.g. FFT-based techniques?

For the multiple pattern case, it seems that simply scanning for each of the might be the best possible solution, at least unless the strong exponential-time hypothesis fails.

Recall that given sets $S_1, S_2, \dotsc, S_n$ and $T_1, T_2, \dotsc, T_n$ over universe $[m]$, if we could decide if there are $S_i$ and $T_j$ such that $S_i \cup T_j = [m]$ in time $O(n^{2-\varepsilon}\operatorname{poly}(m))$, then SETH fails, i.e. we have a CNF-SAT algorithm with running time $O^*\bigl(2^{(1-\varepsilon/2)n}\bigr)$.

Given sets $S_1, S_2, \dotsc, S_n$ and $T_1, T_2, \dotsc, T_n$, we encode the above problem as multi-pattern matching with don't cares over binary alphabet as follows:

The text is $$1[T_1]10^{m+2}1[T_2]10^{m+2}\dots0^{m+2}1[T_n]1\,,$$ where $[T_i]$ is the natural encoding of $T_i$ as a binary string.
We have $n$ patterns of form $1\langle S_i \rangle 1$, where $\langle S_i \rangle$ is a string $y = y_1y_2\dots y_m$ such that $y_j = 1$ if $j \notin S_i$ and $y_j = * $ if $j \in S_i$ (here $*$ is the don't care symbol).

Now it's clear that a pattern $1\langle S_i \rangle 1$ can match the text at an occurrence of $1[T_j]1$, and only when $S_i \cup T_j = [m]$. The total length of patterns and the length of the text are both $O(nm)$, for instance so a near-linear single-pass algorithm for multiple patterns would give substantial improvements over best known CNF-SAT algorithms...

(Note that this does not say anything about algorithms that use lots of time preprocessing the patterns, say, quadratic in the total length of the patterns.)


On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!P}$ We know that $\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}$. From Savitch's Theorem, $\mathcal{N\!L}\subseteq\mathcal{L}^2$, and, from Space Hierarchy Teorem, $\mathcal{L}\neq\mathcal{L}^2$. So, as we don't know if $\mathcal L\neq\mathcal P$, we don't know if $\mathcal L^2\subseteq\mathcal P$, or do we know that $\mathcal L^2\not\subseteq\mathcal P$? Has anybody been trying to prove that $\mathcal L^2\subseteq\mathcal P$? What are the latest results, or efforts, in this way? I've been trying to write a survey on this topic, but haven't found anything relevant.

Furthermore, whether exists or not a $\mathcal{N\!P}$ problem which is not $\mathcal{N\!P}$-complete is an open question, and such existence would imply $\mathcal L\neq\mathcal{N\!P}$, as every $\mathcal L$ problem is complete for $\mathcal L$. But do we really not know that $\mathcal L\neq\mathcal{N\!P}$? Has anybody been trying to prove this? Again, what are the latest results, or efforts, in this way?

Maybe I'm missing something, or searching wrongly, but I couldn't find anyone working on the $\mathcal L^2\subseteq \mathcal P$ and $\mathcal L\neq\mathcal{N\!P}$ questions.

You can check the following paper:

Translational lemmas, polynomial time, and $ (\log n)^j$-space by Ronald V. Book (1976).

Figures 1 and 2 in the paper give the summary of what is known and what is unknown.

I put Theorem 3.10 in the paper here:

$ DTIME(poly(n)) \neq DSPACE(poly(\log n)) $;
for every $ j \geq 1 $, $ DTIME(n^j) \neq DSPACE(poly(\log n)) $;
for every $ j,k \geq 1 $, $ DTIME(n^j) \neq DSPACE( (\log n)^k ) $.


Multi-language DFA minimisation I'm interested in a slight generalisation of DFA. As usual we have state-set $Q$, finite alphabet $\Sigma$, a $\Sigma^*$-action defined on $Q$ by $\delta : Q\times\Sigma\rightarrow Q$, and initial state $q_0$; but instead of the usual terminal set, we take a family $(T_i)_{i\in 1..n}$ of subsets of $Q$. A Multi-language DFA $M$ is then the tuple

$(Q, \Sigma, \delta, q_0, (T_i))$

and $L \subseteq \Sigma^*$ is recognised by $M$ iff $L = \{s\in\Sigma^*|q_0s\in T_i\}$ for some $i\in 1..n$ . Define $(L_i(M))_{i\in 1..n}$ to be the family of languages recognised by M, if you like.

Okay, now for my question: given a family of regular languages $(L_i)_{i\in 1..n}$ , I want to find the minimal Multi-language DFA $M$ as described above such that $L_i = L_i(M)$ for all $i\in 1..n$ , that is, such that $|Q|$ is minimised over all such machines. My question is, are there any known efficient ways of doing this, perhaps analogous to standard DFA minimisation theory? Conversely, is there any evidence that this problem might be hard?

Short answer. Given a finite family of regular languages $\mathcal{L} = (L_i)_{1 \leqslant i \leqslant n}$, there is a unique minimal deterministic complete multi-automaton recognizing this family.

Details. The case $n = 1$ corresponds to the standard construction and the general case is not much different in spirit. Given a language $L$ and a word $u$, let $u^{-1}L = \{ v \in A^* \mid uv \in L \}$. Define an equivalence relation $\sim$ on $A^*$ by setting
$$
 u \sim v \iff \text{for each }L \in \mathcal{L},\ u^{-1}L = v^{-1}L
$$
Since the $L_i$ are regular, this congruence has finite index. Further, it is easy to see that each $L_i$ is saturated by $\sim$ and that for each $a \in A$, $u \sim v$ implies $ua \sim va$. Let us denote by $1$ the empty word and by $[u]$ the $\sim$-class of a word $u$. Let $\mathcal{A}_\mathcal{L} = (Q, [1], \cdot, (F_i)_{1 \leqslant i \leqslant n})$ be the deterministic multi-automaton defined as follows:

$Q = \{ [u] \mid u \in A^*\}$,
$[u] \cdot a = [ua]$,
$F_i = \{ [u] \mid u \in L_i\}$.

By construction, $[1] \cdot u \in F_i$ if and only if $u \in L_i$ and hence $\mathcal{A}_\mathcal{L}$ accepts the family $\mathcal{L}$. It remains to prove that $\mathcal{A}_\mathcal{L}$ is minimal. It is actually minimal in a strong algebraic sense (which implies that it has the minimal number of states). Let $\mathcal{A} = (Q, q_-, \cdot, (F_i)_{1 \leqslant i \leqslant n})$ and $\mathcal{A}' = (Q', q'_-, \cdot, (F'_i)_{1 \leqslant i \leqslant n})$ be two multi-automata. A morphism $f: \mathcal{A} \to \mathcal{A}'$ is a surjective map from $Q$ onto $Q'$ such that

$f(q_-) = q'_-$,
for $1 \leqslant i \leqslant n$, $f^{-1}(F'_i) = F_i$,
for all $u \in A^*$ and $q \in Q$, $f(q \cdot u) = f(q) \cdot u$.

Then for any accessible deterministic multi-automaton $\mathcal{A}$ accepting $\mathcal{L}$, there is a morphism from $\mathcal{A}$ onto $\mathcal{A}_\mathcal{L}$. To prove this, one  first verifies that if $q_- \cdot u_1 = q_- \cdot u_2 = q$, then $u_1 \sim u_2$. Now $f$ is defined by $f(q) = [u]$ where $u$ is any word such that $q_- \cdot u = q$. Then one can show that $f$ satisfies the three required properties.

The end is a bit sketchy, let me know if you need more details.


What is the goal behind abstract interpretation in programming languages? I am now trying to understand better what "abstract interpretation" in programming languages are. I found a good book chapter that explains the idea of extending the domain with a least fixed element, the four axioms that yield a fixed point for a continuous function, and so on. I understand these technical details (though I am not quite sure what is "abstract interpretation" exactly referring to in this whole scheme).

What I am not sure about is what motivates the use of abstract interpretation? Is it just identifying fixed points for computable functions? Is the main motivation coming from having recursion in most programming languages?

Would also be glad to get some high-level overview which does go technically deep enough for someone who has a degree in computer science. I find the Wikipedia page rather unsettling.

Abstract interpretation is a very general concept and depending on whom you ask, you will receive different explanations because versatile concepts admit multiple perspectives. The view in this answer is mine and I would not assume it is general.

Computational hardness as a motivation

Let's start with decision problems, whose solutions have a structure like this:

There is often an NP-hard lower bound on the procedure. Checking semantic properties of programs is even undecidable. What can we do?

Let's make two observations. First, we can sometimes solve specific problem instances even if we cannot solve the general problem. Second, applications like compiler optimization tolerate approximation in that a compiler that eliminates some but not all sources of inefficiency is useful. To make this intuition precise, we must answer:

What does it mean formally to solve some, but not all problem instances?
What is an approximate solution to a decision problem?

Abstract Interpretation Idea 1: Change the Problem Statement

To me, a major insight of abstract interpretation is to change the problem formulation so that instead of asking for a Yes/No answer, we ask for a Yes/No/Maybe answer.

As a consequence, every problem has a trivial, constant time solution (output Maybe). We can now shift our attention to deriving a procedure that does not always produce Maybe. To return to the questions above, a solution that works for some problem instances is one that returns Maybe on problems it cannot solve. Moreover, Maybe is an approximation of Yes and No  because we are not certain what the answer is.

This idea is not restricted to decision problems. Consider these problems concerning programs.

Which lines of code in the program are dead (will never be executed)?
Which variables in the program have constant values?
Which assertions in the program are violated?

In all these situations, we can move from an exact solution to an approximate one by considering solutions that have some uncertainty.

What is a set of lines of code that is dead?
What is a set of variables in the program that have constant values?
What is a set of assertions in the program that is not violated?

The sets produced need not be the largest. This idea is extremely general and applies to problems that have little to do with program analysis.

Instead of adding $m$ and $n$, we can ask for a range $[a,b]$ in which the sum lies.
Instead of multiplying $m$ by $n$ we can ask for $k$ bits of the result (specific, common examples are the sign or the parity bit).
Instead of asking for the satisfying assignments to a formula, we can ask for a set that contains the satisfying assignments.

Note that we have not only changed the problem but also strictly generalized it because a solution to the original problem is still a solution to the modified problem. The big unanswered question now is: How can we find an approximate solution?

Abstract Interpretation Idea 2: Fixed Point Characterization of the Original Solutions

The second big idea is to observe that the set of solutions to many problems has a characterization as a fixed point in a lattice of candidate solutions. As an example, suppose you have a graph and you want to know if a vertex $t$ is reachable from a vertex $s$. We can break this down into finding the set $\mathit{Reach}(s)$ of all vertices reachable from $s$ and then checking if $t$ is in this set. We can further observe that $\mathit{Reach}(s)$ is the least solution to the equation:

  $X = \{s\} \cup \{ w ~|~ v \text{ is in } X \text{ and } (v,w) \text{ is an edge}\}$

The value of a fixed point characterization is that the exact solution can be viewed as the limit of a series of approximations. In this example, the $n$-th element of the series is the set of graph vertices reachable in $n$ steps from $s$ and approximation is a subset of these vertices.

The fixed point characterization is a design decision. There are many different characterizations of a set of solutions. Each of them may have different advantages. In the case of programming languages, we have more structure than just dealing with a graph. The fixed point equations we care about can be defined by induction on structure of the input program. This idea is not specific to programs. When applying abstract interpretation to elements of a structured language such as a grammar, logical formula, program, arithmetic expression, etc. we can define fixed points by induction on the structure of some syntactic object.

By giving this fixed point characterization, we are committing to a specific way of computing solutions. We will not actually calculate this fixed point because it is at least as hard as solving the original problem, which brings us to the next step.

Abstract Interpretation Idea 3: Fixed Point Approximation

Instead of computing a fixed point of a function $F$ in a lattice $L$, we can compute a fixed point of another function $G$ in a lattice $M$. Provided certain conditions are met relating $M$ to $L$, a solution computed in $M$ is guaranteed to be an approximation of the solution in $L$. This is one of the foundational results of abstract interpretation, usually called the fixed point transfer theorem. The soundness condition is given either by Galois connections, or weaker settings involving abstraction or concretization functions, or soundness relations.

The fixed point transfer theorem guarantees that you do not have to prove that you are computing a sound approximation every time you design an approximate analysis. You only have to prove that the lattices $L$ (containing original solutions) and $M$ (containing approximations)  and the functions $F$ and $G$ satisfy certain constraints. This is a big win if you are the designer of an analysis and you care about soundness.

You may find the intuition behind fixed point transfer insightful. We can think of a fixed point as the limit of a (possibly transfinite) chain of elements. Computing approximate solutions amounts to approximating this limit, which we can do by approximating elements of the chain.

The notion of approximation depends on the application. If you are using graph reachability to plan a trip, you may accept an approximation that tells you there is no path between $s$ and $t$ even if there is a path, but you will not be happy if the algorithm says there is a path from $s$ to $t$ where there is no path.

Abstract Interpretation Idea 4: Fixed Point Approximation Algorithms

Everything seen so far has been a mathematical existence result. The final step is to compute the approximation. When the lattice of approximations is finite (or if the ascending/descending chain condition is met), we can use a simple iterative procedure. If the lattice is infinite an iterative procedure may not suffice, though computing a fixed point may still be decidable. In this situation, many techniques are used to further approximate the solution, or to jump to an exact solution faster than a naive iteration algorithm. In the context of computing a solution, you hear terms like widening, narrowing, strategy iteration, acceleration, etc.

Summary

In my opinion, abstract interpretation provides a mathematical basis for the notion of abstraction in the same way that mathematical logic provides a mathematical basis for reasoning. The solutions to many problems we care about have characterizations as fixed points. This observation is not restricted to programming language problems and even to computer science. Approximate solutions can be characterized as approximations of fixed points and are computed with specialized algorithms. These characterizations and algorithms will exploit the structure of the problem instance. In the case of programs, this structure is given by the syntax of the language.

Computing approximations to problems that do not have a natural metric is an art constantly developed and refined by practitioners. Abstract interpretation is one mathematical theory for the science behind this art.

References
There are several good tutorials on abstract interpretation that you can read.

A casual introduction to Abstract Interpretation, Patrick Cousot (Joint work with Radhia Cousot), Workshop on Systems Biology and Formals Methods (SBFM'12)
A gentle introduction to formal verification of computer systems by abstract interpretation, Patrick and Radhia Cousot, Marktoberdorf Summer School 2010.
Lecture 13: Abstraction Part I, Patrick Cousot, Abstract interpretation, MIT Course.
Introduction to Abstract Interpretation, Samson Abramsky and Chris Hankin, Abstract Interpretation of Declarative Languages, 1987.
Abstract interpretation and application to logic programs, Patrick and Radhia Cousot, 1992. The first two sections have a general, high-level overview with several examples.


"lambda" term usage in programming could any one please let me know what is the relation between "lambda" and anonymous functions in programming?

in other words why we say lambda function to an anonymous function?

I am here trying to understand the reason for use of the term

There is a popular formal system called Lambda calculus. It is Turing complete and has great importance in the theory of programming languages. Lambda calculus is based on anonymous functions with very simple syntax. You start a new function with a $\lambda$, list the arguments, place a dot, and write down the return value. For example, $\lambda x.x$ is the identity function, $\lambda x.xx$ applies the functional argument $x$ to itself.

Since programming language designers know Lambda calculus very well, it seemed like a good idea to call anonymous functions in their language lambdas.


Starting SAT solver papers I want to make a first SAT solver. I know the SAT competition and the SAT conference, and there are just so many papers on this subject. I'm a starter, an overwhelmed starter. Where should I begin? Eventually I want to push the state-of-the-art. I want some expert advice on how to start, so that I won't be wasting my time on the non-essentials too early. Many thanks.

An excellent beginner overview is given by the following article from 2009.

Boolean Satisfiability: From Theoretical Hardness to Practical Success, Sharad Malik, Lintao Zhang,  Communications of the ACM, 2009

There are several ways to get into the technical aspects. You can even start with the original Davis-Putnam paper. It is extremely clear and has detailed examples. When discussing SAT optimizations in a course, we discovered that a few one  may imagine are already there. The Davis-Logeman-Loveland paper is (I feel) less instructive, but it is so short you may as well read it.

A Computing Procedure for Quantification Theory, Martin Davis, Hilary Putnam, Journal of the ACM, 1960.
A machine program for theorem-proving, Martin Davis, George Logemann, Donald Loveland, Communications of the ACM, 1962.

There are may ways to catch up on the developments of the next 50 years. I would recommend lecture slides. Just searching for 'DPLL' will throw up many many tutorials. If you browse through them, I'm sure the mist will clear -- to some extent. There are also many useful surveys. The Zhang-Malik paper is a good place to start. There are several articles in the Handbook of Satisfiability you may find useful.

The Quest for Efficient Boolean Satisfiability Solvers, Lintao Zhang, Sharad Malik, Joint invited paper for CAV and CADE 2002.
Handbook of Satisfiability, Edited by Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, 2009
Anatomy and Empirical Evaluation of Modern SAT Solvers, Karem  Sakallah, Joao Marques-Silva, Bulletin of the EATCS, 2011.

I second the suggestion of Mikolaos. The MiniSAT code is clean and of manageable size. You can play with it. There are several other solvers you can try. CryptoMiniSat is also quite clean. You should also consult the work of Armin Biere, who writes SAT solvers and writes about writing SAT solvers.


How can we know that formal methods work? An important goal of formal methods is to prove the correctness of systems, either by automated or human-directed means. However, it seems that even if you can give a correctness proof, you may NOT be able to guarantee that the system will not fail. For example:

The specification may not model the system correctly, or a production system may be too complicated to model, or the system may be flawed inherently due to contradictory requirements. What techniques are known to test whether a specification makes any sense at all?
The proof process may be flawed too! Who knows that those inference rules are correct and legitimate? Furthermore, proofs can be very large, and how do we know that they do not contain errors? This is the heart of the critique in de Millo, Lipton, and Perlis's "Social Processes and Proofs of Theorems and Programs".  How do modern formal methods researchers respond to this critique?
At runtime, there are many nondeterministic events and factors that can seriously affect the system. For example, cosmic rays can alter RAM in unpredictable ways, and more generally we have no guarantees that hardware will not suffer Byzantine faults, which Lamport has proved are very difficult to be robust against. So the correctness of the static system does not guarantee the  system won't fail! Are there any techniques known to account for the fallibility of real hardware?
At present, testing is the most important tool we have for establishing that software works. It seems like it should be a complementary tool with formal methods. However, I mostly see research which is either focused on formal methods or testing. What is known about combining the two?

Regarding 4: There's plenty of work combining formal methods and testing. Googling "formal methods testing" reveals quite a large amount of work. Although there are many different goals of such work, one of the key goals is to generate more effective test suites. This talk gives a nice introduction, based on model checking.

Also regarding the issue software security, which has been edited out of the question: formal methods need to work harder to deliver in that realm. Typically one writes a specification for a piece of software and verifies that the specification is satisfied, namely, that when the input satisfies the precondition that the output satisfies the postcondition. To ensure secure software one also needs to check also that the software behaves sensibly for input that does not satisfy the precondition. (This is of course equivalent to setting the precondition to true for all input.) The space of all inputs is typically much larger than just well-formed input, but typically this is one place where even functionally correct software can be violated, simply by violating its assumptions.

Regarding point 3: Some work has been done for verifying systems in settings where faults are explicitly modelled, including Faulty Logic:  Reasoning About Fault-tolerant Programs. Matthew Meola and David Walker. European Symposium on Programming, 2010. Work on probabilistic model checking and probabilistic verification certainly both also address the issue of faults to some degree.


What is the simplest universal unidimensional interaction net system? The Interaction Combinators are possibly the simplest multidimensional system of interaction nets that is Turing-complete. What about interaction nets with only 2 ports - 1 principal, 1 auxiliary? What is the simplest of those systems which is Turing-complete?

Turing machines and unidimensional cellural automata may both be regarded as "unidimensional" interaction net systems (see Lafont's Interaction Combinators paper).  So any simple UTM or Turing-complete cellula automaton induces a "simple" Turing-complete system.  I'm afraid no better answer is known.

Anyway, "simple" is relative: the interaction net system corresponding to even a very small UTM is big compared to the interaction combinators. Cellular automata probably give smaller systems (although still bigger than the interaction combinators) but the interest of these is nevertheless unclear as no special feature of interaction nets is used about them, they are just paraphrases of the original model.


Constructivity in Natural Proof and Geometric Complexity Recently, Ryan Willams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$.

Constructivity in Natural Proof is a condition that all combinatorial proofs in circuit complexity satisfies and that we can decide whether the target function in $\mathsf{NEXP}$ (or another "hard" complexity classes) has a "hard" property by a algorithm that runs in poly-time in the length of target function's truth table.

The other two conditions are: useless condition that require "hard" property can not be computed by any circuits in $\mathsf{TC}^0$ and largeness condition that the hard property is easy to find.

My question is :

Does this result make the Geometric Complexity Theory (GCT) unavailable to resolve main separation problems such as $\mathsf{P}$ vs $\mathsf{NP}$, $\mathsf{P}$ vs $\mathsf{NC}$, or $\mathsf{NEXP}$ vs $\mathsf{TC}^0$?

References:

Ryan Williams, "Natural Proofs Versus Derandomization"

No, the unavoidability of constructivity definitely still leaves GCT open as a viable plan of attack on lower bound problems such as $NP$ vs. $P/poly$.

First, it is worth mentioning that Ryan's result on constructivity is very similar in flavor to the so-called "Flip Theorems" by Mulmuley, which say, for example, that if permanent does not have poly-size arithmetic circuits, then there is a randomized poly-time constructible set of (polynomially many) matrices $\{M_1, \dotsc, M_{p(n)}\}$ such that every small circuit differs from the permanent on one of these matrices. See  Explicit Proofs and The Flip, Technical Report, Computer Science Department, The University of Chicago, September 2010 by Mulmuley.

Second, the centrality of symmetry-characterization (mentioned already by siuman) in GCT has become more apparent since Regan's survey. If symmetry-characterization turns out to be as crucial to GCT as it seems like it is going to, then this already gets around the largeness condition. For the definition of symmetry-characterzation, see this answer to a closely related previous question.

For a proof that symmetry-characterization violates largeness, see Section 3.4.3 "Symmetry-characterization avoids the Razborov–Rudich barrier" in my thesis (shameless self plugs, but I don't know anywhere else where this is written down so completely). I suspect it also violates constructivity, but left that as an open question there. (Earlier in Chapter 3 there's also an overview of the flip theorems in GCT and how they relate to symmetry-characterization.)

(I find it interesting that symmetry-characterization - the very property we suspect will be used in GCT that gets around Razborov--Rudich - is used to prove the flip theorems, which essentially say that constructivity is necessary.)

Finally, it is worth mentioning that although in the long run GCT aims to address $NP$ versus $P/poly$ and other Boolean problems, at the moment most work in GCT is focused on algebraic analogs of these, such as over the complex numbers, and there is as yet no algebraic analog of Razborov--Rudich (that I know of).


"Caged" complexity classes ? This is a somewhat frivolous question that popped up in my head after reading the various responses to "What's the “smallest” complexity class for which a superlinear circuit bound is known?".

Answers refer to $\mathsf{S_2 P}$, and when I looked at the zoo entry for it, I discovered this:

  $\mathsf{S_2-EXP•P^{NP}}$: Don't Ask

  One of the caged classes of the
  Complexity Zoo.

  Has been implicated in a collapse
  scandal involving $\mathsf{AM}[\text{polylog}]$, $\mathsf{coNP}$,
  and $\mathsf{EH}$

So now I'm intrigued. What's a caged complexity class, and what's the juicy scandal here :) ? The zoo has no references to clarify.

The Complexity Zoo has a reference to that result in the description of the class AM[polylog]:

  […] [SS04] show that if AM[polylog] contains coNP, then EH collapses to S2-EXP•PNP. ([PV04] improved the collapse to AMEXP.)

In the Complexity Zoo, a class or a statement is caged when it looks very scary.  Examples of caged statements can be found in the descriptions of coNP/poly and SFk (not for the easily scared, reader discretion is advised).


Multidimensional arithmetic progression variant For $\vec{d} \in \mathbb{N}^n$, let $Q(\vec{d}) \subset \mathbb{N}^n$ be the set of vertices of the $n$-dimensional cube scaled in the direction of the $i$-th coordinate by $d_i$, i.e.
$Q(\vec{d} = \{\langle \pm d_1, \ldots, \pm d_n\rangle\}$.

Consider the following problem:

  Given a set of points in $\mathbb{N}^n$ and number $k$,
  does the set contains an $n$-dimentional arithmetic progression of length $k$?

More formally,

  Input:
  given a finite set $X \subseteq \mathbb{N}^n$ and a positive integer $k \in \mathbb{N}^+$.

  Question:
  are there $\vec{o}\in \mathbb{N}^n$ and $ \vec{d} \in (\mathbb{N}^+)^n$ such that
  $\vec{o}+ Q(i\vec{d})\subseteq X$ for all integers $0 \leq i \leq k$?

Informally we are looking at the containment of
the vertices of scaled $n$-dimensional axis-aligned cubes centered at $\vec{o}$.

Does this problem have a name?
What is its complexity?
Can we solved it using dynamic programming?

The book Additive Combinatorics by Terence Tao and Van Vu discuss arithmetic sequences in depth from a mathematical point of view.  They establish the existence of arithmetic sequences under various conditions of your set $X$.

Example: Szemeredi Theorem

If a subset positive "density"  in your lattice it has infinitely many arithmetic progressions of arbitrary length.

$$\displaystyle \mathrm{density}(E) =  \limsup_{N \to \infty}  \frac{|E \cap [1,N]| }{N} \geq 0$$

Let $E \subseteq \mathbb{N}$ be set of positive upper density, then $E$ has a non-trivial $k$-term arithmetic progression.

You could totally imagine looking for vectors arranged in various patterns rather than restrict your attention to $\mathbb{Z}$.

The book simplifies very technical Fourier analysis and probability replacing it with less technical Fourier theory and probability.   They break down the heavy duty math into lemma and theorem that are useful for more specific problems.

Example Consider a random set $E \subset [1,N]$ with probability $\mathbb{P}[k \in E] = \frac{1}{2}$.  Any  3 evenly spaced numbers elements $a, a+d, a+2d \in \mathbb{N}$ will chosen inside $E$ with probability $\frac{1}{8}$, so we can expect many arithmetic progressions in the random set $E$.

On the other extreme is using the floor function  $\{[n \sqrt{7}] : n \in \mathbb{Z}\} = \{ [  0,   2,   5,   7,  10,  13,  15,  18,  21,  23,\dots \}$.  This is about as "ordered" as you can get, and it will also have many arithmetic progressions of arbitrary length.

Then it would be up to you to consider the run-time aspects of the algorithms they are implying.  It may not necessarily be easy to find arithmetic sequences in the prime or square free numbers even if we know they exist.


Deciding satisfiability and non-validity For propositional logic, a decision procedure for satisfiability can be turned
into a decision procedure for non-validity by giving it the negated
version of a formula.

Does this hold for all logics for which satisfiability is decidable?

More precisely:

Let $F$ be a set of well-formed formulas in some logic $L$. $F$ is closed under
negation, i.e. $f \in F \implies \neg f \in F$. Let $F'$ be a subset of $F$ such that
satisfiability of $F'$ is decidable. Let $F'' = \{ \neg f | f \in F' \}$. Is there a logic
$L$ for which satisfiability is decidable for $F'$ but not for $F''$?

For (propositional) intermediate logics, a decision procedure for satisfiability cannot generally be turned into a decision procedure for (non)validity, because all intermediate logics happen to have the same set of satisfiable formulas, namely, the set of classically satisfiable formulas, whereas some (a majority of) intermediate logics are undecidable.

(To make sense of the juxtaposition, all of the intermediate logics should be considered in the language of the weakest one, i.e., $\land$, $\lor$, $\to$, and $\neg$ or $\bot$.)

The coincidence of SAT's for these logics is a consequence of Glivenko theorem (which can be paraphrased by asserting that $\neg\varphi$ is provable classically iff it is provable intuitionistically, for any formula $\varphi$). See also this post.


automorphism in Cai-Furer-Immerman gadgets In the famous counter example for graph isomorphism via Weisfeiler-Lehman (WL) method the following gadget was constructed in this paper by Cai, Furer and Immerman.
They construct a graph $X_k = (V_k, E_k)$ given by

$V_k = A_k \cup B_k \cup M_k \\ \text{ where } \\
\quad A_k = \{a_i \mid 1 \leq i \leq k\}, \\
\quad B_k =\{b_i \mid 1 \leq i \leq k\}, \mbox{ and } \\
\quad  M_k = \{ m_S \mid S \subseteq \{1,2,\ldots, k\},\ |S| \text{ is even} \}\\
E_k =\{(m_S,a_i) \mid  i \in S\} \cup  \{(m_S, b_i)\mid i \notin S\}$

One of the lemmas in the paper (lemma 3.1 page 6 )  states that if we color the vertices $a_i$ and $b_i$ with color $i$ then $|Aut(X_k)| = 2^{k-1}$ (color has to be preserved by the automorphism) where each automorphism corresponds to interchanging $a_i$ and $b_i$ for each $i$ in some subsets $S$ of $\{1,2,\ldots, k\}$ of even cardinality. They say that the proof is immediate. But I fail to see how even in the case of $k= 2$. In $X_2 \ (a_1, m_{\{1,2\}})$ is an edge but if we have automorphism which interchanges $a_1, b_1$ and $a_2, b_2$ the above edge gets transformed to $(b_1, m_{\{1,2\}})$ which is not an edge. So that should not be an automorphism.

I would like to understand what is my misunderstanding.

You're missing the emptyset $\emptyset$ which is connected to all $b$'s. To get an  automorphism, you select a subset $T\subseteq \{1,...,k\}$ of even cardinality and then swaps $a_i$ with $b_i$ for each $i\in T$ and then adjusts the sets in the middle. In your example the graph is $$(a_1,\{12\}),(a_2,\{12\}),(b_1,\emptyset),(b_2,\emptyset).$$

Still in your example if $T=\emptyset$ you don't need to do anything and if
$T=\{1,2\}$ the automorphism is given by swapping $a_1$ with $b_1$, $a_2$ with $b_2$ and $\{1,2\}$ with $\emptyset$.

Now for the general case, we need to show that there is always a way of adjusting the middle vertices. We know that $T$ has even cardinality. So let $|T|=2r$. We just need to show that such an
automorphism exists if $|T|=2$ since otherwise we can apply the composition of $r$ automorphisms corresponding to partitioning $T$ into $r$ subsets of size $2$. Thus assume $T=\{i,j\}$.  Then the automorphism swaps $a_i$ with $b_i$,
$a_j$ with $b_j$, each middle vertex $S$ such that $S\cap\{i,j\}=\emptyset$ with the middle vertex $S\cup \{i,j\}$ (this can be seen in your example), and each subset $S$ such that $S\cap \{i,j\}=\{i\}$ with the subset such that $S\cap \{i,j\}= \{j\}$ (This you can see for $k=3$). Notice that this swapping process is an automorphism since for an index $p\neq \{i,j\}$ the edge relation between $a_p$, $b_p$ and these swapped vertices is completely preserved, and clearly the edge relation between $a_i,a_j,b_i,b_j$ is properly adjusted.

Finally to see that these are the only possible automorphisms, notice that each $a_i,b_i$ is colored with its own color. So they cannot be mapped to another pair $a_j,b_j$. Also notice that it is not possible to have an automorphism that maps an middle vertex to a middle vertex without swapping some $a_i$ with some $b_j$. $\square$


Are types propositions? (What are types exactly?) I've been reading a lot on type systems and such and I understand roughly why they were introduced (in order to resolve Russel's paradox). I also understand roughly their practical relevance in programming languages and proof systems. However, I'm not entirely confident that my intuitive notion of what a type is, is correct.

My question is, is it valid to claim that types are propositions?

In other words the statement "n is a natural number" corresponds with the statement "n has the type 'natural number'" meaning that all the algebraic rules that involve natural numbers hold for n. (I.e. Said another way, algebraic rules are statements. Those statements that hold true for natural numbers also hold true for n.)

Then does this mean that a mathematical object can have more than one type?

Furthermore, I know that sets are not equivalent to types because you cannot have a set of all sets. Could I claim that if a set is a mathematical object similar to a number or a function, a type is a sort of meta-mathematical object and by the same logic a kind is a meta-meta-mathematical object? (in the sense that every "meta" indicates a higher level of abstraction...)

Does this have some kind of link to category theory?

The key role of types is to partition the objects of interest into different universes, rather than considering everything existing in one universe. Originally, types were devised to avoid paradoxes, but as you know, they have many other applications. Types give a way of classifying or stratifying objects (see blog entry).

Some work with the slogan that propositions are types, so your intuition certainly serves you well, though there is work such as Propositions as [Types] by Steve Awodey and Andrej Bauer that argues otherwise, namely that each type has an associated proposition. The distinction is made because types have computational content, whereas propositions don't.

An object can have more than one type due to subtyping and via type coercions.

Types are generally organised in a hierarchy, where kinds play the role of the type of types, but I wouldn't go as far as saying that types are meta-mathematical. Everything is going on at the same level – this is especially the case when dealing with dependent types.

There is a very strong link between types and category theory. Indeed, Bob Harper (quoting Lambek) says that Logics, Languages (where types reside), and Categories form a holy trinity. Quoting:

  These three aspects give rise to three sects of worship: Logic, which gives primacy to proofs and propositions; Languages, which gives primacy to programs and types; Categories, which gives primacy to mappings and structures.

You should look at the Curry-Howard Correspondence to see the link between Logic and Programming Languages (types are propositions), and Cartesian Closed Categories, to see the between the relationship with Category Theory.


Complexity Theory Consequences of $\mathsf{NP} = \mathsf{QP}$ I have a certain impossibility result that holds unless $\mathsf{NP} = \mathsf{QP}$. It seems quite likely that one could strengthen this to hold unless $\mathsf{NP} = \mathsf{P}$, which I would not need to motivate further in my paper.
Unfortunately, I don't have time to do that in this particular paper, so instead want to quickly motivate to cryptographers why $\mathsf{NP} = \mathsf{QP}$ is unlikely. I know of basic consequences (namely that it would badly violate essentially any form of ETH, so would imply that tournament dominating set is in P), but not much else.
Of course, there's also the obvious motivation that $\mathsf{NP} = \mathsf{QP}$ implies $\mathsf{NP}\cap\mathsf{coNP}\subseteq \mathsf{QP}$. Most hardness assumptions used in crypto are in $\mathsf{NP}\cap\mathsf{coNP}$, and a particular weak hardness assumption (fixed characteristic finite field discrete log) is known to be in $\mathsf{QP}$. One can therefore interpret $\mathsf{NP} = \mathsf{QP}$ as "most hardness assumptions in crypto are roughly comperable to fixed characteristic finite-field discrete log", which may work fine as motivation.
Still, is there any clearer motivation from a complexity theory point of view? For example a hierarchy collapse/something along those lines.

We can prove $\mathrm{NP\ne QP}$ unconditionally: $\mathrm{QP}$ is closed under quasipolynomial-time reductions, whereas $\mathrm{NP}$ is not (a simple padding argument shows that the closure of $\mathrm{NP}$ under quasipolynomial-time reductions includes all languages computable in nondeterministic quasipolynomial time, and this class strictly contains $\mathrm{NP}$ by the nondeterministic time-hierarchy theorem).
As for consequences of the weaker assumption $\mathrm{NP\subseteq QP}$, see the question Is NP in $DTIME(n^{poly\log n})$?.


Bivariate low-degree polynomial testing of Polishchuk-Spielman In the seminal paper of Polishchuk and Spielman where they give a construction of nearly linear sized $PCP$ for an $NP$ problem, one of the key ingredients is a low-degree test for bivariate polynomials.

The following paragraph just provides some information about the paper and context for my question. Strictly speaking, it may be skipped. My question itself is concerned with simple multivariate polynomial algebra

Essentially, to test if the function values on a set of evaluation points correspond to a bivariate polynomial of maximum degrees $(d,d)$, we check whether the restriction of this to axis parallel lines (i.e. rows and columns) are all degree $d$ univariate polynomials (This is an equivalence condition in the absolute case, which is easy to verify. The interesting part is the robustness of the test: that is, if the function values on the restrictions to axis parallel lines agree with low-degree polynomials on "most" points, then there is a bivariate low degree polynomial which also agrees with the function on most evaluation points). The proof of robustness uses the notion of error-corrector polynomial to capture the "bad" evaluation points, polynomial interpolation and then uses resultants.
I am intentionally not being too precise here because none of this is relevant to my actual doubt, which is probably a minor algebraic technicality in a part of the proof:
http://cs.yale.edu/homes/spielman/PAPERS/holographic.pdf

The problem

Consider section 5: "Piecing it together" in the above paper. The polynomials $P(x,y)$ and $E(x,y)$ are interpreted as univariate polynomials in $y$ over the field of rational functions in $x$ over $\mathbb{F}$, that is $\mathbb{F}(x)$ . We would ultimately like to show that $E(x,y)$ divides $P(x,y)$ as bivariate polynomials in $\mathbb{F}[x,y]$, and this is shown by arguing that $E(x,y)$ divides $P(x,y)$ as univariate polynomials in $y$ over $\mathbb{F}(x)$, and then use Gauss's lemma to imply the former.

I am unable to see how Gauss's lemma trivially establishes this implication.

For instance, suppose $P(x,y)=y^2x$ and $E(x,y)=yx^2$. Then $E$ does divide $P$ as polynomials in $y$ over $\mathbb{F}(x)$, but clearly not as bivariate polynomials in $\mathbb{F}[x,y]$.

(Gauss's lemma states that if a univariate polynomial in $\mathbb{D}[x]$ (where $\mathbb{D}$ is a UFD) is reducible as a polynomial in $\mathbb{K}[x]$ (where $\mathbb{K}$ is the field of fractions of $\mathbb{D}$), then it is reducible in in $\mathbb{D}[x]$ itself.)

If I understand it correctly, Gauss's lemma implies that that $P$ and $E$ have a non-trivial common factor over $\mathbb{F}[x,y]$.

But in the beginning of the proof of Lemma 8 they assume without loss of generality that $P$ and $E$ do not have a common factor. More specifically, they show that if $P$ and $E$ have a common factor then they can use induction to show that $E$ divides $P$.


Quantum circuit simulation divergence in results I'm learning about quantum computing in order to code a simulator. I tried the following circuit in Quirk

And ran the same circuit using OPENQASM 2.0:

Notice that the input is |11> in both cases, but it seems that the probabilities for 01 and 10 are switched. What I'm missing here? Thank you!

Peter Shor nailed the reason. This is because OpenQASM and Quirk have different conventions for how the order of wires maps into the order of bits shown in the kets. The simplest way to check this is to use a circuit that toggles only the top qubit.

Quirk considers the top qubit to be the least significant qubit, and labels kets in big endian order (i.e. the ordering humans use; why 12 represents twelve instead of twenty-one). So the 4-output chance display is showing outputs in the following order: probability of top=bottom=0; probability of top=1 and bottom=0, probability of top=0 and bottom=1; probability of top=bottom=1.

The reason I chose this order when making Quirk is because it makes the displays behave better when resizing. If you resize the chance display from 2-qubits to 3-qubits, and the third qubit is off, the original four outputs stay together in the top half instead of being spread apart. Also it's just the natural thing to do when programming: the wire at index k has weight 1<<k. Quirk's tendency to expand circuits and gates downward pushed it towards a "down means more/bigger" convention in other places as well, e.g. in the arithmetic circuits.


Dimensionality reduction with slack? The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ such that for all $x, y \in S$:
$$(1-\epsilon)||f(x)-f(y)||_2 \leq ||x-y||_2 \leq (1+\epsilon)||f(x)-f(y)||_2$$
It is known that similar statements are not possible for the $\ell_1$ metric, but is it known if there is any way of getting around such lower bounds by offering weaker guarantees? For example, can there be a version of the above lemma for the $\ell_1$ metric that only promises to preserve the distances of most points, but might leave some arbitrarily distorted? One that makes no multiplicative guarantee for points that are "too close"?

The standard reference for such a positive result is Piotr Indyk's paper on stable distributions:

http://people.csail.mit.edu/indyk/st-fin.ps

He shows a dimension reduction technique for $\ell_1$ where the distance between any pair of points does not increase (by more than factor $1+\epsilon$) with constant probability and distances do not decrease (by more than factor $1-\epsilon$) with high probability. The dimension of the embedding will be exponential in $1/\epsilon$.

There are probably follow up works that I'm not aware of.


Is Redis Turing Complete? Is Redis with all its data types (Strings, Lists, Hashes, Sets, Sorted Sets, etc.) Turing Complete?

No and in a sense yes.

No - this question is strongly reminiscent of those about SQL and the conclusion that it isn't (Turing complete). Despite its many capabilities, Redis does not provide looping or recursion for via native API, so that pretty much nails it.

However, you can easily run Lua scripts in Redis and Lua is in fact Turing complete, so in a sense so is Redis (similarly to how SQL becomes so once you allow the use of PL/SQL or the likes).


Given a B-Tree, determine the order keys were inserted Given a B-tree, determine what order the keys were inserted in.  There may be multiple answers: I'd like to generate them all.

Is there any known method for this?  Or similar problems?

Clarification: As the comments mentioned, enumerating them all may be intractable.  I'd like to do two things:

Create a partial ordering. Node 7 was inserted before Node 4, but cannot be compared to Node 20.  (I've done this successfully for a binary search tree, and am wondering if this can be applied to B-tree as well. For BSTs, it seems to be simple: Node A < Node B iff Node A is an ancestor of Node B, assuming no deletions.)
Create what I call a probabilistic partial ordering.  For example: Out of x possible orderings, y have Node 4 inserted before Node 20, and 1 - y have Node 4 after Node 20.  I still am working on this even for binary search trees, so perhaps it's better to ask this question there first.

I'm also working on expanding the model to include deletions (probablisticly), but that will come later.

Simple... keep two pointers, a next and a previous.


Computational Power of Neural Networks? Let's say we have a single-layer feed forward neural network with k inputs and one output. It calculates a function from  $\lbrace 0,1\rbrace ^{n}\rightarrow\lbrace 0,1\rbrace $, it's fairly easy to see that this has at least the same computational power as $AC^0$. Just for fun, we'll call the set of functions computable by a single layer neural network "$Neural$".

It seems, however, that it might have more computational power than $AC^0$ alone.

So ... is $AC^0 \subseteq Neural$ or is $Neural = AC^0$? Also has this kind of complexity class been studied before?

There are some references I could find:
General-purpose computation with neural networks: A survey of complexity theoretic results, 2003 and Counting hierarchies: polynomial time and constant depth circuits, 1993.

It appears that neural networks are considered threshold circuits; i.e. those circuits using MAJORITY gates. In (2) it is the case that a depth $d$ neural network has complexity $TC^0_d$ (here's a link to link to complexity zoo entry about $TC^0$).

Since $TC^0$ containts $ACC^0$, which is $AC^0$ with arbitrary MOD gates, then $AC^0 \subset TC^0$. Also, it is mentioned in the zoo that such circuits with depth 3 are strictly more powerful than those of depth 2.

In On the computational power of sigmoid versus Boolean threshold circuits,1991 it is mentioned that for a constant depth $d$, Boolean and real-valued threshold circuits (with polynomially bounded weights) are essentially the same.


Lower-bound of a decision problem What's the lower-bound of the decision problem that decides:

Whether there is at least one element A[i] such that A[i] = i in a sorted array A of non-negtive integers? (An example is A = {0,1,1,3,4,4,5}.)

Is there any sub-linear deterministic algorithm can solve the problem?

There is no sub-linear algorithm for it, assuming the array may have duplicates as in your example. The following shows that any algorithm must read all of $|A|$'s values.

Assume that there's sub linear algorithm $Alg$ that decides it.

Define an array $A$ by $A_k = k+1$.

Since $alg$ is sublinear, there has to be some cell of $A$ he didn't query. Denote such cell's index by $i$.

Define $B_k = \left\{
 \begin{array}{ll}
  k+1  & \mbox{if } k \neq i \\
  i & \mbox{if } k = i \\
 \end{array}
\right.$

Note since $Alg$ doesn't read cell $i$, it will answer the same for both $A$ and $B$, but obviously one of these answers is wrong..


Approximation algorithms for multicut for special classes of graphs The multicut problem is the following.

Given a graph $G=(V,E)$ with edge costs $c_e$ for edge $e$ and a set of $k$ terminal pairs $\{(s_1,t_1),\ldots,(s_k,t_k)\}$, the objective is to find a set of edges $F \subseteq E$ of minimum cost, such that in the graph $H=(V,E \setminus F)$, no terminal pair $s_i,t_i$ are in the same connected component. In other words, deleting the edges in $F$ will remove all paths between any terminal pair $s_i,t_i$.

This problem is NP-hard. For general graphs, an $O(\log k)$-approximation is known. For trees, a 2-approximation is known. It is also known to be APX-hard. Is there any other results known for special classes of graphs?

I am particularly interested in the following graphs, but other classes of graphs will also be informative.

Paths
Cycles
$n \times n$ grids
Outerplanar graphs
Planar graphs
Series-parallel graphs

Any reference or survey paper will be highly appreciated.

Check the following survey:

Marie-Christine Costa, Lucas Létocart, and Frédéric Roupin, "Multicut and integral multiflow: a survey", 2005

You can also check my dissertation on the directed case.


Möbius values of CNF and DNF lattices of a monotone Boolean function Let $\phi$ be a monotone Boolean function on a set of variables $\langle k \rangle := \{0,\ldots,k\}$ such that $\phi$ depends on all the variables in $\langle k \rangle$ (that is, for every variable $x \in \langle k \rangle$, there is a valuation $\nu: \langle k \rangle \setminus \{x\} \to \{\top,\bot \}$ such that $\phi(\nu \cup x \mapsto \top) \neq \phi(\nu \cup x \mapsto \bot)$).

Let $F_{\text{cnf}} = C_0 \land \ldots \land C_n$ be the (unique) minimized CNF representing $\phi$, where we see each clause simply as the set of variables that it contains.
For $\mathbf{s} \subseteq \langle n \rangle$, define $d_{\mathbf{s}} := \bigcup\limits_{i \in \mathbf{s}} C_i$. Note that we can have $d_\mathbf{s} = d_\mathbf{s'}$ for $\mathbf{s} \neq \mathbf{s'}$. Further notice that $d_\emptyset = \emptyset$.

We define the CNF lattice $(L_{\text{cnf}},\leq)$ of $\phi$ as the lattice with underlying set $L_\text{cnf} = \{ d_\mathbf{s} \mid \mathbf{s} \subseteq \langle n \rangle \}$, and where $\leq$ is reversed set inclusion (i.e, $d_\mathbf{s} \leq d_\mathbf{s'}$ iff $d_\mathbf{s'} \subseteq d_\mathbf{s}$). The top element $\hat{1}$ of that lattice is then $\emptyset$, while its bottom element $\hat{0}$ is $\langle k \rangle$.

We define similarly the DNF lattice $(L_{\text{dnf}},\leq)$ of $\phi$, where instead of $F_{\text{cnf}}$ we use $F_{\text{dnf}} = D_0 \lor \ldots \lor D_m$, the unique minimized DNF representing $\phi$. Observe that we have again $\emptyset$ as the top element and $\langle k \rangle$ as the bottom element.

Now, let $\mu_\text{cnf}: L_{\text{cnf}} \times L_{\text{cnf}} \to \mathbb{Z}$ be the Möbius function of the CNF lattice of $\phi$ (resp., $\mu_\text{dnf}$ the Möbius function of its DNF lattice). See, for instance, 3.7 of Enumerative Combinatorics for a definition of that function.

Example:
Let $\phi$ be the monotone Boolean function on variables $\langle 4 \rangle$ defined by the CNF $F_\text{cnf} = (3 \lor 4) \land (0 \lor 4) \land (0 \lor 1 \lor 2)$. You can check that its corresponding DNF is $F_\text{dnf} = (0 \land 3) \lor (0 \land 4) \lor (2 \land 4) \lor (1 \land 4)$. The Hasse diagrams of the CNF and DNF lattices of $\phi$, together with the values $\mu(e,\hat{1})$ for each element $e$ of the lattices, are drawn below (where, e.g., "034: 1" means that it is element $e=\{0,3,4\}$ and we have $\mu(e,\hat{1})=1$):

CNF lattice:

DNF lattice:

QUESTION: Is it always the case that $\mu_\text{cnf}(\hat{0},\hat{1})=0$ if and only if $\mu_\text{dnf}(\hat{0},\hat{1})=0$?
I know a proof of this conditionally to FP $\neq$ #P (which is beyond our scope here), but I would like to prove it unconditionally.

What I know:

First, I know that it does no matter if we start from minmized expressions or not, thanks to the crosscut theorem (see Corollary 3.9.4 of Enumerative Combinatorics, for instance);
Second, using the Möbius inversion formula on the lattices to count the number of satisfying valuations $\#\phi$ of $\phi$, I can easily show that $\#\phi$ is even iff $\mu_\text{cnf}(\hat{0},\hat{1})$  and $\mu_\text{dnf}(\hat{0},\hat{1})$ are both even, so that they have the same parity;
Third, I coded a little something to generate all monotone functions that depend on all their variables $\langle k \rangle$, up to $k=5$ (and there are a lot of them!) and tested my question. I found out that in fact I always had $|\mu_\text{cnf}(\hat{0},\hat{1})| = |mu_\text{dnf}(\hat{0},\hat{1})|$. Moreover I have cases where the signs are the same, and cases where they are opposite.

OK so, more than one year later, here is the answer to this. We'll see Boolean valuations $\nu$ as the set of variables that are mapped to $1$.

We can show that $\mu_\text{cnf}(\hat{0},\hat{1}) = (-1)^k \mu_\text{dnf}(\hat{0},\hat{1}) =  \sum_{\nu \models \phi} (-1)^{|\nu|}$.
In the literature, the quantity $\sum_{\nu \models \phi} (-1)^{|\nu|}$ is also called the Euler characteristic of $\phi$.

I'll only show that $\mu_\text{cnf}(\hat{0},\hat{1}) = \sum_{\nu \models \phi} (-1)^{|\nu|}$, because the proof is similar for $\mu_\text{dnf}(\hat{0},\hat{1}) = (-1)^k \sum_{\nu \models \phi} (-1)^{|\nu|}$.

Let $w \in \mathbb{R}$ be a weight. Define the mass of a valuation $\nu$ under $w$ as $m_w(\nu) = w^{|\nu|} (1-w)^{|\langle k \rangle \setminus \nu|}$, and the mass of $\phi$ under $w$ as $M_w(\phi) = \sum_{\nu \models \phi} m_w(\nu)$. (when $w \in [0,1]$ this can be seen as a probability.)

Define the functions $f,g: L_{\text{cnf}} \to \mathbb{N}$ by:

$f(d_\mathbf{s}) = M_w \left( (\lnot \bigvee_{i \in \mathbf{s}} C_i) \land \bigwedge_{i \in \langle k \rangle \setminus \mathbf{s}} C_i \right)$; in other words the total mass of the valuations that do not satisfy exactly the (disjunctive) clauses $C_i$ for $i \in \mathbf{s}$.
$g(d_\mathbf{s}) = M_w \left( \lnot \bigvee_{i \in \mathbf{s}} C_i \right)$; in other words the total mass of the valuations that do not satisfy at least the clauses $C_i$ for $i \in \mathbf{s}$.

We have $g(x) = \sum_{u \leq x} f(u)$ for all $x \in L_{\text{cnf}}$. So by Möbius inversion formula $f(x) = \sum_{u \leq x} \mu_\text{cnf}(u,x) g(u)$.
    Moreover, for $u = d_\mathbf{s} \in L_\text{cnf}^\phi$, we have that $g(u) = (1 - w)^{|d_\mathbf{s}|}$.
    Now, since $M_w(\phi) = f(\hat{1})$ are the same polynomials in $w$, by identifying the coefficients of $w^{k+1}$ we get that $\mu_\text{cnf}(\hat{0},\hat{1}) = \sum_{\nu \models \phi} (-1)^{|\nu|}$.


Program for computing Tree decomposition of a graph Does anybody know of an open-source program for computing Tree decomposition of graphs for a fixed "k"(width)? I know that the problem of finding Tree-Decomposition is NP-Hard for variable "k", but my input instances will be really small (~10 nodes) and "k" is fixed.

Some of these software might help you. (Not all of them are open-source though.)

*TreeD http://www.itu.dk/people/sathi/treed/

*dlib http://dlib.net/

*QuickBB http://www.cs.washington.edu/homes/vgogate/quickbb.html

*Hypertree http://www.dbai.tuwien.ac.at/proj/hypertree/downloads.html

*LibTW http://www.treewidth.com/treewidth/


Is there any research on approximation of reals with computable numbers I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential height functions.

The basic premise of Diophantine approximation is that you take a dense countable set(traditionally the rationals or the algebraic numbers), $A$ in some range(generally $(0,1)$) and a function $H: A \to \mathbb N$, the height function. You then see how given $N \in \mathbb N$ close you can get a member of $A$, usually referred to as $\alpha$ with $H(\alpha) < N$. The most famous result from this field is Dirichlet's Approximation Theorem which states that for any real in $(0,1)$ there exist infinitely many rationals $\frac{p}{q}$ such that $|x-\frac{p}{q}| \le \frac{1}{q^2}$. This has been shown to be optimal up to a constant.

Some height functions I imagined for the computable numbers would be

1) $H_c(\alpha)$ This is a restricted version of the above when the Turing machine is restricted to having $c$-characters not counting blank.

2) Same as 1 just counting transitions instead of states.

3) Some function on the time complexity to generate the number

4) Some function on the space complexity to generate the number

The first 2 are basically variants on Kolmogorov complexity I believe. The last two I'm not even sure how to map to the Naturals.

Here are some preliminary results I believe are true.

For 1 Using just rationals and an $x \in (0,1)$ you get an approximation of the following form
$$|x-\alpha| \le Cc^{-H_c(\alpha)}$$
For some $C>0$. I believe I can prove this. If it is true that using algebraic numbers of degree at most $d$ gives an approximation function of $|x-\alpha| \le cH^{-d-1}(\alpha)$ for some $c>0$ then I believe the same approximation function holds even if you use all algebraic numbers. The basic reasoning behind this is that it takes $O((d+1)\log_c(\max(a_1,\dots,a_{d+1})))$ states to output all the coefficients to the tape and then you should be able to do Newton's algorithm with a constant number of states. In the last equation $a_1,\dots,a_{d+1}$ is the set of coefficients of the minimal polynomial specifying $\alpha$.

Noting that the number of transitions is approximately equal to $c+1$ times the number of states you get an equivalent statement for 2 that for $x \in (0,1)$ you get
$$|x-\alpha| \le Cc^\frac{-H_c(\alpha)}{c+1}$$

For some constant $C > 0$. Due to these results I'd say 2 is probably the nicest approximation function since $c^\frac{n}{c+1}$ when restricted to integer inputs is bounded by $\sqrt[5]{4}^n$ or roughly $1.3195^n$.

A result I'd like to have and I believe is true is that the bounds on the approximation function for $3$ are optimal, that is that there exists $x \in (0,1)$ such that
$$|x-\alpha| \ge Cc^\frac{-H_c(\alpha)}{c+1}$$
For some constant $C>0$ and all but finitely many computable $\alpha$.

This is a cross-post from math.stackexchange. It was suggested to me that this site would be more likely to answer my question if there is any research or if this is worth pursuing any farther.

It's funny you should ask, because computability and diophantine approximation has actually been a popular topic in recent years. In particular Becher and Slaman and coauthors have many results and papers. See for instance

Becher, Verónica; Reimann, Jan; Slaman, Theodore A., Irrationality exponent, Hausdorff dimension and effectivization,  ZBL06837203.


Trace Equivalence vs LTL Equivalence I am looking for an easy example of two transition systems that are LTL equivalent, but not trace equivalent.

I have read the proof of Trace Equivalence being finer than LTL Equivalence in the book "Principles of Model Checking" (Baier/Katoen) but I'm not sure I really understand it. I am unable to picture it, is there maybe a simple example that can visualize the difference?

Reading Baier and Katoen closely, they are considering both finite and infinite transition systems. See page 20 of that book for definitions.

First, take the simple transition system $EVEN$:

Lemma: No LTL formula recognizes the language $L_{even} = $Traces$(EVEN)$. A string $c \in L_{even}$ iff $c_i = a$ for even $i$. See Wolper '81. You can prove this by first showing that no LTL formula with $n$ "next-time" operators can distinguish the strings of the form $p^i\neg p p^\omega$ for $i> n$, by a simple induction.

Consider the following (infinite, non-deterministic) transition system $NOTEVEN$. Note that there are two different initial states:

Its traces are precisely $\{a,\neg a\}^\omega - L_{even}$.

Corollary to the Lemma: If $NOTEVEN \vDash \phi$ then $EVEN \not\vDash \neg\phi$

Now, consider this simple transition system $TOTAL$:

Its traces are clearly $\{a,\neg a\}^\omega$.

Thus, $NOTEVEN$ and $TOTAL$ are not trace equivalent. Suppose they were LTL inequivalent. Then we would have an LTL formula $\phi$ such that $NOTEVEN \vDash \phi$ and $TOTAL \not\vDash \phi$. But then, $EVEN\vDash \neg\phi$. This is a contradiction.

Thanks to Sylvain for catching a stupid bug in the first version of this answer.