Designing a Transport network path suggestion tool I am working on a suggestion system to passengers on transits to take.
The thing is we are formulating stations on a transport network (eg. bus transport) as nodes and route between spatially adjacent stations as edges. The
weights on edges being the time it takes to reach between stations.

We are in search of route, a person should take if he/she desires
to go from node A to node B. I am aware that I can use the shortest path
problem to find a shortest route. But the complication is that the
shortest route may not be the fastest route to the destination. This is because
on the shortest route one of the leg of the journey has very low bus frequency and thus may take longer.

Let me elaborate it further. What I mean is that say A--C--B is the shortest route  but the frequency of buses is hourly. But A--D--B is another route which
is longer that A--C--B but has more frequency say once in 10 minutes.
Thus in this case A--C--B is the desired route. It is quite clear that the standard shortest path may not give the desired result.

Can you suggest a solution to this problem? I was thinking may be
detect all unique cycles involving node A & B. And compute actually required
time (taking into account bus frequencies) on that route. But I am not
sure how to go about this.

The obvious way of doing this is via time-dependent or time-independent graphs where you run a Dijkstra on it. This is also described in the lectures I mention below.

Also you should have a close look into transfer patterns (used at google) and RAPTOR (used at microsoft). There is a nice introduction into transfer patterns at university freiburg in lectures 9-11. RAPTOR is implemented in OpenTripPlanner and later this year probably also in my GraphHopper project.

  But the complication is that the shortest route may not be the fastest route to the destination.

Of course, but why not just use the time as weight instead of the distance? So 'shortest' and 'fastest' is not really a big difference ...


Complexity of greedy coloring I was looking at some heuristics for coloring and found this book on Google books: Graph
Colorings By Marek Kubale

They describe the Greedy algorithm as follows:

While there is an uncolored vertex v
    choose a color not used by its neighbors and assign it to v

Then they describe a sequential algorithm:

order the vertices in a random way
execute the greedy algorithm

They claim that this algorithm is $O(m+n)$.

Its seems to me that the greedy algorithm is in fact $O(n^2)$.
Am I missing something here? Or is the greedy method $O(m)$?
($m$ = edges, $n$ = vertices)

The book probably assumes an adjacency list representation. Each vertex is visited once, so to decide what color it should get, all its neighbors are checked, so each edge is crossed twice (once in each direction).

If you have an adjacency matrix representation, I think it will be $O(n^2)$.


Characterization of read-once formulae over the full binary basis Background

A read-once formula over a set of gates (also called a basis) is a formula in which each input variable appears once. Read-once formulas are commonly studied over the De Morgan basis (which has the 2-bit gates AND and OR, and the 1-bit gate NOT) and the full binary basis (which has all 2-bit gates).

So for example, the AND of 2 bits can be written as a read-once formula over either basis, but the parity of 2 bits cannot be written as a read-once formula over the De Morgan basis.

The set of all functions that can be written as a read-once formula over the De Morgan basis has a combinatorial characterization. See, for example, Combinatorial characterization of read-once formulae by M. Karchmer , N. Linial , I. Newman , M. Saks , A. Wigderson.

Question

Is there an alternate characterization of the set of functions that can be computed by a read-once formula over the full binary basis?

Easier Question (added in v2)

While I'm still interested in an answer to the original question, since I haven't received any answers I thought I'll ask an easier question: What are some lower bound techniques that work for formulae over the full binary basis? (Other than the ones I list below.)

Note that now I'm trying to lower bound the formula size (= number of leaves). For read-once formulae, we have formula size = number of inputs. So if you can prove that a function needs a formula of size strictly greater than n, then that also means it cannot be represented as a read-once formula.

I'm aware of the following techniques (along with a reference for each technique from Boolean Function Complexity: Advances and Frontiers by Stasys Jukna):

Nechiporuk's method for universal functions (Sec 6.2): Shows an $n^{2-o(1)}$ size lower bound for a certain function. This doesn't help you find lower bounds for a particular function that you might be interested in though.
Nechiporuk's theorem using subfunctions (Sec 6.5): This is a proper lower bound technique in the sense that it will provide a lower bound for any function you're interested in. For example it shows that any formula over the full binary basis that represents the element distinctness function has size $\Omega(n^2/\log n)$. (And this is the largest lower bound the technique can prove — for any function.)

there is also a method called the Krapchenko lower bound "which can be slightly larger than Nechiporuks method". see John E Savage, Models of Computation, section 9.4.2. (which is covered right after the Nechiporuk method in section 9.4.1)


Ackermann Function Time Complexity Are there any known problems that have an Ackermann function time complexity lower bound?

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

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

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

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

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

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


Permanent as projection of determinant and another permanent I am looking for explicit examples where permanent of a given matrix $A$ is given by a determinant of a larger matrix $B$ (projection in the sense of Valiant). Is there any reference where I can find such an example for $n \times n$ matrix $A$ for say $n \le 5$.

Also are there examples where permanent of a given matrix $A$ is given by permanent of a larger matrix $A$? Again any explicit example for $n \times n$ matrix $A$ for say $n \le 5$ would help.

A way to have such an explicit example is the following: Consider a matrix $A$ full of indeterminates (you can specialize the entries if you wish). Then use some formula for the permanent of this matrix (Ryser's or Glynn's for example). From this formula, you can build another matrix $B$, of quite huge dimensions, whose determinant equals the formula, thus the permanent of $A$.

Another thing you can do is to consider a matrix A whose determinant and permanent are the same (adjacency matrix of a graph whose cycles are of odd length). Then you can use different constructions to build a new matrix B with the same determinant. For instance, in our paper Symmetric Determinantal Representation of Formulas and Weakly-Skew Circuits, we give an algorithm that given a matrix $A$ builds a symmetric matrix $B$ such that $\det A=\det B$ (Section 3.2).

You can have a look at our paper for the classical techniques to do what you want (if I am not mistaken). For the second part, it is easy to change the constructions giving a matrix $B$ whose determinant equals some other determinant or formula, in such a way that you obtain another matrix $C$ such that $\operatorname{per} C=\det B$.

A last word to be more explicit:

$$\operatorname{per}\begin{pmatrix} x&y\\ 1&1\end{pmatrix}
   = \det\begin{pmatrix} x&0&0&1 \\ 0&y&0&1 \\ 0&0&1&0 \\ 1&1&0&0\end{pmatrix}$$

I hope this helps, even though I am not quite sure to exactly understand what you mean by "explicit example". If you are looking for an explicit example where for some $(n\times n)$ matrix $A$, the smallest matrix $B$ such that $\operatorname{per} A=\det B$ has dimensions $>n$, then you should look at Mignon & Ressayre's paper "A quadratic bound for the determinant and permanent problem" or subsequent works by Jin-Yi Cai and coauthors.


Fragments of the mu calculus I would like to know if somebody has studied the following very simple fragment of the modal mu-calculus:

$$F::= X \;| \; p \; | \; F \wedge G \; | \; [a]F \; | \; \nu X.F$$

where p ranges over propositional letters. In other words this is the mu-calculus where no disjunction, diamond or least fixed point operators are ever used.

This is a almost trivial fragment, of course. But i'm interested in the following two questions:

A) Is it true that if F is satisfiable, then it is satifiable in a finite model such that every vertex $X$ in the labeled Kripke structure has at most one $a$-labeled children?
i.e., such that $X\xrightarrow{a}Y$ and $X\xrightarrow{a}Z$ then $Y=Z$?

B) What is the complexity of the satisfiablity problem for this logic?

C) What is the complexity of model checking?

To answer the first part of your question

  Modal specifications are a syntactic fragment of the Mu-calculus, Guillaume Feuillade, 2005.

From the introductory paragraph

  As a consequence, we define a syntactic fragment of the Mu-calculus, called the conjunctive modal Nu calculus, ...In this report, we prove that the conjunctive modal Nu-calculus and modal specifications have the same expressive power and that we can switch between both without loss of generality. We also prove that the set of models of a modal specification is a lattice with finite models as extrema.

You should examine the details, particularly because the notion of a modal specification is not standard, and is defined in the article.


Examples of collapsing hierarchies Are there interesting examples of "collapsing hierarchies" in computer science?

The formal definition of a hierarchy here would be a class of languages/problems/objects which is parametrized by a partially ordered set. But I am of course looking for an at least somewhat "natural" hierachy, where the parameter represents some type of resource. I am particularly interested in hierarchies where the parameter space is $\mathbb{N}$ or the $\Sigma_i/\Pi_i$ ladder. Some examples are

the polynomial hierarchy (counting alternations),
the lightface hierarchy (same),
$NC^i$ and $AC^i$,
various ways to associate languages to $k$-headed finite-state automata (as $k$ grows).

I am also happy with more complicated parameter spaces such as polynomial time languages parametrized by their time-complexity or space-complexity, if you know interesting collapsing results for them.
By collapsing I simply mean that some level of the hierarchy already contains all elements of the hierarchy. In all natural cases I can think of, either we know hierarchy does not collapse or we don't know whether it collapses. I would like to know some examples of hierarchies that do collapse. The hierarchy should be "natural", and I would prefer an example where the collapse does not happen "on the first level".
I did not carefully check that none of the hierarchies listed in What hierarchies and/or hierarchy theorems do you know? collapse, but at least it is not known to collapse for any of the ones I was familiar with, or for which this was mentioned in the answers.

The analogue of the $\mathsf{NC}$ hierarchy for algebraic circuits is known to collapse to the second level. That is, algebraic circuits of size $n^{O(1)}$ computing a polynomial of degree $n^{O(1)}$ can be rebalanced to have depth $O(\log^2 n)$ while only increasing the size by a polynomial factor. This is due to Valiant, Skyum, Berkowitz, and Rackoff. It is open whether $\mathsf{NC}^1 \stackrel{?}{=} \mathsf{NC}^2$ in this setting, but I believe the popular opinion is that $\mathsf{NC}^1 \neq \mathsf{NC}^2$ here.
If one further restricts to syntactically multilinear algebraic circuits, then we in fact know $\mathsf{NC}^0 \subsetneq \mathsf{NC}^1 \subsetneq \mathsf{NC}^2 = \mathsf{NC}$ unconditionally. The fact that $\mathsf{NC}^1 \subsetneq \mathsf{NC}^2$ is due to Raz, and the fact that $\mathsf{NC}^2 = \mathsf{NC}$ is due to Raz and Yehudayoff.
Raz, Ran, Separation of multilinear circuit and formula size, Theory Comput. 2, Paper No. 6, 121-135 (2006). ZBL1213.68301.
Raz, Ran; Yehudayoff, Amir, Balancing syntactically multilinear arithmetic circuits, Comput. Complexity 17, No. 4, 515-535 (2008). ZBL1188.68367.
Valiant, L. G.; Skyum, S.; Berkowitz, S.; Rackoff, C., Fast parallel computation of polynomials using few processors, SIAM J. Comput. 12, 641-644 (1983). ZBL0524.68028.


Is $CAPP \in P$ known to collapse some quantum complexity classes to classical ones? Lets define the class

$ZBQP = \{ L \mid \exists \textit{P-uniform circuit family } \{C_i\}, \forall n \in \mathbb{N}, |x| = n, |\langle 0|C_n|x \rangle - I(x \in L)| \leq 9/10 \Longleftrightarrow x \in L\}.$

We note a construction of Ashley Montanaro, that for any quantum circuit $C$ there exists some multilinear polynomial of size linearly proportional to $C$, $f_C$, such that

$\langle 0 | C|0\rangle = \frac{gap(f_C)}{2^n}$

where $n$ is the number of variables in the polynomial and

$gap(f) = |f^{-1}(0)| - |f^{-1}(1)|.$

We now define CAPP, the Circuit Approximate Probability Problem, which is a function problem:

$C \mapsto v \textit{ where } |v - Pr_x(C(x) = 1)| \leq 1/10.$

Using this problem, we can get a $2/10$ error approximation for $gap(f)$, as

$gap(f) = 2^n (Pr(f(x) = 0) - Pr(f(x) = 1))$

and thus we can get an approximation for $\langle 0|C_n|0 \rangle$ (or for $\langle y| C_n |x \rangle$ by modifying the circuit and thus $f_C$ in the obvious way). As we have a two sided error for $ZBQP$ and this approximation gets us close enough to distinguish which side we're on, it seems that this allows us to solve $ZBQP$ problems in basically whatever function classes where we can do $CAPP$, which is suspected to be in $FP$ and is already in $FBPP$.

Does $ZBQP \neq BQP$ for any reason I'm missing? It seems like they may be equal, but I dunno.

This is a bit of a subtle point, but the reason that solving CAPP (and hence finding an approximation to $gap(f)$ with the corresponding level of accuracy) doesn't immediately give a good algorithm for approximating $\langle 0 | C | 0 \rangle$ for arbitrary quantum circuits $C$ is because of normalisation. This is discussed in Proposition 8 of the paper you mention.

But in particular, we don't have $\langle 0 | C | 0 \rangle = gap(f) / 2^n$, where $n$ is the number of variables in the polynomial; we have $\langle 0 | C | 0 \rangle = gap(f) / 2^{n-h/2}$, where $h$ is the number of internal Hadamard gates in the circuit (see Proposition 1). So this means that to get a good approximation to $\langle 0 | C | 0 \rangle$ (say, up to an additive error $1/3$, which is BQP-complete), we would need to approximate $gap(f)$ up to additive error $1/3 \cdot 2^{n-h/2}$, which can be much smaller if $h$ is large.


The Maxwell's Demon and Computer Science What is the best source -in terms of quality- that would explain the argument that uses computations concepts to demonstrate that the Maxwell's Demon does not break the second law of thermodynamics? I have an impression that this argument has some flaw, because all the sources I know use natural language. However, I would like some source that demonstrates formally.

A good place to start looking at these ideas is this paper, though it talks about the (related) idea of information and thermodynamics. It relates fundamental computational tasks (eg. editing a bit) to fundamental thermodynamic tasks (eg. energy extraction). Following the links within the paper should give reasonable access to literature on the subject. Also, see this paper.

EDIT - There is also discussion regarding this on Scott Aaronson's blog https://www.scottaaronson.com/blog/?p=3327. See the comments section too.

References -

1. The Hot Bit 1 : The Szilard-Landauer Correspondence,
M Gopalkrishnan - arXiv preprint arXiv:1311.3533, 2013

2. The Thermodynamics of Computation — a Review, C. Bennet -
International Journal of Theoretical Physics 21.12 (1982): 905-940.


Formalized priority argument A priority argument, an important proof technique in recursion theory, was introduced by Friedberg and Muchnik, to solve Post's Problem, i.e., the existence of two r.e. sets that do not Turing reduce to each other.

My question is whether or not there has been an attempt to formalize priority arguments in some proof system adopted by proof checkers or proof checkers.  I believe this is an interesting problem, since:

Priority arguments can sometimes be very complicated (for humans to read);
Objects constructed by priority arguments are constructive (relative to something else), so it is possible that the argument is suitable to formalize in some proof systems, many of them are based on typed lambda calculi; and
Yet most construction in priority arguments do not look like a typical functional programs at all

Computability theory in general has been somewhat under-formalized. The short answer is that most theorems of computability theory do not pass one of the three tests for formalization:

A proof that is computationally intensive or untrusted for some reason (long, complex).
A result that is relevant to undergraduate mathematics.
A result that is useful to program verification.

Reason 1 may apply in this case, but the preliminary work to build up to that result unfortunately hasn't been carried out. I found one reference to mechanized computability theory by Xu, Zhang and Urban in Isabelle. It falls significantly short of priority results though.


Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$? Let $\mathsf{ATISP}(f(n), g(n))$ be the class of languages decided by alternating Turing machines that halt in time $f(n)$ using space $g(n)$. Let $\mathsf{AALTSP}(f(n), g(n))$ be the class of languages decided by alternating Turing machines that halt using $f(n)$ alternations and space $g(n)$.

Ruzzo proved that $\mathsf{NC}^k = \mathsf{ATISP}(\log^k n, \log n)$. He also showed that $\mathsf{NC}^k \subseteq \mathsf{AALTSP}(\log^k n, \log n) \subseteq \mathsf{NC}^{k + 1}$.

Is $\mathsf{NC}^k = \mathsf{AALTSP}(\log^k n, \log n)$?

Of course the equalities and inclusions claimed in the question hold only for uniform $\mathsf{NC}^k$. The class $\mathsf{AALTSP}(\log^k n, \log n)$ is the same as uniform $\mathsf{AC}^k$, so the question is the same as whether $\mathsf{NC}^k = \mathsf{AC}^k$.

In particular the case $k=1$ implies that $\mathsf{L}$ is equal to $\mathsf{NL}$ and even $\mathsf{LogCFL}$, since $\mathsf{NC}^1 \subseteq \mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{LogCFL} \subseteq \mathsf{AC}^1$.


How intrinsic is the $d^d$ term in the running time for constructing $\varepsilon$-nets in range spaces of VC-dimension d? An $\varepsilon$-net for a range space $(X,\mathcal{R})$ is a subset $N$ of $X$ such that $N\cap R$ is nonempty for all $R\in \mathcal{R}$ such that $|X\cap R| \ge \varepsilon |X|$.

Given a range space $(X,R)$ of VC-dimension $d$, an $\varepsilon$-net of size $O\left(\frac{d}{\varepsilon}\log\left(\frac{d}{\varepsilon}\right)\right)$ can be computed in time $O(d)^{3d}\left(\frac{1}{\varepsilon^2}\log\left(\frac{d}{\varepsilon}\right)\right)^d|X|$ (see [1], Thm 4.6).

To what extent is the $O(d)^{3d}$ term intrinsic to this problem?  Specifically, can it be improved to $2^{O(d)}$?  Are there lower bounds known?

A related question: are there general conditions on $(X,R)$ for which such an improvement is known to exist?

[1] Bernard Chazelle.  The Discrepancy Method.  2000.

If you are ok with a randomized algorithm, then you can just randomly sample $O((d/\epsilon) \log (d/\epsilon \delta))$ points, and this will be an $\epsilon$-net with probability at least $1-\delta$.

For the deterministic algorithm, I believe the $d^{O(d)}$ term comes from the following reason.  You first partition your full set into subsets of size about $s = O((d/\epsilon) \log (d/\epsilon))$ where $s$ is the size of the $\epsilon$-net you hope to get in the end.  Then you merge two such subsets and reduce to half that size.  (Basically, this is repeated until one set is left.)  The reduction step essentially considers all interesting ranges of the merged set of size $2s$.  By VC-bounds there are about $O((2s)^d)$ ranges, and you need to "check" each of these to see if it has been hit.  The $s^d$ has a $d^{O(d)}$ in it.  The $d$ in the $s$ term is needed.  So to reduce this bound, using this deterministic framework, you would somehow need to implicitly "check" all ranges without explicitly enumerating them.   This seems difficult to do deterministically, but I am not sure I know an explicit lower bound - most work in this arena assumes $d$ is constant and abuses this heavily.


Determinant of a generalized Vandermonde matrix Moore matrix is similar to Vandermonde matrix but has a slightly modified definition.
http://en.wikipedia.org/wiki/Moore_matrix

What is the complexity of computing the determinant of a given $n \times n$ full rank Moore matrix modulo some integer?

Can Moore determinant be reduced from $O(n^{3})$ using FFT techniques to $O(n\log^{a}n)$ for some $a \in \mathbb{R}_{+} \cup \{0\}$?

Is complexity of Moore det modulo an integer and Vandermonde det the same?
Complexity of Vandermonde determinant is $O(n\log^{2}n)$ (Page 644 in Handbook of Theoretical Computer Science: Algorithms and complexity By Jan Leeuwen)

Post similar to the current one: Determinant modulo m

In general, there is a theoretical $O(n^{2.376})$ time algorithm for finding the LU decomposition of an arbitrary matrix using the Coppersmith–Winograd algorithm, which then obviously yields the determinant (adding $O(n)$ time).  There is a problem however that the Coppersmith–Winograd algorithm isn't considered usable in practice.  Afaik, people mostly use the $O(n^{2.807})$ time Strassen algorithm.  Doesn't Boost UBLAS's lu_factorize use this?

In you case, the Moore matrix should admit considerable optimizations because basically any Gaussian elimination like procedure like LU decomposition can be done abstractly.  Indeed, you'll find a nice $O(n)$ formula for computing the Moore determinant referenced by wikipedia, which presumably one proves by simply working out the LU decomposition in general.


Other kinds of running time analysis besides worst-case, average-case, etc? Here are some ways to analyze the running time of an algorithm:

1) Worst-case analysis: Running time on the worst instance.

2) Average-case analysis: Expected running time on a random instance.

3) Amortized analysis: Average running time on the worst sequence of instances.

4) Smoothed analysis: Expected running time on the worst randomly perturbed instance.

5) Generic-case analysis: Running time on the worst of all but a small subset of instances.

My question: Is this a complete list?

I have two more for the list, which are somewhat similar.

Parameterized Analysis expresses the running time as a function of two values instead of one, using some additional information about the input measured in what's called the ``parameter''. As an example take the Independent Set problem. The best running time for the general case is of the form $O(c^n n^{O(1)})$ for some constant $1 < c < 2$. If we now take as parameter the treewidth of the graph and represent it by the parameter $k$, an Independent Set can be computed in $O(2^k n^{O(1)})$ time. Hence if the treewidth $k$ is small compared to the total size of the graph $n$, then this parameterized algorithm is much faster.
Output-sensitive analysis is a technique which is applied to construction problems, and also takes the size of the output into account in the run-time expression. A good example is the problem of determining the intersection points of a set of line segments in the plane. If I'm not mistaken you can compute the intersections in $O(n \log n + k)$ time where $k$ is the number of intersections.


How much time to recognize palindromes in logarithmic space? It is well-known that palindromes can be recognized in linear time on $2$-tape Turing machines, but not on single-tape Turing machines (in which case the time needed is quadratic). The linear-time algorithm uses a copy of the input, and thus also uses a linear space.

Can we recognize palindromes in linear time of a multitape Turing machine, using only  a logarithmic space? More generally, what kind of space-time trade-off is known for palindromes?

You can use the same argument used to prove the $\Omega(n^2)$ time bound on single tape.

Suppose that you have a TM with $S(n)$ space that recognize palindromes
$\{x\,0^{\frac{n}{3}} x^R \mid |x|=n/3 \}$ (where $x^R$ is the reverse of $x$) in time $T(n)$.
When the (input) head crosses the middle $0^{n/3}$ it can carry only $S(n)$ bits of information. So it needs to make $\Omega(n / S(n))$ crosses, and each cross requires $n/3$ time.

So $T(n)S(n)=\Omega(n^2)$.


Evidence that matrix multiplication can be done in quadratic time? It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple:

  What reasons do we have for believing that $\omega = 2$?

I'm aware of fast algorithms like Coppersmith-Winograd, but I don't know why these might be considered evidence for $\omega = 2$.

Naively, it seems to me like a classic example where a community just hopes that a result is true purely for aesthetic reasons. I would love to know if that's essentially the case here.

I don't know about others but I can tell you why I tend to believe that $\omega=2$. When you read through the history and development of fast matrix multiplication algorithms, I think that it is hard not to get feeling that all that we need is just a slightly better basic algorithm from which, even using known techniques, $\omega=2$ will follow. Basically, all algorithms today (including group theoretic ones) start with some "simple" construction that is then amplified. Those constructions are clever but they give the reader some sort of an "ad-hoc" feeling. I don't see a reason to believe that we cannot come up with better simple constructions.


Is DSPACE(n) = DSPACE(1.5n)? From space-hierarchy theorem it is  known that if $f$ is space-constructible then
DSPACE($2f(n)$) is not equal to DSPACE($f(n))$.

Here, by DSPACE($f(n))$  I mean the class of all problems that can be solved in space $f(n)$ by a Turing machine with some fixed alphabet. This allows  to consider Space-hierarchy theorem with such accuracy.

The standard argument gives multiplicative constant $2$: we need space $f(n)$ for constructing a calculation of some Turing machine by an universal one. Also we need $f(n)$ to solve a problem with halting.

Question: Is DSPACE($f(n)$) equal to DSPACE($\frac{3}{2}f(n)$)?

It can be proved that DSPACE$(f(\frac 32 n))\ne $ DSPACE$(f(n))$ if $f$ grows at least linearly by using a simple variant of the standard padding argument.
For a language $L$, let $L'=\{x0^{|x|/2}\mid x\in L\}$.

Claim. $L\in$DSPACE$(f(n))$ if and only if $L'\in$DSPACE$(f(\frac 23n))$ if $f(n)\ge \frac 32n$.

(My first answer had several incorrect statements, thanks to Emil for spotting this.)

I will first show how to use the claim to prove the hierarchy.
Since $f$ grows at least linearly, we have DSPACE$(2f(n))\subset$DSPACE$(f(2n))$.
Take a language $L\in$DSPACE$(f(2n))\setminus$ DSPACE$(f(n))$.
Using the claim, $L'\in$DSPACE$(f(\frac 43 n))=$ DSPACE$(f(n))$, where the last equality is by the indirect assumption.
But then $L\in$DSPACE$(f(\frac 32 n))=$ DSPACE$(f(n))$, where the last equality is again by the indirect assumption, giving a contradiction.

Proof of the claim.
If $L'\in$DSPACE$(f(\frac 23 n))$, then to prove $L\in$DSPACE$(f(n))$, we just need to write $|x|/2$ 0's to the end of the input $x$ and simulate the machine that accepted $L'$.
Since $f(n)\ge \frac 32 n$, this won't increase the space we use.
(In fact, knowing how many 0's to write is not clear at all if $f$ is small and we cannot increase the alphabet size - instead, we can use another tape and write on that everything that would come after the end of $x$.)

The other direction is just this simple by replacing the 0's with *'s, if we are allowed to write *'s. (See the issues with this in my comment to the question.)
If we are not allowed to write stars, then we slightly modify the definition of $L'$ as $L'=\{x10^{|x|/2}\mid x\in L\}$.
Now, instead of writing stars, we keep the original input $x10^{|x|/2}$ and work with that.
But whenever we reach a 1, we go right until we hit another 1 to check whether it was the end-of-word 1 or not.
If we've found another 1, we just go back to our 1.
If we haven't, we still go back, but we'll know that it should be treated as a star - if we were to write on it, then we also write a 10 after it to have a new end-of-current-word marker.
(In fact, there's also a small catch in this part if $f$ is small - how can we check if the input is of the form $x10^{|x|/2}$? Without destroying the input, I can only solve this by using multiple heads for small $f$.)


Lower bound on alternations needed in $BQP$ versus $PH$ result? What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ holds where $n$ is number of inputs to $\mathsf{SAT}$ formula (note $\mathsf{BQP}\subseteq\mathsf{PP}$) (here $\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ refers to $\mathsf{FP}$ with oracle access to ${\mathsf{PH}[O(f(n))]}$)? Is $f(n)=O\Big(\frac{n}{\log n}\Big)$ (comments in https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.html seems to indicate such a bound on $f(n)$ however was not sure)?
What would be the consequence if indeed $\mathsf{PP}$ and/or $\#\mathsf{SAT}$ are/is in $\mathsf{PH}[O(\log n)]$ and $\mathsf{FP}^{\mathsf{PH[O(\log n)]}}$ respectively? Would it nullify the $\mathsf{BQP}$ versus $\mathsf{PH}$ result of Raz and Tal (it could still be $\mathsf{BQP}\not\subseteq\mathsf{PH}$ is true but the evidence achieved will be falsified) and the result Robin Kothari is quoting? Would it have other consequences?

If you just want oracle separations with $\#P$, you don't need to use the new result of Raz and Tal. You can use the classic Parity/Majority not in $AC^0$ results from the 1980s.

For example, the strongest quantitative version of Parity not in $AC^0$ says that the $n$-bit Parity function cannot be computed by a quasi-polynomial size $AC^0$ circuit of depth $o(\log n/ \log\log n)$. So scaling this up, we get an oracle separation between $\oplus P$, which is in $\# P$, and $PH$ with $o(n/\log n)$ quantifiers.


Uses of quasi-PERs/difunctional relations/zig-zag relations? Given sets $A$ and $B$, a difunctional relation $(\sim) \subseteq A \times B$ between them is defined to be a relation satisfying the following property:

  If $a \sim b$ and $a' \sim b'$ and $a \sim b'$, then $a' \sim b$.

Difunctional relations are a generalization of the concept of partial equivalence relations which permit one to define a notion of equality from different sets. As a result, they are also known as quasi-PERs (QPERs), and they are also known as zig-zag relations, due to the following picture:

I'm writing a paper that uses them, but I've had trouble tracking down good references for their use in semantics.

Martin Hoffman uses them in Correctness of Effect-Based Program Transformations.
I have seen mentions (but no good references) claiming that Tennant and Takeyama have proposed their use as well.

They are such a pretty idea that I have trouble believing my particular use of them is original. I would really appreciate any further references.

Makoto Takeyama and I sent the following to data-refinement@etl.go.jp on Jan 5, 1996:

  Subject: what is a data refinement relation?

  Dear all:  anyone still interested in data refinement?

  Recently Mak and I have been looking again at an idea we considered
   many months ago.  The motivation is to characterize
   the logical relations relevant to showing data refinement.
   This was stimulated by the realization that logical relations can
   be used to show "safety" of abstract interpretations
   (see Section 2.8 of the chapter by Jones and Nielson in
   volume 4 of the Handbook of Logic in CS), but such relations
   are more general than those used to show data refinement.

  My reasoning goes as follows.  If a relation R is establishing a data
   refinement between (among) sets, then it must be inducing
   (partial) equivalence relations on each of the sets, with
   these equivalence classes in one-to-one correspondence,
   and every element of an equivalence class must be related
   to all elements of the corresponding equivalence classes in
   the other domains of interpretation.  The idea is that each
   equivalence class represents an "abstract" value; in a fully
   abstract interpretation the equivalence classes are singletons.

  We can give a simple condition to ensure that an n-ary relation R induces
   this structure.  Define v ~ v' in domain V iff there exists a value
   x in some other domain X (and arbitrary values ... in the
   other domains) such that R(...,v,...,x,...) and R(...,v',...,x,...).
   This defines symmetric relations on each of the domains.  Imposing
   local transitivity would then give us pers on each domain, but
   this would not suffice because we want to ensure transitivity
   across interpretations.  The following condition achieves this:
   if v_i ~ v'_i for all i, then R(...,v_i,...) iff R(...,v'_i,...)
   I call this "zig-zag completeness"; in the case n=2, it says
   that if R(a,c) & R(a',c') then R(a,c') iff R(a',c).

  Proposition. If R and S are zig-zag complete relations, so
   are R x S and R -> S.

  Proposition.  Suppose t and t' are terms of type th in context pi,
   and R is a zig-zag complete logical relation;
   then, if the equivalence judgement t=t' is interpreted as follows:

  for all u_i in V_i[[pi]],
      R^{pi}(...,u_i,...) implies that, for all i, V_i[[t]]u_i ~ V_i[[t']]u_i

  this interpretation satisfies the usual axioms and rules
   for equational logic.

  The intuition here is that the terms are to be "equivalent" both
    within a single interpretation (V_i) and across interepretations;
    i.e., the meanings of t and t' are in the same R-induced
    equivalence class, no matter which interpretation is used.

  Questions:

  Has anyone seen this kind of structure before?
  What are the natural generalizations of these ideas to
    other propositions and "arbitrary" semantic categories?

  Bob Tennent
  rdt@cs.queensu.ca


Fast Computation of First k Eigenvectors of Graph Laplacian I'm looking for references for the following; Given the unnormalized Laplacian matrix of a graph $L = D - A, ~ L \in \mathbb{R}^{n\times n}$

Algorithm(s) to efficiently estimate the first $k$ (smallest in magnitude) eigenvectors of $L$ -- and, the time complexity of such an algorithm. Denote these eigenvectors by $U_{:,1:k} \in \mathbb{R}^{n\times k} $.
For $1 \leq i, j \leq n$ and $p \in \{1,2\}$, can we determine whether or not $||U_{i,1:k} - U_{j,1:k}||_p$ is a close estimate of $||U_{i,:} - U_{j,:}||_p$ up to small multiplicative error, with high probability?

Edit 1: Based on helpful comments, I've corrected Q2 to hopefully something more accurate.

Answer to Q1:

In [1], it is argued at the end of section 1 that the first k eigenvectors can be approximated in time roughly $O(mk)$ (up to log-factors), with $m$ the number of edges. They are not very precise in their statement however, but I'm not aware of a better reference explictly stating this.

Answer to Q2:

No, this will not hold in general. You are describing a $k$-dimensional embedding of the nodes $[n] \to \mathbb{R}^k; i \mapsto U_{i,1:k}$, as is used in for instance spectral clustering. For nodes $i, j$ which lie in the same cluster (e.g., in the same clique of a dumbbell graph), the quantity $\|U_{i,1:k} - U_{j,1:k}\|_2$ will be small for sufficiently small $k$. On the other hand, if $i \neq j$ then $U_{i,:}$ is orthogonal to $U_{j,:}$ and hence $\|U_{i,:}-U_{j,:}\| = \sqrt{2}$.

[1] Koutis et al. "Faster spectral sparsification and numerical algorithms for sdd matrices." (2015)


The average number of compressible strings in a random set of random strings In the book Elements of Information Theory (p.446), it is stated:

...although there are some simple sequences, most sequences do not have simple descriptions. Similarly, most integers are not simple. Hence, if we draw a sequence at random, we are likely to draw a complex sequence. The next theorem shows that the probability that a sequence can be compressed by more than k bits is no greater than 2−k.

[snip latex Theorem and Proof]

Thus, most sequences have a complexity close to their length. For example, the fraction of sequences of length n that have complexity less than n − 5 is less than 1/32.

So, the answer I'm looking for looks something like:

For some given set and string length, for a random set of random strings, the number of compressible strings in that set will be on average X percent of that set.

Where X may be 0.0001% or 0.00002193487% or 0.000000009% or something more specific.

The answer is less than $2^{n-k}$ of the sequences of length $n$ have complexity less than $<n-k.$ Due to the uniformity assumption on these sequences we just count.

Consider all short programs of bitlength $<n-k.$ Even if all represented sequences of length $n$ the total number of such programs (starting with the empty program) is $$1+2+2^2+..+2^{n-k-1}<2^{n-k}.$$

To clarify,the number of compressible strings by $k$ bits in a the set of length $n$ bits is $2^{n-k}$, their relative number is $2^{-k}$ and their percentage is $100\times 2^{-k}.$ So for each fixed $k$ and all $n$ you get a constant. For example the percentage of strings of length $n$ which are compressible by $k=3$ is $100\times 2^{-3}=12.5\%,$ those compressible by $10$ bits have percentage $100\times 2^{-10}=0.09765625 \%.$


Partitioning the edges of a complete graph into smaller complete graphs Consider the (simple, undirected) complete graph $K_n$. Is it possible to partition its edges into less than $n$ cliques, each having less than $n$ vertices?

Note: It is easy to see that $n$ cliques of size $<n$ always suffice. Take a $K_{n-1}$ as one clique, and take a $K_2$ for each of the $n-1$ edges that are not contained in the $K_{n-1}$. This gives an edge partition into $n$ cliques, each with size $<n$. The question is whether there is such a partition into less than $n$ cliques of size $<n$.

After some search, I have found out that a solution was already published in 1948. De Bruijn and Erdos proved that it is not possible to partition the edges of $K_n$ into fewer than $n$ smaller cliques. I do not have a direct link to their paper, but it is referred to in the 1988 paper by Erdos, Faudree and Ordman, "Clique Partitions and Clique Coverings".


Non-termination, strict positivity and free monads Using the standard encoding of a free monad in Haskell and its fmap instance:

data Free f a = Pure a
              | Roll (f (Free f a))

Writing an equivalent to this in a dependently typed theory gets rejected because of the strict positivity condition.

Is it possible to cause non-termination with this encoding of a Free monad?

If this isn't the case does it point to some known relaxation of the strict positivity condition?

If this is the case is there a strictly positive datatype which acts as Free for strictly positive functors?

I don't specify the exact type theory I am working in, as some might allow addition of features to allow this. The base theory might be something like Coq's CoC.

Using Free, you can have a HOAS embedding of the untyped lambda calculus. And then write a structurally recursive function firing the top-level redex again and again. Good luck trying to normalise reduce omega.

{-# NO_POSITIVITY_CHECK #-}
data Free (f : Set → Set) (a : Set) : Set where
  Pure : a → Free f a
  Roll : f (Free f a) → Free f a

data LAMF (T : Set) : Set where
  App : T → T → LAMF T
  Lam : (T → T) → LAMF T

LAM : Set → Set
LAM = Free LAMF

pattern `lam b   = Roll (Lam b)
pattern `app f t = Roll (App f t)

data ⊥ : Set where

-- Type of closed term: LAM ⊥

delta : LAM ⊥
delta = `lam λ x → `app x x

omega : LAM ⊥
omega = `app delta delta

reduce : ∀ {A} → LAM A → LAM A
reduce (`app (`lam b) t) = reduce (b t)
reduce t = t


Facility Location problem, multiple facilities with no specific locations My problem is as follows:

I have $n$ customers, each with a predetermined location in the plane, i.e. $(x,y)\in\mathbb{R}^2$. I have $k$ facilities I want to distribute such that each one of them can serve up to $m$ customers.

I'm struggling with how I should formulate the cost function so I can solve it with non-linear programming (I'm going to start off by using http://abel.ee.ucla.edu/cvxopt/).

I have also though about just using a modified $k$-means method if everything else fails but I really want to try the other option first.

Edit: If the task above is too hard I could consider skipping the requirement that each facility can only serve $m$ customers and that I only have to distribute the facilities to minimize distance to their customers.

Edit 2 (real scenario to explain the reason for this formulation): A company has location information for all their customers, the company is going to open $k$ facilities (e.g. shops). Each facility can serve up to $m$ customers, how should we place the facilities such that the total distance to the customers they serve is minimized?

What you're talking about is, I believe, called the Capacitated Facility Location Problem.  Searching for that should give you plenty of papers to read.  It appears the problem is NP-hard, but in Euclidean space a simple search procedure gives you a 6-approximation [PDF].


Problems that are hard w.r.t UGC-hardness of VERTEX COVER Are there any problems $P$ such that an $\alpha$-approximation for $P$ (for soem choice of $\alpha$) would imply a better than 2-approximation for VERTEX COVER, which would be hard via the UGC ?

Node-weighted multiway-cut is a problem to which vertex-cover can be reduced to in an approximation preserving way. Thus, a better than $2$-approximation for node-weighted multiway cut is not possible assuming UGC. The reduction was shown by Garg-Vazirani-Yannakakis in their paper which also established a $2$-approximation for node-weighted multiway-cut.


What's the complexity of this estate-division game? Alice and Bob are splitting their deceased uncle Charlie's estate (a finite collection $X$ of discrete items) according to his wishes.  First A picks an item, then B, then A, and so on.

Alice and Bob each have additive utility functions $u_A, u_B$, so that if Alice ends up with the set $Y \subseteq X$, her utility is $\sum_{y \in Y}u_A(y)$.

These utility functions are common knowledge, as is the fact that Alice and Bob are perfectly rational utility-maximizers.  This implies that the players will not always follow a greedy approach, grabbing the item of greatest worth to them; they will be more strategic.

So, what is the computational complexity of implementing the players' strategies?  It's doable in polynomial space, and that's all I know.

Perhaps this paper will be of interest though I don't know if it addresses complexity issues:

http://or.journal.informs.org/cgi/content/abstract/19/2/270

or

http://www.jstor.org/pss/169267


On derandomizing polynomial identity testing In polynomial identity testing we seek a deterministic algorithm to infer equality of two polynomials $g,h\in\Bbb Z[x_1,\dots,x_n]$. Derandomizing known efficient randomized algorithms and producing an efficient deterministic algorithm is an important open problem. Is there a complete problem for PIT so that derandomizing identity testing for this one class of polynomials solves this open problem? If not, are there classes of polynomials where this problem is solved and classes where they are open?

[tl;dr] A lot is known, and it is a very active area! [/tl;dr]

It is important to specify the representation of the input polynomials, since it they are given as lists of coefficients or nonzero monomials, the problem is trivial. Thus one usually assumes the polynomials to be given as arithmetic circuits (a.k.a. straight-line programs). And the general case actually boils down to testing whether a given polynomial is the zero polynomial.

There are two main settings that have been studied: the whitebox case in which one has the arithmetic circuit and can inspect it, and the blackbox case in which one knows some things about the circuit (size, formal degree, ...) but cannot inspect it, only evaluate it on some values.

Here are some of the restrictions on the circuits that have been studied:

Bounded depth: The depth of a circuit is the longest path from an input to the output gate. Testing circuits of depth $2$ is trivial, depth $3$ is very well understood (completely solved? I do not know...), depth $4$ is also well understood. There are results showing that solving the problem for depth-$3$ and depth-$4$ circuit is almost the same as solving the general case.
Top/bottom fan-in: For bounded-depth circuits, many results have been proved when the fan-in (or arity, that is the number of inputs to a given gate) of either the top gate or the bottom gates is bounded.
Other restrictions such as a bound on the number of times a variable is used have also been studied.

This survey by Nitin Saxena is a good source for these results. Note though that it is already more than one year (!) old, and this is a very active area. So the most recent results are not covered.

Finally, there are links between the derandomization of PIT and the derandomization of other problems:

Noether's Normalization Lemma, by Ketan D. Mulmuley;
Multivariate Polynomial Factorization, by Swastik Kopparty, Shubhangi Saraf and Amir Shpilka.


Surveys in other languages than English Where can I find surveys in languages than English ?

If the question is found to be interesting (it could be usefull for graduated students who are not fluent in English for instance), it would be practical to propose one reference by answer, i.e. by subject and by language.

To open the list, here is a survey on SAT in French by Cristina Bazgan:
Optimisation Combinatoire : problèmes paradigmatiques et nouvelles problématiques, Hermes, ed. Vangelis Paschos, pp. 21-50, 2007


What Lecture Notes Should Everyone Read? There has been several questions with the same scheme as this one:

What papers should everyone read
What books should everyone read
What are the recent TCS books whose drafts are available online
what videos should everybody watch

I was reluctant to post yet another one, but Jeff Erickson's lecture notes on algorithms changed my mind. I thought: Oh my! All these years and I haven't seen these excellent notes!

So, I thought there might be other great lecture notes, which are really worth reading. So, for each computer science subfield (data structures, algorithms, theory of computation, computational complexity, cryptography, etc.), recommend the superb lecture notes of your choice, and say why you think it excels.

One simple rule to keep it tidy: One answer per each subfield. (This will be a community wiki, so you can edit existing answers, and add your recommendation.)

Probability Theory And Randomized Algorithms

Lecture notes from Ryan O'Donnell's course Probability and Computing is pretty neat.

Lecture notes from Amit Chakrabarti's course Data Stream Algorithms


Figuring EasyVer problems - problems whose witness can be verified in time independent on the instance size In a related question I've defined a class of graph problems which are verifiable using a time related only on the size of the witness:

$EasyVer=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness $w$ of $L$'s instance can be verified in $poly(k)$ time$\}$, i.e. independent of $|V|,|E|$.

You can assume that the verifier has random access to the graph adjacency matrix in $O(1)$ time.

Examples for $EasyVer$ problems will be $VC, Clique, IS$ and $Steiner Tree$.

Also, many packing and problems, $triangle-packing$, $k-path-packing$, or in general $H-packing$ for a graph $H$ with constant treewidth, are all in $EasyVer$.

Problems which aren't in (i.e. require more extensive interaction with the input) are also easily found: $VC, DominatingSet, FVS$(Feedback Vertex Set).

In order to get a sense of how $EasyVer$ relates to known complexity classes it would be useful to have a list of problem it contains.

Which other NP-complete problem (or even better, problem classes) can be verified in $poly(k)$ time, where $k$ is the size of the problem witness?

If I get it right, you are interested in those parameterized problems that can be verified by a bounded-time NTM (running in time $f(k)$ for some function of the parameter). Up to fpt-reduction, these are precisely the problems in the class $W[1]$, see "On the parameterized complexity of short computation and factorization" by Cai, Chen, Downey and Fellows.


What's the probability for a random graph with degrees greater than 1 to be Hamiltonian? Given a random graph by the Erdős–Rényi model, if the minimal node degree is greater than 1 (or $\geq 2$), or randomly select a graph from the graphs with node degrees greater than 1 ($\geq 2$), what's the probability for it to be a Hamiltonian graph?

The probability that a random graph with $n$ nodes and $cn\log n$ edges contains a Hamiltonian circuit tends to $1$ as $n\rightarrow\infty$ (and for sufficiently large $c$) (Pósa 1976).  Since an ER random graph has $\Omega(n^2)$ edges, it is almost certainly Hamiltonian as $n\rightarrow \infty$, even without the constraint on the minimal degree.


NP completeness over reals I am studying the BSS model of computation recently (cf. for instance Complexity and Real Computation; Blum, Cucker, Shub, Smale.)

For reals $R$, it is shown that, given a system of polynomials $f_1,\cdots, f_m\in R[x_1, \cdots, x_n]$, the existence of zeros is $NP_R$-complete. However, I am wondering, if those $f$'s are polynomials only have integer coefficients, i.e., $f_1,\cdots, f_m\in Z[x_1, \cdots, x_n]$, is still the problem $NP_R$-hard? (it is obviously in $NP_R$).

I suspect yes, but is there a simple proof?

I think the answer is no, assuming $\mathsf{P}_{\mathbb{R}} \neq \mathsf{NP}_{\mathbb{R}}$ (I believe I give a proof below, but there are enough potentially nitpicky definitional issues here that I'm being cautious about my claims).

Proof that the answer is no assuming $\mathsf{P}_\mathbb{R} \neq \mathsf{NP}_{\mathbb{R}}$: In fact, I believe the following stronger statement holds:

Lemma: For any BSS decision problem $L$ over $\mathbb{R}$, if $L$ poly-time-BSS$_{\mathbb{R}}$ reduces to a problem on integer inputs, then $L \in \mathsf{P}_\mathbb{R}$.

Proof of lemma: Suppose there were a polynomial-time BSS$_{\mathbb{R}}$ reduction from $L$ to a problem on integer inputs, given by a machine $M$. For inputs consisting of $n$ real parameters, unroll the computation of $M$ into an algebraic computation tree. There are only finitely many leaves, and the result at each leaf is a single rational function in the input parameters. In order for a rational function of real inputs to always output an integer value, it must be a constant function, and therefore not depend on the input. However, which constant function is used at each leaf can, of course, depend on the branches. However, since $M$ is a uniform machine, there can be only $O(1)$ output nodes, and thus only $O(1)$ output values. Thus $M$ can be trivially modified to in fact decide $L$ in polynomial time. QED

Now, take $L$ to be real feasibility of real polynomials. If $\mathsf{P}_{\mathbb{R}} \neq \mathsf{NP}_{\mathbb{R}}$, then $L \notin \mathsf{P}_{\mathbb{R}}$, and by the Lemma there is no reduction from $L$ to any problem on integer inputs (in particular, to real feasibility of integer polynomials).

Promise problem issue?: Another potential issue with your question is that real feasibility of integer polynomials may not be in $\mathsf{NP}_{\mathbb{R}}$, but only in its promise version. The issue here is that to verify that an input (such as the coefficient of a polynomial $f_i$) is an integer takes time that depends on the magnitude of $x$, whereas the set of instances (all instances, not just yes-instances) for an $\mathsf{NP}_{\mathbb{R}}$ decision problem should be decidable in $\mathsf{P}_\mathbb{R}$, the latter meaning that it takes polynomial time in the number of parameters, and not their magnitudes. This is, I believe, closely related to the fact that the integers are not first-order definable within the reals. (Essentially the best a BSS$_{\mathbb{R}}$-machine can do to test if an input $x$ is an integer is to compute the integer part of $x$ by computing powers of $2$ and doing "binary search." Once it's computed the integer part of $x$, it just checks whether that is equal to $x$.) So I think the probleam of real feasibility of integer equations is in $\mathsf{PromiseNP}_{\mathbb{R}}$ but probably not in $\mathsf{NP}_{\mathbb{R}}$ (or at least it seems nontrivial to prove that it is in $\mathsf{NP}_{\mathbb{R}}$).


Complexity of distributively verifying that the diameter is small Consider a graph $G=(V,E)$ and an integer parameter $k$.

I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than $k$.

Formally, assume that we need (all vertices) to report "small" if the diameter is at most $k$ and "large" if it is larger than $f(k)$ for some function $f$ (e.g., $f(k)=100k^2$).

A closely related problem asks to approximate the diameter. In this paper, it was shown that deciding whether the diameter is at most $2\ell+1$ or larger than  $3\ell+1$ requires $\widetilde \Omega(n)$ rounds for any $1\le \ell\le \text{polylog}(n)$. However, this just shows that a (small) constant factor approximation is hard.

On the algorithmic front, it is possible to compute a $3/2$-approximation in $O(\sqrt{n\log n}+D)$ rounds.

  Does the round complexity depends on $n$ for any function $f(k)$? Are there functions $f$ for which this dependency is reduced, say, to logarithmic?

  If we allow super-linear functions $f$, is it possible to reduce the dependency on the diameter (e.g., to $f^{-1}(D)$)? (e.g., can we get a round complexity of $O(k^2 \sqrt{n})$ for $f(k)=k^2$?)

There is an $O(k)$ rounds algorithm for distinguishing between graphs of diameter at most $k$ and those with a diameter larger than $2k$.

This works in two stages:

First, each vertex broadcasts the smallest ID it has learned about for $k/2$ rounds.
For a vertex $v$, let $L_v$ be the smallest ID that $v$ has observed by the end of this stage.

Next, the algorithm makes $k+1$, such that in each iteration every vertex broadcasts the largest $L_v$ and smallest $L_u$ it has learned about. If the graph is indeed of diameter $k$, then we would have these equal in all vertices.

Assume that the graph has a diameter larger than $2k$, then any vertex $v$ has a path of length at least $k+1$ starting from it. This means that there exists a vertex $u$ such that $d(u,v)=k+1> 2(k/2)$ which implies $L_u\neq L_v$. Thus, both $u,v$ would learn that not all vertices agreed on the node with the minimal identifier.


Is there any justification to believe that $NL\neq L$? I wonder if there is any justification to believe that $NL=L$ or to believe that $NL\neq L$?

It is known that $NL \subset L^2$.
The literature on derandomization of $RL$ is pretty convincing that $RL=L$.
Does anyone know about some articles or ideas convincing that $NL\neq L$?

First, let me cite skepticism that $L \neq NL$. As it has been shown that undirected graph connectivity is in $L$ (Reingold), and that $NL=coNL$ (Immerman-Szelepcsényi), I think that confidence in $L \neq NL$ has only decreased. Some prominent researchers have never had a strong belief. For example, Juris Hartmanis (founder of the CS department at Cornell and Turing award winner) has said:

  We believe that NLOGSPACE differs from LOGSPACE, but not with the same depth of conviction as for the other complexity classes. (Source)

I know he said similar things in the literature as far back as the 70's.

There is some evidence against $L=NL$, although it is circumstantial. There has been work on proving space lower bounds for $s$-$t$ connectivity (the canonical $NL$-complete problem) in restricted computational models. These models are strong enough to run the algorithm of Savitch's theorem (which gives an $O(\log^2 n)$ space algorithm) but are provably not strong enough to do asymptotically better. See the paper "Tight Lower Bounds for st-Connectivity on the NNJAG Model". These NNJAG lower bounds show that, if it's possible to beat Savitch's theorem and even get $NL \subseteq SPACE[o(\log^2 n)]$, one will certainly have to come up with an algorithm that's very different from Savitch.

Still, I don't know of any unlikely, unexpected formal consequences that come from $L=NL$ (except for the obvious ones). Again, this is primarily because we already know things like $NL=coNL$.


Constructing a k-perfect permutations family I'm looking for a set of permutations over $n$ elements $\mathcal{P}=\{P_1,P_2,...,P_r\}$ of minimal size such that for every ordered subset of size $k$, $S=<x_1,x_2,...,x_k>, (x_i \in [n])$, there exists a permutation $P \in\mathcal{P}, $ such that $P(x_1)<P(x_2)<...<P(x_k)$.

A simple probabilistic argument can show that such family of size $r=k!\cdot k\cdot log(n)+1$ exists:

Suppose we draw $r$ random permutations.
The chance that some specific $<x_1,...,x_k>$ is not ordered by non of the permutations is $(1-\frac{1}{k!})^r$.

Using the union bound, the chance that any ordered k tuple will not be ordered is bounded by:

$(1-\frac{1}{k!})^r\cdot$$ n\choose k$$\cdot k!<(1-\frac{1}{k!})^r\cdot n^k < n^k\cdot e^{-r/k!}$

If we demand that the probability will be less than 1 (which ensures such family exists), we get the desired size, $r>k!\cdot k\cdot log(n)$.

The question is:

Is there an explicit build for such family? is it computable in $O(k!\cdot poly(n))$ time?

This question might have been referred to somewhere in a different name, so if anyone is familiar with it, a reference will be great.

Edit: Andreas gave a nice build for parametric $k$.

What about the case that $k$ is a small, fixed number?

If $k=2$, then it's easy: take $\mathcal{P}=\{<1,2,...,n>,<n,n-1,...,1>\}$.

Can we build $O(1)$ sized 3-perfect permutation family? higher fixed $k$?

Here is a sketch on how to do almost what you want, but not quite.
It only proves a $k^{k+\operatorname{polylog}(k)}\log n$ bound.

Consider a set of size $m=n\log_2 k$ which we think of as $n$ groups on $\log_2 k$ elements each.

Next construct an $(m,k\log_2 k)$-universal set family $F$ of size $2^{k\log k+\operatorname{polylog}(k)}\log m$ using
the method of Naor, Schulman, and Srinivasan. We interprete each set in $F$ as a string on $n$ symbols from $[k]$ with one symbol for each group.

Now we turn each string into a permutation of $[n]$ in the following way:

We first think of the $n$ first positive integers divided in $k$ stacks $T_0$ throgh $T_{k-1}$ where $T_0$ contains the elements $1,...,n/k$ from top to bottom, $T_1$ contains $n/k+1,...,2n/k$, and so on.

We parse each string $s_1s_2...s_n\in F$ into a permutation by considering the symbols one at a time for increasing $j$, and on encountering symbol $s_j$ we pop the stack
$T_{s_j}$ from the top and put that number in place $j$ of the permutation.

Since the family $F$ was $(m,k\log_2 k)$-universal, we know that for every ordered set of $k$ of the $n$ groups, there is one string that maps the symbols $0$,$1$,...,$k-1$ to that ordered set. By the construction of the stacks, the elements fetched to the permutations preserve the order required.


Ordered-file maintenance I am studying the Advanced Data Structures material and I'd like to implement the Ordered-file maintenance data structure. I have few questions in order to start.

The papers rely on a static view, where the data structure already contains elements, but I need to start from scratch. The data structure partitions an array of $N$ (circa) elements into chunks of $\log N$ elements, and each chunk is ordered. When inserting, I need to choose a chunk and insert into a blank spot, if I fill the chunk, I need to move and possibly reorder elements based on density in a binary tree fashion.

At the beginning how many chunks do I have? I suppose one.
When the array is full according to the target density, do I need to grow the array and how? I suppose yes, always by a power of two (number of chunks).
Is there a possibility that a tree is impossible to rearrange according to the density? I hope not.
Is there any source code that I can take a loot at?
When $N$ changes do I need to change the chunk size accordingly? I think so.

Thanks!

I assume you're talking about maintaining keys, in order, in an $O(N)$-sized array, with $O(\log^2 N)$ amortized worst-case update time.

  At the beginning how many chunks do I have? I suppose one.

At the beginning, you will have one chunk.  Ordered file maintenance doesn't make sense for very small arrays.  Pick a smallish number (like 64 or 1024), and only start this whole chunking method once you grow above this small number.  In the small array do something naive, pushing elements around as necessary.

  When the array is full according to the target density, do I need to grow the array and how? I suppose yes, always by a power of two (number of chunks).

Yes, you can use standard dynamic array methods, like doubling in size when it gets too large.

Some data structures like to avoid this, as a full rebuild is a really large cost.  But this isn't a big deal for us, as this data structure is highly amortized anyway.  In other words, you have to do about $\Theta(\log N)$ rebuilds of the entire data structure every $N$ insertions anyway, just to maintain balance.  This just adds an extra one.

  Is there a possibility that a tree is impossible to rearrange according to the density? I hope not.

No, so long as there aren't too many elements.  This is fairly easy to see---so long as you don't have too many elements, you can distribute the elements in the whole array evenly, meeting the density bound of the top array.  But the arrays have looser requirements as they go down.  So if the top array fits in density (and the elements are distributed evenly), the entire data structure is correctly balanced.

  Is there any source code that I can take a loot at?

Yes, here (this was a class project; beyond that I know almost nothing about that code).  The author of that code has a nice writeup of the data structure as well.  Some more recent academic work on that data structure has experimental results.  You may try looking through those as well (though of course, many are variations on the original concept).

  When $N$ changes do I need to change the chunk size accordingly? I think so.

It depends on what you mean.  Do you mean "when I insert a single element, so $N\gets N+1$, should I update the chunks?" then the answer is no.  On the other hand, if you mean "when I run out of room in the data structure, and double its size, rebuilding the entire data structure, should I update the chunks?" then the answer is yes.


Is NP in $DTIME(n^{poly\log n})$? Is NP in $DTIME(n^{poly\log n})$?

$DTIME(n^{polylogn})$ is known as $QP$ (quasi-polynomial).

It is widely believed that $NP\not \subset QP$, although it is a stronger statement than $P\neq NP$.

Some common conjectures, such as the  Exponential Time Hypothesis imply $NP\not \subset QP$.


Is Hamiltonian cycle fixed parameter tractable with parameter clique cover? We conjecture that Hamiltonian cycle is fixed parameter tractable with parameter clique cover, given $k$-clique cover.

Let $G$ be connected simple graph.

$k$-clique cover of graph $G$ is partition of the vertices of $G$
into $k$ disjoint cliques $D'_i$.

Given $G$ and $k$-clique cover, can we solve Hamiltonian cycle
in time $O(\mathrm{polynomial}(n) n^{O(k)}$) or better?
Let $k$ be fixed, is it true that for all graphs with given $k$-clique
cover Hamiltonian cycle is polynomial in $n$?

The basic idea is that all paths in cliques are easy.

One possible approach is to merge the cliques to single vertex
and then enumerate walks allowing visiting vertex more than once.

For $k=2$ the answer is easily true.

For $k=3$ the merged graph is either $K_3$ or $P_3$
and we can try to extend walk to Hamiltonian cycle in $G$.

For $k=4$ the merged graph might be claw, so we need
more complicated algorithm.

Yes, this problem is FPT. We showed this in the paper "Parameterized Edge Hamiltonicity" (Lampis, Makino, Mitsou, and Uno, DAM 2018).

In particular, in this paper we state the result for Hamiltonian Path, but things doesn't change much if you want to consider Hamiltonian Cycle. In the conference version (and the slightly outdated version on the arxiv) we state the result as parameterizing by the chromatic number of the complement of the input graph (which is equal to clique cover).


Data Structure to calculate which interval a point lies in? I have a list of $n$ non-overlapping intervals, namely $[a_1,a_2],[a_2,a_3],...,[a_n,n_{n+1}], a_i \in \mathbb{N}$.

Each of these intervals has a corresponding value $v_i$ corresponding to it.

Now I have another interval $[x,y], a_1 \leq x < y \leq a_{n+1}$. I want to query the $n$ intervals and find the sum of values of the overlapping intervals with it in $O(\log n)$ time.

To make it clearer, I'll give an example.

Suppose the intervals are $[0,2],[2,4],[4,10]$ with values corresponding to $1,3,5$.

For the interval $[0,3]$, the first and second intervals overlap with it so a total value of 1+3=4.

For the interval $[0,5]$, all three overlap with it so a total value of 1+3+5=9.

For the interval $[5,9]$ only the last one overlaps it so the total value is 5.

I know that I can use a segment tree and query the point based on my interval $[a,b]$. However, how would I calculate the sum of all the values of all the intervals in between also in $O(\log n)$?

Since the intervals are non-overlapping, this can be done by building a 1-D summed area table of the interval values. Building the table takes $O(n)$ time; querying the table consists of two $O(\log n)$ binary searches followed by an $O(1)$ subtraction.

Note that the above solution specifically only works because the operation we want to perform on the interval values (addition) is invertible. It is also possible to design a more general data structure that has the same asymptotic performance and works on values from any monoid, using a trick similar to the parallel prefix sums algorithm.

For the initial construction, in $O(n)$ time we build a balanced binary tree, where each leaf node is labeled with an interval/value pair from the problem input, and each internal node is labeled with the union of its two child intervals and the sum of its two child values. For your example problem, the binary tree might look like this:

       [0,10]=9
      /        \
[0,2]=1        [2,10]=8
              /        \
         [2,4]=3     [4,10]=5

To query the data structure, you perform the following steps:

Use two $O(\log n)$ binary searches in the tree to find the endpoints of the smallest union of input intervals that contains the query interval. (Same as in the first solution.)
Sum the values of all of subtrees whose intervals are between these endpoints in the tree. Since we already have cached values for each subtree, only $O(\log n)$ node values need to be summed together.

For your example queries:

For the interval [0,3], we find the containing interval [0,4], then compute 1 + 3 = 4.
For the interval [0,5], we find the containing interval [0,10], then compute 9 = 9.
For the interval [5,9], we find the containing interval [4,10], then compute 5 = 5.


Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism? I have a (hopefully simple, maybe dumb) question on Babai's landmark paper showing that $\mathsf{GI}$ is quasipolynomial.

Babai showed how to produce a certificate that two graphs $G_i=(V_i,E_i)$ for $i\in\{1,2\}$ are isomorphic, in time quasipolynomial in $v=|V_i|$.

  Did Babai actually show how to find an element $\pi\in S_v$ that permutes the vertices of $G_1$ to $G_2$, or is the certificate merely an existence-statement?

If an oracle tells me that $G_1$ and $G_2$ are isomorphic, do I still need to look through all $v!$ permutations of the vertices?

I ask because I also think about knot equivalence.  As far as I know, it's not known to be, but say detecting the unknot were in $\mathsf{P}$.  Actually finding a sequence of Reidemeister moves that untie the knot might still take exponential time...

These problems are polynomially equivalent.
Indeed, suppose that you have an algorithm that can decide whether two graphs are isomorphic or not, and it claims that they are.
Attach a clique of size $n+1$ to an arbitrary vertex of each graph.
Test whether the resulting graphs are isomorphic or not.
If they are, then we can conclude that there's an isomorphism that maps the respective vertices to each other, thus we can delete them.
By repeating this test $n$ times, we can find (a possible) image for any vertex.
After this, we attach another clique, this time of size $n+2$ to a (different) arbitrary vertex of each original graph, and proceed as before, etc.
Eventually, we'll end up with two graphs that are isomorphic, with cliques of size $n+1,\ldots n+n$ hanging from their vertices, which makes the isomorphism unique.


CNF Rule hierarchy discovery This is bothering me for some time. Consider that I have a set of CNF formulae:

$F_1 = \left( A \lor B \lor C \right) \land \left( C \lor D \lor E \right) \land \left( B \lor F \lor G \right)$

$F_2 = \left( B \lor F \lor G \right)$

$F_3 = \left( A \lor B \lor D \right)$

Now, given the values (T/F) of the literals ($A$, $B$, $\cdots$), I wish to evaluate these formulae.

However, the point is that, if we observe closely, we can see that formula $F_1$ subsumes formula $F_2$ (i.e., while evaluating $F_1$, I will be automatically evaluating $F_2$). If I evaluate $F_1$ first followed by $F_2$, I will be unnecessarily repeating the efforts (since I already evaluated the $3^{rd}$ clause in $F_1$, I could have used that result for $F_2$, if I had some way of knowing it). Again, in case of $F_1$ and $F_3$, they do share some parts of the $1^{st}$ clause.

So, the question is, whether I can re-use the work done while performing this evaluation, by discovering the relationships (or hierarchy) of these CNF rules. I would like some scheme which tells me to evaluate $\left(A \lor B \right)$, use that for $F_1$ and $F_3$, tells me to evaluate $F_2$ before $F_1$ and directly use that result while evaluating $F_1$ (and so on...)

Is anyone aware of such problems? I know concepts such as Junction Trees in machine learning, Memoization in DP, or data structures like Trie which loosely achieve the same, but I am not able to fit my problem to these formulations. Any help would be greatly appreciated.

Thanks,

Salil

(PS: I posted this earlier on math.SE, but could not get any ideas, and was instead suggested to post this problem here)

Efficient CNF Simplification based on Binary Implication Graphs, Marijn Heule, Matti Jarvisalo, and Armin Biere, 2011

  "This paper develops techniques for efficiently detecting and removing redundancies from CNF (conjunctive normal form) formulas based on the underlying binary clause structure (i.e., the binary implication graph) of the formulas.

  In addition to considering known simplification techniques (hidden tautology elim- ination (HTE), hyper binary resolution (HBR), failed literal elimination over binary clauses, equivalent literal substitution, and transitive reduction  of the binary implication graph), we introduce the novel technique of hidden literal elimination (HLE) that removes so-called hidden literals from clauses without affecting the set of satisfying assignments."

I recommend Section 2.1 of the paper which reviews known simplification techniques.


Finding the two shortest paths while minimizing the number of nearby/common edges The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary.

Consider the following variant:

Find the two shortest paths between 2 pairs of arbitrary nodes, however  the cost is considered to be the length of the path and in addition the number of nearby/common edges in the two paths. This cost is $|P_1| + |P_2| + |P_1 \cap P_2|$ when considering only common edges. More generally we can state the cost as $|P_1| + |P_2| + f(P_1, P_2)$ where it can generalize to consider both penalizing common edges or nearby edges.

Has this problem been addressed before?

If the cost is $|P_1|+|P_2|+|P_1∩P_2|$, then a simple reduction to the shortest pair edge disjoint paths gives us a polynomial time solution. For each edge $e=(u,v)$ add two edges $(u,uv)$ and $(uv,v)$ each of them with same edge weight as $e$. The shortest pair edge disjoint paths in the new graph corresponds to the required solution in the original graph.

The algorithm for shortest pair edge disjoint paths is known as Suurballe's algorithm.

https://en.m.wikipedia.org/wiki/Suurballe%27s_algorithm

If the cost is some arbitrary function the problem can be NP-complete.
e.g assuming edge weights one, let the cost function be as $|P_1| + |P_2| + |P_1∩P_2| + 2\cdot |G-P_1\cup P_2|$.
Then the cost is always $ \ge |G|+2$ (if source and terminal are distinct vertices). The equality holds iff the graph has a Hamiltonian cycle.


Most significant bit of integer multiplication and binary decision diagrams Let $x$ and $y$ two binary numbers with $n$ bits and $z = x \cdot y\ $ the binary number (length $2n$) of the product of $x$ and $y$. We want to compute the most siginifcant bit $z_{2n-1}$ of the product $z = z_{2n-1} \ldots z_0$.

In order to analyse the complexity of this function in the model of binary decision diagrams (in particular read-once branching programs) I try to look for some equivalent expressions for the case $z_{2n-1} = 1$. The first obvious thing is $z_{2n-1} = 1 \Leftrightarrow x \cdot y \geq 2^{2n-1}$ (here $x$ and $y$ are the corresponding integers to the binary numbers). I want to get an intuition what happens if I set some input bits constant. E.g. if I set the most significant input bit from $x$ and $y$ to 0 I get the constant 0 function. But bits with lower significance haven't such an influence on the result.

Are there any other equivalent expressions for the case $z_{2n-1} = 1$ which help more to see what happens if I fix some input bits? Are there any refined methods to compute the product of two binary numbers which can help? Or do you have some other approach to this problem?

An interesting source is D. E. Knuth: The Art of Computer Programming, Volume 4, Fascicle 1, Bitwise Tricks & Techniques; Binary Decision Diagrams, Addison-Wesley, Pearson Education 2009

On page 96, there is a BDD for all bits of z = x⋅y, where x and y have 3 bits. It shows, that in the case of 3 bits, BDD representing the most significant bit has 7 non-terminal nodes. See the image bellow, I have redraw it using your indices x = (x2,x1,x0) and y = (y2,y1,y0).

On page 140 in Knuth's book, there is a question (no. 183) about BDD representing the most significant bit for multiplication of two numbers with infinitely many bits (it is called "limiting leading bit function") - this is similar to what you are loking for! The answer on page 223 gives first levels of the resulting BDD and discusses the number of nodes on all levels, but unfortunatelly it does not give algorithm to construct such a BDD.

Fig. 1: The most significant bit for multiplication of (x2,x1,x0) * (y2,y1,y0)


Why would a TCS researcher need funding? I was reading this. It says

  ... You won't find yourself as starving for funding like Pure Mathematics. (You'll still always find yourself starving for funding.)...

Why do pure mathematicians need funding?(Ooops its mathoverflow  question)

Why would someone doing theoretical research need funding?

I think tools of trade are papers, pencils, a laptop with good internet connection and a printer(?).

Please enlighten me! :-)

This is purely US-centric: other countries have different funding models. This is also from the perspective of an academic with a Ph.D, rather than a graduate student

As Jamie and Peter point out, the primary purpose of funding is to support graduate students. A secondary purpose is to support yourself during the summer. It's not widely known, but most US-based academics aren't paid for the 3 months of summer, and use grant money as salary for those months (I'll not discuss the limitations of NSF vs DARPA etc etc).

So you say, "I don't need students, I'll just work with colleagues". Great ! but then you need money to visit them. Without grant money, you have to wait your turn for whatever meager departmental funds might be available for travel (usually minimal).

So you then say "Fine ! I'll use skype and email to collaborate". Great ! but then you need to travel to a conference to give a talk. How do you fund that ?

So you say "Fine ! I'll just publish in journals and on the arxiv, and the brilliance of my research will shine through". Um, yeah....

If you're a junior academic, not getting funding can also affect your ability to retain your job itself. Funding is a major income source for most American universities.

None of this is ideal. But that's how the system is currently structured, dating back to Vannevar Bush, the founding of the NSF, and the mutation of the university into a research-generating enterprise.


Problems that are easy on unweighted graphs, but hard for weighted graphs Many algorithmic graph problems can be solved in polynomial time both on unweighted and weighted graphs. Some  examples are shortest path, min spanning tree, longest path (in directed acyclic graphs), max flow, min cut, max matching, optimum arborescence, certain densest subgraph problems, max disjoint directed cuts, max clique in certain graph classes, max independent set in certain graph classes, various max disjoint path problems,  etc.

There are, however, some (although probably significantly fewer) problems that are solvable in polynomial time in the unweighted case, but become hard (or have open status) in the weighted case. Here are two examples:

Given the $n$-vertex complete graph, and an integer $k\geq 1$, find a spanning $k$-connected subgraph with the minimum possible number of edges. This is solvable in polynomial time, using a theorem of F. Harary, which tells the structure of the optimal graphs. On the other hand, if the edges are weighted, then finding the minimum weight $k$-connected spanning subgraph is $NP$-hard.
A recent (Dec 2012) paper of S. Chechik, M.P. Johnson, M. Parter, and D. Peleg (see
http://arxiv.org/pdf/1212.6176v1.pdf) considers, among other things, a path problem they call Minimum Exposure Path. Here one looks for a path between two specified nodes, such that the number of nodes on the path, plus the number of nodes that have a neighbor  on the path is minimum. They prove that in bounded degree graphs this can be solved in polynomial time for the unweighted case, but becomes $NP$-hard in the weighted case, even with degree bound 4. (Note: The reference was found as an answer to the question What is the complexity of this path problem?)

What are some other interesting problems of this nature, that is, when switching to the weighted version causes a "complexity jump?"

In the world of approximation algorithms there is the capacitated vertex cover problem.
Given $G=(V,E)$ and integer capacities $c(v)$ for each $v \in V$ the goal is to find
a minimum sized vertex cover for $G$ where the number of edges covered by $v$ is at most $c(v)$. This problem has a constant factor approximation in the unweighted case (that is, we want to minimize the size of the vertex cover) while it is $\Omega(\log n)$-hard (unless $P = NP$) in the weighted case (each vertex has a weight $w(v)$ and we want to minimize the weight of the cover).


$\mathsf{NP} \cap \mathsf{coNP}$ as oracle Does $\mathsf{NP^{NP \,\cap\, coNP}=NP}$ hold?

Clearly $\mathsf{NP^{NP}\neq NP}$, but it seems to me that $\mathsf{NP\cap coNP}$ is "deterministic" which makes me believe this is true.

Is there a simple proof (or maybe just by definition)?

Yes. Indeed, an oracle $A$ satisfies $\mathsf{NP}^A=\mathsf{NP}$ if and only if $A \in \mathsf{NP} \cap \mathsf{coNP}$. This class is called $\mathsf{Low(NP)}$ or sometimes $\mathsf{L_1 P}$ (see the link and the paper cited there for more of an explanation of the low hierarchy in general).

Your intuition about "determinism" is actually somewhat correct (although it's not deterministic enough for us to conclude $\mathsf{P} = \mathsf{NP} \cap \mathsf{coNP}$). Try this as an exercise and you'll see this intuition vindicated: first show - carefully, spelling out the details - that if $A \in \mathsf{P}$, then $\mathsf{NP}^{A} = \mathsf{NP}$. Figure out exactly the part of your proof that doesn't work if you only assume $A \in \mathsf{NP}$, and then realize why that part does work when $A \in \mathsf{NP} \cap \mathsf{coNP}$.

(Showing the converse is not too difficult either: $\mathsf{NP}^A = \mathsf{NP}$ implies $A \in \mathsf{NP} \cap \mathsf{coNP}$.)


Is the topsort from "Structuring Depth-First Search Algorithms" guaranteed to be (reverse) stable? In "Structuring Depth-First Search Algorithms in Haskell", implemented in Data.Graph in the Haskell standard library, an algorithm for topologically sorting graphs is given:

postorder :: Tree a -> [a] -> [a]
postorder (Node a ts) = postorderF ts . (a :)

postorderF   :: Forest a -> [a] -> [a]
postorderF ts = foldr (.) id $ map postorder ts

postOrd :: Graph -> [Vertex]
postOrd g = postorderF (dff g) []

topSort      :: Graph -> [Vertex]
topSort       = reverse . postOrd

Experimentally, this topological sort seems to be stable with respect to the reverse of the input graph, e.g.:

Prelude> import Data.Graph
Prelude Data.Graph> let d = buildG (0,3) []
Prelude Data.Graph> topSort d
[3,2,1,0]

Is this actually true? That is, given an ordered list of nodes $N$ with edges $E$, is the result of topSort on this graph an ordering of nodes such that if there is no path from $n_1$ to $n_2$, the ordering of $n_1$ and $n_2$ from the original list is swapped from in the topologically sorted list?

As an extra thought, is there an elegant way to rewrite this algorithm so that it doesn't reverse the original order?

Stripping the Haskell encryption from your question (and ignoring why you are using dff instead of dfs to get a search that respects a given order), you appear to be asking about the stability of the topological sorting algorithm that performs a depth first search and reverses a postorder traversal of the depth-first spanning forest. However, there is a more general answer to your question: it is not generally possible, given a sequence of vertices in a DAG, to find a topological ordering that respects the input sequence for all incomparable pairs of vertices in the DAG. That is, stable topological ordering is not possible.

To see this, consider a DAG with three vertices $a$, $b$, and $c$, and one edge $a\rightarrow b$, with the vertex ordering $bca$. The DAG has three topological orderings $abc$, $acb$, $cab$, but none of these are stable: $abc$ and $acb$ both reverse the pair $ca$, and $acb$ and $cab$ both reverse the pair $bc$.

For the same reason, reverse-stable topological ordering is also not possible. In particular the reverse-postorder-dfs algorithm is not reverse-stable.


Find a boundary from set of 3d line segments I have a set of n 3d line segments  [(p1_start,p1_end), (p2_start,p2_end),....(pn_start,pn_end)].
(I believe that they shod be nin-intersecting...)
These segments represent a (closed) boundary.  I am looking for effective algorithm to generate this boundary, i.e. to find the order of segments for boundary :  [pj_start,pj_end, ...p1_start, p1_end.....]
(segments can be connected via their ends: start to start , start to end, end to start, end to end)
I thought to start from arbitrary segment , say s = (pm_start, pm_end),
among all other segment find the one , which distance to pm_start or  pm_end is minimal, and add this segment end based on calculated minimum distance and continue this way for all segments
The complexity of this approach is not good
Can anyone propose effective algorithm for this problem

For each segment extract the two endpoints (remembering which segment they came from), now sort the endpoints by (say) lexicographical ordering. Any two endpoints that are the same are now adjacent. so, scan the sorted list, attache adjacent segments that share endpoints, and then read the cycle by following the resulting list like structure among the segments.
One can improve the running time to linear using hashing and the floor function, etc.


Graphs-like data structure with weighted vertices I am searching for literature related to a graph-like data structure where vertices are weighted instead of edges.
Formally, we can define a weighted-(edge)-graph $G=(V,E, w(\cdot))$ as a tuple of vertices $V$ and edges $E$ and a weights function $w: E \to \mathbb{R}$.

Now, I want to define a new data structure say a weighted-vertex graph as a tuple $(V,E,w(\cdot))$ of vertices $V$, edges $E$ and a weights function $w: V \to \mathbb{R}$

This seems related to graph coloring. Indeed, if we restrict to integer weights, then we can define vertex-colored graphs exactly this way.
My questions are as follows:

Is the formulation of weighted-vertex graph somehow equivalent to the standard formulation of an undirected weighted-(edge)-graph? (The answer to this is most likely no)
What are some problems/algorithms studied for weighted-vertex-graphs? As mentioned before, graph coloring is one major class of problems if we restrict to integer weights. Are there any other problems with integer weights or can every problem be formulated as a coloring problem? What about for real weights?

For example, one possible problem comes to mind. (I don't know if this has been studied)

Suppose $G_0 = (V,E,w_0)$ and $G_1 = (V,E, w_1)$ are weighted-vertex-graph that share the same vertices and edges (but different weights). An "action" for a vertex $v$ consists of distributing $w(v)$ equally to its neighbors and then setting $w(v) = 0$. Graphs $G_0$ and $G_1$ are called vertex-weight-isomorphic if you can convert from $G_0$ to $G_1$ using a finite sequence of actions. Find an algorithm that outputs whether two graphs are vertex-weight-isomorphic.

I haven't given this specific problem much thought so it's possible it can be converted to a problem in standard graphs but it seems like these types of problems might be interesting.

Your description of an example of your question #2 of having vertex weights and distributing the weight on some $v$ to its neighbours sounds reminiscent of the discharging method famously used in proofs towards the 4-colour theorem. That method, though, had weights assigned to vertices and to the faces of the (planar) graph. But I believe the discharging method has found other applications. Here is a thesis on discharging methods: https://tel.archives-ouvertes.fr/tel-02083632/document
As for your general question #2 of example problems studied with vertex weights, consider looking up

graceful labelings (e.g. https://en.wikipedia.org/wiki/Graceful_labeling)
channel assignment problems (e.g. https://www.sciencedirect.com/science/article/pii/S0166218X04002562)
any vertex selection problem (like max clique, min vertex cover, etc) has a vertex-weighted analogue
problems that choose orderings of vertices (i.e. assign a timestamp to vertices) like in fire-fighter problems (https://www.sciencedirect.com/science/article/pii/S0012365X0600776X)  or graph burning problems (https://arxiv.org/abs/1507.06524)
the definition of threshold graphs involves looking at a vertex-weighted graph and adding an edge between any two vertices whose sum of vertex weights exceeds some threshold value: https://en.wikipedia.org/wiki/Threshold_graph

Here is a paper talking about more application problems of vertex-weighted graphs: https://www.researchgate.net/publication/268065544_Vertex-weighted_graphs_and_their_applications


Data structure for getting all matches of a prefix from a large list of strings Suppose I have a very long list of strings (millions of them), ordered by importance. For example:

...
barracudas
oftwalj
velasp
offso
skenep
vitriolic
offscre
...

What is an appropriate data structure for storing this data to make it efficient to obtain all matches of any prefix? For example, I may want to search for the prefix of, which should return oftwalj, offso, offscre, etc. in the order of importance.

Things I have used in the past to solve this problem:

Linear search - eventually became too slow as the list became very large.
Storing the data in a simple hash table, where the key is the prefix, and the value is the list of words matching the prefix together with their "importance score" - this works, but the space requirement is high.

For a fixed-length prefix, store them in a hash table.  For a variable-length prefix, use a trie.

If you have a static list and don't need to support insertions or deletions into the list, storing them in sorted order by lexicographic order also works, as you can use binary search to find the matches (they will all be consecutive).


NP-hard problems on the class of caterpillars My question is whether there exist an NP-hard problem that has only a caterpillar as input.

By saying only caterpillar as input, I wanted to emphasize that no function (eg: weights on vertices or edges) or specially chosen vertex (or edge) or anything like that is part of the input.

Instance: a caterpillar $T$
Question: __________

There are two similar question in the site: NP-hard problems on trees, NP-hard problems on paths. Note that all answers for the latter problem needs more than one path in input and/or additional structures (edges weights, for instance). In fact, so are most (but not all) answers of the former problem (on trees) as well.

I feel that it is implausible to have an NP-hard problem that take only a path as input. But, it is possible to have an NP-complete problem that take only a caterpillar as input (isn't it?).

Update: I am interested in problems that are naturally defined on caterpillars. True, we cannot define naturality: but we can sense it when we see it.

Thank you

A caterpillar is equivalent to a list of integers $n_1,n_2,...,n_m$ (given in unary), in which integer $n_i$ represents a central node $i$ and its $n_i$ neighbours.

So your question could be rephrased: "Are there hard problems in which the input is a list of (unary) integers?"

Clearly this is cheating, but a list of integers can encode everything (e.g. a binary number $(0,1,0,0,1,1,0,1)$, a string, a graph, ...), so given a polynomial time instance decoding/encoding algorithm, every problem (in particular all NP-complete problems) can be translated to a problem on a single caterpillar; note that this is not valid for problems in which the input is a single path given in unary: in this case we end up to the open (is it still open? :-) question $P=^?NP$ (through TALLY).

You could change your question to "Are there natural hard problems on caterpillars?", but like in many other contexts the word natural (probably) cannot be defined formally.

As a trivial (fairly natural :-) example of NP-hard problem: "Given a caterpillar $n_1,n_2,...,n_{3m}$ of length $3m$, can it be rearranged into a new caterpillar $n_{j_1}, n_{j_2}, ..., n_{j_{3m}}$ such that all groups of consecutive 3 central nodes (starting from the first) has the same number of total neighbours? ($n_{j_1} + n_{j_2} + n_{j_3} = n_{j_4} + n_{j_5} + n_{j_6} = ...$ and so on)


Uniform mortality problem for Turing Machines Consider the following generalisation of the mortality problem for Turing Machines.

  Given a Turing Machine $M$. Is there a bound $k_M$ such that starting
  from any configuration $c$ machine $M$ stops after at most $k_M$ steps?

Is the presented problem (un)decidable? Can you provide any references?

We stress that "configuration" here means any possible configuration, not only the initial one.

The mortality problem is undecidable (P.K. Hooper, Th eUndecidability of the Turing Machine Immortality Problem (1966))

The uniform mortality problem undecidability follows from the following:

Theorem: A Turing machine is mortal if and only if it is uniformly mortal

I found the proof in: Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Undecidable Boundedness Problems for Datalog Programs. J. Log. Program. 25(2): 163-190 (1995)

Proof: Let $\delta_1,...,\delta_n$ be the possible transitions of $M$. We call a sequence $\delta_{i_1},..,\delta_{i_k}$ of transitions consistent if it reflects a computation of $M$, i.e., if there exists a configuration $c = (l,s,r,q)$ ($l$ left tape, $s$ symbol under head, $r$ right tape, $q$ current state) from which $M$ will execute that sequence.

Now arrange all consistent transition sequences in a (possibly infinite) tree, with the empty sequence at the root and each node extending the sequence at its parent by one transition. This tree is of bounded degree. Also (1) $M$ is mortal iff there is non infinite path in the tree, and (2) $M$ is uniformly mortal iff there are no arbitrarily long paths in the tree. By Konig's Lemma (in a tree of bounded degree there is an infinite path if and only if there is a family of paths of unbounded length), these two conditions are equivalent.


Example of a function that you can write in Calculus of Constructions but not in System-F It's been suggested in an answer to this question that the Calculus of Constructions has more computational strength than System-F. What are examples of functions that you express in CoC that you cannot write in System-F?

Since the CoC has dependent types and system $F$ does not, I'll assume you mean a function whose types is in system $F$, but whose definition can only be written in CoC. Luckily in this case we can restrict to system $F_\omega$, which can express the same non-dependent functions as CoC, by some erasure argument.

In general, a rule of thumb to construct such functions is to consider systems $F$ and $F_\omega$ as the language of realizers of theorems of 2-nd and higher-order arithmetic, respectively, and to prove a theorem of the form $\forall x, \exists y, P$ in one not provable in the other, which by extraction should be a function definable in one and not the other.

One such theorem is the proof of normalization of system $F$ itself, which is provable in higher-order arithmetic using the "standard" proof, and not in 2nd order arithmetic by a simple diagonalization argument (though it is instructive to see where the standard proof fails).

Extracting this gives a normalization function for encodings of system $F$ terms, definable in system $F_\omega$, but not in system $F$.

I've explained this a bit in a related answer.