texts: Efficient Online Algorithms for Matrix rank

texts: Suppose, we have a matrix with known rank. Then, in each step one element of this matrix will be changed. Is there any efficient online algorithm to find rank of each matrix after each element update?


texts: Are there non-closed complexity classes for which there are complete problems?

texts: Is saying that a class is non closed analogous to stating there are complete problems that have not been identified for that class under a certain type of reduction?


texts:
The N-queen problem is this:

Input : N

Output : A placement of N "queens" on an NXN chessboard such that no two queens lie on the same row, column or diagonal.

Doing a google search on this, I found that many slides by many professors claim this is an NP-Hard problem.(eg. web.mst.edu/~ercal/387/slides/NP-Hard.ppt)

However I havent been able to find a proof (or derive one).
The reason I ask this question is because I think I have an algorithm that solves certain instances of the problem i.e. with N not a multiple of 2 or 3 (N is the number of queens)
Related Issue - Can we consider the input size to be N (where N is the number of queens)? Or do we take the input size to be log(N), since the number 'N' can be represented in log(N) bits?


texts: Complexity of solving a polynomial equation

texts: Given a polynomial equation of degree n with m variables, that is guaranteed to have at least one solution, what is would be the Big O notation of the least complex algorithm to find a solution?


texts: How to constrain a finite automaton (NFA and DFA) to a tree?

texts:
I have a finite automaton by the standard model Hopcroft & Ullman define:
$$
M = (Q, \Sigma, \delta, q_0, F)
$$

Where $\delta$ is the transition function mapping $Q \times \Sigma \mapsto Q$, such that $\delta(q, a)$ is a state for each state $q \in Q$, the set of all states, and input symbol $a \in \Sigma$, the alphabet. That allows for $\delta$ to map to any element of $Q$. So that's a graph, although it's not described using the usual $G = (V, E)$ notation.

Without specifying any particular definition for $\delta$, I'd like to be able to write the constraint that $\delta$ may only define transitions which form a tree. How can that be expressed?

My thought is that I might say that $\delta$ must be recursive somehow (to give a tree shape), but I'm not sure how to go about that.

Thank you,


texts: Creating HMAC keys using a fixed prefix and a random string

texts:
In a system that uses HMAC for a number of different applications, it is important to use different keys for different applications.  Suppose:

there is just a single random string available (50 bytes long, in this case)
we are using HMAC-SHA1
we will shorten keys longer than the blocksize using SHA1 (as per RFC 2104)

Is it safe to generate unique keys by prefixing the application name to the secret, so that the key for application 1 ends up as SHA1("application1" + secret) and the key for application 2 ends up as SHA1("application2" + secret)? The strings "application1" and "application2" are not kept secret. Or does this open up significant weaknesses compared to using completely different secret keys for each application?

Thanks.


texts: Best polynomial-time approximation factor for NP-optimization problems

texts:
Let us say that a function $f(n)$ is the best approximation factor for an NP-optimization problem, if both of the following hold:

There exist a polynomial-time algorithm $A,$ and an integer $n_0$, such that $A$ provides an $f(n)$-approximation for the NP-optimization problem for every instance with size $n\geq n_0$. (Note: the role of $n_0$ is merely to treat potentially deviant small instances, which might make the function "ugly.")
There is no polynomial-time $(1-o(1))f(n)$ approximation, unless $P=NP$.

A classic example where such a best approximation is known is the SET COVER problem (for a summary and references see its Wikipedia page): the Greedy Algorithm provides an $\ln n$ approximation, but there is no  $(1-o(1))\ln n$ approximation, unless $P=NP$.

Questions:

Which are some other interesting NP-optimization problems for which a best approximation factor, along with its realizing algorithm, are known?
Are there any counterexamples, i.e., NP-optimization problems, for which such a best approximation cannot exist, unless $P=NP$?


texts: How to compute K and n? [Item-based Collaborative Filtering]

texts:
I'm currently studying this item-based collaborative filtering algorithm on this thesis that I've researched and I've formulated the algorithm below based on it. I have no problem on steps 1 to 3 but in step 4 it says there: Set the threshold value n.
How can I determine the value of n? Is there a formula for getting the value of it? I already checked it out but there's nothing there.
And also in Step 5: Select the K most similar products in M. The same question, how can I compute the value of K?

  Retrieve all the item rated by an active user and put it to Q.
  Isolate the users who have rated both the target item (i) and the items rated by the active user in Q, get the item and put it in R.
  (co-rated items)
  Calculate the item similarities using the Pearson Correlation Coefficient with all the  items (j) in R.
  Set the threshold value n, If the similarity of i and j is greater or equal to n, (sim(i,j) >= n),  Then include it in M.
  Select the K most similar products in M.
  Take the weighted average of the users rating on these similar items K.


texts: Reduction from a geometric decision problem to its maximization problem

texts:
I am interested in the following NP-complete decision problem:

Given n collections of M axis-parallel squares in the plane,
is it possible to pick a single representative from each collection,
such that all n representatives are pairwise disjoint?

I found several useful approximation algorithms to the following maximization problem:

Given n axis-parallel squares in the plane,
find the largest set of pairwise disjoint squares.

(see Timothy M. Chan and Sariel Har-Peled, 2013, for a recent survey of approximation algorithms for this and similar problems).

I am trying to use them for solving my original problem, but in order to get a better understanding of the relation between these two problems, I ask the following theoretical question:

Given an oracle that solves the maximum-disjoint-squares problem, how can it be used for solving the square-representative-decision problem?

NOTE 1: The two problems can be seen as special cases of the following set packing problems:

Decision problem:

Given n collections of M sets,
is it possible to pick a single representative from each collection,
such that all n representatives are pairwise disjoint?

Maximization problem:

Given n sets,
find the largest set of pairwise disjoint sets.

In this case, there is a simple reduction from the decision problem to the maximization problem: add a unique element $A_i$ to all sets in collection $i$, find the largest set of pairwise disjoint sets, and return "true" if the largest set has $n$ sets. Unfortunately this reduction doesn't work in the geometric scenario.

NOTE 2: Both the decision problem and the maximization problem can be solved with an oracle to the following problem:

Given n collections of M axis-parallel squares in the plane,
find the maximum number of disjoint representatives, one per collection.

For the decision problem, just check if the maximum is $n$. For the maximization problem, take $M=1$.


texts: Deciding whether a graph contains a complete balanced bipartite graph

texts:
Is it known whether the following problem is in P or is NP-complete?

Problem: given an input graph $G$ on $n$ vertices, decide whether $G$ contains a complete $n/2 \times n/2$ bipartite graph.


texts: Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

texts:
I have a (hopefully simple, maybe dumb) question on Babai's landmark paper showing that $\mathsf{GI}$ is quasipolynomial.

Babai showed how to produce a certificate that two graphs $G_i=(V_i,E_i)$ for $i\in\{1,2\}$ are isomorphic, in time quasipolynomial in $v=|V_i|$.

  Did Babai actually show how to find an element $\pi\in S_v$ that permutes the vertices of $G_1$ to $G_2$, or is the certificate merely an existence-statement?

If an oracle tells me that $G_1$ and $G_2$ are isomorphic, do I still need to look through all $v!$ permutations of the vertices?

I ask because I also think about knot equivalence.  As far as I know, it's not known to be, but say detecting the unknot were in $\mathsf{P}$.  Actually finding a sequence of Reidemeister moves that untie the knot might still take exponential time...


texts: Identity testing of margins of boolean functions

texts:
Consider a boolean function $f(\vec{x},\vec{y})$, we define an (integer-valued) function $g(\vec{x})=\sum_{\vec{y}}f(\vec{x},\vec{y})$, i.e., $g$ can be considered as a (sort of) margin of $f$. The question is to decide whether there are $\vec{x}$ and $\vec{x}'$ such that

$g(\vec{x})\neq g(\vec{x}')$.

The computation of $g$ is $\sharp P$-hard, However, I am still seeking practically efficient (approximate, randomized) algorithms. Possibly one does not need to compute $g$ directly?

One might view the problem from a couple of different perspectives: it is a polynomial identity testing problem, but here, it is over $F_2$ which the  Schwartz-Zippel Algorithm might not work (I am not sure although); or it is a problem of analysis of boolean functions, but this  is a bit vague, and I am not clear whether powerful techniques (e.g., Fourier analysis) are applicable here. Any hints are highly appreciated.


texts: Does P = NP imply NP being a strict subset of PSPACE?

texts: Does $\textbf{P} = \textbf {NP}$ imply that $\textbf{NP} \subsetneq \textbf{PSPACE}$? Or, for a slightly stronger result, does it imply that $\textbf{NL} = \textbf P$?


texts: Complexity of Membership-Testing for finite abelian groups

texts:
Consider the following abelian-subgroup membership-testing problem.

  Inputs:

  A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with arbitrary-large $d_i$.
  A generating-set $\lbrace h_1,\ldots,h_n\rbrace$ of a subgroup $H\subset G$.
  An element $b\in G$.

  Output: 'yes' if $b\in H$ and 'no' elsewhere'.

Question: Can this problem be solved efficiently in a classical computer? I consider an algorithm efficient if it uses $O(\text{polylog}|G|)$ time and memory resources in the usual sense of classical Turing machines. Notice that we can assume $n= O(\log|G|)$ for any subgroup $H$. The input-size of this problem is $\lceil \log|G|\rceil$.

A bit of motivation. Intuitively it looks like the problem can be tackled with algorithms to solve linear systems of congruences or linear diophantine equations (read below). However, it seems that there are different notions of computational efficiency used in the context of computations with integers, such as: strongly versus weakly polynomial time, algebraic versus bit complexity. I am not an expert on these definitions and I can not find a reference that clearly settles down this question.

  Update: the answer to the problem is "yes".

  In a late answer, I proposed a method based on Smith normal forms which is efficient for any group with the prescribed form.
  An answer by Blondin shows that in the particular case where all $d_i$ are of the form $d_i= N_i^{e_i}$ and $N_i, e_i$ are "tiny integers" then the problem belongs to $\text{NC}^3\subset \text{P}$. Tiny integers are exponentially small with the input size: $O(\log\log|A|)$.

  In my answer I used "orthogonal subgroups" to solve this problem, but I believe this is not necessary. I will try to provide a more direct answer in the future based a row Echelon forms method I am reading.

Some possible approaches

The problem is closely related to solving linear system of congruences and/or linear diophantine equations. I briefly summarise these connection for the sake of completion.

Take $A$ to be the matrix whose columns are the elements of the generating set  $\lbrace h_1, \ldots, h_n \rbrace$. The following system of equations

$$
Ax^{T}=
\begin{pmatrix}
h_1(1) & h_2(1) & \ldots & h_n(1)\\
h_1(2) & h_2(2) & \ldots & h_n(2)\\
\vdots & \vdots & \cdots & \vdots\\
h_1(m) & h_2(m) & \ldots & h_n(m)
\end{pmatrix}

\begin{pmatrix}
x(1)\\
x(2)\\
\vdots\\
x(n)
\end{pmatrix}
=
\begin{pmatrix}
b(1) \\
b(2) \\
\vdots\\
b(m)
\end{pmatrix}
\begin{matrix}
\mod d_1\\
\mod d_2\\
\vdots\\
\mod d_m
\end{matrix}
$$

has a solution if and only if $b\in H$.

If all cyclic factors have the same dimension $d=d_i$ there is an algorithm based on Smith normal forms that solves the problem in polynomial time. In this case, an efficient algorithm from  [1]
finds the Smith normal form of  $A$: it returns a diagonal matrix $D$ and two invertible matrices $U$ and $V$ such that $D=UAV$. This reduced the problem to solving the equivalent system system $DY=Ub \mod d$ with $D$ diagonal. We can decide efficiently if the system has a solution using the Euclidean algorithm.

The above example suggest that the problem can be solved efficiently using similar techniques in the general case. We can try to solve the system doing modular operations, or by turning the system into a larger system of linear diophantine equations. Some possible techniques to approach the problem that I can think of are:

Computing the Smith normal forms of $A$.
Computing the row Echelon form of $A$.
Integer Gaussian elimination.


texts: Are innermost reductions perpetual in untyped λ-calculus?

texts:
(I have already asked this at MathOverflow, but got no answers there.)

Background

In the untyped lambda calculus, a term may contain many redexes, and different choices about which one to reduce may produce wildly different results (e.g. $(\lambda x.y)((\lambda x.xx)\lambda x.xx)$ which in one step ($\beta$-)reduces either to $y$ or to itself). Different (sequences of) choices of where to reduce are called reduction strategies. A term $t$ is said to be normalizing if there exists a reduction strategy which brings $t$ to normal form. A term $t$ is said to be strongly normalizing if every reduction strategy brings $t$ to normal form. (I'm not worried about which, but confluence guarantees there can't be more than one possibility.)

A reduction strategy is said to be normalizing (and is in some sense best possible) if whenever $t$ has a normal form, then that's where we'll end up. The leftmost-outermost strategy is normalizing.

At the other end of the spectrum, a reduction strategy is said to be perpetual (and is in some sense worst possible) if whenever there is an infinite reduction sequence from a term $t$, then the strategy finds such a sequence - in other words, we could possibly fail to normalize, then we will.

I know of the perpetual reduction strategies $F_\infty$ and $F_{bk}$ given respectively by:
\begin{array}{ll}
F_{bk}(C[(\lambda x.s)t])=C[s[t/x]]       & \text{if $t$ is strongly normalizing} \\
F_{bk}(C[(\lambda x.s)t])=C[(\lambda x.s)F_{bk}(t)] & \text{otherwise}
\end{array}
and
\begin{array}{ll}
F_\infty(C[(\lambda x.s)t])=C[s[t/x]] & \text{if $x$ occurs in $s$, or if $t$ is on normal form} \\
F_\infty(C[(\lambda x.s)t])=C[(\lambda x.s)F_\infty(t)] & \text{otherwise}
\end{array}
(In both cases, the indicated $\beta$-redex is the leftmost one in the term $C[(\lambda x.s)t]$ - and on normal forms, reduction strategies are necessarily identity.) The strategy $F_\infty$ is even maximal - if it normalities a term, then it has used a longest possible reduction sequence to do so. (See e.g. 13.4 in Barendregt's book.)

Consider now the leftmost-innermost reduction strategy. Informally, it will only reduce a $\beta$-redex which contains no other redexes. More formally, it is defined by
\begin{array}{ll}
  L(t) = t
   &\text{if $t$ on normal form}\\
  L(\lambda x.s) = \lambda x. L(s)
   &\text{for $s$ not on normal form}\\
  L(st) = L(s)t
   &\text{for $s$ not on normal form}\\
  L(st) = s L(t)
   &\text{if $s$, but not $t$ is on normal form}\\
  L((\lambda x. s)t) = s[t/x]
   &\text{if $s$, $t$ both on normal form}
\end{array}

The natural intuition for leftmost-innermost reduction is that it will do all the work - no redex can be lost, and so it ought to be perpetual. Since the corresponding strategy is perpetual for (untyped) combinatory logic (innermost reductions are perpetual for all orthogonal TRWs), this doesn't feel like completely unfettered blue-eyed optimism...

  Is leftmost-innermost reduction a perpetual strategy for the untyped $\lambda$-calculus?

If the answer turns out to be 'no', a pointer to a counterexample would be very interesting too.


texts: How does one sample uniformly at random from an uncountably infinite set?

texts:
I want to know if there are any examples of polynomial time algorithms which can sample uniformly at random from a given uncountably infinite set? (assuming it is possible)
Does it help if the sample space of events is actually a Lie group on which a Haar measure is known? Does knowing the Haar measure explicitly as a function help one get such an algorithm? (..because the Haar measure is "uniform" in the sense that it is invariant under the group actions..)


texts: Transferring results on coalgebras in one category to another

texts:
Let $F$ and $G$ be endofunctors over categories $C$ and $ D$, respectively.  Suppose that there is a forgetful functor $C \to D$ that has a left adjoint.  Can we infer properties of $F$-coalgebras from those of $G$-algebras, or vice versa, by exploiting the connection between the two categories?
Presumably the situation here is too vague.  Is there some special case of this scenario in which my question make sense and answerable?  What are the relevant literature here?

(The application I had in mind is this: suppose that I have a coalgebraic modal logic $L$ for coalgebras in $D$, and that $L$ as it is does not generalize to other categories than $D$ since it relies on some special properties of $D$.  Can I still use $L$ to describe coalgebras in $C$,  at least in some limited cases, by using the adjunction?)


texts: Worst case ratio between minimum clique cover and maximum independent set

texts:
The maximum independent set problem gives a lower bound for the minimum clique cover problem.  This is easy to see because given any clique cover together with an independent set, any two vertices which are part of the independent set must belong to separate cliques in the clique cover.

Is there any way to put a worst case (hopefully constant) upper bound on the ratio between these two values?  What about when the number of vertices grows large?  I know it must be at least $\frac{3}{2}$, since we can have a graph composed of an arbitrary number of pentagons (each pentagon has a maximum independent set of 2 vertices, but a minimum clique cover of 3 cliques).  Can anyone find a graph where the ratio is larger than $\frac{3}{2}$? larger than 2?


texts: Automatically creating weighted DFAs penalizing sequences of subsets of the alphabet

texts:
For a given finite alphabet $\Sigma$, my goal is to write an algorithm
that receives as input a sequence $V=V_{1}V_{2}\dots V_{n}$ of subsets
($V_{i}\subseteq\Sigma$), and returns a weighted deterministic finite-state
automaton with the following property: for every input string $s$,
the automaton penalizes each substring $s_{1}s_{2}\dots s_{n}$ of
$s$ if $s_{i}\in V_{i}$ for every $1\le i\le n$.

For example, if $\Sigma=\{a,b\}$, $V=V_{1}V_{2}=\{b\}\{b\}$, the
returned automaton would penalize the string $s=bbbb$ $3$ times,
i.e. when accepting the string and summing over the weighted arcs,
the result would be $3$.

The algorithm should return the weighted DFA as a 4-tuple $<Q,\delta ,q_0 , F>$:

$Q=\{q_{0},q_{1}\}$

$\delta=\{(q_{0},a,0,q_{0}),(q_{0},b,0,q_{1}),(q_{1},b,1,q_{1}),(q_{1},a,0,q_{0})\}\subseteq Q\times\Sigma\times\{0,1]\times Q$

$q_{0}=q_{0}$

$F=\{q_{0},q_{1}\}$

The algorithm must return the DFA as a 4-tuple as described. My main concern is the size of the resulting DFA. Therefore, the structure of $V$ should be taken advantage of. Capitalizing on subset relations, it is possible to eliminate states from the resulting automaton. For example, when all subsets are pairwise disjoint,
the automaton would have $n$ states.

The problem arises in the general case, where the inclusion relation
between subsets is unknown.

For example, if $\Sigma=\{a,b,c,d,e\}$ and $V=\{a,b\}\{b,c,d\}\{d,e\}$,
the string $abde$ should be penalized twice (both $abd$ and $bde$
are penalized), where $acde$ should be penalized only once ($acd$
is penalized, but not $cde$). This happens since there is a chain
of non-empty intersections between subsets $(V_{1}\cap V_{2},V_{2}\cap V_{3}\not=\emptyset)$,
so having accepted a penalized substring, some paths taken must be
remembered in order to know how to move on. Paths in the required automaton
would have to be splitted accordingly. In this case the resulting automaton could be minimally built with 5 states.

When the sequence is longer, there is a chance for more complex inclusion
relations between its subsets.

I'm interested in a general algorithmic solution for this problem, currently not in any implementation or performance considerations. As stated, my main concern is the size of the DFA.

Any insight, reference or suggestion on how to tackle this problem
would be appreciated.

More specifically, I'm now trying to figure out how to capitalize on inclusion relations between subsets in order to eliminate states (in advance) when building the DFA.

EDIT:
Added a paragraph and a final comment about using the structure of V to minimize the DFA, emphasis on my need of a smallest DFA as possible.


texts: Parameterized Algorithm to Speed up Exact Exponential-time Algorithm

texts:
The connection between $c^kn^{O(1)}$  for $c<4$ and exact exponential-time algorithms beating brute-force $O(2^n)$ algorithms has been known for a long time. However, when $c\geq 4,$ there are not many known results. Fomin et al. [1] showed a technique to handle this case, can improved a lot of exact exponential-time algorithms. For example, for the Interval Vertex Deletion Problem, the fastest previously known exponential-time algorithm is $O((2-\epsilon)^n)$ for $\epsilon <10^{-20}$ [2]. The fastest parameterized algorithm is $8^kn^{O(1)}$ [3]. Combined them together, Fomin et al. [1] got a $1.875^{n+o(n)}$ time algorithm.

Do you known any other techniques and known results to improve the exact exponential-time algorithms using parameterized algorithms when $c\geq 4$?

[1] Fomin, Fedor V., et al. "Exact algorithms via monotone local search." arXiv preprint arXiv:1512.01621 (2015).

[2] Bliznets, Ivan, et al. "Largest chordal and interval subgraphs faster than 2 n." European Symposium on Algorithms. Springer Berlin Heidelberg, 2013.

[3] Cao, Yixin. "Linear recognition of almost interval graphs." Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2016.


texts: For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$?

texts:
In a related question, Saeed and Super8 have mentioned the Robertson-Seymour theory which enables us to find $k$ disjoint paths between pairs of vertices $\{s_i,t_i\}_{i=1}^k$ in poly time for fixed $k\in \mathbb{N}$.

Suppose now that we are trying to find $k$-disjoint-paths, such that the sum of their lengths is minimal.

Related results:

Using a similar reduction to the one I proposed here, it is possible to show that if there's a single source (and $k$ targets), the problem is in $P$.
There's a known algorithm(with the unusual runtime of $O(|V|^8)$) for a related problem, where only shortest $s_i\to t_i$ paths are to be considered. In this variant, $k=2$ is in $P$ .
In the same paper, they state that (notice it's not the same problem):

  "the complexity for fixed $k \geq 3$ remains an open  problem. "

What can we say about the "short-$k$-disjoint-paths" problem?


texts: The problem of deciding whether a monotone CNF implies a monotone DNF

texts:
Consider the following decision problem

Input: A monotone CNF $\Phi$ and a monotone DNF $\Psi$.

Question: Is  $\Phi \to \Psi$ a tautology?

Definitely you can solve this problem in $O(2^n \cdot \mathrm{poly}(l))$-time, where $n$ is the number of variables in  $\Phi \to \Psi$ and $l$ is the length of input. On the other hand, this problem is coNP-complete. Moreover, a reduction which establishes coNP-completeness also shows that, unless SETH fails, there is no  $O(2^{(1/2 - \varepsilon)n} \mathrm{poly}(l))$-time algorithm for this problem (this holds for any positive $\varepsilon$). Here is this reduction. Let $A$ be a (non-monotone) CNF and let $x$ be its variable. Replace every positive occurence of $x$ by $y$ and every negative occurence of $x$ by $z$. Do the same for every variable. Let the resulting monotone CNF be $\Phi$. It is easy to see that $A$ is satisfiable iff $\Phi \to yz \lor \ldots $ is not a tautology. This reduction blows up the number of variables by a factor of 2, which implies $2^{n/2}$ (SETH-based) lower bound mentioned above.

So there is a gap between $2^{n/2}$ and $2^n$-time. My question is whether any better algorithm or better reduction from SETH is known?

Just two remarks seemingly related to the problem:

a reverse problem of whether a monotone DNF implies a monotone CNF is trivially solvable in polynomial time.
interestingly, the problem of deciding whether $\Phi$ and $\Psi$ compute the same function   can be solved in quasi-polynomial time due to Fredman and Khachiyan (On the Complexity of Dualization of Monotone Disjunctive Normal Forms, Journal of Algorithms 21 (1996), no. 3, pp. 618–628, doi: 10.1006/jagm.1996.0062)


texts:
A read-once decision tree is defined as follows:

$True$ and $False$ are read-once decision trees.
If $A$ and $B$ are read-once decision trees and
$x$ is a variable not occurring in $A$ and $B$,
then $(x \land A) \lor (\bar x \land B)$ is also a read-once decision tree.

What is the complexity of the equivalence problem for read-once decision trees?

Input: Two read-once decision trees $A$ and $B$.
Output: Is $A \equiv B$?

Motivation:
This problem came up while I was looking at
the proof equivalence problem (permutation of rules) of
a fragment of Linear Logic.


texts: How to prove $k^{n-1}, k^{n-2}, \ldots, k^0$ will result with minimum number of coins?

texts: I am not sure how to prove or disprove for $A_n = \{k^{n-1}, k^{n-2}, \ldots, k^0\}$ for some $k > 1$, the greedy method will yield solutions with minimum number of coins.  I know that each number is a subset of $k$ and that they are exponential but I dont know how I would prove or disprove this.


texts: What is the most important notion of sparsity for the design of efficient graph algorithms?

texts:
There are several competing notions of a "sparse graph".  For instance, a surface-embeddable graph could be considered sparse.  Or a graph with bounded edge density.  Or a graph with high girth.  A graph with large expansion.  A graph with bounded treewidth.  (Even within the subfield of random graphs, it is slightly ambiguous as to what could be called sparse.)  Et cetera.

What notion of "sparse graph" has had the most impact on the design of efficient graph algorithms, and why?  Similarly, what notion of "dense graph" ... ?  (NB: Karpinski has worked a great deal on approximation results for one standard model of dense graphs.)

I have just seen a talk by J. Nesetril on a program of his (together with P. Ossona de Mendez) to capture measures of sparsity in graphs within a unified (asymptotic) framework.  My question -- yes, maybe quite subjective and I expect different camps -- is motivated by the desire to catch a multi-faceted perspective on the use of sparsity in algorithms (and plug any gaps in my own understanding of the issue).


texts: Variable wire weights in DLOGTIME-uniform circuits

texts:
The definition of a $DLOGTIME$-uniform circuit family is based on a Turing machine that accepts the language $\langle t, a, b \rangle$, where gate $a$ is of type $t$ and has gate $b$ as a child, according to Barrington et. al's paper "On Uniformity Within $NC^1$" (1). However, this definition assumes that whether there is a wire or not between two gates is a binary choice. While this is true for $AND/OR$-based circuit classes like $AC^0$, other circuit classes like $CC^0$ and especially $TC^0$ assume that circuits can have an arbitrary constant or even $O(n)$ number of wires between two gates.
My questions are:

Is there a standard way in the literature to extend the definition of dlogtime-uniformity with wire weights greater than 1?
Is there a standard way to add this feature to logical characterizations of these families (e.g. $FO[bit]$)?


texts: Vertex disjoint simple paths of length k

texts:
A lot of effort has been invested in finding simple k-paths, as well as in finding vertex disjoint paths.

Is there any known parametrized algorithm that given a graph $G=(V,E)$, decides whether there exist $p$ vertex disjoint simple paths of length $k$ in the graph?

Finding a single simple k-path is known to be single exponent $FPT$ for a long time, what about this variant (with respect to both $p,k$ as parameters)?


texts: Algorithm to find $n$ player nash equilibrium

texts:
This is the question asked 10 years before.
Most of the algorithm and software mentioned are out of date. I am wondering is there new approchs for this problem in the last 10 years?
The game dealing with is $n$ player, finite actions, general sum.


texts: Historic Relationship between Typed Lambda Calculus and Lisp?

texts:
I was having a discussion with a friend recently (who is an advocate of strongly typed languages). He made the comment:

  The inventors of Lambda Calculus always intended it to be typed.

Now we can see that Church was associated with the Simply Typed Lambda Calculus. Indeed, it seems he explained the Simply Typed Lambda Calculus in order to reduce misunderstanding about the Lambda Calculus.

Now when John McCarthy created Lisp - he based it on the Lambda Calculus. This is by his own admission when he published "Recursive functions of symbolic expressions and their computation by machine, Part I". You can read it here.

McCarthy appears not to have addressed the Simply Typed Lambda Calculus. This seems to be dominated by Robyn Milner with ML.

There is some discussion of the relationship between Lisp and Lambda Calculus here, but they don't really get to the bottom of why McCarthy chose to leave it untyped.

My question is - If McCarthy admits he knew about Lambda Calculus - why did he ignore the Typed Lambda calculus? (ie - is it truly obvious that Lambda Calculus was intended to be typed? It doesn't seem that way)


texts: Existence of incremental algorithm for (canonical) prefix-free codes

texts:
Short version

Given

the $N$ code lengths of an optimal prefix-free code $L[1..N]$ for $N$ unknown weights $W[1..N]$ of known sum $S$, and
$N'$ new weights $W'[1..N']$ all larger than the weights of $W$,

is it possible to compute the code lengths of an optimal prefix-free code for the union of $W$ and $W'$ knowing only $S$, $W'$, and a finite amount of values from $W$ (such as the min and max)?

After a long time taking the existence of such an algorithm for granted, I now suspect it does not exist, but my mind is still foggy from assuming for so long the contrary, and I was hoping that someone with a fresher view could produce a small counter-example and clarify my mind. (This is NOT an assignment given to students, but I think it would make a nice one... if there is a clear answer to it.)

Motivation

Among other consequences, it would prove whether the convoluted algorithm used to compute canonical prefix-free codes (compute prefix-free code, extract code lengths, forget prefix-free code, rebuild canonical prefix-free code from code lengths) can or cannot be made incremental (which would have simplified various other results).

Background

In 1964, Schwartz et al. (1964-ACMCom-GeneratingACanonicalPrefixEncoding-SchwartzKallick), introduced the concept of canonical prefix-free code in which "the numerical values of the codes are monotone increasing and each code has the smallest possible numerical value consistent with the requirement that the code is not the prefix of any other code".  They described how to compute such codes by computing first the Huffman's code, then deducing from it an optimal vector of code lengths, and then computing from the latter an optimal prefix-free canonical code, "iteratively by assigning codes to the words in order of decreasing rank".


texts: What is known about log rank conjecture in special situations of $O(\log N)$ rank $0/1$ matrix of size $N\times N$? Is there at least a conditional result showing better than $O(\sqrt{\log N})$ bound?


texts: Determining the distribution of results of a simple algorithm

texts:
Setting
Consider repeating the following process on the numbers $N=\{1, 2, 3, \ldots, n\}$:

Pick an integer $k \in N$, uniformly at random.
Pick a subset of $k$ elements from $N$, uniformly at random.

After picking $s$ such sets, we repeatedly (until exhaustion) mark each number that is in a set whose other numbers are all marked.
Example
For example, if $N=\{1,2,3,4,5\}$ and $s=3$, we might pick the sets $s_0=\{1,3,5\}$, $s_1=\{1,4\}$ and $s_2=\{4\}$.  In the marking phase, we'd first mark $4$ (because in $s_2$ all 0 other elements are marked), then we'll mark $1$ (from set s_1), and we'll be done.
More generally, if $s=1$, then we know that $\frac{1}{N}$ fraction of times, we will have marked exactly one element with this process, and $\frac{N-1}{N}$ fraction of times we will mark no elements.
Question
Can anyone provide a closed-form expression for the distribution of the number of marked elements after this procedure for arbitrary $s$?
P.S.  I am purposefully leaving out the motivation or reference for this algorithm so as not to bias answers.  Those who recognize the motivation are kindly asked not to mention it, unless it specifically helps with the solution.


texts: Making a minimum-width tree decomposition lean in polynomial time

texts:
As is well known, a tree decomposition of a graph $G$ consists of a tree $T$ with an associated bag $T_v \subseteq V(G)$ for each vertex $v \in V(T)$, which satisfies the following conditions:

Every vertex of $G$ occurs in some bag of $T$.
For every edge of $G$ there is a bag containing both endpoints of the edge.
For every vertex $v \in V(G)$, the bags containing $v$ induce a connected subtree of $T$.

We may also demand the following condition, called leanness, from our decomposition:

For every pair of bags $T_a$, $T_b$ of $T$, if $A \subseteq T_a$ and $B \subseteq T_b$ with $|A| = |B| = k$, then either a) there are $k$ vertex-disjoint $A-B$ paths in $G$, or b) the tree $T$ contains an edge $pq$ on the path from node $a$ to node $b$ such that $|V(T_p) \cap V(T_q)| \leq k$ and the set $V(T_p) \cap V(T_q)$ intersects all $A-B$ paths in $G$.

Robin Thomas showed that there is always a minimum-width tree decomposition which is also lean, and simpler proofs of this fact have been provided by several authors, for example by Patrick Bellenbaum & Reinhard Diestel.

  What I am interested in is the following: given a graph $G$ and a
  minimum-width tree decomposition of $G$, can we find a minimum-width
  lean tree decomposition of $G$ in polynomial time?

The two mentioned proofs do not yield such efficient constructiveness. In the paper of Bellenbaum and Diestel it is mentioned that "Another (more constructive) short proof of Thomas’s theorem has been given in P. Bellenbaum, Schlanke Baumzerlegungen von Graphen, Diplomarbeit, Universitat Hamburg 2000." Alas, I have not been able to find the manuscript online and my German is not that great.


texts: Multi-round communication complexity of greater than

texts:
For the "greater-than" problem in Yao's 2-party communication complexity model, Alice receives $X$ and Bob receives $Y$, and they need to decide whether $X>Y$.
I recently listened to an (online) seminar talk where the speaker mentioned that it is known that any randomized $k$-round protocol that computes "greater-than" requires $\Omega\left(\frac{(\log n)^{1/k}}{k^2}\right)$ bits.
Unfortunately, I didn't get to ask the speaker about where this result appeared and I didn't have any luck searching for it online. Is there a reference where I could find the proof for this round-communication trade-off?


texts: Quantum complexity separation evading the algebrization barrier?

texts:
Question: Which results in complexity theory use quantum computing to evade the algebrization barrier?

I am aware of the separation $NEXP\not\subset ACC$, which evades all barriers, but it does not involve quantum classes.$^1$ I am also aware of the result $QIP(3)=PSPACE$, but the proof seems to be a natural extension of the original proof, defeating relativization and natural proofs but not algebrization. The same holds for a recent result of Aaronson, that $PP$ does not have quantum circuits of size $O(n^k)$ for any $k$, because the only non-relativizing part is the same as in the proof that $PP$ does not have classical circuits of size $O(n^k)$, namely it uses LKNF's algebrizing theorem that the matrix permanent has an interactive proof.

This question and this question asked about barriers, but no quantum answer was given.

$^1$In fact, quantum computing seems to occupy a special place in William's proof by being one of the only branches of computer science it does not draw from!


texts: Producing colouring of maximal planar graphs G from colouring of dual of G

texts:
A (simple) graph is said to be maximal planar if it is planar and adding one more edge loses planarity. In other words, the graph is planar and every face is a triangle. Tait gave a one-one correspondence between 4-colourings of maximal planar graphs and 3-edge colourings of their dual graphs. That is, given a 4-vertex colouring of a maximal planar graph $G$, one can produce a 3-edge colouring of the dual graph $G^*$ of $G$, and vice versa. The schemes to produce one from the other are elegant.

Similarly, there are schemes to produce (vertex) colouring of $G^*$ from colouring of $G$.

Is there a known scheme to produce a colouring of a maximal planar graph from a colouring of its dual graph?
(In other words, given a face colouring of a maximal planar graph, can we produce a vertex colouring?)

Clarification: I am not asking for a 4-colouring of the maximal planar graph. From a 4-colouring (or 5-coluoring) of its dual graph, is it possible to produce a colouring of the maximal planar graph (may be with 5 or even 6 colours; but it should be a colouring scheme that actually use the colouring of the dual graph).


texts:
In page 3 of PageRank paper is mentioned:

  let c be a factor used for normalization
  (so that the total rank of all web pages is constant).

What is the use of c and how can its value be computed?


texts:
Is there known any complexity class containing online counterparts of optimization problems? If not, then how such class can be defined?

We know that many problems have their online version: e.g. online version of bin packing problem. The online problems are harder as measured by their competitive ratios.

And I haven't found anything similar in complexity zoo.

Essentially, we could say that there are no online problems, but only online algorithms for offline problems. However, if there are online problems, why there can't be complexity class containing them?


texts: What are the ways in which one can add a decidable equivalence relation in a type system with undecidable type checking/extensional equality?


texts: The random densification technique-JL lemma

texts: In Ailon's paper (p.3): How $1/(20nd)$ is obtained?


texts: Example of $MSO_2$ definable NP-hard problem on bounded clique-width graphs

texts:
All $MSO_1$ and $MSO_2$ definable graph problems can be solved in linear time on bounded tree-width graphs by Courcelle's theorem. But it seems this theorem doesn't work for $MSO_2$ definable graph problems on bounded clique-width graphs.

Can some provide me an example of $MSO_2$ definable NP-hard problem on bounded clique-width graphs.


texts: SETH-like hypothesis for machine with oracle access to some level of PH

texts:
I am wondering if hypothesis such as Strong Exponential Time Hypothesis (SETH) have been studied for problems being in a higher level of the polynomial hierarchy when we give the machine access to an oracle.

More precisely, I am interested in hypothesis of the form:

$H_k$: For all $\varepsilon < 1$, QBF cannot be solved in time $2^{\varepsilon n}$ with a machine having oracle access to a problem of $\Sigma_k$, where the oracle can be called only on polynomial-size instances (calling an oracle on non-polynomial-size inputs looks way too powerful to be reasonable).

Is there any evidence to support $H_k$ (or $\neg H_k$)? More precisely, is it known if such hypothesis is comparable to SETH somehow?

I have not found any mention of this kind of hypothesis in the literature. The only hypothesis that I have found so-far are:

#ETH introduced in Exponential Time Complexity of the Permanent and the Tutte Polynomial by Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén but it is weaker than ETH.
NSETH introduced in Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility by Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider. But again, this hypothesis is stated for a problem "easier" than QBF.

I am also aware of Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity by Rahul Santhanam and Ryan Williams where it is proven that improvement on the complexity of QBF implies strong circuit lower bounds but their results cannot be applied directly to $H_k$.


texts:
So I have an issue I'm facing in regards to clustering with live, continuously streaming data.  Since I have an ever-growing data set I'm not sure what is the best way to run efficient and effective clustering.  I've come up with a few possible solutions including:

Setting a limit on how many data points to allow, thus whenever the limit is reached as another data point comes in the oldest point is removed.  Essentially, this would suggest that older data isn't relevant enough to us anymore to care what we're losing by throwing it out.
Once there is enough data to make a good clustering, consider this "the setup" and as new points come, rather than re-clustering all the data just figure out which cluster center the new point is closest to and add it to that.  The benefit here is you could avoid having to re-cluster on every new point and you wouldn't have to store all the other points, just the cluster centers, considering this clustering "good enough".  The downside is that re-running the algorithm with all data points from the beginning may be more accurate.

While those are some potential solutions I brain-stormed, I'd like to know if there are any better known techniques to face this problem.  I figure sites like Google had to deal with it somehow (and I'm hoping that "add more ram, servers and processors" or "continually expand your data centers" aren't the only answers available).


texts: Counterexample for Corneil's efficient algorithm for Graph Isomorphism

texts:
In the paper An Efficient Algorithm for Graph Isomorphism by Corneil and Gotlieb, 1970 a conjecture was stated upon which the stated algorithm relied for solving GI in polynomial time. Namely:

  that the representative graphs exhibit the automorphism partitioning of the
  given graph

Obviously, this conjecture isn't proven until now (otherwise we would know that GI is in P). My question is whether it was already shown to be false and possibly a counter example was given?


texts: Are there problems for which divide-and-conquer / recursion is provably useless?

texts:
When we try to construct an algorithm for a new problem, divide-and-conquer (using recursion) is one of the first approaches that we try. But in some cases, this approach seems fruitless as the problem becomes much more complicated as its input grows.

My question is: are there problems for which we can prove that a divide-and-conquer approach cannot help to solve? In the following lines I try to make this more formal.

Let $P(n)$ be a certain problem whose input has size $n$ (e.g. a problem that accepts an input an array of $n$ numbers). Suppose we have a recursive algorithm for solving $P(n)$.    The recursive runtime of that algorithm is calculated assuming an oracle which can solve $P(k)$ for every $k<n$ in constant time. For example:

The recursive runtime of binary search is $O(1)$, since it uses only a comparison and two recursive calls.
The maximum element in an array can be found in recursive time $O(1)$.
The recursive runtime of merge sort is $O(n)$, because of the merging step.

The recursive time is usually smaller than the actual runtime, which reflects the fact that the recursive algorithm is simpler than a straightforward non-recursive solution to the same problem.

Now my question is:

Is there a problem which can be solved in time $f(n)$, but provably has no recursive algorithm with recursive runtime asymptotically less than $f(n)$?

Some specific variants of this question are:

Is there a problem in $P$ which has no algorithm with recursive runtime $O(1)$? (Maybe sorting?)
Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?

EDIT: contrary to my guess, sorting has an algorithm with recursive runtime $O(1)$. So it is still open, whether there a problem in $P$ which has no algorithm with recursive runtime $O(1)$.


texts: VC dimension of Voronoi cells (Manhattan distance)

texts:
If the distance function originates from the Euclidean norm ($l_2$-norm), then the Voronoi diagram of $n$ points in a compact subset of $\mathbb{R}^d$ consists of cells that are convex polytopes. In this case, the maximum number of faces from a cell is $n(n-1)/2$.
How many faces does a cell have when the distance changes from the $l_2$ to the $l_1$-norm? I know already  that the Voronoi cells in this case are not convex sets. What can I do if I want a bound for the VC dimension of a Voronoi diagram under the $l_1$-norm ?


texts: Is there any link between TCS and Sustainable Energy research?

texts: Does anybody know of any work that links Theoretical Computer Science and Cheap/Sustainable Energy? i.e is there any work in TCS with the application being in Cheap/Sustainable Energy.


texts:
Say there's a public encryption scheme whose public key is $p_k$ and secret key is $s_k$. Prover $P$ wants to convince verifier $V$ that he knows $s_k$. The protocol is:

$V$ uniformly generates $m$ and sends $c = Enc_{p_k}(m)$ to $P$
$P$, receiving $c$, sends $m' = Dec_{s_k}(c)$ to $V$
$V$ checks whether $m = m'$. If so, accept. Else, reject.

Completeness and soundness are obvious. Intuitively decryption shouldn't leak information about the secret key $s_k$ if this scheme is CCA-secure. But I just haven't come up with a proper simulator to argue this. If $V$ cheats, it's hard to get the correct plaintext without knowledge of $s_k$. If the simulator just guess, the probability is so low that exponentially many rounds are required. So the question is:

Is this protocol really zero knowledge? If so, how to construct the simulator?


texts: algorithms to split data into roughly equal sized quantiles

texts:
What is the state-of-the art on algorithms that calculate/estimate approximate quantiles?

I don't even worry about errors in terms of the value of quantiles (here meaning the cutoff) but having roughly equal sized bins. E.g. if I need vingtiles, I want to have low risk of having any bin having less than 4% of the data or more than 6%.

If I need to implement this in an existing high-level statistical system, I think the question inevitable becomes restricted to downsampling from a population of $N$ to a subsample of $n$ and take quantiles using sorting at costs at the order $O(n \log n)$ instead of $O(N \log N)$, but at the right ratio as a function of the original sample size. I am looking for guidance on how to pick $n$ for any $N$.


texts:
In the paper "On Graph Contractions and Induced Minors" by Pim van't Hof et al. they showed that this problem is fixed parameter tractable in |VH| if G belongs to any non-trivial minor-closed graph class and H is a planar graph.

However, My failure to find a specific algorithm led me to ask the following question.

  If G is a bipartite graph , and H is a tree then is there any polynomial time algorithm to
  find if H is contained in G using only vertex deletion and edge contraction as the graph
  operations.


texts: Minimum Tree-width of circuit for MAJORITY

texts:
What is the minimum tree-width of a circuit over $\{\wedge,\vee,\neg\}$ for computing MAJ?

Here MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ outputs 1 iff at least half of its inputs are $1$.

I care only about the size of the circuit (ought to be polynomial) and that an input should be read only once though the fan-out of an input gate can be arbitrary (this crucially affects the tree-width of the circuit - the branching programs obtained from Barrington's theorem from the MAJ $\in$ $\mathsf{NC}^1$, interpreted as skew circuits, do not help). And of course the tree-width is the most crucial thing. I do not care about the depth or any other parameter.

Some of the common circuits for MAJ include:

Wallace tree circuits (e.g.Theorem 8.9 here) which use the 3-to-2 trick to place MAJ in $\mathsf{NC}^1$?
Valiant's monotone $\mathsf{NC}^1$ circuits for MAJ (e.g. Theorem 4 here)
$\log^{O(1)}{n}$ depth sorting network such as Batcher sort
AKS sorting network

  Do any of them have bounded or even polylogarithmic tree-width?

Or in fact,

  Are there reasons to believe that there are no bounded tree-width circuits for
  MAJ?

Notice that every function computed by a bounded tree-width circuit can be computed by an $\mathsf{NC}^1$ circuit even when there is no read-once stipulation via JansenSarma. Thus the implausibility of such a circuit family would indicate
that this bound can be tightened further in the case of read-once circuits.


texts: Switching between representations of boolean functions between circuits and Fourier expansions

texts:
I'm currently learning about the analysis of boolean functions (mainly based on their Fourier coefficients) by reading this excellent resource
There, boolean functions are represented as linear combinations of parity functions (which form an orthonormal basis).

From other areas I'm used to functions being represented as circuits.
My question therefore is: What is the most efficient/simple way to convert a function from its representation by Fourier coefficients to a small circuit and vice versa?


texts: How much programming is practiced in Theoretical Computer Science jobs?

texts:
I am an undergraduate student studying Information Technology. I like both math and CS, so I am considering to go into either "Computer Science and Math" or "Theoretical Computer Science" for my postgraduate study. Some of the fields I'm interested are: combinatorial and computational complexity.

I heard that the only career option in Theoretical CS is to become a researcher - and from where I come from, research are not strongly supported and encouraged (especially in CS), so researcher is not just a common career here.

But what I concern the most is people tell me that there are little programming practice in TCS, while I enjoy programming.

Is that true? Of all the research categories in TCS, which ones require more programming practices and what programming is used for there?
I have never worked theoretical math & rigorous math analysis e.g.: proving theory etc, though I'm quite sure I can master it if I learn it. How much will it affect me if I study TCS?

Your answer will be a great help for me. Thanks in advance!


texts: Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?

texts:
In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks.

Isn't it straight forward to reduce any classical physics problem into Spin-Glass which is NP-complete problem?

What I am saying is: since Spin-Glass is at least as powerful model (computationally) as any classical physics model it is always possible to restate a classical system using Spin-Glass.

I believe I am missing a huge point here, because these 2 papers are highly cited ones.

EDIT: If you downvote, please, kindly consider to add a constructive comment.


texts: Sample complexity of PAC learning all k-DNFs over the uniform distribution

texts:
Is sample complexity of PAC learning all $k$-DNFs over the uniform distribution known (that is all DNFs with all terms of size at most $k$ and without restriction on the number of terms)?
The only bounds I'm aware of are

the obvious upper bound of $O(n^k/\epsilon)$ (which is true even for distribution independent learning)
the obvious lower bound of $\Omega(2^k)$ (even for a constant $\epsilon$).
the upper bound of $\tilde{O}(k^{k \log{1/\epsilon}})$ which is implied by Mansour's (1992) paper on learning DNF (the algorithm there uses membership queries but the structural result can also be used to get a sample upper bound).

I'm primarily interested in lower bounds.
Also, anyone knows anything interesting about the same question for monotone $k$-DNF? For this case I don't know if even the trivial lower bound is true. Although slightly weaker bounds can be obtained by scaling lower bounds for learning monotone functions from Blum-Birch-Langford paper.


texts: What is the categorical semantics of subtyping?

texts:
Starting from Curry-Howard-Lambek, there has been a nice trinity of type theories, logics, and categories. I'm curious what categorical semantics you get when you add (coercive) subtyping to a type theory -- it seems like this has not been explored very much, if at all.

In general, adding coercive subtyping to a type theory does not ruin its meta-theoretic properties such as strong normalization, so its categorical semantics should be something of actual interest, I think!


texts: granularity of bidirectional breadth-first search

texts:
I tried posting this on stack overflow and it got no takers, decided to cross post here:
One thing that I've never seen discussed about bidirectional breadth-first-search (which I'll abbreviate as bidi-BFS) is how exactly to search from both ends at once.  Some options:

Literally use two separate threads.  This might actually slow things down terribly if it means you have to switch to some fancy concurrent data structures to coordinate them.  (Or maybe it actually comes out ok.  Never tried.)  We could avoid this by making sure the threads take turns, but then why bother with using two threads?
Use one thread, and the algorithms take turns on that thread.  But how big is a "turn"?  (Actually we could stick with two threads that take turns, and we still have to answer the exact same question.)  Some ideas:

A turn is a full "level".  That is, we search everything at distance k from src, then distance k from dst, then k+1 from src, then k+1 from dst, etc.
Or we could have more "fine-grained" turns.  For instance, we enqueue the neighborhood of the node that's currently at the front of the queue for the "forward search" (from src), then we switch to the "backward search" (from dst) and so on.  In other words, each turn, we dequeue exactly one node from the queue that BFS maintains, and do all the work associated with that node.  (This one is probably the simplest to code, because you can simply take the inner loop of an ordinary BFS and call it one "step".)
We can be even more fine-grained than that.  We can switch after the current search makes a certain amount of "progress", such as traversing exactly 100 edges (which will result in enqueueing less than 100 nodes, unless there are no duplicates encountered in the search).
Eventually we can get so fine grained that we start feeling silly: each turn is "X assembly instructions", or perhaps "Y clock cycles" or even "Z milliseconds".

Now, if the graph has a fairly regular shape, than all these variations will tend to produce similar results, and none of this matters much.  But suppose the graph is somehow "lumpy" in that we sometimes see nodes with many neighbors, and sometimes see nodes with very few.  Then it seems to me that the same intuition that says bidi-BFS is better than plain BFS should lead to the conclusion that finer-grained turned taking is better than larger-grained turn taking.  (For example, if by the time the two parallel searches meet, it turns out that the forward search had traversed ten times as many edges as the reverse search, then it seems very likely that if we had somehow "favored" the reverse search more, we would have done less TOTAL work.)
Now, it could be that other factors such as ease of coding or overhead of switching matter more than this stuff, but: all else being equal, am I right that finer-grained is always better, or at least never worse?  Or is there some other factor I'm neglecting?


texts: Convergence of HITS Algorithm in the absence of Normalization

texts:
Kleinberg's HITS Algorithm (Authoritative sources in a hyperlinked environment) requires the hub (/authority) vector to be normalized after each step of the iteration $x(k+1) = A.x(k)$, in order to guarantee convergence of the algorithm. However, as the matrix is reducible, uniqueness is not guaranteed.

I'm primarily interested in knowing what would happen to the vector if it is not normalized after each iteration. Is it possible to guarantee convergence (even if not uniqueness) under some special cases when the vector is not normalized. For instance, when $\parallel A \parallel_{\infty} \leq 1$ or when $A$ represents the adjacency matrix of a graph.


texts: Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed

texts:
Update:
This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution.
http://www.youtube.com/watch?v=VbSwwos4R2E
I want to know if there is an efficient algorithm that allows me to visit every node in a planar graph with the minimum weight, revisiting allowed.  Each node can have up to 4 linked nodes.

I uploaded the graph drawing as an example. In that example, one good route would be:

A - B - C - D - E - F - G - H - I - J - K - L - H - I - M

Summing weights:

11 + 3 + 1 + 7 + 10 + 7 + 3 + 2 + 2 + 4 + 4 + 4 + 2 + 1 = 61

But another route, with less weight, would be:

A - B - C - D - E - F - G - H - I - M - I - H - L - K - J

Weights:

11 + 3 + 1 + 7 + 10 + 7 + 3 + 2 + 1 + 1 + 2 + 4 + 4 + 4 = 60

Of course, I want to get the path with less weight. Revisited is allowed because otherwise I can't visit all nodes.
I'm not a Mathematician myself so easy talk would be much appreciated. I'm familiar with algorithms like A* and Dijkstra, that algorithms are useful when I have a target to search, but in this case I'm not searching a particular target.
Thanks!


texts:
I'm trying to wrap my head around the concepts of universal and existential types but everywhere I look, I see either logical or operational intuitions (or implementations) (e.g. TAPL book by B. Pierce), which, well... is good, but I'd like to see the definitions (where we look at them as sets) -- and from them, derivations of some laws, as well as justifications for our intuitions.

So, because I cannot find those definitions, I decided to do it myself and I think these may be reasonable:

$$\forall x.T \overset{def}{:=} \bigcap_{S - type} T[x := S] $$
$$\exists x.T \overset{def}{:=} \bigcup_{S - type} T[x := S] $$

But, in the aforementioned TAPL book, we are given this definition (although I would call it an identity)

$$\exists x.T \overset{def}{:=} \forall y. (\forall x. T \rightarrow y) \rightarrow y \quad (*)$$

I have two problems with this:

On the LHS of $(*)$ I would expect that $x$ was the only free variable of $T$ (because how to view a type "not-yet-built" with some free variables dangling in it?), but on the RHS it seems like $y$ may have some impact on $T$, so it better be a free variable in $T$. Hence LHS cannot be equal to RHS because sets of free variables of $T$ differ on both sides, right?
Even disregarding the concern at the point 1. -- I tried to rewrite RHS using my definitions and see if I can get my definition of existential type but I stuck:
$$ RHS = \bigcap_{S} (\forall x.T \rightarrow y)[y := S] \rightarrow S  = \bigcap_{S} \left(\bigcap_{R} T[x := R, y := S] \rightarrow S\right) \rightarrow S $$

It doesn't even remotely resemble my definition. Is it possible to simplify the formula I arrived at? Intuitively, because there are function types, it probably will never be equal to my definition. But if they are not equal -- are they at least 'isomorphic' in some sense? If not -- what "went wrong"?


texts: Is multiprocessing possible on a Turing Machine?

texts: I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on Turing Machine?


texts:
I have developed a new derandomization technique which is aimed at recursive randomized algorithms (or) more generally randomized algorithms that use a stack. Unfortunately, I could not find natural randomized algorithms to apply my techniques. Recursive Markov Chains and Stochastic grammars are very close to what I am looking for. Are there other (more natural) randomized algorithms that make "essential" use of stack ? Any help is greatly appreciated, since I am stuck with this for more than six months now.

To give you more context, I am looking for a list of problems similar to those in SivaKumar's Paper. Note that SivaKumar used Nisan's Pseudo-random generator to derandomize these problems.


texts: Where to learn more about what Theoretical Computer Science is?

texts:
I am a graduate student in math, and theoretical computer science is a domain which I never understood what it is about because I couldn't find a good read about the topic. I want to know what this domain is actually about, what kind of topics it is concerned with, what prerequisites are needed to embark into it, etc. For now, I just want to know:

  What is a good introductory book to theoretical computer science?

Given that there is such a thing. If not, where should a mathematician who has basic knowledge about computer science (i.e. they know the basics of one or two programming languages) start if they want to understand what theoretical computer science is about? What do you recommend?

thanks!


texts: Calculating least fixed points in equations

texts:
Given a set of relations/equations in some logic like LTL would it be possible to find a least fixed point for those equations?

For example take the equations in LTL

$$ P = Play ~\land X(P \cup S)\\
   S = Stop \land X(S)$$

These have a least fixed point with
$$ P = Play~ W~ Stop\\
   S = G~Stop $$

Are there any algorithms for finding fixed points or is this problem undecidable?


texts: Approximation algorithms for dominating set problem

texts:
I am working on approximation algorithms for minimum dominating set problem. In particular, I am interested in graphs classes restricted by forbidden induced subgraphs.
Since the domination problem and its variants have been extensively studied, I suppose someone may worked on this before.
So, the question is:

Does someone knows papers where it is studied approximation algorithms for domination problem for graphs classes defined by forbidden induced subgraphs?

Thanks in advance.
Kind regards.


texts: Finding subgraphs with high treewidth and constant degree

texts:
I am given a graph $G$ with treewidth $k$ and arbitrary degree, and I would like to find a subgraph $H$ of $G$ (not necessarily an induced subgraph) such that $H$ has constant degree and its treewidth is as high as possible. Formally my problem is the following: having chosen a degree bound $d \in \mathbb{N}$, what is the "best" function $f : \mathbb{N} \to \mathbb{N}$ such that, in any graph $G$ with treewidth $k$, I can find (hopefully efficiently) a subgraph $H$ of $G$ with maximal degree $\leq d$ and treewidth $f(k)$.

Obviously we should take $d \geq 3$ as there are no high treewidth graphs with maximal degree $<3$. For $d = 3$ I know that you can take $f$ such that $f(k) = \Omega(k^{1/100})$ or so, by appealing to Chekuri and Chuzhoy's grid minor extraction result (and using it to extract a high-treewidth degree-3 graph, e.g., a wall, as a topological minor), with the computation of the subgraph being feasible (in RP). However, this is a very powerful result with an elaborate proof, so it feels wrong to use it for what looks like a much simpler problem: I would just like to find any constant-degree, high-treewidth subgraph, not a specific one like in their result. Further, the bound on $f$ is not as good as I would have hoped. Sure, it is known that it can be made $\Omega(k^{1/20})$ (up to giving up efficiency of the computation), but I would hope for something like $\Omega(k)$. So, is it possible to show that, given a graph $G$ of treewidth $k$, there is a subgraph of $G$ with constant degree and linear treewidth in $k$?

I'm also interested in the exact same question for pathwidth rather than treewidth. For pathwidth I don't know any analogue to grid minor extraction, so the problem seems even more mysterious...


texts: Practical interactive proof schemes for NP-hard problems

texts:
Model-checking (in the sense of reachability in a succinct graph) is PSPACE-complete. SAT is NP-complete. Both problems are considered intractable, yet there exist tools capable of solving them on many industrially relevant instances.

Since IP=PSPACE, I was wondering whether there are approaches capable of performing interactive proofs on "realistic" instances of co-NP-hard problems.

I am aware of Goldwasser et al.'s Delegating Computation, but they focus on tractable problems (prover in P) with a very fast verifier. I'm rather considering difficult problems, such as showing that a propositional formula is unsatisfiable.

Obviously, for model-checking, I could encode the problem into TQBF (using Savitch's construction), then use Shamir and Shen's reduction to IP. I believe, however, that this would not yet anything workable even on instances on which known model-checking algorithms (e.g. based on ROBDDs or IC3) would work. As far as I know, reducing model-checking of non-toy examples to TQBF yields formulas that none of the best QBF solvers can deal with!

I realize this is not truly a theory question, since I'm requesting an answer about "workable" solutions rather than something along the lines of "this would require a prover capable of solving intractable problems so it's impossible".


texts: Effect of protocol ordering on multiparty comm. complexity

texts:
Brief Background

In Multi-Party Protocols by Chandra, Lipton, and Furst [CFL83], a Ramsey-theoretic proof is used to show a lower bound (and later, a matching upper bound) for the predicate Exactly-$n$ in the NOF multiparty communication complexity model. From the paragraph at the top of the second column of Page 1, we can see that they define the model such that the communication is strictly cyclic: e.g., for parties $P_0, P_1, P_2$, $P_0$ broadcasts at time $t=0$, $P_1$ broadcasts at time $t=1$, $P_2$ broadcasts at time $t=2$, then $P_0$ broadcasts at time $t=3$, and so on.

In most other papers, this cyclic ordering restriction is not made. For (arbitrary) example, in Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity by Beame, David, Pitassi, and Woelfel [BDPW07], a counting argument over protocols separates $\bf{RP}^{cc}_k$ from $\bf{P}^{cc}_k$. By their definition, "a protocol specifies, for every possible [public] blackboard contents [i.e., broadcast history] whether or not the communication is over, the output if over and the next player to speak if not." (emphasis added)

Importantly, the proof technique in [CFL83] appears (to my eyes) to crucially depend on the parties speaking in a cyclic/modular fashion.

Question

Allow me to play Devil's Advocate:

  Doesn't the lower bound proof of [CFL83] break if we allow the parties to speak in an ordering specified by the protocol? More specifically, is it possible there could there be a protocol with a different communication pattern than cyclic for Exactly-$n$ in the NOF model that costs less than the $\log(\chi_k(n))$ lower bound given in the paper?

Or more generally -- what's going on here? Why is one (highly cited) paper (I use the following very liberally) "allowed" to restrict the possible protocols to round-robin communication patterns only?


texts: Property testing of triangular properties

texts:
Several years ago I worked a few days with a collaborator on property testing of triangular property. We end up with a disappointing result that I am sharing here and for which I am asking if a better result is known, or if you have some ideas about the problem.

Let $K_n=(V,E)$ be the complete graph on $n$ vertices and $S$ be a set. Let $\phi:V\times V\rightarrow S$ be a function, and let $1>\epsilon>0$ be a real number.

We are interested in triangular properties, that is properties of triangles (sets of 3 items). Our final goal is to decide with high probability if a set violates "strongly" a triangular property (in the sense of the property testing.

definition
A triangular property $P$ is a function $P:S^3\rightarrow{0,1}$ that is invariant under permutations.
The function $\phi$ is said to have the property $P$ if for all triangles ${a,b,c}$ the value $P(\phi(a,b),\phi(b,c),\phi(c,a))$ is equal to 1.
The function $\phi$ is said to be at least $\epsilon$-far from having property $P$ if for all function $\psi:V\times V\rightarrow S$ having the property $P$ the functions $\phi$ and $\psi$ differ on at least $\epsilon\cdot n^2$ values.
Two triangles are said to be independent if their intersection is empty.
A triangle $v$ is said to be bad (with respect to $P$) if $P$ takes the value 0 on it.

Our result is a property tester for triangular properties :

Input: a function $\phi:V\times V \rightarrow S$ and a triangular property $P$.
Output: the answer to whether or not $\phi$ is $\epsilon$-far from having property $P$.

1) Select a random set of vertices $V'$ of size $\epsilon^{-1/3}n^{2/3}$.
2) Request all the values of the restriction of $\phi$ to the complete graph $K_{\epsilon^{-1/3}n^{2/3}}$ induced by $V'$
3) Check on all the triangles whether $P$ is satisfied or not.
4) Return 0 if a triangle is bad, and 1 otherwise.

How do we obtain this? the first step is a technical result that gives the proportion of disjoints triangles that violate $P$, then we use a probabilistic argument based on a balls and bins theorem, and the result follow. Clearly this algorithm is far from being optimal. The problem is in the technical result:

The technical result:
Suppose that $\phi$ is $\epsilon$-far from having property $P$. Let $B$ be a set of vertices so that $\phi$ induces a function that has property $P$ on the restriction of $K_n$ to $V-B$. Then the cardinality of $B$ is greater than $\epsilon\cdot n$.
Using a $B$ as defined before, There exists a family $C$ of independent triangles in $K_n$ such that
- each triangle in $C$ is bad,
- $|C|\geq\lfloor\frac{|B|}{3}\rfloor\geq \frac{\epsilon\cdot n}{3}-1$.

Clearly, the problem is that our lower bound on the size of $C$ is poor. It is a shame that we have no better bound since the bound on $B$ is great.
Since we have a bad lower bound on $|C|$, we cannot obtain an interesting complexity for the tester...

So, the question is : are you aware of a result on this problem ? And if not, have you got some better ideas that we have ?


texts: Algorithm Suggestion for Scoring System - weighted solution

texts:
I'm trying to validate a series of words that are provided by users. I'm trying to come up with a scoring system that will determine the likelihood that the series of words are indeed valid words.

Assume the following input:

xxx yyy zzz

The first thing I do is check each word individually against a database of words that I have. So, let's say that xxx was in the database, so we are 100% sure it's a valid word. Then let's say that yyy doesn't exist in the database, but a possible variation of its spelling exist (say yyyy). We don't give yyy a score of 100%, but maybe something lower (let's say 90%). Then zzz just doesn't exist at all in the database. So, zzz gets a score of 0%.

So we have something like this:

xxx = 100%
yyy = 90%
zzz = 0%

Assume further that the users are either going to either:

Provide a list of all valid words (most likely)
Provide a list of all invalid words (likely)
Provide a list of a mix of valid and invalid words (not likely)

As a whole, what is a good scoring system to determine a confidence score that xxx yyy zzz is a series of valid words? I'm not looking for anything too complex, but getting the average of the scores doesn't seem right. If some words in the list of words are valid, I think it increases the likelihood that the word not found in the database is an actual word also (it's just a limitation of the database that it doesn't contain that particular word).

NOTE: The input will generally be a minimum of 2 words (and mostly 2 words), but can be 3, 4, 5 (and maybe even more in some rare cases).


texts: What is the best exact algorithm to compute the core of a graph?

texts:
A graph H is a core if any homomorphism from H to itself is a bijection. A subgraph H of G is a core of G if H is a core and there is a homomorphism from G to H.
http://en.wikipedia.org/wiki/Core_%28graph_theory%29

Given a graph G, what is the best known exact algorithm to find its core?


texts: "Directed" problems that are easier than their "undirected" variant.

texts:
I was presenting a lecture on pancake sorting, and mentioned that:

Sorting by reversals is NP-hard
"signed" sorting by reversals is in P.

Which got me thinking. There is a sense in which "signed" sorting is "directed" - you can view the sign as a direction (and indeed, this is the motivation from evolutionary biology). But it's an easier problem ! This is unusual because generally (at least on graphs) directed problems are harder (or at least as hard) as their undirected counterparts.

  Assuming a generous definition of "directed", are there any examples
  of directed problems that are easier than their undirected
  counterparts ?


texts: Program size versus program running time

texts:
Short "naive" question:

Is it true that faster algorithms require longer programs ?

Given a decision problem $A$ and a reasonable model of computation, there can be many ways (algorithms) to solve it, and some of them can be extremely inefficient or extremely efficient (when the time complexity of the algorithm matches the time complexity of the problem). For example the primality test can be done using the Sieve of Eratosthenes algorithm which is quite simple but requires exponential time or the AKS primality test which runs in polynomial time but is rather complex and requires a "lot of code".

Are there other examples of problems that can be solved "slowly" by a very simple algorithm, but the most efficient algorithm known is very complicated and requires a much bigger program?
What could be the underlying explanation for such behviour? (e.g. Kolmogorov complexity seems not to play any role)


texts: Lexicographic perturbation for euclidean shortest path instances?

texts:
Assume we have an undirected graph $G=(V,E)$ and vertex locations $\pi: V \rightarrow \mathbb{R}^2$. I am looking for a procedure to perturb the vertex positions to obtain new positions $\pi'$ such that the following statements hold:

For every pair $s\neq t \in V$, there is a unique shortest s-t-path $P_{s,t}$ in $G$ w.r.t. the euclidean weight function $c(v,w)=|\pi'(v)-\pi'(w)|_2$.
$P_{s,t}$ is also a shortest s-t-path w.r.t. the original vertex positions $\pi$.
$\pi'$ can be deterministically computed in polynomial time given $\pi$. The length of the numbers occuring in $\pi'$ are polynomially bounded in the length of those in $\pi$.

I know that lexicographic perturbation is a standard procedure to do this deterministically. Sadly there is no simple way to modify the distance of only a single edge in euclidean instances.

Is there any known approach that can be applied to those euclidean instances? Even a randomized perturbation algorithm would be interesting for me.


texts: Is $GCT$ necessarily a negative result program?

texts: $GCT$ is a candidate program to separate permanent and determinant through symmetries. If indeed permanent and determinant can be handled in similar complexity class would $GCT$ be a program which can provide the insight? Is so how would the hypothetical demonstration be?


texts: VC-dimension of infinite set of triangle wave

texts:
I am searching for the VC-dimension of the following:
What is the VC-dimension of the infinite set of triangle wave functions with
amplitude 1 and period parameter p on points on the line?
2πarcsin(sin(2πx⁄p))


texts: Why does LTL equivalence (with next oeprator) implie trace equivalence in finite transition machines?

texts:
I am following Katoen's YouTube course about Model Checking.
I am trying to understand how finite transition machines are different from infinite transition machines in terms of equivalences. That lead me to the following question regarding equivalences, but the focus there was on infinite transition machines. Comments in the thread claimed that LTL equivalence = trace equivalence in finite transition machines, when LTL includes the next operator but I do not see how.
The direction from trace equivalence to LTL equivalence is immediate, due to the fact that only traces satisfy LTL formulas.
The other direction is problematic for me:
If we have two transition machines that are LTL equivalent, I understand that they are equivalent with respect to finite traces, because I can use the next operator, but what happens with infinite traces?
If I try and assume the claim is false in hopes of reaching a contradiction, I get that an infinite number of prefixes from each infinite trace from either transition system would have to be in both trace sets, but where's the problem? Can't I express infinitely many different prefixes using a finite transition machine?


texts: TSP heuristics for limited distance information

texts:
this is my first question on Theoretical CS. :)

I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site.

Problem:

  I'm looking for TSP heuristics in the case of limited information about the edges, for example: I have $n$ nodes but can only ask for $~\sim4n$ distances. My graphs are metric and
  I can make an estimate in advance with the euclidean distance, which provides a lower bound, but those estimates might be very bad.

Question:

  So what are the TSP-Heuristika for those distance-matrices?

Thanks in advance.


texts: To what extent can the mathematics of Reals be applied to Computable Reals?

texts:
Is there a general theorem that would state, with proper sanitization,
that most known results regarding the use of real numbers can actually
be used when considering only computable reals? Or is there a proper
characterisation of results that remain valid when considering only
the computable reals? A side question is whether results concerning
computable reals can be proved without having to consider all real, or
anything that is not computable. I am thinking specifically of
calculus and mathematical analysis, but my question is in no way
limited to that.

Actually, I suppose there is a hierarchy of computable reals
corresponding to the Turing hierarchy (Is that correct?). Then, more
abstractedly, is there an abstract theory of real (I am not sure what
the terminology should be), for which a number of results could be
proved, that would apply to the traditional real numbers, but also to
computable reals, and to any level of the Turing hierarchy of
computable reals, if it exists.

Then my question could possibly be stated as: Is there a
characterization of results that will apply in the abstract theory of
reals when they have been proved for traditionnal reals. And, could
these results be proved directly in the abstract theory, without
considering traditional reals.

I am also interested in understanding how and when these theories of
reals diverge.

P.S. I do not know where to fit this in my question. I realised that a good deal of the mathematics on the reals have been generalized with topology. So it may be that the answer to my question, or part of it, can be found there. But there may also be more to it.


texts: There is a paper by Ritt from 1923 that calls the relation,  $f(g(x)) = g(f(x))$, permutable functions. Is there a more recent terminology used in the literature, or is this still the standard?


texts:
I hope you can help.  I am looking for the best way to generate random bipartite graphs with localised structure within one of the node types.  Such that type A visits a local group of type B with a particular probability and then within that group connectes an edge with type be also with a particular probablity based on the attribute of nodes of type B.  Basically this is social network data where one group has a preference function that determines the probability of linking with another individual of a different type. However the choosey group os restricted in the node value distributions they see due to the localised groupings of the chosen type.

Sorry I hope this question does not bore.  All programs I have tried do not allow both this localised structure by trait values as well as probability of pairing based on trait values.

Best Wishes,
Colin


texts: Number of mincuts of a graph without using Karger's algorithm

texts:
We know that Karger's mincut algorithm can be used to prove (in a non-constructive way) that the maximum number of possible mincuts a graph can have is $n \choose 2$.

I was wondering if we could somehow prove this identity by giving a bijective (rather injective) proof from the set of mincuts to another set of cardinality $n \choose 2$. No specific reasons, its just a curiosity. I tried doing it on my own but so far have not had any success. I would not want anyone to squander time over this and so if the question seems pointless I would request the moderators to take action accordingly.

Best
-Akash


texts:
I am interested in the following flow problem, since it turns out to be equivalent to a more general problem.

INPUT: A graph where each edge $e$ has an integer multiplier $q_e$, and a lower bound $b_v$ for each vertex $v$

QUESTION: Is there a flow, such that the flow sent on each $e$ is a multiple of $q_e$ (in either direction), and such that the net flow in to each $v$ is greater than or equal to $b_v$?

Is this problem in P or NP-complete?

So far I have found it is in P if the $q$'s form a chain under division; but if to that we add upper and lower bounds to edges then it becomes NP-complete.

I posted a reformulation using lattices on MO.


texts: Is there a natural problem in quasi-polynomial time, but not in polynomial time?

texts:
László Babai recently proved that
the Graph Isomorphism problem is in quasipolynomial time.
See also his
talk at University of Chicago,
note from the talks by Jeremy Kun
GLL post 1,
GLL post 2,
GLL post 3.

According to Ladner’s theorem,
if $P \neq NP$, then $NPI$ is not empty,
i.e. $NP$ contains problems that are neither in $P$ nor $NP$-complete.
However, the language constructed by Ladner is artificial and
not a natural problem.
No natural problem is known to be in $NPI$
even conditionally under $P \neq NP$.
But some problems are believed to be good candidates for $NPI$,
such as Factoring integers and GI.

We may think that with Babai's result,
there might be a polynomial time algorithm for GI.
Many experts believe that $NP \not\subseteq QP = DTIME(n^{poly\log n})$.

There are some problems for which we know quasi-polynomial time algorithms,
but no polynomial time algorithm is known.
Such problems arise in approximation algorithms;
a famous example is the directed Steiner tree problem,
for which there is a quasi-polynomial time approximation algorithm
achieving an approximation ratio of $O(\log^3 n)$
($n$ being the number of vertices).
However, showing the existence of such a polynomial time algorithm
is an open problem.

My question:

  Do we know any natural problems which are in $QP$ but not in $P$?


texts: Is the Balanced Boolean Formula problem solvable in sublogarithmic space if the input has a tree structure?

texts:
Suppose that instead of the usual linear work tape the input is given in a binary tree structure with n leaves and log n depth, the initial position being the root. At every node, we can step to its parent, left child or right child.

I am interested in what "tree-languages" can be accepted by what machines. More specifically, take the language where in every non-leaf we have the gate of a boolean circuit (ie. and or not), in the leaves either a constant or a variable (different for each leaf) and such a "tree-word" is in the language if and only if it has a satisfying assignment. Can this language be decided by a turing machine that has an o(log n) space worktape?

Note that it is accepted by a non-deterministic finite state machine and also by a deterministic turing machine with O(log n) space. Similarly, if all the variables are constant, then it can be decided by a deterministic finite state machine. (If there are no constants, then every formula is satisfiable.)


texts: Is the value of $\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf}$ polynomially computable?

texts:
For a graph $G$ on $n$ vertices, what is the value of following ratio:

$$\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf} ,$$

where $L_G=D_G-A_G$ is the laplacian matrix of $G$?

Is this parameter related to the spectrum of $G$?

Is this parameter polynomially computable?

Remark: Note that we have
$$\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{f^Tf} = \lambda_n(G),$$
where $\lambda_n(G)$ is the largest eigenvalue of $L_G$.


texts:
In the multiterminal cut the input is a graph $G$ and a subset $T$ of its vertices. The task is to remove the minimum number of edges from $G$ such that there is no path connecting any distinct vertices of $T$. The problem is APX-hard, even when $T$ has 3 vertices. This was shown in by Dalhaus et al (E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, M. Yannakakis: The Complexity of Multiterminal Cuts. SIAM J. Comput. 23(4): 864-894, 1994.)

I am interested in the actual value $\alpha>1$ such that no $(\alpha-\varepsilon)$-approximation is possible for multiterminal cut, unless P=NP. A quick adaptation of the reduction used by Dalhaus et al. for general $T$ implies $\alpha=89/88$. (For $|T|=3$ the constant is worse, but I am interested in arbitrary $|T|$.)

My question is: has there been any improvement over Dalhaus et al for the inapproximability of multiterminal cut? Are there other NP-hardness proofs of multiterminal cut in the literature?

Since there are constant-factor approximations for the problem, the question here is about constants.


texts: What is known about this binary representation polytope?

texts:
Consider the following set.

$S_n =\{ (x,y) ~|~x \in \mathbb{Z}_+~\wedge~ y \in \{0,1\}^n ~\wedge~x=\sum_{i=0}^{n-1} 2^i y_i \}$

$S_n$ is a collection of pairs $(x,y)$, where $x$ is an integer between 0 and $2^n-1$ and $y$ is its binary representation. I'm interested in the convex hull of $S_n$; you can call it $P_n$.

Has $P_n$ been studied before? Does it admit a compact extended formulation?


texts: Average number of sets given by greedy set cover? Is it uniform distribution?

texts: We're covering the whole random universe $U$ of size $m$ with random sets $S_{1},\dots S_{n}$. I know that greedy set cover gives us a number between size of the minimal set cover and size of the minimal set cover multiplied by factor $H_{max\{|S_{i}|, \hspace{1 mm} for \hspace{1 mm} i=1,\dots, n\}}$ where $H_{i}$ is the $i-th$ harmonic number. My qestion is, what is the exact average number of sets we're going to get? Does the number of sets given by greedy behave as a normal distribution?


texts: How to analyze the quality of data definition language?

texts:
I know that DDL is most often used when talking about databases, but I see no reason why XML, PDF or even to some extent Prolog shouldn't belong to this category. It looks like branches of CS traditionally associated with studying languages wouldn't do very good job at analyzing DDLs.

Whichever approach to semantics you take, it doesn't seem to be meaningful, when applied to structured representation of data.

The notion of complexity is only so much relevant to data structures - it tries to answer the question of what would it mean to use a data structure for a particular task, but not the questions about the data structure itself.

Another reason for me to ponder this question is that based on my intuition, I can say things like "this data definition language seems to be better suited for the task", or "this data definition language seems to do a bad job when modelling the real-world situation", but I don't know where to look for the formalism which may support or debunk this intuition.

The comments suggested that I rephrase the question. Of course quality is a very broad concept, but I'm not only interested in efficiency. Or, more precisely, I don't really know what does it mean for a DDL to be efficient.

I will make it furthermore concrete. I was tasked with improving a file format of an application for editing presentations. The current version of this format is an XML, which basically dumps the application state at the time the user requested to save the file, and that's it. There are multiple downsides of this approach, beside the entire format was created ad hoc, unsystematically etc.

I red the Grammar of Graphics by Wilkinson, and thought that it had many great ideas about how to generalize and conceptualize in conceptually similar field. I also red about Allen's interval calculus and some other literature on how to formalize time in language. But more then just a set of ideas, I need some sort of quality assurance. Something that would give me some sense of guarantee, that the tools available to the language do indeed meet the needs, and that they do it in an optimal way (or not, and if not, then how far off am I). Of course it might be too naive to expect to have a metric that would just produce a numerical answer, but anything that I could use in the same way one could use asymptotic analysis would be great.

I did try to find an answer to the question myself. Here is the closest I think I found so far:

Orthogonality principle, as stated by Wilkinson in Grammar of Graphics:

  As much as possible everything should work everywhere and in every
  combination.

Hierarchy principle

  Complicated tasks should be done by enlisting support of simpler
  helpers.

While this sounds reasonable to me, I don't know how to approach the task of calculating these.

I also took courage to add one more principle:

Comprehensiveness. The notation should observe the bounds imposed by physical abilities of the reader.

Beside these, I tried to approach the problem from linguistic perspective. There is, for example, a notion of a measure of entropy of a grammar (for example, if talking about Hausdorff dimensions and topological entropy). But this is both too advanced for me, and I don't think this is "a thing" about data definition languages.

I also tried to approach the problem from the perspective of expressiveness, for which purpose I've been reading Matthias Felleisen On The Expressive Power of Programming Languages, but I find the analogy too removed / difficult to apply, because this book models its notion of expressiveness on lambda calculus, which doesn't fit well with what I'm trying to understand.


texts: Parallel building time of a k-d tree on n points with n processors

texts:
Given a point set with $n$ points to build a k-d tree on. We have $n$ processors available. What is the time-optimal building time for the k-d tree?

A straight forward parallelization would be as follows: In each step $i$, we have to sort $i$ sets of $n^2/2^i$ points in the dimension with largest spread, which takes $\log(n^2)-i$ time for each of the $\log(n^2)$ levels of the tree, resulting in an upper bound for the total building time of $\Omega(\log^2(n))$.

However, this only holds for a straight forward parallelization. As a k-d tree can be used for sorting by placing all points along one dimension, by e.g. this paper, it therefore has a minimum build time of $\mathcal{O}(\log(n))$.

Can this gap be closed in either direction? That is: Can the k-d tree be built in $\Theta(\log(n))$ or $\Theta(\log^2(n))$?


texts: If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?

texts:
NP-hard problems are not used in cryptography, because they are believed to be computationally-intractable in the worst case but are not computationally-intractable in the average case.

Is there a way to identify whether a given problem instance (for example, of 3SAT) is computationally-intractable before attempting to solve it? Are there characteristics common to all pathological instances?
If we can identify the characteristics of computationally-intractable problem instances, why are those considered to be the same problem as other problem instances which are easily solvable? It seems like the real NP-Hard problem statement should be "3SAT instances with structure {x, y, z}" not just "3SAT".

For example, any 2SAT problem instance (solvable in polynomial time) can be restated as a 3SAT problem instance:

$(x_0 \lor x_1) \land (x_0 \lor \lnot x_2) = (x_0 \lor x_1 \lor x_1) \land (x_0 \lor \lnot x_2 \lor \lnot x_2)$


texts: New algorithm for Discrete log and its implications for Quantum computing

texts:
A new paper came out claiming quasi-polynomial algorithm for Discrete Logarithm.
http://arxiv.org/abs/1306.4244

If correct, does it mean we no longer have an exponential separation in complexity of a classical algorithm and its quantum version for the discrete logarithm problem? Does this have any implication for quantum complexity theory?


texts: Relation between computational complexity and information

texts:
I work in a computational neuroscience lab that quantifies the mutual information between pairs or groups of neurons. Recently, the boss his shifted focus to measuring the "complexity of neural dynamics". In pursuing that line of research, some people in my group appear to equate "complex" with "has a high entropy".

Can anybody guide me on what the relationship is between computational complexity (in a CS sense) and entropy in the information theory sense?

To explain a bit further, measures like Lempel-Ziv complexity, don't seem, to me, valid measures of complexity because they conflate informative (to the user) with carrying a lot of bits. Other measures, like [Causal State Splitting Reconstruction][1] are much less known but have the appealing property that random processes have zero complexity, because zero hidden states are needed to represent a stationary random process.


texts:
Given a list of (small) primes $ (p_0, p_1, \dots, p_{n-1})$, is there an (efficient) algorithm to enumerate, in order, all numbers that can be expressed as $ \prod_{k=0}^{n-1} p_k^{e_k} $, where $e_k \in \mathbb{Z}, e_k \ge 0 $?  What about in a certain interval, potentially at an exponential starting point?

For example, if we had the set $(2,3,5)$, the first few numbers would be $(2, 3, 2^2, 5, 2 \cdot 3, 2^3, 3^2, 2 \cdot 5, \dots )$.

Is there an algorithm to efficiently enumerate all the numbers not expressible as a product of powers of primes from the set?  How about in an interval?

Note:  I just saw the Polymath paper on deterministic prime finding in an interval ( Deterministic methods to find primes ) and thats what inspired this question.  I don't know if it's important that the set be a list of primes, but I'll keep it in there just in case.

EDIT: I was unclear by what I meant by 'efficient' .  Let me try making it more precise:

Given a list of $n$ primes $(p_0, p_1, \dots p_{n-1})$ and a bound, $B$, is it possible to find in polynomial time with respect to $lg(B)$ and $n$, the next integer, $x$, such that $x > B$ and is expressible as a product of powers of primes from the list?


texts:
Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$?

i.e. Given $N = 2^\eta$, $M = 2^\mu$ (with $N$, $M \in \mathbb{Z}$), find bit $2^\mu$ of $(2^\eta)!$ in $O( p(\eta, \mu) )$.

Note: I have asked this on mathoverflow.net here and have not been getting any answers so I have cross-posted.

From the comment on the other site, Gene Kopp points out that one can efficiently compute the lower order bits by doing modular arithmetic and higher order bits using Stirling's approximation, so this question is really 'how efficiently can one compute the middle order bits?'.


texts: Known property? Maximum radius of connected induced subgraph

texts:
I was wondering if the following graph property has a name and has been researched:
Consider any connected induced subgraph $H \subseteq G$.
Then $r(G)$ denotes the maximum radius of any such $H$.

I think it is an interesting property since graphs with bounded $r(G)$ are closed under taking induced subgraphs whereas graphs of bounded radius are not.

Edit: The reason why I am only interested in induced subgraphs is that it otherwise would degenerate to the length of the longest (not necessarily) induced path.