texts: Freivalds matrix multiplication with non binary random vector

texts:
Freivalds' algorithm verify matrices (over a field) product $A \times B = C$  by choosing a random binary vector $r$ and verifying if $A(Br)=Cr$ which fails if $AB \neq C$ with probability at most $1/2$.

It seems to me that it can be done by choosing $r$ in some set $S$ which include $0$ resulting that the algorithm fails with probability $\leq 1/|S|$.

All I could find about the algorithm uses binary vector; is the above approach possible? And, as another question, is it possible deduce Freivalds result from Schwartz–Zippel lemma?

this is a tentative proof:

$Dv= (AB-C)v = 0$ imply there exists $\ell, c$ such that
$d_{\ell,c}\neq 0$ and $\sum_{j=1}^{n}v_{j} d_{j,c}=0$, thus

$(*)$  $v_{\ell}= - \frac{1}{d_{\ell,c}}\sum_{\substack{j=1\\ j\neq \ell}}^{n}v_{j}
   d_{j,c}$

Let $E=\big\{v \in S^{n}\colon {v}{D}={0}\big\}$ and $E_\ell = \left\{(v_1,v_2,\dots,v_n)\in S^{n}\colon (*)\right\}$

Partition $S^n$ putting for each $(r_{1},\dots,r_{n-1})\in S^{n-1}$

$A_{r_{1},\dots,r_{n-1}} = \{r_1\}\times \cdots \times \{r_{\ell-1}\} \times S \times \{r_{\ell}\} \times \cdots \times \{r_{n-1}\}$

By total probability law and $E\subset E_\ell$

$P(E) = \sum_{(r_{1},\dots,r_{n-1})}P(E\cap A_{r_{1},\dots,r_{n-1}})\leq$
$\sum_{(r_{1},\dots,r_{n-1})}P(E_\ell\cap A_{r_{1},\dots,r_{n-1}})=$
$\sum_{(r_{1},\dots,r_{n-1})}P(E_\ell~|~ A_{r_{1},\dots,r_{n-1}}) P(A_{r_{1},\dots,r_{n-1}})$

Finally

$P(E_\ell~|~ A_{r_{1},\dots,r_{n-1}})= P\left( \left\{s\in S\colon s=
        \frac{-(\sum_{j<\ell} r_jd_{j,\ell} + \sum_{j>\ell}
          r_{j-1}d_{j,\ell}) }{d_{\ell,c}} \right\}\right) \leq \frac
    1{|S|}$
and
$P(E)\leq  \sum_{(r_{1},\dots,r_{n-1})}\frac 1{|S|}
      P(A_{r_{1},\dots,r_{n-1}})
      =\frac 1{|S|}.$


texts:
Let $p$ be a large prime.  Let $A$ be a $2\times 2$ matrix with coefficients in $GF(p)$ (i.e., coefficients taken modulo $p$).  Let $B=A^k$, where $k$ is an integer not given to us.  Given $p$, $A$, and $B$, the problem to find some $k$ such that $A^k=B$.

For which matrices $A$ does this problem have an efficient (poly-time) solution, and for which is it hard (say, as difficult as the discrete logarithm in $GF(p)$)?

I realize that for some choices of $A$ this problem can be solved efficiently.  For others, it is as hard as the discrete log problem modulo $p$, for which there is no known poly-time algorithm.  Can we somehow classify which matrices $A$ make this easy and which make it hard?  I can work out the answer for some special cases but am having a hard time getting the overall picture.

In other words: When is there an efficient algorithm to solve the discrete logarithm problem, when working with $2\times 2$ matrices over $GF(p)$?

Follow-up question: is there a neat way to generalize from $2\times 2$ matrices to $n\times n$ matrices?


texts: Sorting points such that the minimal Euclidean distance between consecutive points would be maximized

texts:
Given a set of points in a 3D Cartesian space, I am looking for an algorithm that will sort these points, such that the minimal Euclidean distance between two consecutive points would be maximized.

It would also be beneficial if the algorithm would have a tendency toward a higher average Euclidean distance between consecutive points.


texts:
I have a manuscript that has been conference-rejected 3 times up to this point.
Just to clear things up, I am by no means a senior researcher but I am not a junior who cannot judge the strength of my own work either (I have published in some top conferences such as STOC, PODC, etc.). For this manuscript, I haven't submitted it to any venue that is clearly inappropriate with respect to its strength.
In particular, what usually happened was that I get a mix of accept/weak-accept/weak-reject. Even in the reviews that recommended a rejection, they said the paper was decent (my point is that I did not submit a junk paper!). In general, even though I disagree with some of the reviews, I respect the PC's decision.
Now, I don't want to keep submitting it to conferences because while the paper is publishable, it usually does not fall into the top percentage of conferences' acceptance allocation. It will keep wasting people's time (i.e., reviewing). Improving the paper is also unclear because I have matching upper and lower bounds.
I have someone suggest submission to Information Processing Letters since they sort of accept short and simple contributions. I wonder if there is any alternative since I don't really like the idea of publishing with Elsevier.


texts: Distinguishing semantics vs syntactic techniques and the syntax of your semantic domains

texts:
Consider a denotational semantics from simply-typed $\lambda$-calculus into dependent type theory. Is that actually a (trivial) term transformation into that dependent type theory? After all, type theory has a syntax.

In fact, even set theory has a syntax*! So how do we distinguish a denotational semantics from a compositional term transformation?

Now, let's generalize to less trivial program transformations — say, transformation to continuation-passing style (or store-passing style, environment passing style, ...). You can show the same idea through a non-standard semantics (here, a continuation-passing semantics) or a term transformation into a continuation-passing term, and they're distinguished by a binding-time shift. Again, isn't the non-standard semantics also a term transformation?

This is a concrete confusion which I've observed at least twice:

In my work (on incremental computation) I've used a non-standard denotational semantics into type theory (a "change-passing" semantics). After a presentation of that, Gabriel Scherer remarked (kindly) that for him, that was a term transformation into a dependently typed language.
"F-ing modules" preempts this confusion — they defend their presentation of the syntax of semantic objects.

  Semantic signatures. The syntax of semantic signatures is given in Figure 9. (And no, this is not an oxymoron, for in our setting the “semantic objects” we are using to model modules are merely pieces of Fω syntax.) [Emphasis added.]

*Apparently, some (non-formalists) claim that set theory is not "just syntax", but something ontologically different. I'll ignore this subtle philosophical issue; the only reference I know on it is Raymond Turner's Understanding Programming Languages.


texts: If $u\cdot v \in (z \cdot z')^*$ and $v \cdot u \in (z' \cdot z)^*$ then $u \in (z \cdot z')^* \cdot z$

texts:
I'm searching for a reference for the following property:

Fact.  Let $u, v \in A^*$.  Write $w$ for the primitive root of $u\cdot v$, i.e., $u\cdot v =  w^c$.  There are unique words $z, z'$ such that:

$w = z \cdot z'$
$v \cdot u = (z' \cdot z)^c$
$u \in (z \cdot z')^* \cdot z$ and $v \in z' \cdot (z \cdot z')^*$

Proof. Most of the statement is given by, e.g., Lothaire 83:

What is left to show is the last point.  From $u \cdot v = (z\cdot z')^c$, we obtain that $u = (z\cdot z')^k\cdot z_{\text{p}}$ and $v = z_{\text{s}}\cdot z' \cdot (z\cdot z')^{k'}$ where $z = z_{\text{p}}\cdot z_{\text{s}}$ (the case where $u$ ends with a prefix of $z'$ is similar).  Since $v \cdot u = (z' \cdot z)^c$, it holds that $$z' \cdot z = z_{\text{s}}\cdot z' \cdot z_{\text{p}}\enspace.$$
  As $z' \cdot z$ is primitive, all of its permutations are distinct, hence the right-hand side of the previous equation is not a permutation, that is, $z_\text{s} = \varepsilon$. $\square$


texts: Succinct complete problems in DTIME(EXP(EXP(...)))

texts:
I understand complete problems for $EXPTIME$ or $NEXPTIME$ formulated as succinct instances of e.g. $NP$-complete problems such as $3-SAT$. On input $x$, one efficiently computes a circuit $R(x)$ such that $R(x)$ is a succinct encoding of a satisfiable formula if and only if $x\in L$.

I am having trouble going beyond $(N)EXPTIME$. Take $DTIME(2^{2^{p(n)}})$. Are there analogue succinct problems here? This could take the form, on input $x$ one can compute a poly-size circuit $R(x)$ which on each input computes an exponential-size circuit which on each input returns a clause...

Aside from the fact that this is hard to grasp, what troubles me if whether one can guarantee that this hierarchy of circuits calling each other exists, i.e. that at every level the circuits of appropriate size exist. When we consider $NEXP$, we are directly verifying the tableau of a Turing-machine computation, so this is pretty straightforward. But a few levels up it becomes much less clear to me. (Ultimately I am interesting in moving up many levels of exponentiation, possibly even a polynomial number of exponentiations, which I believe would move me out of even $ELEMENTARY$?)

My question is, does anyone have pointers to literature discussing such problems? Or a good sense for what is the appropriate way to define "succinct" complete problems for classes that are so high in the time hierarchy?


texts: Empirical probability of k-SAT satisfiability

texts:
Given a random instance $I_m = I_m(n,k)$ of $k$-SAT with $n$ variables and $m$ clauses, what's the probability $I_m$ is satisfiable?

It's believed that there's a threshold above which satisfiability becomes less likely as $m/n$ increases. The reverse is true as $m/n$ decreases.

Is there an empirical formula for $3$-SAT and other $k$'s that describe the rate at which satisfiability becomes more/less likely as you move away from the threshold?


texts: What is the intuition behind linear logic?

texts: I'm trying to understand linear logic to understand linear type systems better. However, when I read the rules, I fail to get an intuition behind it as I've done in modal logic - $\Box A$ means $A$ is required as in Kripke frames $A$ is required for every reachable world [$\Diamond A$ is $A$ is possible mutatis mutandis]. But I cannot find any intuitive explanation for duality and which of conjunction / disjunction pairs (if any) corresponds to $\land$ and $\lor$.


texts: Decomposition of edges of eulerian graph into maximum number of cycles

texts:
I'm interested in the following problem.

Given an eulerian graph $G=(V,E)$, we are to find a partition of its edges $C_1, C_2, \ldots, C_k$ ($\cup_i C_i=E$ and $i \neq j \leftrightarrow C_i \cap C_j = \varnothing$), such that each $C_i$ forms a simple cycle in $G$ and $k$ is maximum possible.

In other words, we are to cover every edge of an eulerian graph with a maximum number of edge-disjoint simple cycles.

Is this problem well-known? Is there a known approach to solve it?


texts: Does an Earley parser equipped with LL(1)-style lookahead parse in linear time for all LL(1) grammars?

texts:
If a standard Earley parser (with proper handling of nullable non-terminals, see Section 4 of "Practical Earley Parsing" by Aycock and Horspool) is modified with LL(1)-style lookahead, does it then parse all LL(1) grammars in linear time?
To be precise with "LL(1)-style lookahead", I reproduce the $\text{Predictor}$ and $\text{Completer}$ steps of the Earley algorithm, with modifications in bold:

$\text{Predictor}$. If $[A \to \ldots\bullet B\dots, j]$ is in $S_i$, add $[B \to \bullet \alpha, i]$ to $S_i$ for all rules $B \to \alpha$ where $x_{i+1} \in \text{FIRST}(\alpha)$ or $\alpha \Rightarrow^* \lambda$.
$\text{Completer}$. If $[A \to \ldots \bullet, j]$ is in $S_i$, add $[B \to \alpha A \bullet \beta, k]$ to $S_i$ for all items $[B\to \alpha \bullet A \beta, k]$ in $S_j$ where $x_{i+1} \in \text{FIRST}(\beta)$ or $\beta \Rightarrow^* \lambda$.

This is also assuming (for the purposes of this lookahead) that the input is augmented with an EOF symbol $\$$. Note that all $\text{FIRST}$ invocations occur on suffixes of productions, and can be precomputed and stored in a table indexed by production number and dot location.
I am aware of the work by Joop Leo that augments an Earley parser to parse all LR(k) grammars in linear time, but I am curious if just the above is enough for LL(1).
As an example grammar where the above reduces complexity, the grammar $S\to a S \mid \lambda$ normally has an quadratic number of Earley items which goes to linear with the above optimization.


texts: Common techniques for the acyclic orientation problem under some special constraint?

texts:
An acyclic orientation of an undirected graph is an assignment of a direction to each edge(an orientation) that does not form any directed cycle and therefore generates a directed acyclic graph(DAG). I've recently encountered a problem in the field of machine learning(Bayesian network), which turns out to be a special case of the acyclic orientation problem:

  A v-structure is a three-vertex induced subgraph of a DAG like $a\rightarrow b\leftarrow c$. Given an undirected and connected chordal graph $G$, count the number of acyclic orientations in which no v-structure occurs.

I was wondering if there are any commonly used techniques or algorithms to deal with:

the general acyclic orientation problem;
acyclic orientation under some special constraint such as no local structure can occur.

Any information you can provide me would be greatly appreciated.


texts:
If we make a random assignment to the variables in $k$-sat ($m$ clauses), we are going to satisfy $(1-2^{-k})m$ clauses in expectation. In general satisfying fewer clauses is considered easy.

There are newer algorithms for 3-sat that satisfy $(1-1/8+\epsilon)m$ clauses in $O(2^{8\epsilon m})$ time. I'm wondering if it's believed that this sort of result is tight in spirit of SETH?

In other words, does it seem reasonable to believe, say, that for any $\delta>0$ there exists $k$ so satisfying $(1-2^{-k}+\epsilon)m$ clauses in $k$-sat takes $\Omega((2-\delta)^{2^k\epsilon m})$ time?


texts: How many more colours do you need if you add to $G$ a maximum matching from $G^c$?

texts:
The title says it all. Let $G$ be a (simple undirected finite) graph, and let $G^c$ be the complement of $G$ (i.e. contains edges not in $G$ and no more). Let $M$ be a perfect matching in $G^c$.
How large can the difference between the chromatic number of $G$ and the chromatic number of $G+M$ be?
That is, can we say anything about $\max_M \chi(G+M)-\chi(G)$? (at least some bounds).
I would like to keep the problem in the general setting. If it matters, I am more interested in the special case when $G$ is a regular graph.
Thank you.


texts: Does the simply typed lambda calculus have general iteration?

texts:
In more expressive calculi such as System F, the Church numerals, by virtue of their design, allow for iteration over an arbitrary type.  Can this effect be replicated in the simply typed case?

To be precise, consider the simply typed lambda calculus with a single base type $0$, giving the Church numerals the type $\mathsf{N} := (0 \rightarrow 0) \rightarrow 0 \rightarrow 0$.  For any type $\sigma$, can we find a closed term $\mathsf{it}_\sigma : \mathsf{N} \rightarrow (\sigma \rightarrow \sigma) \rightarrow \sigma \rightarrow \sigma$ with the property that

$$
\mathsf{it}_\sigma \underline{n} f x \rightsquigarrow f^nx
$$

?


texts:
Given two lists $L,L'\subseteq\mathbb{R}^d$ of $n$ vectors each,
how fast can we compute for all $p\in L$ the vector of $L'$ that maximizes the inner product with $p$, i.e., $\arg\max_{p'\in L'} \langle p, p'\rangle$.
I am only interested in $d=3$ (and possibly $d=4$).


texts: Expected Kolmogorov complexity under Kolmogorov complexity distribution

texts:
If $K(w)$ is the Kolmogorov complexity of a string $w$, where programs are prefix-encoded so $\sum_{w} 2^{-K(w)} \leq 1$, what is

$$\lim_{n\to\infty} \frac{\sum_{|w|=n}2^{-K(w)} K(w)}{\sum_{|w|=n} 2^{-K(w)}}?$$

Also, what is

$$\lim_{n\to\infty} \frac{\sum_{|w|=n}2^{-K(w)} \frac{K(w)}{n}}{\sum_{|w|=n} 2^{-K(w)}}?$$

The distribution here is closely related to the "universal distribution".
The second limit would say whether $\Theta(|w|)$ is an approximation for $K(w)$.


texts: Graph partition optimization with weights on edges and vertices

texts:
I am interesting in studying the complexity of some graph partition problems, where it is important to take into account the weights on the edges as well as the weight on the vertices. Max-cut only cares about the weights on the edges, while other problems only care about the weights on the vertices. Does anyone know problems in which BOTH weights are important in order to make the optimal partition?

Thank you very much

Here's an example problem:

Input: directed graph with vertex weights $u_i$ and arcs weights $w_{ij}$.

Output: a subset S of V to maximize the sum of the following things:

$\sum_{i, j \in S} w_{ij} + \sum_{i,j \in V - S} w_{ij}$ (arc weights inside each side)
$\sum_{|{i,j} \cap S| = 1} w_{ij}u_j$: the sum over all cut edges of product of  arc weight and the weight of the destination vertex.


texts:
From "Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width" (B. Courcelle et al)  we know that any problem that can be written on MSOL (Monadic Second Order Logic) has a linear algorithm that solves it on graphs with bounded clique-width. However the algorithm takes as input the K-expression of the graph and obtaining it is NP-Complete if K is not fixed.

In a later paper "Improved bottleneck domination algorithms" (T. Kloks et al), there is a description of several bottleneck problems, including the Bottleneck Independent Dominating Set (BIDS) which asks for an independent dominating set D such that maximum weight over the vertices in D is as small as possible.

In section 4.4 they give an algorithm with complexity $O(5^kk^3n)$ for the BIDS problem on graphs with clique-width bounded and where the k-expression is given.
As far as I know this problem can be written in MSOL and hence the first paper (which is earlier) gives a better result for the same problem.

Am I wrong? Is there any technical detail or concept that I am missing?

Thanks in advance


texts: Chomsky-Schützenberger for Deterministic CFLs

texts:
Is there a Chomsky-Schützenberger representation theorem for deterministic CFLs?  Knowing precisely the class of morphisms under which DCFL is closed, such a theorem would probably be of the form:

  $L$ is a DCFL iff $L = h(R \cap D_k)$ for $D_k$ the Dyck on $k$
  parentheses, $R$ a regular language, and $h$ a code with bounded
  delay.

Does it hold? Does it appear anywhere?


texts: Can we not output the Kolmogorov complexity?

texts:
Let us fix a prefix-free encoding of Turing-machines and a universal Turing-machine $U$ that on input $(T,x)$ (encoded as the prefix-free code of $T$ followed by $x$) outputs whatever $T$ outputs on input $x$ (possibly both running forever).
Define the Kolmogorov complexity of $x$, $K(x)$, as the length of the shortest program $p$ such that $U(p)=x$.

  Is there a Turing machine $T$ such that for every input $x$ it outputs an integer $T(x)\le |x|$ that is different from the Kolmogorov complexity of $x$, i.e., $T(x)\ne K(x)$ but $\liminf_{|x|\rightarrow \infty} T(x)=\infty$?

The conditions are necessary, because

(a) if $T(x)\not \le |x|$, then it would be easy to output a number that is trivially different from $K(x)$ because it is bigger than $|x|+c_U$,

(b) if $\liminf_{|x|\rightarrow \infty} T(x)<C$ is allowed, then we can just output $0$ (or some other constant) for almost all numbers, by "luckily" guessing the at most one (finitely many numbers) that evaluate to $0$ (to some other constant) and output there something else.
We can even guarantee $\limsup_{|x|\rightarrow \infty} T(x)=\infty$ by outputting something like $2\log n$ for $x=2^n$.

Also note that our job would be easy if we know that $T(x)$ is not surjective, but little is known about this, so the answer might depend on $U$, though I doubt it would.

I know that relations are studied a lot in general, but

  Has anyone ever asked a similar question where our goal is to give an algorithm that does not output some parameter?

My motivation is this problem http://arxiv.org/abs/1302.1109.


texts: On complexity of permanent ${}\bmod 2^t$?

texts: Valiant showed $\mathsf{Per}(M)\bmod 2^t$ can be computed in $O(n^{4t-3})$ operations where $M\in\Bbb Z^{n\times n}$ holds. Has there been a better algorithm since then?


texts: Interpolation of the square of a polynomial

texts:
Let $\mathcal{P}^2_n$ be the set of rational polynomials of degree at most $2n$ that are sqares of polynomials, i.e. $\mathcal{P}^2_n$ consists of the set of polynomials of the following form:
$$(a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n)^2$$
where $a_i \in \mathbb{Q}$.

There is a natural (polynomial) algorithm to recover $p \in \mathcal{P}^2_n$ from $2n+1$ evaluation points. Nonetheless, one may do much better.

Let $\langle \bar{x}, \bar{y}\rangle = \langle x_0, y_0 \rangle, \langle x_1, y_1 \rangle, \dotsc, \langle x_{n+1}, y_{n+1} \rangle$ be a sequence of $n+2$ pairs of rational numbers. We shall say that $\langle \bar{x}, \bar{y}\rangle$ is interpolating if there exists a polynomial $p \in \mathcal{P}^2_n$ (the witness) such that: $p(x_i) = y_i$ for $0 \leq i \leq n+1$; and we say that it is a code if there is at most one such polynomial. By a simple counting argument one may show that every polynomial $p \in \mathcal{P}^2_n$ has an interpolating code.

For example, the sequence $\langle -1, 1\rangle, \langle 0, 1\rangle, \langle 1, 1\rangle, \langle 2, 1\rangle$ is interpolating in  $\mathcal{P}^2_2$. Its witness is $p(x) = 1$. However, it is not a code, because it has another witness: $q(x) = (x^2 - x + 1)^2$.

On the other hand, the sequence $\langle -1, 1\rangle, \langle 0, 1\rangle, \langle 1, 1\rangle, \langle 3, 1\rangle$ is an interpolating code in  $\mathcal{P}^2_2$ --- its unique witness is the constant polynomial $p(x) = 1$.

There are two natural problems associated with the above setting.

Problem 1: For a given interpolating sequence $\langle \bar{x}, \bar{y}\rangle$ find its witness $p \in \mathcal{P}^2_n$

Problem 2: For a given interpolating code $\langle \bar{x}, \bar{y} \rangle$ find its unique witness $p \in \mathcal{P}^2_n$

What is the computational complexity of the above problems? Are these problems polynomial (there are, of course, obvious exponential algorithms)?


texts: What's the difference between Moggi's computational metalanguage and Moggi's lambda calculus?

texts:
This is a reference confusion. Sometimes I see people use the term "Moggi's computational metalanguage" to refer to the calculus presented by Moggi, and sometimes to "Moggi's computational lambda calculus". Sometimes they use $\lambda_{ml}$ and sometimes $\lambda_c$.

I've always assumed they are both the same thing, but reading the abstract from a talk by Katsumata and Moegelberg, it says:

  we show the fullness of Moggi's monadic translation from the computational lambda calculus $\lc$ with sums to the computational metalanguage $\lml$ with sums using TT-lifting and TT-closure operator.

Aren't these languages the same thing? Where are they introduced specifically with these names? It seems like Moggi sometimes talks about $\lambda_c$ model for what he calls a metalanguage, but then in other paper he talks about computational lambda calculus.


texts: Commutation between a permutation matrix and the sum of permutation matrices corresponding to n-cycles

texts:
Let $S_n$ be the set of all permutations of $n$ elements. Consider the regular representation of $S_n$ in $GL(\mathbb{R}^{n!})$ by $S_n\ni \pi \rightarrow P_\pi$:  $(P_\pi)_{\sigma\tau}=1$ if $\pi \circ \tau=\sigma$ and 0 otherwise.  Let $K_n=\{\pi\in S_n \mid \pi \mbox{ is an n-cycle}\}$.

The paper by Raz and Spieker (see page 4) claimed that it is easy to verify that for any $\pi\in S_n$, $(\sum_{\sigma\in K_n} P_\sigma)P_\pi=P_\pi(\sum_{\sigma\in K_n} P_\sigma)$.

I would like to request for a pointer to the relevant facts that can be used to prove this fact. (Please note that I don't have much background on this -- I'm pretty weak at Algebra and know almost nothing about representation theory. So, any relevant facts that can be found in basic textbooks will be much appreciated.)


texts: Graph theory: definiton of the crown of a graph

texts:
I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand:

A crown of a graph $G = (V,E)$ consists of $H\subseteq V$ and $I \subseteq V$ with $H \cap I = \varnothing$ s.t. the following three conditions hold:

$H = N(I)$
$I$ forms an independent set
the edges connecting $H$ and $I$ contain a matching in which all elements of $H$ are matched.

$N(I)$ is the neighborhood of vertices $I$, i.e., $N(I) = \{u \mid v \in I \land  (u,v) \in E\}$.

I'm stuck with the third point: I'm interpreting it as "in the bipartite graph $(H, I, F)$ with $F = \{(u,v) \in E \mid u\in I \land v \in H\}$ there is a matching $M\subseteq F$ s.t. $\forall v \in H: \exists (u,v) \in F$, i.e., each vertex in $H$ is covered by an edge in the matching $M$".

But does this not imply that  $|I| \geq |H|$ since there can at most be $|I|$ non-adjacent edges connected to vertices in $I$? This would imply that $I$ is a set of vertices that have degree 1, which surely is not the intention since a crown is intended to be a generalization of 1-connected vertices.

What am I missing?


texts: What are the parts of consistency model playing in hardware, operating system, and programming language?

texts:
In multiprocessor programming, consistency model is the key concept to express the correctness of concurrent objects ranging from simple read/write shared variable to concurrent data structures like FIFO, SkipList, etc.

I think I can understand the principle underlying consistency model when it is treated as an abstract specification of correctness. I am also able to check an execution of some concurrent object against a specific consistency model.

However, when I want to explore more about multiprocessor programming, especially when it comes to the layers of the hardware, operating system, compiler, and virtual machines (JVM, for example), I am totally confused.

At the hardware level, there is only one main memory while each processors holds its own caches. As a consequence, so called cache coherence problem arises and many protocols are proposed to address it.

What is the relation between cache coherence and consistency model?

Up to the operating system and compiler, processes are interleaved and method calls may be reordered for optimization.

Do these make consistency model indispensable?

At the programming language level, I know there is Java Memory Model and it does not enforce Sequential consistency.

What does it mean for JVM to follow some given consistency model?

  In summary, what are the parts of consistency model playing in hardware, operating system, and programming language?

I don't understand the whole story and very confused.

Thank you for any suggestions and references.


texts: inapproximability of logarithic factor of indepence set

texts:
The hardness result derived using PCP theorem for Independent set suggests that there exists some absolute constant $\epsilon_0$ such that for $0< \epsilon < \epsilon_0$, it is hard to approximate independence number $\alpha$ with a factor $n^{1-\epsilon}$.

What does this tell about some quantity (say $p$) that has a one to one correspondence with say $\ln \alpha$. Is the same inapproximation ratio preserved for $p$ or the inapproximation ratio also becomes logarithmic?

Thanks in advance.


texts: Number of equivalence classes in regular languages as a function of DFA size

texts:
This question is related to a recent
question
by Janoma.
Background
In constraint programming, a regular global constraint $c$ over a
domain $D$ is a pair $(s, M)$ with $s$ a tuple of variables (the
scope) and $M$ a DFA over the domain $D$. An assignment $\theta$ to
$s$ satisfies $c$ if $M$ accepts the string
$\theta(s_1)\theta(s_2)\ldots\theta(s_n)$.
Below, assume that the domain $D$ is fixed. Define an equivalence
relation $\sim$ over the set of strings $T = D^{|s|}$ such that $a
\sim b$ if for every DFA $M$ either $a, b \in L(M)$ or $a, b \not\in
L(M)$. Intuitively, two strings are equivalent iff no DFA can
distinguish them. If that is true, then they also satisfy the same
regular constraints.
If we do not restrict the DFAs in any way, then the set of equivalence
classes $T/{\sim}$ is just $T$ itself. I am interested in the number of
equivalence classes wrt. $\sim$ as a function of the number of states $n$
that we allow for the DFA. Clearly, if $n = |D|^{|s|}$ (ignore
constants) then $|T/{\sim}| = |T|$. (Of course, $n$ here will itself be a
function of $|s|$.)
Questions

What is the smallest $n$ for which $|T/{\sim}| = |T|$?
What happens below that? In particular,

is there an $n$ such that $|T/{\sim}| = O(|s|^{|D|})$?
is there an $n$ such that $|T/{\sim}| = O(|s| \times |D|)$?

My motivation for this question is that having a polynomial
($|s|^{|D|}$) number of equivalence classes like this gave me a
tractable case of constraint problems with cardinality constraints. I
am now trying to see if something along these lines can be done for
the regular constraint.
Edit: Note also this answer by Hermann Gruber to the question referenced at the top. The bounds in the paper the answer links should yield a $k$ such that the answer to question 1 must be $\geq k$, but it is not obvious to me.


texts:
I'm reading the paper (http://proceedings.mlr.press/v9/glorot10a/glorot10a.pdf) from Glorot and Bengio. There is something that I don't understand at the abstract section on page 1.

"Training may be more difficult when the singular values of the Jacobian associated with each layer are far from 1"

Why is the singular value of the Jacobian important for training?

Why is the singular value being far from 1 difficult for training?


texts: Reference for Levin's optimal factoring algorithm  ?

texts:
In Manuel Blum's "Advice to a Beginning Graduate Student":

  LEONID LEVIN believes as I do that whatever the answer to the P=NP? problem, it won't be like anything you think it should be. And he has given some wonderful examples.
  For one, he has given a FACTORING ALGORITHM that is proVably optimal, up to a multiplicative constant.
  He proves that if his algorithm is exponential,
  then every algorithm for FACTORING is exponential.
  Equivalently, if any algorithm for factoring is poly-time,
  then his algorithm is poly-time.
  But we haven't been able to tell the running time of his algorithm because, in a strong sense, it's running time is unanalyzable.

Levin's publications page returns a 404, DBLP shows nothing related to factoring, and a search for "leonid levin factoring" on Google Scholar returns nothing of interest that I could find. AFAIK the generalized sieve is the fastest algorithm known for factoring. What is Manuel Blum talking about? Can anyone link me to a paper?


texts: What is the application of combinatorial game theory

texts: I find Combinatorial Game Theory very interesting as my primary interest is mathematics. My question is why do Computer Scientists (who tend to have a more practical approach) study it as well? Are there some applications of it? This question is similar to this one but I am asking about combinatorial games such as nim. Could someone provide me with a reference?


texts: Smallest Boolean circuit to generate a language

texts:
Consider a non-empty language $L$ of binary strings of length $n$. I can describe $L$ with a Boolean circuit $C$ with $n$ inputs and one output such that $C(w)$ is true iff $w \in L$: this is well-known.

However, I want to represent $L$ with a Boolean circuit $C'$ with $n$ outputs and a certain number of inputs, say $m$, such that the set of the output values of $C'$ for each of the $2^m$ possible inputs is exactly $L$.

  Given $L$, how can I find such a circuit $C'$ of minimal size, and what is the complexity? Is there any relationship between known bounds about the size of circuits of the first kind ($C$) and circuits of this second kind ($C'$), or the complexity of finding them?

(Observe that there is some sort of duality in the following sense: given $C$, I can easily decide if an input word $w$ is in $L$ by evaluating the circuit, but it is NP-hard in general to find some word in $L$ by finding an assignment such that the output is true. Given $C'$ it is likewise NP-hard to decide if some input word $w$ is in $L$ because I have to see if an assignment yields $w$ as output, but it is easy to find some word in $L$ by evaluating the circuit on any arbitrary input.)


texts: Techniques for showing non-derivability in logics and other formal proof systems

texts:
In proof systems for classical propositional logic if one want to show that a certain formula $\psi$ is not derivable one simply shows that $\neg\psi$ can be derived (although other techniques certainly are possible). Non-derivability follows essentially from the soundness and completeness of the proof system.

Unfortunately for non-classical logics and more exotic proof systems (such as the rules underlying operational semantics) no such direct technique exists. This could be because the non-derivability of $\psi$ does not imply that $\neg\psi$ is derivable, as is the case with intuitionistic logics, or simply that no notion of negation exists.

My question is given a proof system $(\mathcal{L},\vdash)$, where $\vdash\;\subseteq\mathcal{L}^*\times\mathcal{L}$, (and presumably its semantics), what techniques exist to show non-derivability?

The proof systems of interest could include operational semantics of programming languages, Hoare logics, type systems, a non-classical logic, or inference rules for what-have-you.


texts:
The standard proof of the Chernoff bound (from the Randomized Algorithms textbook) uses the Markov inequality and moment generating functions, with a bit of a Taylor expansion thrown in. Nothing too difficult, but somewhat mechanical.

But there are other Chernoff bound proofs that expose the deeper structure driving the result. For example, there's an information-theoretic version that goes via the method of types, exemplified by this paper of Impagliazzo and Kabanets, as well as this brief post by Sanjoy Dasgupta. These latter proofs are more "intuitive" in that they provides a generalization of the standard result, as well explaining where the funny terms in the exponent come from (it's a KL-divergence).

  What are good examples of such things
  ? To be more concrete, here are the
  rules:

  The statement should be reasonably well-known (the kind of thing that
  would be taught in some kind of
  graduate class)
  There should be a "standard" proof available in textbooks or standard
  reference material that is "commonly"
  taught
  There should be an alternate proof that is not so well known, is NOT
  commonly taught, and either proves a
  more general statement or links the
  statement to a deeper mathematical
  structure.

I'll start off with two examples.

The chernoff bound

"textbook" proof: markov inequality, moment generating functions, Taylor expansion (MR)
Uncommon and insightful proof: method of types, exponent of tail involving KL-divergence

The Schwartz-Zippel Lemma

"textbook" proof: base-case involving univariate polynomial. Induction on number of variables
"uncommon" proof: geometric argument via Dana Moshkovitz (and Per Vognsen)

One example per answer please.

p.s I'm not necessarily implying that the uncommon proof should be taught: a direct proof is often easier for students. But in the sense that "proofs help us understand", these alternate proofs are very helpful.


texts: Algorithm for Longest Path in Undirected Weighted Graph

texts:
EDIT Dec 14th 2010
The algorithm is not correct: it's not the case that it always returns the optimal $W$.

While reasoning on this and other similar questions, I've sketched an algorithm that, given an undirect weighted graph $G=(V,E)$ of $n$ vertices and a vertex $v_i \in V$, returns an array $W$ of $n$ weights, where each $W_j$ (with $j \in [1,n]$) is the weight of the path of maximum weight from $v_i$ to $v_j$. Something must be wrong with the algorithm, but so far I couldn't figure out what. The algorithm seems correct at first sight, maybe its flaw is that the labeled tree $T$ it builds (see below) grows exponentially in size (I didn't yet implement it to see what happens).

Other than its input, the algorithm uses two further objects:

A labeled tree $T$, which is initially composed by only one node whose label is $i$ (such node will be $T$'s root)
A relation $R \subseteq D^2$. $D$ is the domain of "paths without repetition", and $R(x,y)$ means "path $x$ removes path $y$". $R$ is initially the empty set.
A relation $Q \subseteq D^2$. $Q$ is built from $R$. $Q$ is initially the empty set.

The algorithm operates as follows:

For each leaf $v_k$ of $T$, add to it one new child node labeled $c$ for each $v_c \in V$ such that $\{ v_k, v_c \} \in E$ and there isn't any node labeled $c$ in the path in $T$ from $v_k$ to the root.
If $T$ changed during Step 1, go to Step 3. Else, go to Step 7.
Given a generic node $v_t$ of $T$, let $p_t$ be the path in $T$ from the root to $v_t$, let $w_t$ be the weight of $p_t$, and let $l_t$ be the label of $v_t$. Let $V(l)$ be the set of nodes of $T$ whose label is $l$. Now for each different label $l_k$ appearing in a leaf of $T$, let $V_2(l_k)$ be the set of all those subsets of $V(l_k)$ having cardinality $2$; for each $\{v_{k_1}, v_{k_2}\} \in V_2(l_k)$, if $w_{k_1} \geq w_{k_2}$ then add $(p_{k_1}, p_{k_2})$ to $R$, else add $(p_{k_2}, p_{k_1})$ to $R$.
Compute the relation $Q$ as follows: $Q$ contains all the couples of $R$, plus those obtained according to the following rule: if $(x, y) \in Q$ and $(z, w) \in Q$ and $y$ is a prefix of $z$, then $(x, w) \in Q$.
For each $y$ such that $\exists x (x, y) \in Q$, if $\not \exists z (z, y) \in Q$ such that $y$ is a prefix of $z$, then remove from $T$ the subtree whose root $r$ has a path from $T$'s root to $r$ equal to $y$.
Set both $R$ and $Q$ equal to the empty set. If $T$ changed during Step 5, then go to Step 3. Else, go to Step 1.
Set $W_j = 0, \forall j \in [1,n]$. Visit the tree $T$: for each visited $v_t$, if $w_t > W_{l_t}$, set $W_{l_t} = w_t$. Return $W$.

  Question(s)

  Is the algorithm correct?
  Where is it flawed?
  Is there an instance such that $T$ has exponentially many leaves?

Apologies in advance if this algorithm turns out to be completely uninteresting and naive.


texts: Are there any annotated formal verification systems for pure functional programming languages?

texts:
ACSL (Ansi C Specification Language), is a specification for C code, annotated with special comments, that allows C code to be formally verified.

I have not looked into it, but I imagine that the formal methods used in ACSL verifiers would be similar to Hoare Logic. For pure functional languages though, such as Haskell, I can't imagine what sort of formalism would be used for formal verification.

Has anyone made something similar to ACSL, but for a pure functional language? If not, has there been any research into specification-annotated style formal verification for functional languages?

I know that there's dependent typing, which many languages (Agda, Idris, etc...) support, but in Haskell dependent typing is difficult without doing some (unreadable?) type-wizardry. With that in mind, and since Haskell has so much better library support than Agda and Idris, I believe such a system for functional formal verification might be useful, but I don't know if research has been done on this or not.


texts:
I have $N$ bins with capacity $M$ and $k$ objects with size $s_i$. The goal is to pack these objects in the bins. Until now it is similar to the bin-packing problem. But the twist is that each object has a partial overlap with others. So while object 1 and 2 have sizes $s_1$ and $s_2$, when I put them in the same bin the filled space will be $s_1+s_2-O_{12}$ where $O_{12}\ge0$. Note that for 3 objects it is $s_1+s_2+s_3-O_{12}-O_{23}-O_{13}+O_{123}$

Is there any approximation algorithm like the ones for original bin-packing for this problem too?


texts:
I am new to studying rewriting systems as a first year PhD student.  I would like to propose a special topics course on rewriting theory, and I want to make sure I don't leave any of the original sources out.

I have a copy of Barendregt and Terese as textbook sources.  For original paper's: I have been looking at Dershowitz's work on proving termination, Huet's paper on confluence, Van Oostrom's paper on decreasing diagrams, and Ohlebusch's paper on confluence modulo equivalence, and Toyama's work on modularity.  I hope to end up with a smattering of both classical and recent influential papers.  Also, if anyone can recommend some good papers on the links between algebraic topology, category theory, and rewriting theory, I would appreciate that as well.


texts: Is it possible to add law of excluded middle to Martin-Löf type theory as an axiom? It seems to me, that it's possible to add it to Coq since Coq has a module for non-constructive reasoning. Also, it seems to be impossible to Agda since it leads to inconsistency. But can we add it to plain MLTT? And why it will/won't work?


texts: How to define a function inductively on two arguments in Coq?

texts:
How can I convince Coq that the recursive function given below terminates?
The function takes two inductive arguments.
Intuitively, the recursion terminates because either argument is decomposed.

Specifically, the function takes two trees as input.

Inductive Tree :=
| Tip: Tree
| Bin: Tree -> Tree -> Tree.

On Trees, I like to do the following style of induction.

Inductive TreePair :=
| TipTip : TreePair
| TipBin : Tree -> Tree -> TreePair
| BinTip : Tree -> Tree -> TreePair
| BinBin : TreePair -> TreePair -> TreePair.

Fixpoint pair (l r: Tree): TreePair :=
  match l with
    | Tip =>
      match r with
        | Tip => TipTip
        | Bin rl rr => TipBin rl rr
      end
    | Bin ll lr =>
      match r with
        | Tip => BinTip ll lr
        | Bin rl rr => BinBin (pair l rl) (pair lr r)
      end
  end.

The definition of TreePair is accepted, but the definition of the function pair yields the error message:

Error: Cannot guess decreasing argument of fix.

So I am interested in how to convince Coq of the termination.


texts: Is minimum weight simple cycles through specified vertics fixed parameter tractable?

texts:
The problem formulation is as follows:

Input: Undirected graph $G=(V,E)$, a set of vertices $S\subseteq |V|$, a weight function $w:E\to \mathbb{R}$ and a threshold $T\in \mathbb{R}$.
Parameter: $|S|=k$.
Problem: decide whether there exist in $G$ a simple cycle going through $S$'s vertices and it's weight is $\leq T$.

Andreas Bjorklund et al. gave a $O^*(2^k)$ algorithm for finding the shortest simple cycle through $k$ vertices (i.e. in this setting $\forall e:w(e)=1$).
Can this result be extended (or is there other known result) for finding a minimum weight cycle through $k$ vertices (for a weighted graph) in $FPT$ time?


texts: What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?

texts: I guess it would be called #P-Space but I have found only one article vaguely mentioning it. How about the counting version of EXP-TIME-Complete, NEXP-Complete as well as EXP-SPACE-Complete problems? Is there any previous work that can one cite in regards to this or any type of inclusion or exclusion like Toda's Theorem?


texts: All recursive algorithms are inherently NOT-inplace, isn't it?

texts:
As recursive algorithms depend on the stack whose size is in almost all the cases depend on input, why don't we consider all the recursive algorithms as NOT-inplace algorithms?

Consider for example, Quicksort, we say it as inplace sort, but in reality, (average case) it uses O(log(n)) memory in stack? So, how can it be called inplace sort?!


texts:
I couldn't find documents elaborating on this: if the Curry Howard correspondence is to be interpreted as establishing a strong relation between proofs and programs, should there not be a strong relation between proof and computational complexity?
I'm asking this as a reference request.


texts: What are the outstanding questions in purely functional data structures?

texts:
This question is inspired by another question about what's new in PFDS since the publication of Okasaki's book in 1998.

I'll start with two questions I have:

Is there a purely functional set data structure that approaches the speed of hash tables? Tries aren't  there yet.
Are there purely functional finger trees with O(1) append? The best so far is O(lg lg n), devised by Kaplan and Tarjan.

What other purely functional data structure problems are open?


texts: Construction of graphs where every pair of vertices have an unique common neighbor

texts:
Let $G$ be a simple graph on $n$ vertices $(n > 3)$ with no vertex of degree $n − 1$. Suppose that for any two vertices of $G$, there is a unique vertex adjacent to both of them. It is an exercise from A Course in Combinatorics, van Lint and Wilson, to prove that such a graph is regular.

My question, however, is whether graphs satisfying the given constraints even exist. While discussing the original exercise during a problem-solving session, someone asked if we could come up with an example of a graph where every pair of vertices have an unique common neighbor, and there are no global vertices. Neither were we able to come up with a concrete example or procedure for construction, nor did we establish a proof that no graph has these properties.

Any suggestions?

Note: as for proving that such a graph is regular, it turns out to be fairly straightforward, the rough idea is to pair off the neighbors of every pair of vertices using the unique-common-neighbor criteria to establish the fact that every pair of vertices have the same degree, and then a transitivity argument, with the help of the no-global-vertex constraint, gives us that the graph is regular.


texts: Lower bound for reversing a list using queues

texts:
How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues?

Each queue is FIFO.  Time refers to the number of operations on the queues.

There are different formal models for the queues, but an answer in any of the following models would be interesting (models listed in the order of increasing difficulty of proving the lower bound):

1. Shuffle only: Each item is a black box.
2. Shuffle+copy: Each item is a black box that can be copied and deleted.
3. Linear network coding: Items can be xor-ed but are otherwise black boxes.
4. An item has $O(\log n)$ bits; we have a state machine of our choosing with $n^{O(1)}$ states.
5. An item is 1 bit, and we have a state machine with $O(2^{n^c})$ states ($c < 1$).
6. Same as (5), but we only have the decision problem (palindrome).
7. Same as (6), but we are nondeterministic.

As this question notes, a list can be reversed using two queues in time $O(n \log n)$, but the accepted answer did not prove optimality.  More generally, $k > 1$ queues (with $O(k)$ items in local memory) can be used to sort a list with $O(n \log n / \log k)$ queue operations.

The reason I expect the $Ω(n \log n)$ lower bound in this question is that processing using queues essentially shuffles items, and a list cannot be reversed using $o(\log n)$ riffle shuffles since each shuffle at most halves the length of each ascending sequence.  Intuitively, after $o(n \log n)$ queue operations, most of the list will still have a mostly unshuffled feel, but I do not know how to formalize and prove it.  One attempt is to assign to a sorted subsequence of length $m$ score $m \mathrm{lg} m$, with the total score being the maximum sum of scores across disjoint subsequences; I conjecture that in (1), the total score changes by at most $O(n)$ after $O(n)$ operations.  For (3)-(7) (above), the lack of shuffling will need to be complemented with a communication complexity argument.

Model (5) may look powerful, but even it cannot implement a stack with $o(n^{(1-c)/k})$ amortized time per operation where $k$ is the number of queues (as my answer to this question can be modified to show).  However, data structure lower bounds (even when amortized) are often qualitatively different from (and easier than) superlinear optimal running time lower bounds.

For (7), it is enough to consider two queues, since two queues are known to nondeterministically simulate $O(1)$-queues in linear time by keeping the computation path in one queue, and doing $k$ passes to check the consistency of all $k$ queues (and by repeating the construction, it sufficies that for one of the queues, all reads happen after all writes).


texts: Computing the Levenshtein distance quickly

texts:
Given a huge database of allowed words (alphabetically sorted) and a word, find the word from the database that is closest to the given word in terms of Levenshtein distance.

The naive approach is, of course, to simply compute the levenshtein distance between the given word and all the words in the dictionary (we can do a binary search in the database before actually computing the distances).

I wonder if there is a more efficient solution to this problem. Maybe some heuristic that lets us reduce the number of words to search, or optimizations to the levenshtein distance algorithm.

Links to papers on the subject welcome.


texts: Embedding points in Euclidean space into a box

texts:
If I give you a set of points in Euclidean space, is there a criterion to determine whether there exists a (potentially higher-dimensional) rectangular prism / box that has these points as their vertex set?

For instance, an equilateral triangle has this property, as (1,0,0), (0,1,0), and (0,0,1) form an equilateral triangle and are corners of the unit cube.

This is related to some larger work on L1 and L2 embeddings into a box, on which I have some passing familiarity with the literature (Menger's theorem, Schoenberg, etc.).


texts:
I wrote a code that implements a simple genetic algorithm to maximize:

f(x) = 15x - x^2

The function has its maximum at 7.5, so the code output should be 7 or 8 since the population are integers. When I run the code 10 times I get 7 or 8 around three times out of 10.I chose mating probability of 0.7 and mutation probability of 0.001. What modification should I make to further improve the algorithm and what are different types of genetic algorithms?

Here is the code:

from random import *
import numpy as np

#fitness function
def fit(x):
    return 15*x -x**2
#covert binary list to decimal number
def to_dec(x):
    return int("".join(str(e) for e in x), 2)

#picks pairs from the original population
def gen_pairs(populationl, prob):
    pairsl = []
    test = [0, 1, 2, 3, 4, 5]
    for i in range(3):
        pair = []
        for j in range(2):
            temp = np.random.choice(test, p=prob)
            pair.append(populationl[temp].copy())
        pairsl.append(pair)

    return pairsl

#mating function
def cross_over(prs, mp):
    new = []
    for pr in prs:
        if mp[prs.index(pr)] == 1:
            index = np.random.choice([1,2,3], p=[1/3, 1/3, 1/3])
            pr[0][:index], pr[1][:index] = pr[1][:index], pr[0][:index]

    for pr in prs:
        new.append(pr[0])
        new.append(pr[1])

    return new

#mutation
def mutation(x):
    for chromosome in x:
        for gene in chromosome:
            mutation_prob = np.random.choice([0, 1], p=[0.999, .001])
            if mutation_prob == 1:
                #m_index = np.random.choice([0,1,2,3])
                if gene == 0:
                    gene = 1
                else:
                    gene = 0
    #generate initial population
    randlist = lambda n:[randint(0,1) for b in range(1, n+1)]
for j in range(10):
    population = [randlist(4) for i in range(6)]
    for _ in range(20):
        fittness = [fit(to_dec(y)) for y in population]

        s = sum(fittness)
        prob = [e/s for e in fittness]
        pairsg = gen_pairs(population.copy(), prob)

        mating_prob = []
        for i in pairsg:
            mating_prob.append(np.random.choice([0,1], p=[0.4,0.6]))

        new_population = cross_over(pairsg, mating_prob)
        mutated = mutation(new_population)
        decimal_p = [to_dec(i)for i in population]
        decimal_new = [to_dec(i)for i in new_population]
        # print(decimal_p)
        # print(decimal_new)
        population = new_population
    print(decimal_new)


texts: Finding common label sequences in a directed acyclic graph

texts:
I have a directed acyclic graph with ~250k nodes, each node has one of about 100 symbols as label. Letting a word be the sequence of n symbols that corresponds to a path containing n nodes in the graph, how can I find the most common words? What known algorithms should I study?

An interesting extension is to let edges also have one of about 100 symbols (the set of edge symbols does not intersect the set of node symbols) as label, redefining a word to be the sequence of length n+(n-1) symbols that corresponds to a path containing n nodes and n-1 edges.

Reading tips and wikipedia links are appreciated as well as more elaborate answers.


texts: Small graph with gap between chromatic and vector chromatic number?

texts:
I’m looking for a small graph $G$ whose vector chromatic number is smaller than the chromatic number, $\chi_v(G)<\chi(G)$.

($G$ has vector chromatic number $q$ if there is an assignment $x\colon V \rightarrow \mathbf R^d$, where intuitively the vectors associated with neighbouring vertices are far apart. The requirement is $\langle x(v), x(w)\rangle \leq -1/(q-1)$. For example, for $q=3$, the vertices of a triangle suffice.)

A graph’s vector chromatic number is no larger than the chromatic number: $\chi_v(G)\leq \chi(G)$. Examples are known of graphs with $\chi_v(G)=3$ $\chi(G)=n^\delta$. (The original paper by Karger, Motwani, Sudan [JACM, 45:246-265] (manuscript) suggests generalised Kneser graphs, a more recent paper uses a construction based on random unit vectors.)

I think I have an example graph $K$ with $\chi_v(K)=4$ and $\chi(K)=8$ (based on computer calculation). This graph has 20 vertices and 90 edges.

Is there a smaller example? A tempting avenue would be to provide a concrete vector 3-colouring of the Chvatal or Grötzsch graph, if such a beast exists.

($\chi_v$ need not be an integer, but it would be nice. Update: As pointed out below, the nonintegral case is indeed easy. Thanks.)

Update: Grötzsch and Chvátal

I couldn’t resist thinking about vector 3-colouring the Chvátal and Grötzsch graphs.

The Grötsch graph can be vector 3-coloured as follows: Put the degree five node on the North pole. The 5 degree-4 nodes are evenly placed on the same latitude, around 77 degrees from North: imagine a pentragram painted on Earth’s northern hemisphere. The remaining 5 nodes (of degree 3) end up on the Southern hemisphere, around 135 degree from North. The have the same longitude as the 5 others. (I’ll upload a drawing when I have one, but it’s harder to draw geodesic lines in TikZ than I thought.)

According to an SDP solver, Chvátal also admits a vector 3-colouring, but the output is just a bunch of vectors in 5 dimensions that I have difficulties interpreting.

(A third attempt failed: Inspired by Yury’s construction, take the 5-cycle and add an apex vertex adjacent to all the others. This graph has chromatic number 4. But according to my solver it is not vector 3-colourable.)


texts: Evaluate boolean circuit on batch of similar inputs

texts:
Suppose I have a boolean circuit $C$ that computes some function $f:\{0,1\}^n \to \{0,1\}$.  Assume the circuit is composed of AND, OR, and NOT gates with fan-in and fan-out at most 2.

Let $x \in \{0,1\}^n$ be a given input.  Given $C$ and $x$, I want to evaluate $C$ on the $n$ inputs that differ from $x$ in a single bit position, i.e., to compute the $n$ values $C(x^1),C(x^2),\dots,C(x^n)$ where $x^i$ is the same as $x$ except that its $i$th bit is flipped.

Is there a way to do this that is more efficient that independently evaluating $C$ $n$ times on the $n$ different inputs?

Assume $C$ contains $m$ gates.  Then independently evaluating $C$ on all $n$ inputs will take $O(mn)$ time.  Is there a way to compute $C(x^1),C(x^2),\dots,C(x^n)$ in $o(mn)$ time?

Optional context: If we had an arithmetic circuit (whose gates are multiplication, addition, and negation) over $\mathbb{R}$, then it would be possible to compute the $n$ directional derivatives ${\partial f \over \partial x_i}(x)$ in $O(m)$ time.  Basically, we could use standard methods for computation of the gradient (back-propagation / chain rule), in $O(m)$ time.  That works because the corresponding function is continuous and differentiable.  I'm wondering whether something similar can be done for boolean circuits.  Boolean circuits aren't continuous and differentiable, so you can't do the same trick, but maybe there is some other clever technique one can use?  Maybe some kind of Fourier trick, or something?

(Variant question: if we have boolean gates with unbounded fan-in and bounded fan-out, can you do do asymptotically better than evaluating $C$ $n$ times?)


texts: What is special about $2^{32}/\phi$ in cryptography?

texts:
In the Tiny Encryption Algorithm:

  Different multiples of a magic constant are used to prevent simple attacks based on the symmetry of the rounds. The magic constant, 2654435769 or 9E3779B916 is chosen to be $2^{32}/ \phi$, where ϕ is the golden ratio.

Which properties does $2^{32}/ \phi$ have that makes it useful in this context?


texts:
Suppose we have two dependent random variables $X$ and $Y$, each of which is uniform over $\{0,1\}^n$, such that their mutual information $I(X;Y)$ is small, say, at most $\sqrt{n}$. Does this imply that there exist large sets $\mathcal{X}, \mathcal{Y} \subset \{0,1\}^n$ such that the product set $\mathcal{X} \times \mathcal{Y}$ is contained in the support of the distribution $(X,Y)$?

A variant of this question can be phrased in graph-theoretic terms: Suppose we have a sufficiently dense bipartite graph G. Does this imply that $G$ contains a large complete sub-graph $G'$? (i.e., $G'$ is required to be a complete bipartite graph with bi-partition $(A,B)$ such that $A$ and $B$ are relatively dense in the corresponding parts of $G$)


texts: Complexity results for Lower-Elementary Recursive Functions?

texts:
Intrigued by Chris Pressey's interesting question on elementary-recursive functions, I was exploring more and unable to find an answer to this question on the web.

The elementary recursive functions correspond nicely to the exponential hierarchy, $\text{DTIME}(2^n) \cup \text{DTIME}(2^{2^n}) \cup \cdots$.

It seems straightforward from the definition that decision-problems decidable (term?) by lower-elementary functions should be contained in EXP, and in fact in DTIME$(2^{O(n)})$; these functions also are constrained to output strings linear in their input length [1].

But on the other hand, I don't see any obvious lower bounds; at first glance it seems conceivable that LOWER-ELEMENTARY could strictly contain NP, or perhaps fail to contain some problems in P, or most likely some possibility I've not yet imagined. It would be epicly cool if LOWER-ELEMENTARY = NP but I suppose that is too much to ask for.

So my questions:

Is my understanding so far correct?
What is known about the complexity classes bounding the lower elementary recursive functions?
(Bonus) Do we have any nice complexity-class characterizations when making further restrictions on recursive functions? I was thinking in particular of the restriction to $\log(x)$-bounded summations, which I think run in polynomial time and produce linear output; or constant-bounded summations, which I think run in polynomial time and produce output of length at most $n + O(1)$.

[1]: We can show (I believe) that lower-elementary functions are subject to these restrictions by structural induction, supposing that the functions $h,g_1,\dots,g_m$ have complexity $2^{O(n)}$ and outputs of bitlength $O(n)$ on an input of length $n$. When $f(x) = h(g_1(x),\dots,g_m(x))$, letting $n := \log x$, each $g$ has output of length $O(n)$, so $h$ has an $O(n)$-length input (and therefore $O(n)$-length output); the complexity of computing all $g$s is $m2^{O(n)}$ and of $h$ is $2^{O(n)}$, so $f$ has complexity $2^{O(n)}$ and output of length $O(n)$ as claimed.

When $f(x) = \sum_{i=1}^x g(x)$, the $g$s have outputs of length $O(n)$, so the value of the sum of outputs is $2^n 2^{O(n)} \in 2^{O(n)}$, so their sum has length $O(n)$. The complexity of summing these values is bounded by $2^n$ (the number of summations) times $O(n)$ (the complexity of each addition) giving $2^{O(n)}$, and the complexity of computing the outputs is bounded by $2^{n}$ (the number of computations) times $2^{O(n)}$ (the complexity of each one), giving $2^{O(n)}$. So $f$ has complexity $2^{O(n)}$ and output of length $O(n)$ as claimed.


texts: TCS oriented refs/survey on group theoretic word problem

texts:
The word problem for groups was shown to be Turing-complete in 1955 but has many decidable subcases. This problem arose more in mathematical group theory than in theoretical computer science, but now strong interconnections between the two are now known.

  Are there any TCS-oriented references or surveys on the word problem for groups or its applications?

Related questions:

bridge problems for group theory/formal languages, cs.se
Uses of algebraic structures in theoretical computer science, tcs.se

Related posts on RJ Lipton's blog:

Gromov's Theorem
Word problem for free groups


texts:
I'm attending a course on Type Theory. The textbook is 'Types and Programming Languages' by Prof. Benjamin C. Pierce.

In Chapter 29, Prof. Pierce introduces 'type operator', which can generate another type with an input type. For example, 'Pair' can be a type operator which accepts any two types $X$ and $Y$ to form a type $Pair\; X\; Y$.

However, the 'type operator' itself is a type - a special type which is different from 'proper type' such as $Nat$ and $Nat \rightarrow Nat$. It seems that all 'proper types' have terms of it. For example, $Nat \rightarrow Nat$ has at least $(\lambda x : Nat. x)$. But type operator like $Pair$ does not have any term of it.

Prof. Pierce doesn't explain why $Pair$ has no term. Why 'non-proper' types can be called a 'type' when it does not correspond to any collection of programming language terms?


texts: Books/Lecture Notes on Parametrized Complexity

texts: I would like to learn about Parametrized Complexity (both on the algorithmic side and on the hardness side). What books/lecture notes can I read on this subject?


texts:
I am looking for a formal definition of so-called "flowcharts" used as representation of programs or business processes.

Is there some good one around ?

Thx
JCLL


texts: Local Graph Isomorphism to construct Global Graph Isomorphism

texts:
Does there exist a Graph Isomorphism Algorithm that uses Local Isomorphism to construct a Global Isomorphism?

For example, two graphs are given, say, $H, G$. it is asked to determine whether $G\simeq H$.

Now assume there exists an algorithm that splits graph $G$  in to  Subgraph  $G_1, G_2$(in $G$, $G_1$ and $G_2$ are connected through a  set of edges, say, $R_1$) and finds Isomorphism to corresponding graph $H_1 , H_2$(Local Isomorphism), then merge those Isomorphism to check whether $G\simeq H$ (Global isomorphism).

Does there exist such algorithm in Graph Isomorphism Literature ?

EDIT:

I apologize for a vague description, I should be more specific, but it is really hard to specify at the moment. For the time being, note that I do not mean a splitting based on vertex classification entirely or something like that.  An algorithm that is based on  $K$  Dimensional  Weisfeiler-lehman(depth $K$  neighborhoods) entirely,  is not what I meant, that is for sure**.  if $K=1$, then it can not handle  regular graph. You can "construct" graph that makes $K$  Dimensional  Weisfeiler-lehman ineffective, for example Cai-Furer-Immerman pair. Certainly  I do not mean that.Note that NAUTY  uses  1 Dimensional  Weisfeiler-Lehman method.

This question is the closest I got to mine, but it does not answer  my query.


texts: direct connection between gradient descent and follow the (perturbed) leader algorithm or weighted majority?

texts:
Is there a direct conversion between gradient descent ([1], Alg 1 )
and any of the following algorithms?

1) Weighted Majority: http://onlineprediction.net/?n=Main.WeightedMajorityAlgorithm

2) Follow the Leader:  http://people.cs.uchicago.edu/~kalai/papers/onlineopt/onlineopt.pdf
I keep seeing these together, but I don't see the direct conversion.

[1] http://moodle.technion.ac.il/pluginfile.php/195968/mod_resource/content/0/OCP_ICML03.pdf


texts: How many distinct colors are needed to lower-bound the choosability of a graph?

texts:
A graph is $k$-choosable (also known as $k$-list-colorable) if, for every function $f$ that maps vertices to sets of $k$ colors, there is a color assignment $c$ such that, for all vertices $v$, $c(v)\in f(v)$, and such that, for all edges $vw$, $c(v)\ne c(w)$.

Now suppose that a graph $G$ is not $k$-choosable. That is, there exists a function $f$ from vertices to $k$-tuples of colors that does not have a valid color assignment $c$. What I want to know is, how few colors in total are needed? How small can $\cup_{v\in G}f(v)$ be? Is there a number $N(k)$ (independent of $G$) such that we can be guaranteed to find an uncolorable $f$ that only uses $N(k)$ distinct colors?

The relevance to CS is that, if $N(k)$ exists, we can test $k$-choosability for constant $k$ in singly-exponential time (just try all $\binom{N(k)}{k}^n$ choices of $f$, and for each one check that it can be colored in time $k^n n^{O(1)}$) whereas otherwise something more quickly growing like $n^{kn}$ might be required.


texts: Complexity of a weighted subset selection problem.

texts:
I'm currently thinking about a problem I'd like to manage in one of my applications.

There is a set of objects $\{A, B, C, D, \ldots\}$. Every object has the same attributes with different values. For example, $A$'s attribute $a_1$ has the value $A(a_1)$, $B$'s attribute $a_1$ has the value $B(a_1)$ and so on.

Now I want to pass a number $x$ which represents the maximum number of objects to selected from the set. For example, $x = 2$ would mean that any combination of at most 2 objects are allowed to be selected from the set.

Given this table of attributes and the number $x$, the algorithm should return at most $x$ objects which, in summation, own the largest attributes. Only the greater one counts.

For example: $A,B,C$ with attributes $a_1,a_2,a_3$ and $x = 2$:

$\begin{array}{|c|c|c|c|}
   & a_1 &  a_2 &  a_3\\\hline
 A &   1 & -100 &   -1\\\hline
 B &  -2 &    2 & -200\\\hline
 C & -20 &  -10 &   10\\\hline
\end{array}$

The algorithm should return $A$ and $B$ since $A(a_1) + A(a_2) + B(a_3)$ serve the maximum when at most 2 objects from the set are allowed to be selected.

If I'd use brute-force, I simply would test all $\binom{n}{x}$ combinations and calculate the overall sum.

Is there a faster way to do this?

Thanks!


texts: Is it possible to construct a graph with 5 to 10 vertices for which the Dinic-Algorithm finds exactly |V|-1 blocking flows, and if so what does it look like?


texts:
Why do conferences in TCS take so long to send reviewer's comments and to publish the list of accepted papers?

I guess that sending reviewers comments some days after notification makes some sense, since it may avoid complaints from angry authors of rejected papers. I mean after receiving the news that their papers was rejected some authors may feel compelled to complain with the chairs  in case some review is considered unfair or so. I believe that the probability of such complaints decreases after some days because the authors have some time to accept the bad news.

The reasons why lists of accepted papers are not published right away is less obvious to me. The only reason I can see is if there are some papers that have been accepted conditionally. But does this occur in top conferences like SODA, STOC, FOCS, ICALP etc?

An example is SODA 2018. Notification was 29/September. Reviewers comments were sent on 06/October. Nevertheless, today, 09 October the list of accepted papers is still not public.


texts: Are biases necessary to make neural networks universal approximators when using sigmoid activations?

texts:
In a neural network, a bias is a constant term that is added to the weighted input in a neuron/unit:
output = activation_function( input1*weight1 + ... + inputn*weightn + bias)

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

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


texts: Computing topological sort while keeping edges "short"

texts:
Motivation: I want to compute a topological sort order in which the connected vertices are close to each other.

Problem statement: Given a DAG $G(V,E)$ with $n$ vertices, compute a topological sort with minimum maximum edge length (MEL), where MEL in a valid topological sort order $v_1, v_2 \ldots v_n$ is defined as $\max_{(v_i, v_j) \in E} \ |j - i|$.


texts: How can one ACTUALLY minimize a regular expression?

texts:
Minimizing regular expressions (in terms of number of symbols) is PSPACE-complete

(for example as discussed here: minimizing size of regular expression).

But how do you actually do that (i.e., what does an algorithm

for minimizing regular expressions in PSPACE look like)?

There are many results showing that it's hard in different contexts (such as when

an equivalent DFA is available), but I found none showing how it's actually done.

Probably it's so easy that I'm the only one not getting it. :-)


texts: Triangle counting using approximate matrix multiplication -- suspicious paper

texts:
This paper [1] claims that for matrices with entries in $O(1)$, one can approximately multiply them in time $O(n^2 \log 1/\delta)$ to within error delta in the Frobenius norm (Theorem 1 in that paper). This specifically allows us to take square of an adjacency matrix exactly in $O(n^2 \log n)$ by taking polynomially small $\delta$ and using that the entries have to be integers (specifically, set $\delta$ so as to make all entries be within 0.1 of the correct answer, then round).
This would, for example, allow me to count triangles in this time complexity (square adjacency matrix then add all off-diagonal entries at positions where the adjacency list has ones). That seems very suspicious. The paper has been published in ECCC, which suggests it might be correct. The paper only has one citation which for such major result also seems little suspicious.
Does anyone know more about this? Is there a mistake in the paper? Is there a mistake in my reasoning (I don't think there is)? Or does it actually give a significant speedup for triangle counting (unlikely)?
[1] https://arxiv.org/abs/1408.4230v2


texts: Average-case tautologies/contradictions, beyond the random k-CNF model

texts:
It is well known that random $ k $-CNF formulas over $ n $ variables with $ cn $ clauses are unsatisfiable (i.e. they are contradictions) with high probability, for sufficiently large constant $ c $. Thus, random $ k $-CNF formulas (for $ c $ large enough) constitute a natural distribution over unsatisfiable Boolean formulas (or dually, over tautologies, i.e. negations of contradictions). This distribution has been studied extensively.

My question is the following: are there any other established distributions over propositional tautologies or contradictions, that can be considered as capturing the "average-case" of tautologies or unsatisfiable formulas? Have these distributions been intensively studied?


texts: Existing benchmarks for scheduling problems?

texts: Which benchmarks exist to evaluate the performance of algorithms for Job-Shop or Flow-shop scheduling problems?


texts: Applications of algebraic geometry in type theory/programming language theory

texts:
Lately, I have become interested in algebraic geometry and have started reading on it. I still know very little about this field, but I do want to know if it has any connection with my main field, type theory and programming languages.

I know that algebraic topology has a lot of applications in type theory (homotopy type theory, and many more), but what about algebraic geometry, besides that both type theory/PL theory and AG are good motivators of category theory?


texts: How fast is an equivalent 2-tape TM compared to a $O(n^2)$ 1-tape TM?

texts:
In $O(n^2)$ steps, a 1-tape TM can simulate a 2-tape TM that runs for $O(n)$ steps.
How fast is an equivalent 2-tape TM known to run compared to a $O(n^2)$ time, 1-tape TM?
"Open question" is a fine answer.
Edit: removed the word "simulate" and replace with question about equivalent TMs for clarity, add below facts.
Here are some (uninteresting) related problems I do know bounds on:

$DTIME_{1-tape}(O(n)){\subseteq}DTIME_{2-tape}(O(n))$. It's easy to make an equivalent 2-tape TM by ignoring one tape.
There is a a $O(n)$ time 1-tape TM (recognizing $\{1^n\}$) that takes $O(n)$ time for any equivalent 2-tape TM to run.
$DTIME_{2-tape}(O(n)){\subseteq}DTIME_{1-tape}(O(n^2))$. This is the well-known method mentioned above, to simulate a 2-tape TM on a 1-tape TM.
$DTIME_{1-tape}(O(n^2 logn)){\not\subseteq}DTIME_{2-tape}(O(n))$. Suppose every $O(n^2logn)$ time 1-tape TM ran in $O(n)$ time for some 2-tape TM. Then we would have $DTIME_{1-tape}(O(n^2logn)){\subseteq}DTIME_{2-tape}(O(n)){\subseteq}DTIME_{1-tape}(O(n^2))$ This would contradict known time hierarchy bounds for 1-tape TMs.


texts:
If I take the book Practical Foundations for Programming Languages by Robert Harper, the following definition is given for subtyping:

  A subtype relation is a pre-order on types that validates the subsumption principle: if $\tau'$ is a subtype of $\tau$, then a value of type $\tau'$ may be provided when a value of type $\tau$ is required.

I was wondering whether we can say that a reference on $T$, denoted by $\text{Ref }T$ is a subtype of $T$. If not, why?


texts: expected number of sets generated by greedy set cover ?

texts: I see most of the analysis for the greedy set cover analyses the approximation ratio. However, assume that each element in $T$ belong with a constant probability to one of the sets of $S$ (where $S = \{S_1, ...., S_k\}$). The question is then what is the expected number of sets generated by the greedy set cover in this case ?


texts:
I have been trying to show the following language is undecidable.

$L = \{ (\langle G \rangle , n ): G$ is a context-free grammar with an ambiguous string of length $\le n \}$.

I think it is undecidable because if $G$ doesn't have an ambiguous string, it seems like one would have to check parse trees of arbitrary heights to verify they don't yield $s$.

Or, is there some lower bound on the height of a parse tree for a given string $s$, that is any derivation with more than some number of steps cannot yield $s$?  It seems like the presence of rules $S \to \varepsilon$, where $\varepsilon$ is the empty string, would ensure that there would exist parse trees of arbitrary height, in general.


texts: Higher-rank polymorphism over unboxed types

texts:
I have a language in which types are unboxed by default, with type inference based on Hindley–Milner. I’d like to add higher-rank polymorphism, mainly for working with existential types.

I think I understand how to check these types, but I’m not sure what to do when compiling. Currently, I compile polymorphic definitions by generating specialisations, much like C++ templates, so that they can work with unboxed values. E.g., given a definition of f<T>, if the program invokes only f<Int32> and f<Char>, then only those specialisations appear in the compiled program. (I’m assuming whole-program compilation for now.)

But when passing a polymorphic function as an argument, I don’t see how I can generate the right specialisation statically, because the function could be selected at runtime. Do I have no choice but to use a boxed representation? Or is there a way around the issue?

My first thought was to somehow encode rank-n polymorphism as rank 1, but I don’t believe it’s possible in general because a formula in constructive logic doesn’t necessarily have a prenex normal form.


texts: Are there any topics in theoretical CS that are more about pure math?

texts:
I am a graduate student in theoretical computer science, and in particular, approximation algorithms. I find now that I am more interested in pure math (I can say this because I seem to have enjoyed math courses more than the CS courses). I would like to ask if there are areas in theoretical computer science which are pretty much pure math (to be more precise, an area that is of interest in pure math on it's own without considering the applications to CS), or if I need to consider a major switch. I am already two and a half years into the program, so I am not sure if a switch would be a good idea at this point.

The only such thing I could find was graph minor theory, from browsing acceptance lists of top conferences. But that doesn't count as an 'area' for me that I can just focus on.


texts: Average-case analogue of Small-bias Spaces

texts:
Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias
$$| \mathbb{E}_{x \in S} [ (-1)^{<x,\alpha>} ] | \leq \epsilon$$
is small. Distributions over such subsets $\epsilon$-fool all linear tests, so if we can make $|S|$ as small as possible, we have a good deranomization primitive.

Is an average case analogue of such a construction studied anywhere, and is it useful? More precisely, suppose we take a subset $S \subset \{0,1\}^n$ such that
$$\mathbb{E}_{\alpha}| \mathbb{E}_{x \in S} [ (-1)^{<x,\alpha>} ] | \leq \epsilon$$
This is, of course, weaker than $\epsilon$-fooling all linear tests. My question is: is there a natural approach to constructing such a set $S$ of small size?

A method used to construct $\epsilon$-bias sets is to interpret it as the vectors of the parity-check matrix of an $\epsilon$-balanced linear code, and so the aim becomes to design such a code with as high rate as possible. Would such an approach work for the average-case too? I am unclear on the correspondence though.


texts:
I have a graph $G=(V,E)$, with positive weights $w_e, e\in E$ on the edges, and I would like to randomly perturb the weights of the edges so that for each pair of distinct vertices $(u,v)$ such that there is a path from $u$ to $v$, there is, after perturbation, a unique shortest path from $u$ to $v$, and this shortest path is one of the "original" shortest paths, that is, one of the shortest paths before the perturbation. It seems to me that the perturbation can only be additive and at most equal to the minimum difference between two edge weights divided by the maximum number of vertices in a shortest paths between pair of vertices in $G$ (let this number be $\Delta$). That is, the perturbation that I add to the edge $e\in E$ should be some
$$ \varepsilon_e \in\left[0, \frac{\min_{\ell,r\in E}|w_\ell-w_r|}{\Delta}\right]
$$
and distributed according to some distribution (is uniform sufficient?) on the interval.

Possibly, I would also like the "perturbed" shortest path to be chosen uniformly at random from the set of original shortest paths. Is this possible?
Any reference or hint is appreciated.
Thanks.


texts: Further question on hardness of node partitioning under shortest path constraint

texts:
This question first appeared at Hardness of node partitioning under shortest path constraint and I restate it here

  Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \in \mathbb{Z}$ (integer and negative weight is possible). A label $l(i)$ is associated with each node $i \in V$. How to assign $k$ (or less) distinctive values to $l(i)$ such that
  $$l(j) \leq l(i) + w(i,j),\quad \forall (i,j) \in E ?$$
  Notice that when $k=|V|$, this problem is easily solvable by Shortest path algorithm (Bellman-Ford). But what's the hardness is this problem for $k < |V|$?

@Tsuyoshi has proved this problem to be NP-complete in the original post. Although the reduction is from a weakly NP-complete problem "equal subset sum", the problem listed above seems to be more complicated. So my further question is whether this problem is strongly or weakly NP-complete?


texts: Is induced subgraph isomorphism easy on an infinite subclass?

texts:
Is there a sequence of undirected graphs $\{C_n\}_{n\in \mathbb N}$, where each $C_n$ has exactly $n$ vertices and the problem

  Given $n$ and a graph $G$, is $C_n$ an induced subgraph of $G$?

is known to be in class $\mathsf{P}$? (For example, when $C_n=K_n$, this is the NP-complete clique problem.)


texts: Given a graph, decide if its edge connectivity is at least n/2 or not

texts:
Chapter 1 of the book The Probabilistic Method, by Alon and Spencer mentions the following problem:

Given a graph $G$, decide if its edge connectivity is at least $n/2$ or not.

The author mentions the existence of a $O(n^3)$ algorithm by Matula and improves it to $O(n^{8/3}\log n)$.

My question is, what's the best known running time for this problem?

Let me describe the improved algorithm.

First, decide if $G$ has its minimum degree at least $n/2$ or not. If not, then the edge connectivity is clearly less than $n/2$.

Next, if that is not the case, then compute a dominating set $U$ of $G$ of size $O(\log n)$. This can be done in time $O(n^2)$, by an algorithm described in the previous section of the book.

Next, it uses the following not very difficult to prove fact:

If the minimum degree is $\delta$, then for any edge cut of size at most $\delta$ that divides $V$ into $V_1$ and $V_2$, any dominating set of $G$ must have its vertices in both $V_1$ and $V_2$.

Now consider the dominating set $U = \{u_1, \ldots , u_k\}$. Since $G$ has minimum degree $n/2$, any edge cut of size less than $n/2$ must also separate $U$. Thus for each $i\in \{2, k\}$, we find the size of the smallest edge cut that separates $u_1$ and $u_i$. Each of these things can be done in time $O(n^{8/3})$ using a max-flow algorithm. Thus total time taken is $O(n^{8/3}\log n)$.


texts: Efficient all pair bottleneck computation for a tree

texts:
Consider a weighted tree $T = (V,E)$. The bottleneck weight for a pair of vertices $v_1,v_2 \in V$ is the highest weight of the edges on the unique path from $v_1$ to $v_2$ (if $v_1 = v_2$ it is 0). Clearly, using a simple graph traversal from a given node we can find the bottleneck weight from that node to all other nodes in $\mathcal O(|V|)$ time, so we can find all $V^2$ bottleneck weights in $\mathcal O(|V|^2)$ time.

I am interested in the situation where $V$ is large, and we are not interested in finding bottlenecks for all pairs $(v_1,v_2)$, but nonetheless for an (also large) number of pairs $Q$ (the letter $Q$ stands for queries).

I am wondering whether it is possible to do some preprocessing in less than $\mathcal O(|V|^2)$ time -- in particular, in $\mathcal O(|V|\log|V|)$ -- so that we produce some search mechanism, which will then produce a bottleneck weight for $(v_1,v_2)$ in $\mathcal O(\log |V|)$ time. Then we can produce the answer to all queries in $\mathcal O(|V|\log |V| + Q\log|V|)$.

Note that there are $\mathcal O(|V|)$ edges, and thus also that many possible answers to a query. Hence, a balanced decision tree whose leaves are the edge weights, which takes pairs of vertices and decides the highest weight edge between them -- if such a tree exists -- would do the job.

One attempt to build the tree was as follows: recursively split the original tree by removing the highest weight edge. Assign the nodes of the tree indices so that both resulting trees have indices in a contiguous range. Then make a node in the decision tree, which when given two vertices decides whether they lie in the same of the two ranges; if not, this search tree node represents the highest weight edge between the vertices; if so, continue in either of the children of the search tree node.

Unfortunately, this construction fails as the decision tree need not be balanced. Consider, for example, the tree which is just a simple path with ever decreasing weights along the path. Balancing the tree does not seem to be an option, as the decision procedures created by the balancing operations grow too fast (traversing the tree would take too long).

Any suggestions or insights are welcome.


texts: Partitioning the edges of a complete graph into smaller complete graphs

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

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


texts:
I have a simple algorithm which I believe it is O(N) in worst case. But I cannot prove it.

Here's the problem:
Given a sequence of numbers A[1], A[1], A[2], ... A[N].
The algorithm computes the array L, in which

L[i] = min{k | A[j] >= A[i] for all k <= j <= i}

In other words, L[i] is the left most index so that all the numbers from position L[i] to i is not less than A[i].

The algorithm is as follows.

for i = 1 to N
   k = i
   while (k >= 0 AND A[k] >= A[i])
     L[i] = k
     k = L[k] - 1

How to prove this algorithm is O(N), or is there some input that makes it not O(N)?


texts:
Is there a simple algorithm to calculate the maximal bisimulation relation of a graph/two graphs?
With simple i mean very easy implementation, complexity is not that important for us in this stage.


texts: Multiple solutions to a Min-Cost Flow problem

texts:
Minimum Cost Maximum Flow algorithms have been known to provide an optimal flow routing for network flow problems in satisfactory runtime. Some of the algorithms for solving a min-cost max-flow problems that I'm aware of include :

Cycle cancelling (reff)
Successive shortest path
Relaxation (reff)
Cost scaling (reff)

The above algorithms differ in their approach to solving the problem with some maintaining feasibility and attempting to achieve optimality (Cycle canceling, Cost scaling) whilst iterating over the flow network and some maintain reduced cost optimality at every step and try to achieve feasibility (Successive Shortest Path, Relaxation).
My question is whether any of the above algorithms or one that I haven't listed, can be altered in order to provide a listing of the k-best flow routings that minimise the overall cost instead of the single optimal routing.


texts: Minimum non-zero variable in the optimal solution of linear programming

texts:
Suppose we have a linear programming about the vertex packing of a hypergraph G=(V,E), with size $n = \sum_{e \in E}|e|$. We introduce a variable $x_v$ for each vertex $v \in V$.

$$\max \sum_{v} x_v \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
$$s.t. \sum_{v: v \in e} x_v \le 1, \ \forall e \in E$$
$$\ x_v \ge 0, \ \forall v \in V$$

Is it always possible to find an optimal solution such that the minimum non-zero variable has value at least $c \cdot 1/n$ for some constant $c$? (If representing the contraints as $\mathbf{Ax} \le \mathbf{1}$, there are $n$ entries as $1$ in $\mathbf{A}$ with remaining entries as $0$.)


texts: Separation between existence of crypto primitives

texts:
I understand how one can build a crypto primitive from another crypto primitive to some extent. The constructions I know build the later primitive using the former primitive as a black box. My question is how can we show this is not possible? For example, AFAIU, the existence collision resistant hash functions does not follow from the existence of one-way functions (at least not in a black box manner), but how is this formally stated?

The motivation is to understand what it means to show that DDH against subexponential ($2^{n^\epsilon}$) size circuits does not follow from DDH against polynomial size circuits. Note that the situation is more complicated here because DDH is a hardness assumption about a particular function, so it is not clear what would it meant to relativize it. I would also be interested in references if this is already known.


texts: #P-complete problem whose decision version is in P

texts:
1) Is it possible to have a parsimonious reduction from a #P-complete problem #A to a counting problem #B when (the decision version) A is NP-complete and the B is in P?

For example, can there be a parsimonious reduction from #SAT to #B, when B is in P?

2) If B is in P, what are the different possibilities for the complexity of #B?


texts: Noisy Parity (LWE) lower bounds/hardness results

texts:
Some background:

I'm interested in finding "lesser-known" lower bounds (or hardness results) for the Learning with Errors (LWE) problem, and generalizations thereof like Learning with Errors over Rings. For specific definitions, etc., here is a nice survey by Regev: http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf

The standard type of (R)LWE-style assumption is via (perhaps, quantum) reduction to the Shortest Vector Problem on (perhaps, ideal) lattices. The usual formulation of SVP is known to be NP-hard, and it's BELIEVED to be hard to approximate to small polynomial factors. (Related: It's hard to approximate CVP to within /almost-polynomial/ factors: http://dl.acm.org/citation.cfm?id=1005180.1005182 ) I've also heard it mentioned that (in terms of quantum algorithms) approximating certain lattice problems (like SVP) to small polynomial approximation factors is related to the non-Abelian hidden subgroup problem (which is believed to be hard for its own reasons), though I've never seen an explicit, formal source for this.

I'm more interested, however, in hardness results (of any type) that come as a result of the Noisy Parity problem from Learning Theory. These could be complexity class hardness results, concrete algorithmic lower bounds, sample complexity bounds, or even proof size lower bounds (e.g. Resolution). It is known (perhaps, obvious) that LWE can be viewed as a generalization of the Noisy Parity/Learning Parity with Noise (LPN) problem, which (from Googling) appears to have been used in hardness reductions in areas like coding theory and PAC learning.

From looking around myself, I've only found (mildly subexponential) UPPER BOUNDS on the LPN problem, e.g. http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf

Question:

I know LPN is BELIEVED HARD in the learning community. My question is: Why?

Is it because everyone tried really hard, but no one's found a good algorithm yet? Are there known lower bounds of the italicized variety above (or others I left out)?

If the answer is very clear-cut, a succinct summary of what's known and/or references to surveys/lecture notes would be great.

If much is unknown, the more "state-of-the-art" papers, the better. :) (Thanks ahead of time!)


texts: Edge-partitioning cubic graphs into claws and paths

texts:
Again an edge-partitioning problem whose complexity I'm curious about, motivated by a previous question of mine.

Input: a cubic graph $G=(V,E)$

Question: is there a partition of $E$ into $E_1, E_2, \ldots, E_s$, such that the subgraph induced by each $E_i$ is either a claw (i.e. $K_{1,3}$, often called a star) or a $3$-path (i.e. $P_4$)?

I think I saw a paper one day where this problem was proven to be NP-complete, but I cannot find it anymore, and I don't remember whether that result applied to cubic graphs. On a related matter, I'm aware that edge-partitioning a bipartite graph into claws is NP-complete (see Dyer and Frieze). Does anyone have a reference for the problem I describe, or something related (i.e. the same problem on another graph class, that I could then try to reduce to cubic graphs)?


texts: Choosing one number from each set so that the sum of squares of each distinct number counts is minimized

texts:
Problem is as follows:
We are given $K$ subsets of $\{1,2,...,n\}$. We need to pick one number from each of these subsets such that $\sum_{i=1}^n p_i^2$ is minimized where $p_i$ is the number of times $i$ is repeated among picked numbers. Is there an efficient algorithm to do this?


texts: Confusions about the technique for verifying implementations of linearizable objects in [Herlihy and Wing, 1990]

texts:
In Section 4.3.2 entitled "Proof Method" of

Herlihy and Wing, "Linearizability: A Correctness Condition for Concurrent Objects", 1990

the authors describe the technique for
verifying implementations of linearizable objects as follows:

  Assume that the implementation of $r$ is correct,
  hence $\text{H} \mid {\small \text{REP}}$ is linearizable
  for all $\text{H}$ in the implementation.
  Our verification technique focuses on showing the following property
  (denoted $\mathcal{P}$ for later reference, by myself):
  $$\text{For all } r \in \text{Lin}(\text{H}\mid{\small\text{REP}}), \text{I}(r)
\text{ holds and } \text{A}(r) \subseteq
\text{Lin}(\text{H}\mid{\small\text{ABS}}).$$
  This condition implies that $\text{Lin}(\text{H} \mid {\small \text{ABS}})$
  is nonempty, hence that $\text{H} \mid {\small \text{ABS}}$ is linearizable.

I don't understand:

  Why is it sufficient to show that $\text{A}(r) \subseteq
\text{Lin}(\text{H}\mid{\small\text{ABS}})$ (besides the "invariant" $\text{I}(r)$ property)
  holds for the verification purpose?

Specifically, to show the property $\mathcal{P}$,
are we showing that there exists an $\text{I}(r)$ and an $\text{A}(r)$
such that $\mathcal{P}$ holds?
If so, why cannot we just set $\text{I}(r) = \top$ and $\text{A}(I) = \emptyset$
which trivially satisfy $\mathcal{P}$?
If not, what is the formal definition of "verification" here?

About examples in this paper:

Section 4.3.3: in the queue example,
$\text{I}(r)$ and $\text{A}(I)$ are far from trivial.
What are the specifications that prevent us from choosing
$\text{A}(I) = \emptyset$ in this example?
Section 4.2: to motivate their definitions of
$\text{I}(r)$ and $\text{A}(r)$,
the authors also use the queue example.
At the top of page 477, it reads:

  Let $r$ be the rep value after this history.
  Because $\beta$'s Enq operation has returned,
  $\text{A}(r)$ must reflect $\beta$'s Enq.
  Because $\alpha$'s Enq operation is still in progress,
  $\text{A}(r)$ may or may not reflect $\alpha$'s Enq,
  depending on how $\text{A}$ is defined.

(Note that I have used $\alpha, \beta$ instead of
$A, B$ to denote the processes, to avoid symbol abuses.)
According to this argument,
I suppose that there are some constraints on the definition of $\text{A}$.
But what are they?


texts: A random walk that moves to less-visited nodes

texts:
Consider a random walk on an undirected graph that keeps track of how many times it has visited every node. At each step, it moves to the node among its neighbors which has been visited the least number of times. If there are several such nodes, it chooses one at random. My question is: what is the (worst-case) cover time of this random walk as a function of the number of nodes $n$?

The answer should be at least $\Omega(n^2)$. Consider a star graph where each node has a self-loop. In this graph, the walk starting at the center will visit the leafs in some order, without loss of generality $1,2,3, \ldots, n-1$ (relabel the vertices if necessary). The time spent at leaf $i$ will be at least $i-1$ because the center will have been visited $i-1$ times before leaf $i$.  Thus the total cover time will scale as $\Omega (n^2)$. If we want an example without self-loops, we can consider a star-like graph where each leaf is replaced by a path of length $2$.

Alternatively, what is the largest hitting time between any two vertices for this random walk? This feels like asking a very similar question.

For the usual random walk which jumps to each out-neighbor, the largest hitting time will be $O(n^3)$ but the standard proofs rely on resistances, which are not applicable here due to lack of reversibility.


texts: Planarity of planar finite automata intersection

texts: It was shown that any regular language can be specified by planar $\varepsilon$-free nondeterministic finite automaton (Bezáková, Ivona, and Martin Pál. "Planar finite automata."). Is it possible to provide a planar automata intersection algorithm which instantly preserves planarity? Namely, suppose I have two planar automata $M_1$ and $M_2$. Is there exist an algorithm to construct an intersection of $M_1$ and $M_2$ which acts better (in terms of complexity or in terms of the size of the final automaton) than planarization (using results of Ivona and Martin) after the classical intersection? Also, is it possible to define a respective product of automata (and respective product of adjacency matrices)?


texts: What is a totally ordered sort of sets of a partial order called?

texts:
Given a DAG, which can represent a partial order and has at least one topological sort.

For example the graph

  >B
 /  \
A    >D
 \  /
  >C

has two topological sorts "ABCD" and "ACBD".

My question is the following:
Is there a name for the following total order sort of sets:

S:  ( {A} , {B,C} , {D} )

The inductive definition is similar to constructing a topological sort:

Put the all the graph minima (nodes with no input edges) in set #i S: ( {A} )
Remove the graph minima from the graph.  G:= G \ {A}
repeat step 1. with i := i+1 as long as the graph is non-empty

I find this in several computer science domains. For example method selection in CLOS (Common Lisp), a parallel scheduler of a DAG where nodes are tasks and edges dependencies, the list of all enabled sets in dataflow or petri-net model executions, etc.  I haven't found a single nomenclature or even a reference for it though.  It sounds simple and pervasive enough to merit one.


texts: Genetic Algorithm convergence test functions

texts:
I was working on parallel implementation of Genetic Algorithm with MapReduce. I have found that in many papers authors are referencing OneMAX as problem they used to test scalability and convergence of their algorithm implementations.

I would like to know more about why this problem is good for testing, and if you could recommend any other exotic and nice fitness functions I could use in tests.

Kind Regards,
ZeKoU