texts: Does existence of a total $\mathsf{NP}$ search problem not solvable in polytime imply $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$?

texts:
It easy to see that if $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$ then there are total $\mathsf{NP}$ search problems which cannot be solved in polynomial time (create a total search problem by having both the witnesses for membership and the witnesses for nonmembership).

Is the converse also true, i.e.

  Does existence of a total $\mathsf{NP}$ search problem not solvable in polynomial time imply $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$?


texts: Collapsing of exptime and alternation bounded turing machine

texts:
This question was already asked on math overflow, but I did not find any answer to my question (or let say the answer was that up to the knowledge of those people, no answer were known)

Let C be a set of function (let say time-computable increasing function to avoid pathological cases).
Let's call $\Sigma_j\rm{TIME}(C)$ the class of languages decided by a Turing Machine beginning in existential state, alternating at most $j-1$ times and whose time is bounded by a function $f\in C$.

Let suppose that $\Sigma_j\rm{TIME}(C)=\Sigma_{j+1}\rm{TIME}(C)$ then, can we prove that $\forall k>j \Sigma_j\rm{TIME}(C)=\Sigma_k\rm{TIME}(C)$ ? Or at least, what are the condition over $C$ ?

It is true if $C$ is the class of polynomials because $C$ is then closed under composition. I would have expected it to be true for every polynomially closed set (for example for the exponential hierarchy, a class like $C=\{2^{2^{\dots^{2^{n^{O(1)}}}}}\}$ for a bounded tower of 2.)

I guess and hope that some things are known about it, but I was not able to find any reference, neither my adviser could.

There is at least one related result I can state, which is that if $\Sigma_j\rm{TIME}(\exp_2^c(n^{O(1)}))=\Sigma_k\rm{TIME}(\exp_2^c(n^{O(1)}))$ then $\Sigma_j\rm{TIME}(\exp_2^d(n^{O(1)}))=\Sigma_k\rm{TIME}(\exp_2^d(n^{O(1)}))$ for $d>c$ where $\exp_2^j(n)$ use the notation for tetration($\exp_2^d(n^{O(1)})=\{2^{2^{\dots^{2^{n^{O(1)}}}}}\}$ with $d$ "2"s).

In fact I have a more general result, but this give a good idea. If anything like this is already known, I would like to know the references.

An equivalent way to ask the question in a finite model theory setting, is:

Let HO$^{r,f}_j$ be the class of formula of order $r$ with free variable of order up to $f$ and with $j$ alternations of quantification of order $r$ beginning with an existential quantification.

If there exists $k>2$ such that HO$^{r,2}_j$=HO$^{r,f}_k$ then can we prove that  $\forall l>j$  HO$^{r,2}_j$=HO$^{r,2}_l$ ?


texts: About the ``recent" paper by Razborov in the Annals of Mathematics

texts:
Recently this paper on complexity theory was published at the Annals of Mathematics by Razborov, http://annals.math.princeton.edu/2015/181-2/p01. Curiously this seems to have been submitted to the journal 12 years ago!

I was wondering if by now this work has already gone into some textbook or has it gotten improved or if there are already pedagogic expositions available for this? It would be helpful to get such references if they exist!


texts: Is there any special property the resulting graph G' has?

texts: Undirected graph $G$ can be partitioned into several vertex blocks, each vertex pair $(u,v)$ has an edge if "$u$" and "$v$" are in the different blocks; no edge, otherwise. Question is: Suppose we have several such graphs $G_1,\ldots,G_n$, where a vertex $v_i$ may be in more than one $G_j$.  If we combine graphs $G_1,\ldots,G_n$ by taking the union of their edge sets to get a graph $G'$, as shown in the example below, what is the name of the resulting graph?


texts: Partition of a set of integers into subsets with prescribed sums

texts:
I saw this problem:

A non increasing sequence of positive integers $m_1,m_2,..., m_k$ is said to be n-realizable if the set $I_n=\{1,2,..., n\}$ can be partitioned into $k$ mutually disjoint subsets $S_1,S_2,...,S_k$ such that $\sum_{x\in S_i} x = m_i$ for each $1\leq i \leq k$.

in the paper "PARTITION OF A SET OF INTEGERS INTO SUBSETS WITH
PRESCRIBED SUMS", by Fu-Long Chen, Hung-Lin Fu, Yiju Wang and Jianqin Zhou

http://journal.taiwanmathsoc.org.tw/index.php/TJM/article/view/1028

They have solved the problem under certain constraints. But I can't find anything about its complexity in general. Does anyone know a reference about the complexity of this problem?
It reminds me of the bin-packing problem, or in some sense, it is similar to the subset sum problem. So, I guess it must be NP-complete in general?

More precisely, I like to prove the NP-completeness for the fixed value of $k$, for example, when $k = 3, 4, \ldots$?
In this case, it is very similar to bin-packing or knapsack problem, but as we want the equality it is different. Maybe there are variations of these problems that match my question?


texts:
I am searching for an algorithm to decompose a word with the following constraints:

Decompose the word $w$ such that the following value is minimized:
$\sum_{i=1}^{k} | w_i| + \sum_{i=1}^{k} \log(n_i)$
where $w=w_{i_1}w_{i_2}\ldots w_{i_l}$ is decomposed in words $w_{i_j} \in \{w_1,\ldots,w_k\}$ of length $|w_{i_j}|$ and $n_{i_j}$ is the number of  occurrences of the word $w_{i_j}$ in the word $w$.
Or alternatively decompose $w$ such that the value $\sum_{i=1}^{k} | w_i| + \sum_{i=1}^{k} n_i$ is minimized.

Does somebody know of any algorithm on how to do this?

Applications of this decomposition would be a compression of the word $w$.
After decomposing, one would sort the $w_i$ lexicographically and store the corresponding permutation plus one would store the $w_i$ and the $n_i$.

Example of the compression with one decomposition (possibly not optimal in the above sense):

$w = bc|a|bc|a|bc|a$

The permutation is given by $\sigma=(1,3,5,0,2,4)$. The Lehmer-Number (For a definition see "Factorial Number System" in Wikipedia) of the permutation is $l(\sigma)=187$
One would then store: $187;a:3;bc:3$
To decompress, one would compute the permutation from the Lehmer-Number $187$ and apply its inverse to $(a,a,a,bc,bc,bc)$.


texts: Minimize L2 norm by circular permutation

texts:
Imagine two lists $L$, $M$ of the same length $n$. How to find $j$ such that
$\sum_{i=1}^n(L[i]-M[i+j])^2$ is minimal, where the index $i+j$ is taken modulo $n$?

Of course one can take all the indices $j\in\{1, \dots, n\}$ and compute all the sums, but the goal is to find something faster.

The same question hold for matrices: If $A$, $B$ are two square matrices, how to minimize $f(a,b)=\sum_{i=1}^n\sum_{j=1}^n (A[i][j]-B[i+a][j+b])^2$ for $a,b\in\{1,\dots,n\}$, where indices are again taken modulo $n$?

Thanks a lot. I would like to apologize, if my question is a classic one, but I searched and I didn't find an answer.


texts: Examples where the uniqueness of the solution makes it easier to find

texts:
The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. That is, the solution, if any, is unique in this sense.
It is thought highly unlikely that all $\mathsf{UP}$-problems are in $\mathsf{P}$, because by the Valiant-Vazirani Theorem this would imply the collapse $\mathsf{NP}=\mathsf{RP}$.

On the other hand, no $\mathsf{UP}$-problem is known to be $\mathsf{NP}$-complete, which suggests that the unique solution requirement still somehow makes them easier.

  I am looking for examples, where  the uniqueness assumption leads to a faster algorithm.

For example, looking at graph problems, can a maximum clique in a graph be found faster (though possibly still in exponential time), if we know that the graph has a unique maximum clique? How about unique $k$-colorability, unique Hamiltonian path, unique minimum dominating set etc.?

In general, we can define a      unique-solution version of any $\mathsf{NP}$-complete problem, scaling them down to $\mathsf{UP}$. Is it known for any of them that adding the uniqueness assumption leads to a faster algorithm? (Allowing that it still remains exponential.)


texts: Is there a signature of a first-order language that characterize the class of regular languages?

texts:
A previous question on this site was about extending the first-order logic with logical constants (quantifiers, fixed-point operators, etc.) to obtain a logical characterization of the class of regular languages.

Alternatively, one could try to get a characterization by expanding the signature of the first-order language, i.e., by allowing new kind of atomic formulas.  For example, in Straubing's Finite Automata, Formal Logic and Circuit Complexity, first-order logic with arbitrary number predicates is considered, and it is shown that it characterize the circuit complexity class AC$^0$.  Can a similar thing be done to the class of regular languages?  Or is it known that this is simply impossible?


texts: Finding a minimum directed cut that splits a weakly connected bipartite graph into two such non-edgeless graphs

texts:
Consider a directed, weakly connected bipartite graph $G = (U, V, E)$ where $U$ and $V$ are sets comprising the nodes of $G$, and $E \subseteq U \times V$ is the set of edges. The task is to find a minimum directed cut, say $C \subseteq E$, such that the graph $G = (U, V, E - C)$ consists of two disconnected bipartite graphs each of which are (1) not edgeless, and (2) weakly connected. The cut $C$ is directed in the sense that all edges in $C$ originate from the same bipartite subgraph, and minimum in the sense that it has the lowest cardinality possible.

Is this problem studied? If so, what is the computational complexity of the best known algorithm that solves it? If not, original algorithm ideas are more than welcome!


texts:
I had an idea for a way of representing DAGs, it's very easy to explain:

Each node in the DAG is given an array of n integers. If it is possible to traverse from A to B then each of B's integers must be greater than each of A's respective integers.

For example the graph:

A o - > o C
    \
     ->
B o - > o D

Could be represented by:

A = [0,1]
B = [1,0]
C = [1,2]
D = [2,2]

I have a few questions:

Has such a representation been thought up before?
If no, would you help me to design an algorithm that generates the arrays of integers given a DAG?


texts: Is there a name for this property in set-valued analysis or combinatorics?

texts:
I asked this question a few days ago on MO, but I haven't received an answer. So I thought I would ask here. I have also added a relaxed version of the question here.

Let $F$ be a set-valued, finite-valued map from a set $X$ to subsets of $X$. Consider the following property: $|F(x)| \geq |F(y)|$ for all $x,y$ such that $y \in F(x)$.
I have defined this property myself in a specific context but I am not sure what name to give it. I would like to know if there is a standard name for this property or similar property in set-valued analysis, combinatorics or elsewhere. Any suggestions for names would also be appreciated.

As a relaxation, suppose $X$ is given by the disjoint union, $X = \bigcup_{i \in \mathbb{N}} X_i$ and assume that $F$ maps elements of $X_i$ to subsets of $X_{i+1}$ for any $i$. In this case one can think of elements of $X$ as nodes of a tree-like graph, where a parent node $x$ is joined to nodes $y \in F(x)$. There are no edges between nodes belonging to the same partition $X_i$. But a child could have multiple parents, so this graph is not necessarily a tree. The property $F$ here says that every child of a node has at most as many children as the node. Any suggestions for names here would also be helpful.

At first this property appears to be a kind of monotonicity, but I would like to resort to the name "monotone" only if I can't find something more suitable.


texts: What can the Haskell package category-extras be used for?

texts:
See here. Has anyone attempted to use this to verify category theoretic proofs? Given the relationship between categories and graphs, are there some applications with respect to graph algorithms? What other possible uses are there for this package and those associated with it?

I realize this is a broad, open-ended question, which may not be entirely appropriate for Stack Exchange. A better place to post this question could also be a helpful answer.


texts: What does 'gadget' mean in NP-hard reduction?

texts: This question may not be technical. As a non-native speaker and a TA for algorithm class, I always wondered what gadget means in 'clause gadget' or 'variable gadget'. The dictionary says a gadget is a machine or a device, but I'm not sure what colloquial meaning it has in the context of NP-complete proof.


texts: Approaching Number Theory conjectures through Graph Theory

texts:
i try to find if there was an attempt to prove any famous Number Theory conjectures like Goldbach conjecture or Twin Prime conjectures through Graph Theory.
I have in my mind something like the approach to Fermat Theorem by Andrew Wiles through the Taniyama-Shimura conjecture.
Is there something like that (succesfull or not) using Graph Theory to attack Number Theory?


texts:
For the following, $(w,x) >= (y,z)$ iff $w >= y$ and $x >= z$.

I have a list, $L$, of $k$ points with integer coordinates ranging from $0$ to $n-1$.  Each point has an associated set.  I would like a data structure that can perform the following:

$include(x,y,i)$ - include the element $i$ to all of the sets associated with a point $p$, where $p >= (x,y)$

$remove(x,y,i)$ - remove the element $i$ from all of the sets associated with a point $p$, where $p >= (x,y)$

$retrieve(x,y)$ - retrieve the set associated with point $p = (x,y)$

My intuition is telling me that $include$ and $remove$ should be possible in something like $\text{polylog}(k)$ and $retrieve$ should be possible in something like $\text{polylog}(k) \times (\text{size of set})$.  The 2-dimensional aspect of this is stumping me, however.

Motivation: this data structure could be very useful for quickly calculating edit distances for a data set I'm using at work.


texts: Dynamic all-pairs shortest paths - O(1) query

texts:
I'm trying to come up with an algorithm to solve all-pairs shortest paths (APSP) problem in dynamic directed planar graph with nonnegative real weights. Additionally:

My primary focus is to achieve lowest possible query time ($O(1)$ would be perfect), it's the most important thing for me, this operation will be done very often (of course the price will be increased memory consumption, but I'm fine with that),
Graph is fully dynamic - both edges & vertices can be added/deleted - it would be nice if I didn't have to recompute everything from scratch,
$|V| = 10000$ (approximately).

I've search the Internet and skimmed through lots of articles, but didn't find anything that matched perfectly my case.

Any help and/or links would be highly appreciated.


texts:
A problem P is said to be in APX if there exists some constant c > 0 such that a polynomial-time approximation algorithm exists for P with approximation factor 1 + c.

APX contains PTAS (seen by simply picking any constant c > 0) and P.

Is APX in NP? In particular, does the existence of a polynomial-time approximation algorithm for some approximation factor imply that the problem is in NP?


texts: A Combinatorial algorithm for trivalent graph isomorphism (except some small subclass)

texts:
I am currently working on the isomorphism of graphs, hyper-graphs. The graph isomorphism of graphs of degree at most three (trivalent) known to be in $P$. E.M Luks has given an algorithm for trivalent graph isomorphism, which is algebraic in nature.

  Question : Is there a known graph isomorphism algorithm for graphs of degree at most three other than E.M Luks algorithm? Is there exist a combinatorial algorithm for trivalent graph isomorphism?

I thought of using Weisfeiler-Lehman procedure, but it fails on regular graphs.

Edit : I will use $k$-Weisfeiler-Lehman procedure; it is going to fail on the very small class of graphs called iso-regular graphs, Now I will divide this class into two classes;bounded tree width and unbounded tree width. For bounded tree width we already have a polynomial time (FPT algorithm) algorithm, unbounded tree-width class can be further divided into two subclasses; planar and non-planar, for planar, we already have a combinatorial algorithm that runs in $O(n^2)$ time, Now we are left with non-planar unbounded tree width iso-regular graphs. One thing is that I am not able to come up with an example of a graph, which is  a non-planar unbounded tree width iso-regular graph of degree at most three.

$k$-iso-rgular graphs or $k$-tuple regular graphs :  Graphs in which the number of common neighbours of any k-tuple of a given isomorphism type is constant (for instance, strongly regular graphs are 2-isoregular).


texts: Complexity of a parametrized min-cost flow problem

texts:
Consider the following  min-cost flow variant:

Input:

a positively-weighted complete bipartite graph $G = (S, T, c)$ and extra vertices $s, t$
edges from $s$ to $S$ and from $T$ to $t$.
lower and upper capacity bounds $l_i, u_i$ on each edge $(s, s_i)$
flow values $g_i$ for each edge $(t_i, t)$ with the constraint that $\sum_i g_i = 1$

For any flow assignment $f$ on the edges $(s, s_i)$ (note that by flow conservation $\sum_i f_i = 1$), let $\text{cost}(f)$ be the cost of a min-cost flow satisfying the upper and lower bounds.

Problem:

  Find an $f$ satisfying all capacity constraints such that
  $\text{cost}(f)$ is maximized.


texts:
This is an extension of the classical secretary problem.
In the hiring game you have a set of candidates $\mathcal C=\{c_1,\ldots,c_N\}$, and order on how skilled each worker is.
W.l.o.g, we assume that $c_1$ is the most skilled, followed by $c_2$, etc.
The order in which the candidates interview is picked uniformly at random and it is (obviously) unknown to the employers.
Now suppose you have a market with 2 potential employers. In every round, a new candidate is interviewing for both companies (call them $A,B$). During the interview, both $A$ and $B$ observe the partial ordering of all of the past candidates, including the current interviewee.
The firms then (independently) decide whether to hire today's applicant.
Unfortunately for $B$, it can not compete financially with $A$'s offer, so if both extends an offer for a worker, $A$ gets preference.
Also, once a secretary signs, the company may not interview any further candidates and the competitor becomes aware of the  signing.
The goal of each company is to hire the better skilled candidate (as opposed to the classic problem, where a single company wishes to find the best secretary), as it is known that the company with the better secretary should be able to take over the market.

What is the optimal strategy as the big firm ($A$)?
What about the smaller company ($B$)?
If both companies play their equilibrium strategies, what is the probability $B$ gets the better worker?

In a related work, Kalai et al. discusses the symmetric version of this problem, where both companies have the same power of attracting candidates.
In this setting, the simple (symmetric) equilibrium is that you hire a secretary iff the chance of she being better than the remaining candidates is at least 50%.

How does this result changes in our setting?


texts: Rings and the set of all minimum s-t-cuts

texts:
Let $N$ be a flow network with nodes $V$ and edges $E$. For technical reasons, the source side of a minimum $s$-$t$ cut $(A,B)$ with $s \in A$ and $t \in B$ is defined as $A - \{s\}$. Now, let $\mathcal{R}(N)$ be the set of the source sides of all minimum $s$-$t$ cuts of $N$. $\mathcal{R}(N)$ is now a non-empty family of sets over the universe $E$. Due to submodularity, the intersection of two source sides and the union of two source sides yields the source side of a min-cut. As such, $\mathcal{R}(N)$ is a ring. Hence, for every network $N$, $\mathcal{R}(N)$ is a finite ring of sets.

By ring of sets, I refer to the definition of a non-empty family of sets closed under union and intersection. Hence, a ring of sets is commutative.

I wonder if the converse direction is true, that is if the following statement holds:

  For every ring of sets $\mathcal{R}$ over a finite universe $U$ there is a flow network $N$ with nodes $U$ such that $\mathcal{R}(N) = \mathcal{R}$.

I was unable to come up with a counter example, at the same time literature seems not to know this either. To me it seemed like a constructive proof could work where the family of sets is analyzed in order to determine whether the nodes of $U$ need to be parallel or in series.


texts: What is the complexity of this graph problem?

texts:
Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that

for any vertex $x\in A$ at least half of the neighbors of $x$ are also in $A$, and
the size of $A$ is minimum.

That is, we are looking for a cluster, in which at  least half of the neighborhood of every internal vertex stays internal. The mere existence of such a cluster is obvious, since the whole vertex set $V(G)$ always has property 1.
But how hard is it to find the smallest (nonempty) such cluster?

Is there a standard name for this problem? What is known about its complexity?


texts: Solid applications of category theory in TCS?

texts:
I've been learning a few bits of category theory. It certainly is a different way of looking at things. (Very rough summary for those who haven't seen it: category theory gives ways of expressing all kinds of mathematical behavior solely in terms of functional relationships between objects. For example, things like the Cartesian product of two sets are defined completely in terms of how other functions behave with it, not in terms of what elements are members of the set.)

I have some vague understanding that category theory is useful on the programming languages/logic (the "Theory B") side, and am wondering how much algorithms and complexity ("Theory A") could benefit. It might help me get off the ground though, if I know some solid applications of category theory in Theory B. (I am already implicitly assuming there are no applications in Theory A found so far, but if you have some of those, that's even better for me!)

By "solid application", I mean:

(1) The application depends so strongly on category theory that it's very difficult to achieve without using the machinery.

(2) The application invokes at least one non-trivial theorem of category theory (e.g. Yoneda's lemma).

It could well be that (1) implies (2), but I want to make sure these are "real" applications.

While I do have some "Theory B" background, it's been a while, so any de-jargonizing would be much appreciated.

(Depending on what kind of answers I get, I might turn this question into community wiki later. But I really want good applications with good explanations, so it seems a shame not to reward the answerer(s) with something.)


texts: Communication problems for which a deterministic direct-sum theorem is not known to hold

texts:
It is an old open problem whether a direct-sum theorem holds for deterministic communication complexity, that is, whether solving $t$ independent instances of a problem is $t$ times harder than solving a single instance. [FKNN95] showed the following results:

A negative result: There is partial function (due to [O90]) whose deterministic communication complexity is $\Theta(\log n)$, but computing it on $t$ independent instances has complexity $\Theta(t + \log t \cdot \log n)$.
A positive result: For every function $f$, if the deterministic communication complexity of $f$ is $c$ then the complexity of computing $f$ on $t$ independent instances is at least $\Omega(t \cdot (\sqrt{c} - \log n))$.

I am not aware of any other general positive results on the direct-sum problem. However, it seems that for specific problems that are usually considered in communication complexity, e.g. equality or disjointness, a direct-sum theorem is known to hold.

My question is, are there other examples of problems for which a deterministic communication complexity theorem is not known to hold, or even known not to hold (beside the function of [O90])?

References:

[FKNN95] Tomás Feder, Eyal Kushilevitz, Moni Naor, Noam Nisan: Amortized Communication Complexity. SIAM J. Comput. 24(4): 736-750 (1995)

[O90] Two Messages are Almost Optimal for Conveying Information. Alon Orlitsky. PODC, page 219-232. ACM, (1990)


texts: SERF-reducibility and subexponential algorithms

texts:
I have a question concerning the SERF-reducibility of Impagliazzo, Paturi and Zane and subexponential algorithms. The definition of SERF-reducibility gives the following:

  If $P_1$ is SERF-reducible to $P_2$ and there $O(2^{\varepsilon n})$ algorithm for $P_2$ for each $\varepsilon > 0$, then there is $O(2^{\varepsilon n})$ algorithm for $P_1$ for each $\varepsilon > 0$. (Hardness parameter for both problems is denoted by $n$.)

Some sources seem to imply that the following also holds:

  If $P_1$ is SERF-reducible to $P_2$ and there $O(2^{o(n)})$ algorithm for $A_2$, then there is $O(2^{o(n)})$ algorithm for $P_1$.

My question is, does this latter claim actually hold and if it does, is there a write-up of the proof somewhere?

As a background, I've been trying to understand the area around the Exponential Time Hypothesis. IPZ define subexponential problems as ones that have $O(2^{\varepsilon n})$ algorithm for each $\varepsilon > 0$, but this apparently is not sufficient in the light of the current knowledge to imply the existence of a subexponential algorithm for the problem. The same gap seems to be present in the SERF reducibility, but I am partially expecting that I am missing something here...


texts: Why is an even-odd split 'faster' for MergeSort?

texts:
MergeSort is a divide-and-conquer algorithm that divides the input into several parts and solves the parts recursively.
...There are several approaches for the split function. One way is to split down the middle. That approach has some nice properties, however, we'll focus on a method that's a little bit faster: even-odd split. The idea is to put every even-position element in one list, and every odd-position in another.

This is straight from my lecture notes. Why exactly is it the case that the even-odd split is faster than down the middle of the array?
I'm speculating it has something to do with the list being passed into MergeSort and having the quality of already sorted, but I'm not entirely sure.
Could anyone shed some light on this?


texts: Containment problem of an acyclic NFA in an NFA

texts:
Let $A$ and $B$ be NFAs, such that $A$ is acyclic.

In the general case, deciding whether $L(A)\subseteq L(B)$ is $PSPACE$-hard. However, since $A$ is acyclic, we know that for every $w \in L(A)$, it holds that $|w|$ is linear in $|A|$. It follows that if $L(A) \nsubseteq L(B)$, there must be a polynomial witness $w\in L(A)\setminus L(B)$. Thus, the containment problem when $A$ is acyclic is in $coNP$.

Can it be shown that it is $coNP$-hard?


texts: Expected minimum influence of a random Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$

texts:
For a Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$, the influence of the $i$th variable is defined as
$$
\operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus i})]
$$
where $x^{\oplus i}$ is the string obtained by flipping the $i$th bit of $x$. The minimum influence of $f$ is then $$\operatorname{MinInf}[f] \stackrel{\rm def}{=} \min_{i\in[n]}\operatorname{Inf}_i[f].$$

Given a parameter $p\in[0,1]$, we choose a $p$-random function $f$ by choosing its value on each of the $2^n$ inputs independently at random to be $1$ with probability $p$, and $-1$ with probability $1-p$. Then, it is easy to see that, for every $i\in[n]$
$$
\mathbb{E}_{f}[\operatorname{Inf}_i[f]] = 2p(1-p)
$$
and a fortiori
$$
I_n(p) \stackrel{\rm def}{=}\mathbb{E}_{f}[\operatorname{MinInf}[f]] \leq 2p(1-p).
$$

My question is:

  Is there an asymptotically (with regard to $n$) tight expression for $I_n(p)$? Even for $p=\frac{1}{2}$, can we get such an expression?

  Specifically, I do care about the low order terms, i.e. I'd be interested in an asymptotic equivalent for the quantity $2p(1-p)-I_n(p)$.

(The next question, but which is subordinate to the first, is whether one can also get good concentration bounds around this expectation.)

By Chernoff bounds one can  also show that each $\operatorname{Inf}_i[f]$ has good concentration, so that by a union bound we get (if I did not mess up too badly)
$$
 \frac{1}{2} - O\left(\sqrt{\frac{n}{2^n}}\right) \leq I_n\left(\frac{1}{2}\right) \leq \frac{1}{2}
$$
but this is most likely loose on the lower bound (due to the union bound) and definitely on the upper bound. (I am in particular looking for an upper bound strictly less than the trivial $\frac{1}{2}$).

Note that one of the issues in doing that, besides taking the minimum of $n$ identically distributed random variables (the influences), is that these random variables are not independent... although I do expect their correlation to decay "pretty fast" with $n$.

(For what it's worth, I have computed explicitly the first few $I_n(1/2)$'s up to $n=4$, and have run simulations to estimate the following ones, up to $n=20$ or so. Not sure how helpful this could be, but I can include that once I am back to my office.)


texts: Is Bayes optimal RL of a finite set of DFAs feasible?

texts:
Let $Q$ be a finite set of states, $\Sigma$ a finite alphabet, $q_0\in Q$ the start state and $F\subseteq Q$ the set of accepting sets. Let $\{\delta_k:Q\times\Sigma\rightarrow Q\}_{k=1}^n$ be a set of $n$ possible transition functions and $m$ a fixed natural number. Consider the following problem: find a word $w\in\Sigma^m$ s.t. the DFA accepts $w$ with maximal probability, assuming that the transition function is chosen randomly from a uniform distribution over the $\delta_k$, and that you are allowed to observe the state transitions resulting from $w_1\ldots w_k$ before choosing $w_{k+1}$ (but you don't know which transition function was chosen). In other words, we are doing one-shot reinforcement learning for a deterministic MDP where $\Sigma$ is the set of actions, and the reward is $1$ if we end up in $F$ after $m$ actions and $0$ otherwise.

Given a policy $\pi: (\Sigma \times Q)^{< m} \rightarrow \Sigma$ (that decides which action to take after observing a given history), and some choice of $\delta_k$, we get a particular history $h_{\pi,k}\in(\Sigma\times Q)^{m}$. In fact, the collection of the $h_{\pi,k}$ for $k$ from $1$ to $n$ gives us a compact description of $\pi$: in order to implement $\pi$, we just need to look at the current history $h\in(\Sigma \times Q)^{< m}$ and find $k$ s.t. $h$ is a prefix of $h_{\pi,k}$ to know what action to take next. This description is of size $O(nm|\Sigma||Q|)$, as opposed to a lookup table for $\pi$ which would be of size exponential in $m$. In particular, an optimal policy (i.e. a policy which maximizes the probability of the DFA accepting) also has such a compact description.

Is it possible to find a compact description (as above) of an optimal policy in time polynomial in the size of the problem and $m$?

Here I'm assuming that the $\delta_k$ are given explicitly as lookup tables, and $F$ as a list of states (where states and actions are represented by numbers). For a negative answer, you can assume any standard complexity-theory conjecture.


texts:
Please, correct my terminology as I am not a combinatorician
(I am using http://en.wikipedia.org/wiki/Partial_permutation). Please, refer me to the solution if this is a solved problem.

Let $P_k$ be partial permutations of the set $\{1, 2, \ldots, n\}$, e.g. $n=5$, $P_1=(1,\cdot,3,2,\cdot)$, and $P_2=(\cdot,2,3,1,5)$. Let $T_k$ be permutations from the same set, e.g. $T_1=(1,3,4,2,5)$.  I will write $P_1[4]=2$, $P_2[4]=1$, and $T_1[4]=2$.  I will say, that $P_1[2]$, $P_1[5]$, and $P_2[1]$ do not exist.

Let define that a given partial permutation $P$ is included in the given permutation $T$ if for all $i,j$ for which $P[i]$ and $P[j]$ exist: if $P[i] < P[j]$ then $T[i] < T[j]$. For example, the given $P_1$ and $P_2$ are both included in the given $T_1$.

Let define that two given partial permutations are compatible if there exists a permutation such that both partial permutations are included in it. For example, the given $P_1$ and $P_2$ are compatible, because they are both included in $T_1$.

QUESTION: Propose an algorithm to check if two given partial permutations are compatible. Please propose also the proper data structure for representing partial orders which will allow your (efficient) algorithm.

(I am tagging this question with BDD because the solution may help me to represent BDDs with different variable ordering more concisely)


texts: Why can MIP be restricted to just two provers?

texts: In several places I see it referred to that the MIP class can be assumed to be two interactive provers that don't communicate with each other, rather than any polynomial number of provers. Why are these classes equivalent? Is there a way to take an algorithm for proving membership with k provers, and turn that into an algorithm that works with only 2 provers, with blowup polynomial in k?


texts: Stacks serving interval storage requests

texts:
An interval storage request is represented by a tuple $(s,t,v)$ satisfying $s<t$, meaning that the value $v$ needs to be stored from time $s$ to time $t$. A stack serves the request $(s,t,v)$ in the following natural way: at time $s$, it push an entry with content $v$ into the stack, and pop it out at time $t$. Note that a stack can only pop out its top entry. This implies that a single stack cannot serve two requests $(s_1,t_1,v_1)$, $(s_2,t_2,v_2)$ where $s_1<s_2<t_1<t_2$, since at time $t_1$, the top entry of the stack is $v_2$ rather than $v_1$. However, with two stacks we can serve both requests easily.

The question is: given a set of interval storage requests and capacitated machines, what is the largest subset (in cardinality) of the requests such that we can find a way to serve them using the given stacks (when a request come, we can decide which stack to push it in)?

The formal statement of the problem is the following. We say two intervals $[s_i,t_i]$ and $[s_j,t_j]$ cross if $s_1<s_2<t_1<t_2$ or $s_2<s_1<t_2<t_1$.

Given intervals $I=\{[s_i,t_i]\}_{i\in [n]}$ (assume all endpoints are different integers in $[2n]$), together with integer $T$ and $\{m_t\}_{t\in [T]}$, find a collection of disjoint subsets $J_1,\cdots, J_T\subseteq [n]$  with the largest sum of cardinalities $|J_1|+\cdots+|J_T|$ such that:

(i) (no crossing) for any $t\in [T]$, no two intervals in $I_{J_t}=\{[s_i,t_i]\mid i\in J_t\}$ cross;

(ii) (capacity constraint) for any $t\in [T]$, there is no integer $k\in [2n]$ such that $k$ is contained in at least $m_t+1$ intervals in $I_{J_t}$.

The case $T=1$ is easy. Some other interesting special cases include:

(a) $\forall i\in [T], m_i=\infty.$ Namely, there is no capacity constraint.

(b) Determine whether or not all requests can be served.

I wonder if this problem (or any of the above special cases) was studied before? Any previous results or new ideas are appreciated.


texts: NP-complete problem with polynomially many certificates?

texts:
Let's call a language $L \in$ NP sparsely certificated if and only if:

There exists a polynomial $p : \mathbb{N} \rightarrow \mathbb{N}$ such that for every input $x \in \Sigma^*$ of size $n$, if $x \in L$ then the set $U_x$ of certificates $u$ which verify that $x \in L$ is polynomially sized, i.e. $|U_x| \leq p(n)$.

In shorter terms, every input $x$ has at a most polynomial amount of certificates which verify its inclusion in $L$.

Example: To illustrate, consider the $\mathbf{CLIQUE}$ problem:

$\mathbf{CLIQUE} = \{\; (G,k) \;\mid\; G \text{ has a clique of size } k \;\}$

The language $\mathbf{CLIQUE}$ is not sparsely certificated, as an input $x = (G,k)$ could easily have an exponential amount of $k$-cliques acting as certificates which prove that $x \in \mathbf{CLIQUE}$.

End Example

The question, then, is: are there any known NP-complete sparsely certificated languages? Any insights are welcome, even if they don't answer the question!

Note: this definition is different from that of a sparse language!


texts: Exact version of matroid, given the input weight is in unary.

texts:
Is the following problem in P?

We are given a matroid M. Each element in M has a weight encoded using some unary notation.
We are also give an integer K also encoded in unary bits.
The question is whether there is a base of M that has weight EXACTLY K.

I know the exact spanning tree is in P.

Thanks a lot.


texts:
Not sure how to phrase this really, but here goes.

Suppose you are given $k$ simple graphs, each having exactly $m$ edges. The edges in each graph are labeled from 1 to $m$.

The problem is to find the maximum subset of edges $M \subseteq \{1, 2, ..., m\}$ you can choose, so that $M$ forms a forest in each of the $k$ graphs.

For $k = 1$ this is trivial, but starting from $k = 2$ the problem seems to be harder.

Has this problem been studied extensively?

The problem I am interested in is actually a generalization of the above, where there can be multiple edges between two vertices. (kind of like a weighted version, in some sense)


texts: Computing the approximate population of a bloom filter

texts:
Given a bloom filter of size N-bits and K hash functions, of which M-bits (where M <= N) of the filter are set.

Is it possible to approximate the number of elements inserted into the bloom filter?

Simple Example

I've been mulling over the following example, assuming a BF of 100-bits and 5 hash functions where 10-bits are set...

Best case scenario: Assuming the hash functions are really perfect and uniquely map a bit for some X number of values, then given 10-bits have been set we can say that there has only been 2 elements inserted into the BF

Worst case scenario: Assuming the hash functions are bad and consistently map to the same bit (yet unique amongst each other), then we can say 10 elements have been inserted into the BF

The range seems to be [2,10] where abouts in this range is probably determined by the false-positive probability of filter - I'm stuck at this point.


texts: Model-checking for three-variable logics and restricted structures

texts:
Denote the $k$-variable fragment of logic $L$ by $L^{(k)}$.  The model-checking problem for a logic $L$ with respect to a class of structures $C$, denoted $MC(L,C)$, is the decision problem

  $MC(L,C)$
  Input: formula $\phi$ of $L$, structure $S$ from $C$
  Question: does $S$ satisfy $\phi$?

Is there a logic $L$, with associated class of structures $C$, and a subclass $D$ of $C$, such that
1. $MC(L^{(3)},D)$ is "easy",
2. $MC(L,D)$ is "hard", and
3. $MC(L^{(3)},C)$ is "hard"?

With "easy" vs. "hard" I mean decidable vs. undecidable, PTIME vs. NP-hard, LogCFL vs. P-complete, or similar dichotomies.

Motivation

For many logics the three-variable fragment is enough to express "hard" properties (this is true for MSO and FO over ordered structures).  So results about undecidability often carry across from the logic to its three-variable fragment.  There is also often a way to reduce the arity of predicates used in formulas efficiently (for instance, SAT can be reduced to 3SAT with a linear increase in formula size).  Reducing arity facilitates expressing some formulas with fewer variables.

On the other hand, there exist logics which are "easy" for some classes of structures yet "hard" in general.  For instance, the model-checking problem for MSO is "easy" (linear time) on unordered graphs satisfying the property "has treewidth less than $k$" for any fixed $k$, but "hard" (NP-complete) on unordered graphs in general.

I am asking whether there are any known examples where the restriction to 3 variables interacts with the property defining the subclass $D$ in an essential way to yield tractability, yet where neither of these restrictions on their own is enough.

Apologies for the vagueness of the question: I am trying to leave this general because I can't think of any examples.  As soon as I restrict $D$ enough to ensure condition 1 holds, condition 2 seems to break.  I suspect there are some unnatural classes which would work, but ideally $D$ should be "nice", at least hereditary and closed under isomorphism.  As a further non-example, model-checking for FO is PSPACE-complete while model-checking for $FO^{(3)}$ is PTIME-complete; here the restriction to a finite number of variables is already enough to ensure an "easy" model-checking problem and condition 3 fails.

Definitions for completeness: FO is first-order logic, MSO is monadic second-order logic, where quantification over sets of individuals is allowed, as well as quantification over individuals.


texts: Upper bounds on the length of longest simple path in non-Hamiltonian graph?

texts:
Hamiltonian cycle problem is $NP$-complete on cubic planar bipartite graphs. I'm interested in upper bounds on the length of the longest simple path in non-Hamiltonian cubic planar bipartite graphs.

  What is the best known upper bound on the length of longest simple path in non-Hamiltonian cubic planar bipartite graphs?

Edit: Also, I am interested in non-trivial lower bounds on the length of the longest simple path in this class of graphs.


texts:
ST-Connectivity is the problem of determining whether there exists a directed path between two distinguished vertices $s$ and $t$ in a directed graph $G(V,E)$. Whether this problem can be solved in logspace, is a long-standing open problem. This is called the $NL$ vs $L$ problem.

  What is the complexity of ST-Connectivity, when the underlying undirected graph of $G$ has bounded treewidth.

Is it known to be NL-hard ? Is there a $o({\log}^2n)$ upper bound known ?


texts:
A common scenario is that one has a well-ordered universe, and one wishes to answer queries of the form "how many elements are at most x?". If one has d elements, then one can pick logd thresholds in a geometric sequence, save information on the sets smaller than the thresholds, and be able to approximately answer such queries. The question below deals with a similar scenario but in which one has a bunch of overlapping sets in the universe, and one has to pick thresholds in each. The issue is that when the sets are overlapping one might want to introduce non-trivial dependencies between the thresholds in different sets.

I have a well-ordered universe U of size m, and n (overlapping) subsets $S_1,...,S_n\subseteq U$, each of size $|S_i|=d$.
For a subset $S_j$ and a number $1\leq i\leq d$ let $S_j^{i}$ be the set of the i smallest elements in $S_j$.

I'd like to pick as few $S_j^i$ as possible and ensure the following property:
For any choice of $i_1,\ldots,i_n$ such that $S_{1}^{i_1}\cup...\cup S_n^{i_n}$ contains at least 10% of the elements in U,
there are $i_1'\leq i_1,...,i_n'\leq i_n$, such that we picked $S_1^{i_1'},\ldots,S_n^{i_n'}$, and $S_{1}^{i_1'}\cup...\cup S_n^{i_n'}$ contains at least 5% of the elements in U.

Clearly, one can take all $n\cdot d$ possible sets. Are $n\cdot \log d$ sets sufficient?


texts: What is the name for this special case of the Travelling Salesman involving dynamic edge costs?

texts:
This is a modeling / taxonomy question. Is there a name for this type of problem?

I came up with the following graph problem for a pizza delivery truck, which starts with zero dollars and enough fuel to drive N miles. They want to deliver pizza to C customers. Each customer will immediately pay them some number of dollars.

Edge weights in this graph are the number of miles between destinations.

Vertices in the graph aren't just customers. They also include "gas station" nodes -- places at which the delivery truck can refuel, converting money on hand to "miles able to drive".

The problem is, given a starting location, how much money on hand and/or gas in the tank does the truck need to delivery pizza to every customer, and still return home?

This isn't the classic Travelling Salesman problem because there are two types of resources in play here, $ and fuel. And there's a resource constraint -- the problem isn't just about finding the minimum cost. It's about finding the minimum starting resources necessary to be able to complete a circuit.


texts:
This is related to some old posts that were closed because someone had felt that they're related to homework. All I'm looking for here is a reference to a paper that may have partially or completely solved the following problem:
n points on the unit interval are given. Consider the set of processes operate discretely on the n points as follows: at every time step, a process takes two points and replaces them by their midpoint. The process stops if only two points are left.
I'm interested to know about an optimal process in this set (meaning a process that given an initial set of n points would lead to the smallest distance between the two final points). Any known bounds on the optimal final distance? Any generalization to higher dimensions?
Thanks!


texts:
Max 3LIN is the problem where one is given a linear system of  equations $C$ over $\mathbb{F}_2$ with $3$ variables per equation, and needs to determine the maximum number of equations that can be satisfied. There cannot be two different equations involving the same $3$ variables. Degree-$D$ MAX-3LIN has the additional property that each variable appears in at most $D$ of the equations.

I would like to know whether there is a family of instances $C_i$ for degree-$D$ MAX-3LIN (with $i$ variables in instance $C_i$) where $\forall c > 0$, the fraction of all $2^i$ possible assignments that satisfy at least $\frac{1}{2} + \frac{c}{\sqrt{D}}$ of the equations goes to $0$ as $i$ goes to infinity.

Note that:

Under reasonable conjectures, if we replace the quantifier on $c$ to $\exists$ the statement is true, by a 2001 hardness of approximation result from Trevisan.
There also exist values of $c$ for which there will always be at least one assignment that satisfies $\frac{1}{2} + \frac{c}{\sqrt{D}}$, following a 2015 result from Barak et al.


texts: Algorithms Design and Complexity - How to think in that 'way'?

texts:
My question is a general one: How do I start thinking in terms of Algorithm Design and Complexity? I am going to take a Graduate Course in Algorithm Design. I had enrolled in it earlier but dropped it later because I could not keep up with it. I have to take this course as a requirement.

Is there a 'trick' to think in this way? I know this is putting it quite crudely but sometimes a fresh perspective helps to think about a subject differently.

The main problem I have with this course (and similar theoretical courses) is: How do I know that solutions that I come up with are correct? I find the theoretical part to be arbitrary especially when 'proving' a certain algorithm acts or behaves in a certain way?

Our course will be using the standard text: Introduction to Algorithms by CLRS.

Are there any textbooks/sites/books/etc. that might offer a way in becoming confident in this field?

Thanks to everyone,

Jason Dane


texts: Does a given regular language contain an infinite prefix-free subset?

texts:
A set of words over a finite alphabet is prefix-free if there are no two distinct words where one is a prefix of the other.

The question is:

What is the complexity of checking whether a regular language given as an NFA contains an infinite prefix-free subset?

Answer (due to Mikhail Rudoy, here below): It can be done in polynomial time, and I think in even in NL.

Paraphrasing Mikhail's answer, let $(\Sigma,q_0,F,\delta)$ be the input NFA in the normal form (no epsilon transitions, trim), and let $L[p,r]$ (resp. $L[p,R]$) be the language obtained by having state $p$ as initial state and $\{r\}$ as final state (resp. state $p$ as inital and the set $R$ as final). For a word $u$ let $u^\omega$ be the infinite word obtained by iterating $u$.

The following are equivalent:

The language $L[q_0,F]$ contains an infinite prefix-free subset.
$\exists q \in Q$, $\exists u \in L[q,q]\smallsetminus\{\varepsilon\}$ $\exists v \in L[q,F]$ so that $v$ is not a prefix of $u^\omega$.
$\exists q \in Q$ $L[q,q] \neq \{\varepsilon\}$ $\forall u \in L[q,q]$ $\exists v \in L[q,F]$ so that $v$ is not a prefix of $u^\omega$.

Proof:

3$\Rightarrow$2 trivial.

For 2$\Rightarrow$1, it suffices to see that for any $w \in L[q_0,q]$ we have that $w (u^{|v|})^* v$ is an infinite prefix-free subset of $L[q_0,F]$.

Finally, 1$\Rightarrow$3 is the "correctness" proof in Mikhail's answer.


texts: reference request for construction of expanders

texts: I'm looking for a good exposition of the explicit constructive proof of the existence of expander graph families due to Reingold Vadhan and Wigderson.  Arora/Barak has a chapter on it, but i find it to be full of typos, more serious errors, and other annoying choices (not to knock AB -- I like it generally).  I just started reading the original RVW paper, but I was wondering if there are other good sources.


texts: How should I perform research as an Undergraduate

texts: Are there distinct fields or types of problems which have contributions that are realistic to achieve for an undergraduate?


texts: Decidability of parametric higher-order type unification

texts:
I'm making a language that has higher-kinded types (like Haskell) and allows type synonyms to appear partially applied in type expressions (unlike Haskell). As an example, consider the following pseudo-GHCi session:

> data Foo f a = Foo (f a)
> type Bar a = Char
> type Qux a = a
> :t Foo 'a'
Foo 'a' :: (f a ~ Char) => Foo f a

(GHCi's actual output is an error message saying that f a can't be unified with Char.)

> :t Foo 'a' :: Foo Bar a
Foo 'a' :: Foo Bar a :: Foo Bar a
> :t Foo 'a' :: Foo Qux Char
Foo 'a' :: Foo Qux Char :: Foo Qux Char

(GHCi's actual output is an error message saying Bar and Qux haven't been passed enough arguments.)

I already understand that:

Haskell requires all type synonyms to be fully applied in type expressions. As a consequence, every valid Haskell type expression has an equivalent canonical form in which no type synonyms appear. Haskell type checkers can take advantage of the aforementioned fact by only performing type unification on canonical forms, where the equation f a ~ g b can be soundly reduced to f ~ g and a ~ b.
Without the aforementioned restriction, we can't reduce equations of the form f e1 ~ e2, where f is a free type variable, and e1 and e2 are arbitrary type expressions. In particular, if e2 isn't a lone type variable, the only thing we can do with such a constraint is attach it to the inferred type signature. This is why, in my pseudo-GHCi seesion above, the principal type of Foo 'a' is (f a ~ Char) => Foo f a.

Before I can formulate the remainder of my question, I need to introduce a little terminology:

Head: The head of a type expression of the form f a is equal to the head of f. The head of any other type expression is the entire type expression itself.
Determinacy: A type expression is determinate if and only if its head isn't a free type variable.
Reducibility: A type equation is reducible if its left- and right-hand sides are both determinate.
Stuckness: A type equation is stuck if either side is the application of a type variable to an arbitrary type expression, and the other side isn't a lone type variable.

Under this new formulation, arbitrarily higher-order (but rank-1) type unification simply consists in reducing a system of equations until no more reducible equations remain (e.g., from Either a b ~ Either c d to a ~ c and b ~ d).

However, one problem remains: Equations like f a ~ Int and f a ~ Char are mutually inconsistent, but, because they're both stuck, the unification algorithm outlined above won't even bother analyzing them. As a result, I'd get a nonsensical inferred type signature like (f a ~ Int, f a ~ Char) => ..., instead of a proper type error.

Now, I'm aware that, in general, higher-order unification is undecidable, so there's no solution to the aforementioned problem that works in all cases. But I have one more constraint that I hope could save the day: All type functions must be parametric. (I just don't like type families.) For example:

f Int ~ Char and f Char ~ Int are now mutually inconsistent constraints.
Assuming no kind polymorphism, f a ~ Int and f b ~ Char have exactly one solution (up to type synonym replacement): a ~ Int, b ~ Char and f is the identity type function.

Is parametric higher-order type unification decidable? I highly suspect, but have no proof, that the notion of "type expression head" could be the key to giving a positive solution to this problem.


texts:
This question is inspired by an existing question about whether a stack can be simulated using two queues in amortized $O(1)$ time per stack operation.  The answer seems to be unknown.  Here is a more specific question, corresponding to the special case in which all PUSH operations are performed first, followed by all POP operations.  How efficiently can a list of $N$ elements be reversed using two initially empty queues?  The legal operations are:

Enqueue the next element from the input list (to the tail of either queue).
Dequeue the element at the head of either queue and enqueue it again (to the tail of either queue).
Dequeue the element at the head of either queue and add it to the output list.

If the input list consists of elements $[1,2,...,N-1,N]$, how does the minimum number of operations required to generate the reversed output list $[N,N-1,...,2,1]$ behave?  A proof that it grows faster than $O(N)$ would be especially interesting, since it would resolve the original question in the negative.

Update (15 Jan 2011): The problem can be solved in $O(N \log N)$, as shown in the submitted answers and their comments; and a lower bound of $\Omega(N)$ is trivial.  Can either of these bounds be improved?


texts: Decomposing k-connected graphs into (k+1)-connected components

texts:
A connected graph can be decomposed into its biconnected components. This block cutpoint tree is unique. Similarly, biconnected graphs can be decomposed into triconnected components. The corresponding SPQR tree describes all the 2-vertex cuts in the graph and is uniquely determined from its graph.

This process does not generalize to higher connectivity. For example, given a triconnected graph $G$, there can be multiple "trees" describing all the 3-vertex cuts of $G$.

  Are there special classes of graphs such that $k$-connected graphs (in these classes) can be decomposed uniquely into their $k+1$-connected components.

Note that my question is slightly different from this question.


texts: Is it known whether $BPP\cap NP\subseteq RP$?

texts: The reverse inclusion is obvious, as is the fact that any self-reducible NP language in BPP is also in RP. Is this also known to hold for non-self-reducible NP languages?


texts: Finding a set which dominates the Minimum Dominating Set

texts:
Given an unweighted, undirected graph, a dominating set $S$ is a set of nodes such that every node is in $S$ or adjacent to a node in $S$.

The dominating set problem is NP-hard, but I am considering a new variation.
Given $k$, the size of the minimum dominating set, I need to find a set of nodes $T$ of size at most $k$ such that there exists a minimum dominating set $S$ in the graph which is dominated by $T$. That is, every any node in $S$ should be in $T$ or adjacent to a node in $T$.

My attempt:
The following is an algorithm I came up with that I have not proven or found a counterexample for.
At the start, all nodes are unmarked.

1) Pick an unmarked node $v$ as a center and mark everything within 2 hops of $v$. EDIT: Instead of picking an arbitrary unmarked node in this step, select the node that would cause the least number of nodes to be marked.

2) Repeat step 1 until all nodes are marked. (Note, this will never place more than $k$ centers)

3) If we have picked less than $k$ centers, keep placing centers on undominated nodes until we have placed $k$ centers.

I have proved that the above algorithm finds a set of centers which dominates a minimum dominating set, under the condition that we don't place any centers in step 3. That is, the algorithm works if steps 1 and 2 manage to place exactly $k$ centers.

Any ideas for whether this algorithm works or a counterexample?


texts: Using epsilon biased sets for circuit lower bounds

texts:
I have seen instances of how the technique of epsilon biased sets can be used to construct hard functions against a circuit class - like how in the recent paper of Kane-Williams this was used to construct a hard function for the class of circuits of the form Majority-of-two-layers-of-Threshold-gates.

I was wondering if there is any past work where this object epsilon-biased-sets have been used as a proof technique for showing circuit lower bounds. (..I would be happy to get any reference along these lines that may strike your mind in relation to this...)


texts: Trade off between time and query complexity

texts:
Working directly with time complexity or circuit lower bounds is scary. Hence, we develop tools like query complexity (or decision-tree complexity) to get a handle on lower bounds. Since each query takes at least one unit step, and computations between queries are counted as free, time complexity is as at least as high as query complexity. However, can we say anything about the separations?

I am curious about work in the classical, or quantum literature, but provide examples from QC since I am more familiar.

Some famous algorithms such as Grover’s search and Shor’s period finding, the time complexity is within poly-logarithmic factors of the query complexity. For others, such as the Hidden Subgroup Problem, we have polynomial query complexity, yet polynomial time algorithms are not known.

Since a gap potentially exists between time and query complexity, it is not clear that an optimal time complexity algorithm has to have the same query complexity as the optimal query complexity algorithm.

  Are there examples of trade-offs between time and query complexity?

Are there problems where the best known time complexity algorithm has a different query complexity than the best known query complexity algorithm? In other words, can we perform more queries to make the between-query operations easier?

Or is there an argument that shows that there is always a version of an asymptotically optimal query algorithm having an implementation with asymptotically best time-complexity?


texts: What is the known complexity of this game? (similar to PushPush-1)

texts:
I've been looking at a few entries in http://library.msri.org/books/Book56/files/10demaine.pdf (on combinatorial algorithmic game theory). I didn't see the following game listed there, and I want to know if it has a name, and whether it's computational complexity has been studied:

A block sits on a starting position in a room containing a bunch of blocks, and an exterior agent can slide the block in any one of four directions (N, S, E, W). When it's moved, it slides in that direction until it is stopped by hitting a wall or a block.

For an illustration (not the sharpest, but the first I could find on Google), a student designed this game in the Scratch programming language: http://scratch.mit.edu/projects/StrykerV/1466085.

Specifically, I want to know if this game is NP-hard or PSPACE-complete. It seems that it should be, since it is similar to PushPush-1, but perhaps having only one moving piece makes it easier.


texts: Quantum GCD circuit: On reversibility and clearing ancillae

texts:
Originally posted on PHYS, however, obviously it has more to do with CS

I am currently trying to implement a circuit for computing the greatest common divisor in the Quantum Computing Language. In my work, I partially proceed from the paper Quantum Circuits for GCD Computation with O(nlogn) Depth and O(n) Ancillae published by I. Markov and M. Saeedi in 2013, which may be found at arXiv http://arxiv.org/abs/1304.7516.

The paper introduces a binary GCD algorithm analogue and works out a design of the quantum circuit which is clarified in least details, however, in the same time it is somewhat confusing due to several statements that actually do not correspond with the rest of the work. First of all, let me enclose an image denoting design of the circuit.

(Credit goes to the paper)

As you may see, the circuit entirely corresponds to the classical binary GCD algorithm. It takes advantage of quantum circuits for comparison, bit shift, addition and multiplication. Nevertheless, in our case those functions are controlled by state of ancillary qubits and thus, they may not regarded reversible on their own. It means, we have to account for a separate register of auxiliary qubits which cannot be erased till the end of our computation as it would simply violate desired reversibility otherwise.

But in contrast to that, in the paper we may find at least three statements which do actually deny those simple facts. Let me cite: (About preceding works) The authors did not clear all zero-initialized ancillae which limits the applicability of their techniques. (About the circuit) The zero-initialized ancillae may be modified in-side a given circuit, but should be returned to zero at the end of computation to be reused.  (About implementation) To count ancillae, note that all computational ancillae are cleared inside each block. After the final multiplication block for R·B, one can copy (in log depth) the final GCD result to another n-qubit zero-initialized register and apply the whole circuit (except for copying the result) in reverse order to recover A,B, and zero-initialized ancillae. Given that all components use O(n) ancillae, the total number of ancillae remains linear.

I ask myself: How can be all ancillaes cleared at the end of each computational block while the binary GCD seems to be reversible only with regard to an auxiliary register of control qubits? It is apparent this question reduces to the problem of binary GCD reversibility which is actually something I am doubtful about. Maybe I lack of insight and the usage of other control bits is so obvious so as to omit it, however, in every case I would like to ask you about your view on the problem.


texts: Is there a natural problem on the naturals that is NP-complete?

texts:
Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there any natural problems, i.e. ones that do not use some encoding and special interpretation of the digits? For example "Is n a prime?" is such a natural problem, but this one is in P. Or "Who wins the Nim game with heaps of size 3, 5, n, n?" is another problem that I consider natural, but we also know this to be in P. I am also interested in other complexity classes instead of NP.

Update: As pointed out by Emil Jeřábek, given $a,b,c\in \mathbb N,$ to determine whether $ax^2+by-c=0$ has a solution over the naturals is NP-complete. This is exactly what I had in mind as natural, except that here the input is three numbers instead of just one.

Update 2: And after more than four years waiting, Dan Brumleve has given a "better" solution - note that it's still not complete because of the randomized reduction.


texts: Range concatenation grammars which are unambiguous as (and are NOT CFL)?

texts:
Are there any range concatenation grammars that

generate only one possible parse tree
are not also context-free?


texts: Purpose and determining when to use hidden layers

texts:
Following up on this question...

I am attempting to learn how to use and create neural networks for my research, and one point is somewhat escaping me.  I realize that hidden layers are a somewhat necessary portion of this, however I am stuck on two points which my references aren't explaining to my satisfaction:

What is the exact purpose of the hidden layer?
How does one determine how many hidden layers to use?

From what I gather, it is to "model" real world functionality, but if possible I'd like a bit more of an explanation.


texts: NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family

texts:
I would like to know whether there are any examples of natural problems within the MAX-$k$-CSP family for which (under standard/reasonable conjectures) we believe the following:

There is a value $\epsilon_1$ such that approximation within a factor of $\epsilon_1$ is possible in polynomial time.
There is a value $\epsilon_2$ such that approximation within a factor of $\epsilon_2$ is NP-hard.
There is some value $\epsilon$ between $\epsilon_1$ and $\epsilon_2$ such that approximation within a factor of $\epsilon$ are neither in polynomial time nor NP-Hard.

(There is a general question about NP-intermediate problems here, but it is much more general in its problem domain, as well as oriented towards the exact-answer setting)


texts: Is my understanding regarding how to implement Quotient Types correct?

texts:
I was trying to understand Quotient Types, and determine if Self-Types can be used to implement them. From a Reddit post,

Here is an example and explanation that may be more familiar to non-mathematicians. You can use a list to represent a set. The list [1,2,3] represents a set and [3,2,1] represents the same set. The problem with this is that you can break the abstraction. We could wrap this in a data type Set and define an Eq instance that makes Set [1,2,3] == Set [3,2,1]. We can write a function sum:
sumSet (Set s) = sum s

and we can write a function first:
firstSet (Set s) = first s

The sumSet function is fine, but the firstSet function is problematic. We have Set [1,2,3] == Set [3,2,1] but firstSet (Set [1,2,3]) != firstSet (Set [3,2,1]). If two values are equal, then those values should behave the same in all respects: if x is equal to y then f x ought to be equal to f y for any function f, otherwise we are breaking the abstraction. Actually, sumSet also breaks the abstraction if you have duplicate elements, but we could say that it's a multiset so that Set [1,1] != Set [1].

This made a lot of sense to me. If my understanding is right (and I'm not sure it is), a Quotient Type can be implemented by simply having an extra "phantom constructor" on your datatype, which returns an equality instead of a member of the datatype. As in,
data UPair (A : Set) : Set where
  upair : (a : A) -> (b : A) -> UPair(A)
  usame : (a : A) -> (b : B) -> upair a b == upair b a

Is this correct? If so, this can be easily emulated with Self-Types. Using Formality, which features Self-Types, we can write:
UPair : {A : Type} -> Type
  $self
  { ~P    : {wit : UPair(A)} -> Type
  , upair : {a : A, b : A} -> P(upair(~A, a, b))
  , usame : {a : A, b : A} -> upair(a, b) == upair(b, a)
  } -> P(self)

upair : {~A : Type, a : A, b : A} -> UPair(A)
  new(~UPair(A)){~P, upair, usame}
  upair(a, b)

This behaves as the Reddit comment mentions. For example, it is impossible to write a first function, because the returned value can't differ for the [true, false], [false, true] cases, but it is possible to write a sum function for any commutative binary operator.
I've also attempted to implement a proof that UPair is isomorphic to Trit (which should hold since it has 3 elements, since [true, false] and [false, true] are the same). But I ran into some problems (== considers normal forms, so I guess I need extensional equality, and some way to prove those equalities are equivalent?).
In any case, my question is: did I "get it" and his proposed encoding indeed implements Quotient Types, or am I missing some piece?
For completeness, here is the full code with my experiments.


texts: Can I get all min-cuts after executing Push-Relabel?

texts:
The push-relabel algorithm (here is push-relabel as pseudo-code) assigns a distance-label to each node.

After executing push relabel, you have those distance labels and a max flow in a given network $N = ((V, E), s, t, c)$ with $E \subseteq V \times V$, $s,t \in V$, $c:E\rightarrow \mathbb{R}_0^+$.

How to get one min-cut after executing push-relabel:

Find a number $x \in \mathbb{N}: 0 < x < |V|$
$S := \{v \in V | dist(v) > x\}$ and $V \setminus S = \{v \in V | dist(v) < x\}$
There is no edge $(u,v)$ with $u \in S, v \in V \setminus S$ in the residual network.
$(S, V \setminus S)$ is a min-cut.

Proof of correctness:

Such a number $x$ exists, because you have $|V|$ nodes that can have labels, $s$ has the label $|V|$, $t$ has the label $0$. So you have $|V|-1$ possible numbers for $x$ and only $|V|-2$ nodes that can have labels.
This is a valid partition of $V$, as no node has label $x$.
If there was an edge $(u,v)$ with $u \in S, v \in V \setminus S$ in the residual network it would have to be ...

$dist(u) \geq dist(v) + 2$ as we defined $S$ like this:
$\begin{align}
                  & dist(u) > x \land x > dist(v) \\
      \Rightarrow & dist(u) - 1 \geq x \land x \geq dist(v) + 1\\
      \Rightarrow & dist(u) \geq dist(v) + 2 \end{align}$)
For every edge in the residual network you can say: $dist(u) \leq dist(v) +1$

$\Rightarrow 2 \leq 1 \Rightarrow $ Error $\Rightarrow$ there is no edge between $S$ and $V \setminus S$ in the residual network
As there is no free capacity in the residual network between the sets $S$ and $V \setminus S$, the value of the min cut is the max flow. According to max-flow min-cut theorem $(S, V \setminus S)$ is a min-cut.

So the given algorithm can find at least one min-cut quite fast after push-relabel was executed. As $x$ can have more values (the labels of some nodes might be the same and they can go up to $2|V|-1$ as far as I know), you can also find more than one min-cut.

My question:

Do I find all min-cuts this way?


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

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

Now we know that at the core of Mathematica is a Lisp-like system, but instead of being based purely on the Lambda Calculus, it is based on a term-rewriting system.

Here the author states state:

  Mathematica is fundamentally a term rewriting system... a more general concept than the Lambda Calculus behind Lisp.

It seems that the Lambda Calculus is a small part of a much more general category. (Quite eye-opening as a thought this was more of a foundational concept). I'm trying to read more about this to get some perspective on it.

My question is: How is Lambda Calculus a specific type of Term Writing system?


texts: Relating PAC learning results and abstaining classifiers

texts: Quite a few results are available on learning miscellaneous concept classes in the PAC learning framework. I would like to know whether any of these results have been extended in the abstaining classifier setting, where the classifier is allowed to refrain from classifying certain examples under various restrictions. In particular, does abstaining improve accuracy in any way, and if so, can this improvement be quantified?


texts: Minimize the product of distances from n fixed points

texts:
Given $n$ fixed points $\{p_i\}_{i=1}^n$ in $D$-dimensional Euclidean space $\mathbb{R}^D$, consider the following optimization problem:

$$
\begin{align}
  \text{mininize} \ \ \ &\prod_{i=1}^n \lVert p-p_i\rVert\\
  \text{subject to: } & \lVert p-p_i\rVert \ge 1, \text{for } i=1,\cdots,n
\end{align}
$$

The constraint is to make sure that trivial solution $p=p_i$ won't occur.

Q. Has there been any literature discussing such problem already?

Thanks in advance.


texts: Maximum weight triangles in dense graphs

texts:
There are multiple results (Vassilevska and Williams STOC09, for instance) on computing efficiently minimal-weight triangles (or more generally patterns) in node-weighted graphs.
Several of these results prove more efficient bounds when the graph is sparse.

We can show similar bounds on minimal weight triangles in a dense graph replacing the number of edges $m$ with number of missing edges $m'=n^2-m$, but is there a general argument (e.g., some kind of duality) that would allow to systematically translate bounds on sparse graphs into bounds on dense graphs for such weighted triangles and pattern problems?

Remark: of course I assume we are provided with the list of missing edges, in order to avoid the $n^2$ cost.


texts:
I am curious in a broad sense about what is known about parallelizing algorithms in P. I found the following wikipedia article about the subject:

http://en.wikipedia.org/wiki/NC_%28complexity%29

The article contains the following sentence:

  It is unknown whether NC = P, but most
  researchers suspect this to be false,
  meaning that there are probably some
  tractable problems which are
  "inherently sequential" and cannot
  significantly be sped up by using
  parallelism

Does this sound reasonable? Are there known cases where a problem in P cannot be sped up using parallelism?


texts: Best way to determine if a list of bytes are random?

texts:
Is there some algorithm out there that can return some value indicating a level of randomness? I believe it's called Data Entropy.

I recently read this article: http://faculty.rhodes.edu/wetzel/random/mainbody.html

Would his approach of analyzing coin flips apply for bytes? Should I drop down to the bit level where it's true/false again or is there a way to determine based on the full byte value?

Are their better analyses than this article?


texts: Vertex Covers whose vertex induced subgraph has an even number of edges and no isolated vertices

texts:
Let $G$ be a graph, and let $C_{E,0}$ be the number of those vertex covers of $G$ satisfying both the following properties:

Their corresponding vertex induced subgraph has an even number of edges.
Their corresponding vertex induced subgraph has no isolated vertices.

  Questions

  Did anyone already study the problem of computing $C_{E,0}$? What is known about it?
  More importantly, which is the computational complexity of computing $C_{E,0}\ mod\ 2$?


texts: Which graph parameters are NOT concentrated on random graphs?

texts:
It is well known that many important graph parameters show (strong) concentration on random graphs, at least in some range of the edge probability. Some typical examples are the chromatic number, maximum clique,  maximum independent set, maximum matching, domination number, number of copies of a fixed subgraph, diameter, maximum degree, choice number (list coloring number), Lovasz $\theta$-number, tree width, etc.

Question: Which are the exceptions, that is, meaningful graph parameters that are not concentrated on random graphs?

Edit.
A possible definition of concentration is this:

Let $X_n$ be a graph parameter on $n$-vertex random graphs. We call it concentrated, if for every $\epsilon>0$, it holds that
$$\lim_{n\rightarrow\infty}\Pr\big((1-\epsilon)E(X_n)\leq X_n \leq (1+\epsilon)E(X_n)\big)=1.$$
The concentration is strong, if the probability approaches 1 at an exponential rate. But sometimes strong is used in a different sense, referring to the fact that the convergence remains true with a shrinking interval, yielding a possibly very narrow range.
 For example, if $X_n$ is the minimum degree, then, for some range of the edge probability $p$,  one can prove
$$\lim_{n\rightarrow\infty}\Pr\big(\lfloor E(X_n)\rfloor\leq X_n \leq \lceil E(X_n)\rceil\big)=1$$
which is the shortest possible interval (as the degree is integer, but the expected value may not be).

Note: One can construct artificial exemptions from  the concentration rule. For example, let $X_n=n$, if the graph has an odd number of edges, and 0 otherwise. This is clearly not concentrated, but I would not consider it a meaningful parameter.


texts: Measures of "correlation" between two orderings

texts:
An easy question perhaps?

Taking a (fictional) concrete example, let's say I have two ranking methods for HTML documents: PageRank and HITS. I derive an ordered list over the same set of documents according to their rank values (there can be ties) for both ranking methods.

Now, I want to quantify how much the two orderings correlate. I'm not interested in the absolute values of the ranking measures, but I'm looking for measures of correlation between the orderings.

I can think of some intuitive correlation measures one could apply like "average distance" or such:

${\displaystyle\frac{\sum_{doc_i\in Docs}\mathrm{abs}(pos_{rank1}(doc_i) - pos_{rank2}(doc_i))}{|Docs|^2}}$

but I'm wondering if anyone knows of any standard techniques I could check out?

In particular, I would prefer a symmetric measure which is easy to intuit and whose results are tangible/"portable". I've a number of different orderings which I'll be comparing pair-wise, but the set of $Docs$ remains the same.

Many thanks in advance!

(having difficulty tagging... please feel free to edit tags)


texts: Simple model of computation with homoiconicity

texts:
Is there a simple model of computation with homoiconicity?

It would also be nice if, like beta reduction in lambda calculus, every step in execution yields a new valid program.

Besides the lack of homoiconicity, another annoyance of lambda calculus is the necessity of checking for free variables when performing substitution.


texts:
It is well-known that for classical PAC learning, $\Omega(d/\varepsilon)$ examples are necessary in order to acheive an error bound of $\varepsilon$ w.h.p., where $d$ is the VC-dimension of the concept class.

Is it known that $\Omega(d/\varepsilon^2)$ examples are needed in the agnostic case?


texts: Number of operations to compute product of pairwise sums over a commutative semiring

texts:
Let $S$ be a commutative semiring and $T\subset S$, how many semiring operations are required to compute the following
$$\prod_{a,b\in T} a+b$$?
This problem can be solved for commutative rings in $O(n \log n)$ ring operations using multipoint polynomial evaluation from a related problem. However, the algorithm requires there is an inverse to addition.
Actually I'm mostly interested in a similar problem. We have $M = \{A_1,\ldots,A_k\}$ such that $A_i\subset S$. We want to compute
$$\prod_{A\in M} \prod_{A\neq B\in M} \prod_{a\in A,b\in B} a+b$$
with least number of semiring operations.


texts: Restricted Monotone 3CNF formula: counting satisfying assignments (both modulo $2^n$ and modulo $2$)

texts:
Consider a Monotone 3CNF formula having both the following additional restrictions:

Every variable appears in exactly $2$ clauses.
Given any $2$ clauses, they share at most $1$ variable.

I would like to know how hard is counting the satisfying assignments of such a formula.

Update 06/04/2013 12:55

I would also like to know how hard is determining the parity of the number of satisfying assignments.

Update 11/04/2013 22:40

What if, in addition to the restrictions described above, we also introduce both the following restrictions:

The formula is planar.
The formula is bipartite.

Update 16/04/2013 23:00

Each satisfying assignment corresponds to an edge cover of a $3$-regular graph. After extensive search, the only relevant paper I was able to find on counting edge covers is the (3rd) one already mentioned in Yuval's answer. At the beginning of such paper, the authors say "We initiate the study of sampling (and the related question of counting) of all edge covers of a graph". I'm very surprised that this problem has received so few attention (compared to counting vertex covers, which is widely studied and much better understood, for several graph classes). We do not know whether counting edge covers is $\#P$-hard. We do not know whether determining the parity of the number of edge covers is $\oplus P$-hard, either.

Update 09/06/2013 07:38

Determining the parity of the number of edge covers is $\oplus P$-hard, check answer below.


texts: What are the most significant research papers on the foundations of generics in C# and .NET?


texts: Was this complexity measure studied before?

texts:
An initially unknown string $x$ is known to be in $C\subseteq \{0,1\}^n$. Every round you are allowed to reveal one bit of $x$ (on your choice, and adaptively). How many bits do you need to reveal in order to be certain about what $x$ is?

For example, if $C=\{x\mid \text{parity}(x)=0\}$, then $(n-1)$ bits are needed. If $C=\{e_i\mid i\in [n], e_i=(0,0,\cdots,0,1(\text{i}^{th}\text{coordinate}),0,\cdots, 0)\}$ then also $(n-1)$ bits are needed. But if $C=\{0^p1^{n-p}\mid p\in [n]\}$ then only $\log n$ bits are needed since we can binary search the position where the alternation happens.

Was this "revealing complexity" $RC(C)$ studied before? If not, what is some combinatorial feature (or any sufficient/necessary conditions) of $C$ with $RC$ to be $n-o(\log n)$?

Any previous results or new ideas are appreciated.


texts: LP solver for sparse, PSD and strictly diagonally dominant matrix

texts:
I have a linear problem with a sparse, psd and strictly diagonally dominant matrix. Can you please point me to some known best solvers (in terms of runtime, or easy to be practically optimized for multicore and SIMD system)?

Currently my direction was to try conjugate gradient method, and it seems to solve the problem in about 8-10 iterations (for specific use case), which is pretty good. However I wonder if there are other solvers that take the advantages of those characteristics even better.

Much thanks!


texts:
I want to construct a family of functions $H:\{0,1\}^n \rightarrow \{0,1\}$ with a property that is similar to k-wise independence. Specifically, I want $H$ to satisfy the following property. Let $k$ be some large natural number that is fixed. There exists a $d$ such that for every $n^k$ tuple of $n$ bit strings $x_1,...,x_{n^k}$,

$Pr_{h \leftarrow H}[  \cap_{j=2}^{n^k}  h(x_j)=0 \, \cap \, h(x_1)=1] \geq 1/n^d$

The additional (and crucial constraint) is that I want to be able to compute this family of functions using (a family of) circuits of size at most $n^3$ ($k$ is much bigger than 3). Note that if we don't have this constraint, then it is possible to do this (using family of circuits of size at least $n^e$).

Is it even possible for such a family to exist?


texts:
Assume a planar graph G, and all its vertices have degree at most 4.
 Consider a cycle in G. The weight of cycle c is the total weight of its vertices, and a vertex is weighted with the following manner:

For example look at vertex v, if cycle c traverses vertex v by passing through e2 and e4 then it would cost w1 and if it traverses v by passing through e4 and e3 then it would cost w2 and so on! (G is undirected, so traversing v by passing through e4 and e3 costs the same as traversing v by passing through e3 and e4, and all possible traversal from a vertex contain weights; some of them are showed with pink curves in pic.)

1-What is the complexity of finding a cycle with total weight k? (k is a given value)
2-Is finding weighted cycles in G harder than finding cycles in general weighted graphs?

this is also the link of pic:
http://rapidshare.com/files/435859757/a.bmp


texts: Is there some mathematical closed form (or somewhat tight asymptotic one) for "Google Eggs Puzzle"?

texts:
The following brief description of the known "Google Eggs Puzzle" comes mainly from the web site Google Eggs:

  Google Eggs Puzzle: Given n floors and m eggs, what is the approach to find the highest floor from which eggs can be thrown safely, while minimizing the throws (not broken eggs).

The so called "highest floor" in the above problem deserves more formal definition:

  "highest:" there must be a floor f (in any sufficiently tall building) such that an egg dropped from the  f th floor breaks, but one dropped from the (f-1)st floor will not. Then, f-1 here is the highest floor.

Actually, the description of "highest" is an excerpt from the book "The Algorithm Design Manual (Second Edition)" by Steven S. Skiena. Being an exercise in Chapter 8 "Dynamic Programming", there are plenty of resources in Web devoted to solving the puzzle by the means of dynamic programming, like Google Eggs and The Two Egg Problem.

However, there is a question from the above book:

  Show that $E(n, m) = \Theta(n^{\frac{1}{m}})$, where $E(\cdot)$ is the minimum number of throws. (Note: I have changed the notations used in book for consistency.)

It is the question that motivates my problem:

  My Problem: Is there some mathematical closed form for general "Google Eggs Puzzle" with n floors and m eggs, instead of dynamic programming recurrence, and of course tighter than the $E(n, m) = \Theta(n^{\frac{1}{m}})$ one?


texts: Suppose one has a set of $n$ points in $\mathbb{R}^d$, where the points are represented as $p_1$ through to $p_n$. Define the weight matrix $W$ as follows: let $W_{i,j}$ be $e^{-||p_i - p_j ||^2}$, also sometimes known as a Gaussian weight matrix. My question is, is there a relation of the rank of $W$ to the underlying dimensionality $d$? If not, is there a rank $d$ matrix approximation of $W$?  The reason I say this is that in a loose "information theoretic" sense, all the weights can be reconstructed from the $d$ real coordinates of each point.


texts: Finding a random regular graph with degree d

texts:
I'm trying to find undirected random graphs $G(V,E)$ with $|V|$ = $d^2$ for $d \in \mathbb{N}$ such that $\forall v \in V: deg(v) = d$.

For $d \in 2\mathbb{N} +1$ this trivially is impossible as no such graph exists: The number of incidences (connections between vertices and edges) is given by $|V|\cdot d = d^3 = 8k^3 + 12k^2 + 6k + 1$ (for some $k$). As the number of incidences is always double the number of edges $|E| = d^3/2$ is a contradiction.

This argument however, doesn't work for $d \in 2\mathbb{N}$.

My first guess was just constructing a random graph would do, however, this can get stuck in a local maximum. For instance in $d = 2$:

+---+    example for
|  /     an incomplete
| /      graph that
|/       cannot be
+   +    completed

A similar example can be constructed for $d = 4$ leaving up to two unconnectable vertices (essentially by using a 4-HyperCube).

I strongly suspect that for each $d$ the number of valid graphs significantly outweigh the number of incomplete graphs, but I would like to know how likely it is to end up with an incomplete graph. And if there is a better way to find these graphs than the random algorithm above (which could perhaps be fixed by breaking apart incomplete graphs, but that would not be guaranteed to terminate).


texts: How much computational power fits into a cubic centimeter?

texts:
This question is a followup on the question about DNA algorithms asked by Aadita Mehra.

In comments there, Joe Fitzsimmons said, in part:

  [T]he radius of the system must scale proportionately to the mass to avoid this. The computational power scales at most linearly in the mass. Thus your exponential amount of machinery has an exponential radius. Since you can't signal faster than light, a signal from one side to another takes an exponentially long time to reach the other side, and so if all the machinery contribute to the answer, it is impossible to solve the problem in less than exponential time.

My question has two parts.

(1) What is the best way/ways to formalize a statement like, "The computational power scales at most linearly in the mass" ?  Is this statement really not up for debate?

(2) Suppose the statement is true.  Even so, could nature already have done an exponential amount of preprocessing that we might be able to make use of, for example evolution's creation of vision systems through "brute force randomization."

I've heard and read a fair number of soft (pseudoscientific) answers to questions of this sort, and I'd be grateful for any answers here, but I'm most interested in how (1) and (2) can be recast in TCS rigor.


texts: Voronoi diagram on surface of polyhedron

texts:
Does anyone know of work on computing the Voronoi diagram of a set of points on a polyhedron, where distance is measured by shortest paths on the surface?
I am particularly interested in convex polyhedra.  I have a vague memory that this has been explored, but my memory is too vague to locate any papers.  Thanks for pointers!


texts: Distinguising between the cases of low or high cover number

texts: Is there a known result saying that for some constants $0 < a < b < 1$, it is NP-hard to distinguish a graph having vertex cover number at most $a \cdot n$ from a graph having vertex cover number at least $b \cdot n$? Here n is the number of vertices in the input graph. In other words, I want to know that (unless P = NP) there is no poly-time algorithm that accepts graphs with vertex-cover number at most $a \cdot n$, rejects graphs with vertex-cover number at least $b \cdot n$, and can return anything for a graph whose vertex-cover number is in between.


texts: Normal form for deterministic (sub)sequential transducers with letter-by-letter outputs

texts:
For a project I'm working on, it would seem useful to have a normal form for
deterministic (sub)sequential transducers in which the set of states, $Q$, is
partitioned into states, $r \in Q_R$, that read a letter from the input tape (but do
not write any output) and states, $w \in Q_W$, that write a letter to the output
tape (but do not read any input).  The goal is to have (inputs and) outputs occur one letter at a time.

In some proofs that I've seen, a similar kind of normal form is used for
deterministic pushdown automata.  What I'm looking for is papers that use this kind
of normal form in the context of (sub)sequential transducers.  Does anyone know of
any references?

Specifically, in the normal form that I'm thinking about, there would be two transition functions, one for each part of the partition $Q = Q_R \cup Q_W$:
$$\begin{eqnarray}
\delta_R &:& Q_R \times \Sigma \to Q \\
\delta_W &:& Q_W \to \Gamma \times Q \\
\end{eqnarray}$$
To enforce finite output, each cycle in the state-transition graph must contain at least one state from $Q_R$.  (For subsequential transducers, I think that one needs another class of "terminal write states" that can be entered from a "read state" only when the input has been completely read.)


texts: Using decision version of TSP to solve optimization version

texts:
Given an oracle for solving the decision version of TSP, how would I use this to solve the optimization version of TSP.

This is not a homework assignment, but of general interest. I have been trying to find a place with examples of these types of reductions.


texts: Synchronizing sequences for rubik's cube?

texts: Are there any results on the existence of synchronizing sequences for a standard 3x3 rubik's cube? Like a proof that there are none? My google-skills failed me...


texts: Relationship between size of quantum superposition and rate of decoherence

texts:
I am new here in StackExchange and this will be my first question to ask. I have a background in Computer Science and I am interested in looking into Distributed Quantum Computing (DQC). I have read some papers in DQC and one of the mentioned motivations in doing research in this field is the issue of quantum decoherence with respect to the size of superposition in the quantum system being used for computation. One might opt to resort to DQC by letting quantum computers using small quantum superpositions perform distributed computation than use a monolithic quantum computer using large quantum superposition (resulting to higher decoherence rate). The papers which I have read so far do not provide references to researches working on the relationship of size of quantum superposition to the rate of quantum decoherence though.

I am interested to know whether an upper bound on the size of superposition of a quantum system can be defined as a factor for considering DQC with respect to decoherence rate in place of the monolithic design of a quantum computer using a large quantum superposition.

There are also works on coping up with decoherence like manipulation of the environment to improve the rate. I just think that DQC is still an interesting field for research though.

I would appreciate any references to works on relationship of size of superposition to rate of decoherence anyone could provide.

Best Regards.


texts: On the complexity of Bandwidth Minimization

texts:
The graph bandwidth problem is defined as follows. Given a graph $G=(V,E)$, a layout $f$ of $G$ is a one-to-one mapping of the vertices of $G$ onto the integers $\{1, \ldots, |V|\}$. The bandwidth of $f$ is defined as

$bw(f) = \max \{|f(u) - f(v)| \mid \{u,v\} \in E\}$.

The bandwidth of $G$, denoted $bw(G)$, is defined as the minimum bandwidth of a layout, the minimum being taken over all possible layouts.

The decision question is: given a graph $G$ and an integer $k$, is $bw(G) \le k$?

This problem is known to be NP-complete even for trees of maximum degree three [Complexity Results for Bandwidth Minimization. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, No.3, 1978]. The authors show that one can test whether a graph has bandwidth at most two in polynomial time. The case $bw \le 3$ was open.

Is the complexity of the case $bw \le 3$ known? What do we know about the complexity of the problem when $k$ is not part of the input but a fixed constant at least $4$?

References would be nice.


texts: Finding all possible simple cyclic paths in a digraph

texts: I have a strongly connected component with over 200 vertices and more than 600 edges. I need to iterate through each simple cycle in the graph exhaustively, without specifying a particular node. Is there any efficient algorithm to perform this operation?


texts: Query complexity of quantum search with measuring oracle

texts:
Consider the following problem:

Let $x\in X$ be a uniformly random value.
Let $O$ be an oracle that measures whether the register $Q$ contains $x$. More precisely, $O$ measures $Q$ using the measurement consisting of projectors $\lvert x\rangle\langle x\rvert$ and $1-\lvert x\rangle\langle x\rvert$, and stores the classical outcome in a one bit register $R$.
Goal: Find $x$ using $q$ queries to $O$.

Conjecture: The probability of finding $x$ is $O(q/\lvert X\rvert)$.

Is this true? If not, what is the best upper bound for the probability?

Note: If $O$ is a unitary quantum oracle (i.e., a unitary mapping $\lvert x,r\rangle$ to $\lvert x,1-r\rangle$, and $\lvert x',r\rangle$ to $\lvert x',r\rangle$ for $x'\neq x$), we know that the bound is $O(q^2/\lvert X\rvert)$. But that is not the oracle described above.

Note: If $O$ is a classical oracle (i.e., $O$ performs a complete measurement of $X$ in the computational basis), we know that the bound is $q/\lvert X\rvert$. But that is not the bound in our case, either, because our oracle $O$ performs only a partial measurement (namely, whether $X$ contains $\lvert x\rangle$ or not).


texts: Approximate linear time algorithm for minimum k-cut

texts:
I need to approximately and quickly solve a minimum k-cut problem for n=2^14 and k=512.

It seems that the 2-approximation algorithm given by Saran and Vazirani which needs to solve O(n) instances of max-flow problem will make the overall algorithm take O(n^2m) time. Though we expect the graph to be sparse, this seems prohibitive.

Is there a O(n) time algorithm with possible compromise on the approximation ratio?

Thank you.


texts:
Denote by $\chi_0(f)$ the minimum number of 0 monochromatic rectangles needed to cover the 0-inputs of $f$, and by $\chi(f)$ the minimum number of monochromatic rectangles needed to cover the all inputs of $f$ (both 0 and 1). It is known that

$$\log \chi(f) \leq D(f) \leq (\log \chi_0(f))^2.$$

The last inequality follows from the famous clique vs independent set upper bound. Is there an $f$ that witnesses such a quadratic separation between $\log \chi(f)$ and $\log \chi_0(f)$?


texts: When is Ising partition function easy to compute?

texts:
Consider Ising model on graph $G$ with uniform coupling strength $J$ and magnetic field $h$. I say its partition function $Z$ is easy to compute if $Z$ can be deterministically computed to arbitrary finite precision in time polynomial in size of the graph.

Here's when $Z$ is known to be easy to compute, what cases am I missing?

Arbitrary $J$

$G$ is planar, $h=0$
treewidth$(G)\le C$

Arbitrary $G$

$|J|$ small relative to girth($G$)
$|J|$ small relative to the branching factor of self-avoiding walks on $G$

I suspect it's easy to compute for all $J$ with minor-excluded $G$ and for all $G$ with $J>0$ because FPRAS exist for these cases. Also it seems $G$ with $|J|\ll |h|$ should be easy because of correlation decay, although I haven't seen either FPDAS or FPRAS in this case


texts: What are the negative consequences of extending CIC with axioms?

texts:
Is it true that adding axioms to the CIC might have negative influences in the computational content of definitions and theorems? I understand that, in the theory's normal behavior, any closed term will reduce to its canonical normal form, e.g. if $n : \mathbb{N}$ is true, then $n$ must reduce to a term of the form $(succ ... (succ (0)))$. But when postulating an axiom - say the function extensionality axiom funext - we just add a new constant to the system

$$ funext : \Pi_{x : A} f (x) = g (x) \to f = g$$

that will just "magically" produces a proof of $f = g$ from any proof of $\Pi_{x : A} f (x) = g (x)$, without any computational meaning at all (in the sense that we cannot extract any code from them?)

But why is this "bad"?

For funext, I read in this coq entry and this mathoverflow question that it will cause the system to either loose canonicity or decidable checking. The coq entry seems to present a good example, but I still would like some more references on that - and somehow I can't find any.

How is that adding extra axioms could cause CIC to have a worse behavior? Any practical examples would be great. (For example, the Univalence Axiom?)
I am afraid in this question is too soft, but if anyone could shed some light on those issues or give me some references would be great!

PS: The coq entry mentions that "Thierry Coquand already observed that pattern matching over intensional families is inconsistent with extensionality in the mid 90ies." Does anyone know in which paper or something?