texts: Boolean circuits which correspond to L/poly

texts:
Branching programs are usually used as a computation model for non-uniform logarithmic space $\mathsf{L}/\mathrm{poly}$.
Is there a reference about Boolean circuits corresponding to $\mathsf{L}/\mathrm{poly}$?

Intuitively, bounded space Turing machines seem to correspond to bounded width Boolean circuits, but I can't find a reference.
Is there a reason that branching programs are used for $\mathsf{L}/\mathrm{poly}$ and Boolean circuits are not used?

[Addition after Sam McGuire's answer (in comments)]

Actually, I'm most interested in Boolean circuits corresponding to $\mathsf{L}/\mathrm{quasipoly}$.
I guess that it is quasipolynomial-size $O(\log n)$-width Boolean circuits.

I would like to know that, whether it is right or not, whether I should prove it myself or not, whether it is known and there's a reference or not.


texts: Reference request on using Kolmogorov complexity to measure the simplicity of models

texts:
Have there been any serious attempts to use the notion of Kolmogorov complexity to measure the simplicity of models outside of theoretical CS? I mean models in the english sense - any logical set of rules that attempts to predict a specific domain of reality. Or any attempts to balance this measure of complexity against the accuracy of the model (how will it predicts reality / a dataset) and conclude that the results are better than chance?
Any research that attempts to describe how we could use Kolmogorov  complexity in some specific field of research would also be most helpful.


texts:
I'm interested in the complexity of the following problem:

Problem $P$: Given an undirected planar graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color the vertices in such a way that the sum of the weights of the monochromatic edges (i.e. those between same color vertices) is minimized. Let's call this sum to be the measure for $(G,w)$.

EDIT 1: A major change in the problem definition: $G$ is planar. Previously, I forgot to specify that. And, edge weights are now integers.

EDIT 2: Below text is part of the original post but it's not very useful as Mikhail Rudoy points out in his answer.

Here is what I've thought so far:

Let $k$ be the optimal number of colors, which we do not know beforehand. Suppose an oracle gives us $k$. Then, the problem becomes similar to the minimum edge deletion k-partition (MEDKP) problem, except for the fact that in MEDKP only positive weights are allowed. So, if we modify the weight function by adding a big enough constant $C$ (such that all weights become positive), i.e.

$w'(e) = w(e) + C,\;\;\;e \in E$

then using $w'$, we exactly have an instance of MEDKP.

To solve $P$, we solve MEDKP for each feasible value of $k$, i.e. $k=1 \dots |V|$. Let $M_k$ denote the set of monochromatic edges in the solution of MEDKP for $k$. Then, the solution of $P$ would be $ M_{k^*}$  where  $k^* = \underset{k}{\arg\min} \sum_{e \in M_k} w(e)$.

Now, I conclude that the problem $P$  is at least as hard as MEDKP. And since MEDKP is not in APX [1], $P$ cannot be in APX either.

Is my reasoning correct? Also, independent of my reasoning above, any pointers, hints or comments on the complexity of $P$ is welcome.


texts: Find the maximum flux path between two nodes

texts:
Given a graph $G$ and two vertices $s$ and $t$, I want the maximum flux path from $s$ to $t$.That is, imagine $G$ to be a flow network with capacities on the edges. I want to find a single path that can carry the maximum flow between $s$ and $t$.

Note that this is not the same as the maximum flow problem where you can compute flows from multiple paths.

Can someone point me to fast algorithms for computing the max flux path?


texts: Can one-way alternating automata with one-counter recognize some unary non-regular languages?

texts:
One-way alternating pushdown automata (1APDA) can recognize any language in $ DTIME(2^{O(n)}) $ (Alternation by Chandra, Kozen, and Stockmeyer, 1981). By replacing a pushdown storage of a 1APDA with a counter, we can obtain a one-way alternating automaton with one-counter (1ACA). My question is about 1ACAs on unary languages.

Can 1ACAs recognize some unary non-regular languages?

Note that one-way nondeterministic pushdown automata can recognize only unary regular languages.


texts:
Planar graphs have genus zero. Graphs embeddable on a torus have genus at most 1. My question is simple :

Are there any problems that are polynomially solvable on planar graphs but NP-hard on graphs of genus one ?
More generally are there any problems that are polynomially solvable on graphs of genus g but NP-hard on graphs of genus > g ?


texts: Sequent calculus for nonmonotonic/defeasible logics?

texts:
Is it possible to construct sequent calculus for nonmonotonic/defeasible logic? If it is possible then those logics can be encoded in proof assistants which require sequent calculus for logic to be encoded (Isabelle, Coq).

I am aware of the several papers from the late nineties by Ana Teresa Martins et al. about sequent calculus for paraconsistent logics. the labelling of propositions (given and derived) is used in those papers. But those papers seems to be unpublished, although they contain bright ideas, the quality of language may be a bit higher. It seems to me that those ideas are not caught by others and developed futher.


texts: Natural examples of context-sensitive languages from practice

texts:
I am looking for natural examples of context-sensitive languages from practice. For example, reasonable answers could include grammar syntax of a programming language, or encoding of certain properties of a program. In particular, please draw analogy from call-string-based context sensitive interprocedural dataflow analysis where the matching parentheses context-free language is used to encode the matching of calls and returns. That is an example where context-free language is useful in practice, or at least to explain a practical problem in a nice little theoretical way. Now, how can a context-sensitive language be useful in a similar context/scenario? That is my question.

Please note that I am not looking for artificial encoding into CSL (made up just to answer this question).


texts: Resource on the Lee-Yang zeroes of the partition function of random $3$-SAT problems

texts: Could anyone point me to the representative papers on the study of the Lee-Yang zeroes of the partition function of random $3$-SAT problems?


texts: Complexity of solving systems of linear equations with hash preimages

texts:
Introduction: I'm researching a decision problem that I thought was in NP because there are certificates for its instances that have a polynomial number of elements. However, I realized that there are subproblems one can construct by using hash functions that would probably make this problem fall in a higher complexity class.

Problem: Let $H$ be an arbitrary cryptographic hash function. The goal is to solve the following system of linear equations with integer coefficients

$$\boldsymbol A \boldsymbol x = \boldsymbol c$$

$$\boldsymbol x = \left[\begin{array}{c}
x_1 \\
\vdots \\
x_n
\end{array}\right]$$

where the values assigned to the variables are required to be integers and are restricted by the following constraints

$$H(x_i) = z_i, \hspace{1cm} \text{for } i = 1 \dots n$$

where $z_i$ are arbitrary but fixed hashes.

Question: What is the time complexity of finding values for $\boldsymbol x$ that fulfill these constraints? Are there any references that look into problems similar to this one?

Notes: The problem of finding an $x$ that fulfills $H(x) = z$ for an arbitrary $z$ is in $O(1)$ because all outputs of $H$ have the same size and one could have a table with a precomputed preimage for each hash. Therefore, the additional difficulty would stem from the fact that each hash can have multiple preimages with unbounded sizes. It's pretty easy to see that if any solvable system like this had polynomial-sized solutions the problem would belong to NP. Nevertheless, the fact that there probably isn't any upper bound on the size of the solutions probably means that the problem is infeasible but I can't think of any obvious way to prove this.


texts: On the status of learnability inside $\mathsf{TC}^0$

texts:
I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside $\mathsf{TC}^0$, since I'm not an expert in the area.

What I've discovered thus far is:

All of  $\mathsf{AC}^0$ can be learned in quasipolynomial time under the uniform distribution via Linial-Mansour-Nisan.
Their paper also points out that existence of a pseudorandom function generator prevents learning, and this, coupled with a later result of Naor-Reingold that $\mathsf{TC}^0$ admits PRFGs, suggests that $\mathsf{TC}^0$ represents the limits of learnability (at least in a PAC-sense)
There's a 2002 paper by Jackson/Klivans/Servedio that can learn a fragment of $\mathsf{TC}^0$ (with at most polylogarithmic majority gates).

I've done the usual google scholaring, but am hoping the collective wisdom of cstheory might have a quicker answer:

  Is what I described the state of the art for our understanding of the
  complexity of learning (in terms of which classes sandwich efficient
  learners) ? And is there a good survey/reference that maps out the current state of the landscape ?


texts: Uniform hierarchy of problems that span complexity and computational hierarchies

texts:
Does anyone know of a set of problems that vary uniformly and span one of the "interesting" hierarchies of complexity and computability? By interesting, I mean, for example, the Polynomial Hierarchy, the Arithmetic Hierarchy, or the Analytic Hierarchy. Or maybe (N)P, (N)EXP, 2(N)EXP, $\ldots$

More concretely: You can give a uniform set of problems that characterize the Arithmetic Hierarchy: $0, 0', \overline{0'}, 0'', \overline{0''},\ldots$. But these aren't always the most useful for reducing to actual problems.

On the other hand, the book by Harel, Kozen and Tiuryn has a set of varying tiling problems that are NP, $\Pi^0_1$, $\Sigma^0_2$ and $\Sigma^1_1$ complete. The problems are useful for showing reductions, but it isn't entirely clear if they generalize uniformly to cover the other levels of the hierarchies they sit in.

Does anyone know of such a set of concrete, uniform problems that span a hierarchy?

EDIT: Just for clarification, I know that the 3 hierarchies I give above all have standard definitions in terms of alternating quantifier strength. That's not what I'm looking for. I'm looking for something different, like a game on a graph or a puzzle played with tilings.


texts: Transitive feedback arc set (TFAS): NP-complete?

texts:
Some time ago, I posted a reference request for graph problems where we want to find a 2-partition of the edges where both sets fulfill a property not related to their cardinality. I was trying to prove that the following problem is NP-hard:

  Given a tournament $G = (V,E)$, is there a feedback arc set $F \subseteq E$ in $G$ that defines a transitive relation?

I do have a construction for an attempt at a proof, but it seems that that is going to run into a dead end, so I thought I might ask here to see whether I'm missing something obvious. In order to not confine your creativity to lines of thought similar to the ones I used, I won't post my attempt here.

Is this problem NP-hard? If so, how to prove it?


texts: Piecewise Linear Circuit Identity Testing

texts:
A circuit is used to express a piecewise linear function of one variable $\ f:\mathbb{Q}\to\mathbb{Q}$  The component gates are:

add the outputs of two other gates together
scale the output of one other gate by some constant
offset the output of one other gate by some constant
take as input the outputs of three other gates, labeled X, Y, C.  If C is less than some constant, output X from this gate, otherwise output Y

Given such a circuit, how efficiently can one verify whether $f(x)=0$ for all $x$?

My apologies that I don't have references to possibly related problems.  I tried searching piecewise linear (identity/equivalence) testing without much luck.  Randomized polynomial identity testing could possibly be tropicalized, but I don't have high hopes for that avenue of attack.

Also, I should mention that this came out of a practical problem involving document layout, in case the existence of applications is motivational.

Addendum:  Here is a non-standard "circuit" problem, which is closer to the intended application.

Consider a DAG with a unique root.  Each node in the DAG represents a function of type $f:\mathbb{Q}\to\mathbb{Q}$:

Leaf $\ f(w) = w\ $ This node has no children.
Linear $\ f(w) = child(aw + b)\ $ This node has one child, with function $child(w)$
Branch $\ f(w) = \left\{\begin{array}[ll]\\ left(w) & w < c\\ right(w) & w\geq c\end{array}\right.\ \ $  This node has two children, whose functions are $left(w)$ and $right(w)$ respectively.

Then, the DAG as a whole represents a piecewise linear function, namely the composition of the atomic functions beginning at the root.  Again, the problem is to determine whether the piecewise linear function is $0$. Or, equivalently (I haven't verified the reduction works both ways) whether for two such piecewise linear functions $f=g$?


texts: What are the uses of Limits and Colimits of Category Theory in every day problems?

texts: I am interested in knowing how we can use the concepts of Limits and Colimits in modeling problems in every day life? Could anyone provide (Software) engineering examples, perhaps? Or describe intuitively in general for what sorts of modeling problems we can use these concepts? Thank you.


texts:
Independent Set (IS) is the $\mathsf{NP}$-complete decision problem

Input: graph $G$ with $v=|V(G)|$, integer $k$
Question: is there an independent set $S \subseteq V(G)$ with at least $k$ vertices?

Similarly, we can define $f(v)$-bounded IS as the promise version of IS, where the promise is that $k \le f(v)$.
Note that the function parameter depends only on the number of vertices in the input graph.

It is straightforward to show that when $f(v) = v/c$ for some constant $c$, then $f(v)$-bounded IS remains $\mathsf{NP}$-hard.
This is because IS can be reduced to $f(v)$-bounded IS by blowing up the number of vertices by at most a factor of $c$.
Similarly, when $f(v)=v^{1/c}$ for some constant $c$, then $f(v)$-bounded IS is also still $\mathsf{NP}$-hard, by blowing up the number of vertices by a power of $c$.

On the other hand, when $k$ is a constant, then $k$-bounded IS can be decided in polynomial time by exhaustively checking each of the $\binom{v}{k} = \Theta(v^k)$ different $k$-subsets, in at most $O(v^{k+2})$ steps.

This suggests that there is a spectrum of hardness defined via functions restricting the largest independent set that is sought in any instance.
This is, in fact, the case: Bodirsky and Grohe 2008 (preprint) and Chen, Thurley, Weyer 2008 (preprint) established such results non-constructively via versions of Ladner's theorem, conditional on $\mathsf{P} \ne \mathsf{NP}$.

Keeping in mind that asymptotic behaviour does not induce a total order on functions,

  what is a "smallest" function $f(v)$ such that $f(v)$-bounded IS is $\mathsf{NP}$-hard?

In particular, is there some function $f(v)=o(v^{1/c})$ for every constant $c>0$ for which bounded IS is hard?
(I'd be happy with an argument that is conditional on a common hypothesis such as ETH or $W[1] \ne \mathsf{FPT}$.)

Note that while $f(v) = v^{1/\lg v} = 2$ yields a polynomial upper bound on time, the somewhat faster growing function $f(v)=v^{1/\lg\lg v}$ yields a bound for exhaustive search that is superpolynomial but subexponential.
It would therefore also be interesting to establish whether there is a function $f(v) = \omega(1)$ such that $f(v)$-bounded IS is still in $\mathsf{P}$.


texts:
Say we want to split a cube in $\mathbb{R}^{64}$ into 10 pieces.
NN, nearest-neighbor or Voronoi splits,
take 10 cluster centres $c_0, \ldots, c_9$ in the cube,
e.g. from K-means,
then classify a new data point $x$ by finding its nearest centre:
$$\text{NN}( x, c_0, \ldots, c_9 ) \equiv \text{argmin}_j\ \| x - c_j \| \text.$$

Kmeans centres are averages of data points, so fall near the data.
Could allowing centres outside the data give better splits ?
Is there a variant of Kmeans which converges e.g. to SVM weights,
viewed as points in the data space ?

As Suresh Venkat points out, "better" splitting,
better classification, is hard to define.


texts:
The Not All Equal $k$-SAT problem (NAE $k$-SAT), given a set $C$ of clauses over a set $X$ of boolean variables such that each clause contains at most $k$ literals, asks whether there exists a truth assignment of the variables such that each clause contains at least one true and at least one false literal.

The PLANAR NAE $k$-SAT problem is the restriction of NAE $k$-SAT to those instances where the incidence bipartite graph of $C$ and $X$ (i.e. the graph of parts $C$ and $X$ with an edge between $x\in X$ and $c\in C$ if and only if $x$ or $\overline{x}$ belongs to $c$), is planar.

It is known that NAE 3-SAT is NP-complete (Garey and Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness), but PLANAR NAE 3-SAT is in P (see Planar NAE3SAT is in P, B. Moret, ACM SIGACT News, Volume 19 Issue 2, Summer 1988 - unfortunately I do not have access to this paper).

Is PLANAR NAE $k$-SAT in P for some $k\geq 4$? Is there a value of $k$ for which it has been shown to be NP-complete?


texts: Are bins with more black than white balls negatively 1-correlated?

texts:
Suppose we throw $m_b$ black balls and $m_w$ white balls independently and
uniformly at random in $n$ bins.
Let
$\left\{ B_i \right\}_{i \in \left\{ 1,\ldots,n \right\}}$,
$\left\{ W_i \right\}_{i \in \left\{ 1,\ldots,n \right\}}$
be the number of black and white balls that end up in bin $i$, respectively.

Let
$\left\{ M_i \right\}_{i \in \left\{ 1,\ldots,n \right\}}$
be the binary random variables such that
$$
    \Pr(M_{i} = 1 \,|\, B_i>W_i ) = 1,\\
    \Pr(M_{i} = 1 \,|\, B_i=W_i ) = 1/2,\\
    \Pr(M_{i} = 1 \,|\, B_i<W_i ) = 0.
$$
In other words, $M_{i}$ indicates whether bin $i$ contains more
black balls than white balls (breaking ties u.a.r.).

In
Randomized Distributed Edge Coloring via an Extension of the
Chernoff--Hoeffding Bounds by
Alessandro Panconesi and Aravind Srinivasan, it is shown that the
Chernoff bound holds for dependent binary random variables such that
for each $I \subseteq \left\{ 1, \cdots, n \right\}$
$$
    \Pr \left( \bigwedge_{i \in I} X_{i} = 1 \right)
    \leq \prod_{i \in I} \Pr \left( X_{i} = 1 \right)
$$
They call the latter property negative 1-correlation.

My question is: are the r.v. $M_{i}$ negatively one correlated?

This is very intuitive, but I couldn't figure out any proof. All my attempts end up dealing with the explicit joint probability distribution of the $B_i$ and $W_i$, at which point I'm stuck...


texts: Generalized Geography on graphs of bounded treewidth

texts:
Generalized Geography (GG) is played on a directed graph where a token is moved along arcs alternatively by two players. The vertices from which the token leaves are deleted. When a player cannot play anymore he loses (and his opponent wins).

GG is PSPACE-complete (see page 11, Figure 1 of "On the complexity of some two-person perfect-information games" of Schaefer) while its variant on undirected graphs is polynomial time solvable (see for instance here).
In the technical report Complexity of Path Forming Games of Hans L. Bodlaender (1989), it is shown that GG becomes polynomial time solvable in graphs of bounded treewidth.

I have two questions concerning that result:
1) Do you agree the algorithm is designed for undirected GG? (which is anyway in P for general graphs). Look at figure 4.1 for instance, plus the fact that the treewidth is not re-defined for directed graphs.
2) As mentioned by Saeed in a related post, "The problem is PSPACE-complete even on digraphs of directed tree width 1".
Now, even if we consider (directed) GG, and the treewidth of the undirected graph obtained by changing each arc into an edge, it seems to be untrue that GG is easier with bounded treewidth: take any instance of QBF with bounded pathwidth (which remains PSPACE-complete, result of Atserias and Oliva), number the variables by their order of appearance in bags going from "left to right", and do the reduction of Schaefer (see also the link given by Saeed). The treewidth of the undirected version of the digraph produced by this reduction is bounded. No?

In view of 1) and 2) why do we think that bounded treewidth makes GG easier?


texts: How can I construct sorting network for $k$ numbers

texts:
How can I construct a sorting network for $k$ numbers?

My goal is to implement sorting networks in Java for $k$ in the range $[3,\hspace{-0.03 in}32]$.

To be even more specific, I only want to sort integers.

I found some implementation in this article (pages 2-3), but I don't understand it.

I been trying to convert this problem to SAT. I started with a simple non-optimal network: $[01, 12, \ldots, (n-1)n, 01, 12, \ldots, (n-2)(n-1), \ldots, 01, 12, 01]$ (source). The idea is to convert it to SAT, find the shortest equal-satisfiable SAT formula, and convert it back to a network representation. The problem is that in the network, the order of comparisons is important, so I don't know hot to convert it to SAT. It sounds like some one has already been trying to do something like this, but I don't understand it completely.

Related question.


texts: How to calculate machine learning time for binary classification?

texts:
I want to calculate the training and testing time for binary classification. How to calculate that if a given database D has A attributes and T records. Please any one help me?
or how to calculate the time complexity for binary classifier?


texts: "Computing on data streams" clarification

texts:
In the 1998 technical note "Computing on data streams" by Monika Rauch Henzinger , Prabhakar Raghavan , Sridar Rajagopalan (found here: http://www.eecs.harvard.edu/~michaelm/E210/datastreams.pdf)

They define a directed multigraph with node set V1 union V2 union …
union Vk, all of whose edges are directed from a node in Vi to a node
in Vi+1.

I cannot see how this allows for disconnected components?  Can anyone clarify this?


texts: Good text on introduction to circuit complexity

texts: I would like to ask suggestions for good texts which introduce circuit complexity. Any pointers to recent advances and open problems in this field would also be helpful.


texts:
A program is an encoded Turing Machine. And a size optimizer of a program is a TM $M_1$ such that:

  On any input $M$, $M_1$ outputs $M_{min}$ such that $M_{min}$ is the shortest TM which is equivalent to $M$.

If size-optimization is not computable, the above $M_1$ shouldn't exist.

How do we prove this?
Does this also mean a size-optimality decider can't exist?
How does this generalize to other kinds of optimization (speed-optimization, for example)?


texts: Just out of curiosity, if the classical computation is about permutation matrices and quantum computing is about unitary matrices (of which the permutation matrices are a subgroup), then will there be any computation paradigm beyond unitary matrices?


texts: Sparse subgraph preserving rooted edge connectivity up to $k$

texts:
For a graph $G=(V,E)$ with $n$ vertices and $m$ edges, a subgraph of $O(kn)$ edges   is an $r$-rooted-$k$-sparsifier if it preserves the local edge connectivity from $r$ to every other vertex up to $k$. Namely, it is a subgraph $G_k$, such that $\lambda(r,x,G_k)\geq \min(\lambda(r,x,G),k)$ for all $x\in V$. Here $\lambda(x,y,G)$ is the maximum number of edge disjoint paths from $x$ to $y$.

For undirected graphs, Nagomochi and Ibaraki shows such graph exist and has an algorithm to find a $r$-rooted-$k$-sparsifier in $O(m)$ time. In fact, it finds a subgraph preserves all local edge and vertex connectivity.

Are there similar results for directed graphs? Or are there a proof that a $r$-rooted-$k$-sparsifier cannot exist for some directed graph?


texts:
First asked on math.SE with no replies.

Suppose I have a planar graph, with a planar embedding, how do I find tree decomposition?
What is the optimal tree decomposition of a $d$-by-$d$ square grid? Not completely sure how to define "optimal", but it should distinguish between decomposition with one large bag and decomposition with many large bags.


texts: Efficient algorithm to find number of factors

texts: Given an integer n, is there an efficient algorithm to find the number of factors of n?


texts: Are uniqueness rules converse to introduction rules?

texts:
I've seen many people connecting introduction rules and elimination rules, saying that they're dual notion. Indeed, like in the categorical model, these rules are symmetric morphisms. However, if we think of the introduction rules as 'theorems' (in the sense of CHK-correspondence), the uniqueness rules seem to fit better as a 'converse' of the introduction theorems. Am I right?
My reason: it's because the uniqueness rules take the return type of the introduction rules as input, while the elimination rules take the return value of the formation rule as input.
Examples (as AB asked):

Product type

Intro: given $a:A,b:B$ an instance of $A \times B$ can be uniquely constructed
Unique: given an instance of $A \times B$, it is uniquely constructed by some $a:A,b:B$
Elim (I'm just using the non-dependent version to make it simple): providing a function $A \to B \to C$, we could feed it with an instance of $A \times B$ and we could obtain an instance of $C$

Identity type a la Martin-Löf

Intro: given $x:A$ an instance of $\sum_{x:A}{x=_A x}$ can be uniquely constructed
Unique: given an instance of $\sum_{y:A}{x=_A y}$ must be uniquely constructed from some $x:A$
Elim: omitted

I'm asking to look for criticisms on my pov.


texts: computing maximal bit density over a FSM

texts:
let $L$ be a regular language defined by a FSM over binary symbols $\{0,1\}$. consider a function $f(x)$ on words/ strings that computes "bit density", defined as the number of $1$'s in a word ("Hamming weight") divided by the word length.

  what is an algorithm to compute $\max_{x \in L} f(x)$?

there is a simple randomized/ estimation algorithm that computes $f(x)$ over random words; am looking for a deterministic one. note that $f(x)$ evaluated on the shortest word in $L$ is not necessarily the same as the global minimum. am also interested in other generalizations of $f(x)$ that are based on similar "simple word metrics".

bkg: this question arose in studying & idea in attacking an old open number theoretic problem.


texts: Computational Complexity of cycle double cover

texts:
Let $\mathcal{G}$ be the set of all finite simple graphs. Let graph $G\in \mathcal{G}$ and $C_G=\left <C_1,...,C_m \right >$ be a sequence of cycles of $G$ for some $m$. For every edge $e$ of $G$ define $C_G(e)$ the number of cycles in $C_G$ that have $e$.
A graph $G\in \mathcal{G}$ has cycle double cover iff there exists a $C_G$ of cycles of $G$ such that for every edge $e$ of $G$, $C_G(e)=2$.

CDC Conjecture. Every bridgeless graph in $\mathcal{G}$ has a cycle double cover.

The CDC conjecture is open, but for some classes of graphs like planar graphs, hamiltonian graphs are solved.
My question is about computational complexity of
$$\mathcal{L}_{CDC}=\{x\in \mathcal{N} | x\:represents\: G_x\in \mathcal{G} \land CDC(x)\}$$
$\mathcal{L}_{CDC}\in NP$, because a cycle double cover $C_G$ has a polynomial size in length of $x$ ($G_x\in \mathcal{G}$) and deciding whether $C_{G_x}$ double covers $G_x$ needs polynomial time. Also if the CDC conjecture be true, then $\mathcal{L}_{CDC}\in P$.

Q1. Is $\mathcal{L}_{CDC}$ in $Co-NP$?
Q2. Is $\mathcal{L}_{CDC}$ $NP$-complete?

If the answer to Q2 is yes, then probably CDC conjecture is false (because it seems that $P\not=NP$).

Q2. Is $\mathcal{L}_{CDC}$ in $P$ or $BPP$? If the answer is yes, can deciding this language be in smaller complexity class?
Q3. What is the relation of $\mathcal{L}_{CDC}$ to smaller complexity classes like $NC^1$?

Thanks.


texts: Is there a polynomial-time algorithm to solve graph isomorphism for Delaunay graphs of (finite) hexagonal tessellations?

texts:
Given a finite plane, I have a hexagonal tessellation of that plane with a fixed-size regular hexagon. I then compute the Delaunay graph G for the tessellation. Given such a graph G, I delete specific sets of nodes in that graph to yield multiple subgraphs of G. I need to determine if these subgraphs are isomorphic (to each other).

Does there exist a polynomial-time algorithm to do so?

I know that there is no know poly-time algorithm for solving graph isomorphism in the general case. But I am not sure if it is still the case for such specific Delaunay graphs.


texts: Purely spectral algorithms for the minimum spanning tree problem

texts:
There are many algorithms that address the MST problem, from classical (Boruvka, Prim, Kruskal), optimal (Pettie et al.) to their distributed variants (Bader et al.).

However, I fail to find any references to algorithms that might use spectral properties to algebraically arrive at a suitable representation of the MST (e.g. the set of edges, the adjacency or Laplacian matrix of the MST).

Are there any such algorithms or rationales (proofs) why they don't exist?


texts: Boundedness of expected reward Markov chain

texts:
This is a repost of a question I asked on math.SE.

The problem:

I have an infinite Markov chain $M$ over the natural numbers, with transition probabilities $$P(n,m)=\sum_{i=0}^{min(m,n)} {n\choose i}(1-p)^ip^{n-i}q^{m-i}(1-q).$$

For any natural numbers $n$ and $s$, I define the random variable $O^n_s:\mathbb{N}^*\rightarrow \mathbb{N}$ to be sum of all states visited if we start in state $s$ and end when we first reach a state less than or equal to $n$. Formally, let $w = (s, w_1, w_2, \dots)$ denote the random sequence of states visited by the Markov chain, and let $$O^n_s(w)=\left\{\begin{array}{ll} \sum_{i=1}^{l}w_i& \text{where $l$ is the smallest index such that $w_l\le n$}\\\bot& \text{if $w_i > n$ for all $i$}\end{array}\right.$$

Let $\mathcal{E}^n_s$ denote the conditional expectation $E_w[O^n_s(w)\mid O^n_s(w)\neq\bot]$.

The question is:

Is there a real number $B$ such that $\mathcal{E}^n_s\leq B$ for all natural numbers $n$ and $s$?

what I think:

This process reminds me of a discrete time $M/M/\infty$ queue where at each step $n$ arrives with probability $q^n(1-q)$ and at each step each service terminates with probability $p$.

What I'm looking for:

But I couldn't find any references or hint about a model like that. If you have any idea or references (or, even better, a proof) please tell me.

Any ideas, (even if it doesn't apply directly there) would be accepted. I'm a bit out of idea on how to solve this.

[note: why P is a transition matrix]

For all $n\in \mathbb{N}$, $$\begin{array}{rcl}
\sum_{m\in\mathbb{N}}P(n,m)&=&\sum_{m\in\mathbb{N}}\sum_{i=0}^{min(m,n)} {n\choose i}(1-p)^ip^{n-i}q^{m-i}(1-q)\\
&=&\sum_{i=0}^{n}\sum_{m\geq i}{n\choose i}(1-p)^ip^{n-i}q^{m-i}(1-q)\\
&=&\sum_{i=0}^{n}{n\choose i}(1-p)^ip^{n-i}\sum_{m\geq i}q^{m-i}(1-q)\\
&=&\sum_{i=0}^{n}{n\choose i}(1-p)^ip^{n-i}\sum_{m\geq 0}q^{m}(1-q)\\
&=&\sum_{i=0}^{n}{n\choose i}(1-p)^ip^{n-i}\\
&=&1
\end{array}$$


texts: Does simplex algorithm run in polynomial on Bipartite Perfect matching polytope?

texts:
It is well known that simplex algorithm runs in exponential time in worst case.

However are there situations (necessary and sufficient conditions) where simplex algorithm runs in polynomial time?
In particular does the simplex algorithm run in polynomial time on Bipartite Perfect matching polytopes and other non-trivial examples?

Good references are welcome.


texts:
I have a set of $K$ keywords. Each of this keywords can have a set of bids from $1\$,\ldots, N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost are monotonic in bids. Now, the problem is:

Select a bid for each of the keyword such that overall clicks across the keywords are maximized such that the cost is still within a given budget $B$. Let $\text{Clicks}(W_i)$ and $\text{Cost}(W_i)$ denote the clicks and cost on the keyword $i$. Then (informally) the problem is to select a value of bid for each keyword such that \begin{align}\max\sum_{i=1}^{K}&\text{Clicks}(W_i) \\s.t.&~~\sum_{i=1}^{K}\text{Cost}(W_i)\leq B\end{align} Is this a type of knapsack problem? Are there any known heuristic in the literature.

Following is not important for the question (and thus can be skipped), but is for the curious ones to know how I am solving this currently.

Let $S_{ij}$ denote the cost for using bid $j$ for keyword $i$ and let $C_{ij}$ be the clicks for the same. Let $x_{ij}$ be the indicator variable for using bid $j$ for keyword $i$. Then among variables $x_{i1},\dots,x_{iN}$ only one can be non-zero (i.e. $x_{ij}=1$) whereas the rest is zero (since only one bid can chosen for keyword).

Thus, the whole problem can be formulated mathematically as

\begin{align}\max_{x_{ij}}~&\sum_{i=1}^{K}\sum_{j=1}^{N}x_{ij}C_{ij} \\s.t.~~\sum_{i=1}^{K}\sum_{j=1}^{N}&x_{ij}S_{ij}\leq B\\\sum_{j=1}^{N}x_{ij}=1&~~\forall i\in \{1,\dots,K\}~~,~~x_{ij}\in\{0,1\}\end{align}

Last, two constraints ensure they are indicator variables and only one bid is chosen for a given keyword. Solving this should solve the original problem.


texts:
The syntactic monoid of a language $L \subseteq X^*$ is defined as the monoid obtained from the congruence relation
$$
 u\ \tilde{}\ v \ \mbox{ iff }\ \forall x,y \in X^* : xuy \in L \leftrightarrow xvy \in L.
$$
How to compute this in general? For regular languages I just know an approach via the minimal automaton, from which you compute the transition monoid. More concretely let $\mathcal A = (X, Q, f, q_0, F)$ a DFA, from the state vector $(q_0, q_1, \ldots, q_n)$ compute the closure with regard to
$$
 (q_0, q_1, \ldots, q_n) \cdot w = (f(q_0,w), f(q_1, w), \ldots, f(q_n,w))
$$
and $w \in X^*$. Then the tupel $(q_0, q_1, \ldots, q_n)$ corresponds to the identity element of the monoid and the tupels $(q_0, q_1, \ldots, q_n) \cdot x$ for $x \in X$ correspond to the generators of the monoid. Each tupel corresponds to a minimal word, the product of two tupels $q, q'$ is defined by taking some word $w$ which represents $q'$ and compute $q\cdot w$ (this works because $[u] = [v]$ iff $f(q,u) = f(q,v)$ for all $q$ in the minimal automata). Or more simple set $f_w(q) := f(q,w)$, then $f_u(f_v(q)) = f_{vu}(q)$, the transition monoid is $\{ f_w : w \in X^* \}$ under functional composition.

Two question:

i) Are there other ways without using an automata as intermediate step to compute the syntactic monoid,

ii) This just works for regular languages, how to proceed for non-regular language? (okay for languages like $\{a^nb^n : n \in \mathbb N\}$ one could imagine an infinite automata and proceed, but that does not works in general)


texts:
I am wondering if there is an algorithm that, given a sorted array, allows you to build a binary search tree in linear time?

I am facing a problem where I have about 8 million elements in a file that need to be loaded into a BST so O(n) would be vastly preferable to O(n log n) if it's possible.


texts: Good seating arrangements for sequence of meals and tables of size k for a group of people

texts:
Given a set $S$ of people I'd like to sit them for a sequence of meals at tables of size $k$. (Of course, there are enough tables to sit all $|S|$ for each meal.) I'd like to arrange this such that nobody shares a table with the same person twice. Typical values are $|S|=45$ and $k=5$ and 6 to 10 meals.

Put in a more abstract way, I'd like to find a sequence of partitions of $S$ such that each partition consists of pairwise disjoint subsets of cardinality $k$ and the added global property that any intersection between two such subsets contains no more than one element. I suspect this can be formulated as a graph theoretical or combinatorical problem.

I'd be grateful for a better formulation of the problem and pointers to relevant literature as it is outside of my domain.

The background: this could be used for seating arrangements at Schloss Dagstuhl where many computer scientists come to discuss their research over the course of a week. Currently seating is done randomly and unsurprisingly some people find themselves sitting with the same people twice (or more often) over the course of a week. Also unsurprisingly, we receive some complaints about this and vague suggestions how to improve this. I'd like to understand this better. A stronger formulation of the problem involves optimizing who is sitting next to each other but I believe this is not relevant for tables of size 5.

Outside of the application I think the interesting question is for the maximum number of meals that can be served for a given $S$ and $k$, i.e., how many such partitions exist.


texts: Active learning for inferring a convex optimization formulation

texts:
I was wondering if anybody knows of any relevant references on the general topic of active learning for gradually inferring/updating a convex opt. formulation.
As a specific example, I am thinking of a system where a learner can query an oracle the validity of the current best solution to incrementally learn constraints or coefficients of an LP cost function.
Update
I am interested in problems and methods where we don't have access to the full definition of the problem (e.g. in LP the constraints that define the polytope, or the cost coefficients are unknown). Yet we may be able to iteratively solve the problem by iteratively asking a sequence of questions to an oracle until the last query confirms we have reached an optimal solution (an optimal vertex in LP)


texts: The relationship between QCMA and QMA in the Turing and Communication model

texts:
First my background about computational complexity is still beginner.

Recent paper published by Klauck and Podder [KP14] show that for the first time an exponential gap between computing partial Boolean functions in a QCMA and QMA in communication model. However, Aharonov and Naveh [AN02] conjecture that QMA = QCMA in the Turing model.

[KP14] state the following open problem:

Thus, in order to show that QCMA = QMA; we need nonalgebrizing techniques.

I just don't understand how they relate the communication model with the Turing model?

According to my understanding is that communication model is different than Turing model. that is, we have different results, proofs, etc. therefore, [KP14] argue that any separation in the two-way communication model would imply using non-algebrizing techniques, how could it be?

thanks in advance


texts:
I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. To me it appears that researchers in parameterized complexity are very active (I don't mean that other are not) in terms of number of research papers. I have seen that researchers from communication complexity, arithmetic complexity etc. are also using various parameters to greater extent.

Question :  Is parameterized complexity going to be the future of complexity theory? Future just means number of research papers, number of researchers working in that area etc.

Please note that I am naive and may not be aware of many things.


texts: Chromatic number of a graph where neighbourhood of each vertex is isomorphic

texts:
Consider a graph $G(V,E)$. For any two vertices $v_1 , v_2 \in V$,  the subgraph induced by the neigbourhood of vertex $v_1$, denoted by $G_{v_1}$ be isomorphic to the subgraph induced by the neigbourhood of veretx $v_2$, denoted by $G_{v_2}$.

Now suppose one can color $G_{v_1}$(and $G_{v_2}$) using $k$ colors. Can one upper-bound the chromatic number of the graph $G$ in terms of $k$ (and other graph

EDIT 1: The motivation behind this question is the fact that the chromatic number is upper bounded by max degree of the graph. Therefore it might happen that if the neighbourhood satisfies certain properties (like densely connected?,lot of cycles of all lengths?), may be one can related its chromatic number of graph $G$ to $k$.

Links to related literature will be helpful.

Thanks in advance!


texts: What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they be used to solve instances of NP-complete problems like TSP that von Neumann machines can not solve feasibly in practice?


texts: Proving lower bounds by proving upper bounds

texts:
The recent breakthrough circuit complexity lower-bound result of Ryan Williams provides a proof technique that uses upper-bound result to prove complexity lower-bounds. Suresh Venkat in his answer to this question, Are there any counter-intuitive results in theoretical computer science?, provided two examples of establishing lower-bounds by proving upper-bounds.

  What are the other interesting results for proving complexity lower-bounds that was obtained by proving complexity upper-bounds?
  Is there any upper-bound conjecture that would imply $NP \not\subseteq P/poly$ (or $P \ne NP$)?


texts:
The Isolation lemma of Mulmuley, Vazirani, and Vazirani  can be used to show that certain $\mathsf{NP}$-complete problems can be reduced via randomized polytime reductions to the unique solution version of the problem. This hints that  the promise of a unique solution is not likely to make the problem significantly easier.

A specific example for such a reduction in the Mulmuley, Vazirani, and Vazirani paper (pdf)
 is that CLIQUE can be reduced to UNIQUE CLIQUE via randomized polynomial time reductions. In this sense,  UNIQUE CLIQUE is (almost) as hard as CLIQUE.

  Is there anything similar known about the UNIQUE $k$-COLORABILITY of graphs?

It is worth noting that the promise of unique colorability seems to involve more structural consequences than the uniqueness of the maximum clique.


texts:
I am interested in range searching purely as a black box in another problem. One problem in particular is that of shooting 2D rays among 2D segments. It seems that Agarwal and Matousek have a well known method for doing this in [1] which requires $O(m^{1 + \epsilon})$ time preprocessing and space to answer ray shooting queries for any fixed positive $\epsilon$. It is not clear to me yet (having read the introduction and conclusion of the paper and skimmed the rest), whether this $\epsilon$ arises due to randomization, approximation, or something else. As I said I only need this as a black box and am somewhat trying to avoid becoming an expert in range searching just to know the answer, and since my initial skimming of the paper didn't produce results I decided to ask it here: which of these three is the algorithm: deterministic, approximate, or randomized? If not deterministic, what is the best that can be done deterministically?

[1] Agarwal P. K, Matousek, J. Ray shooting and parametric search. STOC '92 Proc. of the 24th annual ACM symp. on Theory of computing. Pages 517-526


texts: What's the complexity to check whether a matrix is Diagonalizable?

texts:
Given an $n\times n$ matrix $A$ with rational entries. What's the complexity to check $A$ is diagonalizable?

I suspect that this can be done in P, but I do not know any reference. However, a more interesting question is, is there any better complexity class to capture this problem?

Any guidance/comment is welcome! Thanks.


texts:
Is 'Given two codes with alphabet in $\mathbb F_2$ with Generator matrices $G_1$ and $G_2$ do they have the same minimum distance?' in $NP$ or is it in $coNP$ (I can see it in $P^{NP}$)?

If $G_1$ is known to give minimum distance $d$ then the problem 'is the minimum distance with $G_2$ less than $d$?' is $NP$-complete.

Is 'Given two codes with alphabet in $\mathbb F_2$ with Generator matrices $G_1$ and $G_2$ do they have the same number of minimum distance code words?' in $PP$ (I can see it in $P^{PP}$)?

If $G_1$ is known to give $N_d$ number of minimum distance $d$ then the problem 'is the number of minimum distance codewords with $G_2$ greater than $N_d$?' is $PP$-complete.


texts: Are there any implementations for zero-knowledge proofs of NP-complete problems?

texts:
It's been known for a long time that any claim in NP has a zero-knowledge proof for it. Has anybody actually implemented a zero-knowledge proof system for a NP-complete language? Using a search engine, the most relevant thing I could find is this:

www.usenix.org/event/sec10/tech/full_papers/Meiklejohn.pdf

I'm not exactly sure what the scope of ZKPDL, but it looks like it's a combination of many special-purpose zero-knowledge protocols, and that it is not intended to NP-complete. It might turn out to be NP-complete with clauses like "x in [0,1]" and "x*y=z" allowing a reduction from SAT to the languages described there. However, the reduction doesn't seem natural or efficient.

The reason I'm asking this is that I'm currently working on an implementation of a NP-complete zero-knowledge protocol and I want to know what the prior work is.


texts:
What follows might seem stupid (and that probably reflects my poor understanding - so please bear with me)

I had a query on PCP theorem. We know that after the first three steps viz. Degree Reduction, Expanderization and Gap Amplification, we have a constraint graph $G$ with improved gap and huge alphabet size (like $\Sigma^{d^t}$). It is this problem that the alphabet reduction step addresses.

My question is that as outlined in Venkat Guruswami's lecture notes Introduction to Composition, it seems to me that the high level idea is to express the constraint $c_e$ over an edge $e$ as a Boolean constraint over boolean variables. This by itself achieves nothing and we also need to apply the PCP reduction ,$P_e$, on this edge. This "looks like" a recursive invocation of PCP and this is where I start getting a little worried. It seems as this recursive invocation would blow up the alphabet size again.

The authors have offered some explanation by observing that this recursion has a "base case" - namely - the "inner" PCP reduction applies only to constraints of constant size.

(By this I understand that the inner recursion gets invoked only when we are looking at constraints $c_e$ over a single edge which is a binary constraint, but still I have not yet come over the fear that somehow we still might blow up the alphabet size instead of shrinking it). To me, it still seems that a recursive repetition of Gap Amplification step will only make matters worse by blowing up the alphabet size unless we incorporate measures to handle the base case a little differently.

I hope my query  (as silly as it is) is probably clear. Please let me know what essential part am I missing (or have misunderstood).


texts: Rabin's "degree of difficulty of computing a function, and a partial ordering of recursive sets"

texts:
I am looking for:

Michael O. Rabin, "Degree of difficulty of computing a function, and a partial ordering of recursive sets", Hebrew University, Jerusalem, 1960

Summary:

  “We attempt to measure the amount of work inherent in the task of computing a given computable (recursive) function. A notion of degree of difficulty of computing is introduced and studied. The notion is invariant in the sense that it is independent of the idealized computers (Turing Machines) used for computing the functions in question. Applications are made to the classification of solvable decision problems (recursive sets) according to relative difficulty.”

I couldn't find a copy online or at our library.


texts:
We have $m$ list of integers $L_1,\dots,L_m$ and each list $L_i$ contains $n$ distinct integers $L_i(1),\dots,L_i(n)$.

You are given two integers $a$ and $b$ with $b<a$ and we know $n=O(2^{(\log b)^\alpha})$ and $m=O({(\log b)^\beta})$ for $0<\alpha,\beta<1<\alpha+\beta$.

I want to check to see if I can pick one integer from each list to check if product mod $b$ is $a\bmod b$.

Is there a faster than $n^m$ brute force way to search for this? Is this NP hard (Andrew below sort of gives a pseudo polynomial algorithm)?


texts:
I know of the Chomsky hierarchy, which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^*$ made of words on an alphabet $\Sigma$.

Is there a similar hierarchy for grammars/parsers which are specifically taylored for nested words or trees?  In particular, this hierarchy should include tree automata, perhaps streaming tree automata, the algorithms used to apply CSS rules...

As I am planning to implement parsers for one/some of the steps in the hierarchy, I am very interested also in the algorithmic complexity of parsers for those grammars.  I might use this as a basis for a CSS-like functionality in LaTeX.


texts: how to formalize the class(?) of computational models and their equivalence

texts:
Introductory books to theoretical computer science usually introduce a the Turing machine and some of its variants, as well as the Random Access machine as computational models. Sometimes more specialized or even exotic systems (such as quantum computers) can be found briefly sketched.

The equivalence of these models ( say two models A and B ) is usually proven by mimicing the mechanics of A with the "gears" of B and then providing "cheap" conversion functions which convert input of A to input B and output of B back to output A - the same is then done for A and B reversed.

Whereas proofs provide valid statements about well-defined mathematical objects, I don't think they prove what is ought to be proved, namely the equivalance of two computational models, because that question is non mathematically defined. I doubt that this can be done.

First of all, the conversion functions between the different input/output formats cannot necessarily be formalized as computations, because they act in "both worlds" (say binary strings and a cell setting in the game of life), and thus require a new computational model for themselves. Hence at least two further computational models are introduced. The triviality of the conversion functions doesn't seem be formalized. - One might argue that the conversions are the most vital part of the proof, because the "mimicry" of one model A within another model B has no mathematicly well-defined relation with the model A.

Second, I wonder whether the "class" of computational models can be formalized. I don't think it is a set, because, for example, you could build several Turing machines with 0 and 1 represented by arbitrary inequal sets. - One might define a category of computational models, with the arrows, say from object A to object B, present when A can be simulated by B. This raises the question what we would want the objects to be. I do not know.

I regard these points, (i) non having a formal definition for the conversion functions to be trivial, (ii) having no definition of a (Turing-equivalent) model of computation as unsatisfying.

Does anybody know whether and how this has been treated in literature so far? I am aware this touches what to understand the question of what to call "computation", but so do the usual practices in computer science anyway, in my opinion.


texts: Sum of products with bounded coefficients

texts:
The following lemma is not hard to prove.

Lemma : Let $c_1 \neq c_2 \neq \dots \neq c_r \in [n]$ and $k \in [n]$. If $m_1, m_2, \dots, m_r$ are integers (some of them might be negative) such that $m_1c_1 + m_2c_2 + \dots + m_rc_r = k$, then $\exists$ integers $m'_1, m'_2, \dots,m'_r$ satisfying $m'_1c_1 + m'_2c_2 + \dots + m'_rc_r = k$ such that $|m'_1|+|m'_2|+\dots+|m'_r| \leq poly(n)$. Here $poly(n)$ means $n^c$ for some positive constant $c$.

I am guessing that the above lemma is well known. I am looking for a reference of the above lemma and the best possible bound for $poly(n)$.


texts: Let $G=(V,E)$ be a directed acyclic graph. Two vertices is transitive if there is a directed path between them. A Path Cover for a Set of Transitive Pairs (PCSTP) is a set of directed paths such that every pair of transitive vertices belongs to at least one path. The minimum PCSTP problem consists of finding a PCSTP for G having the least number of paths. Is this problem NP-hard?


texts: Maximum number of internally vertex-disjoint odd length s-t paths

texts:
Let $G$ be an undirected simple graph and let $s,t \in V(G)$ be distinct vertices. Let the length of a simple s-t path be the number of edges on the path. I am interested in computing the maximum size of a set of simple s-t paths such that each path has odd length, and the vertex sets of each pair of paths pairwise intersect only in s and t. In other words, I am looking for the maximum number of internally vertex-disjoint odd-length s-t paths. I think that this should be polynomial-time computable by matching or flow-based techniques, but I have not been able to come up with an algorithm. Here is what I know of the problem.

We may replace the restriction to odd length by even-length; this does not really affect the problem since one transforms into the other if we subdivide all edges incident on s.
If there is no restriction on the parity of the paths then Menger's theorem gives the answer, which can be obtained by computing a maximum flow.
The problem of determining the maximum number of vertex-disjoint odd-length cycles which pairwise intersect only at a given vertex v is computable in polynomial time by a matching trick: build a graph G' as the disjoint union of $(G - {v})$ and $(G - N_G[v])$, adding edges between two copies of the same vertex; a maximum matching in this graph of size $|V(G)| - |N_G[v]| + k$ implies that the maximum number of odd cycles through $v$ is $k$; this construction is described in the proof of Lemma 11 of On the odd-minor variant of Hadwiger’s conjecture.
If the graph is directed then testing for the existence of a single even-length s-t path is already NP-complete.
The paper The even-path problem for graphs and digraphs by Lapaugh and Papadimitriou might be relevant, but unfortunately our library does not subscribe to the online archive and we do not have a paper copy.

Any insights will be much appreciated!


texts:
I need some order on binary strings such that if I have a small (but superlinear in their length) number of sufficiently different strings, the order will stay the same if I change a few bits in the strings.

For example, lexicographic order does not satisfy this property because it may be possible to change the order of the string by changing just one bit.

On the other hand, order according to the number of ones is not good either because it only works for linear number of strings.

Is there such an ordering?

Edit: A solution which only works for random strings is also of interest to me.


texts:
I just read the "Is integer factorization an NP-complete problem?" question ... so I decided to spend some of my reputation :-) asking another question $Q$ having $P(\text{Q is trivial}) \approx 1$:

If $A$ is an oracle that solves integer factorization, what is the power of $P^A$?

I think it makes RSA-based public-key cryptography insecure ... but apart from this, are there other remarkable results?


texts: Spectra of Cayley Graphs for non-Abelian Groups

texts:
There appears to be much interest in the subject of the spectra of Cayley graphs. Indeed it appears that the spectra are highly related or may be computed through the irreducible representations of the underlying group in the graph, but I cannot seem to find a general formula for such a computation. For instance an old paper on the spectra of Cayley graphs http://www.sciencedirect.com/science/article/pii/0095895679900790 seems to compute the sum of eigenvalues.

In particular, I am interested in computing the largest and smallest eigenvalues of a particular Cayley graph of the symmetric group with a symmetric but not normal generating set. Is the above the only tool to do something like this? I am struggling to find anything more.


texts: Polyhedral embedding from graph degree sequence

texts:
Given: A degree sequence.

Wanted: A graph and a polyhedral embedding of this graph (described by a rotation system or something equivalent). By polyhedral embedding I mean only the combinatorial concept. See here.

Is there a fast way to do this? I tried a backtracking approach, adding edges one at a time, but it is too slow. It becomes intractable for a 3-regular graph of 30 vertices.


texts: Libraries for programming automata and Turing machines

texts:
What are the most useful libraries around for coding related to automata and Turing machines?

By useful I mean the number of functions and algorithms supported by it.


texts:
Let's say we discover alien civilizations that are able to send and receive messages using an interstellar digital communications channel. (Say using modulated radio waves, laser pulses, re-positioning stars in various orbits, what have you.) Let's assume we have decided to make contact with them.

Once we initiate a dialog, how would we go about establishing a communications protocol and language? What methodology would we use to agree on a basic vocabulary and ways of expressing logical ideas? Is it ad-hoc or is there some way to optimize the process of establishing a common language based on symbolic manipulations. We would want to agree on a language quickly and minimize the resources required to encode and send messages (since they're quite slow to send).

Next, reciprocity: Once we have a shared language, how would we make sure that both sides reciprocate in trading secrets? That is, we don't want to be in a situation where we give away valuable technology without receiving anything in return. Can both sides prove that they posses certain technology? Is there a way to send results piecemeal, gradually, so that each side can have increasing confidence in the value of the message?


texts: Universal constant for bivariate testing

texts:
In the seminal paper of Polishchuk and Spielman where they give a construction of nearly linear sized $PCP$ for an $NP$ problem, one of the key ingredients is a low-degree test for bivariate polynomials.
Essentially, to test if the function values on a set of evaluation points correspond to a bivariate polynomial of maximum degrees $(d,d)$, we check whether the restriction of this to axis parallel lines (i.e. rows and columns) are all degree $d$ univariate polynomials (This is an equivalence condition in the absolute case, which is easy to verify. The interesting part is the robustness of the test: that is, if the function values on the restrictions to axis parallel lines agree with low-degree polynomials on "most" points (that is, close to Reed-Solomon codewords), then there is a bivariate low degree polynomial (a Reed-Muller codeword) which also agrees with the function on most evaluation points). The proof of robustness uses the notion of error-corrector polynomial to capture the "bad" evaluation points, polynomial interpolation and then uses resultants. For more details check out sections 2,3,4,5 in http://cs.yale.edu/homes/spielman/PAPERS/holographic.pdf

In a follow-up paper by Sudan and Ben-Sasson (lemma 6.13 and section 6.6 in http://people.csail.mit.edu/madhu/papers/2005/rspcpp-full.pdf) they extend the basic argument of Polishchuk-Spielman to obtain a universal constant relating the distances of the function from row, column polynomials and the Reed-Muller polynomial. They claim a basic proof using the constant taken to be 128, without optimization.
Then in a follow-up paper (by Ben Sasson et al here http://eccc.hpi-web.de/report/2012/045/, in section 10 (more precisely section 10.3)) they again talk about optimizing this universal constant and get it down to 10.24.

My question is,

Where did the universal constant exactly come into the picture at all, and how did they use the value of 128 in the first place?

It seems to me (and I am sure I'm wrong here but not clear why) that one could have proved that same result without assuming anything about the size of the constant? It would be very helpful if someone could make that (simple and short) proof more explicit so that one sees how the constant and its assumed value enters the proof. Thanks in advance.


texts:
In [1], Turan shows that the sensitivity (called "critical complexity" in the paper) of a graph property is strictly greater than $\lfloor {1\over 4} m \rfloor$ where $m$ is the number of vertices in the graph. He goes on to conjecture that any non-trivial graph property has sensitivity $\geq m-1$. He mentions that this has been verified for $m \leq 5$. Has any progress been made on this conjecture?

Background

Let $x$ be a binary string in $\{0,1\}^n$. Define $x^i$ for $1 \leq i \leq n$ to be the string obtained from $x$ by flipping the $i^{th}$ bit. For a boolean function $f: \{0,1\}^n$ \to $\{0,1\}$, define the sensitivity of $f$ at $x$ as $s(f;x) := |\{i : f(x) \neq f(x^i) \}|$. Finally, define the sensitivity of $f$ as $s(f) := \mbox{max}_x\; s(f;x)$.

A graph property $\mathcal P$ is a collection graphs such that if $G \in \mathcal P$ and $G'$ is isomorphic to $G$ then $G' \in \mathcal P$. We can think of a graph property $\mathcal P$ as the union of properties $\mathcal P_m$ where $\mathcal P_m$ is the subset of $\mathcal P$ consisting of graphs with $m$ vertices. Further, we can conceive of a graph property $\mathcal P_m$ as a boolean function on $\{0,1\}^n$ where $n = {m \choose 2}$. We can encode a graph on $m$ vertices in a binary vector of length $n$; each entry in the vector corresponds to a pair of vertices and the entry is $1$ iff that edge is present in the graph. Thus, the sensitivity of a graph property is its sensitivity qua boolean function.

Turan, G., The critical complexity of graph properties, Information Processing Letters 18 (1984), 151-153.


texts: Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus?

texts:
I know very little about what I am talking about in what follows, so I appreciate any all help in pointing out all of my mistakes -- otherwise I won't be able to learn more and advance in my knowledge of these interesting subjects.

I want to learn about lambda calculus because it seems like an interesting way to think about functions in general, and because a generalization called the stochastic $\pi$ calculus studied by Luca Cardelli and others seems to allow many computational interpretations of biology, something which I am really interested in. Also other reasons, like wanting to learn and understand functional programming, in order to have an alternative to C++ which I dislike.

However, I just learned that type theory, at least as stated by Lof, is supposed to be a way to formalize intuitionistic logic/constructive mathematics, which rejects the Law of the Excluded Middle and even the Axiom of Choice. My background is more in mathematics than computer science, so although I can see how having to construct something to prove that exists is an acceptable restriction for people interested primarily in computation, I am really uncomfortable with having to give up proof by contradiction and the Law of the Excluded Middle. Perhaps that makes me old-fashioned, and my grandkids will laugh at me for this concern, but proof by contradiction can be very useful and is how I learned a lot of the math which I know.

  Is there a way to learn about $\lambda-$calculus and type theory while at least being agnostic about the Law of the Excluded Middle and not outright rejecting it?

The discussion on p.9 of the Homotopy Type Theory book seems to say something to the effect that Univalent Foundations and Homotopy Type Theory can be compatible with the Law of the Excluded Middle and the Axiom of Choice, even though they contradict the univalent axiom? Needless to say I did not quite understand the argument about (-1)  types and thus am still somewhat skeptical and unconvinced.

Also, in one of his lectures at the Oregon Programming Language Summer School posted on youtube, Professor Awodey, one of the big names behind the IAS's Homotopy Type Theory/Univalent Foundations Project, seems to identify the Heyting algebra as underlying logic, rather than the Boolean algebra. I read somewhere else (I forgot where unfortunately), that Heyting algebra is what results if one rejects the Law of the Excluded Middle, and thus presumably founding logic upon Boolean algebra means accepting the Law of the Excluded Middle.

Ideally I would prefer to not have to choose between $\lambda$-calculus and Boolean algebra, since the latter underlies most of my understanding of logic, and is also the basis for probability theory, which I know very well and would not like to give up or reject as half-baked. Also I thought Boolean functions were a very hot topic of computer science research, so it seems kind of strange that some computer scientists would prefer Heyting algebra.

These questions might be relevant:      Where is the proof that Coq + Excluded Middle is consistent
Heyting algebra in simply typed lambda calculus
Can boolean algebra be expressed in simply typed lambda caclulus?

If they even answer my question, would you mind explaining to me how (as if I were five, so to speak)? I don't quite understand the discussions on them.


texts:
the Hidden Subset Problem (HSP) covers several known problems (e.g. Integer Factorization Problem, Discrete Logarithm Problem) as a special case:
Definition [Hidden Subgroup Problem (HSP)] Let $\mathbb{G}$ be a group and $\mathbb{H}$ an unknown subgroup of $\mathbb{G}$, i.e., $\mathbb{H} \leq \mathbb{G}$. Let $S$ be any set and $f$ be a function that maps the group elements of $\mathbb{G}$ to $S$, i.e., $f: \mathbb{G} \rightarrow S$. The function $S$ has the special property that it can distinguish cosets of $\mathbb{H}$: $$ f(e_1) = f(e_2) \Leftrightarrow e_1\mathbb{H} = e_2\mathbb{H} $$ The Problem is, given $\mathbb{G}$ and access to the function $f$, to determine a generating set for the subgroup $\mathbb{H}$.
I found several papers which show how to instantiate the involved groups and functions, for example in case of the Integer Factorization Problem:
$$\mathbb{G} = \mathbb{Z}^+_{\varphi(N)}; \mathbb{H} = \langle r\rangle^+; S = \mathbb{Z}^*_N, f(x)=g^x\pmod{N}$$
whereof the integer $r$ is the order of the multiplicative group generated by $g$.
I am trying to find a direct HSP approach to the RSA problem, without to find the order of the subgroup or to factorize the modulus.
RSA Problem: Given an RSA modulus $N$ and a public exponent $e$ and an integer $C$, find $m$ such that $m^e \equiv C \pmod{N}$
I came up with the following solution, but i am not sure if it is valid:
Let $\mathbb{G} = \mathbb{Z}$ and $\mathbb{H} = \{m, m+N, m+2N, m+3N,\ldots\}$, $S = \mathbb{Z}^*_N$ as well as $f(x) = x^e\pmod{N}$. The group operation that is defined on $\mathbb{G}$ is $\circ_m(a,b) := a+b-m$. So $\circ$ makes $\mathbb{H}$ a subgroup of $\mathbb{G}$ (neutral element is $m$ and inverse is $a^{-1} = 2m-a$). And $f$ can distinguish $N$ cosets of $\mathbb{H}$: $$c\mathbb{H} = \{m+c, m+c+N, m+c+2N,\ldots\}$$. So maybe some technical work has to be done to restrict the size of $\mathbb{G}$ to make it work. What do you think? (I am not sure, since the group operation involves $m$.)
Regards,
Etsch


texts: Is $LL(k)$ for large $k$ considered harmful? If so, why?

texts:
I took a course touching on lexer and parser theory this semester (a sizeable chunk was devoted to regexes and other FSA, but context-free grammars were covered as well).

Over the course of the semester, the prof mentioned that grammars should be optimized to $LL(1)$ whenever possible. Unfortunately, he never explained properly why such grammars are "better." Wouldn't a greater lookahead make for more effective predictive parsing? Or is it considered harmful taking into account physical resource (RAM, CPU) constraints? Or do parsers with more lookahead simply become more complex than they're worth?


texts: Are there NP-complete problems with quasi-polynomial expected time solutions?

texts:
I'm wondering if there exists an exact algorithm for some np-complete problem with  quasi-polynomial time complexity.

My best guess is 'no', because if there was one (with a reasonable C, not any C), probably to find a way to improve the time complexity to polynomial would be just a matter of time, thus, the P vs. NP question will be already closed.

I researched on internet and seems there is no quasi-polynomial solution for any of the known np-complete problem (I do found pseudo-polynomial algorithms)

So, could somebody point me to some exact quasi-polynomial algorithm for some np-complete problem if such algorithm exists?

thanks!


texts: Is it necessary to call matrix multiplication $n$ times to find a claw

texts:
A claw is a $K_{1,3}$. A trivial algorithm will detect a claw in $O(n^4)$ time. It can be done in $O(n^{\omega+1})$, where $\omega$ is the exponent of fast matrix multiplication, as follows: take the subgraph induced by $N[v]$ for each vertex $v$, and find a triangle in its complement.

As far as I know, these basic algorithms are only known. Spinrad listed in his book "efficient graph representations" the detection of a claw in $o(n^{\omega+1})$ time as an open problem (8.3, page 103). For the lower bound, we know that an $O(n^c)$-time algorithm will imply an $O(n^{\max{(c,2)}})$-time algorithm for finding a triangle. So we may consider $\Omega(n^\omega)$ as a lower bound.

Question:

Is there any progress on this. Or any progress on showing it's impossible?
Are there other natural problems with $O(n^{\omega+1})$-time algorithms which are the best?

Remark:

I'm explicitly asking for the detection of a claw, instead of the recognition of claw-free graphs. Although an algorithm usually solves both, there are few exceptions.
It's claimed in Handbook of Algorithms and Theoretical Computer Science that it can be found in linear time, but it was only a typo (see "efficient graph representations").


texts:
I'm a UK student who will soon be going to university and would like some advice from people who have already done this on what course to take.

I really enjoy the theoretical side of computer science, especially the more mathematical concepts. I do enjoy the other area such as algorithm design and programming as a hobby, but I wouldn't really want to be a programmer/tech support/algorithm designer as a job. Those sort of jobs are just not for me. I would prefer a research type job, maybe in quantum computing. I currently' finishing my A-levels in physics and further maths, and I'm expecting A*s in both fields.

Sorry if all this is a bit vague, but I would like some ideas from people about what the best degree is to take to get where I want, and what sort of jobs are out there. Also, if anyone knows what's some universities in UK to study this sort of thing at , I'd very much appreciate the advice.


texts: Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?

texts:
If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice though that, in general, encoding the input for $n$-variable 3-SAT or $n$-vertex 3-COLORING takes something like $O(n\log n)$ bits. For example, to describe a sparse graph as input to 3-COLORING, for each edge we would have to list its endpoints. So the lower bound is not exponential in the length of the input. Therefore, my question is the following:

Is there a problem for which no $2^{o(n)}$ algorithm exists for inputs of length $n$ bits (assuming ETH)?

Ideally, the problem would be in NP (no cheating with succinct NEXP-hard problems!) and be reasonably natural, but I won't be picky.

Let me also note that after digging around I found that there are efficient ways to encode planar graphs with $O(n)$ bits. So, if one could find a problem that takes time exponential in the number of vertices even for planar graphs, the question would be settled. However, because planar graphs have treewidth $O(\sqrt{n})$, most natural problems have sub-exponential algorithms in this case.


texts: Poly time superset of NP complete language with infinitely many strings excluded from it

texts:
For any arbitrary NP complete language is there always a polytime superset the complement of which is also infinite?

A trivial version which does not stipulate the superset to have infinite complement has been asked at https://cs.stackexchange.com/q/50123/42961

For purposes of this question, you can assume that $P \ne NP$.  As Vor explained, if $P = NP$ then the answer is "No".  (If $P = NP$, then $X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$ is NP-complete. Clearly there is no superset of $X$ which is infinite and has an infinite complement, as the complement of $X$ has only a single element.)  Thus we can focus on the case $P \ne NP$.


texts: If we know some lower bound of the solution of a problem in centralized setting, what can we say about the lower bound in a distributed setting?


texts: Exponential blowup in Simple Proof of a theorem of Statman by Mairson

texts:
I'm studying "A simple proof of a theorem of Statman" by H.G. Mairson.

At page 4, he encodes set/type theory in lambda calculus.
In particular, note che "op" trick in the definition of $eq_{k+1}$.

Mairson stress the fact that this trick is essential, because writing $subset_{k+1}$ twice would cause exponential blowup in term size.
I'm asking why! That would not just double the term size?


texts:
While trying to check what is the state of art in formal verification, it seemed to me that there were actually no breakthroughs in decades. For example, here http://www.comp.nus.edu.sg/~hobor/Publications/2011/logicfs.pdf it is stated, that 5-line (imperative) factorial program needs something like 100 lines of Coq code. And I consider Coq to be one of the best tools out there! Adam Chlipala's book (http://adam.chlipala.net/cpdt/) tries to convince, that Coq is much easier, than many think.

So, the first question goes, are there any advances in the field (and what they are), which would make formal methods practical any time soon?

If no, then has any researcher explained this seeming discrepancy between the fact, that programming languages become easier to use (become higher and higher level, handle specific domains better), while formal verification methods seemingly remain in the seventies of last century? (I guess, on the functional programming front situation is a bit better, but still.)

My own speculation on this paradox is that maybe some fundamental, powerful computation formalism is yet to be discovered (that is, the problem lays with the language). Another answer could be, that the complexity gap is inherent in the mathematics, and no development of the theory could destroy it. Personally, I do not believe in the latter case, because all the history of development in mathematics. Added: Third possibility is that for some reason re-use of formal proofs and tactics, finding new axioms is difficult. In "normal" software it is possible to share libraries, which are used to build more complex structures, and these components are stacked together to form even bigger systems. "Normal" software is times easier to develop now than 30-40 years ago.

Would be interesting to know, if I have overlooked something.

EDIT: It may well be, that some narrow problem domains enjoy nice, easy-to-use verification tools, for example, languages with regular grammars may be easy to deal with. This question is not about such cases.

To narrow my question, lets consider one toy example, which is surely broadly known, and which I consider general enough kind of programming problem. Suppose, I want to implement an ADT Queue using two Stacks (another ADT). I write down a solution (it's a couple of methods: enqueue and dequeue). Now, I want a formal proof, that my solution is indeed a Queue (suppose, I have some kind of description of it's behavior). I can program it from assembler to, say, APL and get a size from 2 lines to 100. Now, how long will be the proof? I bet, it's about a page on paper. But what if I have semi-automatic tool? I guess, the proof will be (for imperative case) almost as long as assembler program, will need several insights to come with and the result is much more cryptic in case one needs to manually re-check. And of course, I am not sure how type-checking is going to help in this case.

EDIT2: Some notable results from comments, thanks to commenters:

Conflict-Driven Clause Learning - makes SAT powerful (year 1999)
Separation Logic - "local reasoning" (2002)


texts: Non-trivial applications of Bloom filters

texts: Does anyone have some nice examples of modifying algorithms that employ a set data structure to instead employ a Bloom filter?  In other words, the damage done by the Bloom filter's false positive rate requires an interesting trick to accommodate.


texts: Textbook/resources for a beginning researcher in (Machine) Learning Theory

texts:
I'm looking to begin understanding basic concepts, notions, results and definitions in the area of Computational Learning Theory (or the theory of Machine Learning), as is done in the theoretical computer science community (those represented mainly in STOC/FOCS). My goal is to do research in the area from the strictly theoretical perspective.

What kind of textbooks/resources, basic papers are available for me?
What kind of knowledge I need to have? Algorithms theory, or computational complexity theory? Or probability/probabilistic-methods (a la, Alon-Spencer)?

I have only seen a single textbook An Introduction to Computational Learning Theory by Michael Kearns and Umesh Virkumar Vazirani (1994), but I don't know if this is adequate/up to date.

So the question shortly is:
How can a researcher start obtaining knowledge in theoretical Machine Learning? (Note I'm not interested as of now in any form of applications of ML.)


texts: Reference request: Skeptics of classical threshold theorem

texts:
Early classical computing had skeptics, or at least cautious researchers, that were skeptical reliable computing results were possible. Scott Aaronson references this in a page on his site:

A: The only reason we don't need fault-tolerance machinery for classical computers is that the components are so reliable, but we haven't been able to build reliable quantum computer components yet. Presumably, if we could build extremely reliable components, we wouldn't need error correction and fault-tolerance technology.
Scott: Yes, that's what I would say. In the early days of classical computing, it wasn't clear at all that reliable components would exist. Von Neumann actually proved a classical analog of the Threshold Theorem, then later, it was found that we didn't need it. He did this to answer skeptics [emphasis mine] who said there was always going to be something making a nest in your JOHNNIAC, insects would always fly into the machine, and that these things would impose a physical limit on classical computation. Sort of feels like history's repeating itself.

source (And here is a related question about where that paper first appeared).
My request is for published research article (references) that are skeptical classical fault tolerant computing is possible, or names of individuals advocating for skepticism at the time.


texts: Notion of associativity for ternary relations?

texts:
Consider the problem $\def\GEN{\mathrm{GEN}}\GEN$: given a ternary relation $R \subseteq X^3$ and a subset $S \subseteq X$, is the closure of $S$ with respect to $R$ equal to the whole set $X$? By this we mean the smallest set $S \subseteq C \subseteq X$ such that $u,v \in C$ and $R(u,v,w)$ implies $w \in C$.

It is known that $\GEN$ is $\mathsf{P}$-complete for arbitrary relations, and $\mathsf{NL}$-complete when the relation $R$ expresses an associative composition law $*$ (i.e. $R(u,v,w)$ holds iff $w = u*v$).

We can define a notion of "associative relation" extending the above situation, as follows: say that $R$ is associative if for each $a,b,d,e \in X$, we have

$\exists c. (R(a,b,c) \wedge R(c,d,e)) \Rightarrow \exists c. (R(a,c,e) \wedge R(b,d,c)).$

So I would like to know: what is the complexity of the $\GEN$ problem for such relations?
Also, is it possible to define a notion of "$k$-associative relations" that would induce a hierarchy in the space complexity of the $\GEN$ problem?


texts: How hard is it to count the number of factors of an integer?

texts:
Given an integer $N$ of length $n$ bits, how hard is it to output the number of prime factors (or alternatively number of factors) of $N$?

If we knew the prime factorization of $N$, then this would be easy. However, if we knew the number of prime factors, or the number of general factors, it is not clear how we'd find the actual prime factorization.

Is this problem studied? Are there known algorithms that solve this question without finding the prime factorization?

This question is motivated by curiosity and partially by a math.SE question.


texts:
I have a network flow (with min and max capacities) where the only transport units flowing are within a cycle (of flow value 2). The source of the network does not send out any transport units into any direction and the transport units getting into the sink are all getting sent away directly, so 0 transport units "stay" there. Now my question is, is such a flow allowed as long as minimium neccesarry flow (given by min capacities) exists and the amount of incoming transport units is equal to the amount of outgoing transport units? Or is a flow network where the source doesn´t send out any transport units not permitted?

I look forward for any help.


texts: How does the CHC Algorithm deal with child populations with lower fitness?

texts:
I am basing my question on the pseudocode for the CHC Adaptive Search Algorithm by Eshelman given in this answer by deong:

delta = k/4               # k = chromosome length
while not done
    create new child population
    for i = 1 to n/2     # n = population size
        select p1, p2 from population without replacement
        if hamming_distance(p1, p2) > delta
            c1, c2 = HUX crossover(p1, p2)
            insert c1, c2 into child pop
        end if
    end for
    if child pop is empty
        delta = delta - 1
    else
        take best n individuals from union of parent and child populations as next population
    end if
    if delta < 0
        keep one copy of best individual in population
        generate n-1 new population members by flipping 35% of the bits of the best individual
        delta = k/4
    end if

How does this algorithm deal with situations where the child population has lower fitness than the parent population?

Consider a population of two parent with a large enough hamming distance to produce children. Now if both children have a lower fitness than their parents, doesn't the survivor selection ("take best n") select the same parents again, resulting in an infinite loop?


texts: Implementation of a Logical Hierarchical Hidden Markov Model

texts: Is anyone aware of any implementations of algorithms for learning and/or processing a Logical Hierarchical Hidden Markov Model, as described in this paper? I've found dozens of papers about Logical Hidden Markov Models, Hierarchical Hidden Markov Models, and every variation in between, but no one's published any code.


texts: Finding uniformly random perfect matching of a graph

texts:
Problem: Suppose that we have a graph $ G $ which admits at least one perfect matching. I would like to know if there is an algorithm that allows to find any perfect matching of this graph uniformly at random in polynomial-time.
It seems from this discussion: Complexity of Uniform Generation of Perfect Matchings that the general problem is open. However, the structure of this graph is very specific, so maybe there is a way to address adequately this question (I describe the structure of the graph below).
Motivation: in this reference by Kannan et al. (1999), the authors propose a way to transform the problem of finding a random graph with a given degree sequence into finding a perfect matching of a graph built from the degree sequence using some gadgets.
Finding a polynomial solution to the perfect matching problem would give us a way to find a polynomial solution to finding a random graph with a given degree sequence.
$G$ structure: graph $G$ is built in the following way. Suppose you have a graphic degree sequence $(d_1,...,d_n)$, consider a complete graph with $n$ nodes, then

replace each edge $(u,v)$ by a path $ (u,x_{uv},y_{uv},v) $,
with $d_u$ the degree of $u$, replace each vertex $u$ by $ (n-1-d_u) $ "mini-vertices" $u_1,...,u_{n-1-d_u}$ and connect each mini-vertex to all $ x_{uv} $,
the resulting graph is $G$.

For instance, supposing vertex $a$ is such that $(n-1-d_a) = 4$, vertex $b$ is such that $(n-1-d_b) = 3$ and vertex $c$ is such that $(n-1-d_c) = 2$ then edges $ (a,b) $ and $ (a,c) $ would be transformed as in the figure below (for the sake of readability I only represent the transformation of these two edges).

It can be checked that finding a perfect matching in $G$ is equivalent to finding a simple graph with the degree sequence $(d_1,...,d_n)$: if the edge $ (x_{uv},y_{uv}) $ belongs to the perfect matching in $G$, vertices $u$ and $v$ are connected in the graph with degree sequence $(d_1,...,d_n)$, otherwise they are not.
Additional remarks:

having a graphic degree sequence implies that at least one graph satisfies the degree sequence in the original problem, thus a perfect matching of $G$ exists,
in general $G$ is not bipartite,
it is possible to solve the problem of finding a random graph with a given degree sequence using an appropriate Monte Carlo Markov Chain sampling method, thus it is also possible for the perfect matching problem. However, there is no easy bound to the convergence time of the algorithm, so we want to avoid this type of sampling algorithm.


texts: Algorithm for Minimum Diameter Spanning Tree

texts:
Given a undirected and connected graph G, find a spanning tree whose diameter is the minimum.
How to solve this problem


texts: Efficient way to generate random planar cubic bipartite graphs

texts:
3-regular bipartite planar graphs appear in a variety of NP- / #P-complete problems. Suppose one wants to test the complexity of these problems via numerical experiments. Is there an efficient way to generate random planar cubic bipartite graphs?

I only know of algorithms that can efficiently generate random graphs with only subsets of the set of properties {cubic,planar,bipartite}, and it seems that generating those and then naively testing for the remainder of the properties would be terribly inefficient if one wants graphs with >100 vertices.


texts: Computing a transitive completion / path existence oracle

texts:
There has been a few questions (1, 2, 3) about transitive completion here that made me think if something like this is possible:

Assume we get an input directed graph $G$ and would like to answer queries of type "$(u,v)\in G^+$?", i.e. asking if there exists an edge between two vertices in the transitive completion of a graph $G$? (equivalently, "is there a path from $u$ to $v$ in $G$?").
Assume after given $G$ you are allowed to run preprocessing in time $f(n,m)$ and then required to answer queries in time $g(n,m)$.

Obviously, if $f=0$ (i.e. no preprocessing is allowed), the best you can do is answer a query in time $g(n)=\Omega(n+m)$. (run DFS from $u$ to $v$ and return true if there exists a path).
Another trivial result is that if $f=\Omega(min\{n\cdot m,n^\omega\})$, you can compute the transitive closure and then answer queries in $O(1)$.
What about something in the middle? If you are allowed, say $f=n^2$ preprocessing time, can you answer queries faster than $O(m+n)$? Maybe improve it to $O(n)$?
Another variation is: assume you have $poly(n,m)$ preprocessing time, but only $o(n^2)$ space, can you use the preprocessing to answer queries more efficient than $O(n+m)$?

Can we say anything in general about the $f,g$ tradeoff that allows answering such queries?

A somewhat similar tradeoff structure is considered in GPS systems, where holding a complete routing table of all pairwise distances between locations is infeasible so it's using the idea of distance oracles which stores a partial table but allow significant query speedup over computing the distance of the whole graph (usually yielding only approximated distance between points).


texts: Reference to lower bound on separator in a grid?

texts: It is easy to verify that given the d dimensional grid of the integer points $\{1,\ldots,n\}^d$, with the regular adjacency, one can find a separator of size $n^{d-1}$ (just pick any middle hyperplane, and remove all its vertices). It is also not too hard (but definitely not immediate) to verify that any separator has to be of size $\Omega(n^{d-1})$. Anybody knows a refenence to this?


texts: Help in understanding Symbolic Execution

texts:
I am an undergraduate CS student and currently reading on software security, particularly on static analysis of programs. I am particularly interested in understanding Symbolic Execution - an implementation technique under static analysis.

So far, I am unable to understand some of the research papers on the same, because of the lack of deep understanding of Symbolic Execution and its applications and uses.

There aren't many resources on the web, and the ones that are, assume a considerable formal knowledge on this domain from the reader beforehand.

I would appreciate if somebody can explain in depth the concept of Symbolic Execution and how it can be possibly used in program analysis - identifying bugs/vulnerabilities in softwares.
Any links to some helpful resources on the same that would enable a security enthusiast to get started would be highly appreciated.


texts: Slightly Faster Exponential Algorithm for Integer Programming with Multi-linear Variables

texts:
Integer programing is one of the most narutal optimization tools.
As an analogy of DNF or CNF in the Boolean function theory, we can consider the following equation.
$x_{1}x_{2}x_{3}+$ $x_{3}x_{4}x_{5}+x_{1}x_{7}x_{9}=8,x_{i}\in \{0,1\}$
This constraint is not a linear one. However, every variables in any monomial has at most degree $1$.Call constraints of this kind $multi$-$lienar$ constraints.
We consider the following example as a instance of Multi-linear Integer($0$-$1$) programming, which is a system of multi-linear constraints.
$5x_{1}x_{2}x_{3}+2x_{3}x_{4}x_{5}+x_{1}x_{7}x_{9}=8$
$11x_{1}x_{3}+3x_{2}x_{4}x_{6}+23x_{3}x_{7}x_{8}+x_{10}=4$
$x_{2}x_{6}+4x_{3}x_{4}x_{5}+5x_{5}x_{7}x_{9}=4$
$x_{i} \in \{0,1\} $
Where all coefficients of each monomial is integer and polynomial order $n^{O(1)}$($n$ is the number of variables)
Solving Multi-linear 0-1 programming is deciding whether there exists an $0$-$1$ assingment which satisfies all of given multilinear constraints.
Ofcourse $0-1$ programming is a $NP$-complete problem in one of the 21 problems which R.Karp showed their completeness. More over Exponential Time Hypothesis seems to  get rid of our hope to construct better sub-exponential time algorithms.
My question is :
Q
Are there any $slightly$ better exponential algorithm for Multi-linear 0-1 programming such as $2^{n-C\log n}$ time, $2^{n-C\log ^{2} n}$ times, or $2^{n-Cn^{0.001}}$ ?($C$ is a constant) ,and are there  text-books or papers contains algorithms for integer programming of this type ?


texts: Exponential Concentration Inequality for Higher-order moments of Gaussian Random Variables

texts:
Let $X_1,\ldots, X_n$ be $n$ i.i.d. copies of  Gaussian random variable $X \sim N(0, \sigma^2)$. It is known that
\begin{align}
\mathbb{P}\Bigl( \Bigl|\frac{1}{n}\sum_{j=1}^n X_j \Bigl| >t\Bigr) &\leq 2 \exp( cnt^2)~~\text{and}\\
\mathbb{P}\Bigl( \Bigl|\frac{1}{n}\sum_{j=1}^n (X_j^2 - \mathbb{E}X_j^2) \Bigl| >t\Bigr) &\leq 2 \exp( cn\min \{t^2, t\}).
\end{align}
These two results follows from the concentration inequality of sub-Gaussian and sub-exponential random variables and the second one is a Bernstein-type inequality. I wonder if there are similar results for the higher moments of Gaussian random variables. Can one have
\begin{align}
\mathbb{P}\Bigl( \Bigl|\frac{1}{n}\sum_{j=1}^n (X_j^4 - \mathbb{E}X_j^4) \Bigl| >t\Bigr) \leq 2 \exp( cnt)?
\end{align}
And more generally, for a centered random variable $Y$ satisfying $\mathbb{P}(|Y| > t) \leq 2 \exp(c t^{\alpha})$ for $\alpha > 0$, can we get an exponential inequality for the concentration of $\sum_{i=1}^n Y_i$? That is, can we have
\begin{align}
\mathbb{P}\Bigl( \Bigl|\frac{1}{n}\sum_{j=1}^n (Y_j - \mathbb{E}Y_j) \Bigl| >t\Bigr) \leq 2 \exp( cnt^\beta)
\end{align}
for some $\beta > 0$？


texts: Average-case complexity open problems other than one-way functions

texts:
The list of unsolved problems in computer science on Wikipedia lists no problems in average-case complexity, except "Do one-way functions exist?" which is whether there is a polynomial time computable function that such that all efficient algorithms fail (with high probability) to invert it.

Are there other high-profile, specific open problems in average-case complexity?


texts: Which algorithm for linear programming is suitable for the context of quantum computing?

texts:
There are two major types of algorithms for linear programming : extreme point based, interior point based.
Which will be suitable for quantum computing?


texts: Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture

texts:
The recent and incredibly slick proof of the sensitivity conjecture relies on the explicit* construction of a matrix $A_n\in\{-1,0,1\}^{2^n\times 2^n}$, defined recursively as follows:
$$A_1 = \begin{pmatrix} 0&1\\1&0\end{pmatrix}$$
and, for $n\geq 2$,
$$A_{n} = \begin{pmatrix} A_{n-1}&I_{n-1}\\I_{n-1}&-A_{n-1}\end{pmatrix}$$
In particular, it is easy to see that $A_n^2 = n I_n$ for all $n\geq 1$.

Now, maybe I am reading too much into this, but this looks at least syntactically related to another famous family of matrices, the Hadamard matrices, which is also such that $H_n^2 \propto I_n$ and has 'similar' spectrum:
$$H_1 = \begin{pmatrix} 1&1\\1&-1\end{pmatrix}$$
and, for $n\geq 2$,
$$H_{n} = \begin{pmatrix} H_{n-1}&H_{n-1}\\H_{n-1}&-H_{n-1}\end{pmatrix}$$

  Is there any formal connection, possibly useful, between the two, except that "they look vaguely similar"?

For instance, $A_n$ seen as the signed adjacency matrix of the hypercube $\{0,1\}^n$ has a nice interpretation (the sign of an edge $(x,b,x')\in\{0,1\}^n$ is the parity of the prefix $x$). Is there an analogue for $H_n$? (this may be obvious?)

$^*$ I am also wondering if a non-explicit construction, e.g., a uniformly random $\pm1$ matrix, would have the desired spectral properties, but that'd probably have to wait for another question.


texts: Which $SIZE$-$DEPTH(s, d)$ classes with $log(s(n))^{d(n) - 1} = o(n)$ can we not separate by known methods?

texts:
Define $SIZE$-$DEPTH(s, d)$ to be the functions which are computed by circuit families of size $O(s(n))$ and less than depth $d(n)$.

We know from Boppana's 1997 paper on the average sensitivity of low depth circuits that if we have functions $s, d, s', d' : \mathbb{N} \rightarrow \mathbb{N}$, where

$log(s(n))^{d(n)-1} = o(n)$,

$log(s'(n))^{d'(n) - 1} = o(log(s(n))^{d(n) - 1}$,

we know that $SIZE$-$DEPTH(s, d) \neq SIZE$-$DEPTH(s', d')$.

This is true because in $SIZE$-$DEPTH(s, d)$ we can compute $PARITY$ on a larger number of bits than in its $s', d'$ defined counterpart. This separates a large number of low complexity classes, most interesting to me being $qAC^0 \neq FOLL$. On the other hand, when

$log(s(n))^{d(n) - 1} = \Theta(log(s'(n))^{d'(n) - 1})$,

I don't know of a method to separate them. Obviously there are the degenerate cases where $s(n) = \Theta(s'(n)), d = \Theta(d')$, but I tried to compute the limit and get some constraints on $s, d, s', d'$ but it is seriously gnarly and it doesn't seem to give me anything good. If $d$ is constant you can do something but it doesn't give me much intuition. Can anybody come up with interesting examples, perhaps illustrating the size-depth tradeoffs that you'd imagine would be present, of $s, d, s', d'$ for which the respective classes cannot be separated by Boppana? If so, can you show a separation between these two classes in another way? Is there some reason I'm missing that all such cases are degenerate?


texts: NP-hardness of minimum distance over a code

texts:
There happens to be this NP-complete question,

Minimum-Distance-Over-$\mathbb{F}_{2^m}$

Given $w \in \mathbb{Z}^+$ and a $r \times n$ matrix $H$ over $\mathbb{F}_{2^m}$, is there a $x \in \mathbb{F}_{2^m}^n$ of weight $\leq w$ s.t $Hx=0$?

Is there some "easy" proof of this? (as opposed to say what I can partly fish out of this paper, http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=641542)
Is there any variant of it where the hardness is true even if I assume that $H$ has at least $r$ linearly independent columns? (and such a condition gets automatically satisfied if the rows of $H$ define a code?)


texts: Natural Problems NSPACE[n] but not in DTIME[n]

texts:
It is known that $\mathrm{DTIME}[n]\subseteq \mathrm{DSPACE}[n/\log n]$. Therefore, there are languages in $\mathrm{DSPACE}[n]$ which are not in
$\mathrm{DTIME}[o(n\log n)]$.

Are there examples of "natural" problems which are in
$\mathrm{DSPACE}[n]$ but not in $\mathrm{DTIME}[o(n\log n)]$?
Are there examples of "natural" problems that are in $\mathrm{NSPACE}[n]$ but not in $\mathrm{DTIME}[o(n\log n)]$?

By "natural" I mean problems which are not specifically designed to meet the specifications of the question. Clearly, using diagonalization arguments one can cook up problems that are in $\mathrm{DSPACE}[n]$ but not in $\mathrm{DTIME}[o(n\log n)]$.

Note that the classes DTIME, DSPACE and NSPACE above are defined with respect to multitape turing machines.

Obs 1:  I'm mostly interested in lower bounds of the form $\Omega(n\log n)$ or even $\Omega(n\log \log n)$ for Multitape turing machines. But weaker lower bounds would also be welcome. For instance, it has been shown in
this paper, that satisfiability of succint QBF-formulas with a constant number of alternations require time $\Omega(n\log^* n)$, where $\log^* n$ is the iterated logarithm function. Although $\log^* n$ grows extremely slowly, this lower bound has the advantage that it works not only for multitape TMs but also for more general models, such as $d$-dimensional TM's, random access TM', and alike.