Simplification of Presburger formulas in practice I have formulas in Presburger arithmetic (with initial ∀, but I can apply quantifier elimination so they are quantifier-free) that are fairly complicated, yet, in many useful cases, are equivalent to very simple formulas such as conjunctions of simple arithmetic constrains (e.g. p>=-1, p<q, y>=q, y<n, n>=2 for a quantified formula taking up a whole screen page).

Is there any good simplification method for such formulas? (preferably in an off-the-shelf implementation)

Not knowing anything about the input problem, I suspect that if the blow up is coming from quantifier elimination of Presburger formulas. Cooper's algorithm can introduce a lot of redundancies and duplication during case splitting.
My suggestion comes from a trivial observation: Any tool that can find "very simple" Presburger formula also has to be able to find "very simple" pure boolean formulas. (Just encode each propositional variable $x_i$ with some trivial Presburger atom $s_i < 2$.)

BDDs are a fairly natural candidate for trying to get simple formulas (or at least unique wrt a variable order).
The closest work I am aware of to extending BDDs over Presburger is the Linear Decision Diagram (LDD) work of Chaki et al: slides and the project's homepage. Links to the papers are on the project's site.  This work combines linear real/rational arithmetic with BDDs.  The goal of this work was to have a compact representation in order to do Fourier-Motzkin quantifier elimination. Already LDDs do not try to be canonical, just "canonical enough".  The main idea is to add local conditions to eliminate certain kinds of redundancy during construction. These local conditions are things like: put the constraints on $x$ next to each other in the variable order, if $x < 5$, then $x<7$ always holds on the high branch, etc.  They do mention support for UTVPI constraints over integers in the paper and slides (like what you have above). The tool's API does not seem to support divisibility constraints coming from quantifier elimination or other more elaborate kinds of integer specific reasoning (gcd computations, conversion of $x < 2$ to $x \leq 1$, etc.)

If the formulas have a lot of propositional redundancy introduced by quantifier elimination, this might be a reasonable thing to look into.  (I doubt this includes all of the reasoning you used to get down to the smaller formulas so it might not work out of the box.) I've used tricks like BDDs + unate implications (eg. $x < 2 \implies x < 3$) to reduce Presburger formulas that were blown up by a different algorithm to "very simple" equivalent ones. But I did this for debugging purposes only. It has never made sense to stick what I did into a real implementation so I do not have a tool I can point you to. Good luck.


Is there any gradient descent based technique for searching absolute minimum (maximum) of a function in multidimensional space? I'm familiar with gradient descent algorithm which can find local minimum (maximum) of a given function.

Is there any modification of gradient descent which allows to find absolute minimum (maximum), where function has several local extrema?

Are there any general techniques, how to enhance an algorithm which can find local extremum, for finding absolute extremum?

I presume you are talking about unconstrained minimization. Your question should specify if you are considering a specific problem structure. Otherwise, the answer is no.

First I should dispel a myth. The classical gradient descent method (also called steepest descent method) is not even guaranteed to find a local minimizer. It stops when it has found a first-order critical point, i.e., one where the gradient vanishes. Depending on the particular function being minimized and the starting point, you may very well end up at a saddle point or even at a global maximizer!

Consider for instance $f(x,y) = x^2 - y^2$ and the initial point $(x_0,y_0) := (1,0)$. The steepest descent direction is $-\nabla f(1,0) = (-2,0)$. One step of the method with exact line search leaves you at $(0,0)$ where the gradient vanishes. Alas, it's a saddle point. You would realize by examining the second-order optimality conditions. But now imagine the function is $f(x,y) = x^2 - 10^{-16} y^2$. Here, $(0,0)$ is still a saddle point, but numerically, the second-order conditions may not tell you. In general, say you determine that the Hessian $\nabla^2 f(x^*,y^*)$ has an eigenvalue equal to $-10^{-16}$. How do you read it? Is it negative curvature or numerical error? How about $+10^{-16}$?

Consider now a function such as
$$
f(x) =
\begin{cases}
 1 & \text{if } x \leq 0 \\
\cos(x) & \text{if } 0 < x < \pi \\
-1 & \text{if } x \geq \pi.
\end{cases}
$$

This function is perfectly smooth, but if your initial point is $x_0 = -2$, the algorithm stops at a global maximizer. And by checking the second-order optimality conditions, you wouldn't know! The problem here is that some local minimizers are global maximizers!

Now virtually all gradient-based optimization methods suffer from this by design. Your question is really about global optimization. Again, the answer is no, there are no general recipes to modify a method so as to guarantee that a global minimizer is identified. Just ask yourself: if the algorithm returns a value and says it is a global minimizer, how would you check that it's true?

There are classes of methods in global optimization. Some introduce randomization. Some use multi-start strategies. Some exploit the structure of the problem, but those are for special cases. Pick up a book on global optimization. You will enjoy it.


Minimal-size extending set in a directed graph Let $G=(V,E)$ be a directed graph, i.e. $V$ is a finite set and $E\subseteq V\times V$.

We call a subset $J\subseteq V$ extending if for every $v\in V\setminus J$ there is a directed path from some vertex $j\in J$ to $v$.

Is there a polynomial-time algorithm to find an extending subset of minimal size?

There is a linear time algorithm.

Contract all strongly connected components, then you get a DAG.
Find all the source vertex in the DAG. For each source vertex in the DAG, pick a single vertex from the strongly connected component represented by the source vertex.


Alan Turing's Contributions to Computer Science Alan Turing, one of the pioneers of (theoretical) computer science, made many seminal scientific contributions to our field, including defining Turing machines, the Church-Turing thesis, undecidability, and the Turing test.  However, his important discoveries are not limited to the ones I listed.

In honor of his 100th Birthday, I thought it would be nice to ask for a more complete list of his important contributions to computer science, in order to have a better appreciation of his work.

So, what are Alan Turing's important/influential contributions to computer science?

I did not know of these until recently.

1) The LU decomposition of a matrix is due to Turing! Considering how fundamental LU decomposition is, this is one contribution that deserves to be highlighted and known more widely (1948).

2) Turing was the first to come up with a "paper algorithm" for chess. At that point, the first digital computers were still being built (1952).

Chess programming has had an illustrious set of people associated with it, with Shannon, Turing, Herb Simon, Ken Thompson, etc. The last two won the Turing Award. And Simom, of course, won the Nobel as well. (Shannon came up with a way to evaluate a chess position in 1948.)


Is there simple reduction Dominating Set to Vertex Cover? Is there simple reduction Dominating Set to Vertex Cover?

In the other direction the reduction is simple.

Searching the web returned blog.

It warns This is not finished yet and experiments suggest
the reduction doesn't work.

Added by "simple" I mean graph transformation
$G \to G'$, s.t. $G$ has DS of size $k$ iff $G'$
has VC of size $f(G,k)$ and the transformation
does not depend on $k$ (to avoid reduction to SAT).

How about the following transformation: Given a graph $G(V,E)$ with $V=\{1,\ldots,n\}$ construct $G'(V',E')$ as follows: $V'$ initially consists of two sets of vertices: the vertices $u_i, 1\le i\le n$ and the vertices $v_{i,j}, 1\le i,j\le n$ (a total of $n^2+n$ vertices). We add the following sets of edges: first, connect all $v_{i,j}$ with $v_{i,k}$ for $k\neq j$, so the graph now consists of $n$ cliques of order $n$ and $n$ isolated vertices. Next, for all $i$, connect $u_i$ with the vertex $v_{i,i}$. Then, for all $i$ connect $u_i$ with all vertices $v_{j,i}$ for which $(i,j)\in E$. On the other hand, for all $i,j$ such that $(i,j)\not\in E$ construct a new vertex $v'_{i,j}$ and connect it to $v_{i,j}$ (this constructs two new degree-1 vertices for each non-edge of $G$). This completes the construction.

The claim is that $G'$ has a vertex cover of size $n(n-1)+k$ if and only if $G$ has a dominating set of size $k$. The intuition is that any vertex cover must take at least $n-1$ vertices from each clique (giving at least $n(n-1)$ vertices overall), allowing us to select exactly $k$ of the $u_i$ vertices to represent the dominating set. The vertex that is left out of the $i$-th clique encodes the vertex of the original graph that was used to dominate $i$. Observe that the leaves $v'_{i,j}$ ensure that vertices corresponding to non-edges are not left out of the vertex cover.

Thus, the direction dominating set of $G$ $\to$ vertex cover of $G'$ is straightforward: select the vertices from $u_i$ that represent the dominating set and from each clique select all vertices except the one that is adjacent to a selected $u_i$. For the converse direction, first note that it is never optimal to take a $v'_{i,j}$ vertex in the vertex cover since these vertices have degree 1, so their neighbors must be selected. Second, observe that in any vertex cover that selects all $n$ vertices of a clique we can exchange one of them with its neighboring $u_i$ vertex, therefore we can assume that an optimal vertex cover selects $k$ such $u_i$ vertices. These must be a dominating set of $G$.


Why is the consensus problem so important in distributed computing? In distributed computing, the consensus problem seems to be one of the central topics which has attracted intensive research. In particular, the paper "Impossibility of Distributed Consensus with One Faulty Process" received the 2001 PODC Influential Paper Award.

So why is the consensus problem so important? What can we achieve with consensus both in theory and in practice?

Any references or expositions would be really helpful.

The paper you mention is important for 2 reasons:

It shows that there is no asynchronous deterministic consensus algorithm that tolerates even a single crash fault. Note that in the synchronous setting,there is a deterministic algorithm that terminates in $f+1$ rounds when $\le f$ processes crash.
It introduces bivalence and univalence of configurations (*), which are used in many lower bounds and impossibility proofs later on.

Applications

One important application of the consensus problem is the election of a coordinator or leader in a fault-tolerant environment for initiating some global action. A consensus algorithm allows you to do this on-the-fly, without fixing a "supernode" in advance (which would introduce a single point of failure).

Another application is maintaining consistency in a distributed network: Suppose that you have different sensor nodes monitoring the same environment. In the case where some of these sensor nodes crash (or even start sending corrupted data due to a hardware fault), a consensus protocol ensures robustness against such faults.

(*) A run of a distributed algorithm is a sequence of configurations. A configuration is a vector of the local states of the processes. Each process executes a deterministic state machine. Any correct consensus algorithm must eventually reach a configuration where every process has decided (irrevocably) on the same input value. A configuration $C$ is $1$-valent if, no matter what the adversary does, all possible extensions of $C$ lead to a decision value of $1$. Analogously, we can define $0$-valency. A configuration $C$ is bivalent if both decisions are reachable from $C$ (which one of the two is reached depends on the adversary). Clearly, no process can have decided in a bivalent configuration $C$, as otherwise we get a contradiction to agreement! So if we can construct an infinite sequence of such bivalent configurations, we have shown that there is no consensus algorithm in this setting.


Hardness of 3-dimensional matching variant I am thinking about a variant of 3-dimensional matching. In normal 3d matching, we have three sets of vertices $X$, $Y$ and $Z$, and a set of edges $E \subseteq X \times Y \times Z$. We want to choose a matching $M \subseteq E$ of maximum size.

I would like to instead choose $M$ from the set $E \cup \{(x,w) \bigm| \exists z: (x,w,z) \in E \vee \exists y: (x,y,w) \in E\}$. So for each triple in $E$, assume that choosing a pair with the first and second elements or a pair with the first and third elements to be part of $M$ would also be acceptable. (Note that a pair with the second and third elements is not allowed.) The question is if there a matching $M$ that covers every element in $X \cup Y \cup Z$ exactly once.

I was wondering whether this problem is still hard. The Garey & Johnson proof of NP-hardness of 3d matching seems to break down; if $M$ is chosen as specified above, the gadget for the variable doesn't work anymore.

EDIT (Aug 1):

I posted a small report with a more detailed proof on my blog; the reduction idea is the same, but the "gadget" used are better explained (you can also directly download the pdf from here)

The problem seems NP-complete and this is a possible reduction from SET COVER.

Suppose you have an universe $A$ of $n$ elements: $A = \{a_1,...,a_n\}$, a collection of $m$ subsets $\mathcal{S} = \{S_1,S_2,...,S_m\}$ (with $S_i \subseteq A$) and an integer $k$. The SET COVER problem asks for a sub-collection $\mathcal{C} \subseteq \mathcal{S}$ of size at most $k$ such that $\bigcup_{S_i \in \mathcal{C}} S_i = A$ (with $|\mathcal{C}| \leq k$).

The reduction to your problem (I call it 3DM-relaxed, 3DMR) can be done in the following way.

The subsets $S_i$ are simulated using one or more elements of the set $X$, the elements of the universe $A$ are simulated using elements of the sets $Y$ and $Z$ ($a_{2j}$ is simulated with an element $y_{a_{2j-1}}$ of $Y$, $a_{2j-1}$ is simulated with an element $z_{a_{2j}}$  of $Z$).

We start with $X = \{ e_1,e_2,...,e_{k} \}$ that will force the $|\mathcal{C}|=k$ constraint.

Then, for every subset $S_i$ we create the triple: $(x^1_{S_i}, y_{S_i}, dum)$, where $dum$ is a new element of $Z$; and add the $k$ triples:
 $(e_1,y_{S_i}, dum),(e_2,y_{S_i}, dum),...,(e_{k},y_{S_i}, dum)$

Note that all $dum$ elements are distinct!

In this way at most $k$ of the $x^1_{S_i}$ will be "free" to cover the elements representing the $a_j$: indeed the $(e,\cdot,\cdot)$ triples can include at most $k$ of the $y_{S_i}$, the remaining $m-k$ must be included by the corresponding $(x^1_{S_i},\cdot,\cdot)$ triple.

To link the $x^1_{S_i}$ to the elements $y_{a_{2j}}, z_{a_{2j-1}}$ that correspond to the elements of the universe in $S_i$, we add three bridge triples:
$(x^1_{S_i},y_{B_i},z_{B_i})$,
$(x^2_{S_i},y_{B_i},dum)$,
$(x^3_{S_i},dum,z_{B_i})$

At this point the elements of $A$ can be linked to $x^2_{S_i}$ and $x^3_{S_i}$ (or we can further extend the capacity of $S_i$ adding more bridge triples).

For example adding the triples:

$(x^2_{S_i},y_{a_2},z_{a_1}), (x^3_{S_i},y_{a_4},z_{a_3})$ we simulate the set: $S_i = \{ a_1, a_2, a_3, a_4\}$.

The fundamental point is that if $x^1_{S_i}$ is "used" to cover the element $y_{S_i}$ (blue edges in the figure) then:

$x^2_{S_i}$ must be used to include element $y_{B_i}$ and cannot be used to include elements $y_{a_2}, z_{a_1}$ (red edges in the figure);
$x^3_{S_i}$ must be used to include element $z_{B_i}$ and cannot be used to include elements $y_{a_4}, z_{a_3}$ (red edges in the figure).

Some of the $S_i$ included in the cover can have a  non-empty intersection; so we must be sure that two distinct $x^p_{S_i}, x^q_{S_j}$ that are linked to the same element $a_i$ (i.e. we have the triples $(x^p_{S_i}, a_i, \cdot), (x^q_{S_j}, a_i, \cdot)$) can be included in the matching. For this purpouse for every $x^p, p > 1$ we add a triple with two dum elements: $(x^p, dum, dum)$ (green edges in the figure below).

Finally we can add as many distinct triples $(x, y, dum_i), (x, dum_j, z)$ as needed to be able to garbage collect all the dum elements $dum_i \in Z$ and the dum elements $dum_j \in Y$ (otherwise the would not be included in the matching) if they are left alone.

Also note that if there are too many $S_i$, the elements $e_i$ can be included in the matching using their $z_{dum}$ element in $Z$ (only the pair $(e_i, z_{dum})$ is picked).

The resulting 3DMR instance has a solution if and only if there is an set cover $\mathcal{C}$ of $A$ of size at most $k$.

In the figure a triple $(x,y,z)$ is represented with two edges $(x,y),(x,z)$ of the same color. As an example, if $x^1_{S_1}$ corresponding to $S_1 = \{a_1,a_2,a_3,a_4\}$, must be used to include $y_{S_1}$ (blue edges), then it cannot be used to include the elements $z_{a_1},y_{a_2},z_{a_3},y_{a_4}$ (red edges).


NP-hardness of a special case of Number Partitioning Consider the following problem,

Given a set of $n = k m$ positive
numbers $\{ a_1, \dots, a_n \}$ in
which $k \ge 3$ is a constant, we
want to partition the set into $m$
subsets  of size $k$ so that the product of the
sum of each subset is maximized.

The problem is quite similar to the well known $m$-way number partitioning except we have a limit on the number of numbers in each partition.
For $k = 2$ the following simple polynomial algorithm can be proposed,

assume the numbers are sorted, i.e.
$a_1<a_2<...<a_n$. Then, for $i≤m$ assign $a_i$
to the subset $i$, for $i>m$, assign it
to the subset $n−i+1$.

It's not hard to see why the algorithm works. Just pick two arbitrary bins. Any swap in the numbers will not increase the amount of the product.

But for larger $k$'s, I'm wondered if the problem can be solved in polynomial time or not? I'd be also thankful if somebody can show it's np-hardness.

Note: I encountered the problem while I was working on a scheduling problem in wireless networks. I found a good heuristic algorithm to solve the problem. But after a while I thought the problem might be theoretically interesting.

(This is a little more detailed version of my comments on the question.)

As turkistany suggested in a comment on the question, this problem is NP-hard for every constant k≥3 by a reduction from the k-partition problem.  The reduction does not change instances at all: just note that the maximum of the product of the sums is at least (∑ai/k)m if and only if the numbers can be partitioned into m sets each with size k whose sums are all equal.

Note that the input to the k-partition problem is usually defined to be km numbers which may not be all distinct, and this is essential in the standard proof of its NP-completeness (such as the one in Garey and Johnson).  Therefore, the reduction above only proves the NP-hardness of a slight generalization of the current problem where the input is allowed to be a multiset instead of a set.  However, this gap can be filled because the k-partition problem remains NP-complete even if the numbers in the input are required to be all distinct; see [HWW08] for the case of k=3 (see also Serge Gaspers’s answer to another question), which can be modified easily for larger values of k.

In addition, everything stated here remains NP-complete/NP-hard even when the numbers in the input are given in unary.

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger.  Multigraph realizations of degree sequences: Maximization is easy, minimization is hard.  Operations Research Letters, 36(5):594–596, Sept. 2008.  http://dx.doi.org/10.1016/j.orl.2008.05.004


How tight is the XOR lemma? The XOR lemma states that if you have a distribution $D$ on $\{0,1\}^n$, and all the Fourier coefficients of $2^n D$ are small, then it is close in $L_1$ to the uniform distribution. Specifically, suppose all Fourier coefficients are at most $\epsilon$.

The argument is a simple application of Cauchy—Schwarz with the fact Fourier preserves the $L_2$ norm to obtain:

$$|U-D|_1 \leq 2^{n/2} \epsilon$$

How tight is this? I obviously care about the exponent of $2$, not a constant outside.

I was a certain a 'probabilistic' $D$ would show tightness but that doesn't seem to be the case. Below is an explanation:

Consider generating $D$ as follows: let $D(x)$ be $\frac{1}{2^n} + z(x)\frac{\epsilon}{2^{n/2}}$ where $z(x)$ is iid on $\{-1,1\}$.

Even if we ignore this is probably not a distribution (I'm trying to point here that a probabilistic construction seems to fail so that's okay.) , this can't be turned into a tight example since there are so many Fourier coefficients, one of them will correlate significantly more in signs than the random $2^{n/2}$ with our $z$, and then we'll get more than $2^{n/2} \frac{\epsilon}{2^{n/2}}$.

Thus tightness if it exists needs to come from a controlled pseudorandom construction.

EDIT-
As clement posted in a comment, bent functions are apparently a thing and clearly solve our tightness.

First notice that if $f,g$ are each bent functions on a different set of variables, then so is $fg$. Thus if there is one for $m,n$ variables, there is one for $m+n$.

Now consider $1/2-1/2x+1/2y+1/2xy$, it's a bent function in two varibles, so tensoring gives for any even $n$ gives a bent function.

Instead of choosing $z\in\{-1,1\}^{2^n}$ uniformly at random, you may want to look instead at more structured (yet "pseudo-random"-ish) functions such as bent functions:

  Definition. A Boolean function $f\colon\{-1,1\}^n\to\{-1,1\}$ is called bent if $|\hat{f}(S)|=2^{-n/2}$ for all $S\subseteq [n]$.

Such functions are known to exist; see, e.g., Chapter 6.3 of Ryan O'Donnell's Analysis of Boolean functions (2014) (or the online version).


Is this variant of PAC learning known? Here is a problem I've never seen, in a model similar to the PAC model. It asks a similar question to PAC learning, but wishes to optimize, rather than learn. I wonder if this problem is known, has any name, or has ever been solved.

Input: A Random Oracle to function $f:[0,1]^n \rightarrow [0,1]$ from a concept class $C$. Additionally, $n$ points $x_1,\ldots,x_n$ in the domain.

Goal: Select an $i$ such that $E[f(x_i)]$ is as large as possible. We assume the function $f$ is randomly distributed amongst all functions in the class $C$ that agree with all the samples we have drawn.

One way to solve this problem is to draw many samples from $f$, create a hypothesis $h$, and choose the $x_i$ whose $h(x_i)$ is largest. There are two problems with this:

$h$ might not be representative of the set of all $f$'s that agree with the samples we've drawn.
To solve our problem it is not clearly necessary to learn $f$: for some classes $C$ might be a more efficient way to select a good $i$ without trying to learn $f$.

An example setting is where $C$ is the set of linear classifiers. In that case it should probably be quite easy to solve the problem. But what about other, more complicated classes?

The real version I'm interested in is that of agnostic learning of linear functions? we assume the function $f$ is somewhat correlated with a linear function, and the goal is to choose an i which maximizes $E[f(x_i)]$ to the best of our ability.

What you describe is a non-stochastic version of the "functional multi-arm bandit problem": you know you have an unknown function from some class C (does not have to be randomly selected), and you have query access to this function. The goal is to find the element which maximizes the function. As you say, depending on the class C, this may or may not require learning the function.

This paper by Amin, Kearns, and Syed exactly characterizes the query complexity of the problem: http://www.cis.upenn.edu/~mkearns/papers/haystack.pdf


Dynamic all-pairs shortest paths - O(1) query I'm trying to come up with an algorithm to solve all-pairs shortest paths (APSP) problem in dynamic directed planar graph with nonnegative real weights. Additionally:

My primary focus is to achieve lowest possible query time ($O(1)$ would be perfect), it's the most important thing for me, this operation will be done very often (of course the price will be increased memory consumption, but I'm fine with that),
Graph is fully dynamic - both edges & vertices can be added/deleted - it would be nice if I didn't have to recompute everything from scratch,
$|V| = 10000$ (approximately).

I've search the Internet and skimmed through lots of articles, but didn't find anything that matched perfectly my case.

Any help and/or links would be highly appreciated.

theory results:

exact:

Jittat Fakcharoenphol, Satish Rao: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5): 868-889 (2006)

approximate:

Ittai Abraham, Shiri Chechik, Cyril Gavoille: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. STOC 2012: 1199-1218

Philip N. Klein, Sairam Subramanian: A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica 22(3): 235-249 (1998)

implementation for road networks:

Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato Fonseca F. Werneck: Customizable Route Planning. SEA 2011: 376-387

(updates only to cost of edges, might be possible to extend to addition and deletion of edges)

comment

none of the methods above achieves O(1) query time

note that if you use lots of space for a data structure, it probably means that you will need significant time to update the data structure in case the graph changes
(low query time at the cost of high update time)

if updates are rare, it might be worth it.
what is the application?


More efficient non-uniform derandomization ? Adleman, FOCS'78 showed that any randomized circuit for inputs of length $n$ can be non-uniformly derandomized. However, the construction effectively duplicates the original circuit  $O(n)$ times, so the derandomized circuit is larger than the original one by a factor of $O(n)$. Is there any more efficient construction out there that multiplies the circuit size by a smaller factor  ?

I don't think something much better is known.  Because for example, if it were possible to derandomize circuits with only a sublinear blowup, then I think it would also be possible to non-trivially (but non-uniformly*) derandomize communication protocols.  And I don't believe the latter is known.  Adleman's proof gives a linear blowup as you say, so that the derandomization of communication protocols is trivial because it would give a linear blowup in the communication complexity.

*: By "non-uniform" in the context of communication protocols, I mean the algorithm for the two parties to compute the next bit to send to the other is not explicit.  I recall reading a discussion about this in some paper, but I can't seem to find a reference now...


What is a totally ordered sort of sets of a partial order called? Given a DAG, which can represent a partial order and has at least one topological sort.

For example the graph

  >B
 /  \
A    >D
 \  /
  >C

has two topological sorts "ABCD" and "ACBD".

My question is the following:
Is there a name for the following total order sort of sets:

S:  ( {A} , {B,C} , {D} )

The inductive definition is similar to constructing a topological sort:

Put the all the graph minima (nodes with no input edges) in set #i S: ( {A} )
Remove the graph minima from the graph.  G:= G \ {A}
repeat step 1. with i := i+1 as long as the graph is non-empty

I find this in several computer science domains. For example method selection in CLOS (Common Lisp), a parallel scheduler of a DAG where nodes are tasks and edges dependencies, the list of all enabled sets in dataflow or petri-net model executions, etc.  I haven't found a single nomenclature or even a reference for it though.  It sounds simple and pervasive enough to merit one.

In the context of geometric dominance orders, the standard term is "layers of maxima" (in your case, minima). Obviously, the same term can be used for any partial order.

http://dx.doi.org/10.1007/11785293_34

http://dx.doi.org/10.1007/s00453-004-1082-5


Extractors in Practice: How to Determine the Min-Entropy in the Source Distribution One of the main parameters in the construction of extractors is $k$, the min-entropy of the source distribution. In practice, suppose we want to extract randomness from a given source $S$. How do we determine $k$ in this source $S$? More generally, how do we quantify the amount of (extracted) randomness in the output distribution of the extractor.

In practice, if you want to extract randomness from a source $S$, you don't use an extractor.  Instead, you use a cryptographic hash function and hash the data from the source.  (This is how cryptographic-strength pseudo-random number generators distill randomness from many non-uniformly distributed sources of randomness.)  This can be proven safe in the random oracle model.

Of course, if you care mostly about theoretical bounds, extractors are better because they provide provable bounds without requiring cryptographic assumptions, so theoretical work will naturally focus on extractors -- but if you want to do this in practice, that consideration is less important.  If you want to do this in practice, I recommend you use a cryptographic hash function, as the assumptions are reasonable and you get something that does not waste any entropy.  (And before you reject the idea of depending upon cryptographic assumptions: Hey, if it's good enough to protect e-commerce and banks and classified documents, it's probably good enough for your purposes.)

If you use a cryptographic hash function, the bottom line (essentially) is that all of the entropy of the source is preserved (up to the security level of the cryptographic hash function).  So, quantifying the amount of extracted randomness comes down to quantifying how much randomness is present in the source.

There is no good black-box way to determine the min-entropy of the source distribution.  So, in practice, you don't try to determine the min-entropy of a source through observational methods (e.g., observing many samples and then doing something).  Instead, you need to have a model of how the source works, and to derive estimates of its entropy based upon that model.  That model might be based upon the physics of the source or other domain-specific assumptions.  This is not a question that algorithms can help you with much.

Why is it hard to estimate the min-entropy of a source?  Consider two sources: $S_1$ outputs a random $1000$-bit value $x$ (distributed uniformly at random); $S_2$ picks a random $128$-bit value $k$, then uses AES in CTR mode (a secure pseudorandom generator) to stretch $k$ to a $1000$-bit value $y$, and outputs $y$.  Notice that, assuming AES is secure, there is no feasible way to distinguish source $S_1$ from source $S_2$ by just observing their outputs: any algorithm for distinguishing the two sources would require something like $2^{128}$ steps of computation.  However, the min-entropy of $S_1$ is very different from the min-entropy of $S_2$ ($1000$ bits vs $128$ bits).  This example shows that computing the min-entropy of a source is a difficult in general, so you should not expect to find any efficient algorithm to do that for you based solely on observing some outputs from the source.

For a more rigorous treatment of the complexity of estimating the min-entropy, see e.g. the following paper:

The Complexity of Estimating Min-Entropy.  Thomas Watson.  CC 2015.

The bottom line is that it's hard.  (Thanks to epsfooling for pointing me to this paper.)

The literature on cryptographic pseudorandom number generators has lots more on this topic.


Research on call-site based type inference? I'm trying to learn more about whole-program type checking and type inferencing systems that use information from function call sites to compute type information (in addition to the standard approach of using the function body). For example, such an algorithm might use a function call like foo(1) to infer that the function in foo takes integer arguments. Obviously this would complicate inference a lot and make the check non-modular.

Anyway, I haven't had much luck finding any research on this approach, probably because I don't know the correct terminology to describe what I'm talking about. Any pointers?

Almost all systems with type inference use call-site information to do this.  Examples include Standard ML, OCaml, F#, and Haskell.  Many other languages use call-site information to infer type parameter instantiation, such as Java, C#, Scala, and Typed Racket.  This often goes by the name "Local Type Inference".

I would just describe what you're looking for as "Type Inference", and you should probably start by looking up what's commonly known as the "Hindley-Milner" system.  The Wikipedia page gives a reasonable introduction, and pointers to the original papers.

The place to start for Local Type Inference is Pierce and Turner's original paper, best read in the TOPLAS 2000 version (ACM, PDF).


Why does predecessor(zero) need to be zero in Church numerals? My question may be similar to: Why naturals instead of integers?, but it is more specific.

I am trying to learn lambda calculus. All the books make a big deal about how it was necessary that predecessor(zero) == zero and it was very tricky to get it right.

Why was that necessary? Can someone point me to some literature, or, better yet, give me a 30 sec explanation?

The only thing I can figure out is that this resulted in the naturals being closed under subtraction, but at a cost of having subtraction being a non one-to-one mapping from the natural numbers to themselves.

Thanks,

Charlie

The other reason (than the one already stated) for pred 0 = 0 are the (all too often unstated) requirements that

pred be a total function from nat to nat
pred succ n = n be true.
pred be as close to injective as possible.
pred be as close to a monotone decreasing function as possible.

It is that last requirement which really 'seals the deal' in forcing pred 0 = 0, since that is the choice which minimizes the distance to not being monotone decreasing.


Special properties of bipartite expanders It is well known that expanders, and often the special case of bipartite expanders, have found many uses in derandomization, coding, etc.

However, I am curious if there are any special properties of bipartite expanders that more general families of expanders don't have (or vice versa). In particular, are there any extreme differences, where bipartite and non-bipartite expanders differ greatly (especially in a combinatoric, algorithmic, or complexity-theoretic sense)?

A priori, we might expect that bipartite and non-bipartite expanders would likely share many pseudorandom properties, and in fact are constructible from each other. So that would suggest a negative answer to this question.

On the other hand, bipartite graphs in general have many special properties (eg. König's theorem) that have complexity-theoretic implications. So it's not unreasonable to think that differences between random bipartite and non-bipartite graphs may yield interesting differences between bipartite and non-bipartite expanders.

This is sort of a vague, open ended question, since I'm not exactly sure what kind of answer I'd like, and I am open to any interpretation. However, an example of a 'non-answer' might be 'bipartiteness is distinguished by the smallest eigenvalue in the spectrum'; I'm more interested in specifically bipartite expanders rather than spectral properties of bipartite graphs as a whole.

Two things come to mind when I hear "bipartite expanders"

The only proof we have about existence of Ramanujan expanders at every size is through bipartite expanders. The "Interlacing families" construction of Marcus-Spielman-Srivastava effectively settles for the case of bipartite graphs what has been conjectured by Bilu and Linial to be true for all graphs - that every graph has a Ramanujan $\mathbb{Z}_2$ signing. [http://arxiv.org/abs/1304.4132]
The work by Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson about how entropy can help understand the construction of optimal lossless expanders and zig-zag product seems to be essentially focussed on bipartite expanders. [ http://dash.harvard.edu/bitstream/handle/1/3330492/Vadhan_CondLosslessExpanders.pdf?sequence=2 ][ http://arxiv.org/abs/math/0406038  ]

Seems all optimality results about expanders are about when they are bipartite? May be this is because somehow our technologies are more tuned to control the upper edge of graph spectrum and only with bipartiteness does it imply something for the whole. (MSS result can in principle be generalized for a larger class of expanders but this larger class is not as conveniently describable)


How many disjoint edge-cuts a DAG must have? The following question is related to the optimality of the Bellman-Ford $s$-$t$ shortest
path dynamic programming algorithm (see this post for a connection). Also, a positive answer would imply that the minimal size of
a monotone nondeterministic branching program for the
STCONN problem is $\Theta(n^3)$.

Let $G$ be a DAG (directed acyclic graph)
with one source node $s$ and one target node $t$.
A $k$-cut is a set of edges, whose removal destroys all $s$-$t$ paths
of length $\geq k$; we assume that there are such paths in $G$.
Note that shorter $s$-$t$ paths need not be destroyed.

Question:
Does $G$ must have at least (about) $k$ disjoint $k$-cuts?

If there are no $s$-$t$ paths shorter than $k$, the answer is YES, because
we have the following known min-max fact (a dual to
Menger’s theorem) attributed to Robacker$\ast$.
An $s$-$t$ cut is
a $k$-cut for $k=1$ (destroys all $s$-$t$ paths).

Fact:
In any directed graph, the maximum number of edge-disjoint $s$-$t$ cuts is equal to the minimum length of an $s$-$t$ path.

Note that this holds even if the graph is not acyclic.

Proof:
Trivially, the minimum is at least the maximum, since each $s$-$t$
path intersects
each $s$-$t$ cut in an edge.
To see equality, let $d(u)$ be the length of a shortest path from $s$ to $u$.
Let  $U_r=\{u\colon d(u)=r\}$, for $r = 1,\ldots, d(t)$, and
let $E_r$ be the set of edges leaving $U_r$.
It is clear that the sets $E_r$ are disjoint, because the sets $U_r$ are such.
So, it remains to show that each $E_r$ is an $s$-$t$ cut.
To show this, take an arbitrary $s$-$t$ path $p=(u_1, u_2, \ldots,u_m)$
with $u_1=s$ and $u_m=t$. Since $d(u_{i+1})\leq d(u_i)+1$, the sequence
of distances $d(u_1),\ldots,d(u_m)$ must reach the value
$d(u_m)=d(t)$ by starting at $d(u_1)=d(s)=0$ and increasing the value by at
most $1$ in each step. If some value $d(u_i)$ is decreased , then we must
reach value $d(u_i)$ latter. So, there must be a $j$ where a jump
from $d(u_j)=r$ to $d(u_{j+1})=r+1$ happens, meaning the edge $(u_j,u_{j+1})$
belongs to $E_r$, as desired. Q.E.D.

But what if there are also shorter (than $k$) paths? Any hint/reference?

$^{\ast}$
J.T. Robacker, Min-Max Theorems on Shortest Chains and Disjoint Cuts of a Network,
Research Memorandum RM-1660, The RAND Corporation, Santa Monica, California, [12 Jan-
uary] 1956.

EDIT (a day later): Via a short and very nice argument,
David Eppstein answered the original question
above in negative: the complete DAG $T_n$ (a transitive tournament) cannot have more than four disjoint $k$-cuts! In fact, he proves the following interesting structural fact, for $k$ about $\sqrt{n}$. A cut is pure if it contains no edges incident to $s$ or to $t$.

Every pure $k$-cut in $T_n$ contains a path of length $k$.

This, in particular, implies that every two pure $k$-cuts must intersect! But perhaps there still are many pure $k$-cuts that do not overlap
"too much". Hence, a relaxed question (the consequences for STCONN would be the same):

Question 2:
If every pure $k$-cut has $\geq M$ edges, does then the graph must have
about $\Omega(k\cdot M)$ edges?

The connection with the complexity
of STCONN comes from the result of Erdős and Gallai that one has to remove all but $(k-1)m/2$ edges from (undirected) $K_m$ in order to destroy all paths of length $k$.

EDIT 2: I now asked Question 2 at mathoverflow.

Short answer: no.

Let $G$ be a complete DAG (transitive tournament) on $n$ vertices with $s$ and $t$ its source and sink, and let $k=\sqrt{n/3}$. Observe that there can be at most four disjoint cuts that contain more tham $n/3$ edges incident to $s$ or more than $n/3$ edges incident to $t$. So, if there are to be many disjoint cuts, we can assume that there exists a cut $C$ that does not contain large numbers of edges incident to $s$ and $t$.

Now let $X$ be the complete subgraph induced in $G$ by the set of vertices $x$ such that edges $sx$ and $xt$ do not belong to $C$. The number of vertices in $X$ is at least $n/3$, because otherwise $C$ would touch too many edges incident to $s$ or $t$. However, $X\setminus C$ cannot contain a $k$-path, because if such a path existed it could be concatenated with $s$ and $t$ to form a long path in $G\setminus C$. Therefore, the longest-path layering of $X\setminus C$ has fewer than $k$ layers, and has a layer containing more than $(n/3)/k=k$ vertices. Since this is a layer of the longest path layering, it is independent in $X\setminus C$, and therefore complete in $C$, so $C$ contains a path $P$ through the vertices of this layer, of length $k$. This path must be disjoint from all of the other cuts.

Every cut that is not $C$ must contain either the edge from $s$ to the start of path $P$ or the edge from the end of path $P$ to $t$, or else it would not block the path $s$–$P$–$t$. So if $C$ exists, there can be at most three disjoint cuts. And if $C$ does not exist (that is, if all cuts cover more than $n/3$ edges incident to $s$ or to $t$) there can be at most four disjoint cuts. Either way, this is a lot fewer than $k$ cuts.


Smooth Complexity of the Nonnegative Permanent There has been fantastic work done on the Permanent going on for the last two decades.I have been wondering for a while about the possibility of a Smooth P algorithm for the Permanent of Nonnegative Matrices. There is of course the famous JSV algorithm but this is a fpras. Thinking about other work within Smoothed Complexity, a strong hint of being in Smoothed P was the existence of a fpras / Psuedopolynomial algorithm.

Are there any obstructions to the Nonnegative Permanent being in Smoothed P?

Thanks in advance

Zelah

Lipton (New directions in testing, 1991) showed that if the permanent is easy
for most matrices, then it is easy for all matrices. I do not know an online version but you can find the result in many lecture notes, for instance here:
http://www.cse.cuhk.edu.hk/~andrejb/courses/f07-80240233/notes/lec16.pdf
There are improvements by Gemmel and Sudan (IPL 43(4): 169-174. 1992).
So the permanent is hard on the average for the uniform distribution.
For a smoothed polynomial time algorithm you have to choose the distribution in such a way that this average-case hardness is circumvented.


Scheduling to maximize idle time In the context of scheduling maintenance jobs on arcs of a flow network I came across the problem to schedule jobs, indexed by $j$, and given by triples $(r_j,d_j,p_j)$ of (integer) release time, due time and processing time such that the total time in which no job is processed is maximized. A schedule is given by start times $x_j\in S_j:=\{r_j,r_j+1,\ldots,d_j-p_j+1\}$. For instance, for five jobs with $(r_j,d_j,p_j)$ equal to
\[(1,3,3),\ (20,22,3),\ (10,11,2),\ (1,18,5),\ (8,26,5)\]
and a time horizon of 30, the first three jobs are fixed starting at times $x_1=1$, $x_2=20$ and $x_3=10$, and for the last two jobs it is optimal to start both of them at the same time $x_4=x_5\in\{8,9,10\}$. The objective value (number of time periods without any job) is
\[30-3-5-3=19.\]

The straightforward binary program for $n$ jobs looks as follows ($y_t$ is the indicator variable for the activity of the "plant" machine suggested in the comment by András Salamon)
\begin{align*}
\text{minimize}\ \sum_{t=1}^Ty_t&\\
\text{subject to}\qquad \sum_{t\in S_j}x_{jt} &=1 && j\in[n], \\
y_t-\sum_{t'\in S_j\cap[t-p_j+1,t]}x_{jt'} &\geqslant 0  && t\in[T],\ j\in J_t,\\
x_{jt}&\in\{0,1\} && j\in[n],\ t\in S_j,\\
y_t &\in\{0,1\} && t\in[T].
\end{align*}
Here $J_t=\{j\ :\ r_j\leqslant t\leqslant d_j\}$ denotes the set of jobs that can be "active" at time $t$. Interestingly, the constraint matrix is not totally unimodular in general, but the LP relaxation seems to have always integer optimal solutions. Writing down the dual also yields a problem which can be interpreted combinatorially, but so far I haven't been able to turn this into an integrality proof.

One can look at variants of the problem where the number of jobs that can be processed simultaneously is bounded, or there is a given partition of the job set such that no two jobs from the same part can be processed at the same time.
Has this kind of objective function been studied in the scheduling literature? Or is there any other related problem?

Here's a paper that considers a more general variant of the problem (multiple machines, job dependent demands etc.):

Rohit Khandekar, Baruch Schieber, Hadas Shachnai, Tami Tamir.
Real-time scheduling to minimize machine busy times.
Journal of Scheduling 18(6), 561-573, 2015.
doi:10.1007/s10951-014-0411-z

In particular, their results give a polynomial time algorithm for the case described in my question.


Topological properties of Delaunay triangulations Do Delaunay triangulations satisfy any extra topological conditions over normal planar triangulations?

In other words, if $T$ is a topological triangulation of the plane, when does there exist points $x_i \in \mathbb{R}^2$ s.t. their Delaunay triangulation has topology $T$?

Yes. See

Dillencourt, Michael B.; Smith, Warren D. Graph-theoretical conditions for inscribability and Delaunay realizability. Discrete Math. 161 (1996), no. 1-3, 63–77.

However, if a topological triangulation has no separating triangles, and no chords connecting pairs of vertices on its outer face, then it is always realizable as a Delaunay triangulation.


Determining the Class of a given Cellular Automata structure Is it possible to write an algorithm that can determine the class of a given cellular automata structure ? (ie. Wolfram's 4 Classes)

Thank you

Ricky

No. See

Culik, Karel, II; Yu, Sheng.
Undecidability of CA classification schemes.
Complex Systems 2 (1988), no. 2, 177–190.


Reading list on rewriting systems? I am new to studying rewriting systems as a first year PhD student.  I would like to propose a special topics course on rewriting theory, and I want to make sure I don't leave any of the original sources out.

I have a copy of Barendregt and Terese as textbook sources.  For original paper's: I have been looking at Dershowitz's work on proving termination, Huet's paper on confluence, Van Oostrom's paper on decreasing diagrams, and Ohlebusch's paper on confluence modulo equivalence, and Toyama's work on modularity.  I hope to end up with a smattering of both classical and recent influential papers.  Also, if anyone can recommend some good papers on the links between algebraic topology, category theory, and rewriting theory, I would appreciate that as well.

I don't have a specific recommendation for your reading list, but I want to alert you to the excellent survey on "Rewrite Systems" by Dershowitz and Jouannaud in Handbook of Theoretical Computer Science, volume B.


Multimodal logic with quantification over modal operators I take a multimodal logic to be a logic with multiple (potentially infinitely many) primitive modal operators. I am curious if anyone has studied a logic that allows one to quantify over the modal operators themselves. Intuitively, if we think of $\langle R\rangle \varphi$ as $\varphi$ by doing $R$ (where $R$ is a program), then it should make sense to want to say ``$\varphi$ by doing something,'' hence the thought of quantifying over modal operators.

In topos theory there are modal operators known as the Lawvere-Tierney operators. Such an operator is a certain endomorphism $j : \Omega \to \Omega$ on the subobject classifier. The object $J$ of all such operators is definable in the internal language of the topos, and so we can quantify over all $j$'s. My topos-theoretic knowledge is too poor to know whether anyone has done anything interesting with the object of all $j$-operators.

A related idea is the frame (or locale) of nuclei. If we think of a frame as a kind of logic (geometric logic, to be precise) then a nucleus is a modal operator on it. Once again, the nuclei of a frame themselves form a frame.


Mathematical background needed for pursuing a PhD in TCS Possible Duplicate:
  What kind of mathematical background is needed for complexity theory?

I'm a final year undergrad and I'm looking to pursue a PhD in theoretical computer science in the long term. I've been admitted to some great schools to do theory, I'm looking to defer all my admits to study math for a year in the university.

I'd very much appreciate your thoughts on the following couple of questions.

So, given that I'm not really sure what sort of theory I want to be doing at grad school (as of now, algorithms and combinatorics) what sort of things should I be looking to study there?
As someone who has studied computer science and not pure mathematics for the last few years, I want to take the next few months to prepare myself for the course. Can anyone recommend areas (and/or books) to bone up on before going there?
(Since for instance, I never formally studied abstract algebra or complex analysis)

Thanks.

do the tripos!
its an incredibly awesome opportunity and many of its alums are fantastic computer scientists.

ultimately though its your life though  and you should do stuff because you'll enjoy it.


Is there a pair of different lambda terms in the normal form that behave identically when applied to any input? Let f and g be lambda terms in the normal form, such that f is intensionally different from g - that is, their string representation using bruijn indexes isn't the same. Is there any choice of f and g such that, for any x that is also a lambda term, f x == g x?

The result you are looking for is Böhm's theorem. The equivalence described by "behaves the same way on all inputs" is the same as the equivalence given by normal forms, but only if you treat eta-equivalent normal forms (λx.Ix and I) as equivalent. You could disallow the former as a normal forms (eta-short) and then you'd have the syntactic condition you want by Böhm's theorem, if I'm not mistaken.


Is there any second-order logic finite satisfiability checker? I know that there are implementations of first-order (finite) satisfiability checking that, given a finite set of axioms, searches for a finite model that satisfies them all.
I would like to ask whether there is a second-order logic (finite) satisfiability checker. Although, we can always write a (naive) algorithm that enumerates all possible finite interpretations and check whether they are a model or not, I would like to know if there is some implementation/research doing something more intelligent (instead of a blind search).

There are Nitpick and Nunchaku that are model finders for higher-order logic.
Nunchaku is more recent and can build models for axioms containing higher-order quantification. But, as the problem is generally undecidable, it may not find a (finite) model even if one exists.


Facility location problem with a cost function I'm struggling with a facility location problem.

In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from them and create districts, such that no city in a district is farther from the center than a predefined distance parameter. This is a set covering problem that can be formulated as a binary integer program which I can solve with MATLAB's bintprog(). The solution vector gives me the list of cities that are selected as centers, after which I can establish districts by assigning each city to the closest center, and that's OK.

But I would also like to solve a specialized version of the problem, and this is where it gets ugly and I get stuck:

Let's assume we also know the population of each city and want to minimize the amount  of people who have to commute to the district center, and also the distance they have to do. So we would like to prefer solutions where the cost

$$
C =\sum_{v \in V}P_v \times d_{vc}
$$

is minimal ($v \in V$ are the cities in the district, $P_v$ is the population of $v$, and $d_{vc}$ is the distance to the center).

My problem is that I cannot think of a way to incorporate these constraints into the binary integer program, because computing these costs require the districts to be already established, which right now only happens after bintprog() has returned.

I suspect this problem might not even be formulated as a linear program at all, but I'm yet to find another way to solve it, so any help would be much appreciated. Thanks.

The problem you're asking to solve is a variant of the $k$-median problem on a metric space. You haven't mentioned anything about the various sizes involved, but as a formal matter, there are only $n$ choices for the magic number $k$ (the number of centers), and so after "guessing" the right value of $k$, you can run any of the standard approximation algorithms for $k$-median in graphs (your graph is a complete graph). In particular, one such is the method by Jain and Vazirani.

There's an older technique by Lin and Vitter that says that if you're willing to expand the number of centers by a tiny amount, you can get a pretty good approximation to the cost (w.r.t optimal centers).


Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm Is anyone familiar with Yijie Han's $O(n \log\log n)$, linear space, integer sorting algorithm?  This result appears in a fairly short paper (Deterministic sorting in $O(n \log\log n)$ time and linear space. J. Alg. 50:96–105, 2004) which basically glues together a lot of earlier results, with suitable adaptations.  My problem is that it's written in a rather hand-wavingly manner without going very deep into any specifics.  It relies heavily on previous papers, prominent among them  another paper by Han (Improved fast integer sorting in linear space. Information and Computation 170(1):81–94) written in much the same style.  I am having significant difficulties in understanding these two papers, particularly the way in which they adapt and use previous results.  I would appreciate any help.

This is of course too broad and vague to be considered a proper question, but I am hoping to develop a discussion across several focused well defined questions and answers.

To lead off, here is my first specific question.  In Lemma 2 of the Info. Comp. paper there is a recursive $O(n/k \log k)$ time algorithm for finding the mth smallest integer in a set of $n$ small integers packed $k$ each into RAM words.  The description of the algorithm fails to mention how the base case $k=O(n)$ is handled.  In this case it is required to do the selection in $O(\log k)$ time.  How can this be done?

I was just wondering the same thing.

Fortunately, I was able to find a journal-article published in 2011 which explains this very thing; whats more, you don't need a subscription to view it: Implementation and Performance Analysis of Exponential Tree Sorting

I recommend reading the entire article to learn how it can be implemented and to better understand its underlying theory. It also shows how Exponential Trees stack up against Quick-Sort and Binary Trees. Here's the relevant excerpt related to Han's $\bf O(n \log\log n)$ time, linear space, integer sorting algorithm:

  Yijie Han has given an idea which reduces the complexity to expected
  time in linear space.[6] The technique used by him is coordinated pass
  down of integers on the Andersson’s exponential search tree[8] and the
  linear time multi-dividing of the bits of integers. Instead of
  inserting integer one at a time into the exponential search tree, he
  passed down all integers one level of the exponential search tree at a
  time. Such coordinated passing down provides the chance of performing
  multi-dividing in linear time and therefore speeding up the algorithm.
  This idea may provide speed up, but in practical implementation it is
  very difficult to handle integers in batches.

[6]  Y.  Han,  Deterministic  sorting  in  O(n  log  log n)  time  and linear space, 34th STOC, 2002.

[8]  A.  Andersson,  Fast deterministic  sorting  and  searching  in linear  space,  IEEE  Symposium  on  Foundations  of Computer Science, 1996.


Dijkstra parallelization I'd like to know what is the best method to parallelize the Dijkstra algorithm.

Thanks.

There's a parallel algorithm for shortest paths from Carla Savage's 1977 Ph.D. thesis that consists of forming a square matrix with 0 on the diagonal entries, the length of the edges on the off-diagonal entries corresponding to edges, and a suitably large number for the remaining off-diagonal entries, and then repeatedly squaring this matrix in the (min,+) algebra.

After $\lceil\log_2 n\rceil$ squaring steps, the numbers in the resulting matrix are the distances between each pair of vertices. Each squaring step is easy to parallelize with logarithmic time and cubic work. So overall this algorithm takes $O(\log^2 n)$ time and $O(n^3\log n)$ work. With a little care (using a slightly more complicated algebra) this can be modified so that it also provides the first step of each shortest path in the same time and work bounds.

However, if you only want single source shortest paths rather than all pairs shortest paths, I don't know of anything that comes close to the total work of the sequential Dijkstra algorithm and that provides much in the way of a parallel speedup.


What are TCS conjectures that were proved for primes and small values but then turned out to be false? Are there any conjectures in theoretical computer science that involve some parameter n and were proved for small values of n AND for primes but later turned out to be false?

In number theory such problems do exist, eg. as Aaron Meyerowitz points out the one about the coefficients of the cyclotomic polynomials. From TCS I only know examples like the Evasiveness Conjecture that are still unsettled.

Note: This is more like an extended comment than an answer.

Here is a problem from combinatorics whose status is similiar in flavor to that of Evasiveness Conjecture:

  Background. A Latin square of order $n$ is an $n × n$ matrix in which each element from {1, . . . , n} occurs exactly once in each row and column. Two Latin squares of order $n$ are said to be orthogonal if you get $n^2$ distinct ordered pairs when you superimpose them. A set of Latin squares are said to
  be mutually orthogonal if every pair of them are orthogonal. Let $N(n)$
  denote the maximum number of mutually orthogonal Latin squares of order
  $n$.

It is known that $N(n)\leq n-1$ for all $n$. If $n$ is a prime power then we know that $N(n)=n-1$, but for general values of $n$ the status of lower bounds is wide open.


Consequences of Unique Games being a NPI problem Assume that UG is $\mathsf{NPI}$, i.e. not solvable in $\mathsf{P}$ nor in $\mathsf{NP\text{-}complete}$ (so UGC is false). Is it still NP-hard to give a $(2-\epsilon)$ polytime approximation algorithm for Vertex Cover, for example? If not, where does the new threshold of NP-hardness move in $(1,2-\epsilon]$?

To address your revised question:

  If UGC is false, is it still NP-hard to give a $(2-\epsilon)$ polytime approximation algorithm for Vertex Cover?

If it were known that it is NP-hard to approximate VC better than a factor of 2, even if the UGC is false, then we would unconditionally know that approximating VC to a factor better than 2 is NP-hard. This also works with a factor smaller than 2. If it were known that if UGC is false, then VC is NP-hard to approximate better than a factor of (say) 1.5, then we would know that it is (unconditionally) NP-hard to approximate it better than a factor of 1.5.

Since we don't know that, I guess the best we can say if the UGC is false is that it's NP-hard to approximate it to within a factor of 1.3606 by the result of Dinur and Safra (2005). (I think that's the current best-known inapproximability result.)


Classical Matrix-Vector multiplication Complexity of standard matrices Why are standard unitary transforms such as the Fourier and the Hadamard transforms believed to have a multiplicative complexity (number of multiplications) of $O(n^{1+\delta_{m}})$ and an additive complexity of $O(n^{1+\delta_{a}})$ (number of additions) where both $\delta_{m}$ and $\delta_{a}$ cannot be $0$ simultaneously?

(Please refer: Section 2.2 Page 15 of "Complexity Lower Bounds Using Linear Algebra", by Satyanarayana V. Lokam, for candidate matrices conjectured to have an arithmetic complexity (multiplicative + additive complexity)  of $\Omega(n^{1+\delta})$).

Essentially, your are asking why people believe that DFT or DHT do not have linear size arithmetic circuits. First, researcher tried to find such circuits for decades but did not succeed. Second, there are superlinear lower bounds (Morgenstern's theorem, see the book by Bürgisser, Clausen, Shokrollahi) in restricted models. From Morgenstern's theorem, in follows that in linear arithmetic circuits of linear size over the complex numbers  for the DFT, the absolute values of the constants used in the circuit go to infinity as $n$ goes to infinity.


Why does deterministic recognition of DYCK(2) languages in the streaming model take linear space? I was reading the paper "Recognizing Well-Paranthesized Expressions in the Streaming Model" by Magniez, Mathieu and Nayak where they give upper and lower bounds on the space required to recognize DYCK(2) languages in the streaming model. Quoting a sentence from the introduction section of the paper - "Using a straightforward one-way communication complexity argument for EQUALITY, we can deduce that DYCK(2) requires linear space for deterministic one-pass streaming algorithms." Can anyone see the straightforward argument? (I can't, but perhaps I am being blind.)

Some background -

DYCK(2) languages are basically sequences of two kinds of parantheses that are well-formed. For example, the sequence [()] is in DYCK(2), but the sequence [(]) is not.

One-way communication complexity of EQUALITY refers to the following problem. Alice and Bob both have one n-bit string each. Alice does some computation on her bits and sends some information to Bob. Bob can do computation on this information plus his bits and has to decide whether his n-bit string is exactly equal to Alice's bit string or not. It can be shown using simple communication complexity arguments that the number of bits that must be communicated is $\Omega(n)$.

Communication complexity lower bounds are often used for proving lower bounds for streaming algorithms. The usual scheme is the following. Suppose the problem you want to solve in streaming is P. Pick a communication complexity problem P' for which you know of a lower bound on the number of bits that need to be communicated. Then assume that the problem P can be solved in the streaming model using $o(f(n))$ space. Now in the communication complexity problem P', assume that Alice has as her input the first few bits of the input for P (or some mapping of the first few bits to something else). Then assume that the protocol they use for communication is that Alice runs the streaming algorithm on her input, sends the working space to Bob and then Bob finishes off using his input. In the end, prove that the solution to the streaming problem somehow gives a solution for the communication complexity problem. This will show that the communication complexity problem can be solved with $o(f(n))$ bits of complexity. The trick is to choose $f(n)$ in such a way that this leads to a contradiction.

Consider the restricted case in which the opening parentheses all come before the closing ones. Map ( and ) to 0, and [ and ] to 1. Then (after the map) an expression is well formed if and only if the first half is equal to the second half reversed.

Consider then a one-pass streaming algorithm that solves this restricted version of the problem in sublinear space. Using the construction in your question, to get a protocol for the equality problem with sublinear communication, Alice runs the streaming algorithm on her input (mapping 0 to ( and 1 to [), sends the working space to Bob, and Bob finishes off using the reverse of his input (mapping 0 to ) and 1 to ]). The streaming algorithm will output that the sequence of parentheses is well formed iff their original inputs are equal.


Counting xyz-graphs in $\mathbb{Z}_n^3$ This is a followup question to: Lower bound on the largest restrained cubic subset

How many distinct xyz-graphs exist in $\mathbb{Z}_n^3$? We denote this number as $C(n)$

This question may be seen as a generalization of counting simple cycles in $K_{n,n}$, via the hypergraph description of xyz-graphs given in the linked article. With that in mind, the problem reduces to solving for the number of "Hamiltonian" xyz-graphs, which in our generalization will be xyz-graphs (thought of as sets of hyper-edges) which touch every 2-edge in $K_{n,n,n}$ exactly twice. One example of such a Hamiltonian xyz-graph is provided in the linked question and at https://11011110.github.io/blog/2006/06/09/topology-of-xyz.html and is given by the set:

$\{(x,y,z) \ | \ x+y+z=0\} \ \cup \ \{(x,y,z) \ | \ x+y+z=1\}$

where addition is done mod n. Let the number of Hamiltonian xyz-graphs of $K_{n,n,n}$ be $H(n)$. Now we may simply look at how many copies of $K_{i,i,i}$ exist in $K_{n,n,n}$. This is simply ${n \choose i}^3$, which gives us the formula:

$
C(n) = \sum\limits_{i=2}^n {n \choose i}^3H(i)
$

Note that $H(n)= \frac{n!(n-1)!}{2}$ in the 2-dimensional case of $K_{n,n}$. It seems like we could use a similar strategy for the 3-dimensional case and end up with something along the lines of $\frac{n!^2(n-1)!^2}{4}$ which would lead to

$
C(n) = \frac{1}{4}\sum\limits_{i=2}^n \frac{(i-1)!}{i}(n)_i^3
$

However I'm fairly certain this number is far too large, so there must be a number of extra constraints when building these Hamiltonian cycles.

EDIT: Unfortunately there are trivial examples of xyz-graphs which are not hamiltonian for some n, meaning that the above would only give a lower bound.

Consider that hamiltonian cycles of the bipartite graph are isomorphic (that is we can always permute the rows amongst themselves and the columns similarly to reach any other hamiltonian cycle).

Consider the planes given by $(x,-,-)$ and $(-,y,-)$. Permuting these planes is exactly the same as permuting the rows and columns of the $(-,-,z)$ planes. Thus we may permute in this way to get any of the hamiltonian cycles on one of the $(-,-,z)$ planes, giving us $n!(n-1)!/2$ unique xyz-graphs. Further, we may then permute the (-,-,z) plane, fixing only the one we specifically permuted before, each of which also must give a unique xyz-graph. Thus in total we have:

$H(n) \geq \frac{n!(n-1)!^2}{2}$

Which implies the bound

$C(n) \geq \frac{1}{2}\sum\limits_{i=2}^n \frac{(n)_i^3}{i^2}\\$.

EDIT: In fact, we can do better. We have only considered sub cubes here, but we may also consider xyz graphs inside ([n],[n],[m]). Since all simple cycles are hamiltonian on $K_{n,n}$, we take $m \leq n$ to avoid double counting. Then using the same construction for our first cycle and then the same permutation process above we get:

$H(n,m) \geq \frac{n!(n-1)(m-1)!}{2}$

and then

$C(n) \geq \frac{1}{2}\left (\sum\limits_{i,j=2 \ | \ i \geq j}^n \frac{(n)_i^2(n)_j}{ij} \right )$.


Hyperspherical nature of K-means and similar clustering methods Jain, Murty, and Flynn
state in their article Data Clustering: A Review
all squared error based clustering methods like K-means
tend to generate hyperspherical clusters.

However, they do not give a theoretical justification for this.

Is a theoretical justification for this observation?
Can we change the K-means algorithm to generate rectangular clusters?

K-means tends to create compact clusters, which means that geometrically, the distance between every two points is small.

K-means can create clusters which are ball-like if you use $L_2$ norm, pyramid if you use $L_1$ and hypercubes if $L_\infty$ is used.

As opposed to that there are clustering algorithms which first project the data into lower dimension (such as spectral clustering), which means not all of the points in a cluster has to be close, but rather "connected" via other points in the original space, which will make them close after the projection.

This allow you to find very nice looking clusters, such as this and that.


From Lasserre maps to pseudo-distributions Let me define a ``Lasserre map of degree $d$" as a linear map $L : \mathbb{R}_n[x] \rightarrow \mathbb{R}$ i.e a real valued linear map on polynomials over $n$ variables with real coeffients. This is further expected to satisfy, $(1)$ $L(1) =1$ and $(2)$ as $L(P^2) \geq 0$ if $deg(P) \leq \frac{d}{2}$.

On the otherhand a "pseudo-distribution of degree $d$" is defined as a map $D : \{\pm 1\}^n \rightarrow \mathbb{R}$ such that $(1)$ $\sum_{x \in \{\pm 1\}^n } D(x) =1$ and $(2)$ $\sum_{x \in \{\pm 1\}^n } D(x) f(x) \geq 0 $ if $f$ can be written as a sum of squares of polynomials each of degree $\leq \frac{d}{2}$ i.e if $f \in SOS_{\leq d}$ (the cone of sum-of-squares of polynomials of degree at most $\frac{d}{2}$)

It is trivial to see that given a map $D$ of the later type we can always create a map of the first type by defining , $L(Q) := \sum_{x \in \{\pm 1\}^n } D(x) Q(x)$.

But does every map Lasserre map $L$ induce a pseudo-distribution $D$?
Can one think of this $\{\pm 1\}^n$ as $\mathbb{F}_2^n$ and then is there any meaning (or use!) to ask for a generalization to $\mathbb{F}_q^n$?

The answer to your first question is yes by some linear algebra. Write down the equations for $L(m) = \sum_{x\in\pm 1} D(x)m(x)$ where $m$ is a monomial of degree at most $d$ (with no squared variables in it). You can write this as $L = MD$ where $M$ is a matrix with rows indexed by the monomials $m$ and columns indexed by the points $x \in \{\pm 1\}$, with values $m(x)$, and $D$ is a vector indexed by the points in $\{\pm 1\}$. $M$ has full rank, so you can find $D$ with $MD = L$ for any $L$. That any such $D$ satisfies the pseudodistribution properties follows from the fact that $L$ satisfies the corresponding properties.

As for your second question, formally, it can be done for prime fields by just using equations like $x^p = 1$ in place of $x^2 = 1$. (I'm not sure what to do for general prime powers.) It might be helpful in characteristics greater than two to generalize the rest of the SOS theory to work over $\mathbb{C}$, since you're working with complex roots of unity. This can be done essentially by replacing "sum of squares" by "sum of products-of-conjugates" and making appropriate adaptations elsewhere.

However, I'm doubtful that it's useful to think of $\{\pm 1\}$ as being "like" $\mathbb{F}_2$ in the context of SOS. Embedding finite fields as roots of unity doesn't jive well with sum of squares: addition in the finite field turns into multiplication over $\mathbb{R}$, and hence SOS requires high degree to reason about sums (in the finite field) of many unknowns, because they translate to products (over the reals) of many variables. An essentially canonical demonstration of this is the lower bound for solving linear equations over $\mathbb{F}_2$ (see section 3.1 here). In particular, you can trick low-degree SOS into believing that a certain system of linear equations over $\mathbb{F}_2$ is completely satisfiable, when in reality at most a $\frac{1}{2}+\epsilon$ fraction of equations can be satisfied by any true assignment.


Has parameterized complexity led to better algorithms? I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, this is the only example I've seen on Downey, Rodney G. and Michael R. Fellows. "Parameterized Complexity".
Has considering a problem in a parameterized way led to different algorithms that end up to be feasible in practice? Or is the Parameterized Complexity Theory just a tool for evaluating complexity of problems?

There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems.
In the $k$-Path problem where we are looking for a simple path of length $k$. Alon, Yuster and Zwick [1] showed that this problem can be solved in $2^{O(k)}\cdot n$ time on $n$-vertex graphs. A weighted version of $k$-Path has applications in computational biology and the biologically interesting paths have length at most 20. Several of the implemented algorithms successfully use the color coding technique [2].
The Clique problem parameterized by the solution size $k$ has presumably no FPT algorithm, but Clique parameterized by the degeneracy $d$ of the input graph has an FPT algorithm. More precisely, all maximal cliques of an $n$-vertex graph can be enumerated in $O(3^{d/3}\cdot n)$ time [3]. Since many real-world graphs (e.g. social networks) have small degeneracy, this running time bound explains why clique enumeration is feasible on these graphs.
I would say there is a crucial difference between the two results. In the case of $k$-Path, the color coding technique is an FPT technique that was developed in theory and was later turned into a practical algorithm. In the case of Clique, the central technique of the FPT algorithm, which, roughly speaking, is to enumerate first the cliques containing a minimum-degree vertex $v$ and then enumerating all cliques not containing $v$, was already known, in some form, before the theoretical analysis and probably used in several implementations. Hence, I would say that for $k$-Path, parameterized algorithmics has led to better algorithms, and for Clique, parameterized algorithmics rather explains why algorithms are good.
[1]: Alon, Yuster and Zwick: Color Coding.  J. ACM 42(4): 844-856 (1995) https://doi.org/10.1145/210332.210337
[2] Jacob Scott, Trey Ideker, Richard M. Karp, Roded Sharan: Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks. J. Comput. Biol. 13(2): 133-144 (2006)
[3] David Eppstein, Maarten Löffler, Darren Strash:
Listing All Maximal Cliques in Large Sparse Real-World Graphs. ACM J. Exp. Algorithmics 18 (2013)


Complexity of converting a boolean circuit to a boolean formula Given a boolean circuit $C$ on $n$ variables (which uses just NOT,AND and OR gates), what is the most efficient way to extract the boolean formula represented by the circuit? Is there a polytime algorithm for this problem?

If I understand your question correctly, I'd say you could use the standard reduction from CIRCUIT-SAT to SAT: Represent each gate as a new variable, and then represent the entire circuit in CNF form, with each clause having the form $(v\leftrightarrow\phi)$, where $v$ is the new variable, and the formula for the gate is given by $\phi$, using the variables for other gates to represent the inputs. This can be done by a simple traversal (in linear time, which is clearly optimal).

For example, if you hade three inputs, $x_1$, $x_2$, and $x_3$, with AND gates linking $x_1$ and $x_2$ as well as $x_2$ and $x_3$, and an OR gate linking their outputs, you could introduce three variables to represent the gates—$v_1$, $v_2$, and $v_3$, respectively—and rewrite the formula to $$(v_1\leftrightarrow(x_1\land x_2))\land (v_2\leftrightarrow(x_2\land x_3))\land (v_3\leftrightarrow(v_1\lor v_2))\land v_3\,.$$ Note that the output variable is included explicitly.

Introduction to Algorithms by Cormen et al. explains this in detail, in the chapter on NP-Completeness.


All recursive algorithms are inherently NOT-inplace, isn't it? As recursive algorithms depend on the stack whose size is in almost all the cases depend on input, why don't we consider all the recursive algorithms as NOT-inplace algorithms?

Consider for example, Quicksort, we say it as inplace sort, but in reality, (average case) it uses O(log(n)) memory in stack? So, how can it be called inplace sort?!

Recursion is an abstract concept. Talking about whether or not it has in-place semantics is nonsense. (Unless of course the language specifies recursion semantics.) This idea is related to how it is nonsense to talk about the speed of a language.

How recursion is implemented is another question. For example, a compiler might perform tail call optimization where recursion can be converted to a loop under the hood among other things. In this case, recursion maintains constant stack space (assuming your architechure uses stacks :D)

EDIT: What does this all mean? It means that there exist recursive algorithms that are in-place when implemented in certain fashions. Thus the statement "All recursive algorithms are inherently not in-place" is false.


Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic Berman–Hartmanis conjecture: all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms[1].

I am interested in a more fine-grained version of the "polynomial time", that is, if we use parameterized reductions.

A parameterized problem is a subset of $Σ^∗ × Z \geq 0$, where $Σ$ is a finite alphabet and $Z\geq 0$ is the set of nonnegative numbers. An instance of a parameterized problem is therefore a pair $(I, k)$, where $k$ is the parameter.

A parameterized problem $π_1$ is fixed-parameter reducible to a parameterized problem $π_2$ if there exist functions $f$, $g$ : $Z≥0 → Z≥0$, $ Φ : Σ∗ × Z≥0 → Σ^∗$ and a polynomial $p(·)$ such that for any instance $(I, k)$ of $π_1$, $(Φ(I, k), g(k))$ is an instance of $π_2$ computable in time $f(k) · p(|I|)$ and
$(I, k) ∈ π_1$ if and only if $(Φ(I, k), g(k)) ∈ π_2$. Two parameterized problems are fixed-parameter equivalent if they are fixed-parameter reducible to each other.

Some NP-complete problems are FPT, for example, the decision version of vertex cover problem is NP-Complete, it has a $O(1.2738^k + kn)$ algorithm[2]. Finding better fixed-parameter reductions of a FPT problem which is NP-Complete can lead to a better algorithm, for example, by invoking a reduction to an
"above guarantee version" of the Multiway Cut problem can lead to an algorithm in time $O^*(4^k)$ for AGVC(Above Guarantee Vertex Cover) problem[3], which is better than the original $O^*(15^k)$ algorithm [4].

$\textbf{My Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic.}$

Is that conjecture true?

[1]  Berman, L.; Hartmanis, J. (1977), "On isomorphisms and density of NP and other complete sets", SIAM Journal on Computing 6 (2): 305–322.

[2] J. Chen, I. A. Kanj, and G. Xia, Improved upper bounds for vertex cover, Theor.Comput. Sci., 411 (2010), pp. 3736-3756.

[3] M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk, On multiway
cut parameterized above lower bounds, in IPEC, 2011.

[4] M. Mahajan and V. Raman, Parameterizing above guaranteed values: Maxsat and
maxcut, J. Algorithms, 31 (1999), pp. 335-354.

Serge Gaspers already mentioned why your conjecture is trivially true.

However, one can in fact get polynomial-time fixed-parameter isomorphisms,

which I now realize isn't that much less trivial, since it applies to every

ordered pair of non-trivial FPT problems with a reduction in the ordinary sense.

Let $c$ be an integer that's greater than the degree of the FPT algorithm for $\pi_1$,

and let $Y$ and $N$ be a yes and no instance respectively of $\pi_2$.

The following will be a polynomial-time fixed-parameter reduction from $\pi_1$ to $\pi_2$:

Try the FPT algorithm on $\pi_1$ for up to $n^{\hspace{.02 in}c}$ steps.

If that gives an answer, then output $Y$ or $N$ as indicated by that answer.

Otherwise, output the result of applying an ordinary polynomial-time reduction from $\pi_1$ to $\pi_2$.

Correctness and polynomial runtime are obvious. $\:$ Since $c$ is greater than the degree of the FPT algorithm for $\pi_1$, it's the case that for each fixed $k$, there are only finitely many input lengths $n$ for which the FPT algorithm's maximum runtime is not less than $n^{\hspace{.02 in}c}$. $\:$ Thus, for each fixed $k$, the above reduction has only finitely many outputs. $\:$ Therefore it satisfies your fixed-parameter condition.


Long Cycle in Bounded Tree-Width Graphs using DFS and Dynamic Programming For fixed parameter $k$, I would like to find a long cycle of length $\geq k$ in an undirected graph $G(V,E)$.  This can be done in $O(k!2^k|V|)$-time [2] using 1) depth-first search (DFS) and 2) dynamic programming on a bounded tree-width decomposition of $G$ derived from the DFS traversal.

However, [2] does not contain explicit details on what information should be stored in the tables associated with each bag of the tree decomposition.

  When looking for long cycles using the dynamic programming method suggested by [2], are there any ideas or resources that specify what information needs to be stored at each bag and how to combine such tables?

References:

[1] Gabow & Nie, 2008
contains an overview of the above problem, from the perspective of directed and undirected graphs, and includes a review of research on the undirected case.

[2] Bodlaender, 1993 suggests an $O(k!2^kn)$-time algorithm based on depth-first search (DFS) and dynamic programming.

There is a nice trick to reduce $\geq k$ cycle to finding a cycle of length exactly $t$, for $t \leq 2k$ (I first heard of this trick from Daniel Marx). The key observasjon is that contracting an edge of $G$ may not increase the length of the longest cycle in G, and may only decrease the length by a factor at most two. Thus we can search for cycles of length exactly $t$ for $k \leq t \leq 2k$. If no cycle is found, contract an edge and repeat.

This shoukd be quite a bit faster than the treewidth based algorithms, I believe, especially if you use the sieving methods for finding t-cycles (paths). There are very efficient implementations for $k$-path by Bjorklund et al:

Fast Witness Extraction Using a Decision Oracle, with Andreas Björklund and Petteri Kaski
Proc. 22th Annual European Symposium on Algorithms (ESA 2014), LNCS 8737, 2014, pp. 149-160.

This should be adaptable to your problem.


Results comparing BQP and NEXP Are there oracle results with $$P=NP\neq BQP=NEXP\mbox{ and }P=NP\neq BQP\neq NEXP?$$
Also is there a $PCP$ characterization of $BQP$ like $$PCP(O(poly(n)),1)=PCP(O(poly(n)),O(poly(n)))=NEXP?$$

The oracle you ask for has $P=NP\ne BQP=NEXP$, and therefore it has $BQP\ne PH$. Finding any oracle relative to which $BQP\ne PH$ was an open problem for twenty years until Raz and Tal [1] found such an oracle last year. In summary, the oracle you ask for currently is not known to exist, but people are looking. There are oracles relative to which $P\ne BPP=PH=BQP=NEXP$, but these lack your constraint $P=NP$. [3]*

(The second oracle you ask for exists, namely take $O=PSPACE$, then $P=NP=BQP=PSPACE\ne NEXP$).

There is currently no quantum PCP Theorem, though again, people are looking. Aharonov et al. [2] provide a readable introduction to the Quantum PCP Conjecture. In this context, as in the classical PCP, there are two equivalent versions, one talking about verifying a quantum proof, the other talking about hardness-of-approximation. One major step that has been accomplished is that we know that the two versions are equivalent, that is, they imply each other. Many other questions remain open.

[1] Raz, Ran, and Avishay Tal. "Oracle Separation of BQP and PH." Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. ACM, 2019.

[2] Aharonov, Dorit, Itai Arad, and Thomas Vidick. "Guest column: the quantum PCP conjecture." Acm sigact news 44.2 (2013): 47-79.

[3] Williams, Ryan. "Towards NEXP versus BPP?." International Computer Science Symposium in Russia. Springer, Berlin, Heidelberg, 2013. (Section 4, Conclusion)

[4] Kitaev, Alexei Yu, et al. Classical and quantum computation. No. 47. American Mathematical Soc., 2002.

(*) (Actually I cannot find a reference for such an oracle, but [3] mentions such an oracle)


Stronger Lower Bounds on Nondeterministic Multiparty Communication This is a continuation of my previous question on Lower bounds for Nondeterministic Multiparty Communication.

From the answer, the $\mu^\infty$ norm lower bounds nondeterministic multiparty communication in the number-on-the-forehead model (see the paper by Lee and Shraibman). The problem is that for any given sign matrix $M$, $\mu^\infty(M)=1/Disc(M)$, where $Disc(M)$ is the discrepancy of $M$. It is a problem because the best lower bounds we can prove using discrepancy are polylogarithmic in the size of the input. For example, for disjointment with $k$ parties the lower bound is $\Omega(\log n/(k-1))$. In the same piece of work, the authors show that for randomized protocols, disjointment requires $\Omega(\frac{n^{1/(k+1)}}{2^{2^k}})$ using the $\mu^\alpha$ norm.

Is there any other norm stronger than discrepancy that can be used for lower bounds in nondeterministic multiparty communication? Or is it tight? These results are very recent, so maybe this is an open problem.

Edit(dec/8/2010): I have two more questions,

2) Corruption (cf. Lee and Shraibman 2007, section 4.5) is used for lower bounding 2-sided error randomized communication. Is there any extension of corruption to nondeterminism? A nondeterministic protocol accepts with probability strictly greater than 0, and rejects with probability 1.

3) Is there any other lower bound based on information-theoretic arguments?

There is a tight (within an additive log n) lower bound method for nondeterministic multiparty communication complexity:

Put a hard distribution on the 1-inputs, and measure the size of the largest 1-monochromatic cylinder intersection. To see that it's tight take the relevant section in Kushilevitz and Nisan, and replace the word 'rectangle' with 'cylinder intersection'.

The corruption bound, or rather the one-sided version of it (where you prove that all large rectangles contain a constant fraction of 0-inputs) is harder to use and yields stronger results, for instance allows you to prove MA-communication complexity lower bounds.


Scrambling a Rubik's cube by an adversarial noob My friend dislikes Rubik's cubes, and he asked me how to frustrate amateur solvers by adversarially scrambling the cube. I expect that the answer depends highly on the particular solving algorithm.

  Are there "human" algorithms for solving a Rubik's cube that are known to be very inefficient (compared to optimal) against particular "bad" configurations?

By "human", I mean the common algorithms that are taught in practice to amateurs or used by enthusiasts. There might be too much variety in common human techniques for this question to make sense, but even that would be good to know. (I'm looking for something more interesting than naive random walk, which is clearly almost always inefficient.)

And the relevant followup question:

  Are there ways to find these bad configurations by applying random moves?

That is, is there an easy way to randomly generate hard cube instances for a particular human algorithm?

This is (somewhat) related to another question of mine about shortest paths to solution when randomly scrambling a Rubik's cube.

If the aim is to frustrate amateur solvers, maybe the best is to give them a configuration that seems very simple to solve, but will be hard with the common algorithms.
For instance you can just invert all the centers, or do a few swaps between squares, to have just 1 or 2 wrong on each face.
This is of course betting they don't know the special algorithms to create/solve these special configurations ;)


In a random perfect matching of a regular bipartite graph, are all edges equally probable? Consider a d-regular bipartite graph G, for d>=1. Obviously, G contains a perfect matching. Consider a perfect matching M in G chosen uniformly at random from all perfect matchings in G. Is it the case that, for arbitrary edges e and e', the probability e is in M is the same as the probability e' is in M?

Stated differently, I am asking the following: Is it the case that, for an edge e of a regular bipartite graph G, the number of perfect matchings that include e does not depend on e?

No.

Construction: Take two copies of $K_{3,3}$, one with the nodes $\{a,b,c\} \cup \{a',b',c'\}$ and the other one with the nodes $\{d,e,f\} \cup \{d',e',f'\}$. Remove the edges $(c,c')$ and $(d,d')$. Add the edges $(c,d')$ and $(d,c')$.


Process on finite points in a line This is related to some old posts that were closed because someone had felt that they're related to homework. All I'm looking for here is a reference to a paper that may have partially or completely solved the following problem:
n points on the unit interval are given. Consider the set of processes operate discretely on the n points as follows: at every time step, a process takes two points and replaces them by their midpoint. The process stops if only two points are left.
I'm interested to know about an optimal process in this set (meaning a process that given an initial set of n points would lead to the smallest distance between the two final points). Any known bounds on the optimal final distance? Any generalization to higher dimensions?
Thanks!

Rather than go through some complicated bureaucracy to close this and resuscitate the other earlier-asked variants, it's probably straightforward just to answer this now; I think it's long enough after the previous questions that we don't so much need to worry about it being homework (and the way it's phrased now certainly seems much less suspicious).

The paper I was referring to in the discussion on the earlier problems is:

"Exponentially small bounds on the expected optimum of the partition and subset sum problems", G. S. Lueker, Random Structures and Algorithms, 1998.

But now that I think about it again, I realize that the problem Lueker solves is actually a bit different from what you're asking: he repeatedly replaces a pair of points by their difference, rather than their average. The application for this replacement process is in a variant of the subset sum problem, in which one is given n real numbers and one is trying to find a subset minimizing the difference between the sum of the weights in the chosen subset and the sum of the weights not in the subset. Replacing a pair by their difference is equivalent to imposing a constraint that exactly one of the two items is in the subset: each of the two choices for what to do with the difference in the replaced problem has exactly the same effect as each of the two choices for which item to include in the original problem.

This is also somewhat related to some work of Valiant, "Short monotone formulae for the majority function", J. Algorithms, 5, 1984, 363–366: by repeatedly replacing triples of numbers by their median, you can with high probability find a point near the median of the numbers. See also my paper with Clarkson et al, "Approximating Center Points with Iterated Radon Points", which generalizes this result to higher dimensions.


Constructions better than a random one. I am interested in examples of constructions in the complexity theory which are better than a random constructions.

The only one example of such construction which I know is in the field of error-correcting codes. Algebraic-geometry codes are better in some range of parameters than a random codes.

One can easily to construct such artificial examples.
I am interested in the examples like algebraic geometry codes, where it is easy make a random construction and it is not obvious how to do better.

Ramanujan graphs have second eigenvalue $\lambda_2\leq \frac{2\sqrt{D-1}}{D}$ (with $D$ the degree of the graph), while random graphs only achieve $\lambda_2\leq \frac{2\sqrt{D-1}}{D} + o(1)$ w.h.p. In fact, in general we have that $\lambda_2\geq \frac{2\sqrt{D-1}}{D} - o(1)$, with the $o(1)$ term going to $0$ with $D$ held constant (as the number of vertices $N\rightarrow \infty$), so in some sense these are optimal.


Shortest path in a DAG consisting of multiple copies of a smaller DAG Let's say we have $k$ weighted DAGs (directed acyclic graphs)
$$H_1 = (V_1, A_1), \dots, H_k = (V_k, A_k)$$
that are copies of one another. Now consider another weighted DAG $G$ that is built by combining $H_1, \dots, H_k$ and adding some additional arcs that can only go from one vertex to vertices in the following copies, i.e., consider a weighted DAG $G = (V, A)$ such that:

$V = \bigcup_{1 \le i \le k} V_i$; and
$A = ( \bigcup_{1 \le i \le k} A_i ) \cup A'$, such that for each $a = (u, v) \in A'$ we have $u \in V_i, v \in V_j$ with $i < j$.

Now suppose we want to find the shortest $s$-$t$ path for a given pair of vertices $(s, t) \in V^2$. Can precomputing all-pairs shortest paths in $H_1, \dots, H_k$ be used to speed up the algorithm?

Any references to papers that use similar ideas would be helpful.

Yes, you certainly can (based on the fact that any subpath of a minimal path must also be minimal). That is, any shortest path entering $H_i$ at $u$ and leaving at $v$ must follow the shortest path from $u$ to $v$ in $H_i$.

Basically, you can compute the shortest-path distance matrix $D$ for any $H_i$ (it would be the same for all of them, of course), and replace every subgraph $H_i$ by one consisting only of the in- and out-nodes (that is, the nodes connected to other subgraphs; presumably fewer than $|V_i|$), and use only direct edges from the in-nodes to the out-nodes, with weights given by $D$.

You don't need to explicitly construct this new graph, of course. If you have the macrostructure of $G$ available in implicit form, you can compute $D$, and use that together with the macrostructure of $G$ in a (slightly customized) DP algorithm for finding the shortest path.


Partitioning a rectangle without harming inner rectangles $C$ is an axis-parallel rectangle.

$C_1,\dots,C_n$ are pairwise-interior-disjoint axis-parallel rectangles such that $C_1\cup\dots\cup C_n \subsetneq C$, like this:

A rectangle-preserving partition of $C$ is a partition $C = E_1\cup\dots\cup E_N$, such that $N\geq n$, the $E_i$ are pairwise-interior-disjoint axis-parallel rectangles, and for every $i=1,\dots,n$: $C_i \subseteq E_i$, i.e, each existing rectangle is contained in a unique new rectangle, like this:

What is an algorithm for finding a rectangle-preserving partition with a small $N$?

In particular, is there an algorithm for finding a rectangle-preserving partition with $N=O(n)$ parts?

NEW ANSWER: the following simple algorithm is asymptotically optimal:

  Stretch each of the rectangles $C_i$ arbitrarily, to the maximal extent possible such that the rectangles remain pairwise-disjoint.

The number of holes is at most $k-2$. This is asymptotically optimal, as there are configurations in which the number of holes is at least $k-O(\sqrt k)$.

The proofs are in this paper.

OLD ANSWER:

The following algorithm, while not optimal, is apparently sufficient for finding a rectangle-preserving partition with $N=O(n)$ parts.

The algorithm works with a rectilinear polygon $P$, which is initialized to the rectangle $C$.

Phase 1: Pick a rectangle $C_i$ which is adjacent to a western boundary of $P$ (i.e, there is no other rectangle $C_j$ between the western side of $C_i$ and a western boundary of $P$). Place $C_i$ within $P$ and stretch it until it touches the western boundary of $P$. Let $E_i$ (for $i=1,\dots,n$) be the stretched version of $C_i$. Let $P=P\setminus E_i$. Repeate Phase 1 $n$ times until all $n$ original rectangles are placed and stretched. In the image below, a possible order of placing the rectangles is $C_1,C_2,C_4,C_3$:

Now, $P$ is a rectilinear polygon (possibly disconnected), like this:

I claim that the number of concave vertices in $P$ is at most $2n$. This is because, whenever a stretched rectangle is removed from $P$, there are 3 possibilities:

2 new concave vertices are added (like when placing $C_1,C_4$);
3 new concave vertices are added and 1 is removed (like with $C_3$);
4 new concave vertices are added and 2 are removed (like with $C_2$).

Phase 2: Partition $P$ into axis-parallel rectangles using an existing algorithm (see Keil 2000, pages 10-13 and Eppstein 2009, pages 3-5 for a review).

Keil cites a theorem that says that the number of rectangles in a minimal partition is bounded by 1 + the number of concave vertices. Hence, in our case the number is at most $2n+1$, and the total number of rectangles in the partition is $N\leq 3n+1$.

This algorithm is not optimal. E.g, in the above example it gives $N=13$ while the optimal solution has $N=5$. So two questions remain:

A. Is this algorithm correct?

B. Is there a polynomial-time algorithm for finding the optimal $N$, or at least a better approximation?


Regularity of language with finite number of right derivatives I found this statement listed as a theorem in a textbook:

  If L ⊆ Σ∗ is any language, then L is regular iff it has finitely many right derivatives. Furthermore, if L is regular, then all its right derivatives are regular and their number is equal to the number of states of the minimal DFA’s for L.*

Unfortunately, no proof was provided. Why is this statement true?

See Janusz Brzozowski's 1964 paper Derivatives of Regular Expressions. This is theorem 5.2 in the paper, and the proof is in Appendix 2.


Low rank approximation of matrix under $l_2$ norm Theorem 14 of this paper by Tam´as Sarl´os gives a relative error rank-$k$ approximation of a given matrix $A$ under the frobenius norm. I am looking for reference of a similar result (relative error low rank approximation) under the $l_2$ norm.

Pls let me know I am  able to put the question clearly.

This is the median k-flat problem. Feldman wrote some papers on this and related problems. See for example  http://arxiv.org/abs/1106.1379 .