Is Almost-2-SAT NP-hard? Is a CNF SAT problem NP hard when the total number (but not the width) of the 3-or-more-term clauses is bounded above by a constant?  What about specifically when there's only one such clause?

It is worth noting that the problem becomes NP-hard when the restriction is relaxed slightly.

With a fixed number of clauses that are also of bounded size, the average number of literals in a clause is as close to 2 as one wants, by considering an instance with enough variables.  As you point out, there is then a simple upper bound which is polynomial if the clause size is bounded.

In contrast, if the average number of literals per clause is at least $2 + \epsilon$ for some fixed (but arbitrarily small) $\epsilon > 0$, then the problem is NP-hard.

This can be shown by reducing 3SAT to this problem, by introducing new clauses with 2 literals that are trivially satisfiable.  Suppose there are $m$ clauses in the 3SAT instance; to reduce the average clause size to $(2+\epsilon)$, it is enough to add $m(1 - \epsilon)/\epsilon$ new clauses with two literals.  Since $\epsilon$ is fixed and positive, the new instance is of polynomial size.

This reduction also shows that even the version where the "large" clauses are restricted to 3 literals is NP-hard.

The remaining case is when the few large clauses are not of bounded size; each large clause seems to make the problem harder.  See the SODA 2010 paper by Pǎtraşcu and Williams for the case of two clauses: they argue that if this can be done in sub-quadratic time then we would have better algorithms for SAT.  There might be an extension of their argument to more clauses, which would provide evidence that your upper bound cannot be improved (modulo some form of the exponential time hypothesis).


(N)DFA with same initial/accepting state(s) What is known about the class of languages recognized by finite automata having the same initial and accepting state?  This is a proper subset of the regular languages (since every such language contains the empty string), but how weak is it?  Is there a simple algebraic characterization?

Ditto for languages recognized by non-deterministic automata having the same set of initial and accepting states.

Finite automata in which the initial state is also the unique accepting state have the form $r^∗$, where $r$ is some regular expression. However, as J.-E. Pin points out below, the converse is not true: there are languages of the form $r^*$ which are not accepted by a DFA with a unique accepting state.

Intuitively, given a sequence of states $q_0, \ldots, q_n$ such that $q_0 = q_n$ either $n = 0$ or the underlying state diagram must have a cycle involving $q_0$. The latter case is captured algebraically by the Kleene star.


Explain 0-extension algorithm I'm trying to implement an approximation algorithm for the 0-extension problem

I found the following paper:

  Approximation Algorithms for the
  0-extension problem by Gruia
  Calinescu, Howard Karloff and Yuval
  rabani.

On page 5 they explain the algorithm
but I don't understand it (I'm not English and some words are difficult to understand)

so can someone explain the algorithm from an implementation standpoint?

As input data (numbers are for illustration), I have a graph with 64 vertexes and a number of connections (no info about the max degree)
every connection has a "distance" defined
I want to colour the vertices with 3 colours
some vertices already have a colour

How do I do this? I'm pretty advanced software designer so you can use high-level pseudo-code

EDIT

  $\delta(u,v) = d(f(u),f(v))$

What do they mean with $f(\cdot)$?
Aren't $d$ and $\delta$ the "distance" functions?

  minimize $\sum_{uv \in E} c(u,v) \delta(u,v)$

Where is the $c(\cdot)$ coming from?
Cost function?

Rounding procedure:

  set $f(t) = t$ for all terminals

Are the terminals the colors or the vertices or vertices with a color assigned?

  such that $\delta(u,\sigma_j) \leq \alpha A_u$

What is $A_u$?
What is $\sigma_j$?

edit2

ok so i need to compose the equasions and solve them with a LP solver

lets take this example:
http://i77.photobucket.com/albums/j74/bertyhell/Diagram1.png
I want to know what colour to give B and C
in this case the best solution is to give C the red colour and B a green colour (B and A are furthest from each other)

2 terminals already have a color
and every edge as a "distance"
my cost function is:

int c(u,v){
    if(u.color == undef || v.color == undef){
        return undef //unknown cost
    }else if(u.color == v.color){
        return 90 - "distance"
    }else{
        return 0 //no cost
    }
}

how do I put this in an equation?

and won't the equation system be undefined if there are to many terminals without a colour?

and if it isn't undefined, wont the first step solve the whole 0-extension problem?

Page 1 explains how you can go from the $\delta$-based formulation to the $f$-based formulation and back. But it doesn't matter for the algorithm. The first step is to solve the LP, thus obtaining values for the $\delta(i, j)$ values. From a pseudocode standpoint, you solve this by calling your favorite LP solver.
$c$ is the cost per edge, and is part of the input.
Terminals are the elements of the tree T (also given as part of the input)
$A_u$ is defined in the line above the text 'Rounding procedure' as the minimum distance between u and elements of T.
\sigma_j denotes the jth element of T in some random ordering of the elements (basically scramble the array of indices corresponding to T and take the jth element)


Connectivity Problem Hi. I have a problem but not sure if there is some literature on it or whether it has a standard name. Please let me know some reference from where I can begin.

Given undirected graph along with some pairs of nodes $s_i$ and $t_i$, we want to connect as many pairs in the graph as possible such that paths are edge disjoint.

Please comment on approximation and hardness results if any.

Maximize Edge Disjoint Paths (EDP)

The problem is NP Hard and here are some results:

1) It accepts $O(\sqrt{m})$ approximation by Kleinberg in 96 in general graphs.

2) The above is tight for directed graphs (Guruswami et. al.).

3) Inapproximation result by Andrews, Zhang : O($log ^{\frac{1}{2}-\epsilon}n$).

4) For planar graphs, Chekuri et. al. has found a O(1) approx with any edge being in O(1) paths.

I will update with references later but you can google out.

EDIT: There is a recent paper by Chekuri in 06 which has improvised it to $O(\sqrt(n))$ in undirected graphs. You will get the above references in that paper. The paper is at

theoryofcomputing.org/articles/v002a007/v002a007.ps.gz


Complexity of percolation In the context of bond percolation on $\mathbb{Z}^d$ where $d$ is a positive integer, consider the problem of computing a $2^{-k}$-approximation of the critical percolation $p_c$ given a lattice dimension $d\in\mathbb{N}$ and a precision parameter $k\in\mathbb{N}$ as inputs. Are there any known results about the complexity of such problem?

The problem is definitely in random double exponential time, and likely in exponential space. The first result was in my original post below, and the second in my update.

ORIGINAL POST:
Can't you get a good approximation by simulation, if you're willing to spend time exponential in $k$ and $d$? The input length is logarithmic in $k$ and $d$. So clearly the problem is in random double exponential time. Since nobody knows how to compute these values efficiently in practice, it seems clear this is not known to be in random exponential time. I would be very surprised if any other complexity results were known about this problem.

ADDED UPDATE:
Actually, I think the problem is very likely in EXPSPACE. Let's fix the dimension (to make things easier, and because I don't understand the subtleties of percolation in varying dimension well at all) so the input is just $k$. Also, let's say $k$ is given in unary so that I can drop the exponentials and talk about PSPACE. I propose the following algorithm.

First, we must make the assumption that there is a class of pseudorandom functions $F_\alpha({\mathbf{x}})$ which tell you whether the bond at coordinates $\mathbf{x}$ is present, where $\alpha$ is the seed for the pseudorandom function, and for which the bonds given by $F$ behave like random bonds with respect to percolation.

Now, suppose that we have a fixed value of the pseudorandom function seed $\alpha$. Consider the following two-player game, which two players A and B play, after being given a bond probability $p$ and a seed $\alpha$ for $F$.

Player 1 gives two sites ${\bf a}$ and ${\bf b}$ within distance $2^{k\nu}$ of the origin, but which are still $\theta(2^{k \nu})$ distance apart, where $\nu$ is chosen so that if the percolation probability $p$ is within $2^{-k}$ of the critical percolation probability $p_c$, then with high probability there will be a cluster of diameter $2^{k\nu}$ near the origin ($\nu$ is called a critical exponent, and I believe its value is known with mathematical proof). Player 1 claims that there is a path of length $d$ connecting these sites with bonds in $F_\alpha$, and also gives the site that is the midpoint of this path of length $d$.  Player 2 then claims that either the first part or the second part of this path is not connected. Player 1 responds by giving the point he claims is the midpoint of this allegedly disconnected section of the path. The two players continue in this way for $\log d$ steps, until they reach a segment of path consisting of a single bond, whose presence or absence is easily verified.

This is a two-player game whose result tells whether the critical percolation probability is within $2^{-k}$ of $p_c$, and by the result that alternating polynomial time is in PSPACE, the outcome of this game can be computed in PSPACE. A PSPACE machine could then compute this outcome for all seeds $\alpha$ to find which player wins with high probability: this will tell him whether $p$ is larger or smaller or approximately equal to $p_c-2^{-k} $. It can then do a binary search on $p$ to find $p_c$.

CHALLENGE: Find a PSPACE (or EXPSPACE if $k$ is not given in unary) algorithm without using the assumption that there are good pseudorandom functions for percolation.


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

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

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

Any previous results or new ideas are appreciated.

What you call the "revealing complexity" is sometimes called the (deterministic) query complexity of exact learning with membership queries.

Exact learning refers to the fact that you have to exactly identify $x\in C$ at the end, as opposed to being (say) probably approximately correct (as in PAC learning). Membership queries refers to the fact that you can query the individual bits of $x$ (as opposed to being given a random sample according to some distribution, as in PAC learning).

See this related question where I explain some of what's known about this complexity measure.
For example, we know that the deterministic query complexity of exactly learning a concept class $C\subseteq \{0,1\}^n$ with membership queries is characterized up to a factor of $\log |C|$ by the complexity measure defined in this paper by Servedio and Gortler or the extended teaching dimension of Hegedus. Both measures are combinatorial in nature. Whether there is a combinatorial measure that captures this complexity without a $\log|C|$ factor is unknown to me (and probably an open problem).


Interval partitioning with restrictions: NP-complete or efficiently solvable? The interval partitioning problem can be solved efficiently using a greedy algorithm. However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. Here's my problem formulation:

There are $n$ rooms. We want to hold $m$ events in these rooms. These events have fixed (given as input) starting times $s_1,\dots,s_m$ and finishing times $f_1,\dots,f_m$.
Each event must be held in exactly one room, and two events cannot be held in the same room at the same time.
Certain events can be held in only certain rooms. This is given as an input as an $n$ by $m$ matrix of booleans.
We want to figure out whether all events can be held in these rooms.

It seems to me that a greedy algorithm can't solve this. Additionally, since bipartite matching is a special case of this problem (when all events are held at the same time), I have attempted to transform this "interval partitioning with restrictions" problem into a maximum flow problem, with no success. I have also considered trying to prove that this problem is NP-complete, but I don't know where to start.

Could anybody help me either find an efficient algorithm for this or prove that it is NP-complete?

Here's a reduction from 3SAT. For each of your 3SAT variables $x_0$, imagine there is one event $x_0$ and two rooms called "Room $x_0$ is true" and "Room $x_0$ is false". The event $x_0$ has to be in one of those two rooms. Whichever statement is true, that's the room we don't use. And it is going to take all day. So the only rooms generally available for other events are the rooms named with a true statement.

Now let's say you want to add a condition - $x_0$ OR $x_1$ OR NOT $x_2$. Make that into an event that's just one nanosecond long, at a random time so it doesn't conflict with the other condition-events. And it has to be held in one of "Room $x_0$ is true", "Room $x_1$ is true", or "Room $x_2$ is false".

Now solving your event assignment problem lets you solve an arbitrary 3SAT problem.


Criteria to determine if a complement of a graph has odd-holes Is there any graph theoretic result for recognising graphs whose complement has no odd holes ?
I know about perfect graphs but they have the extra criteria being odd-hole free.

There is a structural result for odd-hole-free graphs by Michele Conforti, Gérard Cornuéjols, and Kristina Vušković:

  Decomposition of odd-hole-free graphs by double star cutsets and 2-joins, Discrete Applied Mathematics, 2004.

Basically what it says is either the odd-hole-free graph belongs to a kind of basic class, or we can decompose the graph into smaller pieces using two kinds of decompositions.  The proof of the strong perfect graph theorem follows the same spirit, and similar results are also known for various classes, e.g. even-hole-free graphs.

The interesting thing is that although the structural theorem of even-hole-free graphs leads to polynomial-time recognition algorithms (1, 2), the corresponding implication is not known for odd-hole-free graphs.  However if we add the restriction that the clique number is bounded then we do have such a result.

$^1$ The first decomposition-based algorithm.
$^2$ The fastest algorithm currently known.


Making planar graph biconnected I've given a planar graph (with clockwise ordering of vertices). I would like to make it biconnected by adding some number of edges. Graph should remain planar, of course. How can I do this?

Few more notes:

By biconnected I mean no single cut vertex and no bridge,
We cannot change given embedding,
We do not have to minimize number of edges added

One way to augmenting an embedded planar graph (i.e. a plane graph) to become biconnected, while preserving the embedding, is

for each articulation vertex v:
  for each two edges vu and vw that are consecutive in the cyclic order around v:
    if u and w belong to different biconnected components of G:
      add edge uw

You have to be a little careful about the ordering of operations, though, because if you did this simultaneously at both endpoints of a bridge edge you could create a non-planarity. You have to do them one at a time.

This method can add significantly fewer edges than triangulation: each new edge reduces the number of biconnected components by one, so the total number of edges added is less than the original number of biconnected components.


How hard is binary Sudoku puzzle? Sudoku is a well-known puzzle that is NP-complete. Binary Sudoku is a variant that only allows the numbers $0$ and $1$. The rules are as follows.

Each row and each column must contain an equal number of zeros and ones.
Each row and each column is unique.
No row or column contains consecutive triples of zeros or ones ($1 1 1$ is a consecutive triple of ones).

The input is a $N \times N$ square partially filled with zeros and ones. To solve the puzzle, each cell in the $N \times N$ square must be filled by either $0$ or $1$ while respecting the above rules. I was not able to find any intractability result for solving the Binary Sudoku puzzle.

  How hard is solving the Binary Sudoku puzzle? Is it NP-complete?

Also, I'm interested in the complexity of a related problem.

Given a fully filled $N \times N$ square that respects only rules 1 and 2 above,

  how hard is it to find a permutation of rows and columns such that the resulting square respects rule 3?

EDIT: I quickly completed the amateur proof that I started a few months ago and never finished.

You can download it in PDF format on my blog ... nobody has checked it yet, so refutations, comments and suggestions are welcome.

I don't know if there is an official proof, but a few months ago I built the gadgets to mimic a planar 3-CNF formula; for example the OR, SPLIT and TURN gadgets are:

I built/checked the gadgets using a simple constraint solver program.

The uniqueness of each row/column (rule 2) can be achieved marking them with a unique "binary number" using a 2x2 block that acts like a "digit":

01 = 0   10 = 1
10       01

And the equal number of 1s and 0s (rule 3) can be achieved mirroring the whole puzzle, and inverting the 0s with 1s (using special walls in the middle that allow the transition without breaking the rules):

  3CNF simulation    |  wall  | 3CNF sim. with  | 0000 (using 2x2 blocks)
                     |        | 0,1 inverted    | 0001
 --------------------+        +-----------------+ 0010
    wall                        wall            | ....
 --------------------+        +-----------------+ ....
  3CNF sim. with     |  wall  | 3CNF simulation |
  0,1 inverted       |        |                 |
 --------------------+--------+-----------------+
 0101 .... (using 2x2 blocks)
 0011 ....
 0000 ....

So deciding if a partially filled $N \times N$ Binary Puzzle board has a solution, is NP-hard.

Like other similar puzzles it's not immediate to say that it is in NP (see for example the discussion on succinct Nurikabe on cstheory). However if the initial board is given as a full string $\{0,1,\bot\}^{N \times N}$ (the representation is not succinct), and you drop the the unique solution constraint (which is another rule of the game), then the problem is in NP (and thus NP-complete).


On Boolean functions with a certain number of zeros Given boolean $f(\Bbb x)$, with $\Bbb x\in\{0,1\}^n$, what are good upper/lower bounds, in terms of $|f^{-1}(0)|$, for minimum $deg(p(\Bbb x))$ of a real polynomial satisfying $p(\Bbb x)=f(\Bbb x)$?

One relevant result is that if $\deg f = d$ then $2^d\hat{f}(S)$ is an integer for all $S$ (see for example exercise 12(b) here). In particular, $2^d\hat{f}(\emptyset) = 2^{d-n}|f^{-1}(1)|$ is an integer, and so $|f^{-1}(0)|$ is a multiple of $2^{n-d}$. This gives a lower bound on $d$ given $|f^{-1}(0)|$, which is tight for an AND of $d$ variables.

In terms of corresponding upper bounds you can't expect much, since there are balanced functions of maximal degree (parity for example). Moreover, there are functions with $|f^{-1}(0)| = 2^{n-k}$ of maximal degree for all $1 \leq k \leq n$, for example parity on $n-k+1$ variables ORed with $k-1$ variables; you can probably be a bit more cunning and construct a function of maximal degree for any given $0 < |f^{-1}(0)| < 2^n$. However, if $|f^{-1}(0)| \in \{0,2^n\}$ then the function is constant.


Using compression to improve edit distance computation I am doing a seminar on a paper titled "Unified Compression-Based Acceleration
of Edit-Distance Computation" that uses straight-line programs to improve edit distance computation. It is a common method to exploit repetitions for ED although I couldn't find the first article that used it and I thought it is important to mention it in the seminar.

Does anybody have a clue what it was?
Thanks!

Crochemore, Landau and Ziv-Ukelson were, I believe, the first to consider (LZ) compression explicitly in this context. As mentioned in the comments above, the earlier technique of Masek and Paterson is also in effect a form of compression. Considering general grammar-compression (SLP) is, I believe, a relatively new idea. Using it for string comparison speedup is original to the paper you cite, although comparing grammar-compressed strings as such has been considered before. You will find references and discussion in the compression chapter of http://arxiv.org/abs/0707.3619 .


Natural CLIQUE to k-Color reduction There is clearly a reduction from CLIQUE to k-Color because they're both NP-Complete. In fact, I can construct one by composing a reduction from CLIQUE to 3-SAT with a reduction from 3-SAT to k-Color. What I'm wondering is whether there is a reasonable direct reduction between these problems. Say, a reduction that I could explain to a friend fairly briefly without needing to describe an intermediate language like SAT.

As an example of what I'm looking for, here's a direct reduction in the reverse direction: Given G with $n$ and some $k$ (the number of colors), make a graph G' with $kn$ vertices (one per color per vertex). The vertices $v'$, $u'$ corresponding to vertices $v, u$ and colors $c, d$ respectively are adjacent if and only if $v \neq u$ and ($c \neq d$ or $vu \not \in G$). An $n$-clique in $G'$ has only one vertex per vertex in $G$, and the corresponding colors are a proper $k$-coloring of $G$. Similarly, any proper $k$-coloring of $G$ has a corresponding clique in $G'$.

Edit: To add some brief motivation, Karp's original 21 problems are proved NP-Complete by a tree of reductions where CLIQUE and Chromatic Number form the roots of major subtrees. There are some natural reductions between problems in the the CLIQUE subtree and the Chromatic Number subtree, but many of them are just as hard to find as the one I'm asking about. I'm trying to drill down on whether the structure of this tree shows some underlying structure in the other problems or if it is entirely a consequence of which reductions were found first, since there is less motivation to search for reductions between two problems when they are known to be in the same complexity class. Certainly the order had some influence, and parts of the tree can be rearranged, but can it be rearranged arbitrarily?

Edit 2: I continue to search for a direct reduction, but here is a sketch of the closest I've gotten (it should be a valid reduction, but has CIRCUIT SAT as a clear intermediary; it's somewhat subjective whether this is any better than composing two reductions as alluded to in the first paragraph).

Given $G, k$, we know that $\overline{G}$ can be $n-k+1$-colored with $k$ vertices all colored True iff $G$ has a $k$-clique. We name the original vertices of $G$ $v_1, \ldots, v_n$ and then add to $\overline G$ additional vertices: $C_{ij}$ with $1 \le i \le n$, $0 \le j \le k$. The key invariant will be that $C_{ij}$ can be colored True if and only if among vertices $\{v_1,\ldots, v_i\}$ there are at least $j$ vertices colored True. So, each $C_{i0}$ can be True. Then, $C_{ij}$ for $j > 0$ gets the color $C_{(i-1)j} \vee C_{(i-1)(j-1)} \wedge v_i$ where all non-true colors are treated as false. There is a $k$-clique in $G$ iff $C_{nk}$ can be colored True, so if we force that coloring, the new graph is colorable iff there was a $k$-clique in the original graph.

The AND and OR gadgets to enforce the relationships are much like the reduction from CIRCUIT SAT to 3-COLOR, but here we include a $K_{n-k+1}$ in our graph, pick vertices T, F, and Ground, and then connect all others to everything but the $v_i$s; this assure that the $C_{ij}$s and the other gadgets receive only 3 colors.

Anyway, the $\overline G$ part of this reduction feels direct, but the use of AND/OR gates is much less direct. The question remains, is there a more elegant reduction?

Edit 3: There have been a few comments about why this reduction would be hard to find. CLIQUE and k-Color are indeed quite different problems. Even without a reduction, though, an answer that details why the reduction is hard in the one direction but possible in the other would be very helpful and contribute a lot to the problem.

Given a graph $G$ and a number $k$, such that you want to know whether $G$ contains a $k$-clique, let n be the number of vertices in $G$. We construct another graph $H$, such that $H$ is $n$-colorable if and only if $G$ has a $k$-clique, as follows:

(1) For each vertex $v$ in $G$, make an $n$-clique of vertices $(v,i)$ in $H$, where $i$ ranges from $1$ to $n$.

(2) Add one additional vertex $x$ to $H$.

(3) For each triple $\{x,y,z\}$ of vertices in $H$, where $y=(v,i)$ and $z=(u,j)$, test whether one of the following conditions holds: either $u\ne v$ and $i=j$, or $u$ and $v$ are nonadjacent vertices in $G$ with $\max(i,j)\le k$. If either of these two things is true, add another $n$-clique to $H$. Within this clique, select three vertices $x'$, $y'$, and $z'$. Connect $x$ to every vertex in the clique except for $y'$ and $z'$; connect $y$ to every vertex in the clique except for $x'$ and $z'$; and connect $z$ to every vertex in the clique except for $x'$ and $y'$.

The gadgets added in step (3) prevent the triple of vertices $x$, $y$, and $z$ from all being given the same color as each other in a valid coloring of $H$. The clique in $G$ can be recovered from a coloring of $H$ as the set of vertices $(v,i)$ that are in the same color class as $x$ and that have $i\le k$.


2DFA that requires many states in equivalent DFA? Is there a 2DFA with $n$ states (where $n$ is nontrivial, say at least 4) that requires at least $2^n$ states to simulate using any DFA?

A two-way DFA (2DFA) is a deterministic finite-state automaton that is allowed to move back and forth on its read-only input tape, unlike finite-state automata that may only move the input head in one direction.

It is well-known that 2DFAs recognize precisely the same class of languages as DFAs, in other words the regular languages.  Less well-understood is the question of how efficient the simulation is.  The original constructions from the late 1950s by Rabin/Scott and Shepherdson used a notion of crossing sequences and are quite hard to analyse.  Moshe Vardi published another construction that shows an upper bound of $2^{O(n^2)}$ states, but this bound may have some slack.

I am asking whether any (families of) 2DFAs are known that require many states in any DFA simulating them, even after Myhill-Nerode minimization of the DFA.  Moreover, would there be any interesting consequences of knowing such 2DFAs?

Moshe Y. Vardi, A Note on the Reduction of Two-Way Automata to One-Way Automata, IPL 30 261–264, 1989.  doi:10.1016/0020-0190(89)90205-6 (preprint)

The tight bound is $ n(n^n -(n-1)^n) $, which was given in Removing Bidirectionality from Nondeterministic Finite Automata by Christos Kapoutsis (2005).

I am also putting a figure from this paper giving a clear picture:

To get more, I think this paper is a good starting point. To check the related recent developments, I can also recommend to check the papers listed here: dblp: Christos A. Kapoutsis.


The logic in derivation of virtual welfare I am learning algorithmic game theory with the lecture notes posted by Tim Roughgarden. In lecture 5 it is proved that the problem of revenue (or profit) maximization in single-parameter environment is equivalent to maximizing something called "virtual welfare". I find it hard to understand the logic of the proof.

The very first step of the proof assumes that the payment rule is exactly in the form given by Myerson's lemma:
$$p_i(b_i,\mathbf{b}_{-i})=\int_0^{b_i}z\cdot x'_i(z,\mathbf{b}_i)\mathrm{dz}$$
where $x'_i(z,\mathbf{b}_i)$ is the derivative of the allocation rule $x'_i(z,\mathbf{b}_i)$. Then substitute the formula of payment into the profit object
$$\mathbb{E}\left[\sum_{i=1}^n\mathbf{p}(\mathbf{v})\right]$$
with some calculus the "virtual-welfare" magically shows up.

Then the author claims that maximizing the virtual welfare is equivalent to maximizing revenue, and if the corresponding allocation rule is monotone then we get a optimal DSIC mechanism. I have two questions about this:

The result relies on the assumption that the payment rule is given in the previous form. Why does it must be in that form? The proof feels like some circular reasoning. Is this because that we are restricted on searching only for DSIC mechanism?
Furthermore, sometimes there exists no monotone allocation rule to optimize the deduced virtual welfare, but does this also mean that there exists no monotone rule to optimize the original profit?

I think I've gotten part of the answer. The above statement actually says that for any truthful mechanism, the expected profit is equal to its expected virtual surplus. If we are searching for truthful mechanisms only, then by the Myerson's Lemma the payment rule must be in that form.


maintaining a balanced spanning tree of a growing undirected graph I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph.

I have an undirected graph that starts as a single node, the "root".

At each step, I add to the graph either a new node and an edge connecting it to the graph, or just a new edge, connecting two old nodes. As I grow the graph, I maintain a spanning tree. Most of the time, this means that when I add a new node and edge, I set the new node to be the child of the old node that it connects to.

I have no control over the order in which the new nodes are added, so the above tree-building algorithm can obviously lead to imbalanced spanning trees.

Does anybody know of online heuristics that will keep the spanning tree "relatively balanced", while minimizing the amount of work done in re-treeing? I have full control over the tree structure. What I don't control is the graph connectivity, or the order in which new nodes are added.

Note that the standard Google responses to terms like "balanced" "spanning" and "tree" seem to be binary trees and B-trees, neither of which apply. My graph nodes can have any number of neighbors, so the tree nodes can have any number of children, not 2 like binary trees. B-trees maintain balance by changing their adjacency lists, and I cannot change the graph connectivity.

Every time you add a new vertex with an edge, you don't have options.
Every time you add a new edge, if the current distance to the root is bigger than the distance through the new edge, you remove the old edge in the old shortest path and add the new one. Otherwise, you just keep your tree unchanged. I think this way you get something very similar to a BFS tree in the sense that the levels of the tree will contain the same vertices and the distance from a vertex to the root will be the same as the distance in the BFS tree (and in the graph), but I don't know if that's enough to satisfy your "ideal balanced spanning tree" condition.


Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the syntactic monoid $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $L$ iff there exists a morphism $\varphi : A^{\ast} \to M$ such that $L = \varphi^{-1}(\varphi(L)))$.

Then we have the nice result:

A monoid $M$ recognizes $L \subseteq A^{\ast}$ if $M(L)$ is a homomorphic image of a submonoid of $M$ (writen as $M(L) \prec M$).

The above is usually states in the context of regular languages, and then the above monoids are all finite.

Now suppose we substitute $A^{\ast}$ with an arbitrary monoid $N$, and we say that a subset $L \subseteq N$ is recognized by $M$ if there exists a morphism $\varphi : N \to M$ such that $L = \varphi^{-1}(\varphi(L))$. Then we still have that if $M$ recognizes $L$, then $M(L) \prec M$ (see S. Eilenberg,  Automata, Machines and Languages, Volume B), but does the converse hold?

In the proof for $A^{\ast}$ the converse is proven by exploiting the property that if $N = \varphi(M)$ for some morphism $\varphi : M \to N$ and $\psi : A^{\ast} \to N$ is also a morphism, then we can find $\rho : A^{\ast} \to M$ such that $\varphi(\rho(u)) = \psi(u)$ holds, simply by choosing some $\rho(x) \in \varphi^{-1}(\psi(x))$ for each $x \in A$ and extending this to a morphism from $A^{\ast}$ to $M$. But this does not work for arbitrary monoids $N$ so I expect the above converse to be false then. And if it is false, for what kind of monoid beside $A^{\ast}$ is it still true, and did those monoids have received any attention in the research literature?

Yes, these monoids have received attention in the research literature and actually lead to difficult questions.

Definition. A monoid $N$ is called projective if the following property holds: if $f:N \to R$ is a monoid morphism and $h:T \to R$ is a surjective morphism, then there exists a morphism $g:N \to T$ such that $f = h \circ g$.

You can find a long discussion on projective monoids in [1], right after Definition 4.1.33. It is shown in particular that every projective finite semigroup is a band (a semigroup in which every element is idempotent). But the converse is not true and it is actually an open problem to decide whether a finite semigroup is projective.

[1] J. Rhodes and B. Steinberg, The $q$-theory of finite semigroups. Springer Monographs in Mathematics. Springer, New York, 2009. xxii+666 pp. ISBN: 978-0-387-09780-0


Can all mathematical operations be encoded with a Turing Complete language? In High School Computing I was taught the Structured Program Theorem - that you could implement any mathematical operation using:

Sequence
Selection
Iteration

After completing a Computer Science degree - we can express what is required for any computable function more formally with M-recursive functions:

The constant $0$ function
The successor function
Selecting parameters
Function composition
Primitive Recursion
The $\mu$-operator (look for the smallest $x$ such that...)

This being the minimal set of axioms. Translating this to code we get:

The constant 0
Incrementation _ + 1
Variable access x
Program/statement concatenation _; _
Countdown loops for ( x to 0 ) do _ end
While loops while ( x != 0 ) do _ end

But I've come away looking for proof. How do we know all this covers all computable functions? Is there an obvious branch of Mathematics for which this is not covered? Is there a shortcoming in Lambda Calculus where it is yet to cover off obscure Mathematical operations?

(Noting of course that

Lambda Calculus is a subset of Term rewriting,
that Mathematica chose Term-writing over Lambda Calculus as its foundation,
and recent work in Univalent Foundations. )

My question is: Can all mathematical operations be encoded with a Turing Complete language?

But I've come away looking for proof. How do we know all this covers all computable functions? Is there an obvious branch of Mathematics for which this is not covered? Is there a shortcoming in Lambda Calculus where it is yet to cover off obscure Mathematical operations?

These are excellent questions! The best answer your question is for you to read Turing's 1936 paper On Computable Numbers, With an Application to the Entscheidungsproblem. It's a very surprisingly readable and accessible paper, and it is concerned with precisely this question.

To gloss the paper, there is no way to give a purely mathematical characterization of the computable functions, because what is computable is partly a question of physics -- it matters what sorts of computers we can build to compute with.

But something we can do is to think about the operations humans perform when doing computations, and once we have a list of these, then we can build a mathematical model of a machine performing these kinds of actions (as a state-transition system). Then we can mathematically analyze this model, of course -- for example to compare it with other proposed formalisms. Turing performed such an analysis, and built a model of the situation where you have a piece of paper and a pencil, and are permitted to write on the paper, and to read what you have written and perform new actions based on what you have read.

All of these operations are obviously physically realizable, and it turns out that (for number-computability) that all the various proposed models of computation, such as Turing machines, Church's lambda calculus, Post's rewriting systems, and Godel's systems of guarded equations are all equivalent.

So that's why people think that Turing-completeness = computability. However, note that it is not a priori impossible that we might discover some new physical principle letting us build machines that could let us decide the halting problem. If we did, then we would be compelled to revisit our definition of computability. (Or more likely, have the super-intelligent noncomputable AI we build using such exotic physics revisit the definitions for us!)


Strong Normalization of Extended Calculus of Constructions (CC with cumulative universes) There are some proofs around to prove the strong normalization of the calculus of constructions (i.e. that all type systems in the lambda cube are strongly normalizing). I have analyzed the proof available from Herman Geuvers which is not an easy read, but understandable.

I am interested in proof of strong normalization of calculi like CC which have cumulative universes i.e. which have sorts
$$
 \text{sort} ::= * \mid \Box_i \quad 0 \le i,
$$
allow subtyping
$$
\begin{array}{c}
\Gamma \vdash t : T
\\
T \le U
\\ \hline
\Gamma \vdash t : U
\end{array}
$$
where $\le$ is based on the ordering of sorts
$$ * < \Box_0 < \Box_1 \ldots$$

and the typing rules are practically the same as for pure type systems where $*$ is impredicative and all $\Box_i$ are predicative.

A simple generalization of the proof of Herman Geuvers does not work because it heavily depends on a distinction between kinds and types and objects and type constructors (based on having only two sorts $*$ and $\Box$ and no cumulativity).

I have searched a lot but I cannot find a comprehensible proof of strong normalization. This is strange because this type system is a subset of the type system of Coq which is in use for several decades now and supposedly strongly normalizing.

Can anybody give hints to understandable proofs of such type systems?

Thanks for any hint.

Addendum:

From the first comment of Cody I conclude that there might be no easier to grasp proofs than the proof in Zhaohui Luo's Phd thesis which I already have but it is a big bullet to bite.

I don't need the full power of cumulative universes, but the calculus of constructions is not sufficient for me, because I have to make a Coq like split between propositions and "normal" types. Is there a way to generalize the proof of strong normalization of CoC to such a type system?

Furthermore a proof of strong normalization would be nice, but a proof of weak normalization would be sufficient at least to make type checking decidable. Is there a simpler proof for weak normalization for systems with cumulative universes?. But, of course, this does not prove that the system is sound (i.e. free of contradictions) which is a major drawback.

I guess this is just an extension of my comment, but I've heard Luo cite Goguen's paper The metatheory of UTT which uses typed operational semantics. I'm afraid I can't find a free online version though, and typed operational semantics doesn't exactly take all the sting from the technical hassles.

A completely different, and IMO under-appreciated paper is Sacchini & Gregoire's On Strong Normalization of the Calculus of Constructions with Type-Based Termination, which treats a system with Prop + 1 universe and natural numbers. Already a feat!

Addressing your other concerns: Weak normalization does imply consistency! I don't think it's significantly easier to prove than strong normalization, though, so usually people will go for gold and try to prove SN directly. It's a well-known conjecture that weak normalization implies strong normalization in "reasonable" theories anyways.

If you're only interested in consistency, you might try building a model of your theory directly! This seems to be quite a bit easier than normalization, and might be seen as a stepping stone if you're going to try to build a proof yourself. One reference I enjoy is  Werner and Lee Proof-irrelevant model of CC with predicative induction and judgmental equality
. I think this easily generalizes to cumulative universes. And if you think their construction is technical, imagine the full normalization proof!


Compiler correctness proofs I am looking for tutorial material that covers compiler correctness proofs, preferably using denotational methods, at the level of a beginning grad student.

Alternatively, do you know of some simple compiler examples that I could use to illustrate the issues?  (The first example that occurred to me was a translator from infix to postfix expressions.  But it failed to show anything interesting other than how to do induction on syntax.)

You'll need to modernize the notation, but McCarthy and Painter's Correctness of a Compiler for Arithmetic Expressions is simple and good, and also of historical interest (since to the best of my knowledge it's the first paper on the subject).


Explicit mu-recursive expression for Ackerman function Can you please point out how to build Ackerman function (actually I'm interested in a version proposed by Rózsa Péter and Raphael Robinson) via standard mu-recursive operators? I tried original papers by Péter and Robinson, but Péter's paper use a language different from English and Robinson's papers “Recursion and Double Recursion” and “Primitive Recursive Functions” also don't help: first of them seems more relevant, but is uses so called double recursion operator to define Ackerman function, so in this case explicit definition of the operator in mu-recursive terms is seeked.

Most closely to the answer goes P. Smith in “An introduction to Godel's theorems” (CUP, 2007) (29.4 The Ackermann-Peter function is μ-recursive), but he comes up with the following: “making the argument watertight is pretty tedious though not difficult. There’s nothing to be learnt from spelling out the details here: so we won’t.”

I also tried Rózsa Péter's book “Recursive functions” (1967, Academic press). There are plenty of variants for recursion operators given there. Usually one reduces to other. I believe that there is a type of recursion operator which fit for definition of Ackerman function and sequence of steps which reduce it to primitive redursion and minimisation operators, but I found myself unable to investigate the whole way down.

Breaking the Ackermann function all the way down to the elementary operators would really be quite lengthy, but here is a sketch:

Note that when computing $A(m,x)$ recursively, at any point of the computation you are dealing with an expression of the form $A(m_1,A(m_2,\dots,A(m_k,z)\dots)$. Given a bijective pairing function $p$ with inverse $(\pi_1,\pi_2)$, we can encode this state as $p(z,p(k,p(m_k,\dots,p(m_2,m_1)\dots)$ (just $p(z,0)$ in case $k=0$). We then can define the one-step evaluation function, given a state:

$e(p(z,0)) = p(z,0)$;

$e(p(z,p(k,p(0,c)))) = p(z+1,p(k-1,c))$;

$e(p(0,p(k,p(m+1,c)))) = p(1,p(k,p(m,c)))$;

$e(p(z+1,p(k,p(m+1,c)))) = p(z,p(k+1,p(m+1,p(m,c))))$.

You then get the n-step evaluation function using primitive recursion:

$E(0,m,x) = p(x,p(1,m))$ and $E(n+1,m,x) = e(E(n,m,x))$.

Finally, wrap $\mu$-recursion around $E$ to find the point where we get to a state of the form $p(z,0)$  - $z$ will be $A(m,x)$.


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

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

Question:

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

Remark:

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

I think that we can do slightly better than $O(n^{1+\omega})$ for dense graphs, by using rectangular matrix multiplication. A similar idea was used by Eisenbrand and Grandoni ("On the complexity of fixed parameter clique and dominating set",
Theoretical Computer Science Volume 326(2004) 57–67) for 4-clique detection.

Let $G=(V,E)$ be the graph in which we want to detect the existence of a claw.
Let $A$ be the set of (ordered) pairs of vertices in $V$. Consider the following Boolean matrix $M$ of size $|V|\times |A|$: each row is indexed by some
$u\in V$, each column is indexed by some $(v,w)\in A$, and the corresponding entry
is one if and only if $\{u,v\}\in E$, $\{v,w\}\in E$ and $\{u,w\}\notin E$.
Consider the Boolean matrix product of $M$ and its transpose $M^T$. The graph $G$ has a claw if and only if there exists $\{u,v\}\notin E$
such that the entry of $MM^T$ in the row indexed by $u$ and the column indexed by $v$ is one.

The complexity of this algorithm is essentially the complexity of computing the Boolean product of an $n\times n^2$ matrix by a $n^2\times n$ matrix, where $n$ denotes the number of vertices in the graph.
It is known that such a matrix product can be computed in time $O(n^{3.3})$, which is better than $O(n^{1+\omega})$ for the best known upper bound on $\omega$.
Of course,  if $\omega=2$ (as conjectured) then the two approaches give the same complexity $O(n^3)$.


What are good books for learning grammar ( BNF )? I'm taking a basic course on programming language theory, and we're covering context-free grammar (BNF). Personally, I'm really interested in how to design syntax for a programming language. I'm planning to write a simple compiler for my graduate project, so what books are good for this area? Any feedback would be greatly appreciated.

Thanks,
Chan

For just learning about BNF grammars, a good reference is this.

However, since you mentioned its with the interest of developing a compiler, the dragon book is probably the best reference possible.


About the position of side conditions in an inference rule Sometimes I see people put side conditions above the inference line as if they were premises of an inference rule.  This feels strange.  My understanding (which may be wrong) is that a side condition belongs to the meta-theory, not to the object-theory: an object-proof of a side condition should not be required and may even not be possible.  So what is the motivation of doing this?  For saving space or for some other deeper reason?

$Update$:

I am no longer quite sure whether a side condition belongs to the meta-theory.  But at least it is outside the object-theory the inference rules describe,that is, the truth of a side condition cannot be derived using the inference rules.

$Update^2$:

Take as an example the rule for typing variables from the simply-typed $\lambda$-calculus.  $(x : T) \in \Gamma$ is a side condition that tests whether the variable $x$ of type $T$ is in the typing context $\Gamma$.  In some presentations, the side condition is put aside, leaving the premises empty to indicate that it is an axiom, though conditional:

$$\frac{}{\Gamma \vdash x : T} (x : T) \in \Gamma$$

while in others, it is put above as if it were a premise:

$$\frac{(x : T) \in \Gamma}{\Gamma \vdash x : T}$$

An inference rule is a symbolic representation of an entire family of closure rules. A side condition cuts down such a family to a subfamily. It is perhaps best to show an example.

We consider the following toy variant of the propositional calculus. The language of expressions is built from primitive constants $\top$ and $\bot$, and a binary connective $\land$. Let $\mathscr{E}$ be the set of all expressions we can build in this language (they correspond to binary trees whose leaves are labeled with $\bot$ and $\top$).

There is only one judgement form $\vdash A$ and only two judgement rules
$$
\frac{ }{\vdash \top}
\qquad
\frac{\vdash A \qquad \vdash B}{\vdash A \land B}
$$
It should be clear that $\vdash A$ is derivable if, and only if, $A$ is an expression which contains no $\bot$'s. Now, how precisely do we read the above inference rules? Bare with me while I describe closure rules and closure operators. These provide an order-theoretic explanation of what rules of inference are and what derivability is about.

Each rule determines a family of closure rules. A closure rule is a pair $(S, A)$ where $S \subseteq \mathscr{E}$ and $A \in \mathscr{E}$. In our case we get the following family of closure rules $\mathscr{C}$:
$$\mathscr{C} = \{(\emptyset, \top)\} \cup \{(\{A,B\},A \land B) \mid A, B \in \mathscr{E}\}$$
Such a family then induces a closure operator $F_\mathscr{C} : P(\mathscr{E})
\to P(\mathscr{E})$ on the powerset of expressions, defined by
$$F_\mathscr{C}(X) = \{A \mid \exists S \subseteq X . (S, A) \in \mathscr{C}\}.$$
The set of all derivable judgements is precisely the least fixed point of $F_\mathscr{C}$. The least fixed point exists by Tarski's theorem because $F_\mathscr{C}$ is a monotone operator on a complete lattice.

Suppose we place a side condition $\phi$ on the second rule:
$$
\frac{ }{\vdash \top}
\qquad
\frac{\vdash A \qquad \vdash B}{\vdash A \land B} \ \text{if $\phi(A,B)$}
$$
Here $\phi$ can be any condition on the expressions. For instance, it could be $A \neq B$ (but in that case there will be a better way of writing the rule without a side condition), or perhaps it says that $A$ has fewer occurrences of $\bot$ than $B$, or whatever. The side condition limits the family of closure rules determined by the rule:
$$\mathscr{C} = \{(\emptyset, \top)\} \cup \{(\{A,B\},A \land B) \mid A, B \in \mathscr{E} \ \text{and}\ \phi(A,B)\}.$$
Thus we see that the side-condition lives at the "meta-level", because it does not appear inside the closure rules, but instead gives an additional condition on the closure rules themselves.

In the example of the variable rule that you mention,
$$\frac{ }{\Gamma \vdash x : T} \ \text{if $(x:T) \in \Gamma$},$$
we clearly have a side-condition.

It is called a side-condition because it is written on the side. And it is so written for a reason, namely to make it clear that it is not a premise of the rule. This is especially important when the object-language described by the rule uses the same symbols as the meta-level language and confusion could ensue. However, it has become fashionable in certain circles to write side-conditions above the line. I am not sure it is a good idea to write side-conditions above the line, as it confuses students and newcomers, but it is stylistically a bit more pleasing.


Is it known whether $BPP\cap NP\subseteq RP$? The reverse inclusion is obvious, as is the fact that any self-reducible NP language in BPP is also in RP. Is this also known to hold for non-self-reducible NP languages?

As with most questions in complexity, I'm not sure there will be a full answer for a very long time. But we can at least show that the answer is non-relativizing: there is an oracle relative to which inequality holds and one relative to which equality holds. It's fairly easy to give an oracle relative to which the classes are equal: any oracle which has $\mathrm{BPP} = \mathrm{RP}$ will work (eg any oracle relative to which "randomness doesn't help much"), as will any oracle which has $\mathrm{NP} \subseteq \mathrm{BPP}$ (eg any oracle relative to which "randomness helps a lot"). There are a lot of these, so I won't bother with the specifics.

It's somewhat more challenging, though still fairly straightforward, to design an oracle relative to which we get $\mathrm{RP} \subsetneq \mathrm{BPP} \cap \mathrm{NP}$. The construction below actually does a bit better: for any constant $c$, there is an oracle relative to which there is a language in $\mathrm{coRP} \cap \mathrm{UP}$ which is not in $\mathrm{RPTIME}[2^{n^c}]$. I'll outline it below.

We'll design an oracle $A$ that contains strings of the form $(x,b,z)$, where $x$ is an $n$-bit string, $b$ is a single bit, and $z$ is a bit string of length $2n^c$. We will also give a language $L^A$ which will be decided by a $\mathrm{coRP}$ machine and a $\mathrm{UP}$ machine as follows:

The $\mathrm{coRP}$ machine, on input $x$, guesses $z$ of length $2|x|^c$ randomly, queries $(x,\mathtt{0},z)$, and copies the answer.
The $\mathrm{UP}$ machine, on input $x$, guesses $z$ of length $2|x|^c$, queries $(x,\mathtt{1},z)$, and copies the answer.

To make the above-specified machines actually meet their promises, we need $A$ to satisfy some properties. For every $x$, one of these two options must be the case:

Option 1: At most half of $z$ choices have $(x,\mathtt{0},z) \in A$ and zero $z$ choices have $(x,\mathtt{1},z) \in A$. (In this case, $x \not\in L^A$.)
Option 2: Every $z$ choice has $(x,\mathtt{0},z) \in A$ and precisely one $z$ choice has $(x,\mathtt{1},z) \in A$. (In this case, $x \in L^A$.)

Our aim will be to specify $A$ satisfying these promises so that $L^A$ diagonalizes against every $\mathrm{RPTIME}[2^{n^c}]$ machine. To try to keep this already long answer short, I'll drop the oracle construction machinery and a lot of the unimportant details, and explain how to diagonalize against a particular machine. Fix $M$ a randomized Turing machine, and let $x$ be an input so that we have full control over the selection of $b$'s and $z$'s so that $(x,b,z) \in A$. We will break $M$ on $x$.

Case 1: Suppose there is a way to select the $z$'s so that $A$ satisfies the first option of its promise, and $M$ has a choice of randomness which accepts. Then we will commit $A$ to this selection. Then $M$ cannot simultaneously satisfy the $\mathrm{RP}$ promise and reject $x$. Nevertheless, $x \not\in L^A$. So we have diagonalized against $M$.
Case 2: Next, assume that the previous case did not work out. We will now show that then $M$ can be forced either to break the $\mathrm{RP}$ promise or to reject on some choice of $A$ satisfying the second option of its promise. This diagonalizes against $M$. We will do this in two steps:

Show that for every fixed choice $r$ of $M$'s random bits, $M$ must reject when all of its queries of the form $(x,\mathtt{0},z)$ are in $A$ and all of its queries of the form $(x,\mathtt{1},z)$ are not in $A$.
Show that we can flip an answer $(x,\mathtt{1},z)$ of $A$ for some choice of $z$ without affecting the acceptance probability of $M$ by much.

Indeed, if we start with $A$ from step 1, $M$'s acceptance probability is zero. $A$ doesn't quite satisfy the second option of its promise, but we can then flip a single bit as in step 2 and it will. Since flipping the bit causes $M$'s acceptance probability to stay near zero, it follows that $M$ cannot simultaneously accept $x$ and satisfy the $\mathrm{RP}$ promise.

It remains to argue the two steps in Case 2:

Fix a choice of random bits $r$ for $M$. Now simulate $M$ using $r$ as the randomness and answering the queries so that $(x,\mathtt{0},z) \in A$ and $(x,\mathtt{1},z) \not\in A$. Observe that $M$ makes at most $2^{n^c}$ queries. Since there are $2^{2n^c}$ choices of $z$, we can fix the unqueried choices of $z$ to have $(x,\mathtt{0},z) \not\in A$, and have $A$ still satisfy the first option of its promise. Since we couldn't make Case 2 work for $M$, this means $M$ must reject on all its choices of randomness relative to $A$, and in particular on $r$. It follows that if we select $A$ to have $(x,\mathtt{0},z) \in A$ and $(x,\mathtt{1},z) \not\in A$ for every choice of $z$, then for every choice of random bits $r$, $M$ rejects relative to $A$.
Suppose that for every $z$, the fraction of random bits for which $M$ queries $(x,\mathtt{1},z)$ is at least $1/2$. Then the total number of queries is at least $2^{2n^c} 2^{2^{n^c}}/2$. On the other hand, $M$ makes at most $2^{2^{n^c}} 2^{n^c}$ queries across all its branches, a contradiction. Hence there is a choice of $z$ so that the fraction of random bits for which $M$ queries $(x,\mathtt{1},z)$ is less than 1/2. Flipping the value of $A$ on this string therefore affects the acceptance probability of $M$ by less than $1/2$.


Algebra and algebraic data types Which of the well-known structures of modern algebra (monoids, groups, rings etc) can be expressed as algebraic data types (ADTs)?

Presumably a free monoid can be considered to be isomorphic to the familiar Nil, Cons construction for lists. Can finitely-presented monoids be represented as an ADT?

If ADTs can't model structures having inverses, then is there a generalisation which can?

In my understanding, algebraic data types are basically types whose terms arise as the terms freely constructed by an algebraic specification: the operations of this specification being the term-constructors.

From this point of view, it seems to me that the only possible structures you can represent with algebraic data types are the free ones, that is those algebraic structures where no axiom is required: for instance magmas.

Observe that the fact you can represent free-monoids (that is monoids of strings/lists) as algebraic data types comes from the fact that lists are  ADTs for the algebraic specification with a $0$-ary operation (namely $\text{Nil}$ or $[]$) and a binary operation ($cons$ or $(:)$).

Until you work constrained in the setting of simple types you cannot add constraints (that is equations) in your data-types, hence you cannot represent more general algebraic structures.

A possible way to solve this problem is to use dependent type systems with an identity type: in these type-systems you can represent algebraic structures because equations(constraints) becomes terms (they are the same as programs).

Hope this helps.


Honest Majority unconditional coinflipping without private channels All communication is assumed to be by the parties

taking turns making authenticated broadcasts.

  Is there a way for $n$ parties, each with access to ideal local randomness, to jointly

  choose a member of  {0,1}  randomly with a distribution that is close to uniform

  even when a small subset of the parties are controlled by a computationally
  unbounded adversary who wants to make that distribution far from uniform?

Regardless of what $n$ is or what "a small subset" means,
the best I've been able to come up with is:

k = parameter
for i in range(k):
 each party outputs a random bit
 if number_of_zeros_outputted < number_of_ones_outputted:
  return 1
 if number_of_ones_outputted < number_of_zeros_outputted:
  return 0
return 0

What you are describing is called the common coin problem and has been introduced in [1]. One way to do this is to elect a leader and then let that leader flip a coin, for example, by using the lightest bin protocol[2].

Intuitively speaking, this works as follows:
We have $n$ processes (=parties) and choose $m=n/\log n$ bins.

In every round, every participating process chooses one of these $m$ bins uniformly at random and broadcasts this choice.
The bad processes get to choose after observing the choices of the good processes.
So at the end of a round every process knows exactly which process chose which bin. All processes that chose the lightest bin (i.e. the one with the fewest members) continue to the next round, while all others stop participating.

The trick is to keep the initial ratio of good processes to bad processes. How can the adversary try to prevent this? Clearly, the adversary's strategy is to make many bad processes survive until the next round, i.e., many bad processes are in the lightest bin. But since the good processes will be distributed almost uniformly among the bins, the adversary cannot place too many bad processes into the lightest bin, otherwise it will no longer be the lightest! (Once you have reached a constant number of participants you switch to $m=2$ bins.)

This protocol elects a good process as the leader with constant probability as long as a majority of processes is good, i.e., you will get an unbiased common coin with constant probability.

[1]: M. Ben-Or and N. Linial. “Collective coin flipping”.
In Advances in Computing Research, S. Micali, ed.,
vol. 5: Randomness and Computation, JAI Press,
Greenwich, CT, 1989, 91–115.

[2] Uriel Feige: Noncryptographic Selection Protocols. FOCS 1999: 142-153


Turbo codes and message passing I'm self-studying turbo codes for a graduate course in coding theory. I understood how turbo codes works by directly reading Berrou' paper and some of the following works on this topic. Given that, there is a simple question that i canno't answer with my self...
Turbo code relies on the fundamental principle of message passing during iterative decoding, more formally speaking the extrinsic information produced by one decoder is passed as a-priori information to the next (companion) decoder. This is my problematic point: why extrinsic information, that is an a-posteriori computation (given from the Log-likelihood-ratio) should be passed as an a-priori information the next decoder?

The LLR can be expressed as:
$$L(u_i)=\log\frac{P(u_i=1|\text{observation})}{P(u_i=0|\text{observation})}=\log\frac{p(obs.|u_i=1)}{p(obs.|u_i=0)}+\log\frac{P(u_i=0)}{P(u_i=1)}$$

What if the apriori knowledge of the source is known? For example...suppose a indipendent binary source, so that $P(0)=P(1)=1/2$. In this case there is no need to update the apriori knowledge because it is exactly equal to $0$, and extrinsic information is, in general, different from $0$, so the estimate is wrong at each step.

Thanks in advance

This is the 'guess' of the second decoder about what would be the a priori information in the above formula (to be used by the other first decoder).
And this exactly message passing of 'extrinsic' information is the major contribution of the French researchers.

Bytheway your formula has typo error, dominator/numerators are in the opossite way, please correct.


List of quantum-inspired algorithms Advances in quantum computing have led to the development of new classical algorithms. Notable recent examples are quantum-inspired algorithms for linear algebra:

A quantum-inspired classical algorithm for recommendation systems
Quantum-inspired classical algorithms for principal component analysis and supervised clustering
Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
Quantum-inspired sublinear classical algorithms for solving
low-rank linear systems

and for Max 3LIN:

Beating the random assignment on constraint satisfaction problems of bounded degree.

It may be very useful to compile a list of all known classical algorithms inspired from quantum computing. What other examples are known?

There's also a recent work on low-rank semidefinite programming that, though not based directly on a quantum algorithm, still uses the same quantum-inspired techniques.


Computational Library to compute Quantum Cluster States I want to write a simulator for a quantum computing model that I am working on and I was wondering what would be the correct library / implementation strategy to implement quantum cluster states? Specifically I want to compute a cluster state of a specific topological quantum computation. I am investigating algorithms using this model and I would like to have a toy implementation for a presentation.
The specific algorithm would perform similarly to this.

Encode the given knot algorithm into a set of braids and create a cluster state of those braids
Perform measurement on those braids
Return a element of $Z_{n} \in_{1,0}$
Perform a classical operation on the knot.
Perform another operation until the knot is in a desired state.

See http://arxiv.org/pdf/1101.4722.pdf for a very simlar model.

As Peter mentions in the comments, it seems impossible to give an authoritive answer without knowing what exactly you are planning on doing with them. That said, there are at least a few places I can point you which may be of some use.

Firstly, Pauli measurements on cluster states can be efficiently simulated on a classical computer. This is a direct result of the Gottesman-Knill theorem (see this paper by Gottesman and this follow-up paper by Gottesman and Aaronson), which Clifford group circuits can be efficiently evaluated via the stabilizer formalism. So it may be that stabilizers are the way you want to go.

However, if you want to be a little less general, and restrict yourself to graph states (a general name for cluster states on general graphs) then there are two papers by Hein, Eisert and Briegel and Schlingemann which describe how Pauli measurements performed on a graph state result in states which are locally equivalent to graph states, and provide rules for these transformations. Thus it is quite possible to work with graphs as your data structure, as long as you do not intend to leave the Clifford group.

Finally, Ross Duncan and Lucas Dixon have taken a category theoretic approach for automated reasoning about graphs and have produced some nice proof of concept software using this approach (see here).

Also, I would point out that Raussendorf, Harrington and Goyal have previously looked at implementing topological computations via measurements on cluster states (they use it to achieve fault-tolerance in cluster states in a very beautiful way), and so you might be interested in their work (see here and here). These papers give an explicit encoding for encoding braids in a cluster state.

UPDATE: I notice you have just added the forth point. The Raussendorf-Harrington-Goyal papers I linked to above do provide a very nice way of doing topological quantum computing via cluster states, which allows classical operations on the knots to be done within the Clifford group, and hence the stabilizer and graph transformation approaches I previously mentioned can be used to efficiently simulate these operations.


For efficient algorithm on "minimization" knapsack problem Suppose there are two arrays of positive numbers, $a[\cdot]$ and $b[\cdot]$, and value $B>0$. How to pick a set of indexes $I$, so that

$\sum_{i\in{I}}{b[i]}\geq{B}$

To minimize $\sum_{i\in{I}}{a[i]}$

I know this problem sounds like knapsack problem, but the objective is really to minimise, not maximise. Does this make a difference if I want to seek a polynomial-time, approximate algorithm?

There's a simple reduction from knapsack. Binary search for the solution to your knapsack instance, then solve the "dual knapsack" with that value as your covering constraint $B$. Compare the value given by the "dual knapsack" against your knapsack packing constraint, which gives you the direction to continue the binary search.

I think you can use the same rounding approach as the one for knapsack in order to get a PTAS for this problem. These notes notes should help you do it.


Integrality gap and approximation ratio When we consider an approximation algorithm for a minimization problem, the integrality gap of an IP formulation for this problem gives a lower bound of an approximation ratio for certain class of algorithms (such as rounding or primal-dual algorithm).  In fact, there are many problems whose best approximation ratio matches the integrality gap.

Some algorithm may have a better approximation ratio than the integrality gap for some problem, but I don't know if such an example exists or not.  If the answer is yes, could you give some examples?

I know that some problems admit multiple mathematical formulations.  In such cases, consider the mathematical formulation with the smallest integrality gap, as long as it can be solved in polynomial time (perhaps some formulations may use separation oracles).

This question is related to [the question: The importance of Integrality Gap].

There are various examples in which a semidefinite programming relaxation allows an approximation that is superior to known integrality gaps for linear programming relaxations.

For example, the standard linear programming relaxation of max cut has an integrality gap of 1/2, and this is true even for much more sophisticated linear programming relaxations (c.f. de la Vega-Kenyon and Schoenebeck-Trevisan-Tulsiani), but the Goemans-Williamson SDP algorithm has approximation .878...

The Leighton-Rao linear programming relaxation of sparsest cut has an integrality gap $\Omega(\log n)$, but the Arora-Rao-Vazirani SDP algorithm has approximation $O(\sqrt{\log n})$.

Perhaps less well known, Karloff and Zwick shows that using SDP one can approximate Max 3SAT, in the version in which clauses can have 1, 2 or 3 literals, within 7/8, while Goemans and Williamson had studied a linear programming relaxation that they used to prove a 3/4 approximation (Yannakakis had given 3/4 approximation earlier by other methods), and the Goemans-Williamson LP relaxation of Max 3SAT is easily seen to have integrality gap 3/4.


Multi-Terminal Cuts - Applications and Verifying validity of an approximation algorithm First thing first - I am not a CS guy. I am EE student (Systems and Signals). So it would help if you didn't use any big words :)

The Multi-terminal cut the input is a graph G and a subset T of its vertices. The task is to remove the minimum number of edges from G such that there is no path connecting any distinct vertices of T. Dalhaus et all showed that its NP-Hard for $k\ge 3$ for arbitrary.

Question - Why is this class of problem important? Do they show up in some engineering application.

A few years ago I found a simple algorithm proposed as an approximation of the Multi-terminal cut problem for arbitrary weighted slow-coherent graphs. (Strong connected components which are weakly connected with each other). I did a performance analysis of the algorithm from a linear algebra point of view and was able show that algorithm should be work for these classes of graphs.

I would like to take the algorithm and apply it to an application area and see how it fares compared to the "standard".

The multi-terminal cut problem (which is also known as the multiway cut problem) has many important applications. In the more general setting, each edge $e$ has a cost $c_e \ge 0$. The goal is to remove a minimum cost set of edges such that in the resulting graph there is no path between any two vertices in $T$. Here is an application in distributed computing.

Each vertex represents an object, and an edge $e$ of cost $c_e$ between them represents the cost of communication between the objects. The objects have to be partitioned to reside on $k$ different machines, with special object $s_i$ residing on the $i^{th}$ machine. The goal is to partition the objects residing on the $k$ machines in such a way that the communication cost between the machines is minimized.


Is the decidability of a language decidable? Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language?

Comments + answer say trivially the answer is yes; however, I'm wondering here would it be possible without the use of excluded middle to construct such a machine.

Sure.
There are Turing machines that always reject or always accept...
So, one of them is surely correct...


Savitch's use of measurability In Savitch's 1969 paper, "Relationships Between Nondeterministic and Deterministic Tape Complexities", he states that "all common storage functions L(n) >= lg n are measurable. In particular, any polynomial in n and lg n is measurable."  His definition of measurable is:  "A function L(n) is said to be measurable if there is some Turing machine with just one storage tape such that, given any input of length n, the machine will halt after a computation in which the storage tape head scans exactly L(n) squares."

So, my problem is, based on his definition, I don't understand why storage functions L(n) >= lg n would be measurable, while functions L(n) < lg n would not be.  Is this somehow implicit in his definition?  Or are there some publications that I should read?

I think that this definition is nowadays known under the term space-constructible function. There are functions in sublogarithmic space that are space constructible, while others are not.

http://dl2.acm.org/citation.cfm?id=31171 Andrzej Szepietowski: There are no fully space constructible functions between log log n and log n. Information Processing Letters 24(6),361-362.


Integer linear programming in logarithmic number of variables I read that integer linear programming is solvable in polynominal time if the number $n$ of variables is fixed, i.e. $n \in O(1)$. If the number of variables grows logarithmically, i.e. $n \in O(\log_2(N))$ for a given input of size $N$, is the problem still solvable in polynominal time or is this an open problem?

I can only give a partial answer to this question.

A result by Lenstra (later improved by Kannan, and Frank and Tardos) states that ILP with $k$ variables can be solved in time $k^{O(k)}$ (times a polynomial in the size of the ILP). Therefore, ILP is in P when the number of variables is $O(\log n/\log\log n)$. I am not sure if a $2^{O(k)}$ algorithm is known, or if such an algorithm would contradict the ETH.

I found this information in Daniel Lokshtanov's dissertation. Here are the relevant references.

H.W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8:538–548, 1983.
R. Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research, 12:415–440, 1987.
Andras Frank and Eva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7:49–65, 1987.


How to Create Mission Critical Software? I am self learning formal methods. I heard that formal methods is used (and usually only used) to create mission critical software (such as nuclear reactor controller, aircraft flight controller, space probe controller). That's why I am interested to learn it :p

However, after learning formal methods (especially LTL, CTL and their siblings), I feel that they can only be used to verify the correctness of the specification (safety, liveness, fairness, etc).

But then how to verify that the software (not only the specification) is indeed correct?

Disclaimer: I am a 90% idiot when it comes to theoretical computer science. So please be merciful while answering.

The question is rather broad.  To answer it in a reasonable space I will make many oversimplifications.

Let us agree on terminology.  A program is correct when it implies its specification.  This vague statement is made precise in many ways, by pinning down what exactly is a program and what exactly is a specification.  For example, in model checking the program is a Kripke structure and the specification is often an LTL formula.  Or, the program could be a list of PowerPC instructions and the specification could be a set of Hoare-Floyd assertions written in, say, first-order logic.  There are very many possible variations.  It is tempting to conclude that in one case (Kripke structure) we do not verify an actual program, while in the second case (list of PowerPC instructions) we do.  However, it is important to realize we really are looking at mathematical models in both cases, and this is perfectly fine.  (The situation is quite similar to physics where, for example, classical mechanics is a mathematical model of reality.)

Most formalizations distinguish between the syntax and the semantics of a program; that is, how it is represented and what does it mean.  The semantics of a program is what counts from the point of view of program verification.  But, it is of course important to have a clear way of assigning meanings to (syntactical representations of) programs.  Two popular ways are the following:

(small step) operational semantics: This is very much like defining a programming language by writing an interpreter for it. For this you need to say what is the state, and it is affected by each statement in the language.  (You may wonder in which language you write the interpreter, but I'll pretend you aren't.)
axiomatic semantics: Here each statement type comes with an axiom schema. So, roughly, whenever a particular statement of that type is used, it translates in being able to use certain axioms.  For example, the assignment ${\bf x}:={\bf e}$ comes with the schema $\{P[{\bf x}/{\bf e}]\}\,{\bf x}:={\bf e}\,\{P\}$; the particular assignment $x:=x+1$ comes with the axiom $\{x+1=1\}\,x:=x+1\,\{x=1\}$ if we instantiate the schema with $P=(x=1)$.

(There are others.  I feel particularly bad for omitting denotational semantics, but this answer is already long.)  Machine code plus operational semantics is pretty close to what most people would call a ‘real program’.  Here is a seminal paper, which happens to use operational semantics for a subset of the DEC Alpha machine code:

Necula, Lee, Proof-Carrying Code, 1996

Why would you ever use some higher-level semantics, like the axiomatic ones?  When you do not want your proof of correctness to depend on the hardware on which you run.  The approach then is to prove correctness of an algorithm with respect to some convenient high-level semantics, and then prove that semantics sound with respect to lower-level semantics that are closer to actual machines.

In summary, I could think of three reasons that led to your question:

You saw only high-level semantics that don't look like what you are used to call a program, and you wonder if there are low-level ones.  The answer is yes.
You wonder how you prove that a model corresponds to reality.  Like in physics, you don't.  You simply come up with better models and check them against reality.
You have not seen the distinction between syntax and semantics, and various ways to assign meanings to programs.  Two previous questions list some books.

This answer is merely trying to identify three different ways in which I understood the question.  Going deep in any of these points would require a lot of space.


Why is intuitionistic negation nonconstructive? Can someone simply describe why intuitionistic negation is

not constructive and why intuitionistic proof is constructive?

    in intuitionistic logic the notion of falsity has a 'subordinate' status,

    i.e. intuitionistic logic essentially rests upon a certain disparity between verification

    and falsification in favor of verification. Unlike intuitionistic truth, intuitionistic

    falsity is a non-constructive notion representing simply a non-truth of a sentence"

That is a part of paper entitle "Dual Intuitionistic Logic and a Variety of Negations:

The Logic of Scientific Research" by Yaroslav Shramko.

Intuitionistic negation is perfectly constructive, because $\lnot A$ is simply an abbreviation for $A \to \bot$ (i.e., "A implies false"). You may be thinking of the principle of double-negation elimination (i.e, $\lnot\lnot A \to A$). This principle is indeed nonconstructive.

The reason we call intuitionistic logic constructive is that existentials and disjunctions are "constructive". Concretely, this means that:

if you have a proof of $\exists x.\;A[x]$, then you can find a specific value $v$ such that $A[v]$ is provable.
if you have a proof of $A \vee B$, then you can either find a proof of $A$, or a proof of $B$

The axiom of the excluded middle is not constructive, because it asserts $A \vee \lnot A$ for any $A$, without giving a procedure for deciding which of $A$ or $\lnot A$ is provable.

Double-negation elimination lets you derive the excluded middle. This is because $\lnot\lnot(P \vee \lnot P)$ is derivable in intuitionistic logic. Here's a proof, given as a lambda-term:

f : ¬¬(P ∨ ¬P)
f : (((P ∨ (P → ⊥)) → ⊥) → ⊥ )
f = λk : (P ∨ (P → ⊥)) → ⊥.
     let g : P → ⊥ = λp:P. k (inl p) in
     let h : (P → ⊥) → ⊥ = λn : P → ⊥. k (inr n) in
     h g

We can combine this with double-negation elimination to conclude that $P ∨ ¬P$ holds generally. Hence it follows that double-negation elimination is not a constructive principle in general.


The Average-case Complexity of Simplex Algorithm I was wondering if there are any results on the average case complexity of the simplex algorithm. Let $A \in \mathbb{R}^{m \times n}$ be the matrix in the linear constraint.  I know that Smale did some work in the 80's that says that if we fix $m$, then the average complexity is linear in $n$ when $n$ goes to infinity.

However, by duality theory, $m$ and $n$ are symmetric in LP. Also in the 80's, Adler et al. showed that the expected number of pivots is quadratic in $\min \{ m, n\}$. (See ``A Simplex Algorithm Whose Average Number of Steps
Is Bounded between Two Quadratic Functions
of the Smaller Dimension '') And they even showed a quadratic lower bound.

I was wondering if there are any recent development on such average-case analysis.

The first thing that comes to mind is "Smoothed Analysis" of Spielman and Teng: arxiv.org/pdf/cs/0111050.pdf. Their main result is Theorem 5.0.1, which bounds the expected (over "typical instances") runtime of a version of the Simplex algorithm by a polynomial, though the degree of the polynomial is not stated there.


#P- vs PP-Completeness Suppose $A$ is any #P-complete problem. Now, $A$ is modified to obtain a decision problem $A'$ not by asking whether there is a solution but whether at least half of the potential solutions are actually true solutions. Question: Is $A'$ PP-complete?

This works if $A$ is #Sat, since MajSat is PP-complete. My approach so far: If $A$ is #P-complete, then there is a reduction from #Sat. So it should be possible to adapt this reduction to obtain a reduction from MajSat to $A'$. However, I ran into the problem that the reduction from #Sat to $A$ often requires a Turing (or Cook) reduction and it seemed far from clear how to obtain a many-one reduction from it.

Not necessary. Imagine the following Fake-#SAT problem: possible solutions are extended by one bit, and all vectors with this bit set are solutions. That is, the number of satisfying assignments for the new problem is $2^n+f$, where $f$ is the number of satisfying assignments for the original #SAT problem ($0\le f\le 2^n$).

The problem remains #P-complete; however, the corresponding "majority" problem (formulates as $\ge$ vs $<$) has always the answer "yes".


Low rank Log rank conjecture What is known about log rank conjecture in special situations of $O(\log N)$ rank $0/1$ matrix of size $N\times N$? Is there at least a conditional result showing better than $O(\sqrt{\log N})$ bound?

Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.


Reducing complexity with parallelism Is it possible (slash can you provide an example) to reduce computational complexity of a problem by using a parallel algorithm which does not require a number of processors relative to the input size?

If you mean O(1) processors, then no, computation complexity cannot be reduced.

Simply line up the work done by each processor and do it on a single one. If you are worried about synchronization, then one processor can easily emulate that.


Nonsingular regret bound for UCB Acer et al. "Finite-time Analysis of the Multiarmed Bandit Problem" show that the Upper Confidence Bound 1 (UCB1) algorithm has expected regret bounded by

$$\left[ 8 \sum_{i: \mu_i < \mu^\ast} \frac{\log n}{\Delta_i} \right]+ \left(1 + \frac{\pi^2}{3}\right) \sum_i \Delta_i$$

when run for $n$ steps, where $\mu_i$ are the means of the $K$ arms, $\mu^\ast = \max_i \mu_i$, and $\Delta_i = \mu^\ast - \mu_i$.

However, this bound explodes as any $\Delta_i \to 0$, i.e. when there a nearly optimal non-best arm.  Certainly the true expected regret does not go singular in this case (for any strategy), and intuitively I would expect UBC1 to do fairly well if there are several nearly optimal arms.

Question 1: Is there a nice regret bound for UCB1 which doesn't have this singularity?

Question 2: If no, is there a modified version of UCB1 with such a nonsingular bound?

You can improve this bound by grouping the arms into "almost optimal" arms (arms whose expected payoffs are within a fixed $\Delta$) and the rest of the arms.  So you can bound the regret contributed by the almost optimal arms by $O(T \Delta)$, which actually implies that the worst-case setting of $\Delta$ is approximately $\sqrt{N/T \log T}$, and not a value arbitrarily close to $0$.

This is explained, for example, in section 1.3 of these lecture notes.


Solving linear equations involving min Solve for $\alpha$ if solution exists:
$\min(r_1, s_1 \alpha_1) + \min(r_2, s_2\alpha_1) = d_1$,
where $r_1,r_2,s_1,s_2,d_1$ are integer constants.

One way seems to be enumerate all possible outcomes, e.g.,
$r_1 + s_2\alpha_1 = d_1$. However, for a larger problem ($\sum_{i=1}^{k} \min(r_i,s_i\alpha)$), enumerating all options becomes exponential. Is there a better way to reformulate this problem?

I assume the generalization you are thinking of is the following:

Given value $d$, and values $s_i$ and $r_i$ for $i = 1,2,...,k$, find (if possible) an $\alpha$ such that
$$\sum_{i = 1}^k\min(r_i, s_i\alpha) = d$$

Consider the expression $\min(r_i, s_i\alpha)$. This expression is sometimes equal to $r_i$ and sometimes equal to $s_i\alpha$, with a threshold between these two behaviors at $\alpha = \frac{r_i}{s_i}$.

Then consider the $k$ thresholds of this form for the $k$ different $\min(r_i, s_i\alpha)$ expressions. These thresholds separate the number line into $k+1$ sections. In each section, the behavior of each $\min(r_i, s_i\alpha)$ expression is known. Therefore, we can rewrite the expression $\sum_{i = 1}^k\min(r_i, s_i\alpha)$ for each section without the $\min$s. Then in each section we get an expression of the form $a+b\alpha = d$ which we can solve for $\alpha$; if in any section we find a value $\alpha$ that is both a solution to the equation in that section and a value within the section of the number line, then that $\alpha$ solves the whole problem.

Another way of thinking about this is in terms of your idea of trying every combination of which expressions the $\min$s evaluate to. If you do it by brute force, you have to try exponentially many cases, but using the idea of these threshold values it is possible to narrow down the possibilities to just $k+1$ cases.


What is the intuition behind linear logic? I'm trying to understand linear logic to understand linear type systems better. However, when I read the rules, I fail to get an intuition behind it as I've done in modal logic - $\Box A$ means $A$ is required as in Kripke frames $A$ is required for every reachable world [$\Diamond A$ is $A$ is possible mutatis mutandis]. But I cannot find any intuitive explanation for duality and which of conjunction / disjunction pairs (if any) corresponds to $\land$ and $\lor$.

I'm not sure this question is ideal for CSTheory, but given that it's already gathering upvotes, here is an  answer somebody might have given had the question  been posted on cs.stackexchange.

In order to understand linear logic's notion of duality $(\cdot)^{\bot}$,
which forces conjunction and disjunction apart much further than we are used to in conventional logic, I recommend
not
  to think of linear logic in terms of resources (although this is
  an important reading). Instead  think of linear logic formulae $A$
  as processes that communicate
  at a port / name / channel. This interpretation has been fleshed out first in (1) to the best of my knowledge, but it's already alluded to in Girard's original work. As a picture:

(I'm not sure how properly to center images here.)
Linear conjunction $A \otimes B$ is interpreted as running processes $A$
  and $B$ in parallel.  The process $A \otimes B$
  communicates pairs $(a, b)$ at its port, where $a$ comes from
  $A$ and $b$ is $B$'s communication.

Dualisation $(.)^{\bot}$ (which is linear logic's
  negation) switches input and output. Hence the dual of $A \otimes B$
  is

$$
  (A \otimes B)^{\bot} \quad = \quad A^{\bot} ⅋ B^{\bot}
  $$

In this reading $A^{\bot} ⅋
  B^{\bot}$ is the process that communicates with $A \otimes B$.

Linear logic's equivalent of disjunction can
  be given a similar process-theoretic reading. The formula

$$
  A\ \&\ B
  $$

should also be seen as  two processes $A$ and $B$ in parallel, but rather than actively sending messages, they wait for
  the environment to decide which to run. So $A \& B$ sits there,
  waiting on its channel for a bit of information which decides if $A
  \& B$ should run as $A$ or as $B$. This is a 'parallel' version of
  the $if/then/else$ in sequential programmaning languages. The dual
  $(A \& B)^{\bot}$ of $A \& B$ is

$$
  (A \& B)^{\bot} \quad = \quad A^{\bot} \oplus B^{\bot}
  $$

can be seen as a process sending 1 bit of information to $A \&
  B$, namely: "continue as $A$" or "continue as $B$". This is similar to in  $if\ true\ then\ P\ else\ Q$ evaluating to $P$ while
  $if\ false\ then\ P\ else\ Q$ evaluating to $Q$, except that
the choice between $A$ and $B$ is now made by the environment.

  The !-operator also has a process-theoretic interpretation: if $A$
  is read as a process, then $!A$ can be read as running infinitely
  many processes $A$ in parallel.

In this reading the axioms $A \vdash A$ of linear logic become simple 'wires' that forward messages from processes $A^{\bot}$ to processes $A$. This interpretation of axioms is already in Girard's proof nets (3).

This process-theoretic interpretation  has been influential and
  given rise to a lot of follow-up work like e.g. (2) for session types.
 Nevertheless, there are some
edge cases that make it a bit awkward, and to the best of my knowledge
  it hasn't been made to work perfectly for full linear logic even in 2017.

1. S. Abramsky, Computational Interpretations of Linear Logic.

2. P. Wadler, Propositions as sessions.

3. Wikipedia, Proof net.


Why is non-determinism (Push-down automata) necessary? I would like to know why for the recognition of context-free languages only non-deterministic push-down automata (DPA=NPDA) work. Why do deterministic push-down automata (DPDA) not recognize such languages?

I'm not quite sure which flavour of "why" you are looking for. One reason for the increase in power when allowing nondeterminism can be seen in the following example:

Let $L$ be the set of palindromes $w\bar{w}$ over some alphabet (of at least two symbols), where $\bar{w}$ is the reverse of $w$. An NPDA for this language can just keep pushing symbols onto its stack, and then at some point guess that it has reached the middle of the input and gradually empty the stack. Note that the acceptance condition is purely existential - it is enough that there is a correct guess for the word to be accepted.

A deterministic PDA would have to choose the position it considers the middle in some way that only depends on the current prefix. Assume $A$ is such a DPDA. For any $k\in\mathbb{N}$, let $u_k=ab^{2k}a$; let $v_0$ be the empty word, and $v_{k+1} = v_ku_kv_k$. This is a sequence of palindromes, each a prefix of the next, so that $A$ must be in an accepting state $q_k$, with the stack empty, after reading $v_k$. By the pigeon hole principle, there must be some $k,l$ such that $k\neq l$ and $q_k=q_l$ (there is a finite number of states, and so some must be 'reused' as there are an infinite number of $k$s). But then $A$ cannot distinguish $v_ku_kv_k$, which is a palindrome, from $v_lu_kv_k$, which isn't.


Max-weight connected & co-connected subgraph problem The max-weight connected subgraph problem (MWCS) may be described as follows:
given a simple graph $G=(V,E)$ and a weight function $w:V\to\mathbb{R}$, one
seeks for a subset $L\subseteq V$ for which the spanned subgraph $G[L]$ is
connected and $\sum_{v\in L}w(v)$ is maximal.

The MWCS problem is known to be NP-hard (see https://arxiv.org/abs/1409.5308).

Consider the following variation: in the same settings, one seeks for a vertex
set $L$ for which the spanned subgraphs $G[L]$ and $G[V\smallsetminus L]$ are
both connected, and $\sum_{v\in L}w(v)$ is maximal.

My question is the following: is it possible that this variation takes the
problem out from the NP class?  If not - is it easy to see that it is still
hard, given that the original problem is hard?

And does it make a difference if one asks
$\sum_{v\in L}w(v)-\sum_{u\in V\smallsetminus L}w(u)$ to be maximal?

Problem:
  Given a graph $G=(V,E)$ and a weight function $w:V\to\mathbb{R}$, find
  a partition of $V$ into two parts $V_1$ and $V_2$, so that $G[V_1]$ and $G[V_2]$ are connected and so that $w(V_1)$ is maximized.

This problem is NP-hard, as follows easily from the following paper:

  Pim van 't Hof, Daniël Paulusma, Gerhard J. Woeginger:
  Partitioning graphs into connected parts. Theor. Comput. Sci. 410(47-49): 4834-4843 (2009)

The paper shows that the following problem is NP-hard: Given a graph $G=(V,E)$ and two vertices $s,t\in V$, is there a "good" partition of $V$ into two sets $V_1$ and $V_2$, so that $G[V_1]$ and $G[V_2]$ are connected and so that $s,t\in V_1$.

Take such an instance, and make $w(s)=w(t)=1$ and $w(x)=0$ for $x\in V-\{s,t\}$. If there exists a good partition, you can reach $w(V_1)=2$.
If there is no good parition, the best you can get is $w(V_1)=1$.
(This argument shows NP-hardness, and also in-approximability within a
factor of $2-\epsilon$.)


Finding k nearest neighbors for all points If you have n points in 2d space, how quickly can you report the k nearest points to every point under Euclidean distance? If it helps speed things up we can ignore points that are more than some distance away as well so potentially return fewer than k. A randomized or approximate solution would also be interesting.

One solution is to build a kd tree and do an independent look up for every point. Is this as good as it gets?

$O(kn+n\log n)$. See

P.B. Callahan, S.R. Kosaraju, A decomposition of multidimensional
point sets with applications to k-nearest-neighbors and n-body potential ﬁelds, J. ACM 42 (1995) 67–90.

In some models of computation the $O(n\log n)$ part can be reduced or removed; see also

T. M. Chan, Well-separated pair decomposition in linear time?, Inf. Proc. Lett. 2008.


Membership testing in transformation monoids "Given a finite set $A$, a set of functions $S=\left\{f_{1}, f_{2}, \ldots, f_{k}\right\}$, each $A \to A$, and a candidate function $g:A \to A$, is $g$ in the monoid generated by $S$ with respect to composition?"

Kozen's paper "Lower bounds for natural proof systems" shows that this problem is PSPACE-complete. The following question is about his argument that the problem is in PSPACE.

He argues that it is easy to compute function composition if we represent the functions as bipartite graphs. Now we just guess a sequence of $f_{i}$s, compose them, and check whether it equals $g$. Thus, it can be done in nondeterministic linear space, and by Savitch's theorem, the problem is in PSPACE.

But is this really sufficient to see that the problem is in nondeterministic linear space? The representation of $g$ using terms from $S$ might itself be exponentially long. The paper concedes this just before definition 3.2.2, and is an otherwise interesting little fact about permutations (which are a special case of the system being considered) -- the order of a permutation over $n$ elements may be exponentially large in $n$ (See this).

The nondeterministic polynomial-space algorithm for this problem works as follows:

Initialize h: A→A to the identity mapping.
Is h=g?  If so, we found out that g is in the monoid generated by S; accept and halt.
Guess one element f∈S.
Update h to f∘h.
Go to step 2.

As you correctly pointed out, the sequence can be exponentially long in the input size, so this algorithm may take exponential time before accepting.

Note that the algorithm does not guess a whole sequence at once and store this sequence in the work space—doing so would require exponential space.