texts: Topological sorting of a DAG where special vertices have to come in even groups

texts:
Consider the following problem. The input is a directed acyclic graph (DAG) $G = (V, E)$, and a subset $V' \subseteq V$ of vertices, which we call special vertices. The question is to determine whether $G$ has a topological sort $v_1 < \cdots < v_n$ having the following property: when the sort is enumerating special vertices, then it must always enumerate an even number of them consecutively. In other words, at every step of the sort, we can either take one normal vertex, or take two special vertices one after the other, and we repeat this. Formally, for any contiguous subword $v_i, \ldots, v_{j-1}$ of $v_1, \ldots, v_n$ where all vertices are special, and which is maximal (either $i=1$ or $v_{i-1}$ is not special; and either $j = n-1$ or $v_j$ is not special), then we require that $j-i$ is even.

Is this decision problem NP-hard, or is it in PTIME?

Of course, a necessary condition is that there is an even number of special vertices. But this is not sufficient: the totally ordered graph $w_1 < v_2 < w_3$ with $w_1$ and $w_3$ special is a negative instance, as its only topological sort does not satisfy the condition. In general, the idea is that we can always freely consume non-special vertices, but we must be careful in which special vertices we consume to avoid getting stuck with an odd number of special vertices that block the rest of the graph from being enumerated. Consider for instance a DAG defined by $w_1 < v < w_2$ and $w_3 < w_4$ with the $w_i$ being special and $v$ non-special, then the topological sort $w_1 < w_3 < v < w_2 < w_4$ satisfies the condition, but if we want to start a topological sort by $w_3 < w_4$ then we are "stuck".

[This relates to work on mine about constrained topological sorting. It is listed as an open problem here (search for "Open problem: Is the same true of the CTS problem?"). We have a PTIME algorithm (Proposition 4.6 of the paper) for the much easier problem where $G$ is a disjoint union of chains (total orders), which is a rather intuitive but not entirely trivial greedy algorithm.]

Update (thanks @Louis): The problem presented here is related to another variant of topological sort, which seems unknown but pretty natural, which I'd call "two by two" or "pairwise" topological sorting. This is the problem where you are given a DAG $G = (V, E)$ with an even number of vertices, and you want to decide if there exists a topological sort $v_1 < \cdots < v_n$ where we take vertices two by two (with the second vertex already being available before having taken the first vertex), formally we add the condition that for all $0 \leq k < (n/2)-1$, the vertices $v_{2k+1}$ and $v_{2k+2}$ are incomparable. I do not know the complexity of this problem, either. This problem reduces to the problem asked in my question (make all vertices special, and add a non-special vertex at the middle of every edge), in fact my problem is equivalent to a generalization of this problem.

I also don't know the complexity of the variant where we replace two by some other constant $k$, i.e., my problem where special vertices must be taken in groups of multiples of $k$, or the "$k$ by $k$" topological sorting problem. Any insights about their complexity are also welcome.


texts: Inductive definition of language operators like the set of all permutations of a word came from the shuffle operator

texts:
Let $X$ be a finite alphabet. Given two words $u, v \in X^{\ast}$ the shuffle operator is defined to be
$$
 u || v := \{ u_1 v_1 u_2 v_2 \ldots u_n v_n : 1 \le i \le n, u_i, v_i \in X^{\ast}, u = u_1 \ldots u_n, v = v_1 \ldots v_n \}
$$
i.e. it is the set of all "interlaced" strings (notice its signature $X^{\ast}\times X^{\ast}\to 2^{X^{\ast}}$). For example
$$
 ab || c = \{ cab, acb, abc \}.
$$
There is also an inductive definition
\begin{align*}
 \varepsilon || u & = u || \varepsilon = \{u\} \\
 au || bv & = a(u || bv) \cup b(au || v).
\end{align*}
This operator could be extended to languages. Now, for a language $L \subseteq X^{\ast}$ denote by $\mbox{perm}(L)$ the set of all permutations of words from $L$, for example $\mbox{perm}(\{ abc \}) = \{ abc, bac, acb, cba, cab, bca \}$. Now we have the inductive definition for $x \in X$ and $u \in X^{\ast}$
\begin{align*}
 \mbox{perm}(\varepsilon) & = \{\varepsilon\} \\
 \mbox{perm}(xu) & = x || \mbox{perm}(u).
\end{align*}
which defines it for words, and then extended to languages. Now instead of all permutations, just consider the rotations, or the cyclic permutations, i.e. for $u \in X^{\ast}$
$$
 \mbox{cycle}(L) := \{ vu : uv \in L\}.
$$
For example $\mbox{cycle}(\{abc\}) = \{abc, bca, cab\}$. And similar the rotations and reflections, where if we define $\mbox{reverse}(u) = u_n \ldots u_1$ for $u = u_1 \ldots u_n$ with $u_i \in X$, then for $L \subset X^{\ast}$
the smallest set, called $\mbox{di}(L)$ such that
$$
 u \in \mbox{di}(L) \Rightarrow \mbox{cycle}(\{u\})\subseteq \mbox{di}(L), \quad\mbox{and}\quad\mbox{reverse}(u) \in \mbox{di}(L).
$$
For example $\mbox{di}(\{abcd\}) = \{abcd, bcda, cdab, dabc, cbad, dcba, adcb, badc \}$. Now do the $\mbox{cycle}$-operator and the $\mbox{di}$-operator
admit a similar inductive definition in terms of some composition of words, i.e. exists there some composition such that we can define them inductively like $\mbox{perm}$?


texts:
In the paper The Random Oracle Hypothesis Is False, the authors (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi) discuss the implications of the random-oracle hypothesis. They argue that we know very little about separations between complexity classes, and most results involve either using reasonable assumptions, or the random-oracle hypothesis. The most important and widely believed assumption is that PH does not collapse. In their words:

  In one approach, we assume as a working hypothesis that PH has infinitely many levels. Thus, any assumption which would imply that PH is finite is deemed incorrect. For example, Karp and Lipton showed that if NP ⊆ P/poly, then PH collapses to $\Sigma^P_2$. So, we believe that SAT does not have polynomial sized circuits. Similarly, we believe that the Turing-complete and many-one complete sets for NP are not sparse, because Mahaney showed that these conditions would collapse PH. One can even show that for any k ≥ 0, $P^{\mathrm{SAT}[k]} = P^{\mathrm{SAT}[k+1]}$ implies that PH is finite. Hence, we believe that $P^{\mathrm{SAT}[k]} \ne P^{\mathrm{SAT}[k+1]}$ for all k ≥ 0. Thus, if the polynomial hierarchy is indeed infinite, we can describe many aspects of the computational complexity of NP.

Apart from the assumption about PH not collapsing, there have been many other complexity assumptions. For instance:

Yao deems the following assumption plausible:
$RP \subseteq \bigcap\limits_{\epsilon > 0} DTIME(2^{n^\epsilon})$.
Nisan and Wigderson make several assumptions related to derandomization.

The main idea of this question is what its title says: To be an anthology of complexity-theoretic assumptions. It would be great if the following conventions were adhered to (whenever possible):

The assumption itself;
The first paper in which the assumption is made;
Interesting results in which the assumption is used;
If the assumption has ever been refuted / proved, or whether its plausibility has ever been discussed.

This post is meant to be a community wiki; if an assumption is already cited, please edit the post and add new information rather than making a new post.

Edit (10/31/2011): Some cryptographic assumptions and information about them are listed in the following websites:

Wiki of Cryptographic Primitives and Hard Problems in Cryptography.
Helger Lipmaa's Cryptographic assumptions and hard problems.


texts: Recognition problem of cycle permutation graphs

texts:
A cycle permutation graph is a cubic graph composed from two $n$-cycles each labeled $1, 2,..., n$, with additional edges connecting vertex $i$ in the first cycle to vertex $\pi(i)$ in the second, where $\pi$ is a permutation in $S_n$.

I am interested in the complexity of recognizing cycle permutation graphs. I guess it is NP-complete. I did not find any literature on the computational aspects of this class of cubic graphs.

  Is the recognition problem of cycle permutation graphs $NP$-complete?

The input is a cubic graph. The problem is to determine whether it is a cycle permutation graph or not.


texts: Distinguishing two types of Monte-Carlo algorithms

texts:
Recall from Wikipedia that Monte Carlo algorithm is a randomized algorithm whose running time is deterministic, but whose output may be incorrect with a certain (typically small) probability. Consider the following two types of Monte Carlo algorithms.

Type-1 algorithms: When an algorithm fails, it still outputs a feasible solution.
Type-2 algorithms: When an algorithm fails, it outputs any arbitrary solution which might not even be feasible.

As an example, consider algorithms for, say Travelling Salesman Problem (TSP), where it outputs some value supposed to be an optimal TSP value. Type-1 algorithms are algorithms that either output the value of the optimal solution correctly or otherwise output the value of some Hamiltonian tour. Type-2 algorithms are algorithms that either output the optimal solution correctly or otherwise output an arbitrary number.

  My question is whether there are terms defined to distinguish between these two types of algorithms?

(Note: One point of asking this question is that type-1 algorithms can be used to answer the following gap question with one-sided error while type-2 algorithms cannot: For some parameters $0<a<b$, is the TSP optimal solution has value less than $a$ or more than $b$?)


texts: Is this vertex ordering optimization NP-Hard?

texts:
Could you help me to prove that the following problem is NP-hard?

Problem. Given an undirected graph $G=(V,E)$, find an ordering of the nodes such that $\sum\limits_{v\in V}|succ(v)|\times|pred(v)|$ is minimum.

Given an ordering on the nodes and a node $v\in V$, $pred(v)$ (resp. $succ(v)$) denotes the set of neighbors of $v$ with lower (resp. higher) ordering.


texts: Why does the construction step of Aho-Corasick take linear time in the number of nodes?

texts:
The original paper's analysis of this, as far as I can tell is this:

"THEOREM 3. Algorithm 2 requires time linearly proportional to the sum of the lengths of the keywords.
PROOF. Straightforward."

But it's not at all obvious.


texts: Integer multiplication when one integer is fixed

texts:
$n$ is a parameter in the problem.
For every $n$ we pick a random integer $a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$.
Problem: Given $n$ what is the complexity of multiplication function $f_n(x)=a_nx$ where $x\in\{0,1,\dots,2^n-1\}$?
One is allowed to pre-process integers $a_n$ as appropriate.
Upper Bound: We already have $n^{1+\epsilon}$ complexity algorithms by $\mathsf{FFT}$ and Karatsuba.
The query here is whether $\epsilon=0$ by anything cleverer?
Conjecture: $\exists c>0,n_0>0$ such that at every $n\in\mathbb Z_{>n_0}$ the number of constants $a_n$ where $\epsilon=0$ is supported is $>2^{cn}$.


texts: Optimization problems with same optimal value, but different approximation behavior

texts:
Context: related to this answer.

I would like to see an example to emphasize that approximation behavior depends not only on the optimal value but also the set of solutions. This makes sense logically. If two problems are duals of each other, then they have the same optimal value but can have different behavior with respect to approximation (eg: independent set and vertex cover). But, is the same possible if both are minimization problems, or both are maximization problems?

Are there two minimization problems with same optimal value, but different behavior with respect to approximation?

Existence of such a pair of problems justifies the definition of approximation factor preserving reduction.


texts: Reducing threshold questions to finiteness questions

texts:
It is usually simpler to reason about calculus where the limitation is finiteness of computation rather than a threshold like "computable in polynomial amount of time".

In formal languages theory for example, rather to use the $\exists n. x^{n+1} = x^n$ to characterize aperiodic monoïd, it is easier to use profinite words so that $x^{\omega+1} = x^{\omega}$.

In complexity theory, the only technic I know which is linked to that is the padding trick for example linking the problem of P vs NP to EXPTIME vs NEXPTIME. But the natural infinite equivalent of complexity questions would be computability ones'.

  Are there some results that link complexity to computability questions using some encoding such that the resource threshold of complexity theory becomes a finiteness question of computation in computability theory ?


texts: What is the relation between computational complexity of algebraic number and computational complexity to find the solution to algebraic equation?

texts:
Suppose $\alpha$ is algebraic number, and we have the algorithm with lowest computational complexity to output it, and $f(x)=0$ is algebraic polynomial with $\alpha$ as a root.

If an algorithm which solve the equation and find the root with lowest computational complexity, what is the relation between the computational complexities of the two algorithm? It seems that they are identified and possibly are the same algorithm.


texts: Space requirements for solving True Quantified Boolean Formulas problem

texts:
I came across this section on the wikipedia page for the TQBF solving problem, and just can't wrap my head about the fact that the space requirement is linear. Moreover, it does not provide any reference.

For a given QBF
$$Q_1x_1Q_2x_2...Q_nx_n\phi(x_1,x_2,...,x_n)$$

for each quantifier, the algorithm presented evaluates

$$ A = Q_2x_2...Q_nx_n\phi(0,x_2,...,x_n)$$
$$B = Q_2x_2...Q_nx_n\phi(1,x_2,...,x_n)$$

and returns $A\wedge B$ for $Q_1 = \forall$ and $A\lor B$ for $Q_1 = \exists$. The way I work it out the space should be $O(2^n)$ instead of $O(n + \log(n)) = O(n)$. When I solve a QBF on paper, I realize it is not exponential, so something must be terribly wrong with my analysis.

At each step, the new $A$ and $B$ have one quantifier less, but there are twice as many expressions. I assumed that would build up as
$$ 1: n$$
$$ 2 : (n-1) + (n-1) $$
$$ 3 : (n-2) + (n-2) + (n-2) + (n-2) $$
$$ \ldots $$
$$ k : 2^k (n-k) $$

which goes all the way up to $2^{n-1}$ before decreasing to zero. Can anyone provide a pointer on what I am doing wrong, or even better a good reference?

Thanks


texts: What's the connection between these two categories of games and innocent strategies?

texts:
Lately I've been reading a lot about game semantics and in particular the problem of PCF's full abstraction.

I'm trying to understand how the definition from this article relates to the one found in this notes (section 3.4).

The definition in the notes seem to follow quite closely the original definition used by Abramsky et al and Ong and Hyland.
The definition of the category $\mathcal{INN}$ in the article is more interesting since it uses some more advanced categorical construct(a distributive law between a comonad and a monad) and makes (even) more obvious the connection with linear logic(namely: models of linear logic are given by an adjunction between a symmetric monoidal closed category and a cartesian category).

However I don't understand exactly how $\mathcal{INN}$ is related to $\mathcal{C}_{ib}$ defined in the notes.

For example, reading the article I don't see any mention of well-bracketing(actually the article doesn't even divide the game moves into question and answers). Is this condition implicit somewhere in the definition they give? If yes how?

One of the authors, Hyland, also wrote one of the "original articles" about PCF's full-abstraction. In that article they put the well-bracketing condition in the definition of legal play and hence it is included in the condition of "innocence". It seems strange that they simply ignore it in the article.

Another thing I wonder: is $\mathcal{INN}$ cpo-enriched? Or, more generally, can we obtain the same(or very similar) full-abstract model of PCF using $\mathcal{INN}$ instead of $\mathcal{C}_{ib}$? Is there some major difference that wont allow this?

Note that Hyland et al, in the introduction of the article I linked, state that their "aim is to derive the original notion of innocent strategy together with its basic properties from structure on a primitive category $\mathcal{G}$ of games.", which I believe is in favor of the "equivalence" of $\mathcal{INN}$ with the category used to model the semantics of PCF, however they never make an explicit statement about this and the category they define in the article.

Update:
It just occurred to me that the definition of games and strategies in the article seems to only consider the "well-opened" games(as defined in the notes), i.e. the games whose plays contain a single initial move at the beginning.

This would make much sense since then we can interpret the games $!?A$ and $?!A$ that arise when defining $\mathcal{INN}$ through the distributive law as generic games(since the $!$ and $?$ "allow backtracking" and hence more than an initial move can happen in a single play).

Does this make any sense?


texts: What is a good special-case sorting algorithm?

texts:
I have a dataset which is a number of objects arranged in a 2-D grid.  I know I have a strict ordering, increasing as you go left-to-right within each row, and increasing as top-to-bottom within each column.  For example,

1 2 3
4 6 7
5 8 9

Can I improve on naive sorting to sort the entire dataset linearly (as measured in comparisons)?

What about for n-d datasets?  Arbitrary finite datasets with a subset of comparisons known?


texts: Formalizing a notion of machine Intelligence

texts:
Turing test of Artificial intelligence relies on interaction between two parties with the goal that one party convinces the other party that it has the same computational abilities.

I'm trying to formalize a new notion of machine Intelligence: the ability of Turing machines (algorithms) to recognize their programmer and that they were not generated randomly.
This requires defining metrics to be used by Turing machines to measure the creative abilities of the programmer. We may allow interaction between the algorithm and the programmer.

  How can we formalize such notion of AI? Has any similar idea been investigated before in TCS?

EDIT1: programmer here is a program that is able to generate other algorithms runnable on some computing device.

One motivation is whether intelligence of an algorithm is dependent on programmer's intelligence.

EDIT2: I'd like to formalize a notion for the intelligence and creativity of programs. Not all programs created equal. My question is an attempt to model and formalize aspects of intelligence that are not captured by current definitions of AI. For instance, Does an evolutionary algorithm possess any intelligence? If yes, What is the source of this intelligence?

EDIT3: My goal is to remove the subjectivity from Turing test. If the programmer is able to convince a Turing machine that it was the product of creativity of the programmer then the Turing machine is intelligent. Furthermore, the programmer is far more intelligent than the code he created. So, the challenge is how to formally convince the Turing machine that the programmer has superior computational abilities. In addition, the programmer must convince the Turing machine that those superior computational abilities are required and critical to the creation of the Turing machine code.


texts:
In a talk by Razborov, a curious little statement is posted.

  If FACTORING is hard, then Fermat’s little theorem is not provable in $S_{2}^{1}$.

What is $S_{2}^{1}$ and why are current proofs not in $S_{2}^{1}$?


texts: Simplest Machine Model for a langauge $ L = \{(w\# )^{k}\;|\; w\in \Sigma^{*},\;k\in \mathbb{N}\}$

texts:
What is the simplest machine model accepting the following language?

$$ L = \{(w\# )^{k}\;|\; w\in \Sigma^{*},\;k\in \mathbb{N}\}$$

In other words, $L$ is obtained by taking each string $w$ in $\Sigma^*$,
and then creating the strings $w\#\;,\; w\#w\#\;,\; w\#w\#w\#\;,...$

Here $\#$ is a separator symbol which is not in $\Sigma$.

The simplest I could think of was queue automata with $2$-queues. But these are already Turing complete. Is there some well studied class of machines that is not Turing complete and accepts $L$?


texts: Looking for a quotation by Edsger Dijkstra

texts:
In one of his papers Edgser Dijkstra makes a statement like:

"What we consider to be the standard case is one case among many exceptional cases only it occurs more often " or something along such lines.

Does any one know the paper it came from or the exact quotation?


texts: A basic question about bitcoin's anti double spending mechanism

texts:
Note: much more basic than: Bitcoin and preventing double spending in decentralized digital currencies

I'm trying to understand the concern that bitcoin's chain of blocks technique tries to solve (see http://www.bitcoin.org/bitcoin.pdf). Warning: not a crypto-dude, be tolerant.

I understand that basically we're worried about "double spending". I'm able to grasp this idea when talking about discrete, indivisible coins. E.g. there are only 3 coins in the world, which cant be divided to cents, and we need to track the history of all 3, and to make sure that each payer really had the coin he claimed to have while paying with it.

While I'm able to see how this concept extends to millions of coins, I can't get how does it extend to fractions of coins. How does a "double spending" attack scenario actually looks like? how do the honest nodes scrutinize a nominated new block, after some node proposes it as the new head node? please provide me with some illustrative examples...


texts: Arithmetic circuits with just one threshold gate

texts:
When restricted to $0$-$1$ inputs, every $\{+,\times\}$-circuit $F(x_1,\ldots,x_n)$ computes some
function $F:\{0,1\}^n\to \mathbb{N}$. To obtain a boolean function, we can just add
one fanin-1 threshold gate as the output gate. On input $a\in\{0,1\}^n$, the resulting threshold  $\{+,\times\}$-circuit then outputs $1$ if $F(a)\geq t$,
and outputs $0$ if $F(a)\leq t-1$; the threshold $t=t_n$ can be any positive integer, which may dependent on $n$ but not on input values. The resulting circuit computes some (monotone) boolean function
$F':\{0,1\}^n\to \{0,1\}$.

Question: Can threshold $\{+,\times\}$-circuits be efficiently simulated by  $\{\lor,\land\}$-circuits?

Under "efficiently" I mean "with at most a polynomial increase of size."
The answer is clear "yes" for threshold $t=1$: just replace $+$ by $\lor$, $\times$ by $\land$, and remove the last threshold gate. That is, $\{\lor,\land\}$-circuits are in fact threshold-$1$
$\{+,\times\}$-circuits.
But what about larger thresholds, say, $t=2$?

One can define arithmetic analogues $\#C$ of most boolean circuit classes $C$ by just using $+$
instead of OR, $\times$ instead of AND, and $1-x_i$ instead of $\bar{x}_i$.
For example, $\#AC^0$ circuits
are $\{+,\times\}$-circuits of constant depth with unbounded fanin $+$ and $\times$ gates, and inputs $x_i$ and $1-x_i$.
Agrawal, Allender and Datta have shown that  threshold $\#AC^0$ = $TC^0$. (Recall that $AC^0$ itself is a proper subset of $TC^0$; take, say, the Majority function.) In other words, constant-depth threshold circuits can be efficiently simulated by
constant-depth $\{+,-,\times\}$-circuits, with just a single threshold gate!
Note, however, that my question is about monotone circuits (no Minus "$-$" as gates, and even no $1-x_i$ as inputs). Can one (last) threshold gate be so powerful also then?
I don't know this stuff, so any related pointers are welcome.

N.B. There is yet another interesting related result  due to Arnold Rosenbloom: $\{+,\times\}$-circuits with just one monotone function $g:\mathbb{N}^2\to\{0,1\}$ as output gate can compute every slice function with $O(n)$ gates.
A slice function is a monotone boolean function which, for some fixed $k$, outputs $0$ (resp. $1$) on all inputs with less (resp., more) than $k$ ones. On the other hand, easy counting shows that most slice functions require general $\{\lor,\land,\neg\}$-circuits of exponential size. Thus, one "innocent" additional output gate can make monotone circuits omnipotent! My question asks
whether this can also happen when $g:\mathbb{N}\to\{0,1\}$ is a fanin-$1$ threshold gate.

ACTUALIZATION (added 03.11.2014): Emil Jeřábek has shown (via an amazingly simple construction, see his answer below) that the answer is "yes" as long as  $t\leq n^c$ for a constant $c$.
So, the question remains open only for super-polynomial (in $n$) thresholds.

Usually, in applications, only large thresholds do work: we usually need thresholds of the form $2^{n^{\epsilon}}$ for $\epsilon > 0$. Say, if $F:\{0,1\}^n\to \mathbb{N}$ counts the number of $s$-$t$ paths in graph specified by the $0$-$1$ input, then for $t=m^{m^2}$ with $m\approx n^{1/3}$, the threshold-$t$ version of $F$ solves the existence of a Hamiltonian $s$-$t$ path problem on $m$-vertex graphs (see, e.g. here).

(Added 14.11.2014): Since Emil answered a big portion of my question, and since the case of exponential thresholds is not in sight, I now accept this Emil's (very nice) answer.


texts: The meaning of: a program P posseses a property R

texts:
I am reading an article called The temporal semantics of concurrent programs
.

A construction is then given for assigning to a program P a temporal
formula W(P) which is true on all proper execution sequences of P.
In order to prove that a program P posseses a property R, one has only
to prove the implication $$W(P)\supset R$$
My question is this: Didn't they get the containment the other way
around ?

If I understand correctly, a property,R, is a set of traces, for P
to hold the property each trace of P needs to be in R, hence $$W(P)\subset R$$
Do I understand something wrong here, or is there a mistake in the


texts:
I'm searching for an algorithm that can calculate a suboptimal solution for:

color a graph with 3 colors
some vertices already have a color and can't be changed
the edges have values and the algorithm has to search for a solution where the sum of all the values of all the edges with vertices with the same color is smallest

this is for a practical problem:
a wireless network with wireless accesspoints (vertices)
you can ask the accespoints what neighbors they see and with what signal strength and i can create a graph out of that information
some accespoints are not part of the network, and already have a channel assigned

and accespoint can only have 3 channels that don't interfere (1,6,11) these are the 3 colors

does anyone know a good algorithm  that is powerful enough to solve this?

i heard this was used somewhere in cpu theory, where registers are already filled in (colored)
and you need to assign registers to some programs (colors)
but i can't find it


texts: Finding a path with certain properties in a directed graph

texts:
Define a directed graph $G(V,E)$. We divide its vertex set $V$ into $t$ partitions: $p_1, p_2, \ldots, p_t$. Suppose we have a path $v_1 \to v_2 \to v_3 \to \ldots \to v_n$ where the same vertex can be visited multiple times.

We define the valid point of partition $p_i$ as the last point $\in p_i$ appearing in the abovementioned path. For example, if the path goes through $y, x, z$ and $y, x, z \in p_i$ holds, the valid point of $p_i$ is $z$.

Given $k$ vertices as input (we guarantee that these $k$ vertices belong to different partitions), if there exists an $s-t$ path, such that all these $k$ vertices are all valid points of their respective partitions.

Can we find a polynomial-time algorithm?


texts: Minimize makespan on identical machines when jobs are vectors

texts:
Given are $n$ $d$-dimensional vectors and $m$ machines where $d$ need not be fixed. The objective is to minimize the makespan i.e., assign the vectors to machines such that the maximum of the component-wise sum is minimized over all machines.

I would like to know is there any constant factor approximation algorithm for this problem and is there a generalization of list scheduling to this problem, if so what is its worst-case ratio?


texts: Finding a common factor in $\lambda$-terms that agree under certain substitutions

texts:
Suppose that $\mathcal{L}$ is the language of a simply typed lambda calculus of two base types, $e$ and $t$, with infinitely many constants at each type.

A substitution $j$ is a mapping from constants of type $\sigma$ to arbitrary closed $\mathcal{L}$-terms of type $\sigma$. $j$ extends to a mapping on arbitrary closed terms of type $\sigma$ in the obvious way: $j\alpha$ is the result of substituting the constants in $\alpha$ with their $j$ counterparts.

Now suppose that for each constant $a:e$ there is a term $\phi^a: t$, and suppose moreover that:

For any substitution, $j$, if  $ja = jb$ then $j\phi^a =_{\eta\beta} j\phi^b$

Does it follow that there exists a closed term $\alpha:e\to t$ such that $\phi^a =_{\eta\beta} \alpha a$ for each constant $a$?


texts: Graph nodes preserving changes to the overall graph

texts:
I remember reading about a kind of Graph data structure, where every change to the the graph could be preserved. I don't remember exactly neither the name, neither a good description (if it was the graph that remembered the changes, or each node who kept the changes of its childs).

It was on Wikipedia about 2-1.5 years ago, I was reading about version control. I would really appreciate if someone could help me find the name of this data sctructure.

Thanks Fraser, the paper is J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan, Making Data Structures Persistent, Journal of Computer and System Sciences, Vol. 38, No. 1, 1989.


texts: Order of operations in 2 and 3 phase atomic commit protocols

texts:
I am currently reading through this http://research.microsoft.com/en-us/people/philbe/chapter7.pdf chapter about distributed recovery. The chapter focuses on 2 phase atomic commit (2PC) and 3 phase atomic commit (3PC). Two related questions have me stumped.

  7.11: In  the  2PC protocol  the  coordinatorfirst  decides Commit  (by  writing  a  commit  record  to  its  site’s DT  log)  and  then
  sends COMMIT  messages to  the  participants.  Suppose  the  order  of
  these  two  steps is  reversed.  Show  that  this  variation  of  2PC
  is  non-blocking  if

  a.  there  are no  communication  failures  and  at most  one process
  can  fail,

  or

  b.  there  are no  communication  failures  and  processes have  the
  ability  to  broadcast  messages atomically  (i.e.,  so that  either
  all  recipients  get  it  or  no  recipient  does).

  How  does  this  variation  of  2PC  affect  the  recovery
  procedures?  Give  recovery  procedures  that  work  for  the
  modified  2PC  protocol.

  7.22: In  3PC,  does the  relative  order  of  sending  COMMIT  messages and  writ-  ing  a commit  record  in  the  DT  log  matter?
  What  about  the  relative  order  of  sending  ABORT  messages and
  writing  an  abort  record?

The first does not seem particularly hard, but I am unsure of how to actually prove that a program is non-blocking. The second question is a bit more complex. My intuition is that 3PC has enough built in safeguards with the PRE-COMMIT phase that changing the order wouldn't matter, but again I am uncertain of what a proof of this would look like.


texts: Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers

texts:
It is often said that memoization brings the complexity of recursive-descent parsers
from exponential to polynomial. However, I had a hard time finding an example grammar
that triggers the exponential case.

Because recursive descent parsers cannot (naturally) deal with left-recursion,
the example should not contain left-recursive rules.
BTW, I'm familiar with PEG and Packrat parsers, and I'm not looking for examples
in the that domain. To be more precise, can someone please give me a non-left-recursive
context-free grammar that triggers exponential behaviour?


texts: Winning strategy of an "edge or isolated vertex" deletion game

texts:
Is this perfect information game played on graphs know/studied?

Given a graph $G= (V,E)$, two players alternate picking an edge or an isolated node. If the player picks an edge $e = (u,v)$ the two nodes $u$ and $v$ are deleted along with their incident edges. If the player picks an isolated node, the node is deleted. The first player unable to move loses the game.

What is the complexity of finding the winner?

Any references to similar games?


texts: What should a proof of correctness for a typechecker actually be proving?

texts:
I've been programming for several years, but am very unfamiliar with theoretical CS. I've recently been trying to study programming languages, and as part of that, type checking and inference.

My question is, if I try to write a type inference and checking program for a programming language, and I wish to prove that my typechecker works, what exactly is the proof I'm looking for?

In plain language, I want my type checker to be able to identify any errors in a piece of code that might occur at runtime. If I were to use something like Coq to try proving that my implementation is correct, what exactly will this "proof of correctness" be trying to show?


texts: What does it mean for CvRDT replicas to transmit their state "infinitely often"?

texts:
In Shapiro et al.'s SSS '11 paper on Conflict-Free Replicated Data Types for eventual consistency of distributed replicated objects, they describe a system model in which replicas transmit their state to one another "infinitely often".  On the receiving end, a replica can merge the received state with its own local state by executing a method m.

In the case of convergent replicated data types, or CvRDTs, the states a replica can take on are elements of a (join-semi)lattice, and the m operation takes the join of the the received state and the local state with respect to the lattice.  Also, replicas can update their local state (by calling an update method, u), but only in a way that is inflationary with respect to the lattice (that is, the state can only "get bigger").

My questions have to do with the "infinitely often" bit, and are as follows:

Is it just the state transmission that occurs infinitely often, or also the calls to m?  That is, does the process running at some replica have to explicitly call the m method in order to do a merge, or are these merges happening infinitely often "in the background"?  (It seems to me that it must be happening infinitely often in the background, because otherwise, if a process didn't call m at the end of its run, then its replica wouldn't converge with the others, breaking the eventual consistency guarantee that CvRDTs provide.)
But, if merges occur infinitely often, do updates to a CvRDT really have to be inflationary?  In the presence of infinitely-often merges, it seems like if a non-inflationary update ever happened, that update would just be lost -- which would be unfortunate, but wouldn't actually pose a problem for convergence.  When I look at the proof that CvRDTs are eventually consistent, I don't see the place that the inflationary condition on the u method is required.  Why exactly does u have to be inflationary?
Finally, the definition of causal history in the paper seems fishy if merges are really happening "infinitely often", because if so there would be "no room" for any other method execution to occur! The k'th method execution would have to be a merge, for all k, wouldn't it?  Am I taking "infinitely often" too literally?  (Update: Yes, I am taking it too literally!  See below.)

Thanks!

(Update: After a Twitter discussion with Niklas Ekström, I understand the meaning of "infinitely often" better.  If an event occurs "infinitely often", that doesn't mean anything about the frequency of it occurring; it just means that the event occurs an infinite number of times.

So, if event X occurs infinitely often, and some other event Y occurs once (or some finite number of times), then X is guaranteed to occur after Y, because infinitely many occurrences of X cannot all occur before the occurrence(s) of Y.  And here, in particular, there is no way for a replica to update itself and for the neighbors not to find out, because a state transmission will always occur after that update (because there are infinitely many state transmissions, and therefore they can't all occur before that update!).

I'm still not sure if I should be thinking of state transmissions and merges as happening infinitely often, or just state transmissions.  But, even if merges also occur infinitely often, my comment above about there being "no room" for any other event to occur doesn't make sense, considering what "infinitely often" actually means.)


texts: Relationship between contracts and dependent typing

texts:
I've been reading some articles on dependent types and programming contracts. From the majority of what I've read, it seems that contracts are dynamically checked constraints and dependent types are statically checked.

There have been some papers that have made me think that it's possible to have contracts that are partially statically checked:

Hybrid Type Checking (C. Flanagan - 2006)
Unifying Hybrid Types and Contracts (J. Gronski, C. Flanagan - 2007)

With this, there seems to be a significant amount of overlap and my categorisation of contracts vs dependent types starts to disappear.

Is there something deeper in either concepts that I'm missing? Or are these really just fuzzy categories of representing the same underlying concept?


texts: Has there been any progress in tightening the exponent in the result that polylog independence fools $AC_0$?

texts:
Braverman showed that distributions which are $(log \frac{m}{\epsilon})^{O(d^2)}$-wise independent $\epsilon$-fool depth $d$ $AC^0$ circuits of size $m$ by "gluing together" the Smolensky approximation and the Fourier approximation of $AC^0$-computable Boolean functions. The author and those who had conjectured this originally conjecture that the exponent there can be reduced to $O(d)$, and I am curious if progress has been made towards this, as I'd imagine it would involve producing a polynomial which is close in correlation distance as well as actually agreeing with the function on a large number of inputs, and I think it would be a very interesting approximation to find without gluing these two together. Is there some reason to expect that such an approximation must have degree $O(d^2)$ that wasn't known when Braverman wrote his paper in 2010?

Another question about this paper I have is that the original conjecture resembles Boppana's bound on sensitivity, though it was in a paper written prior to this bound. This, of course, isn't a coincidence, as this bound would correspond to the Fourier concentration you can derive from Boppana's bound if the Fourier polynomial worked, but is there any better intuition that you know of than that "if the Fourier polynomial worked, this is what you'd get" one?


texts: Is it decidable to determine if a given shape can tile the plane?

texts:
I know that it is undecidable to determine if a set of tiles can tile the plane,
a result of Berger using Wang tiles.
My question is whether it is also known to be undecidable to determine
if a single given tile can tile the plane, a monohedral tiling.

If this remains unsettled, I would be interested to know what is the minimum
cardinality of a set of tiles for which there is an undecidability proof.
(I have not yet accessed Berger's proof.)


texts:
What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: Goldreich-Levin theorem about hard core bit, Trevisan's construction of extractor and amplification of hardness of boolean function (by Sudan-Trevisan-Vadhan).

What are other 'serious' or 'recreational' applications of error-correcting codes?

UPD: one amusing application of list decoding of Reed-Solomon codes is a solution to particular variation of 20 questions game (and another, more straightforward, variation).


texts: Depth of bounded fan-in circuits for unbounded fan-in circuits

texts:
Assume that we have an unbounded fan-in circuit family of depth $d(n)$ and size $s(n)$.

What is the smallest depth (in terms of $d(n)$ and $n$ and $s(n)$) bounded fan-in circuit family of size $poly(s)$ for it?

In particular what is the largest depth $d(n)$ for which we know polynomial size unbounded fan-in circuit families of depth $d(n)$ are in $\mathsf{NC^1}$?


texts: Can polynomial-sized circuits use garbage?

texts:
This is a non-uniform (and simplified) version of my previous question about Cook reductions. Let $R\subseteq \{0,1\}^*\times\{0,1\}$. A function $r\colon \{0,1\}^*\to\{0,1\}$ solves $R$ if $(x,r(x))\in R$ for all $x\in\{0,1\}^*$. Let $f\colon\{0,1\}^*\to\{0,1\}$. Consider the following two properties.

There are polynomial-sized circuits using AND,OR,NOT and "$r$" gates, such that for all choices of function $r$ solving $R$, the circuits compute $f$.
For all choices of function $r$ solving $R$, there are polynomial-sized circuits that compute $f$, using AND,OR,NOT and $r$ gates.

Does (2) imply (1)? A negative answer would mean that there's a problem $f$ that can be computed using any particular choices of $r(x)$, but cannot be computed efficiently if we do not fix particular choices of $r(x)$. The funny thing here is that the only obstacles are inputs $x$ with $(x,0),(x,1)\in R$.


texts: Are lambda calculus and combinatory logic the same?

texts:
I am currently reading "Lambda-Calculus and Combinators" by Hindley and Seldin.  I'm not an expert, but have always taken an interest in lambda calculus because of involvement with functional programming (starting with Lisp and SICP, and now with R and Haskell).

In "Binary Lambda Calculus and Combinatory Logic", John Tromp states:

  CL may be viewed as a subset of lambda calculus...the theories are largely the same,
  becoming equivalent in the presence of the rule of extensionality.

Under what conditions would one use combinatory logic instead of lambda calculus?

Any references would be appreciated.


texts: Do there exist two equivalent objective functions one of which can be approximated but another one cannot?

texts:
I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below are the definitions.
Problem A: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$ each of which is not greater than the corresponding weight (i.e., $0<v_h\leq w_h$ ($1 \leq h \leq i$)), and a bag with capacity $B=\sum_h v_h$, we want to insert items into the bag without exceeding the capacity $B$ while maximising the total values (i.e., maximising $\sum_{h=1}^i p_h*v_h$ subject to (1) $p_h=0$ or 1, (2) $\sum_{h=1}^i p_h*w_h \leq B$ ).
Problem B: we have the same inputs and constraints as A. The objective function is different which is minimizing $B-\sum_{h=1}^i p_h*v_h$.
Approximation ratio analysis: Suppose $X$ is the value returned by an approximate algorithm for Problem A, $OPT$ is the optimal value. Then for problem A, the ratio is $\alpha \leq X/OPT$. If the algorithm is greedy algorithm, $\alpha$ is $1/2$. On the other hand, for problem B, the ratio is $(B-X)/(B-OPT)$ which can be infinity large when $OPT$ is close to $B$.
So my question is: (1) can we use approximate algorithms in problem A to solve problem B with approximation ratios? (2) Even if we have specialised algorithms for problem B, the denominator $(B-OPT)$ still can be very small. Can we find approximate solutions for problem B?


texts: Algorithms and computational complexity of clique and biclique covers

texts:
I've been reading a paper by a mathematical chemist.  He proposes some indices to measure the complexity of molecules.  From here on in, instead of molecules, think undirected connected graphs: a vertex is an atom, and an edge is a bond between atoms.  It's possible to consider colorings of the vertices, to tell the Nitrogens apart from the Carbons, say, but I'll ignore that part for now.

The point: the indices he suggests are motivated by heuristics and experimental "looks good so far"-ness.  I think there must be some actual theory known about some of these quantities, and I'm hoping to get some pointers here.

Fix a graph $G$.  Let $C$ and $C'$ be two covers of $G$.  Say $C$ and $C'$ are the same kind of cover if they contain the same types of subgraphs in equal numbers.  (Note $C$ and $C'$ do not have to be isomorphic.)  Now we define the following quantities:

$k_S(G) =$ number of kinds of minimal edge clique covers of $G$
$k_T(G) =$ total number of minimal edge clique covers of $G$
$k^{bi}_S(G) =$ same as $k_S(G)$ but for bicliques
$k^{bi}_T(G) = $ same as $k_T(G)$ but for bicliques
$p_S(G) =$ number of kinds of partitions of the edges of $G$ into cliques
$p_T(G) =$ total number of partitions of the edges of the graph into cliques
$p^{bi}_S(G), p^{bi}_T(G)$ as above, but with partitions of $G$ into bicliques

Empirically, it is apparently easier to calculate the $p$ measures than it is to calculate the $k$ measures.  I expect something must be known somewhere about calculating some of these quantities.  Can anyone provide algorithms, computational hardness, etc.?  Thanks.


texts: Type theory and computational complexity

texts:
Is there a type system, which restricts the lambda terms to the terms which fall inside a complexity class? Like the typable terms in the theory are strictly inside the complexity class ? Or is it not possible at all?

I find the there are lot of studies on expressibility of the type theory, like provably terminating, extended polynomials etc.. But is there any way to restrict that to a complexity class?


texts: Does Nisan's pseudo-random generator relativize?

texts:
Nisan proved in "Psuedorandom Generators for Space-Bounded Computation",
that there exists a pseudo-random generator which "fools" space-bounded computations.
Does this construction hold for every oracle (at least for non-adaptive queries) ?


texts:
I want to define a notion of "closeness" between two regular languages of finite words in $\Sigma^*$ (and/or infinite words in $\Sigma^\omega$). The basic idea is that we want two languages to be close if they don't differ by many words. We could also use the edit distance in some way... I could not find good references on this issue.

I don't call it a distance because I don't require all the distance axioms to be true (although it's not bad if they are).

A first attempt is to define $$d(L,K)=  \limsup_{n\to\infty} \frac{|L_n\Delta K_n|}{|L_n\cup K_n|}$$ where $L_n$ and $K_n$ are the restrictions of $L$ and $K$ to $\Sigma^n$, and $\Delta$ is the symmetric difference.

Is this "distance" studied? Are there references on the subject (possibly with alternative choices for distance function)? Any help or pointer would be appreciated, thanks.


texts: What is known about NP hard problems that access preprocessed information?

texts:
Please accept my apologies ahead of time since I fear that this isn't an adequate question for cstheory.  I plan on releasing my ideas to get feedback, but I don't know if my target audience will include state-of-the-art reaseachers.  I'd like to know more about the research that is already out there concerning this question.

Essentially, what I think I've discovered is an oracle.  The oracle must be precomputed, which will probably take an exponential amount of time.  However, once computed, it can essentially answer any question about 3-SAT fast.  In other words, it can then solve any 3-SAT problem in polynomial time/space.  I'm wondering what has been researched in this scenario.

MY ORIGINAL QUESTION

As an armchair cstheory enthusiast, I'm now working on a way to preprocess 3-SAT.  I'm wondering how this relates to research on oracles and related ideas.  Please let me briefly describe my method, or conjectured approach.

We take a given problem size.  Essentially we have exactly $2^n$ clauses and $v$ variables.  (Note that problems smaller than this can automatically be solved, too.)  After we know the maximum amount of clauses, we can preprocess information for every possible 3-SAT clause, given the information just stated.  This may take an exponential amount of information, even for each individual clause.

However, once the information is preprocessed, we can solve 3-SAT fast.  In other words, using this pre-computed database, which is polynomial in size, we can determine satisfiability for a particular instance as well as generate a certificate in polynomial time and space.

So if I'm correct, we use an oracle and we can ensure that 3-SAT can be solved in polynomial time and space.  However, the oracle itself takes a possibly exponential amount of time and space to compute.

My question is where in the literature can I find information concerning pre-computing information (like I have described) to solve NP-hard and NP-complete problems in polynomial time and space?  What is known about this approach?  I don't mean to be vague, but I'm simply trying to find out what has been considered about an approach like this in the past.  I plan on eventually releasing my ideas if they are interesting, but I would like to know if they have already been researched.


texts:
From space-hierarchy theorem it is  known that if $f$ is space-constructible then
DSPACE($2f(n)$) is not equal to DSPACE($f(n))$.

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

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

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


texts: Defining inductive types in intensional type theory purely in terms of type-theoretic data

texts:
To define a (non-indexed) W-type all we need is a type $A:U$ and a function $B:A\to U$ and we get a type $W_{a:A}B(a)$. To check that this definition is valid we only need to check that the definitions of $A$ and $B$ are valid.
Now general inductive types seem like very scary beasts and I still don't entirely understand what a proof checker kernel (e.g. in Coq) is doing to make sure the definition is valid.
In intensional type theory there is apparently a big gap between W-types and general inductive types. For example the generic W-type recursion applied to the W-type encoding of unary natural numbers is not as strong as standard recursion for natural numbers.
So the question is: is there a way to set up inductive types so that to check the validity of a definition you only need to check the validity of finitely many non-inductive typing judgements?
A strongly normalizing type theory can't fully interpret itself but I guess we could have a partially defined quote unquote specifically for the bits of data necessary to define inductive types. Can you suggest any references?


texts:
The following is from this year's CS GRE practice test. I've worked through the test and I've been able to understand every question except for this one. Can anyone help me understand what's going on here?

  Question:

  Let $T$ be a depth-first search tree of a connected undirected graph $G$. For each vertex $v$ of $T$, let $pre(v)$ be the number of nodes visited up to and including $v$ during a preorder traversal of $T$, and $post(v)$ be the number of nodes visited up to and including $v$ during a postorder traversal of $T$.

  The lowest common ancestor of vertices $u$ and $v$ in $T$ is a vertex $w$ of $T$ such that $w$ is an ancestor to both $u$ and $v$, and no child of $w$ is an ancestor of both $u$ and $v$.

  Let $(u,v)$ be an edge in $G$ that is not in $T$, such that $pre(u) < pre(v)$. Which of the following statements of $u$ and $v$ must be true?

  $post(u) < post(v)$
  $u$ is an ancestor of $v$ in $T$.
  If $w$ is the lowest common ancestor of $u$ and $v$ in $T$, then $w = u$.

I'm not going to post the answer just yet. If you're interested, it's available in the PDF:

http://www.ets.org/Media/Tests/GRE/pdf/CompSci.pdf

I think that none of these can be true, based on the following:

If $u$ is an ancestor of $v$ and $v$ is a leaf, then this would be false because leaves are counted first by postorder traversal.
If $u$ is a left sibling of $v$, then $u$ is counted first by preorder traversal, but $u$ is clearly not an ancestor of $v$.
This statement is equivalent to #2, and could be false by the same argument.

I think it goes without saying that the test answers say I'm wrong about this. Am I missing something here? Can anyone provide an explanation as to why I'm wrong, as well as how to arrive at the correct answer?

Thanks!

EDIT:

Per Sadeq's request, I've included a counter example to #2/#3:

Counter Example http://img39.imageshack.us/img39/6410/counterexample.png

The graph $G$ is shown in the image. If we remove the edge between $A$ and $D$, then we get the tree $T$. Now we have the following:

$(u,v)\in G - T$
$pre(A) < pre(D)$
$A$ is not an ancestor of $D$ in $T$.


texts: What is the VC Dimension of the $k-$Junta class

texts:
A boolean function $f(x_1,x_2,\dots,x_n)$ is $k$-Junta if it depends on at most $k$ variables. Consider the class $\mathcal{J}_{\leq k}$ of all $k$-Juntas over $n$ variables, what is the VC dimension of this class?

Or at least is there any known method to construct the largest shattered set for small values of $k$ say when $k=1$.


texts: Complexity to calculate a full set of eigenvectors over a finite field

texts: Let a full rank $n\times n$ matrix ${\bf A}$ with elements over $\mathbb{GF}(2)$. What is the worst case complexity to calculate $n$ linearly independent (over $\mathbb{GF}(2)$) vectors, such that each one of them obeys $${\bf A}{\bf x} = {\bf x}$$ again over $\mathbb{GF}(2)$.


texts: Examples of learning via exactly integrable gradient flows

texts:
If $\ell (\vec{w}, \vec{z})$ is the loss function at weights $\vec{w}$ and for data $\vec{z}$ then corresponding to a distribution ${\cal D}$ we can consider doing gradient flow with step-length $\eta >0$ to solve the corresponding risk minimization question,
$$\frac{d \vec{w}}{dt} = -\eta \cdot \frac{\partial }{\partial \vec{w}} \mathbb{E}_{\vec{z} \sim {\cal D}} [\ell (\vec{w}, \vec{z}) ]$$

Are there non-trivial examples of this for which the above ODE is exactly integrable and the risk gets minimized as $t \rightarrow \infty$ along the solution?


texts: What's the distribution of the Kolmogorov complexity of the elements in the set of bitstrings of length n?

texts: take e.g. all possible bitstrings of length n=10,000. there are 2^10,000 of them. imagine that for each of those strings we knew the length of the shortest program that could produce the string. what would the distribution of the lengths of those programs look like?


texts:
We have a problem and we found an algorithm that appear to be 2-nexptime.

I would like to find known 2-nexptime-complete problems in order to find a lower bound.

I found in literature mainly two such problems:

whether PCP as a solution of size less than $2^{2^n}$
and the tilling problem for a square of size $2^{2^n}$

However I was unable to encode these problems in mine. So I would like to know other 2-NEXPTIME-complete problems, first to have more intuition on this class, and second in the better case prove a lower bound.

I do not provide here the problem on purpose in order to have a broad overview of 2-NEXPTIME.

Thanks


texts: Neural Networks: Incorporate feature-specific knowledge

texts:
Has any research been done about / are people interested in incorporating prior knowledge of good high-level features into a deep neural net?

I know this somewhat defeats the purpose of feature learning but consider the following applied scenario: image classification task, 20 classes,  'small' training set (10k), expert human knowledge of high-level features.

Ideal would be to compensate for lack of training cases by incorporating knowledge of these features into the architecture (or via other means). How?


texts: Existence of bijective proofs involving Yamanouchi words?

texts:
The following notion comes from algebraic combinatorics and might have some connections to language/permutation theory. Fix an integer $k$. Let us call a $k$-Yamanouchi word a sequence $u$ of integers in $[k]$ such that (i) for every prefix $v$ of $u$, we have $|v|_k \geq |v|_{k-1} \geq \ldots \geq |v|_1$, (ii) when $v = u$, the equalities hold.

These words generalize the notion of Dyck words, which are basically 2-Yamanouchi words. It is well-known that Dyck words are counted by Catalan numbers and can be put in bijection with numerous objects (see e.g. here). On the other hand, $k$-Yamanouchi words are in bijection with Young tableaux of rectangular shape $k \times n$, and thus are counted by the "hook length formula":

$Y^k_n = \frac{(kn)!}{n! (n+1)! \ldots (n+k)!}.$

I'm not aware of any other known bijections involving $k$-Yamanouchi words, so I am asking for possible references or new bijections, involving for instance trees or permutations. A note of caution: these objects seem much harder to handle algebraically than Dyck words so it's not clear whether they can give rise to "well-structured" objects such as trees.


texts: SAT Solution Space - Definition of Cluster of Solutions

texts: I'm looking for a formal definition of Cluster of Solutions. My current understanding is the following. Let $x$ be a boolean assignment on $n$ variables. Let $f: \{ 0,1 \} ^n \to \mathbb{N}$ be a function that, given a boolean assignment $x$ on $n$ variables, just returns the natural number $i \in [0, 2^n-1]$ corresponding to $x$. Let $g: \mathbb{N} \to \{ 0,1 \} ^n$ be the inverse of $f$: given a natural number $i$, $g$ returns the corresponding solution (i.e. the binary encoding of $i$ in $n$ bits). Now, a Cluster of Solutions is a set $S$ of solutions such that, for each solution $x \in S$ and for each solution $y \in S$, it's the case that $g(i) \in S$ for each $i \in (f(x), f(y))$. Less formally, a Cluster of Solutions is a set whose solutions are "packed", i.e. "there are no non-solutions among the solutions". Is this definition correct?


texts: Worst-case optimal Delaunay algorithm based on spatial sort and walking?

texts:
Buchin [2] showed that under "reasonable" assumptions, (polynomial point spread) incremental construction of Delaunay triangulations using the biased randomized ordering of Amenta et al. [1] with a space filling curve takes $O(n \log n)$ even when points are located by walking from the last inserted point.  This reduces to $O(n)$ for uniformly random points if the BRIO jumps are treated carefully.

Question: Are there any "simple to compute" orders which are worst case $O(n \log n)$ for all general position inputs?  I am leaving "simple" intentionally vague, but roughly I mean simpler than computing the Delaunay triangulation itself (from which an optimal order is easy to derive).

Amenta, Nina, Sunghee Choi, and Günter Rote. "Incremental Constructions con BRIO." (2003).
Buchin, Kevin. "Constructing Delaunay triangulations along space-filling curves." Algorithms-ESA 2009. Springer Berlin Heidelberg, 2009. 119-130.


texts: Other norms for Lattice reduction techniques (LLL, PSLQ)?

texts:
LLL and other lattice reduction techniques (such as PSLQ) try to find a short basis vector relative to the 2-norm, i.e. for a given basis that has $ \varepsilon $ as its shortest vector, $ \varepsilon \in Z^n $, find a short vector s.t. $ b \in Z^n, ||b||_2 < ||c^n \varepsilon||_2 $.

Has there been any work done to find short vectors based on other, potentially higher, norms?  Is this a meaningful question?


texts: Aside from the cycle graph, are there other simple unweighted graph constructions for which there are $\omega(n)$ distinct min cuts?


texts: Turing machines whose termination is unprovable?

texts:
I have a naive question: does there exist a Turing machine whose termination is true but unprovable by any natural, consistent and finitely axiomatizable theory? I ask for a mere existence proof rather than a specific example.

This might have some connection with ordinal analysis. Indeed, for a Turing machine $M$, we can define $O(M)$ as the least ordinal of a consistent theory proving its termination (or the infimum of these ordinals). So I guess it would be equivalent to ask whether there exists $M$ such that $O(M) \geq \omega_1^{CK}$?


texts:
Background: Chao Xu posted the following question some time ago: "Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times?". It seems that we are a bit stuck with the problem; I have discussed the same problem with Valentin Polishchuk in 2009, and we got nowhere.

To get some fresh ideas, I tried to come up with the simplest possible question that has a similar flavour and is not completely trivial. Hence the following question.

Question: You are given two sorted lists, each of them with $n$ elements. Can you merge the lists so that each element is only compared $O(1)$ times?

Naturally, the output should be a sorted list that contains all $2n$ elements.

[This turned out to be trivial, the answer is "no".]

Question 2: You are given two sorted lists, each of them with $n$ elements. Can you merge the lists so that each element is only compared $O(1)$ times, if you are allowed to discard a small fraction of elements?

More precisely, the output should be a sorted list that contains $2n-T(n)$ elements, and a "trashcan" that contains $T(n)$ elements. How small can you make the value $T(n)$? Getting $T(n) = n$ is trivial. Something like $T(n) = n/100$ should be doable in a straightforward manner. But can you get $T(n) = o(n)$?

Notes:

We use the comparison model here. Deterministic algorithms only, we are interested in the worst-case guarantees.
Note that both lists have exactly $n$ elements. If we had one list with $n$ elements and another with $1$ element, the answer is clearly "no"; however, if both lists are long, it seems that one might be able to do some "load balancing".
This time any kind of algorithm is valid. If your algorithm uses sorting networks as a building block, it is perfectly fine.
For a starting point, here is a simple algorithm that compares each element for at most 200 times: Just use the standard merge algorithm, but maintain counters for the heads of the lists. Once you reach 200, discard the element. Now for each element that you discard, you have successfully placed 200 elements in your output array. Hence you have achieved $T(n) = n/100$.


texts: Three questions about finite state machines

texts:
Suppose a finite state machine, FSM, has a fixed set of states $S$ and input/output channels $C$, and is uniquely specified by the fixed map $m : S\times D \to S\times D\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it enters a loop and cant exit.

Clearly, if we join together pairwise any of the input/output channels of one or more FSM's, we obtain a new FSM.

Is there a finite set of FSM's, by which any other FSM can be built (using a finite number of each), by connecting channels pairwise?

Can every FSM be built by the two state, 3 channel, FSMs specified by the map:
(A,1)->(B,2),(B,2)->(A,1),(B,1)->(B,1),(A,2)->(C,1),(C,1)->(A,2),(C,2)->(C,2)

Is there a general algorithm, given a set of FSMs, and a target FSM, to determine if the target can be built by any combination of any number of FSM's in the set?


texts: Given a sequence find the shortest reg exp that generates it?

texts:
I'm looking for a way to find the smallest possible regular-expression that accepts a sequence.

To make it interesting I don't want any stars(Kleene stars) and preferably no wildcards?

For instance the sequence : 'aaaaaaaa' would be accepted by 'a^8' and a^8 would be the shortest possible expression to accept the sequence.

Does anyone body know how to generate such an expression?


texts: Does there exist polytime algorithm for this partitioning problem?

texts:
I would like to know if there exists a polytime probablistic algorithm for the problem described below. It is relevant for construction of a crossvalidation-partitioning in statistics, fulfilling certain constraints.

Or is it maybe NP-complete? I don't see any direct connections to any NP-complete problem I know of.

Input: $(N,K, (\phi_1, \ldots, \phi_l))$

Informal description:

Let $ \{1 \ldots N\}$ be partitioned according to functions $\phi_1, \ldots, \phi_l$. Find a random partition $\Phi : \{1\ldots N\} \rightarrow \{1\ldots K\}$ s.t. for all $i$, elements with the same value under $\phi_i$, will get at least 2 different values under $\Phi$. Furthermore, the new partitioning should be balanced.

If no solution exists, halt with error.

Formal description:

Let $N, K \in \mathbb N$, and $\phi_i : \{1 \ldots N\} \rightarrow \{1 \ldots m_i\}$ be given for $i \in \{1 \ldots l\}$.

Find a random $\Phi : \{1\ldots N\} \rightarrow \{1\ldots K\}$ s.t.
$$
\forall i\in \{1 \ldots l\} :\forall v \in \{1\ldots  m_i\} : |\Phi( \phi_i^{-1}(v) )| \geq 2
$$
$$
\forall v \in \{1\ldots K\} :\left\lfloor \frac{N}{K} \right\rfloor \leq |\Phi^{-1}(v)| \leq \left\lceil \frac{N}{K} \right\rceil
$$


texts: Nondeterminism is on average useless for circuits?

texts:
Savický and Woods (The Number of Boolean Functions Computed by Formulas of a Given Size) prove the following result.

  Theorem[SW98]: For every constant $k>1$, almost all boolean functions with formula
  complexity at most $n^k$ have circuit complexity at least $n^k/k$.

The proof consists of deriving a lower bound on $B(n,n^k)$, the number of boolean functions on $n$ inputs computed by formulas of size $n^k$. By comparing $B(n,n^k)$ to the number of circuits of size $C = n^k/k$, which is at most $C^{C}e^{C+4n}$, it can be realized that for large $n$, $C^{C}e^{C+4n} << B(n,n^k)$, and the result follows.

It looks to me that the result could be strengthened by noting that the number of nondeterministic circuits of size $n^k$ with $m$ nondeterministic inputs is not much larger than the number of deterministic circuits of size $n^k$ (for $m$ not too large, say $m=n$). Hence, I think the following corollary holds:

  Corollary: For every constant $k>1$, almost all boolean functions with formula
  complexity at most $n^k$ have nondeterministic circuit complexity at least $n^k/k$ (for nondeterministic circuits with $n$ nondeterministic inputs).

(Recall that a nondeterministic circuit has, in addition to the ordinary inputs $x = (x_1,\dots,x_n)$, a set of "nondeterministic" inputs $y=(y_1,\dots,y_m)$. A nondeterministic circuit $C$ accepts input $x$ if there exists $y$ such that the circuit output $1$ on $(x,y)$).

Obviously, the lower bound on $B(n,n^k)$ is also a lower bound on the number of boolean functions on $n$ inputs computed by circuits of size $n^k$, hence "formula complexity at most $n^k$" can be replaced by "circuit complexity at most $n^k$" in the corollary. The corollary can also be stated as: for functions with polynomial circuit complexity, switching to nondeterministic circuits cannot, on average, decrease the complexity by more than a constant factor.

  Questions:

  (1) Are there any interesting implications/consequences of the corollary above?

  (2) Are there any other results in the same direction? For example, what is known about the following proposition? For problems in P, switching from TMs to NTMs cannot, on average, decrease the complexity by more than a constant factor.

(Gil Kalai also has a  question  somewhat related to this one.)


texts: Proofs techniques related to Curry–Howard correspondence

texts:
I am looking for sources about formalized notion of programs. This seems to be closely related to Curry-Howard correspondence, but one could also track this back to Universal Turing Machines and its ability to read description and input of any TM.

When reading about Curry-Howard correspondece I feel that the primordiality of UTM-s can harm research on programs with the unique conclusion that any program can be reduced to symbols, states and rules. Does there exist the opposite approach, where high-level computation systems are defined and examined? What are good resources about it?


texts: What exactly does "semantically observable" side-effect mean?

texts:
I have question regarding pure functions. According to the Wikipedia page one of the requisites for a pure function is :

  Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices.

Now what does this really mean. Or rather how can i make a side effect which is not semantically observable?


texts:
Recently, a friend of mine (working in TCS) mentioned in a conversation that "he wanted to see/know all (or as much as possible) of the beautiful results in TCS in his lifetime". This kind of made me wonder about the beautiful results in this area and hence the motivation for the following question:

Which results (or ideas), in your opinion, are beautiful in theoretical computer science? It would be great if you mentioned the reason as well.
[Would also be fine even if the ideas originate in mathematics, but have aroused interest and found uses in TCS]

I would start with an answer as Cantor's diagonal argument because it's simple, elegant and yet a powerful result.


texts: Number theoretic problems complete for $\mathsf{RL}$

texts:
Are there number theoretic problems (such as those related to $\mathsf{gcd}$) that are in $\mathsf{RL}$?

Can these also be $\mathsf{RL}$-complete problems (is there any $\mathsf{RL}$-complete problem at all)?


texts:
I have the following problem:
I'm developing a software for data visualization where I get a graph structure and represent it in 3D space. So far, I've been using force-based algorithms to draw graphs and it worked well, until I got requirement that my software should represent very big number of vertices and edges (few millions). It would be very impractical to hold all those in memory, so I'm looking for an algorithm that will enable me to stream small portions of graph as I "walk" through the space.

However, the main problem is in showing and dynamically repositioning of vertices, since I don't have already predefined positions, and I must get them from graph.

Can you point me to some algorithms for incremental drawing and streaming of graph? (and yes, I Googled a lot :))

Thanks in advance!


texts: Finding a largest symmetrical subset of a k-CNF propositional formula

texts:
I have a k-CNF propositional formula $F$ which do not admit any global symmetry i.e. there is no permutation $\sigma$ of its variables such that $\sigma(F) = F$ . I'm interested in finding the largest (in term of number of elements) subset of clauses in $F$ which admit at least one symmetry.

A brute force approach could be to generate all the subsets of $F$ in descending order of their sizes and test whether they admit at least one symmetry. The test here could be performed via the reduction to the graph automorphism problem. But this approach could be unusable for large formulas.

How can I efficiently determine such a subset of $F$ ? By efficient here, I mean an algorithm that performs well in practice but that is not necessary polynomial.

Is the complexity of this problem similar to that of the Max-SAT problem?


texts: efficient data structures for generalized tensor products

texts:
The usual tensor product of vectors is a matrix.  There has been tons of research into efficiently storing and operating on matrices in computers.

But we can generalize the tensor product quite a bit.  For example, a monoid is like a vector that's forgotten a lot of it's properties.  The only structure it has is associative addition.  We can take the tensor product of two monoids to be the "most general, generalized bilinear operator."  See this paper for an example on the constructing their tensor product in the commutative case.

My question is: what are some efficient data structures for representing these generalized tensor products on a computer?


texts:
Has it been charaterized the cost of the translation from LTL with Past to LTL?

In [Gab89] this translation is assumed to be non elementary and in "Temporal Logic with Past is Exponentially More Succinct" is described a detour of complexity 3EXPTIME. But I haven't found any other tight constructions.


texts: Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem

texts:
The Graph Isomorphism problem (GI) is arguably
the best known candidate for an NP-intermediate problem.
The best known algorithm is sub-exponential algorithm
with run-time $2^{O(\sqrt{n \log n})}$.
It is known that GI is not $\mathsf{NP}$-complete unless
the polynomial hierarchy collapses.

  What would be the complexity theoretic consequences of a quasi-polynomial time algorithm for the Graph Isomorphism problem?
  Would a quasi-polynomial time algorithm for GI refute any famous conjectures in complexity theory?

Other similar problems like
Minimum Dominating Set in Tournaments problem,
Group Isomorphism problem, and
Tournament Isomorphism problem
have quasi-polynomial time (QP) algorithms.
The later two problems are polynomial-time reducible to GI.

  Can we efficiently reduce Minimum Dominating Set in Tournaments problem to GI?
  Is there any conjecture ruling out GI being hard for QP?

Update (2015-12-14): Babai has posted a preliminary draft paper on arXiv for his quasipolynomial-time algorithm for GI.

Update (2017-01-04): Babai retracted the claim that the algorithm is in quasipolynomial time, according to the new analysis the algorithm is in subexponential time $\exp \exp(\tilde{O}(\sqrt{\lg n}))$ which is inside $2^{n^{o(1)}}$.

Update (2017-01-09): Babai reinstated the quasipolynomial time claim, replacing the offending procedure with a more efficient one.


texts: Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?

texts:
Since $e$ is transcendental, the function $f:\mathbb Z_{\geq 0}^{n+1}\to \mathbb R$ is injective,
$$ f(\underset{\text{Integers}\ \geq\ 0}{\underbrace{a_0,a_1,\ldots, a_n}}) = a_0 + a_1e+a_2e^2+\cdots a_ne^n$$
Since $f$ is injective, in principle, the numbers $a_i$ can be deduced given the output of $f$.
And since the numbers $a_i$ are non-negative, any interval of the real numbers intersects the codomain of $f$ on only finitely many points.$^*$
I'm wondering whether, in practice, the integer coefficients $a_i$ can be recovered from the value of $f$. Does it suffice to have only polynomially many (in $n$) bits of $f$? (i.e., polynomial in $n$). And can this be done in polynomial time?
There is an exponential-time algorithm, namely: Simply enumerate all $a$ for which $f(a)\leq t$ for a given target value $t$. In fact, in my application I know that $a_0+a_1+\cdots +a_n = 2^n$, so the enumeration is quite simple.

I have the same question for
$$g(a_0,a_1,\ldots, a_n) = \sum_{k=0}^ne^{\frac{i\pi}{p}k}a_k$$
In my application, I can choose $p$, e.g., a prime with $2n<p$, so that the contributions all lie in the north-east region of the complex plane.
$^*$ (Thanks to Emil Jerabek for pointing out that, without that constraint, $f$ cannot be computed from finitely many bits).


texts:
Complexity theory seems to be built around decision problems rather than functions.

Who introduced this first and what is the reason for this choice?

For example, Edmonds' "Paths, trees and flowers" paper is generally credited as the source of the notion of $\mathsf{PTime}$ representing the set of "tractable" problems and this is the path that we have taken.


texts: An integer programming on maximum number of triangles

texts:
Consider three distinct sets $A, B, C$ of $N$ elements respectively. For each pair of sets, say $A,B$, we introduce an variable for each combination of values $a,b$ as $x_{ab}$. Similarly, we introduce a variable $y_{bc}$ for each $b \in B, c \in C$, and $z_{ac}$ for each $a \in A$, $c \in C$.

Consider the following integer programming with the optimal solution as $OPT$.

$$\ \ \ \ \ \ \max \sum _{a \in A, b \in B, c \in C} x_{ab} \cdot y_{bc} \cdot z_{ac}$$
$$s.t. \sum_{a \in A, b \in B} x_{ab} \le N$$
$$\ \ \ \ \sum_{b \in B, c \in C} y_{bc} \le N$$
$$\ \ \ \ \sum_{a \in A, c \in C} z_{ac} \le N$$
$$x_{ab}, y_{bc}, z_{ac} \in \{0,1\}, \forall a \in A, b \in B, c \in C$$

Is the following decision problem polynomial-time solvable or NP-hard:
Given an input integer $k$, whether $OPT > k$ or not?


texts:
I would like the know the complexity of a specific satisfiability problem. I have a feeling it could be solved in polynomial time, but I am not sure about it. The problem is described below.
Given $n$ boolean variables $v_1, v_2, \dots, v_n$ and two types of clauses.

At most $n$ clauses of the form $v_a \to \neg v_i \land \neg v_j \land \dots$ where $v_a$ cannot be on both sides of the implication.
At most $n$ clauses of the form $v_a \lor v_b \lor \dots$ where any combination of variables is possible (but no negations!).

The goal is to satisfy all the clauses. I have a feeling this can be done using limited backtracking just like with 2SAT as described on Wikipedia https://en.wikipedia.org/wiki/2-satisfiability#Limited_backtracking.


texts: Upperbound the order of P3-free partition of P4-free graphs

texts:
A graph $G$ is $P_k$-free if and only if $G$ does not have an induced subgraph isomorphic to a path of $k$ vertices. Thus, $P_2$-free graphs are exactly independent sets (or stable sets). $P_4$-free graphs are exactly cographs.

Question. In the worst case, how many $P_3$-free graphs are necessarily needed to partition a $P_4$-free graph of $n$ vertices?

A trivial upperbound is $\frac{n}{2}$. Because graphs of 2 vertices are trivially $P_3$-free, so we can simply partition any graph of $n$ vertices into $\frac{n}{2}$ components with each component having 2 vertices.

A clique-cover number is also an upperbound because clique is also $P_3$-free.


texts: Conditional results implying difficulty of improving upper/lower bounds for permanent

texts:
Let $A$ be a given square matrix.
Is there any evidence that beating quadratic lower bounds for $B$
such that $\text{det}(B) = \text{per}(A)$ could be hard?

Is there any plausible conjecture which implies that
proving lower bounds is difficult?
Is there any evidence that
proving an $\Omega(n^{2+\epsilon})$ rows (or columns) lower bound
for some $\epsilon > 0$ is hard
(e.g. equivalent to $\mathsf{VP} \ne \mathsf{VNP}$)?

Is there any plausible conjecture which implies that
proving upper bounds is difficult?
Is there any evidence that
proving an $O(2^{n^\epsilon})$ upper bound
for some $\epsilon \in (0,1)$ is hard?


texts:
Recall $\pi(n)$ the number of primes $\le n$ is the prime-counting function.  By "PRIMES in P", computing $\pi(n)$ is in #P.  Is the problem #P-complete?  Or, perhaps, there is a complexity reason to believe that this problem is not #P-complete?

P.S.  I realize this is a bit naive since somebody must have studied the problem and proved/disproved/conjectured this, but I can't seem to find the answer in the literature.  See here if you are curious why I care.


texts: Is there a formulation of Rice's Theorem that does not involve admissible (or Gödel) numberings?

texts:
It is an easy task to devise an encoding for a computing formalism (such as  Turing Machines) that has a function with fixed encoding. That is, the encoding is a numbering $\psi : \mathbb{N} \rightarrow \textbf{P}^{(1)}$ where $\textbf{P}^{(1)}$ is the set of partial unary computable $\mathbb{N} \rightarrow \mathbb{N}$ functions. By a function with fixed encoding we mean a function $f$ that has exactly one $c$ such that $\psi (c) = f$. It is also simple to have such a numbering be realizable, that is, its codes can be decoded and executed by a universal computer, and furthermore it is possible to directly provide a code $u$ for a universal computer.

It seems we have all the ingredients to falsify Rice's Theorem; since there is only one code for $f$, deciding if a function belongs to $\{f\}$ is a simple matter of checking if the function's code is $c$. At this point we must stop and check the theorem's formal statement, in somewhere such as Wikipedia, where we find out that our numbering has to admissible. The proposed numbering is obviously not so; there is no computable function that could map exactly all standard codes for $f$ into exactly $c$.

But that does not mean $\psi$ is an undesirable numbering. On the contrary, i'd argue that having a numbering where a function is restricted to a special code could be a more pleasant evironment to program in, and while i've only spoken of fixing an encoding for a single function, it should be generalizable to finite amounts of functions, and there might even be infinite classes as well (but that's a question for another TCS.se post). It's also clear that most properties over $\textbf{P}^{(1)}$ are still undecidable even under $\psi$, which suggests a more general restatement of Rice's Theorem.

My question is: Are there generalizations of Rice's Theorem that account for realizable numberings, not just admissible ones?


texts: What degree of hash function independence is needed for Bloom filters?

texts:
In the traditional analysis of Bloom filters, it's assumed that the hash functions are truly random functions, meaning that each hash function distributes each key uniformly and independently of each other key. This contrasts with the sorts of analyses that I've seen done elsewhere. For example, both the count sketch and count-min sketch only require 2-independent hash functions, as does a hash table that resolves collisions via chaining. (However, linear probing hash tables require 5-independence).

Has there been any work done into analyzing Bloom filters under the assumption that the hash functions used are, say, only $k$-independent? Or are any lower bounds known on the degree of independence required for Bloom filters to provide reasonable guarantees about false positives?


texts: What's the simplest noncontroversial 2-state universal Turing machine?

texts:
I'm wanting to encode a simple Turing machine in the rules of a card game. I'd like to make it a universal Turing machine in order to prove Turing completeness.

So far I've created a game state which encodes Alex Smith's 2-state, 3-symbol Turing machine. However, it seems (admittedly based on Wikipedia) that there's some controversy as to whether the (2, 3) machine is actually universal.

For rigour's sake, I'd like my proof to feature a "noncontroversial" UTM. So my questions are:

Is the (2,3) machine generally regarded as universal, non-universal, or controversial? I don't know where would be reputable places to look to find the answer to this.
If the (2,3) machine isn't widely accepted as universal, what's the smallest N such that a (2,N) machine is noncontroversially accepted as universal?

Edited to add: It'd also be useful to know any requirements for the infinite tape for mentioned machines, if you happen to know them. It seems the (2,3) machine requires an initial state of tape that's nonperiodic, which will be a bit difficult to simulate within the rules of a card game.


texts: State of the art on approximating quadratic assignment problem

texts:
I was wondering what is the state of the art on approximating the quadratic assignment problem (QAP). In particular, I am interested in the following instance. Suppose the $A = (a_{ij}) \in \{0,1\}^{n \times n}$ is the adjacency matrix of an undirected graph. Let $B = (b_{\ell k}) \in \mathbb{R}^{K \times K}$ and $\pi : [n] \to [K]$ be a map. (We might put some restriction on $\pi$ too, for example, equal number of nodes being mapped to each element of $[K]$.) We would like to solve
$$
\arg \max_{\pi} \sum_{ij} a_{ij} b_{\pi(i),\pi(j)}
$$
A more specific questions is this: what is known about semi-definite programming relaxations (SDP) of this problem? Are there ones which do not significantly increase the dimension of the problem? Any review papers on recent advancements?


texts:
In the Arora-Barak book, in the Cook-Levin reduction, the resulting SAT formula is of size $T(n)\log(T(n))$, where $T(n)$  is the running time of the given Turing machine.

Is there a method to get a $O(T(n))$ length SAT formula?

The original TM is made oblivious (a TM is oblivious if the position of the head at the $i$th step depends only on the length of the input string). This step brings the $O(\log(n))$ factor. Once we have an oblivious TM that takes time $T'(n)$, the SAT formula is of length $O(T'(n))$.

Can we somehow bypass the step of making the TM oblivious?


texts: Given a B-Tree, determine the order keys were inserted

texts:
Given a B-tree, determine what order the keys were inserted in.  There may be multiple answers: I'd like to generate them all.

Is there any known method for this?  Or similar problems?

Clarification: As the comments mentioned, enumerating them all may be intractable.  I'd like to do two things:

Create a partial ordering. Node 7 was inserted before Node 4, but cannot be compared to Node 20.  (I've done this successfully for a binary search tree, and am wondering if this can be applied to B-tree as well. For BSTs, it seems to be simple: Node A < Node B iff Node A is an ancestor of Node B, assuming no deletions.)
Create what I call a probabilistic partial ordering.  For example: Out of x possible orderings, y have Node 4 inserted before Node 20, and 1 - y have Node 4 after Node 20.  I still am working on this even for binary search trees, so perhaps it's better to ask this question there first.

I'm also working on expanding the model to include deletions (probablisticly), but that will come later.


texts: Optimizing $\epsilon$ in $\epsilon$-kernel

texts:
The notion of $\epsilon$-kernel, as defined by Agarwal et al. ("Approximating extent measures of points"), is the following.

Let $S^{d−1}$ denote the unit sphere centered at the origin in $R^d$. For any set $P$ of points in $R^d$ and any direction $u \in S^{d−1}$, we deﬁne the directional width of $P$ in direction $u$, denoted by $\omega(u, P)$, to be

$\omega(u, P)=\max_{p\in P} \langle u, p \rangle  - \min_{p\in P} \langle u, p \rangle$

where $\langle \cdot, \cdot\rangle $ is the standard inner product. Let $\epsilon > 0$ be a parameter. A subset $Q \subseteq P$ is called an $\epsilon$-kernel of $P$ if for each $u \in S^{d−1}$, $(1 − \epsilon)\omega(u, P) \leq \omega(u, Q)$.

It was shown that one can compute an $\epsilon$-kernel of $P$ of size $O(1/\epsilon^{(d−1)/2})$ in time $O(n + 1/\epsilon^{d−(3/2)})$. (Chan, "Faster coreset constructions and data stream algorithms in ﬁxed dimensions".)

I am looking at the problem that is the reverse of this: Let $k$ be a parameter. I want to find an $\epsilon$-kernel of size at most $k$ such that $\epsilon$ is minimized. The running time could be exponential in $d$ but should be polynomial in $k$.

My general question is whether there is anything known for this problem. Some specific questions:
1. Is the problem NP-hard when d=2? (Any clue what problem we can reduce from?)
2. Is there any approximation algorithm for d=2?

Any general comments are also welcomed.


texts: First order expression for functional dependency

texts:
I'm puzzled with functional dependency formula in first order logic. It is triggered by

http://rjlipton.wordpress.com/2010/01/17/a-limit-of-first-order-logic/

where there seems to be a confusion between dependency and functional dependency. The expression

$\displaystyle \forall x \exists y : S(x, y) .$

is anything but functional dependency. The formula for functional dependency is

$\displaystyle \forall y_{1} \forall y_{2} \forall x : S(x, y_{1}) \wedge S(x, y_{2}) \implies y_{1} = y_{2} .$

Now, suppose we have ternary predicate Q(x,y,z). How does one express functional dependency y=f(x)?


texts: what are known bounds on complexity of nontrivial graph automorphism

texts: Given any simple undirected graph G, it is nontrivial to determine if G has nontrivial (non-identity) automorphisms. But what are results on upper/lower bounds of this decision problem?


texts: What is consequence of $PH\subseteq NSPACE((\log n)^2)$?

texts:
What is consequences of $PH\subseteq NSPACE((\log n)^2)$?

We don't even know PH is equals to L or not. I am wondering what will be happened when $PH\subseteq NSPACE((\log n)^2)$?


texts: $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$?

texts:
Can this statement be confirmed or disproved:

  $\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$

[Question changed to use Kaveh's brilliant formulation.]

Here the NDTM must "outrun" the DTM.

This seems similar to the PvNP question, but I'm not sure...

Thanks!

EDIT: This question seeks an inequality between the run time of polytime DTM deciders and their corresponding NP verifiers. If k=1, the proposition fails (e.g.: determining parity requires n steps on a TM and therefore a verifier cannot take any shortcuts). But if k>=2 ...?

I wonder if the statement can be disproved without leading to any major or unexpected complexity class separations... Is there a diagonalization argument that could work here.


texts: Measurability of an $\omega$-regular language

texts: It the previous question of mine I put a reference which shows that any $\omega$-regular language over the alphabet $\Sigma$ is a Borel subset of $\Sigma^\omega$. I am not sure whether the reference I am aware of is the first the showed this result, so I wonder whether there are other papers the contain it. Alternatively, I am also interested in textbooks that contain the proof of this fact.


texts: Complete problems or alternative definitions of the complexity class NP^GI?

texts:
Definition: Let $GraphIso$ be the decision problem whose input is a pair of undirected graphs $(G_1, G_2)$ and the output is true if and only if $G_1$ and $G_2$ are isomorphic.

Definition: Define $\textbf{GI}$ to be the class of all decision problems $L$ for which there is a polynomial-time Turing reduction from $L$ to $GraphIso$.

Definition: Let $\textbf{NP}^{\textbf{GI}}$ be the class all decision problems which can be decided by a polynomial-time non-deterministic Turing machine with access to an oracle for a problem which is in $\textbf{GI}$.

My question is then: is this class known? Is it equivalent to a more standard complexity class? Is there any know complete problem for this class?


texts: Complexity of smooth non-linear functions

texts:
EDIT: A more straightforward way of asking this question is: does evaluating a non-linear function require performing at least one multiplication?

ORIGINAL QUESTION:

I have an infinitely differentiable function f(x) which takes as input an $n$-bit integer $x$ and outputs a $kn$-bit integer, where $k$ is a contant. I know that $f(x)$ is not a linear function of $x$, and I want to argue that the complexity of evaluating $f$ on $x$ is at least $n \log n$.

I think this should be true, since I can write $f(x) = f(x_0) + f'(x_0)(x-x_0) +  f''(x_0)(x-x_0)^2 + ...$ and computing $(x-x_0)^2$ requires at least $n \log n$ operations.

However, I don't think this ``proof by Taylor series" would yield a proof, and this would rule out smooth non-linear functions that have complexity $n \log \log n$, for instance.

Any suggestions on how to prove this / give a counterexample?

Thanks!


texts: Why do computer scientists on the whole work under the assumption that P ≠ NP?

texts: Coming from a math background, it seems interesting to me that on the whole computer scientists tend to work under the assumption that $P \neq NP$. While there is no proof either way, generally, unless something can be specifically unproven in both math and science it is taken with a fair amount of strength. I feel that in the years and years people have spent trying to disprove $P = NP$, the fact that no proof has been discovered yet would at least lead some computer scientists to work within the parameters of viewing $P = NP$ as possibly true. However, I often see people working within the framework of it not being true and I was wondering why? It seems more conservative to assume that $P = NP$ in many fields. I've read countless articles about how many computer science and CS-adjacent fields would have to change a lot of their current methodology if $P = NP$ was proven to be true, so why is this not assumed? While it is unlikely to be proven either way any time soon, it just seems somewhat odd to rely so heavily on the a conjecture like that. It almost seems paramount to assuming that Goldbach's conjecture is invalid as there is no proof for it either.


texts: How many different Huffman encoding for a given number of symbols

texts: In Huffman coding, if we have two symbols to be encoded, we will get the result either 01 or 10. If we have three symbols, we will get 12 different encoding. I am wondering if I give a arbitrary number of symbol, is there a formula to calculate how many different encoding we will have by Huffman coding?


texts:
Do any of you know a reference for the following (surprisingly tedious to prove) result?

Given a connected planar graph $G$ with $n$ vertices and $n+t$ edges, it has a vertex separator of size $O( \sqrt{t}+1)$.


texts: Is this graph transformation unique up to isomorphism? [Answer:NO]

texts:
Suppose, transformation T is defined as given in the diagrams below.
Every vertex (v) is replaced by deg(v)-gon. And then graph is reconnected as shown.

Those on the left are Gs and on the right are T(G)s.

It is easy to see that every vertex in  T(G) has degree 3.
This paper claims that graph isomorphism of such graphs can be tested in polynomial time. Also, G can be converted to T(G) in polynomial time.

Statement I: G1 and G2 are isomorphic iff T(G1) and T(G2) are isomorphic.
EDIT:
Specifications for G1,G2:

G1 = (V1,E1) and G2=(V2,E2)
|E1| = |E2| and |V1| = |V2|
Sort[{deg(v)|v in V1}] = Sort[{deg(u)| u in V2}]

If Statement I is True then do we have solution for GI problem?

Note: I am n00b in this field. I invent funny techniques daily.


texts: Exact algorithms for non-convex quadratic programming

texts:
This question is about quadratic programming problems with box constraints (box-QP), i.e., optimisation problems of the form

minimise $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}$ subject to $\mathbf{x} \in [0,1]^n$.

If $A$ was positive semi-definite, then everything would be nice and convex and easy, and we could solve the problem in polynomial time.

On the other hand, if we had the integrality constraint $\mathbf{x} \in \{0,1\}^n$, we could easily solve the problem in time $O(2^n \cdot \mathrm{poly}(n))$ by brute force. For the purposes of this question, this is reasonably fast.

But what about the non-convex continuous case? What is the fastest known algorithm for general box-QPs?

For example, can we solve these in moderately exponential time, e.g., $O(3^n \cdot \mathrm{poly}(n))$, or is the worst-case complexity of the best known algorithms something much worse?

Background: I have some fairly small box-QPs that I would actually like to solve, and I was a bit surprised to see how poorly some commercial software packages perform, even for very small values of $n$. I started to wonder if there is a TCS explanation for this observation.


texts: 2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

texts:
How can I convert a 2DFA to a normal DFA. Is there an algorithm/elegant way to do that ?
I've been researching this for a few days but I coundn't find anything. Actually I want to implement that in Java.


texts:
I have 400 balls, in which 100 are red, 40 are yellow, 50 are green, 60 are blue, 70 are purple, 80 are black. (balls of the same colour are identical)

i need an efficient shuffling algorithm, so that after shuffling, balls are in a list, and

Any consecutive 3 balls are not of the same colour. e.g, i can not have "red, red, red, yellow...."

And, all permutation are "equally" likely to occur. (well, if the trade-off of efficiency vs. unbiasedness is good enough, i don't mind more efficiency than unbiasedness).

i tried to adapt Fisher-Yates-Knuth, but the outcome is not ideal.

Why Fisher-Yates not good enough? As FY adopts Monte Carlo inverse transformation. And the output distribution treats the same colour balls differently, i.e. it would generate biased result for my needs.

And, the Naive thinking would be to filter out / backtracking all bad permutations from the whole space. When the restriction is very strong, say, if we have only 300 balls and 100 of which are red, then there will be too many back tracking/failures before getting an appropriate permutation.

So, ultimately, I would wish to be able to iterate through all good permutations. However, because the number of valid permutations is too large, i can only randomly sample some of them. I wanna the statistical feature of the "some" of them resemble the population as much as possible.