Isomorphism preserving transformation CNF to Graph?

I think there's a straightforward transformation to graphs with colored edges, which can in turn be transformed into ordinary graphs.
Given a CNF $\phi$ with clauses $c_i$ and variables $v_i$, construct a graph with vertices $c_i,v_i,\neg v_i$.  Add black edges between each clause $c_i$ and each literal in it.  Add a red edge between each variable $v_i$ and its complement $\neg v_i$.  This transformation maps isomorphic CNFs to isomorphic graphs, and vice versa.
(Proof: Given $\pi,\pi'$, you obtain a mapping on vertices: map clause $c_i$ to $\pi'(c_i)$ and map variable $v_i$ to $\pi(v_i)$ and $\neg v_i$ to $\neg \pi(v_i)$.  You can verify that this respects the edges.  Likewise, you can convert any mapping between the two graphs into $\pi,\pi'$.)
There are standard reductions that allow you to reduce colored graph isomorphism to graph isomorphism.  You basically use a gadget to represent the colors (you attach each red edge to a copy of a gadget that is unique to the color red, and attach each black edge to a copy of a gadget that is unique to the color black).  If you compose that with the construction I outline above, then you should get the desired reduction from CNFs to graphs.


How to prove $\tilde{\mathbb{E}}PQ=0$ when $\tilde{\mathbb{E}}P^2 = 0$?

That implication is not actually true.
Consider $P$, $Q$, and the pseudodistribution given by:

$$P = x, \quad Q = x^3,$$
$$r = 4,$$
$$\mathbb{\tilde E} 1 = 1, \quad \mathbb{\tilde E} x = 0,$$
$$\mathbb{\tilde E} x^2 = 0, \quad \mathbb{\tilde E} x^3 = 0,$$
$$\mathbb{\tilde E} x^4 = 1$$

Then $\mathbb{\tilde E}P^2 = 0$ but $\mathbb{\tilde E} PQ = 1$.

This is a valid degree-4 pseudodistribution since its moment matrix is positive-semidefinite.

$$ \left[\begin{array}{ccc} \mathbb{\tilde E}1 & \mathbb{\tilde E}x & \mathbb{\tilde E}x^2 \\ \mathbb{\tilde E}x & \mathbb{\tilde E}x^2 & \mathbb{\tilde E}x^3 \\ \mathbb{\tilde E}x^2 & \mathbb{\tilde E}x^3 & \mathbb{\tilde E}x^4 \\\end{array}\right] = \left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 0  \\ 0 & 0 & 1 \\\end{array}\right] $$


Realizability theory: difference in power between Lambda calculus and Turing Machines

John Longley has a very extensive survey article discussing the issues involved, "Notions of Computability at Higher Type".

The basic idea is that the Church-Turing thesis is only about functions from $\mathbb{N} \to \mathbb{N}$ -- and there's more to computation than that! In particular, when we write programs, we make use of functions of higher type (such as $(\mathbb{N} \to \mathbb{N}) \to \mathbb{N}$).

In order to fully define a model of higher type computation, we need to specify the calling convention for functions, in order to allow one function to call another function it receives as an argument. In lambda calculus, the standard calling convention is that we represent functions by lambda-terms, and the only thing you can do with a lambda in the lambda calculus is to apply it. In typical encodings with Turing machines, we pass functions as arguments by fixing a particular Godel encoding, and then strings representing the index of the machine you want to pass as an argument.

The difference in encoding means that you can analyze the syntax of the argument with a TM-style encoding, and you cannot with a standard lambda-calculus representation. So if you receive a lambda-term for a function of type $\mathbb{N} \to \mathbb{N}$, you can only test its behavior by passing it particular $n$'s -- you can't analyze the structure of the term in any way. This is just not enough information to figure out the code of the lambda term.

One thing worth noting is that with higher types, if a language is less expressive at one order, it is more expressive one order up, because functions are contravariant. So similarly there are functions you can write in LC that you can't with a TM-style encoding (because they rely on the fact that you can pass functional arguments and know that the receiver can't look inside the function you give it).

EDIT: Here's an example of a function definable in PCF, but not in TM+Goedel encodings. I'll declare the isAlwaysTrue function

 isAlwaysTrue : ((unit → bool) → bool) → bool

which should return true if its argument ignores its argument and always returns true, should return false if its argument returns false on any inputs, and goes into a loop if its argument goes into a loop on any inputs. We can define this function pretty easily, as follows:

isAlwaysTrue p = p (λ(). true) ∧ p (λ(). false) ∧ p (λ(). ⊥)

where ⊥ is the looping computation and ∧ is the and operator on booleans. This works because there are only three inhabitants of unit → bool in PCF, and so we can exhaustively enumerate them. However, in a TM+Goedel-encoding style model, p could test how long its argument takes to return an answer, and return different answers based on that. So the implementation of isAlwaysTrue with TMs would fail to meet the spec.


Linear-time algorithm for getting ends of diametral paths in special sequence of trees

Ok,

I have an algorithm I believe is O(nlog*(n)), that's n log-star(n) (log-star n is constant for all practical purposes), but it's hard to prove and I suppose I could be wrong.  The running time guess comes from assuming the path compression step takes amortized O(log*(n)) as it does in a union-find data structure, but I don't remember the proof of that so I don't really know for certain that it applies here.  Nonetheless, I certainly can't generate any examples where the path-compression is generally slow and I can prove the other operations are amortized constant time.

Following Chao Xu's suggestion, I'll describe the "insert a new leaf" operation on the data structure.

Each vertex has to contain pointers to 4 other vertices in addition to remembering its depth.

Each vertex $v_i$ must remember:

$v_i$'s deepest descendant
$v_i$'s child on whose branch (1) is contained
$v_i$'s nearest ancestor $w_i$ for whom $w_i(2)$ is not an ancestor of $v_i$
Which child of $w_i$ is an ancestor of $v_i$

In fact for any given vertex (1), (3), and (4) may be outdated, but using path-compression we can bring it up to date in (hopefully) amortized O(log*n) running time using path-compression.

def get_deepest(v): # returns (1)
  if v.deepest == v:
    return v
  v.deepest = get_deepest(v.deepest)
  while True:
    deep_ancest,_ = get_nearest_ignoring_ancestor(v.deepest)
    if (not deep_ancest) or deep_ancest.depth <= v.depth:
      break
    v.deepest = get_deepest(deep_ancest)
  return v.deepest

def get_nearest_ignoring_ancestor(v): # returns tuple containing (3) and (4)
  if v.nia == None:
    return (None, root)
  elif v.nia.child_containing_deepest == v.nia_child_containing_self:
    v.nia,v.nia_child_containing_self = get_nearest_ignoring_ancestor(v.nia)
  return (v.nia, v.nia_child_containing_self)

Now when we add a new vertex $v$, we traverse upwards through each (3) updating the deepest vertex until we find one that doesn't update.  If we encounter a vertex $w$ which is on the primary path (this is easy to check because $w$.deepest() will be the same as root.deepest()), then we check if the path between the newly inserted node and the current deepest is longer than the currently known longest path.  Then that becomes the new diameter.  This check can be done in constant time since we know the depths of the current deepest, the newly inserted node, and also the node $w$ at which the paths pointing to the two diverge. Then the length (number edges in) the new path is just $d(v)+d(deepest)-2 d(w)$

It's easy to see that this algorithm is correct because any diameter must have an endpoint at the deepest node from the root (This is generally true of trees.  If you don't believe me you can verify it for yourself) and with every node we insert, we check that either

a) It's the deepest node (in which case, we've just increased the currently longest path by one)

OR

b) There exists an ancestor containing a deeper (or equal) node which is not on the deepest path (so the diameter can't have increased)

OR

c) We check the newly inserted node against the deepest node and compute the length of the new path to see if it's longer than the current longest.

To finish the Python pseudo-code for the algorithm:

#root is the root of the tree, it's parent is None
#cur_opp is the vertex currently farthest from get_deepest(root)

def add_node(v, parent):
  v.deepest = v
  v.child_containing_deepest = None
  v.nia = parent
  v.nia_child_containing_self = v

  root_deepest = get_deepest(root)

  while True:
    v_ancest,_ = get_nearest_ignoring_ancestor(v)
    if not v_ancest:
      check_update_path(root_deepest)
      break
    old_deepest = deepest(v_ancest)
    if v.depth > old_deepest.depth:
      old_deepest.nia = v_ancest
      old_deepest.nia_child_containing_self = v_ancest.child_containing_deepest
      v_ancest.child_containing_deepest = v.nia_child_containing_self
      v_ancest.deepest = v
      update_next = True
    else:
      break
  check_update_path(v)

def check_update_path(v):
  cur_deepest = get_deepest(root)
  if v == cur_deepest:
    return
  common = get_nearest_ignoring_ancestor(v)
  if get_deepest(common) != cur_deepest:
    return
  max_len = len_path(cur_opp, cur_deepest)
  new_len = len_path(v, cur_deepest)
  if new_len > max_len:
    cur_opp = v

def len_path(a,b):
  a_ancest = get_nearest_ignoring_ancestor(a)
  assert get_deepest(a_ancest) == b
  return a.depth + b.depth - 2 * a_ancest.depth

The longest path is just the path from cur_opp to get_deepest(root)

Now to show that the number of deepest-branch changes is amortized constant with each add, just imagine that each time we compare two depths and get d(a) == d(b) (when we stop), we reserve one time unit for later.  When a node changes deepest branches, the paths must have first been equal so we use up that time unit.

So now all that remains to prove is that the path-compression step is amortized fast and I unfortunately don't know how to do that.

Please note I haven't tested this code and it is almost certainly buggy.  Also, I may have left out some edge cases such as how to insert the first node or what to do in certain situations if a node already is on the primary path.  It shouldn't be too hard to account for these.


Can MONOTONE WSAT be in solved in polynomial time?

This problem is indeed NP-complete.

Actually, the answer for this question is answered in:

https://cs.stackexchange.com/questions/11558/prove-np-completeness-of-deciding-satisfiability-of-monotone-boolean-formula

Therefore, this question is closed and answered...


Can Hoare logic be used when objects are created or deleted?

There is a lot of work on Hoare Logic for object oriented programs, and for reasoning about memory allocation and deallocation. Some starting points:

A Syntax-Directed Hoare Logic for Object-Oriented Programming Concepts
Separation Logic, does not target OO-languages specifically but applies to the more fundamental problem of reasoning about heap-allocated data.
jStar: Bringing separation logic to Java


Assessing complexity of a language using subset relations

The statement is unlikely to be true since we can deduce NP-hardness for Graph Isomorphism from it (which would imply a collapse of PH to its second level) as follows:

Let SGI be the Subgraph Isomorphism problem which is known to be NP-complete. Then GI is a subset of SGI. Now, take HAMCIRC and define a slightly different version:

ISO-HAMCIRC = $\{ (G_1, G_2) | G_1 \text{ is isomorph to } G_2 \text{ and } G_1 \in \text{HAMCIRC} \}$

It is trivial to see that ISO-HAMCIRC is NP-complete as well.

It follows that ISO-HAMCIRC $\subseteq$ GI $\subseteq$ SGI and therefore GI would be NP-hard assuming the hypothesis holds.


Chordal graphs can be defined as intersection graph of subtrees of any tree.  So the answer to your decision question is trivially YES.  On the construction side, for each subtree $T_v$ of bags (it's convenient and conventional to call the nodes of the tree as bags), you'll have a unique new vertex $v$, which is put into all bags of the $T_v$.


Are bins with more black than white balls negatively 1-correlated?

A good reference is Concentration of Measure for the Analysis of Randomized Algorithms, by Dubhashi and Panconesi.  This is not a standalone proof but shows how you could use the results therein to prove your desired inequality.

We say a set of random variables $X_i, i \in [n]$ are negatively associated if for all disjoint subsets $I,J \subset [n]$, and all nondecreasing functions $f$ and $g$,
$$
\mathbb{E}[f(X_i, i \in I)g(X_j, j \in J)] \leq \mathbb{E}[f(X_i, i \in I)]\mathbb{E}[g(X_j, j \in J)].
$$

By the proof of proposition 3.1 of D&P, the variables $\{B_1, \dots, B_n\}$ and $\{W_1, \dots, W_n\}$ are negatively associated.  By the disjoint monotone aggregation property of negatively associated variables, (p.35 of D&P), $-W_1, \dots, -W_n$ are also negatively associated, and the random variables $B_i-W_j$, over all choices of $i,j$ are as well.  In particular, the set of variables $B_i - W_i$, for any subset $I \subset [n]$ are negatively associated.

Then, per exercise 3.1, or just by applying the above inequality recursively with $f=g=1$,
$$
\mathbb{E}[ \prod_{i \in I}M_i ] \leq \prod_{i\in I}\mathbb{E}[ M_i],
$$
from which your inequality follows.


Making SAT solvers competitive with specialized algorithms

There is a nice paper that helps visualize the internal structure of SAT instances. See Visualizing SAT Instances and Runs of the DPLL Algorithm by Carsten Sienz (Appeared in SAT 2004). Basically, it draws a graph which the author calls "variable interaction graph" (according to some rules) to visualize the relation between the satisfied clauses. The author shows this by several partial runs of DPLL.

The main claim is that these visualization techniques could be used to detect structure and design an appropiate algorithm for it. However, it is still not clear how can we detect efficiently structures like the one presented in the paper. It is well known that SAT algorithms for one specific problem behave poorly in other problems. So there is "no-free-lunch", although this claim cannot be formally stated as far as I know.


Is it possible to unambiguously read back λ terms from interaction nets without node types?

So, yes, turns out it is possible, as can be seen on the decode function of my abstract algorithm implementation here. Basically, Lambda and Apply nodes are given the same tag (here, I use 0), and you can infer which is the case based on their positions. Each Duplication node, though, requires an unique tag. Note some terms such as (2 2) will reduce to a net which has Duplication nodes with the same tag. That is not an issue; when decoding, just treat anything with a tag different from 0 as a Duplication node.


What does a tangible Quantum-Gate look like?

You seem to have the idea that a quantum gate is a physical thing rather than just a conceptual thing. It doesn't  necessarily work that way. While CMOS  gates are usually actual physical devices, quantum gates may be just conceptual.

Consider an ion trap. The ions represent qubits by using one electronic state as a $|0\rangle$ and another as a $|1 \rangle$. A quantum gate is performed by applying a $4 \times 4$ unitary matrix to two of these ions. This is done by shining a sequence of laser pulses on the ions. It's not a physical device into which two ions are input, in which they interact, and out of which the ions come with their states changed.

Quantum gates are performed by shining laser pulses on the ions, but there's not necessarily one laser per quantum gate—the same lasers are used for many different quantum gates. Thus, you can't point to any specific piece of hardware and say "this is the quantum gate".

And if you use flux qubits in superconductors for your quantum computer, the quantum gates don't use lasers at all, and they look completely different (and slightly more like CMOS devices).


Total number of spanning trees of a set of graphs

Can't this problem be used to compute the permanent of a 0-1 matrix? Since permanent is a #P-complete problem (harder than NP), there is very unlikely to a polynomial-time algorithm.

Suppose you have an $n \times n$ matrix $M$ that you want to compute the permanent of. Construct a graph on $2n+1$ vertices, where there is a special vertex $v$ which has one copy, and $n$ of the vertices $x_1$ $\ldots$, $x_n$ have only one copy, while the remaining $n$ vertices $y_1$, $\ldots$, $y_n$, have $n$ copies each. On the $i$'th copy of vertex $y_j$, connect it to $x_i$. Connect the $i$'th copy of $y_j$ to $v$ if and only if the entry $M(i,j) = 1$.

Now, for $x_i$ to be in the spanning tree, you must have chosen the $i$'th copy of $y_j$ for some $j$. So we must have a permutation $\pi$, where we have chosen the $\pi(j)$ copy of vertex $y_j$. For this permutation to be a spanning tree we must have $M(\pi(j), j) = 1$ for each vertex $j$. This shows that the permutation $\pi$ yields a spanning tree if and only if it contributes $1$ to the permanent of $M$. Thus, the number of spanning trees is the permanent of $M$.


The variant of the problem you're referring to is very close to a problem called the $0$-extension problem: it's a special case of a class of problems called 'metric labelling'. In this class of problems, you're given a weighted graph $G = (V, E, w)$, a set of labels $L$, an assignment cost of labels to vertices $c : V \times L \rightarrow R$, and a "discrepancy cost" $d : L \times L \rightarrow R$. The goal is to assign labels to vertices so as to minimize the sum of the assignment costs and the discrepancy cost for the labels on an edge (weighted by the edge weight). In short, find a labelling $l : V \rightarrow L$ to minimize

$$ \sum_{i \in V} c(i, l(i)) + \sum_{(u,v) \in E} d(l(u), l(v)) \cdot w((u,v))$$

In your problem, the assignment cost is zero, and the label "discrepancy" function is the delta function on labels.

One complicating factor here is that the metric labelling family of problems, the label discrepancy is usually a distance, whereas here it's a similarity measure.


"forward-secure" zero knowledge protocols

Regarding the prover's witness, the standard zero-knowledge (ZK) definitions already imply that ZK holds even if the distinguisher is given this witness.

I'm not sure what you mean by "the random bits used by the algorithm that generated the auxiliary input". Please clarify.


What kind of mathematical background is needed for graph theory?

There are plenty of good books on graph theory. Start with something introductory like Graph Theory: Modeling, Applications and Algorithms, or one of the many more or less equivalent books at that level. Then move onto something more advanced, such as

Graph Theory: An Advanced Course (Graduate Texts in Mathematics) by Adrian Bondy and U.S.R. Murty,
Modern Graph Theory (Graduate Texts in Mathematics) by B. Bollobás or
Graph Theory (Graduate Texts in Mathematics) by Reinhard Diestel.

Also building on your background in discrete mathematics is invaluable. A book such as

Concrete Mathematics: Foundation for Computer Science by Ronald L. Graham, Donald E. Knuth, Oren Patashnik

would be provide you will a solid grounding.

Most of these books would then serve as references for life.

See also this question What kind of mathematical background is needed for complexity theory?, as much of the background will overlap, in particular wrt combinatorics and stochastics (probability and statistics).


Perfectly matchable edges in a bipartite graph

It's a consequence of Dulmage-Mendelsohn decompositions.


Practical limits of big-O performance scaling

While I'm not entirely sure what you're getting at, there are a number of frameworks that explicitly capture the cost changes that show up when we hit real resource limits. Three examples:

the external memory framework that emphasizes the expense of going to disk (idealized by setting main memory reference costs to 0, and disk reference costs to some fixed constant)
The cache-oblivious model that assumes an unknown cache size and performance hits for going beyond.
The streaming computational model in which only you're only allowed sublinear working storage.

Are these along the lines that you're thinking ?


Why isn't it "enough" to prove induction with one extra "INat" argument?

Let us spell out the informal meaning of INat, IntNat and IndNat2. Suppose we have a predicate P on natural numbers. Say that P is inductive if we can inhabit P Zero and ∀ k . P k -> P (Succ k). Then we have:

NatInd P states "if P is inductive then, for all j : Nat, we have P j"
INat n P states "if P is inductive then P n"
NatInd2 P states: "if P is inductive and for every n we have an i which allows us to inhabit inductive predicates at n, then we can inhabit P n".

As you can see, NatInd2 just sweeps the problem under the rug, because it essentially asks that we give it a way of implementing induction. It is true that we can inhabit INat Zero, INat (Succ Zero), INat (Succ (Succ Zero)), ... but that does not imply that we can inhabit ∀ k . INat k! If you think otherwise, provide a term that does so.

In essence, you just hid the problem a little deeper by introducing a level of indirection. You could have already asked this: I can inhabit an infinite sequence of types NatInd P S Z Zero, NatInd P S Z (Succ Zero), NatInt P S Z (Succ (Succ Zero)), ... – why is this not sufficient to have induction? The answer: because you are suposed to inhabit ∀ n : Nat, NatInd P S Z n, which is not the same thing! The former is truth at the meta-level and the latter is an internal induction principle inside the calculus.

The question revolves around the difference between having an infinite sequence of terms inhabiting

t0 : Q 0
t1 : Q 1
t2 : Q 2
t3 : Q 3
...

versus having a single term

t : ∀ n : Nat, Q n

Given t, we can of course produce t0, t1, t2, etc. But there is generally no way to produce a t if we know that we have the infinite sequence of terms t0, t1, t2, ..., even in the case when there is an algorithm generating the sequence, for such an algorithm may not be expressible in the language (CiC in our case). Is that clear?

In fact, we can show that, given any (sufficiently expressive) strongly normalizing calculus (and a total language in general), there will be an instance of Q : Nat -> * such that we can inhabit each of Q 0, Q 1, Q 2, ... separately, but not ∀ n : Nat, Q n. This just says that no strongly normalizing calculus can express all total computable functions.

Supplemental: The OP is aksing why one needs, ought, or should internalize universal quantifiers. From a programmer's point of view the answer is simply that this is what is needed. Let us consider the practical difference between having an infinite sequence of terms

t0 : P 0
t1 : P 1
t2 : P 2
...

versus a single term

u : ∀ n : Nat, P n

Suppose you want to write a program which reads from the standard input a natural number k and outputs a witness of the statement P k. If we have u then we can do it easily (I am inventing syntax as I go here):

print "Please enter a natural number" ;
let k = input() in
print (u k)

How could we write such a program if instead of u we had a sequence of terms t0, t1, t2, as above? One could attempt something like

print "Please enter a natural number" ;
let k = input() in
if k = 0 then print t0
else if k = 1 then print t1
else if k = 2 then print t2
...

but this will not do because programs cannot be infinite. One could also try to do it as follows, assuming there is an algorithm A which produces the sequence t0, t1, t2 (but this algorithm is not expressible in our programming language):

The programmer asks the user to tell him a natural number.
The user provides a natural number k.
The programer runs A to get the expression tk of type P k.
The programer writes down the program print (u tk) and runs it.

We can see quite plainly that the programmer is now doing the job of the program, i.e., everything has moved to the meta-level, which is not what we want. We want the machines to do the job for us. You could also use a programming language which can express the algorithm A, but then you've switched to a different programming language and your algorithm A will correspond to the original program u.

The program u is needed because we must be able to compose and combine it with other pieces of code where it is not known in advance how u will be used.

We can also take the logical point of view. What is the difference between having at our disposal an infinite sequence of proofs

t0 : P 0
t1 : P 1
t2 : P 2
...

versus a single proof

u : ∀ n : Nat, P n

When we inspect u and verify that it is valid, we have provided evidence that P holds for all numbers. In contrast, the sequence of proofs t0, t1, t2, ... is not a finite amount of information, and so it cannot be verified and validated in finite time. Such infinite amount of information does not provide evidence that P holds for all numbers, at least not according to the standard that evidence in mathematics means proof. A proof by definition is finite and verifiable.

You may try to save the day by saying something like "but if we verify the algorithm that produces the sequence t0, t1, t2, ... then we will know that P holds for all n". This is true, but again, you're switching to the meta-level in which the verification that the algorithm works corresponds to having the proof u.


Why does deterministic recognition of DYCK(2) languages in the streaming model take linear space?

Consider the restricted case in which the opening parentheses all come before the closing ones. Map ( and ) to 0, and [ and ] to 1. Then (after the map) an expression is well formed if and only if the first half is equal to the second half reversed.

Consider then a one-pass streaming algorithm that solves this restricted version of the problem in sublinear space. Using the construction in your question, to get a protocol for the equality problem with sublinear communication, Alice runs the streaming algorithm on her input (mapping 0 to ( and 1 to [), sends the working space to Bob, and Bob finishes off using the reverse of his input (mapping 0 to ) and 1 to ]). The streaming algorithm will output that the sequence of parentheses is well formed iff their original inputs are equal.


What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?

Why do you think simulating quantum physics means that you have to efficiently implement arbitrary quantum $n$-way interactions? If that's your requirement, quantum computers cannot do it efficiently.

You can write down an $n$-way unitary gate which implements an arbitrary $n$-bit-input $n$-bit-output function. This would let us solve an arbitrary problem on $n$ bits in one step. It is common sense that we can't find quantum systems in "real life" that will let us do this.

Of course, in actual quantum physics, quantum dynamics is Hamiltonian and not just unitary, but there are still roughly $2^n$ parameters in an arbitrary $n$-way Hamiltonian, and doing this using 2-qubit gates (which have a constant number of parameters each) will require an exponential number of gates. Furthermore, I am fairly sure that the ability to implement arbitrary $n$-way Hamiltonians would still let you construct arbitrary binary functions on $O(n)$ bits.

So the requirement you pose for quantum computers to efficiently simulate arbitrary $n$-way interactions is much too strict. What you need is that quantum computers can efficiently simulate the $n$-way interactions that actually arise in quantum physics. Quantum computers are able to efficiently simulate $k$-local Hamiltonian dynamics for constant $k$, which may be enough to simulate interactions that arise in real quantum physics.

If you can suggest any $n$-way interactions that arise in quantum physics that  appear difficult for a quantum computer to simulate efficiently, this would be a truly exciting development. However, I don't know of any current suggestions for such interactions.

Whether quantum computers can efficiently simulate quantum field theory is still an open question, but progress is currently being made on it.


What machine learning classifiers are the most parallelizeable?

There have been efforts to parallelize most of the well-known classifiers, including boosting [a paper], SVM [a paper], and even decision trees [a paper].  Of course, by admitting parallelism, you sometimes lose out on other aspects, whether it be algorithm implementability, sample complexity, or other usual suspects.

From the theory end, the question is harder because when you talk about learning you have to think about the target function.  For example, we don't even know decision trees to be PAC-learnable, so if the target (as well as the method) is a decision tree, then we can't even learn it (yet) without introducing extra facets to the problem.  Boosting gets around that by assuming a weak learning condition, SVM a margin, etc. I think those assumptions transfer to the parallel case to give you PAC learning.

But as always, there's a big gap between the frontiers (and thereby concerns) of theory and of practice.   For example, in practice, it matters whether the parallelism is over cores or clusters.  One algorithm developed especially for practical use in large-data settings is VW, and it's starting to support parallelism.  You might be interested in the papers in the NIPS 2010 workshop on practical parallel learning.


The RL-complete problem of reachability in directed graphs with polynomial mixing-time (shown by Reingold, Trevisan, and Vadhan in Pseudorandom walks on regular digraphs and the RL vs. L problem) is in $\log^{3/2}(n)$ space (see $\text{BPHSPACE}(S) \subseteq \text{DSPACE}(S^{3/2})$ by Saks and Zhou), which is strictly between L and Savitch's bound on NL of $O(\log^2 n)$ space.


Logic programming with integer or even floating point domains

The first question can be solved by googling integer logic programming.

http://en.wikipedia.org/wiki/Constraint_logic_programming

The second question is called the theory of expert programming. I was also able to google this.

http://en.wikipedia.org/wiki/Expert_system

There is a practical need for expert systems and rule based systems. They are used in many domains as you can see from here.

http://en.wikipedia.org/wiki/Expert_system#Examples_of_applications


Lighting up all elements of a poset by toggling upsets

Co-worker here. We haven't solved it yet, but here are a few remarks (in case it gives anyone an idea, because we are stuck).

The main thing we have for now is a partial result on so-called crown-free lattices. To show it, for two elements $x,y$ of the poset $P$, I say that $x$ is covered by $y$ if $x\geq y$, $x \neq y$, and there are no elements in between (i.e., $y$ is just above $x$ in the Hasse diagram of $P$). Let me now show claim (*): we can then assume without loss of generality that $P$ is such that:

there are no elements $x$ of $P$ that cover exactly one element; and
for every minimal element $x$ of $P$, $x$ is covered by at least two elements.

I will show this by taking a poset $P$ such that it has an $x$ satisfying condition 1. or 2., and then considering the poset $P'$ where we have removed $x$, and show that if $P'$ is winnable then so is $P$. Assume first that $x$ satisfies 1., and let $\mathbf{s}$ be a winning sequence for $P'$ (a sequence of moves that goes from $\emptyset$ to $P'$). Then it is easy to see that $\mathbf{s}$ is also a winning sequence for $P$; indeed the state of $x$ (on or off) will always follow the state of its unique child, and we never need to click on $x$ (this can also be explained by checking that $\mu_P(x) = 0$), so all moves are valid. Assume now that $x$ satisfies 2., and again let $\mathbf{s}$ be a winning sequence for $P'$. Let $p$ be the unique parent of $x$ in $P$, and let $a = \mu_P(p)$. It is easy to show that $\mu_{P'}(p) = a+1$ and that $\mu_{P'}(y) = \mu_P(y)$ for all $y \in P'$, $y \neq p$. I then consider two cases:

$a<0$. We can then obtain a winning sequence for $P$ as follows: first, play an on-move on $x$, then play an off-move on $p$ (this is legal since $a<0$), and then play the sequence $\mathbf{s}$. Observe that we have $a+1 \leq 0$, so in the whole sequence we will only play off-moves on $p$, and it is clear that all the moves are valid and that we end up with everything being on, so that this is indeed a winning sequence for $P$.
$a \geq 0$. In this case $a+1>0$, which mean that in $\mathbf{s}$ we will only play on-moves on $p$, and we will play at least one. We then obtain a winning sequence for $P$ as follows: play the sequence $\mathbf{s}$, but the very first time we play an on-move on $p$, play an on-move on $x$ instead. Again, it is easy to see that this is indeed a winning sequence for $P$.

This concludes the proof of claim (*).

If we look at the first example in the question, we can deal with it using claim (*): we can eliminate $E$ because it satisfies condition 1., then we can eliminate $A$, $B$ and $C$ (because they satisfy condition 2.), and we end up with only one node ($D$), and this is clearly a poset that is winnable. However for the second example in the question, we can eliminate $G$ (it satisfies condition 2.), but then there is nothing to eliminate, so here he'd need something else to show that $P'$ is winnable.

Claim (*) implies in particular that join-semilattices that are obtained from dismantable lattices by removing the bottom element are winnable; these are lattices that can be emptied by recursively removing the doubly irreducible elements, see
Kelly, David; Rival, Ivan, Crowns, fences, and dismantlable lattices, Can. J. Math. 26, 1257-1271 (1974). This paper shows in particular that dismantable lattices are exactly the lattices that are crown-free (see the paper for the definition), so if we want to solve our problem for join-semilattices only (instead of for all posets), it becomes equivalent to the following:

Can we win for every join-semilattice that has a crown? (Note that the second example in the question is a join-semilattice that has a crown).

Other than claim (*), we have some code (there) to decide if a given poset is winnable or not, and if yes to visualize the winning strategy. In particular we have generated a lot of join-semilattices and found no counter-example so far.

We are also working on a generalization of this problem: see this note.


Is there a lower bound of number of redundant bits necessary to encode a word with certain Hamming distance?

As Tsuyoshi points out in the comments, there are a number of such bounds. However, for the sake of actually giving you an answer, let me point you to the Singleton bound, which states that for a $(s,N,d)$-code over $\mathbb{F}_b$ that $N\leq b^{s-d+1}$.


Applications of Spectral Graph Theory in Information and Coding Theory

Cayley graphs of codes and derandomized code products can be a good example. See the following thesis (Chapter 6) for details and references: http://library.epfl.ch/en/theses/?nr=3816


The first paper by Rabin (1963) gives the basics what you are looking for. The class of languages recognized by probabilistic automata (with cutpoint) is called stochastic languages.

Let $P$ be a probabilistic automaton defined on the alphabet $ \Sigma $ and $ f_P(w) $ be the accepting probability of $ P $ on the input $ w \in \Sigma^* $. Then, $P$ with cutpoint $\lambda \in [0,1)$ defines the following language:

  $ L(P,\lambda) = \{ w \in \Sigma^* \mid f_P(w) > \lambda \}  $.

Remark that the recognition with cutpoint can be seen as recognition with unbounded error. In case of bounded-error (or isolated cutpoint) probabilistic automata can recognize all and only regular languages.

The book by Paz (1971) and the survey by Bukharaev (1980) are good references.

You can also check a recent survey on quantum automata where you can trace some references on probabilistic automata.


Complexity Classes - separations and inclusions

I like Papadimitriou's book.

Specially, it has "Class Review" sections at the end of several chapters, illustrating the relations among complexity classes.

The relevant sections are:

 Section 10.4.1 (page 235): P, NP, coNP.
 Section 11.5.1 (page 272): P, ZPP, RP, coRP, BPP, NP, coNP, PP.
 Section 15.5.1 (page 385): AC, NC, RNC, P.
 Section 16.4.1 (page 405): NC$_1$, L, SL, RL, SC, NL, PolyL, P.
 Section 17.3.1 (page 433): PH and PSPACE.
 Section 20.2.1 (page 499): P, NP, coNP, PSPACE, EXP, NEXP, coNEXP, EXPSPACE, 2-EXP, ELEMENTARY, R.

The book also includes a nice take on time- and space-hierarchy theorems; see Chapter 7.

EDIT: I also recommend Complexity Zoo's Active Inclusion Diagram (requires Firefox 1.5 or later, or Opera 9 or later). If you don't have that, you may try Zoo's Static Inclusion Diagram.


Almost regular subhypergraph of hypergraph with large minimal degree

Unfortunately the conjecture is wrong (for $d \geq 2$). Here is a counterexample for $d=2$.

Suppose that the conjecture (in its graphical formulation) held for some $c,M_0 > 0$. Consider a complete bipartite graph in which the left side has $M^2$ vertices and the right side has $M$ vertices. Thus the left degrees are $M$ and the right degrees are $M^2$. In order to create a subgraph in which all right degrees are at most $M$, we need to remove at least $M(M^2-M)$ edges. On the other hand, any subgraph in which all left degrees are at least $cM$ must have at most $(1-c)M^3$ edges removed. This means that $M^3 (1-1/M) \leq (1-c)M^3$, which is false for large enough $M$.


Martin Grohe made substantial progress on this question recently. He gives a logic capturing polynomial time on classes of graphs embeddable in a fixed surface: https://dl.acm.org/citation.cfm?doid=2371656.2371662
Edit: the general case seems to be unresolved (but I am by no means an expert on this).


It turns out the answer is no, some counter-examples can be found in this paper.
Also here is a more recent work showing that such Büchi automata can be recognized in polynomial time.


Are there intermediate eta theories for the lambda calculus?

For typed calculi, if you consider the negative types ($1$, $\times$, $\to$), you can turn the eta rules on or off basically at will without affecting confluence.

For positive types (sums, and pairs with the pattern-matching elimination), the situation is much messier. Basically, the question is whether the term has a closed-scope elimination form, which let contexts interact in complicated ways with eta-expansions. For example, if $e$ has type $A \times B$, then its eta-expansion is $\mathsf{let}\;(a,b) = e \;\mathsf{in}\; (a,b)$. But to get the equational theory a category theorist would expect, you need to consider contexts $\mathbb{C}[-]$, and generalize the equation to be $\mathbb{C}[e] \equiv \mathsf{let}\;(a,b) = e\;\mathsf{in}\;\mathbb{C}[(a,b)]$ (with the expected scoping restrictions).

I think that you can still prove a confluence result if you don't allow the commuting conversions. But this is hearsay -- I've never tried it myself, nor looked at papers documenting it.

I don't really know anything about untyped lambda calculus, though.

EDIT: Charles asks about eta-reductions. This is promising for the kind of example he seeks, because I think in general they won't be strong enough to model the full equality theory, which I'll illustrate with a simple example involving booleans. The eta-expansion for booleans is $\mathbb{C}[e] \mapsto \mathsf{if}(e, \mathbb{C}[\mathsf{true}], \mathbb{C}[\mathsf{false}])$. (The eta-reduction is of course the other direction.)

Now, consider the term $\mathsf{if}(e, f, g)\;\mathsf{if}(e, x, y)$. Showing that this term is equivalent to $\mathsf{if}(e, f\;x, g\;y)$ needs to go through an eta-expansion, because we have to replace the $e$ in one of the if-then-elses with $\mathsf{true}$ and $\mathsf{false}$ in order to drive a $\beta$-reduction.


Graph-theoretic properties of the Wiener index

On the same page there was a section: relation to chemical properties (http://en.wikipedia.org/wiki/Wiener_index#Relation_to_chemical_properties) Maybe references in that section mentions more about how this index can be used for graphs. Seems like you can estimate the overall structure of the graph if it is dense (low index) or sparse. Because the lengths of all shortest pairs would be shorter in a dense graph.


Can $\{a^nb^n\}$ be recognized in poly-time probabilistic sublogarithmic-space?

I have found an answer to my own question. The result was given in Section 5 of Karpinski and Verbeek, 1987.

For any input of length $ n $, a PTM can construct $ \Theta(\log \log n) $ space with high probability (Section 4). (With a very small probability, the machine can also construct logarithmic space, and this might be seen as a "drawback" of the algorithm.) Then, the PTM can decide whether the numbers of $a$'s ($n$) and $b$'s ($m$) are equal with high probability by using $ O(\log \log n) $ space in polynomial time.

The idea is as follows. If $ n \neq m $, then $ \exists k \leq 4 \log(n+m) $ such that $ n \not\equiv m \mod k $ (Alt and Mehlron, 1976). The PTM can pick a random $ k $ by using $ O(\log \log n) $ space. $ O(\log \log n) $ is also sufficient to keep a counter and so trying more than half of all possible $k$'s. The case of $ n \neq m $ can be detected with a probability more than $ 1 \over 2 $.


Techniques for proving NP completeness for a specific sequence of instances

If I understand the question correctly, I think that you are essentially asking whether a problem can be NP-hard even when it is defined on a sparse set of input strings.  If your notion of NP-hardness is under polynomial-time many-one reducibility, such a problem cannot exist (unless P=NP) because of Mahaney’s theorem.

See a blog article about Mahaney’s theorem by Lance Fortnow for a nice explanation of Mahaney’s theorem and related results.


Validity of exponentiation in a polynomial time reduction

The proof as presented in the paper is not conclusive.

However, the stated result itself is correct. It can easily be derived by slightly changing the reduction and by using SUBSET PRODUCT instead of SUBSET SUM.

A useful link for the SUBSET PRODUCT problem:
https://cs.stackexchange.com/questions/7907/is-the-subset-product-problem-np-complete


The first positive example will remove enough literals so that the conjunction will become satisfiable.  For example if the first positive example is $x_1\overline{x_2}x_3$ this removes $\overline{x_1}$, $x_2$ and $\overline{x_3}$. So the only time you will end up with an unsatisfiable clause is if you get only negative examples, which is okay, as the correct thing to do is to classify everything as negative anyway.

Also remember that in PAC learning, the learner gets to choose how many examples to see -- so you generally don't have to worry about "not getting enough examples" (as long as you need a number of examples polynomial in the number of relevant parameters).


Minimizing Automata accepting $\omega$-words (i.e. infinite words)

This question generated a lot of literature in the 80's, partly due to a bad approach to the problem. This is a rather long story that I will try to summarize in this answer.

1. The case of finite words

One can find two definitions of a minimal DFA in the literature.
The first one is to define the minimal DFA of a regular language as the complete DFA with the minimum number of states accepting the language.
The second one is longer to define but is mathematically more appealing than the first one and it gives stronger properties.

Let us recall that a DFA $(Q, A, \cdot, i, F)$ is accessible if for all $q \in Q$, there is a word $u \in A^*$ such that $i \cdot u = q$. It is complete if $q \cdot a$ is defined for all $q \in Q$ and $a \in A$.

Let ${\cal A}_1 = (Q_1, A, \cdot, i_1, F_1)$ and ${\cal A}_2 = (Q_2, A,
\cdot, i_2, F_2)$ be two complete, accessible DFAs. A morphism from $\mathcal{A}_1$ to $\mathcal{A}_2$  is a function $\varphi:Q_1 \to Q_2$ such that

$\varphi(i_1) = i_2$,
$\varphi^{-1}(F_2) = F_1$,
for all $q \in Q_1$ and $a \in A$, $\varphi(q)\cdot a=\varphi(q\cdot a)$.

One can show that these conditions imply that $\varphi$ is necessarily surjective (and thus $|Q_2| \leqslant |Q_1|$). Furthermore, there is at most one morphism from ${\cal A}_1$ to ${\cal A}_2$ and if this morphism exists, then ${\cal A}_1$ and ${\cal A}_2$ recognize the same language. Now, one can show that for every language $L$, there is a unique complete accessible DFA ${\cal A}_L$ accepting $L$ and such that, for every complete accessible DFA $\cal A$ accepting $L$, there is a morphism from $\cal A$ onto
${\cal A}_L$. This automaton is called the minimal DFA of $L$. Note again that since
the number of states in ${\cal A}_L$ is smaller than the number of states in $\cal A$, ${\cal A}_L$ is also minimal in the first sense.

It is worth mentioning that there is also a suitable algebraic definition for incomplete DFAs. See [Eilenberg, Automata, Languages and Machines, vol. A, Academic Press, 1974] for more details.

2. Back to infinite words

Extending the first definition does not work, as shown by Shaull in his answer. And unfortunately one can also show that the universal property of the second definition does not extend to infinite words, except in a few particular cases.

Is it the end of the story? Wait a second, there is another minimal object that accepts regular languages...

3. The syntactic approach

Let us first return again to finite words. Recall that a language $L$ of $A^*$ is
recognized by a monoid $M$ if there is a surjective monoid morphism
$f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$. Again, there exists a monoid $M(L)$, called the syntactic monoid of $L$, which recognizes $L$ and is a quotient of all monoids recognizing $L$. This syntactic monoid can be defined directly as the quotient of $A^*$ by the syntactic congruence $\sim_L$ of $L$, defined as follows:
$$
  \text{$u \sim_L v$ if and only if, for all $x, y \in A^*$, $xuy \in L \iff xvy \in L$}
$$
The good news is that this time, this approach has been extended to infinite words, but it took a long time to discover the appropriate notions.
First, the suitable notion of a syntactic congruence was found by A. Arnold (A syntactic congruence for rational $\omega$-languages, Theoret. Comput. Sci. 39,2-3 (1985), 333–335).
Extending syntactic monoids to the setting of infinite words required a more sophisticated type of algebras, called nowadays Wilke algebras in honor of T. Wilke, who was the first to define them (T. Wilke, An algebraic theory for regular languages of finite and infinite words, Int. J. Alg. Comput. 3 (1993), 447–489). More details
can be found in my book Infinite words coauthored with D. Perrin.

4. Conclusion

Thus there is a mathematically sound notion of a minimal object accepting a given regular $\omega$-language, but it does not rely on automata.
This is actually a rather generic fact: automata are a very powerful algorithmic tool, but they are not always sufficient to treat mathematical questions on languages.


How fast can we solve a totally unimodular integer linear program?

I believe On a class of totally unimodular matrices, by Yannakakis, gives an answer to your question for a special case of TU ILP (whenever there are no odd cycles in a bipartite graph obtained by seeing the coefficient matrix as an adjacency matrix).

In that paper there is a reference to Polynomial algorithms for a class of linear programs, which seems to handle all totally unimodular matrices, but I am not sure about how much more efficient it is compared to generic algorithms for LPs.


Well-formedness condition for inductive types

Inductive types have been studied heavily and many variants exist. A well-known introduction to inductive definitions is

P. Aczel, An Introduction to Inductive Definitions

which was originally published in the indispensable Handbook of Mathematical Logic, but is now available online stand-alone. An introduction to inductive types is

T. Coquand, P. Dybjer, Inductive Definitions and Type Theory: an Introduction.

The theory of inductive definitions for Coq was first (?) approached in

F. Pfenning, C. Paulin-Mohring, Inductively defined types in the Calculus of Constructions,

I don't know to what extend modern Coq has diverged from what's described in that paper. Either way, none of those is easy reading. You're probably better off to look at a Coq manual and copy the well-formedness conditions imposed there.


Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$

To answer the first part of your question, a conjecture in Karp'76 states that there is no efficient algorithm to find cliques of size $(1+ \epsilon)\log(n)$ for $G(n, 1/2)$. This conjecture is still open.


An example would be the computation of ground state energy of the Ising model with transverse magnetic fields, as described by [Cubitt+Montenaro-2013]. From the abstract:

  In this work we characterise the complexity of [the calculation of ground-state energies of 2-body Hamiltonians on qubits with terms restricted to some fixed set S]. Depending on the subset S, the problem falls into one of the following categories: in P; NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. The third of these classes contains NP and is contained within StoqMA.


I think the most spectacular example of this approach is Thomas Hales' proof of the Kepler conjecture (aka Hilbert's 18th problem).

In the 1950s, Fejes Toth proved that the Kepler conjecture was equivalent to a large collection of formulas in the first-order theory of real closed fields. Since Tarski had shown this theory to be decidable, he went on to speculate that if a sufficiently fast computer could be built, the Kepler conjecture could be resolved by machine.

Half a century later, Thomas Hales actually made this strategy work (after proving a lot of difficult theorems to further simplify the set of formulas the computer needed to check)!


Best way to determine the minimum dimension of a structure given only distances between points

This problem is sometimes called the low-dimensional Euclidean distance matrix completion or the low-dimensional Euclidean embedding of a weighted graph.

Saxe [Sax79] and Yemini [Yem79] independently showed by a simple reduction from the Partition problem that this problem is NP-complete even in the case of one dimension; that is, the following problem is NP-complete for k=1:

k-dimensional Euclidean distance matrix completion / k-dimentional Euclidean embedding of a weighted graph
Instance: A symmetric matrix M whose entries are either positive integers in binary or “unknown.”
Question: Can the unknown entries in M be filled by real numbers so that M becomes a distance matrix of points in the k-dimensional Euclidean space ℝk?
Equivalently,
Instance: A graph G where each edge has a positive integer weight written in binary.
Question: Can the vertices of G placed in the k-dimensional Euclidean space ℝk so that for each edge of G, the distance between the two endpoints equals to the weight of the edge?

Moreover, Saxe [Sax79] showed (by a more involved reduction from 3SAT) that the k-dimensional Euclidean distance matrix completion remains NP-hard even under the restriction that all known entries in M are either 1 or 2, for every positive integer constant k.  In particular, the problem is NP-complete even when the known entries in M are given in unary.  [Sax79] also contains some hardness results about approximate embedding.

By the way, I do not think that it is trivial that the problem is in NP; note that you need irrational coordinates in some cases when k>1.  I do not know if it is known to be in NP.

References

[Sax79] James B. Saxe.  Embeddability of weighted graphs in k-space is strongly NP-hard.  In Proceedings of the 17th Allerton Conference on Communications, Control, and Computing, pp. 480–489, 1979.  Also in James B. Saxe: Two Papers on Graph Embedding Problems, Department of Computer Science, Carnegie-Mellon University, 1980.

[Yem79] Yechiam Yemini.  Some theoretical aspects of position-location problems. In 20th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1–8, Oct. 1979.  DOI: 10.1109/SFCS.1979.39


Type theories have multiple uses, and with each kind of usage comes a different
notion of correctness. They two key uses are

As a foundation of mathematics. In this context correctness means
primarily that we can't deduce falisity.
As a tool in programming. Here correctness means primarily that that
well-typed programs "don't go wrong" in Milner's famous words, i.e. that they do not
exhibit a certain forms of error, such as trying to execute 3 +
"hello".

Both notions of correctness are related, but not the same.

Gödel's second incompleteness theorem puts serious restrictions in the way of showing the 'correctness' of type theories as a foundation of mathematics. The best you can hope for is to show 'correctness' (understood as consistency) relative to some other foundation, e.g. by giving a set-theoretic model.

The key thing we worry about with type theories is  that a given type-theory is inconsistent because we can define a non-terminating term. Modern type-theories are fairly complicated beasts, and it's quite easy to make them too powerful  so  that a fix-point combinator
becomes definable. Such fixpoint combinators inhabit every type, making the type-theory inconsistent as a foundation of mathematics. Since fixpoint combinators can be subtle, it is quite easy to overlook how one's typing system allows them to be defined. Indeed, famous foundationalists have a habit of
proposing foundations of mathematics that are unsound for this reason.  For example Martin-Löf's original proposal for type-theory made the kind of types itself a type (that approach to typing is now referred to as Type:Type). This is
extremely convenient, and gives you the most general form of impredicative polymorphism. Alas,  Girard discovered that this was unsound, when he managed to express the Burali-Forti paradox in Type:Type, see this discussion for more details.  Every since, Martin-Löf's type theories have been predicative, but with added inductive definitions to recover (much of) the expressive power of impredicativity.

Encoding a type theory in another foundation such as set theory gives us a fuzzy feeling of security: it says there are unlikely to be  an obvious unsoundness bugs in our type-theory. The justification behind this intuition is strictly empirical (!): in the century of since Cantor invented and Zermelo formalised it, nobody has found a soundness bug in conventional set theory. (As an aside, this situation is similar to cryptography where we trust RSA, Diffie-Hellman, AES or 3DES for little other reason than that they have withstood sustained attempts at breaking.)

Note that while a system with Type:Type is wrong as a foundation of
mathematics, it is perfectly acceptable as a typing system for
programming languages, because we can still show that no typeable program goes "wrong".

Regarding proof techniques for correctness, the different properties you mention relate to different notions
of correctness. Termination is the key step to showing correctness
of a type-theory as a foundation of mathematics, while subject
reduction is usually the key step to showing that a type-theory
is usable as a tool in programming. Note that since a termination
proof is the high-road to consistency as a foundation, by
Gödel's second incompleteness theorem, we can prove termination of a type-theory only by using a stronger system.


Computing topological sort while keeping edges "short"

Your problem is known under the name MINIMUM DIRECTED BANDWIDTH.
It is NP-complete:

  M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth:
  "Complexity Results for Bandwidth Minimization"
  SIAM Journal on Applied Mathematics 34, (1978), pp. 477-495

It is problem [GT41] in the NP-completeness book by Garey and Johnson.

The special case where every vertex in $G=(V,E)$ has indegree $\Theta(|V|)$ has a polynomial time approximation algorithm with worst case guarentee 2:
https://www.nada.kth.se/~viggo/wwwcompendium/node54.html


Is there a relationship between computational complexity theory and complex systems theory?

This paper by Kanter, Kopelowitz, and  Kinzel, Public Channel Cryptography: Chaos Synchronization and Hilbert’s Tenth Problem shows that there is a strong connection between nonlinear dynamics and NP-complete problems with the promise of novel secure public-channel protocols.

Phys. Rev. Lett. 101, 084102 (2008)


Recommendation for a good book on first order logic w.r.t inductive logic programming

How about foundations of disjunctive logic programming? While rather old (1992), it has over 100 examples. For instance, SLI and SLD resolutions are discussed and exemplified in section 4.2.

PS: You may read some parts of that section on Google Books.


Differential Privacy and Randomized Responses for Counting Queries

You have $\mathbb{E}[y_i]=\epsilon q(x_i) + (1-\epsilon)/2$ and $0 \leq y_i \leq 1$, with all they $y_i$s being independent. Thus the Chernoff-Hoeffding bound gives
$$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n y_i -\epsilon q(x_i) - \frac{1-\epsilon}2\right| \geq \lambda\right] \leq 2 \cdot e^{-2\lambda^2 n}$$
for all $\lambda>0$. Multiply through by $1/\varepsilon$ to get
$$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n \frac{1}{\epsilon}\left(y_i  - \frac{1-\epsilon}2\right)-q(x_i)\right| \geq \frac{\lambda}{\epsilon}\right] \leq 2 \cdot e^{-2\lambda^2 n}.$$
Set $\lambda=\sqrt{\log(2/\delta)/2n}$ and substitute in $q(x)=\frac{1}{n}\sum_{i=1}^n q(x_i)$ to get
$$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n \frac{1}{\epsilon}\left(y_i  - \frac{1-\epsilon}2\right)-q(x)\right| \geq \frac{\sqrt{\log(2/\delta)}}{\epsilon\sqrt{2n}}\right] \leq \delta.$$
Now "suppress" the $\delta$ parameter using big-O notation to get
$$\left|\frac{1}{n} \sum_{i=1}^n \frac{1}{\epsilon}\left(y_i  - \frac{1-\epsilon}2\right)-q(x)\right| \leq O\left(\frac{1}{\epsilon\sqrt{n}}\right)$$ with high probability, as required.


It all depends how deep you want to go, and how much you already know. For a beginner Winksel's book is really nice, but yes, it's not introducing you to the state of the art in semantics as it was written about 20 years ago. Nevertheless it's still a good first introduction to the subject. It might also be worthwhile pointing out that T. Nipkow has formalised a substantial chunk of Winskel's book in Isabelle/HOL, see here. So if you want to learn using interactive proof assistants together with understanding the semantics of programming languages, you have a lot of coherent material to draw on.

Other books that are more advanced are:

Gunter, Semantics of Programming Languages, a more advanced book focussing on denotational semantics, an approach to semantics, which hasn't lived up to expectations. Focusses on purely functional lanugages and ignores concurrency. This is the book that I taught myself semantics from as an undergraduate, and in retrospect I wish I had used Winksel's book instead. Gunter is not an easy read for a beginner.
Domains and lambda-calculi by Amadio and Curien. Another book coming written more in the domain-theoretic tradition, although it discusses process calculi.
John Mitchell's books which have already been mentioned above. They are also mostly about sequential computation.

Books like Pierce's TAPL are very nice, but focus narrowly on one aspect of programming languages, namely types, as important as that is. I would not recommend it as a first introduction to the general area of programming languages, but it is mandatory to read for anyone who wants to learn about types.

Truth be told, I think there's currently no up-to-date introductory book on language semantics that reflects the substantial progress the last decade has seen, with its decisive shift away from denotational methods and sequential computation to concurrency (process calculi and game semantics), axiomatics semantics and the use of interactive proof assistants in verification.

Update 22. April 2014: Tobias Nipkow and Gerwin Klein have published a new book

Concrete Semantics

which can be seen as 'Winskel in Isabelle/HOL'. It's an introduction to the
semantics of programming languages (primarily operational and
axiomatic) but unlike previous pen-and-paper-based approaches, this
book expresses all its mathematics in Isabelle/HOL. In other words,
it's at the same time a book about theorem proving.

The book is brand new so I have not used for teaching, but it looks really suitable
as an introduction that is pitched at a lower level than Software Foundations
by
Pierce et al.


In the following paper my colleague Uli Schöpp presents a formal verification (in Coq)  of a nontrivial result by Cook and Rackoff on the computational power of graph automata. https://scholar.google.at/scholar?oi=bibs&cluster=4944920843669159892&btnI=1&hl=de (Schöpp, U. (2008). A formalised lower bound on undirected graph reachability. In Logic for Programming, Artificial Intelligence, and Reasoning (pp. 621-635). Springer Berlin/Heidelberg.)


Does treewidth $k$ imply the existence of a $K_{1,k}$ minor?

It is indeed true that every graph $G$ with no $K_{1,k}$ minor has treewidth at most $k-1$. We prove this below, first a few definitions:

Let $tw(G)$ be the treewidth of $G$ and $\omega(G)$ be the maximum size of a clique in $G$. A graph $H$ is a triangulation of $G$ if $G$ is a subgraph of $H$ and $H$ is chordal (i.e has no induced cycles on at least $4$ vertices). A triangulation $H$ of $G$ is a minimal triangulation if no proper subgraph of $H$ is also a triangulation of $G$. A subset $X$ of vertices of $G$ is a potential maximal clique if there exists a minimal triangulation $H$ of $G$ such that $X$ is a maximal clique of $H$. It is well known that
$$tw(G) = \min_{H} \omega(H) - 1$$
Here, the minimum is taken over all minimal triangulations $H$ of $G$.

The above formula implies that to prove that $tw(G) \leq k-1$ it is sufficient to prove that all potential maximal cliques of $G$ have size at most $k$. We now prove this. Let $X$ be a potential maximal clique of $G$, and suppose that $|X| \geq k+1$.

We will use the following characterization of potential maximal cliques: a vertex set $X$ is a potential maximal clique in $G$ if, and only if, for every pair $u$, $v$ of non-adjacent (distinct) vertices in $X$ there is a path $P_{u,v}$ from $u$ to $v$ in $G$ with all its internal vertices outside of $X$. This characterization can be found in the paper Treewidth and Minimum Fill-in: Grouping the Minimal Separators by Bouchitte and Todinca.

With this characterization it is easy to derive a $K_{1,k}$ minor from $X$. Let $u \in X$. For every vertex $v \in X \setminus \{u\}$, either $uv$ is an edge of $G$ or there is a path $P_{u,v}$ from $u$ to $v$ with all internal vertices outside $X$. For all $v \in X$ that are non-adjacent to $u$ contract all the internal vertices of $P_{u,v}$ into $u$. We end up with a minor of $G$ in which $u$ is adjacent to all of $X$, and $|X| \geq k+1$. So the degree of $u$ in this minor is at least $k$, completing the proof.


Answered by Claude Carlet in a private email. The AND function is bent as long as it has only two variables.


Applications of representation theory of the symmetric group

Here are a few other examples.

Diaconis and Shahshahani (1981) studied how many random transpositions are required in order to generate a near uniform permutation. They proved a sharp threshold of 1/2 n log(n) +/- O(n). Generating a Random Permutation with Random Transpositions.
Kassabov (2005) proved that one can build a bounded degree expander on the symmetric group. Symmetric Groups and Expander Graphs.
Kuperberg, Lovett and Peled (2012) proved that there exist small sets of permutations which act uniformly on k-tuples. Probabilistic existence of rigid combinatorial structures.


Why not expand the HMM to a state graph and apply a k-shortest-paths algorithm to the graph? I have a recent survey on k-best enumeration that includes the k-shortest paths problem at http://bulletin.eatcs.org/index.php/beatcs/article/view/322.


Noisy channel coding theorem in quantum information

You have two questions here.

Why can't Shannon's Noisy Coding Theorem be used for a quantum channel?

What gaps are there to proving a quantum noisy channel coding theorem?

I will concentrate on the first question.
Shannon's noisy coding theorem says that for a memoryless channel,
$$ {\displaystyle \ C=\sup _{p_{X}}I(X;Y)},$$
where $p_X$ is maximized over all probability distributions over the input variable $X$.
If you try to apply this naïvely to quantum channels, you run into a bunch of problems:

The input and the output of a quantum communication channel are never around simultaneously, so the classical definition of $I(X;Y)$ doesn't work at all.
The proof depends on the fact that the channel is a probabilistic map taking the input to the output. This isn't true for quantum channels; a quantum channel is a completely positive trace-preserving linear operator.
Classical channels essentially only have one capacity. There are many different capacities for quantum channels. Are you trying to send classical or quantum information?  Do the sender and receiver have access to quantum entanglement? Can the receiver communicate on a classical channel that sends information back to the sender? Neither of these last two abilities change the capacity of classical channels, but they do change the capacity of quantum channels.
There are two equivalent expressions for mutual information:
$$I(X;Y) =H(X) +H(Y) - H(X,Y) = H(Y) - H(Y|X). $$
The quantum equivalents of these two expressions are not equal. In fact, each of these corresponds to a different quantum channel capacity; the first corresponds to the entanglement-assisted classical capacity  and the second to the Holevo-Schumacher-Westmoreland capacity.

So to summarize, you can't apply Shannon's Noisy Channel Coding theorem directly to quantum channels because not only does the proof not work, but the standard formulation of Shannon's capacity formula isn't even defined for quantum channels, and mutual information has two plausible extensions to the quantum case.
For your second question, there are several different quantum noisy channel coding theorems. The main problem with most of them is that they have a regularization step in them. Instead of getting an answer that you can compute by maximizing over inputs to a single channel use, you get an answer that is difficult to compute: you need to maximize a quantity that depends on $n$ channel uses and divide by $n$, and then take $n$ to infinity. There may not be a single-channel-use formula; even a lot of quantities in classical information theory don't have a single-symbol formula.


Which algorithms are used most often in practice?

Is the Fast Fourier Transform the algorithmic problem solved most times per day by real computer systems?  It has to be close.  So I'd nominate the Cooley-Tukey FFT algorithm.


This is a question of encoding and decoding constant-weight code. There are several possible efficient algorithms for that, that provide different efficiency benefits.

Here's a list of some papers on this field:

Tenkasi V. Ramabadran. A Coding Scheme for m-out-of-n Codes. IEEE Transactions on Communications, 38(8):1156–1163, August 1990.

Vitaly Skachek, Kees A. Schouhamer Immink: Constant weight codes: An approach based on Knuth's balancing method. ISIT 2011: 321-325

Chao Tian, Vinay A. Vaishampayan, Neil J. A. Sloane: A Coding Algorithm for Constant Weight Vectors: A Geometric Approach Based on Dissections. IEEE Transactions on Information Theory 55(3): 1051-1060 (2009)
and its followup
N. J. A. Sloane, Vinay A. Vaishampayan: Generalizations of Schöbi's Tetrahedral Dissection. Discrete & Computational Geometry 41(2): 232-248 (2009)

All three approaches are/seem to be efficient, but concrete approaches are very different. The first paper uses arithmetic decoding/encoding, the second paper generalizes Knuth's algorithm, and the third paper uses a geometric approach.


Impacts of quantum computing on Theoretical Computer Science

One major impact is that quantum computing gave us a polynomial time algorithm to solve the integer factoring problem which is not known to be efficiently solvable on classic computers. This partially motivated the development of public key cryptography that does not depend on the hardness of factoring problem.

Efficient quantum algorithm for an NP-complete problem would have the greatest impact on TCS since it would give us insights into the fundamental differences between the computational power of classical and quantum algorithms (assuming classic deterministic algorithms can not solve NP-complete problems in polynomial time) .


For any given objective function, let BotL (best-of-the-list) be the algorithm that evaluates the objective function on a set of inputs and returns an input from that list that had maximal output (from among those inputs), with ties broken arbitrarily. $\:$ Since APX only includes problems

who's objective function can be computed in deterministic polynomial time, BotL can be implemented deterministically in polynomial time. $\:$ Furthermore, the value returned by BotL

is at least as good as any of inputs in the least that BotL was evaluated on. $\:$ In particular,

if any of the inputs in that list is good-enough then BotL's output will be good-enough.

Therefore running BotL on the outputs of a sufficiently large number of independent executions of a base algorithm can amplify the success probability from 1/poly to 1-(1/(2^poly)).

As consequence of the preceding paragraph, the precise

confidence level essentially does not affect the resulting class.

(This situation is highly analogous to RP.)

I was not able to find anything about that on the complexity zoo, although there

might have been talks on it given at the workshop referred to in this paper.


Looking for algorithm (or at least name) for this optimization problem

If I understand your problem correctly, we can formulate it like so: given pairs $(\alpha_k,\beta_k)$ and $\Delta_0$, find $s > 0$ such that $\max_k (s\alpha_k + \beta_k) = \Delta_0$. Here is one way to solve this (this algorithm can be made more efficient). Go over all possible $k$. For each $k$, find the value of $s$ such that $s\alpha_k + \beta_k = \Delta_0$ (namely $s = (\Delta_0 - \beta_k)/\alpha_k$), check that it's positive, and check that for all $l \leq k$, $s\alpha_l + \beta_l \leq \Delta_0$. This runs in $O(m^2)$, where $m$ is the number of pairs (in your case, $m = n(n-1)$); you can probably get the running time down to quasilinear. Your case is more structured, so you may be able to get an even faster algorithm.


A natural definition of "near-linear" should be:

  A function $f:\mathbb{N}\to\mathbb{N}$ is near-linear, if $~f(n)\in O(n^{1+\varepsilon})~$ for all $\varepsilon>0$.


In some of these bounds, the $\varepsilon$ doesn't come from an approximation, but rather from the degree to which you recurse in a partition tree. Roughly speaking, the idea goes like this. Find a small sample of the input objects that form an arrangement so that the remaining objects are "spread out nicely". In particular, each cell of the arrangement is not intersected by too many of the remaining objects. Then recurse in each piece.

Using things like $(1/r)$-cuttings, you get recurrences that look like

$$ S(n) = r^d( 1 + S(n/r) ) $$

Solving such recurrences gives you bounds like $S(n) = n^{d+\varepsilon}$, where $\varepsilon$ is roughly $1/\log r$.


Is the concept of the Turing Machine derived from automata?

Neither!

The best way to see this independence is to read the original papers.

Turing's 1936 paper introducing Turing machines does not refer to any simpler type of (abstract) finite automaton.
McCulloch and Pitts' 1943 paper introducing "nerve-nets", the precursors of modern-day finite-state machines, proposed them as simplified models of neural activity, not computation per se.

For an interesting early perspective, see the 1953 survey by Claude Shannon, which has an entire section on Turing machines, but says nothing about finite automata as we would recognize them today (even though he cites Kleene's 1951 report).

Modern finite automata arguably start with a 1956 paper of Kleene, originally published as a RAND technical report in 1951, which defined regular expressions.  Kleene was certainly aware of Turing's results, having published similar results himself (in the language of primitive recursive functions) at almost the same time.  Nevertheless, Kleene's only reference to  Turing is an explanation that Turing machines are not finite automata, because of their unbounded tapes.  It's of course possible that Kleene's thinking was influenced by Turing's abstraction, but Kleene's definitions appear (to me) to be independent.

In the 1956 survey volume edited by Shannon and McCarthy, in which both Kleene's paper on regular experssions and Moore's paper on finite-state transducers were finally published, finite automata and Turing machines were discussed side by side, but almost completely independently.  Moore also cites Turing, but only in a footnote stating that Turing machines aren't finite automata.

(A recent paper of Kline recounts the rather stormy history of this volume and the associated Dartmouth conference, sometimes called the "birthplace of AI".)

(An even earlier version of neural nets is found in Turing's work on "type B machines", as reprinted in the book "The essential Turing", from about 1937 I think.  It seems likely that many people were playing with the idea at the time, as even today many CS undergrads think they have "invented" it at some point in their studies before discovering its history.)


Creating HMAC keys using a fixed prefix and a random string

Let's put it more formally first. Let $s$, $t$ be strings known to the adversary, and $k$ be a secret key. Let $k_1$ and $k_2$ be the keys obtained as $k_1 = H(s|k)$ and $k_2 = H(t|k)$ respectively, where $H(\cdot)$ is a collision-resistant hash function, and $|$ denotes the concatenation. The question is,

  Is function $f_i(\cdot)=HMAC(\cdot, k_i)$ a MAC?

The answer is yes. I don't have a formal proof, yet the following reasoning seems just fine (see also this topic):
Given $s$ and $t$, and keeping $k$ secret, the adversary will be unable to deduce $k_1$ or $k_2$ with non-negligible probability. Lacking access to $k_i$, the key to HMAC, function $f_i$ will indeed act as a MAC.


For which graph classes the fractional chromatic index rounded up equals the chromatic index?

It is known that for any multigraph $G$ on at most 8 vertices, $\chi'(G)$ is the maximum of the maximum degree and the ceiling of the odd-sets bound, see http://dx.doi.org/10.1016/S0012-365X(96)00364-0 (so what you find with sage is not very surprising).

This recent arXiv manuscript gives some more references for your problem (top of page 3)
http://arxiv.org/pdf/1406.0757v1.pdf

Beside bipartite graphs, non-trivial classes with the property you're looking for include series-parallel graphs.


What is wrong with this $\mathsf{L} \subseteq \mathsf{L}-$uniform $\mathsf{NC}^1$ argument?

In fact, the circuit depends on the input structure, not only on the input structure size. We take a tree-decomposition of the graph with additional colours and turn it into a convolution tree. The evaluation of the formula on this tree is reduced to computing the value of the convolution tree. To compute the value of the tree, it is turned into an arithmetic circuit. Hence we do not get one circuit for each input size as required for $NC^1$, but rather one circuit for each single input.


Proof software for Primitive Recursive Arithmetic

The ACL2 theorem prover seems quite close to what you want, though it is hard to know exactly what the strength of the system is.

From the logical description here it looks like the base is a quantifier-free equational logic with induction principles, which include principles allowing the definition of PR functions.

This gives exactly PRA, but in addition, the standard library defines induction up to $\varepsilon_0$, which brings the strength up to full Peano Arithmetic.

You might therefore want to work in ACL2 with a restricted version of the standard induction principle (I don't know how hard that is).


Does kd tree requires triangular inequality for finding k-nearest neighbors

First of all, I'm not sure why you even need a kd-tree for 3D data. Any reasonable grid structure will be ok to find near neighbors (See the work by Franklin for example, on spiral search methods). Secondly, the triangle inequality is needed to prune the search space correctly, so without it things will run a lot slower.

Finally, as a side note, the coefficients on the first and third square terms are of the form $\alpha, 5-\alpha$, where $2 \le \alpha < 3$. So what you really have is a space in which the distance is defined by a Mahalanobis distance (an affinely transformed Euclidean distance) which is almost fixed (since the coefficients vary between 2 and 3). So even if the triangle inequality is not satisfied (and it's very likely it doesn't), it will be "almost satisfied" in a way that will make near-neighbor searching entirely possible.


Twins in a graph are just modules of size 2. The modular decomposition of a graph can be found in $O(n+m)$ time. The modular decomposition tree implicitly represents all modules of the graph and consists of three types of internal nodes: series, parallel and prime nodes, and the leaves consists of the individual nodes. A set of at least two vertices $S \subset V$ is a module if and only if it is some node in the tree or the union of some set of children of a series or a parallel node.

So to find a pair of twin nodes, if they exist, we can construct the modular decomposition tree in $O(n+m)$ time. Then look at the leaves, if the parent of any leaf is a series or parallel node then that node must have at least two children which form a twin pair. So the total running time is linear.

http://en.wikipedia.org/wiki/Modular_decomposition


Is there a natural restriction of VO logic which captures P or NP?

For information, VO is in fact really more powerful than what you state; it contains the entire analytical hierarchy (hence, also the entire arithmetical hierarchy). The result is not published, neither submitted to any place, but you can find it on my page, www.milchior.fr/ho.pdf section 7 page 47.

In it I show how VO lets you express addition and multiplication on order variable; may be some idea in this paper can help you. In particular I gave an equivalent definition (I prove it is equivalent) and I think it is more easy to use. (I wanted to avoid the fact that, in their definition of VO $\forall i \forall X^i\forall j\exists Y^j (X^i=Y^j)$ is false while    $\forall i \forall X^i\forall i\exists Y^i (X^i=Y^i)$ is true; which means that $i$ was changed after $X$ was quantified; hence it is useless to add "$^i$" when one quantifies $X$.

One straightforward restriction would be to forbid to quantify the same variable twice. I am pretty sure that the restriction is the class ELEMENTARY. The idea is that, for every formula $\phi(i)$ with a free order variable $i$, there would be one number $k$ such that forall $i>k$ the value of $\phi(i)$ would not change; hence if we can find this $k$ (which is probably an elementary function of the size of the universe) we can avoid to really check every possible $\phi(i)$ when we want the value of $\forall i \phi(i)$ but restrict it to $\forall i < k \phi(i)$.

Else, you can certainly restrain VO by restraining the maximal order accepted; but then you obtain a "higher order" language (HO), and this is probably not what you want.


As mentioned above: question answered by reference to FO(TC) games presented in Finite Model Theory by Ebbinghaus and Flum.


Number of solutions to the biclique cover problem

Given a Graph $G=(V, E),$ it takes $O(|V|^3)$ delay and $O(2^|V|)$space to find all bicliques  in lexicographical order in $G$ [1]. There is no polynomial-delay enumeration algorithm for all bicliques in reverse lexicographical order unless P=NP [2].

Given a bipartite graph $G=(U, V, E),$ it takes $O((|U|+|V|)^2)$ delay with exponential space to find all maximal bicliques in $G$ in lexicographical order in $U$ [3].

[1] Vania M.F. Dias, Celina M.H. de Figueiredo, and Jayme L. Szwarcfiter.
“Generating Bicliques of a Graph in Lexicographic Order”. In:
Theoretical Computer Science 337.1-3 (June 2005), pp. 240–248. doi:
10.1016/j.tcs.2005.01.014.

[2] Wasa, Kunihiro. "Enumeration of enumeration algorithms." arXiv preprint arXiv:1605.05102 (2016).

[3] Alain Gely, Lhouari Nourine, and Bachir Sadi. “Enumeration aspects
of maximal cliques and bicliques”. In: Discrete Applied Mathematics
157.7 (Apr. 2009), pp. 1447–1459. doi: 10.1016/j.dam.2008.10.
010.


Are there known to exist functions with the following direct-sum property?

Well, that is false: it is possible to evaluate M copies of ANY f using only O(N(M+2^N)) gates which can be much less than M*exp(N) (in fact, you get linear amortized complexity for exponential M).  I don't remember a reference, but I think that it can go something like the following:

First add 2^N fictitious inputs which are just constants 0...2^N-1 and now denote the i'th N-bit input by xi (so for i<=2^N we have xi=i, and for 2^N < i <=2^N+M we have the original inputs).  Now we create a triplet for each of the M+2^N inputs: (i,xi,fi) where fi is f(i) for the first 2^N inputs (a constant that is hardwired into the circuit) and fi="*" otherwise.  Now we sort the triplets (i,xi,fi) according to the key xi, and let the j'th triplet be (i_j,x_j,f_j) from this we compute a triplet (i_j,x_j,g_j) by letting g_j be f_j if f_j is not a "*" and let g_j be g_(j-1) otherwise.  Now sort the new triplets back according to the key i_j, and you got the correct answers at the correct places.


Polynomial approximation algorithm for set cover with assumption

I ended up finding the answer.

I'm going to prove the greedy algorithm yields the correct answer.

Count the number of membership relationships. There are at least $n\cdot k$, so one set must contain more than $\frac{n\cdot k}m$ elements.

After one step of greedy algorithm, there are less than $n_1 = n - \frac{n\cdot k}m = n \left(1 - \frac km\right)$ elements left.

At the second step we remove at least $n_1(1-\frac{k}{m-1})$.

We are guaranteed to terminate when $n~\Pi_{i=0}^j \left( 1-\frac{k}{m-i}\right) < 1$, ie $\log(n) + \sum_{i=0}^j \log\left(1-\frac{k}{m-i}\right) < 0$.

Since $\log(1-x) < -x$, $\log(n) < \sum_{i=0}^j \frac{k}{m-i}$ is sufficient.

We are looking for the smallest $j$ such that:

$ m-j < \exp(\log(m) - \frac{\log(n)}{k}) = \frac{m}{n^\frac1k}$

$\Longleftrightarrow j > m\left(1-\frac{1}{n^\frac1k}\right) = m\left(1-\frac{1}{\exp(\frac{log(n)}{k}}\right)$

Now, $1-\frac{1}{\exp(x)} ≤ x$ by convexity, hence $j > \frac{m \log(n)}{k}$ is sufficient.


even many simple counter machines have been proven Turing complete and this result might be surprising to nonresearchers (or researchers who dont specialize in the area). suggest a more relevant research question would be to review the existing models (many listed on wikipedia), determine if yours fits into them anywhere, and if it does not, describe the precise difference with one of the "nearest" models analyzed in the literature.


As David said, we do not have such reductions for AES. However, this does not mean that Rabin or RSA cryptosystem are more secure than AES. In fact, I'd trust the (at least one-way, probably also pseudorandomess as well) security of block ciphers such as  AES/DES etc.. (perhaps with a bit more rounds than standardly used) more than the assumption that factoring is hard, precisely because there is no algebraic structure and so it's harder to imagine that there will be some kind of breakthrough algorithm.

One can construct block ciphers directly from one-way functions, which is a minimal assumption for much of crpyotgraphy, but the resulting construction will be terribly inefficient and hence not used.


Drawing graphs with few "sharp" vertices?

It is possible to construct 3-regular planar graphs with $\Theta(n)$ biconnected components (see e.g. fig.16 of this paper), each of which must contain at least one sharp vertex.

On the other hand, if you require higher levels of connectivity, you can avoid having many sharp vertices. In particular, if you have a 3-connected planar graph, it can be drawn (e.g. by using Steinitz' theorem to find a polyhedral representation and then forming a perspective projection) in such a way that all faces are convex, which causes only the outer face to be sharp. But every 3-connected planar graph can be embedded in such a way that the outer face has at most five vertices (the worst case being a dodecahedron) so you can draw every 3-connected planar graph (3-regular or not) with at most five sharp vertices.


Algorithm to transform an arbitrary MIP problem into the corresponding formulation for PSO

Ok, I have found how to do this by reading Introduction to Mathematical Optimization: From Linear Programming to Metaheuristics. Chapters 7 and 10 clearly explain the possibilities, essentially the penalty method and the use of Lagrange multipliers coupled with Kuhn-Tucker conditions if necessary.


Bounding the number of edges between star graphs such that graph is planar

Your statement is a little ambiguous: first you write that "...such that no edge is incident between the nodes in $R$", but the next paragraph implies that there are also no edges between vertices in $A$. I'll also assume that the stars are disjoint, and that you count all edges (including those initially present in the stars). Let's also assume there are at least two stars, and at least one of them has degree $\ge 2$.

In that case, you cannot beat the $2N-4$ bound ($N$ = number of all vertices). Consider a slightly different scenario: start with any set of $N$ vertices, some red some black, at least two of each kind. At each step add arbitrarily an edge between a red and a black vertex, as long as it does not create intersections or duplicate edges. I claim that when you get stuck, all cycles have length $4$.

Your scenario is a special case of this process where you start by first creating stars and then later adding the remaining edges. If all cycles have length $4$, the $2N-4$ bound follows. More generally, it shows that no matter what bipartite graph you start from, you can always complete it to a quadrilaterated (a word I made it up) graph.

Now, let's show the claim. In this process, all paths will have alternating black and red vertices and each cycle will have length at least $4$. If the graph is not connected, you can connect any red vertex on the outer face of one component with a black vertex on the other face of another component. So we can assume the graph is already connected.

Suppose you have a face $F$ of length $6$ or more. $F$ must have at least three black vertices (some possibly equal). If some vertex $x$ is repeated on $F$, take two clockwise consecutive appearances of $x$, say $x-a-...-x-b...$. $F$ must contain a black vertex $z\neq x$, so, depending on the location of $z$, we could connect either $a$ or $b$ to $z$ inside $F$ without duplicating edges. If no vertex is repeated, pick a clockwise section $x-a-y-b-z$ of $F$, where $x,y,z$ are black and $a,b$ are red. If $x$ is connected to $b$ then $a$ cannot be connected to $z$ (by planarity), so we can add one of the edges $(x,b)$, $(a,z)$ inside $F$.


Complexity lower bound: the gap between decision trees and RAMs

The natural model related to decision trees that can simulates RAMs is the branching program.  Basically, it is a decision tree with common subtrees coalesced yielding a DAG.   Time T and space S on a RAM can be simulated in height T and size 2^S on a branching program.  (You might need to use multi-way branching.)

For decision problems, it is clear that any decision tree only needs height = # inputs and space=total # of bits in the input.  Note that with multi-way branching one might have the # bits in the input larger than the usual measure of the # of inputs (e.g. n pointers each taking log n bits.)    For such problems with nlog n total input bits one can prove that certain problems cannot be solved in time O(n) and space=O(n) bits.  Is that the form of you problem?

You seem to suggest that you are using the # of outputs to try to get a larger lower bound.  It is usual for multi-output problems to allow many outputs along a single edge rather than at leaf nodes (see, for example, Borodin-Cook's 1982 paper on sorting lower bounds).  However, even without this assumption, one also can compute any function with height = # inputs and space = # input bits.  (Read and remember the input, and output all the values at each leaf node.)


What functions can System F not compute?

System $F$ is quite expressive. As proved by Girard here, the functions of type $\mathbb{N}\rightarrow\mathbb{N}$ (where $\mathbb{N}$ is defined to be $\forall X.\ X\rightarrow (X\rightarrow X)\rightarrow X$) are exactly the definable functions ($\mathbb{N}\rightarrow\mathbb{N}$) in second order Heyting Arithmetic $\mathrm{HA}_2$. Note that this is the same as the functions definable in second order Peano Arithmetic.

You'll probably want to check Proofs and Types as a more readable reference. Note that this means that a lot of programs can be written in system F, from the Ackermann function to interpreters for Gödel's system $T$. As for any total programing language (with some mild conditions) system $F$ cannot implement a self interpreter, i.e. a function $\mathrm{eval}:\mathbb{N}\rightarrow\mathbb{N}$ which takes as input a code for a term $t$ of system $F$ and returns a (code for a) normal form for $t$. The proof involves a variant of the diagonalizing trick used for undecidability of the halting problem. Andrej explains it beautifully here.

To answer your other questions: The $\lambda$-calculus underlying Hindley-Milner (HM) languages is also not Turing complete. In fact it is significantly weaker than system $F$, closer in expressiveness to the simply typed $\lambda$-calculus.

Haskell is indeed Turing complete. The most distinctive feature enabling this (though there are others) is the presence of unrestricted recursion: the definition of any program (function) can refer to the program itself. This is similar to the addition of a $Y$ combinator, such as is done in the definition of PCF which is simply-typed but retains Turing-completeness with the $Y$ combinator.

Note there are other features which make Haskell Turing complete, but they are not usually taken to be part of the core language, e.g. references to functions, unrestricted datatypes, etc.


A game of positioning overlapping circles to maximize travel time between them

This answer has two parts, together showing that the correct bound is $\Theta(\log N)$:

A lower bound of $\Omega(\log N)$ (times the radius of the first circle).
A matching upper bound of $O(\log N)$.

Lower bound of $\Omega(\log N)$

Consider two unit circles that touch at a point $p$. (See below; $p$ is on the right, the bug starts on the left.)  Alternate between one circle and the other.  The bug will travel up and down zig-zagging across the crevice between the two circles, moving mostly up and down but also progressing slowly to the right.  If I've done the trigonometry correctly, after $N$ steps, the distance from the common point will be $\Theta(1/\sqrt N)$, and the $N$th step will cause the bug to walk $\Theta(1/N)$, for a total distance of $\Theta(\log N)$.

Here's a sketch of the calculations.  Consider some two consecutive steps that the bug makes.  He goes from some point $a$, to $b$, to $c$.  Points $a$ and $c$ are on same circle; point $b$ is on the other circle.  Let $o$ be the center of the circle that $a$ is on.  Consider the following three triangles, in order of decreasing size:

The isoceles triangle $\triangle oap$ (recall $p$ is the common point).
The triangle $\triangle abp$.
The little triangle $\triangle abc$

These triangles are almost similar (i.e., congruent modulo scaling).
More precisely, for $\epsilon = |ap|$,
all three have the following property:
the ratio of the length of the short leg to the long leg is $\Theta(\epsilon)$.
(I won't prove this in any more detail here, but note that $\epsilon\rightarrow 0$
as the bug walks, and by perturbing one vertex in each triangle by a negligible amount, the triangles can be made similar.)

The long legs $co$ and $po$ of the first triangle have length 1.
Its short leg $|ap|$ has length $\epsilon$.
Segment $ap$ is a long leg of the second triangle,
so that triangle's short leg $ab$ has length $\Theta(\epsilon^2)$.
Segment $ab$ is a long leg of the third triangle,
so that triangle's short leg $ac$ has length $\Theta(\epsilon^3)$.
Thus, in these two steps that the bug takes:

The distance $|ab|+|bc|$ the bug travels is $\Theta(\epsilon^2)$.
The distance from the bug to the common point $p$ decreases from $\epsilon$ to $\epsilon-\Theta(\epsilon^3)$.

Define time $t_k$ to be the number of steps before $\epsilon_t \approx 1/2^k$.
By (2) above, $\epsilon$ decrease by a constant factor after about $\Theta(1/\epsilon^2)$ steps,
so $t_{k+1} = t_k + \Theta(2^{2k}) = t_k + \Theta(4^k)$.
Thus, $t_k = \Theta(4^k)$.
That is, after $\Theta(4^k)$ steps,
the distance from the bug to the common point $p$ will be about $1/2^k$.
Changing variables, after $N$ steps,
the distance from the bug to the common point will be $\epsilon = \Theta(1/\sqrt N)$.
And, in the $N$th step, the bug travels $\Theta(\epsilon^2) = \Theta(1/N)$.
So the total distance traveled in the first $N$ steps is $\Theta(1+1/2+1/3+...+1/N) = \Theta(\log N)$.

This is the lower bound.

It extends to proposed Variant 2 (as I understand it), as follows:

Adding the restriction that the bug should move to the nearest point in the intersection of the two most recently placed circles does not help.  That is, the $\Omega(\log N)$ lower bound above still applies.  To see why, we will modify the example above by adding a single extraneous circle that allows the bug to meet the restriction while still traveling the same path:

The green and blue circles are the two circles from the example above.  The intersection points $a$ and $b$ are the same $a$ and $b$ as in the example above.  The red circle is the new "extraneous" circle.  The previous sequence alternated between the blue and green circles.  The new sequence will be this sequence, but with the red circle added before every circle in the old sequence: red, blue, red, green, red, blue, red, green, red, blue, ...

Suppose the bug is sitting at $a$ after blue is placed.  The next circle placed is red.  Red contains the bug, so the bug doesn't move.  The next circle placed is green.  Now the bug moves to $b$ (which is the closest point on the intersection of the green and red circles).  By repeating this, the bug travels as before.

Upper bound of $O(\log N)$

I only sketch the proof.

Fix any sequence of circles.  We will argue that as $N\rightarrow \infty$,
the total distance traveled by the bug in the first $N$ steps is $O(\log N)$.
Assume without loss of generality that the first circle has radius 1.

Fix an arbitrarily large $N$.  Let $p$ by any point in the intersection of the first $N$ circles.
Note that because of the way the bug moves, in each step that the bug moves it gets closer to $p$.

First, consider steps where the following ratio is at least $1/\log N$:
$$ \frac{\mbox{the reduction in the distance to } p}{\mbox{the distance traveled in the step}}.$$
The total distance traveled in such steps is $O(\log N)$,
because the total distance traveled in such steps
is $O(\log N)$ times the initial distance to $p$.
So we only need to bound the total distance traveled in the other steps ---
those in which that ratio is at most $1 / \log N$.

First, we argue something slightly weaker:
that the total distance traveled in such steps
before the circle radius decreases to 1/2 or less is $O(\log N)$.
(We show later this is enough to give the bound.)

Consider any such step.
Let $a$ and $b$, respectively, denote the locations of the bug before and after the step.
Let $o$ denote the center of the current circle.
Let $b'$ denote the point on the ray $\overrightarrow{pb}$ such that $|pa| = |pb|$:

Consider the following triangles:

$\triangle opb$
$\triangle pba$
$\triangle abb'$

By geometric arguments similar to those in the lower bound,
for some $\epsilon$,
each of these triangles has two long legs and one short leg,
and the ratio (for each triangle) of the short leg length
to the long leg lengths is $\Theta(\epsilon)$:
$$\frac{|bb'|}{|ab|}
= \Theta\big(\frac{|ab|}{|pa|}\big)
= \Theta\big(\frac{|pa|}{|bo|}\big)
= \Theta(\epsilon).$$

This equation and the assumption that $|bo|$, which is the circle radius,
is in $[1/2,1]$ imply
that $|ab| = \Theta(|pa|^2/|bo|) = \Theta(|pa|^2)$,
and then that $|bb'| = \Theta(|ab||pa|/|bo|) = \Theta(|pa|^3)$.

Now we focus on the bug's distance to $p$.
Call it $d$ before the step, and $d'$ after the step.
(Note $d=|pa|$, $d'=|pb|$, and $d-d' = |bb'|$.)

In this step, this distance $d$ reduces by $|bb'|$,
which by the above observations is $\Omega(d^3)$.

Thus, the number of additional steps required to reduce the distance
by a factor of 2 (to at most $d/2$) is $O(1/d^2)$.
Changing variables, if $d=1/2^k$,
the number of additional steps required to bring the distance below
$1/2^{k+1}$ is $O(4^k)$.  Since the sum is geometric,
the total number of steps required to bring the distance below $1/2^{k}$ is $O(1/4^k)$.
Changing variables again,
after $n$ steps, the distance to $p$ will be $O(1/\sqrt n)$.

Finally, recalling the displayed equation several paragraphs up,
in the $n$th step, the distance that the bug travels, i.e. $|ab|$,
is $O((\mbox{the current distance to } p)^2) = O(1/n)$.  Thus,
the total distance traveled in the first $N$ such steps
while the circle radius is in $[1/2,1]$
is at most
$$\sum_{n=1}^N O(1/n) = O(\log N).$$

By scaling, we conclude that, for any $k$, the total distance traveled
while the circle radius is in the range $[1/2^k, 1/2^{k+1}]$
is $O(\log(N)/2^k)$.
Summing over $k$, the total distance traveled is $O(\log N)$.
QED