If $p$ is constant, then the size of the maximum clique in the $G(n,p)$ model is almost everywhere a constant multiple of $\log n$, with the constant proportional to $\log (1/p)$.  (See Bollobás, p.283 and Corollary 11.2.)  Changing $p$ should therefore not affect the hardness of planting a clique with $\omega(\log n)$ vertices as long as the clique is too small for an existing algorithmic approach to work.  I therefore expect that with constant $p \ne 1/2$ the hardness of Planted Clique should behave just like the $p=1/2$ case, although it is possible that the case of $p$ very close to 0 or 1 might behave differently.

In particular, for $p\ne 1/2$ the same threshold of $\Omega(n^{\alpha})$ for $\alpha = 1/2$ for the size of the planted clique applies, above which the problem becomes polynomial-time.
The value of $\alpha$ here is $1/2$ (and not some other value) because the Lovász theta function of $G(n,p)$ is almost surely between $0.5\sqrt{(1-p)/p}\sqrt{n}$ and $2\sqrt{(1-p)/p}\sqrt{n}$, by a result of Juhász.
The algorithm of Feige and Krauthgamer uses the Lovász theta function to find and certify a largest clique, so it relies on this threshold size for the planted clique.

Of course, there may be a different algorithm that does not use the Lovász theta function, and that for values of $p$ far from $1/2$ can find a planted clique with say $n^{1/3}$ vertices.  As far as I can tell this is still open.

Feige and Krauthgamer also discuss when $p$ is not constant but depends on $n$, and is either close to 0 or close to 1.  In these cases other approaches exist to find planted cliques, and the threshold size is different.

Béla Bollobás, Random Graphs (2nd edition), Cambridge University Press, 2001.
Ferenc Juhász, The asymptotic behaviour of Lovász' $\vartheta$ function for random graphs, Combinatorica 2(2) 153–155, 1982.  doi:10.1007/BF02579314
Uriel Feige and Robert Krauthgamer, Finding and certifying a large hidden clique in a semirandom graph, Random Structures & Algorithms 16(2) 195–208, 2000.  doi:10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A


Can we decide whether a permanent has a unique term?

Nice problem!  It's not hard to give a reduction showing that, if one could solve your problem, then one could also solve the following problem, call it ISOLATED SUBSET SUM:

Given integers a1,...,an, is there a subset S of the ai's whose sum is not shared by any other subset?

The reduction works by first reducing ISOLATED SUBSET SUM to ISOLATED PERFECT MATCHING, where given a weighted bipartite graph G, we want to find a perfect matching whose weight isn't shared by any other perfect matching.  This reduction is simple: for each i, create a 2x2 complete subgraph Gi in G, such that which of the two possible matchings we choose for Gi encodes our choice of whether or not ai is in the set S.

Next, reduce ISOLATED PERFECT MATCHING to your problem as follows:

For all i,j, if the edge (i,j) exists and has weight wij, then set Mij:=exp(wij).  (This turns the sums into products.)
For all i,j, if the edge (i,j) doesn't exist, then set Mij:=0.
Pad M to make sure that there are two or more permutations π such that Π Mi,π(i) = 0.  (This rules out spurious solutions that don't correspond to any perfect matching in G.)

Now, ISOLATED SUBSET SUM certainly feels like it's at least NP-hard, and maybe it's even harder than that (the obvious upper bound is only Σ2P)!  Furthermore, perhaps one could prove that ISOLATED SUBSET SUM is NP-hard using a Valiant-Vazirani-style randomized reduction.  This, however, is a challenge I leave to someone else...


Optimizing $\epsilon$ in $\epsilon$-kernel

Jeff Philips has a related result showing the stability of kernels: http://www.cs.utah.edu/~jeffp/papers/stable-kernel.pdf.

As for the problem itself, it can be formulated as a hitting set problem. Indeed, you need to pick a point into the kernel for each "complement of a slab" that contains $\geq \epsilon_k$ fraction of the input points. Here $\epsilon_k$ is the minimum $\epsilon$ that has a kernel of size $k$. Since this is just a hitting set problem, it can be approximated up to $O( \log k)$ factor in geometric settings. You need to guess the value of $\epsilon_k$, but naively just do a binary search on epsilon. As such, one can get two results:

A set of size $O( k \log k)$ that is an $\epsilon_k$ kernel.
A set of size k that is  an $\epsilon_{O(k/\log k)}$ kernel.

The algorithm for computing the set cover is the reweighting algorithm. In fact, the original paper by Clarkson solves a related problem about polytope approximation:

@inproceedings{c-apca-93,
  author       = "Kenneth L. Clarkson",
  title        = "Algorithms for Polytope Covering and Approximation",
  booktitle    = "Proc. 3rd Workshop Algorithms Data Struct.",
  series       = LNCS,
  volume       = 709,
  publisher    = "Springer-Verlag",
  year         = 1993,
  pages        = "246--252"
}

As for what to implement, i would use an incremental algorithm that performs quite well in practice, and add points an incremental fashion. See for example, the paper "Robust Shape Fitting via Peeling and Grating Coresets" and references therein.

it seems believable BTW that one should be able to do constant factor approximation instead of logarithmic.

I dont know of a formal proof that this problem is NP-hard, but it would be very surprising if it is not, IMHO.

The problem is probably solvable exactly in the plane using dynamic programming, I think....


Sufficient condition for termination of an orthogonal first-order rewriting system?

This is an entire field of research! In general, you cannot ensure termination of $R\cup\{l\rightarrow r\}$ by examining simply $l\rightarrow r$ and the knowledge that $R$ is terminating.

Indeed, even if $l\rightarrow r$ shares no function symbols with $R$ you may introduce non-termination! Here is a famous counter-example by Toyama. Take the following systems:

$$f(0,1,x) \rightarrow f(x,x,x)$$
and
$$p(x,y) \rightarrow x $$
$$p(x,y) \rightarrow y$$

each system individually is terminating, and you'll note that both systems do not share symbols, and are o̶r̶t̶h̶o̶g̶o̶n̶a̶l̶,̶ ̶a̶s̶ ̶i̶s̶ ̶t̶h̶e̶ ̶u̶n̶i̶o̶n̶ ̶o̶f̶ ̶t̶h̶e̶ ̶s̶y̶s̶t̶e̶m̶ not orthogonal at all! However, the combination is not terminating. The following term rewrites for ever: $f(p(0,1), p(0,1), p(0,1))$.

There is a further counter-example in which both systems are confluent. However orthogonality is a sufficient condition for modular termination (in addition to not sharing symbols). see this survey of modularity results by Gramlich.

However, there are ways to modularly add rules to a rewrite system even with shared function symbols without introducing non-termination. The most common is dependency pairs. There is a syntactic criterion that guarentees that you do not add cycles to the dependency graph, which captures possible sequences of rule applications.

The dependency graph is uncomputable, but there is a simple heuristic which allows to over-approximate it in an efficient way. If the rule does add a cycle to the graph, all is not lost! It becomes necessary to attempt to find an ordering that makes the rule safe to remove. Here's an overview of the AProVE system which implements many many techniques to show termination of rewrite systems in general. You might want to check the associated references.


It is not provable without additional axioms. In fact, it implies double negation elimination (take $B=\top$), which in turn is equivalent to the excluded middle.


Using the extra power of the negative adversary method

Apparently, I cannot comment so this will be an answer, even if it only a partial answer.

Element-distinctness has a lower bound of $\Omega(N^{2/3})$ and its certificate complexity is $\sqrt{N}$, so if one tries to prove it using the adversary method, he would need to use the adversary method with negative weights (which is optimal), or why not the Multiplicative adversary method.

Otherwise, the polynomial method is sometimes easier to use that the adversary methods since it suffices to prove the existence of polynomial whereas for the adversary method, you need to explicitly have a good adversary matrix, and compute its operator norm.


Codes/Lattices are certain combinatorial objects that are commonly used within TCS. A basic question for both of them is finding "short" codewords/lattice points, known as the Minimum Distance problem/Shortest Vector problem (MDP/SVP).

Both have been known to be NP-hard under randomized reductions for 20+ years. Roughly 10 years ago, the NP hardness proof for MDP was derandomized using some Analytic Number Theory (Weil's Character Sum bound).
SVP has still not been derandomized, but can be derandomized if the following result in analytic number theory is proven:

  For any $\epsilon > 0$, there exists $c\in\mathbb{N}$ such that for all sufficiently large $n$, the interval $[n, n + n^\epsilon]$ contains a square-free integer with no prime factors larger than $\log^c(n)$

Details of both of the above are described in Micciancio's paper Locally Dense Codes.

It's worth mentioning that this "existence of smooth numbers in short intervals" question is known within analytic number theory. For example, section 1.2 of Smooth numbers: computational number theory and beyond mentions that a slight relaxation of the problem (no prime factors larger than $n^\epsilon$) implies Vinogradov's conjecture, a problem in analytic number theory with no progress in 40 years.
There are definitely recent publications on this problem (say this), but I am not an expert, and can't say what the limits of current techniques are.


For emacs users there's the extremely useful org-mode. It is an emacs mode that, in plain ascii, help organizing your life or at least your research :) It has TODOs, deadlines, schedules, effort, tables with some computations capabilities, and lots of other features. It can export projects in LaTeX, html or other formats. Since it is text-based you can manage projects concurrently using some Distributed Concurrent Versions System, such as git or mercurial...


If the $VC$-dimension is $d$, then the number of sets that can be cut out from $m$ points by your family is $(em/d)^d$. (This is called the shatter function.)
Every set that you can cut out, can be changed at most $\sum_{i=0}^{tm} \binom mi$ ways to contribute to the $t$-shattering.
So if you want to $t$-shatter a set of size $m$, then you need $2^m\le (em/d)^d \sum_{i=0}^{tm} \binom mi\le(em/d)^d 2^{H(t)m}$ (if $t\le 1/2$) where $H(t)=-t\log_2 t-(1-t)\log_2(1-t)$ is the binary entropy.
From this we get $VC(t)\lessapprox d/(1-H(t))$.
Also note that $VC(t)\ge d/(1-t)$ holds trivially.
Of course, these bounds are general and not only for halfspaces.


Is there any sparse language known to be in NPI under the $P \neq NP$ assumption ?

I don't know whether you are asking an open problem, or whether it has already been resolved. Yet the following paper can shed some light on this problem:

Kurtz, S. A. 1985. Sparse sets in NP-P: relativizations. SIAM J. Comput. 14, 1 (Feb. 1985), 113-119. DOI= http://dx.doi.org/10.1137/0214008

Basically, it states that, even assuming P≠NP, there is an oracle relative to which no sparse sets in NP-P exists.

On the other hand, the following paper:

T. Baker, J. Gill, and R. Solovay, "Relativizations of the P=?NP Question", SIAM J. Computing (1975), 431-442. DOI= http://dx.doi.org/10.1137/0204037

demonstrates an oracle relative to which sparse sets in NP-P exists.

Since $NPI \subset NP-P$, this proves that, either way, the proof does not relativize.

EDIT: In addition, there exist sparse sets in NP-P if and only if $E \neq NE$:

Hartmanis, J., Sewelson, V., and Immerman, N. 1983. Sparse sets in NP-P: Exptime versus nexptime. In Proceedings of the Fifteenth Annual ACM Symposium on theory of Computing STOC '83. ACM, New York, NY, 382-391. DOI= http://doi.acm.org/10.1145/800061.808769

(Journal version available here: http://dx.doi.org/10.1016/S0019-9958(85)80004-8)


You're really asking two different questions and hoping that there is a single response which answers both: (1) What natural notions of quantum monotone circuits are there? (2) What would a lattice-based Razborov-style quantum result look like?

It isn't obvious how to achieve both at the same time, so I'll describe what to me seems a reasonable notion of quantum monotonic circuits (without indicating whether or not there is a corresponding Razborov result), and a completely different notion of what a "natural" quantum Razborov conjecture would look like (without indicating whether it is likely to be true).

What we want from quantum

As I remark in the comments, I think that it is not necessary to try to squeeze the notion of monotonic circuits into a mold of unitarity. Whether it is in the fact that evolution with time need not preserve the standard basis, or in the fact that there exists multiple bases of measurement in which the outcomes may be entangled, I think the sine qua non of quantum computation is the fact that the standard basis is not the only basis. Even among the product states, it is in some implementations defined only by a choice of frame of reference.

What we must do is to consider things in such a way as to remove the standard basis from its traditional privilidged place — or, in this case, as much as is possible while retaining a meaningful notion of monotonicity.

A simple model of quantum monotone circuits

Consider a circuit model which is implicit in Tsuyoshi Ito's comment about "monotone quantum channels" (and which is pretty much what one must do if one wants a notion of "a circuit" which is not restricted to unitary evolution).

Let $\mathbf H$ be the space of Hermitian operators on $\mathbb C^2$ (so that it contains all density operators on one qubit). How would we define a quantum monotone gate $\mathsf G: \mathbf H_a \otimes \mathbf H_b \to \mathbf H_c$ from two input qubits $a,b$ to an output qubit $c$, in such a way that it isn't effectively a classical monotone gate? I think it's straightforward to say that the output should not be restricted to $|0\rangle\!\langle 0|$ or $|1\rangle\!\langle 1|$, or mixtures of them; bu that to be "monotone", we should require that as $\langle 1 | \,\mathop{\mathrm{Tr}_a}\bigl(\rho_{ab}\bigr)  |1\rangle$ and  $\langle 1 | \,\mathop{\mathrm{Tr}_b}\bigl(\rho_{ab}\bigr) |1\rangle$ increase, the value of $\langle 1 | \mathsf G(\rho_{ab}) | 1 \rangle$ must be non-decreasing. For a two-input-qubit gate, this means that $\mathsf G$ must be implementable in principle as

performing a two-qubit measurement with respect to some orthonormal basis $\{ |00\rangle, |\mu\rangle, |\nu\rangle, |11\rangle \}$, where $|\mu\rangle,|\nu\rangle$ span the subspace of Hamming weight 1, and
producing as output some state $\rho \in \{ \rho_{00}, \rho_\mu, \rho_\nu, \rho_{11} \}$ corresponding to the outcome it measured, where $\langle 1 | \rho_{00} | 1 \rangle \leqslant \langle 1 | \rho_\lambda | 1 \rangle \leqslant \langle 1 | \rho_{11} | 1 \rangle$ for each $\lambda \in \{ \mu, \nu \}$.

The circuits are just compositions of these in the sensible way. We might also allow fan-out, in the form of circuits which unitarily embed $|0\rangle \mapsto |00\cdots 0\rangle$ and $|1\rangle \mapsto |11\cdots 1\rangle$; we should at the very least permit these maps at the input, to allow each (nominally classical) input bit to be copied.

It seems reasonable either to consider the entire continuum of such gates, or to restrict to some finite collection of such gates. Any choice gives rise to a different "quantum monotone gate basis" for the circuits; one can consider what properties different monotone bases have. The states $\rho_{00}, \rho_\mu, \rho_\nu, \rho_{11}$ can be chosen completely independently, subject to the monotonicity constraint; it would undoubtedly be interesting (and probably practical to bound error) to set $\rho_{00} = |0\rangle\!\langle 0|$ and $\rho_{11} = |1\rangle\!\langle 1|$, though I see no reason to require this in the theory. Obviously AND and OR are gates of this type, where $\rho_\mu = \rho_\nu = |0\rangle\!\langle 0|$ and $\rho_\mu = \rho_\nu = |1\rangle\!\langle 1|$ respectively, whatever one chooses $|\mu\rangle$ or $|\nu\rangle$ to be.

For any constant k, one might also consider gate bases including k-input-one-output gates. The simplest approach in this case would probably be to allow gates $\mathsf G: \mathbf H^{\otimes k} \to \mathbf H$ which may be implemented as above, allowing any decomposition of the subspaces $\mathcal V_w \leqslant \mathcal H_2^{\otimes k}$ of each Hamming weight $0 \leqslant w \leqslant k$, and to require that
$$ \max_{|\psi\rangle \in \mathcal V_w}\;\langle 1 | \,\mathsf G\Bigl( |\psi\rangle\!\langle\psi| \Bigr)\, |1\rangle \;\;\leqslant\;\; \min_{|\psi\rangle \in \mathcal V_{w+1}}\;\langle 1 | \,\mathsf G\Bigl( |\psi\rangle\!\langle\psi| \Bigr)\, |1\rangle $$
for each $0 \leqslant w < k$.
It is not clear how much additional computational power this would give you (nor even in the classical case).

I don't know whether there's anything interesting to say about such circuits beyond the classical case, but this seems to me to be the most promising candidate definition of a "quantum monotone circuit".

A quantum variant of Razborov's result

Consider the exposition by Tim Gowers of the results of Alon & Boppana (1987), Combinatorica 7 pp. 1–22 which strengthen Razborov's results (and makes explicit some of his techniques) for the monotone complexity of CLIQUE. Gowers presents this in terms of a recursive construction of a family of sets, staring from the "half-spaces" $$E_j = \Bigl\{ \mathbf x \in \{0,1\}^n \;:\; x_j = 1 \Bigr\}$$ of the boolean cube for each $1 \leqslant j \leqslant n$. If we remove the priviledged position of the standard basis in the base sets, in analogy to the Quantum Lovász Local Lemma, we may consider a subspace of $\mathcal H_2^{\otimes n}$ to correspond to a binary proposition (whether a state belongs to the subspace, or is instead orthogonal to it) which might arise from measurement. For instance, we may consider $n$ subspaces $\mathcal A_j \leqslant \mathcal H_2^{\otimes n}$ given by
$$\begin{align*} \mathcal A_j = U_j \mathcal E_j \;, & \text{ for each $1 \leqslant j \leqslant n$} \\ \text{where }
&\mathcal E_j := \Bigl\{ | \mathbf x \rangle \;:\; \mathbf x \in E_j \Bigr\} ; \\
&U_j : \mathcal H_2^{\otimes n} \to \mathcal H_2^{\otimes n} \text{ a unitary of bounded complexity}.
\end{align*}$$
We allow the quantum-logical analogues of conjunction and disjunction of subspaces:
$$\begin{gather*}
\mathcal A \wedge \mathcal B = \mathcal A \cap \mathcal B ; \\
\mathcal A \vee \mathcal B = \mathcal A + \mathcal B = \Bigl\{ \mathbf a + \mathbf b \,:\, \mathbf a \in \mathcal A\;,\; \mathbf b \in \mathcal B \Bigr\} .
\end{gather*}$$
We then ask how long a recursive construction of conjunctions and disjunctions of spaces are required to obtain a space $C$, such that the projector $\Pi_C$ onto $C$ differs only slightly from the projector $\Pi_{K(r)}$ onto the space spanned by the indicator functions of graphs having cliques of size $r$; for instance, so that $\| \Pi_C - \Pi_{K(r)} \|_\infty <\; 1/\mathrm{poly}(n) $. The monotonic part is involved in the quantum logical operations, and the primitive propositions about the input are quantum as well.

In the general case, there is a problem with treating this as a computational problem: the disjunction doesn't correspond to any knowledge which could be obtained with certainty by measurements on a finite number of copies using black-box measurements for $\mathcal A$ and $\mathcal B$ alone, unless they are the images of commuting projectors. This general problem can still be treated as an interesting result about geometrico-combinatorical complexity, and might give rise to results related to frustrated local Hamiltionians. However, it might be more natural to just require that the subspaces $\mathcal A_j$ arise from commuting projectors, in which case the disjunction is just the classical OR of the measurement outcomes of those projectors. Then we may require that the unitaries $U_j$ all be the same, and this becomes a problem about a unitary circuit (which gives rise to the "primitive events") with monotone classical post-processing (which performs the logical operations on those events).

Note also that if we do not impose any further restrictions on the spaces $\mathcal A_j$, it may being a subspace with very high overlap with some space $\mathcal E_k^\bot$ spanned by standard basis states $\mathbf x \in \bar E_k$, which are those binary strings in which $x_k = 0$.

If this possibility makes you squeamish, you can always require that $\mathcal A_j$ has an angle of separation from any $\mathcal E_k^\bot$ of at least $\frac{\pi}{2} - 1/\mathrm{poly}(n)$ (so that our primitive subspaces are, at worst, approximately unbiased from the subspaces in which one of the bits is set to 1).
If we don't impose such a restriction, it seems to me that admitting subspaces having high overlap with $\mathcal E_k^\bot$ would be an obstacle to approximating CLIQUE(r) anyway; either we would be more-or-less restricted to considering the absence of a particular edge (rather than its presence), or we would be forced to ignore one of the edges altogether. So, I do not see it as terribly important to impose any restrictions on $\mathcal A_j$, except possibly that they all are the images of a commuting set of projectors, if one's goal is to consider how to "monotonically evaluate CLIQUE from simple quantum propositions". At worst, it would amount classically to allowing NOT gates at the input (and having all fan-out occur after the negation).

Again, it is not clear to me whether substituting the base sets with arbitrary subspaces of $\mathcal H_2^{\otimes n}$ gives rise to a more interesting problem than just using the subspaces $\mathcal E_j$; though if we restrict ourselves to the case of CNF formulae (either in the commuting or the non-commuting case), the results we obtain would correspond to some notion of complexity of a frustration-free Hamiltonian whose ground-state manifold consisted of standard basis states representing cliques.


Is the class of primitive recursion functionals equivalent to the class of functions which Foetus proves to terminate?

Yes, the Foetus checker can typecheck everything in Goedel's T. You can show this by using the checker to show that the iteration operator in T is terminating. For example, the following definition will work:

$$
\begin{array}{lcl}
\mathit{iter}  & : &  A \to (A \to A) \to \mathbb{N} \to A \\
\mathit{iter} \;i \;f \;0 & = & i \\
\mathit{iter} \;i \;f \;(n+1) & = & f\;(\mathit{iter} \;i \;f \;n)
\end{array}
$$

This is very easy for the Foetus checker (or most any other termination checker) to check, because it is an obviously structurally recursive definition.

Agda and Coq both permit proving termination of functions that go far beyond what is provably total in first-order arithmetic. The feature which enables this is that they permit defining types by recursion on data, which is called "large elimination". (In ZF set theory, the axiom scheme of replacement serves roughly the same purpose.)

An easy example of something that goes beyond T is the consistency of Goedel's T itself! We can give the syntax as a datatype:

data T : Set where
   N : T
   _⇒_ : T → T → T

data Term : T → Set where
   zero : Term N
   succ : Term (N ⇒ N)
   k    : {A B : T} → Term (A ⇒ B ⇒ A)
   s    : {A B C : T} → Term ((A ⇒ B ⇒ C) ⇒ (A ⇒ B) ⇒ A ⇒ C)
   r    : {A : T} → Term (A ⇒ (A ⇒ A) ⇒ N ⇒ A)
   _·_  : {A B : T} → Term (A ⇒ B) → Term A → Term B

Note that the type dependency permits us to define a datatype of terms containing only the well-typed terms of T. We can then give an interpretation function for the types:

interp-T : T → Set
interp-T N       = Nat
interp-T (A ⇒ B) = (interp-T A) → (interp-T B)

This says that N should be the Agda natural numbers, and T's arrow should be interpreted as the Agda function space. This is a "large" elimination, because we define a set by recursion on the structure of the datatype T.

We can then define an interpretation function, showing that every term of Goedel's T can be interpreted by an Agda term:

interp-term : {A : T} → Term A → interp-T A
interp-term zero    = 0
interp-term succ    = \n → n + 1
interp-term k       = \x y → x
interp-term s       = \x y z → x z (y z)
interp-term r       = Data.Nat.fold
interp-term (f · t) = (interp-term f) (interp-term t)

(I don't have Agda on this machine, so there are doubtless some missing imports, fixity declarations, and typos. Fixing that is an exercise for the reader, who can also be an editor, if they like.)

I don't know what the consistency strength of Agda is, but Benjamin Werner has shown that the Calculus of Inductive Constructions (Coq's kernel calculus) is equiconsistent with ZFC plus countably many inaccessible cardinals.


Universal Approximation - Are ReLUs discriminatory?

Yes, ReLUs are discriminatory. See for example the nice, simple proof in Lemma 3.15 of these notes by Leonardo Ferreira Guilhoto:
http://math.uchicago.edu/~may/REU2018/REUPapers/Guilhoto.pdf

Regarding whether an unbounded function like a ReLU can be discriminatory, note that you can construct a bounded, continuous function as the difference of two ReLUs:

$f(x) = ReLU(W x + b_1) - ReLU(W x + b_2)$

and an appropriate choice of $b_1, b_2$ makes this difference f a sigmoidal function, as defined in Cybenko, so function f is discriminatory.

By definition a function is discriminatory if the zero measure is the only signed Borel measure $\mu$ such that:

$\int f(W x + b) d \mu (x) = 0$
for all W, b

Applying this to the difference of ReLUs above shows that both integrals over each ReLU must have measure zero if integral of f has measure zero.


Is the church-style affine calculus of constructions with unrestricted recursion consistent?

Let me first state that I'm not sure what are you getting at, I'm not sure how linearity/affinity is relevant. I'll answer the question in 'standard' setting.

How would you define how to compare two infinite types lazily?

It seems to me that it can't be done automatically since they can eventually diverge.

[Checking for  nominal equality ("pointer quality", exactly same identifier) seems shortsighted since you could define two identical infinite structures Nat and Nat2 and they would not be equal nominally while they should.]

But in some cases it can be done, its just that the programmer needs to lead the checker on how the equality should be verified.

In your case, think about Nat as a type-level fix point:

natF =
  ∀ nat : *
  ∀ P : *
  ∀ S : nat -> P
  ∀ Z : P
  P

Nat = fix nat . natF nat

That gives Nat and the two functions:

fix : Nat -> natF Nat
unfix : natF Nat -> Nat

You can use these functions as annotations that control the infinity and allow the checker to work with finite structures all the time.

This article has a nice intro (there are plenty of similar tutorials):
Gentle introduction to the general technique of F-algebras

For Nat, you would use this functor:

data Nat nat = Z | S nat


Fan Chung and Linyuan Lu.
Concentration inequalities and martingale inequalities: a survey
available at
http://projecteuclid.org/euclid.im/1175266369 or at Fan Chung Graham's web page.


Great algorithms, machine learning and no linear algebra

You can cover boosting.  It's very clever, easy to implement, is widely used in practice, and doesn't require much prerequisite knowledge to understand.


You could apply the principle of the Configuration Model (Molloy & Reed'95) to bipartite graphs. It allows generating a network possessing any predefined degree distribution. In the original version, you first generate a set of "stubs", where each node is repeated as many times as its targeted degree (i.e. a node whose degree should be 5 will appear as 5 distinct stubs). Then, you randomly draw pairs of stubs, and connect the corresponding nodes in your graph. See this page for additional details.

In the case of a bipartite network, you could do the same thing, but using two distinct sets of stubs (corresponding to both types of nodes). The pairs you draw should be constituted of one stub from each set.

If you want to keep the growth property of the model, you could also directly modify the Barabasi-Albert model you mention, by adding two extra constraints. First, alternate the type of the inserted nodes (I mean: once a node of the first type, then a node of the second type, then another node of the first type, and so on). Second, connect it only to nodes of the other type, using the preferential attachment principle.

Edit: you might be interested by the Networkx library, cf. the Bipartite section in this page.


Practical consequences of $Parity \notin AC^0$

I am not an electrical engineer, but search for online patents regarding switching circuits for parity gates, and all proposals (I found patents only until the end of the 1970s) discuss the size-versus-depth problem. All three patents I have looked at propose solutions of logarithmic depth, based on fanin-2 gates. So the answer to your first question is possibly "no".

J.J. Moyer: Parity Check Switching Circuit, United States Patent US3011073, 1961

A.F. Bulver et al.: NAND Gate realization of the n-input parity function, United States Patent US3718904, 1973

P.J. Baun, Jr.: Parity Circuits, United States Patent US4251884, 1981


Chvátal and Sbihi (Recognizing Claw-free Perfect Graphs, JCTB 44) described the atoms for the class of claw-free perfect graphs, a.k.a. quasi-line perfect graphs.  This description was later refined by Maffray and Reed, and essentially consists of two classes: "peculiar", which are kind of a special case, and "elementary", which are constructed by modifying the line graph of a bipartite multigraph through an operation called augmentation.


Compute Nash Equilibrium for 2-player games

We have developed a user-friendly browser-based system to input and solve 2-player strategic-form and extensive-form games:

http://www.gametheoryexplorer.org/ (GTE)

Currently, we support:

finding all equilibria via polyhedral vertex enumeration (which works on the strategic-form representation, which is converted to in the case of extensive-form games; this uses David Avis' lrs http://cgm.cs.mcgill.ca/~avis/C/lrs.htmlW); and
finding one equilibrium using Lemke's algorithm (which works on the strategic-form representation or on the sequence-form representation for extensive-form games).

You can use lrs separately offline to solve larger bimatrix games.

The GTE project is under active development (supported by the Google Summer of Code in 2011, 2012, and 2014), so please provide feedback and/or let us know if you would like to contribute) at

gte@nash.lse.ac.uk

For a paper that covers the basic theory and a number of methods for enumeration of equilibria, see

D. Avis, G. Rosenberg, R. Savani , and B. von Stengel (2010).
Enumeration of Nash Equilibria for Two-Player Games.
Economic Theory 42, 9-37.

For a paper that describes GTE and what it can do, see

R. Savani and B. von Stengel (2014).
Game Theory Explorer - Software for the Applied Game Theorist.
Computational Management Science, 29 pages, to appear. arXiv version

Zouzias' answer gives a good description of how to use support enumeration, which works fine for small examples. The methods in the paper above and used in GTE will in general be much quicker than support enumeration for finding extreme equilibria. In addition, GTE will find the complete set of equilibria (which can include convex combinations of extreme equilibria) by finding maximal cliques in a bipartite graph.


The answer is that the mechanism must be truthful for every set of possible types: the mechanism does not know which are the true types ahead of time. So for a pair of types $v_i$ and $v_i'$, the mechanism must be truthful if an agent's true type is $v_i$: i.e. his utility must be greater if he bids $v_i$ than if he bids $v_i'$. But the mechanism must also be truthful if the agent's true type is $v_i'$! After all, as far as the mechanism is concerned, it might be! So in this case, an agent's utility must be greater if he bids $v_i'$ as compared to $v_i$.

The point is that truthfulness imposes many different inequalities on the same mechanism simultaneously: one for every type an agent might have, and for every deviation he might consider. All of them hold. This proof uses only two of these inequalities


I am not sure I understand your question. Let $L_M(k)=\{(x,i,t)$ for which on input $x$ we have that the $k$-th bit of $z_{i,t}$ is $1$. This language is in EXP, thus also in P/poly. Putting together these circuits for different values of $k$, we get the multi-output circuit.


What algorithm is behind akinator or 20q?

I think you are probably looking for "On playing “Twenty Questions” with a liar", Dhagat, Gacs, and Winkler, SODA 1992, http://portal.acm.org/citation.cfm?id=139404.139409

The many other papers that cite this one probably include additional relevant hits.


Yes, there is research on this issue.

The Simplex Method is Not Always Well Behaved, Wlodzimierz Ogryczak

retroLP, An Implementation of the Standard Simplex Method, Gavriel Yarmish and Richard Van Slyke

A Numerically Stable Form of the Simplex Algorithm, Philip E. Gill and Walter Murray

You might also be interested in the revised simplex method.  This method can take advantage of matrix sparsity; it doesn't keep a representation of the entire matrix.
This thesis was of great interest to me: A Comparison of Simplex Method Algorithms.


Consider that hamiltonian cycles of the bipartite graph are isomorphic (that is we can always permute the rows amongst themselves and the columns similarly to reach any other hamiltonian cycle).

Consider the planes given by $(x,-,-)$ and $(-,y,-)$. Permuting these planes is exactly the same as permuting the rows and columns of the $(-,-,z)$ planes. Thus we may permute in this way to get any of the hamiltonian cycles on one of the $(-,-,z)$ planes, giving us $n!(n-1)!/2$ unique xyz-graphs. Further, we may then permute the (-,-,z) plane, fixing only the one we specifically permuted before, each of which also must give a unique xyz-graph. Thus in total we have:

$H(n) \geq \frac{n!(n-1)!^2}{2}$

Which implies the bound

$C(n) \geq \frac{1}{2}\sum\limits_{i=2}^n \frac{(n)_i^3}{i^2}\\$.

EDIT: In fact, we can do better. We have only considered sub cubes here, but we may also consider xyz graphs inside ([n],[n],[m]). Since all simple cycles are hamiltonian on $K_{n,n}$, we take $m \leq n$ to avoid double counting. Then using the same construction for our first cycle and then the same permutation process above we get:

$H(n,m) \geq \frac{n!(n-1)(m-1)!}{2}$

and then

$C(n) \geq \frac{1}{2}\left (\sum\limits_{i,j=2 \ | \ i \geq j}^n \frac{(n)_i^2(n)_j}{ij} \right )$.


Linear programming, a non standard handling of absolute value

Your formulation ensures that $|x_i|=t_i$ in every optimal solution. However, this does not hold for an arbitrary feasible point.

Picky people could then complain that your formulation isn't entirely correct. However, as long as you don't change your objective function nor use $t_i$ in any other constraint, then you will be fine in practice.

This blog post describes several ways to model absolute values.


Lower bound proof for compressive sensing (Gel'fand widths)?

$m = \Omega(k \log(n/k))$ is a lower bound for any compressive sensing scheme, not just $\ell_1$-minimization using RIP guarantees on the measurement matrix. In fact, the recovery algorithm need not be polynomial time, and the measurement matrix may be adaptive (in the sense that the $i$'th row of the matrix can depend on the inner product of the input vector with rows $1$ through $i-1$).

Let me sketch the argument for non-adaptive measurements. If $K$ is a subset of $\ell_p^n$, then the Gelfand $m$-width of $K$ is defined to be:
$$d^m(K) = \inf_{A: \mathbb{R}^{m \times n}} \sup_{x \in K \cap \ker(A)} \|x\|_p$$
Define the compressive $m$-width as:
$$E^m(K) = \inf_{A: \mathbb{R}^{m \times n}, \Delta: \mathbb{R}^m \to \mathbb{R}^n} \sup_{x \in K}\|x - \Delta(A x)\|_p $$
Note that $\Delta$, the reconstruction procedure, can be arbitrary.

Lemma 1: If $K$ is symmetric ($K = -K$), then $E^m(K) \geq d^m(K)$.

Proof: Take some arbitrary matrix $A \in \mathbb{R}^{m \times n}$ and function $\Delta: \mathbb{R}^m \to \mathbb{R}^n$. By definition, $d^m(K) \leq \sup_{x \in K \cap \ker(A)} \|x\|$. On the other hand, for any $x \in K \cap \ker(A)$:
$$\|x\| \leq \frac12 \|x-\Delta(0)\| + \frac12 \|-x-\Delta(0)\| \leq \sup_{x \in K} \|x-\Delta(Ax)\|$$
So, we have $d^m(K) \leq \sup_{x \in K \cap \ker(A)} \|x\| \leq E^m(K)$. $\blacksquare$

Now, for the connection with compressive sensing, suppose we have an integer $k \geq 1$,  matrix $A \in \mathbb{R}^{m \times n}$ and a function $\Delta: \mathbb{R}^m \to \mathbb{R}^n$ such that for all $x \in \mathbb{R}^n$:
$$\|x - \Delta(Ax)\|_p \leq \frac{C}{k^{1-1/p}} \min_{k\text{-sparse } z} \|x - z\|_1$$
where $C$ is a constant. Let $B_1$ be the unit $\ell_1$-ball, viewed as a subset of $\ell_p^n$, for $1< p\leq 2$. We clearly have that:
$$E^m(B_1) \leq  \frac{C}{k^{1-1/p}} \sup_{x: \|x\|_1 \leq 1} \min_{k\text{-sparse } z} \|x - z\|_1 \leq \frac{C}{k^{1-1/p}}$$

But we also have a lower bound for the Gelfand width of $\ell_1$-balls.

Theorem 2: There exists a constant $c_1$ such that: $$d^m(B_1) \geq c_1 \min\left(1, \frac{\log(n/m)}{m}\right)^{1-1/p}$$

Combining with the above, we have that:
$$c' \min\left(1, \frac{\log(n/m)}{m}\right) \leq \frac1k$$
Thus, if $k$ is large enough, this gives the lower bound, $m = \Omega(k \log(n/k))$.

The proof can be extended without much difficulty to the adaptive setting. The assumption that $k$ is sufficiently large can also be removed.

I learnt of this argument from Chapter 10 of Foucart and Rauhut's recent book, "A Mathematical Introduction to Compressive Sensing". It's due to Cohen, Dahmen and Davenport ("Compressed sensing and best k-term approximation", 2009). Theorem 2 is due to Garnaev and Gluskin ("On widths of the Euclidean ball", 1984). Foucart, Pajor, Rauhut and Ullrich ("The Gelfand widths of $\ell_p$-balls for $0<p\leq 1$", 2010) give a relatively simple proof of it. In fact, this latter proof is based on a lower bound for the number of measurements needed for exact-recovery of $k$-sparse vectors.


Algorithm for detecting closed region on a plane

Let $S$ be a set of segments with the property that no two segments have an intersection with positive length. The set $S$ bounds a region if and only if the intersection graph of the segments in $S$ has a cycle.


Minimal directed circles partition cover of a directed graph

This is done by using minimum cost flow. See section 17.4 here.


NP completeness of classes of spanning trees

Lemke has shown that it is NP-hard to decide whether a cubic graph on $n=2k$ vertices has a spanning tree in which $k+1$ vertices have degree $1$ and $k-1$ vertices have degree $3$.

  P. Lemke:
  "The maximum-leaf spanning tree problem in cubic graphs is NP-complete."
  IMA publication no. 428, University of Minnesota, Mineapolis, 1988.
  https://www.ima.umn.edu/Maximum-Leaf-Spanning-Tree-Problem-Cubic-Graphs-NP-Complete

Lemke's result implies the NP-completeness of deciding whether there exists a spanning tree without vertices of degree $2$.
A slight modification of Lemke's reduction shows that the following problem is NP-complete for every fixed integer $p\ge4$: Decide whether there exists a spanning tree, in which every non-leaf vertex has degree at least $p$.
The same modification shows that the following problem is NP-complete for every fixed integer $p\ge4$: Decide whether there exists a spanning tree, in which every vertex degree lies in $\{1,p\}$.


Is there a sensible notion of an approximation algorithm for an undecidable problem?

In the case of the halting problem, the answer is "not yet". The reason is that the standard logical method for characterizing how hard a program's termination proof is (eg, ordinal analysis) tends to lose too much combinatorial and/or number-theoretic structure.

The state of the art in practical termination analysis of imperative programs is something called "rank-function synthesis" (Byron Cook has a forthcoming book, Proving Program Termination, on the subject from CUP). The idea is to compute a linear function of the program's variables' values now and at the previous step, which serves as a termination metric. (One cool thing about this method is that it uses Farkas's lemma, which gives a neat geometric viewpoint to what's going on.) The interesting thing is that the tools built on this approach can do things like show the termination of the Ackerman function (which is non primitive recursive), but you can construct non-nested while loops which can defeat them (which only needs $\omega$ to show termination).

This means that there isn't a neat relationship between the proof-theoretic strength of the metalogic in which you show termination (this is very important in rewriting theory, for example) and the functions that techniques like rank-function synthesis can show termination for.

For the lambda calculus, we have a precise characterization of termination in terms of typability: a lambda term is strongly normalizing if and only if it is typeable under the intersection type discipline. Of course, this means that full type inference for intersection types is impossible, but it may also give a way of comparing partial inference algorithms.


Finding a maximum acyclic sub-tournament given two acyclic sub-tournaments

consider the reduction from vertex cover to the above problem.

consider graph $G(V,E)$ with vertex V={1,2,..n}

let T be the tournament with vertices $x_{i},y_{i},z_{i}$ for vertex i=1,2...n

construct the tournament with edges in order of  $x_{1},y_{1},z_{1},x_{2},y_{2},z_{2}...x_{n},y_{n},z_{n}$.if there exist a edge(i,j) then $z_{j},x_{i}$.  $x_{i},y_{i}$ belongs to $T_{1}$ for i=1,2...n and $z_{i}$ belongs to $T_{2}$ for i=1,2...n. It is clear that $T_{1}$ and $T_{2}$ are acyclic.

Example for the construction

consider the graph G(V,E) with vertex set {1,2,3} and edges be (1,2)(2,3)
construction as follows

Tournament has vertices $x_{1},y{1},z{1},x_{2},y_{2},z_{2},x_{3},y_{3},z_{3}$
with construction as follows

Step1
$x_{1}$ has directed edges to all vertices.

$y_{1}$ has directed edges to all vertices except $x_{1}$

$z_{1}$ has directed edges to all vertices except $x_{1},y_{1}$

$x_{1}$ has directed edges to all vertices except $x_{1},y_{1},z_{1}$

and repeat the process till all edges for the tournament constructed

step 2: (1,2) has a edge so swap the edge direction from $(x_{1},y_{2})$ to $(y_{2},x_{1})$ similarly for (1,3)
claim: G has a vertex cover of size k only if T has feedback vertex set of size k

one case is clear, if G has a vertex cover of size k then surely T has a fvs of size k

other way is, if there is edge (i,j) where $i<j$ if both $x_{i},z_{j}$ is not picked into the solution then we are forced to pick all vertices $y_{i},z_{i},x_{k},y_{k},z_{k},x_{j},y_{j}$ where for all k such that $i<k<j$. so picking $x_{i},z_{j}$ will result in better solution.hence proved

please see and verify.


This is addressed in the following paper of Karp and Kleinberg:

  Karp, Richard M.; Kleinberg, Robert. Noisy binary search and its applications. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 881--890, ACM, New York, 2007.

You can find a copy on Kleinberg's website.


Difference between weak duality and strong duality?

Weak duality is a property stating that any feasible solution to the dual problem corresponds to an upper bound on any solution to the primal problem. In contrast, strong duality states that the values of the optimal solutions to the primal problem and dual problem are always equal.
Was this helpful enough?


Integer Programming.

Showing that if there is an integer solution then there is a polynomial size integer solution is quite involved. See

Christos Papadimitriou, "On the Complexity of Integer Programming", JACM, 1981.


In the neutral zone between polynomial and sub-exponential

Graph Isomorphism is known to be in quasipolynomial time but not known to be in polynomial time: https://arxiv.org/abs/1512.03547
You can also come up with synthetic problems by the time hierarchy theorem, which essentially states that there are problems at any (deterministic) time complexity but not below: https://en.wikipedia.org/wiki/Time_hierarchy_theorem


Examples of nontrivial non-discriminatory functions

Let $n=1$. Let $\mu$ be the usual Lebesgue length measure on $[1/2,1]$, and let $\mu$ be the negative of the usual Lebesgue length measure on $[0,1/2]$.

In particular, Lebesgue measure is $|\mu|$.

Let $\mathcal U\subseteq [0,1]$ be a set of Lebesgue measure 0. (For instance, $\mathcal U$ could be the set of all numbers whose binary expansion does not satisfy the law of large numbers...)

Let

$\sigma(x)=1$ for $x\in\mathcal U$, and
$\sigma(x)=0$ for $x\not\in\mathcal U$.

Then given $y$ and $\theta$, there are two cases.

Case 1: $y\ne 0$. Then
$$|\mu|\{X:y^\top X+\theta\in\mathcal U\}=0,$$ hence
$$|\mu|\{X:\sigma(y^\top X+\theta)\ne 0\}=0,$$
so $\int \sigma(y^\top X+\theta)d|\mu|(x)=0$,
so $\int \sigma(y^\top X+\theta)d\mu(x)=0$.

Case 2: $y=0$. Then $\sigma(y^\top X+\theta)$ is the constant $\sigma(\theta)$, which satisfies
$$\int \sigma(\theta)\,d\mu(x)=\sigma(\theta)\int d\mu(x)=\sigma(\theta)\mu([0,1])=0.$$

So, $\sigma$ is non-discriminatory.


Program equivalence wherein the programs are known to always halt

As a counter-example to this, consider the Context-Free Equivalence problem: it's undecidable to determine, given two context free languages, whether they accept the same set.

If your problem were decidable, we could use it to determine CFL equivalence, since it's always possible to turn a CFL into an always-halting Turing machine.

So even for countably infinite inputs, the problem is undecidable.

It's also worth mentioning that, for standard Turing Machines, all input domains are countably infinite, since they're sets of finite strings.


There are "natural" problems hard for Ackermannian time; in fact there is a growing body of literature on the subject.  A place to start is the survey in Section 6 of Complexity Hierarchies Beyond Elementary.

What is even more interesting is that there are complete problems for Ackermannian time, under say primitive-recursive many-one reductions: define for this
$$\mathsf{Ack}=\bigcup_{f\text{ Primitive-Recursive}}\mathsf{DTime}\big(ack(f(n))\big)\;.$$

Many examples arise with counter systems and logics.  For instance, the oldest known such problem is the inclusion problem between the sets of reachable configurations of two vector addition systems (VAS) assuming these sets to be finite:

input: Two VAS $V_1$, $V_2$ with $\text{Reach}(V_1)$ and $\text{Reach}(V_2)$ finite.question: $\text{Reach}(V_1)\subseteq\text{Reach}(V_2)$?

This was shown non primitive-recursive (in a uniform way, thus $\mathsf{Ack}$-hard according to the above definition) by Mayr and Meyer in 1981 (there is a simpler proof published by Jančar in 2001).  An $\mathsf{Ack}$ upper bound was first proved by McAloon (1984), with a simpler proof (but slightly worse bound) by Clote (1986), and improved and simplified arguments by Figueira et al. (2011).

Many problems are shown $\mathsf{Ack}$-hard through reductions from the reachability problem in lossy counter machines (or slight variants).  Those can be defined as Minsky machines where counter values may decrease in an uncontrolled way; see Schnoebelen 2002 & 2010 and Urquhart (1999) for a similar construction.


Von Neumann architectures and quantum computing

What do you mean by von Neumann architecture?

I'll use the Wikipedia definition, and say that it's a computer which keeps its program and its data in the same random-access memory. This works well as a theoretical model of a quantum computer, but there are severe drawbacks to implementing such a device. In particular, for a quantum computer, the data has to be quantum. If the data and program are stored in the same memory device, this would imply that the program has to be quantum, as well. So the computer would then have to be able to implement a superposition of instructions in its instruction set. This is orders of magnitude more difficult experimentally than just having the memory in superposition.

In fact, even indirect memory retrieval, including RAM, pointers, and so forth, appears to be quite difficult to implement experimentally.

This has resulted in the default model of a quantum computer being the uniform quantum circuit model, which is both easier to imagine implementing experimentally and tractable to deal with theoretically from a TCS perspective. The circuit model is able to simulate the von Neumann architecture with only a polynomial slowdown, so quantum complexity classes are not changed by this change of model.


Implementing algorithms well is a skill which takes a different set of tools than just proving theorems. Many algorithms which were discovered by the theory community have indeed been implemented in practice (although I would like to see the theory community take a bigger role in this process). Physics doesn't ask the same researchers to do theory and experiment, although it is expected that the two groups communicate. Why shouldn't you expect to see the same divide in computer science?

ADDED IN EDIT:

Expanding on my comment in answer to Suresh's about what I meant by "role" above, at Bell Labs and AT&T Labs, researchers in algorithms were encouraged to talk to people in development. I didn't do as much of this as I probably should have, but I did get at least one paper out of it, and I think it would be good for the field if there were more communication between people in theory at universities and practitioners. This doesn't mean that I think everybody who comes up with an algorithm should code it (even if it's practical).

On the other hand, coding algorithms (or having a student code them) that you think might be practical can be useful in getting them adapted by practitioners. Consider one example. Lempel and Ziv wrote two technical papers in 1977 and 1978 on new data compression algorithms. Everybody ignored them. In 1984, Welch wrote a much less technical paper giving a slight twist on LZ78 that improved its performance somewhat, and gave the results of a small study comparing its performance with other data compression methods. It was published in a journal read by a number of programmers, and the algorithm was given by a few lines of pseudocode. The method was quickly adapted in a number of places, eventually resulting in an infamous intellectual property dispute.

Of course, one of the best ways for algorithms researchers to communicate with practice is to produce grad students who go off and work at Google, IBM, or other companies, and we're already doing that. Another way might be to answer practitioner's questions in this forum. Hopefully, we're doing a reasonable job of that as well.


What are recent advances in relational databases?

In db query area arguably Provenance Semiring enjoyed the most attention recently. The "provenance" adjective is just marketing connecting it to a large body of research. Nevertheless the idea that one may have much more elegant mathematical foundation for database query languages is compelling. My personal view is that semiring perspective (which works wonders in formal language theory) has to be complemented with Relational Lattice.

Here is another view of what happened in the last decade. (The speaker holds a record of continued PODS admittance:).

On less theoretical note lets mention Dedalus, and plenty of Tutorial D enthusiasts; both, however, are hardly the recent ideas.


NP-complete variants of undecidable problems?

As Jukka pointed out, the answer is trivially no for all undecidable problems.

A more reasonable question would be: Can every problem that is complete for the class of recursively enumerable languages be made NP-complete in a straightforward way? I am not sure this is true in general, but in the special cases you mention in your question (Bounded-Halting and Tiling) these problems are complete for RE even under "special" polynomial time reductions. (I leave "special" mostly undefined in this answer, but the properties needed can be worked out from it.)

So if we ask the even more reasonable question: Can every problem that is complete (under special polytime reductions) for the class of recursively enumerable languages be made NP-complete in a straightforward way?, here the answer is yes. Take any RE-complete problem $A$, defined with respect to a Turing machine $M_A$ that takes a pair of inputs $(x,y)$, such that $x \in A \iff (\exists y)[M_A(x,y)~\text{halts}]$. We are assuming that there is a polynomial time reduction from the Halting Problem to $A$. Define "Bounded-A" to be the set of pairs $(x,1^t)$ such that there is a $y$ of length at most $t$ such that $M_A(x,y)$ halts within $t$ steps.

Clearly "Bounded-A" is in $NP$. It's also $NP$-complete because we can reduce the $NP$-complete Bounded Halting Problem to Bounded-A in polynomial time (Note that here you need special properties on the polynomial time reduction $R$ to ensure that it carries over to Bounded-Halting as well: i.e., you need to be able to efficiently compute an upper bound $t'$ on how long $M_A(R(M,x),y)$ needs to run, assuming that $M(x)$ halts within $t$ steps.)

Now, is there a language which is RE-complete under (say) doubly-exponential-time reductions but not under exponential-time reductions? For such a problem, it is unlikely that you can trivially modify it to get an $NP$-complete version. I would guess that such a problem can be artificially constructed.


The number of inclusion-minimal vertex covers of size at most $k$ is at most $2^k$: They can be enumerated by a search tree algorithm that initially has a budget of $k$, then branches as long as the graph contains an edge $\{u,v\}$ into the two cases to add either $u$ or $v$ to the vertex cover. Each branch can be solved recursively and the parameter $k$ is reduced by one in each case.

The number of minimal vertex covers of size at most $k$ obviously bounds the number of minimum vertex covers of size at most $k$ as well.

Further information can be found in

Henning Fernau:
On Parameterized Enumeration. COCOON 2002: 564-573 dx.doi.org/10.1007/3-540-45655-4_60

and

Peter Damaschke:
Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci. 351(3): 337-350 (2006)
http://dx.doi.org/10.1016/j.tcs.2005.10.004


Dynamic programming algorithm for NP-complete problem

[Edited ro reflect the intended meaning of the 3rd condition]

I believe you you describe the graph vertex coloration problem with a variation . We allow a vertex to have multiple colours :

No adjacent nodes should be colored with the same color.
Every node should have at least one color.
For every pair of nodes (x,y) with x /neq y , one of these nodes must be colored with a color that the other is not colored with.

I want to present two situations, due to the nature of condition 3.

a) If only 1 and 2 apply. The minimum number of sets will be found if we color each node with only one color. Every other color applied to a node not only does not help solve the problem, but it adds additional constraints. Therefore this problem can be reduced to the single-colored vertex coloring problem.

b) 1,2 and 3 apply. For starters, let's 1-colour the graph. That give us a number of sets, let it be S1. For node belonging to different colours, the 3rd condition holds. However, for nodes belonging to the same colour, it doesn't. For every set, the problem of separating the same-set nodes reduces to colouring a full node graph, which we know needs N colours. However, we need not use new colours. We can re-use the already-used colours that of course obey the condition 1.

Therefore, we can create a graph this way: Create a full graph containing all the nodes in the same set. Then, extend it with the nodes that are adjacent to the set colours. Maintain the existing colour for the added nodes (not belonging to the full graph). Also, add a node with the color of the set that is adjacent to every other node in the full graph, so that the original colour cannot be used. Then, try to colour the new graph. Repeat for every set (S1 repeats).

A sketch of the algorithm follows

Multi-colour(graph G) :

Color the graph with 1 color per node. Let S0 be the number of colors used.
For every color ( i from 1 to S0 ) :

a. Create a full graph containing the nodes with THIS color.

b. Add to the graph the nodes adjacent to the nodes colored with THIS color. The adjacent nodes are colored with their colored from step 1.

c. Add a node adjacent to the nodes from step a. Color it with THIS color.

d. Color the graph. Prefer colors that were used in step 1. if none is eligible, use a NEW color.

e. Add every NEW color to the list of "used" colors. Let Si be the number of new colors used. (Si can be zero or positive ). S0 = S0 + Si .
S0 is the number of minimum sets.

Complexity: The number of sets created by step 1 is O(n), where n is the number of vertices. Therefore this problem belongs in the same complexity as the graph coloring problem.

My algorithm is a top-down approach, therefore it is not dynamic programming. I do not know if dynamic programming could be applied to this problem. Does the Principle of Optimality hold for this problem?


Why is an even-odd split 'faster' for MergeSort?

Looking at the graphing network on Wikipedia and this page for even-odd merge sort it appears that it has a higher complexity than traditional merge-sort. However, at the cost of more operations, notice how the operations remain independent of one another.

That is to say, where as in merge sort you eventually end up merging 4 lists and then 2 lists, which cannot be done in parallel, even-odd merge sort allows you to operate in parallel until the end of the algorithm.

The Wikipedia article also points out that it is reasonably fast for doing sort in graphics hardware. I suspect this is because where as merge sort your inputs to compare-and-swap depend on which previous element was merged, the inputs to compare-and-swap in even-odd-merge-sort are always the same.

Hope that helps!


Formula size lower bounds for AC0 functions

A nice question! Khrapchenko can definitely not give quadratic lower bounds for $AC^0$ functions. His lower bound is in fact at least square of average sensitivity. And all functions in $AC^0$ have poly-logarithmic average sensitivity. Subbotovskaya-Andreev can apparently also not give such a function because the argument they use (random restriction results in much smaller formulas) is exactly the reason forcing large $AC^0$ circuit size; Hastad's Switching Lemma (am not quite sure, just an intuition). The only hope is Nechiporuk. But his argument cannot give more than $n^2/\log n$, by information theoretic reasons. So, can it be that everything in $AC^0$ has formulas of quadratic (or even smaller) size? I don't believe in it, but couldn't quickly find a counterexample.

Actually, the Allender-Koucky phenomenon arises also in other context - in graph complexity. Say that a circuit of $2n$ variables represents a bipartite $n\times n$ graph $G$ on vertices $V=\{1,\ldots,2n\}$ if for every input vector $a$ with exactly two 1s is, say, positions $i$ and $j$ ($i\leq n$, $j>n$) the circuit accepts $a$ iff vertices $i$ and $j$ are adjacent in $G$. Problem: exhibit an explicit graph $G$ requiring at least $n^{\epsilon}$ gates to be represented by a monotone $\Sigma_3$-circuit. Seems like an innocent question (since most graphs require about $n^{1/2}$ gates. But any such graph would give us a boolean function of $2m=2\log n$ variables requiring non-monotone log-depth circuits of superlinear size (by results of Valiant). Thus, even proving $n^{\epsilon}$ lower bounds for depth-3 circuits may be a challenge.


Validity of a modal argument about "vagueness"

How about just a blanket statement with no assumptions:

  A and B may be the same part of C

This would seem to be valid by the same reasoning! However it is only so if "may" ranges over all models of the language. If, as is usual, "may" only ranges over the possible worlds in a single model, it is not valid.


What happens to complexity classes if all $\#P$ problems have polynomial-time algorithms?

By definition, $\mathbb{P} = \mathbb{NP}$, since any $\mathbb{NP}$ problem could be solved by answering the question "Is the # of accepting paths non-zero", which by assumption, can be calculated in $\mathbb{P}$. As a consequence, the polynomial hierarchy collapses as well.

You also get other results by using results or their contrapositives.


Complexity status of restricted k-clique

Yes. It is essentially same as the Clique problem. Imagine a clique containing $n$ nodes. Your problem is then asking for a Clique containing $n-1$ nodes, such that all of them are adjacent to vertex $v$. $v$ is connected to all vertices in the graph. The problem is still NPComplete.


what is "one-to-one reduction from a function f to another function g"

The definition is composed of two parts. First, we want a reduction from $f$ to $g$. That's a way of computing $f$ given an oracle to $g$. This reduction is formed by two polytime functions $\alpha,\gamma$ which are used in the following way: $f(x) = \gamma(g(\alpha(x))$.

Second, we want the reduction to be one-to-one. That explains the if-and-only-if in (2). Moreover, for some reason we want an efficient one-to-one right-inverse $\beta$ of $\gamma$, satisfying $y = \gamma(\beta(y))$. The function $\beta$ can be used to answer the following question: what value of $g$ corresponds to a given value of $f$? (In contrast, $\gamma$ tells us what value of $f$ corresponds to a given value of $g$.) Why this is need will be apparent from the way the paper uses $\beta$.

The actual properties stated in the definition are slightly weaker (you want the function to be one-to-one only for values which actually occur in the formulas), but this is the gist of it.


Why isn't the decrease key operation in a pairing heap $O(1)$

An operation can have higher amortized cost than actual cost if it adds too many coins (in the banker's method) or too much potential (in the physicist's method). The lower bound paper you linked to includes the line:

  Decrease-key and insertion operations are both considered to have 0 actual cost.


Theory of computation and automata theory are not really needed for pure computability theory (but they are a very nice complement to computability theory and certainly help put it in perspective and relate it to the real world!).

Rather, a senior undergraduate level course in mathematical logic is the typical prerequisite.

Traditionally since Gödel, mathematical logic is considered to have four parts (in no particular order):

Set theory
Model theory
Computability theory
Proof theory

In computability theory you will learn things like the correspondence between $\Sigma^0_n$ sets in arithmetic and the Turing degree $0^{(n)}$, and of the Turing degrees of complete extensions of Peano Arithmetic.

Both culturally and scientifically, computability theorists are, and consider themselves to be, part of the mathematical logic community and often study things like computable model theory or higher computability theory (which borders on set theory). Some mathematical maturity is also very helpful.


Your question addresses the "exact" recovery problem (we want to recover a k-sparse $x$ exactly given $Ax$). In the following though I will focus on the "robust"  version, where $x$ is an arbitrary vector and the goal of the recovery algorithm is to find a $k$-sparse approximation $x'$ to $x$ (this distinction actually matters for some of the discussion below). Formally you want to following problem (call it $P_1$):

Design $A$ such that for any $x$ one can recover $x'$ where
 $\|x-x'\|_L  \le$

$\min_{x"} C \|x-x"\|_R$, where $x"$ ranges over all $k$-sparse vectors.

Here,  $\| \cdot \|_L$ and  $\| \cdot \|_R$ denote the left and the right norm, and  $C$ is the "approximation factor". There are various choices possible for $\| \cdot \|_L$ and  $\| \cdot \|_R$.  For concreteness, one can think that both are equal to $\ell_2$ or $\ell_1$;  it can get more messy though.

Now to some of the analogs and generalizations.

Arbitrary basis. First, observe that any scheme satisfying the above definition can used to solve a more general problem, where the recovered signal $x'$ is sparse in an arbitrary basis (say, wavelet of Fourier), not just the standard one.   Let $B$ be the basis matrix. Formally, a vector $u$ is $k$-sparse in basis $B$ if $u=Bv$ where $v$ is $k$-sparse. Now we can consider the generalized problem (call it $P_B$):

Design $A_B$ such that  given $A_B x$, one can recover $x'$ where $\|x-x'\|_L \le$

$\min_{x"} C \|x-x"\|_R$, where  $x"$ ranges over all vectors that are  $k$-sparse in $B$.

One can reduce this problem to the earlier problem $P_1$ by changing the basis, i.e., using a measurement matrix $A_B = A B^{-1}$.    If we have a solution to $P_1$ in the $\ell_2$ norm (i.e., the left and the right norms equal to $\ell_2$), we also get a solution to $P_B$ in the $\ell_2$ norm. If $P_1$ uses other norms, we solve $P_B$ in those norms modified by changing the basis.

One caveat in the above is that in the above approach, we need to know the matrix $B$ in order to define $A_B$. Perhaps surprisingly, if we allow randomization ($A_B$ is not fixed but instead chosen at random), it is possible to chose $A_B$ from the a fixed distribution that is independent from $B$.  This is the so-called universality property.

Dictionaries. The next generalization can be obtained by dropping the requirement that $B$ is a basis. Instead, we can allow $B$ to have more rows than columns. Such matrices are called (overcomplete) dictionaries. One popular example is the identity matrix on top of the Fourier matrix. Another example is a matrix where the rows are the characteristic vectors of all intervals in {1 ... n}; in this case, the set { $Bu: \mbox{u is k-sparse}$} contains all "$k$-histograms", i.e., piecewise constant functions over {1 ... n} with at most $k$ pieces.

As far as I know there is no general theory for such arbitrary dictionaries, although there has been a fair amount of work on this topic. See e.g.,
Candes-Eldar-Needell'10 or
Donoho-Elad-Temlyakov, IEEE Transactions on Information Theory, 2004.

Sketching for histograms was extensively investigated in streaming and database literature, e.g.,
Gilbert-Guha-Indyk-Kotidis-Muthukrishnan-Strauss, STOC 2002 or
Thaper-Guha-Indyk-Koudas, SIGMOD 2002.

Models. (also mentioned by Arnab). A different generalization is to introduce restrictions on the sparsity patterns. Let $M$ be a subset of $k$-subsets of {1 ... n}. We say that $u$ is $M$-sparse if the support of $u$ is included in an element of $M$. We can now pose the problem (call it $P_M$):

Design $A$ such that for any $x$ one can recover $x'$ where $\|x-x'\|_L \le$

$\min_{x"} C \|x-x"\|_R$, where $x"$ ranges over all $M$-sparse vectors.

For example, the elements of $M$ could be of the form $I_1 \cup \ldots \cup I_k$, where each $I_i$ corresponds to one "sub-block"of  {1 ... n} of some length $b$, i.e., $I_i$ is of the form { jb+1 ... (j+1)b} for some $j$. This is the so-called "block sparsity" model.

The benefits of models is that one can save on the number of measurements, compared to the generic $k$-sparsity approach. This is because the space of $M$-sparse signals is smaller than the space of all $k$-sparse signals, so the matrix $A$ needs to preserve less information. For more, see
Baraniuk-Cevher-Duarte-Hegde, IEEE Transactions on Information Theory, 2010 or
Eldar-Mishali, IEEE Transactions on Information Theory, 2009.

Hope this helps.


Structure of graphs that exclude a perfect matching on four vertices as an induced graph

Yes; they are known as $2K_2$-free graphs. Some additional references:

"On Toughness and Hamiltonicity of $2K_2$-Free Graphs"
"The maximum number of edges in $2K_2$-free graphs of bounded degree";
"Two characterisations of minimal triangulations of $2_{K2}$-free graphs"


A late answer, but the bound on synchronization delay has been studied for several classes of automata: see for instance Unambiguous Automata; Béal et al. MCS'08.

In particular; there is a family of deterministic automata that have delay $\Omega(|Q|^2)$ as showed in On the Bound of the Synchronization Delay of a Local Automaton; Béal et al. TCS'98, which matches a corresponding $O(|Q|^2)$ upper bound.

P.S. the synchronization delay defined in the paper is the minimal $k$ for which the deterministic local automaton is $k$-local.


Where and how did computers help prove a theorem?

A very well-known example is the Four Color Theorem, originally proven by exhaustive checking.


Type theory and computational complexity

The keywords you are looking for are "Implicit Computational Complexity". The field studies for instance variants of linear logic and the complexity bounds they can guarantee on the terms underlying the derivations.


This problem is NP-complete, by reduction from Hamiltonian cycle in a graph G=(V,E). Every edge in E receives weight 0. If a vertex is traversed, there is a gadget that allows you to use an edge of weight 1. Now in order to maximize the average, you need as many weight-1 edges as possible.

Here are some details for the construction:

Consider an instance $(V',E')$ of directed Hamilton path that asks for a Hamilton path from vertex $x\in V'$ to vertex $y\in V'$.
We create the following instance of the lowest path problem in an undirected graph $G=(V,E)$ from it:

Every vertex $v\in V'$ is replaced by three new vertices $v_1,v_2,v_3$, together with the two edges $\{v_1,v_2\}$ and $\{v_2,v_3\}$.
For every arc $(v,u)\in E'$, we introduce the undirected edge $\{v_3,u_1\}$ in graph $G$.
All edges $\{v_2,v_3\}$ in $G$ with $v\ne x$ and $v\ne y$ have weight 1, and all the remaining edges have weight 0.
The starting point of the desired lowest path is vertex $x_2$, and the endpoint is vertex $y_2$.

Consider a path $P$ in $G$ from $x_2$ to $y_2$, and let $k$ denote the number of weight $1$ edges on $P$.Then $P$ must also contain (at least) $3k+4$ edges of weight $0$, so that the average weight is at most $k/(4k+4)$. This expression is at most $|V'|/(4|V'|+4)$. A Hamilton cycle in $G'$ translates into a path with average weight $|V'|/(4|V'|+4)$ in $G$.


First find the optimal solution, then add the linear constraint that the solution must have value equal to the optimal you want, and restate your LP as the one looking for the largest ball inside the feasible region. Solve this modiefied LP, and you have what you want.

Why the second problem can be solved using LP is a stnadard cute problem in Computational Geometry...

==============

More formally, you find the affine subspace spanning the feasible points containing the optimal solution. So, assume that the optimal solution lies on the hyperplane $h \equiv cx = \alpha$ (i.e., $\min c x$ was the original LP target function). If $P$ is the feasible region of the original LP, we are looking for the largest ball in $P \cap h$. To this end, we need to compute the smallest dimensional affine subspace containing this set. Once you found this subspace, change variables so that you consider only this affine subapce. Now, your polytope is full dimenisonal, and you can use the second LP as I described above.

So, let $v$ be the vertex computed by the first LP.
Considering all the neighboring vertices to $v$. Consider the affine subspace of $v$ together with all its neighbors that have the same target value (i.e., $\alpha$). It is not hard to see, that this affine subspace is the desired subspace.

So, to summerize:
(A) solve LP to discover optimal value.
(B) Compute the smallest dimensional subspace containing the feasible solution with the optimal value.
(C) Rewrite the original LP in this affine subpsace (i.e., dropping all the irrelevant dimensions), add a variable, and turn it into an LP for finding the largest ball inside this polytope.


Via Michael Kass: let $Y(t)$ be a Wiener process starting at $Y(0) = X$, and define

$$f(t) = H(X~|~Y(t))$$

Then $f(0) = 0$, $f(\infty)=1$, and $f(t)$ is smoothly strictly increasing in between.  Thus, for any $k$ we can find $0 \le t \le \infty$ s.t. $X_k = Y(t)$ has the desired conditional entropy ($t$ will be a decreasing function of $k$).


What algorithms are known for computing Craig interpolants?

Take a look at the Phd thesis of Himanshu Jain, Verification Using Satisfiability Checking, Predicate Abstraction, and Craig Interpolation.  He considers the performance of several fundamental techniques with an eye to applications in verification, and has a chapter on interpolation of formulae involving linear equations and Diophantines.

He takes a particular look at what I know as Bibel's connection method, and which he calls General Matings. These are graph-based, rather than formula-inference -based approaches to satisfiability.  If you are interested in them generally, let me recommend Dominic Hughes' reasonably short (11 pages) Proofs without syntax.


Trees: complexity of counting the number of vertex covers

The complement of a vertex cover is an independent set.  Your question is therefore equivalent to asking whether counting independent sets is #P-complete on trees.

The answer to this question is NO, it is not #P-complete: there is actually a polynomial-time algorithm to count the number of solutions.

S. D. Noble, Evaluating a Weighted Graph Polynomial for
Graphs of Bounded Tree-Width, The Electronic Journal of Combinatorics 16(1) R64, 2009. (link)

Noble actually shows much more.  Suppose the class of graphs under consideration has treewidth at most $k$.  Then the weighted graph polynomial $U$, which evaluated at a certain point yields the number of independent sets of a graph, can be evaluated in $O(a_k n^{2k+3})$ operations at any point.  Here $a_k$ depends only on $k$ and $n$ is the number of vertices in the input graph.  Hence there is a polynomial-time algorithm to count the number of vertex covers on trees (or any other class of graphs of bounded treewidth).

On the other side, it is interesting to ask: what is the smallest class that is known to be #P-complete?

  Theorem (Greenhill, 2000): counting independent sets in 3-regular graphs is #P-complete. (link).

In the comments Colin McQuillan pointed out an even stronger result:

Mingji Xia, Wenbo Zhao, #3-Regular Bipartite Planar Vertex Cover is #P-Complete, TAMC 2006, 356–364.

Note that wall graphs are 3-regular (if their corners are joined up), bipartite, and planar, but they have arbitrarily large treewidth.

Finally, a different graph polynomial $R_2$ yields the number of independent sets in a bipartite graph.  This was posed as an open question:

  Question (Ge and Štefankovič, 2010): is the exact evaluation of the $R_2$ polynomial easy for bounded tree-width graphs? (link)


This is NP-hard. See:
Joan Boyar, Philip Matthews, René Peralta. Logic Minimization Techniques with Applications to Cryptology. http://link.springer.com/article/10.1007/s00145-012-9124-7

The reduction is from Vertex Cover and is very nice.

Given a graph $(\{1,\ldots,n\},E)$ with $m=|E|$, define an $m \times (n+1)$ matrix $A$ as: $A[i,j] = 1$ if $j < n+1$ and $(i,j) \in E$, and $A[i,n+1] = 1$. In other words, given $n+1$ variables $x_1,\ldots,x_{n+1}$ we want to compute the $m$ linear forms $x_i+x_j+x_{n+1}$ for all $(i,j) \in E$.

A little thought shows that there is an XOR circuit for $A$ with gates of fan-in two computing the linear transformation $A$ with only $m+k$ gates, where $k$ is the optimal vertex cover for the graph. (First compute $x_{i'} + x_{n+1}$ for all $i'$ in the vertex cover, using $k$ operations. The linear forms are then all computable in $m$ more operations.) It turns out that this is also a minimum size circuit!

The proof that the reduction is correct is not so nice. I would love to see a short proof that this reduction is correct.


Tolerance parameter of statistical query model and adaptivity

What you are saying is that given $N$ random samples one cannot simulate an algorithm that makes $T$ queries to VSTAT$(N)$. If the $T$ queries are chosen adaptively then one might need more samples (the best upper bound is $\sqrt{T} N$ samples).
This is true but not an issue for the planted clique paper you mentioned. That paper is concerned with proving a lower bound against algorithms using VSTAT. Specifically we prove that any algorithm using a polynomial number of queries to VSTAT$(N)$ will not be able to solve the planted $k$-biclique problem for $N=\tilde{\Omega}(n^2/k^2)$ ($n$ is the number of vertices on each side). Answering even a single query to VSTAT$(N)$ requires $\Omega(N)$ samples so the lower bound reflects the difficulty of solving the problem with with $N$ (or less) samples.


Why were Finite Automata and Turing Machines created?

There are different questions being asked here. It is important to keep in mind that most courses on this topic are designed to clearly communicate and deepen a student's understanding of the concept of computation.

Historical motivation and precedence is not usually required to communicate the current understanding of the concepts or even their current relevance. Moreover, historical and philosophical issues are often subtle and doing them academic justice requires time and training that is not usually part of a computer science curriculum.

The creation of Turing Machines I think it is simplistic to believe that Turing Machines were created only to address the Entscheidungsproblem. The theory of computation was an idea whose time has arrived. There were several equivalent models of computation developed in that period with different motivation. The different models were not developed in isolation. Post developed a model of mechanical calculation in addition to more mathematical models of Church and Kleene. Electro-mechanical calculational devices were also in the background of such developments. Turing may have developed his model specifically motivated by a specific problem, but he did not work in a vacuum and his historical and intellectual context should not be discounted.
The creation of Finite Automata I would disagree that finite-automata were over two decades apart from the development of computational devices. McCulloch and Pitts proposed a model similar to finite automata while studying human cognition in the early 40s. The modern heritage of finite automata goes back to Rabin and Scott. Their paper is a model of clarity and is one search away. The first two words  "Turing machines" show that they were clearly aware of Turing machines.
The modern presentation of computability theory It is not true that the material we learn and teach about finite automata was developed independently of work on Turing machines. The material you are taught was developed in the awareness of results of Turing machines and the motivation for these results is clearly available in the work of Rabin and Scott.

I appreciate the desire to know about historical origins, but it is very important to appreciate that this is a nuanced topic and you cannot always find simple answers. Often, we do not even know when or why a concept was developed.

Regarding your last paragraph, the historical origins are, in my opinion, not a good source of motivation for or understanding about the essence of computation. In fact, they are a pretty bad source for undergrads. There are many contemporary essays, books, talks and the like about why computation is important, universal, beautiful, fascinating, and deep. That's where you should be looking. Here are a few random starting points in no particular order.

The Algorithm: Idiom of Modern Science
The emotion universe
The Computational Universe
Great Ideas in Theoretical Computer Science
The Computational Universe
Computers Ltd. What They Really Can't Do
The Unusual Effectiveness of Logic in Computer Science
And Logic Begat Computer Science: When Giants Roamed the Earth


For the second problem, this question is no harder than finding a cycle of a specific weight k in a general weighted graph in the following sense: consider the line graph of G, that is, a graph L(G) with V(L(G)) = E(G), and two nodes u,v in L(G) are adjacent if the corresponding edges in G are incident to each other. By assigning weights to the edges of L(G) according to your definition, it reduces to the normal weighted cycle problem.

Thus to the first problem, in general if we do not have any constrain on k, we can assign 1/|V(G)| to each edge in an unweighted graph G, and reduced the Hamiltonian cycle problem to the weighed cycle problem by asking k=1, thus it is NP-hard. If you are asking non-negative integral weights, then the algorithm mentioned in the MO post again works since we can subdivide the edges into an unweighted graph. But be careful since the size of the subdivided graph will depends on the total weight on the original graph.


The second definition uses the hitting set formulation, which is equivalent to the set cover problem. To see that, you may reverse the roles of sets and elements.  You can find more information on the wikipedia page.


Persistent data structures in RAM computational model

Paul F. Dietz's "Fully Persistent Arrays" uses a variant on van Emde Boas trees, which rely on arrays and also on integers being represented as words.
Brodal et al.'s "Fully Persistent B-Trees" relies on arrays.
Davoodi et al.'s "Cache-Oblivious Persistence" applies a persistence transform to data structures that don't necessarily work in the pointer model.
The Bentley-Saxe logarithmic method, also known as cache-oblivious lookahead arrays is naturally partially persistent, and relies on arrays for the insert time to be $o(\log_B n)$ in an external-memory setting.


Transitioning from quantum to classical random walks on the line

Great question. Actually, the same question popped up in something I was working on a few months ago (arXiv:1011.1217). It seems that any natural kind of decoherence leads to behaviour that looks initially balistic, but which becomes diffusive as time increases, so you are transitionioning between a $t$ regime and a $t^{\frac{1}{2}}$ regime. See figure 2 in the above paper for an example of this. This seems to be the natural behaviour as your state gradually loses coherence.

This would seem to suggest that the variance only ever scales as $t$ or $t^2$, and hence the walk spreads as $t^{\frac{1}{2}}$ or $t$.

However, exactly the same thing happens in quantum metrology when noise is introduced, but can be overcome to yield an intermediate scaling (see for example J. A. Jones et al, Science, 324, 5931 (2009), arXiv:1103.1219, arXiv:1101.2561, etc.). One way this can be achieved is by making intermediate measurements.

Imagine you measure the position of the walker after every period of time $T$ collapsing the wavefunction, and allow free evolution in between. Now, imagine we want to evolve the system for total time $t=nT$. Then the variance in the position of the walker after this time will be $\mbox{Var}(x(nT)) = \sum_{i = 1}^n \mbox{Var}(x(T)) = n \mbox{Var}(x(T))$. In the absence of other decoherence we know the walker moves ballistically, and hence $\mbox{Var}(x(T)) = T^2$, and so the $\mbox{Var}(x(t)) = n T^2$. However, as $t=nT$, we can take $n\propto t^k$ and $T\propto t^{1-k}$. Thus $\mbox{Var}(x(t)) = t^{2-k}$. This way you can achieve any intermediate scaling, by chosing the measurement interval appropriately.


A comment upgraded to partial answer:

There is quite some work these days on a conjectured (or not) quantum version of the PCP theorem: see for example this blog post by Scott Aaronson
http://www.scottaaronson.com/blog/?p=139
or this answer by Peter Shor on MathOverflow
https://mathoverflow.net/questions/45106/quantum-pcp-theorem/45167#45167

Concerning quantum approximation alpgorithms, you can look at this reference "Approximation algorithms for QMA-complete problems"
http://arxiv.org/abs/1101.3884


Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?

I've written the following to talk about the connections between quantum computation and the (extended) Church-Turing thesis. Your question appears to have several other questions, which I don't address due to space (and time to write down this answer).

A statement that reads, "There exists no "reasonable" computational model capable of recognizing languages that a Turing Machine cannot"

This is essentially what the Church-Turing thesis states. It is not the extended Church-Turing thesis, which roughly takes the form:

All "reasonable" computational models can simulate each other with polynomial overhead

Of course, what "reasonable" means must itself be pinned down. For example, if you let $\mathsf{Halt}$ be an oracle to the halting problem, then the computational model $\mathsf{TM}^{\mathsf{Halt}}$ of Turing Machines equipped with halting oracles can compute strictly more than that than that of simply Turing machines.
So if $\mathsf{TM}^{\mathsf{Halt}}$ is viewed as "reasonable", then the CT thesis is already false.
For this reason, "reasonable" is usually phrased as "hypothetically realizable in the real world". As there is no proposed mechanism to create a universal $\mathsf{TM}^{\mathsf{Halt}}$ machine in the real world, this computational model would not be considered "reasonable".
What does this mean for the extended CT thesis, and quantum computation? The complexity class $\mathsf{BQP}$ is the class of problems solvable (with bounded error) by a quantum computer efficiently. You should view it as a quantum analogue of $\mathsf{P}$ (more properly of $\mathsf{BPP}$, or "two-sided error, randomized $\mathsf{P}$", but still).
If quantum computers (which can compute arbitrary problems in $\mathsf{BQP}$) are physically realizable, the extended Church-Turing thesis posits that they can only get a polynomial speedup over "traditional" models of computation. If this is the case, the extended Church-Turing thesis still holds, and quantum computing is in a certain sense "more boring".
Preliminary evidence suggests that this is not the case though. There are a variety of problems which are known to have exponential speedups on quantum computers, famously factorization and the discrete logarithm problem via Shor's algorithm.
While these are large "practical" reasons for investigating quantum computation, they are actually not the theoretically most compelling reason.
Both factorization and discrete log are in $\mathsf{NP}\cap\mathsf{coNP}$, and therefore unlikely to be $\mathsf{NP}$-hard unless the polynomial hierarchy collapses.
This means that "Shor's algorithm leads to an exponential speedup for factoring and discrete log" isn't super interesting from a complexity theory point of view, as it's entirely consistent with current thoughts that both of these problems are actually in $\mathsf{P}$ (or $\mathsf{BPP}$).
There are problems which are more interesting to consider though.
In particular, the Boson sampling line of work posits a particular problem which is $\#\mathsf{P}$-hard, but is in $\mathsf{BQP}$.
This means that this particular problem is highly unlikely to be in $\mathsf{P}$, as this would collapse the polynomial hierarchy to the third level, which is thought to be unlikely by complexity theorists.
So the reason that people bring quantum computing up when discussing the (extended) Church-Turing thesis is that, if sufficiently "physically realized", it provides exponential speedups on practically important problems (factoring and discrete logarithm), as well as an exponential speedup on a problem which is "harder than $\mathsf{NP}$-complete". This would constitute a violation of the extended Church-Turing thesis.


Small $\epsilon$-nets for points and half-planes without VC dimension

For the particular case of points and half-planes, there is a simple (but a little tricky) argument that there is $R\subset X$ of size $r$ such that the supporting open half-planes of the convex hull of $R$ each contain at most $O(\log r)/r$ points of $X$. (Such half-planes are exactly the set of half-planes that are bounded by a line through two points of $R$ and contain no points of $R$.)

Also, any open half-plane that contains no points of $R$ is contained in two such supporting half-planes. (I won't give a proof of this.)

Therefore, $R$ is an $\epsilon$-net for a size $r$ which is $O(\log(1/\epsilon)/\epsilon$.

For the existence of such an $R$, suppose $R$ is a random sample of $X$ of size $r$, each member of $R$ chosen independently. Let $\cal H$ be the set of at most $r(r-1)$ open half-planes $H$ bounded by lines through two (or more) points of $R$, and let $\cal H'\subset \cal H$ be the set of $H\in\cal H$ that contain at least $\alpha |X|$ points of $X$, where $\alpha > 0$ is to be determined. For a given $H\in {\cal H}$, the probability that it is in $\cal H'$, and that none of the other $r-2$ points of $R$ falls in $H$, is at most $(1-\alpha)^{r-2}\le \exp(-\alpha(r-2))$. There is $\alpha = O(\log r)/r$ such that this probability is at most $1/2r(r-1)$. Since $\cal H'$ has at most $r(r-1)$ members, by a union bound, the probability that every member of $\cal H'$ contains a point of $R$ is at least $1/2$. So there is some $R$ such that every supporting half-plane of its convex hull contains at most an $\alpha = O(\log r)/r$ fraction of the points of $X$.

This sort of argument goes back to at least 1985, where $\epsilon$-net results were given for balls and halfspaces, and given in more generality in 1986, where results for $\epsilon$-nets and a kind of partial $\epsilon$-approximation were given. The set $\cal H$ above, a collection of half-planes defined by a set of points, is generalized to a collection of "regions" defined by a set of "objects", where the number of defining objects is typically a function of the dimension, but the simple union bound argument is the same. However, not all range spaces of bounded VC dimension fit in this framework.


What greedy algorithm satisfies greedy choice property but does not have optimal substructure?

One of the standard estimators in robust statistics is a type of trimmed mean where you choose a majority subset of a set of input numbers in such a way as to minimize the maximum difference between any two selected numbers, and then take the mean of the selected subset. There's an easy greedy-choice first step: choose the median as part of your subset. But once you've made that choice, the remaining problem is not of the same type (i.e. we don't have optimal substructures), so there's no obvious method of continuing this algorithm greedily. In particular it doesn't work to keep choosing medians of the remaining points. (The repeated greedy median strategy, done with a little care, gives the interquartile mean which is also robust but does not solve the same problem and has a lower breakdown point.)


Treewidth of deep Sierpiński Sieve Graph

You can recursively decompose each triangle into a smaller triangle and a trapezoid, and each trapezoid into two smaller triangles. The corresponding tree decomposition (whose bags contain the corners of a triangle at one level of the decomposition and a triangle or trapezoid at the next or previous level) has five vertices per bag and therefore has width four.

There is no $K_5$ minor, because the graph is planar. There is, however, a $K_{2,2,2}$ (octahedron) minor (actually, a subdivision), shown below. As this is one of the forbidden minors for treewidth three, the width is four.


What are the uses of Limits and Colimits of Category Theory in every day problems?

Take some relations $R_0\subseteq A_0\times A_1$, $R_1\subseteq A_1\times A_2$. Let $\pi_1:R_0\to A_1$, $\pi_0:R_1\to A_1$ be projections with domains restricted to relations $R_0$, $R_1$. Then the pullback of $\pi_0$, $\pi_1$ is the join of $R_0$ and $R_1$ in the SQL sense.


Space requirements for solving True Quantified Boolean Formulas problem

The main difference between time and space is that you can reuse space that is not needed anymore.

If you return from the recursive call that evaluates $A$, you can reuse the space used by this computation to compute the value of $B$.  Because of this you only need to store one branch of the decision tree of the original QBF formula in memory, which gives you a linear space requirement.

This fact is explained quite well in standard introductory text books on Complexity Theory.  You can have a look into Sipser's Introduction to the Theory of Computation, for example. On page 332 (3rd edition) he explains the space requirement for SAT, of which QBF is a generalization.


Applications of computer science in biology

Quite a few programs have resulted from the application of notions from theoretical computer science or mathematics to problems in biology. This includes phylogeny, sequence alignment, and genome rearrangement (see this, chapter 15) software. But you may be asking too many or too unfocused questions at once.


random sampling DAGs via nilpotent matrix sampling

For question 2 the first answer is "yes": if $M$ is a $0-1$-nilpotent matrix, then it is the adjacency matrix of some digraph.
Now $M^k_{i,j}$ is well-known to be the number of paths of length $k$ between vertices $i$ and $j$. Meanwhile, there exists some integer $\nu$ such that $M^k=0$ for $k \ge \nu$, so there are no paths of size greater than $\nu$ in the graph, in particular there cannot be any oriented cycle, hence the graph is a DAG.
For the rest of your questions, I have a mixed answer: indeed your going to get all adjacency matrices (as you're saying, this is just shuffling the topological order) ; and since the set of strictly upper triangular $0-1$-matrices of size $n$ along with the set of permutations of $n$ elements, each DAG of order $n$ will appear with positive probability.
Now I'm guessing what you want is that this probability is greater than some bound for any $n$, and this seems doubtful. Take for instance the path of size $n$, up to relabeling there are $n!$ of them. But there are $2^{(n-2)n \over 2}$  strictly upper triangular $0-1$-matrices of size $n$ and $n!$ way to shuffle each of them, so the probability of getting a path goes to $0$ exponentially fast.


Subset sum vs. Subset product (strong vs. weak NP hardness)

Firstly, using exponentiation to go from SS to SP works (using base 2 rather than base $e$), but blows up the size of the numbers involved. Weak NP-hardness means that if the numbers are small (or more precisely, denoted in unary), the problem is no longer hard. Hence, using exponentiation creates exponentially sized instances of SP even for the easy instances of SS, where the numbers are written in unary.

Secondly, using logarithms to go from SP to SS doesn't work, as logarithms typically generates non-integer values. SS and SP are defined using integer numbers, and logarithms often result in transcendental values, which are hard to represent or do math on.

<edit>

Let $A$ be an integer, $A > 0$, then $\log_2 A$ is rational if and only if $A$ is a power of 2, and transcendental otherwise. Firstly, if $\log_2 A = \frac{p}{q}$ for nonzero integers $p$ and $q$, then $A = 2^{\frac{p}{q}}$, $A^q = 2^p$. We therefore have that $A = 2^r$ by prime decomposition. Furthermore $A^{rq} = 2^p$, so given an $A$ we can pick $q=1$ and $p=r$ to prove $\log_2 A$ is rational.

We just need to show that $\log_2 A$ is never transcendental otherwise. This follows from the Gelfond-Schneider theorem, for an equivalent formulation (as can be found on the Wiki page) is "if $\alpha$ and $\gamma$ are nonzero algebraic numbers, and we take any non-zero logarithm of $\alpha$, then $(\log \gamma)/(\log \alpha) = \log_\alpha \gamma$ is either rational or transcendental." It is also easy to verify by taking the converse of the theorem and setting $\alpha^\beta = \gamma$ and hence $\beta = \log_\alpha \gamma$.

</edit>

Lastly, consider what happens when we try the dynamic programming algorithm from SS on SP. Because we use products rather than sums, the numbers involved blow up enormously, and the arbitrary precision math required suddenly becomes a factor in the running time. This is why the algorithm cannot solve SP instances quickly even if the numbers are in unary.


How would a theory of computation course that culminated in lambda-calculus as "the" model of computation, instead of Turing machines, look like?

The kind of approach to theory of computation you describe is what I like to call an abstract machine based computability theory:
i.e. a theory that define computable functions/languages/etc via some abstract kind of machine (automata, linear automata, Turing
machine etc).

An approach that uses $\lambda$-calculus instead of Turing machines could be thought as an expressions based computability theory:
i.e. a theory where one prescribe some basic operations which are intuitively calculable and some operators defined between them to
build other computable operations.

In this expression based computability theory

regular expressions correspond to finite state automata;
linear and context free grammar correspond to pushdown automaton and linear bounded automaton
(untyped) $\lambda$-calculus correspond to Turing machines
I don't know very much about complexity in $\lambda$-calculus but I guess  it could be approached as done for complexity of $\mu$-recursive function or of logic formulas, classifying $\lambda$-terms in complexity
classes by their structure (then of course it would be nice to compare these complexity classes with complexity classes for other models of computation, like Turing machines).

Hope this helps.


Algorithms with multiple right answers --- complexity theory terminology

I think algorithm is the right word. An algorithm doesn't need to decide or compute a function.

The type of problems you want is called search problems in complexity theory. For example, see the definition of the complexity class FNP. But we still refer to the algorithms solving them simply as algorithms.

There is also the notion of multifunction which is used in computability, but again it is for problems not algorithms.