Integer roots of a polynomial What algorithm can we use to find all integer roots of a polynomial $f(x)$ with integer coefficients?

I observe that Sage can find the roots within a few seconds even when all coefficients of $f(x)$ are very large.  How is it able to do that?

Assuming that the coefficients of $f$ are integers or rationals and that you want integer roots, the simplest approach is to use the integer or rational root theorem. See http://en.wikipedia.org/wiki/Rational_root_theorem
As noted by D.W., this might be problematic if the constant coefficient is hard to factor (see also https://math.stackexchange.com/questions/123018/polynomial-and-integer-roots)

In any case, the Sage documentation clearly explains how they are doing the root search: "The next method, which is used if K is an integral domain, is to attempt to factor the polynomial. If this succeeds, then for every degree-one factor a*x+b, we add -b/a as a root (as long as this quotient is actually in the desired ring)."
See http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html.

So your question becomes How do they efficiently factor polynomials with integer coefficients ?  Apparently, Sage is calling NTL to do that (see http://www.shoup.net/ntl/doc/ZZXFactoring.txt for NTL details).

If you want an asymptotically efficient method, you could refer to the method of Lenstra, Lenstra and Lovasz (https://openaccess.leidenuniv.nl/handle/1887/3810).


Good seating arrangements for sequence of meals and tables of size k for a group of people Given a set $S$ of people I'd like to sit them for a sequence of meals at tables of size $k$. (Of course, there are enough tables to sit all $|S|$ for each meal.) I'd like to arrange this such that nobody shares a table with the same person twice. Typical values are $|S|=45$ and $k=5$ and 6 to 10 meals.

Put in a more abstract way, I'd like to find a sequence of partitions of $S$ such that each partition consists of pairwise disjoint subsets of cardinality $k$ and the added global property that any intersection between two such subsets contains no more than one element. I suspect this can be formulated as a graph theoretical or combinatorical problem.

I'd be grateful for a better formulation of the problem and pointers to relevant literature as it is outside of my domain.

The background: this could be used for seating arrangements at Schloss Dagstuhl where many computer scientists come to discuss their research over the course of a week. Currently seating is done randomly and unsurprisingly some people find themselves sitting with the same people twice (or more often) over the course of a week. Also unsurprisingly, we receive some complaints about this and vague suggestions how to improve this. I'd like to understand this better. A stronger formulation of the problem involves optimizing who is sitting next to each other but I believe this is not relevant for tables of size 5.

Outside of the application I think the interesting question is for the maximum number of meals that can be served for a given $S$ and $k$, i.e., how many such partitions exist.

Here's a variant of the original answer (below) that gives the desired setting: tables of size 5, 45 people, and 10 meals, except that one meal has a few tables of size 4.

Let $F$ be the field of size 9.  Pick 4 vertical, degenerate lines  $\{(b,x) | x \in F\}$ for every $b = 0,1,2,3$ and declare their people "empty."  We are left with 81 - 9x4 = 45 people.

9 meals are given by slopes $a = 0,1,\ldots,8$.  The intersections with the 4 empty degenerate lines reduce the table size to 9-4=5.

An additional meal is given by the remaining degenerate lines $\{(b,x) | x \in F\}$ for every $b = 4,5,6,7,8$.  Here the table size is 9.  However (in any solution) we can break a table of size 9 into a table of size 5 and one of size 4.

If there are a few more people one can use the field of size 11.

First let us handle $k^2$ people and $k$ meals.

Pick a finite field $F$ of size $k$ and identify people with $F \times F$.  To each meal there corresponds a slope, to a table a line parallel to that slope.

Specifically, meal $a$ has $k$ tables $\{(x,ax+b) | x \in F\}$ for every $b \in F$.

The intersection property you want is the fact that lines with distinct slopes intersect in exactly one point.

To handle $2k^2$ people, divide them up in two groups of $k^2$ each, and apply the construction above to each group.  To handle $2k^2 - k = 45$, label (in the first group) a fixed line such as $\{(x,x)|x\in F\}$ as "empty."  You may have a few tables with $k-1$ people.

For more meals one could e.g. pick a different partition in two groups at the beginning of the 6th meal. (Say you interleave the original partition, to ensure that the two groups "mix.") Though of course this may result in some intersections.


Agnostic PAC sampling lower bound It is well-known that for classical PAC learning, $\Omega(d/\varepsilon)$ examples are necessary in order to acheive an error bound of $\varepsilon$ w.h.p., where $d$ is the VC-dimension of the concept class.

Is it known that $\Omega(d/\varepsilon^2)$ examples are needed in the agnostic case?

I now realize that a lower bound has indeed been established by Anthony and Bartlett (see the presentation here).

Edit 24-Sep-2018. This question has kept me occupied all of these years, and recently, I. Pinelis and I have obtained the exact optimal constant in the agnostic PAC lower bound to appear in Ann. Stat.


Fast Algorithm to Check if a Set of Sets forms an Anti-chain Given a set $S$ of sets, what is the fastest algorithm to check if elements of $S$ form an anti-chain with respect to subset ordering? That is, how can I quickly decide if there exists two sets $A$ and $B$ in $S$ such that $A \subseteq B$?

This problem is SETH-hard at time $n^2$ (Williams 04). There is is no $n^{2-\epsilon}$ algorithm for any $\epsilon > 0$ if the universe has size $\omega(\log n)$.

For small universe size ($c \log n$ for some $c$), there is an algorithm with time $n^{2-1/O(\log c)}$ (Abboud, Williams, Yu 15)


Are space and time hierarchies even comparable? I am wondering if there are any results to what extent the space and time hierarchies "disagree" on which problem is harder. For example, is it known whether there are languages $L_1$ and $L_2$ such that $L_1 \in \DeclareMathOperator{TIME}{TIME} \TIME(f(n))\setminus SPACE(g(n)),L_2\in \DeclareMathOperator{SPACE}{SPACE} \SPACE(g(n)) \setminus \TIME(f(n))$? How often does this occur?

P.S.- The question Function with space-depending computation time seems to ask something similar but was worded confusingly and none of the answers seem to be what I'm looking for.

You can get the situation you describe by choosing weird functions $f(n)$ and $g(n)$.

For example, let $g(n) = n^3$ and $$f(n) = \begin{cases}
 n & \text{if $n$ is odd},
\\\
 2^{n^5} & \text{if $n$ is even}.
\end{cases}
$$

Then choose $L_1$ and $L_2$ as follows:

$L_1$ is a language containing only strings of even length which can be decided in time $O(2^{n^5})$ but not in time $O(2^{n^4})$. The existence of such a language is pretty easy to prove from the time hierarchy theorem.

$L_2$ is a language containing only strings of odd length which can be decided in space $O(n^3)$ but not in space $O(n^2)$. The existence of such a language is pretty easy to prove from the space hierarchy theorem.

Then we have the following facts:

$L_1 \in TIME(f(n))$:

To decide whether a string is in $L_1$, simply check whether the length $n$ is even. If it is, then continue to use the $O(2^{n^5})$ time decider for $L_1$ whose existence is guaranteed by the definition of $L_1$. If $n$ is odd, immediately reject since $L_1$ does not include any odd length strings anyway. This procedure decides $L_1$, runs in time $O(n)$ when $n$ is odd, and runs in time $O(2^{n^5})$ when $n$ is even. In other words, this procedure decides $L_1$ in time $O(f(n))$. As desired, $L_1 \in TIME(f(n))$.

$L_2 \in SPACE(g(n))$:

By the definition of $L_2$, $L_2$ can be decided in space $O(n^3)$. Thus, $L_2 \in SPACE(n^3) = SPACE(g(n))$, as desired.

$L_1 \not\in SPACE(g(n))$:

Suppose for the sake of contradiction that $L_1 \in SPACE(g(n)) = SPACE(n^3)$. We know that $SPACE(n^3) \subseteq TIME(2^{O(n^3)}) \subsetneq TIME(2^{n^4})$. Thus, there exists a decider for $L_1$ which runs in time $O(2^{n^4})$. This directly contradicts the definition of $L_1$. Then by contradiction, we see that $L_1 \not\in SPACE(g(n))$.

$L_2 \not\in TIME(f(n))$:

Suppose for the sake of contradiction that $L_2 \in TIME(f(n))$. This means that there exists a constant $c$ and an algorithm $A$ deciding $L_2$ such that on any input of size $n$, algorithm $A$ terminates in time $c\times f(n)$.

We construct a new algorithm $A'$ as follows: given some input, walk through the entire input, keeping track of whether the input length is even or odd; if at the end of the input the length is determined to be odd, return to the start of the input and run $A$; otherwise, reject. For any input of odd length, $A'$ returns the same answer as $A$. For any input of even length, $A'$ rejects, which matches the expected behavior since $L_2$ contains no even length strings. Thus, $A'$ also decides $L_2$. On even length inputs, $A'$ runs for exactly $n$ steps. On odd length inputs, $A'$ runs for exactly $2n$ steps more than $A$ requires. But $A$ requires at most $c\times f(n)$ steps, which for odd $n$ is $cn$. Thus, in all cases, $A'$ runs in at most $(c+2)n$ steps. In other words, algorithm $A'$ decides $L_2$ in time $O(n)$.

But since $TIME(n) \subseteq SPACE(n)$, we can conclude that $L_2 \in SPACE(n) \subsetneq SPACE(n^2)$. This contradicts the definition of $L_2$. Thus, by contradiction we see that $L_2 \not\in TIME(f(n))$.


Is Descriptive Complexity dead? I recently started reading about Descriptive Complexity, the branch of Complexity Theory studying the logic languages needed to express complexity classes. The main milestone in the area seems to be Neil Immerman's book, but this is already quite old. Seems like this line of research is dead. Is this the case? If so, why?

I also have the impression that Descriptive Complexity is a less active area of research nowadays. Nevertheless, there are some topics in which people are still active:

Rank logics:

Rank Logic is Dead, Long Live Rank Logic! by Grädel and Pakusa
Symmetric Circuits for Rank Logic by Dawar and Wilsenach
Separating Rank Logic from Polynomial Time
by Lichter

Choiceless Polynomial Time:

Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time by Lichter and Schweitzer
Choiceless Logarithmic Space by Grädel and Schalthöfer

Dynamic Complexity:

Dynamic Complexity of Parity Exists Queries by Vortmeier and Zeume
Reachability Is in DynFO by Datta, Kulkarni, Mukherjee, Schwentick and Zeume
PHD thesis of Thomas Zeume

Other interesting things:

Descriptive Complexity for Counting Complexity Classes by Arenas Muñoz and Riveros
Descriptive complexity of real computation and probabilistic independence logic by Hannula, Kontinen, Van den Bussche and Virtema
Descriptive Complexity of Deterministic Polylogarithmic Time by Ferrarotti et al
On the Power of Symmetric Linear Programs by Atserias, Dawar and Ochremiak
Traversal-invariant characterizations of logarithmic space by Bhaskar, Lindell and Weinstein

The list is not supposed to be complete. Just giving you a glimpse on what kind of problems are people looking at.


Optimal randomized comparison sorting So we all know the comparison-tree lower bound of $\lceil\log_2 n!\rceil$ on the worst-case number of comparisons made by a (deterministic) comparison sorting algorithm. It does not apply to randomized comparison sorting (if we measure the expected comparisons for the worst case input). For instance, for $n=4$, the deterministic lower bound is five comparisons, but a randomized algorithm (randomly permute the input and then apply merge sort) does better, having $4\frac{2}{3}$ comparisons in expectation for all inputs.

The $\log_2 n!$ bound without the ceilings does still apply in the randomized case, by an information-theoretic argument, and it can be slightly tightened to
$$k+\frac{2(n!-2^k)}{n!} \text{, where } k=\lfloor\log_2 n!\rfloor.$$
This follows because there is an optimal algorithm that randomly permutes the input and then applies a (deterministic) decision tree, and the best decision tree (if it exists) is one in which all leaves are in two consecutive levels.

What if anything is known about upper bounds for this problem? For all $n>2$, the randomized number of comparisons (in expectation, for the worst-case input, for the best possible algorithm) is always strictly better than the best deterministic algorithm (essentially, because $n!$ is never a power of two). But how much better?

Since your question is: "What is known?" Here's something:

http://arxiv.org/abs/1307.3033

This gives an average case analysis of the Ford-Johnson Algorithm. The expected number of comparisons is $\log n! +cn$ for a surprisingly small constant $c$ (about .05).


Is the Mendler-encoding in System-F adequate? In the paper "Efficiency of Lambda-Encodings in Total Type Theory" it is mentioned that the Church-encoding is adequate and the Parigot encoding is not adequate. This means that any inhabitant of an encoded datatype actually represents an element of the datatype.
My question is if the Mendler-style encoding is adequate. I think I found a counter example (in System F):
-- Mendler-style encoding
Alg f t = forall r. (r -> t) -> f r -> t
Fix f = forall t. Alg f t -> t

-- Natural numbers
NatF r = forall t. t -> (r -> t) -> t
Nat = Fix Nat

-- the valid constructors for natural numbers
Z : Nat = /\t. \alg. alg [Nat] (\y. y [t] alg) (/\t. \z s. z)
S : Nat -> Nat = \n. /\t. \alg. alg [Nat] (\y. y [t] alg) (/\t. \z s. s n)

-- An inhabitant of Nat that is not a valid natural number
wrong : Nat =
  /\t. \alg.
    alg [forall t. t -> t]
    (\x. alg [t] (\y. y) (/\t. \z s. z))
    (/\t. \z s. s (/\t. \x. x))

$\newcommand{\Alg}{\mathsf{Alg}\ }$
$\newcommand{\NatF}{\mathsf{NatF}\ }$
$\newcommand{\Nat}{\mathsf{Nat}}$
$\newcommand{\map}{\mathrm{map}\ }$
$\newcommand{\Z}{\mathrm{Z}}$
$\newcommand{\S}{\mathrm{S}}$
I don't think this is an actual counter-example.
Parametricity implies:
$$∀(α : \Alg \NatF t) (g : r → t)(x : \NatF r). \\
α\ [r]\ g\ x = α\ [t]\ (λx.x)\ (\map g\ x)
$$
(a special case of the free theorem), where
$$\map g\ x = Λt. λz\ s. x\ [t]\ z\ (s \circ h)$$
let:
$$h : (∀s. s → s) → t \\
h\ \_ = α\ [t]\ (λy. y)\ (Λt. λz\ s. z)$$
which is your first argument to $α$. Then in your example:
$$α\ [∀s. s→s]\ h\ x \\
= α\ [t]\ (λx.x)\ (\map h\ x) \\
= α\ [t]\ (λx.x)\ (Λt. λ\_\ s. s (α\ [t]\ (λx. x)\ (Λt. λz\ \_. z)))$$
Now observe the following from $\Z$ and $\S$
$$
α\ [\Nat]\ (λy. y\ [t]\ α)\ (Λt. λz\ \_. z)  \\
  = α\ [t]\ (λx.x)\ (\map (λy. y\ [t]\ α) (Λt. λz\ \_. z)) \\
  = α\ [t]\ (λx.x)\ (Λt. λz\ \_. z)
$$
$$
α\ [\Nat]\ (λy. y\ [t]\ α)\ (Λt. λ\_\ s. s\ n) \\
 = α\ [t]\ (λx.x)\ (map (λy. y\ [t]\ α) (Λt. λ\_\ s. s n)) \\
 = α\ [t]\ (λx.x)\ (Λt. λ\_\ s. s (n\ [t]\ α))
$$
Then, if we go back to the calculation from your example:
$$
α\ [t]\ (λx.x)\ (Λt. λ\_ s. s (α\ [t]\ (λx.x)\ (Λt. λz\ \_. z))) \\
  = α\ [t]\ (λx.x)\ (Λt. λ\_\ s. s (\Z\ [t]\ α)) \\
  = \S\ \Z\ [t]\ α
$$
So your example is extensionally equal to $1$, assuming my calculations are correct.


Complexity of Localization in Wireless Networks Let distinct points $1 ... n$ sit in $\mathbb{R}^2$.  We say points $i$ and $j$ are neighbors if $|i-j| < 3 \pmod{n-2}$, meaning each point is neighbors with points with indexes within $2$, wrapping around.

The problem is:

  For each pair of neighbors we are given their pairwise distances (and we know which distance corresponds to which points), and we want to reconstruct the
  pairwise distances of all points.  My
  questions is, what is the complexity
  of this localization problem?

I don't know of a polynomial time algorithm.

This is motivated by problems in localization in sensor networks, where agents, placed ad-hoc, can wirelessly communicate with their lexicographic neighbors, and we want to reconstruct their positions.

I don't know much about geometry / localization problems, so this might be easy or known.  The closest problem I know about is the Turnpike problem, recently pointed out on this forum by @Suresh Venkat.

It is actually NP-hard. See the following paper for references.

Sriram V. Pemmaraju, Imran A. Pirwani: Good Quality Virtual Realization of Unit Ball Graphs. ESA 2007: 311-322


$d$-regular bipartite expander graph I have seen that there exists $d$-left regular bipartite graphs. My question is do there exists $d$-regular bipartite expander graphs in which both the degree of the left and the right vertices is exactly equal to $d$? If yes, is there any constructive proof for such graphs and what is the expansion factor? Kindly provide a reference as well.

There is a simple construction: Take any $d$-regular non-bipartite expander $G=(V,E)$ - there are several constructions of those, e.g., Margulis, or the Zig-Zag construction. Now, turn it into a bipartite graph $G' = (V_1 \cup V_2, E')$ as follows: $V_1$ and $V_2$ are copies of $V$. Two vertices $v_1 \in V_1$ and $v_2 \in V_2$ are adjacted in $G'$ if and only if the corresponding vertices in $G$ are adjacted. The expansion of $G'$ follows from the expansion of $G$.

However, one thing that should be noted is that the expansion factor in all those constructions is at most $d/2$. We do not have bipartite expanders that have a better expansion factor and are balanced (i.e. have degree $d$ on both sides).


Boolean error correcting code over $\mathbb{F}_q$ Is there any known construction of a linear error correcting code $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ (with reasonable parameters), such that when given a Boolean vector $v\in \{0,1\}^n$, it also returns a Boolean vector w.h.p.? (although it is over $\mathbb{F}_q$)

(that is, $\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon$, where the probability is taken over uniformly choosing $v\in \{0,1\}^n$, and $\epsilon$ is arbitrarily small)

If not, what if we relax the condition to
$$\Pr[\mathsf{ECC}_i(v) \in \{0,1\}]> 1-\epsilon$$
Where $\mathsf{ECC}_i$ returns the $i$'th coordinate of $\mathsf{ECC}$, $\epsilon$ is arbitrarily small, and the probability is taken both over uniformly choosing $v\in \{0,1\}^n$ and uniformly choosing a coordinate $i\in[m]$.

Yes. For example, a Reed-Solomon code contains a BCH code, which is a binary linear code, as a sub-code. These are called subfield-subcodes.


Variable profit knapsack sorry for bad formatting earlier

We are given Cx,i, Cy,i, Cz,i ∈ ℕ and Px,i, Py,i, Pz,i > 0 for i=1,2,3 such that Px,1 < Px,2 < Px,3, Py,1 < Py,2 < Py,3, and Pz,1 < Pz,2 < Pz,3. We are also given K∈ℕ.

The values Cx,i and Px,i describe the content of a stack named x. From top to bottom, the stack x contains Cx,1 items each of profit Px,1, Cx,2 items each of profit Px,2, and Cx,3 items each of profit Px,3. The contents of stacks y and z are defined in the same way.

We are allowed to pop K items in total from the three stacks. How can I maximize the total profit?

This is not an answer, but the description of a problem which I think the asker wants to ask.

To vaibhav: While I believe that this is at least close to what you want to ask, please edit the question so that it is clearly understandable.  Otherwise, we can only make a guess about what is being asked.

We are given Cx,i, Cy,i, Cz,i ∈ ℕ and Px,i, Py,i, Pz,i > 0 for i=1,2,3 such that Px,1 < Px,2 < Px,3, Py,1 < Py,2 < Py,3, and Pz,1 < Pz,2 < Pz,3.  We are also given K∈ℕ.

The values Cx,i and Px,i describe the content of a stack named x.  From top to bottom, the stack x contains Cx,1 items each of profit Px,1, Cx,2 items each of profit Px,2, and Cx,3 items each of profit Px,3.  The contents of stacks y and z are defined in the same way.

We are allowed to retrieve K items in total from the three stacks.  How can we find efficiently the way to maximize the total profit?


Can words in regular languages be generated by automata in a unique way? If $L\subset \Sigma^\ast$ is a regular language then it is known that we can find a directed graph (aka automaton) $G$ with edges labelled with symbols from $\Sigma$, an ‘initial’ vertex, and a set of ‘terminal’ vertices, with the property that a word $w$ is in $L$ iff $w$ is the sequence of edge labels along a path from the initial vertex to a terminal vertex.

It’s possible that the same word can appear as a result of different paths in $G$. Can we guarantee that for any regular $L$ we can find a $G$ such that each word in $L$ appears as a path in $G$ in a unique way?

(I’m interested in this because I want to know whether the solution to the problem I worked on here applies cleanly to any regular language, or just for a certain class of them.)

Maybe I misunderstood your question, but wouldn't a Deterministic Finite Automaton do what you want?


Merging Two Binary Search Trees I'm looking for an algorithm to merge two binary search trees of arbitrary size and range.  The obvious way I would go about implementing this would be to find entire subtrees whose range can fit into an arbitrary external node in the other tree.  However, the worst case running time for this type of algorithm seems to be on the order of O(n+m) where n and m are the size of each tree respectively.

However, I've been told that this could be done in O(h), where h is the height of the tree with the larger height.  And I'm completely lost on how this is possible.  I've tried experimenting with rotating one the trees first, but rotating a tree into a spine is already O(h).

In ArXiv:1002.4248, John Iacono and Özgür Özkan describe a relatively simple algorithm to merge two binary search trees in $O(\log^2 n)$ amortized time; the analysis is the hard part.  [Update: As Joe correctly observes in his answer, this algorithm is due to Brown and Tarjan.]  They also describe a more complicated dictionary data structure, based on biased skip lists, that supports merges in $O(\log n)$ amortized time.

On the other hand, a worst-case bound of $O(\log n)$ is impossible.  Consider two binary search trees with $n$ nodes, one storing the even integers between $2$ and $2n$, the other storing the odd integers between $1$ and $2n-1$.  Merging the two trees creates a new binary search tree storing all integers between $1$ and $2n$.  In any such tree, a constant fraction of the nodes have different parity than their parents.  (Proof: The parent of an odd leaf must be even.)  Thus, merging the even and odd trees requires changing $\Omega(n)$ pointers.


Time complexity of Held-Karp algorithm for TSP When I looked through "A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp, I came up with the following question:
why the complexity of their algorithm for TSP is $(\sum_{k=2}^{n-1}k(k-1)\binom{n-1}{k})+(n-1)$ (p. 199), I mean where do they take the factor $k$? If I understood correctly $k-1$ means the number of additions for each subset of cities. Then why each addition operation is coupled with unknown to me $k$ operations? I suppose it is connected somehow to taking minimum, but computing minimum doesn't seem to require such many operations.

Dynamic programming algorithm by Held and Karp and independently Bellman runs as follows:
for each pair $(S,c_i)$, meaning a path going through $c_1$, all the elements of $S$ and terminating at $c_i$ compute

$OPT[S,c_i]=min\{OPT[S\setminus\{c_i\},c_j]+d(c_j,c_i):c_j\in S\setminus\{c_i\}\},$

where $d(c_j,c_i)$ means the distance between cities $c_j$ and $c_i$. Then in the formula from the paper $k$ means the size of $S$.

Addendum to below, clarifying the $k(k-1)$ terms:

So, if you examine the terms in the expression, you can envision (as analogy) the $n-1 \choose k$ term is an enumeration of all binary strings containing $k$ 1's that have a 1 in the first position. In other words, we let each position in the binary string represent the choice of whether a given one of the $n$ cities in the problem are in the exact subset we are considering at the time. So, for 5 cities, 10101 corresponds to the subset {1,3,5}.

Thus, to compute across all subsets of {1,...,$n$}, we simply count through each binary subset (i.e. count through binary strings) of size=2 (i.e. binary strings of size $n$ that contain two 1's), then size=3, then size=4, ...then size=n. (Note that the size=1 subset must contain only the first city, and thus it's irrelevant to compute its partial distance, since the distance from 1 -> all other cities in the subset -> 1 is exactly 0.)

At each subset with $k$ cities, we have to consider up to $k-1$ candidate-optimal, partial paths. Specifically, the optimal, total path could conceivably traverse through the given subset and end up on any of the $k-1$ cities, excluding the first city. Then, for each such candidate sub-path, we compute the optimal tour up to that point as the minimum of any of the previous, size=$k-1$ sub-paths plus the distance from the terminal city for that sub-path to the terminal city for the current candidate sub-path. This gives $(k-1)(k-2)$ such comparisons that we must make. The discrepancy between my $(k-1)(k-2)$ term, and the $k(k-1)$ term in the analysis linked is a notational difference (I would sum over a different range, given my definition of $k$ than they did). At the very least, however, it should illustrate the quadratic-order complexity of that term.

How interesting -- I just finished coding this exact algorithm up in C++ a few minutes ago. (So forgive the tangent from pure theory into a little practical discussion. :))

It costs $O(2^n n^2)$ time and $O(2^n n)$ space -- at least under my implementation. Practically speaking though, when your space requirements grow that fast, they become way more painful than the time requirements. For instance, on my PC (with 4 GB of RAM), I can solve instances with up to 24 cities -- any more than that, and I run out of memory.

Of course, I could just be a bad programmer, and you might be able to do better than me in practice. :)

Edit: A little more specifics on one detail of your question: The $k(k-1)$ term comes from the fact that you have to, in the worst case, calculate the partial, optimal distance from the previous subsets (there are at most $n$ of them; note that $k$ is summed over $n$ in the analysis you linked) to the current one. This requires, again in the worst case, $O(k)$ comparisons with subsets of size $k-1$ for a total of $O(k^2)$.

Also, if my explanation wasn't clear enough, here are some nice lecture notes of Vazirani's (PDF). Scroll down to P. 188 for a discussion of TSP, including an analysis of Held-Karp.


A public key cryptographic technique usable without aid of computer I wondered if there is any known algorithm for secure messaging without pre-shared keys (i.e. public key cryptography) that is practical to use without the aid of a computer?

Obviously I would not expect it to be as secure as modern 256-bit encryption, but I wondered whether it was theoretically possible that older civilizations ever could have used something akin to public key cryptography, perhaps something with a computational complexity on the order of the Vigenere technique but without the need for a pre-arranged shared key?

Secure cryptographic protocols that can be executed by humans are considered in this paper: http://link.springer.com/chapter/10.1007%2F3-540-45682-1_4 (Hopper and Blum, "Secure Human Identification Protocols"). Reading the abstract, it sounds like they don't fully solve the problem. I suspect a satisfying solution is not known, but if you want to look into it I would start by looking at papers citing this one.


Increasing the capacity to maximize the min cut Consider a graph with all edges having unit capacity.
One can find the min cut in polynomial time.

Suppose I am allowed to increase the capacity of any $k$ edges to infinity
(equivalent to merging the nodes on either side of the edge).
What is the optimal way of selecting an optimal set of $k$ edges
(whose capacity will be increased to infinity)
to maximize the min cut?

Theorem. The problem in the post is NP-hard.

By "the problem in the post", I mean, given a graph $G=(V,E)$ and integer $k$, to choose $k$ edges to raise the capacities of so as to maximize the min cut in the modified graph.

The idea is to reduce from Max Cut.  Roughly, a given graph $G=(V,E)$ has max cut size $s$ if and only if you can increase the capacities of $n-2$ edges so that the resulting graph has min cut size $s$.  The idea is that $n-2$ edges are just enough to force the resulting graph to have only one finite-capacity cut, and that can be any cut you choose.

This idea doesn't quite work because to get a given cut $(C, V\setminus C)$, you need the subgraphs induced by $C$ and $V\setminus C$ each to be connected.  But you can work around this with an appropriate gadget.

Proof.
Given a connected graph $G=(V,E)$, define a connected cut to be a cut $(C,V\setminus C)$ such that the subgraphs induced by $C$ and by $V\setminus C$ are each connected.  Define Max Connected Cut to be the problem of finding a connected cut (in a given connected graph) maximizing the number of edges crossing the cut.

We show that Max Connected Cut reduces to the problem in the post. Then we show that unweighted Max Cut reduces to Max Connected Cut.

Lemma 1.  Max Connected Cut reduces in poly time to the problem defined in the post.

Proof.  Given a Max-Connected-Cut instance $G=(V,E)$, let $k=|V|-2$.  To prove the lemma, we prove the following:

Claim 1: For any $s>0$, there is a connected cut $(C,V\setminus C)$ in $G$ of capacity at least $s$, IFF it is possible to raise $k$ edge capacities in $G$ to infinity so that the resulting graph has min cut capacity at least $s$.

ONLY IF: Suppose there is a connected cut $(C,V\setminus C)$ of capacity at least $s$. Let $T_1$ and $T_2$ be subtrees spanning, respectively, $C$ and $V\setminus C$, then raise the capacities of edges in $T_1$ and $T_2$.  (Note that $|T_1|+|T_2|=|C|-1 + |V\setminus C|-1 = |V|-2 = k$.)  The only finite-capacity cut remaining in the graph is then $(C, V\setminus C)$, of capacity at least $s$, so the resulting graph has min cut capacity at least $s$.

IF: Suppose it is possible to raise $k$ edge capacities in $G$ so that the resulting graph has min cut capacity at least $s$. Consider the subgraph formed by the $k$ raised edges.  Without loss of generality, assume this subgraph is acyclic.  (Otherwise, "unraise" one edge from a cycle of raised edges and instead raise some unraised edge that joins two connected components from the subgraph.  This only increases the min cut in the resulting graph.) By the choice of $k=n-2$, the subgraph of raised edges has two connected components, say $C$ and $V\setminus C$, so the only finite-capacity cut in the resulting graph is $(C,V\setminus C)$.  And this cut has capacity at least $s$, as it did in the original graph.

This proves the claim (and the lemma). (QED)

For completeness, we show that Max Connected Cut is NP-complete, by reduction from unweighted Max Cut.

Lemma 2. Unweighted Max Cut reduces in poly time to Max Connected Cut.

Proof. For any integer $N\ge 1$, define graph $P(N)$ to consist of two paths $A$ and $B$, each of length $N$, with edges from each vertex in $A$ to each vertex in $B$.  We leave it as an exercise to the reader to verify that the max cut in $P(N)$ ($A$ on one side, $B$ on the other) has size $N^2$, and no other cut has size larger than, say, $N^2-N/100$.

Here is the reduction.
Given any unweighted Max Cut instance $G=(V,E)$, construct a  graph $G'=(V',E')$ as follows.  Let $n=|V|$.  Let $N = 100(n^2 + 2n)$.  Add to $G$ the graph $P(N)$ defined above (with its two paths $A$ and $B$).  From each vertex $v\in V$ add an edge to one vertex in $A$ and another edge to one vertex in $B$.  This defines the reduction.  To finish, we prove it is correct:

Claim 2: For any $s\ge 0$, there is a cut $(C,V\setminus C)$ in $G$ of capacity at least $s$, IFF there is a connected cut in $G'$ of size at least $s+N^2+n$.

ONLY IF:  Given any cut $(C,V\setminus C)$ in $G$ of capacity at least $s$, consider the connected cut $(A\cup C, B\cup V\setminus C)$ in $G'$.  This connected cut in $G'$ cuts at least $s$ edges from $C$ to $V\setminus C$, plus $N^2$ edges from $A$ to $B$, plus $n$ of the $2n$ edges from $V$ to $A\cup B$.

IF: Suppose there is a connected cut in $G'$ of size at least $s+N^2+n$. $A$ and $B$ are on opposite sides of the cut.  (Otherwise, since the second largest cut in $P(N)$ cuts at most $N^2-N/100$ edges in $P(N)$, the total number of edges cut is at most $N^2-N/100 + |E| + 2|V| \le N^2 - N/100 + n^2 + 2n = N^2$.) Let $C$ denote the vertices in $V$ on the side of the cut with $A$.  Then there are $N^2$ edges in the cut from $A$ to $B$, and $n$ from $V$ to $A\cup B$, so there must be at least $s$ from $C$ to $V\setminus C$.

This proves the claim and Lemma 2.  (QED)

By Lemmas 1 and 2, since unweighted Max Cut is NP-hard, the problem in the post is also NP-hard.


A Notion of Monotone Quantum Circuits In computational complexity there is an important distinction between monotone and general computations and a famous theorem by Razborov asserts that 3-SAT and even MATCHING are not polynomial in the monotone Boolean circuits model.

My question is simple: Is there a quantum analog for monotone circuits (or more than one)? Is there a quantum Razborov's theorem?

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

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

What we want from quantum

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

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

A simple model of quantum monotone circuits

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

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

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

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

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

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

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

A quantum variant of Razborov's result

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

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

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

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

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


Language/type system closest to Haskell without general recursion I've implemented a completely functional DSL, and now I'd like to reason about it.  It would be helpful to be able to compare it to existing languages.

The type system is parametric polymorphic with higher order functions but no dependent types.  The only recursion allowed is structural recursion in the form of a fold over an inductively defined type (including natural numbers).

The way I see it, the language shares its turing-incompleteness and form of recursion with Coq, but shares parametric polymorphism with Haskell.  Is there a more exact comparison to be made?  In particular, I was wondering if System F can be pared down to only support structural recursion, and what that would look like.

Thanks!

The language closest to Haskell without general recursion is Haskell without general recursion, with suitable fold operations taken as primitive.

Haskell's datatypes have non-wellfounded values thanks to Haskell's lazy evaluation strategy. Once we remove general recursion from Haskell, the difference between lazy and eager evaluation does not matter anymore, and the datatypes become inductive in the sense that only well-founded values may be expressed (because every program is terminating, and folding over an non-wellfounded value woudl give a non-terminating program). So, you can just keep Haskell without general recursion, it's got parametric polymorphism, and the inductive types will work as expected.


Examples of #P problems which are in FP ? Is there any case of SAT problems (except the affine ones) whose counting version can be computed in polynomial time ?

$SAT$ and $\#SAT$ for CNF formulas of bounded rank are tractable. See $[1]$.

Andrei S. et al. A hierarchy of tractable subclasses for SAT and counting
SAT problems. 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing.


Lower bounds for nonuniform circuits and oracles separating complexity classes I have read that Furst, Sax, and Sipser came up with their lower bound for nonuniform AC0 while trying to prove an oracle separation.

Can someone explain how proving lower bounds for circuits and constructing oracles separating complexity classes are related?
Are there other circuit lower bounds related to separating oracles?
Is there a general theme connecting nonuniform lower bounds for circuits and  separating oracles?

Yes, yes, and yes.

The basic idea is to consider the characteristic function of a language $L$
(the oracle you're constructing) at length $n$ as a string of length $2^n$
that will be an input to a ("big") circuit.
An OR gate in that circuit will correspond to
a polynomially-bounded existential quantifier, and
an AND gate to a polynomially-bounded universal quantifier.

Consider Furst-Saxe-Sipser as an example of
how this can be used to build oracles:
If the language $L$ is constructed so that
the characteristic function of $L \cap \Sigma^n$ is an input
whose parity differs from an $\mathsf{AC}^0$ function
(which exists, by Furst-Saxe-Sipser),
then you've just successfully diagonalized against
the language in $\mathsf{PH}$ corresponding to that $\mathsf{AC}^0$ function.
Doing this over all $\mathsf{AC}^0$ diagonalizes against all of $\mathsf{PH}$, and thus builds an oracle $L$ such that $\mathsf{PH}^L \neq \mathsf{PSPACE}^L$
(since the latter includes the language corresponding to
the "big" parity circuit).

For more discussion and examples of this general theme see the following survey :

Ker-I Ko, "Constructing Oracles by Lower Bound Techniques for Circuits", 1989.


Finding Tours through Near-Hamiltonian Paths? Say I have a connected graph.  I want to find a tour that visits each vertex at least once.  It's not always possible, though, for there to be a solution if there is a bridge in the graph.  Is there a term for this sort of problem or a recommended approach to solving it?  The motivation if it helps that I ultimately have in mind is traversing every station in a subway system.

There are no polynomial-time $\alpha$-approximation algorithms for TSP where $\alpha$ is a constant unless $\mathsf{P} = \mathsf{NP}$.

However, for metric TSP there are approximation algorithms, e.g. Christofides algorithm. A simpler 2-approximation is obtained by taking an MST.


Would polynomial solution for #P-complete problem mean polynomial solution for PSPACE problem? After looking at textbooks and trying to derive by my own deductive abilities, I was not able to see whether polynomial solution for #P-complete problem (that is counting problem done in polynomial time) do or do not lead to polynomial solution for PSPACE problem. Can anyone show me why it has to be one or the other way?

We know that #P is included in FPSPACE (the class of function problems corresponding to PSPACE), but we currently do not know if this inclusion is proper or not. Therefore, a polynomial time algorithm for #P-complete problems does not necessarily imply a polynomial time algorithm for all problems in PSPACE.


Extensional type theory and function extensionality Is the principle of function extensionality
$ (\forall x. f(x) = g(x)) \implies f = g$, derivable from ETT?
Most notably is this derivable in Agda with axiom K?

Yes, equality reflection and $\eta$-rule for functions together imply function extensionality.

Recall that equality reflection is the rule
$$\frac{\vdash p : \mathsf{Id}_A(a,b)}{\vdash a \equiv b : A}$$
Suppose $A$ is a type, $x : A \vdash B(x)$ is a type over $A$, and $f, g : \prod_{x : A} B(x)$. We claim that function extensionality
$$\textstyle (\prod_{x:A} \mathsf{Id}(f x, g x)) \to \mathsf{Id}(f, g)$$
is inhabited by $\lambda r \,.\, \mathsf{refl} f$. Indeed, suppose $r : \prod_{x:A} \mathsf{Id}(f x, g x)$. We have $$y : A \vdash r y : \mathsf{Id}(f y, g y),$$ therefore by equality reflection $$y : A \vdash f y \equiv g y : B(y).$$ Now it follows that $$(\lambda y : A . f y) \equiv (\lambda y . g y) : \textstyle\prod_{x : A} B(x)$$
By $\eta$-rule for functions (it does not matter whether this is propostional or judgemental $\eta$, thanks to equality reflection) we get
$$f \equiv (\lambda y . f y) \equiv (\lambda y . g y) \equiv g : \textstyle\prod_{x : A} B(x)$$
Because $f$ and $g$ are judgmentally equal, $\mathsf{refl}\,f$ indeed has the type $\mathsf{Id}(f,g)$.


Conesequences of $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$ Does $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$  has any separation of classes or consequences?

  My main question is can use this to show that $P \neq NP$ or some thing useful about $P \neq NP$ .

This would imply that L⊊NP since L⊆TISP(poly(n),n^k) k∈N


How to make a paper stronger? After reading this question and David's answer I thought a more general question asking for tips would be useful. So

  how can authors make (and write) a paper stronger?

This is sort of an unserious answer in that it's not what I consciously do most of the time, but:

Think about what the next paper after yours might be — not the next paper that takes some small follow-on problem from your paper and solves that too, but the next paper that takes it to another level, finds tight upper and lower bounds, shows that it's an instance of a more general phenomenon, and generally makes your paper obsolete. Then write about the results in that paper instead of the ones you already have.


Complexity of Turing self-reducibility of Clique problem? I'm interested in the complexity of self reducibility of a variant clique problem. Namely, the NP-complete problem HALF Clique: given a graph on $N$ nodes, Is there a clique of size $N/2$ in the graph?

How hard is it to reduce an instance of HALF CLIQUE of input size $2N$ to an instance of size $N$ using Turing reduction? Is there a Cook reduction? I'm looking for references for upper bounds and lower bounds on the complexity of Turing reductions of this type.

This is not a reference, but an NP-complete problem cannot have a polynomial-time self-reduction which halves the input size unless NP has a nO(log n)-time algorithm, even if we allow Turing reductions.

Suppose there is a p(n)-time Turing reduction from an NP-complete problem L to itself such that given an input of length n, the reduction only makes queries to strings of length at most n/2.  Then you can convert this reduction to a standalone deterministic algorithm for L by using recursion.  By writing down a recurrence relation for the running time of this deterministic algorithm, it is not hard to see that it runs in time nO(log n).


What evidence is there that Graph Isomorphism is not in $P$? Motivated by Fortnow's comment on my post, Evidence that Graph Isomorphism problem is not $NP$-complete, and by the fact that $GI$ is a prime candidate for $NP$-intermediate problem (not $NP$-complete nor in $P$), I am interested in known evidences that $GI$ is not in $P$.

One such evidence is the $NP$-completeness of a restricted Graph Automorphism problem(fixed-point free graph automorphism problem is $NP$-complete). This problem and other generalizations of $GI$ were studied in "Some NP-complete problems similar to Graph Isomorphism" by Lubiw. Some may argue as evidence the fact that despite more than 45 years no one found polynomial-time algorithm for $GI$.

  What other evidence do we have to believe that $GI$ is not in $P$?

Before this question, my opinion was that Graph Isomorphism might be in P, i.e. that there is no evidence to believe that GI is not in P. So I asked myself what would count as evidence for me: If there were mature algorithms for $p$-group isomorphism that fully exploited the available structure of $p$-groups and still would have no hope to achieve polynomial runtime, then I would agree that GI is probably not in P. There are known algorithms that exploit the available structure like Isomorphism testing for $p$-groups. by O'Brien (1994), but I haven't read it in sufficient detail to judge whether it fully exploits the available structure, or whether there is any hope to improve this algorithm (without exploiting additional non-obvious structure of $p$-groups) to achieve polynomial runtime.

But I knew that Dick Lipton called for action near the end of 2011 to clarify the computational complexity of the group isomorphism problem in general, and of the $p$-group isomorphism problem specifically. So I googled for

site:https://rjlipton.wordpress.com group isomorphism

in order to see whether the call for action had been successful. It was indeed:

The Group Isomorphism Problem: A Possible Polymath Problem?
Advances on Group Isomorphism
Three From CCC: Progress on Group Isomorphism

The last post reviews a paper which achieves $n^{O(\log \log n)}$ runtime for certain important families of groups, exploits much of the available structure, and acknowledges the above mentioned paper from 1994. Because the $n^{O(\log \log n)}$ runtime bound is both compatible with the experience that graph isomorphism is not hard in practice, and with the experience that nobody is able to come up with a polynomial time algorithm (even for group isomorphism), this can be counted as evidence that GI is not in P.


Example of context-free tree language which can not be generated by monadic CFTG Assuming that a context-free tree language (CFTL) is that which is generated by a context-free tree grammar (CFTG), I am looking for an example of CFTL which can not be generated by a monadic CFTG (MCFTG).

In other words, I am looking for such a non-monadic CFTG for which it is not possible to construct an equivalent (MCFTG).

The all examples of CFTG's which exist in papers are essentially monadic CFTG.

I am still trying to build such a grammar by myself. But may be somebody already knows such an example and could share it as an answer. I deeply appreciate any help.

Based on the comment of Michael Wehar, I've found this grammar to be that one which doesn't have an equivalent MCFTG:

$S\rightarrow T(a,a)$

$T(x_1,x_2)\rightarrow T(b(x_1,x_2),c(x_1,x_2))$

$T(x_1,x_2)\rightarrow a(x_1,x_2)$

This grammar produces perfect binary trees where in each branch the left child has a label a if it is a leaf, and has a label b otherwise; the right child has a label a if it is a leaf, and has a label c otherwise.

I don't have a very rigorous proof of this fact, however here below there are some observations.

It makes it impossible to build such a monodic context free tree grammar which will produce the same language of trees. This is because any single-ranked non-terminal can not properly set a parent node label (b or c). This label depends on "context": a knowledge about wether this node is left or wether it is right.

Also, because the depth of each path in the given tree is the same, it can not be produced by a grammar where each next branch is generated by an independent non-terminal.


What is known about solutions to sparse integer linear programming problems? If I have a set of linear constraints in which each constraint has at most (say) 4 variables (all nonnegative and with {0,1} coefficients except for one variable that can have a -1 coefficient), what is known about the solution space?  I am less concerned with an efficient solution (although please indicate if one is known) than with knowing how small the minimum of the objective function can be, as a function of the number of variables and number of constraints, and the number of variables per constraint.

More concretely, the program is something like

minimize t
  subject to
for all i, x_i is a positive integer
x1 + x2 + x3 - t < 0
x1 + x4 + x5 - t < 0
...
x3 + x6 - t     ≥ 0
x1 + x2 + x7 - t ≥ 0
...

If a concrete question is needed, then is it the case that the minimum solution obeys t <= O(max{# of variables, # of constraints}), with the constant in the O() depending on the sparseness?  But even if the answer is no, I am more interested in knowing what kind of textbook or paper to study for a discussion of such issues, and if there is an area of study devoted to this kind of thing but I just don't know the terms to search for.  Thank you.

Update: With further reflection (and thinking through the rather simple reduction of 3SAT to ILP, which uses constraints with three variables), I realize that the issue of coefficients is critical (if there is going to be an efficient algorithm).  More precisely, all x_i variables have 0 or 1 coefficients (with at most three 1 coefficients in any one constraint), and all t variables have -1 coefficients, and all comparisons have variables on the left and 0 on the right.  I updated the above example to clarify.

The answer to this (at least to the concrete question about linearly bounding the solution) is no.  This is part of the following paper: http://arxiv.org/abs/1011.3493.  Theorem 5.1 was the motivation for this question.

The counterexample is this:

base case:

a_1'  + b_1'  - t ≥ 0
a_1'' + b_1'' - t ≥ 0
a_1   + b_1'  - t ≤ -1
a_1 ' + b_1'' - t ≤ -1

recursive case:

a_n'  + b_n'  + a_{n-1}   - t ≥ 0
a_n'' + b_n'' + a_{n-1}   - t ≥ 0
a_n   + b_n'  + a_{n-1}'' - t ≤ -1
a_n'  + b_n'  + a_{n-1}'' - t ≤ -1

along with requiring them all to be nonnegative.

You can prove by induction that any real solution must satisfy a_n'' >= a_n + 2^n.  We change the "< 0"-inequalities into "≤ -1" because any integer solution satisfies "≤ -1" if and only if it satisfies "< 0".

So, the moral is that n inequalities of this form can have the property that all integer solutions have at least one integer at least exponential in n, certainly not linearly bounded as we originally suspected.


Proof of Levenshtein distance In the article Levenshtein distance Wikipedia says about the proof of invariant that:

  This proof fails to validate that the number placed in d[i,j] is in
  fact minimal; this is more difficult to show, and involves an argument
  by contradiction in which we assume d[i,j] is smaller than the minimum
  of the three, and use this to show one of the three is not minimal.

So how can I show that d[i,j] is actually minimal? (informal proof is ok)

There is an optimal edit sequence in which the edit operations occur in order from left to right.  There are only three options for the last edit operation: insert the last character of the target string, delete the last character of the source string, or replace the last character.  Everything before the last edit operation must be optimal.

See section 3.7 of this textbook.


Complexity of weighted cycle in a hamiltonian graph Assume a weighted graph G and a positive value k are given.

What is the complexity of finding a cycle with total weight k when G is Hamiltonian or Hamiltonian-connected?

pointing to papers and books is also welcome!
I wish it wouldn’t look as a homework!

If we are asking for a simple cycle the problem is NP-complete by a reduction from the Hamiltonian cycle problem.

We want to find a Hamiltonian cycle in a graph $G$. We assign weight 1 to all edges of $G$, and add to this graph all the other edges with weight $\infty$. We have thus created a clique, which is obviously Hamiltonian, and we ask whether there exist a cycle with weight $n$ in it.


Research problems in communication complexity There have been many open challenges questions in this forum.

For instance,

Research and open challenges in Programming Language Theory
What are current open problems in compiler theory?
Outstanding conjectures and open problems in (algorithmic) game theory?
Open problems on the frontiers of TCS
Open problems related to Graph isomorphism

What are some of research avenues, areas available within communication complexity? What are some of most interesting open problems?

Some famous open problems AFAIK are status of log-rank conjecture, status of $\mathsf{IP}^{}\notin\mathsf{PH}^{cc}$, status of examples of natural problems in $\mathsf{NP}_k^{cc}$,$\mathsf{coNP}_k^{cc}$.

What are some of lesser known open problems or areas that are not yet mature within communication complexity or areas that have made new progress but much more needs to be done?

Are there any problems relating other areas such as circuit complexity, machine learning etc?

AFAIK communication complexity is more about finding bounds that about algorithms. Are there any problems with number theoretic, algebraic, geometric flavor or more generally in an algorithmic flavor?

More generally what would be some areas a newly entered person should focus energy to select a problem to work on (comm complexity field does not have many hearsay research topics as other traditional areas in mainstream theory CS with direct real world applications)?

I'll start with answers to your general questions, then give one nice open problem with applications towards circuit complexity.

It's hard to say what areas a new communication complexity researcher should delve into, since easy problems have likely been solved already, and harder problems are hard ;)  One suggestion is to take known communication lower bounds (such as for Disjointness or Equality) and apply these to get new lower bounds in other areas of computer science.  New applications of communication complexity pop up all the time, and if you can find a niche no one's considered before, you might be able to leverage the existing bounds you're learning now rather than having to develop new lower bounds.  This will help you get some papers out while you're learning all about communication complexity ;)

Another suggestion is to work hard to ask new questions people haven't yet considered, or to think about new settings that are fresh and less well-studied. Multiparty communication might be a good area to look at---it is generally less understood than two-party communication, and (IMO at least) there's lots of fresh motivation for studying it (from e.g. multicore processors to wireless sensor networks)

For a concrete open problem, there's a nice one from multiparty communication in the number-on-the-forehead (NOF) model.  In the NOF communication model, there are $k$ players who wish to compute some function $f(x_1,\ldots, x_k)$ on $k$ inputs.   However, each player $PLR_i$ sees every input except $x_i$.  (You can imagine $PLR_i$ having $x_i$ written on his forehead.) Because lots of input is shared between players, it should be easier to compute functions of their input.  Conversely, proving lower bounds on the communication complexity in the NOF model is harder.

Here's a $\textbf{big open problem}$ in this area:  come up with some explicit function f(x_1,\ldots, x_k) for k=polylog(n) such that $\omega(polylog(n))$ communication is required in the NOF model.

Through a chain of results from the early nineties [Hastad-Goldman91, Beigel-Tarui94], it's known that such a result would imply that $f \not\in ACC_0$.  For this connection to circuit complexity, you're actually free to assume that each player sends a single message to some "referee" who compiles the messages to produce an output.  Lower bounds even in this restricted setting are far from what we'd like.  The current state-of-the-art lower bound techniques for the NOF model don't give lower bounds better than $\Omega(n/2^k)$ or thereabouts.  These become trivial once $k > \log(n)$.


Is there some mathematical closed form (or somewhat tight asymptotic one) for "Google Eggs Puzzle"? The following brief description of the known "Google Eggs Puzzle" comes mainly from the web site Google Eggs:

  Google Eggs Puzzle: Given n floors and m eggs, what is the approach to find the highest floor from which eggs can be thrown safely, while minimizing the throws (not broken eggs).

The so called "highest floor" in the above problem deserves more formal definition:

  "highest:" there must be a floor f (in any sufficiently tall building) such that an egg dropped from the  f th floor breaks, but one dropped from the (f-1)st floor will not. Then, f-1 here is the highest floor.

Actually, the description of "highest" is an excerpt from the book "The Algorithm Design Manual (Second Edition)" by Steven S. Skiena. Being an exercise in Chapter 8 "Dynamic Programming", there are plenty of resources in Web devoted to solving the puzzle by the means of dynamic programming, like Google Eggs and The Two Egg Problem.

However, there is a question from the above book:

  Show that $E(n, m) = \Theta(n^{\frac{1}{m}})$, where $E(\cdot)$ is the minimum number of throws. (Note: I have changed the notations used in book for consistency.)

It is the question that motivates my problem:

  My Problem: Is there some mathematical closed form for general "Google Eggs Puzzle" with n floors and m eggs, instead of dynamic programming recurrence, and of course tighter than the $E(n, m) = \Theta(n^{\frac{1}{m}})$ one?

With m eggs and k measurements the most floors that can be checked is exactly $$n(m,k)={k \choose 0} + {k \choose 1} + \ldots + {k \choose m},$$ (maybe $\pm 1$ depending on the exact def). Proof is trivial by induction. This expression has no closed form inverse but gives good asymptotic.


Subrange of a Red and Black Tree While trying to fix a bug in a library, I searched for papers on finding subranges on red and black trees without success. I'm considering a solution using zippers and something similar to the usual append  operation used on deletion algorithms for immutable data structures, but I'm still wondering if there's a better approach I wasn't able to find, or even some minimum complexity boundary on such an operation?

Just to be clear, I'm talking about an algorithm that, given a red&black tree and two boundaries, will produce a new red&black tree with all the elements of the first tree that belong within those boundaries.

Of course, an upper bound for the complexity would be the complexity of traversing one tree and constructing the other by adding elements.

This answer combines some of my comments to the question and expand them.

The subrange operation on red-black trees can be performed in worst-case O(log n) time, where n is the number of elements in the original tree.  Since the resulting tree will share some nodes with the original tree, this approach is suitable only if trees are immutable (or trees are mutable but the original tree is no longer needed).

First notice that the subrange operation can be implemented by two split operations.  Here the split operation takes a red-black tree T and a key x and produces two trees L and R such that L consists of all the elements of T less than x and R the elements of T greater than x.  Therefore, our goal now is to implement the split operation on red-black trees in worst-case O(log n) time.

How do we perform the split operation on red-black trees in O(log n) time?  Well, it turned out that there was a well-known method.  (I did not know it, but I am no expert of data structures.)  Consider the join operation, which takes two trees L and R such that every value in L is less than every value in R and produces a tree consisting of all the values in L and R.  The join operation can be implemented in worst-case time O(|rL−rR|+1), where rL and rR are the ranks of L and R, respectively (that is, the number of black nodes on the path from the root to each leaf).  The split operation can be implemented by using the join operation O(log n) times, and the total worst-case time is still O(log n) by considering a telescoping sum.

Sections 4.1 and 4.2 of a book [Tar83] by Tarjan describe how to implement the join and the split operations on red-black trees in worst-case time O(log n).  These implementations destroy original trees, but it is easy to convert them to immutable, functional implementations by copying nodes instead of modifying them.

As a side note, the Set and the Map modules of Objective Caml provide the split operation as well as other standard operations on (immutable) balanced binary search trees.  Although they do not use red-black trees (they use balanced binary search trees with the constraint that the left height and the right height differ by at most 2), looking at their implementations might be useful, too.  Here is the implementation of the Set module.

References

[Tar83] Robert Endre Tarjan.  Data Structures and Network Algorithms.  Volume 44 of CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, 1983.


Descriptive model theory classification of Counting hierarchy Descriptive model theory uses logic to characterize complexity classes

How to model

Counting Hierarchy
PSPACE

in descriptive model theory?

This is only a partial answer (to the $PSPACE$ characterization), but I don't have the reputation to comment.

$PSPACE$ has the following (equivalent) descriptive characterizations:

$FO[2^{n^{O(1)}}]$, first-order logic with exponentially iterated quantifier blocks.
$SO[n^{O(1)}]$, second-order logic with polynomially iterated quantifier blocks.
$SO[TC]$, second-order logic with a transitive closure operator.
$FO[PFP]$, first-order logic with a partial fixed point operator.
$CRAM$-$PROC[2^{n^{O(1)}}, n^{O(1)}]$, concurrent-read concurrent-write random access machine with exponential time and polynomial hardware.
$CRAM$-$PROC[n^{O(1)}, 2^{n^{O(1)}}]$, concurrent-read concurrent-write with polynomial time and exponential hardware.

These are all mentioned in Immerman's book Descriptive Complexity.

I can't find a reference on a descriptive characterization for the counting hierarchy, but here are some observations:

$PP$ naturally corresponds to existential second-order logic with a second-order majority quantifier.
$TC^0$ is equal to $FO$ with a majority quantifier. Padding arguments give us a relationship between $TC^0$ and $CH$. This relationship makes $SO$ with a majority quantifier (on relations) a natural candidate for a descriptive characterization of $CH$.


polygonal triangulation and 3-colorability Lets define polygonal triangulation a triangulation which has a hamiltonian cycle.

It's easy to see that any polygonal triangulation is 3-colorable since any triangulation of a polygon is 3-colorable.

Is any 3-colorable triangulation also polygonal triangulation?
In other words, is any 3-colorable maximal planar graph hamiltonian?

You seem to be confusing two concepts: triangulations of simple polygons are maximal outerplanar graphs (and every maximal outerplanar graph is Hamiltonian); maximal planar graphs are something else.

But anyway: no.

A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single odd vertex requires four colors, and if it is Eulerian then a 3-coloring may be obtained by coloring a triangle and then extending the coloring in the obvious way to adjacent triangles).

For an example of an Eulerian maximal planar graph that is not Hamiltonian, glue nine octahedra together: one in the center and one attached to each of its faces. The dihedral angle of a regular octahedron is less than 120 degrees so there's plenty of room to do this without even having to distort anything.

If the graph of this polyhedron could have a Hamiltonian cycle, then it would visit the central octahedron's six vertices in an order that is also a Hamiltonian cycle, together with six paths connecting those six vertices. But each of those six paths can only visit one of the eight side octahedra that are glued onto the center, so two of the side octahedra must remain unvisited, contradicting the Hamiltonicity of the cycle.


The Complexity of Advice in Computational Indistinguishability One of the cornerstones of the modern cryptography is the definition of computational indistinguishability: It is used in definition of cryptosystems, pseudorandom generators, zero-knowledge, etc.

Below, we will first define this concept, and then investigate some of its properties:

Let $U=\{U_n\}$ and $V=\{V_n\}$ be two distribution ensembles, indexed by natural numbers. That is, for every $n \in \mathbb{N}$, $U_n$ and $V_n$ are probability distributions. We call $U$ and $V$ computationally indistinguishable if, for all probabilistic Turing machine $D$ which is polynomial-time in the length of its first input, all positive polynomial $p(\cdot)$, every sufficiently large $n \in \mathbb{N}$, and all advice strings $z \in \{0,1\}^*$:

$\left|\Pr_{u \leftarrow U_n}[D(1^n,u,z)=1]-\Pr_{v \leftarrow V_n}[D(1^n,v,z)=1]\right|<\frac{1}{p(n)}.$

The probability is taken over the choice of $u$ and $v$, as well as the internal coin tosses of $D$.

An equivalent definition is obtained by replacing the $\forall z \in \{0,1\}^*$ part by a quantifier over all functions $f$, and letting $z=f(1^n)$. Note that $f$ can be an uncomputable function.

The question is:

  Are there distribution ensembles $U$ and $V$ which are computationally distinguishable, but if we restrict $f$ to computable functions, then $U$ and $V$ are computationally indistinguishable?

Goldreich argued that in cryptographic settings, where all parties are modeled by probabilistic polynomial-time Turing machines, $f$ must be computable by a polynomial-time machine.

Now consider other settings, such as the case of single- or multi-prover interactive proofs. It is proven (Shamir, Babai et al.) that the parties in such systems need not be more powerful than PSPACE and NEXP machines, respectively.

  Is it rational to consider uncomputable functions $f$ in such cases? In particular, do we need to consider $f$ to be computable by machines whose power is beyond PSPACE or NEXP, respectively?

Case 1. The distributions $U_n$ and $V_n$ are computable in the sense that we can eventually tell if your displayed inequality is violated, for fixed $n$ and $z$.

It seems the answer to the first question (following "The question is") is No in this case. Suppose there is a $D$ and a $p$ such that for infinitely many $n$, there is a $z$ violating the inequality. I claim we can find a computable function $f$ such that $f(1^n)$ is infinitely often such a $z$. What $f$ does is run all searches for $z$ for various values of $n$ in parallel. When one is found for some $n$, we define $f(1^n)=z$ and the searches for undefined values $m<n$ are called off and $f(1^m)$ is defined arbitrarily. Then another parallel search is instituted for a larger value of $n$.

Case 2, we do not make any assumption about $U$ and $V$. Then Yes. Both $U_n$ and $V_n$ will be deterministic in the following construction.

Let $D(1^n,w,z)$ simply compute whether $w=z$ and output 1 if this is the case. But $U_n$ and $V_n$ will output the $n$th element $s_n$, $t_n$, of sets $S$ and $T$, respectively. Then such a function $f$ would have the property that infinitely often $f(1^n)=s_n\ne t_n$ or vice versa. Now suppose that $n\mapsto s_n$ and $n\mapsto t_n$ both dominate all computable functions, and $\{n: s_n\ne t_n\}$ is infinite (such sets $S$ and $T$ clearly exist). Then a function $f$ exists with the required property, but cannot be computable.


One-way randomized communication complexity of approximate Hamming distance If Alice and Bob both have $n$ bit strings, consider a one-way randomized communication problem where Bob has to output with some good probability a number which is within a $(1+\epsilon)$ factor of the Hamming distance between their strings.

What is the one-way randomized communication complexity of this problem?

I have found a lot of literature on seemingly related problems (e.g. promise problems, threshold versions of Hamming distance) but I can't find a reference for this precise formulation.

Here is a simple protocol for Hamming distance that uses $O(\varepsilon^{-2} \log n)$ bits. The protocol is essentially the Alon, Matias, Szegedy second moment sketch. Or you can think of it as a version of the Johnson-Lindenstrauss lemma.

I am assuming that Alice has a vector $x \in \{0,1\}^n$ and Bob has a vector $y \in \{0,1\}^n$, and they share randomness. Notice that the Hamming distance between $x$ and $y$ is equal to $\|x-y\|_2^2$. Using the shared randomness Alice and Bob sample a $\varepsilon^{-2} \times n$ matrix $\Sigma$ of IID unbiased $\pm 1$ random variables. The Alice sends $\Sigma x$ and Bob outputs $\varepsilon^{-2}\|\Sigma (x - y)\|_2^2$.

For the analysis notice that $\mathbb{E}[\varepsilon^{-2}\|\Sigma (x - y)\|_2^2] = \|x-y\|_2^2$, so the output is an unbiased estimator of $\|x-y\|_2^2$. Because the rows of $\Sigma$ are IID,

$$
\mathrm{Var}[\varepsilon^{-2}\|\Sigma(x-y)\|_2^2] = \varepsilon^{-2} \mathrm{Var}\left[\left(\sum_{i=1}^n{\sigma_i (x-y)}\right)^2\right],
$$

where $\sigma_1, \ldots, \sigma_n$ are IID unbiased $\pm 1$ random variables. Then, by Khintchine's inequality, for a constant C

$$
\begin{align*}
\mathrm{Var}\left[\left(\sum_{i=1}^n{\sigma_i (x-y)}\right)^2\right] &\leq \mathbb{E}\left[\left(\sum_{i=1}^n{\sigma_i (x-y)}\right)^4\right] \\
&\leq C \mathbb{E}\left[\left(\sum_{i=1}^n{\sigma_i (x-y)}\right)^2\right]^2 \\
&= C\|x-y\|_2^4.
\end{align*}
$$

So, by Chebyshev, with constant probability the output of the protocol is a $1+O(\varepsilon)$ approximation to $\|x-y\|_2^2$, which is equal to the Hamming distance.


Clarification: Are runtime bounds in P decidable? In Emanuele Viola's much upvoted answer to the question, "Are runtime bounds in P decidable?" he uses the following proof:

The problem is undecidable. Specifically, you can reduce the halting problem to it as follows. Given an instance $(M,x)$ of the halting problem, construct a new machine $M'$ that works as follows: on inputs of length $n$, it simulates $M$ on $x$ for $n$ steps. If $M$ accepts, loop for $n^2$ steps and stop; otherwise loop for $n^3$ steps and stop.
If $M$ halts on $x$ it does so in $t=O(1)$ steps, so the run time of $M'$ would be $O(n^2)$. If $M$ never halts then the run time of $M'$ is at least $n^3$.
Hence you can decide if $M$ accepts $x$ by deciding if the run time of $M'$ is $O(n^2)$ or $O(n^3)$.

I have a significant problem with this proof, but as it is well accepted by theoreticians much smarter than me I am sure that I must be misunderstanding.
Here is my issue:

$M'$ simulates $M$ on $x$ for $n$ steps.

If $M$ accepts, then $M$ certainly halts on $x$. However, if $M$ does not accept, this does not mean that $M$ does not halt on $x$; it only means that $M$ does not halt on $x$ in the first $n$ steps. In a comment, Emanuele clarifies that $M$ and $x$ are selected independently of $n$; however, this does not negate the fact that $M$ is only simulated on $x$ for $n$ steps.
So either this is a reduction from, "Does $(M,x)$ halt in $n$ steps?" which is a decidable problem, or I am missing some major component of this proof. Could someone please clarify?

In my opinion, the wording of the answer is a little confusing.  Specifically:

  Given an instance $(M,x)$ of the halting problem, construct a new machine $M′$ that works as follows: on inputs of length $n$, it simulates $M$ on $x$ for n steps.

...confused me, too.  What you have to understand is that the machine $M'$ is based on one specific instance of the halting problem; it doesn't simulate $M$ on $x$ for $|x|$ steps.

Here is how I would word that part:

  Fix an instance $(M,x_1)$ of the halting problem.  Construct a machine $M'$ that takes as input $x_2$, and that works as follows:  simulate $M$ on $x_1$ for $|x_2|$ steps.  If $M$ halts within $|x_2|$ steps, loop for $|x_2|^2$ steps and stop; otherwise loop for $|x_2|^3$ steps and stop.

Hopefully that helps.


Algorithms for finding clique in bounded-degree graph Consider a graph with $n$ vertices and maximum degree $\Delta$. I would like to find if the graph has any $s$ cliques, where $s \leq \Delta$ and both of them are small compared to $n$. I only need to find a single such clique (or certify that none exist)

There is a straightforward way to do this: for each vertex $v$, test all $s$-subsets of the neighbors of $v$. The work is thus $\approx n \binom{\Delta}{s-1}$.

Are there any more efficient algorithms than this? Even achieving an exponential speed-up would be good?

Eppstein, Löffler, and Strash modified the Bron-Kerbosch algorithm, obtaining an algorithm that lists all maximal cliques in $O(dn 3^{d/3})$ time, where $d$ is the degeneracy of the graph (note $d \le \Delta$).

The same idea can be extended for the maximum clique problem in $d$-degenerate graphs, and the runtime can be improved to $O^*(2^{d/4})$.


What type of mathematical problems interesting for TCS researchers? I am Ph.D student (about to graduate) in TCS. I have worked on some problems. I have been able to publish few research paper. There are many research problems in mathematics as well in TCS. I am sure that all of the problems of mathematics are not interesting to all TCS researchers. There seems to be gap between mathematics and TCS to me. I have made many attempts to define research problem on very old mathematical problems, some time algorithm is trivial and some time motivation is not clear to me. I don't if in the future I come up with an algorithmic problem on some mathematical problem will that be interesting to TCS community. I am here as I want to know when it makes sense to define a algorithmic question on mathematical problem for TCS researchers point of view. Let us say I am able to give an algorithm which classify all modules(Algebraic structure) of some rank. Will that interesting to TCS researchers?

There is one other way for me to not care about other and work on problems which I find interesting, but in that case I don't I will be a successful researcher or not.

In short while defining algorithmic question what are things or questions I should ask to myself

Question : What type of mathematical problems interesting for TCS researchers?

Let us say I am able to give an algorithm which classifies all modules (algebraic structure) of some rank. Will that be interesting to TCS researchers?

Roughly speaking...

It will be interesting to applied mathematicians if they find that the algorithm is fast enough in practice in some sense.
It will be interesting to pure mathematicians if the algorithm gives new insight into the structure of modules or lets them compute examples that can be used to test conjectures.
And will be interesting to TCS researchers if there are also lower bounds on how fast an algorithm for this problem can possibly be, or if this problem is related to algorithms for other problems such as classifying rings, module isomorphism etc.

An example that was interesting to all three to varying degrees is Tarski's theorem on the real field.


Minimax agnostic risk for Lipschitz functions For $L>0$, let $F_L$ be the class of all $L$-Lipschitz functions on $[0,1]$. Let $D$ be a joint distribution on $[0,1]\times\mathbb{R}$, from which we sample $n$ iid copies $(X_i,Y_i)$. Given any $f:[0,1]\to\mathbb{R}$,
$
%its empirical risk is
$
$$
% R_n(f) = \frac1n\sum_{i=1}^n (f(X_i)-Y_i)^2$$
its true risk (w.r.t. $D$) is
$$ R(f) = \mathbb{E}_D[(f(X)-Y)^2].$$
Define the minimax agnostic excess risk by
$$ \Delta_n = \inf_{\hat f}\sup_D \mathbb{E}_D[ R(\hat f)-\inf_{f\in F_L}R(f)],$$
where the sup is over all distributions $D$ and the inf is over all estimators taking an $n$-point sample $(X_i,Y_i)$ to a function $\hat f:[0,1]\to\mathbb{R}$.

What is known about the behavior of $\Delta_n$? I was only able to find mimimax rates for additive -- rather than agnostic -- noise models.

Sasha Rakhlin kindly pointed me to:
https://projecteuclid.org/euclid.bj/1486177384

where a rate of $n^{-2/3}$ is shown.


Time complexity of Bellman-Held-Karp algorithm for TSP, take 2 A recent question discussed the now-classical dynamic programming algorithm for TSP, due independently to Bellman and Held-Karp.  The algorithm is universally reported to run in $O(2^n n^2)$ time.  However, as one of my students recently pointed out, this running time may require an unreasonably powerful model of computation.

Here is a brief description of the algorithm.  The input consists of a directed graph $G=(V,E)$ with $n$ vertices and a non-negative length function $\ell\colon E\to\mathbb{R}^+$.  For any vertices $s$ and $t$, and any subset $X$ of vertices that excludes $s$ and $t$, let $L(s,X,t)$ denote the length of the shortest Hamiltonian path from $s$ to $t$ in the induced subgraph $G[X\cup\{s,t\}]$.  The Bellman-Held-Karp algorithm is based on the following recurrence (or as economists and control theorists like to call it, “Bellman's equation”):

$$
    L(s,X,t) = \begin{cases}
       \ell(s,t) & \text{if $X = \varnothing_{\strut} $} \\
       \min_{v\in X}~  \big(L(s, X\setminus\lbrace v\rbrace, v) + \ell(v,t)\big)
              & \text{otherwise}
    \end{cases}
$$

For any vertex $s$, the length of the optimal traveling salesman tour is $L(s,V\setminus\{s\}, s)$.  Because the first parameter $s$ is constant in all recursive calls, there are $\Theta(2^n n)$ different subproblems, and each subproblem depends on at most $n$ others.  Thus, the dynamic programming algorithm runs in $O(2^n n^2)$ time.

Or does it?!

The standard integer RAM model allows constant-time manipulation of integers with $O(\log n)$ bits, but at least for arithmetic and logical operations, larger integers must be broken into word-sized chunks.  (Otherwise, strange things can happen.)  Is this not also true of access to longer memory addresses?  If an algorithm uses superpolynomial space, is it reasonable to assume that memory accesses require only constant time?

For the Bellman-Held-Karp algorithm in particular, the algorithm must transform the description of the subset $X$ into the description of the subset $X\setminus\{v\}$, for each $v$, in order to access the memoization table.  If the subsets are represented by integers, these integers require $n$ bits and therefore cannot be manipulated in constant time; if they are not represented by integers, their representation cannot be used directly as an index into the memoization table.

So: What is the actual asymptotic running time of the Bellman-Held-Karp algorithm?

This is less of a mathematical answer than a philosophical one, but I prefer to think of a RAM model that allows constant-time manipulation of integers with some number B of bits that is unknown but at least as large as $\log_2 S$, where S is the amount of space that the algorithm requires. Because, if the integers weren't that big, how could you even address your memory? For polynomial time and space algorithms it's the same as O(log n) bits, but for exponential space algorithms it avoids the problem.

Of course, if S exceeds the amount of memory you actually have, your algorithm won't run at all. Or, it will run by paging information into and out of memory and you should be using a memory hierarchy model instead of the RAM model.


The ODD EVEN DELTA problem Let $G = ( V, E )$ be a graph. Let $k \leq |V|$ be an integer. Let $O_k$ be the number of edge induced subgraphs of $G$ having $k$ vertices and an odd number of edges. Let $E_k$ be the number of edge induced subgraphs of $G$ having $k$ vertices and an even number of edges. Let $\Delta_k = O_k - E_k$. The ODD EVEN DELTA problem consists in computing $\Delta_k$, given $G$ and $k$.

  Questions

  Is it possible to compute $\Delta_k$ in polynomial time? Which is the best known algorithm to compute it?
  What if $G$ is 3-regular?
  What if $G$ is 3-regular bipartite?
  What if $G$ is 3-regular bipartite planar?

The ODD EVEN DELTA problem is #P-hard, even on 3-regular bipartite planar graphs.

Let $\mathcal{C}$ be the set of vertex covers of a general graph $G$. Then, assuming $G$ has no isolated vertices, the following equation holds (refer to the above article for the proof):

$$|\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k}$$

Counting vertex covers is #P-complete even on 3-regular bipartite planar graphs, and it can be done with a linear number of calls to an ODD EVEN DELTA oracle.


Is this a known problem, and is it #P-complete? Let $G=(V,E)$ be an undirected graph. What I call a selection function of $G$ is a partial function $f:V \to E$ such that for every node $v$, if $f(v)$ is defined then it is one of the adjacent edges to $v$. In other words, every node can either select no edge or select an edge that is adjacent to it. The image of $f$ is simply $\mathrm{Im}(f)= \{e \in E \mid \exists v \in V \text{ s.t. } e=f(v)\}$ i.e., the set of edges that are selected.

I am interested in the following counting problem:

INPUT: a graph $G$

OUTPUT: $|\{\mathrm{Im}(f) \mid f \text{ is a selection function of }G\}|$

Question 1: does it have an established name? (It seems to be to be rather natural so maybe it has already been considered)

Question 2: is this problem #P-hard? (Ideally, I would like it to be hard on bipartite graphs)

Note that this problem is in #P, which is not entirely obvious at first glance. To show this, it is enough to show that for every $S \subseteq E$, we can determine in PTIME if $S$ is the image of some selection function. This can be done as follows. First, construct the bipartite graph $G_S$ with nodes in the left partition being the nodes of $G$ and nodes in the right partition being edges in $S$, and connect $v$ in the left partition to $e$ in $S$ if $v$ is an endpoint of $e$. Then, compute the size $m$ of a maximum cardinality matching of $G_S$. Accept if $m=|S|$, and reject otherwise (observe that $m$ is always $\leq |S|)$. It is easy to check that this accepts iff $S$ is the image of some selection function.

To Question 1: The graphs induced by such edge sets are known as pseudoforests. As your proof of the membership to #P implies, an edge set is the image of a selection function if and only if the graph induced by the edge set allows an edge orientation in which each vertex has out-degree at most 1. A graph is a pseudoforest if each connected component is a tree or a tree + one edge. It is known (and easy to see) that a graph is a pseudoforest if and only if it admits an outdegree-at-most-1 orientation.

To Question 2: The problem is #P-hard on general graphs (not sure about bipartite graphs). The family of edge sets of a graph inducing pseudoforests forms the family of independent sets of a bicircular matroid. Counting the number of independent sets of a matroid $M$ is equivalent to computing the Tutte polynomial $t(M;2,1)$. It is shown by Giménez and Noy that computing $t(M;2,1)$ is #P-hard even if $M$ is a bicircular matroid given as a graph.


Algebraic construction of $\varepsilon$-biased sets Let $\ell> 1$ be an integer and consider the mapping $\text{Tr}:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2^\ell}$ defined by
$$\text{Tr}(x)=x^{2^0}+x^{2^{1}}+\cdots+x^{2^{\ell-1}}$$
It is then possible to show the following

$\text{Tr}$ maps $\mathbb{F}_{2^\ell}$ into $\mathbb{F}_2$.
If $a\in\mathbb{F}_{2^\ell}$ is non-zero, then the mapping $f_a:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2}$ defined by $f_a(x)=\text{Tr}(a\cdot x)$ is $\mathbb{F}_2$-linear and $\mathbb{E}_{x\sim\mathbb{F}_{2^\ell}}[f(x)]=\frac{1}{2}$.

Now, we consider the set $S=\{s(x,y,z):x,y,z\in\mathbb{F}_{2^\ell}\}$ such that we index the entries of $s(x,y,z)$ by $0\leq i,j$ such that $i+j\leq c\sqrt{n}$ ($c$ is a constant so that there are exactly $n$ entries). For such $x,y,z$ and $i,j$ we set $s(x,y,z)_{i,j}=\text{Tr}(x^iy^jz)$.

I want to show that for an appropriate choice of $\ell$, the set $S$ described above is an $\varepsilon$-biased set of size $O(n\sqrt{n}/\varepsilon^3)$.

Fix $\vec{0}\neq \tau\in\{0,1\}^n$, what we need to show is that (under good choice of $\ell$)
$$\bigg|\mathbb{E}_{s\in S}\Big[(-1)^{\langle s,\tau\rangle}\Big]\bigg|\leq \varepsilon$$

Let $x,y,z\in\mathbb{F}_{2^\ell}$ and consider $\langle s(x,y,z),\tau\rangle$, I managed to show that (from $\mathbb{F}_2$-linearity above while indexing $\tau$ as we index $s(x,y,z)$)
$$\langle s(x,y,z),\tau\rangle=\cdots=f_z\Big(\sum_{i,j}x^iy^j\tau_{i,j}\Big)$$
Finally, I thought of defining the bi-variate polynomial $p_\tau(x,y)=\sum\limits_{i,j}x^iy^j\tau_{i,j}$ and saying that since it is a non-zero polynomial of low degree at most $c\sqrt{n}$ it attains each value of $\mathbb{F}_{2^\ell}$ with multiplicity at most $c\sqrt{n}2^\ell$ (from Schwartz-Zippel), so
$$\forall\alpha\in\mathbb{F}_{2^\ell}:\Pr\limits_{x,y\in\mathbb{F}_{2^\ell}}[p_\tau(x,y)=\alpha]\leq c\sqrt{n}/2^\ell$$

I want to use it but I am stuck..., maybe we can say that the distribution of $p_\tau(x,y)$ is close enough to $U_{\mathbb{F}_{2^\ell}}$ in statistical distance in order to infer that the expeced value of $f_z(p_\tau(x,y))$ is close enough to $1/2$?

recall that
$$\langle s(x,y,z),\tau\rangle=\cdots=f_z\Big(\sum_{i,j}x^iy^j\tau_{i,j}\Big)$$

if we define $p_\tau(x,y)=\sum\limits_{i,j}x^iy^j\tau_{i,j}$, we have

$$\langle s(x,y,z),\tau\rangle=f_{p_\tau(x,y)}(z)$$

So, observe that whenever $p_\tau(x,y)\neq 0$ we win as $z$ is uniform and the expected value of $f_{p_\tau(x,y)}(z)$ is also $1/2$ which means that the contribution to the bias of these $x,y$ is zero.

Again from Schwartz-Zippel we have only $O(\sqrt{n}/2^\ell)$ many zeros of $p_\tau$ on them we lose the entire bias. So, the total bias is at most $O(\sqrt{n}/2^\ell)\stackrel{?}{\leq}\varepsilon$. Choosing $\ell=\Omega(\log(\sqrt{n}/\varepsilon))$ finishes the construction.


Constraint Satisfaction Problem: Choosing real numbers with certain characteristics I have a set of n real numbers. I also have a set of functions,

f_1, f_2, ..., f_m.

Each of these functions takes a list of numbers as its argument. I also have a set of m ranges,

[l_1, u_1], [l_2, u_2], ..., [l_m, u_m].

I want to repeatedly choose subsets {r_1, r_2, ..., r_k} of k elements such that

l_i <= f_i({r_1, r_2, ..., r_k}) <= u_i for 1 <= i <= m.

Note that the functions are smooth. Changing one element in {r_1, r_2, ..., r_k} will not change f_i({r_1, r_2, ..., r_k}) by much.

These are the m constraints that I need to satisfy.

Moreover I want to do this so that the set of subsets I choose is uniformly distributed over the set of all subsets of size k that satisfy these m constraints. Not only that, but I want to do this in an efficient manner. How quickly it runs will depend on the density of solutions within the space of all possible solutions (if this is 0.0, then the algorithm can run forever).

Note that n is large enough that I cannot brute-force the problem. That is, I cannot just iterate through all k-element subsets and find which ones satisfy the m constraints.

Is there a way to do this?

What sorts of techniques are commonly used for a CSP like this? Can someone point me in the direction of good books or articles that talk about problems like this (not just CSPs in general, but CSPs involving continuous, as opposed to discrete values)?

[Note that this question is a special case.]

This problem is clearly NP-Complete, so finding an efficient solution is almost surely out of the question.  Since you've put no real constraints on $f_i$, the best general solution is probably a brute force search.  If you knew something more about the $f_i$ then maybe you could exploit that to cull the search space or even come up with an efficient algorithm, but in general, even for simple functions this problem is difficult.

For example, choose just one function, $f( { r_0, r_1, \dots , r_{k-1} } ) = \sum_{i=0}^{k-1} r_i $, with the constraint $ -\epsilon < f( { r_0, r_1, \dots, r_{k-1} } ) < \epsilon$, then this is essentially the number partition problem.