Post Correspondence Problem variant This is probably pretty simple, but consider the standard Post Correspondence Problem:

Given $\alpha_1, \ldots, \alpha_N$ and $\beta_1, \ldots, \beta_N$, find a sequence of indices $i_1, \ldots, i_K$ such that $\alpha_{i_1}\cdots \alpha_{i_K} = \beta_{i_1}\cdots \beta_{i_K}$. This is, of course, undecidable.

Now, I call this a 'variant', but it's not really--it essentially throws away 'correspondence'. Anyway, consider the following variant:

Given $\alpha_1, \ldots, \alpha_N$ and $\beta_1, \ldots, \beta_N$, find two sequences of indices $i_1, \ldots, i_K, j_1, \ldots, j_{K}$ such that $\alpha_{i_1}\cdots \alpha_{i_K} = \beta_{j_1}\cdots \beta_{j_{K}}$. What can be said about this variant? If this is trivial, my apologies!

This new version - where $K = K'$ - is decidable.

Let's show that the language $L := \bigcup_{k \geq 1} (A^k \ \cap \ B^k)$ is a CFL.  Then the decidability follows from the decidability of the emptiness of a CFL.

We'll design a PDA to accept $L$.  On input $x$, this PDA will try to construct two factorizations of $x$, one using words of $A$, and the other using words of $B$.  It will use a counter on the stack to ensure these two factorizations are of the same length.  Conceptually I will refer to the $A$-factorization of $x$ so far as sitting on top of $x$ and the $B$-factorization as sitting on the bottom of $x$.  Then the stack will contain $n$ counters iff the absolute value of the difference of the number of words matched on the top, minus the number of words on the bottom, is $n$.  We need another state of the PDA to record what the appropriate sign is corresponding to $n$ (which tells us if the $A$-factorization is longer than the $B$-factorization, or vice versa).

As we scan the letters of $x$, we nondeterministically guess a word $t$ of $A$ and a word $u$ of $B$ to which this letter begins.  Once we guess, we are committed to matching the rest of $t$ and $u$ against $x$; if at any point our match fails, we halt in this nondeterministic choice.  So we also maintain, in the state of our PDA, the suffix of $t$ and $u$ that remains to match.

As we scan further letters, we continue matching until we hit the end of $t$ or the end of $u$ (or both).  When we hit the end of a word, we update the stack appropriately, and then guess a new word to match in either the top or bottom (or both).

We accept if the suffixes remaining to be matched are both empty in top and bottom, and the stack contains no counters.

We can construct this PDA effectively, so we can effectively decide if it accepts anything or not (for example, by converting effectively to a grammar $G$ and then using the usual method to see if G generates anything).

Edit: One can also turn this into an upper bound on how big $k$ can be, in the worst case.  I think it should give an upper bound of something roughly like $2^{O(l^2)}$, where $l$ is the sum of the lengths of the words in $A$ and $B$.

Edit: I see now that the requirement that $A$ and $B$ be finite sets can also be relaxed, to the requirement that $A$ and $B$ be regular (possibly infinite).  In this case, instead of maintaining the suffix remaining to be matched in "top" and "bottom", instead we maintain the states of the respective DFA we are in, after processing the prefix of a possible matched word.  If we hit a final state in either "top" or "bottom", we can nondeterministically choose to go back to the initial state for a new guessed word.


Matrix rank approximation I am aware of the problem of low rank approximation of matrices which has been studied in various models of computation. My question is the following:

What is the status of approximating rank of a matrix in these models (e.g., communication complexity, query complexity, streaming etc)? Here the goal is to output a number which is approximately the rank of the matrix. Is there a paper(s) which presents the state-of-the-art regarding this?

A quick Google search points only to the papers involving low rank approximation. The exact rank problem, however, has high lower bound (in randomized communication complexity) which follows from a reduction from singularity problem (i.e., whether a matrix is of full rank or not).

Here is a fairly recent paper by Balcan et. al. from SODA'19 that gives a sample-optimal algorithm to test matrix rank. Note, in the query complexity setting, you need to have an appropriate notion of gap, which is exactly what they consider here. The paper should also list most of the relevant references.


Solution/Hardness of the following (integer) budgeted problem? I have no idea how to solve the following INTEGER problem or prove its hardness. Thanks for any help/comment/open discussion!

Assume there are $N$ startups. For each startup $i$, you can invest $x_i\in \{0,1,...,C_i\}$ dollars where $C_i$ is the maximal investment that it accepts, and you will get a reward as $f_i(x_i)$. The reward function $f_i(x_i)$ has the following properties for all $i$:

(1) $f_i(.)$ is non-decreasing and $f_i(0)=0$

(2) $f_i(.)$ is not necessarily "convex" or "concave"

(3) $0 \leq x\leq x'\leq C_i$, $f_i(x)x' \geq f_i(x')x$

(4) the function $g_i(x) = f_i(x+1) - f_i(x)$ is not necessarily non-decreasing or non-increasing.

Your total budget is $C$. By selecting an INTEGER vector $(x_1,...,x_N)$, you want to maximize the total rewards $\sum_{i=1}^Nf_i(x_i)$ subject to (1) $x_i\in \{0,1,...,C_i\}$ for any $i$ and (2)$\sum_{i=1}^N x_i \leq C$.

Solving this exactly this ends up being $\mathsf{NP}$-hard.

The reduction I have doesn't pay much attention to the representation of the $f_i$'s. That said, the values of $f_i$ I end up giving can be computed efficiently, so this reduction works for any "black box" use of the $f_i$'s.

I'll give the reduction in two parts. Composing the two pieces gives the whole argument.

Firstly I claim that condition (iii) doesn't help very much, even when combined with condition (i). In particular, there is a reduction from the problem with (iii) ignored to the original version of the problem: Suppose there is an instance with $f_i$'s that are non-decreasing but otherwise arbitrary. Then we can make a new instance (whose data is denoted with primes (')) which has

$f_i'(0) \gets 0$,
for $x \ge 1$, $f_i'(x) \gets f_i(x-1) + A$ for an unspecified large constant $A$, and
$C_i' \gets C_i + 1$ and $C' \gets C + N$.

Note that if a given $f_i$ is initially non-decreasing, then so is the new $f_i'$, while the rest of condition (i) holds for $f_i'$.

To satisfy condition (iii), it suffices to make $A$ large enough. This follows from thinking geometrically about what condition (iii) imposes on the $f_i$s. In particular, for any particular $x$, let $\ell$ be the line through the origin and $(x,f_i(x))$. The condition (iii) says that every point $x' \ge x$ must have $(x',f_i(x'))$ below $\ell$, and every point $x' \le x$ must have $(x',f_i(x'))$ above $\ell$. Thinking of increasing $A$ as pulling the origin down while fixing the rest of $f_i$, it's clear that this condition limits toward the empty constraint as $A$ increases, since the lines $\ell$ become arbitrarily steep.

We also need to ensure this reduction is actually a reduction. We can accomplish this also by making $A$ large enough. In particular, it's easy to see that if $A$ is sufficiently large, then any optimal solution of the new instance must invest at least one unit into each startup (ie $x_i' \ge 1$ for any $x'$ optimal in the new instance). Once we have this, identifying each solution $x$ to the original instance with the solution $x'$ of the new instance defined by $x'_i \gets x_i + 1$ gives a correspondence between optimal solutions.
Now, if we ignore condition (iii), we can easily reduce from knapsack by making each $C_i$ the weight of item $i$, $C$ the capacity of the knapsack, and each $f_i$ "all-or-nothing" ($f_i(C_i) = C_i$ and $f_i(x) = 0$ otherwise). Then maximizing $\sum_i f_i(x_i)$ boils down to picking items that go into the knapsack. This is (in my opinion) easy to check and not the interesting part of this answer, so I won't belabor the details.


Idea for a white-box PIT deterministic algorithm in polynomial time Just a warning, I am an amateur and this algorithm probably doesn't work.

A high level description of the algorithm:

Be $f(x_1,...,x_n)$ a polynomial, $n$ the number of variables and $d$ is the maximum degree of a variable in $f$.

Find a vector set with at least $m=n*d$ elements such that any combination of $n$ elements forms a linearly independent subset of vectors.

As pointed out by @SashoNikolov and @kodlu in another question, just use the geometric progressions in a Vandermonde matrix to create this set:
$$
\begin{bmatrix}
1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{n-1}\\
1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{n-1}\\
1 & \alpha_3 & \alpha_3^2 & \dots & \alpha_3^{n-1}\\
\vdots & \vdots & \vdots & \ddots &\vdots \\
1 & \alpha_m & \alpha_m^2 & \dots & \alpha_m^{n-1}
\end{bmatrix}
$$

Where $\alpha_i = i$
Now we use the line-vectors of the Vandermonde matrix above to change the original polynomial $f$ into $m$ univariate polynomials $f_i(t)$ which corresponds to the values of the original polynomial $f$ along the line passing through the origin with the line-vector.

This is where it needs to be white-box, you go in the arithmetic circuit changing all variables according to the transformation:
$$f_i(t)=f(\alpha_i^{0}t,\alpha_i^{1}t,...,\alpha_i^{n-1}t)$$
Being a univariate polynomial, it is trivial to normalise this polynomial and check if it is identically $0$ or not.
If and only if all the univariate polynomials are identically $0$ then the original polynomial $f$ is identically $0$.

The geometrical reasoning:

Supposing $f$ is not identically $0$, to maximize the amount of non-colinear lines through the origin where $f=0$, $f$ should be a union of hypersurfaces (homogeneous polynomial).

Supposing $f$ is an homogenous polynomial (worst case), each hypersurface is able at best to make $f=0$ along $n-1$ of the Vandermonde line-vectors. So a union of $d$ hypersurfaces (best case as d is the maximum degree of a variable in $f$) is able at best to make $f=0$ along $(n-1)*d<m$ vector-lines.

Would this work? What is wrong?

Would this work? What is wrong?

No proof sketch that this is a polynomial time algorithm is given. The point where the algorithm might stop being a polynomial time algorithm is step 3:

  Being a univariate polynomial, it is trivial to normalise this polynomial and check if it is identically 0 or not.

Even so normalising a univariate polynomial is trivial from a conceptual point of view, it's unclear whether it can be done in polynomial time (or even polynomial space). For multivariate polynomials, it's obvious that polynomials like $(1+x_1)(1+x_2)\dots(1+x_n)$ can't be normalized in polynomial space. For univariate polynomials, the details of the problem formulation become important. If the input polynomial is given by an arithmetic circuit and the coefficients are from $\mathbb Z$, then repeated squaring will give you abundant examples of polynomials which cannot be normalized in polynomial space. (PIT is often done over finite fields, which avoids this sort of space explosion.)

The proof sketch that the algorithm works as intended has too many holes for being a valid mathematical proof. However, it is quite possible that there is a proper mathematical proof showing that the proposed algorithm works as intended, and this wouldn't even be a surprise. Here are some of the holes:

  $f$ should be a union of hypersurfaces (homogeneous polynomial)

This reads like a claim that $f$ is a homogeneous polynomial iff $f=0$ is a union of hypersurfaces (through the origin). But $f(x,y,z)=x^2+y^2-z^2$ is a homogeneous polynomial for which $f=0$ is not a finite union of hypersurfaces.

  Supposing $f$ is an homogenous polynomial (worst case), each hypersurface is able at best to make $f=0$ along $n−1$ of the Vandermonde line-vectors.

This seems to assume that $f(x_1,\dots,x_n)=\prod_i(\sum_j a_{ij}x_j)$, which might be yet another interpretation of "union of hypersurfaces". The hole in the proof here is that the "(worst case)" claim isn't proved. Note that $f(x,y,z)=x^2+y^2-z^2$ is a homogeneous polynomial, but it cannot be written in the assumed form.


Division by two of functions in #P Let $F$ be an integer valued function such that $2F$ is in $\#P$.  Does it follow that $F$ is in $\#P$?  Are there reasons to believe this is unlikely to always hold?  Any references I should know about?

Somewhat surprisingly, this situation came up (with a much larger constant), for a function $F$ for which $F \in? \#P$ is an old open problem.

Note: I am aware of the paper M. Ogiwara, L. Hemachandra, A complexity theory for feasible closure properties where a related division-by-2 problem has been studied (see Thm 3.13).  Their problem is different however, as they define the division for all functions via the floor operator.  That allowed them to make some quick reductions to parity problems.

I try to give my intuition why I think this is unlikely to hold. Take your favorite problem in $PPA$, and convert it into a problem in $\sharp P$, e.g., our function $f$ can be the number of Hamiltonian cycles in an input 3-regular graph containing a certain fixed edge. From the parity argument we know that $f$ is always even, so you can define $F:=f/2$ and I see no reason why $F$ would be in $\sharp P$.


The structure of pathological instances for simplex algorithms As far as I understand, all know deterministic pivot rules for simplex algorithms have specific inputs on which the algorithm requires exponential time (or at least not polynomial) to find the optimum. Let us call these instances 'pathological' since usually (i.e. on most inputs) the simplex algorithm terminates quickly. I remember from my mathematical programming course that the standard examples of pathological instances for specific rules were highly structured. My general question is if this is an artifact of the specific examples, or a feature of pathological instances in general?

Results like smoothed analysis and the polynomial time algorithm extending it rely on perturbing the input --- suggesting that the pathological examples are very special. Hence the intuition that the pathological instances are highly-structured does not seem that far fetched.

Does anybody have any specific insights on this? Or some references to existing work? I have been specifically vague about what I mean by 'structured' to try to be as encompassing as possible, but suggestions on how to better pin down 'structured' would also be useful. Any advice or references are greatly appreciated!

Amenta and Ziegler proved that all currently-known constructions of exponential-time instances for simplex follow a particular structure that they call "deformed products":

  Deformed Products and Maximal Shadows of Polytopes by Amenta and Ziegler

However, I don't think there's any reason to believe that all bad instances for simplex have this structure.  This is probably just an artifact of the research process:

Klee and Minty found the first exponential-time example.
Other researchers looked and Klee and Minty's techniques and extended them to other pivot rules.  They naturally took the path of least resistance and followed the Klee-Minty cube as closely as possible.
Once someone finds one bad example for a pivot rule, there's no incentive for people to look for more.  As a result, all the bad examples we know of have a similar structure.


If you could rename dynamic programming... If you could rename dynamic programming, what would you call it?

Richard Bellman's autobiography suggests that he chose the term “dynamic programming” to be intentionally distracting.

  The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was secretary of Defense, and he actually had a pathological fear and hatred of the word ‘research’.  I'm not using the term lightly; I'm using it precisely.  His face would suffuse, he would turn red, and he would get violent if people used the term ‘research’ in his presence. You can imagine how he felt, then, about the term ‘mathematical’.  The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially.  Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation.

  What title, what name, could I choose?  In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word ‘programming’. I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely ‘dynamic’, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word ‘dynamic’ in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought “dynamic programming’ was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.

(As Russell and Norvig point out in their AI textbook, however, this story must be a creative embellishment of the truth.  Bellman first used the phrase "dynamic programming" in 1952, and Charles Erwin Wilson did not become Secretary of Defense until 1953.)

Anyway, Bellman's original motivation suggests multistage planning, but at least for algorithmic purposes, I'd prefer something like frugal bottom-up recursion, only with fewer syllables.


Program inversion algorithms for higher-order programs The term program inversion
has multiple shades of  meaning, but probably got started with
J. McCarthy's 1956 work The Inversion of Functions Defined by Turing Machines in the context of AI. By now many
connections between program inversion and other fields have been discovered, e.g. reversible
programming (physical and logical), partial evaluation, verification,
bidirectional programming, logic programming, and machine learning.

What is program inversion? In first approximation it's something like
this: Given a program $P : A \rightarrow B$ taking arguments of type
$A$ and returning results of type $B$, produce a program $P^{-1}$ that
is "somehow" the inverse of $P$. I'm deliberately being vague here,
since the concept can be (and is) clarified in various ways: e.g. is $P$ required to be injective?  Should
$P^{-1}(b)$ return all or just some $a$ such that $P(a) = b$?

There are generic ways of inverting a program, e.g. using
diagonalisation as already pointed out by McCarthy, or using partial
evaluation, but they tend not to be efficient. Also most work on
program inversion I'm familiar with does not seem to deal with full
higher-order programming languages (i.e. $\lambda$-calculi).

Reference request. What is the state-of-the-art in explicit algorithms for program
inversion of $\lambda$-calculi (with no restriction on higher-orderness)?

There hasn't been a huge amount of work in this space, but what work there is, is pretty interesting.

Torben Mogensen has worked on this problem. Here are two papers of his.

The first paper gives an algorithm for first-order functional programs, and the second extends it to higher-order. The precise characterization of when this algorithm will succeed is left to future work.

Semi-inversion of Guarded Equations
Semi-Inversion of Functional Parameters

Tetsuo Yokoyama, Holger Bock Axelsen, and Robert Glück.

This describes the RFun programming language, which inverts first-order functional programs, but enforces injectivity and backwards determinism constraints which ensure that backwards evaluation is as fast as forwards. (They have written a number of other papers on this subject, which I have had trouble getting hold of.)

Towards a Reversible Functional Language.

Stefan Bohne and Baltasar Trancón Widemann.

This is a really neat paper! It observes that (a) you can construct a category where the morphisms are functions paired with their inverse (for whatever particular notion of inverse you are using), and (b) this category has dagger compact structure. This means you can write a program with a slightly funky linear type discipline, and then read off the forwards and backwards interpretations from the semantics.

They give a functional language with a fairly wild syntax: nigh-arbitrary expressions can be used as patterns, and reversibility makes it sensible.

An Approach for Generalized Reversible Functional Programming

Francesco Tiezzia, Nobuko Yoshida

I haven't read this one, but only just discovered it when Googling for the other papers. Given the authors and the subject, I suspect this is right up your alley!

Reversible session-based pi-calculus


What are some theory problems in Information Retrieval and Search Engines which are not yet solved or can be bettered? I'm interested in IR and Search Engines and want to work on a theory problem in this space. Most thoughts that I get are focused towards implementation and would like to explore something not solved or can be bettered instead of implementing

Anaphor resolution:

  Since this type of understanding is still poorly implemented in software, automated anaphora resolution is currently an area of active research within the realm of natural language processing.


maximum weighted 2D coverage problem by a rectangle Let $P=\{p_1,\ldots,p_n\}$ be a set of $n$ points in a 2D plane, that is $p_i\in \mathbb{R}^2$, $\forall i=1,\ldots,n$.
Each point, $p_i$, is associated with a weight, $w_i \geq 0$. Imagine a axis-parallel rectangle with a fixed size that can translate in the plane.
The question is how to preprocess the points so that, for all possible positions of the rectangle, it is efficient to determine the largest weight of the
subset of points that can be covered by the rectangle at the same time.

Question: what are the best running time and algorithm for finding the largest weight of the subset of points? Is $O(n \log n)$ possible?

I thought this might be an easy question to answer, but I failed to find any proper reference to this question. Any thought or reference will be appreciated.

Let me describe first how to solve this problem without precomputation, then I'll describe how to make use of precomputation.  I'll focus on the unweighted case (each point has weight 1); all the ideas should extend to the weighted case straightforwardly.

Here is an algorithm without precomputation: Use a sweep line.  Think of sweeping a vertical line from left to right.  This line represents the right edge of the rectangle.  The set of possible values for this sweep line will be the set of possible $x$-value of some point, so we only need to consider $O(n)$ locations of the sweep line.  Imagine that it starts at the left and slowly moves rightward.

The one thing we don't know is the $y$-value of the bottom edge of the rectangle; call it $b$ (for "bottom").  However, for any specific position of the sweep line, we can build a data structure that counts the number of points in the rectangle with bottom $b$, for all $b$ (i.e., that maps from the value of $b$ to the number of points if the rectangle's bottom edge is $b$ units above the axis, and the right edge coincides with the sweep line).  I suggest you use an interval tree to represent this data structure.  There are $O(n)$ possible values for $b$, and thus $O(n)$ intervals in the interval tree.  When we move the sweep line right, we might need to add or remove one interval from the interval tree.  When the sweep line hits a new point $(x_i,y_i)$, we add a new interval to the tree for the interval $[y_i,y_i+h]$ (where $h$ is the height of the rectangle).  When the sweep line hits $w$ units to the right of the point $(x_i,y_i)$, i.e., the sweep line hits $x=x_i+w$, then we delete the interval $[y_i,y_i+h]$ from the interval tree.  For each location of the sweep line, we can also use the interval tree to efficiently find the rectangle that covers the most points and has its right edge coincide with the sweep line; doing that for each possible location of the sweep line gives us the optimum rectangle.

The running time of this algorithm is $O(n \lg n)$.  Each insertion/deletion can be done in $O(\lg n)$ time, and we do $O(n)$ insertions and deletions, so the whole thing can be done in $O(n \lg n)$ time.

What about precomputation?  Well, if we are given the width $w$ and height $h$ of the rectangle in advance, along with the set of points, then we can build all of the interval trees.  Naively, it sounds like we need to store $O(n)$ interval trees, each of size $O(n)$, for a total of $O(n^2)$ space -- but one can do better.  We can reduce this to $O(n \lg n)$ space in total by using persistent data structures.  It is straightforward to build a persistent version of the interval tree data structure, using standard methods.

Once you've done the precomputation, given any vertical line representing the right edge of the rectangle, you can efficiently find the best rectangle that coincides with that right edge (in $O(1)$ time).  (Actually, you don't need persistent data structures for that: since there are only $O(n)$ possible queries, you can just record the answer for each possible query.)  I don't know if this is what you are looking for, though, as I found your question hard to understand (it was hard for me to tell what is available during precomputation and what is made available later for each query).


$NP$-hardness of scheduling problem I have been attempting to show that this problem is $NP$-complete but haven't been successful.  I wonder if anyone has a suggestion for a problem I could reduce to it.

$CALLS$: Suppose we have nodes $\{0, \ldots, n - 1\}$, with undirected edges between $(i \mod n, i + 1 \mod n)$ for all $i$.  Furthermore, suppose we have a set $C$ of calls, which are the form $(i \mod n, j \mod n)$, and an integer $K$.  The problem is to determine whether it is possible to schedule the set of calls (to schedule a call, one decides whether to go clockwise around the circle or counterclockwise) such that the maximum load (i.e. number of calls going through a given edge) is $\le K$.

I have been able to show that if we assign each call a weight the problem is $NP$-complete by reducing $PARTITION$ to it.  However, I haven't been able to reduce any $NP$-complete problem to unweighted $CALLS$.

Indeed, it can be solved in polynomial time.  This is a result by Frank (1985).


Lower bound on independence number in terms of clique number and order of graph In the paper "On Multi-dimensional Packing Problems" by Chekuri and Khanna there is the following lemma:

Lemma 4.3.(p. 191 of the paper) Let $G$ be a graph on $n$ vertices with $\omega(G) ≤ k$. Then $\alpha(G) ≥ n^{1/k}$.

If we substitute $G$ by a complete graph, then we get:
$\omega(G) = n$, then $\alpha(G) ≥ n^{1/n}>1$.

However, if I correctly understand the notion of an independence number, then $\alpha(K_n)=1,\forall n$. A contradiction to the lemma.

I have checked for several cases and it seems that this is the only one where the lemma doesn't hold.

Could someone explain what is wrong with my reasoning?

P.S. I sent this question to one of the authors before posting it here, but haven't received any answer.

Where it says

then any maximal independent set has size at least $n^{1/k}$,

it should say

then any maximal independent set has size at least the floor of $n^{1/k}$,

(Then this sentence is true for the complete graph $K_k$.)

They are being a bit sloppy, but I imagine that they just need the result for "large enough $n$".


Bellman-Ford with Non-edge-decomposable Path Weights Consider a directed graph $G(V,E)$ with non-negative edge weights. Also, let us define the weight of a path as non-edge-decomposable, that is, the weight of a path cannot be written as the sum of a function of the weights of its edges. Can we still use Bellman-Ford to converge to the shortest (i.e., minimum weight) path from some source $S$ to some sink $T$ after some number of iterations? Would Bellman-Ford converge eventually?

Follow up question:

The particular path weight function I am interested in uses a set operation where each edge is associated with a set of items. Each item has a weight. The weight of a path is then the sum of weights of items associated with the edges on the path. For example, in the following figure, we have items of $I_1$, $I_2$, and $I_3$ with weights $w_1$, $w_2$, and $w_3$, respectively. The weight of paths $P_1$ and $P_2$ is computed as $w_1+w_2$ and $w_1+w_2+w_3$, respectively.

$w_{P_1}$ = $\sum_{\gamma \in \{~\{I_1, I_2\}~\cup~\{I_2, I_3\}~\cup~\{I_2\}~\}} w_\gamma$

$w_{P_2}$ = $\sum_{\gamma \in \{~\{I_1, I_2\}~\cup~\{I_2\}~\}} w_\gamma$

No, Bellman-Ford won't work because the problem you described is NP-hard.

This is pretty easy to prove. I've been able to come up with several reductions using the same strategy. The general idea is to make it so that in the path you have several sections that can be chosen independently; then the overall question becomes whether you can coordinate all those choices so as to minimize the sum of the weights of the items in the chosen subpaths. You can easily set up the independent choices by using a sequence of "bottleneck" vertices $S = v_0, v_1, \ldots, v_{n-1}, v_n=T$ and making several paths between each $v_i$ and $v_{i+1}$ (the choices of which path piece from $v_i$ to $v_{i+1}$ to take for each $i$ are the independent choices I was talking about earlier).

For example, you can reduce from 3SAT. For each variable $x$, make one of the subpath choices be between item $x$ and item $\neg x$. For each clause, make one of the choices be between the items corresponding to the literals in the clause. For each variable either the variable, the negation, or both must be in any path. The only way to get away with having only one version of each variable in the path is if there exists an assignment that makes every clause true. If each item has weight 1, then the overall weight of the items in the path will equal the number of variables iff the 3SAT instance is satisfiable.

As another example, you can reduce from set cover. For each set that you want to cover, make a piece of the path be a choice that lets you chose any of the items in that set. Then to minimize the number items chosen in all, you have to cover all the sets with as few items as possible.


Subset of a bipartite graph with maximal number of minimal unmatched vertices Given a bipartite graph $G = (U \sqcup V, E)$ with sets of vertices $U$ and $V$ and edge set $E \subseteq U \times V$, a matching $M$ is a subset of $E$ whose edges have no common vertices: for all $(u, v)$ and $(u', v') \in M$, $u = u'$ or $v = v'$ implies $(u, v) = (u', v')$. A maximum matching is a matching containing the maximum number of edges. It is immediate that a maximum matching is a matching achieving the minimal number of unmatched vertices, where I say that $u \in U$ is unmatched in $M$ if there is no $(u', v') \in M$ such that $u = u'$, and likewise for $v \in V$. Hence, the minimal number of unmatched vertices in $G$ over all possible matchings of $G$, that I write $f(G)$, can be computed by finding a maximum matching, which can be done in polynomial time with, e.g., the Hopcroft-Karp algorithm.

I now consider the following problem: from a bipartite graph $G = (U \sqcup V, E)$, what is the maximum, over all subsets $U'$ of $U$, of $f(G_{|U'})$? By $G_{|U'}$ I mean the bipartite graph which is the restriction of $G$ to $U'$, namely $G_{|U'} = (U' \sqcup V, \{(u, v) \in E \mid u \in U'\})$.

Is this problem NP-hard, or can it be solved in PTIME? On the one hand it seems related to set cover or exact cover which are NP-hard, but on the other hand the subproblem of maximum matching is PTIME and maybe there is a clever way to identify what is the worst subset.

To motivate this problem, here is a rephrasing in terms of assignments of agents to tasks. $U$ is a set of tasks, $V$ a set of agents, and $E$ indicates which agents can perform which tasks. A matching is a way of assigning tasks to agents such that each agent does at most one task and each task is done by at most one agent. The cost measure is the number of unmatched vertices, namely the number of undone tasks plus the number of unoccupied agents. I want to know what is my worst possible cost in this sense, over all subsets of the tasks (think of $U$ as a set of possible tasks from which an arbitrary subset will be requested, and $V$ as a fixed set of agents that I cannot adjust but which I can allocate freely once a subset has been requested).

To see why this problem is not trivial, observe that choosing the empty subset $\emptyset \subseteq U$ yields a cost of $|V|$ (the cost of leaving all agents unoccupied), the complete subset $U \subseteq U$ yields a certain cost and may be the worst if e.g. $|U|$ is much larger than $|V|$, but in general my best solution may be to choose a subset of $U$ which retains the tasks than can be done by only few agents (so that many of them will have to remain undone as each of those agents can do only one task) but would not retain the tasks that can be done by otherwise unoccupied agents (so that those agents remain unoccupied and contribute to the cost).

If this problem is in PTIME, I am also interested to know if the following weighted version is also PTIME: each vertex and each edge has a weight, the cost of a matching is the sum of the weights of the unmatched vertices plus the sum of the weights of the retained edges, and I want again to find the subset of $U$ with the worst minimal cost in this sense. In the vocabulary of the assignment problem, this means that each task and each agent has an individual cost of remaining undone or unoccupied, and assigning a task to an agent is not free anymore but carries a certain cost indicated on the edge.

The problem is in $P$ by reducing the problem to submodular minimization.

Let $v(A)$ be defined as the size of the maximum matching in $G_{|A}$. $v$ is submodular. One way to see this is convert the problem to a max flow problem, and use the fact that the set function $c(U)=$ max flow from $U$ to $t$ defined over $V\setminus \{t\}$ is submodular.

I will use $f(A)$ to mean the $f(G_{|A})$ in your notation.

$f(A) = |A| + |V| - 2v(A)$. $|V|$ is a constant, so we can maximize over $f(A)-|V| = |A| - 2v(A)$, which is the same as minimize $g(A) = 2v(A)-|A|$. $g$ is a submodular function(difference of submodular and modular function), and you can apply any polynomial time submodular function minimization algorithm.

This can be extended to weighted case if weighted analogue of $v(A)$ is submodular.


Algorithms to synthesize optimal plans satisfying temporal logic constraints I know how NuSMV can be applied on a model to check if certain temporal logic statements are satisfied, particularly LTL. I also know of the LTL to BA conversion routines available online.

I am concerned with specific types of temporal logic constraints such as:

this task can begin after this task
this task can happen only in this time interval

I think this falls in LTL, STL domain. I am mostly interested in generating motion and task plans based on temporal logic constraints. NuSMV only seems to check the validity of certain statements on a model. I am more interested in software tool or codes that can lead to optimal plan synthesis based on my specification of LTL etc.?

I know there are research papers that solve this problem. But i do not know the theory of LTL, BA, etc. in depth so it is difficult to understand what these papers are doing and then recreate the process. Can someone tell some seminal papers or simply written paper easy to understand that explain how to build such algorithms. Even relevant sections of book are useful. Most books on model checking solve the inverse that is given a model does it satisfy this LTL constraint? I am interested in creating a model that satisfies a given LTL, STL constraint etc.? This technology is lying around so if someone can even suggest me some source codes that tackle such problems that will be even more helpful. I am not keen on understanding the theory if possible and would be happy to use someone else's software to develop plans and test them.

Maybe take a look at http://www.syntcomp.org/

This is a competition of tools solving the LTL synthesis problem (and some related problems).


Optimal value of a semidefinite program Is a local optimum value of a SDP always the global one?

If not, what are the conditions for that?

Here are a few more details for Suresh and Yoshio's answer. Following e.g. https://en.wikipedia.org/wiki/Semidefinite_programming, an SDP is of the form

$$\begin{array}{rl}
{\displaystyle\min_{X \in \mathbb{S}^n}}
& \langle C, X \rangle_{\mathbb{S}^n} \quad\text{subject to}\\
& \langle A^{(k)}, X \rangle_{\mathbb{S}^n} \leq b_k, \quad (\forall k \in \{1,\ldots,m\}) \\
& X \succeq 0
\end{array}$$
where $\mathbb{S}^n$ is the space of all $n\times n$ real symmetric matrices, $\langle C, X \rangle_{\mathbb{S}^n} = \sum_{ij} C_{ij} X_{ij}$, and $X \succeq 0$ constrains $X$ to be positive semi-definite.
The latter constraint is equivalent to (sometimes by definition)
$$y^T X y \ge 0~~~(\forall y\in \mathbb{R}^n).$$
(See e.g. here.)
Hence, the SDP is equivalent to
$$\begin{array}{rr@{}ll}
{\displaystyle\min_{X \in \mathbb{R}^{n\times n}}}
& \sum_{ij} C_{ij} X_{ij}  &\text{subject to}\\
& \sum_{ij} A^{(k)}_{ij} X_{ij} &\leq b_k,
& (\forall k \in \{1,\ldots,m\}) \\
& \sum_{ij} y_i y_j X_{ij} &\ge 0
& (\forall y\in \mathbb{R}^n)\\
& X_{ij} &= X_{ji} & (\forall i,j\in\{1,\ldots,n\}).
\end{array}$$

So, we can think of the SDP as minimizing (or maximizing) a linear function of the vector $X$ subject to (infinitely many) linear constraints on $X$.  Hence, it is an optimization problem with a convex feasible region and a linear objective.  So any local optimum is a global optimum.


Stronger notions of uniformizations? One gap that I was always aware that I don't really understand is between non uniform and uniform computational complexity where the circuit complexity represents the non uniform version and Turing machines is were things are uniform. I suppose "uniform" is a way to restrain the class of algorithms, e.g. not allowing an entirely different circuit for a problem with n variables compared to a problem of n+1 variables.

My questions are: 1) It there a description of uniformity just in terms of circuits, and 2) Is it possible to come with an even stronger form of uniformity and thus to give even more restricted notion of what effective (or restrained) algorithms in P are?

Late clarification: my intention in question 2 is about a restricted class of algorithms that "practically" has the same power as the class of polynomial algorithms.

I think the answer to you first question is negative: A circuit has a fixed number of inputs, and thus, IMO, we can only talk about "families" of circuits, rather than just one uniform circuit.

Regarding your second question, you may note that there are "uniform families of circuits," whose description is generated by a Turing machine. That is, let $\{C_n\}$ be a uniform family of circuit, and let $M$ be a Turing machine. Then, for each $n$, $[C_n] = M(1^n)$, where $[C_n]$ denotes the description of $C_n$.

There are several complexity classes below P, defined by uniform families of circuits. For example:

$\mathbf{NC}^i$ is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates and depth $O(\log^i n)$.


Notion similar to k-wise independence I want to construct a family of functions $H:\{0,1\}^n \rightarrow \{0,1\}$ with a property that is similar to k-wise independence. Specifically, I want $H$ to satisfy the following property. Let $k$ be some large natural number that is fixed. There exists a $d$ such that for every $n^k$ tuple of $n$ bit strings $x_1,...,x_{n^k}$,

$Pr_{h \leftarrow H}[  \cap_{j=2}^{n^k}  h(x_j)=0 \, \cap \, h(x_1)=1] \geq 1/n^d$

The additional (and crucial constraint) is that I want to be able to compute this family of functions using (a family of) circuits of size at most $n^3$ ($k$ is much bigger than 3). Note that if we don't have this constraint, then it is possible to do this (using family of circuits of size at least $n^e$).

Is it even possible for such a family to exist?

You can do it with the isolation lemma. Here are the important details (admittedly hastily written):

We'll imagine picking a hash function from $H$ as follows: first, pick $w_1^0,\ldots,w_n^0,w_1^1,\ldots,w_n^1$ uniformly and independently from  integer weights in $[1,4n]$. Then pick a threshold $T$ in $[1,4n^2]$ also uniformly and independently at random. Let $w(x) = \sum_i x_iw_i^1 + (1-x_i)w_i^0$. Now define $h(x)$ to be one if $w(x) \le T$ and zero otherwise.

We can then lower-bound the probability you're interested in by
$$\begin{align*}
P_{h\gets H}[ h(x_2) = \cdots = h(x_{n^k}) = 0, h(x_1) = 1 ] \\
&\ge P_{h \gets H}[ \forall i > 1 : w(x_1) < w(x_i), T = w(x_1) ] \\
&= P_{h \gets H}[ \forall i > 1 : w(x_1) < w(x_i) ] \cdot P_{h\gets H}[ w(x_1) = T \mid \forall i > 1 : w(x_1) < w(x_i) ]
\end{align*}$$
which is to say that $x_1$ is the unique minimum-weight element, and $T$ equals $w(x_1)$. We can easily compute the right factor
using the uniformity and independence of $T$:
$$P_{h\gets H}[ w(x_1) = T \mid \forall i > 1: w(x_1) < w(x_i) ] = \frac{1}{4n^2}$$
Bounding the other factor will involve the isolation lemma. The lemma tells us that
$$P_{h \gets H}[\exists j \forall i\ne j : w(x_j) < w(x_i)] \ge 1-\frac{2n}{4n} = \frac{1}{2}$$
By a union bound, the left hand side is at most
$$\sum_{j=1}^{n^k} P_{h \gets H}[\forall i\ne j: w(x_j) < w(x_i)]$$
From here, observe that the distribution of $w(x)$ doesn't depend on $x$. Hence, the terms in the above sum are all identical (they don't depend on $j$). Combining with the previous inequality and rearranging, we thus have
$$P_{h \gets H}[\forall i > 1 : w(x_1) < w(x_i)] \ge \frac{1}{2n^k}$$
Plugging this into our earlier work, we conclude
$$P_{h\gets H}[ h(x_2) = \cdots = h(x_{n^k}) = 0, h(x_1) = 1 ] \ge \frac{1}{8n^{k+2}}$$
Lastly, each $h$ can be computed very easily: a fixed $h$ needs $O(n\log(n))$ bits to store the $w_i^b$ and $T$, and then some circuitry to sum the appropriate weights and compare against $T$.


Higher-order algorithms Most of the well-known algorithms are first-order, in the sense that their input and output are "plain" data.
Some are second-order in a trivial way, for example sorting, hashtables or the map and fold functions: they are parameterized by a function, but they don't really do anything interesting with it except invoke it on pieces of other input data.

Some are also second-order but somewhat more interesting:

Fingertrees parameterized by monoids
Splitting a fingertree on a monotonous predicate
Prefix sum algorithms, again usually parameterized by a monoid or a predicate etc.

Finally, some are "truly" higher-order in the sense that is most interesting to me:

The Y combinator
Difference lists

Do there exist other nontrivial higher-order algorithms?

In attempt to clarify my question, under "nontrivial higher-order" I mean "using higher-order facilities of the computational formalism in a critical way in the algorithm's interface and/or implementation"

there are a bunch of algorithms that are "truly 2nd order" although usually not explicitly described in these terms.  Whenever we have sub-linear time algorithms, implicit is some kind of oracle access to the input, i.e. really treating the input as a function.

Examples:

(1) The Ellipsoid algorithms when working with a "separation oracle" (eg http://math.mit.edu/~vempala/18.433/L18.pdf )

(2) Submodular function minimization (eg http://people.commerce.ubc.ca/faculty/mccormick/sfmchap8a.pdf )

(3) The whole field of property testing is really of this form ( http://www.wisdom.weizmann.ac.il/~oded/test.html )

(4) Combinatorial auctions in the query model (eg  http://pluto.huji.ac.il/~blumrosen/papers/iter.pdf )


Reference for context-free grammar for Martin-Löf type theory Are the terms and the types of Martin-Löf type theory described by context-free grammars? Have such grammars been written down somewhere?

Generally, there will be one context-free grammar for both types and terms, and judgements will be used to identify those expressions which are types and which expressions are terms of a particular type.
This has been written down many, many times. For a pretty typical example, you could look at Abel, Coquand and Dybjer's LICS 2007 paper, Normalization by Evaluation for Martin-Löf Type Theory with Typed Equality Judgements.


Consensus clustering using set union I've already posted this question a while ago on MathOverflow, but to the best of my knowledge it is still open, so I'm reposting it here in the hope that someone might have heard of it.

Problem statement

Let $P$, $Q$ and $R$ be three partitions into $p$ nonempty parts (denoted by $P_h$'s, $Q_i$'s and $R_j$'s) of the set {$1,2,\ldots,n$}. Find two permutations $\pi$ and $\sigma$ that minimise $$\sum_{i=1}^p\left|P_i\cup Q_{\pi_i}\cup R_{\sigma_i}\right|.$$

Questions

1) What is the complexity of this problem (or of the corresponding decision problem)?

2) If the problem is indeed solvable in polynomial time, does it remain true for any number $k\geq 4$ of partitions?

Previous work

Berman, DasGupta, Kao and Wang (http://dx.doi.org/10.1016/j.ipl.2007.06.008) study a similar problem for $k$ partitions, but using pairwise $\Delta$'s instead of $\cup$ in the above sum. They prove that the problem is MAX-SNP-hard for $k=3$, even when each part has only two elements, by reducing MAX-CUT on cubic graphs to a special case of their problem, and give a $(2-2/k)$-approximation for any $k$. So far, I have not been able to find my problem in the literature, or to adapt their proof.

Easy subcases

Here are some subcases I've found to be solvable in polynomial time:

the case $k=2$;
the case $p=2$, for any $k$;

Moreover, when $k=3$, no two parts are equal and all parts have size $2$, we have the lower bound $3p+1$ (I don't know if it's tight).

The problem is NP-hard. Proof is by reduction from the following problem:

Given a tripartite graph $G$ with $N$ vertices in each part, are there $N$ vertex-disjoint triangles in $G$?

Here's the reduction: given an instance $G$ of the above problem, let $A_1$, $A_2$, $A_3$ denote the set of vertices in each part of $G$, and $E_{ij}$ be the set of edges between $A_i$ and $A_j$. Also, number the vertices in each part by $1,\dotsc,N$.

We construct an instance of your problem with $n = |E(G)| + M$, where $M$ is a large number (say, $M = 10 |E(G)|$), and $p = N + 1$.  The first $|E(G)|$ elements of $\{1,\dotsc,n\}$ correspond to the edges of $G$.  The partition $P$ is defined as follows: $P_i$ for $i=1,\dotsc,N$ is the set of edges that have the $i$th vertex of $A_1$ as one of their endpoints. Clearly these sets are disjoint and their union is $E_{1,2} \cup E_{1,3}$. $P_{N+1}$ is everything else, i.e., $E_{2,3} \cup \{|E(G)| + 1, \dotsc, |E(G)| + M\}$. Similarly, we define $Q$ using $A_2$ instead of $A_1$, and $R$ using $A_3$ instead of $A_1$.

Now, we claim is that this instance has a solution of cost at most $3|E(G)| - 3N + M$ if and only if $G$ has $N$ disjoint triangles. To see this, first notice that since $M$ is large, any solution that has cost less than $2 M$ must map $P_{N+1}$ to $Q_{N+1}$ and $R_{N+1}$. This already accounts for $|E(G)| + M$ of the total cost, so we are left with $2 |E(G)| - 3 N$. Now, note that the intersection of each $P_i$ and each $Q_j$ is at most one (and similarly for $P_i$ and $R_k$, and also for $Q_j$ and $R_k$). So, the objective function is minimized if all these intersections can be 1 at the same time. This corresponds to $N$ disjoint triangles in $G$.


an axiomatic framework for clustering by jon kleinberg may have a problem? In the paper An Impossibility Theorem for Clustering, Jon Kleinberg introduced an axiomatic framework for clustering and showed that his set of axioms are inconsistent. One of the axioms is the Richness Axiom: any partition of the input can be produced by some distance function.

My question is:

  Isn't the richness axiom unnatural?

The axiom implies that both trivial partitions: the one which puts all elements in the same cluster, and the one in which each cluster is a singleton, are both considered as valid clusterings. However, this is counter-intuitive in real life situations. In many (i guess most) real life situations we wouldn't have both these clusterings considered as valid simultaneously. so i guess the richness axiom could be modified. do we truly need  all partitions to be considered as valid clusterings?

I do not want to attempt a general definition of "unnatural", but I find your argument about the inherent incompatibility of the scale-invariance axiom and the richness axiom as defined in Section 2 of Kleinberg's NIPS paper.

The impossibility result in Section 3 of his paper is stronger, however, and can directly address your concern.

  Theorem 3.1 If a clustering function f satisfies Scale-Invariance and Consistency,
  then Range(f) is an antichain.

So you can consider weakening the richness axiom, e.g. by asking for all partitions with at least 2 parts, and as long as your set of partitions is rich enough to not be an anti-chain, the impossibility theorem goes through.

Hopcroft and Kannan have come up with a "natural" alternative to the richness axiom for which clustering is possible.  It is buried in their book Computer Science Theory for the Information Age, and described in a lovely teaser on the Gödel’s Lost Letter blog.


What does mechanism design constitute? (Game Theory) I've been reading about mechanism design and the field seems a little abstract, in that I cannot ascertain whether a certain approach towards solving games falls under mechanism design.

Let me clarify with the help of a specific example of an evolutionary game.

I have a population within which agents are either mutants or incumbents. The parameters to be decided are:

the fraction of the mutants ($\epsilon$)
the fitness $F$ of the agents

Now, if I came up with algorithms to define/calculate the above in such a way that the population ends up being evolutionarily stable, would my solution be called a mechanism?

Thanks

Mechanism design is basically just algorithm design, where you don't control the inputs: instead, you assume that the inputs are controlled by different agents, who each have their own set of feasible actions, and their own utility function over outcomes, and are acting to maximize their own utility (and not yours, as the mechanism designer). So you are constrained in how you can design your algorithm, because you have to design it in such a way so as to manage the incentives of the agents so that they will want to share their data with you. The classic example is designing an auction for a good in such a way so that the bidders will reveal to you how much they really value the good.

So the fundamental characteristic in mechanism design is that you have agents who will act independently of the mechanism to further their own goals. Its hard to tell from your description, but it sounds like you simply have an algorithms problem. Possibly your problem is to design an algorithm to compute an equilibrium of some sort, but this would not typically be thought of as mechanism design.


Bounds on size of self-concatenation of Finite Languages Given a finite language $L$ with $|L|$ number of elements, what is $|L^i|$ (the language $L$ concatenated with itself $i$ times)? If there is no exact result, is there an upper/lower bound?

Define concatenation of $L$ with itself to be as the classical definition: $LL = \{wx \space | \space w,x \in L\}$. Similarly, $L^n = \{a_1a_2...a_n \space | \space a_i \in L, \forall i \in [1, n] \}$.

Clearly, a non-tight upper bound is $|L|^i$ (each element in concatenation is unique) given that $|L| > 1$, but I would like to know if there is either a tight upper bound or tight lower bound.

You can show $ |L|^i $ is a tight upper bound by using the following language:

  $ L = \{ ab,aab,aaab,\ldots,a^kb \mid k \geq 1 \}. $

Any concatenation gives a new string. For a lower bound, I can suggest the following unary language:

  $ U = \{a,aa,aaa,\ldots,a^k \mid k \geq 1 \} $.

Then, $ U^i = \{ a^i,a^{i+1},\ldots,a^{ki} \} $ and so $ |U^i| = i|U|-i+1 $.

Emil's (Jerabek) comment appeared during writing my answer and so before posting my answer.


Reconstructing a tree from separator queries Suppose $T$ is an constant-degree tree whose structure we do not know. The problem is to output the tree $T$ by asking queries of the form: "Does the node $x$ lie on the path from node $a$ to node $b$?". Assume that each query can be answered in constant time by an oracle. We know the value of $n$, the number of nodes in the tree. The objective is to minimize the time taken to output the tree in terms of $n$.

Does there exist an $o(n^2)$ algorithm for the above problem?

Assume that the degree of any node in $T$ is at most 3.

What I know

Bounded diameter case is easy. If the diameter of the tree is $D$, then we can get a divide-and-conquer algorithm:

Any binary tree has a good separator that divides the tree into components of size no less than 1/3n.

Pick any vertex x. If it is a good separator label that and recurse.
Find all the 3 neighbors of x.
Move in the direction of the neighbor which has the largest number of nodes. Repeat Step 2 with the neighbor.

Since finding the separator takes at most $D$ steps, we get a $O(nD\log n)$ algorithm.

An $O(n\;\log^2 n)$ randomized algorithm. (moved from comments below)

Pick two vertices x and y randomly. With 1/9 probability they will lie on the opposite sides of a separator. Pick the middle node of the path from $x$ to $y$. See if it is a separator, if not do binary search.

It takes $O(n\;\log n)$ expected time to find the separator. So we get a $O(n\;\log^2 n)$ randomized algorithm.

Background. I learnt about this problem from a friend who works in probabilistic graphical models. The above problem roughly corresponds to learning the structure of a junction tree using an oracle which, given three random variables X,Y and Z, can tell the value of mutual information between X and Y given the value of Z. If the value is close to zero, we may assume that Z lies on the path from X to Y.

No.  The following simple adversary strategy implies that any algorithm to reconstruct an $n$-node tree requires at least $\binom{n-1}{2} = n(n-1)/2$ "betweenness" queries.

Arbitrarily label the nodes $0,1,2,\dots,n-1$.  The adversary answers all queries as though the tree is a star with vertex $0$ in the center; think of $0$ as the root and the other nodes as its children.

Between?(a,x,b)
    if x=0 return TRUE else return FALSE

Now suppose the algorithm halts after performing less than $n(n-1)/2$ queries.  Then there must be two vertices $y$ and $z$, neither equal to zero, such that the algorithm has not queried any permutation of the triple $(0,y,z)$.  If the algorithm claims that the tree is not a star with center $0$, the adversary reveals its input, proving the algorithm wrong.  The adversary then reveals that $x$ is actually the only child of $y$, proving the algorithm wrong again.

Update: Oops, just noticed the degree constraint.  Fortunately, this is not a major hurdle.  Replace node $0$ with your favorite binary tree, with the other $n-1$ nodes as leaves in some unknown order, and then reveal this subtree to the reconstruction algorithm.  Reconstructing the resulting $(2n-3)$-node binary tree still requires at least $n(n-1)/2$ queries.  Equivalently, reconstructing an $m$-node binary tree requires at least $(m+3)(m+2)/8$ queries.  (I'm sure a more subtle construction would improve the constant.)  As Jagadish points out, this generalization doesn't work; queries about internal nodes in the tree impose an ordering on the leaves, which reduced the number of necessary queries.


Regarding Elements of Programming, is a uniqueness of the value type sufficient for equality testing? I have just started on the book Elements of Programming (2019) and after thinking about the definitions for value types in chapter 1, that in principle seem to link meaning (the abstract entities of a species) to a bit representation, I started wondering about the following quote (Section 1.2 "Values" p. 3):

  Lemma 1.1 If a value type is uniquely represented, equality implies representational equality.

  Lemma 1.2 If a value type is not ambiguous, representational equality
  implies equality.

  If a value type is uniquely represented, we implement equality by testing that both sequences of 0s and 1s are the same. Otherwise we must
  implement equality in such a way that preserves its consistency with the
  interpretations of its arguments.

With the definition of equality in the book being:

  Two values of a value type are equal if and only if they represent the
  same abstract entity. They are representationally equal if and only if their
  datums are identical sequences of 0s and 1s.

Doesn't this imply, that implementing equality by testing for representation equality is impossible for ambiguous value types?
If that is the case, shouldn't the book require a value type to be uniquely represented and unambiguous, in order to implement equality?
If a given value type is ambiguous, one could resolve the ambiguous-ness per contract, such that the comparison checks for equality under the assumption that the passed parameters are never ambiguously refer to different abstract entities, though that would probably not be enforceable at all.

I am probably nitpicking when reading that paragraph :)

Looking at the book, they give a really good example where representational equality doesn't imply equality. You have two unordered collections, which are equal if after sorting and removing duplicates, they are representationally equal. For example

Collection A:    5 5 2 3 1 1 1 1
Collection B:    1 5 5 5 3 3 3 2

Are representationally unequal. But if you sort them and remove duplicates...

Collection A:    1 2 3 5
Collection B:    1 2 3 5

And are now representationally equal. In this sense, they're originally representationally unequal, for the sake of easier processing perhaps. However, once you perform the operation which determines equality, they are indeed equal.

So no, they don't have to be representationally equal to be equal.


Amortized analysis of red-black trees Is there an analysis of red-black trees using amortized analysis? I saw it mentioned somewhere as an example of amortized analysis but all the proofs that I know use a global approach ("black height") to demonstrate the O(log n) runtime of individual operations.

You may need to look at this report:
https://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

Each individual operation takes $O(\log n)$ but when you apply amortized analysis to a sequence of operations, you get something interesting.

Directly from this report:
"However, amortized analysis can be used to show that any sequence of $m$ insert and delete operations causes $O(m)$ structural modifications in the worst case (Cormen et al. p.428). It can similarly be shown that the total time for  $m$ consecutive insertions in a tree of $n$ nodes is $O(n + m)$ (Tarjan 1985)."


Identifying useless edges for shortest path Consider a graph $G$ (the problem makes sense both for directed and undirected graphs). Call $M_G$ the matrix of distances of $G$: $M_G[i, j]$ is the shortest path distance from vertex $i$ to vertex $j$ in $G$ for a certain fixed aggregation function (for instance $+$ or $\max$).

I say that a subgraph $G'$ of $G$ (with same vertex set) is sp-equivalent to $G$ if $M_G = M_{G'}$. In other words, removing edges to go from $G$ to $G'$ does not change the length of shortest paths; the removed edges are not required for any shortest path.

In general there is no single sp-equivalent subgraph of $G$ that is minimal for inclusion. For instance, if $G$ is undirected and all edges have weight $0$, any spanning tree of $G$ is a minimal sp-equivalent subgraph (indeed, any edge in a cycle could be removed, but disconnecting a vertex pair obviously changes the distance). However I can still call edges of $G$ useless if they are in no minimal sp-equivalent subgraph, necessary if they are in all minimal sp-equivalent subgraphs (i.e., in their intersection), and optional if they are in some of them (i.e., in their union).

My first question is: Do these notions have a standard name?

My second question is: What is the complexity of classifying the edges of $G$ in this fashion, depending on whether $G$ is undirected or directed, and on the aggregation function?

(For instance, for $G$ undirected and for $\max$, the minimal sp-equivalent subgraphs are spanning trees of minimum weight, so at least if all edge weights are different the classification is easily computed by computing the unique minimum spanning tree, but in general I do not know how things work.)

If you are looking for a way to name (or alternately characterize) these edges you call "useless" and "necessary," you could refer to them as the edges with betweenness centrality =0 and =1, respectively. Every edge can be classified as having =0, =1 or in(0,1) betweenness measure in time of all-pairs-shortest-paths.

This is a well-studied measure of network edges, and there are fast algorithms for updating all the edges' centrality scores upon edge deletions (but I'm not sure about other perturbations).

A centrality function is built-in to mostly every network analysis I've seen, and there is a definition that applies to directed graphs as well:

(edit: the link I gave initially only discussed node betweenness centrality, but here is the only wikipedia article I can find that discusses edge-betweenness centrality:
http://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm
Still, edge-betweenness is a standard measure that can usually be found in network analysis packages.)


Is perfect matching for bipartite graph with no cycles unique? Given a balanced bipartite graph that satisfies Hall's theorem (is non singular) then it shown that it has at least one perfect matching.

My question is if the balanced bipartite graph is also acyclic then is the perfect matching unique?

If so (I am almost certain it is), can you point me to a cite-able source? I was not able to such a document.

If the graph is acyclic, which implies that it is also bipartite, then the perfect matching is unique by the following algorithm:

While the graph is not empty, pick a leaf vertex $u$ (which exists because the graph is acyclic) add the edge between $u$ and its unique neighbor $v$ to the matching and then remove $u$ and $v$. If at some point graphs without incident edges are produced, then there is no perfect matching.

This is probably folklore knowledge which would mean that there is no citable source.


Does randomness buy us anything inside P? Let $\mathsf{BPTIME}(f(n))$ be the class of the decision problems having a bounded two-sided error randomized algorithm running in time $O(f(n))$.

Do we know of any problem $Q \in \mathsf{P}$ such that $Q \in \mathsf{BPTIME}(n^k)$ but $Q \not \in \mathsf{DTIME}(n^k)$?
Is its non-existence proven?

This question was asked on cs.SE here, but did not get a satisfactory answer.

Problem: An array $A[1..2n]$ consists of $n$ 1s and $n$ 0s. Find an $i$ such that $A[i]$ is 1.

You are allowed to query 'Which number is present in $A[i]$'? Each query takes constant time.

Solution:
Randomized Algorithm: Pick a random index $i$ and check if $A[i]$ is 1. Expected number of queries is 2, but any deterministic algorithm must make at least $n$ queries. Therefore, the randomized upper bound is strictly better than the deterministic lower bound in this model.

This is an example from query complexity which Tsuyoshi was referring to in the comment.


Has a proof checker bug ever invalidated a major proof? Most (all?) proof assistants have soundness bugs fixed on occasion.  However, from those I've seen these bugs are usually difficult to come across unintentionally, and results proved before the bug is fixed generally hold up after the fix.

Three questions, in order of strength:

Has such a soundness bug fix ever caused a major proof to fail, without modifying the proof?
If (1) is true, were major modifications ever required to fix the proof?
If (2) is true, has anyone proved a wrong major theorem due to a soundness bug?

I'll leave the definition of "major" up to others.

To my knowledge, no machine checked proof of a complex mathematical development has ever been retracted.

As Andrej points out though, it occasionally happens that soundness-breaking bugs do crop up in these systems (though usually not silently, as Andrej suggests), and the fix to that bug involves some changes to existing proofs, or, more likely, of the standard library of the proof system involved.

Some examples of such library breaking proofs in Coq:

https://coq.inria.fr/bugs/show_bug.cgi?id=4294

https://sympa.inria.fr/sympa/arc/coq-club/2013-12/msg00119.html

It's hard to say whether the established proofs depended on the inconsistency, since after the fix, they required minor tweaks to be accepted by the proof checker. But this happens at each non-trivial update!

My personal opinion is that such mistakes are unlikely to happen, since the paper proof needs to be well polished before machine formalization can even be attempted.

Inconsistencies in proof frameworks usually require the heavy use of strange combinations of esoteric features, and so very rarely crop up "by accident".


Paths in a weighted line arrangement This is a followup to my followup to David's question.  This question admittedly leaves the original motivation far behind, but it might provide some useful intuition.

Suppose we are given a set of n non-vertical lines, each with a (possibly negative) real weight.  The lines partition the planes into convex polygonal cells; the cell complex is usually called an arrangement.  Define the weight of a cell to be the sum of the weights of the lines that lie above it.  Let p be a point that lies above every line, and let q be a point that lies below every line.

  Suppose there is a path between p and
  q that intersects only cells with
  non-negative weight.  Is there a path
  from p and q that intersects only
  cells with non-negative weight and
  crosses each line exactly once?

Equivalently: Suppose we are given a set of points in the plane, each with a (possibly negative) real weight.  Now imagine continuously moving a straight line, starting above all the points and ending below all the points, such that the line is never vertical.  Call the motion legal if at all times, the total weight of the points above the line is non-negative.

  If there is a legal motion, must there
  be a legal motion where the moving
  line passes over each point exactly
  once?

(It is easy to find such a path/motion or determine that none exists in $O(n^2)$ time.)

The answer is no, me think.

To see why consider two lines that are a perturb copy of each other that intersect at a point p. By giving one line weight 1, and one line weight -1, we created a tiny wedge where the path can not go through. Think about this wedge now as a ray. Now, using a collection of such rays, we can create the following configuration:

------------------------

             -----------------------------------

-------------------------

             --------------------------------

--------------------------

That is - interleaving horizontal rays. Now, the path must wiggle between these rays in the natural way. It is now trivial to add an almost vertical ray that its tail (i.e., non ray part) intersect all the horizontal rays. The path must intersect the two lines defining this ray as many times as we want.

Here is a figure:

(source: uiuc.edu)

(Ipe source.)

The solution is slightly more complicated because these rays open up. By adding the two rays on the sides, one guarentees that only the region of interest is really relevant.


Space complexity for multiplying $m$ matrices Suppose you have $m$ $n$ by $n$ matrices $M_1,M_2,\dotsc,M_m$, and you want to calculate their product $\prod_{i=1}^{m} M_i$.

The naive method use $m \cdot poly(n)$ times but needs $poly(n)$ memory. I am wondering can there be any algorithm with $polylog(n,m)$ memory but still $m \cdot poly(n)$ or $poly(n,m)$ running time. It sounds like an old problem but I couldn't find any reference.

Note that using the divide and conquer technique (like in Savitch's theorem), we can achieve $polylog(n,m)$ memory and $m \cdot n^{O(\log m)}$ running time.

Letting m be [number of vertices minus 1] and letting each matrix be

[the adjacency matrix of the result of giving the vertex t a loop]

gives a reduction from st-connectivity to your problem, so no such algorithm is known.


Algorithm for "Swiss teams" (bridge) I am writing on software that has to create matches between teams of bridge players. Each round a new series of matches is calculated. The algorithm has to meet these two criteria:

Each round every teams must meet a team against which it has not played before.
The teams that play against each other should have as close a total score as possible.

This method is known as "Swiss teams". Can someone point me in the right direction?

Read some more about the Swiss-tournament system

Specifically this looks like the Stable Roommate Problem (SRP). Alternate the order of preference based on position in a list sorted by distance from the total score. I.E., imagine a list with the following scores:

1, 3, 18, 19, 20, 21.

Then the preference list would be:

1: 3, 18, 19, 20, 21
3: 1, 18, 19, 20, 21
18: 19, 20, 21, 3, 1
19: 18, 20, 21, 3, 1
20: 19, 21, 18, 3, 1
21: 20, 19, 18, 3, 1

For more accuracy use the Stable Roommate With Ties (SRT) algorithm.

The way Swiss Teams differs from SRP is that not everyone will be listed. That is, if the teams with scores 20 and 18 have played each other already then neither list each other as preferences. It's possible that SRP will still give the correct result but it remains to be verified.


Set query in a universe with overlapping sets Suppose we have a universe $U$ of $n$ items $u_1,u_2,u_3,...,u_n$.
And a collection of sets (no restriction on being disjoint or exhaustive etc.)
which cover some items. Size of each set is bounded by some parameter $k<n$.
We need to perform the following update and query efficiently.

Update:
1- Add a new set to the collection having some elements of $U$.

2- Delete any existing set from collection.

Query:
Given two vertices, does there exist a set which has both these vertices.

A trivial way would be to maintain a 2D matrix with each $M(i,j)$ storing number of sets containing both $i$ and $j$. Update would be done in $O(k^2)$ by incrementing $M(i,j)$
for all pairs of vertices in set S_i. The query can be done in$ O(1)$ time.

I am looking for some solution with o(k^2) update time and poly log query time..

One can reverse the roles of elements and sets. This can be seen by considering a Boolean matrix of size $m\times n$ where there are $m$ sets and $n$ is the size of the universe. The $i$th row corresponds to the characteristic vector of the $i$th set. Transposing this matrix reverses the roles of sets and elements ($n$ sets and $m$ elements).

Now the question of whether there exists a set containing two items is the same of asking if two sets intersect (after reversing the roles). In a paper that has recently been accepted to WADS 2015, (arxiv version here. see Theorem 3), we show various tradeoffs for the fully dynamic set intersection problem. Since adding/deleting a set corresponds (after role reversal) to adding/deleting an element to or from a bunch of sets, then in terms of the question in mind the update time would be $S\cdot N^{1-\epsilon}$ and the query time is $N^\epsilon$, where $S$ is the size of the set, $N$ is the sum of the sizes of all of the sets, and $0\leq \epsilon\leq 1$. Notice that different points on this tradeoff curve use a different amount of space, specifically $O(N^{2-2\epsilon})$ words. In particular, for constant query time, the space usage is $O(N^2)$ words and the update time is $O(N)$.

However, for the particular scenario where one is interested in poly log query time, we have a preprint (arxiv version here) that in particular shows that unless the 3SUM conjecture is false, if one is interested in sub-polynomial query time, then the constructing of a static data structure for disjointness queries requires $\Omega(N^{2-o(1)})$ time. This immediately implies a lower bound for the incremental version of the problem, where one is only allowed to add elements to sets. In particular, since the total number of elements in sets, counting multiplicity, is $N$, each element that is being added must spend $\Omega(N^{1-o(1)})$ time.

As such, a (polynomially) more efficient update time does not seem likely, even when allowing poly-log query time.


Alternating automata In the paper Fast LTL to Buchi Automata Translation (2001, Gastin and Oddoux)  the authors, while defining co-Buchi alternating automata define  $\Sigma’= 2^\Sigma$ where $\Sigma$ is the alphabet.
They say that because of this the transitions that differ only by action can be gathered.

What does this statement exactly mean? Any pointers will be helpful.

thanks

Expanding on Markus' answer a bit, note that the alphabet $\Sigma$ is in turn the powerset $2^{Prop}$ of the set $Prop=\{p_1,\dots,p_k\}$ of atomic propositions, i.e. it represents the set of valuations $a:Prop\to\{T,F\}$ of the $p_i$.

In the LTL formula, most boolean subformulas involve only a few of the propositions. In the translation, any such subformula corresponds to the set of all valuations $a\in\Sigma$ satisfying it, which is typically large. Using $\Sigma'$, you still only have one transition.

For example, Figure 1 in the paper shows an automaton with transitions labelled simply by $p$ or $q\wedge\neg r$ (where $p,q,r$ are the propositions from the formula). Using $\Sigma$, for the first you would instead have four transitions labelled $\{p\},\{p,q\},\{p,r\},$ and $\{p,q,r\}$.


Which $AC^0$ problems are not "truly feasible"? Neil Immerman's famous Picture of The World is the following (click to enlarge):

His "Truly feasible" class includes no other class; my question is then:

  What is an AC0 problem which is considered to be unpractical, and why?

If you want an example of an AC0 function that requires depth $d$, and cannot be computed by AC0 circuits of depth $d-1$, then try the Sipser functions $S^{d,n}$. The superscript $d$ is depth needed for a polynomial-size AC0 circuit. With depth $d-1$, the circuit would need exponentially many gates.

So computing $S^{d,n}$ for $d = 10^{10^{100}}$ would not be "truly feasible."

EDIT: Your question also asks why this would not be feasible. I guess the reason is that $10^{10^{100}}$ is more than the number of atoms in the visible universe.


Communicating a string of zeros and ones quantumly Alice wants to communicate an arbitrary $x \in \{0 ,1\}^n$ to Bob. Alice and Bob communicate
in rounds, in each round Alice (or Bob) applies a unitary transformation on his/her part and
transmits a qubit to the other side, until at the end Bob measures his state and tries to infer
x. The protocol is successful if for every $x \in \{0,1\}^n$ Bob succeeds with probability 1. Let
$n_A / n_B$ be the number of messages sent by Alice / Bob respectively.

Now I want to show that for any successful protocol we must have $n_A \geq  \lceil n/2 \rceil $, and $n_A+n_B \geq n$, and I need to show that the same argument above follows also for p-successful protocols, i.e if there's a p-successful protocol then the ineqaulities above should also follow for this protocol; a p-successful protocol is one in which Bob succeeds with probability p.

Any hints or prefereably bibliography where this or similar problem is disscused?

Thanks.

This paper proves the results you have described:

  Ashwin Nayak and Julia Salzman. Limits on the Ability of Quantum
  States to Convey Classical Messages. Journal of the ACM, 53(1):
  184-206, 2006.


Start learning proof complexity I recently started to read a lot about proof complexity and have been really enjoying what I have been reading. I would really like to learn more about this, but I am having difficulty finding some good beginner material to start with. Would anyone be able to recommend some basics?

It depends on what kind of a "beginner" level you wish to have. I don't think there is a real good undergraduate level text on proof complexity (this is probably true for most specialized sub-areas in complexity). But for a beginner (graduate level) sources, I would recommend, something like understanding well the basic exponential size lower bound on resolution refutations of the pigeonhole principle (via random restrictions, width-size tradeoff and feasible interpolation), and to expand from that point further. This could be achieved (approximately) as follows:

Stasys Jukna, Extremal Combinatorics With Applications in Computer Science, 2001, Springer-Verlag, Section 4.8.
Eli Ben-sasson and Avi Wigderson, Short Proofs are Narrow - Resolution made Simple (2000), JACM.
P. Beame and T. Pitassi, Propositional proof complexity: Past, present, and future, Current trends in theoretical computer science: Entering the 21st century (G. Paul, G. Rozenberg, and A. Salomaa, editors), World Scientific Publishing, 2001, pp. 42--70.
Pavel Pudlák, Lower bounds for resolution and cutting planes proofs and monotone computations, The Journal of Symbolic Logic, vol. 62 (1997), no. 3, pp. 981-998.

You can also consult the more self contained and lengthy text:

Peter Clote and Evangelos Kranakis, Boolean Functions and Computation Models (Chapter 5)

For the more logical side of proof complexity, as Kaveh suggested, you can start reading the first chapters of:

Stephen Cook and Phuong Nguyen, Logical Foundations of Proof Complexity (Perspectives in Logic, Cambridge Press, 2010).


How well can we do with this variable assignment problem? Given in this problem is a set of values $0 \le c_{a,b} < n$, where $0 \le a < n$ and $0 \le b < n$.

The problem is to find the following sum as quickly as possible:

$$\sum_{a,b}{c_{a,b}x^a y^b} \bmod n$$

Here $x$ and $y$ are also assumed to be integers modulo $n$.

I'd like to know what the best method/approach is to solving this problem, and what kinds of worst-case behavior we can expect to get the sum.

Are there any similar problems whose solutions may help with this?

SOME NAIVE IDEAS

There are $n^2$ different constants and only $n$ different possible assignments for each $c_{a,b}$, so it seems that grouping some of the coefficients together is the best way to go.  However, beyond simple ideas, I'm not sure what will work best.  I'm hoping I can get some good suggestions.

MOTIVATION

My motivation for tackling this particular problem is that its solution may help improve the bounds of #3-SAT by some small degree.  However, the relation between the two is fairly complicated.

Assuming that the $c_{a,b}$ values appears in a nicely ordered way, you can use Horner's rule to evaluate the polynomial in $O(n^2)$ arithmetic operations. As mentioned by frogeyedpeas, you can't expect beating $n^2$ because it is the size of the input.

Note that if you are interested by the number of bit operations then you need to multiply this by the elementary cost of multiplication (for numbers of the size considered in your problem).

It you want to beat the $n^2$ bound, you need the $c_{a,b}$ to be represented in a more compact/structured way.


Algorithmic game theory - nonstandard equilibrium concepts? I'm beginning my studies of algorithmic game theory, and it seems that the equilibrium concept usually taken is that of a fixed point in a graph. However, have people looked at alternative equilibrium concepts, such as limit cycles? I can imagine that a "tight" limit cycle - that is, a cycle in the graph of very small length - could be considered something that's "close" to the standard definition of equilibrium.

I've tried digging around Google Scholar, but to little avail.

You may be looking for something like Sink Equilibria (start from e.g. http://arxiv.org/abs/0902.0382 ) -- but the cycle length is not considered.


Why is the "free store" memory called the "heap"? Does it have anything to do with the heap data structure, for example the Buddy blocks implementation, or does it only take the literal English meaning of the word (a big pile)?

I know heap memory is more practical than theoretical, but there's no Stack Exchange for "Practical Computer Science" yet.

I don't think it has anything to do with the data structure.
It's just the opposite of the stack, which carefully orders its elements and doesn't allow them to be read or written except at the top.


Complexity of testing for a value versus computing a function In general we know that the complexity of testing whether a function takes a particular value at a given input is easier than evaluating the function at that input.  For example:

Evaluating the permanent of a nonnegative integer matrix is #P-hard, yet telling whether such a permanent is zero or nonzero is in P (bipartite matching)
There are n real numbers $a_1,...,a_n$, such that the polynomial $\prod_{i=1}^{n}(x - a_i)$ has the following properties (indeed most sets of $n$ real numbers will have these properties). For given input $x$, testing whether or not this polynomial is zero takes $\Theta(\log n)$ multiplications and comparisons (by Ben-Or's result, since the zero set has $n$ components), but evaluating the above polynomial takes at least $\Omega(\sqrt{n})$ steps, by Paterson-Stockmeyer.
Sorting requires $\Omega(n \log n)$ steps on a comparison tree (also $\Omega(n \log n)$ steps on a real algebraic decision tree, again by Ben-Or's result), but testing if a list is sorted only uses $n-1$ comparisons.

  Are there general conditions on a polynomial that are sufficient to imply that the (algebraic) complexity of testing whether or not the polynomial is zero is equivalent to the complexity of evaluating the polynomial?

I'm looking for conditions that do not depend on knowing the complexity of the problems beforehand.

(Clarification 10/27/2010) To be clear, the polynomial is not part of the input.  What that means is that, given a fixed family of functions $\{ f_n \}$ (one for each input size (either bitlength or number of inputs)), I want to compare the complexity of the language/decision problem $\{ X : f_n(X) = 0 \text{ where } n \text{ is the "size" of } X \}$ with the complexity of evaluating the functions $\{f_n\}$.

Clarification: I am asking about the asymptotic complexity of evaluating/testing families of polynomials.  For example, over a fixed field (or ring, such as $\mathbb{Z}$) "the permanent" is not a single polynomial, but an infinite family $\{perm_{n} : n \geq 0 \}$ where $perm_{n}$ is the permanent of an $n \times n$ matrix over that field (or ring).

Makowski's "Algorithmic uses of the Feferman–Vaught Theorem" is possibly relevant. He defines polynomials by summing over MSOL-definable structures on graphs and shows that they are tractable to evaluate when graphs are tree-width bounded.

This doesn't say much about difference in complexity of testing/evaluation beyond being FPT. Testing for a value means asking if there exists a setting of variables such that given MSO2 formula on given graph evaluates to true, whereas evaluating involves enumerating over satisfying assignments of MSO2 formula. This seems to be related to the question of how complexity of counting SAT relates to complexity of SAT.

Edit 10/29
Another useful concept might be to look into Uniform Difficult Point Property. Apparently polynomials with this property are either easy to evaluate in all points, or hard to evaluate almost at every point. Makowski gives some references on slides 46-52 -- http://www.cs.technion.ac.il/admlogic/TR/2009/icla09-slides.pdf


Question about "typical set" in Shannon's source coding theorem I was following the textbook by David Mackay: Information theory inference and learning algorithms.

I have question on asymptotic equiparition' principle:

  For an ensemble of $N$ $i.i.d$ random variables $X^N=(X_1,X_2....X_N),$ with $N$ sufficiently large, the outcome $x=(x_1,x_2...x_N)$ is almost certain to belong to a subset of $|A_x^N|$ having only $2^{NH(x)}$ members, with each member having probability  "close-to" $2^{-NH(x)}$.

And then in the textbook, it also says that typical set doesn't necessarily contain the most probable element set.

Because the "smallest-sufficient set" $S_{\delta}$ which is defined as:

  the smallest subset of of $A_x$ satisfying  $P(x\epsilon S_{\delta})\ge 1-\delta $, for $0\leq{\delta}\leq1. $  In other words, $S_{\delta}$ is constructed by taking the most probable elements in $A_x$, then the second probable......until the total probabily is  $\ge1-{\delta}$.

My question is, as $N$ increases, does $S_{\delta}$ approaches typical set such that these two sets will end up being equivalent of each other? If the size of the typical set is identical to the size of $|S_{\delta}|$,  then why are we even bother with $S_{\delta}$? Why can't we just take the typical set as our compression scheme instead?

$S_δ$ is not a subset of the typical set. As you mentioned, the most probable element is a member of $S_δ$ but it is not necessarily a member of the typical set.

The only reason to use the typical set instead of $S_δ$ is to make the proof of the source coding theorem easier. (See the paragraph at the top of page 84 in your book.) The typical set along with the asymptotic equipartition property makes it easy to count the size of the typical set and to put bounds on the probability of each element in the set. This is not so easy to do when working with $S_δ$


Status of Cerny Conjecture? A DFA has a synchronizing word if there is a string that sends any state of the DFA to a single state. In ‘The Cerny Conjecture for Aperiodic Automata” by A. N. Trahtman (Discrete Mathematics and Theoretical Computer Science vol. 9:2, 2007, pp.3-10), he wrote,

  Cerny conjectured in 1964 that every
  n-state synchronizable DFA possesses a
  synchronizing word of length at most
  $(n-1)^2$.

He also wrote, "in the case when the underlying graph of the aperiodic DFA is strongly connected, this upper bound has been recently improved by Volkov who has reduced the estimation to $n(n + 1)/6$.

Does anybody know the current status of Cerny conjecture?
And in which paper Volkov obtained the result n(n+1)/6 ?

Thanks for any pointer or link.

Trakhtman has a bibliography on the problem, which is apparently kept up to date; so I suppose Černý's question remains unresolved until today. The same is stated in Volkov's recent survey (LATA 2008) linked from the wikipedia article cited in the question. There you find pointers to some partial results, for example, for which subclasses of regular languages the conjecture is known to be true. Even more recent is a research paper by Ananichev, Gusev & Volkov (MFCS 2010) on a related topic, where they confirm that Černý's conjecture is still open now (at least as of May 2010).


Minimal generator for a set of sets Is this a known problem?

Given a set of sets $S$ find a set of sets $B$ s.t. each set in $S$ can be obtained through unions of some sets in $B$. The set $S$ is already a solution but the objective is to find the smallest $B$.

For instance $\{\{a,b\}, \{c\}, \{a,b,c\}\}$ can be obtained from $\{\{a,b\}, \{c\}\}$.

Since it's somewhat similar to set-cover, I suspect it's NP-hard.

Additional remark: $B$ does not have to be a subset of $S$.

A decision variant, without the minimality condition, asking whether there is a set $B$ of size $n$ is called the set basis problem [SP7] in Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson. The NP-completeness of it was proved by Stockmeyer.


How is Real-Time Computing defined? How is real-time computing defined in theoretical computer science (e.g. complexity theory)? Are there complexity theoretic models designed to capture the real-time computation?

Like many things in life, there is no one definitive definition. For an algorithm to run in real-time, some people on the theoretical side say that this means it will take constant time per 'something.' Now you have to decide what a 'something' is but let me give a concrete example. Let's say that the input arrives one symbol at a time and you want to output the answer to a query as soon as a new symbol arrives. If calculating that output takes constant time per new symbol then you might say the algorithm runs in real-time.    An example of this is real-time exact string matching, which outputs whether a pattern matches the latest suffix of a text in constant time per new symbol. The text is assumed to arrive one symbol at a time.

However, an engineering answer will be less worried about "constant time" and more worried about it happening fast in practice and in particular fast enough that the result can be used by the time it is needed. So for example in robotics, if you want to play ping-pong it is useful for the robot to be able to work out where the ball is and move to hit it as the ball arrives, and not after the ball has passed. The asymptotic time complexity of the underlying algorithms will perhaps be of less interest there than just the observation that the code works out the location quickly enough.  To give another example, if you want to render video and can do it at 25 frames per second then it is reasonable to say that the rendering is happening in real-time.

So basically you have two answers. One for the theoreticians/algorithmists and one that just says that you are doing the work as you need it on the fly.

EDIT: I should probably add that one extra feature one should require of even a constant time algorithm is that the time complexity is not amortised.  In this context, real-time == unamortised constant time.


formal languages: what does R-trivial mean? What is an R-trivial language? What is an R-trivial monoid?

Context: Formal languages. Afaik, R-trivial languages is a subset of the starfree languages.

I mostly have background in formal languages and automata theory but not so much with the syntactic monoid characterization. So it would be nice to give a basic definition with maybe a small example of such a language.

(In order to support multiple QA-sites because I don't want to have any QA-site stay behind and to have that question also represented there, I have also posted this question on these other sites: stackoverflow.com, math.stackexchange.com, mathoverflow.net. In general I am against cross-posting but in this case, as they all have the same goal to be a complete reference of questions in the specific area, having the question cross posted is the best thing you can do.)

A semigroup $S$ is $R\text{-trivial}$ iff $a \: R \: b \Rightarrow a = b$ for all $a, b \in S$ where $R$ is Green's relation $a \: R \: b \Leftrightarrow aS^1 = bS^1$. The set of $R\text{-trivial}$ monoids forms a variety which can be ultimately defined by the equations $(xy)^n x = (xy)^n$.

A language is $R\text{-trivial}$ if its syntactic monoid is $R\text{-trivial}$. This variety of languages is alternatively defined as the set of all languages that can be written as a disjoint union  of languages of the form $A_0^* a_1 A_1^* a_2 \ldots a_n A_n^*$ where $n \geq 0$, $a_1, \ldots, a_n \in A$, $A_i \subseteq A \setminus \{a_{i+1}\}$ for $0 \leq i \leq n-1$. Another definition given in [Pin], which I'm not familiar with, uses the so-called automates extensifs ("extensive automata"). You can find more results about those languages in [Pin]. There is an English version of this book, I've never read it but I'm pretty sure that you can find the same content.

For the sake of completeness, here is an example of an (artificial) $R\text{-trivial}$ language: $\{b\}^* a \{a,c\}^* b \{a\}^* b \{a,b,c\}^* \cup \{d\}^* \cup abcd$. You can build other examples with the previous definitions. Note that all of the properties of varieties of languages hold for $R\text{-trivial}$ languages, therefore they are closed under union, intersection and complementation. It should help to build more complicated languages.


Running time of randomized algorithms This is a very basic doubt, something I've always swept under the carpet.

The definition of BPP allows a machine access to random bits, which are 0 and 1 with equal probability. Many a randomized algorithms need to sample points from a space/set of size $n$, where $n$ need not be a power of two, and sampling from such a space using random bits would typically yield Las Vegas sort of behaviour as far as running time is concerned i.e. at best, the expected running time can be bounded by polynomial.

Am I missing something here (like there being a way to sample from arbitrary sets using random bits without having to make the running time expected polynomial time), or is this something that is swept under the carpet for convenience sake i.e. BPP actually requires only expected running time being polynomial?

Use $k=\lceil\log n\rceil$ random bits to get a random number $r$ between $0$ and $2^k$.  With probability at least $\tfrac{1}{2}$, $0\leq r < n$ so use that as your answer; otherwise, try again. If you've not succeeded after $t$ attempts, reject your input.  The probability of this happening is at most $2^{-t}$, which can be made as small as you like and is a component of the probability that the machine gives the wrong answer.


Fast treewidth algorithms I would like to compute the treewidth of a graph. There are really good heuristics for other NP-hard graph problems such as VF2 for subgraph isomorphism, with code available in igraph for example.   I have tried them on my graphs and I find they run very fast for my data.

Are there any fast algorithms for treewidth calculation in a similar vein?

As far as I know, the state of the art is what is reported in

Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos (2012), "On exact algorithms for treewidth", ACM Transactions on Algorithms 9 (1): A12, doi:10.1145/2390176.2390188.

The methods described there include an implemented $O^*(2^n)$ algorithm with some heuristic optimizations to make it faster in practice.


Is there a gadget that reduces generalized geography to undirected graphs? The directed Generalized Geography game is well-known to be PSPACE-complete, however, I could not find anything for the undirected version. I saw that in Hans L. Bodlaender, Complexity of path-forming games, Theoretical Computer Science, Volume 110, Issue 1, 15 March 1993, Pages 215-245 (thx to Marzio De Biasi for the link) it is posed as an open problem. Is it still open?

In fact, I wonder if there is a simple gadget that we can put in the place of every directed edge to make a straight-forward reduction from the directed version. Is it known that no such gadget can exist?

Undirected (Vertex) Geography is in P. In particular, the game on graph $G$ with starting vertex $v$ is a win for player 1 if and only if every maximum matching of $G$ uses the vertex $v$. This can be checked in polynomial time.

The above is Theorem 1.1 from the paper "Undirected Edge Geography", by Fraenkel, Scheinerman and Ullman, Theoretical Computer Science 1993.


On the Shannon Capacity of Cycles Let $\alpha(C_{n}^{\boxtimes k})$ be independence number of $k$-fold strong product of an $n$-vertex cycle graph $C_{n}$.

$\forall n > 6$, is $\alpha(C_{n}^{\boxtimes (k+r)})^{\frac{1}{k+r}} \geq \alpha(C_{n}^{\boxtimes k})^{\frac{1}{k}}$ for infinitely many positive integer pairs $(k,r)$?

It is a standard fact that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$ for every graph $G$. (See the proof below.)
Denoting $b_k := \sqrt[k]{\alpha(G^k)}$, this implies that the tail of the sequence $(b_k)_{k \geq 1}$ cannot be monotone decreasing, and hence there are infinitely many $k$'s for which $b_{k+1} \geq b_k$, as required.

In order to prove that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$ note that the sequence $(\alpha(G^k))_{k \geq 1}$ is super multiplicative, i.e., $\alpha(G^{k+\ell}) \geq \alpha(G^k) \alpha(G^\ell)$ for all $k,\ell \geq 1$. Indeed, if $I$ is an independent set in $G^k$, and $J$ is an independent set in $G^\ell$, then $I \times J$ is an independent set in $G^{k+\ell}$. Therefore, by (the multiplicative version of) Fekete's lemma it follows that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$.