Expected length of longest construction path in Barabási–Albert Model The Barabási-Albert Model is used for constructing scale-free networks using the preferential attachment technique. The essence, as I understand it, is that nodes are incrementally added to a graph by adding an edge to an existing node selected with probability proportional to the number of edges connecting the node. The algorithm starts on some initial clique, $G$.

Now let's assume that newly added nodes are labelled $0, 1, 2, \ldots$.
Define a construction path to be a path $l_0l_1l_2\ldots l_n o$ in the generated graph such that $o$ is a node from the initial clique $G$, $l_n<\cdots<l_2<l_1<l_0$ and $l_0$ is maximal.

Clearly, at one extreme, such paths will be of length $1$, when all newly added nodes connect to one of the initial nodes.
At the other extreme, the length of the path will be equal to the number of nodes added to the graph. Both of these cases are extremely unlikely.

I'm interested in the average case.  Are there any known results about the expected value of the lengths of construction paths?

NB. Construction path is a name I invented for this question: please let me know if such paths go by another name.

(Answer-in-progress, according to comments.)

I will look at a special case, and then discuss how it relates to the general case. The special case is $m=1$ and $V(G)=\{0\}$ with no edge. The added vertices, in order, are $1,2,\ldots,n$, starting from $1$.

Let $d_{i,n}$ be the degree of vertex $i$ divided by $2n$. So $\sum_{i=0}^n d_{i,n}=1$. Let $l_i$ be the length of the longest path from $i$ to $0$ that visits vertices in decreasing order. (Vertices added after $i$ do not affect decreasing paths starting from $i$, so there is no need for $l_{i,n}$.) Both $d_{i,n-1}$ and $l_i$ are random variables. The generating model for these variables is how you'd expect: Once we fixed their values for $n-1$, we pick a number $k_n$ from $\{0,\ldots,n-1\}$ according to the probabilities $d_{i,n-1}$, and compute $d_{i,n}$ and $l_n$ as if we added edge $nk_n$.

We have that $l_n=1+l_{k_n}$, where $k_n$ is a random variable drawn from $\{0,\ldots,n-1\}$ according to the distribution given by $d_{k,n-1}$. In other words, $l_n=1+\sum_{i\lt n}[k_n=i]l_i$ and $\mathbb{E}[l_n]=1+\sum_{i\lt n}d_{i,n}\mathbb{E}[l_i]$. (The independence here is a bit tricky. In the comment on the post I said it does not hold, but I think it does. The trick is to think of this as a stratified generative model, such that the choice of $k_n$ is independent from $l_i$, but drawn from a certain distribution.)

Let's assume, without proof for now, that $d_{i,n}$ depends on $i$ as $\Theta(i^c)$ for some constant $c$.

Now, let's assume $\mathbb{E}[l_n]=O(f(n))$, and see what properties should $f(n)$ have. According to the recurrence on $\mathbb{E}[l_n]$, we should have that
$$
\sum_{i=0}^{n-1} i^c f(i) \Big/ \sum_{i=0}^{n-1} i^c = O(f(n))
$$
In the continuous approximation, this is
$$
\int_1^n x^c f(x) \,dx = O(n^{c+1}\cdot f(n))
$$
One function that has this property is $f(n)=\log n$.

But, does $d_{i,n}$ grow like $i^c$ (for fixed $n$)?

When $m=1$, we can write a recurrence on vertex degrees. The arc $ni$ occurs with probability $d_{i,n-1}$, so $$d_{i,n}=d_{i,n-1}\frac{2(n-1)d_{i,n-1}+1}{2n}+(1-d_{i,n-1})\frac{2(n-1)d_{i,n-1}}{2n}=d_{i,n-1}\Bigl(1-\frac{1}{2n}\Bigr)$$ The border conditions are $d_{n,n}=1/2n$ and $d_{0,1}=d_{1,1}=1$. Now apply linearity of expectation and approximate $\sum_k\log\Bigl(1-\frac{1}{2k}\Bigr)$ with an integral. Alternatively, note that $d_{i,n}/d_{i-1,n}=d_{i,i}/d_{i-1,i}=(i-1)/(i-1/2)$, so $d_{i,n}$ is roughly $\Gamma(n)/\Gamma(n+1/2)$.

Both approaches lead to $\mathbb{E}[d_{i,n}]=\Theta(i^{-(1/2)})$.

For $m=2$, you draw two variables $k_n$ and $k'_n$ from $\{0,\ldots,n-1\}$ according to $d_{i,n}$, and we keep just the maximum. This is like picking just one variable, $\max\{k_n,k'_n\}$, but from a different distribution. The question is if this distribution is still $\Theta(i^c)$ for some (other) $c$. Let $d^{(2)}_{i,n}$ be this distribution. We have, dropping the $n$ subscript, $d^{(2)}_i=2\sum_{j=0}^i d_i d_j + d_i^2$. So, $d^{(2)}_i=\Theta(1/i)$. In fact, $d^{(2m)}_i=2\sum_{j=0}^i d^{(m)}_i d^{(m)}_j + {d^{(m)}_i}^2$. Again based only on some quick-and-dirty calculations, I believe that for $m\gt 2$ we have $d^{(m)}_i=\Theta((\log i)^{cm}/i)$, which would seem to say that the $O(\log n)$ bound on $\mathbb{E}[l_n]$ doesn't work anymore.

The only thing that matters about the seed graph is how many edges it has. I didn't look at how this affects the answer, but, again, it cannot increase the expected length.


Why doesn't computer science follow biology more closely in computer design? Nature has proved with the brain that it can create complex computers with very little energy consumed and released, extremely low energy compared to a common computer.

However, I noticed the design is completely different, why hasn't anyone tried to or succeeded to create a similar one?

For example:

1) Computers use memory as the main building block. After that, a processor is used to manipulate it.

2) However, biological computers do not use memory as the main building block. This is a by-product. The main building block appears to be a combination of static geometry and design of the computer (DNA) which is combined with the energy generators (mitochondria, components of both DNA and energy transfer).

This might be more suitable as a comment than an answer.

From computability point of view, any machine which uses finite memory (but not necessarily constant) at any point in time and modifies it according in a local way is equivalent to Turing machines (this is an informal statement of a result by Robin Gandy from 1980 IIRC). On the other hand Turing Machine models are simpler to deal with in many respects and therefore are easier as a object of study. Natural models of computation are usually more complicated to study.

There are also studies into natural models of computation. You may want to take a look at Aaron's answer here.


Why is it difficult to develop a subexponential functoral approach to discrete log Call a discrete logarithm algorithm functoral if the commutative algebraic object that the algorithm acts on can be changed with another commutative object in the same category and the algorithm does not asymptotically slowdown.

Why is it difficult to develop a single functoral discrete logarithm (classical) algorithm that works on all commutative groups?

The reason that sub exponential algorithms for the discrete log in $\mathbb{Z}/p\mathbb{Z}$ do not carry over to groups based on elliptic curves is because $\mathbb{Z}/p\mathbb{Z}$ has extra structure that doesn't seem to be present in elliptic curve groups.

In particular, $\mathbb{Z}/p\mathbb{Z}$ has both addition and multiplication, whereas the elliptic curve groups have only one operation.  The sub exponential algorithms for the discrete log in $\mathbb{Z}/p\mathbb{Z}$ make essential use of this: the extra structure allows us to define the notion of a smooth integer.  A smooth integer is an integer that factors into small primes; here the notion of "small" makes use of this additional structure (namely, the addition operation).  This notion of smoothness is critical to the effectiveness of the sub exponential algorithms for $\mathbb{Z}/p\mathbb{Z}$.

Any discrete log algorithm that relies upon "smoothness" (or this additional structure) is therefore not going to be "functoral".  A consequence is that the best existing techniques we know of for computing the discrete log in $\mathbb{Z}/p\mathbb{Z}$ are not functoral and do not carry over to elliptic curve groups.

Why is it hard to develop an efficient functoral algorithm for the discrete log in $\mathbb{Z}/p\mathbb{Z}$?  Because if you want it to be functoral, you're disallowing use of smoothness, which is essential to all known techniques.

See, e.g., http://en.wikipedia.org/wiki/Index_calculus_algorithm and http://en.wikipedia.org/wiki/Number_field_sieve.

Here is a second hurdle to functoral algorithms.  There are known lower bounds on the discrete log problem in "black box" groups.

A black box group is one where we do not have an explicit representation of group elements.  Instead, all we have are a few black boxes: a black box that, given two group elements, returns their product; a black box that, given a group element, returns its inverse; a black box that returns a random element of the group; and so on.  In particular, in a black box group, you cannot do something like "look at the third bit of the representation of the group element and branch based upon whether it is 1 or 0".  You also can't access any additional structure (since you're only given a black box for the group operation; it's a black box group, not a black box ring).

In this setting, it is known that, if the group is of order $p$ where $p$ is a prime, there is no generic algorithm for the discrete log whose running time is better than $\Theta(\sqrt{p})$.  I'm not 100% clear on how you plan to define "functoral", but it looks to me like this implies you cannot expect a functoral algorithm whose running time is sub exponential.

See, e.g., the following paper:

Lower Bounds for Discrete Logarithms and Related Problems.  Victor Shoup.  EUROCRYPT '97.


Two matrices related by a permutation $B = P A P^T$ - complexity What is computational complexity of the following problem:

given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that:
$$B = P A P^T.$$

If it helps, one can assume that $A$ and $B$ are hermitian (or even that $A$ and $B$ are real and symmetric).

Notes:

The problem stems from checking if two sets of vectors are related by an unitary rotation, see Sets of vectors related by a rotation - MathOverflow. In that context $A$ and $B$ are their Gramian matrices.

The problem is at least as hard as the graph isomorphism problem - take $A$ and $B$ as adjacency matrices.

It is equivalent to deciding whether two given multigraphs (or edge-labelled graphs) are isomorphic or not, which is known to be equivalent to the usual graph isomorphism problem.


Is there any problem in $\mathsf{\Sigma^P_2}$ which is solvable in bounded tree width graphs? I'm looking for a problem which belongs to $\mathsf{\Sigma^P_2}$ in general graphs but is in $\mathsf{P}$ in bounded tree width graphs, In fact I think this problems are harder than using normal dynamic programming in bounded-treewidth graphs to solve them.

I think 2-clique-coloring [GT19 in Schaefer and Umans] is an example. The question is whether the given graph can be (improperly) 2-colored in such a way that none of its maximal cliques are monochromatic. For graphs of bounded treewidth, each maximal clique should occur within a single bag of the tree decomposition, so it should work to use the standard dynamic programming approach in which the states of the dynamic program are 2-colorings of the bag that correctly color all maximal cliques within the bag and are consistent with good states of the child bags.


maximizing inner product Given two lists $L,L'\subseteq\mathbb{R}^d$ of $n$ vectors each,
how fast can we compute for all $p\in L$ the vector of $L'$ that maximizes the inner product with $p$, i.e., $\arg\max_{p'\in L'} \langle p, p'\rangle$.
I am only interested in $d=3$ (and possibly $d=4$).

For three-dimensional vectors, construct the three-dimensional convex hull of the vectors in $L'$ in time $O(n\log n)$. The maximizer for a vector $v$ in $L$ is the point of the convex hull that is most extreme in the direction of $v$, and extreme-vertex queries may be answered in logarithmic time by using a Dobkin-Kirkpatrick hierarchy for the convex hull. For this part see e.g. O'Rourke's Computational Geometry in C, pp. 272ff. So the 3d problem can be solved in total time $O(n\log n)$.

For 4-dimensional vectors, the same thing would work, but you don't want to construct the convex hull because it's too expensive. Instead, it is possible to process a set of $n$ points in time and space $\tilde O(m)$ (for any $m$ between $n$ and $n^2$) so that you can answer extreme-point queries in time $\tilde O(n/\sqrt{m})$; see Corollary 8(iii) of Agarwal and Erickson's range query survey. Choosing $m=n^{4/3}$ gives total time $\tilde O(n^{4/3})$ to set up a data structure for $L'$ and query all vectors in $L$.


Average-case randomized communication complexity in the small-advantage regime Let $f\colon \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}$. I'm interested in randomized communication protocols $\pi$ that compute $f$ in the weak sense that
$$
\Pr_{x, y}\left[\Pr_r[\pi(x, y, r) = f(x, y)]\geq 1/2 + \varepsilon\right] \geq 1/2 + \varepsilon,
$$
where $r$ is the internal randomness of $\pi$ and the inputs $x, y$ are sampled independently and uniformly at random from $\{0, 1\}^n$. What upper/lower bounds are known in this setting? E.g., for the inner product mod 2 function $f(x, y) = \langle x, y\rangle$, are $\Omega(n - \log(1/\varepsilon))$ bits of communication required?

It is big open problem to prove lower bounds. This would imply lower bounds for BP.PP communication protocols (e.g., Tarui's Theorem in communication complexity), which would then imply lower bounds on matrix rigidity (over the real numbers).
For inner product, there is $O(1)$-bit public coin protocol for $\epsilon=1/n^{O(1)}$. Let me simplify by assuming that all $x_i$ and $y_i$ are IID and get value $1$ with probability $1/\sqrt{2}$ so that $x_i=y_i=1$ with probability $1/2$. This simplifies the calculations (the uniform distribution is similar). Observe that $\langle x,y \rangle \in [0,n]$ is binomially distributed with mean $n/2$. Note that for $c\ll\sqrt{n}$ we have $\langle x,y\rangle \in n/2\pm c$ with probability $\Theta(c/\sqrt{n})$.
For warm up, consider the following protocol: Sample random $i\in[n]$ and accept if $x_i=y_i=1$. Assuming $n$ is odd, $\lfloor n/2\rfloor$ is even and $\lceil n/2\rceil$ is odd, this protocol guesses $IP(x,y)$ right (with advantage $\approx 1/n$) whenever $\langle x,y\rangle \in \{\lfloor n/2\rfloor,\lceil n/2\rceil\}$, which occurs with probability $\Theta(1/\sqrt{n})$ over $(x,y)$.
More generally, using the connection between small-advantage computations (class PP) and low-degree polynomials approximating Xor for inputs of Hamming weight $n/2\pm c$ (e.g, The expressive power of voting polynomials) there are $O(c)$-bit protocols that guess $IP(x,y)$ right (with advantage $1/n^{O(c)}$) when $\langle x,y\rangle \in n/2 \pm c$.
When $\langle x,y\rangle$ is outside middle interval, $\langle x,y\rangle \notin n/2 \pm c$, we expect the protocol to err on roughly half the inputs $(x,y)$. Choosing a large enough constant $c$, the correctness in the middle interval starts dominating: protocol guesses right with probability $1/2+\Theta(c/\sqrt{n})$ over $(x,y)$.


Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges A walk in a graph is a finite or infinite sequence of edges which joins a sequence of vertices. A trail is a walk in which all edges are distinct. Note that a trial may visit a vertex multiple times as long as no edge is revisited.

Given a directed graph $G=(V,E)$ where the weight of each edge may be negative. Let $s,t \in V$ be our source and destination vertices, respectively. We are asked to find the shortest $s-t$ trail in $G$.

This problem seems harder than the elementary shortest path problem. But I failed to reduce it to this problem. I've also tried to do reductions from Hamiltonian cycle or feedback arc set, however I failed again. Could you please shed some light upon it?

The longest path problem can be reduced to this problem. Let $G = (V,E)$ be an instance of longest $s,t$-path problem. For each vertex $v \in V$ create two vertices, $v_{in}$ and $v_{out}$, and a directed edge with weight $-1$ from $v_{in}$ to $v_{out}$. For each edge $(u, v) \in E$, create an edge from $u_{out}$ to $v_{in}$ with weight $0$. Now each trial in this graph corresponds to a simple path in the graph $G$, and the edges with weight $-1$ count its length.


Finding mapping between two spatial representations of the same objects I have two matrices $U$ and $V$.  $U$ is $n \times n$ and $V$ is $n \times m$. (Both are empirical results of an experiment.) I would like to find a linear transformation $A$, $m \times n$, such that $VA = \hat{U}$, where $\hat{U} = \underset{X}{\arg \min}$ $m(X, U)$ for some metric $m$.

Is there a closed form or iterative solution to this problem?

If your error norm is the Frobenius distance (that is, $m(X, U) = \|X - U \|_F$, then there is a closed form for your problem. $A = V^+ U$, where $V^+$ is the Moore-Penrose pseudoinverse of $V$ (this is a generalized inverse for non-square matrices).


Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply? A decade ago I observed what I dub "Murphy's Law of Complexity Theory": whenever a new separation or collapse is discovered, the question is answered in the direction that makes $P\overset?=NP$ most challenging to determine. I do not believe this rule has failed once in the intervening years. This leads me to wonder what the implications would be if the Law were actually true.

What questions could be answered using this conjecture? Are the answers consistent, or is there some set of questions such that they can't all be answered in the way that makes proving $P\overset?=NP$ most challenging without causing inconsistencies?

A counterexample to this Murphy's Law could actually be the famous paper

Baker, Theodore; Gill, John; Solovay, Robert, Relativizations of the $\cal P=?\cal N\cal P$ question, SIAM J. Comput. 4, 431-442 (1975). ZBL0323.68033.

It shows that the $P=^? NP$ question is

hard: you cannot solve it with relativizable techniques; but also
easy: we can establish $P^A= NP^A$ for some oracles $A$, and $P^B \ne NP^B$ for some oracles $B$, so now we just have to figure out what whether a trivial oracle is more like $A$ or like $B$...


Optimal greedy algorithms for NP-hard problems Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive algorithms for many problems in P. More interestingly, for some NP-hard problems the obvious and natural greedy/local algorithm results in (provably) optimal approximation factor (under suitable complexity theoretic assumptions). A classic example is the Set Cover Problem. A natural greedy algorithm gives an O(ln n) approximation factor, which is optimal unless P = NP.

Name some natural greedy/local algorithms for NP-hard problems that are provably optimal under suitable complexity theoretic assumptions.

The method of conditional expectations (for derandomizing the "random assignment" algorithms for Max-Cut and Max-SAT) can be viewed as a greedy strategy: for $i=1,\ldots,n$, you pick the value of a variable $x_i$ such that the expected number of constraints satisfied in the resulting reduced instance exceeds the expected number of constraints satisfied in the current instance. (In fact, the greedy algorithm for $1/2$-approximating Max-Cut is the same as the "method of conditional expectations" algorithm for $1/2$-approximating Max-Cut.)

Since the method also works for Max-E3-SAT and achieves a $7/8$-approximation, this is an example of a greedy algorithm which is an optimal approximation unless $P=NP$ (cf. Hastad and Moshkovitz-Raz's inapproximability results for Max-E3-SAT).


Is equivalence of unambiguous context-free languages decidable? It is well known that the equivalence problem is undecidable for general context-free languages. However, all proofs of this fact that I am aware of seem to involve some ambiguous context-free grammars. For this reason, I would like to ask if it is known whether the problem remains undecidable while restricting oneself to unambiguous context-free languages. That is, given two context-free grammars that are a priori granted to be unambiguous, is it decidable whether they are equivalent or not?

I find this problem a little intriguing, since it is known that equivalence is decidable for deterministic context-free languages, though this result is far from trivial... On the other hand, there might be some simple reason for undecidability that I have been overlooking.

This is currently an open problem.
As correctly pointed out, if it is decidable, then one expects the proof to be hard since it generalises the famous DPDA equivalence problem.
On the other hand, the classical arguments for undecidability of the CFL universality problem make use of inherently ambiguous languages, and thus one needs new ideas to show undecidability.

Let me point out that the universality problem for UCFLs is decidable (in PSPACE), using generating functions [1].

REFERENCES

[1] N. Chomsky and M. P. Schützenberger, The Algebraic Theory of Context-Free Languages, Computer Programming and Formal Systems, 1963.


Resolution augmented with the rule of symmetry or the rule of extension Krishnamurthy (here is the abstract of his paper) showed that resolution augmented with the principle of symmetry forms a proof system (referred to as SR) in which certain formulas (which do not admit short proof in resolution proof system) can exhibit  short proofs.

This also holds for the resolution proof augmented with the rule of extension (referred to as ER). He however left open the question if these proof systems SR and ER p-simulate each other.

Is there any recent work on this question?

Does SR polynomially simulate ER?

First, ER p-simulates SR: for example, ER is p-equivalent to the extended Frege proof system (EF) which is p-equivalent to the substitution Frege proof system (SF), and it is easy to see that SF p-simulates SR (the symmetry rule amounts to substitution of a special kind).

On the other hand, Urquhart [1] proves an exponential lower bound on SR refutations of Tseitin tautologies for certain graphs. Since Tseitin formulas have polynomial-size ER (or extended Frege) refutations, this shows that ER is exponentially more powerful than SR.

Reference:

[1] Alasdair Urquhart: The symmetry rule in propositional logic, Discrete Applied Mathematics 96–97 (1999), pp. 177–193, doi: 10.1016/S0166-218X(99)00039-6.


On polytope lattice points Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$.

Denote $\mathcal P(a,c)$ to be the set of convex polytopes in $\Bbb R^n$ presented by $O(n^a)$ linear inequalities with $e/d=O(n^c)$.

Is it $\#P$ complete to find number of integer points in such polytopes?
Is it $NP$ complete to decide existence of integer points in such polytopes?

I am essentially asking if the polytope is reasonably round what is the difficulty of counting and decision problems. Here for quantifying roundedness I use width and max distance (but may be some other quantification which I do not know may be appropriate).

I think some strange partition of 0/1 cube with convex faces might suffice for 1.

Let's just take the reduction from SAT to IP and see if it works. For a 3-CNF $\phi$, define a polytope $P$ which contains all $x \in \mathbb{R}^n$ satisfying the constraints

$0\le x_i \le 1$ for all $i$,
clause constraints for any clause $C$ of $\phi$: for example if $C = x_i \vee \bar{x}_j \vee x_k$ put the constraint $x_i + 1-x_j + x_k \ge 1$. (I trust you can figure out the general rule.)

Clearly $P$ has an integer point if and only if $\phi$ is satisfiable. Also the number of integer points in $P$ equals the number of solutions of $\phi$. So as long as the ratio between the diameter and the width of $P$ is polynomial, this answers both your questions.

Let us then compute its diameter and width. $P \subseteq [0,1]^n$, so the diameter of $P$ is at most $\sqrt{n}$. By width, I am assuming you mean the standard

$$
\min_{\theta: \|\theta\|_2 = 1} \max_{x, y \in P} \langle \theta, x-y\rangle,
$$

i.e. the smallest distance between two parallel hyperplanes that sandwich $P$. Notice that any $x$ which satisfies $\frac13 \le x_i \le \frac23$  for all $i$ is in $P$. So, for a $\theta$, pick $x_i$ to be $\frac23$ if $\theta_i > 0$ and $\frac13$ otherwise, and pick $y_i$ to be $\frac13$ if $\theta_i > 0$ and $\frac23$ otherwise. Then:

$$
\langle \theta, x - y \rangle = \sum_{i = 1}^n \frac{|\theta_i|}{3} = \frac13 \|\theta\|_1 \ge \frac13 \|\theta\|_2.
$$

So the width is at least $\frac13$.


Shor's factoring algorithm help I'm having a little trouble fully understanding the final steps of Shor's factoring algorithm.

Given an $N$ we want to factor, we choose a random $x$ which has order $r$.

The first step involves setting up the registers and applying the Hadamard operator. The second step a linear operator is applied. The third step the second register is measured (I believe this step can be performed later instead). The fourth step the discrete Fourier transform is applied to the first register. Then we measure the first register.

Here's where I'm a little hazy:

We get a measurement in the form $\mid j , x^k \textrm{mod} N \rangle $.

From this we can find the convergents of the fraction $ \frac{j}{2^q} $ , the convergents are possible values of the order $ r $. Here do we just try all the convergents $ < N $ and if we don't find $ r $ as one of the convergents do we just start again?

Also how does the probability for possible values $ j $ differ? They way I see it they should all have the same probability but Shor's paper says this isn't the case?

Just a little confused as some papers seem to say different things.

Thanks.

From this we can find the convergents
  of the fraction $j/2^q$ , the convergents
  are possible values of the order $r.$
  Here do we just try all the
  convergents $<N$ and if we don't find $r$
  as one of the convergents do we just
  start again?

You could; the algorithm works fairly fast if you do. If you want to reduce the expected number of quantum steps, you could also do some other tests; for example you should check whether $r$ is a small multiple of one of the convergents. But if you don't find $r$ after these extended tests, you need to start again.

  Also how does the probability for
  possible values $j$ differ? They way I
  see it they should all have the same
  probability but Shor's paper says this
  isn't the case?

I don't know whether I can help you more with this, because you haven't given me enough information for me to tell why you're confused. The probability for each value of $k$ in the fraction $k/r$ is (very nearly) the same. However, depending on exactly where $k/r$ falls between the adjacent values of $j/2^q$ and $(j+1)/2^q$, the probabilities of the specific values of $j$ differ.


Elementary bounds on parameter in fixed-parameter tractability? In the definition of (strong) fixed-parameter tractability, the time bound is an expression of the form $$f(k).p(|x|),$$ where the input instance is $(x,k)$ with parameter $k$, $p$ is a polynomial, and $f$ is a computable function.

It is possible to replace the computability requirement for $f$ with other classes of functions, as long as the notion of reduction is similarly restricted.  (For instance, Flum and Grohe cover exponential and subexponential families in chapters 15–16 of their textbook, with the associated erf and serf reductions.)

  Has anyone studied the family of elementary functions for the parameter bound $f$?

An elementary function can be bounded above by a fixed tower of exponentials, so this class is closed under composition.  The growth in the parameter in a reduction must then be bounded above by an elementary function as well.

There do exist interesting problems from automata theory which are fixed-parameter tractable, but where the parameter bound is non-elementary (unless P = NP, see Frick and Grohe, doi: 10.1016/j.apal.2004.01.007).  I am wondering if anyone has looked at the fixed-parameter tractable problems which exclude fixed values of the parameter leading to such "galactic" constants (to use Richard Lipton and Ken Regan's term).  Speculating wildly, such a restriction might have useful connections with finite model theory, such as being characterized by a fragment of monadic second-order logic that doesn't lead to the non-elementary constants that can arise from applying Courcelle's Theorem to a fragment with unbounded quantifier alternation.

In his dissertation thesis "Modiﬁzierte parametrische Komplexitatstheorie", Mark Weyer considered, among other things, hierarchies within FPT w.r.t. the function f and reductions between them.   He also did indeed relate these sub-hierarchies to fragments of FO and MSO: Chapter 6 is essentially about the relation between FO/MSO (the number of quantifier alternations of the formulas) and the function f(w) in Courcelle's theorem (w being the treewidth).  He considered both upper and lower bounds and, using the aforementioned reduction framework between certain hierarchies within FPT, he was able to give quite tight bounds.  The examiners of the thesis were Flum and Grohe.

Unfortunately the thesis is in German, and I'm not aware whether material of his thesis has been published in an English journal.  I'm therefore aware that they might be of limited use for you, but nevertheless the references therein might be a good starting point.


Prime factorisation of decidable problems Disclaimer: I am not a theoretical computer scientist.

The set of decidable problems $\mathbb{D}$ is countable so $\lvert \mathbb{D} \rvert = \lvert \mathbb{N} \rvert$ and this led me to the following idea.

Given two decision problems $p,q$ in $\mathbb{D}$ and $\mathcal{M}_p,\mathcal{M}_q$ the minimal-length Turing Machines deciding $p$ and $q$ we may say that $p$ and $q$ are relatively prime if:

\begin{equation}
K(\mathcal{M}_p|\mathcal{M}_q) = K(\mathcal{M}_p) \tag{1}
\end{equation}

and

\begin{equation}
K(\mathcal{M}_q|\mathcal{M}_p) = K(\mathcal{M}_q) \tag{2}
\end{equation}

where $K(\cdot)$ denotes Kolmogorov Complexity.

I think we should then be able to define $\mathbb{B} \subset \mathbb{D}$ such that $\lvert \mathbb{B} \rvert = \lvert \mathbb{D} \rvert$ and:

\begin{equation}
\forall b \in \mathbb{B} \forall d \in \mathbb{D} \setminus \{b\}, K(\mathcal{M}_b|\mathcal{M}_d)=K(\mathcal{M}_b)  \tag{3}
\end{equation}

where $\mathbb{B}$ is analogous to the set of primes in $\mathbb{N}$. Has this idea been explored?

I think a candidate for such a set $\mathbb{B}$, or something very much like it, could be produced by considering an infinite sequence of singleton languages: $L_1=\{w_1\},L_2=\{w_2\},\ldots$ --- where the $w_1\cdot w_2\cdot\ldots$ form an incompressible sequence. You might be able to shave off a bit here or there (this will strongly depend on the encoding -- which is why Kolmogorov complexity really only makes sense up to an additive constant). But modulo additive constants, this family of strings has the property where being given one of them as input does not in any way help in generating any other one.


Formal definition of parser? I'm looking for an accepted, formal definition of a parser as function $f$ returning an AST, but I cannot find any reference in literature; all I can find is the definition of a recognizer as a function $f:\Sigma^*\to \{0,1\}$ with obviously $f(w)=1$ when $w\in L(G)$ and $0$ otherwise ($G$ being a grammar and $L(G)$ the generated language).

There is more in recognition that appears at the first sight. It is naturally generalized into recognizing all the substrings of a given string so that the output is a matrix A where matrix element A[i,j) corresponding to semiopen interval/segment [i,j) contains all the symbols derived for the substring cut by this interval. For example, given a grammar

S → S + M
   | M
M → M * T
   | T
T → number

and an input

6 + 7 * 8

we have

A[2,5) = {M,S}

i.e. the symbols M and S were derived for the substring 7 * 8 at the interval [2,5). It is essentially a table used by CYK parser. “Principles and Implementation of Deductive Parsing” by Shieber, Schabes, Pereira describes how Earley parsing fits into this framework as well.

Given a parsing matrix, one can recover a parse tree (and contrary to what wikipedia CYK page says, one doesn't have to store backpointers), but the takeout message here is that parsing matrix is more fundamental than the parse tree; in particular, it is well defined even for ambiguous derivation.


Many-one reduction from inequality problem to equality problem Let the k-inequality-MIS problem be the decision problem whether an arbitrary graph $G=(V, E)$ contains a maximal independent set of at least size $k$, that is the corresponding language is:

$$\mathbf{M}_{ineq} = \{(G,k): \exists V'\subset V, |V'|\geq k \wedge V'\in MIS(G)\},$$

where $MIS(G)$ collects all possible maximal independent sets of $G$.

Let the k-equality-MIS problem be the decision problem whether $G$ contains such a set exactly of size $k$. Its language being:

$$\mathbf{M}_{eq} = \{(G,k): \exists V'\subset V, |V'|=k \wedge V'\in MIS(G) \}$$

I'm wondering whether $\mathbf{M}_{eq}$ is many-one reducible to $\mathbf{M}_{ineq}$. My intuition tells me it should be but I cannot get it working. As I suspect similar problems pop up quite often, I figured someone here might know.

Note that this is not trivial as the corresponding independent sets problem, $\mathbf{I}$, where $(G,k)\in\mathbf{I}_{ineq}\Leftrightarrow (G,k)\in\mathbf{I}_{eq}$. As an example, for a graph, $G'$, that is a perfect matching with more than two vertices we have $(G',1)\in\mathbf{M}_{ineq}$ but $(G',1)\not\in\mathbf{M}_{eq}$.

And how about the other way around, is $\mathbf{M}_{ineq}$ many-one reducible to $\mathbf{M}_{eq}$?

I'm quite new to complexity theory, so I hope I get this right and the question is not obvious. Also sorry for the rather vague title, but my question is a bit vague. I hope my example made it clear. My question is, however, really about all problems with similar characteristics.

The following should yield a many-one reduction from $M_{ineq}$ to $M_{eq}$:

Given $G=(V,E)$ and $k$ construct $G'$ with

vertex set $V \times \{1,\dots,k\}$ and
edges between $(v,i)$ and $(w,j)$ if

(1) $i=j$ or
(2) $v=w$ or
(3) $(v,w) \in E$.

Because of (1), no independent set can be larger than $k$ (as all vertices in the same slice are connected). Because of (2) and (3) each independent set in $G'$ induces an independent set of $G$ and vice versa, therefore $G$ has an ind. set of size $\ge k$ if and only if $G'$ has an independent set of size exactly $k$.


Precise definition for cryptographic protocol? Is there some precise definition of cryptographic protocol?
I'm asking because I have tried a few good books and they don't seem to define it (Douglas Stinson, Wenbo Mao, Trappe/Washington). The lecture notes by Goldwasser and Bellare come close, but don't really define protocols (and leave key distribution out of the protocols chapter, for example).

I've seen people include key management in protocols and others keeping it out; the same for secret sharing and some other topics.

So, does that mean there no widely-accepted definition for cryptographic protocols?

Edit: I'm not sure I was clear enough when I originally posted the question -- I wanted to know what usually is considered a "protocol" in cryptography and what is not (and not how I'd go about defining some particular protocol)

There are several definitions of cryptographic protocols, each of which tries to capture some particular features of interest.

I start with Goldwasser, Micali, and Rackoff definition (1985): They first defined interactive Turing machines (ITM), based of which they defined (two-party) interactive protocols. An ITM is a special TM equipped with one read-only and one write-only communication tape. A pair of ITMs  constitutes an interactive protocol if the read-only communication tape of party A coincides with the write-only communication tape of party B, and vice versa. The power of parties and the adversary model is then defined accordingly (see the paper).

The multi-party case was later defined by Goldreich, Micali, and Wigderson (1987). They modeled a secure multi-party game in an elegant way, though the paper (as Goldreich states himself) leaves a lot of doors open. For a more concrete discussion see: http://www.wisdom.weizmann.ac.il/~oded/pp.html.

Finally, a much stronger model was proposed by Canetti (2001). In his paper, he defines a framework called Universal Composability (UC), based on which he defines the cryptographic protocols and puts forward a notion of security for them.

As far as I recall, the last paper cites a lot of other works which try to define and model security protocols. Therefore, I strongly advise you to take a look at it.


Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed The MAX-CUT problem has constant factor approximation, but we can't control the sizes of the sets in resulting partition. What is known about maximizing cut size, if we restrict one part of the partition to have size exactly $k$?

Formally, given a graph $G(V, E)$ and integer $k$, find the set $S \subset V$, such that $|S| = k$ and the number of edges between $S$ and $V \setminus S$ is maximized. What is the name of this problem (for example, if $k = |V|/2$, this is known as MAX-BISECTION)? Does it become easier to approximate in polynomial time, if $k$ is $polylog(|V|)$?

There is a 1/2-approximation for Max-Cut with a given size k where k is part of the input. This is in a paper of Ageev and Sviridenko on pipage rounding. See below.
http://www.springerlink.com/content/r37k4302n7m17427/

The above problem is an example of submodular function maximization subject to a matroid base constraint. There has been much recent work on submodular function maximization subject to a variety of constraints.


How to write the introduction of a research paper? Apologies if this is too broad a question for this forum, but I'm interested in specific tactics and tips that researchers (in TCS) use to write the introduction of a research paper.

Simon Peyton Jones has an excellent web page devoted not only to advice on writing introductions, but whole papers, and there is a cool video as well. On page 18 of his slides he says that the purpose of an introduction is to:

Describe the problem.
State your contributions.

He then goes on for a while to explain what precisely that means in pracrtice. But there is much more to his talk, I highly recommend it.
My personal piece of advice: never ever start your paper by saying "In the recent years the foo technology has become important [1, 2, 3, 7, 10, 12, 13, 21] for saving the world peace, taking photos of kittens, and obtaining academic promotions. But all the people who did foo before us missed a minute point, which we are going to talk about at length in this paper. But first, let us bore you with a review of all the foos out there." Just get to the point, please.


Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science? I am a mathematician interested in set theory, ordinal theory, infinite combinatorics and general topology.

Are there any applications for these subjects in computer science?
I have looked a bit, and found a lot of applications (of course) for finite graph theory, finite topology, low dimensional topology, geometric topology etc.

However, I am looking for applications of the infinite objects of these subjects, i.e. infinite trees (Aronszajn trees for example), infinite topology etc.

Any ideas?

Thank you!!

One major application of topology in semantics is the topological approach to computability.

The basic idea of the topology of computability comes from the observation that termination and nontermination are not symmetric. It is possible to observe whether a black-box program terminates (simply wait long enough), but it's not possible to observe whether it doesn't terminate (since you can never be certain you have not waited long enough to see it terminate). This corresponds to equipping the two point set {HALT, LOOP} with the Sierpinski topology, where $\emptyset, \{HALT\}, and \{HALT, LOOP\}$ are the open sets. So then we can basically get pretty far equating "open set" with "computable property". One surprise of this approach to traditional topologists is the central role that non-Hausdorff spaces play. This is because you can basically make the following identifications

$$
\begin{matrix}
\mathbf{Computability} & \mathbf{Topology}\\
\mbox{Type} & \mbox{Space} \\
\mbox{Computable function} & \mbox{Continuous function} \\
\mbox{Decidable set} & \mbox{Clopen set} \\
\mbox{Semi-decidable set} & \mbox{Open set} \\
\mbox{Set with semidecidable complement} & \mbox{Closed set} \\
\mbox{Set with decidable equality} & \mbox{Discrete space} \\
\mbox{Set with semidecidable equality} & \mbox{Hausdorff space} \\
\mbox{Exhaustively searchable set} & \mbox{Compact space} \\
\end{matrix}
$$

Two good surveys of these ideas are MB Smyth's Topology in the Handbook of Logic in Computer Science and Martin Escardo's Synthetic topology of data types and classical spaces.

Topological methods also play an important role in the semantics of concurrency, but I know much less about that.


What is the tradeoff between population size and the number of generations in genetic algorithms Genetic algorithms evolve in fewer generations with a larger population, but also take longer to compute a generation. Are there some guide lines for balancing those two factors, in order to arrive at a viable solution as soon as possible?

Also, is this the best place for the question?

There are some works on this issue. Since you don't specify for what problems you want guidelines I will list some major and some last papers of general interest. They are:

C. Witt (2008) Population Size versus Runtime of a Simple Evolutionary Algorithm // Theoretical Computer Science, 403(1), pp. 104-120.
T. Chen, K. Tang, G. Chen and X. Yao A large population size can be unhelpful in evolutionary algorithms // Theoretical Computer Science. Article in Press
O. Giel, P.K. Lehre (2010) On the effect of populations in evolutionary multi-objective optimisation // Evolutionary Computation 18 (3), pp. 335-356.
P.S. Oliveto, J. He, X. Yao (2008) Analysis of Population-based Evolutionary Algorithms for the Vertex Cover Problem. In Proceedings of the IEEE World Congress on Computational Intelligence.
P.S. Oliveto, J. He, X. Yao (2007) Time Complexity of Evolutionary Algorithms for Combinatorial Optimization: A Decade of Results // International Journal of Automation and Computing. See here 4.1 section for results on population-based EAs.


What is the difference between LTL and CTL? I already read examples of formulas in CTL but not in LTL and vice-versa, but I'm having trouble gaining a mental grasp on LTL formulas and really what, at the heart, is the difference.

To really understand the difference between LTL and CTL you have to study the semantics of both languages. LTL formulae denote properties that will be interpreted on each execution of a program. For each possible execution (a run), which can be see as a sequence of events or states on a line — and this is why it is named "linear time" — satisfiability is checked on the run with no possibility of switching to another run during the checking. On the other hand, CTL semantics checks a formula on all possible runs and will try either all possible runs (A operator) or only one run (E operator) when facing a branch.

In practice this means that some formulae of each language cannot be stated in the other language. For example, the reset property (an important reachability property for circuit design) states that there is always a possibility that a state can be reached during a run, even if it is never actually reached (AG EF reset). LTL can only state that the reset state is actually reached and not that it can be reached.

On the other hand, the LTL formula $\Diamond\Box s$ cannot be translated into CTL. This formula denotes the property of stability : in each execution of the program, s will finally be true until the end of the program (or forever if the program never stops). CTL can only provide a formula that is too strict (AF AG s) or too permissive (AF EG s). The second one is clearly wrong. It is not so straightforward for the first. But AF AG s is erroneous. Consider a system that loops on A1, can go from A1 to B and then will go to A2 on the next move. Then the system will stay in A2 state forever. Then "the system will finally stay in a A state" is a property of the type $\Diamond\Box s$. It is obvious that this property holds on the system. However, AF AG s cannot capture this property since the opposite is true : there is a run in which the system will always be in the state from which a run finally goes in a non A state.

I don't know if this answers to your question, but I would like to add some comments.

There is a lot of discussion of the best logic to express properties for software verification... but the real debate is somewhere else. LTL can express important properties for software system modelling (fairness) when the CTL must have a new semantics (a new satisfiability relation) to express them. But CTL algorithms are usually more efficient and can use BDD-based algorithms. So... there is no best solution. Only two different approaches, so far.

One of the commenters suggests Vardi's paper "Branching versus Linear Time: Final Showdown".


Oncina-Garcia RPNI algorithm for learning DFAs The question refers to this paper:
ftp://altea.dlsi.ua.es/people/oncina/articulos/asspr1992.pdf

Given a sample of $p$ positive and $n$ negative strings, RPNI constructs a consistent DFA in time $O((p+n)p^2)$. Nothing is claimed about the size of this DFA; if its size were $o((p+n)/\log(p+n)))$, that would imply a compression-based generalization bound. Of course, if they were able to always compress to size poly(opt) -- where opt is the size of the minimal consistent DFA --- that would imply P=NP, via a result of Pitt and Warmuth.

Questions: (1) Is anything at all known about the size of RNPI's resulting DFA? (2) In the linked paper, they claim that RNPI "can identify any regular language in the limit". Has that claim been rigorously proved anywhere? I couldn't find such a proof in the paper.

The algorithm is named RPNI, not RNPI.

Given that the language generating the inputs is regular and that enough examples are given (the characteristic set), the algorithm returns the canonical (i.e., minimal) DFA for that language. If the generating language is not regular, the automaton may grow unboundedly with the set of inputs.

Since the algorithm merges states, the output automaton has at most |p| states. Therefore, the output is bounded by the sum of input lengths in p.

A proof appears in "Inferring regular languages in polynomial update time".
There are more details about the algorithm in the "Grammatical Inference" book by Colin de La Higuera.


Is MAX CUT approximation resistant? CSP optimization problem is approximation resistant if it is $NP$-hard to beat the approximation factor of a random assignment. For instance, MAX 3-LIN is approximation resistant since  a random assignment satisfies $1/2$ fraction of  the linear equations but achieving approximation factor $1/2+ \epsilon$ is $NP$-hard.

MAX CUT is a fundamental $NP$-complete. It can be formulated as CSP problem of solving linear equations modulo 2 ($x_i + x_j= 1$ mod 2). A random assignment achieves  $1/2$-approximation factor (of the total number of edges $|E|$). Haglin and Venkatesan proved that achieving an approximation factor $1/2+ \epsilon$ is $NP$-hard (i.e. finding a cut better than $|E|/2$). However, Hastad showed that MAX CUT is not approximable to $16/17+ \epsilon$ factor within the optimal cut unless $P=NP$. Goemans and Williamson gave a SDP-based polynomial time algorithm with 0.878 approximation factor (within the optimal cut) which is optimal assuming the Unique Games Conjecture. It seems to me that expressing the approximation factor relative to total number of constraints ($|E|$) is more natural and consistent with the convention used for MAX 3-LIN problem.

  Why is the approximation factor for MAX CUT given relative to the size of optimal cut instead of the number of constraints (# of edges)? Am I right in concluding that MAX CUT is approximation resistant when the approximation factor is relative to the total number of constraints ($|E|$)?

If you measure approximation as a ratio between the number of constraints satisfied by your algorithm divided by the total number of constraints, then trivially all constraint satisfaction problems are unconditionally approximation-resistant.

By definition, a problem is approximation resistant if the (worst-case) approximation ratio of a random solution is (up to an additive $o(1)$ term) best possible among the (worst-case) approximation ratios achieved by all polynomial time algorithms.

With your definition of approximation ratio, you get approximation resistance of Max Cut (and all constraint satisfaction problems)  just because you can always construct instances for which the ratio given (on average) by a random assignment is more or less (up to a $o(1)$ term) the same as the ratio given by an optimal assignment.

For example, in the Max Cut problem, a clique on $n$ vertices is a graph that has ${n \choose 2} = n\cdot (n-1)/2$ edges, and in which an optimal cut cuts $n^2/4$ edges. This means that every algorithm, and in particular every polynomial time algorithm, has a worst-case approximation ratio (according to your definition) that is at most $1/2 + O(1/n)$ on $n$-vertex graphs. The random assignment has ratio $1/2$ on all instances, and so no algorithm can do better than the random algorithm, and the problem is approximation-resistant.


Directed NP-hard problems on DAGs Tree width measures how close a graph is to a tree. Several NP-hard problems are tractable on graphs with bounded tree width. If a problem remains NP-hard on trees then tree width cannot save us. This was the motivation behind one of my previous questions asking for NP-hard problems on trees.

There are several directed versions of tree width measuring how close a directed graph is to a directed acyclic graph (DAG). What are some directed problems that remain NP-hard on DAGs ? A directed problem makes essential use of the directions of the edges. For example, hamiltonian path is a directed problem whereas vertex cover is not. One of the answers to my previous question gave a general recipe for generating problems that are hard on trees. Is there such a recipe for DAGs ?

This only aims at partially answering the first question of the post:

  What are some directed problems that remain NP-hard on DAGs ?

In [1], a few natural problems on directed graphs are given that remain NP-hard on DAGs. The motivation of the paper is to find a "good" treewidth-like measure for digraphs. They argue that the drawback of many measures for digraphs is that they are constant for DAGs, but many directed counterparts of natural problems remain NP-hard on DAGs. For more on this topic, see also [2] and the references of these papers.

[1] Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith: On Digraph Width Measures in Parameterized Algorithmics. IWPEC 2009:185-197. Full version

[2] Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar: Are there any good digraph width measures?. IPEC 2010, to appear. arXiv


What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates? It is known $AC^0[2]$ cannot get majority function.
Is there a literature on simulation of $MAJ$ function utilizing $AC^0[2,3,\dots,p]$ gates for a finite fixed set of primes $2$ to $p=O(1)$?
What is the best we found?

Although not exactly what you're looking for, this paper seems to be the most current (2019) efforts towards tight $AC^0[2]$ bounds as of yet, and provides a good summary of the difference between $AC^0$ and $AC^0[2]$ bounds.


The Cost of an Equivalence Query for DFA Inspired by this question, I am curious about the following:

  What is the worst-case complexity of checking whether a given DFA accepts the same
  language as a given regular expression?

Is this known?  The hope would be that this problem is in P -- that there is an algorithm polynomial in the size of both.

According to Garey and Johnson (p. 174), REGULAR EXPRESSION NON-UNIVERSALITY is PSPACE-complete. This is the problem of deciding whether a regular expression over $\{0,1\}$ does not generate all strings. So your problem is also PSPACE-complete.

Here is one way to see that the OP's problem is in PSPACE. Given a DFA $A$ and a regular expression $r$, construct an NFA $B$ for $r$, and use the power set construction to virtually construct a DFA $C$ equivalent to $B$; we will not keep $C$ in memory, but we have oracle access to $C$ using only polynomial space. Now virtually construct a DFA $D$ for the symmetric difference of $A$ and $C$ using the product construction. This DFA accepts no strings (and so $L(A) = L(r)$) if there is no path from the starting state to an accepting state. Since reachability is in NL and $D$ has size $2^{\mathrm{poly}(n)}$, we can check whether $L(D) = \emptyset$ in $\mathrm{NSPACE}(\mathrm{poly}(n)) = \mathrm{NPSPACE} = \mathrm{PSPACE}$, the latter equality due to Savitch's theorem.


Computational complexity and reductions to linear programming My question is rather general, but I have not been able to find a satisfactory answer for quite a long time, and I wonder if there has been a research concerning these issues.

I have come over a relatively large number of optimization problems, that can be expressed as a Linear Programming problem, or as an Integer Linear Programming problem. Also decision problems could be expressed as LP or ILP, with a constant objective function (i.e., concerning only (in)feasibility). If a problem can be expressed as LP, then it is certainly in $\mathbf{P}$, since Linear Programming problems can be solved in polynomial time. On the other hand, problems that cannot be expressed as LP, but only as ILP, usually are $\mathbf{NP}$-complete, despite the fact that this is not a valid proof of $\mathbf{NP}$-completeness (there could be a polynomial algorithm not based on LP solving the problem).

So my question is: is there any known relation between the complexity of a problem and it's expressibility in the form of (integer) Linear Programming (except the obvious facts stated in the previous paragraph)? Moreover, I believe that there are inherently nonlinear problems that cannot be expressed in the form of LP nor ILP. Is there some known relation between their complexity and their expressibility in the form of some type of Nonlinear Programming problems? Are there any references dealing with similar problems?

Thank you in advance.

ILP is NP-complete.  This has a few implications to your question.

  Moreover, I believe that there are inherently nonlinear problems that cannot be expressed in the form of LP nor ILP.

As long as you consider problems in NP, no, all problems in NP can be rewritten as ILP in polynomial time.  If you consider problems not in NP, then they cannot be expressed in the form of LP or ILP because both LP and ILP are in NP.

  is there any known relation between the complexity of a problem and it's expressibility in the form of (integer) Linear Programming (except the obvious facts stated in the previous paragraph)?

This is essentially asking which special cases of ILP can be solved in polynomial time.  One of the fairly large classes of ILP which can be solved in polynomial time is ILP with totally unimodular constraint matrices; see Wikipedia.  But if you want a very general result, it is unlikely that you get anything more than tautological statements such as “the optimization problem is in P if there is a polynomial-time algorithm to solve it.”  Indeed, your question is formally equivalent to asking which problems in NP are in P, and obviously we do not know any necessary and sufficient characterization which is easy to check.


Shoup-style hashing without one-wayness Let $H$ be an almost universal hash family of functions from $D^2$ to $D$. For any functions $f,g \in H$ define the function $\langle f,g \rangle : D^4 \to D$ by $\langle f,g \rangle(a,b,c,d) \triangleq f(a,g(b,f(c,d)))$.

  Is the family $H' \triangleq \{\langle f,g \rangle : f,g \in H\}$ almost universal?
  If not, what conditions on $H$ would make $H'$ almost universal?

Note that if we instead defined $\langle f,g \rangle(a,b,c,d) \triangleq g(f(a,b),f(c,d))$, $H'$ would be almost universal. This was defined in Wegman and Carter's "New hash functions and their use in authentication and set equality", and it is sometimes called "tree hash".

The scheme in which $\langle f,g \rangle(a,b,c,d) \triangleq f(a,g(b,f(c,d)))$ is a variation on one in Shoup's "A composition theorem for universal one-way hash functions". Shoup proves that $H'$ is a family of Universal One-Way Hash Functions if $H$ is a family of Universal One-Way Hash Functions. However, I do not believe the proof works to show that $H'$ is almost universal if $H$ also is.

One advantage of Shoup's scheme over Carter and Wegman's is that Shoup's functions can be evaluated with room for only one temporary value from $D$.

Here is a partial answer:

Sometimes $H'$ is almost universal, but not always.

For an example of an $H$ that makes $H'$ almost universal, let $D$ be a field and consider $H_R = \{ h_x(a,b) = a + bx : x \in D\}$. $H_R$ is universal: Consider $(a,b) \neq (c,d)$. If $b \neq d$, then $(\Pr_x h_x(a,b) = h_x(c,d)) = (\Pr_x a + bx = c + dx) = (\Pr_x (b-d)x = c-a) = (\Pr_x x = (c-a)/(b-d)) = |D|^{-1}$. Otherwise, $b=d$, and thus $a \neq c$, and by a similar calculation $h_x(a,b) \neq h_x(c,d)$.

In this case, $\langle f,g \rangle(a,b,c,d)$ is a polynomial of degree $3$, with four terms with different coefficients. If $(a',b',c',d') \neq (a,b,c,d)$, $\langle f,g \rangle(a,b,c,d) - \langle f,g \rangle(a',b',c',d')$ is a polynomial of degree at most $3$ with at least one non-zero coefficient. By Schwartz-Zippel, $H'$ is almost universal.

If $H = \{h_x(a,b) = ax + b : x \in D\}$, then $\langle h_x, h_y \rangle(a,b,c,d) = ax + by + cx + d$, and $(c,b,a,d) \neq (a,b,c,d)$ is guaranteed to have the same hash value. Thus, $H'$ is not almost universal.


Is the D-Wave architecture a close implementation of quantum interactive proof? A very high level architecture is, as mentioned here, shown in this picture.

The component on the left is classical while the one on the right is the D-Wave box. I understand that in QIP, Arthur is BQP. Here the classical component is always in BQP if we are not too restrictive. On the other hand, the D-Wave box although don't have unbounded computational resources is not violating any law of quantum mechanics. Let's consider this as not-so-strong Merlin.

Can we say that this architecture is an restricted implementation of quantum interactive proof system? My motivation for this question is that if we want to do the complexity analysis of the D-Wave architecture should we model it as QIP?

This question seems a little confused. The class of decision problems solvable efficiently on a quantum computer is BQP, while on a classical computer it is either P or BPP depending on exactly how you define things. An interactive proof is something entirely different. It is a protocol which allows a prover to prove, beyond reasonable doubt, the outcome of some decision problem, and allows the prover and verifier to interact. QIP is the class of interactive proofs where the verifier, not the prover, has access to a quantum computer. It turns out that this doesn't help very much since you can prove exactly the same things to a fully classical verifier. I think what you have in mind is something different: an interactive proof where the prover is limited to quantum computation. This is something that has been studied in recent years (see for example arXiv:0807.4154, arXiv:0810.5375 and arXiv:1209.0449). The extent of our current knowledge is that you can basically prove anything in BQP if you have either some limited quantum power for the verifier (the ability to prepare single qubit states, for example) or if you have several provers who do not communicate, but share entanglement.

The DWave machine does not implement anything like these schemes, and does not constitute any form of interactive proof. Actually, the problem of implementing such a scheme on DWave hardware has been something that has interested me for a while. There are a few hurdles to doing this. All of the known schemes are based in the circuit model or the closely related measurement based model, while the DWave machines use a very different model of computation. This introduces a few problems, as their system is not a general purpose quantum computer, and so cannot implement any of the known schemes directly. Further, it cannot really accept any kind of quantum input, which rules out many of the tricks used to construct the known schemes.

However, I don't mean this to be a criticism of DWaves device: virtually no other quantum device has been used to implement such a proof. The closest you get are things like violations of Bell's inequalities and the recent experimental demonstration of blind quantum computing in linear optic (arXiv:1110.1381). At this point, no one has yet published an experimental demonstration of a quantum prover interactive proof, so DWave isn't any better or worse in this respect than anyone else.

By the way, I apologise for linking to two of my own papers in the above, but this is a question I have been very interested in in recent years, and I think those papers are relevant to the question at hand. It's not intended as self-publicity.


Is Kolmogorov complexity quasi-surjective? For Kolmogorov complexities $\hspace{.02 in}K$ induced by essentially-optimal description languages,

does there exist an integer $c$ such that for all positive integers $n$,

there exists a string $x$ such that $\;\;\; n \: < \: K(x) \: < \: n\hspace{-0.04 in}+\hspace{-0.03 in}c \;\;\;\;$?

Unlike the question I was inspired by, this question's answer is robust against the choice of $\hspace{.02 in}K\hspace{-0.02 in}$, since by definition $L_{\hspace{.03 in}0}$ is an "essentially-optimal description language" if and only if

it is a computable partial function from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^{\hspace{-0.03 in}*}$ to itself such that for all

computable partial functions $L_{\hspace{.02 in}1}$ from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^{\hspace{-0.03 in}*}$ to itself, there exists an

integer $c$ and a computable (total) function $\: f : \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^{\hspace{-0.03 in}*} \to \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^{\hspace{-0.03 in}*} \:$ such that

for all strings $x$, $\;\;\; \operatorname{length}(\hspace{.05 in}f(x)) \: < \: \operatorname{length}(x)+c \;\;\;$ and $\; L_{\hspace{.03 in}0}\hspace{-0.02 in}(\hspace{.05 in}f(x)) = L_{\hspace{.02 in}1}\hspace{-0.02 in}(x) \:\:$.

Suppose $L_0$ is an essentially-optimal description language, and consider the identity function, which is a computable partial function from $\{0,1\}^*$ to itself. According to the definition, there is a computable function $f$ and a constant $C$ such that $|f(x)| \leq |x| + C$ and $L_0(f(x)) = x$.

Take now a Kolmogorov random string $x$ of length $n$. On the one hand, $K(x) \geq n$. On the other hand, we have seen above that $K(x) \leq n + C$.


Minimum Parity Weight Path - what is the complexity? Consider an undirected graph, with non-negative  weights on the edges, and two distinguished  nodes $s\neq t$. If $P$ is a simple $s-t$ path in this graph, let $W_1(P)$ denote the sum of the weights on the path, but only adding up every other one, as we traverse the path from $s$ to $t$, starting the summation with the first edge. That is, we add up the first, third, fifth etc. weights on the path. Let us call it the parity weight of the path.

What is the complexity of finding the minimum parity weight $s-t$ path?

The problem can be solved in $O(n(m + n \log n))$ time. The solution below is based on one by Grötschel and Pulleyblank to compute shortest paths with an even (odd) number of edges (Gröschel and Pulleyblank in turn contribute it to 'Waterloo-folklore'. Schrijver contributes their solution to J. Edmonds.) We'll solve the stronger problem of finding a minimum parity weight $s - t$ path with an odd (even) number of edges. The cheaper of the odd and even solutions is the minimum parity weight $s - t$ path.

Let $G=(V,E)$ be your input graph. Create a new graph $G'$. Graph $G'$ contains two copies of $G$ denoted $G_1$ and $G_2$. Every edge $e \in E$ retains its weight in $G_1$ but is given weight $0$ in $G_2$.
Finally, for every vertex $v \in V$, $G'$ contains an edge of weight $0$ between $v$'s copies in $G_1$ and $G_2$. Let $v_i$ be the copy of $v$ in graph $G_i$. Find a minimum weight perfect matching $M$ in $G' - s_2 - t_2$ in $O(n(m + n \log n))$  time (Gabow [1990]). Let $P = (V,E')$ contain exactly the edges of $M$ that were copied from $G$ (possibly with multiplicity). One connected component of $P$ is a minimum parity weight $s - t$ path with an odd number of edges, and its parity weight is equal to $M$'s total weight.

To prove the claim, let $P$ a minimum parity weight $s - t$ path in $G$ with an odd number of edges. Let $M$ be the perfect matching of $G' - s_2 - t_2$ containing $G_1$'s copies of the first, third, etc. edges of $P$, $G_2$'s copies of the second, forth, etc. edges of $P$ and the $0$ weight edges between $v_1$ and $v_2$ for every vertex $v$ not in $P$. Matching $M$ has the same weight as $P$'s parity weight, so some perfect matching of $G'$ contains $P$ and has the appropriate weight.

Conversely, let $M$ be a perfect matching in $G' - s_2 - t_2$, and let $P = (V,E')$ contain exactly the edges of $M$ that were copied from $G$ (possibly with multiplicity). For every vertex $v \notin \{s,t\}$, either $v$ is incident to two edges copied from $G$ in $M$, or both copies of $v$ were matched along a $0$ weight edge not present in $G$. Vertices $s$ and $t$ have one matched copy in $M$. Therefore, every vertex of $P$ has degree $2$ or $0$ except for $s$ and $t$ which have degree $1$. Therefore, $s$ and $t$ lie in the same connected component of $P$, and that component is a path. Further, when tracing the edges of that path from $s$ to $t$ you find they come from $G_1$, then $G_2$, then $G_1$, etc. ending with $G_1$. There are an odd number of edges, and the parity weight of that path is the weight of those edges in $G'$. Every other component of $P$ must have non-negative weight, so $M$ is a perfect matching in $G' - s_2 - t_2$ with weight no less than $P$.

Finding a minimum parity weight $s - t$ path with an even number of edges is solved in exactly the same way, except you find a minimum weight perfect matching in $G' - s_2 - t_1$.


Theoretical proof of convergence of sequential weight update procedure (Neural Networks and Machine Learning) My question is at the bottom.
(Most of the descriptive words come from Chris. Bishop's Neural Networks for Pattern Recognition)

let $w$ be the weight vector of the neural network and $E$ the error function.

According to the Robbins-Monro algorithm, this $$w_{kj}^{(r+1)}=w_{kj}^{(r)}-\eta\left.\frac{\partial E}{\partial w_{kj}}\right|_{w^{(r)}}$$ will converge to where $$\frac{\partial E}{\partial w_{kj}}=0$$

In general the error function is given by a sum of terms each of which is calculated using one of the patterns from the training set, so that $$E=\sum_nE^n(w)$$
And in applications we just update the weight vector using one pattern at a time $$w_{kj}^{(r+1)}=w_{kj}^{(r)}-\eta\frac{\partial E^n}{\partial w_{kj}}$$

My question is: Why the algorithm will converge using the last formula? Once we use it to update the $w$, the value of $w$ is changed, I can't prove the convergence using $$\frac{\partial E}{\partial w_{kj}}=\sum_n \frac{\partial E^n}{\partial w_{kj}}$$

As pointed out by Rong, for gradient descent to converge the learning rate $\eta$ has to be chosen appropriately. It has to be large enough that every update determines a big enough change in the weights, but it has to be small enough not to overshoot the local minimum of the cost function. You may want to take a look at this paper that analyzes some sufficient conditions for gradient descent to work

Armijo, Larry (1966). "Minimization of functions having Lipschitz continuous first partial derivatives". Pacific J. Math. 16 (1): 1–3.


Independent Node Degree in Undirected Graphs Let $G=(V,E)$ be an undirected graph. The independent node degree $d^i(v)$ of a node $v$ is the maximum size of a set of independent neighbors of $v$. Denote by $\Delta^i(G) = \max \{d^i(v) \mid v \in V\}$. Obviously $\Delta^i(G) \le \alpha(G)$, where $\alpha(G)$ is the independence number of $G$.

Examples: $\Delta^i(G)=1$ for complete graphs. $\Delta^i(G)\le 5$ for unit disc graphs. $\Delta^i(G)=n-1$ for a star graph with $n$ nodes.

My questions:

What natural graph classes have $\Delta^i(G)\in O(1)$?
What is known about the distribution of $d^i(v)$ in random graphs?
For dense graphs the expected value of the independent node degree should be small. Are there any quantitative results? E.g. relating $m/n$ with $\Delta^i(G)$?

Concerning the third question, triangle-free graphs have $\Delta^i(G) = \Delta(G)$. From Turán's theorem, we know that the maximum number of edges on a triangle-free graph is $\big\lfloor\frac{n}{4}\big\rfloor$, and this bound is tight for the complete bipartite graph $K_{n/2,n/2}$. Hence, at least in this case, you can have a dense graph with a large independent node degree, namely $d^i(v) = \frac{n}{2}$ for all $v$.


Would it be possible for a compiler to convert a recursive sum into the average formula? def sum1(n):
    if n==0: return 0
    else: return n + sum1(n-1)

def sum2(n):
    return n*(n+1)/2

A compiler can not convert sum1 into sum2 because function equality in turing-complete languages is undecidable. My question is: is there a system strong enough to express both functions, that is also weak enough to a compiler can make the conversion? Or, even better, is there a simple system where the mere reduction of sum1 would fall into sum2?

I assume you are asking whether a "reasonable" system exists that can express these functions and also also decide whether any two expressible function definitions define the same function. (An unreasonable system would be, for example, the language which has only the two function definitions above in it...)

Both of functions are expressible in Buss's bounded arithmetic, so yes, to your first question, though I'm not aware that anyone has actually converted these systems into practical computer languages. For one thing, the algorithm should exist, but are (almost?) certainly unfeasible unless P==NP. (Almost: I'd guess that the problem of function equivalence in any of Buss's systems is at least NP hard, but I have no proof.)

For your second question, I guess we would have to define "reasonable" meant more carefully. It seems plausible to me that one could create a "combinatorics expert system" that could recognize and "automatically optimize" many such simple functions -- perhaps it would look something like "Mathematica" :) -- but I assume that isn't what you are talking about.


How many sets of vectors can be represented as the solutions of a Horn-SAT instance? Let the solution space of a SAT instance be the set of Boolean vectors of satisfying assignments of $\{0,1\}$ to the variables (that result in the formula evaluating to TRUE).
In other words, a solution space represents all the solutions of an instance.
There are at most $2^n$ solutions, so $n$-variable SAT (denoted here by SAT$_n$) can represent at most $2^{2^n}$ different solution spaces.
Moreover, it is easy to see that this number can actually be reached, by considering instances where every clause contains all $n$ variables.

We know that Horn-SAT is less expressive than SAT, for instance there is no Horn-SAT$_2$ representation of the solution space of $a \lor b$, which contains the 3 vectors $01, 10, 11$.
Hence Horn-SAT$_n$ must be able to represent fewer than $2^{2^n}$ solution spaces.

  What is the number of solution spaces of a Horn-SAT$_n$ instance?

For completeness, recall that a literal is either a variable or its negation,
and that $n$-variable SAT consists of formulas built from at most $n$ variables (we can fix the set of variable names, e.g. $\{1,2,\dots,n\}$), in conjunctive normal form (a conjunction of disjunctions), where each disjunction of literals is known as a clause.
Horn-SAT$_n$ is the fragment of $n$-variable SAT where each clause in an input formula contains at most one non-negated variable.

An equivalent counting formulation of the question is: how many different values can #Horn-SAT$_n$ have?
However, note that I am not interested here in the complexity of #Horn-SAT, just its range of values for each number of variables.

If one tries to work syntactically, then one faces the same challenge as for SAT.
Suppose one tries to count the number of different SAT instances syntactically.
There are $2^{3^n}$ different ways to write down a SAT instance with $n$ variables and no repeated clauses (if the variable order is fixed and no variable may appear more than once in a clause), so one has to find the equivalence classes of syntactically different instances that lead to the same solution space, to retrieve the $2^{2^n}$ number.
One then needs to similarly take the quotient of the set of different Horn-SAT instances with $n$ variables to obtain the correct value of the number of different solution spaces.
It is not clear to me how to take quotients for SAT, let alone how to do so for Horn-SAT.

$\def\pw{\mathcal P}$
It is an easy exercise to show that if we identify Boolean assignments to $n$ variables with subsets of $[n]=\{0,\dots,n-1\}$, then the solution sets of Horn CNFs are exactly the families $S\subseteq\pw([n])$ that are closed under nonempty intersections.

The picture is a little nicer for conjunctions of clauses each of which contains exactly one positive literal. Their solution sets are families closed under arbitrary intersections (where in particular the empty intersection is the full set), also known as closure systems or Moore families. These are in 1–1 correspondence with closure operators (functions $C\colon\pw([n])\to\pw([n])$ satisfying $X\subseteq C(Y)\iff C(X)\subseteq C(Y)$), consequence relations (relations ${\vdash}\subseteq\pw([n])\times[n]$ satisfying a handful of natural conditions), and I guess there are more similar combinatorial characterizations (https://oeis.org/A102896 or https://oeis.org/A102897 mention semilattices).

These two numbers only differ by a factor of two (given a closure system $S$, we may either retain $[n]\in S$ or throw it out without affecting anything else).

Alekseev proved that the number $\alpha(n)$ of closure systems on an $n$-element set satisfies

$$2^{\binom{n}{\lfloor n/2\rfloor}}\le\alpha(n)\le2^{\binom{n}{\lfloor n/2\rfloor}(1+o(1))}.$$

See http://www.renyi.hu/~ohkatona/paper_72.pdf for related information.


Problems in NC not known to lie in NC2 Are there interesting problems that are in $\mathsf{NC}$ but not known to be in $\mathsf{NC^{2}}$? In the paper 'A Taxonomy of Problems With Fast Parallel Algorithms', Cook mentions that MIS was known to only be in $\mathsf{NC^{5}}$ but this has since been brought down to $\mathsf{NC^{2}}$. I am wondering if there are any other problems with polylog-depth parallel algorithms where we seem to be stuck on improving the depth.

To narrow down even further, are there any problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$?

Disclaimer: I'm not an expert in fast parallel algorithms, hence the probability that I missed more recent results that put the problems I mention in lower levels of the $\mathsf{NC}$ hierarchy is non-negligible. If you observe that it is the case, please tell me and I'll update my answer.

The report Parallel Algorithms for Depth-First Search discusses known parallel algorithms for DFS on various types of graphs. The list given on pages 9-10 indicates several algorithms in $\mathsf{NC} \setminus \mathsf{NC}_2$, such as DFS for planar undirected graphs, or in $\mathsf{RNC} \setminus \mathsf{RNC}_2$, such as DFS for general undirected graphs.
With a quick search, I could not find papers improving over the parallel algorithms for sparse multivariate polynomial interpolation over finite fields of this paper, which is in $\mathsf{NC}_3$. However, several papers that could possibly have been relevant were behind a paywall.
Computing all maximal cliques in a graph is in $\mathsf{NC} \setminus \mathsf{NC}_2$ when the number of maximal clique is polynomially bounded, according to this paper.
The maximal path problem seems to be in $\mathsf{NC}_5$ for general (undirected) graphs, I've not found a faster parallel algorithms without restrictions on the underlying graph.

Other potential candidates might include algorithms for finding perfect matchings in specific types of graphs, or algorithms for finding a maximal tree cover in arbitrary graphs (e.g. this paper mentions a randomized polytime algorithms in parallel time $O(\log^6n)$). This paper also mention solving classes of CSPs problems that arise in computer vision application, in parallel time $O(\log^3n)$.


Number of Vertex Covers: when it is polynomial and when it is superpolynomial The number $C$ of vertex covers of a graph $G = (V, E)$ can be either polynomial in $|V|$ or superpolynomial in $|V|$. $C$ being superpolynomial in $|V|$ doesn't necessarily mean that $C$ is hard to determine. For instance, consider the graph $G = (V, E)$ where $|V| = 2n$ and $E$ is defined as $E = \{ \{ i,j \} | i \mod 2 = 1 \land j = i + 1 \}$: such graph has a number of vertex covers $C=3^{|E|} = 3^{\frac{|V|}{2}}$ which is both superpolynomial in $|V|$ and very easy to determine. On the other hand, knowing in advance that $C$ is polynomial in $|V|$ allows us to use brute force keeping the running time polynomial in $|V|$. So it seems that determing $C$ is hard only if it is superpolynomial in $|V|$, but not always (as the above example demonstrates).

  Questions

  Is it possible to determine in advance if $C$ is polynomial in $|V|$ or superpolynomial in $|V|$? Is there any known result linking some parameter of the graph with the number of its vertex covers? An example of such result would be: "Every graph with $\frac{|E|}{|V|} \geq 4$ has not more than $n^{\frac{|E|}{|V|}}$ vertex covers". Another example would be: "Every graph with $\frac{|E|}{|V|} < 2$ has not less than $1.18^{\sqrt{|E|}}$ vertex covers". How $C$ varies with $G$? Clearly, the more edges $G$ has, the less vertex covers it has: did anyone formalized this trivial fact, showing precisely how $C$ decreases as $|E|$ increases? Which other parameters affect $C$, and how? I mean, from a pure empirical point of view, it's almost evident that a graph with $\frac{|E|}{|V|} \geq 5$ has not so many vertex covers, where "not so many" means "certainly polynomial in $|V|$".
  When $C$ is superpolynomial in $|V|$ brute force is useless. However, I wonder if, as in the above example, it is always true that $C$ being superpolynomial intrinsically implies the presence of "multiplying blocks" (I don't know how to state this more formally), which in turns would mean that the set of all vertex covers is easy to represent (in other words, it is compactly representable). Is there any known result in this spirit?

There's a close relation between the independence number of a graph and the number of its vertex covers, not close enough to completely answer your question but close: if the independence number is superlogarithmic then the number of covers is superpolynomial, and otherwise it's quasipolynomial.

More specifically if the independence number is $\alpha$, and the maximum independent set $I$ is the complement of a vertex cover $C$, then each of the $2^\alpha$ supersets of $C$ is also a vertex cover. So in this case if $\alpha \ge c\,\log_2 n$ then the number of covers is lower bounded by $n^c$. But each cover is complementary to an independent set and there can be only $O(n^\alpha)$ sets of at most $\alpha$ vertices, so if $\alpha \le c\,\log_2 n$ then this upper bound is $O(2^{c\, \log^2 n})$.


Variants of direct product theorems A direct product theorem, informally, says that computing $k$ instances of a function $f$ is harder than computing $f$ once.

Typical direct product theorems (e.g., Yao's XOR Lemma) look at average-case complexity, and argue (very roughly) that is $f$ cannot be computed by circuits of size $s$ with probability better than $p$, then $k$ copies of $f$ cannot be computed by circuits of size $s' < s$ with probability better than $p^k$.

I am looking for different types of direct product theorems (if they are known). Specifically:

(1) Say we fix the probability of error $p$ and are instead interested in te size of the circuit needed to compute $k$ copies of $f$? Is there a result that says that if $f$ cannot be computed by circuits of size $s$ with probability better than $p$, then $k$ copies of $f$ cannot be computed with probability better than $p$ using a circuit of size less than $O(k \cdot s)$?

(2) What is known with respect to worst-case complexity? E.g., if $f$ cannot be computed (with 0 error) by circuits of size $s$, what can we say about the complexity of computing $k$ copies of $f$ (with 0 error)?

Any references would be appreciated.

(1): This question was studied in the paper "Towards proving strong direct product theorems" by Ronen Shaltiel, and it turns out that such a conjecture is false: For example, it could be that $f$ can be computed with probability $0.99 * p$ with size much smaller than $s$, and only the additional $0.01 * p$ probability mass requires size $s$. In such case, when computing $f$ on $k$ instances, the circuit could solve $f$ on most of the instances with size much smaller than $s$, and will need size $s$ only on few of the instances.

(2): A direct product theorem for worst-case complexity is known for formulas and for monotone circuits, but is actually known to be false for general circuits. For an easy example, consider a function $f : \{0,1\}^n \to \{0,1\}^n$ that views its input as a vector and multiplies it by some fixed $n \times n$ boolean matrix. Then, computing the function $f$  may require size $n^2$, but computing it on $n$ instances can be done much faster than $n^3$ using a matrix multiplication algorithm.
You can find a thorough discussion of this subject in the book "The complexity of Boolean Functions" by Ingo Wegener - see Chapter 10.2 here: http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/.


Random sampling data structure with removal I'd like a data structure with the following operations:

create a new instances from an array of floating point weights.
randomly sample, returning an item with probability proportionate to its weight.
set the weight of a specific item to 0.

Without the third option this is pretty standard: Just implement an alias method sampler using Vose's algorithm, but the ability to do a dynamic update makes it harder.

The first operation is intrinsically O(n) (or at least it is if you don't make the second operation O(n)), but it would be nice to be able to do the other two in amortized O(1), or at least O(log(n)). Sampling will be significantly the more common operation, so ideally I would like to have it not be much slower (either in complexity or constant factors) than using the alias method.

One option is to just rebuild the sampler every time you do a remove, but that's O(n) which is less than ideal.

The following is currently my best bet, which builds on that to amortise it a bit:

We keep a copy of the set of weights, and build an alias method sampler initially. When we set the weight of an item to zero we update our weights table appropriately. Then when we sample from our alias table, we check the weight. If it's zero then we rebuild the alias table with the updated weights and draw again.

This should work OK for amortising some of the cost, but unfortunately the workload I'm likely to want to put it through is probably pessimal for it: Items that are going to be removed will have been drawn from the sampler, so will tend to be of high weight. This means that it will end up hitting the rebuild case fairly commonly.

So I'm hoping for something better. Any suggestions?

Copying my comment on that from here:

There exist published algorithms that support sampling from discrete probability distributions in O(1) time, AND modifying the distribution in O(1) time per update:

Hagerup, T., K. Mehlhorn, and J. I. Munro. "Optimal algorithms for
generating discrete random variables with changing distributions."
Lecture Notes in Computer Science 700 (1993):
253-264.
Matias, Yossi, Jeffrey Scott Vitter, and Wen-Chun Ni. "Dynamic
generation of discrete random variates." Theory of Computing Systems
36.4 (2003): 329-358.

These papers are a little unsatisfactory in that they are theoretical algorithms in a model that doesn't fully deal with issues of numerical precision and bit complexity. This can be an issue in practice if the probability distribution has some entries that are much larger than others. Consequently, in the application I had, I used some of the ideas from these papers, but implemented something else that was more practical.

EDIT: What I implemented was a bucketing system. Assume without loss of generality that each weight (non-normalized probability) is a power of 2.(Normalize so each weight is a 64-bit integer. Round each weight up to its nearest power of 2, then sample from the rounded weights instead.  When you sample a value $i$ that has been rounded up to $2^k$, only actually take it with probability $i/2^k$, and otherwise resample. You get at most 1 repeat in expectation.)  Keep all rounded weights with the same value $2^k$ in a single bucket indexed by $k$.  As you do updates, keep track of the currently largest rounded weight $2^K$, the sum of the weights in each bucket, and the total weight $W$.

To sample, draw a random integer $x$ in $[1,W]$, start from the non-empty bucket that holds the largest weight $2^K$.  If $x$ is at most the sum of the weights in the bucket, take the $j$th item in this bucket, where $j$ is something like $\lceil x/2^K\rceil$. Oherwise subtract the sum of the weights in the bucket from $x$ then recurse with the bucket that holds $2^{K-1}$.

If you have a weight distribution with very high ratio of largest weight to smallest weight, classify a weight as small if its ratio to the maximum weight is less than, say, $1/n^3$.  Let $2^k$ be the smallest power of 2 larger than all small weights, and round each small weight up to $2^k$ (instead of its next largest power of 2).  (This may be necessary in order to use 64-bit integer arithmetic to keep track of the exact total weight $W$.) If you happen to sample a small weight $i$ that has been rounded up to $2^k$, as before you only keep it with probability $i/2^k$, and otherwise resample.  The probability of keeping it can be small, but the probability that you draw any such item is, say, $O(1/n^3)$, so you still do $O(1)$ resamples in expectation.

Now you have at most $3\log_2 n$ buckets, and worst-case (expected) time per sample is $O(\log n)$.  As you delete weights, when the total weight of the small items reaches, say, a $1/n^2$ fraction of the total weight, reclassify the small items, taking some out of the "small-item" bucket.  This happens $O(\log X / \log n)$ times, where $X$ is the ratio of largest weight to smallest weight.

You can get time $\Theta(\log n)$ for some distributions (e.g., for each $k\le \log n$ you have $2^k$ items of weight $n/2^k$).  But in practice I was getting small constant sample time and update time.


A question to the #P-complete proof of the permanent from Ben-Dor/Halevi In the paper of Ben-Dor/Halevi [1] it is given another proof that the permanent is
$\#P$-complete. In the later part of the paper, they show the reduction chain
\begin{equation}
\text{IntPerm} \propto \text{NoNegPerm} \propto \text{2PowersPerm} \propto \text{0/1-Perm}
\end{equation}
while the permanent value is preserved along the chain. Since the number of satiesfying assignments of a 3SAT formula $\Phi$ can be obtained from the permanent value, it is sufficient to compute the permanent of the final $0/1$-matrix. So far so good.

However, it is well known that the permanent of a $0/1$-matrix $\text{A}$ is equal to the number of perfect matchings in the bipartite double cover $G$, i.e., the graph from the matrix $\begin{pmatrix} 0 & \text{A} \\
\text{A}^t & 0 \end{pmatrix}$. And this number can be computed efficiently if $G$ turns out to be planar (using Kastelyens algorithm).

So in total this means, someone could compute the number of satiesfying assignments of a boolean formula $\Phi$ if the final graph $G$ is planar.

Since the embedding of $G$ depends heavily on the formula $\Phi$, the hope is, that there exists certain formulas that lead more often into planar bipartite covers.
Does anyone know if it has ever been investigated how large the chances are that $G$ will be planar?

Since counting satiesfying solutions is $\#P$-complete, the graphs will be for sure almost always non-planar, but i can not find any hints regarding this topic.

[1] Amir Ben-Dor and Shai Halevi. Zero-one permanent is #p-complete, a simpler proof. In 2nd Israel Symposium on Theory of Computing Systems, pages 108-117, 1993. Natanya, Israel.

This topic has been extensively investigated in recent years under the name of Holographic Algorithms by researchers such as Valiant, Cai, Lu, Xia, Lipton, and others. Essentially all tractable cases of #CSP (counting constraint satisfaction problems) have been identified in terms of dichotomy theorems (FP vs. #P-complete). In particular, Matchgate computations have been identified as the specific class of counting problems that become tractable on planar graphs. See e.g. this link for further references.


Why is an even-odd split 'faster' for MergeSort? MergeSort is a divide-and-conquer algorithm that divides the input into several parts and solves the parts recursively.
...There are several approaches for the split function. One way is to split down the middle. That approach has some nice properties, however, we'll focus on a method that's a little bit faster: even-odd split. The idea is to put every even-position element in one list, and every odd-position in another.

This is straight from my lecture notes. Why exactly is it the case that the even-odd split is faster than down the middle of the array?
I'm speculating it has something to do with the list being passed into MergeSort and having the quality of already sorted, but I'm not entirely sure.
Could anyone shed some light on this?

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!


Is there an algorithm which gets incrementally "smarter" as it runs? Mind the following program:

n = 0
best = 0
while (true):
  if (hash(n) > best):
     best = hash(n)
  ++n

If you leave this program running for 10 years, when you come back you'll have a n : N such that hash(n) is really, really big. If someone ever needed a proof of ∃ n : ℕ . hash(n) > K, you could probably sell/provide it to him. In a way, as time passed, that program became incrementally smarter at proving statements of this specific shape. In a way, you could say it was generating knowledge. Obviously, the knowledge generated by that program is very specific and probably useless.

What I want to know is: is there any "generic" way to convert "computing power" in "knowledge"? In other words, is there an algorithm that, as it evolves, becomes incrementally more efficient at proving arbitrary statements?

More formally, given a function A : {0,1}* -> Theorem -> Maybe Proof (which attempts to prove a theorem given some knowledge), and an heuristic H : {0,1}* -> A -> Number (which estimates the efficiency of A at proving arbitrary statements given a specific knowledge), does there exist a P : {0,1}* -> {0,1}* such that ∀ n : ℕ . ∀ m : ℕ . n > m ⇒ H(P^n(∅)) > H(P^m(∅))?

Let's assume you're working on a toy programming language Flarp late at night and someone whispers in your ear a great deal of its particular Chaitin's Omega and you're clever enough to realize what you've got and type it down.

You could then write a special interpreter function F and a little script that enumerates Flarp programs and runs them as follows (from the wikipedia page):

  Given the first n digits of Ω and a k≤n, the algorithm enumerates the
  domain of F until enough elements of the domain have been found so
  that the probability they represent is within 2−(k+1) of Ω. After this
  point, no additional program of length k can be in the domain, because
  each of these would add 2−k to the measure, which is impossible. Thus
  the set of strings of length k in the domain is exactly the set of
  such strings already enumerated.

As your algorithm ran and enumerated more and more programs, the size of programs for which you can solve the halting problem will grow as well, allowing you answer many interesting questions like Goldbach's conjecture, etc.

(obviously this answer is a bit of a joke. I'm also not an expert on any of the above and may have misrepresented things)