Array implementation of dictionary data structure Is there a data structure that supports searching, inserting, deletion in worst-case O(log n) time and that satisfies the following "array implementation" property: at any point in time, the data structure only occupies memory cells 1..n (or 1..O(n)) if there are n elements?

Note that e.g. heaps do satisfy the property.

In particular, do standard data structures such as red-black, AVL, etc. allow for such an implementation?  (And if so, why is this not discussed in standard textbooks?)

(This is vaguely related to a previous question which got no answer.)

I believe you are looking for the paper Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees by Franceschini and Grossi.


Does this graph class have a name ? It's formulated by extending threshold graphs.  Given a threshold graph $(C,I)$ where $C$ is the clique and $I$ is the independent set, my extension is as follows: Each vertex $v\in I$ can be replaced by a new clique $K_v$ such that the vertices of $K_v$ have the same neighbors of $v$.

I guess this should have been studied, but it is hard to search such thing in graphclasses.org.

I believe that these are exactly the ($C_4$, $P_4$, $2P_3$)-free graphs — that is, the graphs whose induced subgraphs do not include 4-cycles, 4-vertex paths, or the graphs formed from the disjoint union of two 3-vertex paths. This class seems to lie between the threshold graphs themselves, which may be characterized as the ($C_4$, $P_4$, $2K_2$)-free graphs, and the trivially perfect graphs (intersections of nested intervals), which may be characterized as the ($C_4$, $P_4$)-free graphs. I don't think it has a name; at least, it doesn't seem to be listed at graphclasses.org.

To see that this is the correct characterization, consider the representation of trivially perfect graphs as the transitive closures of rooted forests. A forest gives rise to a (connected) threshold graph if and only if it has a directed path that contains all non-leaf nodes: adding a new isolated vertex corresponds, in the forest, to adding a new single-node tree, which doesn't change this property, and adding a new vertex connected to all of the others corresponds to adding a new root connected to all the previous tree roots, which again doesn't change this property (the new root can be part of the path).

Now your clique-replacement operation corresponds, in the tree view of a trivially perfect graph, to subdividing tree edges into paths (or replacing a one-vertex tree by a path). The forests that you can get from this operation are the ones in which there is a single directed path that contains all nodes with two or more children. A forest has such a path if and only if it does not have two unrelated forks (nodes with two or more children, neither of which can reach each other). And the subgraph you get in your trivially perfect graph when there are two forks is exactly $2P_3$.

The graphs whose complements are in the class you ask about — that is, the ($2K_2$,$P_4$,co-$2P_3$)-free graphs — were studied by Gurski, who showed that they are the same as the graphs of linear clique-width at most two. See theorem 10 of Gurski, Frank, "Characterizations for co-graphs defined by restricted NLC-width or clique-width operations", Discrete Math. 306 (2006), no. 2, 271–277.


A weighted sorting problem Given a data matrix $D=[d_1 ... d_N]$, one would like to sort it in terms of rows such that the weighted distance of sorted $d$s to a target vector $y$ is being minimized.

It can be formulated as follows

$\min_{P\in\Pi} \sum_i w_i ||Pd_i-y||_2 $

where $w_i$ is the weight, $\Pi$ is the set of permutation matrix: $\Pi = \{P|Pe=e,P^Te=e,P_{ij}\in \{0,1\}\}$

Is there any optimal sorting strategy?

It is NP-hard. Here is a reduction from the minimum bisection problem. Let $G = ([n],E)$ be a graph on $n$ vertices with $m$ edges (assume that $n$ is even). Let $N=2m$. Let $y= (1,\dots, 1,-1,\dots,-1)$ consist of $n/2$ ones and $n/2$ minus ones. For every edge $(i,j)$ introduce two columns: one with ones at positions $i$ and $j$, the other with $-1$ at positions $i$ and $j$. Each permutation $P$ defines a bisection $(S,\bar S)$ and vice versa:
$$S=\{i:1\leq P(i) \leq n/2\} \qquad \bar S=\{i:n/2+1 \leq P(i) \leq n\}.$$
($P$ is not uniquely defined by $S$; but all permutations corresponding to $S$ are equivalent).

If an edge $(i,j)$ is not cut by $(S,\bar S)$ then it contributes $C_1 = \sqrt{n-2}+\sqrt{n+6}$ to the objective function. If $(i,j)$ is cut then it contributes $C_2 = \sqrt{n+2}+\sqrt{n+2}$. Let $\Delta = C_2 - C_1 > 0$.
Observe that the value of the problem equals $m C_1 + \Delta\cdot |E(S,\bar S)|$. That is, the optimal solution to this problem corresponds to the minimum bisection and vice versa.


Which cryptographic protocols are secure against quantum computer attacks? Are there any cryptosystems that we know that would be secure against an attack by a quantum computer?

Are there problems which are known or suspected to be hard for quantum computers, and can these be utilized to yield cryptographic protocols which are secure against quantum computers?

"Quantum Computers" may give you significant speedup in many types of attacks.
These speedups may not necessarily be exponential like the current Shor's algorithm usage for breaking RSA.
You may find more information here: https://security.stackexchange.com/questions/116596/will-quantum-computers-render-aes-obsolete


How not to compute the smallest circle enclosing a finite set of circles Suppose we have a finite set $L$ of disks in $\mathbb{R}^2$, and we wish to compute the smallest disk $D$ for which $\bigcup L\subseteq D$. A standard way to do this is to use the algorithm of Matoušek, Sharir and Welzl [1] to find a basis $B$ of $L$, and let $D=\langle B\rangle$, the smallest disk containing $\bigcup B$. The disk $\langle B\rangle$ may be computed algebraically using the fact that, since $B$ is a basis, each disk in $B$ is tangent to $\langle B\rangle$.

($B\subseteq L$ is a basis of $L$ if $B$ is minimal such that $\langle B\rangle=\langle L\rangle$. A basis has at most three elements; in general for balls in $\mathbb{R}^d$ a basis has at most $d+1$ elements.)

It is a randomised recursive algorithm as follows. (But see below for an iterative version, which may be easier to understand.)

Procedure: $MSW(L, B)$
Input: Finite sets of disks $L$, $B$, where $B$ is a basis (of $B$).

If $L=\varnothing$, return $B$.
Otherwise choose $X\in L$ at random.
Let $B'\leftarrow MSW(L-\{X\}, B)$.
If $X\subseteq\langle B'\rangle$ then return $B'$.
Otherwise return $MSW(L, B'')$, where $B''$ is a basis of $B'\cup\{X\}$.

Used as $MSW(L, \varnothing)$ to compute a basis of $L$.

Recently I had cause to implement this algorithm. After verifying that the results were correct in millions of randomly-generated test cases, I noticed that I had made an error in the implementation. In the last step I was returning $MSW(L-\{X\}, B'')$ rather than $MSW(L, B'')$.

Despite this error, the algorithm was giving the right answers.

My question: Why does this incorrect version of the algorithm apparently give correct answers here? Does it always (provably) work? If so, is that also true in higher dimensions?

Added: some misconceptions

Several people have proposed incorrect arguments to the effect that the modified algorithm is trivially correct, so it may be useful to forestall some misconceptions here. One popular false belief seems to be that $B\subseteq\langle MSW(L, B)\rangle$. Here is a counterexample to that claim. Given disks $a,b,c,d,e$ as below (the boundary of $\langle a,b,e\rangle$ is also shown in red):

we can have $MSW(\{c, d\}, \{a,b,e\})=\{c,d\}$; and note that $e\notin\langle c,d\rangle$:

Here is how it can happen. The first observation is that $MSW(\{c\},\{a,b,e\})=\{b,c\}$:

We wish to compute $MSW(\{c\},\{a,b,e\})$
Choose $X = c$
Let $B' = MSW(\varnothing, \{a,b,e\}) = \{a,b,e\}$
Observe that $X\notin\langle B'\rangle$
So let $B''$ be a basis of $B'\cup\{X\} = \{a,b,c,e\}$
Observe that $B''=\{b,c\}$
Return $MSW(\{c\}, \{b,c\})$, which is $\{b,c\}$

Now consider $MSW(\{c, d\}, \{a,b,e\})$.

We wish to compute $MSW(\{c, d\}, \{a,b,e\})$
Choose $X=d$
Let $B' = MSW(\{c\}, \{a,b,e\}) = \{b,c\}$
Observe that $X\notin\langle B'\rangle$
So let $B''$ be a basis of $B'\cup\{X\} = \{b,c,d\}$
Observe that $B''=\{c,d\}$
Return $MSW(\{c,d\}, \{c,d\})$, which is $\{c,d\}$

(For the sake of definiteness, let us say that the disks $a,b,c,d,e$ all have radius 2, and are centred at $(30,5)$, $(30,35)$, $(10, 5)$, $(60, 26)$, and $(5, 26)$ respectively.)

Added: an iterative presentation

It may be easier to think about an iterative presentation of the algorithm. I certainly find it easier to visualise its behaviour.

Input: A list $L$ of disks
Output: A basis of $L$

Let $B\leftarrow\varnothing$.
Shuffle $L$ randomly.
For each $X$ in $L$:
  If $X\notin\langle B\rangle$:
    Let $B$ be a basis of $B\cup\{X\}$.
    Go back to step 2.
Return $B$.

The reason the algorithm terminates, incidentally, is that step 5 always increases the radius of $\langle B\rangle$ – and there are only finitely many possible values of $B$.

The modified version doesn’t have such a simple iterative presentation, as far as I can see. (I tried to give one in the previous edit to this post, but it was wrong – and gave incorrect results.)

Reference

[1] Jiří Matoušek, Micha Sharir, and Emo Welzl. A subexponential bound for linear programming. Algorithmica, 16(4-5):498–516, 1996.

This step of removing $X$ from $L$ before continuing recursion actually improves the algorithm, because it removes the already-added $X$ from the pool of basis candidates. It will always, provably work, because it's equivalent to the existing algorithm, and it will also work for higher dimensions.

Trace through the algorithm. When you use $MSW(L,B^{\prime\prime})$, there is $X \in L$ and $X \in B^{\prime\prime}$. Suppose we chose it again in step 2. Regardless of the result of step 3, $B^\prime$ will always have $X$, because the recursive function has the invariant $B \subseteq MSW(L,B)$.

In other words, your improvement to the algorithm shortcuts to step 3 in the part where $X$ is chosen.


Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges This question was originally posted on mathoverflow. Having obtained no answers after one month, I've decided to cross-post it here.

Let $H = ( V, E )$ be a $k$-uniform connected hypergraph, with $n = |V|$ vertices and $m = |E|$ hyperedges. Let $O_w$ be the number of distinct edge induced subgraphs of $H$ having $w$ vertices and an odd number of hyperedges. Let $E_w$ be the number of distinct edge induced subgraphs of $H$ having $w$ vertices and an even number of hyperedges. Let $\Delta_w = O_w - E_w$.

Let $b_w$ be the number of bits required to encode $\Delta_w$, i.e. $b_w = log_2 \ \Delta_w$.

Let $b = \displaystyle\max_{\substack{w}} b_w$.

I'm interested in how $b$ grows. I would like to determine the best possible upper bound for $b$ which is expressible as a function of only $n$, $m$ and $k$. More precisely, I would like to determine a function $f(n,m,k)$ having both the following properties:

$b \leq f( n, m, k )$ for any $k$-uniform hypergraph $H$ having $n$ vertices and $m$ hyperedges.
$f(n,m,k)$ grows slower than any other function which satisfies the 1st property.

In general both $O_w$ and $E_w$ are exponential in $m$, therefore I expect that their difference $\Delta_w$ is not exponential in $m$ and thus that $b \in o( m )$.

However for the moment I've no clue on how to try to prove this.

  Questions

  How does $b$ grow with respect to $n$, $m$ and $k$?
  Are there any relevant results in the literature?
  Any hint on how to try to prove $b \in o(m)$?

It is the case that $b \notin o( m )$.

Let $G = ( V_G, E_G )$ be a $3$-regular connected graph. Without loss of generality, let us fix $w = |V_G|$ and focus on $\Delta_{|V_G|} = O_{|V_G|} - E_{|V_G|}$.

Pick an arbitrary edge $e = \{u, v\} \in E_G$. Remove $e$ and replace it with the following gadget:

This has the effect of multiplying $\Delta_{|V_G|}$ by $8$. The resulting graph $H = (V_H, E_H)$ is still $3$-regular connected, and has $60$ vertices more than $G$.

By repeating this process $i$ times, we obtain a $3$-regular connected graph having $|V_H| = |V_G| + 60i$ vertices, and whose $\Delta_{|V_H|}$ is $8^i$ times bigger than $\Delta_{|V_G|}$.

After $i = \frac{|V_G|}{3}$ iterations, our final graph will have $|V_H| = 21|V_G|$ vertices and a $\Delta_{|V_H|}$ which is $2^{|V_G|}$ times bigger than the $\Delta_{|V_G|}$ we started with. Let $n = |V_H|$, recall how $m = 1.5n$ for $3$-regular graphs, and we get a $\Delta_{|V_H|}$ whose absolute value is lower-bounded by $2^{\frac{m}{31.5}}$. Henceforth $b$ is linear in $m$ in the worst case, and thus it cannot belong to $o( m )$.

Contrarily to intuition (at least mine), the number of edge covers of odd cardinality and the number of edge covers of even cardinality may diverge by an exponential amount.


What are current open problems in compiler theory? Compiler theory seems to be a pretty vetted subject. What are some open problems or current research happening in the field?

In my experience, I've seen the following new compiler developments:

Work on automating data parallelism (or at least, reducing the amount of explicit work done by the programmer). This typically requires extensions to the language as well.
Work on extreme optimization strategies such as supercompilation or partial evaluation (where a program is collapsed via evaluation until it is reduced to its "smallest" form and then compiled)

I've seen a variety of work on things such as type checkers and so on, but I assume you're talking more about compiler-specific stuff.


Graph coloring/partitioning problem 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.

Your problem is NP-complete.
Take an instance $G'=(V',E')$ of the (NP-complete) max-cut problem. Let $m=|E'|$.

Create two new vertices $x_1$ and $x_2$, create the edge between $x_1$ and $x_2$, and all edges between $V'$ and $\{x_1,x_2\}$.
The edge $[x_1,x_2]$ receives positive weight $1000m$
All edges $[x_i,v]$ with $i=1,2$ and $v\in V'$ receive negative weight $-2m$
All edges in $E'$ receive positive weight $1$

It can be easily seen that your optimal coloring for this graph

assigns two distinct colors to $x_1$ and $x_2$ (say color 1 to $x_1$ and color 2 to $x_2$)
and colors every vertex $v\in V'$ with one of these colors 1 or 2

Hence, the two-coloring on $V'$ induces a max-cut in $G'$.


Freivalds matrix multiplication with non binary random vector Freivalds' algorithm verify matrices (over a field) product $A \times B = C$  by choosing a random binary vector $r$ and verifying if $A(Br)=Cr$ which fails if $AB \neq C$ with probability at most $1/2$.

It seems to me that it can be done by choosing $r$ in some set $S$ which include $0$ resulting that the algorithm fails with probability $\leq 1/|S|$.

All I could find about the algorithm uses binary vector; is the above approach possible? And, as another question, is it possible deduce Freivalds result from Schwartz–Zippel lemma?

this is a tentative proof:

$Dv= (AB-C)v = 0$ imply there exists $\ell, c$ such that
$d_{\ell,c}\neq 0$ and $\sum_{j=1}^{n}v_{j} d_{j,c}=0$, thus

$(*)$  $v_{\ell}= - \frac{1}{d_{\ell,c}}\sum_{\substack{j=1\\ j\neq \ell}}^{n}v_{j}
   d_{j,c}$

Let $E=\big\{v \in S^{n}\colon {v}{D}={0}\big\}$ and $E_\ell = \left\{(v_1,v_2,\dots,v_n)\in S^{n}\colon (*)\right\}$

Partition $S^n$ putting for each $(r_{1},\dots,r_{n-1})\in S^{n-1}$

$A_{r_{1},\dots,r_{n-1}} = \{r_1\}\times \cdots \times \{r_{\ell-1}\} \times S \times \{r_{\ell}\} \times \cdots \times \{r_{n-1}\}$

By total probability law and $E\subset E_\ell$

$P(E) = \sum_{(r_{1},\dots,r_{n-1})}P(E\cap A_{r_{1},\dots,r_{n-1}})\leq$
$\sum_{(r_{1},\dots,r_{n-1})}P(E_\ell\cap A_{r_{1},\dots,r_{n-1}})=$
$\sum_{(r_{1},\dots,r_{n-1})}P(E_\ell~|~ A_{r_{1},\dots,r_{n-1}}) P(A_{r_{1},\dots,r_{n-1}})$

Finally

$P(E_\ell~|~ A_{r_{1},\dots,r_{n-1}})= P\left( \left\{s\in S\colon s=
        \frac{-(\sum_{j<\ell} r_jd_{j,\ell} + \sum_{j>\ell}
          r_{j-1}d_{j,\ell}) }{d_{\ell,c}} \right\}\right) \leq \frac
    1{|S|}$
and
$P(E)\leq  \sum_{(r_{1},\dots,r_{n-1})}\frac 1{|S|}
      P(A_{r_{1},\dots,r_{n-1}})
      =\frac 1{|S|}.$

The answer to both questions is yes. The matrix $A B - C$ gives rise to a linear application over your field $\mathbb F$, which is a multivariate polynomial of total degree $d=1$. By the Schwartz-Zippel lemma, when $x$ is drawn from $S^n$ (where $S \subseteq {\mathbb F}$), the probability that $(A B - C) x = 0$ is at most $d/|S| = 1/|S|$, provided that $A B \neq C$.
As you observe, this can also be proved directly using the standard argument for Freivald's algorithm.


What is the asymptotically fastest known algorithm for computing the nullspace of a matrix? I know Gaussian Elimination takes $O(n^3)$ arithmetic operations, but I'm unsure if any better algorithms are known.

The exponent of computing a basis of the kernel is the same
as the exponent of matrix multiplication, see the
book Algebraic Complexity Theory by Bürgisser, Clausen & Shokrollahi.
So it can be done in time $O(n^{2.38})$.


Fully linear time regular expression matching Is there an $O(n+m)$ algorithm to check whether a size $n$ regular expression matches a size $m$ string, assuming a fixed size alphabet if that matters?

The standard NFA algorithm is $O(nm)$ worst case.  Groz et al. achieve linear time for a variety of regular expression classes, but not all.  Are there any better results?

Groz, B., Maneth, S., & Staworko, S. (2012, May). Deterministic regular expressions in linear time.

Groz et al. explicitly state that the best known algorithm for general regular expressions (as of 2012) is $O(nm(\log\log n)/(\log n)^{3/2}+n+m)$, due to Bille and Thorup 2009, doi:10.1007/978-3-642-02927-1_16 (preprint).

For a fixed size alphabet, Sebastian Maneth pointed out to me that $O(n+m)$ is possible for deterministic regular expressions by constructing the Glushkov DFA: each position in the regular expression is one state, and the transitions are determined by the bounded set of symbols that may appear before moving to a position.
However, without fixing the alphabet size, it still holds that "finding a time $O(m+n)$ algorithm remains an open problem" even in the deterministic case.


Recent publications on NP ?= coNP question I am interested in the question of whether NP is equal to coNP or not. I'd much appreciate some advice on good publications to read on the topic.

For the record, I know that this question is intimately connected to the question of whether P equals NP or not (such that if NP != coNP then P != NP).

Cheers,
Derek

NP is equal to coNP if and only if there are efficiently verifiable proofs of unsatisfiability. I.e., if and only if there exists a polynomial time turing machine $M$, which given any SAT formula $\phi$ and a string $\pi$ outputs $M(\phi, \pi) = 1$ if and only if $\phi$ is unsatisfiable. Most theorists believe there are no such efficient proofs, but proving that they don't exist would resolve the P vs NP question. However, there has been progress in showing that proofs of a restricted type must necessarily be superpolynomial in size. This is the subject of proof complexity: see the foundational paper by Cook and Reckhow, the  survey by Krajicek, or these lecture notes by Razborov.


Concerning decidability of a problem on real numbers This question is an outgrowth of a certain maths problem I've been thinking about.

Suppose you use an oracle to represent a real number. The oracle is of the following form: you give it an integer and it returns you an integer back (for example: given input $n$ the oracle representing $r$ returns integer $k$ such that $k/n \leq r < (k+1)/n$; but it can be any other oracle complying to the aforementioned rule).

Now, given two oracles like that you can't decide if they represent equivalent numbers (if the numbers are equal the algorithm won't halt in 'most' cases). So you are given another oracle that takes two real-number oracles as input and tells if they represent equal numbers.

Given two real numbers $r$ and $s$ represented by such oracles plus the oracle that tells us if two real numbers are equal is it possible to decide if $s = qr + p$, where $q$ and $p$ are rational?

Please provide a formal proof (or at least an idea that can be easily formalized into a proof).

Update: There is a problem with the oracle comparing two real numbers - see comments. Intuitively what I want is the answer to the following question: is deciding that two real numbers belong to the equivalence class defined by $s=qr+p$ harder than deciding if they are equal. I'll close this question and restate it.

I think it's undecidable, but I don't have a proof. Intuitively, if $s\neq qr+p$ for all $p,q\in\mathbb{Q}$ (i.e. if the answer is "NO"), then you will be always looking for a "next" pair $(q,p)$ such that $|s-(qr+p)|$ is smaller than before. You don't really have an argument to decide when to stop and return "NO" because, for all you know, there is a better approximation to $s$ of the form $qr+p$ than the one you already have.


Intuition behind proof systems I'm trying to under stand the paper On p-Optimal Proof Systems and Logic for PTIME. There is a notion called proof systems in the paper and I do not get the intution:

  $\Sigma = \{0,1\}$ ... We identify problems with subsets of $Q$ in $\Sigma^*$.

I think the intution is that we encode a certain structure in $\Sigma^*$ (e.g. undirected graphs) and subsets of these structures are problems (e.g. planar graphs).

  A proof system  for a problem $Q \subset \Sigma^*$ is a surjective
  function $P:\Sigma^* \to Q$ computable in polynomial time.

Now one possibilty is to say $\Sigma^*$ is the set of all possible models in a certain structure (e.g. all the undirected graphs). But that does not make sense because why should a undirected graphs be mapped on a subset? It could be encoded turing machines but this does not make sense either ...

Any ideas?

Think of $\Sigma^{*}$ encoding some sort of objects, and $Q$ as the set of all objects satisfying some property. Think of $P$ as a function which accepts (the encoding of) a pair $(x, p)$ where $x$ is an object and $p$ is alleged "evidence" of $x \in Q$. The function $P$ is a "proof checker": it verifies that $p$ actually represents valid evidence that $x \in Q$. If so, it returns $x$, otherwise it returns a default element of $Q$.

As an example, suppose $\Sigma^{*}$ encodes graphs and let $Q$ be the set (of encodings) of Hamiltonian graphs. A possible $P$ is this: decode input as $(G, \ell)$ where $G$ is a graph and $\ell$ is a list of vertices of $G$; verify that $\ell$ is a Hamiltonian cycle in $G$; if so then return $G$ otherwise return the graph on one point.

You considered the case of planar graphs. To get a suitable $P$ we need a notion of poly-time checkable evidence of planarity.

In general the input to $P$ need not encode a pair $(x, p)$. The important thing is that $P$ can extract two pieces of information from its input: the object in question and the alleged evidence that the object belongs to $Q$. For example, let us take as $Q$ the set of all sentences provable in some first-order theory. Now $P$ decodes its input as a formal proof. If the encoding is invalid, it returns $\top$. If the encoding represents a valid proof, it returns the statement that was proved by the proof (which is likely to be the root of proof tree, or the last formula in a sequence of statements, depending on how you formalize proofs).


Reducing $n$ in $(n,k)$ secret sharing while keeping it effective Assume Bob wants to share a secret with Alice.
Assume he can only send messages using a one-sided channel which is insecure and unreliable.
Unreliable, meaning: Alice only gets messages sent over this channel with probability $P$.
Insecure, meaning: Mallory the bad guy can read any message sent over this channel with probability $P'$.

Assuming $P>P'$, Bob can use $(n,k)$-secret sharing when $P>k/n>P'$.
As Bob increases $n$, the probability that Alice receives a correct message increases and that Mallory receives a correct message decreases.
This is because the mean of secret shares Alice and Bob get remains $P n$ and $P' n$ respectively, while the standard deviation drops as $n$ increases.

But there is more than one way to do this. For example, Bob and Alice could choose a relatively small $n$, transfer TWO secrets s.t. their XOR is the original secret. In this case Mallory's probability of learning the original secret will be squared, and decrease much faster than Alice's.

So my question is: Is 'classic' secret sharing ALWAYS the best way (giving the smallest possible $n$ for a given $P$ and $P'$)? I could not find a counter-example yet.

This sounds related to Wyner's "wiretap channel": Wyner showed that an asymmetry between receiver and eavesdropper could be used to achieve information-theoretic security. There have been many, many follow-up works since then.

Reference:
A. D. Wyner, The wire-tap channel. Bell Sys. Tech. J., vol. 54, pp. 1355-1387, 1975.


All pair shortest path problem for large number of nodes I am having a small problem. I have the complete city's data which has over 100,000 nodes and 40,000 paths in my database. Now I need to calculate the all pair shortest path between all of them.

Obviously running them all together will take a long long time to compute as the complexity being $\Theta(n^3)$. So what I have decided is that to divide all the nodes into 20 different circles. I will compute for each different circle and then merge all the table's using a small dynamic programming approach which has the complexity of $\Theta(n_1n_2)$

where $n_1$ i the number of nodes in 1st and $n_2$ in the 2nd circle. In my case $n_1$=$n_2$.

So this way I am running it in $O(n^3)$, but practically its much faster than before. Yet overall it still is taking a long long time to compute. Is there any better approach?
Or are there any better well known algorithms which can solve such problems faster?

Quite helpless

Search papers on : "Shortest Path Queries Using Highway Hierarchies". There is a paper by Sanders and Schultes. If you follow their citations, there are lot of other papers. These methods are very useful for real road networks.


Which formal language class are XML and JSON with unique keys? I moved this question from stackoverflow where id got no answers. We had a similar question whether JSON is regular:

JSON and XML are both frequently called to be context-free languages - they are both specified mainly by a formal grammar in EBNF. However this is only true for JSON as defined in RFC 4329, section 2.2 which does not require uniqueness of object keys (many may not know but {"a":1,"a":2} is valid JSON!). But if you require unique keys in JSON or unique attribute names in XML this cannot be expressed by a context-free grammars. But which is the language class of JSON with unique keys and for well-formed XML (which implies unique attribute names?).

One of the best paper I found on this subject (Murato et al, 2001: Taxonomy of XML Schema Languages using Formal Language Theory) explicitly excludes integrity constraints such as keys/keyrefs and uniqueness to be checked on an additional layer. Beside this the subset of XML defined by an XML Schema or by a DTD is context-free. But not the full set of all well-formed XML documents.

I think a nested stack automaton (=indexed language) should be able to parse JSON with unique key constraint. For XML can simlify the question to the language S of all comma-separated lists of unique integers. Does anyone know more, preferably with citations?

P.S: A simple algorithm to decide the languages (beside the context-free part) is based on a good sorting algorithm. Therefore it should be decidable in "linearithmic time" with O(n log n) worst case. I have not found out yet, whether the complexity class is for instance "mildly context-sensitive", or "indexed" but probably something between context-free and context-sensitive (?).

EDIT: Maybe I better reformulate the question for the more theoretical computer scientists. Given the class CFL of all languages that can be expressed by Backus-Naur-Form with repetition (x := a+ $\Leftrightarrow$ x := a | x a). Now what do I gain in computational power if I introduce a "repetition with unique instances" operator ^, so a^ is a sequence of a where each element results in a different sequence of terminals?

Using BNF with your unique-repetition operator, x := S^ says that an x is an instance a of symbol S, optionally followed by an instance b of set S - a, itself optionally followed by an instance c of set S - a - b, and so forth. If |S| is the number of possible S, and is finite, then 2 ^ |S|! - 1 is the number of possible S^.

It's not really meaningful to talk in terms of the computational power of the language being described, since this is about static semantics, in the twilight between syntax and ordinary (dynamic) semantics. The expressive power of the grammar is extended, since it has a formal means of expressing a particular type of input adaptation.

Specifically, it provides a means of accepting a permutation of a subset of a particular set. I don't think there is any existing name for this class of language. It's certainly not context-free, but the context requirement is at least pretty strictly controlled. If you need a term for it, just coin one. I suggest context-respecting for the class of languages that cannot be described by a context-free grammar without additional embedded information about static semantic constraints, which to be fair are vaguely syntactic in spirit.

The most useful application of this particular extension is probably just the ability to introduce unique-key constraints, but it also lets you describe such interesting sets as x := [0-7]^, which matches any octal number of 8 or fewer non-repeated digits. As for the complexity of it, determining whether an element of the set has been seen is no worse than logarithmic, and the frequency of checking is linear in the number of elements matched, so the ^ operator is indeed decidable in worst-case linearithmic time.


Core algorithms deployed To demonstrate the importance of algorithms (e.g. to students and professors who don't do theory or are even from entirely different fields) it is sometimes useful to have ready at hand a list of examples where core algorithms have been deployed in commercial, governmental, or widely-used software/hardware.
I am looking for such examples that satisfy the following criteria:

The software/hardware using the algorithm should be in wide use right now.

The example should be specific.
Please give a reference to a specific system and a specific algorithm.
E.g., in "algorithm X is useful for image processing"
the term "image processing" is not specific enough;
in "Google search uses graph algorithms"
the term "graph algorithms" is not specific enough.

The algorithm should be taught in
typical undergraduate or Ph.D. classes in algorithms or data structures.
Ideally, the algorithm is covered in typical algorithms textbooks.
E.g., "well-known system X uses little-known algorithm Y" is not good.

Update:
Thanks again for the great answers and links!
Some people comment that it is hard to satisfy the criteria
because core algorithms are so pervasive that it's hard to point to a specific use.
I see the difficulty.
But I think it is worthwhile to come up with specific examples because
in my experience telling people:
"Look, algorithms are important because they are just about everywhere!" does not work.

Algorithms that are the main driver behind a system are, in my opinion, easier to find in non-algorithms courses for the same reason theorems with immediate applications are easier to find in applied mathematics rather than pure mathematics courses. It is rare for a practical problem to have the exact structure of the abstract problem in a lecture. To be argumentative, I see no reason why fashionable algorithms course material such as Strassen's multiplication, the AKS primality test, or the Moser-Tardos algorithm is relevant for low-level practical problems of implementing a video database, an optimizing compiler, an operating system, a network congestion control system or any other system. The value of these courses is learning that there are intricate ways to exploit the structure of a problem to find efficient solutions. Advanced algorithms is also where one meets simple algorithms whose analysis is non-trivial. For this reason, I would not dismiss simple randomized algorithms or PageRank.

I think you can choose any large piece of software and find basic and advanced algorithms implemented in it. As a case study, I've done this for the Linux kernel, and shown a few examples from Chromium.

Basic Data Structures and Algorithms in the Linux kernel

Links are to the source code on github.

Linked list, doubly linked list, lock-free linked list.
B+ Trees with comments telling you what you can't find in the textbooks.

  A relatively simple B+Tree implementation.  I have written it as a learning exercise to understand how B+Trees work.  Turned out to be useful as well.

  ...

  A tricks was used that is not commonly found in textbooks.  The lowest values are to the right, not to the left.  All used slots within a node are on the left, all unused slots contain NUL values.  Most operations simply loop once over all slots and terminate on the first NUL.

Priority sorted lists used for mutexes, drivers, etc.
Red-Black trees are used for scheduling, virtual memory management, to track file descriptors and directory entries,etc.
Interval trees
Radix trees, are used for memory management, NFS related lookups and networking related functionality.

  A common use of the radix tree is to store pointers to struct pages;

Priority heap, which is literally, a textbook implementation, used in the control group system.

  Simple insertion-only static-sized priority heap containing pointers, based on CLR, chapter 7

Hash functions, with a reference to Knuth and to a paper.

  Knuth recommends primes in approximately golden ratio to the maximum
  integer representable by a machine word for multiplicative hashing.
  Chuck Lever verified the effectiveness of this technique:

  http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

  These primes are chosen to be bit-sparse, that is operations on
  them can use shifts and additions instead of multiplications for
  machines where multiplications are slow.

Some parts of the code, such as this driver, implement their own hash function.

  hash function using a Rotating Hash algorithm

  Knuth, D. The Art of Computer Programming,
  Volume 3: Sorting and Searching,
  Chapter 6.4.
  Addison Wesley, 1973

Hash tables used to implement inodes, file system integrity checks etc.
Bit arrays, which are used for dealing with flags, interrupts, etc. and are featured in Knuth Vol. 4.
Semaphores and spin locks
Binary search is used for interrupt handling, register cache lookup, etc.
Binary search with B-trees
Depth first search and variant used in directory configuration.

  Performs a modified depth-first walk of the namespace tree, starting
  (and ending) at the node specified by start_handle.  The callback
  function is called whenever a node that matches the type parameter is
  found. If the callback function returns a non-zero value, the search
  is terminated immediately and this value is returned to the caller.

Breadth first search is used to check correctness of locking at runtime.
Merge sort on linked lists is used for garbage collection, file system management, etc.
Bubble sort is amazingly implemented too, in a driver library.
Knuth-Morris-Pratt string matching,

  Implements a linear-time string-matching algorithm due to Knuth,
  Morris, and Pratt [1]. Their algorithm avoids the explicit
  computation of the transition function DELTA altogether. Its
  matching time is O(n), for n being length(text), using just an
  auxiliary function PI[1..m], for m being length(pattern),
  precomputed from the pattern in time O(m). The array PI allows
  the transition function DELTA to be computed efficiently
  "on the fly" as needed. Roughly speaking, for any state
  "q" = 0,1,...,m and any character "a" in SIGMA, the value
  PI["q"] contains the information that is independent of "a" and
  is needed to compute DELTA("q", "a") 2. Since the array PI
  has only m entries, whereas DELTA has O(m|SIGMA|) entries, we
  save a factor of |SIGMA| in the preprocessing time by computing
  PI rather than DELTA.

  [1] Cormen, Leiserson, Rivest, Stein
   Introdcution to Algorithms, 2nd Edition, MIT Press

  [2] See finite automation theory

Boyer-Moore pattern matching with references and recommendations for when to prefer the alternative.

  Implements Boyer-Moore string matching algorithm:

  [1] A Fast String Searching Algorithm, R.S. Boyer and Moore.
   Communications of the Association for Computing Machinery,
   20(10), 1977, pp. 762-772.
   http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

  [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq,
  2004
   http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

  Note: Since Boyer-Moore (BM) performs searches for matchings from
  right
  to left, it's still possible that a matching could be spread over
  multiple blocks, in that case this algorithm won't find any
  coincidence.

  If you're willing to ensure that such thing won't ever happen,
  use the
  Knuth-Pratt-Morris (KMP) implementation instead. In conclusion,
  choose
  the proper string search algorithm depending on your setting.

  Say you're using the textsearch infrastructure for filtering,
  NIDS or
  any similar security focused purpose, then go KMP. Otherwise, if
  you
  really care about performance, say you're classifying packets to
  apply
  Quality of Service (QoS) policies, and you don't mind about
  possible
  matchings spread over multiple fragments, then go BM.

Data Structures and Algorithms in the Chromium Web Browser

Links are to the source code on Google code. I'm only going to list a few. I would suggest using the search feature to look up your favourite algorithm or data structure.

Splay trees.

  The tree is also parameterized by an allocation policy
  (Allocator). The policy is used for allocating lists in the C free
  store or the zone; see zone.h.
  Voronoi diagrams are used in a demo.
  Tabbing based on Bresenham's algorithm.

  There are also such data structures and algorithms in the third-party code included in the Chromium code.

Binary trees
Red-Black trees

  Conclusion of Julian Walker

  Red black trees are interesting beasts. They're believed to be
  simpler than
  AVL trees (their direct competitor), and at first glance this seems
  to be the
  case because insertion is a breeze. However, when one begins to play
  with the
  deletion algorithm, red black trees become very tricky. However, the
  counterweight to this added complexity is that both insertion and
  deletion
  can be implemented using a single pass, top-down algorithm. Such is
  not the
  case with AVL trees, where only the insertion algorithm can be
  written top-down.
  Deletion from an AVL tree requires a bottom-up algorithm.

  ...

  Red black trees are popular, as most data structures with a
  whimsical name.
  For example, in Java and C++, the library map structures are
  typically
  implemented with a red black tree. Red black trees are also
  comparable in
  speed to AVL trees. While the balance is not quite as good, the work
  it takes
  to maintain balance is usually better in a red black tree. There are
  a few
  misconceptions floating around, but for the most part the hype about
  red black
  trees is accurate.
  AVL trees
  Rabin-Karp string matching is used for compression.
  Compute the suffixes of an automaton.
  Bloom filter implemented by Apple Inc.
  Bresenham's algorithm.

  Programming Language Libraries

I think they are worth considering. The programming languages designers thought it was worth the time and effort of some engineers to implement these data structures and algorithms so others would not have to. The existence of libraries is part of the reason we can find basic data structures reimplemented in software that is written in C but less so for Java applications.

The C++ STL includes lists, stacks, queues, maps, vectors, and algorithms for sorting, searching and heap manipulation.
The Java API is very extensive and covers much more.
The Boost C++ library includes algorithms like Boyer-Moore and Knuth-Morris-Pratt string matching algorithms.

Allocation and Scheduling Algorithms

I find these interesting because even though they are called heuristics, the policy you use dictates the type of algorithm and data structure that are required, so one need to know about stacks and queues.

Least Recently Used can be implemented in multiple ways. A list-based implementation in the Linux kernel.
Other possibilities are First In First Out, Least Frequently Used, and Round Robin.
A variant of FIFO was used by the VAX/VMS system.
The Clock algorithm by Richard Carr is used for page frame replacement in Linux.
The Intel i860 processor used a random replacement policy.
Adaptive Replacement Cache is used in some IBM storage controllers, and was used in PostgreSQL though only briefly due to patent concerns.
The Buddy memory allocation algorithm, which is discussed by Knuth in TAOCP Vol. 1 is used in the Linux kernel, and the jemalloc concurrent allocator used by FreeBSD and in facebook.

 Core utils in *nix systems

grep and awk both implement the Thompson-McNaughton-Yamada construction of NFAs from regular expressions, which apparently even beats the Perl implementation.
tsort implements topological sort.
fgrep implements the Aho-Corasick string matching algorithm.
GNU grep, implements the Boyer-Moore algorithm according to the author Mike Haertel.
crypt(1) on Unix implemented a variant of the encryption algorithm in the Enigma machine.
Unix diff implemented by Doug McIllroy, based on a prototype co-written with James Hunt, performs better than the standard dynamic programming algorithm used to compute Levenshtein distances. The Linux version computes the shortest edit distance.

Cryptographic Algorithms

This could be a very long list. Cryptographic algorithms are implemented in all software that can perform secure communications or transactions.

Merkle trees, specifically the Tiger Tree Hash variant, were used in peer-to-peer applications such as GTK Gnutella and LimeWire.
MD5 is used to provide a checksum for software packages and is used for integrity checks on *nix systems (Linux implementation) and is also supported on Windows and OS X.
OpenSSL implements many cryptographic algorithms including AES, Blowfish, DES, SHA-1, SHA-2, RSA, DES, etc.

Compilers

LALR parsing is implemented by yacc and bison.
Dominator algorithms are used in most optimizing compilers based on SSA form.
lex and flex compile regular expressions into NFAs.

Compression and Image Processing

The Lempel-Ziv algorithms for the GIF image format are implemented in image manipulation programs, starting from the *nix utility convert to complex programs.
Run length encoding is used to generate PCX files (used by the original Paintbrush program), compressed BMP files and TIFF files.
Wavelet compression is the basis for JPEG 2000 so all digital cameras that produce JPEG 2000 files will be implementing this algorithm.
Reed-Solomon error correction is implemented in the Linux kernel, CD drives, barcode readers and was combined with convolution for image transmission from Voyager.

Conflict Driven Clause Learning

Since the year 2000, the running time of SAT solvers on industrial benchmarks (usually from the hardware industry, though though other sources are used too) has decreased nearly exponentially every year. A very important part of this development is the Conflict Driven Clause Learning algorithm that combines the Boolean Constraint Propagation algorithm in the original paper of Davis Logemann and Loveland with the technique of clause learning that originated in constraint programming and artificial intelligence research. For specific, industrial modelling, SAT is considered an easy problem (see this discussion). To me, this is one of the greatest success stories in recent times because it combines algorithmic advances spread over several years, clever engineering ideas, experimental evaluation, and a concerted communal effort to solve the problem. The CACM article by Malik and Zhang is a good read. This algorithm is taught in many universities (I have attended four where it was the case) but typically in a logic or formal methods class.

Applications of SAT solvers are numerous. IBM, Intel and many other companies have their own SAT solver implementations. The package manager in OpenSUSE also uses a SAT solver.


dependent types and higher-order logic applied in the realm of DSLs (this is a beginner question and English is not my first language)

I am searching for references on using theorem proves based on dependent type theory (or Martin Löf type-theory) and higher-order logic in the development of domain specific languages (DSLs).

Dependent types, i.e., Coq and Agda
Higher-Order logic, i.e., Isabelle/HOL

Currently, I am attending an course on higher-order logic for PhD students, and it seems to me there are possible applications to DSLs. As I am not so familiar with Coq so I may have overlooked some references.

I found only two references:

Oury, Nicolas, and Wouter Swierstra. "The power of Pi." ACM Sigplan Notices. Vol. 43. No. 9. ACM, 2008.

Chlipala, Adam. "Ur: statically-typed metaprogramming with type-level record computation." ACM Sigplan Notices. Vol. 45. No. 6. ACM, 2010.

Any suggestions on papers that I missed?

It's time for you to meet Edwin Brady:

http://edwinb.wordpress.com/publications/

His earliest papers are about designing DSLs to solve very concrete problems. Lately, he has also been working on optimizing their performance (using type theoretic tools!).

To explore this design space, I would recommend playing with Agda or Idris.


Number of minimal DFAs of size at most $m$? Let $\Sigma$ be an alphabet of size $2$, and consider minimal DFAs whose size is bounded by at most $m$.  Let $f(m)$ denote the number of different such minimal DFAs.

Can we find a closed-form formula for $f(m)$?

Considering that for $|\Sigma|=2$ the transition function of a DFA of size at most $m$ is a graph. Since the nodes degree is bounded by $2$, for each node there are $m^2$ possibilities of pairs of arcs (as suggested in the comments). In this graph there are at most $m$ possible choices of initial state and at most $2^m$ possible choices of final states sets. Thus, the maximum number of DFAs of size at most $m$ is $f(m) \leq m^{2m}\cdot m\cdot2^m = 2^m\cdot m^{2m+1}$.

We can generalize to an arbitrary alphabet $\Sigma$: the bound becomes $f(m) \le 2^m\cdot m^{|\Sigma|m+1}$.

But we bounded here arbitrary DFAs and I'm interested in bounding the number of minimal DFAs. Thus, it looks like this bound could be tighter... Does someone have a better estimate?

I would appreciate if possible, some papers related to this problem or a proof/counter-example.

According to Ishigami Y., Tani S. (1993) The VC-dimension of finite automata with $n$ states,
http://link.springer.com/chapter/10.1007/3-540-57370-4_58
,
the VC-dimension of the concept class of $n$-state DFAs over an alphabet of size $k$ is
$$ d=d(n,k) := (k-1+o(1))n\log_2 n.$$
It follows that there are at least $2^d$ distinct $n$-state automata on a $k$-letter alphabet. The upper bound on the number such automata follows from a simple counting argument (given in the paper), and is at most $2^d$.


Conductance and diameter in regular graphs Given an undirected, regular graph $G=(V,E)$, what is the relationship between its diameter - defined as the largest distance between two nodes - and its conductance, defined as $$\min_{S \subset V} ~\frac{e(S,S^c)}{\min(|S|,|S^c|)},$$ where $e(S,S^c)$ is the number of edges crossing between $S$ and $S^c$.

More concretely suppose I know the diameter is at least (or at most) $D$. What does this tell me about the conductance, if anything? And, conversely, suppose I know the conductance is at most (or at least) $\alpha$. What does this tell me about the diameter, if anything?

As Hsieh notes, your definition of conductance is off from the one I know by a factor of $d$, where $d$ is the degree of the regular graph. This is also known as edge expansion for regular graphs.

A relationship between edge expansion and diameter is quite easy to show. Intuitively, an expander is "like" a complete graph, so all vertices are "close" to each other. More formally, let

$$
\min_{S \subseteq V}\ { \frac{ e(S, S^c) }{ d \cdot \min\{|S|, |S^c|\} }} \geq \alpha
$$

Take any set of vertices $S$ with $|S| \leq |V|/2$. There are at least $\alpha d |S|$ edges coming out of $S$ and since $G$ is $d$-regular, the neighborhood of $S$ (including $S$ itself) is of size at least $(1+\alpha)|S|$. Applying this claim inductively, starting from $S = \{u\}$ for any vertex $u$, we see that for some $t = O(\log_{1 + \alpha } |V|)$, $u$'s $t$-hop neighborhood has size at least $|V|/2$. Therefore, the $t+1$-hop neighborhood of any vertex $v$ has to intersect the $t$-hop neighborhood of $u$, or the graph would have more than $|V|$ vertices, a contradiction. So you have

$$
D = O\left(\frac{\log |V|}{\log (1 + \alpha)}\right)
$$

Of course, it also follows that having a lower bound on the diameter implies an upper bound on edge expansion.

I don't think small diameter implies conductance. If you don't insist on regular graphs (and use Hsieh's definition), then two complete graphs connected by a single edge provides a counterexample.


Complexity Theory in Finance and journals? What journals are there that try to combine these two areas ? I came across the Algorithmic Finance Journal, are there others ? Looking at papers, mixed to overly -ve views about the quality and direction.

Not sure if such a combo can be useful in practice.

To answer your question, I don't think you have done your homework.

Look at the thread:
Computational complexity in quantitative finance

But if this is a general remark about the journal. The editorial board appears almost impeccable. Sure, it looks a bit suspect that the editor in chief advocated a field that has been dubbed controversial as seen in A New Kind of Finance.
Some critics maintain that the creation of the journal is strongly coupled with Wolfram Research's efforts to tap academics in the finance field. Other hidden agendas ?

Also consult with Wilmott's thread:
http://www.wilmott.com/messageview.cfm?catid=11&threadid=89959

Last, my 3 cents. The inaugural issue is one that usually sets the tone. Papers looked good.

Efficient Greek Estimation in Generic Swap-Rate Market Models.
This is by the great Mark Joshi. It deals with how to compute Greeks using automatic differentiation for a range of swap-rate market models. It's useful to practitioners since they want fast Greeks.

Markets are Efficient if and Only if P = NP. Not an expert in TCS, so refer to thread above computational-complexity-in-quantitative-finance for comments.

Forecasting Prices from Level-I Quotes in the Presence of Hidden Liquidity. Seemed important.

Binomial Options Pricing Has No Closed-Form Solution. Nifty. Nice read.


When to apply soft constraints evaluation functions in genetic algorithms? As stated in the question, say i created a random population of 100 timetables. 1 % of these timetables are valid. Then, if I apply the soft constraints evaluation functions on the 1% valid timetables, the population will have few outstanding finesses like below:

population = 5;

finesses = { 0.121,0.115,0.117,0.855,0.145} , the one in bold is an outstanding fitness and has the soft constraints evaluation functions applied on it. i have two hard constraints and three soft constraints and i use the weighted average to calculate overall fitness like this: (0.05)*h1+(0.05)*h2+(0.3)*s1+(0.3)*s2+(0.3)*s3

the question is:
Is this approach correct ?

someone suggested that i should treat soft and hard constraints the same, but if i do how can one soft constraints evaluate an invalid timetable!?

Experiment.  It depends on the topology of your problem domain. If you knew how to optimize more efficiently you wouldn't be throwing a GA at it.


Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$? There are several well-known $\mathsf{AC^0}$ circuit size lower-bound results based on random restrictions and the Switching Lemma.

Can we develop a Switching Lemma result to prove a size lower-bound for $\mathsf{TC^0}$ circuits (similar to the lower-bound proofs for $\mathsf{AC^0}$)?

Or is there any inherent obstacle to using this approach for proving $\mathsf{TC^0}$ lower-bounds?

Do barrier results like Natural Proofs say anything regarding using Switching Lemma like techniques to prove $\mathsf{TC^0}$ lower-bounds?

It is actually possible to make use of random restrictions to prove lower bounds for threshold circuits.

In particular in the paper Size-Depth Tradeoffs for Threshold Circuits, Impagliazzo, Paturi, and Saks use random restrictions to prove a superliner lower bound (on the number of wires) for constant depth threshold circuits computing the parity function.

With regards to proving superpolynomial lower bounds for $\mathsf{TC}^0$
 circuits then yes, the natural proof concept is of relevance since there are constructions of pseudo-random function generators in $\mathsf{TC}^0$.


Is the transducer version of BPP closed under complement? Obviously, recognizing BPP languages is closed under complement. For primes and composite integers both recognizing primes/composites and generating primes/composites can be done in "BPP". Is this true generally for BPP languages, i.e. can generating random words in a BPP language (and it's complement) be done in probabilistic polynomial time?

Specifically, given a probabilistic polynomial time algorithm which outputs strings in $F_2^n$ by computing the functions $g_i(x_k)$, where $i = 1 .. n$ and $x_k$ are random bits, is it possible to output (uniformly or otherwise) strings from the complement of the image of $g_i$, $F_2^n \setminus Im(g)$ in probabilistic polynomial time?

If so, is there a known practical algorithm to find the complement and what is its computational complexity and is that complexity bound optimal? If only an approximate complement can be computed efficiently, what are the upper bounds on approximation? Could there be a PCP theorem?

No. For example, if your input is a CNF with few solutions, then you can randomly generate non-satisfying assignment: just generate an assignment and keep it if it's non-satisfying. But generating a satisfying assignment is NP-hard.


Difference between PRAM and machine model in dynamic multithreading In the first edition of Introduction to Algorithms (Cormen et al., MIT Press, 1990), the discussion of parallel algorithms is based on the PRAM model. In the second edition, paralellism has been eliminated, but in the third edition (Cormen et al., MIT Press, 2009), the topic is reintroduced, but with a dynamic threading model (based on Cilk). The chapters are very different, for sure, and the models seem to be, as well, at least superficially. But I'm wondering: What are the differences in the underlying computational model or abstract machine here?

Their underlying model is still a shared-memory RAM machine with multiple processors. How is this different from the PRAM? Is it the case, perhaps, that they are in fact using the same underlying model, but approaching it differently? The threading is certainly handled differently in the classic PRAM algorithms – more in line with static threading, where you manually schedule which threads/processes are to run on which processors, rather than simply express concurrency/potential parallelism and have some automatic scheduler use the processors available. But still: Are there more fundamental differences?

In their chapter notes (3rd ed., Chapter 27), Cormen et al. write, “Prior editions of this book included material on […] the PRAM (Parallel Random Access Machine) model.” This seems to indicate that they do not view their dynamic multithreading as being built on this model. Is this so? If so, what differences am I missing?

Dynamic multithreading (like Cilk) does not involve processors working synchronously (in lockstep), for instance. PRAM is (sort of) SIMD, while DM is (sort of) MIMD. Notice that there are async PRAM models, but none seem to have gathered enough pull. Notice also that DM assumes logical parallelism, while PRAM is very much explicit parallelism, and that PREM machines (unlile DM) don't really exist beyond the lab.


Calculating a fast matrix vector product between vector of reals and a 0-1 matrix Given:
 some vector $R=(r_1...r_l)$ - real numbers,
 and a set of distinct vectors with $0$ or $1$ coordinates
  $$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\
  V_2=(c_{2,1} ... c_{2,l}),\\
   .....\\
  V_n=(c_{n,1} ... c_{n,l})\end{array}$$
  each $c_{i,j}$ are $0$ or $1$.
  $n\lt 2^l$ is some number. (For example in my case: $n=2^{10}, l=20$).

 Problem:
I need to calculate inner products $ (R, V_i) $ - how to do this in the fastest way ?
I mean how to organize calculations such that number of additions will be the smallest ?
The point is that some vectors have same subsequences of 1 and 0,
so I do not need to calculate several times such pieces.

Background: $V_i$ is fixed once and forever, "R" is coming every "millisecond".

Example:
    $V_1 = (1, 1 , 0 , 1)$
    $V_2 = (1, 1 , 1 , 1)$

Algorithm:

x = r_1+r_2+r_4
y= x+r_3

So $(R, V_1) = x$ ; $(R, V_2) = y$;  required only 3 additions, instead of naively seen $5=2+3$.

Well, if you dont mind some approximation than regular dimension reduction techniques would give you some speedup as they preserve (approximately) dot product.

Otherwise, you can think about each vector as being a CNF clause. If you just have to decide if the dot product is not zero for all vectors, then what you are asking for is the shortest equivalent DNF to the given CNF (or to be more precise some kind of minimal computation that compute the given CNF). This however is easier than the problem of deciding if the given CNF is never satisfiable, which is co-NP complete. In short, this problem should be computationally hard.

I think there was quite a bit of work on stuff like that in the learning community, especially in the dinosaurs age ;) (80s and earlier?).


The existence of planar distance preserver? Let G be an n-node undirected graph, and let T be a node subset of V(G) called terminals.  A distance preserver of (G,T) is a graph H satisfying the property

$$d_H(u,v) = d_G(u,v)$$

for all nodes u, v in T. (Note that H is NOT necessarily a subgraph of G.)

For example, let G be the following graph (a) and T be the nodes on the external face. Then graph (b) is a distance preserver of (G,T).

Distance preserver with various parameters are known to exist. I'm particularly interested in the one with the following properties:

G is planar and unweighted (that is, all edges of G has weight one),
T has size $O(n^{0.5})$, and
H has size (the number of nodes and edges) $o(n)$. (It would be nice if we have $O(\frac{n}{\log\log n})$.)

  Does such a distance preserver exist?

If one cannot meet the above properties, any kind of relaxations are welcomed.

References:

Sparse Source-wise and Pair-wise Distance Preservers, Don Coppersmith and Michael Elkin, SIDMA, 2006.
Sparse Distance Preservers and Additive Spanners, Béla Bollobás, Don Coppersmith, and Michael Elkin, SIDMA, 2005.
Spanners and emulators with sublinear distance errors, Mikkel Thorup and Uri Zwick, SODA, 2006.
Lower Bounds for Additive Spanners, Emulators, and More, David P. Woodruff, FOCS, 2006.

Distance preserver is also known as an emulator; many related work can be found on internet by searching the term spanner, which requires H to be a subgraph of G. But in my applications we can use other graphs as well, as long as H preserves the distances between T in G.

Many years later, it looks like OP has finally answered his own question: Near-Optimal Distance Emulator for Planar Graphs by Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes, and Oren Weimann was just posted on the arxiv.

The answer to the original question is yes: it is shown that $\widetilde{O}(\min\{t^2, \sqrt{tn}\})$ edges suffice to preserve distances between $|T| =: t$ terminals, which is optimal up to log factors.  In particular $\widetilde{O}(n^{3/4})$ edges suffice for the setting in the OP.  This preserver can also be computed in $\widetilde{O}(n)$ time; I would strongly suspect that the log factors in the size can be removed if we care only about existence and not computation time of the preserver, but I have not rigorously verified this.

(On a less formal note, I find this result really amazing.  Congrats!)


What is the smallest Turing machine where it is unknown if it halts or not? I know that the halting problem is undecidable in general but there are some Turing machines that obviously halt and some that obviously don't. Out of all possible turing machines what is the smallest one where nobody has a proof whether it halts or not?

The largest Turing machines for which the halting problem is decidable are:

$TM(2,3), TM(2,2), TM(3,2)$ (where $TM(k,l)$ is the set of Turing machines with $k$ states and $l$ symbols).

The decidability of $TM(2,4)$ and $TM(3,3)$ is on the boundary and it is difficult to settle because it depends on the Collatz conjecture which is an open problem.

See also my answer on cstheory about Collatz-like Turing machines and "Small Turing machines and generalized busy beaver competition" by P. Michel (2004) (in which it is conjectured that $TM(4,2)$ is also decidable).

Kaveh's comment and Mohammad's answer are correct, so for a formal definition of the standard/non-standard Turing machines used in this kind of results see Turlough Neary and Damien Woods works on small universal Turing machines, e.g. The complexity of small universal Turing machines: a survey (Rule 110 TMs are weakly universal).


How do I store data with a query that's a approximated ? I'm trying to find a way to store my data with fast access (better than O(n)).

My database consists of data (4096 byte strings) that represents some information about some items.
The problem is, that the query is never exact. I get one Item, and then need to find the closest match using a function F(a,b).

just an example:

1234
3456
6466
F(a,b) = return % of similar digits

GetClosest(1233,F) = 1234

The problem is that F(a,b) is a complicated algorithm, (not a proper metric).

What I have now is just go over the whole database to search for the best match.
Is there a kind of tree or other cluster database type that can give me faster finding complexity ?

More information:

F gives back a similarity value in %percentage. where 100% is a perfect match.

You should explain how F works ... however I try to give you some tips.

Suggestion 1

The standard information retrieval approach may help you:

split each "item" in small size words (for example 4 digits), and build an inverted index, i.e. a table that maps each word to the items that contains it:

word1 -> item1, item2, item5, ...
word2 -> item2, item3, item6, ...
...

Then if you must find items similar (closer) to item X:

split X in words w1 w2 w3 ... w4
easily (and quickly) retrieve items that contains those words
order the retrieved items according to your F (weighting each item using the number of  common words also contained in X)

You can also expand the inverted index to include the word positions if required by your function (w1#1 -> item1, item4; w1#2 -> item3, item6; ...).

Obviously, this approach works only if your F can be rearranged and calculated only using the word co-occurences.

The inverted index can be very large if the choosen word size is small.

Suggestion 2

Perhaps you can try to "fit" your data in a compressed prefix tree.

In the paper Prefix Tree Indexing for Similarity Search and
Similarity Joins on Genomic Data the authors combine several techniques and implement similarity searches (and joins) on a prefix tree.

We present PETER, a prefix tree based indexing algorithm supporting
approximate search and approximate joins. Our tool supports Hamming
and edit distance as similarity measure and is available as C++ library,
as Unix command line tool, and as cartridge for a commercial database.
It combines an efficient implementation of compressed prefix trees with
advanced pre-filltering techniques that exclude many candidate strings
early.

...Our experiments reveal that PETER is faster by orders of magnitudes compared to the command-line tools. Compared to RDBMS, it computes similarity joins in minutes for which UDFs did not finish within a day and outperforms the built-in join methods even
in the exact case.


Generate random permutation via iid uniforms --- is inverse transformation possible? A very common technique in the analysis of algorithms involving random permutations is to have each element $x$ select a rank $\rho(x)$ uniformly at random from the real interval $[0,1]$. The permutation $\pi$ is then formed by sorting on ranks.

Is it possible to invert this transformation? That is, given a permutation $\pi$ generated randomly in $S_n$, choose ranks $\rho(x)$ (with some additional randomness) such that

Over all possible $\pi$, each $\rho(x)$ is uniformly distributed in $[0,1]$
$\rho(\pi(1)) < \rho(\pi(2)) < \dots < \rho(\pi(n))$
(Optional) $\rho(\pi(i))$ depends only only $\pi(1), \dots, \pi(i)$

Seemingly, giving $\rho(\pi(1))$ the distribution on the minimum of  $n$ uniform variables, and so on, would work. Is there are any reference?

It's possible that what the OP wants is as follows:

Fix an ordering. By the standard trick using hyperplane arrangements, each such ordering represents one of the n! congruent simplices that make up the unit hypercube in $n$ dimensions.

Now the goal is to define a way of sampling from this simplex with independent samples from the data (rather than trying to sample from the simplex directly).

In fact this can be done. Luc Devroye's book describes the procedure (see V.3), which essentially boils down to letting $x_i$ be an exponentially distributed random variable, normalizing them, and then setting $\rho(\pi(i))$ to be the partial sum $\sum_{j \le i} x_i$ (I'm over simplifying a little, so what I said isn't entirely precise, but it's the general idea).


Quantum evasiveness conjecture? A property of simple $n$-vertex graphs is said to be evasive if its deterministic query complexity is exactly maximal, $\binom{n}{2}$ (that is, the best algorithm must query all $\binom{n}{2}$ possible edges in the worst case). The Evasiveness Conjecture (see here) is a strengtheneing due to Karp says that all nontrivial monotone graph properties are evasive. The current best lower bound of $(1/3 - o(1))n^2$ is due to Scheidweiler and Triesch, and the evasiveness conjecture is known to hold for various classes of graphs (and this). The smallest open case is for graphs on 10 vertices, see e.g. Angel & Borja.

Very recently, Aaronson, Ben-David, Kothari, and Tal used Huang's proof the Sensitivity Conjecture to show that the quantum query complexity of any nontrivial monotone graph property is $\Omega(n)$, which is optimal up to a constant.

The Evasiveness Conjecture conjectures the exact form of the deterministic query complexity of such properties.

  Is there a natural conjecture as to the exact form of the quantum query complexity of nontrivial monotone graph properties? If so, what is it, and how close/far are the current results from it?

The Evasiveness Conjecture has also been generalized to various classes of functions; I'd be interested to know about the same in the quantum setting as well.

Buhrman, Cleve, de Wolf, and Zalka (1999) mention quantum evasiveness, but only to show that some monotone graph properties do not require $\Omega(n^2)$ quantum queries. I had trouble finding anywhere else that discusses quantum evasiveness.

Update 2020 May 05: As pointed out by smapers in the answer & its comments, since the quantum query complexity of non-emptiness is $\Theta(n)$ (using Grover for the upper bound) and that of connectivity is $\Theta(n^{3/2})$, there is no function $f(n)$ that only depends on $n$. Leading me to refine the question to:

  Is there some nice (meta-)property of the monotone property such that there is a reasonable conjecture that depends on $n$ and that meta-property?

Really I'm just curious about a conjecture more refined than big-Theta.

Since the quantum query complexity typically denotes the bounded-error quantum query complexity, there's some ambiguity. A more precise question could be: "What is the quantum query complexity to decide nontrivial monotone graph properties with probability at least $2/3$?".

A natural example in this context is the monotone property of having a single edge. Since Grover search is optimal for this problem, its bounded-error quantum query complexity seems like the natural candidate.

update (2020 May 5):

Since the monotone property of connectivity has quantum query complexity $\Theta(n^{3/2})$ (see here), and the property of having a single edge has quantum query complexity $\Theta(n)$, there is actually no hope for a simple function $f(n)$ only dependent on $n$ to fully characterize the quantum query complexity of monotone graph properties (even up to constants). This is in contrast to what is conjectured for the classical deterministic query complexity.

Alternatively, one could ask about "the minimum possible quantum query complexity of a nontrivial monotone graph property" (as formulated in the paper by Aaronson, Ben-David, Kothari, and Tal). In this case, a simple function of $n$ might still be possible, and the complexity of having a single edge again seems like a natural candidate.

update 2 (2020 May 5):

Answering the updated question, a possible candidate for the additional property would be the (worst-case) certificate size $c$ of the property. A corresponding candidate for the query complexity would then be $\Theta(\sqrt{n^2 c})$, which describes the quantum query complexity when using Grover search on a graph that is empty apart from a single certificate (i.e., a minimal graph having the property). This would be consistent with the examples of having a single edge ($c = 1$) and connectivity ($c = n-1$).

Here's some other consistent examples:

Nonplanarity. Certificate size $c \in \Theta(n)$ (consider the graph obtained by replacing all edges of a $K_5$ graph by paths of length $\Omega(n)$). The quantum query complexity is $\Theta(n^{3/2}) = \Theta(\sqrt{n^2c})$ (link).
Having more than $\binom{n}{2}/2$ edges. Certificate size $\binom{n}{2}/2+1$. The quantum query complexity is $\Theta(n^{3/2}) = \Theta(\sqrt{n^2c})$ (link).
Triangle finding. Has certificate size $c = 3$. The current best upper bound is $\tilde{O}(n^{5/4})$ (Le Gall), but the best lower bound is only $\Omega(n) = \Omega(\sqrt{n^2 c})$.$^1$

$^1$At the end of his QIP talk (link), Le Gall does mention that he would be "surprised" if the quantum query complexity were $\tilde O(n)$.


All-or-Nothing Single-Sink Flow Problem I have a problem where I want to find the maximum flow from $s$ to $t$, such that, for an edge $e \in E$, $f(e) = 0$ or $f(e) = c(e)$. Where $f(e)$ is the flow in the edge and $c(e)$ its capacity. Basically, if a solution uses an edge, this edge is saturated.

I know this is an NP-hard problem, but I would like to know if there is any similar problem in the literature. Searching on Google I could only find algorithms for the All-or-Nothing Multicommodity flow problem, but I guess that my problem is simpler. I don't need to solve this optimally, approximation algorithms or heuristics are fine.

Thanks!

While I can't give you a name, I can provide evidence that the problem is $\mathbf{NP}$-hard to approximate to any factor, and thus is likely to be unstudied in full generality in the literature (hinting that it may remain unnamed).

Indeed, consider the $\mathbf{NP}$-hard instance of the problem you have in mind, with source $s$ and destination $t$. Via standard arguments, there is a corresponding $\mathbf{NP}$-hard decision problem, of the form "is it possible to route at least $k$ units of flow from $s$ to $t$"? I'll assume here that $k$ is polynomial, since that seems to be the case for most reductions I can think of (such as the one through Max-3D-matching). We begin with this problem to construct our inapproximable example.

Let $u$ denote the maximum (unrestricted) flow routable from $s$ to $t$, which is an upper bound for the solution to your problem. Further, let $t'$ be a new vertex you tack onto the graph. For every possible value in the set $Q = \left(\{k, k+1, k+2, k+3, \cdots, 2k-1\} \cup \{2k, 4k, 8k, 16k, \cdots \}\right)$ no larger than $u$, add a parallel edge with that capacity from $t$ to $t'$. While this transforms your graph into a multigraph (we will fix this later), the number of parallel edges we added here is at most polynomial.

If the original problem had a solution with value $\geq k$, then there is some amount of flow routable from $s$ to $t'$. Indeed, route that flow to $t$, decompose the amount of flow at $t$ into a sum of values in $Q$, and then route it along the corresponding edges. Otherwise, it is impossible to route any flow between $t$ and $t'$, and thus the maximum flow routable (in your set up) from $s$ to $t'$ is $0$.

Since the dependency on parallel edges can be removed by subdividing each edge with a vertex, we conclude that it's impossible to distinguish cases where the optimal solution has value $0$ from that  where it's at least some $k > 0$, and thus there is no multiplicative approximation. Standard modifications to this argument rule out additive (polynomial) approximations as well.

As a side note, this approach is pretty thematic in proving such hardness results, and in general problems that can encode an all-or-nothing "all solutions must be of size at least X" constraint for arbitrary X tend to be very inapproximable.


TCS Research Frontier with Huge Practical and Industrial Impact on our Society While CS theorists pursue the beauty and unity of their mathematical theories, their results can have a practical and industrial impact.

As we know, P versus NP is often talked about with its relation to public crypto. systems. Moreover, streaming algorithms often directly lead to industrial benefits.

Is there any possible research direction that would satisfy the following conditions?

(1)Solving problems in this area of TCS would lead to a fundamental change in our society.

(2)It would be required to understand other academic subjects (such as physics or electronics) to solve problems related to this TCS field.

I am afraid that this question is not appropriate for this stack exchange, but please forgive me if it is.

There are many examples of theoretical research that had a big impact on society, e.g., the RSA cryptosystem, the algorithm behind Google search, the algorithmic ideas behind Akamai, etc.
But the thing with basic research is that it's hard to know in advance what's going to be influential, when and how.

One potential candidate could be quantum computing, which has strong ties to both physics and electronics, and could make a huge difference (allowing efficient simulations of quantum systems, breaking RSA, and more). However, it's hard to know when quantum computers will be built (if at all).


Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete? In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks.

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

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

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

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

Classical physical problems often involve real-number positions or parameter values rather than values from a discrete set (such as the integers) which would be more typical of NP-complete problems. Because of this these problems can often be NP-hard but not (or not obviously) NP-complete. For instance, we do not know whether the Euclidean TSP (for integer points in the plane, with Euclidean distances) is NP-complete, because it hinges on an unsolved problem, the complexity of comparing sums of square roots. Some other geometric problems, such as the recognition of unit distance graphs (of some relevance as an abstraction of protein folding) are complete for the existential theory of the reals, which as far as we know is a different complexity class than NP.


Las Vegas vs Monte Carlo randomized decision tree complexity Background:

Decision tree complexity or query complexity is a simple model of computation defined as follows. Let $f:\{0,1\}^n\to \{0,1\}$ be a Boolean function. The deterministic query complexity of $f$, denoted $D(f)$, is the minimum number of bits of the input $x\in\{0,1\}^n$ that need to be read (in the worse case) by a deterministic algorithm that computes $f(x)$. Note that the measure of complexity is the number of bits of the input that are read; all other computation is free.

Similarly, we define the Las Vegas randomized query complexity of $f$, denoted $R_0(f)$, as the minimum number of input bits that need to be read in expectation by a zero-error randomized algorithm that computes $f(x)$. A zero-error algorithm always outputs the correct answer, but the number of input bits read by it depends on the internal randomness of the algorithm. (This is why we measure the expected number of input bits read.)

We define the Monte Carlo randomized query complexity of $f$, denoted $R_2(f)$, to be the minimum number of input bits that need to be read by a bounded-error randomized algorithm that computes $f(x)$. A bounded-error algorithm always outputs an answer at the end, but it only needs to be correct with probability greater than $2/3$ (say).

Question

What is known about the question of whether

  $R_0(f) = \Theta(R_2(f))$?

It is known that

  $R_0(f) = \Omega(R_2(f))$

because Monte Carlo algorithms are at least as powerful as Las Vegas algorithms.

I recently learned that there is no known separation between the two complexities. The latest reference I can find for this claim is from 1998 [1]:

[1] Nikolai K. Vereshchagin, Randomized Boolean decision trees: Several remarks, Theoretical Computer Science, Volume 207, Issue 2, 6 November 1998, Pages 329-342, ISSN 0304-3975, http://dx.doi.org/10.1016/S0304-3975(98)00071-1.

The best known upper bound of one in terms of the other is

  $R_0(f) = O(R_2(f)^2 \log{R_2(f)})$

due to [2]:

[2] Kulkarni, R., & Tal, A. (2013, November). On Fractional Block Sensitivity. In Electronic Colloquium on Computational Complexity (ECCC) (Vol. 20, p. 168).

I have two specific questions.

[Reference request]: Is there a more recent paper (after 1998) that discusses this problem?
More importantly, is there a candidate function that is conjectured to separate these two complexities?

Added in v2: Added ref [2], emphasized second question about existence of candidate function.

As far as I know, this is still open. A very recent paper that mentions these quantities and some bounds is Aaronson et al: Weak parity (see http://arxiv.org/abs/1312.0036). You can also see chapter 14 of Jukna: Boolean funcions and the 1999 (still beats 1998!) survey by Buhrman and de Wolf. Another very recent paper about randomized decision tree complexity is Magniez et al: http://arxiv.org/abs/1309.7565

Finally, a short summary I made for myself last month (without defs):

R2<=R0<=D<=n

D<=N0*N1<=C^2<=R0^2

s<=bs<=C<=s*bs<=bs^2 (new: [Gilmer-Saks-Srinivasan]: there is f s.t. bs^2(f)=O(C(f)))

D<=N1*bs<=bs^3<=(3R2)^3

deg<=D<=bs*deg<=deg^3 (new: [Tal]: bs<=deg^2)

D<=N1*deg

C<=bs*deg^2<=deg^4

Sensitivity conjecture is that s is also polynomially related to other parameters.


Number of accepting path of a non deterministic automaton I have a question that seems to me really natural and have probably already been studied. But keyword search on this site or google does not seems to help me to find any relevent paper.

I have got a finite non deterministic automaton $A$ over an alphabet $\alpha$ without epsilon-transition.

What can I tell about the number of different path the automaton could take for accepting a word ? In particular, I want to know if this number is bounded, or if for every $c$ I can find a word $w_c$ that is accepted in at least $c$ different way by the automaton.

Right now, I can find some necessary, and some sufficient condition, but not any necessary and sufficient condition, for the number to be unbounded

By clarity, I'll define the way I cound the number of accepting path. Let $w\in\alpha^*$ and $q$ a state, I can define the number of path to $q$ by inuction on $|w|$ by $N(\epsilon,q)=1$ if $q\in I$ else $0$, where $I$ is the set of initial state and $F$ of final state. $N(ws,q)=\sum_{q'\in Q\atop \delta(q',s)=q}N(w,q')$.

Then the number of path is $\sum_{q \in F}N(w,q)$.

This concept is called the ambiguity of the NFA.
Typically, there are 3 classes of ambiguity in this context: Bounded, polynomially bounded, and exponentially bounded.

Every NFA has at most an exponential number of runs on a given word (this is easy to see).

Interestingly, there is a simple syntactic characterization of polynomially bounded NFAs:

An NFA has a polynomial number of runs on a word $w$ iff for every state $q$, there is at most one cycle from $q$ to itself on every word $x\in \Sigma^*$. See this for details.

Testing for bounded ambiguity is PSPACE-complete. A good starting point is this paper


Exact algorithm or parameterized algorithm for Maximum Edge Biclique Problem? The Maximum Edge Biclique(MEB) problem is to find a biclique with as many edges as possible in a bipartite graph. It was proved to be NP-complete by Peeters in 2003, and then the inapproximability result for MEB was given by this paper in 2011 . But I could hardly find any exact algorithm or parameterized algorithm for MEB problem(maybe there are some).

What is the state of research on exact algorithm or parameterized algorithm for MEB problem? I appreciate if someone can provide guidance on where to look for such research and whether designing such algorithms is valid as a research point.

A good starting point could be the paper Exact exponential-time algorithms for finding bicliques which provides an $O(1.31^n)$-time algorithm for Constrained Bipartite Vertex Cover on graphs with $n$ vertices. As discussed in the paper this algorithm can be used to find bicliques with constraints on the sizes of the two parts. This in turn can be used to find bicliques with a maximum number of edges by considering all possibilities for the size constraints.

Concerning parameterized algorithms, it depends on the parameter that you want to consider.

If the parameter is the number $\ell$ of edges in the biclique, then a simple fixed-parameter algorithm can be obtained from the fact that whenever $\ell\le \Delta$ where $\Delta$ is the maximum degree of the input graph $G$, then we have a yes-instance. If $\ell>\Delta$, then one may find a maximum-edge biclique by considering for each vertex $v$ in $G$ the induced subgraph of $G$ containing $v$ and all vertices within distance 2 of $v$. This subgraph has $O(\Delta^2)$ vertices giving a running time of $2^{O(\ell^2)}\cdot n^{O(1)}$ for the nontrivial case. This can probably be improved but I am not aware of algorithms with running time $2^{O(\ell)}\cdot n^{O(1)}$.

If the parameter is the number of vertices in the maximum edge biclique, then one needs to be quite careful with the exact problem definition. For example,
if one asks for a biclique on at least $k$ vertices with at least $\ell$ edges, then one should obtain fixed-parameter tractability for $k$ by the above arguments. In contrast, if one asks for a biclique on at most $k$ vertices with at least $\ell$ edges, then the problem is a generalization of Balanced Bipartite Subgraph, also known as $(k,k)$-Biclique, which is W[1]-hard with respect to $k$ as shown by Bingkai Lin in The Parameterized Complexity of $k$-Biclique.


Isomorphism of ‘ordered’ DAGs / acyclic semiautomata I am wondering what is known about the isomorphism problem on ordered DAGs, in particular how to find a canonical representative modulo isomorphism.
By ordered I mean that each vertex has a list of outgoing edges in fixed order and that order must be respected by the isomorphism. I don't know if there is a widely used name for such structures.
An equivalent problem is probably isomorphism of acyclic deterministic semiautomata (the ordering of the edges can be recovered by just fixing an order on the alphabet and listing the transitions for a state in that order).
If the DAG is restricted to have only one root, it is trivial (just order by left-to-right DFS). Or, for the automaton, if the automaton has a designated initial state and all other states must be reachable. But if that's not the case, I'm at a loss.
I don't see any obvious polynomial reductions from GI-complete problems that I am familiar with. My intuition tells me this looks like it should be in P.
The best algorithm I came up with so far tries to successively label the nodes with numbers from 1 to n in a canonical way by picking the ‘smallest’ root w.r.t. some suitable partial ordering (e.g. based on the number of children and the ordering numbers that have already been assigned), but when there are still several minimal roots, I don't see how to get around trying all permutations of them.
There is a paper on isomorphism of ‘ordered graphs’ that seems to be similar to my problem except that their graphs are undirected and their ‘ordering’ is not a list, but a cyclic list. My intuition would tell me that my problem can be reduced to this (e.g. by adding some conspicuous ‘list beginning marker’ to recover the list from the cyclic list) but I am not quite sure. I am also not sure if there is not something more direct than their approach for my case.
EDIT: I thought about it a bit more and I think their approach doesn't work for my case at all. In my setting, there is an ordering on the outgoing edges of each node, but not on the ingoing ones. That makes a huge difference.
For illustration, here are two instances of the problem:

If you only need to order the outgoing edges the problem is GI complete. Reduce from GI of directed graphs. Given a digraph $D$ make a new one $D’$ as follows: Make a vertex in $D’$ for every vertex of $D$ and every arc of $D$. For every arc $u \rightarrow v$ of $D$, add the arcs: $uv \rightarrow u$ and $uv \rightarrow v$ in $D’$ (in this order). Clearly $D’$ is an (ordered) DAG and two digraphs $D_1$ and $D_2$ are isomorphic iff their corresponding ordered dags $D_1’$ and $D_2’$ are (ordered) isomorphic.
If you need to order both outgoing and incoming edges there is a simple polynomial time algorithm: if $D_1$ and $D_2$ are connected then fixing $f(u) = v$ (for $u \in V(D_1)$ and $v \in V(D_2)$) uniquely determines $f$.


Applications of Hamiltonian Cycle Problem The Hamiltonian Cycle Problem and Travelling Salesman Problem are among famous NP-complete problems and has been studied extensively.

I am looking for applications of the HamCycle and TSP.
What are some interesting real world problems where the HamCycle and TSP come up?

One application involves stripification of triangle meshes in computer graphics — a Hamiltonian path through the dual graph of the mesh (a graph with a vertex per triangle and an edge when two triangles share an edge) can be a helpful way to organize data and reduce communication costs.


What are the different notions of one-way functions? For instance, A function that is computable but not invertable in log space, Is it one-way function?

What are the known definitions of one-way functions? (especially the ones that do not invoke polynomials)

Usually one-way functions are used for crypto, and so you want that no efficient adversary can invert the function. Identifying efficient adversaries with randomized polynomial-time, you get  the typical notion of security which talks of randomized poly-time machines. But of course you can think of different security notions.

For super-fast crypto, you may want the one-way function to be computable in restricted models. Here a great result by Applebaum, Ishai, and  Kushilevitz shows that a poly-time computable OWF implies a OWF where each output bit depends on just O(1) input bits (which is arguably one of the simplest computational models you can think of).


Why are mod_m gates interesting? Ryan Williams just posted his lower bound on ACC, the class of problems that have constant depth circuits with unbounded fan-in and gates AND, OR, NOT and MOD_m for all possible m's.

What's so special about MOD_m gates?

They allow one to simulate arithmetic over any ring Z_m.
Before Ryan's result, throwing MOD_m gates to the mix gave the first class for which the known lower bounds did not work.

Is there any other natural reason to study MOD_m gates?

$ACC^0$ is a natural complexity class.

1) Barrington showed that computation over non-solvable monoids capture $NC^1$ while over solvable monoids capture $ACC^0$.

2) Recently, Hansen and Koucky  proved  a beautiful result that poly-sized constant width planar branching programs are exactly $ACC^0$. Without the planarity condition, we of course get Barrington's result characterizing $NC^1$.

So the difference between $ACC^0$ and $NC^1$ is group-theoretic on one hand and topological on the other.

Added: Dana, a simple example of a solvable group is $S_4$, the symmetric group over elements. Without getting into details, any solvable group has a series whose quotients happen to be cyclic. This cyclic structure gets reflected as mod gates while building a circuit to solve word problems over the group.

On planarity, one would like to believe that planarity may impose restrictions/bottlenecks in the flow of information. This is not always true: for example, variations of planar 3SAT are known to be NP-complete. However, in smaller classes, these restrictions are more "likely" to hold.

In similar vein, Wigderson showed NL/poly=UL/poly using the isolation lemma. We do not know how to derandomize the isolation lemma over arbitrary DAGs to get NL=UL, but we know how to do so for planar DAGs.


For log-space machines, why do we care about PRGs? Assumptions

I believe RL can be derandomized in polynomial time:

We need to store the following state:

The position of the head on the input.
The state of the TM

Both can be stored with O(log n) bits.
We use dynamic programming, building a table of poly(n) size encapsulating the state of the TM. Then, we march along the random bits, calculating the probability of each TM state after reading a given bit.

This should give us exact acceptance probability in $poly(n)$ time.

Observation

People care about prgs for log space machines.

Question:

Why? What can we do with a prg for RL that we can't do with an exact acceptance probability algo for RL ?

What is implied by a O(log n) seed length PRG for RL?

Thanks!

You show that RL$\subseteq$P. Better derandomization could show that RL=L.


What are theoretically sound programming languages for graph problems? There are numerous graph theoretic tools/packages. Each with its pros and cons. What should be the semantics/syntax of a programming language meant to solve graph theoretic problems?

You might want to look at The Graph Programming Language GP. From the linked page:

  GP (for Graph Programs) is a rule-based, nondeterministic programming language for solving graph problems at a high level of abstraction, freeing programmers from handling low-level data structures. The core of GP consists of four constructs: single-step application of a set of conditional graph-transformation rules, sequential composition, branching and iteration.

Sandra Steinert devoted her PhD thesis to the topic.

There's also a Hoare logic for reasoning about the correctness of such programs.


Can constant ambiguity reduce the state complexity of a regular languages? We say that NFA $M$ is Constantly Ambiguous if there exist $k\in \mathbb{N}$ such that any word $w\in \Sigma^*$ is accepted by either $0$ or (exactly) $k$ paths.

If automaton $M$ is constantly ambiguous for $k=1$, then $M$ is called Unambiguous FA (UFA).

Let $L$ be a regular language.

Can some constantly ambiguous automaton $M_c$ for $L$ be smaller than the smallest UFA that accepts $L$? How much smaller could it be?

Can Finitely ambiguous automaton be exponentially smaller than the smallest CFA for the same language?

It is known that there are Finitely ambiguous automatons (there exists $k$, such that every word is accepted by up to $k$ paths) which are exponentially smaller than the smallest UFA for the same language, but I haven't seen something about constant ambiguity.

Also, here's a related question I've posted here a few months ago.

EDIT:

Domotorp's answer shows that $CFA$ is polynomially reducible to $UFA$, but doesn't address the question of whether we can gain that polynomial space reduction by $CFA$s.

So the new question becomes: How much smaller (linearly/quadratically/etc.) can a $CFA$ be compared to the minimal $UFA$? for the same language?

I claim that if for some language there is a CFA with with $s$ states and $0$ or $c$ accepting paths for every word, then there is a UFA with $C_ss^c$ states. The basic idea is that the states of the UFA are the (ordered) c-tuples of the states of the CFA and it accepts if and only if all c states accept. Of course we also have to make sure that these were indeed different computations and that we do not count all $c!$ permutations, so for these we need some extra $C_s$ bits of storage.

A bit more detailed description of the basic idea: If $(s_1,\ldots,s_c)$ is a state of the UFA, then it has a transition from it (reading some letter $a$) to the state $(s_1',\ldots,s_c')$ if and only if the CFA has a transition (reading letter $a$) from $s_i$ to $s_i'$ for every $i$. A state $(s_1,\ldots,s_c)$ is accepting if and only if $s_i$ is accepting for every $i$. Of course the starting state of the UFA is $(s_0,\ldots,s_0)$ where $s_0$ is the starting state of the CFA.

The problem with the above is that the $c$ simulated runs of the CFA might be the same. So we add some extra information, encoded, say, in a graph on $c$ vertices that has an edge between vertex $i$ and vertex $j$ if during the run so far at least once we had that $c_i\ne c_j$.

Now we still have a problem, that we have counted everything $c!$ times because of the possible permutations. We can remedy this by requiring that if the $i$-th and $j$-th states have been the same until now and in the next step they would differ, then in the next step the $i$-th state should have a larger index.


TCS oriented refs/survey on group theoretic word problem The word problem for groups was shown to be Turing-complete in 1955 but has many decidable subcases. This problem arose more in mathematical group theory than in theoretical computer science, but now strong interconnections between the two are now known.

  Are there any TCS-oriented references or surveys on the word problem for groups or its applications?

Related questions:

bridge problems for group theory/formal languages, cs.se
Uses of algebraic structures in theoretical computer science, tcs.se

Related posts on RJ Lipton's blog:

Gromov's Theorem
Word problem for free groups

One family of results not mentioned in the excellent references of @Marzio's answer is relations between the isoperimetric (Dehn) function of a group $G$ and the nondeterministic time complexity of the word problem in $G$. For example:

For finitely generated groups $G$, $WP(G) \in \mathsf{NP}$ if and only if $G$ can be embedded in a finitely presented group that has polynomial Dehn function. (In fact, if $WP(G)$ can be solved in $\mathsf{NTIME}(T(n))$, then $G$ can be embedded in a group with isoperimetric function $\leq n^2 T(n^2)^4$.) (Birget-Ol'shanskii-Rips-Sapir)
There are individual groups whose word problem is $\mathsf{NP}$-complete (corollary to the preceding), and similarly groups whose word problem is $\mathsf{coNP}$-complete (Birget, also available on the arXiv).
The collection of functions $\mathcal{D}_4$ that are Dehn functions $\geq n^4$ of finitely presented groups are closely related to the collection $\mathcal{T}_4$ of time functions $\geq n^4$ of nondeterministic Turing machines. Specifically, $\mathcal{T}^4 \subseteq \mathcal{D}_4 \subseteq \mathcal{T}_4$, where $\mathcal{T}^4$ is the set of super-additive functions that are fourth powers of time functions of nondeterministic TMs. (Sapir-Birget-Rips)

See this survey by Sapir for more.