texts: A conjecture on 4-coloring maximal planar graphs

texts:
The question/task is to prove/disprove the conjecture below.
Let $G$ be a maximal planar graph with a 4-coloring $f$. Let $(a,b,c,d)$ be a cycle in $G$. Let $S$ be the collection of all $a,c$-paths in $G$ and all $b,d$-paths in $G$.
Conjecture: At least two members of $S$ are bicolored.
(i.e., there exist distinct paths $Q_1,Q_2\in S$ and colors $i,j,k,l\in\{1,2,3,4\}$ such that $f(u)\in\{i,j\}$ for every vertex $u$ on $Q_1$ and $f(v)\in\{k,l\}$ for every vertex $v$ on $Q_2$).
Definitions:-
$G$ is a maximal planar graph if it can be drawn on a plane such that no edges cross and boundary of every face is a triangle. A 4-colouring $f$ of $G$ is a function $f:V(G)\to\{1,2,3,4\}$ such that $f$ map endpoints of each edge to different 'colors' (i.e. $f(u)\neq f(v)$ for every edge $uv$ of $G$).
Notes:-
It is easy to see that the conjecture is true if the cycle $(a,b,c.d)$
is tricolored (or bicolored). The following is the crux of the conjecture.
Let $G$ be a planar graph with a 4-coloring $f$. Let $(a,b,c,b)$ be a cycle in $G$ such that boundary of each face inside the cycle is a triangle. Suppose that the cycle $(a,b,c,d)$ receives all four colors.
Conjecture 2: Then, there is a bicolored $a,c$-path or a bicolored $b,d$-path inside the cycle.
If Conjecture 2 is true, then the main conjecture above is true (apply Conjecture 2 to outside region of the cycle $(a,b,c,d)$ ).


texts:
I am currently trying to understand whether I can make some claims about the relation between eigenspaces of a sparsifier and the original matrix. In this context, let me first define a couple of entities.

Definition 1: Partial Ordering Among Matrices:
We say that two commuting matrix $\mathbf A,\mathbf B$ have a partial ordering $\mathbf A \preceq \mathbf B$ if the matrix $\mathbf B - \mathbf A$ is positive semidefinite, i.e. $\vec x^T (\mathbf B - \mathbf A) \vec x \geq 0 $ for all non-zero $\vec x$.
Now with this definition we can define an $\epsilon$-approximation of the graph to be $(1- \epsilon) \mathbf B \preceq \mathbf A \preceq (1+\epsilon) \mathbf B$, i.e. $\mathbf B$ is an $\epsilon$-approximation of $\mathbf A$ (definitions vary here slightly).

Spielman and Peng famously gave the first algorithm to spectrally sparsify a graph, i.e. given a graph $G=(V,E)$, the algorithm returns a graph $H$ such that $H$ is an $\epsilon$ spectral approximation of $G$, with average degree $\mathcal{O}(1/\epsilon^2)$ (~ sparsity).
These spectral sparsifiers can then in turn be used to solve e.g. Laplacian systems in nearly linear time (nowadays I believe linear time was achieved by Joannis Koutis et al., or others around M. B. Cohen).

Now the question I have is the following:
Usually when comparing the solution of linear systems, instead of inverting the matrix, some sort or polynomial is used to approximate the inverse. Hence, the eigenspaces of the (pseudo-)inverse and the polynomial is the same and we can easily show that the eigenvalues of the polynomial and the inverse are all $\epsilon$-close. How does this change for a general case, wehere $\mathbf B$ is a spectral sparsifier of $\mathbf A$? Can I say anything about the relationship between eigenspaces?

My idea was to use the eigenvalue decomposition of both matrices and project the basis of $\mathbf B$ into the basis of $\mathbf A$. However this doesn't seem to give me a more qualitative understanding. Are there any ways to bound the differences eigenspaces? It seems that in the worst case the sum of plus and minus terms could cancel out each other allowing for quite large ranges of distances (from the projections) between the actual eigenvectors of $\mathbf A$ and $\mathbf B$?


texts: Small $\epsilon$-nets for points and half-planes without VC dimension

texts:
I have recently learned the proof of Haussler and Welzl of the following theorem.

Theorem. Suppose we have a set system $\mathcal{F} \subseteq 2^X$, where $X$ is a finite set. Suppose $\mathcal{F}$ has VC-dimension $d$. Then for every $\epsilon > 0$ there exists a hitting set ($\epsilon$-net) of size $O(\frac{d}{\epsilon} \log \frac{1}{\epsilon})$ of the following subfamily of $\mathcal{F}$: $\{F \in \mathcal{F} \mid |F| \geq \epsilon |X|\}$.

The proof itself is essentially a probabilistic argument. Despite its simplicity it looks very unnatural (we consider very mysterious coupling).

There is an interesting non-trivial case: suppose $X$ is a finite set of points in $\mathbb{R}^2$ and $\mathcal{F}$ is a family of subsets of $X$ which can be separated from their complements by half-planes. It is easy to check that in this case $d = 3$.

Is there a proof of the existence of a good $\epsilon$-net in this case from the first principles (without introduction of VC-dimension)?


texts: Career advice needed: Switching from theoretical CS to pure math

texts:
I couldn't think of a better forum to ask this question. I am a first year cs graduate student. I couldn't really pursue theoretical cs during my undergrad, but as part of our PhD qualifiers, i had to take computability and complexity theory,  advanced algorithms, and i loved those courses. More than the computational aspects, i enjoyed the theoretical aspects and rigorous proofs. This kindled a lot of interest in me and I checked out Enderton's set theory, which i liked. Right now I am going through Spivak's Calculus in order to refresh my knowledge for a real analysis course next semester. Lately, i have been feeling that i would love learning and doing pure math more than applied CS. I know theoretical CS is an option, but i feel i would enjoy pure math more.

So my question is, whether introductory graduate level courses on algorithms and complexity theory involve enough rigor and abstract concepts (computability and complexity theory) that i am not underestimating pure math. I would really appreciate sincere inputs. I am thinking of taking standard analysis, algebra, topology sequence next year and find a professor to work with.


texts:
I have been wondering about comparison versus RAM models and have some very basic sounding questions.

Is there a name for the subset of P (or FP really) that is computable by comparison RAM algorithms? For the avoidance of confusion we can think of the comparison RAM model as just being the normal RAM model where the input symbols are given in terms of rows/columns of a ternary matrix that tells us if pairs of symbols are bigger, the same, or smaller.  That is we never get to find out or use the value of the input symbols.

What are the biggest known gaps for the time complexity of RAM and comparison RAM algorithms for natural problems coming from this subset of P (or FP)? We can imagine unnatural examples where comparisons are constant time but the RAM model has to spend a lot of time inputting the bits.  Those are not the ones I am interested in.  Sorting is the simplest example with a log gap for poly size inputs but is there anything bigger?

Related to the last question, is there some reason to suppose a maximum gap between (natural) RAM and comparison RAM problems? I suppose one route would be to say that you could simulate one with the other efficiently.


texts: Quantum capacity for ensemble of Pauli channels

texts:
In Preskill's quantum computing notes Chapter 7 approximate page 82, he shows that a Pauli channel has capacity $Q \geq 1-H(p_I,p_X,p_Y,p_Z)$ where $H$ is Shannon entropy and $p_I, p_X, p_Y, p_Z$ are the probabilities of the channel acting like the appropriate Pauli matrix. In particular this gives us the 'hashing bound' or 'random coding bound' for the quantum capacity of the depolarizing channel $Q(p) \geq 1-H(p,1-p)-p\log_23$.

He then describes work of Shor and Smolin [1]: if you take a $m$-repetition code and concatenate it with a suitable random code you can do better than the hashing bound. The argument for this is that taking $m-1$ measurements the inner repetition code thought of as a super channel is a Pauli channel with entropy $H_i$. Then averaging over the $2^{m-1}$ possible classical measurements you can find the average entropy of the superchannel $\langle H \rangle$.

[1] P.W. Shor and J.A. Smolin, “Quantum Error-Correcting Codes Need Not Completely Reveal the Error Syndrome” quant-ph/9604006; D.P. DiVincen, P.W. Shor, and J.A. Smolin, “Quantum Channel Capacity of Very Noisy Channels,” quant-ph/9706061.

Then by random coding on this new channel you can achieve a rate $R=\frac{1-\langle H \rangle}{m}$ (dividing by $m$ to get this rate in bits/original channel use).

I don't see how random coding works. You have a random code which is optimal for each particular channel but how do you decide which one to use? By the time you know the classical measurements for your channel you have already sent the codeword.

So two questions:

1) If you have an ensemble of Pauli channels with average entropy $\langle H\rangle$, can you by using random coding achieve a rate $1-\langle H \rangle$?

2) If you can't do this, am I misinterpreting the results of Shor and Smolin or Preskill's exposition?


texts: AMQ (Bloom-filter like structure) lower bounds

texts:
I want an Approximate Member Query structure (that is, something like Bloom filter), but with the highest possible compression ratio. I know that for AMQs where query is done in constant time, the number of bits taken is proportional to the number of items.

I want to go below that, possibly even below 1 bit per item, or below O(n).

My assumptions are humble. For each key in the set, the AMQ has to return positive. For a key not in the set, the probability of false positive must be at most 50%.

I had one idea. Let's make a normal Bloom filter storing n keys, using only one hash and 2n bits. At most half of the bits will be set, so the probability of false positive is below 50%.
Then I thought we could just compress the resulting filter using Huffman encoding. The size of the resulting structure would be O(n) in the number of objects stored, but it could be lower than 2 bits per object.

Question 1.: is there any known lower bound for the size of AMQ for given false positive probability, dropping the assumption that query must be constant time?

Question 2.: Are there any practicals algorithms in use capable of doing that, beyond Bloom filter, quotient filter and cuckoo filter?


texts: Hardwiring the output in a quantum circuit

texts:
In this paper, while using a diagonalization argument in Section $5$, the authors write:

Fix some enumeration over all $poly(n)$-size quantum verifiers $M_{1},
 M_{2},...$ which we can do because the number of such machines is
countably infinite (by the Solovay-Kitaev theorem [15]). Some of these
verifiers may try to decide a language by trivially “hardwiring” its
outputs; for example, by returning 1 independent of the input. We
start by fixing a unary language $L$ such that no machine $M_{i}$ hardwires
the language. We can always do this because there are more languages
than $poly(n)$-sized machines.

Maybe I am missing something very basic, but:

Why do we care if some of the verifiers have the output hardwired?
How/why can we find an $L$, like in the description? Why will this $L$ even be decidable? I know there are more languages than there are Turing machines, but those extra languages aren't decidable.


texts:
A function $f\colon\{0,1\}^n\to\{0,1\}$ is called an affine disperser for dimension $d$, if for every affine subspace $S\subseteq \{0,1\}^n$ of dimension at least $d$, $f$ is not constant on $S$. This means that $n-d$ linear substitutions of the form
$x_i=\bigoplus_{j\neq i}{x_j\cdot b_j}\oplus b_0$, where $b_i\in \{0,1\}$ do not make the function constant.

For example, the inner product function $IP(x_1, y_1, \ldots, x_{n/2}, y_{n/2})=\bigoplus{x_i\cdot y_i}$ is an affine disperser for dimension $\frac{n}{2}+1$.

Using the probabilistic method one can easily show that affine dispersers for dimension $o(n)$ do exist.

Ben-Sasson and Kopparty, Shaltiel showed that there are affine dispersers for dimension $o(n)$ in P.

Let's say that a function $f$ is a $2$-affine disperser for dimension $d$, if it is not constant after $n-d$ substitutions of the form $x_i=b$ and $x_i=x_j\oplus b$, where $b$'s are constants. It is possible to show (Lemma~$4$ in Paturi, Saks, Zane) that almost all polynomials of degree $2$ are $2$-dispersers for dimension $o(n)$ ($k$-wise independent distributions allow us to derandomize the construction to obtain an explicit function).

It seems that this restriction to 'short' substitutions makes it much easier to find explicit affine dispersers. The first question is: do you know a 'simple' argument showing that some 'explicit' function is a $3$-affine disperser for dimension $o(n)$? By this I mean a function $f\in NP$ which does not become a constant even after $n-o(n)$ substitutions of the form $x_i=x_j\oplus x_k\oplus b$.

Let's consider the following extension of affine dispersers. Now we allow linear and 'quadratic' substitutions. We start with a function of $n$ variables. Then we make a substitution of the form $x_i=\bigoplus_{j\neq i}{x_j\cdot b_j}\oplus b_0$ or $x_i=(x_j\oplus b_j)\cdot(x_k\oplus b_k)\oplus b$, s.t. the substitution makes it a function of $n-1$ variables (i.e., after substituting $x_i$, it will never appear in the subsequent substitutions). We make $n-k$ substitutions as above and require the resulting function of $k$ variables to be non-constant. Again, the probabilistic argument shows that these functions exist for dimension $k=o(n)$. My main question is whether it is possible to find dispersers of this kind for dimension $o(n)$ in NP?

If it helps, we may consider functions with $o(n)$ outputs rather than functions outputting one bit only.


texts: Complexity consequence of logarithmic boolean width of co-bounded degree graphs?

texts:
The paper On graph classes with logarithmic
boolean-width claims that the
boolean width of co-k-degenerate graphs is at most $k\log{n}$
and a lot of graph vertex partition problems can be solved in
polynomial time.

co-k-degenerate graphs include complements of bounded degree graphs.
Clique is NP-hard on co-maximum degree 4.

On the other hand,
graphclasses.org claims
that clique is boolean width fixed parameter tractable, giving clique
width as reference. Since $\exp{\log{n}}=n$ it could be polynomial.

Are there complexity consequence of logarithmic boolean width of
co-bounded degree graphs? Like ETH not holding for them?


texts: What is the complexity of distinguishing a true Fourier spectra from a fake one?

texts:
A $PH$ machine is given oracle access to a random Boolean function $f:\{0,1\}^n \to \{ -1,1 \}$ , and two Fourier spectra $g$ and $h$.

The Fourier spectra of a function $f$ is defined as $F:\{0,1\}^n \to R$:

$F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x)$

One of $g$ or $h$ is the true Fourier spectra of $f$ and the other one is just a fake Fourier spectra belonging to an unknown random Boolean function.

It is not hard to show that a $PH$ machine, cannot even approximate $F(s)$ for any $s$.

What is the query complexity of deciding with high success probability which one is the true one ?

It is interesting to me, since if this problem is not in $PH$, then one can show that there exists an oracle relative to which $BQP$ in not a subset of $PH$.


texts:
Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am looking in particular to find minimum distance of binary (codes over $\mathbb{F}_{2^l}$) quasi-cyclic  of rate q/q+1. Parity check matrix for such codes have a structure
$H=[I|C_1|C_2|...|C_m]$ where each $C_¡$ is a from class of circulant matrices. It may be useful that one can treat these codes as modules.
Or even if there are any approximate algoruihms for this ?


texts: Is there a well-defined division operation on finite automata?

texts:
Background:

Given two deterministic finite automata A and B, we form the product C by letting the states in C be the cartesian product of states in A and states in B. Then, we choose transitions, initial state, and final states so the language accepted by C is the intersection of the languages for A and B.

Questions:

(1) Can we "divide" C by B to find A? Is A even unique, up to isomorphism? We care about the state diagrams, not the languages here and below. Thus, we don't allow compressing the state diagrams to reduce the number of states.

(2) If A is unique, is there an efficient algorithm to find it?

(3) Does every deterministic finite automaton have a unique factorization into "primes". A prime here means an automaton that cannot be factored, that is, written as a product of 2 smaller automata.

Work with @MichaelWehar


texts: Lower bound on maximum simple cycle in connected cubic bridgeless graphs

texts: I would like to ask if anybody knows any result on the least number of edges the maximum simple cycle of connected cubic bridgeless graphs, must have. Thanks


texts: Equivalence for Constant-width Read-Once Branching Programs with Distinct Orders

texts:
Let $X={x_1,...,x_n}$ be a set of variables and $\pi:[n]\rightarrow [n]$ be a permutation of the $n$-element set $[n]=\{1,...,n\}$.

A $\pi$-OBDD is an oblivious, read-once branching program where the variables are tested in the order $x_{\pi(1)}x_{\pi(2)}...x_{\pi(n)}$. The width of an OBDD $F$ is the maximum number of nodes in a layer of $F$.

Let $c$ be a constant. Given a $\pi_1$-OBDD $F_1$ and a $\pi_2$-OBDD $F_2$, both of width at most $c$, where $\pi_1$ and $\pi_2$ are possibly distinct permutations, what is the complexity of determining whether $F_1$ and $F_2$ represent the same function?

Obs: If $\pi_1 = \pi_2$ then testing whether $F_1$ and $F_2$ represent the same function can be done in polynomial time via classic automata-theoretic techniques.


texts: What are theoretical computer science jobs?

texts:
Beside academia which is clearly the home of theorists, I am wondering about industrial jobs related to theoretical computer science, the ones which demand pure mathematical background.

Cheers !


texts: Which $AC^0$ problems are not "truly feasible"?

texts:
Neil Immerman's famous Picture of The World is the following (click to enlarge):

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

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


texts:
Let $A$ be an $(n\times n)$-matrix with entries from $\{0,1\}$ and $B$ its biadjacency matrix $B = \begin{pmatrix} 0 & A\\ A^t & 0 \end{pmatrix}$.

My simple question is: Is there a relationship between the planar-property of the graph $\mathcal{G}_A$ (the graph constructed from the matrix $A$) and $\mathcal{G}_B$?  Note that the graph $\mathcal{G}_B$ is necessarily undirected and loop-free.

(A good answer would be, e.g., that if $\mathcal{G}_A$ is planar, $A$ has to have some additional properties therewith $\mathcal{G}_B$ will be also planar)

Update: A property $\mathcal{G}_A$ must have therewith planarity passes on to $\mathcal{G}_B$ is to be bipartite. In that case $\mathcal{G}_B$ is the graph that consists of two disconnected copies of $\mathcal{G}_A$.


texts: Uniform derandomisation of circuit complexity classes

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

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

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

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


texts: The power of randomized logspace with two-way access to the random tape

texts:
Let $\mathsf{ZPL}$/$\mathsf{RL}$/$\mathsf{BPL}$ denote the classes of the languages which are accepted (with zero/one-side/two-side error) by a logspace Turing machine with one-way access to the random tape.

Let $\mathsf{ZP^*L}$/$\mathsf{R^*L}$/$\mathsf{BP^*L}$ denote the corresponding classes by replacing one-way to two-way access.  We have the normal inclusions $\mathsf{ZPL} \subseteq\mathsf{RL}\subseteq\mathsf{BPL}$ and $\mathsf{ZP^*L} \subseteq\mathsf{R^*L}\subseteq\mathsf{BP^*L}$.

In the following paper,

  On Read-Once vs. Multiple Access to Randomness in Logspace, Noam Nisan, 1995

he prove that $\mathsf{BPL} \subseteq \mathsf{ZP^*L}$, which is rather surprising because it seems that two-way access may be stronger than the one-way access.

  Question.  Do we have any further results which demonstrate the power of two-way access randomized logspace?


texts: Can NP-hard statements be proved by PCPs that only involve reading 2 bits?

texts:
For non-negative integers q, let PCP(q) denote the set of promise problems

that have polynomial-length probabalistically checkable proofs

over the binary alphabet in which the verifier only reads q bits.

(with no restriction on the amount of randomness that the verifier can use)

Let sPCP(q) denote the analogous class in which the verifier has

perfect completeness and chooses the bits to read non-adaptively.

(sPCP stands for "strong PCP", a term I made up for this question)

Obviously, $\:$PCP(0) = promiseBPP$\:$.

It is slightly less obvious, but still easy to show, that $\:$PCP(1) = promiseBPP$\:$.

It is known, though highly non-trivial, that $\:$NP $\subseteq$ sPCP(3)$\:$.

Since $\:$2SAT $\in$ P$\:$, $\:$ one has $\:$sPCP(2) $\subseteq$ promise-coRP$\:$ by reasoning similar to the PCP(1) equality.

However, that does yield any comparison between PCP(2) and NP.

  Is either $\;\;\;$NP $\subseteq$ PCP(2) $\:$ or $\:$ PCP(2) $\subset$ NP$\;\;\;$ known to hold under plausible assumptions,

  such as the promise versions of $\:$ P = BPP $\subset$ NP = MA ≠ coNP $\:$ ?


texts: I want good sources for starting with decision tree complexity and query complexity , what papers to start with ? what book chapters to read ? I already seen arora and barak book and I begin to read it ... so any other suggestions will be welcomed ...


texts:
When I teach tail bounds, I use the usual progression:

If your r.v is positive, you can apply Markov's inequality
If you have independence and also bounded variance, you can apply Chebyshev's inequality
If each independent r.v also has all moments bounded, then you can use a Chernoff bound.

After this things get a little less clean. For example

If your variables have zero mean, then a Bernstein inequality is more convenient
If all you know is that the combining function is Lipschitz, then there's a generalized McDiarmid-style inequality
if you have weak dependence then there are Siegel-style bounds, (and if you have negative dependence, then Jansson's inequality might be your friend)

Is there a reference anywhere to a convenient flowchart or decision tree describing how to choose the "right" tail bound, (or even when you have to dive into a sea of Talagrand) ?

I'm asking partly so that I have a reference, partly so that I can point it to my students, and partly because if I'm sufficiently annoyed and there isn't one, I might try to make one myself.


texts: Complexity of optimization over unitary group

texts:
What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$?

A typical task, arising often in quantum information theory, would be maximizing a quantity of type $\mathrm{Tr}AUBU^{\dagger}$ (or higher order polynomials in $U$) over all unitary matrices $U$. Is this type of optimization efficiently (perhaps approximately) computable, or is it NP-hard? (maybe this is well known, but I've been unable to find any general references)


texts:
$(k,j)$-projective clustering is the natural generalisation for k-clustering, in which one needs to find $k$ $j$-flats in $\mathbb{R}^d$ that minimizes the cost function as defined below:

Given a $j$-flat $f$ in $\mathbb{R}^d$, and a point $x$ in $\mathbb{R}^d$, define $dist(x,f) = \min_{q\in f}{||x-q||}$.

Given a set of $k$ $j$-flats $F$ in $\mathbb{R}^d$, and a point $x$ in $\mathbb{R}^d$, define $dist(x,F) = \min_{f\in F}{dist(x,f)}$.

Given a set $P$ of $n$ points in $\mathbb{R}^d$, a set of $k$ $j$-flats $F$ in $\mathbb{R}^d$, define the cost function as $cost(P,F) = \sum_{p\in P}dist(p,F)^2$.

This paper gives a PTAS for this problem with a running time $O(d(\frac{n}{\epsilon})^{\frac{jk^3}{\epsilon}})$. Further research also gives bicriteria approximation for this problem. A very general framework is given in this paper that achieves better bounds (but not a PTAS).

It would be very nice to have some input from the cs theory community. Some reference to recent paper regarding this problem would be greatly appreciated.

Thanks


texts: What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?

texts:
I asked this question some weeks ago at mathoverflow, but I got no reply.

Here, by 3D-grid of sidelength $k$ I mean the graph $G=(V,E)$ with $V= \{1,\ldots,k\}^3$ and $E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$, i.e., the nodes are placed at 3-dimensional integer coordinates between 1 and $k$, and a node is connected to the at most 6 other nodes that differ in precisely one coordinate by one.

What is the name of this graph? I'll use 3D grid, but perhaps 3D mesh or 3D lattice are what other people are used to.

  What is the treewidth or pathwidth of
  this graph?  Is this already published
  somewhere?

I know already that $tw(G) = (3/4) k^2 + O(k)$, i.e. it is really smaller than $k^2$.
To me, this suggests that the standard arguments showing that the $k\times k$ 2D-grid has treewidth and pathwidth $k$ will not easily generalize.

To see this, we consider a path decomposition that "sweeps" the grid using mainly node-sets of the form $S_c= \{(x,y,z)\mid x+y+z = c\}$.
Observe $|S_c| \leq (3/4) k^2 + O(k)$, $S_{3/2 k}$ being the largest such set.
The sets between $S_c$ and $S_{c+1}$ are created by sweeping with a line and need $O(k)$ additional nodes to be separators. More precisely, use the sets
$S_{c,d} = \{(x,y,z)\mid (x+y+z = c \wedge x \leq d ) \vee (x+y+z = c \wedge x \geq d ) \}$ as a path decomposition of $G$.

I also have an idea for a proof that shows $tw(G) = \Omega(k^2)$, but that is not finished yet.


texts: Approaches to GI inspired by knot problem

texts:
GI and Knot Problem both are problem of deciding structural equivalence of mathematical objects. Are there any results establishing connections between them? Nice connections of knot problem to statistical physics have been explored via knot polynomials, are there similar results for $GI$?

It would be particularly helpful to know if there are any standard results/warnings/suggestions/comments before one start looking into $GI$ motivated by knot problem. Actually, I was wondering if its recommended to explore in this direction for my master's thesis. I am interested in quantum/classical approaches to $GI$ and algebraic problems. Any other suggestions are welcome.


texts: Convergence and representation theorems for machine learning

texts:
I come from a pure math background and am not very familiar with machine learning. So, I'll start with an example to compensate for my confused grasp of the terminology.

Let's say we have a function $f:X \to Y$, and we want to develop a neural network to compute this function. For instance, $X$ could be $\{0, 1, ... 255\}^N$ for some large $N$, and $Y$ could be $\{0, 1\}$, if we wanted to build a network that performs a binary classification on images of $N$ pixels. We have some algorithm which adjusts, maybe stochastically or maybe deterministically, the weights and parameters of our network, creating a sequence of networks which should converge to $f$.

What theorems exist to guarantee that we do indeed converge to $f$, or even that a network exists to represent $f$? If we don't want to make assumptions about $f$, we would need some theorem establishing that given any function $f$, and any initial network, the sequence of networks generated by the learning algorithm will converge to $f$.

I'm not just interested in neural nets, though. Are there textbooks on machine learning which cover this sort of thing in depth? What keywords should I be looking out for?


texts: Minimum number of transpositions to sort a list

texts:
In trying to devise my own sorting algorithm, I'm looking for the optimal benchmark to which I can compare it.  For an unsorted ordering of elements A and a sorted ordering B, what is an efficient way to calculate the optimal number of transpositions to get from A to B ?

A transposition is defined as switching the position of 2 elements in the list, so for instance

1 2 4 3

has one transposition (transposition 4 and 3) to make it

1 2 3 4

Something like

1 7 2 5 9 6

requires 4 transpositions (7, 2), (7, 6), (6,5), (9, 7)

Update (9/7/11): question changed to use "transposition" instead of "swaps" to refer to non-adjacent exchanges.


texts: What mathematical models can analyze and optimize such message passing system?

texts:
I look for a mathematical model that can accommodate, analyze and suggest optimizations for a system that can be humanly described as message passing black box programs to which where optimal message directions shall be suggested depending on their reactions to different messages.

System description:

We have a graph. Its nodes can appear and disappear in time (we know only if node is alive at a discreet moment of time). We can assume that all nodes can be connected one to another via $N $ types of connections (message passing channels and patterns) any node to any node alike ZeroMQ.

Nodes send messages to one to another, messages are different, we know some hash function-based signature for each message and its size. We have f(size,t,c) that describes how fast a message can be passed from one node to another, it uses message size, current time, and c for size of all other messages being sent to this node concurrently.

Each node has a set $M $ of parameters describing their state given via monitoring utilities. We do not know lows of how parameters change, but we know that they change as time goes on and new messages arrive so we can try to approximate them for each node looking at incoming messages and time.

Task at hand

A node can be called "useful" if it receives and sends as much messages as possible, while its values of set M are as low as possible, or if it sends and receives none messages and values of set M are as low as possible.

We cannot control when a node sends a new message we can only tell to the node having current system time, message hash and size where to send it. Our task is to make as much nodes useful as possible.

I seek for a theoretical studies that encountered/solved such or similar problem. At least mathematical models which allows such problem to be solved in your opinion. So a name of the theory + reference to a paper with a model would be the answer.
So what game or any other mathematical model can suggest to which node to send the next message (to make whole system as "useful" as possible)?


texts:
Consider a finite uniform grid $G$ in three dimensions with a function $f$ mapping integer grid positions $p$ to a boolean value $f(p)$ (i.e., a black/white volume image.)

A ball in $f$ is a set of grid points with center $c$ and radius $r$ where $f(p)$ is true for all $p \in G$ with euclidean distance $|c-p| \leq r$.

The maximum ball transform $MB$ finds for each grid point $p$ the radius $r$ of the largest ball in $f$ containing that point.  (Note: This is probably not the actual, commonly used name for this. However I don't know what else to call it.)

Are there good algorithms to compute this transform?

I assume this is related to the (euclidean) distance transform. (Find for each grid point $p$ the radius of the largest disk in $f$ with center $p$.)

$DT(p) = min_{x \in f} |p-x|$

$MB(p) = max_{|x-p| < DT(x)} DT(x)$

In the literature I can find algorithms that compute the euclidean $DT$ (and its reverse) in linear time. There are also algorithms to compute the medial axis transform $MAT$ (the set of all center points of the maximum balls).

Is there a faster algorithm than computing the $MAT$, iterating over all found maximum balls and naively tracking the largest one for each grid point?

Edit:
It seems this is sometimes known as Thickness Distribution or Euclidean Opening Function.

A recent paper computes an approximation: Fast and Accurate Approximation of the Euclidean Opening Function in Arbitrary Dimension (D. Coeurjolly, 2010), (presentation)


texts: Connectivity keeping centralized algorithm for multi-agent network navigation

texts:
We have a network of $N$ agents moving in a field. Every agent has communication bandwidth of range $R$. During the process we must keep all-to-all communication among the agents. So we have constantly the constraint max(inter-agent distance)<=R. At every step of the process a metric is minimized, which depends on the current positions of the agents. This minimization defines the directions which must be followed by the agents during the next step of the algorithm. In general the directions are different for every agent, but can be communicated to the others.
How the agents should be controlled in order to achieve the most efficient motion (in the sense of maximizing the total distance covered in let's say $m$ steps)?

PS I suppose that our approach must be greedy.


texts: What is the time complexity of computing a Fibonacci number of at least n?

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

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

1  2  3  5  8
↑        ↑
↑        subrope
subrope

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

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

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

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

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


texts: Large real-world graphs for teaching use?

texts:
Possible Duplicate:
  graphs from real-life problems

I'm teaching Algorithms for the 7th time or so, and I want augment the class by asking the students to implement some of our thematic algorithms on large graphs.  I could of course just generate random graphs and ask them to find the diameter, shortest paths, strongly-connected components, etc.  But I think it would be more interesting to them if I had a real-world graph derived from news, media, Facebook, or any source that would be familiar to them.

The graphs should be large enough that algorithmic efficiency matters, but not so large that they cannot be handled by commodity computers (ie, they must fit in 1GB of memory).


texts: Is homogeneity required in Hyafil's arithmetic circuit decomposition theorem when applied to monotone circuits?

texts:
I'm new to circuit complexity, and trying to understand Hyafil's decomposition theorem (Theorem 1 in [1], Lemma 3 in [2], Decomposition Lemma in [3], also mentioned in [4]). My question is: Is homogeneity required if we apply this theorem to monotone circuits (i.e. circuits that compute over the semiring of non-negative reals)?
The statement of the theorem is: Let $f$ be a polynomial of degree $deg(f)$ computed by an arithmetic circuit** with $t$ gates. The polynomial $f$ can be written as $f = g_1 \cdot h_1 + \ldots + g_t \cdot h_t$, where $deg(g_i) \le 2deg(f)/3$ and $deg(h_i) \le 2deg(f)/3$.
** with some restrictions
This theorem is proved by repeatedly finding a gate $v$ that computes a polynomial $f_v$ where $deg(f)/3 \le deg(f_v) \le 2deg(f)/3$ and writing the polynomial as $f = f_v \cdot h + f_{v=0}$, where $h$ is some polynomial that must be of degree at most $2deg(f)/3$ and $f_{v=0}$ is the polynomial obtained by setting the gate $v$ to zero.
All statements of this theorem that I have seen require homogeneity of the circuit, which I guess is required for non-monotone circuits. However, to my understanding of the proof it should also work for non-homogeneous monotone circuits. (It should work when for polynomials $g$ and $h$ it holds that $deg(g+h) = \max(deg(g), deg(h))$ and $deg(g \cdot h) = deg(g) + deg(h)$.) Am I missing something?
[1] Hyafil, L. (1979). On the parallel evaluation of multivariate polynomials. SIAM Journal on Computing, 8(2), 120-123.
[2] Valiant, L. G. (1979, April). Negation can be exponentially powerful. In Proceedings of the eleventh annual ACM symposium on Theory of computing (pp. 189-196).
[3] https://arxiv.org/pdf/1803.05380v1.pdf
[4] https://arxiv.org/pdf/1710.09502.pdf


texts: Quantum circuit simulation divergence in results

texts:
I'm learning about quantum computing in order to code a simulator. I tried the following circuit in Quirk

And ran the same circuit using OPENQASM 2.0:

Notice that the input is |11> in both cases, but it seems that the probabilities for 01 and 10 are switched. What I'm missing here? Thank you!


texts:
A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a shuffle of MISIPP and SSISI.  Let me call a string square if it is a shuffle of two identical strings. For example, ABCABDCD is square, because it is a shuffle of ABCD and ABCD, but the string ABCDDCBA is not square.

Is there a fast algorithm to determine whether a string is square, or is it NP-hard?  The obvious dynamic programming approach doesn't seem to work.

Even the following special cases appear to be hard: (1) strings in which each character appears at most four six times, and (2) strings with only two distinct characters.  As Per Austrin points out below, the special case where each character occurs at most four times can be reduced to 2SAT.

Update:  This problem has another formulation that may make a hardness proof easier.

Consider a graph G whose vertices are the integers 1 through n; identify each edge with the real interval between its endpoints.  We say that two edges of G are nested if one interval properly contains the other.  For example, the edges (1,5) and (2,3) are nested, but (1,3) and (5,6) are not, and (1,5) and (2,8) are not.  A matching in G is non-nested if no pair of edges is nested.  Is there a fast algorithm to determine whether G has a non-nested perfect matching, or is that problem NP-hard?

Unshuffling a string is equivalent to finding a non-nested perfect matching in a disjoint union of cliques (with edges between equal characters).  In particular, unshuffling a binary string is equivalent to finding a non-nested perfect matching in a disjoint union of two cliques.  But I don't even know if this problem is hard for general graphs, or easy for any interesting classes of graphs.
There is an easy polynomial-time algorithm to find perfect non-crossing matchings.

Update (Jun 24, 2013): The problem is solved!  There are now two independent proofs that identifying square strings is NP-complete.

In November 2012, Sam Buss and Michael Soltys announced a reduction from 3-partition, which shows that the problem is hard even for strings over a 9-character alphabet.  See "Unshuffling a Square is NP-Hard", Journal of Computer System Sciences 2014.
In June 2013, Romeo Rizzi and Stéphane Vialette published a reduction from the longest common subsequence problem.  See "On Recognizing Words That Are Squares for the Shuffle Product", Proc. 8th International Computer Science Symposium in Russia, Springer LNCS 7913, pp. 235–245.

There is also a simpler proof that finding non-nested perfect matchings is NP-hard, due to Shuai Cheng Li and Ming Li in 2009.  See "On two open problems of 2-interval patterns", Theoretical Computer Science 410(24–25):2410–2423, 2009.


texts: Data structure to determine if sets are disjoint in o(n) time

texts:
My initial question was exactly the title of this post, but after feedback from commenters I have formulated a more precise version of the question that attempts to capture its essence.

Does there exist an encoding of length-$n$ bit strings with the following properties?

The encoding can be computed in $o(n^2)$ time and space, i.e., the encoding $e\colon \{0,1\}^n\to \{0,1\}^{o(n^2)}$ factors as a composition of $o(n^2)$ elementary bitwise operations.
There exists an algorithm computing the disjoint set function with respect to this encoding in $o(n)$ time, i.e., the disjoint set function $e\bigl(\{0,1\}^n\bigr)^2\to \{0,1\}$ factors as a composition of $o(n)$ elementary bitwise operations.

Note: this is inspired by a comment on this unsolved question https://cs.stackexchange.com/questions/96222/find-common-min-in-logarithmic-time


texts: Rademacher Complexity of the Composition with an Indicator

texts:
Consider the statistical learning setting where you have an arbitrary hypothesis space $\mathcal{H}$, a data space $\mathcal{Z}$, and a bounded loss function $\ell: \mathcal{H}\times \mathcal{Z} \rightarrow [0,1]$. Further, for $c\in(0,1)$, let $\mathcal{F}_c$ be the function class defined by
\begin{align}
\mathcal{F}_c := \{ z \mapsto  \mathbb{I}\{\ell(h,z) \leq c\}: h \in \mathcal{H}\}.
\end{align}
Question. Is it in any way possible to relate the Rademacher complexity of the function class $\mathcal{F}_c$, to that of $\ell \circ \mathcal{H}:= \{z\mapsto \ell(h,z): h \in \mathcal{H}\}$?
My goal is to show that when the complexity of the latter class is small, so is the complexity of the former.
Rademacher Complexity. The Rademacher complexity of a function class $\mathcal{F}$ is defined as
\begin{align}
\mathfrak{R}_n(\mathcal{F}) := \mathbb{E}\left[\sup_{f\in \mathcal{F}}\frac{1}{n} \sum_{i=1}^n \sigma_i f(z_i)\right], \quad n \in \mathbb{N},
\end{align}
where $(\sigma_i,z_i)$ are i.i.d. random variables with $(\sigma_i)$ having a Rademacher distribution.
Failed Attempt. There are results on the Rademacher complexity of the composition of functions, but these typically rely on some Lipschitzness properties, which do not hold for our function class $\mathcal{F}_c$ since we compose with an indicator function.


texts: Template Metaprogramming and Turing Completeness

texts:
I am trying to design a Turing Machine using C++ Template Metaprogramming. What steps must be taken to ensure that the code that I'm gonna write will actually build a Turing machine ? I have read that C++ templates are Turing complete but I don't actually know how to prove this thing.

How should I proceed? Turing completeness is really tough to understand and so simulating a Turing Machine would be tougher I guess. What do you guys suggest?


texts: Intuitively, why is the complementary slackness condition true?

texts:
What's an intuitive proof that shows that the conditions of complementary slackness are indeed true:

If $x^*_j > 0$ then the $j$-th constraint in the dual is binding.
If the $j$-th constraint in the dual is not binding, then $x^*_j = 0$

And similarly for the dual variables $y^*_i$ and constraints in the Primal. Where $x^*$ and $y^*$ are the optimal solutions to the Primal and Dual respectively.

What's an intuitive proof as to why this is the case? Staring at the equations makes sense algebraically, but I wish to understand it at a more visceral level.


texts: Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)?

texts:
The kernel of a parameterized problem $L$ is a reduction $(x,k) \mapsto (x',k')$ such that:

$(x,k) \in L \Leftrightarrow  (x',k') \in L$
$|x'| \leq f(k)$ for some function $f$
$k' \leq g(k)$ for some function $g$
transformation must be computed in polynomial time.

Can I say that the reduction is a Karp reduction $(x,k) \mapsto (x',k')$ such that

$(x,k) \in L \Leftrightarrow  (x',k') \in L$
$|x'| \leq f(k)$ for some function $f$
$k' \leq g(k)$ for some function $g$

I am confused because the language is a binary language.
Perhaps, this is a naive question, but I am not sure if I can call it Karp reduction. It seems that the Karp reduction is not used in parameterized complexity.


texts: Parameterized complexity of graph intersection number

texts:
What if anything is known about the parameterized complexity of computing the intersection number of a graph (the smallest number of cliques needed to cover all its edges)?

It has long been known to be NP-complete, and it's obviously FPT because it has a kernel: if you can cover a graph with $k$ cliques then there are at most $2^k$ different closed neighborhoods of vertices (two vertices have the same neighborhoods if they belong to the same set of cliques), and you might as well keep only one vertex per neighborhood. Is this observation in the literature somewhere? What kind of dependence on $k$ is known?


texts: Search for all nearest neighbors within a certain radius of a point in 3D?

texts:
I have about 80 million spatial points(3D) and I want to find all the nearest neighbors of a query point which lie under a sphere of a certain radius(can be given as input) with the query point as center.

I have read about some data structures that are used for such kind of search, such as Kd-trees, octrees or range trees. For my application, I only need to populate the data structure once and then search for multiple query points.

My question is:

Is there any better way or a better data structure than Kd-trees in this case?

With kd trees, I'll have to find the median of such a large dataset multiple times, which may take a lot of time to populate the tree.

I don't know much about any of these data structures so could you please refer some tutorials about whatever solution you may recommend. I know this question may seem repeated but from all the questions I found and read, no one was using such a large set of points.


texts: What notable automaton models have polynomially-decidable containment?

texts:
I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if you have machines $M_1, M_2$ you can test if $L(M_1) \subseteq L(M_2)$ efficiently.

The obvious ones that come to mind are DFAs and reversal-bounded counter machines where the number of counters is fixed (see this paper).

What other notable classes can be added to this list?

The more powerful the automata, the better. For example, DFA's aren't enough to solve my problem, and the counter machines can't do it with a fixed number of counters. (Naturally, if you get too powerful, then containment is either intractible, like for NFA's, or undecidable, for CFG's).


texts: Candidates for combinatorial one-way permutation

texts:
It is known that (worst-case) one-way permutations exist if and only if $P\ne UP \cap coUP$. Almost all candidates that I know are based on hard number theortic problems. I came across a combinatorial construction of one-way permutations based on quasigroup string transformations.

  What other combinatorial candidates for one-way permutations are known?


texts: Finding a median in a union of sets given as sorted arrays

texts:
You are given $k$ sorted arrays $A_1, A_2, ..., A_k$, each containing $n$ elements.

How fast can you compute the median of $A_1 \cup A_2 \cup ... \cup A_k$ ?

I have a solution running in $\Theta(k\log k\log n)$, but this seems rather inefficient if $k=\Omega(2^\frac{n}{\log n})$, as we can always ignore the order, think of it as a unsorted array of $nk$ elements, and solve it in $O(nk)$ time.

Assuming $k=\omega(1)$ (hence the fact the arrays are sorted give us some information), is there a sub-linear median finding algorithm (regardless of the ratio between $k$ and $n$)?
Assuming $k=\text{poly}( n)$, can we beat $O(k\log k\log n)$?
Can we prove a lower bound for the problem (maybe $\Omega(k\log n)$?)?


texts: Has ping based failure detector 'strong completeness' and 'weak accuracy'?

texts:
I was reading 'Unreliable Failure Detectors for Reliable Distributed Systems' (PDF) and I was wondering if ping (with increasing timeouts in case of failure) is in class S of failure detectors:

strong completeness
weak accuracy


texts: Solution/Hardness of the following (integer) budgeted problem?

texts:
I have no idea how to solve the following INTEGER problem or prove its hardness. Thanks for any help/comment/open discussion!

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

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

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

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

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

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


texts: Computing spanning trees with low crossing number using simplicial partitions

texts:
I'm reading a paper that uses the following result:

  Let $S$ be a set of $n$ points in the plane. Then a spanning tree for $S$ with crossing number $O(\sqrt{n})$ can be computed in $O(n^{1+\epsilon})$ time for any $\epsilon > 0$.

The paper refers the reader to Matoušek's paper [1] for this result. However, Matoušek does not discuss spanning trees of points in [1], rather several methods for computing simplicial partition trees.

So I've been trying to track down where the result comes from. I finally found, in [2], the following statement:

  So-called simplicial partitions ([Mat91b], see Section 5) can be used to obtain a spanning tree with crossing number $O(\sqrt{n})$ in time $O(n^{1+\epsilon})$ for any $\epsilon > 0$ (where the constant in the crossing numbers depends on $\epsilon$), [Mat91a].

The reference [Mat91b] in the quote is my reference [1], and the reference [Mat91a] is a private communication between Wezl and Matoušek. It seems that this sentence from [2] is most likely why [1] is referenced in the paper I'm currently reading. I think this is a slight mistake, since [Mat91b] appears to be included as a reference for simplicial partitions, and [Mat91a] (the private communication) is the reference for the entire section and hence the claim. I must admit the first time I read this sentence I made the same mistake, but after searching in vain for the result in [1], have come to the conclusion above.

So my question is this: has the proof of this result appeared in the literature? Perhaps it is obvious (it is not yet obvious to me, but I am still learning about these algorithms). If it is not obvious, I am hoping someone can either provide me with a reference to where it has appeared, or a (rough?) explanation of how a simplicial partition of a point set can be used to construct a spanning tree of the point set with stabbing number $O(\sqrt{n})$ in $O(n^{1 + \epsilon})$ time (or any other $O(n^{1+\epsilon})$ time method, really)?

Thanks.

References

[1] Matoušek, J. Efficient Partition Trees. Discrete Comput. Geom., 8:315-334, 1992.

[2] Wezl, E. On spanning trees with low crossing numbers. Data Structures and Efficient Algorithms, LNCS 594:233-249, 1992.


texts:
Given a graph $G=(V,E)$, what I call an improper $3$-coloring of $G$ is simply a function $c:V \to \{1,2,3\}$. I say that $c$ is $1$-$2$-avoiding when
there do not exist two adjacent nodes $u,v$ with $c(u)=1$ and $c(v)=2$. I am interested in the problem that takes as input a graph and counts the number of $1$-$2$-avoiding improper $3$-colorings of $G$. Or equivalently, this is the number of pairs of disjoint node subsets $(S,S')$ that are not adjacent (in the sense that $E \cap (S\times S') = \emptyset$).

Question: has this problem already been studied? It is obviously in the complexity class #P, but is it also #P-hard?


texts: Are there any polynomial cases of Balanced Minimum Evolution?

texts:
The BME problem has an interest in computational biology, for the reconstruction of phylogenetic trees from a distance matrix. Let me provide some context before defining the problem.

Suppose that we are given a set of species $S$ and a symmetric function $\delta : S \times S \rightarrow \mathbb{R}^+$ such that $\delta(i,j)$ is an estimate of the evolutionary distance between species $i$ and $j$. The 'tree fitting' problem consists of finding a weighted tree $\hat{T}$ leaf-labeled by $S$, such that the induced metric $d_{\hat{T}}$ is a good estimation of $\delta$. Here $d_{\hat{T}}(i,j)$ is defined as the length of the unique path of $\hat{T}$ joining $i$ and $j$. If $T$ is unweighted, we denote by $p_T(i,j)$ the number of edges of this path.

Now, given an unweighted tree $T$ and a matrix $\delta$, we may then define the following quantity:

  $L_T(\delta) = \sum_{\{i,j\} \subseteq X} 2^{1-p_T(i,j)} \delta(i,j)$

It is known that $L_T(\delta)$ computes the total length $l(\hat{T})$ of a weighted tree $\hat{T}$ with topology $T$ that best fits $\delta$ (in some precise sense that I won't explain). In particular, when $\delta$ is obtained from some weighted tree $\hat{U}$, we have the property that $L_U(\delta) = l(\hat{U})$ and that $L_T(\delta) \geq l(\hat{U})$ for every $T \neq U$. That is to say, in that case the 'right tree' can be obtained by a parsimony principle.

The BME problem consists, given the function $\delta$, to recover an unweighted tree $T$ minimizing $L_T(\delta)$. By the above remark, the problem is easy when $\delta$ is a tree metric, whereas it is $\sf{NP}$-hard for arbitrary metrics (and probably even for $\ell_p$ metrics of small dimension, although I don't have a formal proof of this fact). Mainly for theoretical reasons, I am looking for other classes of metrics for which the problem is polynomial. An analogy with the TSP problem suggests that circular metrics are possible candidates, as they're known to be among the few tractable cases for TSP.

Thus, to the experts in the field I'd like to ask if (1) they have literature to recommend about circular metrics, (2) they have suggestions of other candidate metrics that are known to be tractable for TSP.


texts: A curious asymmetry in good characterizations

texts:
There are quite a few theorems, mostly in graph theory and combinatorial optimization, that are often referred to as good characterizations. They typically put a property in $NP\cap co-NP$, by showing that a property either holds, or else there is some well identified obstacle that prevents it from holding. Often they are presented as min-max theorems, see the earlier question Optimization problems with good characterization, but no polynomial-time algorithm

Here are two classical examples of good characterizations:

A bipartite graph either has a matching of size $k$, or else there are less than $k$ vertices that cover all edges. The existence of such a cover is a trivial obstacle that excludes the matching. If this obstacle is not there, the matching must exist, this is the nontrivial part, known as Konig's Theorem.
Either there is an $s-t$ flow of value $F$ in a flow graph, or else there is an $s-t$ cut with capacity less than $F$. Again, the existence of such a cut is a trivial obstacle, since then the flow cannot get through. The nontrivial part is that the absence of the obstacle already guarantees the existence of the flow of value $F$, which is equivalent to the Max Flow Min Cut Theorem.

What I find a curious feature in these (and many other) results is that they show a well visible  asymmetry in the proof hardness between the two directions of the equivalence. Usually, it is easy, or even trivial, to prove that the obstacle excludes the considered property. On the other hand, it is much harder to prove that the easy/trivial obstacle is the only obstacle, in the sense that once it is not there, the property must hold.

I am not aware of  a good explanation why this type of asymmetry is so common. It does not appear a priori necessary. Note: do not get misled by the fact that the above examples are both special cases of linear programming duality. There are other examples that have nothing to do with linear programming.

  Question: Do you know any good characterization that does not fall in this category? (Admittedly, it is vaguely defined, but perhaps the idea got through.) In other words, I am looking for a theorem that puts a property in $NP\cap co-NP$, by capturing all possible obstacles of the property, but they are not all easy/trivial obstacles.


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

  Questions

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


texts: Triangular Mesh Reordering - Huddling Triangles

texts:
I am given a 3D model represented by its outside surface as a triangular mesh (hollow inside). The model is mostly 2-manifold, so that each triangle edge is shared by exactly 2 triangles. This, naturally, means that every triangle has exactly 3 neighbors (except at non-manifold bare edges, but we can ignore this case for now).
The mesh is represented as an array of triangles. Assume that I know the indices of each triangle's neighbors.

Is there an algorithm for reordering the triangles such that most triangles are very close to all 3 their neighbors in this 1D ordering?

I suspect this is an NP complete problem, but I wonder if there are approximation algorithms.

Here's what I found but all seem unsatisfactory:

Space-filling Hilbert-like curves (e.g. for triangular grids).
Even if I could generate such a curve for arbitrary topology (non-regular) meshes, these do not preserve or minimize overall locality:

  Both the Hilbert curve and its discrete approximations are useful because they give a mapping between 1D and 2D space that fairly well preserves locality. If (x,y) are the coordinates of a point within the unit square, and d is the distance along the curve when it reaches that point, then points that have nearby d values will also have nearby (x,y) values. The converse can't always be true. There will sometimes be points where the (x,y) coordinates are close but their d values are far apart.

What is guaranteed, is that close points on the 1D curve will tend to be close in 2D space, but the converse is not true (i.e. close points in 2D space will not necessarily be close on the 1D curve) and that is what I want .

Adjacency Matrix Bandwidth Reduction
Another approach I considered was creating the adjacency matrix for the triangle neighborhood graph where each node in the graph is a triangle and there is an edge between each pair of neighboring triangles.
The adjacency matrix is symmetric very sparse since each node has (at most) 3 neighbors.

I'd like an algorithm to reorder the columns and rows of the matrix such that most of the sparse entries are as close to the diagonal as possible. This is called matrix bandwidth reduction, and is an NP-complete problem, but it has several well known algorithms such as the reverse Cuthill–McKee algorithm (RCM). This algorithm and its variants are essentially variants of the breadth-first-search algorithm.

However, IIUC, in my case the graph is mostly locally planar, so the algorithm will essentially generate a spiral of interleaved triangles from and around the start node. This spiral will cause each triangle to get farther and farther away from at least 1 but sometimes all 3 of its immediate neighbors by a distance that is proportional to the circumference of the spiral at that point.

I prefer fewer long non-local hops to many shorter non-local hops.

Am I missing anything? Is there another approach I could take?


texts: Is there an efficient way to reduce a set of graphs under isomorphism?

texts:
Suppose we have a set $S$ of (fixed-size) graphs, many of which are isomorphic to each other. How do you find a minimum-size set $M$ of graphs such that every $g\in S$ is isomorphic to some graph in $M$? It would be nice to have a solution that's more efficient than running graph isomorphism $O(|S|^2)$ times.

If there isn't an efficient way, is there a way to get close? (i.e. find an approximation $M^*$ such that $|M^*| \sim |M|$ asymptotically, or something like that.)


texts:
Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in $\#P$ and remain hard for grid graphs?
Since there seem to be multiple definitions of grid graphs in the literature, let us specify the following families:

Grid: a finite node-induced subgraph of the infinite two-dimensional integer grid.
Solid grid: a grid graph all of whose bounded faces have area one, i.e., a grid graph with no "holes"; see [1].
Rectangular grid: the Cartesian product of $P_n \square P_m$. Special case is the square grid with $n=m$.
Periodic rectangular grid: the 4-regular graph that results from the Cartesian product $C_n \square C_m$. Special case is the periodic square grid with $n=m$.

For problems defined on families 3 and 4, suppose that the input is the numbers $n$ and $m$ in unary. My question concerns all 4 families above, but I'd be particularly interested in any $\#P$-hardness proofs for the more restricted families, especially the periodic square grid.
Comments:
a) Welsh [2] states that problems defined on restricted families such as 3 and 4 can be difficult to treat from a complexity standpoint, because "there are too few inputs", which I guess means only a single instance for each $n$ and $m$. Are there any by now common methods / reductions to deduce complexity for such problems with "too few inputs"?
b) Ref [3] shows that counting self-avoiding walks in family 1 is #P-complete. Are there any known results for the more restricted families?
c) Ref [1] shows that it is easy to find Hamiltonian cycles in family 2. Does this imply anything about the hardness of counting Hamiltonian cycles?
References
[1] W. Lenhart and C. Umans,  "Hamiltonian Cycles in Solid Grid Graphs," Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS ’97). IEEE Computer Society, USA, pp. 496.
[2] Welsh, D. (1993). Complexity: Knots, Colourings and Countings (London Mathematical Society Lecture Note Series), Cambridge University Press, pp. 17.
[3] Maciej Liśkiewicz, Mitsunori Ogihara, Seinosuke Toda, The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes, Theoretical Computer Science, Volume 304, Issues 1–3, 2003, Pages 129-156


texts: Completeness of the quotient of the power set lattice of a partial order induced by the Hoare pre-order

texts:
Let $(P,\le)$ be a partially ordered set and $\preceq$ the Hoare pre-order on its subsets, i.e. for $X,Y\subseteq P$, $X\preceq Y$ iff $\forall x\in X:\exists y\in Y:x\le y$.

Let $\sim$ be the equivalence on the power set $2^P$ generated by $\preceq$, i.e. $X\sim Y$ iff $X\preceq Y$ and $Y\preceq X$.  Let $M=2^P/\mathord\sim$ be the quotient, then $\preceq$ passes to a partial order, also denoted $\preceq$, on $M$.

Is $(M,\preceq)$ a complete lattice?


texts:
I'm trying to put together a general picture of the expressiveness of some logics: First-Order Logics, Fixed-Point Logics, (Finite Variable) Infinitary Logics and the respected versions with Counting. (Source)

$\mathcal{L}^k_{\infty\omega}$ is infinitary logic with $k$ distinct variables and

$$\mathcal{L}^\omega_{\infty\omega} := \bigcup_{k \in \omega}  \mathcal{L}^k_{\infty\omega}$$

is finite variable infinitary logic. (Analog for Counting)

This is in the context of Finite Model Theory so in general all structures are finite.

  We say  $\varphi$ and $\varphi'$ are equivalent if for every structure
  $\mathcal A$

  $$ \mathcal A \models_\mathcal L \varphi \Leftrightarrow \mathcal A
> \models_{\mathcal {L'}}  \varphi'.$$

  If for every $\mathcal L$-sentence there is a equivalent
  $\mathcal L'$-sentence we write

  $$ \mathcal L \leqq \mathcal L'.$$

Most of the relations are relatively straight-forward. $\mathcal{L}^\omega_{\infty\omega}$ cannot express that a graph has an even number of nodes. Hence, both $\mathcal{L}_{\infty\omega}$ and $\mathcal{C}^\omega_{\infty\omega}$ are
strictly stronger because they can express any predicate over finite structures.

A though one is $\mathcal{L}_{\infty\omega} \equiv \mathcal{C}_{\infty\omega}$. I think this is correct since $\mathcal{L}_{\infty\omega}$ can express every predicate, thus adding counting should not make it more powerful. This it far from a proof but at most an intuition. Any ideas?

The other one I don't know is $\mathcal{C}^\omega_{\infty\omega} \lneqq \mathcal{C}_{\infty\omega}$. Again my intuition is that it is correct: How can we express any predicate with finite variables even with Counting? Any ideas on that? Maybe an example which is not expressible in
$\mathcal{C}^\omega_{\infty\omega}$?


texts: Formalizing Homotopy Type theory in Idris

texts:
Looking at the homotopy type theory blog one can easily find a lot of library formalizing most of Homotopy Type Theory in Agda and Coq.

Is there anyone aware if there is any similar attempt to formalize HoTT in Idris?


texts: Rearranging angles of a convex polyline to make it closed

texts:
Let {$\alpha_1, \alpha_2, ... ,\alpha_n$} be a string of n positive reals summing up to 2$\pi$. We inductively construct the following 2D polyline, denoting with $R[\alpha]$ the clockwise rotation by an angle $\alpha$

$$p_0=(0,0)$$
$$p_1=p_0+Rot[\alpha_1](1,0)$$
$$p_2=p_1+Rot[\alpha_1+\alpha_2](1,0)$$
$$...$$
$$p_j=p_{j-1}+Rot[\alpha_1+\alpha_2+...+\alpha_j](1,0)$$
$$...$$

We are constructing each point as the previous point plus the vector (1,0) rotated by the sum of all previous angles. All the edges of our polyline have the same length.

After n steps this curve may close up (it's unlikely if angles are random). Is there a smart strategy for finding whether there is a permutation of the angles that makes the curve close up? More generally, is there a good strategy to find the minimum distance of the last point from {0,0} over the set of all permutations? If not, what about approximations?

This problem sounds very natural to me but I was not able to find any references. I am far from being an expert in complexity theory and the way I came to formulate this problem is as a discretization of the smooth setting where arcs of a smooth convex curve are rearranged to make it closed.


texts:
In general, the query-tape for an oracle counts towards the space-complexity of a TM. However, it seems plausible to allow a write-only oracle-tape (such as is used in L-space reductions).

Is such a construction useful? Does it yield any particularly absurd results?


texts:
The Eulerian Tour problem is of course a well-studied classical problem in graph theory (Wikipedia article). This question concerns non-Eulerian graphs; i.e., graphs that contain one or more odd-degree vertices. In a nutshell, I wonder what is the best "Eulerian-like" way of traversing non-Eulerian graphs.

Given an undirected connected graph, let an Eulerian "semi-tour" be defined as a "cycle" that passes each edge at least once and can visit any vertex or edge multiple times. Consider the following costs for a given semi-tour:

Total cost: The total number of edges visited by the semi-tour, counting multiplicities.
Width cost: The number of times the most-visited edge is visited.

I'm interested in optimization problems that aim to find a semi-tour that minimizes the total cost or the width cost on a given graph. Of course, if a graph is Eulerian, an Eulerian tour would be optimal, for which the total cost is the number of edges and the width cost is zero. For graphs containing odd degree vertices, the optimal cost in both senses must be larger.

I suspect these optimization problems (if not trivial) must have been well studied in the literature. What are the relevant references, if any, and what is known about these problems (both algorithmically and combinatorially)?


texts: Additive combinatorics applications in algorithm design

texts:
I'm reading surveys by Trevisan and Lovett on applications of additive combinatoric in TCS. The majority of these applications fall under computational complexity, e.g., lower bounds. I wonder if additive combinatorics has found applications in algorithm design too.

The motivation for my question is the following: while the connection between additive combinatorics and complexity seems somewhat natural, I'm curious to see how algebraic structure uncovered by additive combinatorics might be exploited in designing efficient algorithms, if any. Pointers to literature would be appreciated.


texts: Finding the set of paths of smallest cumulated length that cover a given set of patterns

texts:
First of all, sorry for this long and maybe not very informative title...

Context:

Let $G=(V,E)$ be a directed graph, let $v_0 \in V$ be the initial node of paths that I will consider in the graph.

Let $\Sigma$ an alphabet and let $T$ (for target) a set of words built from $\Sigma$ (e.g. $T \subset \Sigma^*$). Nodes of $G$ are tagged with letters from $\Sigma$. Each node is tagged with only one letter, and most nodes are tagged with the empty letter.

The general question is: how to find (algorithm, complexity) the set of paths starting at $v_0$ that contains all words from $T$ and whose cumulated length is minimum.

This problem is not that hard to solve (I am not speaking from the complexity point of view): this can be solved using classical optimization methods. For instance we take all paths of a sufficient length that cover elements of $T$, then we choose a subset of these paths that cover all elements of $T$ and whose length is minimum. Before that we off course checked (reachability analysis) if all elements of $T$ can be found in the graph.

My problem:

Imagine now that we don't have access to the graph explicitly (not enough memory for instance).

Instead we are given a function $f : V \rightarrow subgraph_k(G) $ that gives us, for a node $v$, the subgraph of diameter $2k$ centered around $v$ ($k \in \mathbb{N}$ fixed a priori). Moreover we have only a very limited memory (let's say we cannot store more than a few paths of reasonable length).

With this very restricted access to the graph, how to solve the problem? All solutions that I can imagine are based on sampling and are clearly not effective. Does any of you have an idea?


texts: Does MCMC belong to the statistical query model?

texts:
It is known that a wide range of algorithms fall into the statistical query (SQ) learning model by Michael Kearns. Examples include k-means, logistic regression, naive Bayes (NB), SVM, ICA, PCA, gaussian discriminant analysis, EM, and backpropagation for neural networks. (See, e.g., http://papers.nips.cc/paper/3150-map-reduce-for-machine-learning-on-multicore.pdf for proofs.)

According to Feldman et al. (http://arxiv.org/pdf/1201.1214v5.pdf), it seems that MCMC also belongs to the SQ model. However, I didn't find any concrete proofs for this simple fact in existing literature. So, does MCMC directly falls into the SQ model? Or it requires modifications to fit in?


texts:
One classical extension of the max-flow problem is the "max-flow over time" problem: you are given a digraph, two nodes of which are distinguished as the source and the sink, where each arc has two parameters, a capacity-per-unit-time and a delay. You are also given a time horizon $T$. The goal is to compute a flow over time which gets the maximum amount of material from the source to the sink by time $T$. A flow of maximum value can be computed in polynomial time by a clever classical reduction to min-cost max-flow.

I am interested in an extension to this model where edges have a third "life-span" parameter. If an arc has life-span $\ell$, and $t$ is the earliest time at which positive flow is sent through the arc, then we destroy the arc at time $t+\ell$. You can think of this as like the platforms in Super Mario Brothers which fall away/are destroyed shortly after you step on them, or you can think of them as batteries needed to power the edges, which cannot be turned off after they are turned on. (Edit:) The decision problem is, when also given a flow value lower bound $B$, whether one can schedule a flow meeting both the time horizon upper bound and flow value lower bound.

So far I can see that this problem is strongly NP-hard (via 3-partition). But, I do not actually know if it is in NP: is there any guarantee of a way to express a solution compactly? In the classical version, some special type of optimal flow is used to circumvent this problem.

Note: the model above is a little underspecified, since you may allow or disallow the stockpiling of flow at nodes, and you may have a discrete time model or a continuous one. Resolving the question for any of these models would be excellent.


texts: what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?

texts:
Both problems are well-known NP-hard problems with great similarities. In fact, I do not see the real difference between these two problems. It seems relatively easy to model TSR in the form of VRP and likewise inversely. So what is the essential point to make VRP a different problem from TSP?

p.s. I cannot find appropriate tags for this question.  I think important problems such as TSP should be tags themselves.


texts: EXPTIME-complete propositional satisfiability problem

texts:
SAT is NP-complete, QBF is PSPACE-complete, DQBF is NEXPTIME-complete. Is there any extension of QBF or restriction of DQBF that is EXPTIME-complete?

Added later: a definition of DQBF can be found here: https://www.react.uni-saarland.de/publications/sat14.pdf


texts: Trampoline that automatically balances heap and stack

texts:
While working through Fogus' Functional Javascript, I came across the trampoline function, which can be used to make safe recursive functions that don't blow up the stack. In Fogus' words, "Of course there is no free lunch, even when using trampolines. While I’ve managed to avoid exploding the call stack, I’ve just transferred the problem to the heap."

On top of moving this problem to the heap, the trampolined version of the function is slower.

Is it possible to make a "smart" trampoline function that takes two forms of a function, a trampolined version and a non-trampolined version, and chooses (or predicts) the most efficient strategy?*

Ref: https://github.com/funjs/book-source/blob/master/chapter06.js#L195

*(or better yet combines both strategies (is this possible?) that uses fewer trampoline "bounces", where each bounce is almost the maximum number of computations that can be performed recursively using the stack strategy)


texts: multi-agent pickup and delivery algorithm and conflict resolution

texts:
I am looking for a pathfinding algorithm handling the following issues:

multiple agents

the computed paths for agents may not lead to collisions or deadlocks in space-time
a stream of activities

new pickup and delivery points for agents without assigned activities may come in at any point (usually when an agent finished their activity)
a very low number of  branches in the underlying topology (i.e. nodes with more than two neighbors)

I'll detail below why I am listing this.
inertia of agents

some nodes are more expensive depending on from which node you came (e.g. the node you came from or one where you have to change direction)
size of agents

some nodes in the vicinity of another agent may not be occupied, if they are too close

I ordered them by importance. The last two are merely nice to have, but not vital.

The paper "Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks." by Hang Ma, Jiaoyang Li, T. K. Satish Kumar, Sven Koenig gets really close to what I am looking for. It presents an algorithm that resolves the first two issues.

However, the algorithm struggles with, what the authors named, "not well-formed MAPD instances". In my case the following is not satisfied "for any two endpoints, there exists a path between them that traverses no other endpoints." (endpoints being starting positions of agents, pickup positions and delivery positions). Hence, why I am listing the third issue. In something similar to a PAC-MAN level there are very few possibilities to dodge other agents (compared to an open map where you can just sidestep the other agent), making conflict avoidance much harder.

The fourth issue can be resolved by modifying the underlying A*-algorithm, while the fifth issue can be baked into the conflict detection step.

Is there some literature I missed tackling this kind of issue? Or maybe how I could modify above authors' algorithm to another form of conflict resolution which works despite the problem being "not well-formed"?


texts: Applications of Game theory in computer science?

texts: As a computer science student, I have been introduced to game theory, but not seen much detail on the subject. I have searched on Google and looked at some books about game theory and they provided confirmation of its usage in computer science. I have started a formal study of game theory from the economist's perspective. Now I want to know the applications of game theory in computer science. What are some recent major achievements of computer scientists in fields like Artificial Intelligence and Complexity Theory which utilize elements of game theory? Is there a way to approach game theory that is more rooted in computer science than economics?


texts: Which paper to cite when referring to reservoir sampling *with replacement*?

texts:
As far as I can tell, the term "reservoir sampling" is commonly used to refer to sampling without replacement and references [1], [2], and [3] are cited while mentioning it. When referring to reservoir sampling with replacement, which papers should be cited? A recent reference that I found is titled "Reservoir-based Random Sampling with Replacement from Data Stream" available at http://epubs.siam.org/doi/pdf/10.1137/1.9781611972740.53.

[1] Donald E. Knuth: The Art of Computer Programming, Volume II: Seminumerical Algorithms, 2nd Edition. Addison-Wesley 1981, ISBN 0-201-03822-6

[2] McLeod, A.I., Bellhouse, D.R.: A convenient algorithm for drawing a simple random sample. Appl, Stat., pp. 182-184 (1983).

[3] Jeffrey Scott Vitter: Random Sampling with a Reservoir. ACM Trans. Math. Softw. 11(1): 37-57 (1985)


texts: efficient diff algorithm for trees and Levenshtein distance

texts:
I've recently read this summary of the issues involved with doing diff between trees and it got me interested in learning what is the state of the art for this problem.

Also, suppose that between your allowed edit operations are the traditional add/delete node, edit content you add the extended operations of copy/move subtree, does this makes the problem (of finding an optimal diff) easier or harder?


texts: Effect of constraints Density on the hardness of Betweness problem

texts:
Betweeness problem is well known NP-complete permutation problem. Given a family $M$ of triples $(a_i, a_j, a_k)$, the problem is to decide whether a permutation $\Phi$ of elements $a_1, a_2, ..., a_n$ exists which satisfies all betweeness constraints.  For each triple $(a,b,c)$ in $M$, it holds that either $\Phi(a) \lt \Phi(b) \lt \Phi(c)$ or $\Phi(c) \lt \Phi(b) \lt \Phi(a)$.

Motivated partialy by this CS Theory post, I am interested in the relation between density of constraints and hardness of betweeness problem. I am looking for for a classification of problem's hardness based on the number of triples $|M|$ for these cases:

1-$|M|=O(\log n)$, 2-$|M|=o(n)$ , 3-$|M|=\Theta(n)$,  4-$|M|=\Omega(n^2)$, 5-$|M|=\Omega(n^3)$.

Please classify it to PTIME solvable, Quasi-polynomial solvable, Subexponential time solvable, and NP-complete.


texts: What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper

texts:
I have been going through Kempe-Kitaev-Regev's paper The Complexity of the Local Hamiltonian Problem. In the first paragraph of page 3, the authors point out that:

  To the best of our knowledge, this is the ﬁrst reduction inside QMA (i.e., not from the circuit problem).

What does 'not from the circuit problem' mean and what does the circuit problem refer to?


texts: $NP$-complete problems on cubic Hamiltonian graphs

texts:
The class of cubic Hamiltonian graphs is well studied class. I came across the fact that independent set problem is $NP$-complete when restricting input to cubic Hamiltonian graphs. I am interested in other hard problems on this class.

  Which $NP$-complete problems on cubic graphs remain hard when restricted to cubic Hamiltonian graphs?

A survey of such hard problems would be very nice.

Motivation

Given two NP-complete problems on a restricted graph class, I would like to understand the intractability boarderline when we further restrict input instances.

UPDATE: I am not interested in decision version of optimization problem such as clique problem (or maximum independent set). However, Dominating Clique problem is the kind of $NP$-complete problem that would interest me if it was hard on cubic Hamiltonian graphs. Dominating clique in graph $G(V,E)$ is a dominating set of $V$ and a clique of $G$.

Dominating clique problem is interesting for me because the problem definition does not contain a parameter ( unlike clique or MIS for which we must specify the size of the required solution).


texts: Complexity of multi-objective optimization problems

texts:
How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)?

It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the MOOP is also NP-Hard.
However, it's not clear to me how to define the worst-case complexity of the MOOP when all of their objective functions can be solved in polynomial-time, separately.

There is some different technique for proving that the MOOP is NP-Hard (or its decision version is NP-Complete), or I need to use the same techniques for demonstrating the worst-case complexity of single-objective optimization problems (show that it is in NP, then reduce a NP-Complete problem to my own, ...).

It's hard to find a good discussion regarding this theme on the Internet. Besides, I was unnable to find a good paper or book discussing this issue.


texts: When is the duality gap of semidefinite programming (SDP) zero?

texts:
I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold?

For example, when one goes back and forth between the Lasserre and the SOS SDP, in principle one has a duality gap. However, somehow there seems to be some "trivial" reason why this gap isn't there.

Slater's condition seems to be sufficient but not necessary and it applies to all convex programs. I am hoping that for SDPs in particular something stronger might be true. I would be equally happy to see any explicit example of using Slater's condition to prove the vanishing of the duality gap.


texts: References for the mathematical safe problem ?

texts:
An input to Mathematical Safe problem is represented by the 4-tuple $(L,K,S,X_0)$, where

$L=[n]$ is the set of locks,
$K=(k_1,\dots,k_l,\dots,k_n)$, where $k_l$ is the number of the states of the lock $l$ and each state set of lock $l$ is a set of congruence classes modulo $k_l$ ($\mathbb{Z}_{k_l}$),
$S=(S_1,\dots,S_l,\dots,S_n),S_l\subseteq L,l\in S_l,\forall l$,
an initial tuple of lock states $X_0=(x_1^0,x_2^0,\dots,x_n^0), x_l^0\in \mathbb{Z}_{k_l},\forall l$.

Let $x_l^j$ be the state of lock $l$ after turn $j$. Initially we are given a tuple of states $X_0$. After a single clockwise turn $j$ of the key in a lock $l$ all the locks $l'\in S_l$ pass from a state $x_{l'}^j$ to a state $(x_{l'}^j+1)\bmod k_{l'}$. The solution is the sequence of turns which opens the safe, i.e. brings it to the set of lock states $X=\{0,0,\dots,0\}$. The goal is to find a solution with minimum number of turns.

I know that this problem has been studied in some papers after 2002 year by one author, Donets G.A. But it seems to me that it was studied before. Am I right in this respect and if so what references are there on this problem?


texts: Flynn's taxonomy, and "task parallelism and data parallelism"

texts:
Quoted from http://en.wikipedia.org/wiki/Task_parallelism:

  Task parallelism (also known as function parallelism and control
  parallelism) is a form of parallelization of computer code across
  multiple processors in parallel computing environments. Task
  parallelism focuses on distributing execution processes (threads)
  across different parallel computing nodes. It contrasts to data
  parallelism as another form of parallelism.

I was wondering if there is some correspondence between  Flynn's
taxonomy (SISD, SIMD, MISD and MIMD), and "task parallelism and data parallelism"? For example,

does task parallelism mean multiple-instruction in Flynn's taxonomy,
so one can say "task parallelism = MISD+MIMD"?

does data parallelism mean multiple-data in Flynn's taxonomy, so one
can say "data parallelism = SIMD+MIMD"?
If there is no exact correspondence between the two classification
methods, how shall one understand their differences and relations?

Thanks and regards!


texts: Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?

texts:
Actually I found that the set of context-sensitive Languages,
$\mathbf{CSL}$ ($\mathbf{=NSPACE}(O(n))$ $= \mathbf{LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular languages) or $\mathbf{CFL}$ (context-free languages).

And also the open problem $\mathbf{DSPACE}(O(n)) \stackrel?= \mathbf{NSPACE}(O(n))$ is not so famous as the "analogous" problem: $\mathbf{P} \stackrel?= \mathbf{NP}$.

So I have two questions:

Is there a language in $\mathbf{CSL}$ which couldn't be proved to be in $\mathbf{DSPACE}(O(n))$?
Moreover: Is there a language $L$ in $\mathbf{CSL}$ which is "complete" in the following sense: if we can prove that $L$ is in $\mathbf{DSPACE}(O(n))$ we get that $\mathbf{DSPACE}(O(n)) = \mathbf{CSL}$?

Notice:
I have asked these questions in cs.stackexchange and got some interesting Answers but not a concrete (proven) example for such a language:
https://cs.stackexchange.com/questions/79528/a-language-in-nspaceon-and-very-likely-not-in-dspaceon


texts: Level $k$ bounds in Analysis of Boolean functions

texts:
In Ryan O'Donnell's book Analysis of Boolean functions, following Corollary 9.25 the following appears:

If $f\colon \{-1,1\}^n \to \{0,1\}$, and we have $\mathbb{E}[f] = \alpha$, then for any integer $k$ at most $2\ln \frac{1}{\alpha}$, we have $W^{\leq k}[f] \leq \rho^{-k}\alpha^{2(1-\rho)}$. He then deduces the following corollary:

  If $\epsilon > 0$ and $k_\epsilon = 2(1-\epsilon)\ln \frac{1}{\alpha}$, then
  $W^{\leq k_\epsilon}[f] \leq \alpha^{\epsilon^2}$

My question is isn't this bound meaningless?

Indeed, we have

$W^{\leq k_\epsilon}[f] \leq \lVert f\rVert_2^2 = \alpha \ll \alpha^{\epsilon^2}$


texts: Approximating the diameter of a convex set defined by semidefinite constraints

texts:
A convex subset $C$ of $\mathbb{R}^{n^2}$ is given as the set of positive semidefinite $n\times n$ matrices whose coefficients fulfill some affine equations.

Now, if you want to minimize a linear function on $C$, you're dealing with semidefinite programming, and that's efficiently solvable. But what if you want to estimate the diameter of $C$? I can very well imagine that this is a difficult task, but can find no helpful reference (and I'm more willing to blame that on me not finding the right keywords than on the research not having been already done). I would consider estimating the diameter only up to some factor, large but at most slowly increasing in the dimension; so I'm interested in general in the hardness of approximating the diameter.


texts:
On interval graphs, minimal vertex separators are well understood: they are cliques, there are no more than $n$ ones.  However, when we turn to the minimal edge cut, my search found no even one single paper, which surprised me.

To make it more precise, the edge cuts are defined as follows.  In an interval graph $G=(V,E)$, a pair of vertices $u$ and $v$ is called a dominating pair if there is a path $P$ between them such that all vertices of $V$ are adjacent to some vertex in $P$.  A partition $(X,Y)$ of $V$ is called an edge cut if $u\in X$ and $v\in Y$.

A slight different way to define edge cuts is through the clique path decomposition.  It is known that a graph is an interval graph if and only if there is a linear ordering of its $c$ maximal cliques in a way that each vertex appears in a consecutive subset of them.  Then an edge cut is defined as a partition $(X,Y)$ where $K_1\setminus K_2\in X$ and $K_c\setminus K_{c-1}\in Y$.

These two definitions are not exactly the same, and may have different minimum cut sizes.  But I believe they are related.  Also note that it's uninteresting to study the number of minimal edge cuts, as a clique is an interval graph where each partition decides a different minimal edge cut.

EDIT.  My question: what's the properties of the minimum edge cuts?


texts: Exact formula for the number of spanning trees of a rectangle

texts:
This blog talks about generating "twisty little mazes" using a computer an enumerating them.  The enumeration can be done using Wilson's algorithm to get the UST, but I don't remember the formula for how many there.

http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike

In principle the Matrix Tree Theorem states the number of spanning trees of a graph is equal to the determinant of the Laplacian matrix of the graph.  Let $G= (E,V)$ be the graph and $A$ be the adjacency matrix, $D$ be the degree matrix, then $\Delta = D - A$ with eigenvalues $\lambda$, then:

$$ k(G) = \frac{1}{n} \prod_{k=1}^{n-1} \lambda_k $$

In the case of an $m \times n$ rectangle both $A$ and the eigenvalues should take a particularly simple form, which I can't find.

What is the exact formula (and asymptotics) for the # of spanning trees of an $m \times n$ rectangle?

Here is a pretty example of Wilson's algorithm in action.


texts: Worst-Case and Average-Case running-time equal with universal p-distribution with kolmogorov-complexity any applications of this theory?

texts:
at the moment I'm reading "Gems of Theoretical Computer Science" from Schöning and Pruim.
In Chapter 8 the book defines a "universal probability distribution" in a way that the Average-Case running-time of every algorithm A under this distribution is equal (up to a constant factor) to it's worst-case running time.

I was wondering why this construction is even helpful. Or in other words I want to know if someone knows a case where this theorem might come in handy.

I know we don't do maths because we want to use it, but because it is beautiful. But I think to talk about this theory as a "gem" of Theoretical Computer Science there should be some serious outcomes of the theory.

In my opinion the best application for this theory would be if there are certain algorithms for which it is very easy to determine the Average-Case
running-time but very hard to find out the worst-case running time.
But I don't know such a case.
I even think that one has to know the worst-case running-time in order to calculate the average-case (that's because the average-running-time is nothing but the expected value of the running time).
For example it is easy to show that Quicksort runs in wc O(n^2) but it is harder to show that it runs in ac O(nlog(n)). So it seems pointless to get the average running-time under a certain distribution to be O(n^2). We already knew that.

It would be really nice if someone knew some applications of this theory!


texts: Max Sum Product Multi-objective Shortest path problem

texts:
Is anything known about the following problem:

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

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

Is this problem in PTIME or NP-complete?


texts: When does Basis Pursuit and LASSO give the same answer?

texts:
There are 3 different but related optimization questions that one can frame given a $y \in \mathbb{R}^n$ and $A \in \mathbb{R}^{n  \times m}$ and constants $\epsilon, \lambda, k > 0$,

$$\text{argmin}_{x \in \mathbb{R}^m}  \Vert x \Vert_1 s.t \Vert A x - y\Vert \leq \epsilon $$
$$\text{argmin}_{x \in \mathbb{R}^m}  \Vert Ax - y \Vert^2 + \lambda \Vert x \Vert_1$$
$$\text{argmin}_{x \in \mathbb{R}^m}  \Vert A x - y\Vert^2 s.t \Vert x \Vert_1 \leq k $$

The second and the third of the above are Lagrangian duals of each other and what are called "LASSO". The first is the ``Basis Pursuit" form of compressed sensing.

Can someone kindly refer me to references/theorems where its proven what are the "iff" conditions for any pair of them to give the same answer and/or "iff" conditions if known for all of them to coincide?

As is usual feel free to assume that $y = Ax^* + \xi$ for some sparse $x^* \in \mathbb{R}^m$ and maybe some norm of $\xi$ is being assumed to be small.  Often its in these noisily realizable cases that answers like the above are easier to give.

And in this noisy realizable setting as above I can find one key theorem about a sufficient condition guaranteeing when is LASSO a near-exact recovery algorithm and that is as given in Theorem 1.12 (page 37) of this review paper, http://www.ecs.umass.edu/~mduarte/images/IntroCS.pdf (...wonder why the authors here do not use the term LASSO in this context although their equation 1.15 is just that..)

One can see Theorem 1.9 (page 32) of the same review above for a sufficient condition when BP is a near-exact recovery algorithm for a similar noisily realizable condition.

And even in this limited setting one can see that there is a somewhat of a gap between these two theorems. I wonder how far this has been or can be closed.


texts: Issue with inequalities involving probablities

texts:
I'm reading this paper http://eccc.hpi-web.de/report/2016/044/download/, at page 7 you can see this equation:

$$ \sum_t \mathbb{E}_{w \in W} [|p_t - p_{t|w,w}|] = 2 \sum_t \mathbb{E}_{w \in W} [\max(0,p_t - p_{t|w,w})]$$

I think what we're using here is this:
$$a+b+|a-b| = 2 \max(a,b)$$

but with $a=0$ and $b=p_t-p_{t|w,w}$ we get:
$$p_t - p_{t|w,w} + |p_t - p_{t|w,w}| = 2\max(0,p_t - p_{t|w,w})$$
I know it's a bit of a silly question but I just can't figure it out, maybe I'm missing some fact about probabilities?


texts:
I'm currently doing an internship, in which studying TSP and its algorithms are involved. I'm doing fine with understanding the 2 and 1.5-approximation algorithms for the Metric TSP, but when I come to Arora's PTAS for the Euclidean TSP I get stuck.
I understand what a PTAS is, and I understand the main idea behind Arora's, but when I go deeper into the details, I encounter flaws or simply forgotten specifications (at least from what I understand).
The main article I focus on can be found here : http://algo2.iti.kit.edu/schultes/lebenslauf/publications/euclTSPsummary.pdf

1) When the portals are placed, there's no specification if there are also portals placed on the edges of the bounding box? If not, then how are points that are placed on the edge of the bounding box counted in the algorithm?

2) On page 3 of the article, when computing all valid possibilities of pairings, it is stated :

  "Of course, only the possibilities that cover all points inside the square are useful."

So what if a point is placed in a corner of our square (as they always are for the smallest squares)? Is it counted inside the square or not? If yes, then is it also counted inside its neighboring squares sharing the corner? If no, then when and where is the point taken into count for the algorithm?

3) When a point is placed on a portal of one of the smallest squares, and this point is also placed on an edge of a big square, but NOT on a portal of this big square, how can we find a route that passes this edge and simultaneously crosses the point and a portal between the big squares? Can it use the portal of the small square?

If someone can help me with any of my questions, don't hesitate. Thank you for your time.