Maximizing a monotone supermodular function s.t. cardinality I've tried to comb the literature and seen a lot of references to results that almost but don't quite seem to address this.

  Question: Is it known to be true or is there a hardness result contradicting that, for a monotone non-decreasing supermodular $f$, there is a polynomial-time
  constant-factor approximation algorithm for maximizing $f$ subject to
  a maximum cardinality constraint?

Background: Given a ground set $U$ of items, $f: 2^U \to \mathbb{R}_{+}$ is supermodular if for all subsets $A,B$ of $U$, we have $f(A) + f(B) \leq f(A \cup B) + f(A \cap B)$. It is monotone non-decreasing if $S \subseteq S' \implies f(S) \leq f(S')$. A maximum cardinality constraint means to maximize $f(S)$ over all subsets $S$ of size at most $k$, where $k$ is given as input.

My current understanding: This problem seems under-studied because supermodular maximization is equivalent to submodular minimization, so people focus on the latter. Submodular minimization subject to a smallest-size cardinality constraint (i.e. $|S| \geq k$) has a very strong lower bound[1].

But there are several issues in transferring such bounds. (1) It is not clear how the notion of approximation factor would transfer (I'm assuming my supermodular function is nonnegative so the transformation would be always negative...). (2) I'm assuming my supermodular function is montone increasing, whereas it seems nobody has been motivated to study the case of negative decreasing submodular minimization. (3) In this particular example, the cardinality constraint "goes the wrong way".

For a different example approach, you might try to reason as follows. The clique problem (find a clique of size k) is hard, and in fact, known to be inapproximable, hence my objective is inapproximable. However, when you think about the supermodular objective function for clique, it would be "find the set of at most $k$ vertices having the most edges in their induced subgraph", whereas the inapproximability result applies to "find the largest clique of size at most $k$". And I don't see a hardness result anywhere for the correct objective. The same kind of issue seems to go for planted clique and densest $k$-subgraph.

In short, it seems that it would be very surprising to have an approximation, but nobody has bothered to prove this in so many words (though actually for all I know, an efficient approximation algorithm exists).

[1] Svitkeina, Fleisher 2008 http://arxiv.org/abs/0805.1071

I think this is an example showing no kind of approximation is possible except with exponential$(k)$ value queries.

Let $f(S) = 0$ if $|S| \leq k$, otherwise $f(S) = |S| - k$. Now pick a special set $S^*$ uniformly at random from all sets of size $k$, and let $f(S^*) = 0.5$.

I'm claiming that this function is supermodular because every element initially has $0$ marginal value, then possibly $0.5$, then $1$ thereafter. So marginal value of any element only increases in a superset.

$S^*$ maximizes the function subject to a cardinality constraint of $k$, with an objective value of $0.5$.

Meanwhile any algorithm making subexponentially many value queries will be unable (except with tiny probability) to find a feasible set with nonzero value.


Travelling Salesman Problem where a subset of the nodes must be visited in a particular order I’m curious whether there is any work on the variant of the Travelling Salesman Problem where a subset of the nodes must be visited in a particular order. I haven’t found anything with searches or in survey articles, but that may just mean I haven’t found the right search terms or the right surveys.

If there are $n$ nodes in the graph, and a list $a_1, \dots, a_k$ of nodes that must be visited in that order, I can transform the problem to an instance of ATSP with $2k(n-k)+k$ nodes. The result is asymmetric even if the original edge-weights were symmetric, so we lose another factor of $2$ if we want to reduce it to a symmetric instance. I would be interested to know if there is a more efficient reduction.

Edited to add: On further reflection I think I can improve the reduction to $k(n-k)+k$ nodes.

This is a special case of the precedence-constrained TSP which has been studied quite a lot. For instance, there are a polyhedral analysis by Balas, Fischetti and Pulleyblank, and a branch-and-cut algorithm by Ascheuer, Jünger and Reinelt.


Complexity of finding weighted edge-disjunctive triangles in a graph Given a simple graph, in which the edges are weighted with values from the set $\{-1,1\}$. Three pairwise adjacent edges define a triangle. A triangle is called valid, iff two edges have positive weight and one edge has negative weight.

Find a set $S$ of valid, edge disjunctive triangles, such that the cardinality of $S$ is maximized.

Background: An answer to the above question can be used to calcualte an upper bound for the Clique-Partitioning-Problem (Grötschel, Wakabayashi (1989): A CUTTING PLANE ALGORITHM FOR A CLUSTERING PROBLEM, Math. Prog.)

I assume that the problem is NP-complete. However, I failed to reduce "Independent set", "3D Matching", and "Partition into triangles" to the above problem. (Of course there still may be such reduction)

Here's a reduction from edge coloring that I believe shows this to be NP-complete.

Let G,k be an instance of edge coloring: that is, we wish to know whether the edges of graph G can be colored with k colors. Make all edges in G negative, and add k new vertices to G, each connected by positive edges to every existing vertex in G.

Then, if G has an edge coloring, the modified graph has a set of edge-disjoint valid triangles that includes all of the edges in G: simply form a triangle connecting each edge in G to the new vertex that corresponds to its color. Conversely, if there exists a set of edge-disjoint valid triangles that includes all of the edges in G, then one can use the identities of the new vertices in each triangle as colors in an edge coloring of G.


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

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

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

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

If N is a power of two, I believe O(N log N) operations suffice, even for a somewhat more restricted problem in which all items start on one of the queues and must end up in reverse order on one of the queues (without the input and output lists).

In O(N) steps it is possible to start with all elements on one queue, play "one for you one for me" to split them into alternating subsets on the other queue, and then concatenate them all back into one queue. In terms of the binary representations of the positions of the items, this implements a rotate operation.

In O(N) steps it is also possible to pull off pairs of elements from one queue, swap them, then put them back, reversing all pairs. In terms of the binary representations of the positions of the items, this complements the low order bit of the position.

By repeating O(log N) times an unshuffle and a pairwise swap, we can complement all the bits of the binary representations of the positions — which is the same thing as reversing the list.


Finding all solutions by Grover search(not superposition) When there are multiple marked elements, grover search provides only superposition of them. If I want to find all the marked elements, not superposition, I could try this:

1) Do Grover search, get superposition of t marked element,

2) observe ele space, get one marked element,

3) remove that element,

4) goto 1)

This takes time step $O(\sqrt{\frac{N}{t}}+\sqrt{\frac{N-1}{t-1}}+\dots+\sqrt{\frac{N-t+1}{1}})$.

My question is, can i do better?

First note that the sum $O\left(\sqrt{\frac{N}{t}}+\sqrt{\frac{N-1}{t-1}}+\dots+\sqrt{\frac{N-t+1}{1}}\right) = O(\sqrt{Nt})$.

The quantum query complexity of this problem is indeed $\Theta(\sqrt{Nt})$.

The lower bound can be shown by reduction from the problem of deciding whether the input has $t$ marked elements or $t+1$ marked elements. This problem is very similar to $t$-threshold, and has a lower bound of $\Omega(\sqrt{Nt})$. This can be shown using the polynomial method or the adversary method.


Regular expressions without alternation I was wondering about what sets of languages are generated by restrictions of regular expressions.  Supposing that all the restrictions have a constant symbol for each element of $\Sigma$ and concatenation.  Then eight classes can be formed by the presence or absence of complement/negation, alteration/union, and the Kleene star.  (Yes, 'normal' regular expressions don't have a $^C$ operator, but it's convenient here.)

Expressions allowing alternation and the Kleene star, with or without complement (what's a little double-exponential blowup amongst friends?), generate the regular languages. Expressions allowing alternation and complement but not the Kleene star generate the star-free languages. Expressions allowing alternation but not complement or the Kleene star generate the finite languages.

But can any interesting classes of languages be generated without alternation?  Without any of the three operators all that can be generated is a single word.  The complement operator doesn't help much here.

With just the Kleene star the class is somewhat interesting... it's not clear if they can be recognized any faster than regular languages.  (Is anything nontrivial known about these?)

With both the Kleene star and complement... do you get anything interesting?  Does this class have a name?

This question was inspired by Regular Expression question on math.se.

The class of regular languages that can be described by regular expressions without union (and without complementation) are known as union-free regular (also: star-dot regular) languages. This class of languages apparently has received some attention recently:

Benedek Nagy: "Union-free regular languages and 1-cycle-free-path-automata", Publicationes Mathematicae 68(1-2), 2006.

Sergey Afonin and Denis Golomazov: "Minimal Union-Free Decompositions of Regular Languages", Language and Automata Theory and Applications, Springer 2009.

Galina Jirásková and Tomás Masopust: "Complexity in Union-Free Regular Languages", Developments in Language Theory, Springer 2010.


Complexity of a variant of the Mandelbrot set decision problem? Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$  where $c$ is a complex number

Let Set $M=${$(c,k,m) |$ the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ is unbounded and some number $P^n_c (0)$ has a complex magnitude greater than 2 (but less than $m$) for some integer $n$ > $k$}

Assume $k$ and $m$ are integers given in unary encoding

  Is there an efficient algorithm in the real computing model (i.e the Blum-Shub-Smale model) for deciding set $M$ ?

Essentially, I'm asking if there exists efficient algorithm that decides whether the sequence is UNBOUNDED such that breakaway occurs at a number of iterations more than K.

UPDATE: The problem is in $NP$ since there is a polynomially verifiable certificate of membership.

  So, Is there an efficient algorithm or is it $NP$-hard to decide set $M$?

The problem went through major changes for these reasons:

1-For the problem to be interesting, "<" was changed to ">" in the definition.

2-I wanted the problem to be in $NP$, so I introduced parameter $m$.

Also, the bounty may be awarded to the first person who poses an $NP$-complete problem related to Mandelbrot Set

Let's look at $M$ for fixed $k$ first.

Given a fixed $k$ in unary, the problem essentially reduces to figuring out the algebraic set $|P_c^{(k)}(0)| = 2$.  Since the level sets 'at infinity' are properly nested, the question becomes a membership test in an algebraic set.  The issue is that the minimal polynomial is of degree $2^k$.  However, one can represent it as a straight-line problem of size $k$.

So then the question becomes: what is your arithmetic model?  You'll need arbitrary precision arithmetic to do this 'right', and then counting bit operations or counting "real number" operations will give radically different answers [NP-hardness is rather fragile that way, unlike 'computability'].

For arbitrary $k$, things get messier still.  It really depends on whether one would have a uniform modulus of continuity; if that were the case, then the Mandelbrot set would be locally connected, which would indeed be a breakthrough.  So I rather think that that problem is open.

Looking up the Yampolsky and Braverman book is a good idea in any case.


Approximate Maximum Weight Matching I am looking for an approximated (or randomized) maximum weight matching algorithm. Do you have any suggestion for me?

In my problem, I have a bipartite graph with N abound 1000 (#vertices on each side) and the Hungarian algorithm takes too much time to be an option for my case.

the weight on edges are real numbers but it's ok to round them to integer numbers
I have a brute-force greedy implementation, however, I am looking for something more sophisticated

Thanks

You should try Sage's implementation. It uses LP, but I don't think that you would get something so large in less than 100milliseconds. Greedy probabilistic would be nice in this case I guess.

http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph.html#sage.graphs.graph.Graph.matching


Job scheduling: minimizing number of reads Consider the following scheduling problem:

input:

set of computations $C = \{c_1, ..., c_n\}$
set of computing nodes $P = \{p_1, ..., p_n\}$
Dependency graph $D$ between jobs (DAG) $(c_i,c_j)$ means $c_i$ depends on/reads $c_j$

output:

Schedule S = subset of $C \times [1,n]$ where $(c_i,k)$ means that job $c_i$ will be executed in timeslot $k$
the following conditions hold:

precisely one timeslot per job
dependencies have lower timeslots

Now, we want to minimize the cost of the schedule:

$cost(c_i,S) = |\{ k \mid (c_j,k) \in S \wedge (c_i, c_j) \in D \}|$
i.e. the cost of a job is the number of levels where it is read
$totalCost(S) = \sum_{c_i \in C} cost(c_i,S)$

Hence, we want to calculate the best way of assigning the computations to timeslots, such that the number of reads are minimized. Note that the number of computing nodes is irrelevant.

I cannot seem to find any papers on this specific problem. Does anyone know whether this has been investigated? It seems it has to be... :)

Edit:

we can rephrase this as a graph problem:
Consider a DAG $G = (V,E)$.

A schedule is a mapping $S:V\rightarrow\mathbb{N}$ which assigns a number to each node, such that if $v_1$ is reachable from $v_2$, then $S(v_1) < S(v_2)$.

Define the cost of a node $v_1$ is defined as $cost(v_1) = |\{S(v_2) \mid (v_2,v_1) \in E\}|$, i.e., the number of different numbers that are assigned to parent nodes.

The problem: find a schedule S that minimizes the total cost over the nodes.

After a failed polynomial-time quick attempt, here it is an idea to prove that it is NP-complete using a reduction from 3SAT.

Given a 3SAT formula with $x_1,...,x_n$ variables and $C_1,...,C_m$ clauses, first build a variable assignment gadget like in the figure below (thanks to @Jukka for the clarifications, the graph drawing style, and the hint for the gadget with two configurations and same cost!).

Each blue horizontal line corresponds to a different schedule time ($s=1,2,...$).
On the left of the picture there is a complete assignment gadget for three variable ($x1,x2,x3$).
The red nodes correspond to a $true$ assignment ($+x_i$), the blue nodes to a $false$ assignment ($-x_i$). A green node correspond to a variable $x_i$ and can be placed
on the same schedule time of the red or the blue node, without afftecting the total cost of the gadget. The three possible combinations for $x_1$ are showed on the right. The number in the nodes represents the cost (the number of distinct parents). Both $x_1 = true, x_1 = false$ have a cost of 7 ($c=7$). Note that the last combination has a greater cost so it cannot be used.

Now we extend the assignment gadget to "simulate" the clauses of the formula.

First we add a top node, and a mirror chain of $3n+2$ nodes (the chain of nodes on the left of the picture). By construction some of the nodes of the mirror chain must be on the same schedule time of the $true/false$ assignments; we call them $+x'_1, -x'_1, +x'_2, -x'_2,...$ (yellow nodes of the mirror chain in the figure).
Now we add a clause node $C_j$ for each clause and we force it to be at schedule time $s=1$ by adding two directed edges from the bottom of the mirror chain and assignment gadget.

We link the clause node to the three variables it contains (green edges in the figure), and to the corresponding positive/negative literal in the mirror chain (red edges in the figure). Finally we link the clause node to the top node using a chain of 6 clause pegs $P_{j_1},...,P_{j_6}$ (purple nodes in the figure).

How it works

The clause pegs of $C_j$ are linked together so they must be placed at different schedule times. So the cost of $C_j$ is greater than or equal to $6$. We can keep the cost of $C_j$ equal to 6 if and only if the assignment corresponding to the position of the green variables nodes contained in $C_j$ satisfies $C_j$.

First of all note that the bottom peg $P_{j,1}$ must be put at schedule time $s=2$ because $C_j$ is linked to the bottom of the assignment gadget and mirror chain. So only 5 of the pegs are "free" to be assigned to greater schedule times (otherwise the cost of $C_j$ is \geq 7$).

Now, suppose for example that $C_1$ is $(x_1 \lor \bar{x}_2 \lor x_3)$ (like in the figure). We have the green edges: $x_1 \to C_1, x_2 \to C_1, x_3 \to C_1$ and the red edges $+x'_1 \to C_1, -x'_2 \to C_1, +x'_3 \to C_1$.

Suppose that we set $x_1 = true, x_2 = true, x_3=false$ then the green variable $x_1$ will be on the same schedule time of $+x'_1$. But $x_2, -x'_2$ and $x_3, +x'_3$ will be on different schedule times. We can put a peg on the same schedule time of $x_1=true$, and the remaining 4 can be placed on the same schedule times of $x_2=true, -x'_2, +x'_3, x_3=false$ ("mask" them). The total cost of $C_1$ is still 6.

But what happens if we cannot find an assignment that satisfy all clauses? Then, in at least one clause (suppose $C_1$), the green variable nodes $x_1=false,x_2=true,x_3=false$ are all on a different schedule time of the corresponding $+x'_1, -x'_2, +x'_3$. So the 5 free pegs are not enough to "mask" them and the number of distinct parents of $C_1$ increases to $7$, like in the figure below.

Note that without the pegs, the (minimum) total cost $c_t$ of the schedule is fixed, so we can conclude that after adding the pegs, the original formula is satisfiable if and only if the total cost of the graph is less than $c_t + 6*m$.


Quantum capacity for ensemble of Pauli channels In Preskill's quantum computing notes Chapter 7 approximate page 82, he shows that a Pauli channel has capacity $Q \geq 1-H(p_I,p_X,p_Y,p_Z)$ where $H$ is Shannon entropy and $p_I, p_X, p_Y, p_Z$ are the probabilities of the channel acting like the appropriate Pauli matrix. In particular this gives us the 'hashing bound' or 'random coding bound' for the quantum capacity of the depolarizing channel $Q(p) \geq 1-H(p,1-p)-p\log_23$.

He then describes work of Shor and Smolin [1]: if you take a $m$-repetition code and concatenate it with a suitable random code you can do better than the hashing bound. The argument for this is that taking $m-1$ measurements the inner repetition code thought of as a super channel is a Pauli channel with entropy $H_i$. Then averaging over the $2^{m-1}$ possible classical measurements you can find the average entropy of the superchannel $\langle H \rangle$.

[1] P.W. Shor and J.A. Smolin, “Quantum Error-Correcting Codes Need Not Completely Reveal the Error Syndrome” quant-ph/9604006; D.P. DiVincen, P.W. Shor, and J.A. Smolin, “Quantum Channel Capacity of Very Noisy Channels,” quant-ph/9706061.

Then by random coding on this new channel you can achieve a rate $R=\frac{1-\langle H \rangle}{m}$ (dividing by $m$ to get this rate in bits/original channel use).

I don't see how random coding works. You have a random code which is optimal for each particular channel but how do you decide which one to use? By the time you know the classical measurements for your channel you have already sent the codeword.

So two questions:

1) If you have an ensemble of Pauli channels with average entropy $\langle H\rangle$, can you by using random coding achieve a rate $1-\langle H \rangle$?

2) If you can't do this, am I misinterpreting the results of Shor and Smolin or Preskill's exposition?

For your question (1), the answer is yes. The 'hashing construction' for quantum encoding is independent of the quantum channel you use, so if you use this construction for encoding, you can send information over an ensemble of Pauli channels at the right rate. (Actually, this is slightly incorrect ... you do need that the input state you use in the formula for coherent information is the same for all the channels, but in the construction discussed by Preskill it is.)

The original paper Shor and Smolin does not mention an ensemble of channels. If you take a depolarizing channel near the quantum-capacity threshold you can achieve a larger quantum capacity by considering a new superchannel where one signal of the superchannel is five consecutive uses of the original channel. When you apply the 'hashing bound' to this superchannel (acting on a 32-dimensional quantum space rather than a 2-dimensional one), you find that the formula for quantum capacity is larger than five times the formula for the original channel. There is only one channel being considered here: the superchannel composed of five uses of the original channel, and not an ensemble of channels. The ensemble of channels comes in when Preskill gives the intuition for what is happening in Shor-Smolin.

(And of course you should replace five in the above paragraph with the appropriate value of $m$, which is only five for some of these constructions.)


Finding good induced subgraph You are given a graph $G = (V,E)$ with $n$ vertices. It might be bipartite if you  want. There are $m$ sets of edges $E_1,\ldots, E_m \subseteq E$ (say disjoint). I am interested in the problem of finding a subset $S \subseteq V$, as small as possible (or even smaller), such that the induced graph $G_S$ has at least one edge from each class $E_i$, for $i=1,\ldots, m$.

Currently, I know that this problem is set cover hard. I also have a not completely obvious (roughly) $O(\sqrt{n})$ approximation.

This seems like a natural problem - is anyone aware of any relevant references, or any better algorithms?


Functions that typed lambda calculus cannot compute I just want to know some examples of the functions that can be computed by the untyped lambda calculus but not by typed lambda calculi.

As I am a beginner, some reiteration of background information would be appreciated.

Thanks.

Edit: by typed lambda calculi, I was intending to know about System F and the simply-typed lambda calculus. By function, I mean any Turing-computable function.

A nice example is given by Godelization: in lambda calculus, the only thing you can do with a function is to apply it. As a result, there is no way to write a closed function of type $(\mathbb{N} \to \mathbb{N}) \to \mathbb{N}$, which takes a function argument and returns a Godel code for it.

Adding this as an axiom to Heyting arithmetic is usually called "the constructive Church thesis", and is a strongly anti-classical axiom. Namely, it is consistent to add it to HA, but not to Peano arithmetic! (Basically, it is a classical fact that every Turing machine halts or not, and there is no computable function that can witness this fact.)


Prior work on finding domain-theoretic suprema of equivalent total functions? In slightly more down-to-earth terms, this question is sort of about lazy evaluation in functional programming - except that it's more ambitious in general than just seeking what a typical Haskell programmer would consider "least-strict". If the previous sentence made no sense to you, don't worry, ignore it.

In domain theory, we examine posets, and for the purposes of this question we will consider a poset to represent the set of possible partially-specified values of a type in a non-strict programming language, such that two partial values $x$ and $y$ are ordered as $x \sqsubseteq y$ iff $y$ is $x$ "plus zero or more extra bits of information". In other words, $x \sqsubseteq y$ iff y is a version of $x$ where zero or more of the "holes" or "thunks" (if any) have been filled in.

We can (and do) extend this partial order to Scott-continuous functions, by stipulating that $f \sqsubseteq g$ iff for all $x$, $f(x) \sqsubseteq g(x)$.

However, note that in the case of Scott-continuous functions, $f$ can be $\sqsubseteq$ $g$ even if $g$ is distinguishable from $f$ but does not provide any extra information. This can be the case if $g$ provides the same information "more parsimoniously" (or "more lazily", depending on how you want to look at it).

My question is this: If $f$ is a Scott-continuous computable function, and is "total" (i.e. the elements of its domain are all finite, and it takes "fully-defined" values to "fully-defined" values), have techniques been developed for computing a maximal $h$ such that $f \sqsubseteq h$?

Of course, if the domain of $f$ is a finite set, one can just represent $f$ as a lookup table and then use elementary deduction to compute $h$. It's not necessarily efficient in practice, but it yields the correct answer. But what about functions over infinite domains?

My question is this: If f is a Scott-continuous computable function, and is "total" (i.e. the elements of its domain are all finite, and it takes "fully-defined" values to "fully-defined" values), have techniques been developed for computing a maximal h such that f⊑h?
Of course, if the domain of f is a finite set, one can just represent f as a lookup table and then use elementary deduction to compute h. It's not necessarily efficient in practice, but it yields the correct answer. But what about functions over infinite domains?

Scott-continuity rules out the lookup table approach. For a concrete counterexample, let's start with the Sierpinksi domain $O = \{\bot, \top\}$, with order $\bot \sqsubseteq \top$.
Intuitively, think of $\bot$ as nontermination, and $\top$ as termination. In Haskell terms, think of this as the domain interpreting expressions of type $()$ -- i.e., you either get back a unit or the expression fails to terminate. We'll also use $2$, the booleans, and $2_\bot$, the pointed booleans.
Now, suppose you have $f : O \to 2_\bot$. You can't continuously complete this function, even though there are only a finite number of possible $f$'s! The intuitive reason is that when you run $f(\bot)$, there's no finite waiting period sufficiently long enough to decide that its return value is bottom -- if there were, then I could give you a function that spins for one second longer, and then returns the opposite of whatever you completed the function to. (Prove that any continuous $h : (O \to 2_\bot) \to (O \to 2)$ must return a constant function independent of its argument $f$.)
Don't think of bottom as an extra element of the domain of values. This will lead you astray. Instead, think of elements of the domain as observations of a computation. Really do think of sitting in front of a terminal, waiting for your program to print something. Bottom represents your observation when the program is still running and hasn't printed anything to the screen -- it represents observing nothing.
The best book I know for developing the right intuitions is Steve Vickers' Topology via Logic. It's a short and easy read, but your domain-fu will go way up for reading it.


Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient This is somewhat of a meta-cstheory question, and is more historical in nature. What are some good examples of problems for which the literature followed the develpment below:

The original algorithms, despite being hopelessly intractable (e.g. exponential or high-degree polynomial), were considered breakthroughs at the time by the TCS community;
Since then, extremely efficient (e.g. provably linear or sublinear, maybe sub-quadratic) algorithms have been developed and are used in practice.

So, 1) precludes algorithms which have inefficient solutions (e.g. brute-force), but also have efficient solutions. The idea is that these are problems that were initially considered so difficult that even inefficient algorithms were considered a breakthrough by the research community. 2) is meant exclude problems that have shown incremental progress, even if those incremental developments are/were considered theoretically significant (e.g. exponential to high-degree polynomial).
In other words, have we gone from problems that were considered theoretical curiosities to practical, usable algorithms that are widely adopted in practice?

Computing a generating set of invariants (sometimes called the computational problem of "Noether's Normalization Lemma") for the action of $SL_3$ on an $n$-dimensional vector space $V$. (You can also talk about $SL_m$, but it's just a little cleaner to state the results when $m=3$.)
Went from non-constructive proof of finiteness, to computable, to EXPSPACE, to nearly-polynomial, over the course of over a century.
As discussed in GCT V: Hilbert originally proved that the invariant ring $\mathbb{C}[V]^{SL_3}$ was finitely generated non-constructively. After Gordan's criticism, Hilbert [1893] gave an algorithm, showing (in modern language) that a finite generating set can be computed in finitely many steps (so, the problem became computable). Degree bounds proved nearly a century later by Popov and then Derksen combined with Gröbner basis puts it into $\mathsf{EXPSPACE}$. In GCT V, Mulmuley put this problem into time $n^{O(\log \log n)}$.


Beginner's Guide to Derandomization I found the book Pairwise Independence and Derandomization on the subject, but it's more research-oriented than tutorial oriented.

I'm new to the subject of "Derandomization," and as such, I wanted to know which reference to start from?

I prefer one that discusses literature and history, as well as the technical details.

The notes from Salil Vadhan's class, "Pseudorandomness", are excellent for this purpose.  He is writing a textbook based on these.  The draft version of the book is available online.


Data structure for shortest paths Let $G$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Is it possible to preprocess $G$ and produce a data structure of size $m \cdot \mathrm{polylog}(n)$ so that it can answer queries of the form "distance between $u$ and $v$" in time O(n)?

The problem seems too basic to be unsolved.

This is a very interesting question. At a high level, you are asking whether one can preprocess a graph such that shortest path queries become independent of the density of the graph, without using much extra space -- interesting, but as you say, unresolved.

If you are happy with approximate distances, here is a way to get a $2$-approximation. Let $G$ be a weighted undirected graph with $n$ nodes and $m$ edges. It is shown in the following paper that for approximate distance queries, designing data structures for graphs with $m$ edges is no harder than graphs in which each node has degree bounded by $m/n$:

R. Agarwal, P. B. Godfrey, S. Har-Peled, Approximate distance queries and compact routing in sparse graphs, INFOCOM 2011

So, assume that $G$ is a $m/n$-degree bounded graph. Sample $\alpha = O(m/n)$ nodes uniform randomly; call these landmark nodes. During the preprocessing phase, store the distance from each landmark node to each other node in the graph; this requires $O(m)$ space. For each node $u$, store its closest landmark node $\ell(u)$. Also, store the graph within the data structure, say as an adjacency list.

When queried for distance between $u$ and $v$, grow balls around both nodes -- ball of node $w$ is defined as the set of nodes that are strictly closer to $w$ than to its closest landmark node, say $\ell(w)$. It can be shown that the size of each ball is $O(n^2/m)$, in expectation. Let $\Gamma(u) = B(u) \cup N(B(u))$, where $B(u)$ is the ball of node $u$ and $N(B(u))$ is the set of neighbors of nodes in $B(u)$. It can be shown that the size of $\Gamma(u)$ is $O(n)$, in expectation.

Answering the query: if $\Gamma(u) \cap \Gamma(v) \neq \emptyset$, return $\min_{x \in \Gamma(u) \cap \Gamma(v)} \{d(u, x) + d(v, x)\}$; else if $d(u, \ell(u)) \leq d(v, \ell(v))$, return $d(u, \ell(u)) + d(\ell(u), v)$; else return $d(v, \ell(v)) + d(\ell(v), u)$. It is easy to show that this is a $2$-approximation.

In terms of query time, note that growing balls takes $O(n)$ time for a $m/n$-degree bounded graph; constructing $\Gamma(u)$ and $\Gamma(v)$ given respective balls takes $O(n)$ time (since neighbors are stored within the data structure); and checking whether $\Gamma(u) \cap \Gamma(v)$ is empty or not also takes $O(n)$ time.

The above bounds are in expectation; I think it is easy to derandomize the construction. Unfortunately, this technique does not seem to allow getting approximation better than $2$. Its a very interesting question though ....


Postselection in geometric complexity theory Context: As I understand, in geometric complexity theory, the existence of obstructions serves as a proof-certificate, so to speak, for the nonexistence of an efficient computational circuit for the explicit hard function in the lower bound problem under consideration. Now there are some other assumptions for obstructions that they must be short, easy to verify and easy to construct.

Question: My question is that say I have a problem that I conjecture to be solvable in polynomial time. Then how can I show that there exist no obstruction for this problem, i.e. if no obstructions exist then the problem can be computed efficiently and it is indeed in polynomial time.

Approach: I think, and I may be wrong in this assertion, that showing no obstructions exist can be equivalent to standard reduction of NP problems to other problems whose complexity is yet unknown, in the proof that they themselves are in NP. So then in that case one can, if possible, show that obstructions exist as one tries to reduce an NP problem to the problem under consideration, that way, the reduction is intractable. Also what role does postselection play in all of this? Is it possible to simply postselect on the nonexistence of obstructions? Thanks and pardon the lack of precise statements in my approach and questions.

Just an another example, consider a problem X that we know to be in P. Now let's say we didn't know about that problem being solvable in polynomial time, then is it possible, that one can make the following assertion:

Since no obstructions exist in the computation of X we can say that it is in the class P

From there on, the problem is the easy (computationally) discovery of those obstructions, if even one exists, would show that X is not in polynomial time. However going the other way, i.e. finding that no obstructions exist is a difficult task.

I like to think this way too, and I link it with the $P=NP\cap co-NP$ conjecture. It is mentionned there or there (I am having a hard time finding pages about this conjecture as I can only refer to it with math symbols that Google does not like).

A problem is in NP when you can give a certificate for a "True" answer (example : a hamiltonian cycle for the TSP problem or a valid assignment for the SAT problem). It is in co-NP when you can give a certificate for a "False" answer (example : a "proof" that the SAT formula is not satisfiable, a bad cut in a graph that prevents the existence of a hamiltonian cycle, etc...)

Actually, those may be the "obstructions" you may refer too. And this conjecture is about saying : a problem which is in NP is polynomial when I know what the obstructions are.

Now, the "obstructions" can take many different forms. For the matching problem (which is polynomial) it can be a partition of the graph (see Tutte's characterization of graphs admitting a perfect matching), or it can be the certificate given by Farkas's Lemma for linear programming (and graph problems that can be reduced to it). It can actually be a great many things, and so I usually "use" this conjecture in one direction :
When I can find no obstructions, I do not deduce that my problem is NP-Hard. Some obstructions are really hard to find... But when I have a complicated polynomial algorithm for a problem, I am sometimes convinced that "there must be an understandable set of obstructions, which would be easier to understand that the complicated algorithm".

Well... My two cents :-)

Nathann


Quantum polynomial hierarchy vs counting hierarchy First of all, I'm kinda surprised that I couldn't find any paper/article defining such hierarchy.

It can be defined as follows:

$\Delta_0^{\mathsf{BQP}}=\Sigma_0^{\mathsf{BQP}}=\Pi_0^{\mathsf{BQP}}=\Delta_1^{\mathsf{BQP}}\mathsf{=BQP}$

$\Delta_k^{\mathsf{BQP}}=\mathsf{BQP}^{\Sigma_{k-1}^{\mathsf{BQP}}}$

$\Sigma_k^{\mathsf{BQP}}=\mathsf{QMA}^{\Sigma_{k-1}^{\mathsf{BQP}}}$

$\Pi_k^{\mathsf{BQP}}=\mathsf{coQMA}^{\Sigma_{k-1}^{\mathsf{BQP}}}$

Is this whole hierarchy known to be contained in some finite level of counting hierarchy like $\mathsf{PH}$ (which is contained in the second level of counting hierarchy, $\mathsf{P^{PP}}$)? If not, are there some expectations on it?

I was quite surprised as well to not find this hierarchy in the literature, so I wrote my graduate thesis about it. It will be available online soon, at which point I will update this answer with a link to it. I was able to prove some interesting theorems about it.

Theorem For every $i$, $\Sigma_i^{\mathsf{BQP}}\subseteq C_i^\mathsf{P}$, where $C_i^\mathsf{P}$ is the $i$-th level of the counting hierarchy. So the whole hierarchy is contained in the counting hierarchy.

Proof Trivially from $QMA\subseteq PP$. $\square$

Theorem If $\Delta_i^{BQP}=\Sigma_i^{BQP}$ then $BQPH=\Delta_i^{BQP}$.

Proof Excercise for the reader.

Theorem If $QMA=PP$ then $PH\subseteq QMA$ and indeed $PH^{PP}=QMA$.

The first part of this theorem was originally by Vyalyi [4], but his proof is six pages of algebra, whereas new ideas that originated from thinking about your hierarchy allow me to get there in just a few lines:

Proof I prove a new theorem: $QMA\cap coQMA=P^{QMA\cap coQMA}$. This gives us $QMA=P^{QMA}=P^{PP}\supseteq PH$ by Toda. $\square$

For the new part, $PH^{PP}=QMA$, you will have to read my thesis. There's no obvious analogue of Toda's theorem. The reason is that the critical ingredient $QMA\subseteq BPP^{\oplus P}$ seems hard in the quantum case, whereas classically $NP\subseteq BPP^{\oplus P}$ follows trivially from Valiant-Vazirani, because here we don't have a way to "count" solutions. Even if you take $QCMA$ instead of $QMA$, there's the inconvenience that a QCMA protocol can behave arbitrarily on bad certificates to yes-instances. To see what I mean, start with [1].

There's also no obvious analogue of a Karp-Lipton collapse, or Kannan-type circuit lower bounds. Recall that in the classical case, we have

Theorem [3] For every $k\in\mathbb{N}$, there is a language in $\Sigma_4^{P}$ that requires circuits of size $\Omega(n^k)$.

The reason there's no(t yet) a theorem replacing every $P$ in this theorem with $BQP$ is that a critical ingredient in his proof is that he is able to (non-deterministically) guess a circuit and then evaluate that circuit, i.e. compute the circuit's output on an input. Sure, we can guess a (description of a) quantum circuit, but we can only say that we evaluate it if it is a bounded-error circuit, and verifying this is a $\# P$-Hard problem.

Scott Aaronson and Andy Drucker prove something along the lines of a "quantum PH", going only to the second level:

Theorem [2] If $NP\subset BQP_{/qpoly}$ then $\Pi_2^P\subseteq QMA^{PromiseQMA}$.

When I asked Scott Aaronson, he said that people had been thinking about this hierarchy for 15+ years, but nobody had published it because nobody had proved anything non-trivial about it. Here's to hoping you or I change that.

Bonus Theorem! If $QMA=coQMA$ then $PH\subseteq QMA$. Just for you, because you made it all the way to the end of a long answer.

[1] Aharonov, Dorit, et al. "The pursuit for uniqueness: Extending Valiant-Vazirani theorem to the probabilistic and quantum settings." arXiv preprint arXiv:0810.4840 (2008).

[2] Aaronson, Scott, and Andrew Drucker. "A full characterization of quantum advice." Proceedings of the forty-second ACM symposium on Theory of computing. ACM, 2010.

[3] Kannan, Ravi. "Circuit-size lower bounds and non-reducibility to sparse sets." Information and Control 55.1-3 (1982): 40-56.

[4] Vyalyi, Mikhail N. "Qma= pp implies that pp contains ph." In ECCCTR: Electronic Colloquium on Computational Complexity, technical reports. 2003.


What are the consequences of $P \subseteq L/poly$? A language is in $L/poly$ if there exists a logspace Turing machine that decides the language with polynomial amount of advice.

See here for more info: https://en.wikipedia.org/wiki/L/poly

  Question

  What are the consequences of $P \subseteq L/poly$?

One simple consequence is $\mathbf{P}/\text{poly} = \mathbf{L}/\text{poly}$. Proof: For any language $A \in \mathbf{P}/\text{poly}$, there is a language $B \in \mathbf{P}$ and a sequence of polynomial-length advice strings $y_1, y_2, y_3, \dots$ such that $x \in A \iff (x, y_{|x|}) \in B$. By assumption, there is a language $C \in \mathbf{L}$ and a sequence of polynomial-length advice strings $z_1, z_2, z_3, \dots$ such that $(x, y) \in B \iff (x, y, z_{|(x, y)|}) \in C$. This implies $A \in \mathbf{L}/\text{poly}$; the advice string for $x$ is $(y_{|x|}, z_{|(x, y_{|x|})|})$.

(A concise version of the proof: $\mathbf{P} \subseteq \mathbf{L}/\text{poly} \implies \mathbf{P}/\text{poly} \subseteq (\mathbf{L}/\text{poly})/\text{poly} = \mathbf{L}/\text{poly}$.)


Computing the Cheeger constant: feasible for which classes? Computing the Cheeger constant of a graph, also known as the isoperimetric constant
(because it is essentially a minimum area/volume ratio), is known to be NP-complete.
Generally it is approximated.  I am interested to learn if exact polynomial algorithms
are known for special classes of graphs.
For example, is it still NP-complete for regular graphs?
For distance-regular graphs?
(I have not studied the existing NP-completeness proofs to examine their assumptions.)
Literature pointers appreciated—thanks!

Notice that approximating sparsest cut to within $\alpha$ gives a $2\alpha$ approximation for the Cheeger constant as defined. Here are some papers that give constant approximation algorithms for sparsest cut in restricted graphs:

Bounded genus: http://dl.acm.org/citation.cfm?id=1873619
Bounded treewidth: http://arxiv.org/abs/1006.3970

Furthermore, http://arxiv.org/abs/1006.3970v2 proves that sparsest cut is NP-hard for graphs with pathwidth 2, and has quite a few more references to approximating sparsest cut on restricted instances.

I would assume that for all classes of graphs mentioned in the paper, no exact algorithms are known (as they're interested in approximations). In particular, if sparsest cut is NP-hard for graphs with pathwidth 2, it's also NP-hard for graphs of treewidth 2, and cutwidth 2. I suppose that doesn't give quite a lot of room.. maybe there is another better parameterization for sparsest cut.

I am pretty sure that sparsest cut is NP-hard on regular graphs but can't find a reference.

Per noticed that I wasn't careful when I looked at the papers above. The hardness result is for nonuniform sparsest cut. Computing uniform sparsest cut or the Cheeger constant is easy on trees (WLOG the optimal cut separates a subtree). With a little more work that gives a dynamic programming algorithm for computing the Cheeger constant on bounded treewidth graphs.

Table 1 in paper 2 above also mentions a result that gives a constant approximation for graphs with an excluded minor.

For bounded genus graphs, the best that seems to be known is a constant approximation (paper 1 above gives $O(\sqrt{\log g})$ where $g$ is the genus.


Is there an algorithm that's "like" cross-validation for approximation algorithms of NP-hard problems? I normally do machine learning work, and when I'm evaluating an algorithm on a data set, I always use cross-validation to determine how effective the algorithm is.  Is there a similar method for evaluating approximation algorithms on specific instances of NP-hard problems?  If not, how do you determine which algorithm is best for a given problem domain in practice?

Crossvalidation is used to test the difference in behaviour between training and test data. There's no equivalent notion for approximations. However, for many problems it's possible (often via an LP relaxation) to get a good lower bound for a problem. This can be used to test the quality of a given approximation algorithm in practice.

For a good example of this, you should look at David Johnson's survey of experimental work on the travelling salesman problem.


Are randomly generated infinite patterns computable? Fix a prefix-free universal Turing machine $U$. Consider the following random process*. The state of the process is a bit-string $s$, initialized with the empty string (say). Suppose the value of the string on step $n$ is $s_n$. At the next step, we randomly generate a program $A$ using $U$, like in the definition of Chaitin's constant $\Omega$**. If $A$ doesn't halt we discard it and generate a new program. If it halts with output $t$ and $s_n$ is not a prefix of $t$ we also discard it and generate a new program. If $s_n$ is a prefix of $t$, we update the state according to $s_{n+1}:=t$. Note that $s_n$ is a prefix of $s_{n+1}$ i.e. at each step the string gets appended

Allowing the process to continue indefinitely, we get an infinite bit-string $s_{\infty}$. The question:

  What is the probability $p$ that $s_{\infty}$ is computable? Is $p > 0$?

Of course $p$ a priori depends on $U$ but my intuition is that if it vanishes for some $U$ it vanishes for all, for approximately the same reason Kolmogorov complexity only weakly depends on $U$

*This process is closely related to the concept of Solomonoff induction

**This is done as follows. We generate an infinite sequence of bits $a$ by flipping a coin an infinite number of times. Since $U$ is prefix-free, there is a unique prefix $A$ of $a$ which is a valid program for $U$

In the particular way you formulated the question the probability is 0. Because there are only countably many computable sequences, it suffices to show that for each computable sequence the probability is 0. So let's lets consider the sequence 000... (our reasoning works for any computable sequence).

Suppose at some time step $s = 0^n$ for some $n$. Now, we search for a program that outputs a string starting with $0^n$ and halts. For each program outputting $0^m$ with $m>n$, there exists a program that is only $O(1)$ bits longer and also appends $1$ to this output (i.e. it outputs $0^m1$). Hence, there is a probability that $s$ is extended with "wrong" bits, and this probability does not depend on the length of $s$. Therefore, generating infinitely many zeros has 0 probability.


Is $UL\neq PSPACE$ known? $L\neq DSPACE[\omega(\log n)]$ is known.
Is $UL\neq DSPACE[\omega(\log n)]$ and $UL\neq PSPACE$ known?

$\mathbf{UL}$ is contained in $\mathbf{NL}$, which is contained in $\mathbf{DSPACE}(\log^2 n)$ by Savitch's theorem, which is strictly contained in $\mathbf{PSPACE}$ by the space hierarchy theorem, so $\mathbf{UL}$ is strictly contained in $\mathbf{PSPACE}$. It would be surprising if e.g. $\mathbf{UL} = \mathbf{DSPACE}(\log^2 n)$, but I don't think it's known to be false.


Nontrivial separation consequences of P!=NP I am looking for nontrivial examples of complexity class separations that are known to follow from the P!=NP hypothesis. By a "nontrivial example" I mean that it is not just an automatic consequence of an easy containment relationship, such as P!=PSPACE, P!=PH etc. would be.

De Loera, Lee,  Malkin, and Margulies developed an algorithm for determining infeasibility of certain combinatorial problems using Hilbert's Nullstellensatz.

For example, they take the constraints of 3-coloring a graph and describe that problem as a system of polynomial equations.  They compute a set of certificate polynomials which verify that these polynomials have no solutions (using the Nullstellensatz).  To make this computation finite, they bound the degree of the certificates.  For the 3-coloring case, they were unable to find a non-3-colorable graph which required degree higher than four for the certificate.

If P $\neq$ NP, then P $\neq$ coNP and the degree of a Nullstellensatz Certificate for this problem is unbounded, as a finite bound would yield a polynomial-time algorithm.


Computing the existence of a path in a code execution graph I have a need for an algorithm which I can express as a reachability problem in a graph.

Note that I'd appreciate any advices with respect to better wording this question. Also please tell me if this question does not fit this site (I considered posting it to "Computer Science" instead).

Problem Statement

Consider an directed, connected, possibly cyclic graph $G=(V,E)$.

Consider also a finite set of "indicators" $I$, of a finite size. They are numbered $I_0 .. I_n$.

Each indicator $I_i$ can take an integer value in the range $[0..v(i)]$.

Each vertex can be labelled with one or more "assignations" of the form $I_i := v$, with $v \in [0..v(i)]$.

Exactly one vertex $V_0 \in V$ is distinguished as the "graph entry".

It is also considered that $V_0$ is labelled by $I_j := 0, \forall j \in [0..n]$ (i.e. the "value" of all indicators is $0$ at the graph entry).

Some vertices are such that all outbound edges from them are labelled by a "guard" of the form $I_k = v_p$, for a fixed value $k$ and all possible $p \in [0..m(k)]$ (i.e. there are "switches" at some vertexes where an edge is "chosen" based on the "current" value of an indicator).

We define (somewhat informally) a "valid" path in the graph as:

being finite,
respecting the topology constraints in the graph,
and being such that, if is is crossed from its beginning to its end, while collecting the "current" (i.e., latest encountered) value of indicators in the process, then the equality associated to each guard is verified.

Informally, the graph represents all possible execution flows in a piece of code, with indicator variables being set and branching decisions being taken with respect to those indicators.

Now my problem is the following: given a vertex $V_q \in V$, does a valid path (in the sense defined above) exists from $V_0$ to $V_q$?

Note that I only need an algorithm efficiently answering if such path exists; I do not need it to construct one.

What I Did so Far

Empirically, I had quite good results so far with a brute-force execution simulation strategy enumerating all possible paths (with some memoization to limit memory consumption and ensure termination in the presence of cycles). But some larger graphs are proving a challenge, since most probably my current enumeration approach is of an exponential complexity.

Mostly I'd like to express my problem in a domain where I could benefit from existing complexity proofs and (hopefully!) solvers. I tried my hands at classical graph theory problems, considered SAT and Petri Nets too, but did not see a match so far. I also tried some classic and more recent data flow algorithms at first, but they fail short since I need an exact result.

As such, your problem seems to be NP-complete. To see the membership in NP, you can first guess a path, and then check that this path ends with $V_q$ and is valid. For the hardness part, we can directly reduce from the Boolean satisfiability problem (SAT), which itself is NP-hard. The problem SAT takes as input a formula in conjunctive normal form (CNF), and outputs YES if the formula is satisfiable, and NO otherwise. Let $F = C_1 \land \ldots \land C_m$ be a CNF over variables $\{x_1,\ldots,x_n\}$, where each clause $C_i$ is a disjunction of literals. We will construct an instance graph $G_F$ of your problem with distinguished nodes $V_0$ and $V_\top$ such that there exists a valid path from $V_0$ to $V_\top$ if and only if $F$ is satisfiable. For every variable $x_i$, $1 \leq i \leq n$, $G_F$ has a node $V_{x_i}$ and a node $V_{\overline{x_i}}$, and you have one “indicator” $I_{x_i}$, with possible values being $\{\text{TRUE}, \text{FALSE}\}$. The node $V_{x_i}$ assigns $I_{x_i}$ to TRUE (i.e., you have $I_{x_i} := \text{TRUE}$), while the node $V_{\overline{x_i}}$ assigns $I_{x_i}$ to FALSE. Now, we have an (directed) edge between the node $V_0$ and the node $V_{x_1}$, as well as between $V_0$ and $V_{\overline{x_i}}$. For $1 \leq i < n$ we have the edges $(V_{x_i},V_{x_{i+1}})$, $(V_{x_i},V_{\overline{x_{i+1}}})$, $(V_{\overline{x_i}},V_{x_{i+1}})$, and $(V_{\overline{x_i}},V_{\overline{x_{i+1}}})$. For now, a path in the graph simply assigns a Boolean value to each variable, so we now need to construct the part that “checks” that this assignment satisfies $F$. For every clause $C_i$, $1 \leq i \leq m$, we construct a graph gadget $G_{C_i}$ encoding that $C_i$ is satisfied. For instance, suppose that $C_i$ is the clause $x_4 \lor \overline{x_2} \lor x_3$. Then $G_{c_i}$ has an entry node $V_{C_i,x_4}$, and nodes $V_{C_i,\overline{x_2}}$ and $V_{C_i,x_3}$. You have a “switching” edge from $V_{C_i,x_4}$ to the entry node of $G_{C_{i+1}}$ that checks that $I_{x_4} = \text{TRUE}$, and a switching edge from $V_{C_i,x_4}$ to $V_{C_i,\overline{x_2}}$ that checks that $I_{x_4} = \text{FALSE}$, and so on. You then chain these gadgets in series and plug that chain to the already partially constructed graph $G_F$ (that guesses an assignment), and construct the node $V_\top$ in the expected way (I'll leave the missing details), and voilà: there is a path from $V_0$ to $V_\top$ in $G_F$ if and only if $F$ is satisfiable.

Now, the fact that your problem is NP-hard is not necessarily the end of the world, since, as you said yourself, you can still get good results with a simple brute-force strategy. There are two things that you could investigate:

maybe your graphs have a particular structure that actually makes the problem solvable in polynomial time;
if not, you could consider using a SAT solver (such as Glucose), with an encoding similar to this question, for instance. Sometimes this gives really good results and you don't even need to optimize the thing.


Number of strings with unique substrings I have a question about binary strings with a certain property:

Given an integer $n$-bit integer $p$, that is not a perfect power of $2$. Count the number of $(p+n-2)$-bit strings that have the property that they start with $\underbrace{00...01}_{n-bit}$
and end with $\underbrace{100...0}_{n-\mathrm{bit}}$ and each $n$-bit substring occurs exactly once.

E.g., for $n=3$, $p=7$ there are $001 01 100$ and $001 10 100$, which are the only ones for the pair $(n,p)$.

Further examples are: $n=5$ and $p=29$: $00001 0001101001111011100101 10000$

and $n=5$ and $p=19$: $00001 101011110010 10000$.

I searched for related work and found papers about incompressible strings and Kolmogorov complexity. However, they did not helped me out.

Does there exists a combinatorial approach to count the number of solutions? Or is there an heuristic argument that gives a good approximation?

You mean that each nonzero n-bit substring occurs once, and the all-zero n-bit substring occurs no times, right? Essentially, what you are looking for is a De Bruijn sequence.

The number of de Bruijn sequences should be in OEIS somewhere but I'm having trouble finding it. My guess is that it grows doubly exponentially, since it is the number of Hamiltonian cycles in an exponential sized graph (the de Bruijn graph) and graphs tend to have exponentially many such cycles when they have any.


Is integer factorization an NP-complete problem? Possible Duplicate:
  What are the consequences of factoring being NP-complete?

What notable reference works have covered this?

No, its not known to be NP-complete, and it would be very surprising if it were. This is because its decision version is known to be in $\text{NP} \cap \text{co-NP}$. (Decision version: Does $n$ have a prime factor $\lt k$?)

It is in NP, because a factor $p \lt k$ such that $p \mid n$ serves as a witness of a yes instance.

It is in co-NP because a prime factorization of $n$ with no factors $\lt k$ serves as a witness of a no instance. Prime factorizations are unique, and can be verified in polynomial time because testing for primality is in P.


Do you use any article organizers? There is an increasing number of scientific articles which I look through and somehow I feel a lack of a tool to keep track of the already read ones and my summary notes on it. Or another usage scenario would be to search by an author and see which articles of the given author I have already read.

The question is: Do you use or know of any freeware tools for organizing articles?

I used to store them in a SVN repository, and then I found out about Mendeley, quite satisfying so far except for a few bugs. Different features are available depending on whether or not you want to pay some fee, but the free version is enough for many people -- it seems it would be for you.


How to make the Lambda Calculus strong normalizing without a type system? Is there any system similar to the lambda calculus that is strong normalizing, without the need to add a type system on top of it?

I can think of a few possible answers coming from linear logic.

The simplest one is the affine lambda-calculus: consider only lambda-terms in which every variable appears at most once.  This condition is preserved by reduction and it is immediate to see that the size of affine terms strictly decreases with each reduction step.  Therefore, the untyped affine lambda-calculus is strongly normalizing.

More interesting examples (in terms of expressiveness) are given by the so-called "light" lambda-calculi, arising from the subsystems of linear logic introduced by Girard in "Light Linear Logic" (Information and Computation 143, 1998), as well as Lafont's "Soft Linear Logic" (Theoretical Computer Science 318, 2004).  There are several such calculi in the literature, perhaps a good reference is Terui's "Light affine lambda calculus and polynomial time strong normalization" (Archive for Mathematical Logic 46, 2007).  In that paper, Terui defines a lambda-calculus derived from light affine logic and proves a strong normalization result for it.  Even though types are mentioned in the paper, they are not used in the normalization proof.  They are useful for a neat formulation of the main property of the light affine lambda-calculus, namely that the terms of a certain type represent exactly the Polytime functions.  Similar results are known for elementary computation, using other "light" lambda-calculi (Terui's paper contains further references).

As a side note, it is interesting to observe that, in proof-theoretic terms, the affine lambda-calculus corresponds to intuitionistic logic without the contraction rule.  Grishin observed (before linear logic was introduced) that, in the absence of contraction, naive set theory (i.e., with unrestricted comprehension) is consistent (i.e., Russel's paradox does not give a contradiction).  The reason is that cut-elimination for naive set-theory without contraction may be proved by a straightforward size-decreasing argument (as the one I gave above) which does not rely on the complexity of formulas.  Via the Curry-Howard correspondence, this is exactly the normalization of the untyped affine lambda-calculus.  It is by translating Russel's paradox in linear logic and by "tweaking" the exponential modalities so that no contradiction could be derived that Girard came up with light linear logic.  As I mentioned above, in computational terms light linear logic gives a characterization of the polynomial-time computable functions.  In proof-theoretic terms, a consistent naive set theory may be defined in light linear logic such that the provably total functions are exactly the polynomial-time computable functions (there is another paper by Terui on this, "Light affine set theory: A naive set theory of polynomial time",
Studia Logica 77, 2004).


Quantum complexity of TQBF with an untrusted oracle This is a follow up to Quantum complexity of TQBF, trying to model the situation where we have good heuristics.
Let $L$ be the language of true, fully alternating totally quantified boolean formulas with some number $n$ of variables and circuit size $s = \operatorname{poly}(n)$.  The classical complexity of $L$ is $\tilde{O}\left(2^{0.793n}\right)$, and the quantum complexity is $\tilde{O}\left(2^{n/2}\right)$.
Now we assume we have access to an untrusted oracle for all subnodes of a particular formula $F \in L$.  That is, if the oracle is honest it will give the correct value of $F$ where any prefix of quantified variables is replaced by a chosen assignment of $\{0,1\}$ values.  We seek an algorithm which is correct for all oracles, untrustworthy or not, and ask for its worst-case complexity conditional on the oracle being honest.
In the classical case, I believe alpha-beta pruning is the optimal algorithm, and achieves complexity roughly $\tilde{O}\left(2^{n/2}\right)$.  (I'm not certain of this, so confirmation would be appreciated.)  Note that this matches the quantum complexity if we don't have an oracle.
Question: What is the quantum complexity of $L$ given an untrusted oracle, where complexity is measured conditional on the oracle being honest?
Motivation: The goal here is to model the situation where we have some particular TQBF, such as arising from chess or go, where there is enough structure that efficient, accurate heuristics are available but not enough structure to turn those heuristics into a rigorous proof of the game value.  In practice the heuristics would not be perfect (as in the honest oracle case), so this question is trying to get at a lower bound for the practical situation.

This question is more complicated to state than its predecessor Quantum complexity of TBQF, but in hindsight it is also way easier to answer.
Theorem: The complexity is $\tilde{O}\left(2^{n/4}\right)$, using a single call to Grover's algorithm to check if there is a path falsifying the oracle.  Moreover, this is optimal in the black box case.
Consider a TBQF query $F = \exists x_0 \forall y_0 \exists x_1 \forall y_1 \cdots f(x, y)$.  Assume w.l.o.g. that the oracle says $F$ is true.  The oracle is telling the truth about $F$ if, when we use the oracle to choose how to play each $x_k$ move, there is no choice of $y$'s that falsifies the oracle.  But this is just a single call to Grover to search through the space of such $y$'s.  There are $2^{n/2}$ $y$'s, so the complexity is $\tilde{O}\left(\sqrt{2^{n/2}}\right) = \tilde{O}\left(2^{n/4}\right)$.
For the black box lower bound, given a black box boolean function $f(y)$ defined on $n/2$ bits $y$, we can construct a degenerate TBQF formula $F = \exists x_0 \forall y_0 \exists x_1 \forall y_1 \cdots f(y)$ which simply ignores $x$.
(Thanks to Paul Christiano for discussion.)


Circuit lower bounds over arbitrary sets of gates In the 1980s, Razborov famously showed that there are explicit monotone Boolean functions (such as the CLIQUE function) that require exponentially many AND and OR gates to compute.  However, the basis {AND,OR} over the Boolean domain {0,1} is just one example of an interesting gate set that falls short of being universal.  This leads to my question:

Is there any other set of gates, interestingly different from the monotone gates, for which exponential lower bounds on circuit size are known (with no depth or other restrictions on the circuit)?  If not, is there any other set of gates that's a plausible candidate for such lower bounds---bounds that wouldn't necessarily require breaking through the Natural Proofs barrier, as Razborov's monotone-circuits result didn't?

If such a gate set exists, then certainly it will be over a k-ary alphabet for k≥3.  The reason is that, over a binary alphabet, the

(1) monotone gates ({AND, OR}),

(2) linear gates ({NOT, XOR}), and

(3) universal gates ({AND, OR, NOT})

basically exhaust the interesting possibilities, as follows from Post's classification theorem.  (Note that I assume that constants---0 and 1 in the binary case---are always available for free.)  With the linear gates, every Boolean function f:{0,1}n→{0,1} that's computable at all is computable by a linear-size circuit; with a universal set, of course we're up against Natural Proofs and the other terrifying barriers.

On the other hand, if we consider gate sets over a 3- or 4-symbol alphabet (for example), then a wider set of possibilities opens up---and at least to my knowledge, those possibilities have never been fully mapped out from the standpoint of complexity theory (please correct me if I'm wrong).  I know that the possible gate sets are studied extensively under the name of "clones" in universal algebra; I wish I were more conversant with that literature so that I knew what if anything the results from that area mean for circuit complexity.

In any case, it doesn't seem out of the question that there are other dramatic circuit lower bounds ripe for the proving, if we simply expand the class of gate sets over finite alphabets that we're willing to consider.  If I'm wrong, please tell me why!

(Moved from comments as Suresh suggested.  Note some errors in the comment are fixed here.)

Thanks to Scott for a great question.

Scott seems to suggest that the reason for the difficulty of lower bounds may be the restricted language of operations in the Boolean case.  Shannon's counting argument that shows most circuits must be large relies on the gap between countable expressive power and uncountably many circuits.  This gap seems to go away when the alphabet has at least 3 symbols.

For alphabet size 2 (the Boolean case), the lattice of clones is countably infinite, and is called Post's lattice.

Post's lattice also makes clear why there are only a few interesting bases of operations for the Boolean case.

For alphabet size 3 or greater the lattice of clones is uncountable.  Further, the lattice does not satisfy any nontrivial lattice identity, so it seems impossible to provide a complete description of the lattice.  For alphabet size 4 or greater the lattice of clones actually contains every finite lattice as a sublattice.  So there are infinitely many possibly interesting bases of operations to consider when the alphabet has 3 or more symbols.

Bulatov, Andrei A.,
Conditions satisfied by clone lattices,
Algebra Universalis
46
237–241,
2001.
doi: 10.1007/PL00000340

Scott asked further: does the lattice of clones remain uncountable if we assume constants are available for free?

The answer is that it does, see for instance

Gradimir Vojvodić,
Jovanka Pantović, and
Ratko Tošić,
The number of clones containing an unary function,
NSJOM
27
83–87,
1997.
(PDF)
J. Pantović, R. Tošić, and G. Vojvodić,
The cardinality of functionally complete algebras on a three element set,
Algebra Universalis
38
136–140,
1997.
doi: 10.1007/s000120050042

although apparently this was published earlier:

Ágoston, I., Demetrovics, J., and Hannák, L.
On the number of clones containing all constants,
Coll. Math. Soc. János Bolyai
43
21–25,
1983.

A nice specific statement is from:

A. Bulatov, A. Krokhin, K. Safin, and E. Sukhanov,
On the structure of clone lattices,
In: "General Algebra and Discrete Mathematics",
editors: K. Denecke and O. Lueders,
27–34.
Heldermann Verlag, Berlin,
1995.
(PS)

  Corollary 3 (attributed to Ágoston et al. as above): Let $k \ge 3$.  Then the number of clones in $\mathcal{L}_k$ containing all constants is $2^{\aleph_0}$.

To wrap up, I am not aware of any work on using non-Boolean clones for circuit lower bounds.  This seems worth investigating in more depth.  Given the relatively little that is known about the lattice of clones, there may be interesting bases of operations waiting to be discovered.

More links between clone theory and computer science would probably also be of great interest to mathematicians working in universal algebra.  A previous example of this kind of interaction came about when Peter Jeavons showed that algebras could be associated with constraint languages, in a way that allows tractability results to be translated into properties of the algebra.  Andrei Bulatov used this to prove the dichotomy for CSPs with domain size 3.  Going the other way, there has been a revival in interest in tame congruence theory as a result of the computer science application.  I wonder what would follow from a link between clone theory and non-Boolean circuit complexity.


Fast algorithm for weighted bipartite matching problem I have a set of $n$ agents and a set of $n$ tasks, and I need to assign each agent to exactly one task such that a cost is minimised. Some agents are incompatible with some tasks.

I have an implementation of the Hungarian Algorithm which takes about a minute to solve for my $640 \times 640$ matrix. For forbidden assignments, I set the cost to $\infty$. (There always exists a feasible solution in my problem).

I've also set it up as a binary program in CPLEX, which takes about 9 seconds to solve for the same problem. The BIP model excludes forbidden assignments outright by omitting those variables.

I haven't yet investigated setting it up as a networking model in CPLEX, but that will likely be my next step. There is, however, a performance cost with communicating with CPLEX, so I'm sure a dedicated algorithm should get better performance.

This bipartite matching problem is a kernel within another iterative search algorithm, so it must run as fast as possible.

Are there any algorithms that I can implement that will outperform the Hungarian Algorithm in this case? Or do you have any other suggestions on how I can improve the performance of this kernel?

You might try one of the auction-based algorithms for bipartite matchings. (See e.g. lecture notes describing a simple variant here: https://staff.fnwi.uva.nl/n.s.walton/Notes/Bertsekas_Auction.pdf but more optimizations are possible).

These algorithms do not necessarily have the best worst-case running time, but require only very simple operations, and so are often efficient in practice, and are amenable to parallelization. (And they can be used as a basis for recovering the best known worst case running times, see: http://agtb.wordpress.com/2009/07/13/auction-algorithm-for-bipartite-matching/


Field extensions in CS A field is a set with two binary operations called addition and multiplication satisfying various axioms. Wikipedia article: Field_(mathematics)

A field extension is when you add a new element and then have to add all arithmetic combinations of that new element with the existing elements, e.g. adding i to the real numbers to get the complex numbers. If F is a subfield of K then K is called an extension field of F.

Technically you aren't adding new elements, but defining a new field which has a subset isomorphic to the orginal field, e.g. the complex numbers x+0i are identified with the real numbers x.

Wikipedia: Field_extension

Finite field extensions are useful in the construction of BCH codes which are codes over the finite fields of order q=pn which are extensions of the fields of order p where p is prime. These finite fields known as Galois fields GF(p) are extended to GF(q) by adding roots of polynomials that are irreducible (non-factorable) over GF(p).

Wikipedia: BCH_code

Where else in CS does the concept of extension fields arise ? A fundamental appearance in some subject would be more interesting than an occurence in some proof, but if it is used frequently in a common proof stategy then such a proof strategy would also be an interesting answer here.

I used field extensions (and Tarksi's transfer principle) to prove lower bounds for linear degeneracy problems.  Using a field extension of the reals with formal infinitesimals simplified the construction of adversarial inputs.  (But see also Ailon and Chazelle's followup paper, which generalized my result without using field extensions.)

More generally, in the algebraic decision tree model (with real coefficients), the complexity of any problem with real inputs is identical to the complexity of the same problem where the inputs are drawn from any real closed field that contains the reals.


Password checking algorithm Usually to check password validity we used to create over given password it hash value and compare it with stored one. So password protection relies on strength of hashing function.

Could it be used another approach?

Let's say we have encryption algorithm (doesn't matter which one).
Let assume we have some array of predefined chars (for instance just digits)
Then generate random sequence of chars consisting predefined array (for instance just random sequence of digits)
Encrypt sequence with our algorithm with given password and store it somewhere in safe place (let's call it as saved value)
EDIT Also presumed that channel between client and server provides confidentiality and integrity

Now time to check password validity

Trying to decrypt saved value with probe password
If decryption successfull (meaning mathematically correct) check decrypted value to presence of predefined chars array. For instance if value consists only digits - we assume that password is correct. If decrypted value contains extra chars (except digits) - we would assume that password is incorrect.

Now question: what do you think about crypto-strength of this method?

The first problem you face is that a password cannot be used as an encryption key. For instance, let the password be $%^gHk23. How do you interpret this as an AES-256 key?

The second problem is that the client has to send the password in clear, and then the server tries to make a key from it, and decrypt saved values.

Thirdly, the scheme is fixed. No salting whatsoever is incorporated in it, and thus it is vulnerable to a variety of attack, most notably the dictionary attack.

The hashing scheme you described at the beginning of your post is very old. Today, an extremely secure password-based identification scheme, named SRP, is gaining momentum. (See also the demo.)


Finding cliques in a big graph I would like to find (all) cliques in a given graph with 8,568 vertices and 12,726,708 edges. The vertex with the lowes degree has 2000, the vertext with the highest degree has 4007.
The cliques should have exactly 17 vertices.

The algorithm should be fast, because of the size of the graph.

I had the following idea:

Delete all vertices with a degree of 16 or less.
Iterate over every vertex

try to add another vertex:

If the clique has exactly 17 vertices: Add it to a list
Else: Keep trying to add vertices

If no more vertices can be added: go back to the latest point where you had the choice to add some vertices and add one of those that could not be added before.

I didn't implement this algorithm, because I think it will be quite slow. Do you know better ones?

These kind of problems are in general very hard with the decission version of a problem often being NP-hard, so I doubt you will find an algorithm fast enough, unless your graph has some peculiarity which allows you to discard a large number of vertices.

Since you restrict it to cliques of exactly 17 vertices then trivially there is an $O(n^{17})$ algorithm, but I'd hardly call this fast. To do this simply step through all subsets of 17 vertices in lexicographical order and check whether they form a clique. Note that this is exactly $\binom{n}{17}$ subsets. Note however, that for an input graph which is itself a clique, there are $\binom{n}{17}$ cliques of comprised of 17 vertices, and hence this trivial algorithm is optimal if we consider only worst case scaling, since simply reading a list of all such cliques takes $\binom{n}{17}$ steps. In order to do better than this, you need a graph with some structure.

So for your specific case of $n=8568$ you potentially have $2 \times 10^{52}$ cliques of 17 vertices. Further since you have more than 12 million edges, this is enough for a maximally connected graph of 5000 vertices, which would have approximately $2 \times 10^{48}$ unique subsets 17 vertices which form cliques, so for the parameters you have listed it is entirely possible that you simply cannot enumerate cliques fast enough to give you a reasonable run time.


Agnostic Learning of K-Juntas over "small" distribution I have two questions related to agnostic learning, one specific and one more general, specifically when the distribution relative to which the learner must operate is given explicitly as part of the input.

The specific question is closely related to proper agnostic learning of k-Juntas, though the connection is fuzzy. Consider the following optimization problem.

Problem statement: You are given a set $S$ of $m$ binary strings in $\{0,1\}^n$, a boolean function $f: \{0,1\}^n \to \{0,1\}$, and a parameter $k$. Find a k-Junta $g:\{0,1\}^n \to \{0,1\}$ which agrees with $f$ on as many elements of $S$ as possible.

Question: What is the best (multiplicative or additive) approximation algorithm for this problem if you are allowed to query f on points in S, and are allowed to run in time polynomial in m, n, and k? What about if you are allowed to run in time polynomial in m,n and $2^k$?

I sense that the answer to this question may be known or follow directly from existing techniques. A literature search reveals several works on agnostic learning of k-Juntas relative to the uniform distribution, where additive approximation schemes are possible (see, e.g. here). Observe that the problem above differs from the settings considered in much of the literature in that the set of points S in the hypercube that we "care" about classifying correctly is explicitly given in the input. In essense, this can be thought of as learning with respect to a uniform distribution on a subset S of the hypercube, where the runtime of the learner may depend on the size of S and the learner is allowed to query $f$ on $S$. This interpretation raises a more general reference-request question.

Question: Is there literature on agnostic learning relative to "succinctly given" distributions? Anyone know of example papers? What are the keywords one should search for? Also, to what extent do upper/lower bound results on agnostic learning w.r.t the uniform distribution imply something for succinct-distribution variants of the same problem?

Uniform convergence bounds should imply that agnostic learning with respect to a succinct distribution specified by a finite set S is no easier than learning with respect to the uniform distribution, at least for large enough $S$. Specifically, for any class of functions $C$ with VC-dimension $d$, the canonical algorithm which takes a randomly sampled collection of $m$ points for $m = O(d/\epsilon^2)$ and finds the function $f \in C$ which minimizes error with respect to the sample, will be within an additive $\epsilon$ of the minimum error function over the entire target distribution. So if you have an algorithm for agnostically learning with respect to an explicitly represented set of points $S$, you can learn over the uniform distribution by just taking a sufficiently large sample of points $S$ and feeding $S$ to your algorithm for concise distributions. In fact, this holds for any distribution, not just the uniform distribution.

Now there are ${d \choose k}\cdot 2^{2^{k}}$ size $k$ juntas, and so they have VC-dimension at most $d \leq 2^k + k\log d \approx 2^k$.  So for large enough $S$ (at least, larger than $2^k$), lower bounds for agnostically learning w.r.t. the uniform distribution (or any other distribution) should apply to the problem of learning w.r.t. a concise distribution.


How does inheritance differ from subtyping? In programming language perspective, what is mean by subtyping? I heard that "Inheritance is not Subtyping". Then what are the differences between inheritance and subtyping?

[I haven't thought deeply about the issues of object-oriented type systems, but I will say what I know to get the discussion going.]

We say that $A$ is a subtype of $B$ if all $A$-typed values can be used in every context where $B$-typed values are expected.  Or, to put another way, $A$-typed values can "masquerade" as $B$-typed values.

If such masquerading poses no issues with type checking, i.e., plugging in $A$-typed values where $B$-typed values are needed continues to type check, we call it "structural subtyping".  If it cause no issues with behaviour, i.e., such plugging does not alter the behaviour expected, then we call it "behavioural subtyping".  (The "behaviour expected" will have to be formalised separately and many notions of behaviour are possible.)

Structural subtyping does not ensure behavioural subtyping because the structure of a type might match for accidental reasons.  However, defining the behaviour expected is not easy.  So, many programming languages use an intermediate point, where the user has to declare which type is a subtype of which.  This is referred to as "nominal subtyping".  See the question on Implicit vs explicit subtyping for a discussion of this issue.  The idea is that the programmer has to ensure behavioural subtyping for all declared subtypes using his own ingenuity.  The language cannot offer any help.  However, all declared subtypes must be at least structural subtypes.  Otherwise, the program would fail to type check.  The language can help ensure this.  (Some programming languages don't have good enough type systems to ensure this at compile-time.  If so, the type failure would be detected at run-time, or perhaps wrong results might be produced.  Such type holes are obviously undesirable.)

When one defines subclasses in object oriented programs, one typically adds publicly visible fields (or methods).  In most programming languages, such subclasses are regarded as nominal subtypes.  The question is whether they are also structural subtypes.  If they are not, i.e., the programming language allows one to declare nominal subtypes that are not structural subtypes, then there would be type holes in the programming language.

In simple cases, adding fields works fine.  The type of the superclass expects fewer fields than the type of the subclass.  So, if you plug in an instance of a subclass where an instance of the sueprclass is expected, the program will just ignore the additional fields provided and nothing goes wrong.

However, if the superclass or subclass has methods that take arguments of the same type as itself, or return results of the same type as itself, then problems arise.  Then the interface type of the subclass is not a structural subtype of that of the superclass.  Widely used type-safe programming languages such as Java do not allow such subclasses.  So, they restrict the language to obtain type safety.  The programming language Eiffel is said to have sacrificed type-safety to obtain flexibility instead.  If one designs a strong type system that retains flexibility, one must give up the principle that subclasses give rise to subtypes.  Hence the title of the paper "Inheritance is not subtyping".  The authors propose a different notion of higher-order subtyping which works instead.  Kim Bruce also has a closely related proposal called "matching" that achieves the same effect.  See this presentation.  Also helpful is a position paper of Andrew Black.

The semantics community is probably at fault for largely ignoring the problem.  We have traditionally regarded it as a practical type-system engineering issue that is of little theoretical interest.  If that is not the case and there is indeed some semantics work in the area, I hope the other people will mention them.


Is bounded-error probabilistic computation sensitive to transition types? In the unbounded-error case, it is known that both realtime quantum and probabilistic finite automata can recognize some uncomputable languages if they are allowed to use arbitrary real numbers in their transitions (Rabin, 1963; Yakaryilmaz and Say, 2011).

In the bounded-error case, we have a similar result for poly-time quantum Turing machines as well, i.e. the cardinality of $ \mathsf{BQP}_{\mathbb{C}}  $ is uncountable (Adleman et. al., 1997).

My question is whether any bounded-error probabilistic space (time) class defined with unrestricted real numbers contains an uncomputable (or a recursive enumerable) language.

It is also known that (Watrous, 2003) if we restrict ourselves to algebraic numbers ($\mathbb{A}$), for any space-constructable function $ s(n) \in \Omega(\log n) $,
\begin{equation}
\mathsf{PrQSPACE}_{\mathbb{A}}(s) \subseteq \mathsf{DSPACE}(s^2),
\end{equation}
where $\mathsf{PrQSPACE}$ stand for unbounded-error quantum space.

Any partial answer (for the case of bounded-error probabilistic computation using non-algebraic transitions) violating this upper bound would also be nice.

If you have a coin which has an uncomputable probability of landing heads, then you can estimate with bounded error the first $k$ bits of this probability using $O(4^{k})$ coin flips.

This lets you construct a machine with bounded error that computes an uncomputable function. The uncomputable function is the $k$th bit of the probability. The computation is estimating the probability of landing heads by flipping the coin $4^k$ times. Considerations of running time don't matter when you're worrying about whether a function is computable or uncomputable, so it doesn't matter that it takes time exponential in $k$ to estimate the $k$th bit of the function; it's still an uncomputable function.


Max-cut with negative weight edges Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find:
$$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$
If the weight function is non-negative (i.e. $w(e) \geq 0$ for all $e \in E$), then there are many extremely simple 2-approximations for max-cut. For example, we can:

Pick a random subset of vertices $S$.
Pick an ordering on the vertices, and greedily place each vertex $v$ in $S$ or $\bar{S}$ to maximize the edges cut so far
Make local improvements: If there is any vertex in $S$ that can be moved to $\bar{S}$ to increase the cut (or vice versa), make the move.

The standard analysis of all of these algorithms actually shows that the resulting cut is at least as large as $\frac{1}{2}\sum_{e \in E}w(e)$, which is an upper bound on $1/2$ the weight of the max-cut if $w$ is non-negative -- but if some edges are allowed to have negative weight, is not!

For example, algorithm 1 (pick a random subset of vertices) can clearly fail on graphs with negative edge weights.

My question is:

  Is there a simple combinatorial algorithm that gets an O(1) approximation to the max-cut problem on graphs that can have negative edge weights?

To avoid the possibly sticky issue of the max-cut taking value $0$, I will allow that $\sum_{e \in E}w(e) > 0$, and/or be satisfied with algorithms that result in small additive error in addition to a multiplicative factor approximation.

Here was my first attempt at an argument. It was wrong, but I fixed it after the "EDIT:"

If you could efficiently approximately solve the max-cut problem with negative edge weights, couldn't you use that to solve the max-cut problem with positive edge weights?  Start with a max-cut problem you want to solve whose optimal solution is $b$. Now, put a large negative weight edge (with weight $-a$) between $u$ and $v$. The optimum solution of the new problem is $b-a$, so our hypothetical approximation algorithm will get you a solution with maximum cut whose value is at most $(b-a)/2$ worse than optimal. On the original graph, the maximum cut is still at most $(b-a)/2$ worse than optimal. If you choose $a$ close to $b$, this violates the inapproximability result that if P$\neq$NP, you cannot approximate max-cut to better than a $16/17$ factor.

EDIT:

The above algorithm doesn't work because you can't guarantee that $u$ and $v$ are on opposite sides of the cut in the new graph, even if they were originally. I can fix this as follows, though.

Let's assume that we have an approximation algorithm which will give us a cut within a factor of 2 of OPT as long as the sum of all the edge weights are positive.

As above, start with a graph $G$ with all non-negative weights on edges. We'll find a modified graph $G^* $ with some negative weights such that if we can approximate the max cut of $G^* $ within a factor of 2, we can approximate the max cut of $G$ very well.

Choose two vertices $u$ and $v$, and hope that they're on opposite sides of the max cut. (You can repeat this for all possible $v$ to ensure that one try works.) Now, put a large negative weight $-d$ on all edges $(u,x)$ and $(v,x)$ for $x \neq u,v$, and a large positive weight $a$ on edge $(u,v)$. Assume that the optimal cut has weight $OPT$.

A cut with value $c$ in $G$, where vertices $u$ and $v$ are on the same side of the cut, now has value at $c - 2dm$ where $m$ is the number of vertices on the other side of the cut. A cut with $(u,v)$ on opposite sides with original value $c$ now has value $c + a - (n-2)d$. Thus, if we choose $d$ large enough, we can force all cuts with $u$ and $v$ on the same side to have negative value, so if there is any cut with positive value, then the optimal cut in $G^* $ will have $u$ and $v$ on opposite sides. Note that we are adding a fixed weight $(a - (n-2)d)$ to any cut with $u$ and $v$ on opposite sides.

Let $f=(a - (n-2)d)$. Choose $a$ so that $f \approx - 0.98 OPT$ (we'll justify this later). A cut with weight $c$ in $G$ having $u$ and $v$ on opposite sides now becomes a cut with weight $c - 0.98 OPT$. This means the optimal cut in $G^* $ has weight $0.02 OPT$. Our new algorithm finds a cut in $G^* $ with weight at least $0.01 OPT$. This translates into a cut in the original graph $G$ with weight at least $0.99OPT$ (since all cuts in $G^* $ with positive weight separate $u$ and $v$), which is better than the inapproximability result.

There is no problem with choosing $d$ large enough to make any cut with $u$ and $v$ on the same side negative, since we can choose $d$ as large as we want. But how did we choose $a$ so that $f \approx -.99OPT$ when we didn't know $OPT$? We can approximate $OPT$ really well ... if we let $T$ be the sum of the edge weights in $G$, we know $\frac{1}{2}T \leq OPT \leq T$. So we have a fairly narrow range of values for $f$, and we can iterate over $f$ taking all values between $-.49T$ and $-.99T$ at intervals of $0.005T$. For one of these intervals, we are guaranteed that $f \approx -0.98 OPT$, and so one of these iterations is guaranteed to return a good cut.

Finally, we need to check that the new graph has edge weights whose sum is positive. We started with a graph whose edge weights had sum $T$, and added $f$ to the sum of the edge weights. Since $-.99T \leq f \leq -.49T$, we're O.K.


Optimal measurement for MUBs Let $\mathcal{B} = \{B_1, \dots, B_k\}$ be a set of Mutually Unbiased Bases (MUB) in $\mathbb{C}^n$, i.e. each $B_i$ is an orthonormal basis and for $v \in B_i, w \in B_j, i \neq j $ we have $|\langle v\vert w\rangle| = \frac{1}{\sqrt{n}}$. We are interested in discriminating between arbitrary vectors from $\mathcal{B}$. Is the optimal (worst case or average with uniform prior) POVM measurement identified explicitly anywhere in the literature (e.g. using Holevo criterion), at least for some specific constructions of MUBs?

It seems that this problem in full-generality is though. These two references might be helpful to you.

Here [1] the pure-state discrimination of MUBs is studied in a cryptographic set-up. The optimality of different  measurement schemes is rigorously discussed. It also includes a good bunch of useful references about distinguishability of pure quantum states.
For particular choices of pure-state ensembles the Pretty Good Measurement  is proven to be optimal in this task. This [2] is a nice exposition on this topic, although not focused on MUBs.

If you are interested in more restricted scenarios that the ones considered above, regard that there are some factors that influence the complexity of this problem. The following two are considered in several references:

The choice of quantum states to distinguish (in this case the choice of MUBs). This issue is important [3] to find efficient implementations of optimal POVMs.
The particular probabilities $p_{i,j}$ of receiving the $i$th state of the $j$th basis $B_k$ as an input [1][2] (in your notation).

Also, in cryptographic applications the next two seem to be relevant [1]:

If you are using this states to encode some information the particular functions used to encode and decode this information.
Other: ability to store qubits between measurements, some given knowledge about the bases used.

Hope it helps.


Communication complexity for deciding associativity Let $S=${$0,...,n-1$} and $\circ : S \times S \rightarrow S$. I want to compute the communication complexity of deciding whether $\circ$ is associative.

The model is the following. $\circ$ is given as a matrix $M$. Alice (resp. Bob) is given half the entries of the matrix at random (same for Bob). I want to compute the worst case number of entries that Alice must send to Bob so that Bob can decide on the associativity of $\circ$.

In fact, it is simple to reduce the problem of deciding the equality of two bit strings of size $\Omega(n)$ to the problem of deciding the associativity of $\circ$ over $S$. This means that the communication complexity of the associativity is lower bounded by $\Omega(n)$. However, I suspect that this LB is not tight. Being defined on an input of size $n^{2}$, I would have prefer to find a communication complexity of $\Omega(n^{2})$.

Is there a known result on this problem ? Is the answer is $n^{2}$ for an obvious reason I am not seeing ?

There are $n^{n^2}$ binary operations on $S$. The question is how many of them are associative. Kleitman, Rothschild and Spencer give an asymptotic counting formula for this problem in their paper The number of semigroups of order $n$. It has a relatively simple form in what they call the "non-rare instances" where the peak of $f(t)$ dominates so the other terms can be neglected without affecting the asymptotics. You should be able to give a lower bound for your question by cranking through the math with this formula.


Is a PhD in TCS the best way towards achieving a career in industrial research? My idea of a dream career is a career in industrial research, where one gets to tackle problems which are challenging, and also have a practical usage. To that end, is pursuing a PhD in TCS (I'm interested in topics such as distributed/parallel algorithms, online algorithms) a bad idea ? I've the notion that most, if not all, PhD applicants in TCS are expected to pursue a career in academia - is that a valid precept ?

I've noticed distinguished academics who are regular users of this site - I'm especially looking for guidance from any such person, as I don't want to apply for a doctoral program with the wrong goals in mind. To give a brief description of my profile, I've graduated with MTech in CS (from a fairly reputable institute in my country) about 2 years back, and been working in a MNC ever since on kernel level device drivers.

This question may not be the most ideal question for this site, but I couldn't find a better place to ask it. Requesting the moderators not to close this outright, as I'm really in need of some advice here.

The comments are all pretty spot on (and maybe they should be answers). To add to them:

In industrial research of the Google/Yahoo!/AT&T/MSR/IBM variety, there are definitely specific area interests, but there's also interest in people with broad interests and strong foundations. A Ph.D in TCS can provide such a broad set of interests and a strong foundation if you choose the right topics.

So for example you could do a Ph.D in computational geometry, focusing on combinatorial problems in incidence geometry, or you could focus on approximate high dimensional algorithms. It's possible that the second topic might allow you to "sell" yourself more effectively as a data analyst, especially if you can point to some awareness of the applications of your work (some papers etc).

So even if you were to do a Ph.D in TCS as a path towards industrial research, the success of this plan really depends on the kinds of topics you choose. In the long term, I think it'll make you very flexible and able to work on a variety of things, but you'll have to seek out that breadth during your education.