texts: Finding nodes with enough unique ancestors

texts:
Given a DAG $G = (V, E)$, let $T \subseteq V$ be a set of nodes of $V$ that is computed via the following process. Assuming the nodes of $G$ are sorted in topological order, $v_1, \dots, v_n$. We process the nodes in this topological order. Suppose we are processing vertex $v_i$ in the order. Let $r(v_i)$ be the set of ancestors of $v_i$. We add $v_i$ and all ancestors of $v_i$ into $T$ if and only if the number of ancestors of $v_i$ (including $v_i$ itself) that are not in $T$ is at least $\frac{|r(v_i)| + 1}{f}$ where $f$ is some constant $f > 1$ provided as part of the input. If a vertex is added to $T$, then all its ancestors are also added into $T$. Any algorithm that computes $T$ must satisfy the following invariant: any vertex $v_i$ added into $T$ must have at least $\frac{|r(v_i)| + 1}{f}$ of its ancestors (including itself) not in $T$ when it was added, and any vertex $v_i$ not added into $T$ must have $< \frac{|r(v_i)| + 1}{f}$ of its ancestors (including itself) not in $T$.
Problem: Provide an algorithm that runs in $\tilde{O}(m + n)$ time (meaning ignoring polylogarithmic factors) that provides a valid set $T$ given an input graph $G = (V, E)$ and the processing order of the vertices is the toposort order. Approximation (meaning constant error on the $\frac{r(v_i)+1}{f}$ condition) and Las Vegas algorithms are welcome also. You may preprocess the graph but the preprocessing time must also be $\tilde{O}(m + n)$.
Trivial Solution in More Time We can do this trivially in $O(nm)$ time. For each $v_i$, we find via BFS its set of ancestors and check whether each one is in $T$. From this we can compute the exact fraction that is not in $T$ and either put $v_i$ and $r(v_i)$ in $T$ or not.
Example Problem: Suppose you have the following trivial DAG (below) and $f= 2$.

a -> b -> c

Then, $T = \{a, b\}$. $a$ is processed first and $T = \emptyset$ at first so $a$ is added into $T$. Then, $b$ is processed after $a$ and is added to $T$ since $1/2$ of the vertices in $\{a, b\}$ are not in $T$. Finally, $c$ is processed and not added to $T$ since it has at most $1/3$ of the vertices in $\{a, b, c\}$ are not in $T$. Note that in this example, a trivial $O(n)$ algorithm for any line is to keep a counter $c$ of the index of the last element added to $T$ (since adding the element at $c$ also means adding all its ancestors) and add the $i$-th element of the line to $T$ if $\frac{i-c}{i} \geq \frac{1}{f}$. However, this problem is much less trivial for general graphs.
Has anyone seen a problem similar to this in the literature or algorithms which solve similar problems?


texts: Estimate the maximum frequency of substring with given length in a very long character stream

texts:
Suppose there is a very long string $S\in \Sigma^N$ with length $N$, where $\Sigma$ is a relatively small alphabet (for example, $\Sigma=\{'a', 'b', \ldots, 'z'\}$). Now, given a budget $B$, the goal is to find the solution of following problem:
$$
\begin{align*}
\min_{l\in\mathbb{N}} &\quad l \\
\text{s.t. }& \max_{s\subset S, |s|=l} \ \text{freq}(s) < B
\end{align*}
$$
i.e., I want to find a length $l_c$, such that for "any" substring $s\subset S$ with length $|s|>l$, it occurs no more than $B$ times.

Assume every character in $S$ obeys the same known distribution $D$: $S[i]\sim D, \forall i\in[N]$. Here we can allow some violations in the constraint, only requiring
$$
\Pr[\max_{s\subset S, |s|=l} \ \text{freq}(s) < B] > 1-\delta.
$$

Currently I'm using a brute force approach, testing each $l$ from small to large, where for each $l$ I scan through the whole string $S$ to determine if there is one substring occur too often. This is very inefficient since $|S|$ is huge.

So I want to know if there exists some sub-linear (w.r.t. $N$) algorithm that can estimate the maximum frequency of substrings with fixed length.

Maybe I didn’t make it clear. Here is my problem:

Given a constant $B$ and the length of the string $N$, I want to find the minimum length $l$, such that all $l$-long substrings occur no more than $B$ times. Is there a algorithm better than simply testing from small to large?
If it's expensive to determine the exact $l$, an approximated $l$ is also acceptable. Here "approximated" has two meanings: $l$ can be smaller than the true $l_c$ as long as there're not too many violating $l$-long substrings; or it can be larger that $l_c$, but not too far away.
Furthermore, if the distribution of input character is highly skewed (i.e., some characters occur far more often than others), can I find an approximate or exact $l$, such that all $l$-long substrings starting with some fixed character $s$ occur no more than $B$ times?


texts:
Consider a graph optimization on a graph with n vertices and m edges that can be written as an LP (like say bipartite matching). By the duality with vertex cover, we know that there's a sparse dual solution consisting of the  elements of the cover. It's sparse in the sense that its size is linear in n, rather than in m.

Consider the problem of finding the minimum enclosing ball of a set of $n$ points in $d$ dimensions. This is an LP-type problem with (again) a sparse dual solution: a set of $d+1$ points that define the optimal ball. Here, "sparse" means that the size depends on the (smaller) parameter $d$ rather than $n$

In general, suppose I have a problem that can be expressed via an LP with $n$ variables and $m$ constraints, where $m \gg n$. Are there classes of such  problems for which any optimal solution to the problem can be expressed using the intersection of only $O(n)$ constraints (or dually with only $O(n)$ nonzero dual variables ?


texts: Embedded dynamic programming (and planar subgraph isomorphism)

texts:
In Planar Subgraph Isomorphism Revisited, Frederic Dorn obtains an improved algorithm for Planar Subgraph Isomorphism, by using a technique he calls Embedded Dynamic Programming.  This technique appears to me to be a generalization of dynamic programming, in that it builds up from the smallest possible instances, but then, to obtain the next stage, one considers only a relevant subset of the already-computed subinstances, instead of considering all of them.

I am interested both in the planar subgraph isomorphism problem, and in the embedded dynamic programnming technique.

A search on the phrase "embedded dynamic programming" is unhelpful, and it seems to me that this idea is close enough to dynamic programming that (some variant of) it might have been used in the past, for another problem, under another name.  Does anybody know anything about this?

  Are there other papers that use embedded dynamic programming?
  Are there pre-existing techniques in the literature that are "cousins" to this approach?

I am also interested in implementability.  My not-very-serious-yet review of Dorn's paper makes me think his algorithm might be usefully implementable.  Motivation here: most (empirical definition of most) molecular graphs are planar.  The subgraph isomorphism implementations for molecular graphs have been optimized over a period of years, so they would be hard to beat in practice.  Still, if this is a fundamentally new approach without a lot of hidden constants, then there might be something really exciting here.

  Do you think Dorn's algorithm is realistically implementable?  Or could a simple variation have that property?

Thanks, and I hope this question is more sensible than my last one, which was a bit of a disaster.


texts:
Consider the following problem:

Suppose we are given a G=(V, E) Euclidean Graph in the plane and a real $\alpha > 0$. For simplicity assume, there exists only one path whose summation of weights over all edges is equal to \alpha. Give a polynomial decider to report such a \alpha-path in G if exists.

In spite of the fact that there are several experimental results (heuristic algorithm) for this problem I know there are several randomized algorithms have been given by people using color-coding in running times O(2^k. poly(n)) [Williams] and O((1.625)^k.poly(n)) [Abbasi et al.], etc. for the case that graph is Unweighted, Non-geometric and integer k is considered as the number of vertices on the target path. The question is, is there any approximation algorithm for either on Euclidean or general graph or not? ( I know \alpha or k can be large to extract the longest path, but here the length of longest path is given and might not be as hard as longest path problem).
I am trying to come up with a preliminary solution for the Euclidean case using a hierarchical structure like quadtree or something to store the length of each subpath hierarchically into some higher level node(s) of the tree. Finding K=O(log \phi) nodes in the tree that gives us c.\alpha-path or some c, can tell us about the existence of a path on original graph. Can anyone give me some feedback about this approach? Or do I need using another different data structure? Any comment in regard to this problem is appreciated!


texts: Lossless, constant-degree expanders that expand large sets

texts:
It is known how to construct "lossless" unbalanced bipartite expanders with the following properties: the bipartite graph has $n$ left vertices, $m$ right vertices, left-degree $D$, and for all left-sets $S$ of size up to $\gamma n$, the neighbor set $\Gamma(S)$ has size at least $(1 - \epsilon)D|S|$, and this is achieved for any $m \leq n, \epsilon > 0$, and $D = \Theta(\log(n/m)/\epsilon)$, $\gamma = \Theta(\frac{\epsilon m}{Dn})$. The construction due to  Capalbo, et al. achieves these parameters.

It's clear that $\gamma \leq m/(Dn)$, but how large can $\gamma$ be? In particular, I'm wondering if it's possible to make $\gamma$ very close to $1/4$, say; this would essentially require one to make $m = n$ and $D = 4$ for any hope of accomplishing this --  $\epsilon$ hasn't even been considered yet! However, does anyone familiar with expander constructions have a sense of what hidden constants lay within the $\Theta$'s?


texts: Is the integer factorization problem harder than RSA factorization: $n = pq$?

texts:
This is a cross-post from math.stackexchange.

Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $e_i \in \mathbb{N},$ such that $n = \prod_{i=0}^{k} p_{i}^{e_i}.$
Let RSA denote the special case of factoring problem where $n = pq$ and $p,q$ are primes. That is, given $n$ find primes $p,q$ or NONE if there is no such factorization.
Clearly, RSA is an instance of FACT. Is FACT harder than RSA? Given an oracle that solves RSA in polynomial time, could it be used to solve FACT in polynomial time?
(A pointer to literature is much appreciated.)

Edit 1: Added the restriction on computational power to be polynomial time.

Edit 2: As pointed out in the answer by Dan Brumleve, there are papers arguing for and against RSA being harder (or easier) than FACT. I found the following papers so far:

D. Boneh and R. Venkatesan. Breaking RSA may be easier than factoring. EUROCRYPT 1998. http://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf
D. Brown: Breaking RSA may be as difficult as factoring. Cryptology ePrint Archive, Report 205/380 (2006) http://eprint.iacr.org/2005/380.pdf
G. Leander and A. Rupp. On the Equivalence of RSA and Factoring regarding Generic Ring Algorithms. ASIACRYPT 2006. http://www.iacr.org/archive/asiacrypt2006/42840239/42840239.pdf
D. Aggarwal and U. Maurer. Breaking RSA Generically Is Equivalent to Factoring. EUROCRYPT 2009. http://eprint.iacr.org/2008/260.pdf

I have to go through them and find a conclusion. Is someone aware of these results, who can provide a summary?


texts: Dependent C-style types with subtyping rule

texts:
I'm looking for previous work regarding an extension of a C-style type system in which types may have constraints and have a defined subtyping rule. In particular, I'm interested in defining algebra-like rules for types on which an order relation exists.

I will use integers for the rest of the examples, but those could be swapped for any kind of object that defines a total order relation.

Right now, I have a system that allows me to define a type as being a pair $(T, \phi)$ where $T$ is a "basic" C-style type (not a pointer, for instance) and $\phi$ is a constraint expressed in a simple language that is basically an extension of propositional calculus. For example, $(\texttt{int}, (>30)\ \text{and}\ (<40))$ would represent the type of integers between 30 and 40. This is similar to what happens in Dependent types, but is significantly less expressive.

I also define a subtyping rule based on the Liskov substitution principle, that specifies that given two types $\mathcal{T}_1 := (T, \phi_1)$ and $\mathcal{T}_2 := (T, \phi_2)$, $\phi_1 \vdash \phi_2 \implies \mathcal{T}_1 <: \mathcal{T}_2$. For instance,
$$
(\texttt{int}, (>30)\ \text{and}\ (<40)) <: (\texttt{int}, (>0)\ \text{and}\ (<100))
$$

For my needs, I am not interested in equivalence or isomorphism between types, only subtyping. I believe that by such "reductions", this flavour of dependent typing can be proved to be decidable.

I've been searching for previous works regarding something similar to what I have right now, but most of the works seem to focus on higher-order lambda calculus. This thread lists various articles regarding such works.

I'm struggling understand what to look for, as I do not know how such a system could be described, because "dependent types" and "subtyping" are obviously very broad fields and lead me to very general papers, while I'd like to find something that is more specific and less expressive.

EDIT: To clarify, the "C-style type" enhanced by a formula is generally a numeric data type, but could be struct if the struct were to define an order relation. I'm not specifically looking for anything regarding arrays, but it would be a "nice to have".


texts: Unwinding a data structure to a previous state

texts:
Suppose I have an algorithm which maintains a data structure $A$. After the algorithm has run up to time $t_2$, it decides to back-track to a prior state $t_1$. It should be possible to restore the state of $A$ to what it was at time $t_1$ by simulating $A$, instead of running it directly, and maintaining a log of all changes made to $A$. The total time needed to unwind the state of $A$ to time $t_1$ should be $O(t_2 - t_1)$, possibly with some logarithmic factors

I have a few questions about this ---

(1) Does this principle have a name?

(2) Do I have to pay logarithmic factors for simulating $A$ instead of running it? I would like to avoid this if possible. Is there a model of computation, such as the RAM model, that avoids this? Or are there some regularity conditions?

Thanks!

EDIT: Some search of the literature shows that this is called the "rollback method". It seems to be a folk theorem that the RAM model supports linear-time rollback. I am a little surprised that there is nothing proved formally and no papers cited, as (for example) the Turing Machine model requires a logarithmic slowdown.


texts:
Consider a cloud-based accounting system that needs access to aggregate information such as an account's balance but doesn't need access to individual transaction amounts in a ledger.

Does there exist a homomorphic encryption scheme that allows a public observer (such as a cloud computing provider) to compute the plaintext sum of a set of encrypted unsigned integers without being able to decode any individual transaction value (n=1 notwithstanding)?

As another example, regulations exist to ensure capital reserves. An institution could use such a scheme to furnish proof of compliance without disclosing individual transactions.


texts: What is the fastest way to check for set inclusion?

texts:
Given $n$ subsets $S_1,\ldots,S_n$ of $\{1,\ldots,d\}$.

Check whether there are sets $S_i,S_j$ with $S_i \subsetneq S_j$. (If so, find an example, if not, simply say "no")

The trivial solution to this problem goes through all pairs of sets and checks inclusion for a pair in time $O(d)$, so the overall runtime is $O(n^2 d)$. Can this problem be solved faster? Is there a name for it in the literature?


texts: Heuristics for tsp without triangle inequality

texts:
Every heuristic for the traveling salesman problem that I know of (Nearest-Neighbour, Christofides, Held-Karp, ...) assumes that the triangle inequality holds.

Are there heuristics to solve the tsp that don't assume the triangle inequality and still perform well*?
If there aren't, why is that?

*i.e. don't run for a year for 100 cities and get relatively close to the optimum


texts: Is there a list of forbidden subgraphs for comparability graphs?

texts:
The "graph classes: a survey" mentioned Trotter and other authors have presented a list of forbidden subgraph of comparability graph. But the google book( where I read graph classes: a survey) do not have the page which contains the reference of specific literature.
To my knowledge, one forbidden graph is "a k-cycle ( k is an odd intege $\ge$ 5) and no triangle chord".

Thank you for your help in advance. :-)


texts:
I have heard of models of computation where you have a Turing machine, but instead of symbols over a finite alphabet you have elements from some tau-structure, and write instructions are replaced with functions $f \in \tau$ which are applied to the symbols of the tape following the head and the result is stored in the heads current position and read instructions are replaced with the evaluation of some formula $\phi$ on the symbols following the head, allowing you to take different actions based on the result of this "read".

Recently, I have been very interested in this idea, but whenever I try searching it I only get results for descriptive complexity theory, which is not at all what I'm looking for. Does anyone have any references about these machines and what they are called?


texts: One kind of dependence relation between a pair of random variables

texts:
I have been working on privacy and come across a neat problem.

Suppose two random variables $X$ and $Y$, over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$, are given with joint distribution $P_{XY}$.

We want to make sure that there exists a non-degenerate function acting on $\mathcal{Y}$, say, $f(Y)$, such that $f(Y)$ is independent of $X$.

I am looking for a sufficient and necessary condition of this.

It is clear that a necessary condition for this is that $P_{XY}$ be rank deficient.

I am, in particular, hoping to see if there is any connection to the set of singular values of  the conditional expectation operator (like the connection between maximal correlation and the second largest singular value of conditional expectation operator).


texts: Does anyone know where do the names System "F" and System "T" comes from? I am not asking who introduced those names (Girard System F, and Gödel System T), but what the "F" and the "T" means.


texts:
(1) $PP$ contains problems like 'is perm(M)>k'. So what problems does $AWPP$ and $APP$ contain with respect to permanent?

(2) Since it is not known if $NP$ is in $AWPP$ or $APP$ is there a candidate problem in $NP$ not in $AWPP$ and outside $NP$ complete problems? Or does $NP\cap AWPP = NP\backslash NPC$?


texts: Enumerating set combinations in an order that maximises the number of previously unseen subsets

texts:
Consider a set $S=\{a,b,c,d,e,f,g,h,i,j,k\}$, $\left|S\right|=11$.

There are ${11 \choose 5} = 462$ combinations of $S$'s members of size $5$.

There are $462! \approx 1.419 × 10^{1032}$ possible ordering of those sets. All ordering are in $\Phi_0$.

For a given ordering, $\phi \in \Phi_0$, $x_i^\phi$ is the set placed at position $i$.

Initial $\Phi_0$ was defined, following ones are defined as

$$\Phi_i = \left\{\,\phi \in \Phi_{i-1} \mid \not\exists \phi^\prime \in \Phi_{i-1} , C\left(i,\phi^\prime\right) \gt C\left(i,\phi\right)\, \right\}$$

where $C\left(i,\phi\right)$ is number of subsets given by $x^\phi_i$ which have not already exist as a subset of previous $x^\phi$'s

$$C\left(i,\phi\right)=\left|2^{x^\phi_i} \setminus \bigcup_{\forall h<i}{2^{x^\phi_h}} \right|$$

I'm looking for ways to efficiently enumerate any one of the orderings that exists in $\Phi_{462}$.

Any suggestions, pointing towards relevant/potential useful algorithms or papers would be appreciated.


texts: The asymptotic behavior of a recurrence related to stable matchings

texts:
I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows:

$$a_1 = 1, a_2 = 2$$
$$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$

Apparently, Knuth was able to prove that the sequence grows at least like $2.28^n$. Unfortunately, any hint of the proof seems to be lost or never published, as all reference cite "personal communication". I'd like to know the rationale.

While I don't need to know the sequence exactly, lower order terms have some importance. For example, the difference between a growth rate of  $n^{\Omega(1)} c^n$ verses $c^n / n^{\Omega(1)}$ would be significant (although I think I have a proof sketch that the first case is impossible, it would be nice to check).
I'm also interested in the initial conditions $a_1=2, a_2=7$.

So far, I've mostly just tried playing around the with generating function of the sequence, but I haven't gotten anywhere. A reference for applying generating function techniques to recurrence problems involving squares etc. of previous terms would be appreciated! I'm not sure what other techniques would be useful.

Background: [1] introduced a family of stable marriage instances which provide the best known lower bounds for the maximum number of stable matchings possible for some problem instance. [2] is the first source I could find to mention the number $2.28$. [3] generalizes the family created in [1] somewhat but doesn't do better than $2.28^n$.

[1] Irving, Robert W., and Paul Leather. "The complexity of counting stable marriages." SIAM Journal on Computing 15.3 (1986): 655-667.

[2] Pittel, Boris. “On Likely Solutions of a Stable Marriage Problem.” The Annals of Applied Probability, vol. 2, no. 2, 1992, pp. 358–401. JSTOR, www.jstor.org/stable/2959755.

[3] Edward G Thurber. Concerning the maximum number of stable matchings in the stable marriage problem.Discrete Mathematics, 248(1-3):195–219, 2002.

Solution

I wrote up Professor Shor's solution here!


texts: Connections between Graph Isomorphism and Polynomial Equivalence

texts:
Are there any relations between Graph Isomorphism problem and Polynomial Equivalence problem?

In particular does a polynomial time solution to Graph Isomorphism problem provide any evidence towards derandomization of Polynomial Identity Testing?


texts: Is computational complexity of neural networks so old-fashioned?

texts:
I find that works on computational power and complexity of neural nets are all from 1980s/1990s or even earlier. Surveys and books are also from that time. Personally, I find problems in this field are of importance no matter in theory or application.

Why is there few people care about it now? Is it because open problems are almost solved or they are too hard to keep researchers moving on? Are there researches on this topic now?


texts:
Let $X_m=[m]=\{0,1,\dots,m-1\}$ and let $Y_m=[2m]\setminus [m]$.
Given is a complete bipartite graph $G_m$, with parts $X_m$ and $Y_m$ and edges $\{x,y\}$ for every $x\in X_m$ and $y\in Y_m$.
Alice and Bob are given subsets $A$ and $B$ of $[2m]$, with $|A|=a$ and $|B|=b$, and further these subsets are small relative to $m$, in the sense that $a < b \le m$.
For convenience, let $C = A\cup B$.
The parties must agree on a common pair of vertices $u\in X_m$ and $v\in Y_m$, that represent some edge of $G_m$ that is not in the subgraph induced by $C$, in other words so that either $u \not\in C$ or $v\not\in C$.

Is this game known, and is there a good lower bound on the amount of communication required?

The size condition guarantees that the decision version is trivial (Alice sends "YES" to Bob): since $|C|<2m$ there is always some vertex that is not held by either party, so it together with any vertex in the other part forms a non-edge of $G_m[C]$.
Since $a$ is small relative to $m$, Alice can send a description of $A$ to Bob using $\lceil\lg\binom{2m}{a}\rceil = O(a\lg m)$ bits.
Furthermore, Alice sending a random element from $X\setminus A$ and one from $Y\setminus A$ gives a randomized one-way protocol with vanishing error (at least in some parameter regimes) and cost $O(\lg m)$.
In contrast, a set disjointness lower bound applied to the complements of $A$ and $B$ would predict $\Omega(m)$ bits being required, contradicting the trivial upper bound, so a straightforward reduction from set disjointness does not work (of course, a less direct reduction might work).
The implicit description of edges seems to be introducing an ingredient that I do not recognise from the usual communication games.


texts: What separates easy global problems from hard global problems on graphs of bounded treewidth?

texts:
Plenty of hard graph problems are solvable in polynomial time on graphs of bounded treewidth. Indeed, textbooks typically use e.g. independet set as an example, which is a local problem. Roughly, a local problem is a problem whose solution can be verified by examining some small neighborhood of every vertex.

Interestingly, even problems (such as Hamiltonian path) of a global nature can still be solved efficiently for bounded treewidth graphs. For such problems, usual dynamic programming algorithms have to keep track of all the ways in which the solution can traverse the corresponding separator of the tree decomposition (see e.g. [1]). Randomized algorithms (based on so-called cut'n'count) were given in [1], and improved (even deterministic) algorithms were developed in [2].

I don't know if it's fair to say that many, but at least some global problems can be solved efficiently for graphs of bounded treewidth. So what about problems that remain hard on such graphs? I'm assuming they are also of a global nature, but what else? What separates these hard global problems from global problems that can be solved efficiently? For instance, how and why would known methods fail to give us efficient algorithms for them?

For example, one could consider the following problem(s):

  Edge precoloring extension Given a graph $G$ with some edges colored, decide if this coloring can be extended to a proper $k$-edge-coloring of the graph $G$.

Edge precoloring extension (and its list edge coloring variant) is NP-complete for bipartite series-parallel graphs [3] (such graphs have treewidth at most 2).

  Minimum sum edge coloring Given a graph $G=(V,E)$, find an edge-coloring $\chi : E \to \mathbb{N}$ such that if $e_1$ and $e_2$ have a common vertex, then $\chi(e_1) \neq \chi(e_2)$. The objective is to minimize $E'_\chi(E) = \sum_{e \in E} \chi(e)$, the sum of the coloring.

In other words, we have to assign positive integers to the edges of a graph such that adjacent edges receive different integers and the sum of the assigned numbers is minimal. This problem is NP-hard for partial 2-trees [4] (i.e. graphs of treewidth at most 2).

Other such hard problems include the edge-disjoint paths problem, the subgraph isomorphism problem, and the bandwidth problem (see e.g. [5] and the references therein). For problems that remain hard even on trees, see this question.

[1] Cygan, M., Nederlof, J., Pilipczuk, M., van Rooij, J. M., & Wojtaszczyk, J. O. (2011, October). Solving connectivity problems parameterized by treewidth in single exponential time. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on (pp. 150-159). IEEE.

[2] Bodlaender, H. L., Cygan, M., Kratsch, S., & Nederlof, J. (2013). Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In Automata, Languages, and Programming (pp. 196-207). Springer Berlin Heidelberg.

[3] Marx, D. (2005). NP‐completeness of list coloring and precoloring extension on the edges of planar graphs. Journal of Graph Theory, 49(4), 313-324.

[4] Marx, D. (2009). Complexity results for minimum sum edge coloring. Discrete Applied Mathematics, 157(5), 1034-1045.

[5] Nishizeki, T., Vygen, J., & Zhou, X. (2001). The edge-disjoint paths problem is NP-complete for series–parallel graphs. Discrete Applied Mathematics, 115(1), 177-186.


texts: Minimum vertex cover on k-regular graphs, for fixed k>2 NP-hard proof?

texts:
Good Evening!

I am aware that the minimum (cardinality) vertex cover problem on cubic graphs ($3$-regular) graphs is $NP$-hard.  Say positive integer $k>2$ is fixed. Has there been any computational complexity proof (aside from the $3$-regular result, note this would be $k=3$,) that shows the minimum (cardinality) vertex cover problem on $k$-regular graphs is $NP$-hard (e.g., $4$-regular)?  Since $k$ is fixed, you aren't guaranteed the cubic graph instances needed to show the classic result I mentioned above.

Note that this problem would be straightforward to see is $NP$-hard from the result I mentioned at the start if we were to state that this were for any regular graph (since $3$-regular is a special case), we don't get that when $k$ is fixed.

Does anybody know of any papers that address the computational complexity of minimum (cardinality) vertex cover on a $k$-regular graph, when $k$ is fixed/constant?  I have been having difficulties trying to find papers that address this (in the slew of documents that cover the classic result of minimum (cardinality) vertex cover on cubic graphs being $NP$-hard.)

Thank you so much!

EDIT (again): @R B gave a construction below!


texts: Complexity of Maximum Independent Set (or Vertex Cover) on disk packing graphs

texts: I'm interested in complexity results for Maximum Independent Set (or Vertex Cover) problem over the class of disk packing graphs. Having a set of disks we build a graph that has its vertices at the disk centers whereas its edge connects two vertices that correspond touching disks.


texts: Possible to do Complexity theory with only counting and Pigeonhole

texts: Most of the proofs in the book Computational complexity by Barak and Arora seem to be Pigeonhole in disguise. What are some places in Complexity theory where counting and Pigeonhole was insufficient or is it just Complexity theory as we know it today outside quantum Complexity theory and undecidability just some part of large scale of things inferable from counting and Pigeonhole and where does quantum complexity theory fit in (essentially I am asking what kind of structures have been applicable and essential or can we do away with structures completely and reduce complexity theory to counting and pigeonhole?)?


texts: Circuits computing functions of inputs smaller than $n$

texts:
The usual circuit complexity concerns circuits where circuit $C_n$ computes function $f_n$. I am interested in circuits such that $C_n$ can compute $f_i$ for all $i \leq n$. I am assuming that the first $\log n$ inputs specify the $i$.

Is anything known about this?


texts: Can we define a meaningful concept of exptime reductions (as opposed to polytime reductions) for classes like NEXP or NEEXP?

texts:
Typically we are only interested in polytime reductions as we are usually interested in showing a reduction from one NP-problem to another.

However, if we consider larger complexity classes such as NEXP or NEEXP, can we define a new type of reduction which gives the reduction more time.

I realise that we have the problem that if we allow an exptime reduction $EXP^A$ for some oracle A, then given an input $x$ to the machine, we can boost the input to the oracle A to have length $O(2^{|x|})$. This gives us too much power as if, for example A=NEXP, then allowing this essentially allows us to solve NEEXP problems.

However, can we define a more useful/valid reduction where we are only allowed to query the oracle with a $poly(|x|)$ input, or the input to the oracle is required to be in unary? Has this already been investigated somewhere in the literature?


texts: How is the VP=VNP question in char 2 different from other char? What is the current frontier in regards to this question?

texts: What are the caveats one should be aware of when pursuing VP=VNP question in char 2 compared to other char? What is the current frontier in regards to this question?


texts: Definition of Clique vertex and separator vertex

texts:
While converting a tree decomposition of graph to Normalized tree decomposition, the definitions of clique vertex and separator vertex are used in
Sequential and parallel algorithms for embedding problems on classes of partial k-trees
page: 8-9.
Can somebody help me out with the two definitions which are used there.


texts: Remove cycles from a stochastic comparison matrix, while doing the least amount of editing

texts:
Let $\mathcal P_n$ be the collection of all matrices $M \in [0, 1]^{n \times n}$ such that $M_{ij} + M_{ji} = 1$ for all $i, j \in [n]$. Such matrices are called comparison matrices. A comparison matrix $M \in \mathcal P_n$ is said to be strongly stochastically transitive (SST) if $M_{ik} \ge \max(M_{ij},M_{jk})$ whenever $i,j,k$ are distinct and  $\min(M_{ij},M_{jk}) \ge 1/2$. Let $\mathcal T_n \subseteq \mathcal P_n$ be the set of all SST. Given $M \in \mathcal T_n$, consider the following problem

Problem. Find $T^* \in \mathcal T_n$ such that $\Delta(M,T^*)$ is minimal, where $\Delta(M,T) := \|M-T\|_1 = 2\sum_{i < j} |M_{ij}-T_{ij}|$.

$\Delta(M,T^*)$ is just a measure of the amount of editing done on the input matrix $M$, in order to make it into an SST matrix.
Question
Is the above problem reducible to some standard problem in computer science which can be solved efficiently (i.e in time polynomial in $n$) at least apprimately, say an algorithm which returns $\widehat{T} \in \mathcal T_n$ such that $\Delta(M,\widehat{T}) \le (1+\epsilon)\Delta(M,T^*)$ ?


texts: Correctness proofs of classic Paxos and Fast Paxos

texts:
I am reading the "Fast Paxos" paper by Leslie Lamport and get stuck with the correctness proofs of both classic Paxos and Fast Paxos.

For consistency, the value $v$ picked by the coordinator in phase $2a$ in round $i$ should satisfy

  $CP(v,i):$ For any round $j < i$, no value other than $v$ has been or might yet be chosen in round $j$.

For classic Paxos, the proof (Page 8) is split into three cases: $k < j < i$, $j = k$, and $j < k$, where $k$ is largest round number in which some acceptor has reported to the coordinator by phase $1b$ message. I failed to understand the argument for the third case:

  Case $j < k$. We can assume by induction that property $CP$ held when acceptor $a_0$ voted for $v$ in round $k$. This implies that no value other than $v$ has been or might yet be chosen in round $j$.

My question is:

  Why can we assume that property $CP$ held when acceptor $a_0$ voted for $v$ in round $k$?

  It seems that we are using mathematical induction, therefore, what are the basis, inductive hypothesis, and inductive steps?

For Fast Paxos, the same argument (Page 18) goes on. It says,

  Case $j < k$. For any $v$ in $V$, no value other than $v$ has been or might yet be chosen in round $j$.

My question is:

  How is this obtained? In particular, why is "For any $v$ in $V$" here?

  In my opinion, the correctness proof of the case $j < k$ relies (recursively) on those of cases of $k < j < i$ and $j = k$.

  Therefore, how can we conclude the case $j < k$ without first proving $j = k$ completely (namely, missing the subcase of $j = k$ where $V$ contains more than one value)?


texts: A Lambda calculus for invertible (r-Turing computable) functions

texts:
I'm interested in the concept of "r-Turing completeness", as defined by Axelsen and Glück (2011). A system is r-Turing complete if it can compute the same set of functions as a reversible Turing machine, without producing any "garbage" data. This is the same as being able to compute every function that is both (a) computable, and (b) injective.

I would like to computationally explore the space of computable injective functions. In order to do this I'm looking for the "most minimal" reversible programming language --- something that can play the equivalent role for r-Turing computability that the lambda calculus plays for Turing computability.

I know that there are many reversible languages that people have developed and proven to be r-Turing complete. However, these are being developed with practical applications in mind, and so their authors concentrate on giving them expressive features rather than making them minimal.

Does anyone know if such a minimal invertible language has been described, or whether there is any research in such a direction? I'm fairly new to the literature on this topic, so I could easily have missed it. Alternatively, does anyone have any insight into how such a language could be created?

Below is a summary of what I'm looking for. I do not know whether it can be created by modifying the lambda calculus itself, or whether a completely different type of language would have to be used.

r-Turing complete language - computes all computable invertible functions, and can only computes invertible functions
Syntax and semantics as minimal as possible. (E.g. Lambda calculus has only function definitions and applications, and nothing else.) It isn't necessary for the syntax or semantics to be related to those of the lambda calculus, although they could be.
Program = data. That is, the programs operate on expressions rather than any other kind of data. This guarantees that a program's output can always be interpreted as a program. This probably implies that it has to be a functional rather than an imperative style of language.
There is some systematic way to convert a program into its inverse, which doesn't involve substantially more computation than that involved in actually performing the inverse computation. (Not all invertible languages have this property, but some do.)

I should emphasise that Axelsen and Glück's approach to reversible computing is quite different from the well-known approach due to Bennett, where an (in general non-invertible) program is made invertible by returning some information about the computation's history along with the output. r-Turing completeness is about being able to compute injective functions without any additional output. There are several things called variations of "reversible lambda calculus" that are reversible in Bennet's sense - those are not what I'm looking for.


texts:
The Isomorphism Conjecture of Berman and Hartmanis states that all $NP$-complete sets are polynomial time isomorphic to each other. This means that $NP$-complete problems are efficiently reducible to each other via polynomial time computable and invertible bijections. The conjecture implies $P\neq NP$.

The isomorphism conjecture implies an exponential lower bound on the density of $NP$-complete sets since Satisfiability problem is dense. I am wondering if it also implies an exponential lower bound on the density of witnesses for $NP$-complete set.

  Does the isomorphism conjecture imply exponential lower bounds on witnesses density? Does it imply that $NP$-complete problems can not be in $FewP$?

The best result I am aware of is the following:

If $P=UP$ and $NP=EXP$ then the isomorphism conjecture holds.

Density $D$ of a set $S$ refers to the number of strings of length less than $n$ in the language. A set $S$ is exponentially dense if its density is $D=\Omega(2^{n^\epsilon})$ for some $\epsilon \gt 0$ and for infinitely many $n$ and sparse if $D$= $O(poly(n))$.


texts: Alternating tree automata for arbitrary arity tree

texts:
Could alternating tree automata be used for recognizing set (language) of arbitrary-arity trees?

More specifically, as an example: let $\Sigma = \{a,b,c\}$ - labels for tree nodes. Trees from $T$ are of the form: from each node only one of the following children could appear: $\{a,b\},\{b\},\{c\}$.

I.e. tree will be of the form, smth like this ($e$ on picture is just root of the tree, indexes on labels are just features of drawing tool, they aren't related to the question):


texts: What NP-complete problems are expected not to have #P-hard counting problems?

texts:
Let $R(v_{\bullet}, w_{\bullet})$ be some $P$-time computable relation between two binary strings $v_{\bullet}$ and $w_{\bullet}$. $NP$ problems are problems of the form: Given $v_{\bullet}$, determine whether there exists an $w_{\bullet}$ so that $R(v_{\bullet}, w_{\bullet})$. The $\# P$ problems are problems of the form: Given $v_{\bullet}$, count the number of $w_{\bullet}$ satisfying $R(v_{\bullet}, w_{\bullet})$.

There are certainly examples of $R$ from which the counting problem is hard but the existence problem is not:  Determining whether a graph has a perfect matching is in $P$, but counting the perfect matchings is $\# P$-complete.

What are examples of relations $R$ for the existence problem is $NP$-complete but the counting problem is, subject to reasonable conjectures, not $\# P$-complete?


texts: Minor closed properties that are explicitly MSO expressible

texts:
Below, MSO denotes the monadic second order logic of graphs with vertex-set and edge-set quantifications.

Let $\mathcal{F}$ be a minor closed family of graphs. It follows from Robertson and Seymour's graph minor theory that $\mathcal{F}$ is characterized by a finite list $H_1,H_2,...,H_k$ of forbidden minors.
In other words, for each graph $G$, we have that $G$ belongs to $\mathcal{F}$ if and only if $G$ excludes all graphs $H_i$ as minors.

As a consequence of this fact, we have an MSO formula $\varphi_{\mathcal{F}}$ which is true on a graph $G$ if and only if $G\in \mathcal{F}$. For instance, planar graphs are characterized by the absence of the graphs $K_{3,3}$ and $K_5$ as minors, and therefore it is easy to write explicitly an MSO formula characterizing planar graphs.

The problem is that for many nice minor closed graph properties, the list of forbidden minors is unknown. So, while we know that an MSO formula characterizing that family of graphs exist, we may not know what this formula is.

On the other hand, it may be the case that one is able to come up with an explicit formula for a given property without using the graph minor theorem. My question is related to this possibility.

Question 1: Is there a minor closed family of graphs $\mathcal{F}$, such that the set of forbidden minors is not known, but some MSO formula $\varphi$ characterizing that set of graphs is known?

Question 2:  Is some explicit MSO formula $\varphi$ known to characterize some of the following properties?

Genus 1 (the graph is embeddable in a torus)  (see EDIT below)
Genus k for some fixed $k>1$   (see EDIT below)
k-outerplanarity for some fixed $k> 1$

I would appreciate any reference or thoughts on this matter. Please feel free to consider other minor closed properties, the list given above is only illustrative.

Obs: By explicit I do not mean necessarily small. It is enough to give an explicit argument or algorithm showing how to construct the formula characterizing the given property. Similarly, in the context of this question I consider a family of forbidden minors to be known if one has given an explicit algorithm constructing that family.

EDIT: I found a paper by Adler, Kreutzer, Grohe which constructs a formula characterizing graphs of genus $k$ with basis on the formula characterizing graphs of genus k-1. So this paper answers the first two items of Question 2. On the other hand this does not answer Question 1 because there is indeed an algorithm that constructs for each k, the family of forbidden minors characterizing graphs of genus k (See section 4.2). Therefore this family is "known" in the sense of the question.


texts: Turing Machines and Subroutine Simulation

texts:
I have been reading Wikipedia as an introduction to Turing machines. I found a reference to John Hopcroft and Jeffrey Ullman, (1979). Introduction to Automata Theory, Languages and Computation (1st ed.), with a note that it is difficult to read. I am working hard with Wikipedia, and fear I will be unable to understand Hopcort and Ullman.

I am curious about how a Turing machine simulates a subroutine. If I understand http://en.wikipedia.org/wiki/Post%E2%80%93Turing_machine correctly, a Turing machine stores the return address and jumps to the subroutine, and jumps back to exit the subroutine, as an IBM360, IBM3* series machine did using BL (branch and link). Of course, modern machines store the return address on a stack and call the subroutine, but the two are similar. Is my assumption about storing the return address and jumping to simulate a subroutine correct?

Furthermore, has anyone simulated a subroutine by adding a symbol to the Turing machine alphabet for each subroutine? Symbols not defined within the machine would merely default to calling/jumping to the address of the subroutine. This technique is not much different from the one described in the paragraph above. I ask, because a machine I once worked on, and SDS 930 had some undefined op-codes that could be used to call subroutines. (Scientific Data Systems (SDS) was purchased by Xerox and renamed XDS).


texts: Models of computation strictly between classical and quantum in terms of query complexity

texts:
It is well known quantum computers are strictly more powerful than their classical counterparts in terms of query complexity.

  Are there other models (natural or artificial) that are strictly between the quantum and classical in terms of query complexity?

The seperation can be on

specific problems: model X computes function $f$ with strictly more queries than quantum, but fewer queries than the lower bound on classic, or
different problems: model X computes function $f_1$ with strictly more queries than quantum, but computes function $f_2$ with fewer queries than classical.

In both cases, we want for every function $f$ to have $Q_2(f) \leq X(f) \leq R_2(f)$ to avoid examples that are hard to compare to quantum (like the certificate complexity of non-deterministic queries). Here $Q_2(f)$ (and $R_2(f)$) is the two-sided $1/3$-error quantum (and classical randomized) query complexity and the inequalities are within constant factors.


texts:
I'm wondering if someone can provide a good algorithm for the following problem.

If we take 3-SAT in conjunctive normal form, we can partition some or all of the variables (not the literals) into sets.  I'm interested in finding a collection of sets such that at least two of the variables in every 3-SAT clause are in the same set.  We can call this a 2-partitioning.

In order to really solve the problem I'm working on, I need to assign weights to the sets.  If there are $\alpha$ variables in a set, we assign the weight $2^\alpha$ to the set.  We can then total all of the weights of the sets.  For example, if we can find three sets that have sizes $\alpha_1, \alpha_2, \alpha_3$, then the total weight is $2^{\alpha_1} + 2^{\alpha_2} + 2^{\alpha_3}$.  I'm looking for an algorithm that finds a 2-partitioning in time/space less than the total weight.  So, how fast can we make this algorithm?

EXAMPLE 2-PARTITIONING

If we have the formula:

$$(\underbrace{x_1 \lor \neg x_2}_\text{set 1} \lor x_3) \land (\underbrace{\neg x_4 \lor x_5}_\text{set 2} \lor x_6) \land (\underbrace{\neg x_1 \lor \neg x_6}_\text{set 1} \lor \neg x_7)$$

We can create sets $\{x_1, x_2, x_6\}$ and $\{x_4, x_5\}$ so that at least two of the variables in each clause are part of the same set, as shown above.  The total weight is therefor $2^3 + 2^2 = 12$.


texts: Are Alice and Bob allowed to copy qubits in quantum communication complexity model?

texts:
In quantum communication complexity, we always assume that Alice and Bob have unlimited computational power and are still prove lower bounds such as the $\Omega(n)$ lower bounds of parity.

What happens if we assume that Alice and Bob can do something a quantum algorithm cannot do? One particular ability that I'm interested in is when they can copy qubits, i.e., Alice can send Bob a copy of her qubits and also keep a copy of that qubit sent to Bob. Do the lower bounds still hold in this model?

A particular result that I'm interested in is the lower bound in Razborov's paper "Quantum communication complexity of symmetric predicates".

Also, is this ability already included in the formal definition, e.g., as defined in Razborov's paper?

(As you can guess, my understanding in quantum algorithm is very limited. So, besides the full answers, I would appreciate any pointer to anything in the literature as well.)

Update: I realized after reading Artem Kaznatcheev's answer that the model I ask is too general so I　asked a new question here


texts:
I thought I would share this question as it might be interesting for other users here.

Assume that a function which is in a uniform class (like $NP$) is also in a small nonuniform class (like $AC^0/poly$, i.e. nonuniform $AC^0$), does this imply that the function is contained in a smaller uniform class (like $P$)? If the answer to this question is positive, what is the smallest uniform complexity class that contains $NP \cap AC^0/poly$? If negative, can we find an interesting natural counterexample?

  Is $AC^0/poly \cap NP$ contained in $P$?

Note: A friend has already partially answered my question offline, I will add his answer if he doesn't add it himself.

The question is my second attempt to formalize the following informal question:

  Can non-uniformity help us in computing natural uniform problems?

Related:

Is there a candidate for a natural problem in $P/poly−P$?


texts: L-reduction From Matrix-Tiling To Minimal Dominating Set in Unit Disk Graph

texts:
Recently I read this paper which was published in FOCS2007.

In section 4, just before Theorem 4.2, the author mentioned that the gadget construction of Minimum Dominating Set in UDG is similar to that of Maximal Independent Set. But it seemed a little bit difficult to find out the actual gadget construction for Minimal DS in UDG. Could you please give some more details about this construction?


texts: How to construct an $(n,m,k)$ ``separating set''?

texts:
This problem is probably known under some other name, if anyone has seen it before, a reference will be great.

Given $n,m,k$ (for $m,k\ll n$), a $(n,m,k)$ separating set is a set of $n$-sized binary vectors $V$ such that for every disjoint $S,S'\subset \{1,\ldots,n\}$, $|S|=m,|S'|=k$ there exists $v\in V: v_{|S}=0, v_{|S'}=1$.

That is, for every set of $m$ indices $S$ and a non-overlapping set of $k$ indices $S'$, there should be a vector whose $S$ entries are all zeros and his $S'$ entries are all ones.

The goal is to construct a small set $V$ with the above properties.

  Is this problem known? Are there known deterministic constructions of such $V$? What is the minimal size of such $V$? What about a lower bound?

It seems that it is easy to build $V$ randomly (which would yield $|V|=O(2^{m+k}(m+k)\log n)$ by choosing uniformly distributed i.i.d. vectors).

The $2$ at the base of the exponent can be improved if $m\neq k$ by setting each bit with probability $k/(m+k)$.

Is this an optimal construction?


texts: How do I choose a functional dictionary data structure?

texts:
I've read a bit about the following data structures:

Bagwell's Ideal Hash Tries
Larson's Dynamic hash tables
Red-Black trees
Patricia trees

...and I'm sure there are a lot of others out there.  I've seen very little in the way of what each one is better suited for, or why I would choose one over another.  So, here are a few questions along these lines:

What functional dictionary data structures are important to know about?
What are the pros and cons of these approaches?
When does it make sense to use a more imperative data structure?

Numbers 2 & 3 are the more important ones though.  :-)


texts:
The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a linear map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ such that for all $x, y \in S$:
$$(1-\epsilon)\|x-y\|_2 \leq \|f(x)-f(y)\|_2 \leq (1+\epsilon)\|x-y\|_2$$

I've been trying to prove that the inequality above is satisfied if $f$ is picked using
the Haar Transform as follows. Let D be a random $n\times n$ diagonal matrix with each diagonal element drawn uniformly and independently from $\{-1, 1\}$ (i.e. diagonal entries of $D$ are Rademacher random variables). Let $H$ be the standard $n\times n$ Haar matrix. Let finally $M$ be a random $k \times n$ binary matrix, such that each row $i$ has a single entry $M_{ij}$ equal to $1$ for $j$ picked uniformly at random from $\{1, \ldots, n\}$, and $M_{ij} = 0$ for all other $j$. In other words, $MH$ is equal to a random $k\times n$ matrix each of whose rows is a uniformly random row of $H$. Then the transform is defined as

$$
f(y) = MHDx
$$

When $f$ is picked as above, what is the probability that it satisfies the Johnson-Lindenstrauss condition for a fixed pair $x,y$ (when $f$ is given by a an appropriately scaled Gaussian matrix, the probability is $1 - \frac{1}{n^2}$)?


texts: Max network flow with arbitrary source / sink

texts:
I'm wondering: given a fixed graph G, if we're to calculate the max flow between the vertices s and t, how different is the problem to calculate the max flow between the vertices s' and t, or similarly, s and t' (on the same graph)?

I've just started reading a paper by Altner and Ergun -- Rapidly Solving an Online Sequence of Maximum Flow Problems -- where they discuss a method to efficiently recalculate the max flow of a graph given small pertubations in the topology of that graph (for example, deleting or adding an edge). They do this by using the results from the previous max flow as a 'warm start' to calculating the new max flow.

I'm wondering if there is a similar story for recalculating the max flow given a change in source or sink? That is, is it possible to 'warm start' a max flow problem when a different source or sink is chosen?

Any pointers at all would be most welcome :)


texts: Redundancy and Structure of computational problems

texts:
It is widely believed that some computational problems such as graph isomorphism can not be NP-complete because it does not possess enough structure or redundancy to be computationally hard (NP-hard). I'm interested in the different formal notions for structure of computational problems and redundancy measures.

What are the major results known about such formal notions for computational problems? A recent survey  of such notions would be very nice.

EDIT: Posted on MathOverflow


texts: Complexity classes for problems that can be solved only from the length of the input

texts:
A tally language is a language on an alphabet with only one symbol. One can define complexity classes for tally languages, such as $P_1$ (the tally languages that can be decided in polynomial time).

Consider the non-unary alphabet $A = \{0, 1\}$.
Say I have a language $L$ on $A$ such that there is a unary language $L_1$ on the singleton alphabet $\{1\}$ with $L = \{w \in A^* \mid 1^{|w|} \in L_1\}$. In other words, $L$ is the language of words on $A$ whose length (written as a string of $1$'s) is in $L_1$.

The language $L$ is not a tally language, because it is not on a unary alphabet. Intuitively, however, it's not very far from being one: it can be decided only from the length of the input, or in other words it is a tally language "up to remapping the alphabet". Is there a standard name for such a language?

Further, if I consider the class of all such languages on $A$, for tally languages that range in a given tally complexity class (say, $P_1$), is there a standard name for the resulting non-tally class?


texts: What is the best lower bound for the fault-tolerance threshold in quantum computing?

texts:
It is well established that there exists a noise threshold for quantum computation, such that below this threshold, the computation can be encoded in such a way that it yields the correct result with bounded probability (with at most polynomial computational overhead). This threshold depends on the encoding used and the exact nature of the noise, and it is the case that results from simulation often give thresholds much higher than what can be proved for adversarial noise models.

  So my question is simply what is the highest lower bound that has been
  proved for independent stochastic noise?

The noise model I am referring to is the one dealt with in quant-ph/0504218, where Aliferis, Gottesman and Preskill prove a lower bound $2.73 \times 10^{-5}$. Note, however, I do not care which type of encoding is used, and it need not be restricted to the code considered in that paper. The highest I'm aware of is $1.94 \times 10^{-4}$ due to Aliferis and Cross (quant-ph/0610063). Has this value been improved upon since then?


texts: Integer linear programming in logarithmic number of variables

texts: I read that integer linear programming is solvable in polynominal time if the number $n$ of variables is fixed, i.e. $n \in O(1)$. If the number of variables grows logarithmically, i.e. $n \in O(\log_2(N))$ for a given input of size $N$, is the problem still solvable in polynominal time or is this an open problem?


texts: Efficient asympotically universal predictors

texts:
A computable predictor is an algorithm $A$ computing a function $f_A : \{0,1\}^* \rightarrow \{0,1\}$. We regarding the function as providing a predicted continuation of a finite binary sequence. We define an infinite binary sequence $\alpha \in \{0,1\}^\omega$ to be comprehensible for $A$ when

$$\exists n > 0 \, \forall m > n \, f_A(\alpha_{<m})=\alpha_m$$

i.e. sufficiently late in the sequence, $A$ always predicts $\alpha$ correctly.

Obviously $\alpha$ can only be comprehensible when it's computable. It's also easy to see that for any computable predictor $A$, $\exists \alpha$ computable s.t. $\alpha$ is not comprehensible for $A$. For example, we can define $\alpha$ recursively by

$$\alpha_{n} := \lnot f_A(\alpha_{<n})$$

On the other hand, it is possible to define $p : \{0,1\}^* \rightarrow \{0,1\}$ uncomputable s.t. all computable sequences are comprehensible for $p$. For example, $p(x)$ can be defined to be $\alpha_{|x|}$ where $\alpha$ is the minimal Kolmogorov complexity infinite sequence satisfying $\alpha_{<|x|} = x$.

So, it is impossible to construct a universal computable predictor, but we can try to make it "approximately universal". Formally, an infinite sequence of computable predictors $\{A_n\}_{n \in \mathbb{N}}$ is called asymptotically universal when $\forall \alpha \in \{0,1\}^\omega$ computable $\exists n > 0 \, \forall m > n: \alpha$ is comprehensible for $A_m$. It is easy to construct an example of such a sequence. Namely, define $A_n(x)$ to be the following program: "Run the first $n$ programs producing infinite sequences by dovetailing. The first time one of those programs produces output $y$ s.t. $|y| = |x| + 1$ and $y_{<|x|} = x$, terminate and produce the output $y_{|x|}$. If all of the programs produced outputs of length > $|x|$ and neither satisfied the condition, terminate and produce the output $0$".

Suppose $A_n$ from the above example is a run on $\alpha \in \{0,1\}^\omega$ produced by an algorithm $B$. For $n >> 0$ the time of the computation of $A_n(\alpha_{<k})$ is bounded by $p(t(k), 2^{|B|})$ where $t$ is the time complexity of $B$ and $p$ is polynomial. That is:

$$\forall B \, \exists n \, \forall N > n \, \forall k: T(A_N(\alpha(B)_{<k})) < p(t(k), 2^{|B|})$$

It seems natural to ask whether this can be improved. Specifically, we define an asymptotically universal sequence of computable predictors $\{E_n\}_{n \in \mathbb{N}}$ to be efficient when the time of the computation $E_n(\alpha_{<k})$ as above can be bounded by $q(t(k),|B|)$ with $q$ polynomial, given $n >> 0$. The question is thus

  Is there an efficient asymptotically universal sequence of computable predictors?


texts: Bin Packing with uniform size constraints

texts:
Consider the following version of the Bin Packing problem:
We are given $k$ unit-size bins and $n$ items with sizes $\epsilon < a_i \le 1$ for $1 \le i \le n$. Is it possible to pack items in bins?

Here is two simple observations:

When $\epsilon \le \frac{1}{4}$, this problem is strongly NP hard by a reduction from the 3-partition problem (Garey and Johnson: SP15).
When $\epsilon \ge \frac{1}{3}$, this problem is in P: place each item with size greater than $\frac{1}{2}$ in a separate bin. Assign maximum number of items left to non-empty bins. Arbitrarily, pair items still unassigned. If the number of these pairs is not more than the number of empty bins, assign these pairs to empty bins. Otherwise, it's impossible to pack the items in $k$ bins. It's not hard to see that you can generalized this even to the case that $\frac{1}{3} \le a_i$.

Is there any complexity result for the case that $\frac{1}{4} < \epsilon < \frac{1}{3}$?


texts: Hardness of approximating |V|+(size of vertex cover)

texts: I know that UGC implies a hardness of 2 for vertex cover, but is there a way to have this hardness on instances where the size of the vertex cover is at least $(1-\epsilon)\frac{|V|}2$? More generally is anything known on the hardness of approximating $|V|+|\mbox{Minimum Vertex Cover}|$?


texts:
One of the most discussed questions on the site has been What it Would Mean to Disprove the Church-Turing Thesis.  This is partly because Dershowitz and Gurevich published a proof of the Church-Turing Thesis is the Bulletin of Symbolic Logic in 2008.  (I won't discuss that here, but for a link and extensive comments, please see the original question, or -- shameless self-promotion -- a blog entry I wrote.)

This question is about the Extended Church-Turing Thesis, which, as formulated by Ian Parberry, is:

  Time on all "reasonable" machine models is related by a polynomial.

Thanks to Giorgio Marinelli, I learned that one of the co-authors of the previous paper, Dershowitz, and a PhD student of his, Falkovich, have published a proof of the Extended Church-Turing Thesis, which just appeared at the workshop Developments of Computational Models 2011.

I just printed out the paper this morning, and I have skimmed it, nothing more.  The authors claim that Turing machines can simulate any sequential computational device with at most polynomial overhead.  Quantum computation and large-scale parallel computation are explicitly not covered.  My question relates to the following statement in the paper.

  We have shown -- as has been conjectured and is widely believed -- that every effective implementation, regardless of what data structures it uses, can be simulated by a Turing machine, with at most polynomial overhead in time complexity.

So, my question: is this really "widely believed," even in the case of "truly" sequential computation with no randomization?  What if things are random?  Quantum computing would be a likely counterexample, if in fact it can be instantiated, but are there possibilities "weaker" than quantum that would be counterexamples as well?


texts: Maximum weight non-overlapping paths in a DAG

texts:
Suppose we have a weighted DAG $G$. A $m$-path-tuple is defined as $(P_1, ..., P_m)$ in which $P_i$ is a path on the graph, and no $P_i$ and $P_j$ share any edges. In other words each edge of the graph belongs to at most one of these paths. Among these $m$-path-tuples, we want to find the one that has the maximum weight, i.e., sum of the weight of its edges are more than any other $m$-path-tuple.

A max-flow min-cost formulation:
We connect every vertex without incoming edge to source and every vertex without outgoing edge to sink. Also we set the capacity of every edge edge to 1, and then setting the capacity of the source to $m$. In the end we set the cost of each edge to $-w(e)$ and minimise the cost via a "max-flow-min-cost" method. The $capacity=1$ makes sure the paths won't have any edge in common, while minimising the cost would effectively maximise the total weight. The problem with this approach is that it introduces negative weights and therefore solving it is quite slow. I was wondering if is a better way to solve it given that it's a DAG and not any arbitrary graph.


texts: Probability of detecting a transmission error

texts:
I'm trying to calculate the probability that a random transmission error goes undetected.

The packet in question is being transmitted over a serial RS-232C interface using 8 data bits, even parity and 1 stop bit. The packet is transfered in ASCII and structured according to the following:

Frame header (1 character - ASCII STX)
Telegram ID (3 characters, limited set of valid ID's)
Data (0 to 64 characters depending on the Telegram ID)
Checksum (4 characters, hex representation of CCITT CRC16 of Telegram ID + data)
End of frame (1 charcter - ASCII ETX)

I've been trying to locate some papers etc, that describe the strength of the parity check as well as the CRC16 check but so far no luck.

In my own (pragmatic) mind, I've been thinking of something along the lines of:

Ptotal = Pparity * Pcrc * Pcontent

Pparity is the probability that an error is undetected by the RS-232C parity check
Pcrc is the probability the error is undetected by the CRC16 check
Pcontent is the probability that the error changes the content but is otherwise ok (syntax and semantics)

So what I'm asking for is help to calculate the Pparity and Pcrc.

I'm not necessarily looking for the exacts mathmatical models, but some more "at least better than" models.

Any help, hints, indicators, etc. are greatly appreciated.


texts: Help with the definition of clique percolation

texts:
So I can find the Wiki article okay, as I think I understand that this is a definition of a special community in a graph.  However their image in Fig. 1 confuses me from the description.

As I understand it, the definition of a clique percolation within a graph is:

You have a set of k-maximal cliques, which contain k nodes.
You are said to have k-adjacent cliques if each k-maximal cliques are connected by (k-1)-nodes.

So a graph that was (1)<-->(2)<-->(3) could be considered a community because it has 2 2-maximal cliques, [[1,2], [2,3]], and each of them are connected by 1 vertex.

Am I reading the Wiki correctly, because I feel like I'm missing something. Thanks for any help your able to lend.


texts:
A colleague asks the following question:

  Let $S_k$ denote the subsets of $n$ of size $k$. Is there an optimal
  and efficient encoding of these subsets ? Namely, is there an function
  $f$ from $[0,1]^{\log \binom{n}{k}}$ to $S_k$ that can be computed
  efficiently (ideally in linear time).


texts: Additive error in counting the number of 1's in a sliding window?

texts:
The setting is as follows:

We're given a stream of bits. At time $t$ you get to see bit $b_t$, and required to output $\widehat{s_t} \approx \Sigma_{i=0}^{N}b_{t-i}$ (i.e. approximately how many 1's appeared in the last $N$ bits).

This can easily be done in $O(1)$ time if $O(N)$ memory is allowed, but the interesting case is when only $m \ll N$ memory is allowed.

In their well cited paper, Datar et al. have given an algorithm for approximate counting of the number of 1's in a sliding window, computed over a stream of bits.

Their results include:

Every exact counting algorithm requires $\Omega(N)$ space.
$(1+\epsilon)$-multiplicative algorithm that requires $O(\epsilon^{-1} \cdot \log N \cdot \log {(N\epsilon)})$ space and runs in amortized $O(1)$ time ($O(\log N)$ worst case).
Every $(1+\epsilon)$-multiplicative algorithm requires $\Omega(\epsilon^{-1} \cdot \log^2{(N\epsilon)})$ space.

Now I think that if we relax the approximation requirement we can do much better - I have a simple algorithm which seems to (unless I'm missing something):

Gives a $N\cdot \epsilon$-additive factor approximation (i.e. $s_t - N\cdot \epsilon\leq \widehat{s_t} \leq s_t + N\cdot \epsilon$). (Notice that this result is weaker than the multiplicative approximation).
Requires only $O(\log(N\epsilon) + \epsilon^{-1})$ space and runs in $O(1)$ time worst case.

I'm not familiar with this field, and don't know what changed since 2002, so my questions are:

Has there been work on additive approximation of number of bits in a sliding window?

What is the current state of the art result for this problem?

Are there practical usages that require specifically the multiplicative factor that makes the additive factor not interesting?


texts: Independent iterations in Las Vegas algorithms

texts:
In [Randomized Algorithms, Motwani and Raghavan] book, it is stated that the method of independent iterations to reduce the error probability in Monte Carlo algorithms (amplification according to Wikipedia) has its analogy in Las vegas algorithms. The authors then cited the following references:

Alt, Helmut, et al. "A method for obtaining randomized algorithms with small tail probabilities." Algorithmica 16.4 (1996): 543-547.
Luby, Michael, Alistair Sinclair, and David Zuckerman. "Optimal speedup of Las Vegas algorithms." Information Processing Letters 47.4 (1993): 173-180.

These suggestions of the mentioned papers are a bet very generalized in my opinion. I am wondering - are there well-known algorithms that use the concepts introduced in the previous papers ?


texts:
Has anyone thought about the possibility of a programming language, and a compiler, such that the compiler can automatically do worst-case asymptotic analysis? The use case I have in mind is a programming language where I write code, and compile. The compiler tells me that my code runs in O(n^2) (for example). It does this by doing what the smart people who do algorithmic analysis do, possibly counting loops and so on.

Because of halting problem issues, and since one can have programs that work by dovetailing, for example Levin's algorithm for SAT that runs in polynomial time iff P=NP, I suspect that one may have to design the programming language to be sufficiently restrictive to allow something like this. Are there negative results, which rule out certain kinds of programming languages from having such compilers.
I would also be interested in systems that give not an exact asymptotic analysis, but an "interesting" upper bound.
I am specifically NOT interested in black box and statistical methods that sample from inputs of particular length, and find out how long the program takes. These methods are very interesting, but they are not what I'm looking for. I am interested in exact methods that may give approximate bounds.

I would be very grateful if someone could point me to some references on work in this direction.


texts: Complexity of real coefficients Linear Programs

texts:
I would like to know if there are known any polynomial time algorithms for deciding the feasibility of linear programs with real (not integers) coefficients.
I know that for linear programs with integer coefficients Khachyan first proved the existence of a polynomial algorithm which can decide feasibility in polynomial time, but his method relies on the ellipsoid algorithm, which he starts with a large sphere. The radius of the sphere depends on the coefficients of the problem and also relies on the fact that they are integers. Of course, since then many other polynomial algorithms have been discovered which improved the polynomial (running time) in one way or another, but has this fundamental problem been solved?
Moreover, I see on Wikipedia that "Does LP admit a polynomial-time algorithm in the real number (unit cost) model of computation?" is an open problem. What should I understand out of it?
My understanding:
I understand the following: real coefficients need an infinite number of bits (in general) to be represented. So, "unit cost" in order to simplify that  assumes that each real number is represented in "one unit", practically eliminating the memory limitation for representing the coefficients. Probably each floating point operation is also considered as a "unit" of something too ... (this is basically a BSS machine, or Real Random Access Machine ... please correct me if I am wrong)
The Khachyan's bound on the initial sphere (which initializes the ellipsoid) is based on the fact that the coefficients coding length ( $\approx$ number of bits) is finite. However, if we are now using coefficients with an "infinite" coding length, Khachyan's method is no longer applicable ... is it? This means that if the coefficients of the LP are allowed to be arbitrarily in $\mathbb{R}$ there is no known algorithm which guarantees a decision of the feasibility in a number of steps bounded above in a polynomial in the number of inequalities and space dimension, right? This means that for instance, if $\pi$ is a coefficient somewhere in LP, then there is no (known) algorithm which can solve the LP in P time, is it ?


texts: Converting Partial Weighted Max SAT to CIRCUIT SAT

texts:
I am interested in converting Partial Weighted Max SAT to SAT. I have been recommended to go through CIRCUIT SAT.

Partial Weighted Max SAT consists of a set of hard clauses and a set of weighted soft clauses. We seek an assignment which satisfies all hard clauses and achieves at least a weight of k from the soft clauses.

How would I encode this as a boolean combinational circuit?

I can see how I can easily encode the hard clauses. But how would I encode the soft clauses, and associate weights with them, and ensure that a weight of at least k is achieved by a satisfying assignment?

Thanks


texts: Fischer and Rabin's theorem (1974) for theories of "additive" structures

texts:
Fischer and Rabin's Super-Exponential Complexity of Presburger Arithmetic (1974) has the following theorem.

  (Theorem 12) Let $U$ be any class of additive structures, so if $A = (A, +) \in U$,
  then $+$ is a binary associative operation on $A$. Let Th($U$) be the set of sentences
  of $L$ valid in every structure of $U$. Assume $U$ has the property that, for every
  $k \in \mathbb N$, there is a structure $A_k = (A_k, +) \in U$ and an element $u \in A_k$ such that
  the elements $u, u + u, u + u + u, ... , k . u$ are distinct. Then the statement of
  Theorem 1 holds for Th($U$) with the lower bound $2^ {dn}$ for some $d > 0$.

The conclusion that Th($U$) is at least exponential time.  They don't provide a proof for this (they say they will in a subsequent paper, which I believe has never appeared), but they say that their proof for the theory of the real numbers can be adapted by using $ku$ as a representation for $k$.

Is there a more detailed exposition of a proof of this theorem?  The following points are not clear to me:

The exact hypothesis of this theorem is unclear to me.  On one hand, they say "additive", use the symbol $+$, and list commutative monoids or expansions thereof as examples after stating this theorem.  On the other hand, they do not explicitly say "commutative" or "abelian"; it may be sufficient to assume associativity if we are applying the operation to $u, u+u, \dots$ to represent natural numbers because commutativity is not an issue as long as these elements are concerned.
Presumably, one needs to say in the language $\{+\}$ that $u, \dots ku$ are distinct in order to use them as representation for natural numbers up to $k$.  One also needs very large $k$ to simulate Turing machines.  How can one ensure that $u$ has the desired property with a relatively short logical formula?


texts: Do there exist intermediate problems (in the sense of Ladner's Theorem) for FP vs. #P? I assume that something is known, because I read some papers concerned with FP/#P dichotomies. However, I couldn't find a reference.


texts:
Consider the following problem.
Input: An undirected graph $G=(V,E)$.
Output: A graph $H$ which is a minor of $G$ with the highest edge density among all minors of $G$, i.e., with the highest ratio $|E(H)|/|V(H)|$.

Has this problem been studied? Is it solvable in polynomial time or is it NP-hard? What if we consider restricted graph classes like classes with excluded minors?

If we ask for the densest subgraph instead, the problem is solvable in polynomial time. If we add an additional parameter $k$ and ask for the densest subgraph with $k$ vertices, the problem is NP-complete (this is an easy reduction from $k$-clique).


texts:
It is sometimes claimed that Ketan Mulmuley's Geometric Complexity Theory is the only plausible program for settling the open questions of complexity theory like P vs. NP question. There has been several positive commentaries from famous complexity theorists about the program. According to Mulmuley it will take a long time to achieve the desired results.  Entering the area is not easy for general complexity theorists and needs considerable efforts to get a handle on algebraic geometry and representation theory.

Why is GCT considered to be capable of settling P vs. NP? What is the value of the claim if it is expected to take more than 100 years to reach there? What are its advantages to other current approaches and those that may rise in the next 100 years?
What is the current state of the program?
What is the next target of the program?
Has there been any fundamental criticism of the program?

I would prefer answers that are understandable by a general complexity theorist with the minimum background from algebraic geometry and representation theory assumed.


texts: Graph encoding algorithms that you know of ?

texts:
Is there any compilation of graph encoding algorithms? I know about Prufer and Huffman encoding. But papers say, prufer is not good enough to represent Minimum Spanning Trees in the sense it may represent different MSTs with the same string.

Update: It would be a very good future reference if every one could mention the graph encoding algorithm they know of. You can also provide a link/url to a paper.

As a start:

Prufer Encoding
Huffman Encoding
Succinct Trees
Ultra-succinct Representation of Ordered Trees

Thanks


texts:
We say that a Boolean function $f: \{0,1\}^n \to \{0,1\}$ is a $k$-junta if $f$ has at most $k$ influencing variables.

Let $f: \{0,1\}^n \to \{0,1\}$ be a $2k$-junta. Denote the variables of $f$ by $x_1, x_2, \ldots, x_n$. Fix
$$S_1 = \left\{ x_1, x_2, \ldots, x_{\frac{n}{2}} \right\},\quad S_2 = \left\{ x_{\frac{n}{2} + 1}, x_{\frac{n}{2} + 2}, \ldots, x_n \right\}.$$
Clearly, there exists $S \in \{S_1, S_2\}$ such that $S$ contains at least $k$ of the influencing variables of $f$.

Now let $\epsilon > 0$, and assume that $f: \{0,1\}^n \to \{0,1\}$ is $\epsilon$-far from every $2k$-junta (i.e., one has to change a fraction of at least $\epsilon$ of the values of $f$ in order to make it a $2k$-junta). Can we make a "robust" version of the statement above? That is, is there a universal constant $c$, and a set $S \in \{S_1, S_2\}$ such that $f$ is $\frac{\epsilon}{c}$-far from every function that contains at most $k$ influencing variables in $S$?

Note: In the original formulation of the question, $c$ was fixed as $2$. Neal's example shows that such value of $c$ does not suffice. However, since in property testing we are usually not too concerned with constants, I relaxed the condition a bit.


texts:
It is well known that connecting NAND gates allows the construction of arbitrary circuits. Furthermore, a NAND gate can be represented as a digraph with four vertices (in order, the two inputs, the "core" of the gate, and the output) and adjacency matrix

$\begin{pmatrix}0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}$.

Gluing these together gives a bijective correspondence between a certain class of digraphs and circuits built from wires and NAND gates. With this in mind,

  is there a standard terminology for this correspondence/construction?
  Are there common references where it is discussed?

I am particularly interested in the extent to which topological features of the digraph (e.g., the non-trivial homotopy induced by flip-flops) can be or have been related to the computational features of the corresponding circuit.

NB. This was cross posted from MSE after two days.


texts:
Linear programming is, of course, nowadays very well understood. We have a lot of work that characterises the structure of feasible solutions, and the structure of optimal solutions. We have the strong duality, poly-time algorithms, etc.

But what is known about minimum maximal solutions of LPs? Or, equivalently, maximum minimal solutions?

(This is not really a research question, but maybe we can have something less technical for the holidays. I'm just being curious, and after some googling I got the feeling that I must be missing the right keywords. It feels like an obvious problem to study, but I only found some sporadic papers that mention the problem.)

To keep things simple, let's focus on packing and covering LPs. In a packing LP we are given a non-negative matrix $A$. A vector $x$ is feasible if $x \ge 0$ and $Ax \le 1$. We say that $x$ is maximal if it is feasible and we can't greedily increase any component. That is, if $y \ge 0$ and $y \ne 0$, then $x + y$ is not feasible. And finally, $x$ is a minimum maximal solution, if it minimises the objective function $\sum_i x_i$ among all maximal solutions.

(You can define a maximum minimal solution of a covering LP in an analogous manner.)

What does the space of minimum maximal solutions look like? How can we find such solutions? How difficult it is to find such solutions? How can we approximate such solutions? Who studies such things, and what is the right term for it?

These questions were originally motivated by edge dominating sets and minimum maximal matchings. It is well known (and fairly easy to see) that a minimum maximal matching is a minimum edge dominating set; conversely, given a minimum edge dominating set, it is easy to construct a minimum maximal matching.

So they are, in essence, the same problem. Both problems are NP-hard and APX-hard. There is a trivial 2-approximation algorithm: any maximal matching.

However, their "natural" LP relaxations look very different. If you take the edge dominating set problem and form a natural LP relaxation, you get a covering LP. However, if you take the problem of finding a minimum maximal matching and try to come up with an LP relaxation, then what do you get? Well, of course fractional matchings are feasible solutions of a packing LP; then maximal fractional matchings are maximal solutions of such LPs, and minimum maximal fractional matchings are therefore minimum maximal solutions of such LPs. :)


texts: Vertex isoperimetric number of a graph - NP-hard?

texts:
The vertex isoperimetric number of a graph $G=(V,E)$ is
$i_V(G) = \min\{\frac{|N(S)|}{|S|} : S \subseteq V, 1\le |S|\le \frac{|V|}{2}\}$.
Several academic papers state that the problem of computing the vertex isoperimetric number of a graph is NP-hard, without proof or reference.

Can you give a reference where the following problem is shown NP-complete: given a graph $G$ and a number $t$, the question is to decide whether $G$ has vertex isoperimetric number at most $t$?


texts: Confusion about a formal definition of PRAM consistency

texts:
I am reading the paper "Consistency in Non-Transactional Distributed Storage Systems" by Paolo Viotti and Marko Vukolić. The authors provide a comprehensive survey of various consistency semantics based on the notions of history, abstract execution, and the $vis$ (visibility) and $ar$ (arbitration) relations, following Burckhardt (book).

I have some difficulty in understanding the definition of PRAM consistency (wiki). Informally, PRAM requires all processes see memory writes from one process in the order they were issued from the process. Writes from different processes may be seen in a different order on different processes.

In this paper (page 10), the authors define PRAM consistency by requiring the visibility relation ($vis$) to be a superset of session order ($so$; aka, program order). Formally,
$$\text{PRAM} \triangleq so \subseteq vis.$$

Consider the history below, where $w(x)0$ denotes a write of $0$ to $x$ and $r(x)0$ a read of $0$ from $x$.

This history does not satisfy PRAM consistency, because the only serial view of process $p_1$ is $w(x)0, w(x)1, r(x)1, r(x)0$ which is invalid.

However, according to the definition above, $r(x)1$ can be justified by the serial view of $w(x)1, r(x)1$, since the visibility set of $r(x)1$ is $vis^{-1}(r(x)1) = \{w(x)1\}$. Similarly, $r(x)0$ can be justified by the serial view of $r(x)1, w(x)0, r(x)0$, since the visible set of $r(x)0$ is $vis^{-1}(r(x)0) = \{w(x)0, r(x)1\}$.

To make $w(x)1$ visible to $r(x)0$, we require $(vis;so) \subseteq vis$. Therefore, in my opinion, PRAM should be defined as
$$\text{PRAM} \triangleq so \subseteq vis \land (vis;so) \subseteq vis.$$
(By the way, I think the predicate $RVal(\mathcal{F})$ is also needed.)

What is wrong with my arguments above?


texts: Shortest path in DAG with path dependent arc costs

texts:
I've got the following problem

Consider a DAG $G=(V,E)$ with $V=[v_1,…,v_n]$, and edge-set $E=[e_1,…,e_m]$, with associated costs $c_1,…,c_m$. The problem is to find the shortest paths from an initial vertex $s$ to multiple targets $t_1,…,t_k$, taking into account these costs. A typical shortest path problem.

However, my problem is slightly different:
the costs $c_1,…,c_m$ depend on the previously traversed nodes
Is there an alternative to the brute-force solution: find all the simple paths between $s$ and $t$ and then select the one with the lowest cost?

Path can be compared.
Take as example the following graph:
Red arcs are "checkpoint arcs". All the sub-paths having a red arc as last one can be compared, so a local decision can be taken. Similarly, costs are reset after traversing such arcs: 22->23 has a different cost if the subpath includes the arc 11->22 or not.

EDIT 2:

Costs are related to two sequences: $P$ and $Q$, where $len(P)=N$ and $len(Q)=M$. In the aforementioned case $M=N=4$.
Each element of $P$ and $Q$ is a tuple $(t,p)$. The tuple ($t_i,p_i)$ is the ith tuple of the sequence. Tuples are constrained on $t$: $t_{i+1} > t_i$. There's no constraint on $p$.

Let $s_p$ a set of valid indices for the sequence $P$ and $s_qp$ a set of valid indices for the sequence $Q$. The cost $C(s_p,s_q)= C_t(s_p,s_q)+C_q(s_p,s_q)$ where $C_t = max(max(P[s_p][t]),max(Q[s_q][t])) - min(min(P[s_p][t]),min(Q[s_q][t]))$ and $C_p = max(max(P[s_p][p]),max(Q[s_q][p])) - min(min(P[s_p][p]),min(Q[s_q][p]))$

The cost $C(s_p,s_q)$ represents the "diameter" of the element obtained by merging the $s_p$th elements of $P$ and the $s_q$th elements of $Q$.

Each path in the graph builds different $s_p$ and $s_q$ sets.
For example, the path 00,11,22,33 has a cost $C_{tot} = C(0,0)+ C(1,1)+ C(2,2)+ C(3,3)$, while the path 00 - 01 - 12 - 22 - 33 has a cost $C_{tot} = C(0,[0,1])+ C([1,2],2)+ C(3,3)$


texts: Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices

texts:
What is the complexity of the following problem?

Input:

$H$ a Hamiltonian path in $K_n$
$R \subseteq [n]^2$ a subset of pairs of vertices
a positive integer $k$

Query: is there a matching $M$ such that
for every $(v,u) \in R$, $d_G(v,u) \leq k$?
(where $G = ([n], M\cup H)$)

I have been having a discussion with a friend about this problem.
My friend thinks the problem is in polynomial time.
I think it is NP-complete.


texts: For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles

texts:
I have asked the question at Math SE and at SO, but I can't seem to get the answer I want. So I paraphrase the question and it here.

In a planar graph $G$, one can easily find all the cycle basis by first finding the spanning tree ( any spanning tree would do), and then use the remaining edges to complete cycles. Given Vertex $V$, edge $E$, there are $C=E−V+1$ number of cycles ( Euler formula), and there are $C$ number of edges that are inside the graph, but not inside the spanning tree.

Now, there always exists a set of cycle basis such that each and every edge inside the $G$ is shared by at most 2 cycles. My question is, is there any algorithm that allows me to find such a set of cycle basis? The above procedure I outlined only guarantees to find a set of cycle basis, but doesn't guarantee that all the edges in the cycle basis is shared by at most two cycles.

One of the suggestion I got from Math SE is to use planar embedding algorithm to "guess" the most natural coordinates for each vertex ( so that the graph looks "nice" visually), and then construct the polygonal faces. But this is exceptionally long-winded. I believe that this problem can be tackled more simply without involving coordinates.


texts: Almost uniform sampling implies approximate counting

texts: I began studying papers about approximate counting and I keep seeing the above being quoted,  without further explanation. I suppose the procedure that yields the result is very well known and that is why. Can anyone give me roughly the idea if possible and secondly some references about it?


texts: On the stopping criterion of coordinate descent method

texts:
I am trying to implement the coordinate descent method to solve the dual of linear SVM problem, but blocked at the stopping criterion.

Consider the optimization problem
\begin{equation}
\min f(\mathbf{x})
\end{equation}
under the constraints $x_i\in C_i$ for $i=1,2,\ldots,m$ where $\mathbf{x}=(x_1,x_2,\ldots,x_m)$.

At iteration $k$ we perform $m$ inner iterations where the $i$-th inner iteration updates $x_i$ by solving:
$$x_i^{k+1} = \arg\min_{y} f(x_1^{k+1},x_2^{k+1},\ldots,x_{i-1}^{k+1},y,x_{i+1}^{k},\ldots,x_{m}^{k})$$
under the constraint $y\in C_i$.

My question is, what is the stopping criterion of this algorithm if we want to obtain an $\epsilon$-accurate solution $\mathbf{x}$, i.e. $f(\mathbf{x}) - f(\mathbf{x}^*) \le \epsilon$ where $\mathbf{x}^*$ is the true optimal solution? If it's too general then let's consider in particular the dual of linear SVM problem: $$\min f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^\top K \mathbf{x} - C\mathbf{1}^\top\mathbf{x},\quad \mbox{s.t. } 0\le x_i\le C \quad i=1,\ldots,m$$
where $K$ is a positive semi-definite matrix and $C$ is a positive constant.

For the moment I take $f(\mathbf{x}^k) - f(\mathbf{x}^{k+1})<\epsilon$ but $f(\mathbf{x}^k) - f(\mathbf{x}^{k+1})$ is only the lower bound of $f(\mathbf{x}^k) - f(\mathbf{x}^*)$.

Thank you in advance.


texts: Is the dual of a polyhedral embedding a polyhedral embedding?

texts:
A polyhedral embedding of a graph on a surface is an embedding without edge crossings such that all the faces are bounded by simple cycles, and any two faces share a common vertex, share a common edge, or do not intersect at all. Moreover, all the faces are disks.

Given a graph $G$ with a polyhedral embedding on a surface $S$, one can define a dual graph $G'$ embedded in the same surface $S$, by creating a vertex in $G'$ for each face of $G$, and adding an edge between two vertices of $G'$ for each edge that the corresponding two faces in $G$ share.

I have a feeling that this will be simple, but I don't know how to prove it, so here it goes anyways. Question: The dual embedding that one obtains for $G'$ is also polyhedral?


texts: hardness of constant approximation of largest matching set

texts:
We say that $H$ is a matching graph if it contains $2n$ vertices and only $n$ vertex-disjoint edges, i.e. $H$ only contains those $n$ edges and no more.

Given a graph $G=(V,E)$ a subset $U\subseteq V$ is called a matching set if the sub graph that is induced by $U$ is a matching graph.

Prove that approximating the problem of finding the largest matching set is $NP-Hard$ for any constant factor.

I tried reducing to it from the $IS$ problem. I know that it is $NP-Hard$ to approximate $IS$ for any constant factor. I thought of this reduction, given a graph $G=(V,E)$:

$1)$ Find $k=\max\limits_{\ v\in V} deg(v)$.

$2)$ Construct $k$ graphs exactly like $G$: $G_1(V_1,E_1),\dots,G_k(V_k,E_k)$. those graphs are exactly like $G$ but the vertices are signed by the index and so does the edges.

$3)$ Return $H=(\cup_{i} V_i,\cup E_i)$.

I wanted to say that:

If $m$ is the size of the maximal $IS$ in $G$, the size of the largest matching set in $H$ is: $k\ \cdot m$.

I failed doing so. Can someone help?


texts:
This is particularly pertinent to the CS culture, where competitive conferences are often the main publication unit, which are then (sometimes) followed by journal versions.

Suppose that a paper was published at a conference as version A, and say, 5 years later, in a journal as version B (with the same title and authors). Assume also that during those 5 years, additional relevant papers on the topic were published.

When doing literature review in the introduction of future papers, the author of A and B is faced with a dilemma. To accurately reflect the historical development, he wants to cite version A and then the papers that followed it. However, the paper he actually wants people to read and cite is version B -- since it's cleaner, expanded, improved, etc. He can cite both versions, but then it looks like he's trying to rack up citations.

Does the CS community have a set etiquette for dealing with this situation? Is there perhaps a bibtex format where a single bib-entry covers both versions? Something that conveys the point "published first in year Y at venue V [so precedence is established] and then expanded version appeared in year Y' at venue V' [so just go read that one]"?


texts: Given a CSL formula, how can we generate an automaton that accepts the formula?

texts: The problem is same as the title, given a Continous Stochastic Logic(CSL) formula how can we create a machine which accepts the formula? Any intuitive ideas or references will be appreciated.


texts: Is there a lower bound for the decisional Grover search problem?

texts:
What is known about the decisional version of the search problem? By decisional version of the search problem, I mean the problem in which you wish to determine whether there are $0$, or exactly $t$ values $x$ for which the black-box function $f$ takes the value $1$. Of course, this problem reduces to the traditional Grover search problem; just find an $x$ such that $f(x)=1$ or run the algorithm so many times as to have a good probability that such an $x$ does not exist. This can be done with $O(\sqrt{N/t})$ oracle queries to the oracle function. However, those two problems are not equivalent or at least I don't see how they could be.

Obviously if those two problems were equivalent, the $\Omega(\sqrt{N/t})$ lower bound for Grover search would translate into a lower bound for the decision version. Are there results of equivalence of the two problems or of lower bounds for the decision problem?


texts: Embedding a graph with specified edge lengths in d-dimensional space

texts:
Given any undirected edge-weighted graph (with weights > 0) and some dimension d, is there a way to assign positions in $\mathbb{R}^d$ to those vertices such that all of the edges between them have euclidean distance equal to their weights?

The resulting edges may be crossing, that is okay. I'm really interested in the decision problem of when it is or isn't possible but an efficient algorithm to do it when it is possible would also be nice.


texts: From Lasserre maps to pseudo-distributions

texts:
Let me define a ``Lasserre map of degree $d$" as a linear map $L : \mathbb{R}_n[x] \rightarrow \mathbb{R}$ i.e a real valued linear map on polynomials over $n$ variables with real coeffients. This is further expected to satisfy, $(1)$ $L(1) =1$ and $(2)$ as $L(P^2) \geq 0$ if $deg(P) \leq \frac{d}{2}$.

On the otherhand a "pseudo-distribution of degree $d$" is defined as a map $D : \{\pm 1\}^n \rightarrow \mathbb{R}$ such that $(1)$ $\sum_{x \in \{\pm 1\}^n } D(x) =1$ and $(2)$ $\sum_{x \in \{\pm 1\}^n } D(x) f(x) \geq 0 $ if $f$ can be written as a sum of squares of polynomials each of degree $\leq \frac{d}{2}$ i.e if $f \in SOS_{\leq d}$ (the cone of sum-of-squares of polynomials of degree at most $\frac{d}{2}$)

It is trivial to see that given a map $D$ of the later type we can always create a map of the first type by defining , $L(Q) := \sum_{x \in \{\pm 1\}^n } D(x) Q(x)$.

But does every map Lasserre map $L$ induce a pseudo-distribution $D$?
Can one think of this $\{\pm 1\}^n$ as $\mathbb{F}_2^n$ and then is there any meaning (or use!) to ask for a generalization to $\mathbb{F}_q^n$?


texts: Learning a discrete distribution in $\ell_r$ norm

texts:
Let $P=(p_1,\ldots,p_d)$ be a distribution on $[d]$. Given $n$ iid draws from $P$, we construct some empirical estimate
$\hat P_n=(\hat p_{n,1},\ldots,\hat p_{n,d})$. Let us define the $r$-risk
by
$$ J_n^r = \sum_{i=1}^d |p_i-\hat p_{n,i}|^r.
$$

It is known (see, e.g., Lemma 2.4 here)
that when $\hat P_n$ is the maximum likelihood (i.e., empirical frequency) estimator
and $r\ge2$,
we have
$\mathbb{E}[J_n^r]\le1/n$. In particular, the expected $r$-risk decays at a dimension-free rate.

It is also known that for $r=1$, the risk decays at a minimax rate of $\Theta(\sqrt{d/n})$.

Question: what is known for $1<r<2$?


texts: Are there perceptrons that maximize the average margin, rather than the minimum?

texts:
A perceptron is a linear classifier.    The standard method for training a perceptron involves maximizing the minimum margin.  That is, we are trying to find:

$x^* = \text{argmax}_{x\in \text{unit vectors}} \min_{i \in 1..n} A_i x $

where $x$ is a normal vector to the separating hyperplane, $A$ is the $n\times d$ matrix of input values, $n$ is the number of input data points, $d$ is their diminsion, and $A_i x$ is the dot product between $x$ and the $i$th data point.

My question is: has there been any work on perceptrons whose hyperplane maximizes the average margin?  That is,

$x'^* = \text{argmax}_{x\in \text{unit vectors}} \sum_{i \in 1..n} A_i x $

This is a much easier quantity to calculate because it does not require gradient descent.  The problem is that it is not guaranteed to find separating hyperplanes even when they do exist---the points with low margin aren't given enough weight to do this.


texts: P vs. NP via psuedo-random number generators

texts:
Possible Duplicate:
  P vs. NP and Pseudorandom Bit Generators

Hello again , and thank you all for making this website a great vehicle for knowledge exchange. So my question is , are you trying to tell me that all I have to do is design a psuedo-random number generator that puts out a random bit stream such that no analysis of the output bits can ever have any correlation at all to the imput bits(a one way function) and I can win a million dollars? You got to be kidding me , right? I have to say right off the bat that I know nothing about computer science but I do know a little bit about electronic design and I must confess that this does not seem to be that difficult. I will have a design for