texts: Will core decomposition get a maximal clique?

texts:
I have read David Eppstein's paper about maximal clique enumeration by using degeneracy order. It has mentioned the core decomposition, which is removing the vertex with the smallest degree iteratively.

And I pick up with a theorem:
If we remove the vertex with the smallest degree iteratively until the smallest degree is |S|-1, where S is the remaining graph, is S a maximal clique?

example graph:

In this graph, we will delete vertex a whose degree is the smallest one ( deg(a)=2 ), and then delete vertex f. And we will get the 4-maximal clique {b,c,d,e}.

I cannot prove this theorem but I also can't find a counterexample. Is there anyone can help me figure out this theorem right or wrong?

PS:

Clique is a subgraph whose every vertex is adjacent to each other. And maximal clique is a clique that cannot be contained by another clique, it means the maximal one cannot be extended.

I can prove the remaining graph that above algorithm produced is not a maximum clique which is the largest one in the graph, but I can't prove this graph whether is a maximal clique.

Also notice that when the vertex v is removed from the graph, all it's neighbors' degree will decrease one.


texts: Deterministic Parallel algorithm for perfect matching in general graphs?

texts:
In complexity class $\mathsf{P}$, there are some problems conjectured NOT to be in the class $\mathsf{NC}$, i.e. problems with deterministic parallel algorithms. Maximum Flow problem is one example. And there are problems BELIEVED to be in $\mathsf{NC}$, but a proof is not found yet.

Perfect Matching problem is one of the most fundamental problem raised in graph theory: given a graph $G$, we have to find a perfect matching for $G$. As I could found on the internet, despite of the beautiful polynomial time Blossom algorithm by Edmonds, and a RANDOMIZED parallel algorithm by Karp, Upfal and Wigderson in 1986, only a few subclasses of graphs are known to have $\mathsf{NC}$ algorithms.

In Jan. 2005 there's a post in the blog Computational Complexity that claims it remains open whether Perfect Matching is in $\mathsf{NC}$. My question is:

  Is there any progress since then, beyond the randomized $\mathsf{NC}$ algorithm?

To clarify my interest, any algorithm which deals with GENERAL graphs are nice. Although algorithms for subclasses of graphs are OK too, that may be not on my attentions. Thank you all!

EDIT at 12/27:

Thank you for all your help, I try to summarize all the results in one figure:

The lowest known classes contain the following problems:

Matching in general graphs: $\mathsf{RNC}$ [KUW86], $\mathsf{RNC}^2$ [CRS93]
Matching in bipartite planar/constant genus graphs: $\mathsf{UL}$/$\mathsf{SPL}$ [DKT10]/[DKTV10]
Matching when the total number is polynomial: $\mathsf{SPL}$ [H09]
Lex-first maximal matching: $\mathsf{CC}$ [MS89]

Furthermore, under plausible complexity assumption: $\mathsf{SPACE[n]}$ requires exponential circuits, Matching in general graphs is in $\mathsf{SPL}$ [ARZ98].


texts: How to construct a special data structure that allows for "fast" subset operation?

texts:
If I have a set S = {1,2,3,4,5} that represents a universe and the following subsets of S:

U1 = {1,2}

U2 = {3,4,5}

C1 = {3,5}

C2 = {2}

The above sets are guaranteed to be subsets of S, however they may not be subsets of each other. To check if C1 is subset of U2 I need to iterate through both sets and check if all elements of C1 are in U2.  In this case 3 and 5 are elements of U2 thus C1 is a subset of U2.

But this operation is O(n) at best if you keep everything sorted.  I'm wondering, is it possible to select the elements of S wisely or construct a data structure in such a way to perform fast (like O(1)) subset check operations ?

If this means I need to look into parallel algorithms I am open to that as well.


texts: Is this generalization of context free grammars known and strict?

texts:
Let $\Sigma$ be an finite alphabet and $(N, \circ)$ a semigroup. The semigroup operation on $N$ can be extended to $\mathscr{P}(N)$: $N_1 \circ N_2 := \{ \; n_1 \circ n_2 \; | \; n_1 \in N_1, \; n_2 \in N_2 \; \}$ for $N_1, N_2 \subseteq N$.

Want to define:

A finite set $\mathcal{S} := \{ S_1, S_2, ..., S_k \}$ with $S_i \subseteq N$ is called a finite system of $N$. For $w \in \{1, .., k\}^+$ we have the homomorphism $\mathcal{S}(w) := S_{w_1} \; \circ \; ... \; \circ \; S_{w_{|w|}}$.
A set $M \subseteq \mathscr{P}(N)$ has a finite generating set, iff there is a finite system $\mathcal{S}$ of $N$ so that $\forall m \in M: \exists w_1, ..., w_j \in \{1,...,|S|\}^+: m = \mathcal{S}(w_1) \; \cup \; ... \; \cup \; \mathcal{S}(w_j)$

An equivalent definition is:

Consider the semiring $R := (\mathscr{P}(N), \cup, \circ)$.
A set $M \subseteq R$ has a finite generating set if there is a finite set $S \subseteq R$ so that every subsemiring of $R$ that contains $S$ also contains $M$.

Applied to formal languages:

Let $w^{-1}L := \{ \; v \; | \; wv \in L \; \}$ for a language $L \subseteq \Sigma^*$ and $w \in \Sigma^*$.
A language $L \subseteq \Sigma^*$ has a finite generating set, iff
$M_L := \{ \; w^{-1}L \; | \; w \in \Sigma^* \; \}$ has a finite generating set.

Clearly, all context free languages have a finite generating set. There are also languages that don't have a finite generating set, e.g. $L_1 := \{ \; w\#v \; | \; v, w \in \Sigma^*, \; v \not\in w^* \; \} $. This can be shown easily by using that $M_1 := \{ \; \mathbb{N}_0 \setminus k \mathbb{N} \; | \; k \in \mathbb{N} \; \}$ does not have a finite generating set.

For $\Sigma = \{ a, b \}$ and $L \subseteq \Sigma^*$ we have the identity: $w^{-1}L = \{ a \} \circ (wa)^{-1}L \; \cup \; \{ b \} \circ (wb)^{-1}L$.

As a fun fact: if we limit $j$ from the definition above to $1$ and consider infinite sets $M \subseteq \mathscr{P}(\Sigma^*)$ with $\forall m \in M: \varepsilon \in m$ that have a finite generating set, we can always find $m_1, m_2 \in M, \; m_1 \neq m_2$ so that $m_1 \subseteq m_2$. This is because the subsequence ordering on $\{ 1,...,|\mathcal{S}| \}^*$ is a well quasi ordering.

Does anybody know

whether this generalization of context free languages has been explored?
an example of a language that is not context free but has a finite generating set?
better terminology?

It seems obvious that languages with finite generating sets are more powerful than context free grammars (the elements of a finite system don't even have to be decidable), but I wasn't able to construct a counter example.

However, if $M_L$ itself is finite, $L$ is even regular and the sets of $M_L$ are decidable!

I have posted this question on math.stackexchange without any response.


texts: Gap-Hamming with different "threshold" (i.e., not $n/2$)

texts:
Following a previous question, I'm trying to get a better understanding of the parameters at play in $\textsf{Gap-Hamming}$. In the "standard" setting, we have
$x,y\in\{0,1\}^n$ and the partial function
$$
\textsf{GHD}_{n,n/2,\sqrt{n}} = \begin{cases}
0 & \text{ if }\operatorname{d}_H(x,y) \leq \frac{n}{2}-\sqrt{n}\\
1 & \text{ if }\operatorname{d}_H(x,y) \geq \frac{n}{2}+\sqrt{n}.
\end{cases}$$
This can be generalized to
$$
\textsf{GHD}_{n,t,g} = \begin{cases}
0 & \text{ if }\operatorname{d}_H(x,y) \leq t-g\\
1 & \text{ if }\operatorname{d}_H(x,y) \geq t+g.
\end{cases}$$
Lemma 4.1 to Proposition 4.4 of [CR10] allow to get a lower bound on the communication complexity of $\textsf{GHD}_{n,t,g}$ for (most) of the settings of $t,g$. Another generalization is introduced and studied in [BBM13] (Lemma 2.5), $\textsf{EGHD}_{n,k,t}$, which corresponds to $\textsf{GHD}_{n,k/2,g}$ with the additional promise that that $\lvert x\rvert = \lvert y\rvert = k/2$.

However, as far as I could see none of the above covers the "corner cases" where $t$ is itself sublinear (and say, comparable to $g$), but $\lvert x\rvert, \lvert y\rvert$ are still arbitrary. Is the behaviour of the randomized communication complexity for e.g. $\textsf{GHD}_{n,2\sqrt{n},\sqrt{n}}$ obvious?

(I suppose two reasonable conjectures would be that the CC be either $\Omega(\sqrt{n})$ or $O(1)$ in this case, the first inspired by the difficulty of distinguish a coin with bias $\varepsilon$ from one with bias $2\varepsilon$ with less than $1/\varepsilon$ samples; the second because it "looks" easy, and a completely hazy feeling.However, and most likely because I'm missing something obvious, I don't really see which holds, nor how to get a general tradeoff that would cover the whole spectrum of $t,g$.)


texts: Hardness of Approximation of Set Cover with Growing Size Bound

texts:
I'm considering the minimum set cover problem with the constraint that each set contains at most $k$ elements.
Here, $k$ depends on the size of the universe.

For example, $k$ may equal $\log n,\sqrt n$, etc., if the universe is $\{1,2,\ldots,n\}$.

In this post and this paper of Luca Trevisan, they seem to deal with constant $k$. In this paper of Uriel Feige, there is no size bound.

Though I suspect it is still $(1-o(1))\ln k$ inapproximable, any reference on this would be nice.


texts: Stochastic version of a strongly NP-Complete problem

texts:
Does a strongly NP-Complete problem remain strongly NP-Complete if the variable set on which the objective/cost function depends are made stochastic ?
The problem Tree CVRP(Capacitated Vehicle Routing Problem) is proven to be strongly NP-Complete by Hamaguchi & Katoh (1998)( http://bit.ly/VdUBDz ). If the demands are made stochastic then does the problem remain strongly NP-Complete?


texts: Why do k min-hashes, instead of one hash where we find the k minimum elements?

texts:
Traditionally if one wants to sketch streams for Jaccard similarity hashing, one finds the minimum element in each of $k$ permutation for comparison purposes, and then takes number_of_collisions / $k$ as an estimate of Jaccard similarity between target streams. (There is additional work on how to compute these k-hashes more efficiently, or use a single bit from each, etc, but let's not get into that.)

My question is why not find the $k$ minimum elements instead in a single permutation? Especially since reduces the computation cost of $k$ hashes to just $1$. Is the required size of $k$ much larger, or does the analysis break?


texts:
I was teaching the HyperLogLog estimator in class earlier this week and a student asked where the “hyper” bit came from. I know that HyperLogLog is a refinement/improvement to the LogLog estimator, so in one sense “HyperLogLog” makes sense as a way of saying “a better LogLog.” What I wasn’t sure about was whether there were any specific parts of the analysis or design that specifically would merit the term (hypergeometric functions? hypergraphs? hyperbolas?).
Beyond just meaning “better than LogLog,” is there any specific mathematical reason for calling it “HyperLogLog?”


texts: Asymmetry in converting Burrows-Wheeler transform to suffix array?

texts:
Given a suffix array of a string $w$, it's possible to construct the Burrows-Wheeler transform of $w$ by subtracting one from the indices of the suffix array (wrapping around if necessary), then outputting the characters in $w$ that appear in that position.

However, to the best of my knowledge, there doesn't seem to be an algorithm to directly construct a suffix array for $w$ given the Burrows-Wheeler transform of the string $w$. It's still possible to do so in linear time by inverting the transform to get back $w$ and then constructing the suffix array directly, but that doesn't make any use of the transformed array.

Is there a fundamental reason why the reverse direction would be "harder" than the forward direction?

Thanks!


texts: What is the minimal class of subshifts for which conjugacy is known to be undecidable?

texts:
The question of whether two finite one directional shifts are conjugates is known to be decidable.

The same question for sofic shifts is famously open.

I have seen that some works manage to prove undecidability of related problems for cellular automata. My question is what is the known undecidability landscape?

Do we know that it's undecidable if the shift corresponds to e.g., a context-free grammar? A one counter automaton? Something else?

To keep things focused, I am more interested in undecidability results that step from the underlying computational model, rather than an increased dimension.

I didn't bother writing the definitions, since I assume anyone not familiar with them will not likely be able to answer the question anyway...


texts: $NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$

texts:
Stephen Smale claims in Mathematical Problems for the Next Century that

$$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}.$$

Can someone sketch the argument or provide a reference?

Is there any similar result in the reverse direction?

$NP_{\mathbb{C}}$ (definition) and $P_{\mathbb{C}}$ (definition) are NP and P over complex numbers $\mathbb{C}$ using the Blum–Shub–Smale machine model.


texts: Testing whether letters can be scheduled to achieve a word in a regular language

texts:
I fix a regular language $L$ on an alphabet $\Sigma$, and I consider the following problem that I call letter scheduling for $L$. Informally, the input gives me $n$ letters and an interval for each letter (i.e., a minimal and maximal position), and my goal is to place each letter in its interval such that no two letters are mapped to the same position and so that the resulting $n$-letter word is in $L$. Formally:

Input: $n$ triples $(a_i, l_i, r_i)$ where $a_i \in \Sigma$ and $1 \leq l_i \leq r_i \leq n$ are integers
Output: is there a bijection $f: \{1, \ldots, n\} \to \{1, \ldots, n\}$ such that $l_i \leq f(i) \leq r_i$ for all $i$, and $a_{f^{-1}(1)} \cdots a_{f^{-1}(n)} \in L$.

Obviously this problem is in NP, by guessing a bijection $f$ and checking membership to $L$ in PTIME. My question: Is there a regular language $L$ such that the letter scheduling problem for $L$ is NP-hard?

Some initial observations:

It seems that similar problems have been studied in scheduling: we could see the problem as scheduling unit-cost tasks on a single machine while respecting starting and finishing dates. However, this latter problem is obviously in PTIME with a greedy approach, and I don't see anything in the scheduling literature for the case where tasks are labeled and we would want to achieve a word in a target regular language.
One other way to see the problem is as a special case of a bipartite maximum matching problem (between letters and positions), but again it's hard to express the constraint that we must fall in $L$.
In the specific case where $L$ is a language of the form $u^*$ for some fixed word $u$ (e.g., $(ab)^*$), then the letter scheduling problem for $L$ is in PTIME with an easy greedy algorithm: build the word from left to right, and put at each position one of the available letters which is correct relative to $L$ and has the smallest time $r_i$. (If there are no available letters which are correct, fail.) However, this does not generalize to arbitrary regular languages $L$ because for such languages we may have the choice of which kind of letter to use.
It looks like a dynamic algorithm should work, but in fact it's not so simple: it seems that you would need to memorize which set of letters that you have taken so far. Indeed, when building a word from left to right, when you have reached a position $i$, your state depends on which letters you have consumed so far. You cannot memorize the entire set because then there would be exponentially many states. But it's not so easy to "summarize" it (e.g., by how many copies of each letter were used), because to know which copies you used, it seems that you need to remember when you have consumed them (the later you have consumed them, the more letters were available). Even with a language like $(ab|ba)^*$, there may already be complicated constraints about when you should choose to take $ab$ and when you should choose to take $ba$ depending on which letters you will need later and when the letters become available.
However, as the regular language $L$ is fixed and cannot memorize so much information, I'm having a hard time finding an NP-hard problem from which I could reduce.


texts: Huffman Tree Depth, Is there any theory?

texts:
I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without drawing tree.

Specific Example is : 10-Input Symbol with Frequency 1 to 10 is 5. the above question mentioned depth is 5.


texts: Looking for papers and articles on modal substructural logics

texts: I am looking for papers and articles on modal substructural logics-- not on the semantics of linear logic modalities, but on substructural logics augmented with standard modal operators, e.g. substructural K (something like MALL with box operator, necessitation and K rules).


texts: What is known about finding heavy hitters in a sliding window?

texts:
This question is strongly related to another question I asked here a few weeks ago.

In this problem setting we have a stream of elements $s_1,s_2,...$, such that $\forall i: s_i\in \mathcal X$ for some set $\mathcal X$.

At time $t$ we get $s_t$, and required to update our data structure to be able to answer queries of the form "did $x$ ($x\in \mathcal X$) appear at least $N\epsilon$ times in the last $N$ elements in the stream ($s_{t-N+1},s_{t-N+2},\dots ,s_{t}$)?".

What is the best algorithm (memory-wise, and then runtime as a secondary objective) that answers these queries correctly w.p. 1?

Two related papers, which implement a sliding bloom filter (answering queries of the form "did $x$ appear at least once in the last $N$ elements") appeared last year, one by Naor and Yogev and the other by Dautrich and Ravishankar.

These results can be seen as a special case of the sliding heavy hitters problem for $\epsilon=\frac{1}{N}$.


texts: Public-key encryption without the assumption that $P \neq NP$

texts:
I'm not talking about the RSA, El-gamal, nor any specific encryption scheme. Rather, my question, as related to this and this threads, is why the idea of Public-Key encryption scheme cannot be secure under CPA (which has equal power as eavesdropper in the public-key area) without the assumption that $P \neq NP$.

If $P=NP$ the task to compute a decision of "whether a secret key $S_k$ is the complement of the given public key $P_k$?" takes a poly time (where complement may be refer to inverse in the Euler group in RSA or discrete-log in El-Gamal or any other term but my question is general) is equal (in regard to the time complexity) to the task of "finding the actual complement $S_k$ from a given $P_k$ and additional public settings (as the group description etc.)" which will also take poly time.

Does my last state seems logical/correct?
How can I further formalize it?


texts: More powerful generator than Nisan-Wigderson one

texts:
Nisan-Wigderson generator can be computed in $\log^{O(1)} n$ space and fools all constant-depth circuits of size poly($n$). I mean Theorem 5 here.

I want another generator, that can be computed in poly($n$) space (but stil it is a function $\{0,1\}^l \to \{0,1\}^n$, where $l = \log^{O(1)} n$ ) however can fool more powerful circuits.

Do such generators exist (unconditional to assumptions)?


texts: Graph-theoretic properties of the Wiener index

texts:
The Wiener index of a graph is the sum of the lengths of the shortest paths between all pairs of its vertices.

Are there useful graph-theoretic properties of this index?


texts: Are there strongly normalizing lambda terms that cannot be given a System F type?

texts:
I know that all well-typed System F terms are strongly normalizing, but is the converse true as well? In other words, does System F typeability precisely characterize program termination? (And if so, how to prove it?) Or are there lambda terms that are strongly normalizing but cannot be given a System F type?
A System F interpreter cannot be implemented in System F. On the other hand, a System F interpreter can be implemented in untyped lambda calculus, but that's not enough. Can a strongly normalizing System F interpreter be implemented in untyped lambda calculus? If yes, this answers our question positively, but I am not sure about it.


texts: Comparison Huffman Encoding and Arithmetic Coding dependent on Entropy

texts: Where can I get an understanding of how Arithmetic Coding and Huffman Encoding compare as entropy increases. I know Arithmetic Coding is better for low entropy distributions, but how can I get a sense of HOW the two scale as you increase entropy? Is this a silly question because I'm missing some piece of the puzzle?


texts:
Given an unweighted tree $T=(V,E)$ what is the minimum number of distance oracles that allow to detect the position in the graph of every node $v$?

A distance oracle is "special node" $u$ of the graph that represents a function $d(u,v)$ giving the distance from $u$ to $v$ in constant time.

I have the intuition that this problem is strictly related to all pair shortest path problem, in particular to the Dijkstra algorithm, but can't find a valid algorithm to detect the oracles.
Also a backtracking procedure comes to mind for this kind of problem. Maybe you have a better intuition.


texts: What are the different notions of one-way functions?

texts:
For instance, A function that is computable but not invertable in log space, Is it one-way function?

What are the known definitions of one-way functions? (especially the ones that do not invoke polynomials)


texts: Universal predictor for $\mathsf{L}$-sequences in $\mathsf{P}$?

texts:
Consider any language $K$. Define $s(K) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula

$$s(K)_n=\chi_K(s(K)_{<n})$$

Here $\chi_K$ is the characteristic function of $K$ i.e. $\chi_K(w)=1$ for $w \in K$, $\chi_K(w)=0$ for $w \notin K$

Fix $\mathsf{X} \subset 2^{{\lbrace 0, 1 \rbrace}^*}$ a set of languages, typically a complexity class

A language $U$ is called an $\mathsf{X}$-predictor when

$$\forall K \in \mathsf{X} \, \forall n>>0:s(K)_n=\chi_U(s(K)_{<n})$$

It is easy to see $U \notin \mathsf{X}$ by considering $K = U^c$. In particular, given $\mathsf{Y} \subset 2^{{\lbrace 0, 1 \rbrace}^*}$, $U \in \mathsf{Y}$ implies $\mathsf{X} \ne \mathsf{Y}$

I am interested to know whether there is an $\mathsf{L}$-predictor in $\mathsf{P}$. Obviously if true it would very difficult to prove since it would imply $\mathsf{L} \ne \mathsf{P}$. However it might be feasible to either prove it under assumptions such as $\mathsf{L} \ne \mathsf{P}$ or prove the converse or at least provide some evidence to one side or other

  What is the evidence for/against the existence of an $\mathsf{L}$-predictor in $\mathsf{P}$?

EDIT: There is a weaker type of predictor the existence of which also implies $\mathsf{L} \ne \mathsf{P}$. Define $s'(K) \in {\lbrace 0, 1 \rbrace}^\omega$ by the formula

$$s'(K)_n=\chi_K(0^n)$$

$U_w$ is called a weak $\mathsf{L}$-predictor when

$$\forall K \in \mathsf{L} \, \forall n>>0:s'(K)_n=\chi_{U_w}(s'(K)_{<n})$$

It's easy to see that any $\mathsf{L}$-predictor is (in particular) a weak $\mathsf{L}$-predictor. However this definition is weaker since when the sequence $s(K)$ is computed, $s(K)_{<n}$ serves as a state of the process of linear size in $n$. On the other hand when $s'(K)$ is computed, we're bounded by the logarithmic size state allowed for deciding $K$

$U_w \in \mathsf{P}$ implies $\mathsf{L} \ne \mathsf{P}$ since it's easy to see that if $\mathsf{L} = \mathsf{P}$ then a weak $\mathsf{L}$-predictor is a $\mathsf{P}$-predictor

  What is the evidence for/against the existence of a weak $\mathsf{L}$-predictor in $\mathsf{P}$?

As a sidenote, $U_w \in \mathsf{P}$ also implies that there is a polynomial $p(n)$ such that any $K \in \mathsf{TALLY} \cap \mathsf{L}$ can be decided in time $t_K(n)$ with $t_K(n) < p(n)$ for $n >> 0$

Actually proving that there is no $\mathsf{L}$-predictor in $\mathsf{P}$ must also be very difficult since it would imply $\mathsf{P} \ne \mathsf{PSPACE}$. This is so since it's possible to construct an $\mathsf{L}$-predictor in $\mathsf{PSPACE}$, analogously to the construction of a $\mathsf{P}$-predictor in $\mathsf{E}$ given here


texts: Integer Factoring via Lattice Reduction?

texts:
I found a paper titled "Factoring integers and computing discrete logarithms via diophantine approximation" by C. P. Schnorr from 1993.  It looks like a probabilistic method with expected polynomial run time (and space) is presented to do integer factorization.

From the paper: "A scenario for factoring $N \approx 2^{512} $ ... The corresponding lattice problem is unfeasible for the presently known lattice reduction algorithms.  We have no experience with lattice basis reduction for lattices with dimension 6300.  Moreover the bit length of the input vectors is at least 1500."

I take this to mean that the algorithm presented is polynomial but the exponent and factors are so large that it makes it computationally impractical for current technology.

Can anyone weigh in on this?  Is this paper legitimate?  Isn't this huge news if it is?  Doesn't this mean that integer factoring is likely in P?  Have people been progressing towards making lattice reduction algorithms more tractable?


texts: Can we decide Red-blue cut problem in polynomial time?

texts:
Given a directed graph whose arcs are coloured red and blue and integers $r$ and $b$, can we decide in polynomial time whether the digraph has a cut with at most $r$ red arcs and at most $b$ blue arcs?

Related references can be found here http://lemon.cs.elte.hu/egres/open/Red-blue_cut_problem

It is known that the undirected version of the problem is in P even if there are weights on the edges.


texts: Context-Sensitive Grammar characteristic properties

texts:
This question can look like some kind of puzzle, but it is actually part of more complex applied problem.

Let's consider subspace of Context-Sensitive Grammars, which contains grammars which can not be represented neither as Context-Free Grammars, neither as Regular Grammars. Let's call them "strong CSG".

And let's suppose that we are given only by alphabet, set of nonterminals, set of production rules, but without left sides (which is hidden from us). For instance:

$\Sigma=\{a,b,c\}$
$N=\{S,B,W,X\}$

and rules:

$?\rightarrow abc$
$?\rightarrow aSBc$
$?\rightarrow WB$
$?\rightarrow WX$
$?\rightarrow BX$
$?\rightarrow Bc$
$?\rightarrow bb$

The question is: are any general properties regarding right-side of these production rules using which we can distinguish strong-CSG from CFG and RG looking only on this non-complete set of rules?

Alternative formulation of this question: in this particular case, can given grammar be Context-free?

Let's also consider that in case of CFG given grammar is always present in reduced (simplified) form (by reduction I mean finding a CFG with the fewest nonterminal symbols or with the fewest rules that is equivalent to G) - (we're talking here about weak-equivalent grammar with smallest number of non-terminals and production rules - thanks to @Marzio De Biasi for pointing this).

Disclaimer: original grammar was Context-Sensitive, taken from wikipedia article.


texts: Complexity of the Transductive SVM training problem

texts:
The Transductive Support Vector Machine training problem is a non-convex mixed integer programming problem:

  Transductive Support Vector Machine training problem.
  $$
\begin{align}
\mathop{\text{minimize}}_{\xi,\theta,b,u} \;&\|\theta\|^2 + C \sum_{i=1}^{m+k} \xi_i \\[1ex]
\text{subject to:}\;
&y^{(i)}(\theta^T x^{(i)}-b) \geqslant 1-\xi_i, \quad\text{for } \; i=1, \ldots, m\\
&u_i\;\;(\theta^T x^{(i)}-b) \geqslant 1-\xi_i, \quad\text{for }\; i=m, \ldots, m+k\\
&u_i \in \{-1, 1\}\\
&\xi_i \geqslant 0
\end{align}
$$
  where $C > 0$, and:

  $x^{(1)},\dots,x^{(m+k)} \in \mathbb{R}^n$ are data points;
  $y^{(1)},\dots,y^{(m)} \in \{-1, 1\}$ are labels provided for $1 \leqslant i \leqslant m$ (the vectors $x^{(i)}$ are missing labels for $i > m$).

If I recall correctly, it can be proved that this problem is NP-hard, but I can't find a reference to that claim.

Questions.

Is it really NP-hard?
Is it APX-complete?


texts: Finding the two shortest paths while minimizing the number of nearby/common edges

texts:
The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary.

Consider the following variant:

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

Has this problem been addressed before?


texts: Is there any tool where one can figure out if two people have coauthored or not? Like the tool where one can figure out somebody's Erdos _number_ .


texts: Which areas of computer science have lots of overlap with physics?

texts: I'm an undergrad in computer science but I've always loved physics and its ability to constantly amaze and surprise us about our world. I am wondering if there are areas in graduate level computer science that one can get into which involve a lot of work on physics. The one I know of that is talked a lot about is Quantum computing. I've also heard of information theory, which involves the study of thermodynamics. Which other ones are there?


texts: Is this graph polynomial known? Can it be efficiently computed?

texts:
Consider a connected simple graph $G$ with $n$ vertices and $m$ edges. View each edge $\ell$ as a transposition $t_{\ell}$ acting on the set of vertices. [To be more explicit, given an edge $\ell$ joining vertices $v_1$ and $v_2$, $t_{\ell}$ is a permutation exchanging $v_1$ and $v_2$, leaving all other vertices fixed.] Let ${\cal L}$ be the set of ordered $m$-tuples of the edges, so that elements of ${\cal L}$ are of the form $L = (\ell_1, \dots, \ell_m)$, with each edge appearing exactly once.

To each $L \in {\cal L}$ we can associate a permutation $\pi(L) \in S_n$ by taking the product of transpositions, $\begin{equation} \pi[(\ell_1, \dots, \ell_m)] = t_{\ell_1} t_{\ell_2} \cdots t_{\ell_m}. \end{equation}$

For $\pi \in S_n$, let $c(\pi)$ be the number of cycles in the the cycle decomposition, counting 1-cycles. So for example $c(1) = n$, and $c(\pi) = 1$ for $\pi$ an $n$-cycle. Then I can define the polynomial of interest: $\begin{equation} X(N) = \sum_{L \in {\cal L}} N^{c[\pi(L)]} \text{.} \end{equation}$

My primary question is whether an efficient (in practical terms) procedure is known to compute $X(N)$, either for arbitrary graphs, or for certain families of graphs. In my application, I need to compute $X(N)$ for all graphs that are subgraphs of a given regular lattice, up to some maximum number of edges (which I would like to make as large as possible). In particular, I am focused on the square lattice (for now), which restricts to bipartite planar graphs. Perhaps also relevant, in my application parallel edges are allowed, but I focused on simple graphs here for simplicity.

I already know $X(N) = m! N$ if $G$ is a tree, and $X(N) = m! N^2$ if $G$ is a cycle. In addition, removing all bridges from $G$, there is a simple formula giving $X(N)$ as a product of the $X(N)$'s of the resulting components, multiplied by an overall factor. Beyond this, so far the best I can do is to take a brute force approach.
Beyond my primary question, I am also more generally interested to learn what, if anything, is known about this polynomial. For instance, are there references where $X(N)$ is studied, is $X(N)$ related to other (perhaps better-known) graph polynomials, etc.?

Cross posted from mathoverflow, https://mathoverflow.net/questions/177103/is-this-graph-polynomial-known-can-it-be-efficiently-computed#177103"


texts:
I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent.  I don't know if researchers in quantum complexity have started using parameterized complexity or not, so I will not comment on that.  I tried to search on google but did not find able to find anything.

Question : Are there works on "quantum parametrized complexity"?


texts: Meaning of P=NP? depends on space-time geometry ?

texts:
This question is about Page 125 of the book "Cellular automata in hyperbolic spaces: Volume 2" By Maurice Margenstern, Publisher Archives contemporaines, 2008.

http://books.google.com/books?id=eEgvfic3A4kC&pg=PA125

In the author's opinion, the question P=NP is ill-posed because in the hyperbolic setting P=NP or in the notation used later in the book Ph=NPh.

I don't know enough about complexity to know what to make of this, but it sounds interesting.

So the question is basically, what do you make of it?

Do his claims make sense ?


texts: How can I obtain famous articles which are not available online?

texts:
I have Googled myself to death, but have been unable to find the following articles:

Breen, E., Monro, D., 1994. An evaluation of priority queues for
mathematical morphology.
R. Beare and H. Talbot., 1999 Exact seeded region growing for image
segmentation.

These articles are well known, important and often cited by others, but they seem to be impossible to find. Does anyone know where I could find these or maybe someone could point me in the right direction?

More generally,

  What should I do when I cannot find an online copy of an article?


texts: Simple candidates for pseudorandom permutations?

texts:
Even though it is not known whether one-way functions exist, there are several candidate functions used in practice for cryptographic applications that are efficiently computable but are conjectured to be hard to invert (such as modular exponentiation, the Rabin function etc.) Moreover, many of these functions are relatively simple to compute in some sense.

Are there any simple candidates for strongly pseudorandom permutations? By a simple candidate, I mean one with small circuit complexity (or maybe small complexity under some different complexity measure). For example, are there any candidates for PRPs that can be computed by $NC^1$ circuits? (I am looking for PRPs which work with arbitrarily long inputs, as opposed to block ciphers operating on fixed-length strings.)


texts:
I wonder, what would happen, if in the definition of $PH$ (Polynomial Hierarchy, see, e.g., here), the role of $NP$ would be replaced by $RP$?

It seems, we could still build a hierarchy, the same way as $PH$ is built, just using $RP$ everywhere instead of $NP$, and $coRP$ instead of $coNP$. Let us call it Randomized Polynomial Hierarchy ($RPH$).

My first guess is that $RPH\subseteq BPP$, or maybe $RPH=BPP$. It is based on the known  fact that $NP=RP$ implies $PH=BPP$. Nevertheless, if $P\neq RP$, then $RPH$ could still be a proper, infinite hierarchy within $BPP$.

Of course, the edge of the issue is blunted by the fact that $P=RP$ is conjectured (even $P=BPP$), which would flatten $RPH$ into $P$.  However, $P=RP$  is not known at this time, and it has resisted all proof attempts so far. Therefore,  $RPH$ still has at least some chance to be a proper hierarchy.

While $RPH$, admittedly, has a good chance to be "flat," could the concept still be useful for something nontrivial? Here is an example: if one can prove $RPH=BPP$, then it would yield that $P=RP$ implies $P=BPP$, which, I think,  would be an interesting result.

Is anything known about this?


texts: What are recent advances in relational databases?

texts:
I'm wondering what are recent advances in relational database theory and related domains?

I'm interested in new approaches, query languages (alternatives to SQL and/or extensions to it), products (proprietary and open source, though I'm much more interested in open source) and research projects developed in last years.


texts: Sorting algorithm with a complexity smaller than $n \log n$?

texts:
If we consider literature, sorting algorithms are based only on number of comparisons needed to sort a list of size n, considering that n is the size of the input.

But if we want to encode input, we can't encode each object of the list into a fixed-size binary representation because hence, we would consider that the domain of the objects is fixed and thus, I think we could find better sorting algorithms by precomputing some stuff in the Turing Machine.

If we consider that the domain isn't fixed, we have to encode each of our items into a $\log(n)$-size representation. Thus the input is of size $N = n\log(n)$. But as our numbers are of variable length, then we can consider that comparison has a cost of $\log(n)$, but even with this, if we apply a reasonable sorting algorithm (ie an $n \log n$ algorithm), the algorithm will take $n \log^2(n)$ time in a Turing machine, where $n$ is the number of objects, but where $n \log n$ is the size of our input. In this case, we have an algorithm of complexity lower than $O(N \log(N))$ where $N$ is the size of the input.

Is there a mistake?


texts: Regex Equivalence is a hard problem which in general takes exponential space and exponential time. Are there any approximation/sub-optimal algorithms with some theoretical guarantees over equivalence available?


texts: What is schema theory within Genetic Algorithms

texts:
I understand (some) of the workings behind schema theory in genetic algorithms, for example:

*****0 would match the genome 010100

But could anyone explain what schema theory (in Genetic Algorithms) is used for, and how it's used?


texts: Efficient quantum algorithm for CLASSICAL FFT

texts:
Is there a known improvement on the current O(n*log(n)) algorithm for CLASSICAL FFT using quantum computation? 'n' is the number of samples.

I need to find the amplitude and phase of the K dominating (highest amplitude) frequencies, where K is a fixed constant and K is much smallet then n.


texts: Metrics for modelling convergence in the lambda-calculus

texts:
I wonder if there have been efforts to reconcile the measure approach to termination and Scott's domain theory or other topological models of computation. In other words, can we translate this measure that one use in automation of program termination to metric or measures in a topological interpretation of a programming language?
Examples:
$\Omega = (\lambda x. x x) (\lambda x. x x)$
References:
Models and theories of lambda calculus
Computable topology


texts: What is the relationship between the number of states in Quantum Finite Automata and the number of non-regular languages they can recognize?

texts:
It is has been shown that Quantum Finite Automata can recognize at least some non-regular languages. What is the relationship between the number of states in a qfa and the number of non-regular languages it can recognize? Is there a relationship at all or has it not yet been established?

I have been unable to find a paper that addresses this in an overtly and understandable way. More specifically, for any one specific type (ex/ 1-way MM-QFA), has any such relationship been established for the class it recognizes? I know different types of QFAs have different closure properties and other characteristics that can make them vastly different and bounds have been established for some, but I'm wondering if anyone knows of, has seen, or knows who to contact regarding the relationship between teh number of states in a qfa and its recognition properties? Or, if this question is totally mute and I'm looking at it wrong, tell me why. I have read into some of Freivalds' research where he touches on this, but can't find any theorems, proofs, lemmas, ect. that hammer it out, if anyone has done so at all. There is a possibility that this question is open and that's why I havent found an answer. Any help you can give would be appreciated.


texts: Commutative matrix multiplication algorithms

texts:
What is known about commutative algorithms like Winograd algorithm and its variants for Matrix Multiplication? Why is there not much study on them? Can they be asymptotically as efficient as Non-commutative algorithms?

Update

Existence of $O(n^\omega)$ non-commutative algorithms for matrix multiplication implies existence of $O(n^\omega)$ commutative algorithms. Does converse statement hold truth?


texts: Concurrent transactions satisfying "serializability" but not "snapshot isolation"

texts:
In [Lin et al@TODS'2009] (Page 5), a history of concurrent transactions satisfying "serializability" ($\textrm{SR}$) but not "snapshot isolation" ($\textrm{SI}$) is given as follows:

  $H_{example}: s_1 \; s_2 \; w_1(x_1) \; r_2(x_1) \; w_2(x_2) \; w_2(y_2) \; c_1 \; c_2 \; s_3 \; r_3(x_1) \; c_3 \; s_4 \; w_4(y_4) \; a_4$

where, $s_1$ denotes the start of transaction $T_1$; $w_1(x_1)$ denotes the write of $T_1$ of version $v_1$ to data item $x$; $c_1$ denotes the commit of $T_1$; and $a_4$ denotes the abort of transaction $T_4$.

Pictorially (horizontal axis is time),

T1: s1    w1(x1)                      c1
T2:    s2        r2(x1) w2(x2) w2(y2)    c2
T3:                                         s3 r3(x1) c3
T4:                                                      s4 w4(y4) a4

My Confusion:

However, as my basic understanding, Serializability is strictly stronger than snapshot isolation. In particular, we have a hierarchy of isolation levels as shown in the following figure copied from [Berenson et al@MSR-TR'1995].

My question:

  What is wrong with my understanding and what is going on here?

  Any comprehensive references on the relationships among $\textrm{SI}$, $\textrm{SR}$, and maybe other isolation levels are appreciated.

References:

([Lin et al@TODS'2009]) Snapshot Isolation and Integrity Constraints in Replicated Databases

(Berenson et al@MSR-TR'1995) A Critique of ANSI SQL Isolation Levels


texts: Implications of a deterministic polytime prime-finding algorithm

texts:
I'm wondering what are the current known uses/implications of a polynomial-time algorithm for the following problem:

  Given $n$ in binary, output a prime $p > n$.

I'm both curious about specific useful applications, and any more broad complexity implications (for instance, would this get us any closer to $P=BPP$?).

Edit: by the way, this problem was (is?) the subject of the Polymath4 project, which produced this writeup, but I do not see anywhere that they discuss implications of truth of the conjecture.


texts: Reduction/transformation from MinCostSat to MaxSat

texts:
I recently ran into MaxSAT competitions website and was looking into the problem formulation. I vaguely remember reading somewhere that MinCostSAT and MaxSAT are related to each other and one can be reduced to another. I read here http://repository.lib.ncsu.edu/ir/handle/1840.16/4594 that the MaxSAT to MinCostSAT reduction is to use a slack variable for each clause in the MaxSAT and giving it the value of 1 and all other boolean variables 0 reduces the problem to MinCostSAT. Can some one please tell me how does this work? How does it make the MaxSAT instance the instance of MinCostSAT?

Also, what is the reduction from MinCostSAT to MaxSAT or may be even weighted MaxSAT, especially considering the fact that I have a problem to which I know the cost of assignments and want to minimize this cost and if I have the off the shelf solvers available like the ones that have won MaxSAT competitions, how do I go about reducing my MinCostSAT problem to MaxSAT?

P.S. I hope this won't be rejected as an implementation level question since my question is really about reduction. I can think about implementing it, if I know the reduction at least.


texts: Complexity of balanced graph partition problem

texts:
Wagner and Wagner, in "Between min cut and graph bisection" (MFCS 1993), studied a variant of minimum bisection problem where we seek a cut with minimum size such that each partition has at least $\log n$ verticies. They stated that the complexity of this variant is an open problem since they did not find an efficient algorithm nor NP-hardness proof.

  Has anyone setteled the complexity of $\log n $ balanced graph partition?


texts: Given an undirected unweighted graph, the almost minimum cycle is defined as the cycle whose length is greater than that of a minimum cycle by at most one. Itai and Rodeh in a seminal paper in 1978 gave a simple O(n^2) algorithm to find such an almost minimum cycle. My question is, has it been improved ever since? If yes, which paper does that?


texts: Consequences of lower bounds for $\epsilon$-nets on approximation

texts:
Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [PDF].  I would like to know what, if anything, such a lower bound implies about the approximability of the associated Set Cover/Hitting Set problems.

To be slightly more specific, consider a family of range spaces, for example, the family:

$\big\{(X,\mathcal{R})$ : $X$ is a finite planar point set, $\mathcal{R}$ contains all intersections of $X$ with lines$\big\}$

If, for some function $f$ that is linear or super-linear, the family contains a range space that does not admit $\epsilon$-nets of size $f(1/\epsilon)$, what, if anything, does this imply about the Minimum Hitting Set problem restricted to this family of range spaces?


texts: Maximum subgraph problem with unknown complexity

texts:
Let $Q$ be a polynomial time decidable graph property. In a graph let us call a subgraph $S$ a $Q$-subgraph, if $S$ has the property $Q$. Consider the following optimization problem:
Maximum $Q$-Subgraph problem
Input: Simple undirected graph $G=(V,E)$, and an integer $\ell$, with $1\leq \ell\leq |V|$.
Question: Does there exist a subset $S\subseteq V$ with $|S|\geq \ell$, such that the subgraph induced by $S$ is a $Q$-subgraph?
With various choices for the property $Q$ we can get classical problems. For example, if $Q(S)=$ "$S$ spans a clique" then we obtain the Maximum Clique problem, which is $NP$-complete. The choice  $Q(S)=$ "$S$ spans a subgraph with a perfect matching" leads to the Maximum Matching problem, which is in $P.$ If we take $Q(S)=$ "$S$ spans a subgraph with minimum degree $\geq k$" leads to the $k$-core problem, which is also in $P.$
Questions:

Is there any choice for the (polynomial time decidable) graph property $Q$, such that the complexity of the Maximum $Q$-Subgraph problem is not known?

If we do not find such an example for $Q$, then I would venture into the following conjecture: there is a dichotomy here, that is, for every polynomial time decidable graph property $Q$, the Maximum $Q$-Subgraph problem is always either $NP$-complete or is in $P.$ Is there any argument for or against this conjecture?


texts: Complexity of existence of simple polygonalization with prescribed area?

texts:
This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization  is a closed chain of straight line segments that does not cross itself).

I am interested in the complexity of this problem:

Input: Set $S$ of $N$ points on integer 2D grid and a rational number $A$

Question: Is there a polygonalization that has enclosed area $A$?

  Is this problem still NP-complete?

The area $A$ is given as an integer (represented in unary)

Fekete, Sándor P. "On simple polygonalizations with optimal area." Discrete & Computational Geometry 23.1 (2000): 73-110


texts: Simple to implement approximate quantile data structure for a stream of integers?

texts:
I'm looking for a simple data structure that will let me compute arbitrary approximate quantiles, within a percent or two error, on a stream of 64-bit integers (think of $n$ as being potentially as high as a trillion or so).

In order of importance, it would have the following desired traits:

1) Fast update time, at most a few hundred cycles per element in the stream, but even lower is better

2) Memory usage of at most a few hundred bytes per stream

3) Simplicity of implementation. Hopefully no more than a few hours to implement. Properties 1 and 2 are essential, but this one is also very important as well.

I encountered the following paper, which suggests that Q-Digest may be a good option. Is this true, and are there any other possibilities I should be aware of?


texts: What is an "informational density" and why numeral system with the base of e (2,71828...) has the maximum informational density? How do you calculate "informational density" of a given numeral system?


texts: Is partitioning a multiset into two multisets with equal averages NP-complete?

texts: The subset sum problem of partitioning a multiset of integers into two multisets with equal sums is NP-complete. Is the seemingly related problem of partitioning a multiset of integers into two multisets with equal averages also known to be NP-complete? Does the problem have a received name? I have found no formal analysis of the problem online, only an occasional speculation that the problem may be “hard.”


texts: Canonical representation of Binary Decision Tree in Ptime?

texts:
I am wondering whether there may exist a way to give a sort of "normal form" for binary decision trees (BDT) in a tractable way.

More precisely: a BDT is a tree with internal nodes labelled by boolean variables and leaves labelled by $0$ or $1$. A BDT represents a boolean function in the obvious way. Two BDT $A,B$ are equivalent ($A\sim B$) when they represent the same function.

Does there exist a function $f$ that inputs a BDT and turns it into some other data structure such that:

$f$ is in Ptime
$f(A)=f(B)$ if and only if $A\sim B$
$f$ has a pseudo-inverse $g$, that is $g(f(A))\sim A$, also in Ptime

For instance reduced ordered binary decision diagrams OBDD validate 2 and 3, but not 1 because with the wrong variable ordering the output might be of exponential size.

I have a feeling that this might not be possible, but have not found any evidence of that anywhere.

To comment further on Ricky Demer's suggestion:

This paper defines the $PEq$ (equivalence classes in Ptime) and $Ker$ (complete invariant in Ptime)  and CF (canonical form in Ptime) classes. They study various (unlikely) implications of $PEq=Ker$ and $Ker=CF$ but do not provide a definite answer to these questions.

Various negative answers (impossibility of 1&2, 1&2&3) to this question would provide separation results as $PEq\neq Ker$ or $Ker\neq CF$... which seems to be an open problem so far.


texts:
Let $A$ be any EXP complete problem. Then, $P^A = NP^A$.

Let $B$ be some oracle that takes into accounts the queries that $M$ (a TM in P) will make, and we can get $P^B \neq NP^B$.

Question: Do we have similar oracle results for P vs BPP?


texts: Looking for algorithm (or at least name) for this optimization problem

texts:
Suppose that we have $n \geq 2$ distinct triplets $t_0, t_1, ..., t_{n-1}$ of real numbers, $t_i = (x_i, l_i, r_i)$.

Define $$\Delta(s) = \max_{i, j} \left[ s (x_j - x_i) + (r_j - l_i) \right]$$

The problem is, given some arbitrary target $\Delta_0$, to find $s^*$ such that $\Delta(s^*) = \Delta_0$.  (NB: There may be no such $s^*$.  For example, $n = 2$, and $t_0 = (0, -1, 0), t_1 = (0, 0, 1)$, then $\Delta(s)$ has constant value $2$, so the problem has a solution, infinitely many in fact, only if $\Delta_0 = 2$.)

  I'm looking for an algorithm to solve this problem, or at least some search terms (keywords, author names, etc) that I may try when searching online for such an algorithm.

FWIW, for the special case I'm working with, the following additional conditions/considerations apply:

$x_0 < x_1$;
$l_0 = r_0 = l_1 = r_1 = 0$;
$l_i < r_i, \forall \, i > 1$;
only positive solutions $s^*$ are of interest;
$\Delta_0 \geq \max_{i,j} (r_j - l_i)$.


texts: Progress on generalized star-height problem?

texts:
The (generalized) star height of a language is the minimum nesting of Kleene stars required to represent the language by an extended regular expression. Recall that an extended regular expression over a finite alphabet $A$ satisfies the following:

(1) $\emptyset, 1$ and $a$ are extended regular expressions for all $a\in A$

(2) For all extended regular expressions $E,F$;
 $E\cup F$, $EF$, $E^*$ and $E^c$ are extended regular expressions

One phrasing of the generalized star height problem is whether there is an algorithm to compute the minimum generalized star height.  With regards to this problem I have a few questions.

Has there been any recent progress (or research interest) concerning this problem? I know a number of years ago that Pin Straubing and Thérien published some papers in this area.
The restricted star height problem was resolved in 1988 by Hashiguchi but the generalized version  (as far as I know) is still open. Does anyone have any intuition as to why this might be the case?

A link that might be helpful is the following:  starheight


texts: Is there a known notion of "stochastic dependent pair"?

texts:
I came upon this when thinking about the semantics of probabilistic programs.  Say you have a generative model
N ~ Poisson()
for n = 1:N
  X[i] ~ Normal()

Then the size of X will stochastically depend on N.  Thinking about this as dependent pairs, I would intuitively write something like
$$
X : \sum_{n \sim \operatorname{Poisson}()} \operatorname{Vect} n
$$
Has anyone come up with such a theory of representing stochastic structure by dependent types?
For a bit of context, I am interested in ways how trace types could be extended to more dynamic settings, in the sense of probabilistic programs that would require a trace type whose key space is itself random (i.e., the encountered variables and their shapes can vary in sampling).


texts:
So, a quick search on the web led me to believe that "APXHardness implies that no QPTAS exist for a problem unless [some complexity class] is included in some [other complexity class]" and it is well known too! It seems like everybody knows this except for me. Unfortunately, no reference to support this statement is given. I have two questions:

What is the strongest version of this statement that is currently known?
A reference? Please?

Thanks in advance.

Chandra Chekuri's answer suggests that a $QPTAS$ for a $APX$-hard problem implies $NP\subseteq QP$. Can anyone explain why it is true, or preferably give a reference for that? In other words, why does quasi polynomial time approximability imply QP time solvability?


texts: Finding a basis for quantum measurement with maximum distinguishability

texts:
I wish to find a basis state for the quantum measurement of two states which provides the maximum possible distinguishability. In this example let's say we wish to find the best basis ($|\psi\rangle$) to distinguish between $|0\rangle$ and $|+\rangle$.

My approach was to generalize the quantum states as density matrices:

$\rho_+=|+\rangle\langle+|=\frac{1}{\sqrt{2}}\pmatrix{1\cr1}\frac{1}{\sqrt{2}}\pmatrix{1&1}=\frac{1}{2}\pmatrix{1&1\cr1&1}$

$\rho_0=|0\rangle\langle0|=\pmatrix{1\cr0}\pmatrix{1&0}=\pmatrix{1&0\cr0&0}$

$\rho_{\psi}=\frac{1}{2}\left(I+r_x\pmatrix{0&1\cr1&0}+r_y\pmatrix{0&-i\cr{i}&0}+r_z\pmatrix{1&0\cr0&-1}\right)=\frac{1}{2}\pmatrix{1+r_z&r_x-ir_y\cr{r_x+ir_y}&1-r_z}$

$\left|\vec{r}\right|\le1$

My next step was to maximize the difference in quantum fidelity, which I assume is calculated as:

$\Delta Fidelity=p_\psi\left(|+\rangle\right)-p_\psi\left(|0\rangle\right)=|\langle+|\psi\rangle|^2-|\langle0|\psi\rangle|^2=tr\left(\rho_+\rho_\psi\right)-tr\left(\rho_0\rho_\psi\right)$

$\rho_+\rho_\psi=\frac{1}{2}\pmatrix{1&1\cr1&1}\frac{1}{2}\pmatrix{1+r_z&r_x-ir_y\cr{r_x+ir_y}&1-r_z}=\frac{1}{4}\pmatrix{1+r_x+ir_y+r_z&1+r_x-ir_y-r_z\cr1+r_x+ir_y+r_z&1+r_x-ir_y-r_z}$

$tr\left(\rho_+\rho_\psi\right)=\frac{1}{2}\left(1+r_x\right)$

$\rho_0\rho_\psi=\pmatrix{1&0\cr0&0}\frac{1}{2}\pmatrix{1+r_z&r_x-ir_y\cr{r_x+ir_y}&1-r_z}=\frac{1}{2}\pmatrix{1+r_z&r_x-ir_y\cr0&0}$

$tr\left(\rho_0\rho_\psi\right)=\frac{1}{2}\left(1+r_z\right)$

As far as I can tell, the work so far looks right, since a density matrix with $r_x=1$ and $r_x=r_y=0$ is the density matrix of state $|+\rangle$, same for $|0\rangle$. This next part is where I get stuck. I try to find the basis state which maximizes distinguishably by finding the quantum state which results in the largest difference in fidelity:

$\Delta Fidelity=\frac{1}{2}\left(1+r_x\right)-\frac{1}{2}\left(1+r_z\right)=\frac{1}{2}\left(r_x-r_z\right)$

I know the correct answer here is $|\psi\rangle=\frac{|+\rangle+|0\rangle}{2cos\left(\frac{\pi}{8}\right)}$, which is a quantum state where $r_x=\frac{1}{\sqrt{2}}$ and $r_z=\frac{1}{\sqrt{2}}$. This quantum state has a fidelity of 0.854 with $|+\rangle$ and a fidelity of 0.146 with $|0\rangle$. However, I coudld not have gotten to this answer with $\Delta Fidelity=\frac{1}{2}\left(r_x-r_z\right)$, since that equation would have led me to picking $r_x=1$ and $r_z=0$ (which is $|+\rangle$) as a measurement basis.

I'm wondering what it is I missed here?


texts: Theoretical background of Classes and Objects

texts: I would like to learn about the possible ways of formalizing Classes and Objects (in programing languages like java) using formal languages. Where should I start? This might be related to my previous question I asked here.


texts: Can any Steiner Tree Problem be converted to Node-Weighted Steiner Tree Problem?

texts:
Steiner Tree Problem:
Given a weighted graph G(V,E,w) where w is the weight function on edges and a subset of vertices S⊆Q called terminals, a Steiner Tree is a connected subgraph which connects all vertices in S. Finding minimum weight Steiner Tree is called Steiner Tree Problem.

Node-weighted Steiner Tree Problem
Given a weighted graph G(V,E,w) where w is the weight function on nodes and a subset of vertices S⊆Q called terminals, a Node-Weighted Steiner Tree is a connected subgraph which connects all vertices in S. Finding minimum weight Steiner Tree is called Node-Weighed Steiner Tree Problem.

My question is: can any Steiner Tree Problem be converted to Node-weighted Steiner Tree Problem? I have the following approach and need to verify whether it is correct:

Lets assume we have a Steiner Tree problem with weighted edges. Consider an edge (u, v) with weight w assigned to it. Lets place a vertex X on this edge, so that the edge splits in two edges: (u, X) and (X, v). Assign zero weight to each of those edges, and assign weight w to vertex X. Repeat this for every edge of the initial graph.

The obtained graph will be node weighted and any solution to the node-weighted problem can be easily converted to match initial Steiner Tree Problem.

Basically, I need someone to verify all above is valid. I would also greatly appreciate any references from reliable sources, regarding this issue.


texts: Is $MSB$ of permanent and certifying half number of witnesses easy?

texts:
Can there be a $P$ algorithm to decide if number of perfect matchings is at least $(n!/2)+1$ for a bipartite graph on $n+n$ vertices?
Can there be a $P$ algorithm to decide if number of witnesses exactly $2^n$ for a $SAT$ formula with $2n$ variables

At least are any of above problems in $PH$? Is there any consequence if they are so?


texts:
It is well-known that sorting permutations by transposition is in $\sf{P}$, as the minimum number of transpositions required to sort $\pi \in S_n$ is exactly $inv(\pi) = \{ (i,j) \in [n] \times [n] : i < j \text{ and } \pi(i) > \pi(j) \}$. This notion of "inversion number" has also applications in algebraic combinatorics, for instance it allows to endow $S_n$ with a structure of lattice, called the permutohedron and based on the weak Bruhat order.

It can be illuminating to recast the problem in group-theoretic terms. We are given a group $G$ with generator set $\Gamma$ and a mapping $i_G : \Gamma^* \rightarrow G$, and another group $H$ on which $G$ acts transitively, and we want to solve the following problem: given $h \in H$, find a minimum-length $w \in \Gamma^*$ such that $i_G(w).h = 1_H$. In the permutation case, $G = H = S_n$ and $\Gamma$ is the set of transpositions.

Question: are there other instances of this problem which admit efficient algorithms?


texts: Finding the distance between two polynomials (represented as trees)

texts:
A colleague who works on genetic programming asked me the following question. I first tried to solve it based on a greedy approach, but on a second thought, I found a counterexample to the greedy algorithm. So, I thought it's worth mentioning here.

Consider two polynomials which are represented by their expression trees. For instance, $x^3-2x+1$ and $x^2 + 4$ are illustrated below:

Rules:

Each node is either a variable name ($x, y, z, \ldots$), a number, or an operation (+,-,×).
The in-order traversal of the tree should result in a valid polynomial.
Operation nodes have in-degree 2. Other nodes have in-degree 0. All nodes have out-degree 1 (except root, whose out-degree is 0).

On a node N of the tree, define the basic operation as follows:

A basic operation can change the label of the node. For instance, $x$ can be changed to 3, or + can be changed to $\times$.
A basic operation can build an expression tree on top of N (see the example below).

The cost of the basic operation of type 1 is 1. The cost for type 2 is equal to the number of {+,-,×} operations in the newly built expression tree.

Example for type 2: The cost of the following basic operation is 2, since the expression tree built on top of node N uses two operations (- and ×).

Let T1 and T2 be two expression trees representing polynomials.
Define the distance of T1 and T2 as follows: the minimum cost of basic operations for converting T1 to T2. Note that we don't require the converted tree to have the same structure as T2. We just want it to compute the same polynomial as T2. (See the comments for an example.)

  The problem: Given T1 and T2, present an algorithm which computes their distance.

Example 1: Let T1 and T2 are the two trees illustrated at the beginning of this post. To convert the right tree to the left tree, one can build a tree of cost 3 on top of ×, and change 4 to 1 (the total cost is 4).

Example 2: Let T1=$x^4$ be represented by the following tree. To convert T1 to T2=$x^4+4x^3+6x^2+4x+1$, it suffices to add 1 to each of the $x$ nodes, to optain $(x+1)^4$=T2. This can be done by adding a cost-1 expression tree on top of each $x$ node. This example shows that the term-by-term conversion (which I called the greedy approach at the beginning of this post) is not an optimal approach. That is, if one wants to produce terms in T2 which are not present in T1 (i.e. $4x^3$, $6x^2$, $4x$, and 1), the cost will be much higher.


texts: Complexity of Comparative Independent Set Decision Problem

texts:
Consider the following problem:

Input: (G1, G2) where G1 and G2 are undirected graphs

Question:  Is the size of the max independent set of G1 at least as large as the size of the max independent set of G2?

This seems like a fairly natural question to ask, and yet I have been unable to find a complexity class for which this problem is complete.  Does anyone know of such?  As a starting point, it is readily seen that the problem is NP-hard and contained in P with access to an NP oracle with log many queries.


texts: What's the effect of imposing the following restriction on inductive type families?

texts:
Let a simple expression be either:

A free variable
A data constructor of an inductive type family, applied to 0 or more simple expressions

What would be the effect of imposing the following restriction on a programming language with inductive type families?

  Given a data constructor C of an inductive type family T, within C's type signature, T and (=) (the propositional equality type constructor) may only appear fully applied to simple expressions whose free variables are bound within the type signature itself.

For example, in GHC Haskell (to avoid writing foralls in obvious places):

{-# LANGUAGE DataKinds, GADTs, KindSignatures #-}

data Color = Red | Black
data Sign = Positive | Negative

-- Bad: Test appears applied to Color and Sign, neither
-- of which is a data constructor of an inductive type.
data Test :: * -> * where
  Foo :: Integer -> Test Color
  Bar :: Float   -> Test Sign

-- Good: List only appears applied to free variables.
data List :: (k -> k -> *) -> k -> k -> * where
  Nil  ::                        List f a a
  Cons :: f a b -> List f b c -> List f a c

-- Good: RBT appears applied to Black and Red, both of
-- which are constructors of an inductive type (Color).
data RBT :: Color -> * -> * where
  Empty ::                                    RBT Black a
  R     :: RBT Black a -> a -> RBT Black a -> RBT Red   a
  B     :: RBT l     a -> a -> RBT r     a -> RBT Black a

Now, what I want to know is:

From the POV of language implementors, can this restriction simplify type checking? How much?
From the POV of programmers using languages like Agda, Idris, Coq, etc., are there any useful programs that type check without the restriction, that can't be refactored into equivalent programs that type check under the restriction?
From the POV of type theorists and other mathematicians using type theory as a foundational system, does the restriction prevent any useful mathematical results from being obtained internally to type theory?


texts: Concentration Bounds for Dependent Rounding

texts:
Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$:

At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its value to $x'_i$ such that $0\leq x'_i \leq 1$ and $E[x'_i]=x_i$. We stop the process when all the numbers are either $0$ or $1$.

Given that the process is stopped, it is easy to verify that Chernoff bounds hold in the following sense: Let the outcome of the process be the binary numbers $y_1,\ldots,y_n$. For any subset $S$ of indices define $\mu_S=\sum_{i\in S} x_i$, then we have
\begin{align*}
\Pr\left\{\biggm|\mu_S - \sum_{i\in S} y_i\biggm| >\epsilon \cdot \mu_S \right\} \leq 2e^{-\epsilon^2 \mu_S /3}.
\end{align*}

I need to find a similar bound for a slightly more complicated process:

At each step, pick a subset of numbers of size at most $d$, say $\{x_{i_1},\ldots,x_{i_d}\}$, and change their values to $\{x'_{i_1},\ldots,x'_{i_d}\}$ by either increasing all of these numbers or decreasing all of them. This is done in such a way that $0\leq x'_{i_j}\leq 1$ and $E[x'_{i_j}]=x_{i_j}$ for all $j$.

Can we get a similar result for this process too? For instance, is it possible to replace the right-hand side of the above bound with $2e^{-\epsilon^2 \mu/O(d)}$? Thank you very much.


texts:
In Razborov-Rudich's Natural Proofs paper, page 6, in the part they discuss that there are "strong lowerbounds proofs against monotone circuit models" and how they fit into the picture, there are the following sentences:

  Here the issue is not constructivity - the properties used in these proofs are all feasible - but that there appears to be no good formal analogue of the largeness condition. In particular, no one has formulated a workable definition of a "random monotone function."

Isn't it easy to distinguish the outputs of a monotone function from a random string?
Isn't the existence of strong lowerbounds telling us that there are no such things?

My question is:

  What do they mean by a workable definition of a "random monotone function"?


texts: Problem understanding "connectivity" characteristic for the $k$-connected subgraph problem

texts:
I am reading this article, and I am having trouble to understand the 11th definition (page 7) about the connectivity characteristic. I do understand the raw definitions, but have no idea what this gives my intuitively.

The definition:

  For each pair of distinct vertices v, u of H: let $Com_{H}(v, u)$ be the set of portal completions which augment H to a graph with k internally vertex-disjoint paths between v and u.
  For each vertex v of H, let $Path_{H}(v)$ be the set of pairs (U, Q) where U is a multiset of P(H) with vertex multiplicities bounded by from above by the vertex degrees in H and Q is a partial g-matching on the complete multigraph on P(H) with g(w) equal to the difference between the degree of w in UH and the multiplicity of w in U such that there are $|U|+|Q|$ internally vertex-disjoint paths in H connecting v with each copy a vertex in U, and connecting each pair of endpoints of each edge in Q, respectively.
  $Path_{H}$ is the set of all Q for which $(\phi, Q)$ is in $Path_{H}(v)$ for an arbitrary vertex v in P(H).
  We will call the triple ($Com_{H}(v, u)$, $Path_{H}(v)$, $Path_{H}$) the $connectivity\ characteristic$ of H.

Context: The paper presenta a PTAS for minimum-cost k-connected subgraph problem. This is done by dissecting the graph into smaller parts, brute-forcing a solution on the small parts, and then connecting them in a way that doesn't increase is stays a $(1+\epsilon)$-approximation. This connectivity characteristic is a property of the subgraphs that is maintained by the algorithm while augmenting the big graph from the smaller parts. A foot note at page 6 states that it models "missing" connectivity, that will be added later by the augmentation of the regions.
Note that there is also (m, r)-blue which is another property that should be maintained. Could be that only both give something useful.
The definition of an (m, r)-blue graph is at page 10. Mainly says that a facet is being crossed at portals, and not too often.

Could someone give me some intuitive explanation about what this characteristic is, and why its helpful?


texts: Knapsack problem with dependent weight and profits among the items

texts:
I'm working on a problem that may be reduced to the following variant of multiple knapsack problem:
Each knapsack has its own valuation function; an item brings different profit and weight to a specific knapsack. Also, the profit and weight of an item depend on the profit and weight that has been assigned to the knapsack.
For example, suppose two items $a$ and $b$ have profit $p_{ai}$ and $p_{bi}$ and weight $w_{ai}$ and $w_{bi}$ in the $i^{th}$knapsack. If the item $a$ is selected to the knapsack $i$, everything goes well. However, if both items are presented to knapsack $i$, the combined profit of $a$ and $b$ is not $p_{ai} + p_{bi}$ and instead be little smaller than that. The total weight of $a$ and $b$ is also larger than $w_{ai} + w_{bi}$. Though, we can know the value of each combination, it takes expensive computation overheads. This relationship is not limited between two items, but holds among all items, which means if a knapsack is assigned three items $a$, $b$ and $c$, its profit is not $p_{ai} + p_{bi} + p_{ci}$ or $Value({a, b}) + Value({a, c}) + Value({b, c})$ and its weight is not $w_{ai}+w_{bi} + w_{ci}$. As usual, we always want to maximize the total profit. Though, it seems like a variant of quadratic knapsack problem, the overhead to compute the additional profit for all subsets is too costly.
My question is, has there work been done on this variant of (multiple)knapsack problem? Are there any papers that I can read to better understand it? I am not very familiar with the literature of knapsack problems and have tried to search for this but still gets little useful.


texts: largest language class for which inclusion is decidable

texts:
am wondering what is the largest language class that is known for which set inclusion is decidable, ie a class such that if $A, B$ are in that class then $A \subset B$ is decidable.

am also interested in the same question for what were once called "GSMs", generalized sequential machines, or maybe more modernly, FSM "transducers", where if $f(x)$ is the transducer, $C \subset f(C)$, $C$ in the class.

(of course, the problem is also equivalent to determining whether the intersection of a complement is empty.)

[simply asking for the "largest known" language is a literature related question. however some kind of proof that there exists a "largest class" I believe is an open question. although, there might be a straightfwd argument of nonexistence via diagonalization...?]

unfortunately wikipedia does not have some of this basic info for major language classes. wonder if there is any table, paper, or reference esp online.

there is a nice table of decidability & undecidability of basic language questions in [1] but its quite dated at this point.

[1] Hopcroft/Ullman, Intro to Automata Theory, Languages & Computation, 1979


texts: Can Elementary Affine Logic be used as the core type system of a practical programming language?

texts:
Elementary Affine Logic is a type system which captures the class of λ-terms that can be reduced in elementary time. Moreover, EAL-typeable terms can be reduced using the abstract fragment of Lamping's algorithm, which is particularly interesting to me because I'm exploring the corresponding interaction combinators.

My question is, how can one make a practical programming language using EAL as the underlying type system? I.e., what kind of extensions (fix-points, polymorphism, dependent types, datatypes, etc.) could be made to the core type system without affecting that characteristic, and would such a language be usable in practice, or would it be somehow too restrictive for reasons I'm not aware?


texts:
In Proof and Types by Girard et alii. Section 7.4.2, I think that the authors want to show that:

(1) The set of functions definable in System T coincides with the set of
recursive functions whose termination is provable in Peano arithmetic

I don't understand the arguments given to support this thesis.

  In particular, if t is a closed term of type $Int \to Int$ of T, it
  induces a function $|t|:\mathbb{N} \to \mathbb{N}$ defined by:

  $|t|(n) = m$ iff $t \overline{n} \leadsto \overline{m}$ $[\ldots]$

  The functions $|t|$ are clearly calculable: the
  normalization algorithm gives $|t|(n)$ as a function of $n$. So those
  functions representable in T are recursive. Can we characterize the
  class of such functions?

This is how I read this parragraph:

Regarding calculability of $|t|$: using the iff one computes $|t|(n)$ by computing $t \overline{n} \leadsto \overline{m}$. Then $\overline{m}$ syntax can be more complex that an integer  and in order to obtain $m$ one has to rewrite it into a normal form (which should be an integer by the term's type).
Regarding recursivity: I believe that they stress that the normalization begins with term $t \overline{n}$ and thus $|t|$ is indirectly "recursive" in its argument.

The next parragraph seems to confirm this view:

  $[\ldots]$ Seen as a partial algorithm, $|t|$ amounts to looking for
  the normal form, and, in the case where this succeeds, writing it. The
  normalization theorem is thus a proof of program guaranteeing
  termination of all algorithms obtained from $T$.

From here I get the idea that every function written in $T$ is terminating. The next parragraph comes as a surprise though:

  Now, what are the mathematical principles necessary to prove the
  reducibility of a fixed term t?

  to be able to express the reducibility of t and of its subterms: one must be able to write a finite number of reducibilities, which can be
  done in Peano arithmetic (PA)
  to be able to reason by mathematical induction on this finite number of reduciblity predicates; that can again be done in PA, modulo some
  awful coding without significant interest (Godel numbering).

  Summing up, the termination is provable in arithmetic: we say that
  $|t|$ is provably total in PA.

If every function was terminating in System T why would one want to prove in PA specifically?

My question is if you can solve the doubts I presented or if you have your own way of showing statement (1)?


texts: Complexity of graph isomorphism with properly colored edges (ref. request)

texts:
An edge-colored graph $G$ is a graph whose edges are labeled with a color (generally represented by an integer). Such a coloring is proper if all adjacent edges in $G$ have different colors. I recently realized that isomorphism between two such graphs can be tested in polynomial time. The arguments are pretty simple and the question natural, so this fact should already be mentioned somewhere. However, I could not find it so far.

The arguments: Fix an arbitrary vertex $v_1$ in $G_1$. We will try to send it to every vertex $v_2$ of $G_2$ successively, until either a valid bijection is found (accept) or all the vertices of $G_2$ have been tried (reject). The key point is that once the selection of $v_2$ is made, no other choice remains to be done, because local constraints imposed by the colors recursively determine the remaining of the bijection. For instance, if $v_1$ shares an edge colored $c$ with vertex $u_1$, then this vertex must be sent to a vertex that shares an edge colored $c$ with $v_2$. This vertex (if any qualifies) must be unique due to the fact that the coloring is proper.

Has anyone seen such an observation somewhere or has an idea where to find it?


texts: A System for Visualizing Bibliography Information

texts:
I'm looking for a software for visualizing main trends in some field.
Specifically, I want it to build a graph of the field with vertexes representing papers and edges representing how close papers are (probably, based on number of co-citations).
It seems to be very useful in order to find important subfields (clusters in the graph) and important papers (centers of the clusters).


texts: Is there a method for proving non-regularity of string transformations?

texts:
There are a number of different models for defining transformations between languages. Finite state transducers and MSO-definable graph transformations over string graphs are the two that I am best acquainted with. We know that 2-way finite state transducers (which are more expressive than their 1-way counterparts) and MSO-definable string transformations capture the same set of transformations along with some other less well-known models that use combinators. This class of transformations is considered regular, and so it is easy to show then that a transformation is regular if you can provide a description of it with one of these models.

Is there a straight-forward way to say that a transformation is outside of this class? Something akin to the pumping lemma for regular languages or the Myhill-Nerode theorem but for string transformations is the sort of thing I am looking for.


texts: The Mobius function $\mu(n)$ is defined as $\mu(1)=1$, $\mu(n)=0$ if $n$ has a squared prime factor, and $\mu(p_1 \dots p_k)= (-1)^k$ if all the primes $p_1,\dots,p_k$ are different. Is it possible to compute $\mu(n)$ without computing the prime factorization of $n$?


texts: Algebraic topology for termination proofs

texts:
I'm reading about various ways in which termination proofs of software verifiers are built: ad-hoc methods that detect recursions, term-rewriting, synthesis of lexicographic orderings...
From the ad-hoc methods I came with the following intuitive idea. Is it possible to formalize termination with algebraic topology? The idea would be:

look at termination as the problem of finding loops in the code of the program.

look these loops as a fundamental group at some origin (a point in the source code)

test whether this fundamental group is simply connected (implying that this node is terminating)

Of course both problems are undecidable (the second one being testing the simple connectedness) but it seems to me theoretically feasible.
Has this been done before? You find it is not feasible?
Resources I find interesting (feel free to add)
Progress Measures and Finite Arguments for Infinite Computations, page 3.
Power domains and predicate transformers: A topological view (if I ever get access to it)
The topology of program termination.
Scott approach distance on metric spaces


texts: How hard is it to reduce termination to partial correctness?

texts:
If you are familiar with program verification you are likely to prefer reading the Question before the Background. If you are not familiar with program verification then you may still be able to answer this question, but you are likely to prefer reading the Background first.

Background

It is often stated that checking partial correctness is undecidable. For the sake of discussion, let's pick one very particular way of making this statement precise, in the style of Floyd--Hoare. A flowgraph is a digraph with a distinguished initial node from which all nodes are reachable. A program is a flowgraph whose nodes are commands. There are three types of commands (1) assumptions assume q, (2) assertions assert q, and (3) assignments v:=e. Here q is a fol (first-order logic) formula, e is a fol term, and v is a variable.

We say that a program is partially correct when there is a way to annotate each node x with a precondition a(x) and a postcondition b(x) such that (1) the precondition of the initial node is valid, (2) {a(x)} x {b(x)} holds for all commands x, and (3) (b(x) implies a(y)) is valid for all edges from x to y. Here the Hoare triples are defined as follows:

{p} assert q {r} means that (p implies (q and r)) is valid
{p} assume q {r} means that ((p and q) implies r) is valid
{p} v:=e {r} means that ((p with e substituted for v) implies r) is valid

Here's a hand-wavy argument of why checking this partial correctness is undecidable: Once you fill in some a(x) and some b(x) you need to check if some fol formulas are valid, and that is undecidable.

A typical way to encode termination in partial correctness is to add some special assertions that essentially say "since last time I was executed, there was progress towards termination." These progress assertions must be placed such that all infinite walks on the flowgraph (that start at the initial node) contain infinitely many progress assertions. To be more specific, let's say that progress assertions always have the form assert u < v, where u and v are positive integers, are preceded by the assignment u:=f, and are followed by the assignment v:=u. Here f is a variant function, u is its current value, and v is its former value. Now, since we talk about "positive integers" and we compare them, we need to ensure that a bit more than fol is available: Let's say Peano arithmetic is available. (I don't feel strongly about this choice. Feel free to disregard if convenient.) Of course, f may use any other functions and constants that are mentioned in the program. (Note that adding assumptions at the beginning of the program is equivalent to introducing non-logical axioms.)

Now, if the program with progress assertions is still partially correct, then we know that the original program terminates.

Question

Given a terminating program, it feels that coming up with variant functions for progress assertions is hard. But how hard? (I know that even with the huge background above, I still left this question sort of open-ended, or ill-defined, depending on how you want to look at it.)

To put it differently: I'm looking for a reference that formalizes the problem of reducing termination to partial correctness and then says something about its complexity. An answer that does all this would of course be welcome.


texts: Is there a non Turing-complete model of computation whose halting problem is undecidable?

texts:
I cannot think of any such model, maybe some form of typed lambda calculus? some elementary cellular automaton?

This would almost disprove Wolfram's "Principle of Computational Equivalence":

  Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication


texts: For a specific unbounded Turing machine, is its Halting problem undecidable?

texts:
The question is on the title.

To make it clearer, I state some facts. We all know that the Halting problem with  input is undecidable. It leads to, given a specific input (e.g. empty string), the corresponding Halting problem with  input is also undecidable. Moreover, given a time or space bounded Turing machine M, the Halting problem of that specific M is decidable (on input x, save all of the configurations of M on x to check if M loops on x).

From there, I naturally have this question. I believe the problem is undecidable (because, otherwise, there seems to be no way to compute if M loops or not). But I haven't proved it yet.


texts: What is the consequence if there are only polynomially many 'yes' classes of instances of a language that is polynomial time reducible from a problem equivalent to UnambiguousSAT (such as possibly unique subset sum)?


texts:
Are Ising spins scalar or operators? I am not a condensed matter physicist hence having some confusion. I have learnt about Ising models from adiabatic quantum algorithm papers. For example this presentation or this paper encodes their quantum adiabatic algorithm for an Ising model. In an Ising model the spins are $\pm 1$. In his original adiabatic quantum computation paper, Farhi didn't mention about Ising models. Moreover he explicitly used Pauli's spin matrices and not the  $\pm 1$ spins.

Can we use $\pm$ spins and Pauli's matrices interchangeability at least in the context of adiabatic quantum algorithms?


texts: What's new in purely functional data structures since Okasaki?

texts:
Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few:

IntMap (also invented by Okasaki in 1998, but not present in that book)
Finger trees (and their generalization over monoids)

There are also some interesting ways of implementing already known datastructures, such as using "nested types" or "generalized algebraic datatypes" to ensure tree invariants.

Which other new ideas have appeared since 1998 in this area?


texts: Non-uniform average-case complexity of NP

texts:
It is conjectured that NP-complete problems are hard not only in the worst case but also in the typical case. Formally, given a language $S \in \lbrace 0,1 \rbrace^*$ and for each $n$ a probability distribution $X_n$ on $\lbrace 0,1 \rbrace^n$, $(S, X)$ is called "hard in the typical case" when for any algorithm $A$ and polynomial $q(n)$, the probability $P_n$ that $A$ decides membership in $S$ correctly in time at most $q(n)$ for an $X_n$-random element of $\lbrace 0,1 \rbrace^n$ is s.t. $1-P_n$ decreases with $n$ slower than some polynomial. We henceforth restrict attention to $X_n$ that are polynomial-time-sampleable, that is, $X_n$ can be sampled by a random algorithm with time complexity polynomial in $n$. It can be show than there are problems $(S, X)$ such that

(i) $S \in NP$

(ii) For any $(T, Y)$ with $T \in NP$, $(T, Y)$ can be reduced to $(S, X)$ in an appropriate sense, in particular if $(S, X)$ is feasible (polynomial) in the typical case then $(T, Y)$ is feasible in the typical case

O. Goldreich calls such problems sampNP-complete. For most (all?) natural NP-complete problems $S$, we can find $X$ s.t. $(S, X)$ is sampNP-complete. It is conjectured that such problems are hard in the typical case. In particular, it is a necessary condition for existence of one-way functions

The question is how this theory is affected by introducing non-uniformity. For worst-case complexity, it is known that $NP \subset P/poly$ implies $PH=\Sigma_2$ which is considered unlikely. What about average-case complexity? That is, what evidence can be brought for/against the following statement:

  Given $(S, X)$ sampNP-complete, there exists a polynomial-size family of Boolean circuits $C_n$ s.t. $C_n$ decides membership in $S$ correctly except for a fraction of the inputs which diminishes faster than polynomially w.r.t. $X$

EDIT: After posting this question I noticed it is more or less the same as that question. However the answer accepted there seems to me somewhat unsatisfactory. That answer says that the non-degeneracy of the polynomial hierarchy is not known to imply typical-case hardness of $NP$. However it might be that we can get a stronger conclusion by making a stronger assumption e.g. something about the average-case complexity of problems on different levels of the polynomial hierarchy


texts: Decidability of equality between higher-kinded equirecursive types (or: between nonregular Böhm trees)

texts:
In §3 of Polytypic values possess polykinded types, Ralf Hinze described a calculus of types with higher-kinded recursive types. There is a fixed-point combinator $$\mu_\kappa : (\kappa \rightarrow \kappa) \rightarrow \kappa$$ for every kind $\kappa$. Furthermore, there is a convertibility rule $(\mu)$, which says recursive types and their expansions are interconvertible: $$\mu_\kappa t \leftrightarrow t\;(\mu_\kappa t)\qquad\qquad(\mu)$$ Together with the congruence convertibility rules, $(\mu)$ means that recursive types and their expansions are interchangeable in all contexts. In other words, the system has equirecursive types.

My question is: Can one decide whether two types in Hinze's system are interconvertible?

The question is related to the equality of Böhm trees; it seems two types are interconvertible iff their Böhm trees are equal. Gérard Huet* showed the decidability of equality between regular Böhm trees, i. e., those with a finite number of distinct subtrees. However, types in Hinze's system can have nonregular Böhm trees; the following type is an example (it is related to the Sequ datatype in Hinze's paper):

$$\lambda g.~\mu f.~\lambda a.~g~a~(f~(g~a~a))$$

Is anything known about the decidability of equality between nonregular Böhm trees?

Huet, Gérard. "Regular böhm trees." Mathematical Structures in Computer Science 8.06 (1998): 671-680.


texts: Is Deolalikar's 2010 proof that $P \ne NP$ correct?

texts:
There was recently a claimed proof that $P \ne NP$. Not long after its publication there were raised some issues with this proof.

So ... is the proof correct or not ? (Please only answer this if you have evidence ... this question might take some time until it's answered)


texts: Voronoi diagram in presence of polygonal obstacle

texts:
Suppose there is a set of convex polygons ($\mathbb{P}$) on the plane. For each convex polygon $P_i$ there is one "facility" $f_i$ placed on the boundary of $P_i$.

The distance between a point $p \in \mathbb{R}^2\setminus \mathbb{P}$ and a facility $f_i$ is the distance of the shortest path between $p$ and $f_i$ avoiding interiors of the convex polygons.

My question is: Is there a known algorithm to compute the voronoi diagram ($\mathbb{V}$) in such settings ? I found something similar in Aronov's paper which deals with geodesic voronoi diagrams inside a simple polygon. Since, the paper does not considers holes inside the polygon it does not solve my problem.

Edit: The problem I stated can also be formulated as follows: Consider a large rectangle ($R$) containing $\mathbb{P}$ as convex holes inside it. The point sites are placed on the boundary of the holes. Now the geodesic voronoi diagram would be same as $\mathbb{V}$ bounded by $R$.


texts: I am a junior in college who is very interested in doing some sort of REU/research internship in theoretical computer science this summer, as I would like to get research experience before potentially applying to grad school. However, I have not had much luck in finding many research opportunities. The most theoretical focused one I stumbled upon was at the Toyota Technological Institute at Chicago, but I want to apply to more than just one program, of course. If anyone has any advice or knows of any good research opportunities for an undergrad in theoretical computer science I would love to know, as I am beginning to have difficulty finding other options.


texts: How and How fast can we infer a logical formula that expresses a given graph in C$^2$( logic with 2 vars and counting quantifiers)?

texts:
In the following paper the author's claim that almost all graphs can be expressed in first order logic with counting quantifiers and two variables.
I would like to know, is there any algorithm that infers a C$^2$ representation of a graph ?
If there is then what is its time complexity ?
https://people.cs.umass.edu/~immerman/pub/canon.pdf


texts:
Let $F$ be a family of $d$-element subsets of a finite universe $U$ of objects.
A family $H$ of $k$-element subsets of $U$, with $1 \le k < d$, is a $(k,d)$-hitting-set of $F$ if for each $V \in F$ there exists at least one set $W \in H$ such that $W \subset V$.

Given a collection $F$ as above, the $(k,d)$-hitting-set problem is to find a smallest $(k,d)$-hitting-set $H$ for $F$.

When $k = 1$ we have the standard hitting-set problem, and there are lots of previous results for it.
I know of parameterized analyses for the case with $k = 1$ and $d \le 3$ (see Brankovic and Fernau, for example).

Does anyone know any results regarding the complexity or the hardness of approximation of the $(k,d)$-hitting-set problem with:

$k = 1$ and $d = 4$?
$d = 4$ and $1 < k < d$?
$1 \le k < d$ and $d$ arbitrary?


texts: Complexity of the $(3,2)_s$ SAT problem?

texts:
Let define the $(3,2)_s$ SAT problem : Given $F_3$, a satisfiable 3-CNF formula, and $F_2$, a 2-CNF formula ($F_3$ and $F_2$ are defined on the same variables). Is $F_3 \wedge F_2$ satisfiable?

What is the complexity of this problem ? (Has it been studied before ?)


texts:
A permutation phrase is an extension to the standard (E)BNF context free grammar definitions: a permutation phrase $\{ A_1, \dots, A_n \}$ contains $n$ productions (or equivalently, nonterminals) $A_1$ through $A_n$. At the position of the permutation phrase, we'd like to see every one of these productions exactly once, but we are not interested in the ordering of these nonterminals.

For example:

S <- X { A, B, C } Y

is equivalent to:

S <- X  A B C  Y
S <- X  A C B  Y
S <- X  B A C  Y
S <- X  B C A  Y
S <- X  C A B  Y
S <- X  C B A  Y

The concept seems to be introduced in "Extending context-free grammars with permutation phrases". Therein it is also described how to parse these phrases in linear time using an LL(1) parser.

The paper "Parsing permutation phrases" describes a method for parsing permutation phrases using parser combinators. These are the only two papers I've found that talk about permutation phrases and how to parse them.

Seeing that we can easily parse these kinds of permutation phrases with LL(1) based parsers, my guess would be that we can do the same with LR(1) style parsers. My question is therefore:

  Can a grammar containing permutation phrases be parsed in time linear in the input string size using LR(1) machinery while maintaining a reasonably sized table?

Permutation phrases do not extend the power of context-free languages: as in my example above one can simply enumerate all possible permutations. However, the grammar then explodes as the resulting grammar can be of size $O(|G|!)$. This allows linear time parsing, but the size of the grammar becomes way too large.

The above approach works for any parsing algorithm (although it is not useful), so maybe we can do better for specific algorithms. We can reduce the blowup to 'merely' exponential ($O(2^{|G|})$) by encoding the phrases into the LR table: we can have LR items encode which productions have yet to be seen, and therefore reduce the blowup to all subsets of the permutation phrases.

Although this is better, it is of course not good enough - having a permutation phrase of 30 items would make the grammar unusable. There is still one part of LR parsing we haven't touched yet, and that is the actual stack-based procedure used for parsing. I imagine storing counters on the stack may be able to solve the problem, but I'm not sure how to do that.

I'm currently implementing a parser generator, and in the problem domain permutation phrases would be a gift from heaven. As I'm using LR(1) machinery, the above question followed.


texts:
SHORT QUESTION: Is MAJ-3CNF a PP-complete problem under many-one reductions?

LONGER VERSION:
It is well-known that MAJSAT (deciding whether the majority of assignments of propositional sentence satisfy the sentence) is PP-complete under many-one reductions and #SAT is #P-complete under parsimonious reductions. It is also apparent that #3CNF (that is, #SAT restricted to 3-CNF formulas) is #P-complete, because the Cook-Levin reduction is parsimonious and produces a 3-CNF (this reduction is actually used in Papadimitriou's book to show #P-completeness of #SAT).

It seems that a similar argument should prove that MAJ-3CNF is PP-complete under many-one reductions (MAJ-kCNF is MAJSAT restricted to kCNF formulas; that is each clause has k literals).

However, in a presentation by Bailey, Dalmau and Kolaitis, "Phase Transitions of PP-Complete Satisfiability Problems", the authors mention that "MAJ3SAT is not known to be PP-Complete" (presentation at https://users.soe.ucsc.edu/~kolaitis/talks/ppphase4.ppt). This sentence does not seem to appear in their related papers, only in their presentations.

Questions: Can the proof that #3CNF is #P-complete be indeed adapted to prove that MAJ3CNF is PP-complete? Given the statement by Bailey et al., it seems not; if the proof does not carry, then: Is there a proof that MAJ-3CNF is PP-complete? If not, is there some intuition as to the difference between PP and #P with respect to this result?


texts: Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?

texts:
This question is on "Vertex Partitioning Problems" framework of Telle and Proskurowski.
For solving problems in parital $k$-trees (i.e., graphs of bounded treewidth), the "Vertex Partitioning Problems" framework of Telle and Proskurowski looks promising. This framework gives practical algorithms for some problems (as opposed to MSO). Given a graph $G$ and a $q\times q$ matrix $D$ each entry of which is a subset of $\{0,1,2,\dots\}$, the question "Does there exist a partition $V_1, V_2, \dots ,V_q$ of $V(G)$ such that $\forall x \in V_i,\; |N(x) \cap V_j| \in D(i,j)$" is a vertex partitioning problem.
Their paper (Algorithms for vertex partitioning problems on partial k-trees) claim that every vertex partitioning problem is solvable in time polynomial for partial $k$-trees (time complexity is like $\mathcal{O}(nq^{2(k+1)})$
My doubt is regarding the "cofinite" condition they use. Is this important? Doesn't that mean this method doesn't work (out of box) for distance-2 coloring, since for distance-2 coloring the matrix $D$ must consist of entries $\{0\}$ along (main) diagonal and entries $\{0,1\}$ for off-diagonal.
Note: They explicitly state that the method works for coloring. For coloring also, diagonal entries are same; May be main diagonal is a special case?
Thank you.