Math foundation for namespace problem TLDR;
What is the mathematics foundation for the namespace problem? Can I reduce namespace problem to set theory or other math concepts/objects (lambda calculus, category theory)?

I'm doing an essay on concepts like namespaces, packages and modules in programming languages. Among other topics, I'm studing how to avoid names collitions and in particular how programming languages solve the problem. For example:

Given any programming language, suppose that we have following user defined functions (or other language specific "object") named $a$ and $b$:

function a () {
  // do something
}

function b () {
  // do something
}

And a function called $c$ that uses above functions:

function c () {
  a();
  b();
}

If in the "context" above we defined another function called $a$, we would have a collision in function $c$ because it doesn't know what $a$-function implementation must use.

So to avoid name collisions a programming languages can implement namespace/package/module systems and let the programmer doing something like the following:

module alpha{
  function a () {
    // do something
  }
  function b () {
    // do something
  }
}

module beta{
  function a () {
    // do something
  }
}

And then doing:

function c () {
  alpha.a();
  alpha.b();
}

or

function c () {
  beta.a();
  alpha.b();
}

Thanks.

Looking around on google, I couldn't find much on this topic at all. However, I did find this thesis on arxiv, which I believe addresses this problem, albeit in a semi-roundabout way. As the author states in the conclusion

  The goal of this work was to discover namespaces in mathematical notation
  given a collection of documents with mathematical formulae. This
  problem could not be performed manually: this task it too time consuming
  and requires a lot of effort.
  To achieve the goal we proposed an automatic method based on cluster
  analysis. We noted that document representation in terms of identifiers is
  similar to the classic Vector Space Model. This allowed us to apply traditional document clustering techniques to the namespace discovery problem.

So cluster analysis seems to be something to look into here.

Hope this helps; I'll keep looking around for other resources.


Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving? A function $f: A^* \to A^*$ is regularity-preserving if, for each regular language $L$ of $A^*$, the language $f^{-1}(L)$ is regular. I think I have a proof, as a consequence of more general results, that the function defined by
$$
f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)
$$
is regularity-preserving. If this result is correct, could someone provide an elementary proof?

Here is a proposition for an elementary proof:
Let $\mathcal A=(A,Q,q_0,F,\delta)$ be a DFA for $L$, we want to build a DFA  $\mathcal A'=(A,Q',q_0',F',\delta')$ for $f^{-1}(L)$. Intuitively, when reading a word $u$, $\mathcal A'$ will remember the state reached in $\mathcal A$ by $f(u)$, together with the action of $u$ on all states of $\mathcal A$. More formally, we take:

$Q'=Q\times Q^Q$
$q_0'=(q_0,\mathit{id})$
$F'=F\times Q^Q$
$\delta_a'(p,g)=(\delta_a(g(p)),\delta_a\circ g)$

Where $\delta_a:Q\to Q$ is the transition function associated with a letter $a$.
This ensures that after reading a word $u$, the first component of the state of $\mathcal A'$ gives the state reached by $\mathcal A$ on $f(u)$.


Why is counting the number of hamiltonian subgraphs $\sharp P $ hard? I'm confused about how to prove either of the following closely related statements. They are both from this paper: https://epubs.siam.org/doi/10.1137/0208032

1) "A further problem that can be shown to be #P-hard is that of counting the number of Hamiltonian subgraphs of an arbitrary directed graph." (I think he means subgraphs as sets of edges, not induced by nodes.)

2) "Given a complete graph on n nodes and arbitrary
probabilities assigned to each edge, the probability that the graph has a Hamiltonian circuit (or some other NP-complete substructure) is easily seen to be #P-complete."

Given $1)$, it's easy to see that $2)$ problem is $\sharp P$ hard$^*$, but it's unclear to me why this problem is in $\sharp P$. Valiant mentions that $1)$ is likely not in $\sharp P$, so maybe this is a typo. $2)$ appears to perhaps even strictly harder than $1)$.

Can anyone give me a hint on how to think about $1)$?

(*In the following way: For any given graph $G$, embed $G$ into a complete graph. On that complete graph, set the probabilities for edges not in the embedding to zero, and for edges in the embedding to $1/2$. Then each subgraph of $G$ has probability $(1/2)^{E(G)}$ of appearing, so the probability that the random subgraph has a HC can be used to easily determine the number of subgraphs with Hamiltonian cycles. This shows that (given 1) ) it is $\sharp P$ hard to compute those probabilities.)

I think you could be interested by the counting class Span-P (which is the class of counting problems that can be defined as the number of distinct outputs of a nondeterministic Turing machine running in polynomial time). It was introduced in this paper. Both 1) and 2) are in Span-P. For 1): guess a subgraph, then guess a Hamiltonian circuit, then output the graph (of course order the nodes beforehand so that you don't output the same graph twice). For 2) something similar should work.

In this paper they also show that a version of 1) is Span-P complete (page 375). The only difference is that a number $k$ is also part of the input and they want only the Hamiltonian subgraphs of size $k$ (I'm assuming the "positive integer $c$" was a typo). Also at the end of Section 6 ("A variation of the above...") they specifically mention your problem (so without the restriction of size $k$) and they that they do not know if it is Span-P hard.


Euclidean transitive relations I am currently looking at relations that are both transitive and Euclidean, but not necessarily symmetric, hence not necessarily equivalence relations. I have found nothing about this kind of relations. Does anyone know of some work concerning these relations? And first of all do they have a name?

Thanks!

The correspondence theory of modal logic is concerned with the study of specific types of relations definable by modal formulae. My one sentence description does not do justice to the numerous motivations behind correspondence theory; consider it an explanation of why it relates to your sentence.

Specific examples arising in correspondence theory are the following.

The modal formula $\Box p \implies p$ is true in a frame if and only if the frame is reflexive.
The formula $\Box p \implies \Box \Box p$ is true in a frame if and only if the frame is transitive.

So the types of relations you are asking for can be viewed as being defined by a finite set of modal formulae. These formulae can in turn be viewed as the axioms of a logic, so your question is directly related to the study of modal logics. You can look up material on the model theory of modal logic for more details.

Modal Correspondence Theory, van Benthem
Modal Logic, Blackburn, de Rijke, Venema
Model Theory of Modal Logic, Goranko and Otto


W-types vs Inductive types Martin-Löf type theory uses W-types to define inductive structures like integers, lists, etc. However, calculus of inductive constructions doesn't use them in the same way, inductive types there seems to be more like axiom schemas.

Are these two approaches equivalent (they seem to be)? Are there any philosophical reasons why one is better than the other (for me, W-types feel like more intuitive, because the are just trees of special structure)? Which is easier from implementation point of view (inductive types seems to be better for me, since for W-types to be useful we need at least finite types and products to be available in a system's core)

(I'm assuming that by 'axiom schemas', you have in mind the work of Gimenez)

Extensionally, W-types and Gimenez' axiom schemas are equivalent.

However, in an intensional setting, you won't go far with W-types: they are too extensional (by the very definition of the encoding) to be fit for programming. This has been discussed by several authors, especially :

Conor McBride: http://mazzo.li/epilogue/index.html%3Fp=324.html
Peter Dybjer, "Representing inductively defined sets by wellorderings in Martin-Löf's type theory"
Guogen & Luo, "Inductive data types: well-ordering types revisited"


Clifford group quantum operations and classical computation The Clifford group of quantum operators is generated by the quantum operations:

Controlled-Z,
Hadamard, and
Phase ($= |0\rangle\langle0| + i |1\rangle\langle1|$).

A circuit composed only of these gates can be simulated efficiently on a classical computer. However, if I understand correctly, not all classical algorithms can be implemented efficiently using Clifford group operations, at least as far as we know.

Is there a construction to implement, even inefficiently or approximately, a classical algorithm using Clifford group operations?
For instance, how do you implement a Toffoli gate using Clifford group gates, if it's possible?

As pointed out in a comment above, if it were possible to coherently implement a Toffoli gate using Clifford group gates, then the Clifford group would be universal for quantum computation. It was noted in Section 5 of this paper that something even stronger is true: informally speaking, if there exists a class of quantum circuits which can be simulated efficiently classically, and which is universal for classical computation, then BQP=BPP. Thus we would expect simulable classes of quantum circuits not to be universal for classical computation.

Clifford group circuits themselves are particularly weak, and correspond to the complexity class Parity-L, as was shown here.


Space complexity to compute the optimal string alignment for the Levenshtein edit distance If we are given two strings of size $n_1$ and $n_2$, the standard Levenshtein edit distance computation is by a dynamic algorithm with time complexity $O(n_1 n_2)$ and space complexity $O(n_1 n_2)$. (Some improvements can be made as a function of the edit distance $d$, but we make no assumption on $d$ being especially small.) If you are only interested in the value of the edit distance (i.e., the minimal number of edits), a well-known improvement of the usual algorithm (where you only keep the previous and current row of the alignment table) reduces the space complexity to $O(\max(n_1, n_2))$.

However, if you want to get the actual edits of an optimal edit script, is it possible to do better than $O(n_1 n_2)$ memory usage, possibly at the expense of running time?

There is no need for the tradeoff that Yuval suggests.  The entire optimal editing sequence can be computed in $O(nm)$ time and $O(n+m)$ space, using a mixture of dynamic programming and divide-and-conquer first described by Dan Hirschberg.  (A linear space algorithm for computing maximal common subsequences.  Commun. ACM 18(6):341–343, 1975.)

Intuitively, Hirschberg's idea is to compute a single editing operation halfway through the optimal edit sequence, and then recursively compute the two halves of the sequence.  If we think of the optimal edit sequence as a path from one corner of the memoization table to the other, we need a modified recurrence to record where this path crosses the middle row of the table.  One recurrence that works is the following:

$$
Half(i,j) = \begin{cases}
   \infty & \text{if $i<m/2$}\\
   j & \text{if $i=m/2$}\\
   Half(i-1,j) & \text{if $i>m/2$ and $Edit(i,j) = Edit(i-1,j)+1$}\\
   Half(i,j-1) & \text{if $i>m/2$ and $Edit(i,j) = Edit(i,j-1)+1$}\\
   Half(i-1,j-1) & \text{otherwise}
\end{cases}
$$

The values of $Half(i,j)$ can be computed at the same time as the edit distance table $Edit(i,j)$, using $O(mn)$ time.  Since each row of the memoization table depends only on the row above it, computing both $Edit(m,n)$ and $Half(m,n)$ requires only $O(m+n)$ space.

Finally, the optimal editing sequence transforming the input strings $A[1..m]$ into $B[1..n]$ consists of the optimal sequences transforming $A[1 .. m/2]$ into $B[1 .. Half(m, n)]$ followed by the optimal sequence transforming $A[m/2 + 1 .. m]$ into $B[Half(m, n) + 1 .. n]$.  If we compute those two subsequences recursively, the overall running time obeys the following recurrence:
$$
T(m,n) = \begin{cases}
  O(n) & \text{if $m\le 1$}\\
  O(m) & \text{if $n\le 1$}\\
  O(mn) + \max_h \left( T(m/2,h) + T (m/2, n−h)\right)  & \text{otherwise}
\end{cases}
$$
It's not hard to prove that $T(m,n) = O(mn)$.  Similarly, since we only require space for one dynamic-programming pass at a time, the total space bound is still $O(m+n)$.  (The space for the recursion stack is negligible.)


Hardness of finding if a vertex lies on a simple directed path between two vertices Given a directed graph $G = (V, E)$ and three vertices $u, v, w \in V$. Is it NP-Hard to find whether there is a simple path from $u$ to $v$ passing through $w$?

I found a couple of hardness statements of similar problems referring all to the same paper [The directed subgraph homeomorphism problem, Fortune, Hopcroft and Wyllie, 1980]. The papers include

two disjoint directed paths,
and directed simple cycle passing through two vertices.

However, it is not very clear to me, if this case reduces directly to the paper as in the case of these to problems.

I just found a reduction from the two disjoint paths problem. Given a directed graph $G = (V, E)$ and two pairs $(s_1, t_1)$ and $(s_2, t_2)$, we can add a new vertex $w$ to the graph and an edge from $t_1$ to $w$ and from $w$ to $s_2$.

The new graph admits a simple path from $s_1$ to $t_2$ through $w$ if and only if the original graph admits two disjoint paths one from $s_1$ to $t_1$ and the other from $s_2$ to $t_2$.


paradox-driven computers? Has any research been done on paradox-driven computers?

An example of what I mean by "paradox-driven":

Given a computer which can send information back through time, an algorithm to instantly break passwords would be:

crackPassword(){
    String password=recieveFromFuture();
    if (password.checkIfCorrect()){
        sendToPast(password);//no paradox generated, valid password found.
    }else{
        sendToPast(password++);//paradox generated, this "parallel universe" cannot exist.
    }
    return password;
}

Since every parallel universe which does not contain a correct password is impossible, the user will continue on one or more valid "parallel universes".

This allows for the solution of any problem in O(1) time, so long as the answer is easily verified.

To the user this would appear as if the program immediately jumped to a valid password.

This idea, known as Time loop logic has been investigated by Moravec, Deutsch and Aaronson.


Sorted intervals query I'm in search for a data structure which efficiently operates over closed intervals with the following properties:

dynamically add or remove an interval
set, and anytime change, a number ("depth") for each interval. no two depths are ever the same
find all intervals that overlap with any given interval, sorted by "depth"

The closest structure I found is Interval tree but it lists the found intervals in arbitrary order with respect to their depths. I could collect all the "unsorted" intervals as reported and sort them afterwards but I was hopping it was possible to avoid to sort the result for every query.

Please, does anyone know of such data structure or have any suggestion how (if at all possible) to enhance the Interval tree to support such sorting?

Example:

add [1,2] to the empty structure and set its depth to 1
add [10,100], depth = 2
add [5,55], depth = 3
query for [5,50] reports [10,100] and [5,55]
set depth of [10,100] to 3, and of [5,55] to 2
query for [5,50] reports [5,55] and [10,100]

Edit

I'm more interested in fast adds/removes and queries, than in updating of depths. A depth can take as much as O(n), if that helps speed-up the other operations.

Using an interval tree and sorting results is a great solution.  It will have quite good running time.  You can add, remove, or find an interval in $O(\log n)$ time and change the depth of an interval in $O(1)$ time once you've found it.  Also, you can process an intersection query (report all intervals that overlap a given interval) in $O(\log n + m \log m)$ time, where $n$ is the total number of intervals and $m$ is the number of results.

Can you do better?  It seems clear that you can't do very much better.  Obviously, no comparison-based data structure can beat $\Omega(\log n + m)$ running time for intersection queries, so this trivial lower bound shows you are at most $\log m$ times slower than optimal.

Also, we can prove that no comparison-based data structure can beat $\Omega(\log n + m \log m)$ time for an intersection query in general, if you can change the depth of an interval in $O(1)$ time.  Consider the case $n=m$, and where all intervals overlap and should be returned.  If you could answer the intersection query faster than $O(m \log m)$ time, you could sort $m$ numbers faster than $O(m \log m)$ time, which we know is impossible for comparison-based algorithms.  (Well, more precisely, if you have $t$ arrays of length $m$, and if you knew how to answer intersection queries in $O(\log n + m)$ time and change depths in $O(1)$ time, you could sort all $t$ of those arrays in $O(m \log m + t (m + \log m)) = O(m (t+ \log m))$ time using your data structure by adding $m$ copies of the same interval, changing all their depths based on the first array, doing an intersection query, then changing all of their depths based on the second array, and so on.  However $O(m(t+\log m))$ running time is provably impossible for this task: the standard lower bound on comparison-based sorting shows that this takes $\Omega(t m \log m)$ time, and when $t$ is large enough, this is a contradiction -- e.g., when $t=m$, this would give a way to sort $m$ arrays of length $m$ in $O(m^2)$ time, when we know it actually takes $\Omega(m^2 \log m)$ time.)

So, if you want to hope for a data structure that allows intersection queries to run strictly faster than $\Theta(\log n + m \log m)$, you either need to allow changing the depth of an interval to take longer than $O(1)$ time, or you need to consider non-comparison-based data structures.

If you knew that your depths were all small integers, you could speed up this algorithm by using a faster sorting algorithm optimized for that case (e.g., counting sort).  However in practice existing sorting algorithms are already very fast so it's not clear whether this would make a big difference in practice.

So this algorithm already seems quite good, and it seems unlikely that we can beat it using comparison-based data structures.  If you want to do better, you'll have to specify a model of computation (e.g., the RAM model), but it's unclear that algorithms with a better asymptotic running time will lead to something that is faster in practice.


Natural problems in $NP \cap coNP$ not in $UP \cap coUP$? Are there any natural problems in $NP \cap coNP$ that are not (known to be/thought to be) in $UP \cap coUP$?

Obviously the big one everyone knows about in $NP \cap coNP$ is the decision version of factoring (does n have a factor of size at most k), but that is in fact in $UP \cap coUP$.

While parity games are known to be in both, it's been claimed that stochastic parity games are not known to be in UP intersect coUP.


The TOC Blog Aggregator is Offline I apologise if this is off-topic.

It seems that the domain name has expired. I hope some member(s) of the community here (I am not one) may know who was the administrator/owner of that site. It was quite a useful resource.

In 2007, Princeton professor Arvind  Narayanan created the TOC Blog Aggregator.

In 2018, CSTheory.se Moderator Suresh Venkatasubramanian  (@SureshVenkat) stepped down from moderating here, but took over the aggregator:

  Apologies for the downtime this week. This is @random_walker handing over the aggregator code (and this Twitter account) to @geomblog. Thanks everyone for following and special thanks to @geomblog for taking things over.— TCS blog aggregator (@cstheory) November 23, 2018


One-way quantum verification The theory of cluster-state computation is well-established by now, showing that any BQP circuit can be modified so it uses only single qubit quantum gates, possibly classically controlled, provided ample supply of a state known as the "cluster state" - which is a simple to produce stablizer state.

My question is: is a similar notion known for quantum verification - i.e.
can one replace QMA circuits with classically controlled 1-qubit gates, possibly using some "special state"?
At least initially, I'm unclear on why the cluster state can even work in this case.

It is possible to restrict the QMA verifier to single-qubit measurements and classical pre- and postprocessing (with randomness) while keeping QMA-completeness.

To see why, take any class of $k$-local QMA-complete Hamiltonians on qubits. By adding a constant of order $\mathrm{poly}(n)$ and rescaling with a $1/\mathrm{poly}(n)$ factor, the Hamiltonian can be brought into the form
$$
H=\sum_i w_i h_i\ ,
$$
where $w_i>0$, $\sum_i w_i=1$, and $h_i = \tfrac12(\mathrm{Id}\pm P_i)$, where $P_i$ is a product of Paulis. Estimating the smallest eigenvalue of $H$ up to accuracy $1/\mathrm{poly}(n)$ is still QMA-hard.

We can now build a circuit which only uses single-qubit measurements which, given a state $|\psi\rangle$, accepts with probability $1-\langle\psi|H|\psi\rangle$ (which by construction is between $0$ and $1$).  To this end, first randomly pick one of the $i$'s according to the distribution $w_i$. Then, measure each of the Paulis in $P_i$, and take the parity $\pi$ of the outcomes, which is now related to $\langle\psi|h_i|\psi\rangle$ via
$$
\langle\psi|h_i|\psi\rangle = \tfrac12(1\pm (-1)^\pi)\in\{0,1\}\ .
$$
The circuit now outputs $1-\langle\psi|h_i|\psi\rangle$, and the output is therefore distributed according to $\langle\psi|H|\psi\rangle$.

This is, if we picked a yes-instance of the (QMA-complete) local Hamiltonian problem, there is a state $|\psi\rangle$ such that this verifier will accept with some probability $\ge a$, while otherwise any state will be rejected with probability $\le b$, with $a-b>1/\mathrm{poly}(n)$.  The variant of QMA where the verifier is restricted to one-qubit measurements is therefore QMA-complete for some $1/\mathrm{poly}(n)$ gap.  Finally, this version of QMA can be amplified using just the conventional amplification techniques for QMA, which finally proves it is QMA-complete independent of the gap (within the same range as QMA).


A k-approximation to k-way number partitioning The $k$-way number partitioning problem accepts as input a multiset $S$ of positive numbers, and returns a partition of $S$ into $k$ subsets such that the subset sums are as nearly-equal as possible, namely,

the largest sum is as small as possible, or -
the smallest sum is as large as possible.

Both problems are NP-hard even for $k=2$. Denote the optimal solutions of both problems by $MinMax(S,k)$ and $MaxMin(S,k)$ respectively. Note that both are weakly-decreasing functions of $k$. Are there polynomial-time algorithms that find a partition of $S$ into $k$ subsets such that -

the largest sum is at most $MinMax(S,k-1)$, or -
the smallest sum is at least $MaxMin(S,k+1)$?

The Wikipedia page on number partitioning describes many polynomial-time approximation algorithms for this problem, but they have guarantees of different forms -  at most $(1+\epsilon)\cdot MinMax(S,k)$ or at least $(1-\epsilon)\cdot MaxMin(S,k)$.
There are also algorithms that give constant-factor approximations to the related problems of bin packing and bin covering. Using these algorithms and binary search, I think it is possible to find approximations to number partitioning in weakly-polynomial time. However, the guarantees would be of the form $MinMax(S,k/(1+\epsilon))$ or $MaxMin(S,k/(1-\epsilon))$, where $\epsilon$ is the corresponding approximation factor.
is it possible to attain in polynomial time, an additive $k$-approximation?

This is not an answer - it is just a reply to Neal Young's comment regarding the greedy algorithm. I claim that in the outcome of the greedy algorithm:

The largest sum is at most $\operatorname{MinMax}(S, \lfloor(k+1)/2\rfloor)$;
The smallest sum is at least $\operatorname{MaxMin}(S, 2k-1)$.

Proof. Let $X_1,\ldots,X_k$ be the outcome of the greedy algorithm. It is sufficient to prove the claims for an arbitrary subset from this partition, say for $X_1$. For any set $X$, denote by $v(X)$ the sum of numbers in $X$.
Proof of 1.
Let  $Z_1,\ldots,Z_{\lfloor(k+1)/2\rfloor}$ be a min-max partition.
If $X_1$ contains a single item, then it is contained in at least one $Z_i$, so $v(X_1)\leq \max_i v(Z_i)$.
Otherwise, let $x_1$ be the last item added to $X_1$. By the greedy algorithm definition, both $v(x_1)$ and $v(X_1\setminus \{x_1\})$ are smaller than $v(X_2),\ldots,v(X_k)$. So in the $(k+1)$-partition $\{x_1\},X_1\setminus \{x_1\},X_2,\ldots,X_k$, the first two elements are smallest. Therefore, their sum is at most $2/(k+1)$ of the total:
\begin{align*}
v(X_1) \leq \frac{2}{k+1}v(S)
\end{align*}
On the other hand:
\begin{align*}
\max_i v(Z_i) \geq \frac{1}{\lfloor(k+1)/2\rfloor}v(S)
\geq
\frac{2}{k+1}v(S)
\end{align*}
Therefore, $v(X_1)\leq \max_i v(Z_i)$ too.
Proof of 2.
Let $x_2,\ldots,x_k$ be the last item added to $X_2,\ldots,X_k$ respectively.
By the greedy algorithm definition, if we remove $x_2,\ldots,x_k$ from $X_2,\ldots,X_k$, then $v(X_1)$ is largest among the remaining subsets. Therefore,
\begin{align*}
v(X_1)\geq \frac{1}{k}v(S\setminus \{x_2,\ldots,x_k\})
\end{align*}
Let $Y_1,\ldots, Y_{2k-1}$ be an optimal $(2k-1)$ partition.
The items $x_i$ belong to at most $n-1$ sets in the partition $Y$, so there are at last $n$ sets in that partition that do not contain any $x_i$; denote them by $Y_1,\ldots,Y_k$. So
\begin{align*}
\min_{i=1}^{2k-1} v(Y_i)
\leq
\min_{i=1}^{k} v(Y_i)
\leq
\frac{1}{k}v(Y_1\cup\cdots \cup Y_k)
\leq
\frac{1}{k}v(S\setminus \{x_2,\ldots,x_k\})
\end{align*}
Therefore, $v(X_1)\geq \min_i v(Y_i)$.
So the greedy algorithm is a 2-approximation. The question of whether there exists an additive approximation remains open.


Fast private computation of dot product Consider two paranoid parties Alice and Bob. Say Alice owns a secret vector $x=(x_1,\ldots,x_n) \in \mathbb R^n$ and Bob owns a secret vector $y=(y_1,\ldots,y_n) \in \mathbb R^n$.

Question. How can both parties compute the dot product $x\cdot y$ in time $\mathcal O(n)$ without leaking their respective secrets ?

I will assume you are in the honest-but-curious model.  You can't represent real numbers in finite space, so I will assume all values are represented in fixed-point arithmetic, to $d$ bits of precision; thus $x$ is represented as $x = x'/2^d$ where $x'$ is an integer.  Then $x \cdot y = x' \cdot y' / 2^{2d}$, so the problem is equivalent to computing $x \cdot y$ where $x,y \in \mathbb{Z}^n$.  Here is a scheme for that.
Pick a sufficiently large prime, and let $E$ denote a public-key encryption algorithm that is additively homomorphic modulo $p$.  Alice generates a public/private keypair for $E$, and computes $E(x_i)$ for each $i$.  She sends these to Bob, along with the public key she generated.  Bob computes $E(x_i y_i)$ for each $i$, using the homomorphic properties of $E$, and from them, computes $E(\sum_i x_i  y_i) = E(x \cdot y)$, again using the homomorphic properties of $E$.  Bob sends $E(x \cdot y)$ to Alice.  Alice decrypts, and shares the result with Bob.
Note that if $E$ is additively homomorphic, given $E(x)$ you can compute $E(2x) = E(x+x)$.  Therefore, given $E(x)$ and an integer $y$ you can compute $E(xy)$, using a double-and-add algorithm (analogous to square-and-multiply).


Who introduced the complexity class AC? I taught $AC^0$ lower bounds today, and one of the students asked about the reason for the name $AC$.
The official explanation is that the "A" stands for "Alternation".

I vaguely remember being told many years ago that Nick Pippenger Steve Cook named $NC$ after Nick Pippenger (Nick's class), and later Nick named $SC$ after Steve (Steve's class).

The $NC$ part of the story is documented, e.g., in Wikipedia and in the complexity zoo, the story for $SC$ is told here.

I wonder whether $AC$ has a similar history, but I couldn't find any reference to $AC$'s inventor.

Does someone know who defined $AC$?

I believe that the notation AC first appears in Cook's "A Taxonomy of Problems with Fast Parallel Algorithms" from 1985. On page 11 (page 12 of the journal) we read:

  To state a more general form of this result we introduce the following terminology.

  Definition. $AC^k$, for $k=1,2,\ldots$, is the class of problems solvable by an ATM in space $O(\log n)$ and alternation depth $O(\log^k n)$.

This class is actually a uniform version of AC.

There follows an alternative characterization by Ruzzo and Tompa, appearing in a technical report by Stockmeyer and Vishkin, and later on in "Constant depth reducibility" by Chandra, Stockmeyer and Vishkin from 1984. They use the notation SIZE-DEPTH(poly, constant) (see page 3).

Cook goes on to mention another unpublished characterization by himself and Ruzzo. Further results due to Ruzzo are mentioned, including $AC^k \subseteq NC^{k+1}$ ("On uniform circuit complexity", Ruzzo, 1981). The latter paper (as well as Ruzzo's earlier paper also mentioned) doesn't contain the notation AC, but rather a myriad of other notations, emphasizing the notion of uniformity used.

All these papers mention alternating Turing machines a lot, giving credence to the hypothesis that A stands for alternating.


Asymptotic Approximation to Number of Knapsack Solutions Is there an asymptotic approximation to the fraction of sets satisfying a knapsack feasibility constraint?

More precisely, imagine I have a large number $n$ of items with bounded weights $X_1,...,X_n \in [0,1]$. For a given bound $Y$, I want to compute the fraction of sets $S \subset \{1,...,n\}$ which satisfy the feasibility constraint $\sum_{i \in S} X_i \leq Y$. That is, I want to compute:

$$N(X_1,...,X_n,Y) =  \frac{\# \{S: \sum_{i \in S} X_i \leq Y\}}{2^n}$$

I want to understand how the ``partial derivatives'' of $N$ behave when $X$ and $Y$ change. That is, I want to compute some analogue of $\frac{\partial N}{\partial X_i}$ or $\frac{\partial N}{\partial Y}$. As defined, the function $N$'s partial derivatives are not very interesting: the function is constant, except at regions of discontinuity where the number of feasible sets changes, and at those points the derivatives do not exist.

More concretely, I want to know if there's a function $F(X_1,...,X_n,Y,n)$ such that

F is differentiable in $X_1,...,X_n,Y$
$\lim_{n \to \infty} \frac{F(X_1,...,X_n,Y, n)}{N(X_1,...,X_n,Y)} = 1$

I know that, when $X_1,...,X_n = 1$, then $N(X_1,...,X_n,Y)=\sum_{k=0}^{\lfloor Y \rfloor} \frac{\binom{n}{k}}{2^n}$, which converges to the normal CDF $\Phi(Y; \frac{n}{2}, \frac{n}{4})$. But I don't know if this kind of approximation generalizes to arbitrary bounded $X_i$.

The answer is no, assuming we interpret Condition 2 as follows:

For every infinite sequence $X_1,X_2,\ldots$ with each $X_i$ in $[0,1]$,
$$\lim_{n \to \infty} \frac{F(X_1,...,X_n,Y, n)}{N(X_1,...,X_n,Y,n)} = 1.$$

Lemma 1. No function $F$ that satisfies the above condition is continuous (much less differentiable) in every $X_i$.

Proof. Fix any candidate function $F$ that is continuous in each $X_i$.  Fix $Y=1$. To complete the proof, we show there must be a sequence $X_1', X_2', \ldots$ such that
$$\lim\inf_{n\rightarrow\infty} \frac{F(X_1',\ldots,X_n',1,n)}{N(X_1',\ldots,X_n',1,n)} = 0$$
or
$$\lim\sup_{n\rightarrow\infty} \frac{F(X_1',\ldots,X_n',1,n)}{N(X_1',\ldots,X_n',1,n)} = \infty.$$

Start by fixing an arbitrarily large index $n_1$.  To ease notation, for $z\in[0,1]$, define
$$\begin{align}
 F_1(z) &{} = F(z, z, \ldots, z, 1, n_1), \text{ and } \\
 N_1(z) & {}= N(z, z, \ldots, z, 1, n_1).
\end{align}$$
(That is, the restrictions of $F$ and $N$ to $X_1=X_2=\cdots=X_{n_1}=z$, $Y=1$, and $n=n_1$.)

Fix $\epsilon_1>0$ such that
$$F_1(1/2) - F_1(1/2+\epsilon_1) \le 1/2^{n_1}.$$
(This is possible because $F_1$ is continuous, as $F$ is continuous in each $X_i$.)

Meanwhile, by inspection
$$
\begin{aligned}
N_1(1/2+\epsilon_1) &{} = (1 + n_1)/2^{n_1} &&{} = \Theta(n_1/2^{n_1}), & \text{ while} \\
N_1(1/2) &{} = \Big(1 + n_1 + {n_1 \choose 2}\Big)/2^{n_1} &&{} = \Theta(n_1^2/2^{n_1}).
\end{aligned}
$$

Case 1.1. First consider the case that $F_1(1/2+\epsilon_1) \le n_1^{3/2}/2^{n_1}$.

In this case, define $X'_1 = X'_2 = \cdots = X'_{n_1} = 1/2$.
Then
$$\frac{F(X'_1, \ldots, X'_{n_1}, 1, n_1)}{N(X'_1,\ldots, X'_{n_1}, 1, n_1)} =
\frac{F_1(1/2)}{N_1(1/2)}
\le
\frac{F_1(1/2+\epsilon_1)+1/2^{n_1}}{N_1(1/2)}
= O(1/\sqrt{n_1}).$$

Case 1.2. Otherwise $F_1(1/2+\epsilon_1) > n_1^{3/2}/2^{n_1}$.

In this case, define $X'_1 = X'_2 = \cdots = X'_{n_1} = 1/2 + \epsilon_1$.
Then $$\frac{F(X'_1, \ldots, X'_{n_1}, 1, n_1)}{N(X'_1,\ldots, X'_{n_1}, 1, n_1)} = \frac{F_1(1/2+\epsilon_1)}{N_1(1/2+\epsilon_1)} = \Omega(\sqrt{n_1}).$$

So, at index $n=n_1$, the ratio in question is either $O(1/\sqrt n)$ or $\Omega(\sqrt n)$.

To continue, choose index $n_2 \ge n_1^2$,
and set the values of $X'_{n_1+1}, X'_{n_1+2}, \ldots, X'_{n_2}$ as follows. Define
$$\begin{align}
 F_2(z) &{} = F(X'_1, X'_2, \ldots, X'_{n_1}, z, z, \ldots, z, 1, n_2), \text{ and } \\
 N_2(z) & {}= N(X'_1, X'_2, \ldots, X'_{n_1}, z, z, \ldots, z, 1, n_2).
\end{align}$$
(Above, $z$ occurs $n_2-n_1$ times in each parameter list.)
Fix $\epsilon_2>0$ such that
$$F_2(1/2) - F_2(1/2+\epsilon_2) \le 1/2^{n_2}.$$
(This is possible because $F_2$ is continuous, as $F$ is continuous in each $X_i$.)

By inspection, using that $n_2 \ge n_1^2$,
$$
\begin{aligned}
N_2(1/2+\epsilon_2) &{} = O((n_1^2 + n_2)/2^{n_2}) &&{} = O(n_2/2^{n_2}), & \text{ while} \\
N_2(1/2) &{} \ge {n_2 \choose 2}/2^{n_2} &&{} = \Theta(n_2^2/2^{n_2}).
\end{aligned}
$$

Case 2.1. First consider the case that $F_2(1/2+\epsilon_2) \le n_2^{3/2}/2^{n_2}$.

In this case, define $X'_{n_1+1} = X'_{n_1+2} = \cdots = X'_{n_2} = 1/2$.
Then
$$\frac{F(X'_1, \ldots, X'_{n_2}, 1, n_2)}{N(X'_1,\ldots, X'_{n_2}, 1, n_2)} =
\frac{F_2(1/2)}{F_1(1/2)}
\le
\frac{F_2(1/2+\epsilon_2)+1/2^{n_2}}{N_2(1/2)}
= O(1/\sqrt {n_2}).$$

Case 2.2. Otherwise $F_2(1/2+\epsilon_2) > n_2^{3/2}$.

In this case, define $X'_{n_1+1} = X'_{n_1+2} = \cdots = X'_{n_2} = 1/2 + \epsilon_2$.
Then $$\frac{F(X'_1, \ldots, X'_{n_2}, 1, n_2)}{N(X'_1,\ldots, X'_{n_2}, 1, n_2)} = \frac{F_2(1/2+\epsilon_2)}{N_2(1/2+\epsilon_2)} = \Omega(\sqrt{n_2}).$$

So, at index $n=n_2$, the ratio in question is either $O(1/\sqrt n)$ or $\Omega(\sqrt n)$.

Continuing in this way, we can set $X'_1, X'_2, \ldots$ so that there is an infinite sequence of indices $1\le n_1 < n_2 < n_3 < \cdots$
such that, at each index $n=n_i$, the ratio in question is either $O(1/\sqrt n)$ or $\Omega(\sqrt n)$.

Then either there are infinitely many indices $n$ such that the ratio is $O(1/\sqrt n)$, in which case
$$\lim\inf_{n\rightarrow\infty} \frac{F(X_1',\ldots,X_n',1,n)}{N(X_1',\ldots,X_n',1, n)} = 0,$$
or there are infinitely many indices $n$ such that the ratio is $\Omega(\sqrt n)$, in which case
$$\lim\sup_{n\rightarrow\infty} \frac{F(X_1',\ldots,X_n',1,n)}{N(X_1',\ldots,X_n',1, n)} = \infty.$$
$~\Box$


A natural problem in $\textrm{S}_2^\textrm{P}$? The complexity class $\textrm{S}_2^\textrm{P}$ is defined as follows (from Wikipedia):

  A language $L$ is in $S_2^P$ if there exists a polynomial-time predicate $P$ such that

  If $x \in L$, then there exists a $y$ such that for all $z$, $P(x,y,z)=1$
  If $x \notin L$, then there exists a $z$ such that for all $y$, $P(x,y,z)=0$

  where the size of both $y$ and $z$ must be polynomial in the size of $x$.

Also see Fortnow's post and the complexity zoo for more informal explanations and discussions.

While this class seems reasonably natural, I can't find an example of a problem that's in $\textrm{S}_2^\textrm{P}$ for a non-trivial reason (i.e., not just because it is in NP or MA or some class contained in $\textrm{S}_2^\textrm{P}$). Does anyone know a problem that fits this description?

If no one can think of a problem like that, I wouldn't mind a problem that's in a sub-class of $\textrm{S}_2^\textrm{P}$, but it's non-trivial to show this, whereas the problem is obviously in $\textrm{S}_2^\textrm{P}$.

How about a problem complete for promise-$\mathsf{S_2^p}$?

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, and Chris Umans. On the complexity of succinct zero-sum games. Computational Complexity 17:353-376, 2008.

From the abstract:

  We prove that approximating the value of a succinct zero-sum game to within an additive factor is complete for the class promise-$\mathsf{S_2^p}$, the "promise" version of $\mathsf{S_2^p}$. To the best of our knowledge, it is the first natural problem shown complete for this class.

(Historical note: it is not too surprising that not many natural problems are known to be in $\mathsf{S_2^p}$ but not known to be in its subclasses $\mathsf{MA}$ or $\mathsf{P^{NP}}$. If you check the original papers of Russell--Sundaram and Canetti (independently), it seems as though the definition of $\mathsf{S_2^p}$ was made more or less specifically to capture their improved arguments placing $\mathsf{BPP}$ in $\mathsf{PH}$, rather than to capture some set of of natural problems.)


Matching on bipartite graph - multiple edges I have a weighted bipartite graph consisting of two sets $S$ and $P$. ($|S| > |P|$).
I need to find a matching so that every node $s$ in $S$ matches a node of $P$. But a node $p$ in $P$ can match multiple nodes of $S$. Each $p$ has an individual limit of how many nodes it can match. The total weight of the matching should be as small as possible.

My research ended quite quick because I do not know the right key words to search for. Does this kind of matching problem have a specific name?

Second question: Do you already know some algorithms I should have a glance at?

According to the comments above, the problem can be reduced to a weighted bipartite matching / assignment problem.

If $f(p)$ specifies the limit of matches for a node in $P$, we replace each $p$ by $f(p)$ nodes.
To assure $|S| = |P|$ we can add dummy nodes to $S$.

Now we can solve the problem by a standard algorithm. E.g. Hungarian Method.


Reading Papers with Unclear Typesetting From time to time, I have to read a paper with unclear typesetting. By this, I mean:

very small fonts; sometimes 8pt or smaller.
very bad scan;
Using bitmap fonts instead of vector ones.
too old formatting (usually dating back to 1970s or the beginning of 1980s.)

In these cases, one might prefer to read a more clear version submitted to the authors' home page. Unfortunately, the author version is not always available; and even in that case, they might be very lengthy (the so-called full version of the paper).

In the case of bitmap fonts, I found a good strategy: Find the postscript (PS) version of the paper, and convert the bitmap fonts to their vector counterparts using pkfix or a combination of pkfix-helper + pkfix, whichever applies (read the documentation).

However, I still can't find a workaround for other problems. Specially, small-font papers bother me a lot. My best bet is to use a desk lamp: I don't know why, but magically the words seem  larger under its light!

  How do you read a paper whose typesetting is unclear? Specially, what do you do when the font is too small to read?

PS: Some months ago, I found an application which "splited" a PDF into several segments, so that they were easy to read on an iPhone or the like. (Sorry, I don't recall the name of that app.) However, the output was downgraded to fit the iPhone small screen, and therefore it wasn't apt for computer screen or printer.

If you work on a university campus, there's likely a large building nearby full of study carrels and magazine racks called a "LIE-BURY".  Deep in the bowels of such buildings, one can often find images of old research papers inscribed onto thin sheets of cellulose fiber extracted from wood and cotton, called "paper", and then bound into larger brick-sized objects called "books".  (At least according to Wikipedia, this is the reason we call our research reports "papers".  Who knew?!)

Surprisingly, despite the crudeness of the technology that produced them, these so-called "books" are often significantly easier to read than their more modern electronic counterparts.

One serious disadvantage of this approach is that one must actually walk all the way across campus, but we all must occasionally suffer for our art.


Describing state machines mathematically The short paper "Computer Science and State Machines" by Leslie Lamport seems quite strange to me.
On the one hand, I am surprised to see that an important hardware protocol called "two-phase handshake" can be derived from a trivial program, simply by mathematical substitution.
On the other hand, I think that this example is (and should be) chosen deliberately. What I doubt about is its generality. If this method (i.e., describing state machines mathematically and deriving a protocol from its specification by mathematical substitution) is so fresh that researchers have not developed a general theory, I would like to see more examples.

My question is straightforward:

  Is this derivation a coincidence? Could anyone offer more examples or related references?

The derivation of the "two-phase handshake" protocol from a trivial program:

The trivial program mentioned above is just to alternately perform the $\mathcal{P}$ and $\mathcal{C}$ operations:

  $\mathcal{X}: \textrm{ loop } \mathcal{P} \textrm{ } ; \textrm{ } \mathcal{C} \textrm{ endloop}$

By introducing a variable $pc$ to represent the "program counter", $\mathcal{X}$ can be described as the following state machine:

  $Init_{\mathcal{X}} \triangleq (pc = 0) \land Init_{\mathcal{PC}}$
  $Next_{\mathcal{X}} \triangleq \big( (pc = 0) \land \mathcal{P} \land (pc' = 1) \big) \lor \big( (pc = 1) \land \mathcal{C} \land (pc' = 0) \big)$

where $Init_{\mathcal{X}}$ denotes the set of initial states; $Next_{\mathcal{X}}$ specifies the next-step transition. $Init_{\mathcal{PC}}$ specifies the initial values of the variables in $var_{\mathcal{PC}}$ involved in $\mathcal{P}$ and $\mathcal{C}$. The primed variable ($pc'$ here) is used to represent the modified version of its unprimed counterpart ($pc$ here).

The two-phase handshake protocol can be described as follows, where $p$ and $c$ are initially equal.

  \begin{eqnarray}
\mathcal{Y} :  & \textrm{ process } & Prod: \textrm{ whenever } p = c \textrm{ do } \mathcal{P} \textrm{ } ; \textrm{ } p = p \oplus 1 \textrm{ end} \\
& \Arrowvert & \\
& \textrm{ process } & Cons: \textrm{ whenever } p \neq c \textrm{ do } \mathcal{C} \textrm{ } ; \textrm{ } c = c \oplus 1 \textrm{ end}
\end{eqnarray}

Note that process $Prod$ reads $c$ and writes $p$ while $Cons$ reads $p$ and writes $c$. It is not hard to find out that $\mathcal{Y}$ alternately performs $\mathcal{P}$ and $\mathcal{C}$.

The protocol $\mathcal{Y}$ can also be described as a state machine:

  $Init_{\mathcal{Y}} \triangleq (p = c) \land Init_{\mathcal{PC}}$
  $Next_{\mathcal{Y}} \triangleq Prod \lor Cons$
  $Prod \triangleq (p = c) \land \mathcal{P} \land (p' = p \oplus 1) \land (c' = c)$
  $Cons \triangleq (p \neq c) \land \mathcal{C} \land (c' = c \oplus 1) \land (p' = p)$

The amazing observation is:

  $\mathcal{Y}$ can be obtained from $\mathcal{X}$ by substituting $p \oplus c$ for $pc$ in their state machines.

There is a general theory here, which was introduced into CS by Robin Milner, which Lamport did not go into.

A state machine is generally given as a triple $(Q \in \mathrm{Set}, q \in Q, f \in I \times Q \to \mathcal{P}(O \times Q))$, consisting of a state set $Q$, an initial state $q$, and a transition relation $f$.

Now, suppose we have two automata $(Q, q, f)$ and $(T, t, g)$. Let's ask a question: when are these automata equivalent? If all we are going to do is take the machines and send them inputs and listen to the outputs, we don't want to require the state sets to be the same (for example, if $(T, t, g)$ is the result of running a DFA minimization algorithm on $(Q, q, f)$).

It turns out that the right notion of equivalence is bisimulation.  The idea is that we take two state machines to be the same, if we can produce a relation $R \subseteq Q \times T$, such that

$(q,t) \in R$
for all $(q,t) \in R$ and $i \in I$ and $o \in O$ then:

for all $q' \in Q$, if $(o, q') \in f(i, q)$, then there is a $t' \in T$ such that $(o, t') \in g(i, t)$.
for all $t' \in T$, if $(o, t') \in g(i, t)$, then there is a $q' \in Q$ such that $(o, q') \in f(i, q)$.

This says that if we can figure out any relation such that (a) the initial states are related, and (b) from related initial states, any I/O action the first machine can take can be mimicked by the second machine in a way that keeps you in the relation, and (c) similarly, the first machine can mimic anything the second can do.

Lamport's notation with primes is a way of concisely describing input-output relations. In this case, the state sets are the program counter of the first program, and the two program counters of the second program. The bisimulation relation is $R(pc, (p, c)) \triangleq pc = p \oplus c$, and then the bisimulation conditions follow trivially (since the relation expressions are equal under the subsitution).

The general theory at work is the theory of coinduction. State machines are representions of corecursively defined sets, and bisimulations tell you when two state machines are representations of the same potentially-infinite object.

Incidentally, this paper is written in a rather polemical style. Equally polemically, I'll point out that the style he advocates in this paper simply fails should you ever need to verify part of a program in isolation -- for example, if you want to prove a library implementation correct, or verifying a program using higher-order functions (or even just dynamic linking).

But both of us will use coinduction, nonetheless.


Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices I am interested in the MulitColoredClique problem with an additional restriction.
(Def.: A $k$-coloring $V_1,V_2,\dots,V_k$ of a graph $G$ is a partition of the vertex set of $G$ into $k$ independent sets $V_1,V_2,\dots,V_k$).
MulitColoredClique with Simple Modules
Instance: A graph $G$, an integer $k$, and a $k$-coloring $V_1,V_2,\dots,V_k$ of $G$ such that
$\quad\qquad\;\ $for every pair of colors $i$ and $j$, $V_i\cup V_j$ induces the disjoint union of
$\quad\qquad\;\ $ a complete bipartite graph with an independent set.
(in other words, if $x\in V_i$ has a neighbor in $V_j$, and $y\in V_j$ has a neighbor in $V_i$, then $x$ and $y$ are neighbors).
Question: Is there a clique of size $k$ in $G\,?$
Is this problem NP-hard?  (or even W[1]-hard?)
I have a feeling that it is indeed NP-hard, but I am unable to prove it.
Or, is this problem in P?
If it is in P, an interesting combinatorial problem will also be in P.
Is this or any related problem (other than MultiColoredClique) studied in the literature?
PS: Sorry, I asked the wrong question. Somehow, I assumed that bipartite complement of biclique+isolated vertices was again biclique+isolated vertices. What I wanted to ask is here: Complement of Multi-colored Clique with an extra condition

The problem is polynomial-time solvable.
Observe that we have to pick exactly one vertex from each color class to form a $k$-clique.
If there is a vertex $x \in V_{i}$ that has no neighbor in some $V_{j}$ with $i \ne j$,
then no $k$-clique includes $x$. Thus, we can remove such a vertex.
Repeat this until every vertex has a neighbor in each color class (except for the class it belongs to).
If some class becomes empty, then the graph does not have a $k$-clique.
Otherwise, since the property ``every pair of color classes induces a biclique + isolated vertices''
is closed under taking induced subgraphs,
the remaining graph is a complete $k$-partite graph, which contains a $k$-clique.


Algebraic account of Gaussian elimination? For fun, I've been looking at the interpretation of linear logic in terms of finite-dimensional vector spaces, and ran into an interesting
question about the interpretation of double-negation-elimination in this category.

As is well-known, vector spaces have a natural notion of dual space -- given a vector space $V$,(over a field $R$) the dual space $V^\ast$ is
just the set of linear functions into $V \multimap R$. Furthemore, it is well-known (indeed, so well-known that I don't know who proved it) that every finite-dimensional vector space is isomorphic to its double-dual.

One direction of the isomorphism $V \to V^{\ast\ast}$ is easy (it's just the map $f : V \to V^{\ast\ast} \triangleq v \mapsto \lambda k.\;k(v)$). The other direction is trickier. The usual proof goes something like this:

The dimension of a dual space $V^\ast$ is the same as the original space $V$.
So the double-dual $V^{\ast\ast}$ has the same dimension as the original space $V$.
So if we can show that $f$ has a zero kernel, then we know that $f$ has a range of all of $V^{\ast\ast}$, and so is (one half of) an isomorphism.

But the only way I know of actually computing the inverse $f^{-1}$ requires choosing a basis and then inverting the matrix.

What I'd really like is an algebraic or categorial account of Gauss-Jordan matrix inversion (or Gaussian elimination or LU decomposition or
whatever), so that I can give a syntactic theory of inversion (and hence an operational semantics for double-negation elimination in FD vector spaces).

This seems like the sort of thing that must have been studied before, but my Google skills are apparently not up to the task....

You really should read Gowers' essay carefully - it cleanly details the reasons why you need a basis in general. So if there is going to be an algebraic account of Gauss-Jordan, it will necessarily involve some additional conditions.  You can get an idea of the kinds of conditions by reading the n-lab page on dual vector spaces.  There it shows that there are a lot of spaces which are isomorphic to their double duals.

As you mention, this is related to double-negation elimination.  But let's spell that out. The isomorphism is linear CPS transform, as it is the set of functions $\left(V\multimap R\right)\multimap R$. You are seeking `unCPS'. Which highlights how miraculous the structure of $V$ must be for this to be feasible at all.  The page on the n-lab gives some of these miracles. [Turns out that, syntactically, this works for the duality measure $\leftrightarrow$ linear functional on programs if you choose your programming language "just right"; if you're curious, see my work with Chung-chieh Shan at PADL 2016, where we implement $\texttt{unCPS}$].

Another way, more computational, to look at this is to look at more general versions of LU decomposition. For LU with full pivoting, you can decompose $A$ as $PAQ = LDU$ with $P$ and $Q$ as permutation matrices, $D$ diagonal, $L$ unit lower triangular and $U$ unit upper triangular. You can generalize even more to various kinds of rings (see Fraction free factors by Zhou and Jeffrey). The point is that $P$ and $Q$ are arbitrary, but $L,D,U$ depend on them -- another way to see the base dependence. Clever choices of $P$ and $Q$ allow you to deal with whatever defects the expression of $A$ in the original basis were, and 'rotate' things in better position -- be it for stability, sparsity, expression size blowup, etc.


number of PCP queries we know from the PCP theorem that $PCP[O(log(n)),O(1)]=NP$,what if we choose specific number of queries will the theorem hold ?

I believe the best result (with regards to the number of queries) is still Håstad's 3-query PCP. So if you choose at least 3, then it's a definite yes.

These lecture slides might be a bit more useful as they cut straight to the chase.


Term for a correspondence of two point sets regarding their ordering in each dimension Let there be two sets of points $S$ and $S'$ in $R^d$. $|S| = |S'|$, and for each point $s_i$ in $S$ it exists exactly one corresponding point $s'_i$ in $S'$, such that the ordering of $S$ equals the ordering of $S'$ with respect to any axis of $R^d$.

Is there any term that describes this relationship or 'morphism' between $S$ and $S'$?

E.g. in $R^2$, if $x_{s_i} < x_{s_j}$ then $x_{s'_i} < x_{s'_j}$, or if $y_{s_i} \ge y_{s_j}$ then $y_{s'_i} \ge y_{s'_j}$, etc.

Associate with $S$ and $S'$ the posets $P = (\leq, S)$ and $P' = (\leq, S')$, where $\leq$ is the dominance order in $\mathbb{R}^d$. The function you describe is an isomorphism between $P$ and $P'$.


Why exactly are complexity theorists interested in closed timelike curves? Context:

There are several papers that study the implications of closed timelike curves (CTCs) to quantum complexity. In 2008, Aaronson and Watrous published their famous paper on this topic which shows that certain forms of time travel can make classical and quantum computing equivalent i.e. quantum computers provide no computational advantage if they can send information to the past through closed-timelike curves.

Questions:

The abstract clearly says that closed timelike curves are not known to exist. So why exactly are complexity theorists interested in this topic? Does the study of CTCs provide some non-trivial insight into the fundamentals of complexity theory?
Are there any other world lines that are popularly studied in the context of complexity theory? If yes, why? If not, why not (and then what's so special about CTCs)?

I haven't really gotten around to working through the CTC papers, but I'm trying to get an idea of the "big picture" here, so as to understand the motivation behind studying this topic.

Note: I previously asked about this on Quantum Computing SE, in the context of quantum information theory, but here I'm specifically trying to view it through the lenses of a complexity theorist or computer scientist.

Sorry for the very "big picture" answer from a non-quantum-theorist, but this contrast might help: you could describe algorithms as the study of how to solve computational problems, whereas complexity theory studies the resources (especially time) required in theory to solve them. How hard are these problems really at some fundamental level, and how are they classified by resource requirements? This question is considered interesting regardless of how many or what kinds of resources puny humans happen to have at their disposal.

(For instance, an $n^{100000}$ time algorithm for SAT would totally upend our view of complexity theory even if it never impacted any algorithms we could run in this universe. A $2^{0.00000001n}$ time algorithm for SAT would change our understanding of complexity much less, even though it would have huge practical implications.)

The question of how much time is needed in theory to solve a problem changes if you allow CTCs, therefore they are interesting to complexity theory by definition.

So I feel your first question is like asking why computability theorists would study Turing degrees higher than zero; it's what they do.


Bigger picture behind the choice of matrices in the Strassen algorithm In the Strassen algorithm, to compute the product of two matrices $\mathbf{A}$ and $\mathbf{B}$, the matrices $\mathbf{A}$ and $\mathbf{B}$ are divided into $2 \times 2$ block matrices and the algorithm proceeds recursively computing $7$ block matrix-matrix products as opposed to a naive $8$ block matrix-matrix products, i.e., if we want $\mathbf{C}=\mathbf{A} \mathbf{B}$, where
$$\mathbf{A} =\begin{bmatrix}
\mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\
\mathbf{A}_{2,1} & \mathbf{A}_{2,2}
\end{bmatrix}
\mbox { , }
\mathbf{B} =
\begin{bmatrix}
\mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\
\mathbf{B}_{2,1} & \mathbf{B}_{2,2}
\end{bmatrix}
\mbox { , }
\mathbf{C} =
\begin{bmatrix}
\mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\
\mathbf{C}_{2,1} & \mathbf{C}_{2,2}
\end{bmatrix}$$
then we have
$$
\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}\\
\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}\\
\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}\\
\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2} $$
which requires $8$ multiplications. Instead in Strassen, we compute
$$
\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})\\
\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}\\
\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})\\
\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})\\
\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}\\
\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})\\
\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})
$$
and obtain $\mathbf{C}_{i,j}$'s using $\mathbf{M}_{k}$'s as
$$
\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}\\
\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}\\
\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}\\
\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}
$$
However, the choice of the matrices $\mathbf{M}_k$'s seem arbitrary to me. Is there a bigger picture as to why we choose these specific products of sub-matrices of $\mathbf{A}$ and $\mathbf{B}$? Also, I would expect $\mathbf{M}_k$'s to involve $\mathbf{A}_{i,j}$'s and $\mathbf{B}_{i,j}$'s in a symmetric fashion, which does not seem to be the case here. For instance, we have $\mathbf{M}_2: = (\mathbf{A}_{2,1}+\mathbf{A}_{2,2})\mathbf{B}_{1,1}$. I would expect its counterpart say $\mathbf{A}_{1,1} (\mathbf{B}_{1,2} + \mathbf{B}_{2,2})$ also to be computed. However, it is not since it can be obtained from other $\mathbf{M}_k$'s.

I would appreciate if someone could throw some light on this.

De Groote (On Varieties of Optimal Algorithms for the Computation of Bilinear Mappings. II. Optimal Algorithms for 2x2-Matrix Multiplication. Theor. Comput. Sci. 7: 127-148, 1978) proves that there is only one algorithm to multiply $2 \times 2$-matrices with 7 multiplications up to equivalence. This might be a unique feature of $2 \times 2$-matrix multiplication. (Note: You will find different variants of Strassen's algorithm in the literature. They are all equivalent with the right notion of equivalence.)

If you now start to prove a lower bound for $2 \times 2$-matrix multiplication - see the book by Bürgisser, Clausen, and Shokrollahi how to do that - then Strassen's algorithm or some variant shows up quite naturally. You will find out a lot of identities that determine how the products look like. Then you can finish by some guessing.
(De Groote's proof shows that even guessing is not necessary.)

Schönhage once told me that Strassen once told him that he found his algorithm in this way, by trying to prove a lower bound.


What can I do to supplement my theoretical undergraduate CS curriculum so that I can increase my value in industry & academia? As most well-known universities are, my university also has a theoretical-based CS curriculum where the classes either teach straight-up theory, or teach you how to implement systems rather how to use them effectively.

I originally came into CS hoping for knowledge about how the world works (in a practical sense) so that I'd be able to see opportunities & advantages in every corner (if you know what I mean). So I was hoping that I could streamline what I'm learning in my courses to optimize it toward this goal.

I need some suggestions on what skills or knowledge I should accumulate before I graduate and apply for graduate school, or get a job in industry (hopefully more than just programming). Basically, I'm looking for a good direction.

I need some suggestions on what skills or knowledge I should accumulate before I graduate and apply for graduate school, or get a job in industry (hopefully more than just programming). Basically, I'm looking for a good direction.

What are you really passionate about?

Among the things that you're really passionate about, what are you really good at?

Do that.

Talk to everyone you can who does that.  Figure out who does that well and who just spouts shiny nonsense about doing that.  Ask the good ones how they got good at doing that.  Do what they do.  Most of what they do won't work for you, but until you try and fail yourself, you won't know what works and what doesn't.  And you will fail; brush it off, get back up, and keep doing that.  Don't avoid the uncomfortable, frustrating,  boring, but necessary stuff you have to do to learn to do that well and to keep doing that.

Oh, and as long as you're in college, you might as well take some classes.


How to generate Extended Finite State Machines Randomly with some properties? This is related to my academic project

An extended finite state machine is a tuple $SM=(I,S,T)$ (simplified):

$I$ is the set of identifiers and it's divided into two sets Inputs and outputs, for simplification we will just consider boolean variables. Let $\sigma$ be the evaluation function $\sigma :I \to \{0,1\}$ which associate to very identifier its value, And let $\Sigma$ be the set of all evaluations.
$S$ is the set of states
$T\subseteq S\times S \times G\times A$ the set of transitions, a transition $t=(s_1,s_2,g,a)$ means :

$s_1$ the source state
$s_2$ the target state
$g$ the guard,which is usual expressed in the guard language and here we can just consider it as its semantic $g:\Sigma \to \{0,1\}$ where $g(\sigma)$ is an element of $\{0,1\}$.
$a$ is usually expressed in the action language, and we will here identify it with its semantic $a:\Sigma \to \Sigma $ where $f(\sigma)$ is another evaluation function.

Now a configuration of the state machine $SM$ is a tuple $(s_i,\sigma)$ where $s_i$ is the current state and the $\sigma$ the current evaluation function. A run of the machine is :
$$(\sigma_0,s_0)\to(\sigma_1,s_{1})\to (\sigma_2,s_2)\to \cdots (\sigma_k,s_k)\to(\sigma_{k+1},s_{k+1})\to \cdots $$
where for every $k$ we have $(s_k,s_{k+1},g,a)$ is a transition and $g(\sigma_k)=1$ (meaning true) and $a(\sigma_k)=\sigma_{k+1}$

Example of action : we denote an action by $Rep(a)=[e_1,\cdots,e_n] $ where $e_i$ is a boolean expression over the variables in $I=[o_1,\cdots,o_n,i_1,\cdots ,i_k]$ where $i_j$ are the inputs of the system and are determined by the environment. And from this representation of the action we can have $a(\sigma)(x)=e_j(\sigma) $ if $x=o_j$ and $a(\sigma)(x)=i_j$ if $x=i_j$

The guards  are represented by expressions over the set of the variables $I$

What I am  able to do : I was able to generate some boolean expressions that are valid or satisfiable using either well known examples, or using the threshold density of boolean formulas. Hence I am able to generate the guards and the actions (which are random, and have some properties like satisfiable or valid)

  Question : how could I generate a random Extended State machine with the property that: Every state is reachable and every transition can be executed

you can use that fact that I am able to generate a formula that evaluates to $1$ or $0$ and I can generate a satisfiable or unsatisfiable formula

Any other ideas to do  tests  with Extended State Machines?
Thanks

Edit 29/04/2016

As my question is either not very clear or difficult; I have an alternative question:

  Question 2: what are some well known random Extended State Machines for which every state is reachable.

The purpose of my project is to test the efficiency of an algorithm

You can generate a random automaton naively (i.e., every state sends a directed edge uniformly at random to every other state, including itself) and then remove the unreachable states. If you start with $n$ states, you will end up with roughly $cn$ states (where $c$ is explicitly computable), and this is tighly concentrated:
https://dl.dropboxusercontent.com/u/3198145/rand-dfa.pdf

Thus, if your goal is $n$ states, start with, say, $n/c$ states, generate a random automaton, and remove unreachable states. Note that this process does not sample uniformly from all $n$-state automata, but you didn't ask for a uniform distribution. See also references in that linked paper for generating random automata with various properties.


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

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

Any insights will be much appreciated!

(It's not an answer, but I can't comment yet) I think the above answer doesn't work, because it doesn't guarantee that the paths would be vertex disjoint. One path could use u', and the other u" in G'; in G they would use the same vertex u.


Are the `ArrowApply` and `Monad` typeclasses equivalent? It is stated e.g. on Hackage, that the ArrowApply and the Monad typeclasses are equivalent. I have my doubts about this.

It is obvious that there are morphisms from ArrowApply to Monad and back, and one can check that one can prove the Monad laws and the ArrowApply laws in each case. What I doubt is that these morphisms are inverses.

They are defined this way:

Let $\leadsto: \operatorname{Type} \times \operatorname{Type} \to \operatorname{Type}$ be an instance of ArrowApply, so there is $arr: (a \to b) \to (a \leadsto b)$, $first: (a \leadsto b) \to (a \times c \leadsto b \times c)$ and $app: ((b \leadsto c) \times b) \leadsto c$, and $\leadsto$ is the hom of some category. I'm leaving out the universal quantifiers on lower-case letters, like in Haskell-style.
We define a monad $m: \operatorname{Type} \to \operatorname{Type}$ by $m a = 1 \leadsto a$. For example, $\operatorname{return}: a \to m a$ is defined as $\operatorname{return} x = arr (\lambda y. x)$, and $\operatorname{join}$ and the monad laws are not very hard.
Or the other way: Given a monad $m$, define $a \leadsto b = a \to m b$. This defines obviously a category and also gives rise to an ArrowApply.

I cannot see at all that these constructions are inverse to each other. Here is what I believe to be a counter-example:

Define your arrow type as the fixpoint of $a \leadsto b = a \to (b \times (a \leadsto b))$. This is the terminal coalgebra of the functor $x \mapsto A \to (b \times x)$. It represents a stateful, causal stream function. Constructions like this are used in functional reactive programming, e.g. Yampa.

We then define the monad $m$ in terms of $\leadsto$.
Intuitively, $m a$ is the type of stream functions from unit to $a$, in other words, streams in $a$.
But Kleisli arrows of this monad aren't stream functions:
$$m a = 1 \to a \times (1 \leadsto a) \cong a \times (m a)$$
$$\implies a \to m b \simeq a \to b \times (m b) \not\simeq a \to b \times (a \leadsto b) \simeq a \leadsto b$$
So in this case, the constructions are not equivalent, if I haven't made a mistake somewhere.

Are ArrowApply and Monad inequivalent then, since the constructions aren't inverses of each other? Or is there another construction that makes them equivalent?

The problem with your counterexample is that the type you presented is not a valid instance of ArrowApply as far as I can tell.

You didn't present what the implementation of app but the only one I could come up with (where you use the input stream function once and then discard it) doesn't satisfy the 2nd and 3rd ArrowApply laws.

What definition of app did you have in mind?


Is there an approximation algorithm for MAX k DOUBLE SET COVER? Given a set system $(X,\mathcal S)$, let us say that a subset $\mathcal C\subseteq \mathcal S$ doubly covers a vertex $x$ in $X$ if $x$ is contained in at least two sets of $\mathcal C$. Let us define the following maximization problem:

MAX k DOUBLE SET COVER
INPUT: a set system $(X,\mathcal S)$, an integer $k$
OUTPUT: a set $\mathcal C\subseteq \mathcal S$, $|\mathcal C| \le k$
MEASURE: the number of elements of $X$ that are doubly covered by $\mathcal C$

MAX k DOUBLE SET COVER is a generalization of the problem MAX k SET COVER, where we only require simple coverage instead of double coverage (see the celebrated 1998 paper by Feige, "A threshold of $\ln n$ for approximating Set Cover"), where a $(1-1/e)$-approximation is given).

  My question: Is there any known nontrivial positive approximation bound for MAX k DOUBLE SET COVER?
  Note: I am especially interested in the restriction where the set system has maximum intersection one, that is, any two sets in $\mathcal S$ share at most one element (SET COVER for these set systems remains hard to approximate, see this paper).

As pointed out in the answer to this other question, the problem DENSEST k-SUBGRAPH is a special instance restriction of MAX k DOUBLE SET COVER with set systems with intersection one: an input graph $G$ corresponds to the hypergraph $(E(G),\mathcal S_G)$ where $\mathcal S_G$ has a set $S_v$ for each vertex $v$ of $V(G)$ containing the edges incident to $v$ in $G$.
DENSEST k-SUBGRAPH has an $O(n^{1/4})$-approximation algorithm (this paper); perhaps this algorithm can been (has been) extended to MAX k DOUBLE SET COVER (for set systems with intersection one)?
(The complexity of DENSEST k-SUBGRAPH being well-studied and a tough open problem, for MAX k DOUBLE SET COVER I am not expecting anything better than an approximation ratio of the form $O(n^{\delta})$ for some $\delta<1$.)

Any related observation or reference is welcome. Thanks!

(Comment $\rightarrow$ Answer)

Consider the following algorithms for a hypergraph $(U,\mathcal S)$, with $n=|U|$:

For a set $X\subseteq \mathcal S$ of sets and a set $A \in X$, define $d_X(A)$ as the number of elements in $A$ that are double covered by $X$, i.e. $|A \cap \left(\bigcup(X \setminus \{A\})\right|$. Additionally, let $c(X)$ denote the number of elements double covered by $X$. By simple counting arguments, $$\max_{A \in X} d_X(A) \leq c(X) \leq \tfrac{1}{2}\sum_{A \in X} d_{X}(A)$$.

Now do the following for each set $A \in \mathcal{S}$: fix your choice of $A$ as one of the sets in your candidate solution. Now consider the Max-$(k-1)$-cover problem with set system $\mathcal{S} \setminus \{A\}$ and universe $A$. Let $X$ be the output of the greedy algorithm for this Max-$(k-1)$-cover problem, which approximates the optimal solution to within a factor of $1-1/e$. Call this greedy solution $Y_A$, and consider the candidate solution $X_A = Y_A \cup  \{A\}$. Call the best such solution $Z$. For each $A \in \mathrm{OPT}$, the solution generated this way satisfies (by the guarantee of the greedy algorithm) $$d_{X_A}(A)/(1-1/e) \geq \max_{\stackrel{T \subseteq S}{|T|=k-1}} d_{T\cup\{A\}}(A) \geq d_{\mathrm{OPT}}(A)$$. Now, letting $B$ be the set in $\mathrm{OPT}$ maximizing $d_\mathrm{OPT}(B)$, we have

$$\begin{eqnarray}
c(\mathrm{OPT}) & \leq & \tfrac{1}{2}\sum_{A \in \mathrm{OPT}} d_{\mathrm{OPT}}(A) \\
& \leq & \tfrac{k}{2}d_\mathrm{OPT}(B) \\
& \leq & \tfrac{k}{2-2/e} d_{X_B}(B) \\
& \leq & \tfrac{k}{2-2/e} \max_{A \in X_B} d_{X_B}(A) \\
& \leq & \tfrac{k}{2-2/e} c(X_B) \\
& \leq & \tfrac{k}{2-2/e}c(Z).
\end{eqnarray}$$

$\,$

First, remove from $U$ all elements that can't possibly be double covered. Initialize $Y = \emptyset$. While $|Y| \leq k$ (and $Y$ doesn't fully double cover $U$), arbitrarily pick an element $x \in U$. We then add sets containing $x$ to $Y$ (chosen arbitrarily) until $Y$ at least double covers $x$. When the loop terminates, return $Y$. The total number of elements double covered this way ($c(Y)$) is at least $\min(|U|, k/2)$. If it's $|U|$, we solved the problem exactly so there's no need for further analysis. Otherwise, we have $$c(\mathrm{OPT}) \leq n = \tfrac{2n}{k} \cdot k/2 \leq \tfrac{2n}{k} \cdot c(Y).$$

Now run the two above algorithms, generating solutions $Z$ and $Y$, and let $X = \max(Y, Z)$. Multiplying the two inequalities, $$c(\mathrm{OPT})^2 \leq \tfrac{k}{(2-2/e)} \tfrac{2n}{k} \cdot c(Y)c(Z) = \tfrac{n}{1-1/e} c(Y)c(Z) \leq \tfrac{n}{1-1/e} c(X)^2.$$ So $$c(\mathrm{OPT}) \leq \sqrt{\tfrac{n}{1-1/e}} c(X),$$

giving an $O(\sqrt{n})$ approximation.


ATSP with direction restrictions I'm trying to find any material on this problem. It extends the Asymmetric Travelling Salesman Problem (ATSP) in that it requires for some destinations that they are approached in the specified direction (but not for all). I couldn't find anything about this problem on the internet. Can anybody point me to some paper or the correct name for this problem? Or maybe similar problem from graph theory?

UPDATE

In my current design each node has a property of direction in which it is being approached. This direction can be restricted or unrestricted. When unrestricted, then I think all possible combinations of directions should be tried to the combination which minimizes the cost function.
Also I have 4 distance matrices corresponding to different direction combinations: 0-0, 0-1, 1-0 and 1-1. Where 0 is positive direction and 1 is negative direction.

UPDATE 2

The calculations are performed on a real street network data. Direction mean street direction (or side of the street). Each point on the street can be aproached from two different directions. Some points are restricted to be approached in a particular direction, some are not.

I will answer for the general setting. Assume a directed graph $G=(V, E)$ with costs as assumed in the question, that is the costs for entering a node depend on which edge it is left on and vice versa.

Let $v \in V$ arbitrarily; the following construction can be performed iteratively for all nodes in any order. Let $e_1, \dots, e_k \in (V \times \{v\}) \cap E$ (incoming edges) and $f_1, \dots, f_l \in  (\{v\} \times V)\cap E$ (outgoing edges).

Now create for all pairs of $e_i =: (u,v)$ and $f_j =: (v,x)$ a node $v_{ij}$ and edges $(u, v_{ij})$ as well as $(v_{ij}, x)$. Assign the costs as per the described model: costs for edge $(u, v_{ij})$ are the costs for entering $v$ from $u$ when leaving in direction of $x$; costs for edge $(v_{ij}, x)$ are the costs for leaving $v$ to $x$ when having come from $u$.

Add all thusly created $v_{ij}$ and their incident edges to $G$ and remove $v$ and its incident edges from it. Iterate for all nodes.

The resulting graph has $\mathcal{O}(|E|\cdot d^2)$ many edges ad $\mathcal{O}(|V| \cdot d^2)$ many nodes, $d$ the maximum node degree in $G$. It can be reduced by merging (or not splitting) those combinations that have the same costs.

The original problem is equivalent to finding a path with exactly one from each $\{v_{ij} \mid v \in V \}$.


Smallest possible universal combinator I am looking for the smallest possible universal combinator, measured by the number of abstractions and applications required to specify such a combinator in the lambda calculus. Examples of universal combinators include:

size 23: λf.f(fS(KKKI))K
size 18: λf.f(fS(KK))K
size 14: λf.fKSK
size 12: λf.fS(λxyz.x)
size 11: λf.fSK

where S = λxyz.xz(yz) of size 6 and K = λxy.x of size 2 are the combinators of the SK combinator calculus. The first 4 examples are described in this paper.

My questions are:

Are there any universal combinators that are smaller in size?
What is the smallest possible universal combinator?

EDIT: See also https://math.stackexchange.com/a/180263/76284, which has λazbc.bc(a(λy.c)) (which would be of size 8, matching the sum of sizes of the SK basis). Does anyone know how to express S and K from this combinator?

It should be noted that finding combinators with certain reduction properties is always difficult, and finding the smallest such combinator may easily be undecidable (for trivial reasons, as it may be undecidable to prove that a certain application of the combinator even halts).

There are several simple open questions of a similar flavor, e.g. problems #4, #6 and #10 from the TLCA list of open problems.

One thing to note is that your combinator certainly needs to have at least 2 bound variables, one of which is duplicated (as does any complete set of combinators) and one needs to be erased. This puts a lower bound of 4, I think (2 abstractions and 2 appearances of a variable), which is not so far from the upper bound of 11.

Edit: Noam's comments and reference push the lower bound to 5! I wouldn't be surprised if the proof also requires the extra variable to appear as well, which would push us to 6.


What is the descriptive complexity of the basic modal logic? This is kind of multiple questions in one. Let's consider $\phi$ a formula in the basic modal language (that is, in propositional language based on a set of propositional variables $\Phi$, plus one of the basic modal operators, say, $\Diamond$)

1) Define the $\phi-\mathsf{MODEL}$ problem as: Given a finite structure $M = (W, R, V, w)$, where $W$ is a set, $R \subseteq W \times W$, $V : \Phi \rightarrow 2^W$ and $w \in W$, is $\phi$ satisfied in $M$, as per the usual modal logic definition of satisfiability?

2)  Define the $\phi-\mathsf{FRAME}$ problem as: Given a finite structure $F = (W, R)$, where $W$ is a set and $R \subseteq W \times W$ is $\phi$ valid in $F$, as per the usual modal logic definition of validity?

We could go on and define other variants, asking if there is a world in which the formula is satisfied (or valid), if there is a valuation such that the formula is satisfied, and so on.

Now consider, for example, the collection of $\phi-\mathsf{MODEL}$ problems, for all basic modal formulas $\phi$. My question could be formulated as thus: Is this class of problems equal to any well-known complexity class? Of course, the question could be formulated for any of the variants i just proposed, so it's as i said earlier, kind of multiple questions in one.

(It goes without saying, but for other logics, such as first and second-order logics, this is a much-studied subject with the name Descriptive Complexity, with classic results such as Fagin's Theorem relating the existential fragment of second-order logic to the complexity class NP)

Modal logic does not capture any interesting complexity class. As it is invariant under bisimulation, it cannot even test whether the vertex $w$ has degree greater than $2$, which is a constant time property. We are interested in ML for a different reason: ML is the bisimulation invariant fragment of first-order logic (Theorem of van Benthem). In other words, ML is the "first-order logic of process behaviour". Similarly, the bisimulation invariant fragment of monadic second-order logic is the $\mu$-calculus (Theorem of Janin/Walukiewicz).


Consequences of lower bounds for $\epsilon$-nets on approximation Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [PDF].  I would like to know what, if anything, such a lower bound implies about the approximability of the associated Set Cover/Hitting Set problems.

To be slightly more specific, consider a family of range spaces, for example, the family:

$\big\{(X,\mathcal{R})$ : $X$ is a finite planar point set, $\mathcal{R}$ contains all intersections of $X$ with lines$\big\}$

If, for some function $f$ that is linear or super-linear, the family contains a range space that does not admit $\epsilon$-nets of size $f(1/\epsilon)$, what, if anything, does this imply about the Minimum Hitting Set problem restricted to this family of range spaces?

If a range space has $\epsilon$-net of size $f(1/\epsilon)$, then the integrality gap of the fractional hitting set (or set cover) is $f(1/\epsilon)/(1/\epsilon)$. See the work by Philip Long (here [The Even etal. work is later than this work, and rediscover some of his stuff]). See also the slides 13-16 here.

In short, having non-linear $\epsilon$-nets, indicates that approximating the relevant hitting-set/set cover problem within  better than a constant factor is going to be very challenging.


Strongly Regular Graph and GI-Completeness It is not known if graph isomorphism (GI) for strongly regular graphs (SRGs) is in P. Are there any hints that it might or might not be GI-Complete? Are there any strong consequences in such cases? (Similar to the belief that GI may not be NP-Complete).

I believe all known GI-completeness results are functorial (definition in the paper), and Babai has recently shown (ITCS 2014, free author's copy) - based on bounds on the structure of automorphism groups of strongly regular graphs - that there is no functorial reduction from GI to strongly regular GI.


Is there a problem in ZPP not yet in P? Primality was a nice problem that was in ZPP but was not known to be in P. Is there a (preferably simple to state) problem of which we can prove that it is in ZPP but we do not know whether it is in P or not?

I know ZPP=EXP might hold and so on, I want a problem surely in ZPP that is not surely in P.

The Problem:

Input: $\;\;$ a tuple that parses as $\:\langle \hspace{.04 in}p,\hspace{-0.03 in}y,\hspace{-0.03 in}i\hspace{.02 in}\rangle$

Output:

if $p$ is prime and $y$ is a quadratic residue modulo $p$, $\;$ then the $\hspace{.02 in}i\hspace{.03 in}$th$\hspace{.01 in}$ bit of the

non-negative integer $x$ that satisfies $\;\;\; x^{\hspace{.02 in}2} \equiv y \; \pmod p\;\;\;$ and $\;\; 2\hspace{-0.04 in}\cdot \hspace{-0.04 in}x \: \leq \: p \;\;$,

else 0

According to the wiki article, that problem is in ZPP but is not known to be in P.


Intermediate $\mathsf{NP}$-complete problems? Partition problem is weakly NP-complete since it has polynomial (pseudo-polynomial) time algorithm if input integers are bounded by some polynomial. However, 3-Partition is strongly NP-complete problem even if input integers are bounded by a polynomial.

  Assuming, $\mathsf{P \ne NP}$, Can we prove that intermediate NP-complete problems must exist? If the answer is yes, Is there such "natural" candidate problem?

Here, Intermediate NP-complete problem is a problem that neither has a pseudo-polynomial time algorithm nor NP-complete in the strong sense.

I guess that there is an infinite hierarchy of intermediate NP-complete problems between weak NP-completeness and strong NP-completeness.

EDIT March 6th: As mentioned in the comments, an alternative way to pose the question is:

  Assuming, $\mathsf{P \ne NP}$, Can we prove the existence of NP-complete problems that neither have polynomial time algorithm nor NP-complete when the numerical
  inputs are presented in unary? If the answer is yes, Is there such "natural" candidate problem?

EDIT2 March 6: The reverse direction of the implication is true. The existence of such "intermediate" $NP$-complete problems implies $\mathsf{P \ne NP}$ since if $\mathsf{ P=NP}$ then unary $NP$-complete problems are in $P$.

This is a partial answer that only gives a candidate intermediate $NP$-complete problem.

$k$-Equal Sum Subsets problem: Given a multiset of $n$ positive integers $A = \{a_1,...,a_n\}$, are there $k$ nonempty disjoint subsets $S_1,...,S_k ⊆ \{a_1,...,a_n\}$ such that $sum(S_1) = ... = sum(S_k)$?

The problem is weakly $NP$-complete when $k= O(1)$ and therefore has pseudo-polynomial time algorithm for any fixed constant integer $k > 2$. However, it becomes strongly $NP$-complete when the number of equal sum subsets $k= \Omega(n)$.

If $k= \omega(1)$ and $k= O(\log n)$ then $k$-Equal Sum Subsets problem is a candidate intermediate $NP$-complete problem (as described in the question). This problem is neither known to have a pseudo-polynomial time algorithm nor proven to be $NP$-complete in the strong sense.

Reference:

CIELIEBAK, EIDENBENZ, PAGOURTZIS, and SCHLUDE, ON THE COMPLEXITY OF VARIATIONS OF EQUAL SUM SUBSETS, Nordic Journal of Computing 14(2008), 151–172


Average distortion embeddings Consider two metric spaces $(X, d)$ and $(Y, f)$, and an embedding $\mu : X \rightarrow Y$.
Traditional metric space embeddings measure the quality of $\mu$ as the worst-case ratio of original to final distance:
$$ \rho = \max_{p,q \in X} \{ \frac{d(x,y)}{f(\mu(x), \mu(y))}, \frac{f(\mu(x), \mu(y))}{d(x,y)} \}$$

There are other measures of quality though: Dhamdhere et al study the "average" distortion:
$$ \sigma = \frac{\sum d(x,y)}{\sum f(\mu(x), \mu(y))}.$$

However, the measure I'm interested in here is the one used by MDS-like methods, which looks at the average additive error:
$$ \varepsilon^2 = \sum | d(x,y) - f(\mu(x), \mu(y))|^2$$

Although MDS-like methods are studied extensively outside the theoryCS community, I'm aware of only one paper (by Dhamdhere et al) that examines optimization under this measure, and that too for the limited problem of embedding onto the line ($Y = \mathbb{R}$) (side note: Tasos Sidiropoulos' 2005 MS thesis has a nice review of earlier work)

Is there any more recent work that people are aware of regarding rigorous quality analysis under this notion of error ? While these problems are generally NP-hard, what I'm more interested in are approximations of any kind.

This is a nice question. I don't know of approximation algorithms, but the known hardness results for approximating minimum distortion (and related problems such as metric labeling) should also show that $\epsilon^2$ is hard to approximate.

The reason is that they give a reduction from an NP-hard problem such that in the YES case the distortion is $O(1)$ and in the NO case the distortion is $\Omega(k)$ for at least a constant fraction of the edges. Hence, in the YES case $\epsilon^2$ will be a factor $k$ smaller than in the NO case. For details, see for instance the paper by Khot-Saket: www.cs.cmu.edu/~rsaket/pubs/approx.pdf

I'm not exactly sure which hardness factor follows from their paper, but it shouldn't be difficult to figure out. (I would guess at least the $\log^c(n)$ factor that you get for metric labeling should follow.)


Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all? DISCLAIMERI do apologize in advance if this question turns out to be
  silly, for some trivial reason that I may be overlooking in this
  moment.

Suppose for a moment that $\mathbf{P} = \mathbf{BQP}$ is true: it is possible to efficiently simulate quantum computation by classical deterministic computation.

Now, from that very little I know about quantum computing (I'm much less than an amateur when speaking about it), if I'm not wrong a Quantum Turing Machine is able, by its very definition, to generate true randomness.

Henceforth, if $\mathbf{P} = \mathbf{BQP}$, then there exists a classical deterministic algorithm which is able to quickly output true randomness (by just quickly simulating some Quantum Turing Machine).

But... what would randomness be then? Would it even exist at all? Would you be willing to continue to call it randomness?

John Von Neumann once said: "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin". But the above classical deterministic algorithm would indeed be an arithmetical method of producing random digits, no? When thinking a bit about it, I was also considering Max Tegmark's view (expressed in his last book) according to which randomness does not exist at all: he believes it is only an illusion, more precisely the subjective feeling you perceive each time you get cloned (i.e. each time the Universe you live in gets branched in 2 or more Universes).

From my amateur point of view, if I were told that we live in a $\mathbf{P} = \mathbf{BQP}$ world, then I would believe that there is no such thing as randomness. How could it even exist, if it is perfectly producible by a mechanical procedure? Where would it reside? If true randomness can be implemented into a C++ concretion of the above classical deterministic algorithm, then where would it actually be? Would it be hidden somewhere? Would it continue to be present somehow, inspite there is no trace of it in the C++ code? For me, simply it would not exist.

Now, to summarize, this question is not about how likely you consider $\mathbf{P} = \mathbf{BQP}$ to be. Rather, the question boils down to the following:

  In a world where $\mathbf{P} = \mathbf{BQP}$, would randomness exist at all?

P and BQP are decision-problem classes, i.e. the correct output is always a deterministic functions of the inputs. The only question is whether randomness helps "along the way" to speed up computing this deterministic function (at the cost of sometimes being wrong), or does not. This is the key point: P=BQP says nothing about outputting random strings in general situations, but only for the situation of computing a deterministic function in polynomial time.

So for instance the statement

  if P=BQP, then there exists a classical deterministic algorithm which is able to quickly output true randomness (by just quickly simulating some Quantum Turing Machine).

is false. P=BQP only implies that if a machine with randomness can usually output the correct bit, then there is a machine with no randomness that always ouptuts the correct bit.

More comments on your question:

What is closer to true is that some form of pseudorandom generators exist (deterministic machines whose output "looks random" to other deterministic machines of bounded running time). However, again, these PRGs would be targeted to machines that always output just a single bit, not all tasks that use randomness in general.
For an example single-machine problem that can be solved by a randomized machine and provably cannot be solved by a deterministic machine, consider the problem "output a string of Kolmogorov complexity $\geq n$". This is essentially the problem of outputting a random string, and of course we can prove that no deterministic machine can do this.
As Kaveh points out, in areas like communication complexity between multiple machines, also distributed systems and probably others, we have provable differences between what can be achieved with and without randomness. The classic example is for two machines to decide if they hold the same $n$-bit string while communicating fewer than $n$ bits.
It may be that even if BQP = P, the randomized algorithm is much faster and more useful in practice. (It may even be that someday complexity theory could prove this.) Example: Miller-Rabin primality test (randomized) vs AKS (deterministic).
As I understand it, we could have P = BQP and yet cryptography is perfectly useful, one-way functions exist, etc. (Not the factoring problem, of course.) And cryptography relies completely on randomness.
I think BPP is as much a model of "true" randomness as BQP. Just a different type of randomness. How to get "truly" random bits in the real world is a different story.


Has this online problem been studied before ? Consider the following online problem:

  For $\sigma$ and $k$ fixed, given a string of symbols from alphabet
  $[1..\sigma]$, given one by one, guess a set $S$ of $k$ symbols such that the
  next symbol belongs in $S$, in space independent of the length of the past
  string.

This problem is similar to online cache management in the sense that failing the guess is a miss, while guessing correctly is a catch. It is much more general than cache management in the sense that symbols can be added to (the cache) $S$ without having generated a miss, just based on correlations previously learned (e.g. $b$ always follows $a$). It presents the same problem of analysis (competitive analysis and the like) than other online problems in the sense that the worst case is intractable while some good performance can be expected on practical instances.

It could have application to caching with pre-fetching. I thought of it while thinking about the dream specs of a diary application on a smart phone (i.e. reduced screen and costly typing), which given the past submissions of the user (went to bed, woke up, ate eggs, took the bus, etc...) must suggest on the screen $k$ activities to be logged next, a menu for others and a field to enter a new one (using the menu is a miss, writing a new one is unavoidable for any solution).  In this case one should consider the space taken by the algorithm: remembering the whole section of previous queries is not an option, only a finite, lossy (ditching outliers) summary of it. One could give additional information to the guesser such as the time of the day, but I do not know how to fit it nicely in the theoretical model.

Was such a problem or a variant already studied? Under which name? Using which model (Dorrigiv and Lopez-Ortiz "cooperative" analysis comes to mind)?

While I'm still not entirely sure what you're looking for, you might try reading Avrim Blum's talk on Online Learning and Prediction, and that might help you focus on areas of interest.


Numeral system information density What is an "informational density" and why numeral system with the base of e (2,71828...) has the maximum informational density? How do you calculate "informational density" of a given numeral system?

Let you want to represent integer values from 0 to 999. You need 3 digits, each has 10 states, 30 states overall. When using binary digits, you need 10 digits with 2 states, 20 states overall, So binary representation is more "dense". In general case, p*ln(N)/ln(p) states is required. This formula has minimum at p=e. However, this is pure theoretical speculation. Numeral system with the base 3 is slightly more dense than that of 2, and 3-based computers were really built, but appeared more complex than binary computers.


Reducing the Height of Context-Free Grammars Let $G$ be a context free grammar in Chomsky normal form (CNF) with language $L(G)\subseteq \Sigma^n$. In other words, all strings generate by $G$ have size $n$.

Say that a string $w\in L(G)$ has height $h$ if $w$ has a parse-tree of height at most $h$. Say that $G$ has height $h$ if each string $w\in L(G)$ has height $h$. Let $|G|$ be the number of production rules in $G$. I have the following problem, which I believe it is well studied in the field of parallel parsing, but with a somewhat distinct terminology.

Problem: Given a context free grammar $G$ in CNF accepting a language $L(G)\subseteq \Sigma^n$, construct a context free grammar $G'$ in CNF such that

$L(G') = L(G)$,
$h(G') = O(\log n)$,
$|G'| = |G|^{O(1)}\cdot n^{O(1)}$.

Does the problem given above has always a solution?
In other words, from $G$ we want to construct a context free grammar $G'$ accepting the same language as $G$ but such that every string in this language has a parse tree of logarithmic height. The size of the obtained grammar $G'$ is allowed to blow up polynomially in $n$ and in the size of the original CFG $G$.

I'm mostly interested in references dealing with the problem above or similar problems.

Obs 1: Without the requirement that $|G'|=|G|^{O(1)}\cdot n^{O(1)}$, we can construct a grammar $G'$ with size $2^{O(n)}$ by considering a distinct set of production rules for each string in $L(G)$.

Obs 2: I don't care about the time necessary to construct $G'$. The only important thing is its size $|G'|$.

Obs 3: Both grammars are required to be in Chomsky normal form. Also both are allowed to be ambiguous.

The partial case is presented here: Balancing Straight-Line Programs for Strings and Trees. I'm not sure, that the problem can be solved in the general case.


Kruskal-Katona Theorem with Majority? I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem.

Let $A_k \subseteq \{0,1\}^n$ be a subset of the hypercube such that every element in $A$ has exactly $k$ ones. For any element $x \in \{0,1\}^n$ let $N_l(x)$ be the set of elements obtained by flipping one of the 1's in x to 0. (Generally referred to as the lower shadow of X)

Let the majority upper shadow of $A_k$ referred to as $M_u(A_k)$ be the set such that for each $a \in M_u(A_k)$ number of ones in $a = k+1$ and $|N_l(a) \cap A_k| \geq (\frac{k+1}{2})$. That is more than half of a's neighbours are present in $A_k$. Given the size of $A_k$ can we put an upper bound on the size of $M_u(A_k)$.

Has this problem been studied and are there results are relevant to the above. Note that in case $|A_k| = \binom{n}{k}$ we of course have that $|M_u(A_k)|=\binom{n}{k+1}$. In general I am looking at the size of $A_k$ to be $\epsilon\cdot \binom{n}{k}$ where $\epsilon$ is a small constant.

Could you also refer to me a good survey of the Kruskal-Katona Theorem in general , one that surveys recent results in this setting ?

Thanks in advance

I am not sure if these results are known. If you define the $t$-thick upper (or lower, does not matter) shadow of $A_k$ as the sets of one level higher (resp. lower) that contain (resp. are contained in) at least $t$ sets from $A_k$, then what you ask for is the $(k+1)/2$-thick upper shadow. As far as I know it is open to determine the size of the smallest $A_k$ whose $2$-thick shadow is empty. Unfortunately I cannot point you to a reference but I think I heard it from Katona. (And in case I am wrong, then I remember incorrectly...)