Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs? Feedback Vertex Set (FVS) is NP-complete for general graphs. It is known to be NP-complete for degree-$8$ bounded graphs due to a reduction from vertex cover.
The Wikipedia article says that it is poly-time solvable for degree-$3$ bounded graphs and is NP-complete for degree-$4$ bounded graphs. But I have not been able to find any proof for this anywhere. Is it true?

What is the minimum $d$ such that FVS in degree-$d$ bounded graphs is
NP-complete?

Li and Liu's algorithm is incorrect (see below).  Ueno et al.'s algorithm is correct, and a similar algorithm can be found in Furst et al. 1.  Both algorithms reduce the problem to the polynomial-solvable matroid parity problem [3].

Its reduction from VC ensures the NP-hardness for degree-6 bounded graph!  As VC is already NP-hard on cubic graphs. Speckenmeyer has claimed that his thesis [4] contains the proof of NP-hardness of FVS on planar graphs of maximum degree four, but it's very hard to find (I'll greatly appreciate if who have access to his thesis can send me a copy). Fortunately, a new proof of
the NP-hardness of degree-four bounded graphs can be found in 2:

Remarks on 2:
 - In fact, he proved that the problem is APX-hard, but it is easy to verify
that his reductions are also valid for the proof of NP-hardness of the problem.
 - Its reduction does NOT apply to planar graphs.

Merrick L. Furst, Jonathan L. Gross, and Lyle A. McGeoch, “Finding a maximum-genus graph imbedding,” Journal of the ACM, vol. 35, no. 3, pp. 523–534, 1988. 10.1145/44483.44485
Rizzi, R.: Weakly fundamental cycle bases are hard to find. Algorithmica 53(3), 402-424 (2009) 10.1007/s00453-007-9112-8
László Lovász, “The matroid matching problem,” in Algebraic Methods in Graph Theory, ser. Colloquia Mathematica Societatis János Bolyai, vol. 25, Szeged, Hungary, 1980, pp. 495–517.
Ewald Speckenmeyer, “Untersuchungen zum feedback vertex set problem in ungerichteten graphen,” PhD thesis, Universität-GH Paderborn, Reihe Informatik, Bericht, 1983.


What is the time complexity of computing a Fibonacci number of at least n? This is not the same as that classic time complexity problem about Fibonacci numbers your professor taught you in school. (That one asked for the time complexity of the nth Fibonacci number; I'd like the complexity of computing the Fibonacci sequence until encountering a value ≥ n.)

This arises in the data structure for ropes: the Boehm et al. paper on Ropes requires us to slot subtrees (containing subropes) into slots in the array; are numbered by their Fibonacci number¹:

1  2  3  5  8
↑        ↑
↑        subrope
subrope

That is, the slot labelled "3" holds a (single) rope whose length is in [3, 5).

A various points, we have leaves of (mostly) arbitrary size, which must then be slotted into a slot; thus, we need to compute which slot it goes into.

That algorithm is (mostly) trivial to write, but in terms of the number n, what is the running time of fibonacci_of_at_least(n)?

¹I've mirrored the diagram over a vertical line from how the Boehm et al. paper represented it; I frankly find the Boehm et al. paper's representation odd from a CS perspective, where the slot 1 is almost certainly going to be index 0 in an array in an implementation, and ergo belongs on the left.)

The Boehm et al. paper mostly elides this problem: since the Fibonacci numbers we need correspond to the length of a string, we only need up to that length. 64-bits is ~100 numbers, and gets you out to exabyte string lengths. You can thus compute these in O(1) time, by just precomputing the table. However, I'm interested in the theoretically complexity.

It is known that
$$
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}.
$$
Using this, compute $F_1,F_2,F_4,\ldots,F_{2^m}$ until $F_{2^m} \geq n$. Then use binary search to recover the minimal Fibonacci number exceeding $n$.

Since $F_r$ grows exponentially in $r$, we have $2^m = \Theta(\log n)$ and so $m = \Theta(\log \log n)$. The algorithm thus runs in $O(\log\log n)$ steps. Each one involves calculation with numbers of size $O(\log n)$, so the overall complexity is $\tilde{O}(\log n)$.


Smallest set that intersects some given sets Let $S_1,S_2,\ldots,S_n$ be sets that may have elements in common.  I'm looking for a smallest set $X$ such that $\forall i,\,X\cap S_i \ne \emptyset$.

Does this problem have a name?  Or does it reduce to some known problem?

In my context $S_1,\ldots,S_n$ describe the elementary cycles of a strongly connected component, and I'm looking for a smallest set of vertices $X$ that intersects all cycles.

Your first problem is the hypergraph transversal problem (aka the HITTING SET problem). The second problem is the FEEDBACK VERTEX SET problem. Both the problems are NP-complete.


Efficient representation of set of partial order I guess that notions I describe are already well known, may be by combinatorician, but I do not know their name or any book/article about them. So if you have a link/title I would love to read it.

Let $r$ be an integer, let $P_r$ be the set of partial (pre)order over $[1,r]$ and $T_r$ the set of total (pre)order. I say that $P\in P_r$ is included in $T\in T_r$ if it is included as subset of $[1,r]^2$, or to state it another way, if for all $i,j$ with $i$ less than $j$ for $P$ then it is also less for $T$. Finally I say that $P$ and $P'$ are incompatible if there is $i,j$ with $i<j$ for $P$ and $i>j$ for $P'$ (or if $i=j$ for $P$  and $i<j$ for $P'$).

Let $P\in P_r$ with $i<j$ and no $k$ such that $i<k<j$, then $P_{i,j}$ is the same partial (pre)order, except that $i$ and $j$ are incomparable.

I would like to find an efficient data structure to store a subset of $P_r$. I can't imagine something better than a trie of depth $r(r-1)/2$, with one level for every pair $(i,j)$ with $i<j$. If possible I would want to be able to efficiently add and remove elements from the set, or at least to easily transform $P$ into $P_{i,j}$ as defined above.

I need to know if for a given subset $S$ of $P_r$ and $P\in P_r$, $P$ is incompatible with every $P'\in S$. Or an equivalent problem would be to figure out if a set $S$ is such that its element are one to one incomparable. I also need to know if for every total (pre)order $T$ it is a superset of a partial order $P\in S$.

Intuitively, to each $P\in P_r$ is associate its set $T_P=\{T\in T_r\mid T\supseteq P\}$ and I need to know if $(T_P)_{P\in S}$ form a partition of $T_r$.
Then let $T_S=\bigcup_{P\in S} T_P$, then I would also be interested by having a way to efficiently describe $T_S$. (That is, efficiently checking for a given $T\in T_r$ if $T\in T_S$.

Finally, I will introduce the real structure I'm interested in, which is more complicated and probably less usual.

A partial preorder $P$ can be seen as partial function from $[1,r]^2$ to $\{<,>,=\}$, where $i=_P j$  if $i<j$ and $j<i$ in $P$ and $f(i,j)$ is undefined if neither $i<j$ nor $i>j$ in $P$. We can associate to $P$ a subset of $\mathbb N^r$ called $\mathbb N_P$ defined by  $(x_1,\dots,x_r)\in \mathbb N_P$ if for all $i<_Pj$  $x_i<x_j$ and for all $i=_Pj$, $x_i=x_j$.

The real data structure I must study is the structure of partial function from $[1,r]^2$ to $\{<,\le,>,\ge,=,\not=\}$. I will call this structure "extended preorder". Let $P$ be an extended preorder,  where $(x_1,\dots,x_r)\in \mathbb N_P$ if for all $i<_Pj$  $x_i<x_j$ and for all $i=_Pj$, $x_i=x_j$, for all $i\le j$, $x_i\le x_j$, and for all $i\not_P=j$, $x_i\not=x_j$.

I say that a total preorder $T$ is included in an extended preorder $P$ if $i\le_Pj$ implies $i<_Tj$ or $i=_Tj$, and $i\not=_Pj$ imply $i<_Tj$ or $j<_Ti$.

The operation I must have are still the same, having a set $S$ of extended preorder, verify if an extended preorder is incompatible with every extended preorder of the set, and verify that every total preorder is included in an extended preorder of the set. Or to say it another way,  $(\mathbb N_P)_{P\in S}$ is a partition of $\mathbb N^r$.

Restrictions on pre-orders

You've described that you would like to assert restrictions on a given pre-order: for instance, that specifically $a < b$ rather than merely $a \leqslant b$, so that it would not be compatible with a pre-order in which $a \cong b$ (that is $a \leqslant b$ and $b \leqslant a$). We can achieve this by supplementing the pre-order with a list of forbidden relationships: that is, we specify $a < b$ using a pre-order which specifies $a \leqslant b$ along with many other relationships, and by separately specifying that $b \leqslant a$ is forbidden.

We may similarly represent $a \not\cong b$ by having any pre-order in which at least one of $a \leqslant b$ or $b \leqslant a$ fails to hold. (I got this confused in a previous edit.)

So: we will consider how to represent pre-orders, and presume that we have a list of further restrictions representing relations of the type $\leqslant$, $\geqslant$, and $\cong$ which we forbid between certain pairs. (For each pair $(a,b)$, there are then four possibilities for forbidden relations, including the the case of no forbidden relation.) The forbidden relations I would represent as a list, which we will later iterate through exactly once; however, in order to be able easily to remove restrictions when computing the order $P_{a,b}$ from a pre-order $P$, you might want to combine this list structure with an $r \times r$ array $F$ which stores for each $1 \leqslant a < b \leqslant r$ what sort of relation (if any) is forbidden between $a$ and $b$.

Representing pre-orders

You can easily represent a partial order by a transitive reduction: a minimal relation (naturally represented as a directed graph, via adjacency lists for immediate predecessors and immediate successors) subject to the constraint of having the partial order as its transitive closure. For a pre-order, you can instead use a relation $R$ which would be the transitive reduction if you "collapsed" all sets of equivalent elements to a single item each; where for all $i \leqslant j$, we have $(i,j) \in R$ if and only if $\exists k: i \leqslant k \leqslant j$ implies that $j \leqslant i$. That is, $(i,j) \in R$ only if one of the following holds:

$i < j$ and $\neg\exists k: i < k < j$;
$i \leqslant j$ and $j \leqslant i$.

Such a relation can be easily computed by reduction to computing the transitive reduction of the partial order obtained, as I described, by collapsing equivalence classes (using only one representative node for each equivalence class, and then copying relations across the class). This can be done in time $O(r^3)$ or better.

Given such a representation of pre-orders $P$ by reductions $R$, one may decide $(i,j) \in P$ by testing $(i,j)$-connectivity in $R$, e.g. by breadth-first search. This, of course, takes time $O(n)$. However, one can quite efficiently compute the reduction $R_{i,j}$ of the pre-order $P_{i,j}$ for $i<j$, by

copying the immediate successors of $j$ and sharing them with $i$,
copying the immediate predecessors of $i$ and sharing them with $j$,
removing the relation $(i,j)$ from $R$.

The complexity of this is essentially the sum of the in-degree of $i$ and the out-degree of $j$. I imagine that you would also like to remove the prohibition on $i \leqslant j$ and/or $j \leqslant i$ at the same time; we can achieve this simply by removing any restrictions which are stored at $F[i,j]$ or $F[j,i]$ as appropriate.

Representing subsets of $S \subseteq P_r$

Assuming that all you want to use the subsets $S \subseteq P_r$ for is to check compatibility of individual pre-orders with the elements of $S$, I think the best approach is to store an $r \times r$ array where each element $(i,j)$ contains a collection which indicates the labels of all pre-orders $P \in S$ such that $(i,j) \in P$. (That is: you do not need to store any forbidden relationships.)

The collection may as well be a simple list, for small sets $S$ or if the orders which it contains don't have too many common relations (e.g. minimal and maximal elements in common); otherwise use your set-implementation of choice (e.g. balanced search trees) instead. This can be updated simply by adding a new relation $P'$ to the entries for all pairs $(i,j)$ which are contained in $P'$. If $P'$ is represented by a reduction $R'$, one may do this by a depth-first search from its minimal elements (which one may store a list of in the representation), and performing depth-first search to find all descendants of each element.

If one maintains a list of traversed nodes along each path of the traversal, one may add each newly traversed node to the descendants of each of those already on the list; after finishing a traversal, pop the node off the list and mark it as visited.
For each visited node, we copy its descendants to any nodes on the traversal-list, rather than re-traversing it.

This is also a good thing to do, to compute a more explicit representation of $P'$ from $R'$, once your interest in $P'$ becomes dominated by testing $(i,j) \mathbin{\in?} P'$. This will take time $O(r^2)$, as there is essentially unit cost to reverse each edge $(i,j) \in R$, and to record each of the descendants of any $i \in [1,r]$ throughout the traversal. If $s = |S|$ and you use trees for collections at each index $(i,j)$, constructing the representation for $S$ takes time $O(r^2 s \log s)$, with the $\log s$ factor being saturated in the case where many elements of $S$ share many pairs $(i,j)$ in common. This works best for partial orders which are sparse and essentially unrelated, which would reduce both the expected overlap for pairs $(i,j)$ and the number of entries $(i,j)$ for which any relationship is recorded in the traversal of its reduction.

Having this representation of $S$, you can test incompatibility of $P$ with $S$ (where $P$ is given by a reduction $R$) as follows.

Initialise a list of all of the elements of $S$, representing those which are potentially compatible with $P$.
Iterate through your forbidden relations, and remove from the list of potentially compatible relations, any element of $S$ which violates any of the constraints. (That is, if $a \leqslant b$ is forbidden, remove any element of $S$ for which that relation holds; and similarly for any element of $S$ fo which $a \cong b$, if that relation is forbidden.)
Perform a breadth-first search of $R$: and at each link $(i,j) \in R$ traversed, remove from the list of potentially-compatible orders any order $P$ for which $j < i$, by checking for each order on the list whether this is the case.

If the list of potentially-compatible orders ever becomes empty, then $P$ is incompatible with $S$. Otherwise, the list contains at least one partial order in $S$ with which $P$ is compatible.

We can bound each index search $(i,j)$ for a potentially-compatible order by $O(\log s)$, for $s =|S|$; this will happen for each "reduced" relation in $P$, that is for every ordered pair in $R$. If $m = |R|$, then the worst case is $O(ms \log s) \subseteq O(r^2 s \log s)$, in the case that every element of $S$ is compatible with $P$. If you have $f = |F|$ forbidden relationships, then iterating through these and eliminating potentially compatible relations takes time $O(f \log s)$; this is also dominated by $O(r^2 \log s)$, though the larger $f$ is the faster the subsequent compatibility-checking becomes.


Uniform derandomisation of circuit complexity classes Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined in the same way as $\textrm{BPP}$ is defined with respect to $\textrm{P}$. More formally we provide polynomially many random bits and we accept an input iff the probability to accept is over $\frac{2}{3}$.

In a previous post, I asked if it was known whether the equality holds between  $\mathcal{C}$ and $\textrm{BP-}\mathcal{C}$ for $\mathcal{C}$ a circuit complexity class. The answer is yes for all complexity classes expressive enough to compute Majority and for $\textrm{AC}^0$ for some other reason.
Those results are however non-uniform and I would like to know:

Are uniform versions of those results studied or known? Any partial results ?
Do they imply long standing conjecture?

I believe that uniform derandomisation of $\textrm{P}/\textrm{poly}$ is exactly $\textrm{P}=\textrm{BPP}$ so I expect the answer to be "yes" but it is less clear to me what uniform derandomisation of small classes within the $\textrm{NC}$-hierarchy would imply.

The class uniform-RNC has been studied a lot.
It is an open problem whether uniform-RNC = uniform-NC. Uniform-(R)NC correspond to (randomized) PRAMs with polynomially many processors and polylogarithmic running time (see the Handbook of Theoretical Computer Science Vol. A). So the question is whether every efficient randomised parallel algorihm can be derandomized.

Since symbolic determinant identity testing is in uniform-RNC, derandomizing RNC implies circuit lower bounds by the results of Kabanets & Impagliazzo (Computational Complexity, 13(1-2), pages 1-46, 2004).

An important special case is the question whether we can compute perfect matchings in uniform-NC. There are several randomized parallel algorithms known, but we do not know whether there is a deterministic one. Recently,
Fenner, Gurjar and Thierauf (STOC 2016) have shown that we can compute perfect matchings in bipartite graphs by uniform circuits of polylogarithmic depth and quasipolynomial size.


Constant Width Max Sum Product Multi-objective Shortest path problem This question is a follow-up on the question I asked three days ago here.

For convenience I restate it here.

I am given a graph. Each edge is labelled by a vector of numbers, called weights. They are numbers between 0 and 1, which sum up to 1 (at most).
A path is first assigned a vector, which is the component-wise product of the weights of the edges along the path. The path is then assigned a value, which is the sum of the entries of this vector. I am interested in the maximum path.

More specifically, I consider the following decision problem: given a graph, a source, a target and a threshold c in (0,1), does there exist a path from the source to the target whose value beats the threshold c?

As @Denis has shown, this problem is NP-complete if the size of the vector is part of the input.

I am interested in the following restriction: now the size of the vectors (meaning, number of entries) is restricted to a constant K (not part of the input).
It is clear that the problem is polynomial for K = 1. Is it polynomial for K = 2? Is there K such that it is polynomial for K and NP-complete for K+1?

For K=2, PARTITION reduces to this problem, so it is NP-hard.

Take an instance of PARTITION: a list of nonnegative integers $x_1,\dots ,x_n$, and you ask if there is a subset $I\subseteq [1,n]$ such that $\sum_{i\in I} x_i=\sum_{i\notin I}x_i$.

Let $S=\sum_{i\in[1,n]} x_i$, and $y_i=\exp(-\frac{x_i}S)$ for each $i$. Note that $y_i\in (0,1)$.

You build a graph with $n+1$ nodes $p_1,\dots ,p_n,p_{n+1}$.
You have two edges from $p_i$ to $p_{i+1}$: one with weight $(\frac{y_i}2,\frac12)$ and the other with weight $(\frac 12,\frac{y_i}2)$. The division by $2$ is there to ensure the additionnal constraint that the sum of coordinates is at most $1$.

A path from $p_1$ to $p_{n+1}$ corresponds to a partition $I$: you end up with the vector $$\big(\dfrac{\exp(-\frac1S\sum_{i\in I} x_i)}{2^n}~,~ \dfrac{\exp(-\frac1S\sum_{i\notin I} x_i)}{2^n}\big).$$
Since the minimum of $e^{-x}+e^{-(1-x)}$ is reached for $x=1/2$, there exists a path of weight $\exp(-1/2)/2^{n-1}$ if and only if there was a balanced Partition of the initial integer list.


VC-Dimension and sample complexity dependent on size of subsets I have a range space $(X,R)$, were $R$ is a collection of subsets of $R$ and I have an upper bound $d$ to the VC-dimension of $(X,R)$. Suppose for simplicity that $X$ is finite. Given $\delta\in(0,1)$ and an integer $m>1$, I know that if I have a random sample $S$ from X of size $|S|=m$, then for $\varepsilon=\sqrt{\frac{d+\log(1/\delta)}{m}}$, we have
$\Pr\left(\exists r\in R ~:~ \left|\frac{|r|}{|X|}-\frac{|r\cap S|}{|S|}\right|>\varepsilon \right)<\delta$.

Notice how $\varepsilon$ does not depend on the sizes of the members of $R$. I was wondering whether I can get a smaller $\varepsilon$ if I know that all members of $R$ have a specific size, or better, if I know that there is a $\phi\in(0,1)$ sucht that $\frac{|r|}{|X|}=\phi$ for all $r\in R$.

Thanks.

No, you cannot. See Thm 2.1 of http://link.springer.com/article/10.1007%2FBF02187833 (it says that a random family gives an example, with appropriately chosen parameters).


Diameter of a graph with O(|V|) edges What's the minimum diameter of a connected undirected graph with |V| vertices and O(|V|) edges?

A line graph has O(V) edges and diameter V-1. A star graph also has O(V) edges and diameter 2. So it seems that the constraint that a graph has O(V) edges places almost no restriction at all on what the diameter can be.

Of course, 2 is the minimum, since only a complete graph has diameter 1.


How to build comparison operator (comparator) in an arithmetic circuit I am trying to convert a basic program into an arithmetic circuit. I am stuck on the step of converting the greater than operator into an arithmetic circuit. To be specific, I do not know how to convert the following into an arithmetic circuit (where x,y is input):

if x >= y:
    return 1
else:
    return 0

To be clear, I need to be able to express this in terms of an ARITHMETIC circuit. Meaning that I need to be able to compute this using only addition and multiplication of numbers (in Z_p).

I've been searching all of the web for solutions, but everything I find tells me how to do this with boolean circuits. I am aware that I can convert the numbers into their bit string and do this boolean way. I would like to know of any alternative way to do this. This show be possible to do with just addition and multiplication, but I cannot figure out how to.

For context, I'm considering this in the case of Multi-Party Computation. Therefore, taking advantage of how I represent my number (i.e. two's complement) will not work because my number will be split into secret shares.

I believe this is generally done in MPC by converting the sharing of the field element to some sharing more amenable to comparison. See this (section 6.3), or chapter 9 in Secure Multiparty Computation and Secret Sharing by Cramer et al.

Generically, comparisons are dependent on how you represent values in $\mathbb{F}_p$. For example, in $\mathbb{F}_3$ you might want to say that $1 \leq 2$, but since $-1$ is in the same equivalence class as $1$ any polynomial that computes this (for $\mathbb{F}_3\cong \{0,1,2\}$) would also compute $1 \leq -1$ (for $\mathbb{F}_3\cong\{-1,0,1\}$). You could of course use Lagrange Interpolation to get any polynomial to have arbitrary values, but it'd be difficult to call that polynomial "the comparison polynomial", and your model of arithmetic circuits would have to be with respect to a specific representation of field elements (which sounds non-standard, but I'm no expert).

The book by Cramer et al has some commentary on how comparisons using solely $\mathbb{F}_p$ arithmetic leads to large circuits, so maybe there is actually some "comparison polynomial" (and m preceding paragraph is wrong), but it appears the standard thing to do still is to convert to an easier representation to do comparisons on for efficiency.


FloodSet in general networks I would like to ask how could someone modify FloodSet algorithm to work in a general network,
where process failures happen..Is it possible for it to work if a "crucial" [1] failure happens?

[1]: As crucial i mean a failure in a process that "cuts" the network in two separate pieces

I'm assuming that you mean the Flood Set algorithm for solving the agreement problem in Section 6.2 of [1]. The Flood Set algorithm proceeds in rounds and requires every process $u$ to forward all received values, which it stores in a set $W$; initially $W$ contains $u$'s input value. We assume that $f$ processes can be faulty. After $f+1$ rounds, every alive process $u$ checks if its set $W$ is a singleton. If so, $u$ decides on the singleton value, otherwise $u$ decides on a default value $x$. It can easily be shown that after $f+1$ rounds, all correct processes have the same set $W$.

For a general graph, the answer is obviously no: Suppose that the network is cut by a faulty process $u$ into parts $C_0$ and $C_1$ and processes in $C_0$ start with $0$ whereas processes in $C_1$ start with $1$. If $u$ crashes initially, the following happens in round $f+1$: all processes in $C_0$ will decide on $0$ and all processes in $C_1$ will decide on $1$.

Note that this impossibility argument holds for any agreement algorithm.

[1] Nancy Lynch. Distributed Computing. Publisher: Morgan Kaufmann


Is there any research on Turing machines with transition relation homomorphic to given algebraic structure? A Turing machine is defined as a structure $ TM(L,Q,T) $, where $L,Q$ are sets of symbols and internal states of TM respectively, and T is a transition relation:

$T: L \times Q \to L \times Q $

for simplicity suppose that $Q$ contains all "terminal states" that is $ \{ START,STOP \} $, and information about next move of the head on the tape, that is $\{L,R\}$ - it is just another information about internal state of the machine. $L$ contain all terminal symbols. This are finite sets.

This assumptions are for simplicity and easy notation, because full definition of TM is well known, and there is no need to explain it I presume. Please take a look for other questions below where such simplification is provided in more detailed way.

$T$ is then a table with for example elements $Q$ in the column and elements of $L$ in  the rows. An element of such table is value of $T$ for its arguments that is:

$T(q_i,a_k) = (q_j,a_s)$

Suppose that there is a homomorphism between $T(q_i,a_k)$ (as table) and certain finite algebraic structure (group, monoid, algebra, possibly some exotic structure). Or suppose that such transition relation has certain symmetries (for a stupid example here let me write: $T(q_i,a_k) = T(q_k,a_i)$) or "subtables" with structure or symmetries homomorphic to given algebraic or other structure.

For given structure of $T(q_i,a_k)$,
are there any known facts about
class    of TM with that structure?
Are there any known equivalence
classes of $T(q_i,a_k)$ arising from algebraic
properties of $T(q_i,a_k)$ ?

Asking this question I follow the suggestion of  Dave Clarke. This is question related to following questions:

asked here - Turing Machine which generates order on the set of its states
asked on mathoverflow (and for which there is an answer by Joel David Hamkins) Turing Machine which generates order on the set of its states

There are results about algebraic properties of languages (as opposed to the machines accepting the languages). For example, regular languages can be characterised using monoids. The Myhill-Nerode theorem relates an algebraic structure with the transition relation of a specific class of finite automata. You could look up those and subsequent results.

Rather than homomorphisms, bisimulation and simulation relations are the notion of choice for relating the structure of transition systems. Checking language equivalence between pushdown automata is undecidable but deciding equivalence of languages accepted by deterministic PDAs was open until 2001 when Gerard Sénizergues showed it was decidable. His proof uses algebraic ideas. Colin Stirling later gave a simplified proof (writeups and slides are available on his homepage).

  Sénizergues, Géraud, The equivalence problem for deterministic pushdown automata is decidable, Degano, Pierpaolo (ed.) et al., Automata, languages and programming. 24th international colloquium, ICALP ’97, Bologna, Italy, July 7--11, 1997. Proceedings. Berlin: Springer-Verlag (ISBN 978-3-540-63165-1/pbk; 978-3-540-69194-5/ebook). Lecture Notes in Computer Science 1256, 671-681 (1997). ZBL1401.68168.


Does such a bipartite graph exist? In the course of my studies on graphs I sometimes use gadgets. I recently came upon a need for a certain bipartite graph with the following properties, and I am wondering if anyone knows if such a graph exists, or can give a construction.
Given two integers $d$ and $k$, I seek an undirected bipartite graph $G=(L∪R,E)$ with:

All vertices in $L$ have degree either $d$ or $d+1$.
Exactly $k$ vertices in $R$ have degree $d−1$, all other vertices in $R$ have degree exactly $d$
The graph is $d−1$ edge-connected.

I really believe that such a graph does exist. But it is a bit difficult to come up with a proof, or a construction. Anyone can show that such a graph exists?

Theorem 1. For every $d$ and $k$, there is a graph with the desired properties.
I'll describe the construction in two stages.
First, construct a bipartite multi-graph $G_1=(L_1, R_1, E_1)$ where

$L_1=\{\ell_1,\ell_2,\ldots,\ell_k\}$

$R_1 =  \{r_1, r_2, \ldots, r_k\}$

$E_1$ is the multi-set union of $d-1$ matchings $M_1, M_2, \ldots, M_{d-1}$, where

$M_h = \{(\ell_i, r_j) : (i + j + h) \bmod k = 0\}$ for $h\in\{1,\ldots, d-1\}$

Note that there may be multiple copies of each edge in the multigraph $G_1$.  (In particular, in the case that $d-1\ge k$, we can have $M_h = M_{h+k}$.)  We add a copy of $(\ell_i, r_j)$ to $E_1$ for each occurrence in any matching, making $E_1$ a multiset and $G_1$ a multigraph.
Lemma 1. $G_1$ is $(d-1)$-edge connected.
Proof. Consider the $d-1$ edge sets $M_1 \cup M_2$, $M_2 \cup M_3$, $\ldots$, $M_{d-2} \cup M_{d-1}, M_{d-1} \cup M_1$.  Each such edge set is a hamiltonian cycle, so any cut is crossed by at least $2(d-1)$ edges in the multiset union of these $d-1$ edge sets.  But each edge (copy) occurs twice in this multiset union, so any cut is crossed by at least $(d-1)$ edge (copies). $~~\Box$
Now obtain the desired graph $G=(L, R, E)$ from $G_1$ as follows.
For each vertex $\ell_i$ in $L_1$, replace $\ell_i$ by a distinct copy of $K_{d,d}$ (the complete bipartite graph with $d$ vertices on each side),
and replace each edge copy $(\ell_i, r_j)$ in $E_1$ by an edge from a vertex on the left side of the $K_{d,d}$ to $r_j$, so that each vertex on the left side of each $K_{d, d}$ has at most one edge added in this way.  This is possible because each $\ell_i$ has degree $d-1$, and the $K_{d,d}$ that replaces it has $d$ vertices on its left side.  Note that $G$ is a graph (not a multigraph), and that $G_1$ is obtained by contracting each $K_{d, d}$ into a single vertex.
Take $L$ to contain the vertices on the left sides of the $K_{d, d}$'s (each of degree $d$ or $d+1$).  Take $R$ to contain the $k$ degree-$(d-1)$ vertices in $R_1$, together with all vertices on the right sides of the $K_{d, d}$'s (each of degree $d$).  To finish, we prove the following lemma:
Lemma 2. $G$ is $(d-1)$-edge connected.
Proof. Suppose otherwise for contradiction.  Let $C$ be a cut of $G$ with less than $d-1$ edges.  The cut $C$ respects (doesn't cut) any $K_{d, d}$, because each $K_{d, d}$ is itself $d$-edge connected.  So contracting each $K_{d, d}$ yields a cut in $G_1$ that has less than $d-1$ (multi) edges, contradicting Lemma 1.  $~~~\Box$


Rademacher complexity and lowerbounds in learning theory Is there any function class known whose Rademacher complexity has a non-trivial lowerbound?
Can the Rademacher complexity be used to lowerbound the generalization error in any learning situation?

First, let's distinguish between empirical end expected Rademacher complexities. The former is defined for a function class $F$ and sequence of points $X_1,\ldots, X_n$, by
$$ \hat R_n(F;X_1,\ldots,X_n) = E_\sigma \sup_{f\in F}\frac1n\sum_{i=1}^n
\sigma_i f(X_i).$$
The latter is defined for a function class $F$ and distribution $D$, by
$$ R_n(F;D) = E_{(X_1,\ldots,X_n)\sim D^n}[\hat R_n(F;X_1,\ldots,X_n)].
$$

It's known that for any function class with VC-dimension $d$, we have
$\hat R_n(F;X)=O(\sqrt{d/n})$ (for any sequence $X$) -- and hence the bound carries over to $R_n(F;D)$ for all distributions $D$.

It's also known that the Rademacher complexity upper bounds the generalization error for agnostic PAC (plus a confidence term decaying as $\sqrt{\log(1/\delta)/n}$). On the other hand there exist adversarial distributions that force any learner to have a generalization error of $\Omega(\sqrt{d/n})$;
see, e.g., my course notes
https://www.cs.bgu.ac.il/~asml162/Class_Material
.

From these considerations alone, we can conclude that for any function class with VC-dimension $d$, there is a distribution for which $R_n(F;D)=\Omega(\sqrt{d/n})$.

Edit: I also like to give the following exercise. Let $F$ be the set of all $\{\pm1\}$-valued functions on the integers. Prove that there exists a sequence of distributions $D_n$ such that $\lim_{n\to\infty}R_n(F;D_n)=1$.


Are biases necessary to make neural networks universal approximators when using sigmoid activations? In a neural network, a bias is a constant term that is added to the weighted input in a neuron/unit:
output = activation_function( input1*weight1 + ... + inputn*weightn + bias)

I can see that the bias in a sigmoid activation function adds the ability to control the threshold of the activation. But when I started learning about neural nets we didn't use any bias, just the weighted inputs. I've also been told that sigmoid in particular can do without a bias, but this is not intuitively true for me at all.

So is it true that biases are redundant in sigmoid neural nets? How can neural nets learn to approximate any continuous function if they do not have a bias input?

No, you don't need a bias. You can have a "dummy" input (input(n+1) in your formualtion) which is always set to 1. Then the bias term is absorbed into the weights.


Balanced partitioning of a set of axis-parallel 2D rectangles Fix a constant $0<\alpha<1/2$. The problem is the following. Suppose there are $N$ axis-parallel rectangles on the 2D plane with weights $w_1, w_2,\ldots, w_N$ and with coordinates all in the range $[0,M]$ for some $M$. Let $W=\sum w_i$. Find a simple (i.e. non self-intersecting) curve that partitions them into two sets of rectangles such that each set has total weight at least $\alpha W$ and the total weight of all rectangles cut by the curve is as small as possible, or output that no such curve exists. This is NP-complete, and I'm interested in a good heuristic/approximation algorithms with $O(N+poly(M))$ time (or more exactly $O(N+poly(M)+polylog(W))$ time).

A thorough search doesn't give me any reference in literature that studies this problem. Any insight is appreciated!

This seems like a hard problem. You might be able to do something if the rectangles have some packing property. For example, if no point is covered more than $t$ times (for some constant T), and the rectangles are not too long and narrow. Then one can probably prove that a curve intersects $O( \sqrt{n})$ rectangles, using some $k$-ply planar separator argument.


Boundary between decidability and undecidability for small theories There is a lot of research on the boundary between decidability and undecidability of the halting problem for small models of computation: Turing machines, tag systems, CAs, ... This boundary is clearly linked to the (non-)universality of such models.

I'm wondering if there are similar works on the "logic-side":

  What are the smallest theories for which the boundary between  decidability and undecidability (of valid formulas) is unknown ?
  Is there a survey paper on the subject ?

I realize that it is not easy to formalize the notion of "small theory" (or "simple" theory), but it should include the number of axioms of the theory and the size of the signature.

For example Andrzej Grzegorczyk in “Undecidability without arithmetization” (Studia Logica 79(2005))
proved that Tarski’s theory of concatenation (TC) is already undecidable; the axioms are:

TC1: $x*(y*z) = (x*y)*z$
TC2: $(x*y = u*v ) \to \exists w((x*w = u \land w*v = y)\lor(u*w = x \land w*y = v))$
TC3: $\neg (\alpha = x*y)$
TC4: $\neg (\beta = x*y)$
TC5: $\neg (\alpha = \beta)$

Let $V_k (n)$ be the function that maps $n$ to the largest power of $k$ dividing $n$.  (Not the exponent of the largest power; the largest power itself.)  It follows from the work of Büchi (as corrected by, e.g., Hodgson) that the first-order theory Th($N, +, V_k$) for fixed integer $k \geq 2$ is decidable.  But Villemaire showed (￼Theoretical Computer Science 106 (1992), 337-349) that Th($N, +, V_k, V_l$) is undecidable if $k, l$ are multiplicatively independent.  So this is a nice boundary between decidable and undecidable.

The survey paper of Bès (available here:  http://lacl.univ-paris12.fr/bes/publi/survey.ps ) makes good reading!


The relation of Gödel's Incompleteness Theorems to the Church-Turing Thesis This may be a naive question, but here goes. (Edit -- it is not getting upvotes, but nobody has offered a response either; perhaps the question is more difficult, obscure, or unclear than I thought?)

Gödel's First Incompleteness Theorem can be proven as a corollary of the undecidability of the halting problem (e.g. Sipser Ch. 6; blog post by Scott Aaronson).

From what I understand (confirmed by the comments), this proof does not depend on the Church-Turing thesis. We derive a contradiction by showing that, in a complete and consistent formal system, a Turing Machine could solve the halting problem. (If on the other hand we had just shown that some effective procedure could decide the halting problem, we would need to also assume the Church-Turing thesis to get a contradiction.)

So, we might say that this result provides a bit of intuitive support for the Church-Turing thesis, because it shows that a limitation of Turing Machines implies a universal limitation. (Aaronson's blog post certainly supports this view.)

My question is whether we can gain something more concrete by going in reverse: What formal implications do Gödel's theorems have for the Church-Turing thesis? For instance, it seems intuitively possible that the First Incompleteness theorem implies that no effective procedure can determine if an arbitrary Turing Machine halts; the reasoning might go that the existence of such a procedure implies ability to construct a complete $\omega$-consistent theory. Is this correct? Are there any results along these lines?

(I'm asking out of curiosity -- I don't study logic myself -- so I apologize if this is well-known or not research-level. In that case, consider this a reference request! Thanks for any comments or responses!)

Question that sounds related, but isn't: Church's Theorem and Gödel's Incompleteness Theorems

EDIT: I'll try to make the question more clear! First -- my naive intuition is that Gödel's Incompleteness should imply at least some limitations on what is or is not computable. These limitations would be unconditional, i.e., they should apply to all models of computation rather than just Turing Machines.

So I am wondering if this is the case (there must be some implication, right?). Assuming it is, I'm most curious about how it impacts the Church-Turing Thesis -- the notion that anything effectively calculable can be computed by a Turing Machine. For example, it seems possible that the existence of an effective procedure for deciding whether a Turing Machine halts would contradict  the First Incompleteness Theorem. This result would demonstrate that no possible method of computation can be "much" more powerful than Turing Machines; but is this result true? I have a couple similar questions in the comments. I would be very interested to hear an answer to one of these questions, a pointer to an answer in the literature, an explanation of why my entire reasoning is off-base, or any other comments!

Here is a philosophical answer that may entertain you.

Gödel's incompleteness theorems are about the formal system of Peano arithmetic. As such they say nothing about models of computation, at least not without some amount of interpretation.

Peano arithmetic easily shows existence of non-computable functions. For example, being a  classical theory expressive enough to talk about Turing machines, it shows the particular instance of excluded middle which says that every Turing machine halts or runs forever. Nevertheless, from the work of Gödel an important notion of computability arose, namely that of a (primitive) recursive function. So it is not the theorems themselves that connect to computability, but rather the method of proof which establishes them.

The gist of the incompleteness theorems can be expressed in an abstract form using provability logic, which is a kind of modal logic. This gives the incompleteness theorems a wide range of applicability well beyond Peano arithmetic and computability. As soon as certain fixed-point principles are satisfied, incompleteness kicks in. These fixed-point principles are satisfied by traditional computability theory, which therefore falls victim to incompleteness, by which I mean existence of inseparable c.e. sets. Because the provable and refutable sentences of Peano arithmetic form inseparable c.e. sets, the traditional Gödel's incompleteness theorems can be seen as a corollary to incompleteness phenomena in computability. (I am being philosophically vague and your head will hurt if you try to understand me as a mathematician.)

I suppose we can take two stands on how all this relates to the informal notion of effectivity ("stuff that can actually be computed"):

For all we know, we are just a rather large finite automaton, capable of contemplating fictional super-heroes called "Turing machines" that are able to calculate with unbounded numbers (gasp!). If this is the case, Gödel was just a very good story-teller. How his stories translate to effectivity is then a matter of some (necessarily inaccurate) application of imagination to reality.
Because incompleteness phenomena arise naturally in many contexts, and certainly in all reasonable notions of computability, we conclude that the same has to be the case for effectivity. For example, suppose we could send Turing machines into black holes to compute a la Joel Hamkin's infinite-time Turing machines. This gives us immense computational power in which the halting oracle is a kindergarten toy. But still, the model satisfies the basic conditions that allow us to show the existence of inserparable sets. And therefore once again, computation is not all-powerful and incompleteness is a fact of life.


State-of-the-art unification for associative-commutative functions I am interested what are the open problems on unification methods for associative-commutative functions, and what is the state-of-the-art work? I have found some old work, but nothing new. I am wondering if I am missing something since I am quite new to this.

It might help to say that I am generally interested in this area as I would like to apply it to modern programming languages, in terms of code canonicalization.

Here are the standard references on unification:

Franz Baader and Tobias Nipkow. Term Rewriting and All That. Cambridge University Press, United Kingdom, 1998. (Book homepage)
Franz Baader and Wayne Snyder. Unification Theory. In J.A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, pages 447-533. Elsevier Science Publishers, 2001. (Online copy here)


Embedding a n-tree into a b-dimensional space Given a (directed) n-tree $T=(N,E,r)$ rooted in $r\in N$, I want to represent each node $n\in N$ at most as a $m$-dimensional vector $v_n\in \mathbb{R}^m$ (From the current Yuri's reply, m cannot be $b$). In particular, given $h$ the height of the tree (that is, the maximum path length starting from $r$), I want to guarantee that $\forall a,b\in N. \|v_a-b_b\|_2\leq h$ if and only if there exists a directed path $\pi(a,b)$ or $\pi(b,a)$ in $T$.

Example, given the following tree rooted in $1$, $(\{1,2,3,4\},\;\{(1,2), (1,3),(3,4)\},1)$, I would instantiate the distance constraints as follows:

$\forall (a,b)\in E\cup \{(b,a)|(a,b)\in E\}. \|v_a-v_b\|_2\leq 1$
$\|v_1-v_4\|_2\leq 2$ by transitive closure
$\forall (a,b)\in V^2\backslash (E\cup \{(b,a)|(a,b)\in E\}. 3\leq \|v_a-v_b\|_2\leq 4$

I was thinking to reduce this problem into the Distance Geometry Problem, and to use the former distances to feed known solvers like DGSOL or MD-Jeep: while the first commits non-negligible errors, MD-Jeep returns some errors during the computation of the torsion angle, and therefore cannot provide a viable solution. Is this a problem of the Distance Geometry Problem itself, or are there other implementations that would not suffer from the same problem? Alternatively, is it possible to express this problem using mathematical programming, i.e. using one of the already existing libraries?

This is not possible if the dimension $m$ is fixed. Consider a complete $b$-ary tree, in which all edges are oriented from the root $r$. Then all vertices lie in a ball of radius $h$ around $v_r$. On the other hand, the distance between every two leaves is greater than $h$. Since there are $N = b^h$ leaves, we get that

  there are $N$ points in a ball of radius $h$ such that all the pairwise distances between the points are greater than $h$

We must have that $m = \Omega(\log N) = \Omega(h \log b)$.


Choosing subsets of a set such that the subsets satisfy a global constraint We have a set of items $I = \{i_1, i_2, ..., i_n\}$.  Each of these items has what we call a p value, which is some real number.  We want to choose a subset of $I$, call it $I'$, of size $m$ (for some $m$ with $1 \le m \le n$) such that the average of the p values of the items in $I'$ falls within some specified range, $[p_l, p_u]$.  (For example, we might require an average p value between 0.70 and 0.74.)  Moreover, we want to do this efficiently.

We hope to do this in O(n) time, but any polynomial time algorithm is good enough.  We certainly do not want to just try every possible subset of I of size $m$ and then check whether it satisfies the average p-value constraint.

Finally, we will be doing this repeatedly and we want the subsets chosen to be a uniformly random distribution over all the possible such subsets.

Is there a way of doing this?

From my answer at math.stackexchange: https://math.stackexchange.com/questions/3205/choosing-subsets-of-a-set-such-that-the-subsets-satisfy-a-global-constraint/3207#3207

Assuming $m$ is an input, your problem is NP-Complete.

Subset sum can be reduced to it.

Given $A = \\{x_{1}, ..., x_{n}\\}$ for which we need to find a subset of sum $S$, we can create $n$ inputs to your algorithm, with input $A$, $m$ and $p_{L} = p_{U} = \frac{S}{m}$, for $1 \leq m \leq n$.

If $m$ is fixed then the brute force algorithm (which you don't want) is $O(n^m)$ and so has a polynomial time algorithm.

If this does not answer your question, can you please clarify exactly what you need?


Is longest common subsequence with bounded occurrences NP-complete? The general longest common subsequence problem (LCS) over a binary alphabet is NP-complete. Does the problem remain NP-complete if each input string has m zeros and n ones, where m and n are constants?

I asked this question on cs.stackexchange and was told, "The problem probably remains NP-complete." However, I was unsuccessful in showing a reduction from the original LCS problem.

This paper by Blin et al. (Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths, CPM'12) provides a reduction from independent set to LCS where the Hamming weights of all strings are the same (it is $n-1$ where $n$ is the number of vertices in the independent set instance). Thus, the problem remains NP-complete under this assumption.


How hard is deciding the existence of a polygonization with prescribed perimeter? Polygonization problem of a set of points in the Euclidean plane (2D lattice) is to find a simple polygon that passes through all points. Deciding the existence of a polygonization with minimum (or maximum) enclosed area is NP-complete. The answer to this post shows that it is NP-complete to decide the existence of a polygonization with some prescribed area.
Meanwhile, Minimum perimeter polygonization of 2D lattice points is a variant of the NP-complete Euclidean TSP. However, complexity of the maximization version of planar Euclidean TSP is an open problem. The authors conjecture that the Maximum TSP for Euclidean distances in the plane is an NP-hard problem.
I am interested in the complexity of deciding the existence of a polygonization of a set of 2D lattice points (in Euclidian plane) with prescribed perimeter. I suspect that it is NP-complete. What is known about its complexity?

Your problem is NP-hard, since it contains the Hamiltonian cycle problem on grid graphs as special case: Given a set of lattice points in the plane, is there a cycle in which all edges have lengths $1$ (and hence connect two horizontally or vertically adjacent lattice points.
The grid graph has a Hamiltonian cycle, if and only if the corresponding $n$ lattice points (interpreted as geometric points) have a polygonization with perimeter $n$.

Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter:
Hamilton Paths in Grid Graphs.
SIAM Journal on Computing 11, pp 676-686 (1982)


How to quantify the complexity of vectors whose components are real numbers? I started to study Kolmogorov complexity today, and  this question came to mind. Is there any way to use LZW to do this? I'm looking for a guidance to my studies

You can use LZW or other standard compression methods to approximate the Kolmogorov complexity. In some real-world cases this works well. However, it is dangerous, as it can also be a pretty bad approximation to the true Kolmogorov complexity, viz. http://bactra.org/notebooks/cep-gzip.html.

Another option is to seek the smallest Boolean circuit that outputs a given string. This problem appears to be hard*, but (a) isn't uncomputable like $K(x)$, and (b) doesn't suffer from the potentially erroneous measure given by gzip etc. (since circuits are a standard non-uniform, universal model of computation).

*[Update: It's actually essentially the Minimum Circuit Size Problem, which is looking like it's not $\mathsf{NP}$-hard, but it's still quite hard.]


Evidence that PPAD is hard? There is often-quoted philosophical justification for believing that P != NP even without proof. Other complexity classes have evidence that they are distinct, because if not, there would be "surprising" consequences (like the collapse of the polynomial hierarchy).

My question is, what is the basis for belief that the class PPAD is intractable? If there was a polynomial time algorithm for finding Nash equilibria, would this imply anything about other complexity classes? Is there a heuristic argument for why it should be hard?

PPAD is pretty "low" above P and not much would change in our understanding of complexity if it was shown equal to P (except that the few problems in PPAD would now be in P).  The main "evidence" that PPAD!=P is an oracle separation, which is essentially equivalent to the  combinatorial fact that no "black-box simulation" exists.


Primal Dual model in the continuous domain The continuous max flow problem is posed as follows :

sup $\int_\Omega  p_s(x)dx$

subject to :

$|p(x)| \le C(x);  \forall x \in \Omega $

$p_s(x) \le C_s(x);  \forall x \in \Omega $

$p_t(x) \le C_t(x);  \forall x \in \Omega $

$\nabla \cdot p(x) - p_s(x) + p_t(x) = 0;  \forall x \in \Omega $

Here $p(x)$ is a field vector and is analogous to the flow in the discrete domain. $\nabla \cdot p$ is the divergence of the field p.

How do i find out the dual of this maximization problem using the lagrangian dual technique, i.e. the equivalent min cut formulation of the problem in the continuous domain.

Your question may be answered in the following paper:

@article{strang1983maximal,
  title={Maximal flow through a domain},
  author={Strang, G.},
  journal={Mathematical Programming},
  volume={26},
  number={2},
  pages={123--143},
  year={1983},
  publisher={Springer}
}


Is it possible to prove that a general purpose integer factorization algorithm must contain a loop? 1)
Let $A$ be a (general purpose) algorithm that factors $n$. Suppose $A$ contains a loop (which is hard to imagine if not impossible that it does not.) If $A$ contains nested loops then these loops can be combined to one loop. If $A$ contains more loops in sequence, then these loops can also be combined to one loop.
So suppose that $A$ contains exactly one loop. Since $A$ must finish the factorization after finitely many steps and output $x$ with $1 < x < n$, $x|n$, there must be an if-then statement which tests if $1 < x < n$, $x|n$ or any other mathematically equivalent test. Hence in each step $1,\cdots,t$ we have a number $a_i \in \mathbb{N}$ which is tested. But then letting $g_i = \gcd(a_i,n)$ we have $1 \le g_i \le n$. It could happen that $g_i = g_j$ for $i \neq j$.

Heuristic: We imagine that the numbers $g_i$ are drawn with replacement from the urn $\{1,\cdots,n\}$.

2) Let $n=pq$ be the prime decomposition of $n$ and let $n=2^e$.
Let us suppose that $p \equiv q \equiv \sqrt{n}$.
Let $p_n$ be the probability to have a number $1 \le x \le n$
with $1 < \gcd(x,n) < n$ and as such to also have a non-trivial factor of $n$.
Then we have
$$p_n = 1-\frac{\phi(n)}{n}=1-\prod_{p|n}{(1-\frac{1}{p})} = 1-(1-\frac{1}{p})(1-\frac{1}{q}) $$
$$ = 1-(1-\frac{1}{\sqrt{n}})^2 = 1-(1-\frac{1}{\sqrt{2^e}})^2 $$
Suppose there exists a factoring-algorithm which runs in polynomial time $f(e)$ which draws with replacement a number $x$ and computes $\gcd(x,n)$.
Let $X$ be the number of numbers $x$ with $1 \lt x \lt n$ and $1 \lt \gcd(x,n) \lt n$ which the algorithm
finds after $f(e)$ steps. Then by definition of the algorithm we must have
$ 1 = P(X \ge 1) $
But on the other hand we have
$$ P(X\ge 1) = 1 - P(X=0) = 1 - (1-p_n)^{f(e)}  $$
$$= 1-(1-\frac{1}{\sqrt{2^e}})^{2 \cdot f(e)} $$
The last equality is by definition of the algorithm valid for every $e$.
But for $e \rightarrow \infty$ we have
$$1 = P(X \ge 1) = 1-(1-\frac{1}{\sqrt{2^e}})^{2 \cdot f(e)} \rightarrow_{e \rightarrow \infty} 0$$
hence for $e \rightarrow \infty$ we have the contradiction $1 = 0$.

My question is, if someone has an idea how to replace the condition $p \equiv q \equiv \sqrt{n}$ with a more rigorous condition.
My second question is, how does one prove, that no (general purpose) factoring algorithm can do without a loop? Maybe using Kolmogorov complexity of the primes to be factored?

Edit:
As @D.W. pointed out the heuristic with $g_i$ is clearly wrong. What I meant to write is that we imagine that the $a_i$ are chosen with replacement from the urn $\{m,m+1,\cdots,M-1,M\}$, where
$ m = \min_i(a_i), M = \max_i(a_i)$. Let $N= M-m+1$ and $N_1 = |\{ k | m \le k \le M, \gcd(k,n)=1 \text{ or } \gcd(k,n)=n\}|$. Then the probability $p_n$ to have a non-trivial factor of $n$ is $p_n = 1 - \frac{N_1}{N}$
If $X$ counts the number of successes of the algorithm , then by definition of the algorithm we must have:
$$1 = P(X \ge 1) = 1-P(X=0) = 1-(1-p_n)^t$$
Now for this argument to be valid, one would need a number theoretic formula for $N_1$.
Also what I meant with loop is not the reading of the number $n$ but a loop for "the search for the solution".
If there is such a loop which produces the numbers $a_1,\cdots,a_t$ then there must be a criterion to stop the loop after $t$ steps.
The loop will terminate earliest when an $x$ ( a solution) such that $1<x<n$ and $1 < \gcd(n,x) < n$ is found. So in this fashion, one might see the statement, "there must exist an if-then statement such that..".

It depends on the precise model of computation you work within.  However, this doesn't seem to be a useful direction for proving lower bounds on the time to factor.

Uniform algorithms

Let's look at uniform algorithms.  Suppose our model of computation is a Turing machine or the transdichotomous model or something similar, where each step can do at most a constant amount of work (or a logarithmic amount of work).  Then any such algorithm must contain a loop or backward branch.

(Why?  Such an algorithm must work on inputs of all possible lengths.  The algorithm has finite length, say length $k$.  If there are no loops or backward branches, then this means that any execution of the algorithm must involve at most $k$ steps, where $k$ is fixed.  This means there exists $n$ large enough so that, when the input is $n$ bits long, the algorithm can't even read the entire input using $k$ steps of computation. Consequently, any such algorithm without loops cannot possibly be correct on all inputs.)

This doesn't seem useful for proving non-trivial lower bounds on the complexity of factoring.

Non-uniform algorithms

Non-uniform algorithms don't require loops.  In particular, if there is a non-uniform algorithm (possibly with loops) that takes $T(n)$ time on $n$-bit inputs, then there is a non-uniform algorithm without loops that takes $O(T(n)^2)$ time on $n$-bit inputs and has size $O(T(n)^2)$.

(Why?  Simply unroll all loops.  Since the algorithm takes $T(n)$ time, each loop will execute at most $T(n)$ times, so you can unroll it and make $T(n)$ copies.)

Other notes

Your question claims "there must be an if-then statement which tests if $1<x<n$, $x|n$ or any other mathematically equivalent test", but this claim is not justified and I don't think it is correct.  There could be algorithms that contain a loop with some other loop condition.  Also, your heuristic is clearly false.  The output of $\gcd(a_i,n)$ isn't anything like a uniformly distributed number from $\{1,\dots,n\}$.  So the direction you're taking seems like it is based on faulty premises and seems like a dead end.


Limited number of variable occurrences in 1-in-3 SAT Is there a known result on complexity class of 1-in-3-SAT with restricted number of variable occurrences?

I've come up with the following parsimonious reduction with Peter Nightingale,  but I want to cite something if this is known.

Here is the trick we came up with. This shows that 1-in-3-SAT limited to 3 occurrences per variable is NP complete and #P complete (since 1-in-3-SAT is), while 3-SAT limited to 3 occurrences is in P

Let’s say we have more than three occurrences of x.  Say we need 6. Then we will introduce 5 new variables x2 to x6 equivalent to x and two new variables d1 and d2 guaranteed to be false with the following 6 new clauses:

x  -x2 d1
x2 -x3 d1
x3 -x4 d1
x4 -x5 d2
x5 -x6 d2
x6 -x  d2

Obviously we replace each occurrence of x after the first one by xi for some i. That gives three occurrences of each xi and d.

The above sets each di to false and all the xi to the same value. To see this, x has to be true or false. If it's true then the first clause sets x2 true and d1 false, and then this propagates down the clasues. If x is false then the last clause sets x6 false and d2 false and it propagates up the clauses. It's obviously strongly parsimonious so preserves counting.

Up to my knowledge the current "limits" have been settled in:

Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer, Andreas Wotzlaw:
XSAT and NAE-SAT of linear CNF classes. Discrete Applied Mathematics 167: 1-14 (2014)

See also Schmidt's Thesis: Computational Complexity of SAT, XSAT and NAE-SAT for linear and mixed Horn CNF formulas

Theorem 29. XSAT remains NP-complete for $k$-$CNF^l_+$ and $k$-$CNF^l$, $k, l \geq 3$.

(XSAT for $3$-$CNF^3$ is exactly 1-in-3-SAT where each variable appears exactly $l=3$ times)

Note that the theorem also proves the NP-completeness of the stronger monotone case ($CNF_+$)


What is/are the lower bounds for finding a something akin to complex residue? Given a function $\sum_{i=-N}^N{c_i x^i}$:

$f(x) \equiv \sum_{i=-N}^N{c_i x^i}$ where $c_i$ is an integer; $0 \le c_i \le a$ for some $a$.

The constant $c_0$ is desired, and we start with only $f(x)$ and $N$.  $N$ is $\Theta(2^{b})$ for some $b$.

  Can you clarify?

First, we start with a closed form of a function.  The function itself is similar to a generating function, so that the function description is usually more concise than a list of all of its coefficients, yet it describes all of the coefficients.  Some examples are

$\frac{1-x^{100}}{1-x} = 1 + x + x^2 + ... + x^{99}$

$\frac{ 1 - (n+1)x^n + nx^{n+1} }{ (x-1)^2 } = 1 + 2x + 3x^2 + ... + (n+1)x^n$

The problem seems to be that this coefficient is in the middle of a list of positive and negative coefficients.  In the two examples above, the coefficient c_0 can be easily extracted.  However, this is not so when there are negative coefficients.  For example, take the functions above and divide by x^m to get a function that contains some negative coefficients.

  What is known about the general form of $f(x)$?

The function $f(x)$ is a rational function:

$f(x) = P(x)/Q(x)$

where $P(x)$ and $Q(x)$ are polynomials.

Here's a little insight into how $f(x)$ is calculated.
I use a standard rational function:

$g(x) = (x^s(x^t-1)) / ((x-1)(x^u+1))$

I then multiply $g(x)$ by $g(y)$, and $g(y)$ is of the same form of $g(x)$, but in another variable.  I then possibly subtract this from a function of one coefficients:

$h(xy) = (1-(x y)^v) / (1-x y)$

I then use another variable function similar to $g(x)$, say $g(z)$, and multiply again.  Possibly subtract again.  Repeat this until the function I want is constructed.  Then reassign variables like so (to either positive or negative exponents):

$y \mapsto \displaystyle x^{\pm 2^N}$

$z \mapsto \displaystyle (x^{\pm 2^N})*(x^{\pm 2^N})$

and so on.  This is how the function is created, without going into detail.

  How fast can this computation be performed?

So far, I've seen that Bruno Salvy's webpage hosts a "gfun" package that solves this in O(N).

I'm attempting to write a more efficient algorithm than this, so I'm hoping that it's possible to do better.  I imagine that a bounds related to the length of the function description may be possible...

So far, I've seen that Bruno Salvy's webpage hosts a "gfun" package that solves this in O(N). I'm attempting to write a more efficient algorithm than this, so I'm hoping that it's possible to do better. I imagine that a bounds related to the length of the function description may be possible...

There are different measures of polynomial sparseness in the literature and you haven't been very clear on which one you might mean. However, your optimism is likely not well founded.

Take (x-2) / x^32. It's almost maximally sparse by any reasonable measure, but the coefficients in its Laurent series grow exponentially fast. If multiplication is unit cost you can still use the binary exponentiation method to keep up with the exponential growth in sublinear time in the total degree of the series, but the example suggests that things aren't rosy. This is an area littered with hardness results for division and related problems, at least in realistic models of computation where multiplication isn't constant time.

Jacques Carette is an expert in this area, so let's hope he posts a definitive answer.


Hardness of approximating acyclic chromatic number I have some doubts on the inapproximability result for acyclic coloring presented in the paper New acyclic and star coloring algorithms with application to computing Hessians. They claim that there exist an $\epsilon>0$ such that acyclic coloring cannot be approximated within $O(n^\epsilon)$ unless $\textsf{P=NP}$. It is proved by means of a reduction from Coloring.

Given an instance $G$ of Coloring, an graph $H$ is constructed by replacing each edge $e=uv$ of $G$ by $\Delta=\Delta(G)$ parallel edges and subdividing them exactly once. The construction has the following properties. They prove that for all $p$ in $3\leq p\leq \Delta$, $\chi(G)\leq p \iff \chi_s(H)\leq p$. From this, and the result Chromatic number is NP-hard to approximate within $O(n^\epsilon)$ for some $\epsilon>0$, they conclude that Acyclic chromatic number is NP-hard to approximate within $O(n^\epsilon)$ for some $\epsilon>0$.

(In the above paragraph, $\Delta(G)$ denotes the maximum degree of $G$ ).

What type of reduction is this? I am assuming it is the basic type gap-preserving reduction presented in Vazirani's book (see quote below).

The details of the gap-preserving reduction are not clear to me. I think it is proved using a gap-preserving reduction.(Disclaimer: I don't know whether they are using some specific type of approximation preserving reduction such as L-reduction).
This is my best guess on the reduction. Clearly,
$\chi(G)\leq 3 \implies \chi_s(H)\leq 3$,
$\chi(G)>\Delta \implies \chi_s(H)>\Delta$

Let me recall definition for gap-preserving reduction from Vazirani's book here (slightly modified to fit this context).

  A gap-preserving reduction from minimization problem A to minimization problem B with parameters $f,\alpha,g,\beta$ maps an instance $x$ of A to an instance $y$ of B such that
  $\bullet\ $ the mapping is poly. time computable,
  $\bullet\ $ $OPT\leq f(x) \implies OPT\leq g(y)$, and
  $\bullet\ $ $OPT>\alpha(|x|)\  f(x) \implies OPT>\beta(|y|)\ g(y)$.

(Also for all $x$ and $y$, $\alpha(|x|)>1$ and $\beta(|y|)>1$. OPT refers to optimal value for problem A when used on left side, and problem B when used on right side.)

Here, it seems $f_A=f_B=3$ and $\alpha(|x|)=\beta(|y|)=\Delta/3$. But, here $|x|=n+m$ and $|y|=(n+\Delta m)+2\Delta m$ (where $n=$ #vertices in $G$, and $m=$ #edges in $G$). But then, functions $\alpha$ and $\beta$ cannot be defined like this!

What are the correct functions $f,g,\alpha,\beta$ implicit in the inpproximability proof of the paper?

It is not a gap-preserving reduction, but an approximation factor preserving reduction. The comment by Manuel Lafond is very close to an answer (but I cannot concur with the opinion that having same optimal values suffices; that is why I am writing this as an answer)

Quoting from Vazirani (the notation $s_1,s_2$ is mine):

  Let $\Pi_1$ and $\Pi_2$ be two minimization problems. An approximation factor preserving reduction from $\Pi_1$ to $\Pi_2$ consists of two polynomial time algorithms, $f$ and $g$, such that

  for any instance $I_1$ of $\Pi_1$, $I_2 = f(I_1)$ is an instance of $\Pi_2$ such that
  OPT$_{\Pi_2}(I_2) \leq$ OPT$_{\Pi_1}(I_1)$, and
  for any solution $s_2$ of $I_2$, $s_1= g(I_1 ,s_2)$ is a solution of $I_1$ such that
  obj$_{\Pi_1}(I_1,s_1) \leq$ obj$_{\Pi_2}(I_2,s_2)$.

Note: obj$_{\Pi_1}(I_1,s_1)$ simply means the value of the objective function for instance $I_1$ for solution $s_1$. Here, for example it is the number of colours used by a colouring($s_1$) of a graph($I_1$).

The whole point of this reduction is that $\chi(G)=\chi_a(H)$. For $3\leq p\leq \Delta$, it is proved that $\chi(G)\leq p\iff \chi_a(H)\leq p$. Also, $\chi(G)\leq \Delta+1$ and $\chi_a(H)\leq \Delta+1$ (I wonder why they didn't mention the latter non-trivial fact in the proof). The choice of exactly $\Delta$ multilpe edges in the construction of $H$ plays a big role here.

I am told in person by someone working in the area that OPT$_{\Pi_1}(I_1)=$ OPT$_{\Pi_2}(I_2)$ suffices. But, I think this is not the case. If this were true, the definition of approximation factor preserving reduction can be simplified to the simple condition OPT$_{\Pi_1}(I_1)=$ OPT$_{\Pi_2}(I_2)$. Note that the 2nd condition implies that OPT$_{\Pi_1}(I_1) \leq$ OPT$_{\Pi_2}(I_2)$. I guess there must be a reason why they used a stronger condition in the definition. (As an evidence, many other approximation related reductions also demand mapping between objective value of solutions.)


What is the Complexity Classification of Portfolio Theory in Financial Economics? As you will all know, there is ongoing fall out from the Financial Crisis of 2008. I was thinking about how complexity theory fitted into all this, when I realised I did not know the basic complexity classes relating to Financial Economics.

So my question is what is the complexity classification (if any) of Markowitz's Portfolio Theory in general and the CAPM model in particular? Also, any comments relating to how complexity theory relates to the Financial Crisis would be welcome!

The classic Markowitz model is a quadratic programming problem. I'm not sure at all about the state of current research, but one paper that might constitute a starting point is here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.9504

By the way, there's a paper that's been making the rounds on related issues: "Computational Complexity and Information Asymmetry in Financial Products" by Sanjeev Arora, Boaz Barak, Markus Brunnermeiery, and Rong Ge. The latter has posted it along with some additional comments here: http://www.cs.princeton.edu/~rongge/derivativeFAQ.html

I tend to think the results are of theoretical interest but don't explain anything that actually happened.

My suspicion is that complexity is not the main barrier in most models (generally, anything complicated gets turned into a monte-carlo eventually anyway, and generally things get complicated fast -- so yes this opens the way to certain malicious attacks, but maliciousness in the financial world can much more easily be much more crude, general, and straightforward) so much as many other, generally well known critiques of these models (sometimes from an information theory standpoint) that aren't really appropriate for this forum.


Where is the proof of universality of Rule110 in Stephen Wolfram's book? I have Stephen Wolfram's book A New Kind Of Science. And I want to find the proof of the universality of Rule 110. I couldn't find the clue in the contents page since it only shows 12 chapters and no details.

Could some one help me please? Does he show the proof in his book at all? What is the page number where he shows the proof?

I'm reading the paper by Matthew Cook for sure. It's just more pictures help me understand things better. I now know pretty well what is the tag system and the cyclic tag system, but still trying to find a way to visualize the equivalence between the tag system and the turing machine. Other resources about this are welcome, too!

Many thanks!

Found it:

cyclic tag system to tag system p.669

glider p.678

The pictures are very helpful!


Solving Linear Equations over $Z_q$ Suppose we are given a linear equation $Ax = b$, where $A \in Z_{q}^{m \times n}$ and $b \in Z_{q}^{m}$.

Note that $q$ is NOT necessarily a prime here. I wonder whether the following can be done in $poly(n, m ,q)$ time:

Check whether there exists $x \in Z_{q}^{n}$ such that $Ax = b$.
Suppose there exists $x$ such that $Ax = b$, find such $x$.

Thanks.

Yes, it is well known it can be done by diagonalizing the matrix using row and column operations. An outline of the procedure is given in the paper The Complexity of Solving Equations over Finite Groups by Goldmann and Russell.


Can a computer simulate itself as part of a simulated world? Let's say you build a computer that will calculate the state of all atoms in the Universe at certain future point in time. Because the Universe is, by definition, everything that exists (and anything that interacts with the rest), it also includes the computer that you are building. Can you calculate the state of all atoms in the Universe using your computer, including the atoms of the computer itself?

If such a computer is not possible for some other theoretical or practical reason, then what is it?

No, a computer cannot perfectly simulate itself in addition to something else without violating basic information theory: there exist strings which are not compressible.

Here's the simplest possible proof: suppose the computer has a total of $N$ possible states, and suppose there is something outside of the computer in the universe, so the universe has at least $N+1$ possible distinct states.  With zero overhead, each state of the computer can correspond to a state of the universe, but since the universe has more states than the computer, some states of the universe will map to the same state of the computer, in which case the simulation will not be able to distinguish between them.


When we say a parameter is good for a problem? I am studying parameterized complexity. I have seen few parameterized algorithm for problems like vertex cover, feedback vertex set etc. I have difficulty in determining when a parameter is said to be a " good parameter ". My definition of good parameter is not clear although, but it simply means if I can come up with an FPT algorithm for that problem using that parameter then it will solve some non-trivial set of instances.

For an example:  If we talk about the parameterization of some graph problem using independent set (I) and vertex cover (V) and some how we get an FPT algorithm of type $g(k)^{f(I)}\text{Poly}(n)$. Will it a good parameterization of the problem.

  Question : When we say a parameter is good for a problem? I can define many parameters for a problem, but the question here is to how to decide it is a good parameter.

In my opinion, this is actually one of the main questions in parameterized algorithms. There is a number of articles that discuss the "art" of problem parameterization, I list a few of them below.

In a nutshell, an ideal parameter $k$ for a problem should give you two things:

The problem is fixed-parameter tracable for parameter $k$ with a good running time dependence on $k$. That is, it can be solved in $f(k)\cdot n^{O(1)}$ time for some moderately exponential function $f$.
The value of $k$ is small in typical instances of this problem.

Most of research in parameterized algorithms focuses on the first issue. The second issue is not really treated in a systematic empirical fashion I'd say. That is, there are no comprehensive studies measuring the value of parameters in real-world instances. What people do to justify the study of particular parameters is to systematically compare parameter values. For example, one may say that a fixed-parameter algorithm for a parameter $k$ is more useful than a fixed-parameter algorithm for parameter $\ell$ if $\ell>k$ in many instances and $\ell\ge k$ in all instances. Using these relations between parameter values one may navigate through parameter space to obtain useful fixed-parameter algorithms.

For example, if you have shown that a graph problem with input graph $G$ is fixed-parameter tractable for the parameter vertex cover number $\mathrm{vc}(G)$ you may want to show that it is fixed-parameter tractable for the parameter feedback vertex set number $\mathrm{fvs}(G)$ because  $\mathrm{fvs}(G)\le \mathrm{vc}(G)$ in all graphs. If this is the case, then you may want to show that the problem is fixed-parameter tractable for the treewidth $\mathrm{tw}(G)$ of the graph since $\mathrm{tw}(G)\le \mathrm{fvs}(G)+1$ in all graphs and so on.

Some references:

Michael R. Fellows, Bart M. P. Jansen, Frances A. Rosamond:
Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3): 541-566 (2013)
Rolf Niedermeier:
Reflections on Multivariate Algorithmics and Problem Parameterization. STACS 2010: 17-32
Christian Komusiewicz, Rolf Niedermeier:
New Races in Parameterized Algorithmics. MFCS 2012: 19-30


How can I obtain famous articles which are not available online? I have Googled myself to death, but have been unable to find the following articles:

Breen, E., Monro, D., 1994. An evaluation of priority queues for
mathematical morphology.
R. Beare and H. Talbot., 1999 Exact seeded region growing for image
segmentation.

These articles are well known, important and often cited by others, but they seem to be impossible to find. Does anyone know where I could find these or maybe someone could point me in the right direction?

More generally,

  What should I do when I cannot find an online copy of an article?

It seems that:

The first paper was published in Mathematical Morphology and Its Applications to Image Processing, J. Serra and P. Soille (Eds.), Kluwer 1994, ISBN 0-7923-3093-5 (a.k.a. Proc. 2nd International Symposium on Mathematical Morphology, ISMM 1994). Amazon link.
The second paper was published in Proc. DICTA 1999. Worldcat knows about the book. It seems that there are at least two Australian libraries that have it in their collections, so it should be possible to order copies of articles from them.

Fairly often, the interlibrary services of university libraries can provide copies of papers published in hard-to-find books and journals.

As Peter Shor suggested in comments, you can also try to contact the authors. Usually, authors will be happy to send you copies of their articles – after all, researchers write papers in order to make their results as widely known as possible.


Help on the following combinatorial problem? I have $m$ bit vectors, each of which is composed by $m$ bits. Let's denote with $v_i[j]$ the $j$-th bit of the $i$-th vector, $i,j \in [1, m]$. Each bit vector $v_i$ is subject to the following 2 restrictions:

$v_i[j] = 0\ \forall j \geq i$.
$v_i[j] = 1\ \forall j < i - \frac{m}{log(m)}$.
Those bits that do not fall in the restrictions above can be either $0$ or $1$, but in such case the number of $0$'s can be at most $12$.

Now I have another bit vector $s$, of $m$ bits: initially all the $m$ bits of $s$ are set to $1$. By "applying $v_i$ to $s$" I mean performing a bitwise AND between $s$ and $v_i$, and then storing the result in $s$. I'm interested in the evolution of $s$ after repeated applications of the vectors $v_1, ..., v_m$ given in input.

Let's call those "repeated applications" a trajectory, and let's define such trajectory more formally. A trajectory is a sequence composed by at most $m$ vectors (selected from those $v_1, ..., v_m$ given in input) such that if $v_i$ is in the sequence, then all the $v_j$ after it must have $j < i$. So, for example, $<v_8, v_3>$ is a trajectory, while $<v_3, v_8, v_7>$ is not (because $8\geq3$).

Clearly, there are $2^m$ different trajectories. Let $S=\emptyset$. Suppose to take $s = 1^m$ and to let it undergo a trajectory $T_1$: for each step of the trajectory $T_1$, put the new value taken by $s$ in $S$. Then repeat the same process for another trajectory $T_2$ (always starting from $s=1^m$, and always putting every new value of $s$ in $S$). Then again, until you tried all the possible $2^m$ trajectories. At the end, the set $S$ will contain all the possible values that $s$ may ever assume given the vectors in input.

  Questions

  I have $v_i, ..., v_m$ in input. I want to know $|S|$, i.e. how many distinct values may $s$ ever assume. Of course, I want to compute $|S|$ efficiently, i.e. without trying all the possible trajectories one by one.
  Suppose to remove the 2nd restriction on the vectors in input. How doing so affects $|S|$?
  More importantly, what I most care about is how $|S|$ grows with $m$. Is $|S|$ at most polynomial in $m$? Is $|S|$ at most sub-exponential in $m$? Or do there exist bad instances on which $|S|$ is necessarily exponential in $m$?

The following figure is an example with $m=17$:

I'm collecting experimental data in order to try to figure out which is the relationship between $m$ and $|S|$. So far, experiments seems to suggest that $|S|$ grows faster than $m^3$ and slower than $m^4$. However, for the moment those data have not much significance: I was only able to make tests up to $m = 90$, so there may be a big hidden constant or some other factor that lets an exponential law look like a polynomial law for small $m$. I need help in figuring out the asymptotic behaviour of $|S|$ with respect to $m$.

I've rethought this and my initial bound was correct. In the worst case, $|S| = \Theta(m \; 2^\frac{m}{\lg m})$

Proof is in two parts. Firstly, $|S| = O(m \; 2^\frac{m}{\lg m})$. Consider the possible values of $s$ of a trajectory which ends at $v_x$. Every bit $s[j]$ for $j \ge x$ is 0, and every bit $s[j]$ for $j < x - \frac{m}{\lg m}$ is 1. Therefore there are only $2^\frac{m}{\lg m}$ values which $s$ can take. Multiply up by the number of $v_x$ and we have the upper bound.

Secondly, consider

    0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
    0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
    0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1
    0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1
    0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1
    0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1
    ...
    0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

I assert that this scheme gives you $|S| = \Omega(m \; 2^\frac{m}{\lg m})$. For each column $v_x$ consider also the $(\frac{m}{\lg m}-2)$ columns to its right. Each of the $2^{\frac{m}{\lg m}-2}$ combinations of them gives a different $s$, and in each of those $s$ the top set bit is the top set bit of $v_x$, so there is no double-counting between different $v_x$.


Minimum Flip Connectivity Problem I formulated the following problem today while playing with my GPS. Here it is :

Let $G(V,E)$ be a directed graph such that if $e=(u,v) \in E$ then $(v,u) \notin E$, i.e., $G$ is an orientation of the underlying undirected graph. Consider the following operations :

$Flip(u,v)$ : Replace an edge $(u,v)$ with an edge $(v,u)$
$undirect(u,v)$ : Make the edge $(u,v)$ undirected

Let $s,t \in V$ be two special vertices. Consider the following optimization problems :

Min-Flip st-connectivity : Given $G$ and two vertices $s,t$ find the minimum number of edges that need to be flipped to make a directed path from $s$ to $t$.
Min-Flip strong-connectivity : Given $G$ find the minimum number of edges that need to be flipped to make $G$ strongly connected. If it is not possible to make $G$ strongly connected by flipping edges then output NO.
Min-undirect strong-connectivity : Given $G$ find the minimum number of edges that need to be undirected to make $G$ strongly connected.

Note that you are not allowed to add "new" edges. You are only modifying the existing edges using the above operations. Is this problem known in the literature. If so what are the known results ?

This is an answer for the first problem:
Consider a new weighted graph $G'=(V,E')$, where $E'=\{(u,v,0)|(u,v) \in E\} \cup \{(v,u,1)|(u,v)\in E \}$ (weights of all edges that are in $G$ are 0, and weights of 'reversed' edges are 1). Now You just have to find the shortest path from $s$ to $t$.


Is a monotone boolean function monotone as a multilinear polynomial? Let $f:\{-1,1\}^n \rightarrow \{0,1\}$ be a monotonically increasing boolean function. That is, $f(x) \leq f(y)$, if coordinate-wise $x \leq y$. Now, let $F: [-1,1]^n \rightarrow \mathbb{R}$ be $f$ expressed as a multilinear polynomial (i.e. $F$'s Fourier transform). Is $F$ still a monotonically increasing function?

Yes.

  Let $f : \{-1,1\}^n \to \mathbb{R}$, and let $F : [-1,1]^n \to \mathbb{R}$ be its multilinear extension. If $f$ is monotone, then so is $F$.

proof: Fix a variable index $i$; we'll show that $\frac{\partial F}{\partial x_i} \ge 0$ at all $x \in [-1,1]^n$. If this holds for all $i$, we're done. Since $F$ is multilinear, we can write this partial derivative as $\frac{1}{2}\left( F\restriction_{x_i=1} - F\restriction_{x_i = -1} \right)$, where $F\restriction_{x_i = a}$ means we assign $a$ to $x_i$ and leave the remaining variables free. So it suffices to show that $F\restriction_{x_i = 1} \ge F\restriction_{x_i = -1}$ for all $x\in [-1,1]^n$. Since $f\restriction_{x_i = 1} \ge f\restriction_{x_i = -1}$ on $\{-1,1\}^n$, and since $F\restriction_{x_i=a}$ is the multilinear extension of $f\restriction_{x_i=a}$, this reduces to the following claim:

  Let $f,g : \{-1,1\}^n \to \mathbb{R}$ be functions, and $F,G : [-1,1]^n \to \mathbb{R}$ their respective multilinear extensions. If $f \ge g$ point-wise, then $F \ge G$ point-wise as well.

proof: Recall that if $M$ is a multilinear function, then we can write
$$M(a) = \sum_{x \in \{\pm 1\}^n} M(x) \prod_{i=1}^n \left\{\begin{array}{rcl}\frac{1+a_i}{2} &:& x_i = 1\\ \frac{1-a_i}{2} &:& x_i = -1\end{array}\right.$$
From this formula, it directly follows that if $M(x) \ge 0$ for all $x \in \{-1, 1\}^n$, then $M(a) \ge 0$ for all $a \in [-1,1]^n$. The claim then follows by applying this fact to $M = F - G$, since for $x \in \{-1,1\}^n, (F - G)(x) = (f - g)(x) \ge 0$.


Secretary hiring game This is an extension of the classical secretary problem.
In the hiring game you have a set of candidates $\mathcal C=\{c_1,\ldots,c_N\}$, and order on how skilled each worker is.
W.l.o.g, we assume that $c_1$ is the most skilled, followed by $c_2$, etc.
The order in which the candidates interview is picked uniformly at random and it is (obviously) unknown to the employers.
Now suppose you have a market with 2 potential employers. In every round, a new candidate is interviewing for both companies (call them $A,B$). During the interview, both $A$ and $B$ observe the partial ordering of all of the past candidates, including the current interviewee.
The firms then (independently) decide whether to hire today's applicant.
Unfortunately for $B$, it can not compete financially with $A$'s offer, so if both extends an offer for a worker, $A$ gets preference.
Also, once a secretary signs, the company may not interview any further candidates and the competitor becomes aware of the  signing.
The goal of each company is to hire the better skilled candidate (as opposed to the classic problem, where a single company wishes to find the best secretary), as it is known that the company with the better secretary should be able to take over the market.

What is the optimal strategy as the big firm ($A$)?
What about the smaller company ($B$)?
If both companies play their equilibrium strategies, what is the probability $B$ gets the better worker?

In a related work, Kalai et al. discusses the symmetric version of this problem, where both companies have the same power of attracting candidates.
In this setting, the simple (symmetric) equilibrium is that you hire a secretary iff the chance of she being better than the remaining candidates is at least 50%.

How does this result changes in our setting?

For company $A$/the firm/giant corporation/"big pharma"/"THE MAN", the strategy does not change from the symmetric version:

Consider a round where the probability of seeing only lesser candidates thereafter is $> .5$.  If company $A$ keeps the candidate, then it has a chance of winning $> .5$.  If $A$ does not keep the candidate, then company $B$ can hire the candidate and company $A$ has a chance of winning $< .5$.  So, obviously, company $A$ would hire (and company $B$ would attempt to hire) in this situation.

For a candidate with winning odds of exactly $.5$, $A$ may or may not choose to hire, but $B$ would choose to hire because $B$ can never get odds better than $.5$.

If company $A$ hired before it saw a candidate with winning chance $>= .5$, then the odds of a better future candidate existing (and hence $B$ winning) would be $> .5$.  So $A$ will not hire until it sees a candidate of winning odds $>= .5$.

Therefore, $A$'s strategy is identical to the symmetric case: hire the first candidate that yields winning odds of $> .5$.

$B$'s strategy, then, is formed with $A$'s strategy in mind.  Obviously, if $A$ hires (at or) before $B$, then $B$'s strategy is to hire the next candidate that is better than $A$'s, if any.  Also, if a candidate comes by with winning odds $> .5$, $B$ should try to hire, even though $A$ will also try to hire (and force $B$ to keep looking).

The only question left is: is it ever beneficial for $B$ to hire when the odds of winning is $<= .5$.  The answer is: yes.

Intuitively, say there is a round where the odds of winning with the candidate is $.5 - \epsilon$.  Also, there is "likely to be" (explained later) a future candidate with winning odds $> .5 + \epsilon$.  Then it would benefit $B$ to choose the earlier candidate.

Let $d_r$ be the candidate interviewing in round $r$ for all $1 <= r <= N$.

Officially, $B$'s strategy is: "hire $d_r$ if doing so yields better odds of winning than if not".  The following is how we calculate such a decision.

Let $p_{r,i}$ be the probability of winning after interviewing and hiring $d_r$ given $d_r$ is the $i$th best interviewed candidate.  Then:

$p_{r,i} = $ probability that $d_s < d_r$ for $s > r$

$ = (1-\frac{i}{r+1})(1-\frac{i}{r+2})\times ... \times (1-\frac{i}{N})$

...

$ = \frac{(N-i)!r!}{(r-i)!N!}$

Notably, $p_{r,i}$ is easily computable to constant accuracy.

Let $P_{B,r}$ be the probability that $B$ wins given that neither company hired in rounds $1$ through $r-1$.

Then $B$ would hire $d_r$ if the probability of winning after hiring $d_r$ is better than $P_{B,r+1}$.

Note that $P_{B,N} = 0$, because if it is the last round, then $A$ is guaranteed to hire and $B$ will not hire anyone and loose.

Then, in round $N-1$, $B$ is guaranteed to try to hire and will succeed unless $A$ hires as well.  So:
$$
P_{B,N-1} = \sum_{i=1}^{N-1}\frac{1}{N-1}
\left\{
\begin{array}{lcl}
p_{N-1,i}   & : & p_{N-1,i} < .5 \\
1-p_{N-1,i} & : & p_{N-1,i} >= .5
\end{array}
\right.
$$

Which leads to the recursive function:

$$
P_{B,r} = \sum_{i=1}^{r}\frac{1}{r}
\left\{
\begin{array}{lcl}
1-p_{r,i} & : & p_{r,i} >= .5 \\
p_{r,i}   & : & P_{B,r+1} < p_{r,i} < .5 \\
P_{B,r+1} & : & \text{else}
\end{array}
\right.
$$

It's pretty obvious that $P_{B,r}$ can be calculated to constant accuracy in polynomial time.  The final question is: "what is the probability of $B$ winning?"  The answer is $P_{B,1}$ and varies with $N$.

As to the question of how often does $B$ win?  I have not calculated exactly, but looking at $N$ from 1 to 100, it appears that as $N$ grows, that $B$'s winning rate approaches .4 or so.  This result may be off as I just did a quick python script to check and did not pay close attention to rounding errors with floating numbers.  It may very well end up that the real hard limit is .5.


Survey on Optimization algorithms I am trying to solve an optimization problem. I need some help in getting the results or survey on related issues. The question is a bit general but any help in identifying the correct sources would help.

Are their any good survey work/tutorial/book that could provide information on the known algorithms and complexity results for $L_{0}$, $L_{1}$, $L_{2}$ optimization and also the relation among them for both sparse and general solutions?

You will find lots of links in Steve Wright's plenary talk at the SIAM Optimization 2011 conference: http://pages.cs.wisc.edu/~swright/talks/sjw-siopt11.pdf

At the same conference, Michael Friedlander gave a tutorial with many references and pointers to applications and software: http://www.cs.ubc.ca/~mpf/papers/mpf-tutorial-siopt11.pdf

The video lectures on compressive sensing given by Emmanuel Candes at Cambridge are also a great way to get into the subject: http://www.sms.cam.ac.uk/collection/1117766


Generalization of the Hungarian algorithm to general undirected graphs? The Hungarian algorithm is a combinatorial optimization algorithm which solves the maximum weight bipartite matching problem in polynomial time and anticipated the later development of the important primal-dual method. The algorithm was developed and published by Harold Kuhn in 1955, who gave the name "Hungarian algorithm" because the algorithm was based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry. Munkres reviewed the algorithm in 1957 and observed that it is indeed polytime. Since then the algorithm is also known as Kuhn-Munkres algorithm.

Although the Hungarian contains the basic idea of the primal-dual method, it solves the maximum weight bipartite matching problem directly without using any linear programming (LP) machinery.
Thus, in answer of the following question, Jukka Suomela commented

  Of course you can solve any LP by using a general-purpose LP solver, but specialised algorithms typically have a much better performance. [...] You can also often avoid issues like using exact rational numbers vs. floating point numbers; everything can be done easily with integers.

In other words, you don't have to worry about how to round a rational/floating point solution from the LP solver to get back a maximum weight perfect matching of a given bipartite graph.

My question is the following:

  Is there a generalization of the Hungarian algorithm that works for general undirected graph without the use of LP machinery similarly to the spirit of the original Hungarian algorithm?

I would prefer modern and easy-to-read exposition instead of some original complicated paper. But any pointer will be very appreciated!

Many thanks in advance and Merry Christmas!!!

Update: The question is nicely answered by Arman below. I just want to point out that another nice source to study the Edmonds's Blossom Algorithm (for the  weighted case) is Chapter 11 of  Combinatorial Optimization by Korte and Vygen. Google book actually  shows nearly all the parts I need to understand the algorithm.

Edmonds's matching algorithm (also called Blossom Algorithm) solves the maximum matching on general graphs. Actually it is a generalization of alternating paths method. (I am not sure of the name of the method but it shoud be König-Hall method.) It basically finds augmenting paths (see wikipedia page: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm) to extend the current matching and stops if there is no more augmenting paths. In general graphs, the only problem occurs in odd cycles. In the Edmonds's matching algorithm odd cycles are contracted (blossoms) and expended back to have a solution.

There is also a correspondence between Blossom Algorithm and Primal Dual method.
Odd cycles cause fractional extreme points. Therefore we add so called blossom inequalities for each odd cycle.

Minimum weighted perfect matching and maximum weight matching problems could also be handled with this approach.

For details of the algorithm, see
http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm
http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf

For mathematical formulation and the corresponding primal-dual method, see
http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf


Why valuations when defining FOL? Why does one need valuations in order to define the semantics of first-order logic? Why not just define it for sentences and also define formula substitutions (in he expected way). That should be enough:

$$M \models \forall x. \phi \iff \text{for all }d\in \mathrm{dom}(M),\ M \models \phi[x\mapsto d]$$

instead of

$$M,v \models \forall x. \phi \iff \text{for all }d\in \mathrm{dom}(M),\ M, v[x\mapsto d] \models \phi$$

It is perfectly possible to define satisfaction using just sentences as you suggest, and in fact, it used to be the standard approach for quite some time.

The drawback of this method is that it requires to mix semantic objects into syntax: in order to make an inductive definition of satisfaction of sentences in a model $M$, it is not sufficient to define it for sentences of the original language of $M$. You need to first expand the language with individual constants for all elements of the domain of $M$, and then you can define satisfaction for sentences in the expanded language. This is, I believe, the main reason why this approach went into disuse; if you use valuations, you can maintain a clear conceptual distinction between syntactic formulas of the original language and semantic entities that are used to model them.


Hook length formuli and their invariance properties? Let $P = (V,\leq_P)$ be a poset, and for each $x \in V$ let $x^P = \{ y \in V : x \leq_P y \}$. A well-known property of certain posets (forests, Young diagrams) is the existence of a simple hook length formula counting their linear extensions - while the problem is $\# P$-hard in general. To make this notion precise, we say that $P$ has a hook length formula if there exists a function $h : V \rightarrow \mathbb{N}$ such that for every $x \in V$, the number of extensions of $P | x^P$ is equal to:

  L(x) = $\frac{|x^P|!}{\prod_{y \geq_P x} h(y)}$.

It can be seen that this property is preserved by some natural operations: parallel composition, adjonction of a minimal or maximal element. This immediately implies the Knuth hook formula for forests, although it has a number of different proofs (including some of algorithmic nature).

I'd like to know if there are examples of other operations preserving/breaking the existence of a hook length formula, in particular is it possible to define a gluing operation extending the above adjonction operation?

Consider two posets $P,Q$ and an element $x \in V(P)$. Let $Pe(x)$ denote the immediate predecessors of $x$ and let $Su(x)$ denote the immediate successors of $x$ in $P$. Let $Min_Q,Max_Q$ denote the minimal, resp. maximal, elements of $Q$. Fix two mappings $Conn_1 : Pe(x) \rightarrow Min_Q$ and $Conn_2 : Su(x) \rightarrow Max_Q$. It is then possible to define a poset $R$ by starting with $(P - x) \uplus Q$ and by adding an arc $(w,Conn_1(w))$ for each $w \in Pe(x)$, and an arc $(w,Conn_2(w))$ for each $w \in Su(x)$.

This operation has a simple meaning for trees: given a tree $T$, you pick a node $u$, and you substitute it by a tree $T'$ by attaching the leaves of $T'$ to the children of $u$ in an injective manner. This means that the trees are closed under this operation of substitution, and thus we could expect that it preserves the property you're interested in. I admit though that I have no idea of what I'm doing with this defn, this might be a joke so please check on your side :)