texts: In external memory, is grouping equal elements easier than sorting?

texts:
Sorting an array will put equal elements adjacent to each other. So, in no model of computation can grouping equal elements be harder than sorting. In the RAM model, grouping equal elements is $O(n)$ because you can accomplish it by putting everything into a hashmap that maps keys to lists of equal elements.

The external memory model of computation is one where for an input size $N$ that's stored in "external memory," you can fit $M$ elements inside cache, and can transfer $B$ elements from cache to external memory per one slow I/O operation. All computation has to be done in cache.

The fastest sort in external memory is generally accepted to be an $O(N \log N)$ mergesort, even when the position in the output can be computed directly from the keys without any comparison. A surprising result shown in [1] is that, for practical[2] values of $B$ and $M$, permuting the values in external memory based on indices that are already known is no faster than sorting them! (This is in sharp contrast to permutation in RAM, which is trivially $O(n)$.)

I think grouping equal elements might be easier than permuting, because there are many permutations that would group equal elements. In a sense, if there is one "easy permutation" that groups equal elements, the algorithm could give you that instead of being forced to give you a specific permutation that may be very hard. Is this so? If it is so, what algorithm is known that could do it?

[1] https://pdfs.semanticscholar.org/05f5/c5521c69a87ed2fc32521312d85aeb1da874.pdf

[2] This is actually not true for big (>4KB) elements on solid state drives, but it's commonly repeated and valid for many cases.


texts: arithmetic circuits for polynomials (updated)

texts:
I am concerned about the  following question, consider
$P_n(x)= \sum_{i=0}^n \frac{x^n}{n!}$

Is there a straight line program (or arithmetic circuits) of polynomial size (wrt $n$) for the  polynomial $P_{2^n}(x)$? The difficulty seems to lie in the factorial, as for example the polynomial $x^{2^n}$ has a polynomial size arithmetic circuit (by repeated squaring).

Sorry in my previous post I did not make the question clear, as it would become a very simple question.


texts: Abstract definition of universal computation

texts:
There are many universal computation systems. Turing machines, tag systems, rewrite systems, cellular automata to name just a few. The universality of a system is proved via reduction from a known universal (Turing-complete) model.

I am wondering if it is possible to define abstract conditions, that make each of the systems universal. For example, in definitions of algebraic structures, there are conditions (like: Closure, Associativity, etc.) that can be examined in a structure to determine if it is e.g. a group. There is no reduction from other structure, that is already known to be group.

Is it possible to define in similar way the universality? Are there any related works on the topic?


texts: On Boolean functions with a certain number of zeros

texts: Given boolean $f(\Bbb x)$, with $\Bbb x\in\{0,1\}^n$, what are good upper/lower bounds, in terms of $|f^{-1}(0)|$, for minimum $deg(p(\Bbb x))$ of a real polynomial satisfying $p(\Bbb x)=f(\Bbb x)$?


texts: Is there an expressiveness hierarchy for type systems?

texts:
Inspired by the extensive hierarchies present in complexity theory, I wondered if such hierarchies were also present for type systems. However, the two examples I've found so far are both more like checklists (with orthogonal features) rather than hierarchies (with successively more and more expressive type systems).

The two examples I have found are the Lambda cube and the concept of k-ranked polymorphism. The first one is a checklist with three options, the second is a real hierarchy (though k-ranked for specific values of k is uncommon I believe). All other type system features I know of are mostly orthogonal.

I'm interested in these concepts because I'm designing my own language and I'm very curious how it ranks among the currently existing type systems (my type system is somewhat unconventional, as far as I know).

I realise that the concept of 'expressiveness' might be a bit vague, which may explain why type systems seem like checklists to me.


texts: Is there any sparse language known to be in NPI under the $P \neq NP$ assumption ?

texts: I wonder to know wether there are sparse language (even constructed by delayed diagolanization) in NPI under the assumption that $P \neq NP$.


texts: Finding if an edge lies within a set of disjoint rectangles

texts:
I'm using a triangulation library to compute the Constrained Delaunay Triangulation of a set of rectangles within some large boundary. The algorithm returns all the edges, but also adds edges inside of the rectangles that define the constraints. I want to be able to find if an edge lies inside of a rectangle in O(1) time.

Here's a more general description of the problem I want to solve. Given a set of nonoverlapping rectangles (the borders of the rectangles may touch) and an edge e with endpoints (x1,y1) and (x2, y2), find in O(1) time if e lies within any of the rectangles (including the border).


texts: Searching for the first item satisfying property with penalty for every test

texts:
The problem in terms of a step function on integers: A step function of integers is $0$ until $s$ (the "item" in question) and then $1$. That is, $s$ is the first integer that satisfies the property $f(s) = 1$. The only way to find out the function's value $f(x)$ is to run a test to evaluate it, where each test has a penalty $p(x)$. Given a range $[a,b]$ in which the step is known to occur, find the stepping point $s$ with minimal total penalty.

In the case I'm interested in, $p(x) = x$.

If $p(x)$ is just a constant, then binary search is the solution (I think?).

Background: There is a process that takes X minutes before a certain event occurs, always at the same time, but this time is unknown. I need to find this time. To check, start the process, wait X minutes and then run a test to find out if the event happened or not. After testing, the process restarts (so you can't just test every minute to find out the minimum time).

Edit: I forgot to mention that for simplicity's sake the distribution of $s$ is uniform in $[a,b]$, that is $P(x=s, x \in [a,b]) = 1/(b-a+1)$. A more realistic distribution in my actual problem is monotonically increasing, for example $P(x) = 2x/(b-a+1)^2$.

Update: usul's answer (with a minor tweak) describes how to calculate the value which needs minimizing, which is the expected cost given a penalty function and the probability distribution of the target value.

The question still stands: which algorithm actually minimizes that value in the case $p(x)=x$ and the two distributions discussed above (uniform and increasing)? More generally - what's an algorithm that takes the penalty function and always yields the minimum expected cost?


texts:
I have a finite graph with vertices $V$.

The sets $A_i, i=1,\ldots,N$ are non-empty disjoint subsets of $V$.

I want to find out if there is some way of selecting $a_i, i=1,\ldots,N$ such that

$a_i \in A_i$ for all $i$.
For any $i$ and $j$ such that $i\ne j$ there is no edge connecting
$a_i$ and $a_j$ in the given graph

I know that I can set this up as a boolean satisfiability problem. But I was wondering if there is anything in the structure of this particular problem which will allow for a more efficient approach?


texts: Optimization Problem on a Directed Graph

texts:
I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For each node we can compute the "activation value" $a_i$ as a sum of the activation values of the selected predecessor nodes, i.e.:
$$a_i = \sum_{j \in P(i)}x_{ji}a_{j}$$
where $x_{ij} \in \{0,1\}$ are edge selector variables and $P(i)$ is the set of predecessor nodes of $i$. The optimization objective is for each node in the graph to select a set of incoming edges with minimal cost that "activate" that node:

$$\underset{x}{\text{argmin  }}\sum_{i} \sum_{j \in P(i)} a_ix_{ji}$$
$$\text{  such that  }  \sum_{j \in P(i)}x_{ji}a_{j}\ge v_i, \forall{i}$$

We can assume that there exist some leaf nodes in the graph whose activation value is 1, and that each node in the graph can be activated for a large enough subset of incoming edges.

If $G$ is a DAG, then we can solve this with dynamic programming, but I can't seem to figure out if there is a way to do this on a general DG, or if its NP hard.

Any pointers are appreciated. Thanks a lot.


texts: Matrix vector multiplication algorithm using minimal number of additions

texts:
Consider the following problem:

  Given a matrix $M$
  we want to optimize the number of additions in
  the multiplication algorithm for computing $v \mapsto Mv$.

I find this problem interesting because of its ties with
the complexity of matrix multiplication
(this problem is a restricted version of matrix multiplication).

What is know about this problem?

Is there any interesting results
relating this problem to the complexity of matrix multiplication problem?

The answer to the problem seems to involve
finding circuits with only addition gates.
What if we allow subtraction gates?

I am looking for reductions between this problem and other problems.

Motivated by

Automated optimization of 0-1 matrix vector multiplication
What are the relationships between those hypotheses in Fine-Grained Complexity Theory?


texts:
What's the lower-bound of the decision problem that decides:

Whether there is at least one element A[i] such that A[i] = i in a sorted array A of non-negtive integers? (An example is A = {0,1,1,3,4,4,5}.)

Is there any sub-linear deterministic algorithm can solve the problem?


texts: How do conference proceedings add to academic prestige?

texts:
I come from mathematics and, for whatever reason, am trying to publish in theoretical computer science. I'm still trying to understand the role of conference proceedings, and I have two specific question about them. I have tried to phrase the questions so that the analogous questions in mathematics would not be opinion based; if you think they are opinion based here then that is interesting in an of itself, so I would be grateful if you could comment to explain this!

In maths, a common marker of academic prestige is the specific journals someone's articles appear in, while I understand in TCS conference proceedings are more important.

  Are some conferences better thought of than others? If not, then how do conference proceedings add to prestige?

In maths, there are four un-disputed "top" journals (Acta Mathematica, Annals of Mathematics, Inventiones Mathematicae, Journal of the American Mathematical Society), and then there is a large second tier of world-class journals which is too large to mention here and varies wildly between different areas of mathematics. Getting a single paper in one of these four journals is a fast track to a permanent job.

  Are there a small number of top, world-class conferences where getting an article in the proceedings stands out like a gold star? If so, what are they?

Any suggestions for further reading is also appreciated :-)


texts: Asymptotic time required to simulate a Turing machine M for k steps

texts:
Problem: Given an encoding of a Turing machine M and a natural number k as input, find the output of M (given a blank tape) after k steps.

Wikipedia's page on EXPTIME-complete says it takes O(k) time but the page on universal Turing machines says O(k log k) on a multitape machine which only implies a single tape machine might do even worse.

Am I mixing things up? What is the best known bound for the given problem? Is it provably optimal? If not, what is the best bound that probably cannot be beaten?

Thanks for clearing this long standing doubt


texts:
The theory of cluster-state computation is well-established by now, showing that any BQP circuit can be modified so it uses only single qubit quantum gates, possibly classically controlled, provided ample supply of a state known as the "cluster state" - which is a simple to produce stablizer state.

My question is: is a similar notion known for quantum verification - i.e.
can one replace QMA circuits with classically controlled 1-qubit gates, possibly using some "special state"?
At least initially, I'm unclear on why the cluster state can even work in this case.


texts:
In distributed version control systems (such a Mercurial and Git) there is a need to efficiently compare directed acyclic graphs (DAGs). I'm a Mercurial developer, and we would be very interested in hearing about theoretical work that discuss the time- and network-complexity of comparing two DAGs.

The DAGs in question are formed by the revisions recorded. Revisions are uniquely identified by a hash value. Each revisions depend on zero (initial commit), one (normal commit) or more (merge commit) of the previous revisions. Here is an example where revisions a to e were made one after each other:

a --- b --- c --- d --- e

The graph comparison comes into the picture when someone has only part of the history and wants to retrieve the missing part. Imagine I had a to c and made x and y based on c:

a --- b --- c --- x --- y

In Mercurial, I would do hg pull and download d and e:

a --- b --- c --- x --- y
              \
                d --- e

The goal is to identify d and e efficiently when the graph has many (say, more than 100,000) nodes. Efficiency concerns both

network complexity: the number of bytes transferred and the number of network round-trips needed
time complexity: the amount of computation done by the two servers that exchange changesets

Typical graphs will be narrow with few parallel tracks like above. There will also typically be only a handful of leaf nodes (we call them heads in Mercurial) like e and y above. Finally, when a central server is used, the client will often have a couple of changesets that are not on the server, while the server can have 100+ new changesets for the clients, depending on who long ago the client last pulled from the server. An asymmetric solution is preferred: a centralized server should do little computation in comparison to its clients.


texts:
To put it straight - are qubits fermions, bosons or else?

For example, the Bell states that are frequently used in quantum computations have different symmetry (00 + 11 is symmetric, 10 - 01 is antisymmetric). Indistinguishable physical particles in a real world are either bosons (symmetric) or fermions (antisymmetric), not both.

Should we take into account permutation symmetry while discussing multiple qubit states?


texts:
I have written the following answer as an attempt to prove a variation of Sispser-Lautmann theorem, but it was rejected without any comments. I would appreciate if anyone can find the flaws in this attempt of proof.
The variation is the following: given a language $A$ in $BPP$ that has a probabilistic turing machine running in polynomial time $t(n)$, with an error at most $\frac{1}{10t(n)}$, prove that $A \in \Sigma_2^p$.

My outline for the proof was the following:

From the amplification lemma of $BPP$ (meanning running poly-many times, choosing majority, and using chernoff's bound to bound the error), we can without loss of generality assume there is a probabilistic machine $M$ for $A$ that run in polynomial time $q(n)$ and with error at most $2^{-p(n)}$
When fixing the coins that $M$ uses, $M$ is deterministic, and there is a SAT formula that is satisfied if only if M accepts for the same coins and input.
There is a $\Sigma_2$-sat formula that is equivalent to $M$: there exist $p(n)$ coins that for any other sequence of coins $M$ accepts.

Thanks


texts: whether two sets of stabilizer generators are related by a Clifford circuit

texts: I have two stabilizer models each specified with a given set of generators. Let's call the two generating sets $S_1$ and $S_2$. By stabilizer model, I mean putting the generators on unit cells of a lattice. I would like to check whether stabilizer generator sets $S_1$ and $S_2$ are related via a Clifford circuit. Is this possible to check efficiently? Can one put constraints of spatial locality on the Clifford circuit and answer the same question?


texts:
Edit: there is now a follow-up question related to this post.

Definitions

Let $c$ and $k$ be integers. We use the notation $[i] = \{1,2,...,i\}$.

A $c \times c$ matrix $M = (m_{i,j})$ is said to be a $c$-to-$k$ colouring matrix if the following holds:

we have $m_{i,j} \in [k]$ for all $i, j \in [c]$,
for all $i,j,\ell \in [c]$ with $i \ne j$ and $j \ne \ell$ we have $m_{i,j} \ne m_{j,\ell}$.

We write $c \leadsto k$ if there exists a $c$-to-$k$ colouring matrix.

Note that the diagonal elements are irrelevant; we are only interested in the non-diagonal elements of $M$.

The following alternative perspective may be helpful. Let $R(M,\ell) = \{ m_{\ell,i} : i \ne \ell \}$ be the set of non-diagonal elements in row $\ell$, and similarly let $C(M,\ell) = \{ m_{i,\ell} : i \ne \ell \}$ be the set of non-diagonal elements in column $\ell$. Now $M$ is a $c$-to-$k$ colouring matrix iff $$R(M,\ell) \subseteq [k], \quad C(M,\ell) \subseteq [k], \quad R(M,\ell) \cap C(M,\ell) = \emptyset$$ for all $\ell \in [c]$. That is, row $\ell$ and column $\ell$ must consist of distinct elements (except, of course, at the diagonal).

It may or may not be helpful to try to interpret $M$ as a special kind of hash function from $[c]^2$ to $[k]$.

Examples

Here is a $6$-to-$4$ colouring matrix: $$\begin{bmatrix}
-&2&2&1&1&1\\
3&-&3&1&1&1\\
4&4&-&1&1&1\\
3&2&2&-&3&2\\
4&2&2&4&-&2\\
3&4&3&4&3&-
\end{bmatrix}.$$

In general, it is known that for any $n \ge 2$ we have $${2n \choose n} \leadsto 2n.$$ For example, $20 \leadsto 6$ and $6 \leadsto 4$. To see this, we can use the following construction (e.g., Naor & Stockmeyer 1995).

Let $c = {2n \choose n}$ and let $k = 2n$. Let $f$ be a bijection from $[c]$ to the set of all $n$-subsets of $[2n]$, that is, $f(i) \subseteq [2n]$ and $|f(i)| = n$ for all $i$. For each $i,j \in [c]$ with $i \ne j$, choose arbitrarily $$m_{i,j} \in f(i) \setminus f(j).$$

Note that $f(j) \setminus f(i) \ne \emptyset$. It is straightforward to verify that the construction is indeed a colouring matrix; in particular, we have $R(M,\ell) = f(\ell)$ and $C(M,\ell) = [k] \setminus f(\ell)$.

Question

Is the above construction optimal? Put otherwise, do we have $${2n \choose n} + 1 \leadsto 2n$$ for any $n \ge 2$?

It is well-known that the above construction is asymptotically tight; necessarily $k = \Omega(\log c)$. This follows, e.g., from Linial's (1992) result or from a straightforward application of Ramsey theory. But to me it is not clear whether the construction is also tight up to constants. Some numerical experiments suggest that the above construction might be optimal.

Motivation

The question is related to the existence of fast distributed algorithms for graph colouring. For example, assume that we are given a directed tree (all edges oriented towards a root node), and assume that we are given a proper $c$-colouring of the tree. Now there is a distributed algorithm that computes a proper $k$ colouring of the tree in $1$ synchronous communication round if and only if $c \leadsto k$.


texts: Is #PE (#P Easy) closed under decrement?

texts:
Given a function $f : \Sigma^* \to \mathbb{N}$, define function $f_{-1}$ as: $f_{-1}(x) = f(x) - 1$ if $f(x) > 0$, and $f_{-1}(x) = 0$ otherwise. Moreover, say that a class ${\cal C}$ of functions is closed under decrement if for every $f \in {\cal C}$, it holds that $f_{-1} \in {\cal C}$.

Define $\#\text{PE}$ [2,3] as the class of functions in $\#\text{P}$ with easy decision versions, that is, the class of functions $f \in \#\text{P}$ for which there exists a polynomial-time deterministic TM $M$ such that $L(M) = \{ x \in \Sigma^* \mid f(x) > 0 \}$. It was shown in [1] that if $\#\text{P}$ is closed under decrement, then $\text{NP} \subseteq \text{SPP}$. But the ideas in the proof of this result cannot be used to provide evidence that  $\#\text{PE}$ is not closed under decrement. So I was wondering what is known about this problem. Is $\#\text{PE}$ closed under decrement? Can at least one prove that if $f \in \#\text{PE}$, then $f_{-1} \in \#\text{P}$? Any help with this would be greatly appreciate it.

[1] Mitsunori Ogiwara, Lane A. Hemachandra: A Complexity Theory for Feasible Closure Properties. J. Comput. Syst. Sci. 46(3): 295-325 (1993)

[2] Aris Pagourtzis. On the complexity of Hard Counting Problems with Easy Decision Version. In Proceedings of the 3rd Panhellenic Logic Symposium,  2001.

[3] Aris Pagourtzis, Stathis Zachos: The Complexity of Counting Functions with Easy Decision Version. MFCS 2006: 741-752


texts: We work in homotopy type theory. Can there be a type $A:U_m$ and a map $f:A\to U_n$ for some $n\geq m$ such that the type $\prod_{T:U_n} \|\mathrm{fib}_f(T)\|$ is inhabited?


texts: Formalization of Interval Newton methods in a proof assistant or theorem prover

texts:
I am undertaking the task of formalizing Interval Newton Methods in Isabelle. To the best of my knowledge this hasn't been formalized in other proof assistants or theorem provers. However, I want to confirm this impression with you.

The methods I'm talking about are as described in Chapter 8 of Introduction to Interval Analysis. The idea would be to start verifying a one-dimensional version (reusing theories already present in Isabelle) and then extending it into a multivariate setting.

The most similar thing I have found come from ENS of Lyon where they have developed Gappa and produced this Phd thesis. But the first is a generic tool for floating points numbers and the second only deals with interval Newton methods collateraly.

Is there any reference you're aware of that provides a formalization of Interval Newton Methods in a proof assistant or theorem prover?


texts:
Thor Johnson, et al, in their paper: Directed Tree Width, introduced a definition for directed grid $J_k$, and they conjectured:

  $(5.1)$ For every integer $k$ there exists an integer $N$ such that every
  digraph with tree-width $N$ or more has a minor isomorphic to $J_k$.

And they continued by saying:

  We have convinced ourselves that $(5.1)$ holds for planar digraphs,
  but the general case is open.

And I'm looking for this unpublished paper (how they proved the conjecture for di-planar graphs), or related stuff in this case, actually how to use such a grid (I mean $J_k$).


texts: Listing Eulerian orienations with special properties

texts:
An orientation of a simple undirected graph is said to be Eulerian if every vertex has the same number of in-coming edges and out-going edges (i.e., in-degree($v$)=out-degree($v$) for all $v\in V(G)$). The following are equivalent for a connected graph $G$ (hence the name Eulerian orientation):

$G$ has an Eulerian orientation.
Eery vertex of $G$ has even degree.
$G$ is Eulerian  (i.e., it has a Euler circuit).

Let us focus on $2p$-regular graphs $G$ for the time being. In general, it is computationally hard to list all Eulerian orientations of $G$ (it is hard even to count all Eulerian orietations; but, sampling algorithm are avaiable).
Does the listing problem become easier if we demand the Eulerian orientation to satisfy some additional conditions?
Ideally, the conditions should not be too restrctive. Are the following conditions enough to make the listing problem tractable?

For every vertex $x$ of $G$, the set $N^+(x)$ of out-neigbours of $v$ is an indendent set in $G$.
For every pair of vertices $x,y$ of $G$ with a common out-neighbour (i.e., $N^+(x) \cap N^+(y)\neq \emptyset$), the set $N^+(x)\cup N^+(y)$ is an independent set in $G$.

Definition
$v \text{ is an out-neigbour of } x$ if $(x,v)$ is an arc in the oriented graph.
Disclaimer: This is a follow-up to an earlier question.


texts: What was the significance of Leslie Valiant's, "A Theory of the Learnable?"

texts: It seems like two of the main takeaways were that there is a natural limit to what computers can learn, and learning is bounded by polynomial algorithms. Why was his paper significant in the broader area of machine learning?


texts: Linearly independent Fourier coefficients

texts:
A basic property of vector spaces is that a vector space $V \subseteq \mathbb{F}_2^n$ of dimension $n-d$ can be characterized by $d$ linearly independent linear constraints - that is, there exist $d$ linearly independent vectors $w_1, \ldots, w_d \in \mathbb{F}_2^n$ that are orthogonal to $V$.

From a Fourier perspective, this is equivalent to saying that the indicator function $1_V$ of $V$ has $d$ linearly independent non-zero Fourier coefficients. Note that $1_V$ has $2^d$ non-zero Fourier coefficients in total, but only $d$ of them are linearly independent.

I am looking for an approximate version of this property of vector spaces. Specifically, I am looking for a statement of the following form:

Let $S \subseteq \mathbb{F}_2^n$ be of size $2^{n-d}$. Then, the indicator function $1_S$ has at most $d\cdot\log(1/\varepsilon)$ linearly independent Fourier coefficients whose absolute value is at least $\varepsilon$.

This question can be viewed from a "Structure vs. Randomness" perspective - Intuitively, such a claim says that every large set can be decomposed to a sum of a vector space and a small biased set. It is well known that every function $f:\mathbb{F}_2^n \to \mathbb{F}_2$ can be decomposed into a "linear part" of which has $\mathrm{poly}(1/\varepsilon)$ large Fourier coefficients, and a "pseudorandom part" that has small bias. My question asks whether the linear part has only a logarithmic number of linearly independent Fourier coefficients.


texts:
Let $\{0,1\}^{<\omega}$ denote the collection of finite binary sequences. By a hash function we mean a computable map $$h: \{0,1\}^{<\omega} \to \{0,1\}^n$$ for some fixed $n\in\omega$. Define $\text{Fib}(h) = \{h^{-1}(\{y\}) : y \in \{0,1\}^n\}$ to be the set of fibers of $h$. (That is, every element of $\text{Fib}(h)$ is the set of inputs being mapped to some fixed $y\in\{0,1\}^n$.)
It is clear that some elements of $\text{Fib}(h)$ will be infinite. For a hash function to be "fair" in some sense, we would like all fibers to be infinite. Now, given a hash function $h: \{0,1\}^{<\omega} \to \{0,1\}^n$, there is no procedure to determine whether all fibers are infinite.
Question. If we take $h$ to be one of the well-known hash functions (such as MD5, SHA-256, xxHash64,...), is it known whether all their fibers are infinite? Or, more basically, if these functions are surjective, that is, $\varnothing \notin\text{Fib}(h)$?


texts: One way communication complexity of multi exact matching

texts:
Let Alice have $n$ binary strings, each of length $n$ and let Bob have one binary string of length $n$.  Bob has to output $1$ if his string matches any of Alice's exactly and $0$ otherwise.

Clearly Alice can just run $n$ copies of a randomized one-way communication protocol to send a total of $O(n\log{n})$ bits to Bob which will let him output the correct answer with good probability.  Is this the best they can do?

  What is the one-way randomized communication complexity, assuming private randomness, of this
  problem?

My guess is that this is a known problem with existing tight bounds but I have not managed to find a reference yet.


texts: What is $\mathsf{NP}$ restricted to linear size witnesses?

texts:
This is related to the question Is the Witness Size of Membership for Every NP Language Already Known?

Some natural $\mathsf{NP}$(-complete) problems have linear length witnesses: a satisfying assignment for $SAT$, a sequence of vertices for $HAMPATH$, etc.

Consider the complexity class "$\mathsf{NP}$ restricted to linear length witnesses". Formal definition of this complexity class, call it $\mathcal{C}$: $L\in\mathcal{C}$ if $\exists L'\in\mathsf{P}\colon (x\in L \iff \exists w\in\{0, 1\}^{O(|x|)}\colon (x, w)\in L')$.

Is this a known complexity class? What are its properties?


texts: Can any program be implemented mechanically?

texts: Is it possible to build a single purpose (non Turing complete) mechanical implementation of say, Microsoft Word?  Is it possible to implement such things as iterators, first-order functions, the whole gamut of programming techniques?  Could gears and other mechanical parts represent data structures or even program objects?  At a certain point does this necessitate building a general purpose Turing-equivalent machine, or can each function, variable, etc, have its own unique mechanical construct in the form of flywheels and/or gears, ratchets, what have you?  In summary I wonder if any given piece of software on a standard computer could be compiled to a mechanical blueprint.


texts:
Let $0\le p\le 1$ and consider the decision problem

  CLIQUE$_p$
  Input: integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges
  Question: does $G$ contain a clique on at least $s$ vertices?

An instance of CLIQUE$_p$ contains a proportion $p$ out of all possible edges.  Clearly CLIQUE$_p$ is easy for some values of $p$.  CLIQUE$_0$ contains only completely disconnected graphs, and CLIQUE$_1$ contains complete graphs.  In either case, CLIQUE$_p$ can be decided in linear time.  On the other hand, for values of $p$ close to $1/2$, CLIQUE$_p$ is NP-hard by a reduction from CLIQUE itself: essentially, it is enough to take the disjoint union with the Turán graph $T(t,s-1)$.

My question:

  Is CLIQUE$_p$ either in PTIME or NP-complete for every value of $p$?  Or are there values of $p$ for which CLIQUE$_p$ has intermediate complexity (if P ≠ NP)?

This question arose from a related question for hypergraphs, but it seems interesting in its own right.


texts: Generalizing Haskell: could we replace Hask with Cat?

texts:
N.B. I asked the same question on Stack Overflow but it was suggested that it is too theoretical for this forum.

It is great that Haskell allows us to walk around in the category $Hask$. But sometimes I feel it is too tight. So I had this idea about a programming language that would allow us to move around in the category $Cat$ of small categories, where categories would be types and functors from categories $C$ to $D$ would be functions of type $C \to D$. At first it seemed a crazy idea, but I found an article by Glynn Winskel and his student Mario Jose Cáccamo about such calculus! However it is limited to a fragment of $Cat$. Do you think that it would be possible to extend Haskell in this spirit, i.e., instead of working in the category $Hask$, it would work in the category (or better, 2-category) $Cat$? Are you aware of any calculus similar to the one by Cáccamo and Winskel?

http://www.brics.dk/RS/01/27/


texts: Is minimax problem NP-Hard when the inner problem is NP-Hard ?

texts:
Consider a minimax problem of the form:

$\min_{x\in X} \max_{u\in U} f(x,u)$

The outer problem $\min_{x\in X} f(x,u)$ for any given $u$ is polynomially solvable.

If the inner problem $\max_{u\in U} f(x,u)$ for any given $x$ is NP-Hard, is the entire problem also NP-Hard?


texts: Complexity of the directed Steiner tree problem on special graph classes

texts:
I am interested in the complexity of the directed Steiner tree problem: Given a weighted digraph $D=(V,E)$, a root $r\in V$ of $D$, and a set of terminals $T\subseteq V$. The objective is to find a minimum cost arborescence of $D$ rooted at $r$, in which there is a path from $r$ to each node in $T$.

Is a polynomial time algorithm known if the input is restricted to digraphs whose underlying undirected graph is a series-parallel graph (or equivalently is a $K_4$-free graph or is a partial $2$-tree or has treewidth at most $2$)?


texts: Finding k nearest neighbors for all points

texts:
If you have n points in 2d space, how quickly can you report the k nearest points to every point under Euclidean distance? If it helps speed things up we can ignore points that are more than some distance away as well so potentially return fewer than k. A randomized or approximate solution would also be interesting.

One solution is to build a kd tree and do an independent look up for every point. Is this as good as it gets?


texts:
I'm interested in permutations classes defined by one or several excluded patterns of length 4. In particular, the following classes seem interesting but not so-well studied algorithmically.

the skew-merged permutations consist of the permutations that can be partitioned in an increasing and a decreasing subsequence; their basis is $\{3412, 2143\}$.
the vexillary permutations have basis $\{2143\}$; they have been introduced by Lascoux and Schützenberger in connection with Schubert calculus ('Schubert polynomials and the Littlewood–Richardson rule', Letters in Mathematical Physics 10(2), 111-124).

By the basis definition, it is immediate that a permutation $\pi$ is skew-merged iff both $\pi$ and $\pi^r$ are vexillary; this suggests some possible link between these two classes. I am interested in the following algorithmic questions:

Are there linear-time recognition algorithms for these classes? By the previous remark, an algorithm for class 2 would immediately yield an algorithm for class 1, although I suspect a more direct algorithm to exist in that case.
What is the complexity of the subpattern problem for two skew-merged or two vexillary permutations? The subpattern problem is known to be polynomial for separable and 2-increasing permutations, and these classes seem the next to study.


texts:
It is my first question on this site. I am taking a master's course on theory of computation. How you would explain P = NP problem to a 10 year old child and why it has such a monetary reward on it?

Your take?

I will update the question as my head gets clear about it.


texts: Ranking problem (single instance before others)

texts:
Suppose I am trying to learn function $f$ for a ranking-like objective:

The mapping: ranking one element at the top and the rest at the bottom.

More formally, suppose each input instance $I_i$ contains some items:
$$
I_i = \{ 1, 2, \cdots,  k\}
$$
The output of each instance is the variable $y_i$ ($y_i \in \{ 1, 2, \cdots, k \}$) is an index in the instance. So the input-output mapping is:
$$
I_i \rightarrow  y_i
$$

Learning the mapping:
Suppose we want to learn this mapping. For each index $j$ in $I_i$, we extract a feature vector $x_i^j$. So we will have a collection of vectors $x_i^1, ...., x_i^k$. The learning problem can be formulated as following:
$$
 \forall j\neq y_i \Rightarrow f(x_i^{y_i}) > f(x_i^{j})
$$

Now the question is, whether it is possible to reduce this problem to the existing well-known problems (e.g. linear classifiers $f(x) = w^T x$):

Here is a proposal:

Training: first, form the difference representations:

$$
\forall j \neq y_i \Rightarrow z_i^j \triangleq x_i^{y_i} - x_i^j
$$

I argue that we can use traditional linear-classifier frameworks to learn mappings from $z_i^j \rightarrow +1$:

$$
\max_f   \sum_{I_i} \sum_{j \in I_i} \ell ( f(z_i^j), +1)
$$

Prediction: given an instance $I_i$, select the best scoring index:
$$
\hat{y}_i = \arg\max_{j \in I_i} f(x^j_i)
$$

Please let me know if you have thoughts supporting/contradicting this proposal


texts: In Harper's PFPL (Ed. 2, top of page 8), this notation is used but I don't see a definition. What does $x.y$ mean?


texts: Is it possible to simulate a Linear Bounded Automata with logic circuits where links have min-max bounded delays? I need a reference in the literature

texts:
Consider the following building blocks, which can be used to construct a logic circuit:

basic logic gates {OR, AND, NOT} which have $n$ input and $m$ output pins, with $n,m\ge 1$.
generators of stable values {0,1}.
links, which can be used to join each other logic gates or generators.

Signal traversing a link have a propagation delay between a minimum $d_{min}$ and a maximum finite value $d_{max}$, with $0<d_{min}< d_{max}$. Different links may have different minimum and maximum values. When an input pin of a gate changes its value, the output value of the gate is instantaneously computed and, if the output value is changed, it is sent through all the output links.

In order to "execute" a logic circuit, it must be initialized.
At the initial state, each input and output pin of every gate in the circuit must be initialized to a certain value in such a way that for each link, its endpoints have the same value. As soon as the circuit is started:

each gate instantaneously computes its output value. If the output value is changed, it is sent through all the output links of the gate.

A logic circuit halts if, for each possible execution, (i) for each link its endpoints have the same value and (ii) for each gate, its output value is the correct output w.r.t. the current gate inputs. A logic circuit oscillates if, for each possible execution, it does not halt.
E.g., a NOT gate, whose pins are each other connected, oscillates since it never halts for each possible execution.

Problem. Given a Linear Bounded Automata $L$ (as defined here, page 6), is it possible to construct in polynomial time (w.r.t. the size of $L$) a logic circuit $C$ that simulates $L$ in the following way: if $L$ halts, then $C$  halts and if $L$ does not halt, then $C$ oscillates.

I think that I solved this problem with a long construction with a positive answer.
It seems that this is a problem that must have been studied in the past, but I cannot find any reference in the literature. I really would like to have a reference that answers this question. Can anyone help me?

Observe that, the problem is not trivial. In fact, as proved by Brzozowski and Ebergen, if $d_{max}$ is allowed to be infinite, it is not possible to build any interesting memory logic structures (e.g., flip-flops, muller c-element, linear bounded automata,$\dots$).


texts: An algorithm to compute the number of paths of length at most k

texts:
So I had to answer the following question:

Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, but $k$ is. In fact, we may even be interested in calculating this number modulo $n \in \mathbb{N}$.

If the question had been "of length exactly $k$", then the well known way is to take $A$ the adjacency matrix of $G$, and compute $A^k_{i, j}$. Since this can be done using exponentiation by squaring, we get $O(n^\omega \log n)$, where $\omega$ is the exponent of matrix multiplication.

In this case, the number I'm after is $\displaystyle \left(\sum_{r = 1}^k A^r\right)_{i, j}$. If these were numbers, or we knew that $A - I$ was invertible, we could compute the equivalent expression $\displaystyle \frac{A^{k + 1} - I}{A - I}$. In general, however, we do not know this, and we cannot invert $A - I$.

With that introduction, the idea of the algorithm is as follows:

Using the fact that $A^1 + A^2 + ... + A^k = T + A^{\lfloor\frac{k}{2}\rfloor} \cdot T$, where $T = A^1 + A^2 + ... + A^{\lfloor\frac{k}{2}\rfloor}$, plus $A^k$ if $k$ is odd. To avoid exponentiation $A$ each time, we maintain the invariant that after calling $F(t)$, $A$ is now $A^t$. Since we make at most three multiplications, and decrease $k$ by half each time, we again make $O(n^\omega\log n)$ operations. If we are interested in this number modulo $n$, even better, since these multiplications can all be done modulo $n$.

Code:

A a global matrix, mutable input.
T a global matrix, output.
F(k):
  If k == 0:
    T := I.
    Return.
  If k == 1:
    T := A.
    Return.
  k' := floor(k / 2).
  F(k').
  T := T + A * T.
  A := A * A.
  If k == 1 (mod 2):
    A := A * A'.
    T := T + A.

A' := A.
F(k).

I feel this is a ridiculously simple algorithm, but I've failed to find any references to it. Does this technique have a name? I'm almost certain it must be well known!


texts: The Relationship between P^NP and the Permanent

texts:
In the lecture notes Introduction to Complexity Theory by Goldreich, there is a section called "How close is $\#P$ is to $NP$". It is stated there that a $P^{NP}$ machine would approximate $\#P$ in random polynomial time. In fact I interpret this random approximation as a $FPRAS$ for any function in $\#P$.

Now in the seminal paper: M. Jerrum, A. Sinclair, and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries (JACM version), on page 31, there is an binary search algorithm which takes an $FPRAS$ for the Permanent to a $BPP$ algorithm for the Permanent.

Taking both algorithms together, this suggest that one could exponential approximation with high probability the Permanent leading to $P^{NP} \ge \#P$.

This clearly cannot be right! So the question is what mistake have I made?

My apologies if this question is stupid.


texts: BWT: is it possible to predict the next character in a sequence?

texts:
A very simple questions. Let B be the BWT (Burrows–Wheeler transform) of a string S. My question is, due to  "grouping" of consecutive characters in BWT, is it possible to somehow know the number of equal characters that follow given the first character of its kind (or at least some lower bound on the number of such characters). So let say B=...caaaaabaccccccacc... then, is it possible to know that after the first a there will be at least 2 consecutive a's or maybe the exact number of a's that follow?

Or alternatively one can pose a complementary question, a flip side of the above question (I write the question in order to better describe the problem):

Is there a better way to find breaks in BWT aside from checking each character and comparing it with the previous one. That is, let say I want to locate "ab" break. I would need to go from left to right and compare second character with the first one and then third with the second and so on until I find out where the pair mismatches. Is there a way to check every second character and come to the same result, because if this is possible then there exist a lower bound on the number of same consecutive characters (which is 2)?


texts: A partition problem with order constraints

texts:
In the OrderedPartition problem, the input is two sequences of $n$ positive integers, $(a_i)_{i\in [n]}$ and $(b_i)_{i\in [n]}$.
The output is a partition of the indices $[n]$ into two disjoint subsets, $I$ and $J$, such that:

$\sum_{i\in I} a_i = \sum_{j\in J} a_i$
For all $i\in I$ and for all $j\in J$: $b_i\leq b_j$.

In other words, we have to first order the indices on a line such that the $b_i$ are weakly increasing, and then cut the line such that the sum of the $a_i$ in both sides is the same.

If all $b_i$ are the same, then condition 2 is irrelevant and we have an instance of the NP-hard Partition problem.
On the other hand, if all $b_i$ are different, then condition 2 imposes a single ordering on the indices, so there are only $n-1$ options to check, and the problem becomes polynomial. What happens in between these cases?

To formalize the question, define by OrderedPartition[n,d], for $1\leq d\leq n$,
the problem restricted to instances of size $n$, in which the largest subset of identical $b_i$-s is of size $d$. So the easy case,  when all $b_i$-s are different, is OrderedPartition[n,1], and the hard case, when all $b_i$-s are identical, is OrderedPartition[n,n].

More generally, For any $n$ and $d$, in any OrderedPartition[n,d] instance, the number of possible partitions respecting condition 2 is $O(n 2^d)$. Hence, if $d\in O(\log{n})$, then OrderedPartition[n,d] is still polynomial in $n$.

On the other hand, for any $n$ and $d$, we can reduce from a Partition problem with $d$ integers to OrderedPartition[n,d]. Let $p_1,\ldots,p_d$ be an instance of Partition. Define an instance of OrderedPartition[n,d] by:

For each $i\in \{1,\ldots,d\}$, let $a_i := 2n\cdot p_i$ and $b_i := 1$.
For each $i\in \{d+1,\ldots,n\}$, let $a_i := 1$ and $b_i := i$
[if $n-d$ is odd, make $a_n:=2$ such that the sum will be even].

Hence, if $d\in\Omega(n^{1/k})$, for any integer $k\geq 1$, then OrderedPartition[n,d] is NP-hard.

QUESTION: What happens in the intermediate cases, in which $d$ is super-logarithmic but sub-polynomial in $n$?


texts: Complexity of a GLR parser on an ambiguous grammar

texts:
Let's consider the following expression grammar that is ambiguous:

$E ::= E + E~|~a$

Although GLR parsing (recognition actually, I'm not interested in parse tree creation)
is worst case $O(n^3)$, but how does a GLR parser behaves on this grammar that is
not worst-case?

I suspect the complexity is $O(n^2)$ or close to it. Can anyone reason about the
complexity of this grammar in a generalized setting like GLR that explores all the paths?


texts: Let $P$ be a prime. Given a number $a$, what is the computational complexity in establishing if $a$ is a cubic or higher order residue modulo $P$? Are there any good algorithms?


texts:
Generally, low density parity codes are decoded using sum product decoder (also known as decoding under belief propagation). Such codes are usually decoded nicely if there are no short length cycles in tanner graph, in particular length 4 cycles are to be avoided. Naturally, this puts some bound on column weight in such a parity matrix. What is the general column weight $t$ that is allowed (in terms of code dimensions $k,n$) so that there are no 4-cycles?

To state it formally

given n and k what is maximum value of $t$ for which tanner graph (bipartite t regular) has no 4 cycle?


texts: Widest path between s and t with additional constraints

texts:
Given a directed graph G and vertices s and t, the maximum capacity path between s and t is the path for which the minimum edge on the path is maximum, among all such s-t paths. Now I can use a modified Dijkstra's single-source shortest path algorithm to find a single maximum capacity path. But suppose, among all such maximum capacity paths, I want the one with the maximum capacity between all pairs of vertices on the path. Does anyone know a reference for this? I use the following modification of Dijkstra's:

ModifiedDijkstra(G,s)
for all v in G
    d(v) -> -1
    pred(v) -> null

d(s)-> infinity
Q -> V[G] // enqueue all the vertices in G.

while Q is not empty
    u->EXTRACT_MAX(Q)
    for each v in Adj(u)
        if d(v)<min(c(u,v),d(u))        // d(v)=max(d(v),min(d(u),c(u,v)))
            d(v)=min(c(u,v),d(u))
            pred(v)=u

Note that the answer I am looking for is a specific maximum capacity path (of many). For example for the directed graph G=({a,b,c,d,e},{(a,b),(b,c),(a,c),(c,d),(c,e),(d,e)}) with capacities c(a,b)=10,c(b,c)=10,c(a,c)=5,c(c,d)=20,c(c,e)=11,c(d,e)=15. Maximum capacity paths from a to e can be abce or abcde but I need abcde as answer as it is fattest from c to e, i.e. maximum capacity from c to e on abcde is 15 as opposed to 11 on abce.

Update: In practice all my edge weights are floating point numbers and guaranteed to be unique (say). In that case, once I find a single max capacity path, I will fix the minimum weight edge (say (u,v)), and recurse to find the max capacity path over the 2 subraphs, s...u and v....t. I will have to do this a maximum of E times so the time complexity of such an algorithm would be O(V^2E): with a naive implementation of Dijkstra's.


texts: Is "Is a permutation p an automorphism of a graph in my set?" NP-complete?

texts:
Suppose we have a set S of graphs (finite graphs, but an infinite number of them) and a group P of permutations that acts on S.

Instance: A permutation p in P.
Question: Does there exist a graph g in S that admits the automorphism p?

Is this problem NP-complete for some sets S?
It would be easy to check that a graph admits the permutation p (i.e. certificate).  Moreover, it's easy to find examples of S where the problem is not NP-complete, such as S being the set of complete graphs, whence the answer is always yes.
Note: I'm not really interested in what type of graphs they are; if you like they can be non-simple, directed, coloured, etc.
ADDENDUM:  The problem I'm currently looking at is classifying which isotopisms are autotopisms of Latin squares (which can also be interpreted as a special type of graph automorphism).
Given a Latin square L(i,j) we can construct a graph in the following way:

The vertex set is the set of cells (i,j) in the matrix and
There is an edge between distinct (i,j) and (i',j') whenever i=i' or j=j' or L(i,j)=L(i',j').

Such a graph is called a Latin square graph (see e.g. this article by Bailey and Cameron http://designtheory.org/library/encyc/topics/lsee.pdf).  We can interpret an autotopism of a Latin square as an automorphism of the Latin square graph.  So let S be the set of Latin square graphs formed from the Latin squares of order n.  So the question I'm interested in is:

Given a permutation p, is p an automorphism of one (or more) of the graphs in S?

My feeling is that it is a difficult question to answer in general -- I'm currently writing a 30+ page paper on the matter (with 2 co-authors).  Actually most of the time it is easy (most of the time it's "no"), but there are some difficult cases.
So I'm interested in finding decision problems that would be related to "symmetry classification".  They don't really need to be related to Latin squares, I'm just hoping to use these techniques to answer the question for Latin squares.


texts:
It's obvious that NP $\subseteq$ #P. How about #P $\subseteq$ PSPACE?

It strikes me as semi-obvious, since we can check whether an assignment (e.g. for SAT) is a solution in polynomial time (and hence space), and since each assignment can be checked separately, we can re-use the memory needed for this check, and thus use only a polynomial amount of space to check every assignment (plus a counter to track how many of the assignments were solutions).


texts: A question of relationships between #P and PSPACE

texts:
Let us assume there is some machine X that converts boolean formula to following form in polynomial time:

$$\Phi(x_1, x_2 .. x_m) = r_1(x_{i_1}, x_{j_1}, x_{k_1}) \land r_2(x_{i_2}, x_{j_2}, x_{k_2}) \ \land \ ... \ \land r_n(x_{i_n}, x_{j_n}, x_{k_n})$$

With following rules:

$r_l$ is given as it's table, example: $r_5 = 01101100$.
No different $r$ share all 3 same literals.
If $\Phi(... , x_i, x_j, x_k, ...) = 0$ for fixed $x_i, x_j, x_k$ then $r_l(..x_i..) = 0$.

What can this machine do after converting the formula? Really, if DTM has such formula as an input, following is true.

Solve SAT in $\mathcal{O}(1)$ time. It is a consequence of third rule. If $\Phi$ is not true for any arguments, it is not true for all $r$.
Solve TQBF in $\mathcal{O}(n)$ time. If all $r$ are true then $\Phi$ is true. Checking all $r$ takes linear time.
Return certificate for (TQ)BF in $\mathcal{O}(n)$ time. You can convert any $1$ bit to a set of 3 variables in $\mathcal{O}(1)$ time using Gray code.

What it can't do? It may be surprising.

It can't solve $\text{#SAT}$ in polynomial time. At least I don't know the algorithm.

Even if you know amount of solutions for all $r$ of non-quantified formula it doesn't give an answer.

Is this a proof that $PSPACE \subseteq \text{#}P$ ? And thus a much stronger theorem for $\text{#}P$ than Toda's.

How this will affect relationships between $PSPACE$ and $IP$ ?

It is known that $IP$ can solve exactly-k-#SAT. Can it answer if boolean formula has at least $k$ solutions?


texts:
A classic tiling problem with Wang tiles has the form:
Given $n$ tiles $T=\{t_1,...,t_n\}$ and some constraints
$H,V\subseteq T\times T$, is there
a way to tile a  $w\times h$ rectangular grid with $t_1$ at the SW corner, $t_n$ at the NE corner, and such that
any two horizontally or vertically adjacent tiles are in $H$ or $V$ respectively.

In this problem, $T,H,V$ are given and the question asks for the existence of some $w,h>0$ such that the rectangle can be tiled. This is undecidable and in fact $\Sigma_1^0$-complete.

A variant problem is the following: Given the same $T,H,V$, are there some dimensions $0<w<\ell$ and a sequence $d_1,...,d_\ell$ of tiles such that $d_1=t_1$, $d_\ell=t_n$,  $(d_i,d_{i+1})\in H$ for all $1\leq i\leq\ell-1$ and $(d_i,d_{i+w})\in V$ for all $1\leq i\leq \ell-w$. This is similar to the rectangular grid problem with $w$ being the width but the $H$ constraint wraps around the lines of the grid and the last line is maybe not full. The classic problem is easily reduced to the variant problem (use several copies of the original tiles so that positional information can be encoded and checked by the H and V constraints) so the variant problem is undecidable.

My question: is this variant mentioned in the literature? Where? If not, is there a similar problem mentioned somewhere?

Motivation: I am using the classic problem in a reduction showing that some (unrelated) problem is undecidable and the reduction will be simpler/more elegant if I start from the variant problem.


texts: Are there cascade decompositions of machines that are more general than finite automata?

texts:
The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn & Rhodes and has been explored relatively thoroughly. Krohn & Rhodes gave an algebraic presentation of this, and since then there have been more automata-theoretic treatments of the same idea such as this paper by Oded Maler.

Has the notion of cascade decomposition been extended to other types of machines such as finite-state transducers or push-down automata?


texts: Does a non-constructive proof of bounds of a computable asymptotic complexity, with impossible fix, exist?

texts: Does there exist an algorithm, about which a non-constructive $\omega$-consistent theory $A$ can prove that it has time complexity $O(f(n))$ where $n$ is some univariate function of the input, but there is no $\omega$-consistent constructive theory which proves this bound, and there is a constructive $\omega$-consistent theory $B$, which proves that the algorithm terminates? If it is, is there such a case for a polynomial-time algorithm?


texts: Complexity of Acyclic Hypergraph Isomorphism

texts:
It is well known that the graph isomorphism problem restricted on trees is much easier than the general case. It can be done in logarithmic space (Jenner B, Lange KJ, McKenzie P. "Tree isomorphism and some other complete problems for deterministic logspace." DIRO, Université de Montréal. 1997)

I would like to know whether something similar is known for the hypergraph isomorphism problem. In that case instead of trees we would have alpha-acyclic hypergraphs (see Characterization 15 on page 20 of https://arxiv.org/abs/1403.7076 for the definition of alpha acyclicity).

So, I am asking whether some non-trivial complexity bounds for the following problem are known:
Given two alpha acyclic hypergraphs G and H, is there an isomorphism between G and H?

Of course if something is known for other forms of acyclicity (e.g. beta or gamma) that would be interesting too.


texts: One-way randomized communication complexity of Greater-Than

texts:
Let $\mathrm{GT}_n:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ be the greater than function: $\mathrm{GT}_n(x,y)=1$ exactly when the positive integer whose binary representation is $x$ is greater than the positive integer whose binary representation is $y$.
It is well-known that the randomized communication complexity of $\mathrm{GT}_n$ is $\Theta(\log n)$. Several references claim that the randomized one-way communication complexity of $\mathrm{GT}_n$ is $\Theta(n)$, but I am unable to find a reference that actually contains a proof. It is easy to show a $\Omega(n/\log n)$ lower bound by a reduction from INDEX, and this is done in a paper by Kremer, Nisan, and Ron. They also claim that the proof of the $\Omega(n)$ lower bound appears in a paper by Miltersen, Nisan, Safra, and Wigderson. The latter paper uses a round-elimination lemma to show a $\frac{n^{1/k}}{120^k}$ lower bound on the $k$-round communication complexity of $\mathrm{GT}_n$ but never gets around to proving the base case somehow (see Theorem 14), and the base case is all I am asking for. They also claim this is an unpublished result of Yao, but as far as I know that result may never have been written down.
Surely at some point someone wrote down a proof of this lower bound? The closest I could find (with help from Clément Canonne) is this paper showing a lower bound on the quantum one-way communication complexity of $\mathrm{GT}_n$ and that just seems like an overkill.


texts: Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)

texts:
In a read-twice opposite CNF formula each variable appears twice, once positive and once negative.

I'm interested in the $\oplus\text{Rtw-Opp-CNF}$ problem, which consists in computing the parity of the number of satisfying assignments of a read-twice opposite CNF formula.

I was unable to find any reference about the complexity of such problem. The closest I was able to find is that the counting version $\#\text{Rtw-Opp-CNF}$ is $\#\text{P}$-complete (see section 6.3 in this paper).

Thanks in advance for your help.

Update 10th April 2016

In this paper, the $\oplus\text{Rtw-Opp-SAT}$ problem is shown to be $\oplus\text{P}$-complete, however the formula produced by reduction from $3\text{SAT}$ is not in CNF, and as soon as you try to convert it back into CNF you get a read-thrice formula.
The monotone version $\oplus\text{Rtw-Mon-CNF}$ is shown to be $\oplus\text{P}$-complete in this paper. In such paper, $\oplus\text{Rtw-Opp-CNF}$ is quickly mentioned at the end of section 4: Valiant says it is degenerate. It is not clear to me what being degenerate exactly means, nor what does it imply in terms of hardness.

Update 12th April 2016

It would be also very interesting to know if anyone has ever studied the complexity of the $\Delta\text{Rtw-Opp-CNF}$ problem. Given a read-twice opposite CNF formula, such problem asks to compute the difference between the number of satisfying assignments having an odd number of variables set to true and the number of satisfying assignments having an even number of variables set to true. I've not found any literature about it.

Update 29th May 2016

As pointed out by Emil Jeřábek in his comment, it is not true that Valiant said that the problem $\oplus\text{Rtw-Opp-CNF}$ is degenerate. He only said that a more restricted version of such problem, $\oplus\text{Pl-Rtw-Opp-3CNF}$, is degenerate. In the meanwhile, I continue to not know what degenerate exactly means, but at least now it seems clear that it is a synonym of lack of expressive power.


texts: Difference between a lossy encoder and a noisy channel in Information Theory

texts:
$S \to X \to Y \to \hat{S}$
$\text{source} \to \text{input} \to \text{output} \to \text{target}$
In information theory introductory books, an encoder is usually defined as a deterministic function $f:\mathcal{A}_\text{S} \to \mathcal{A}_\text{X}$ that converts a symbol from the alphabet of the source into a code (a symbol of the input of the channel). But it is not uncommon to see it defined as a stochastic map p(X|S). The channel is normally denoted as p(Y|X). In practice, is there any difference between an encoder and a channel? They are both transformations after all.

changed the title to reflect better what I mean.


texts: Theoretical guarantees for running times of belief propagation methods?

texts:
Belief propagation has been shown to be a very powerful method through research in probabilistic graphical models.

However, I don't know anything about BP that's comparable to MCMC methods where we can have fully polynomial randomized approximation schemes (FPRAS) for #P-complete problems.

Could someone point me to some references?


texts: Sieve Methods for Twin Primes - How to extract algorithm from formula

texts:
I am reading Cojocaru and Murty's Introduction to Sieve Methods and their Applications.  They wait until Chapter 5 to discuss the Sieve of Eratosthenes for finding primes - and their version of it is not very algorithmic.  She writes the inequality:

$$ \#\{ n \leq x : n \text{ not divisible by }p< z \} \approx
x \prod_{p < z}\left( 1 - \frac{1}{p} \right)  + O(...)$$

This makes sense the number of primes should be proportional to the residue classes which you left out upon sieving.  The textbook spends a lot of time estimating the main $\prod_{p < z}\left( 1 - \frac{1}{p} \right)$ and the error term $O(...)$.

How do we turn this equation into an algorithm?

Knowing the sieve algorithm already I remember to keep the smallest prime, and we sieve accordingly.

The other example in that chapter focuses on twin primes.   They given an approximation like so:

$$ \#\{ n \leq x : n \not \equiv 0,-2 \text{ for }p< z \} \approx
x \prod_{p < z}\left( 1 - \frac{2}{p} \right)  + O(...)$$

The book says, unfortunately, these are not the twin primes - I don't understand why.  It says the number of twin primes is less than

$$ \#\{ \text{ primes }p < z \}
+ \#\{ n \leq x : n \not \equiv 0,-2 \text{ for }p< z \} = \pi(z)+ x \prod_{p < z}\left( 1 - \frac{2}{p} \right) $$

If this were an algorithm I take it to mean you still have to compute primes up to a certain point, but not all of the primes up to $x$ in order to find the twin primes.

The book is not very clear in many places, so I have put in my - possibly wrong - interpretation of the equations in certain spots.  Maybe someone among you has the book or knows the Sieve of Eratoshenes very well.

My main complaint about the book is that it doesn't provide algorithms, just estimates.


texts: Are string palindrome questions practically interesting?

texts:
I've been reading Don Gusfield's "Algorithms on Strings, Trees, and Sequences", and quite a some chunk of the textbook concentrates on palindromic-related ideas.

I'm unsure as to whether this is because the question is purely theoretically interesting (in terms of finding good lower bounds), or there are practical use cases for this (in terms of genetics, or even other use cases I don't know of).

So, what do studying palindromes offer us? Do they offer theoretical insight into other string problems --- the way matrix multiplication and matrix inversion offer insights into each other? Are they practically useful? Or is it "just fun"?


texts: NP-complete problems with optimal approximation in poly-time

texts:
I'm looking for examples of hard optimization problems, for which we have an optimal approximation (not that this is not the same as $PTAS$, as we require a completely tight approximation, and not $1+\epsilon$-multiplicative approximation), in a sense defined as follows:

Formally, let $L\subseteq\Sigma^*\times \mathbb N$ be the decision version of some minimization (or maximization, flipping the definitions) problem, i.e.
$$\forall n\leq m:(w,n)\in L\implies (w,m)\in L$$

Which examples of such known languages $L$ is $NP$-hard, but if we are allowed of a minimal relaxation, it is poly time solvable.

By minimal relaxation I mean that there exists a TM such that given an input $(w,n)$:

The machine accepts if $(w,n+1)\in L$.
The machine rejects if $(w,n-1)\not \in L$.
The machine may act arbitrarily on other cases.

An example for such problem is the Degree-constrained spanning tree, where the problem is finding an MST with minimal maximum vertex degree.

  Which other languages are NP-hard but subject to optimal approximation in poly time?


texts: Natural problem arising from diagonalization?

texts: Diagonalization is a frequently used technique in complexity theory. However, the problems (sets) that are created by diagonalization rarely correspond to anything natural. It would be interesting to collect examples, when a problem was originally defined via diagonalization, but later it was found to coincide with a natural problem.


texts: In which posets is the set of compact elements downwards closed?

texts:
In a poset $(D, \sqsubseteq)$, a compact element is an element $d \in D$ such that for every directed set $A$ which happens to have a supremum $\bigsqcup A \in D$ with $d \sqsubseteq \bigsqcup A$, it is $d \sqsubseteq a$ for some $a \in A$ (e.g., Definition I-4.1 of [Gierz et al 2003]).

My (elementary) question. Suppose $d$ is compact and $c \sqsubseteq d$. What are typical extra impositions on the poset, that ensure that $c$ must also be compact?


texts: Proper definition of a graph with with loops and parallel edges

texts:
When a graph has parallel edges and self loops one cannot identify an edge with the set of two adjacent vertices it connects.  I have failed to find a good formal definition of a non-simple graph.  This is my attempt:

  An edge weighted graph $G = (V, E, \omega, \gamma)$ is a set of vertices $V$ together with a set of edge $E$, a function $\gamma: E \rightarrow \{\{u, v\}: u, v \in V\}$ and a weight function $\omega: E\rightarrow R$.

I am wondering whether this is sound, and what is a good standard name for the function $\gamma$ in this context.


texts: Second Smallest $s$-$t$-Cut in a Network

texts:
Is anything known about the second smallest $s$-$t$-cut in a flow network? Or, more general, about this problem:

  Input: A network $N$ and a number $k$, all in binary.
  Output: A $k$th smallest $s$-$t$ cut.

A $k$th smallest $s$-$t$ cut $(S,T)$ is any $s$-$t$ cut, such that there are exactly $k-1$ $s$-$t$ cuts whose capacities

are pairwise different and
truly smaller than the capacity of $(S,T)$.

I would like to know how it can be computed and whether this can be done efficiently as for the case $k=1$.


texts: Is this "subgroup packing" polytope integral?

texts:
Let $\Gamma$ be a finite abelian group, and let $P$ be the polytope in $\mathbb{R}^\Gamma$ defined to be the points $x$ satisfying the following inequalities:

$$\begin{array}{cl}
\sum_{g\in G} x_g \le |G| & \forall G \le \Gamma \\
x_g \ge 0 & \forall g \in \Gamma
\end{array}$$

where $G \le \Gamma$ means $G$ is a subgroup of $\Gamma$. Is $P$ integral? If so, can we characterize its vertices?

My question originally arose with $\Gamma = \mathbb{F}_2^n$, where some small examples ($n = 2,3$) suggest that the answer is "yes" and "maybe, but it's not simple". I also tried the cyclic group on 9 and 10 elements, as well as $\mathbb{F}_3^2$, where again the polytope is integral. The polytope is not integral when $\Gamma$ is any of $S_3$, $D_4$, and $D_5$, so abelianness is apparently essential.

I should mention that if you write the first set of equations as $Ax \ge b$, then $A$ is not necessarily totally unimodular (which would imply the polytope is integral). When $\Gamma = \mathbb{F}_2^3$, you can choose three linearly independent $g$ and take the three $G$'s spanned by each pair of the selected elements $g$. The resulting submatrix is
$$\begin{bmatrix}0&1&1\\1&0&1\\1&1&0\end{bmatrix}$$
up to permutation, and so has determinant $\pm 2$.

It's easy (if tedious) to characterize the vertices for prime-order groups and observe that they're integral. I'm pretty sure this can be extended to cyclic groups with order a prime-power. I'm not sure what happens when taking products.

This system is very reminiscient of those defining polymatroids, but rather than a submodular set function, the constraints are a "subgroup function" that I suspect is 'submodular' once that's been defined the right way. Still, the techniques for showing certain polymatroids are integral might work here, too, but I don't see how.

Also, Fourier analysis may be relevant: when $\Gamma = \mathbb{F}_2^n$, it seems that the vertices maximizing $\sum_g x_g$ are exactly the point with $x_g = 1$ for all $g$, as well as those with $x_g = 1 - \chi_S(g)$ where $\chi_S$ is the $S$-th Fourier character (following standard notation from analysis of boolean functions), and $S$ is nonempty. (When $S$ is empty, the corresponding point is $x_g = 0$, which is also a vertex.)


texts:
According to BGS theorem [1], there is an oracle $A$ such that $P^A\neq NP^A$.

If the relativization operation $B\mapsto B^A$ was a well-defined function,
one would expect that from $B^A\neq C^A$ one would be able to conclude that $B\neq C$,
e.g. $P\neq NP$ would follow from BGS. However, $P\neq NP$ is still open.

Does that mean that relativization is not a well-defined function?

If so, do we have any example of two provably different relativizations of the same complexity class?

[1] T. P. Baker, J. Gill, and R. Solovay, "Relativizations of the P =? NP Question"


texts: Cleaning images in order to perform feature detection

texts:
I have a set of images (e.g. cars) and trying to perform feature detection using SIFT (actually, SIFT modification - A-SIFT, which is more robust to affine transformations) and I'm getting an extremely low results in matching even on the same models, same color and closely same view point.
I'm barely sure, that the problem is car's surface is glossy (that's leads to huge variation of reflections on surface) and shadows & lighting (that's depends on location where photo was taken). Is there's image processing algorithms that can help me clean up images and/or decrease influence of that factors?
I had a quick look at CiteSeerX and Google Scholar but found nothing.


texts:
A language $L$ is in the class $DP$ iff there are two languages $L1 \in NP$ and $L2 \in coNP$ such that $L = L1 \cap L2$

A canonical $DP$-complete problem is SAT-UNSAT : given two 3-CNF expressions, $F$ and $G$, is it true that $F$ is satisfiable and $G$ is not?

The Critical SAT problem is also known to be $DP$-complete : Given a 3-CNF expression $F$, is it true that $F$ is unsatisfiable but deleting any clause makes it satisfiable?

I am considering the following variant of the Critical SAT problem : Given a 3-CNF expression $F$, is it true that $F$ is satisfiable but adding any 3-clause (out of $F$ but using the same variables as $F$) makes it unsatisfiable?
But I don't succeed in finding a reduction from SAT-UNSAT or even prove it is $NP$ or $coNP$ hard.

My question: is this variant DP-complete ?

Thank you for your answers.


texts: Statements that imply $\mathbf{P}\neq \mathbf{NP}$

texts:
This is sort of an open-ended question - for which I apologize in advance.

Are there examples of statements that (seemingly) don't have anything to do with complexity or Turing machines but the answer of which would imply $\mathbf{P}\neq \mathbf{NP}$?


texts:
Checking if there are two edge-disjoint paths from $s$ to $t$
in a given undirected graph $G$ is in P via a standard solution based on maxflow.
I am interested in the complexity of the following edge-labeled version and
whether it is in P or not.

Input: An edge-labeled graph $G$ and two vertices $s$ and $t$ satisfying the following condition:

  every label in $G$ occurs exactly twice.

Output: are there two label-disjoint paths in $G$ from $s$ to $t$?

Two paths are label disjoint iff
the labels appearing in the respective paths are disjoint.

Example:
suppose $G$ is given by $(s, a, v1)$, $(v1, b, t)$, $(s, b, v2)$, $(s, c, v2)$, $(v2, a, t)$, $(v2, c, t)$. Then $s-a-v1-b-t$ and $s-c-v2-c-t$ are two label-disjoint simple paths from $s$ to $t$.


texts: Misunderstanding the Church-Turing thesis?

texts:
My understanding of the Church-Turing thesis is the:

It puts a limit on what can be computed by any discrete and finite process.
Although still a thesis, not a theorem, if it were to be disproven, this wouldn't mean just an update to our current models of computation. It would be a paradigm shifting result for mathematics and physics in general.

Yet many discussions on the Philosophy SE (where I usually hang out) turn to the possibility of "Super-Turing" computation, and arguments in philosophy of mind question are frequently hinged on the proposition that Church-Turing is just a thesis and the there are several proposals for super-Turing computation or hypercomputation.

The mostly frequently cited source for this is the Stanford Encyclopedia of Philosophy  (SEP) article on the Church-Turing thesis.

In particular the article has a section titled "Misunderstandings of the thesis", which states the following:

  A myth seems to have arisen concerning Turing's paper of 1936, namely that he there gave a treatment of the limits of mechanism and established a fundamental result to the effect that the universal Turing machine can simulate the behaviour of any machine. The myth has passed into the philosophy of mind, generally to pernicious effect.

  [...] Turing did not show that his machines can solve any problem that can be solved "by instructions, explicitly stated rules, or procedures", nor did he prove that the universal Turing machine "can compute any function that any computer, with any architecture, can compute". He proved that his universal machine can compute any function that any Turing machine can compute; and he put forward, and advanced philosophical arguments in support of, the thesis here called Turing's thesis. But a thesis concerning the extent of effective methods -- which is to say, concerning the extent of procedures of a certain sort that a human being unaided by machinery is capable of carrying out -- carries no implication concerning the extent of the procedures that machines are capable of carrying out, even machines acting in accordance with ‘explicitly stated rules’. For among a machine's repertoire of atomic operations there may be those that no human being unaided by machinery can perform.

The above mentioned section and especially the quoted passages seem blatantly wrong to me, as if the author doesn't even get the concept of a Turing machine or what the Church-Turing thesis is. And yet, the article is constantly cited as a source by those who argue against the Church-Turing thesis, not just in the Philosophy SE, but even by relatively well known philosophers like Massimo Pigliucci. The main reasons why the article carries so much weight is that the SEP is considered a reputable source in the philosophy community, and the articles there are subject to review, and that the article's author, Jack Copeland, is an established philosopher who has published extensively on Turing and on AI.

And yet the way I see it, the article is fundamentally wrong in its presentation of the thesis, reputability of the source and the author not withstanding.

My questions:

Is my interpretation of the Church-Turing thesis correct?
How could one refute those who use that article's "Misunderstandings" section as a justification for the idea that computing beyond the Turing limit is a realistic prospect?
Is hyper computation taken seriously by mainstream computability theorists, or is it the CS equivalent of cold fusion and perpetual motion?


texts: Question on ascending $k$-tuples of naturals whose sum is less or equal than $S$

texts:
Let $k$ and $S$ be fixed non-negative integers. Let us regard the following set of tuples

$\{ (x_1,\dots,x_k)| x_i \leq x_{i+1}, \sum_j x_j \leq S \}$

I have got some questions on this set.

Is there are name for this set? It is similiar to an arbitrary partition of an integer.
Is there a nice formula that provides the number of elements in this set? It may be recursive.
Is there an easy to compute index for each of the elements, such that in turn any element can be computed from the index (easily)?

Of course, there are brute force algorithms for the last two questions. I am looking for something neater.


texts:
Are there any works where authors tried to define weighted finite state automata over hyperreals (or a similar object allowing for infinite and infinitesimal values) in an attempt to make automata properly behave for any assignment of weights?

In the probability semiring, for instance, epsilon loops with weight $\geq 1$ present a problem since they define an automaton with infinite values (as explained in this paper). An introduction of hyperreals can possibly make such an automaton properly defined, and, furthermore, normalizable (meaning that there exists such a quantity $Z$ that sum values of the automaton on all sequences divided by $Z$ equals to $1$).


texts: Proof of the pumping lemma for context-free languages using pushdown automata

texts:
The pumping lemma for regular languages can be proved by considering a finite state automaton which recognizes the language studied, picking a string with a length greater than its number of states, and applying the pigeonhole principle. The pumping lemma for context-free languages (as well as Ogden's lemma which is slightly more general), however, is proved by considering a context-free grammar of the language studied, picking a sufficiently long string, and looking at the parse tree.

Given the similarity of the two pumping lemmas, you would expect that the context-free one can also be proved in a similar way to the regular one by considering a pushdown automaton which recognizes the language, rather than a grammar. However, I didn't manage to find any reference to such a proof.

Hence my question: is there a proof of the pumping lemma for context-free languages which only involves pushdown automata and not grammars?


texts: Recent Probabilistic Methods in Combinatorics and its appplications to Complexity Theory

texts:
I read the famous book by Alon and Spencer on the probabilistic method in combinatorics.

Is there a survey or lecture notes on recent advances and relationships with the following complexity theoretic topics of this method beyond this textbook?

pseudorandom generators fooling concrete computation models, expander graphs.
complexity lower bounds for concrete computation models such as circuits, branching programs, streaming, property testing, learning, and communication complexity.
randomized complexity theoretic aspects of algebraic coding theory and information theory.
VC-dimension, discrepancy and other geometric topics.


texts: Can a NEXP machine simulate invalid queries to a promise problem oracle?

texts:
Let $A=(A_{YES},A_{NO})$ be some promise problem (such as xSAT, the Local Hamiltonian problem, etc). Suppose we want to show that a P machine with access to a the oracle A can always have its output predicted by a NEXP machine, i.e. $P^A\subseteq$ NEXP. We adopt the convention that if P submits a query  which doesn't satisfy the promise of A (that is, $x\not\in A_{YES}\cup A_{NO}$), then the oracle for A randomly returns 0 or 1 $^*$.
Suppose further that for all valid queries (i.e. those satisfying the promise, $x\in A_{YES}\cup A_{NO}$) there exists a single witness which (when run by an EXP machine) allows all queries to the oracle A to be predicted.
Finally, let it is be trivial (i.e. in P) to determine whether a query $x$ satisfies the promise or not.
Then is it correct to say $P^A\subseteq$ NEXP?
If the P machine were guaranteed to only make valid queries, then it seems like this is trivial as the NEXP machine is (by assumption) capable of simulating the oracle outcomes and any processing done by the P machine. However, the fact that the P machine can make invalid queries which return 0 or 1 randomly could potentially throw a problem in the simulation.
So far all I've found is Oded Goldreich's notes on promise problems. These don't give a direct answer, but do introduce smart reductions: http://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf
Smart reductions seem to force the P machine to only make valid queries. So in this case it would perhaps be correct to say $P_S^A\subseteq$NEXP, where $P_S$ is a ``smart TM'' which only makes valid queries. But is it correct to state the stronger result that $P^A\subseteq$NEXP?
$^*$As I understand it, this is standard (see the link to Oded Goldreich's notes above).


texts: Bounds on this Strategy for Separating Words

texts:
Question
Given binary string $z \in \{0,1\}^n$, let $f(z)$ be the smallest integer $k$ such that there exists a DFA with $k$ states, such that reading $z$ from a specific starting state, we end at a state $t$ where either reading a $0$ or a $1$ at $t$ takes us to a new state. (i.e. a state which has not been reached in the path we took when reading $z$)
Then, defining $F(n) = \max\{f(z):z \in \{0,1\}^n\}$, I was wondering if any bounds are known for $F$. Clearly, we have $F(n) \le n+1$.
Motivation
Generally, the word separator problem about given distinct binary strings, $x,y \in \{0,1\}^n, x \neq y$, to find the smallest DFA such that accepts $x$ but not $y$.
I was wondering if there have been results on this particular method:
Since $x\neq y$, let $z$ be the longest common prefix of $x$ and $y$. (example: if $x = 1101101,y=1100110$, then $z = 110$ because $x,y$ differ on their fourth letter)
WLOG, lets assume $x= z|0|x', y=z|1|y'$, where $|$ denotes concatenation and $x',y'$ are arbitrary. If there exists a DFA of length $k$ such reading $z|0$ or $z|1$ ends at a state $s'$ not visited by reading $z$, then there is a DFA of length $k +O(\log(n))$ separating $x$ and $y$. (because $x,y$ will reach $s'$ at different times, it reduces to unary word separation, which is know to take $O(\log(n))$ states by prime number theorem)
Rough Ideas
Currently this strategy has stuck out to me: we have that $f(z) \le g(z_m)+F(n-m)$ where $z_m$ is the subword consisting of the first $m$ letters in $z$, and $g(w)$ is the smallest integer $k$ such that there is DFA on $k$ states, such that reading $w$ at a specific starting state, we end at a new state $t$. For upper bounding $g(w)$, for any integers $k,i$, and any $w' \in \{0,1\}^k$, there exists an DFA on $2k$ states such that when reading a word $w$, we reach the state $t$ iff $w'$ appears as a factor/substring whose first letter is the $qk+i$-th letter of $w$. (i.e. the first letter is the $m$-th letter of $w$ where $m$ has the same residue as $i$ modulo $k$)
Of course, if $z$ is a string of only 1's, then $g(z_m) = m$ for all $m$, thus we need to combine this with a second idea to handle the cases when $z$ is periodic or otherwise not quasi-random in some sense, to get a sublinear bound.


texts: Regular languages accepted by an automaton with at most one transition per letter

texts:
I'm interested in the (very restricted) subset of regular languages for which there is an automaton having the following property: for every letter $a$ of the alphabet, the automaton has at most one transition labeled with $a$. (Of course, the automaton is then necessarily a partial deterministic automaton.) Is there a name for this class of regular languages?
These languages are quite limited but not entirely trivial either, for instance you could have $(ab)^*$, $ab^*|cd^*$, or $(ab)^*a$ (which I guess cannot be written as a regular expression with only one occurrence of each letter, so my class is more general than imposing the analogous requirement on regular expressions). These automata are clearly local automata, so this is a subclass of the local languages. These automata are also aperiodic, so these languages are star-free. Of course, for any alphabet, there are only finitely many languages of this kind over the alphabet.
I thought this class was pretty natural, but looking around, I could not find anything about it. Does it have a name, or has it been studied somehow?


texts:
I am just starting into process algebra (π-Calculus) for formally defining the operational semantics of a system. One common statement that I come across that π-Calculus is used for Concurrent and parallel processing systems.

However if two processes share the common link and send some token on the same link, where the later process will not begin until it receives the token then does it represent a sequential execution in π-Calculus ? , is my understanding correct?

So the below shows a sequential execution between process P and Q where: first process P outputs y on channel x and then process Q shares the same channel x and get the token y on it and only then begin?.


texts: Optimizing multiplication in a partly commutative semigroup

texts:
Let us say I have a semigroup M and its basis B. I know which elements of B commute.

What is the most efficient way to do multiplication in such a semigroup?

Essentially, this is a question of how to reduce "ABAAAXBCAAB" to "AAAABXAABBC" knowing that A, B and C commute with each other but not with X (after such a transform I can, for example, compute AAAA as (A^2)^2, or even store pre-computed powers of each element of B).


texts: Is the following "Occam's razor" decision problem a member of P?

texts:
While thinking about natural language processing, I came up with the following NP problem:

OCCAM-k:  Given a fixed natural number $k$, consider the following input:  a natural number of states $S$ in unary in a Turing machine $M$, a finite collection $A$ of strings that $M$ accepts, and a finite collection $R$ of strings that $M$ rejects.  Assuming that $M$ is polylimited by the polynomial $n^k+k$, that it contains at most $S$ states, that it accepts every string in $A$, and that it rejects every string in $R$, find a valid deterministic Turing machine that satisfies these conditions for $M$.

The problem is NP because after guessing a Turing machine $M$ of size $S = |S|$ ($S$ is unary), all that remains is to verify that the machine accepts every string in $A$ and rejects every string in $R$.  Since $M$'s running time is bounded above by $n^k+k$, this can be accomplished in polynomial time.

I am skeptical that this problem is NP-complete, as I cannot think of an NP-complete problem that sounds likely to reduce to it in polynomial time.  I would be excited if someone could prove that it is a member of P, as this would help with my motivation, which is to build a simple natural language processing system.

(My reason for calling the language OCCAM is that I believe that one could theoretically try to find a "natural language processing algorithm" that determines the binary truth value of sentences.  Suppose I provided 1 million true natural-language sentences and 1 million false natural-language sentences as part of the input; I could try to find a small enough polytime algorithm that "gets all of these sentences right" and hope that the algorithm would work on all natural language sentences in that language (e.g., English)).

My question is:  To which complexity class should we say OCCAM-k belongs?  NP-complete?  NPI?  P?  Is there an algorithm that could solve it?


texts:
(I moved this question from cs exchange to here, because it might be more on the topic here)

Let $G=(V,E)$ be a directed graph with $n$ nodes. For a subset of nodes $S\subseteq V$, let $\mathcal{N}(S,k)$ denote the directed $k$-neighborhood of $S$ ($d_G(u,v)$ is directed shortest path distance from $u$ to $v$):
$$\mathcal{N}(S,k):=\{u\in V\colon  \exists v\in S: d_G(u,v)\le k\}$$

Problem: For a given bound $B$, find the minimum cardinality set $S$, which dominates all but $B$ vertices in $k$ steps:
$$\min \{|S| \colon S\subseteq V, \; \lvert \mathcal{N}(S,k)\rvert\ge n-B \} \qquad (\star)$$

For $B=0$, this is equivalent to minimum dominating set for graph $G^{(k)}=(V, E^{(k)})$, in which $E^{(k)}$ denotes all the edges in $E$, plus their transitive closures up to $k$ steps. By adding $B>0$, it becomes a relaxed minimum dominating set. Given that for $k=1$ and $B=0$, this problem becomes a standard minimum dominating set, there is probably no efficient algorithms for this problem. My questions are (answer to any one is highly appreciated):

Is an efficient approximation algorithm for some special class of graphs, say bounded out-degree $\Delta$ graphs?
Is this problem related to the highway dimension? (link)
Let $S(B,k)$ denote the set of all minimizers for $(\star)$. As the value of $B$ increases the constraint becomes more relaxed, and the size of the minimizer  $\lvert S(B,k)\rvert$ must decrease. However, is there some continuity in these sets? In other words, can we find a sequence of sets $S_1, S_2, \dots $ respectively belonging to $S(B=1,k), S(B=2,k), \dots$, such that $S_1 \supseteq S_2 \supseteq \dots $?
Here is a real relaxation of this problem:
$$\min \sum_{v\in V} x_v,\\
s.t.\; \forall v\in V \; x_v, b_v\in[0,1] , \sum_{(u,v)\in E^{(k)}} x_u \ge 1-b_v,\sum_{v\in V} b_v \le B$$
Since the integral optimal solutions $x_v^\star,b_v^\star\in\{0,1\}$ are feasible points here, the optimum should be less than or equal to OPT, and by u.a.r sampling from $x^\star, b^\star$ as the minimizers of the real relaxation, we have:
$$\tilde b_v \sim \mathcal{B}(n=1,p=b_v^\star),\; \tilde x_v \sim \mathcal{B}(n=1,p=x_v^\star).$$
($\mathcal{B}$: binomial), can we use Chernof bounds on $\sum_v  \tilde b_v$ snd $\sum_v \tilde x_u$ to prove something about the resulting integral solution?


texts: Complexity of a scheduling problem with a fixed left bound of jobs

texts:
Consider the following scheduling problem. We have a finite set of jobs $\mathcal{J}= \{j_1, j_2, ..., j_n\}$ to do. Every job $j_i$ has its own value $c_i$ (the amount of money we are paid for finishing the respective job before the deadline), processing time $t_i$ and deadline time $b_i$. We can perform only one job in a moment with no interruptions. Our goal is to plan the order of performing the jobs with the highest total value of finished jobs before the deadline.

Formally, we have sets $S=\{1, 2, \ldots, n\}, C=\{c_1, c_2, \ldots, c_n\}, T=\{t_1, t_2, \ldots, t_n\}, B=\{b_1, b_2, \ldots, b_n\}$. We are looking for the subset $S_1 \subseteq S$ with an order $\pi$ on its elements such that $\{\pi_1, \pi_2, \ldots \pi_k\} = S_1$ and the following restrictions are performed:
$$
\forall l \in \{1, 2, \ldots, k\}: b_{\pi_l} \geqslant \sum_{i=1}^{l} t_{\pi_i}
$$
$$
\sum_{i=1}^k c_{\pi_i} \longrightarrow \max
$$

I'm interested in the complexity of this task. It's easy to see that this problem is $NP$-hard if parameters are given in a binary representation (because in the case of all equal parameters $b_i$ we can get the Knapsack problem). So my questions are:

Does this task belong to $P$ if numbers are given in unary form?
What approximation algorithms are known for this task, are there any PTAS or FPTAS?


texts: Eigenvalues of adjacency matrix of a connected bipartite graph

texts:
Let $G=(V,E)$ is a connected d-regular bipartite graph with the same number of vertices on both sides of the bipartition. It's known that that the largest eigenvalue of its adjacency matrix would be d, and the smallest would be -d.

I was wondering if it was true that if the k-th largest eigenvalue here was $\lambda_k$, then the k-th smallest one would be $-\lambda_k$.

I seem to be able to show that this is true for the second largest eigenvalue (using the fact that the all ones and indicators on each side of the bipartite graph are the largest and smallest eigenvectors, and using that the eigenvalues have multiplicity 1 and then applying the sign flipping trick). However this proof does not seem to hold in general.


texts: Example of R and G when $R \subseteq L(G)$ is undecidable

texts:
Could anybody provide an example of regular language R and context-free grammar G such that $R \subseteq L(G)$ is undecidable. Of course, if such language could be constructed.

Thanks.


texts: Halting on a (possibly one-way) write-once tape

texts:
Consider Turing machines (with the Busy Beaver "design specifications")
that must write a 1 whenever they read a 1 (i.e., "write once").

${}$1. $\:$ Is the halting problem decidable for these machines?

If those specifications are modified to use a [one-way infinite] tape instead,

${}$2. $\;$ Is the halting problem decidable for the resulting type of machines if they

a. $\;$ stay where they are

b. $\;$ halt

whenever they try to move off the end of the tape?


texts: Does PPAD really capture the notion of finding another unbalanced vertex?

texts:
Complexity class PPAD was invented by Christos Papadimitriou in his seminal 1994 paper. The class is designed to capture the complexity of search problems where the existence of a solution is guaranteed by "Parity argument in directed graphs": if there is an unbalanced vertex in a directed graph then there must exist another one. But usually the class is formally defined in terms of the $\mathsf{ANOTHER\ END\ OF\ THE\ LINE}$ ($\mathsf{AEOL}$) problem, where the argument is applied only to graphs with both in- and outdegrees $\le 1$. My question is: why are these notions equivalent?

Up to this point it is a duplicate of this question. Now I want to state the problem formally and to clarify why I am not satisfied with the answer there.

Search problem $\mathsf{ANOTHER\ UNBALANCED\ VERTEX}$ ($\mathsf{AUV}$): we are given two polynomial-sized circuits $S$ and $P$ that get $x\in\{0,1\}^n$ and return a polynomial list of other elements in $\{0,1\}^n$. These circuits define a directed graph $G=(V,E)$ where $V=\{0,1\}^n$ and $(x,y)\in E\Leftrightarrow (y\in S(x)\land x\in P(y))$. The search problem is the following: given $S$, $P$ and $z\in V$ such that $indegree(z)\ne outdegree(z)$, find another vertex with the same property.

Search problem $\mathsf{AEOL}$: the same, but both $S$ and $P$ return either an empty list or one element.

The notion of reducibility (corrected according to Ricky's suggestion): total search problem $A$ is reducible to total search problem $B$ via polynomial functions $f$ and $g$ if $y$ is a solution to $f(x)$ in problem $B$ implies $g(x,y)$ is a solution to $x$ in problem $A$.

Formal question: why is $\mathsf{AUV}$ reducible to $\mathsf{AEOL}$? Or should we use another notion of reducibility?

Christos Papadimitriou proves analogous theorem about PPA (Theorem 1, page 505) but the argument seems not to work for PPAD. The reason is that a vertex with degree balance $\pm k$ will be transformed into $k$ vertices with degree balance $\pm1$. Then the algorithm for $\mathsf{AEOL}$ may get one of these vertices and return another one. This would not yield a new vertex for $\mathsf{AUV}$.

Things are getting worse because in $\mathsf{AEOL}$ there is always an even number of unbalanced vertices but in $\mathsf{AUV}$ there might be an odd number of them. This is why one cannot build a bijection between these two sets and $g$ could not be always equal to $f^{-1}$. If $g(x,f(x))\ne x$ then we obtain a method for solving $\mathsf{AUV}$ in polynomial time at least for some instances. If $g$ does not depend on $x$ and $g(y_1)=g(y_2)$ for $y_1\ne y_2$ then $y_2$ may be returned as an answer for $y_1$. That would not give a solution for $\mathsf{AUV}$.

Final question: can the obstacles listed above be somehow overcome? Can one employ possible dependence of $g$ on $x$?


texts: Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree

texts:
I have encountered an interesting problem that I couldn't find any references to solve:

  Determine the smallest subset of nodes that
  need to be removed from an undirected graph to make it a tree.

Obviously when a node is removed, the edges connecting to it are also removed.

Any help would be very much appreciated.
Thank you in advance!


texts: An algorithm to efficiently draw a extremely large graph in real time

texts:
Are there any algorithms to draw a billion node graph or to aggregate the information? The idea would be to allow for it to be parallelized using map reduce so it could be done in realtime

I was wondering if there were any other algorithms? A google search turned up nothing.

Very large graph drawing I have found are as follows

http://www2.research.att.com/~yifanhu/GALLERY/GRAPHS/

Below is a sketch of an algorithm I thought up.

Specifically one that you can pan around and zoom? I thought of the following algorithm.

Take a graph layout algorithm (a force directed layout algorithm)
Create a window of locality using a graph metric that you define
Draw everything in an epsilon of that graph metric.
Iterate the window throughout a n-dimentional space. Where n is defined as the amount of data points you have and a tag is a $S \in $ the set of strings. (vertex, edge, $tag_{1}$,  ...  $tag_{n})

--Begin amended algorithm--

Step 5 is due to @vzn answer: Add a visualization of local regions. Therefore we define a region as a set of points that are "close" due to some locality measure. Pagerank is an example so you have a pagerank of 2 you are in the region.


texts: Normal term of double negation of W-type

texts:
Consider the intensional Martin-Löf type theory without axiom of choice or the law of excluded middle.
Let $A:U_0$ be a type and $B:A\to U_0$ be a function such that $\Sigma_{a:A}(B(a)\to 0)$is inhabited. Then $W_{a:A}B(a)$ is inhabited and so $(W_{a:A}B(a)\to 0)\to 0$ is inhabited. As an inhabited proposition $(W_{a:A}B(a)\to 0)\to 0$ has only one term in normal form. What is that term?


texts: Many-one reducibility equivalent for more general computational problems?

texts:
Many-one reducibility, denoted by $\leq_m$, is a binary relation between 2 decision problems which is defined as follows:
$L' \leq_m L$ iff there exists a computable function $f$ (called a reduction) such that $w \in L' \iff f(w) \in L$.

[source: https://en.wikipedia.org/wiki/Many-one_reduction]

Conceptually, if $L'$ is reducible to $L$, we can use an algorithm solving $L$ to solve $L'$ (by first reducing it to an instance of L first).

This conceptual notion is not restricted to decision problems.

I was wondering whether there are equivalents/formal definitions of this type of reducibility that apply to more general problem classes (e.g. function, search problems).

I think m-reducibility on function problems can be defined as follows:

Let $f:X \rightarrow Y$ and $f': X' \rightarrow Y'$ be two function problems. We say $f' \leq_m f$ iff there exist computable functions $a: X' \rightarrow X$ (reduction) and $b:X' \times Y \rightarrow Y'$ (interpretation) such that $f'(x') = b(x',f(a(x'))$.

Note that  m-reducibility for decision problems is a special case obtained if we fix $b(x',y) = y'$ (yes is yes and no is no).

I have also extended this definition to search problems. However, I would very much like to re-use/refer to prior art if possible, but thus far I failed to find an existing definition of the concept.