Is there a stable heap? Is there a priority queue data structure that supports the following operations?

Insert(x, p): Add a new record x with priority p
StableExtractMin(): Return and delete the record with minimum priority, breaking ties by insertion order.

Thus, after Insert(a, 1), Insert(b, 2), Insert(c, 1), Insert(d,2), a sequence of StableExtractMin's would return a, then c, then b, then d.

Obviously one could use any priority queue data structure by storing the pair $(p, time)$ as the actual priority, but I'm interested in data structures that do not explicitly store the insertion times (or insertion order), by analogy to stable sorting.

Equivalently(?): Is there a stable version of heapsort that does not require $\Omega(n)$ extra space?

The Bently-Saxe method gives a fairly natural stable priority queue.

Store your data in a sequence of sorted arrays $A_0,\ldots,A_k$.  $A_i$ has size $2^i$.  Each array also maintains a counter $c_i$. The array entries $A_i[c_i],\ldots,A_i[2^i-1]$ contain data.

For each $i$, all elements in $A_i$ were added more recently than those in $A_{i+1}$ and within each $A_i$ elements are ordered by value with ties being broken by placing older elements ahead of newer elements.  Note that this means we can merge $A_i$ and $A_{i+1}$ and preserve this ordering.  (In the case of ties during the merge, take the element from $A_{i+1}$.)

To insert a value $x$, find the smallest $i$ such that $A_i$ contains 0 elements, merge $A_0,\ldots,A_{i-1}$ and $x$, store this in $A_i$ and set $c_0,\ldots,c_i$ appropriately.

To extract the min, find the largest index $i$ such that the first element in $A_i[c_i]$ is minimum over all $i$ and increment $c_i$.

By the standard argument, this gives $O(\log n)$ amortized time per operation and is stable because of the ordering described above.

For a sequence of $n$ insertions and extractions, this uses $n$ array entries (don't keep empty arrays) plus $O(\log n)$ words of bookkeeping data.  It doesn't answer Mihai's version of the question, but it shows that the stable constraint doesn't require a lot of space overhead.  In particular, it shows that there is no $\Omega(n)$ lower-bound on the extra space needed.

Update: Rolf Fagerberg points out that if we can store null (non-data) values, then this whole data structure can be packed into an array of size $n$, where $n$ is the number of insertions so far.

First, notice that we can pack the $A_k,\ldots,A_0$ into an array in that order (with $A_k$ first, followed by $A_{k-1}$ if it's non-empty, and so on).  The structure of this is completely encoded by the binary representation of $n$, the number of elements inserted so far.  If the binary representation of $n$ has a 1 at position $i$, then $A_i$ will occupy $2^i$ array location, otherwise it will occupy no array locations.

When inserting, $n$, and the length of our array, increase by 1, and we can merge $A_0,\ldots,A_i$ plus the new element using existing in-place stable merging algorithms.

Now, where we use null values is in getting rid of the counters $c_i$.  In $A_i$, we store the first value, followed by $c_i$ null values, followed by the remaining $2^i-c_i-1$ values.  During an extract-min, we can still find the value to extract in $O(\log n)$ time by examining $A_0[0],\ldots,A_k[0]$.  When we find this value in $A_i[0]$ we set $A_i[0]$ to null and then do binary search on $A_i$ to find the first non-null value $A_i[c_i]$ and swap $A_i[0]$ and $A_i[c_i]$.

The end result: The entire structure can be implemented with one array whose length is increment with each insertion and one counter, $n$, that counts the number of insertions.


Graph traversal with vertex and edge deadlines/windows Hello the question was also posted on stackoverflow, but since this is theoretical oriented, thought I'd give it a try. I have an undirected graph similar to the one below, I need to implement a graph traversing algorithm.
Example:
http://i.imgur.com/15L6m.png

The idea is that each vertex is a city, and each edge is a road.
The weight of an edge represents the time needed to traverse the specified edge.
The conditions are:

Each edge is open for traversal in a specified time window: Time Open1, Time Open2, TimeClose1, Time Close2 - the current time must be in these intervals in order to traverse the edge.
Only some vertices must be visited. The vertices must be visited at leas once in the specified time window for each one:  Time Open1, Time Open2, TimeClose1, Time Close2 - the current time must be in these intervals in order to mark the vertex as visited.
The starting point is always vertex 0

For my example I have:
Vertices that must be visited and their time window (values with -1 are not taken into consideration):

Vertex To1  Tc1  To2  Tc2
  1    0    260  340  770
  4    0    240  -1   -1
  5    170  450  -1   -1

Edges are open in the following time window (values with -1 are not taken into
consideration):

Edge To1  Tc1  To2  Tc2
0-1  0    770  -1   -1
0-4  0    210  230  770
0-5  0    260  -1   -1
1-2  0    160  230  770
1-5  40   770  -1   -1
2-4  80   500  -1   -1
3-4  60   770  -1   -1
3-5  0    770  -1   -1

So the basic idea is to start with vertex 0 and find the shortest route to traverse
vertices 1, 4 and 5 taking in consideration the specified time.
Also if for example you have done 0-1 but you can't use 1-5 you can do 0-1-0-1-5.

I start with vertex 0, end with one target vertex while I have visited all other target vertices at least once respecting the conditions imposed on the edges and target vertices.
For example:
A possible solution is 0 - 4 - 3 - 5 - 1 with a total time of 60+50+60+50=220
From 0 I can also go directly to 5 but as stated in conditions in order to mark vertex 5
I must have a cumulative time between 170 and 450. Also if I go 0-4 I can't use edge 4-2 because it opens at 80 and my cumulative time is 60. Note I can use 0-4-3 because 4-3 opens at 60 and to do 0-4 it takes a time equal to 60.
So is there a way to solve this using dijkstra or other path finding algorithms ?

Thanks in advance for any help!

Edit

My solution for now is something like this

         0
  1      4      5
0 2 5  0 2 3  0 1 3

Basically I try all possibilities. The conditions for stopping in expanding a branch are:
1. I have too many duplicates like I have 0 1 0 4 0 1 0 - so I stop because I have a set number of duplicate 0 values which is 4
2. I find a road that contains all the vertices to mark
3. I find a road that takes longer than another complete road

It is NP-hard to decide whether your problem is soluble. That's bad news from a theoretical point of view, but in practice it is possible that a heuristic algorithm will fare quite well. Also, you're (possibly) dealing with the "promise" variant of the problem, that is, you assume that a solution exists, and want to find it.

To see that the problem is NP-hard, we reduce Hamiltonian cycle to it. All the edges are always open, and they always have unit weight. The windows for each non-zero vertex are $[1,n-1]$ and $[n+1,2n-1]$; for vertex zero they are $\{0\}$ and $\{n\}$. These constraints are satisfiable only via a Hamiltonian cycle, and the converse is also true.


Scaling procedures to address false 0's after multiplying probabilities I need to translate a training algorithm that involves sums and multiplications of probabilities to actual code. For that I need some sort of scaling procedure that allows me to avoid underflows, that is, misleading 0 probabilities.

A typical method is to apply the logs of probabilities but because of the sums this is not readily possible for my case. Another approach I saw in Rabiner's tutorial on HMMs, was his scaling procedure only dependent on t (time) applied to the forward algorithm and (the other way around) the backward algorithm, that when combined cancel each other to obtain the desired trained probabilities.

My question
I wonder if there are books or text resources explaining common approaches to tackle the underflow problem that results in working with continuous multiplications of probabilities. Do you know any?

I hope I can get some ideas from that.

A simplee trick (explained here) that let you use the $\log$ approach even when you must sum probabilities.

Problem: $\log(\exp(a) + \exp(b))$ can lead to an underflow, to avoid it you can use this formula:

$\log(x + y) = \log(x) + \log(1.0 + \exp( \log(y) - \log(x) ) )$

Or use another approach:

$\log(\exp(a) + \exp(b)) = \log( \exp(a - C) + \exp(b - C)) + C$

Setting $C = \max(a,b)$

For example: $\log(e^{-120}+e^{-121}) = \log(e^{-120}(e^0 + e^{-1}))= \log(e^0+e^{-1})-120$


Reduction of graph chromatic number to hypergraph 2-colorability I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this paper, the author tries to reduce graph chromatic number to hypergraph 2-colorability (same as set splitting).

You can find the paper here: http://web.cs.elte.hu/~lovasz/old-papers.html

I'm reproducing the reduction below.

Let $G$ be a graph, $V(G) = \{x_1,\dots,x_n\}$. Let $G_i$ be an isomorphic copy of $G$, $(i=1,\dots,k)$, $V(G_i) = \{x_{i,1},\dots,x_{i,n}\}$ ($x_{iv}$ is a point corresponding to $x_v$). Take a new point $y$ and let $f_v = \{x_{1,v},\dots,x_{k,v},y\}$. Define hypergraph $H$ by
$$
  H = E(G_1) \cup \dots \cup E(G_k) \cup \{f_1,\dots,f_n\}.
$$
Then $H$ is 2-colorable if and only if $G$ is $k$-colorable. I don't understand this conclusion and the only example I've been able to come up with where this is true is $k = 1$.

As the other answer points out, the reduction in the original paper seems to have a bug: $H$ will not be two-colorable unless $G$ is bipartite. I couldn't quite see how to prove the reduction in the other answer works, but here is one that I think does.

The vertices of $H$ will be $\{x_{i, v}: i \in [k], v \in V(G)\} \cup \{z\}$. $H$ has an edge $f_v = \{x_{1,v}, \ldots, x_{k,v}\}$ for every $v \in V(G)$,  and, for each $(u,v) \in E(G)$, and each $i \in [k]$, an edge $\{z, x_{i,u}, x_{i,v}\}$.

Given a coloring $\chi_G:V(G) \to [k]$ of $G$ you can construct a $2$-coloring $\chi_H:V(H) \to \{0,1\}$ of $H$ by setting

$$
\chi_H(z) = 1,\\
\chi_H(x_{i,v}) = 1 \iff \chi_G(v) = i.
$$

It's easy to check that no edge of $H$ is monochromatic.

In the other direction let $\chi_H$ be a proper 2-coloring of $H$, and assume that $\chi_H(z) = 1$. (If this is not the case just rename the colors.) Since no edge $f_v$ is monochromatic, for every $v \in V(G)$ there is some $i$ such that $\chi_H(x_{i,v}) = 1$. Pick an arbitrary such $i$ and set $\chi_G(v) = i$. This is a proper coloring, or otherwise there would be an $i \in [k]$ and an edge $(u,v) \in E(G)$ such that $\chi_H(x_{i,u}) = \chi_H(x_{i,v}) = 1$, which would make the edge $\{z, x_{i,u}, x_{i,v}\}$ of $H$ monochromatic.


Communication complexity of finding common element of two subsets Suppose that Alice receives a subset $S \subseteq \{1,\dots,n\}$ and Bob receives $T \subseteq \{1,\dots,n\}$.  It is promised that $\lvert S \cap T \rvert = 1$.  What is the randomized communication complexity of determining the common element $S \cap T$?

My interest in this is as follows.  The zero-communication cost of this problem is $\log n$ since Alice and Bob can just guess $S \cap T$ using public coins and abort if they guess wrong.  However, I can't think of an $O(\log n)$ cost communication protocol.  Since it is not known whether zero-communication cost is much less than randomized communication cost, I am thinking that I am missing something obvious here.

Zero-communication cost is defined as follows.  After Alice and Bob receive their inputs, they must not communicate at all.  However, they share public coins, and they are allowed to answer with "abort".  If neither party aborts, they must provide the correct answer with $2/3$ probability.  The zero-communication cost is the negative log of the probability of not aborting.  In arxiv:1204.1505 it is shown (among other things) that nearly all known lower bounds on communication complexity are in fact lower bounds for zero-communication.

Update: @Shitikanth showed that the communication complexity is $\Omega(n)$.  So, apparently this gives a gap between communication cost and zero-communication cost.  But arxiv:1204.1505 seems to give the impression that no such gap is known.  What am I missing?

(Reduction from set disjointness)

Suppose Alice and Bob are given sets $S, T \subseteq [n]$ with the guarantee
that $|S\cap T| \leq 1$. Alice and Bob run the protocol for finding the common
element of $S$ and $T$ assuming that their sets have a non-trivial intersection
to decide a common element $X$. Now, they can communicate with each other to
verify that $X$ is in fact common to both $S$ and $T$ with $O(\log n)$ bits.

Therefore, any protocol for finding the common element of $S$ and $T$ must take $\Omega(n)$ bits of communication.


Empirical results in CS papers I'm new to the CS field and I have noticed that in many of the papers that I read, there are no empirical results (no code, just lemmas and proofs). Why is that? Considering that Computer Science is a science, shouldn't it follow the scientific method?

Implementing algorithms well is a skill which takes a different set of tools than just proving theorems. Many algorithms which were discovered by the theory community have indeed been implemented in practice (although I would like to see the theory community take a bigger role in this process). Physics doesn't ask the same researchers to do theory and experiment, although it is expected that the two groups communicate. Why shouldn't you expect to see the same divide in computer science?

ADDED IN EDIT:

Expanding on my comment in answer to Suresh's about what I meant by "role" above, at Bell Labs and AT&T Labs, researchers in algorithms were encouraged to talk to people in development. I didn't do as much of this as I probably should have, but I did get at least one paper out of it, and I think it would be good for the field if there were more communication between people in theory at universities and practitioners. This doesn't mean that I think everybody who comes up with an algorithm should code it (even if it's practical).

On the other hand, coding algorithms (or having a student code them) that you think might be practical can be useful in getting them adapted by practitioners. Consider one example. Lempel and Ziv wrote two technical papers in 1977 and 1978 on new data compression algorithms. Everybody ignored them. In 1984, Welch wrote a much less technical paper giving a slight twist on LZ78 that improved its performance somewhat, and gave the results of a small study comparing its performance with other data compression methods. It was published in a journal read by a number of programmers, and the algorithm was given by a few lines of pseudocode. The method was quickly adapted in a number of places, eventually resulting in an infamous intellectual property dispute.

Of course, one of the best ways for algorithms researchers to communicate with practice is to produce grad students who go off and work at Google, IBM, or other companies, and we're already doing that. Another way might be to answer practitioner's questions in this forum. Hopefully, we're doing a reasonable job of that as well.


What is the motivation behind defining Deterministic Looping Automata? I was wondering about what could possibly be the motivation behind defining the deterministic looping automata? What puzzles me is that they accept a word iff they have a run on it!

I believe they are strongly related to DBWs. And i would like to see how.

My intuition:
since we can assume W.l.o.g that each non-accepting state $q$ in a DBW $A$ has a loop of non-accepting states containing q. Maybe one can look at the $strongly$ $connected$ $components$ of $A_{rej}$, Where $A_{rej}$ denotes $A$ restricted to non-accepting states, as looping automata.

Relevant papers could help.

Note: i am new to research. In particular i have few knowledge about DBWs. Its more a reference than a question.

thanks.

In a looping automaton, the transition function is not assumed to be total. That is, for a state $q$ and a letter $\sigma$, it could be the case that $\delta(q,\sigma)$ is undefined.
Intuitively, this is the same as having a transition to a rejecting sink.

So they are "deterministic" in the sense that there is no non-determinism. But still, this means that for every word either there is a single run, or there are no runs. Thus, saying that a word is accepted iff it has a run on it is not a trivial acceptance condition.

The reason for studying these automata is that they correspond to safety properties. A safety property is a language $L$ such that for every word $w\notin L$, there exists some prefix $x$ of $w$ such that for every suffix $y$, $x\cdot y\notin L$. That is, once you read $x$, there is no way to get in the language.
These properties are useful in practice, as they correspond to "system failure", in a way. That is, once something really bad happens, you can't recover.

Technically, these autoamta are useful because of their simple acceptance condition.

As for references, start here. Also, Orna Kupferman has several papers using these objects (but I suspect you already know that... :) )


Is the following graph optimization problem approximable within a constant factor? Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$.
For a node $v\in V$, we denote by $\text{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of neighbors of $v$ that occur before $v$
(respectively after $v$) in the permutation $\pi$.

  Problem. For a given undirected graph $G=(V,E)$, find a
  permutation $\pi$ of the vertices that minimizes the objective value
  $$\sum_{v\in V} ~\left|\text{succ}_{\pi}(v)\right|\times
\left|\text{pred}_{\pi}(v)\right|.$$

Is there a polynomial time approximation algorithm for this problem, that approximates the optimal objective value within a constant factor?  The problem is known to be NP-hard.

The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. For brevity, let me call you problem $\cal P$ and Min Uncut $\cal U$.
Observation. An instance $G$ of $\cal P$ has a solution of cost 0 if and only if $G$ is bipartite.
Proof: Assume that $G$ is bipartite with parts $L$ and $R$. Consider $\pi$ that first puts the vertices from $L$ and then the vertices from $R$ (the relative ordering of vertices in $L$ and $R$ may be arbitrary). Then the cost of this solution is $0$, as required.
Now assume that $G$ has a solution $\pi$ of cost $0$. Note that $G$ cannot have an odd cycle. Indeed if $a_1  \to a_2 \to \dots \to a_k$ is an odd cycle, then the direction of edges along the cycle should alternate: say $(a_1, a_2)$ goes forward (w.r.t. $\pi$), then $(a_2, a_3)$ goes backward, then $(a_3, a_4)$ goes forward etc (or the other way around). That is impossible since the cycle is odd. We conclude that $G$ doesn't have any odd cycles and thus is bipartite.
QED
Claim. Let $G$ be a regular graph, whose vertices have degree $d$. Denote the costs of optimal solutions of problems $\cal U$ and $\cal P$ in $G$ by $U_G$ and $P_G$, respectively. Then
$$P_G =\Theta(d\cdot U_G).$$
Proof: Let $E'$ be an optimal solution for $\cal U$ in $G$. Then $|E'| = U_G$. Let $(L, R)$ be a bipartition of $G - E'$. Consider a permutation $\pi$ defined by $L$ and $R$, as in the proof of Observation. The cost of $\pi$ is at most $d \cdot |E'| = d\cdot U_G$ (to get this, write the formula for the cost of $\pi$; upper bound $|\mathrm{succ}_{\pi}(u)|$ by $d$ for vertices in $L$; upper bound $|\mathrm{pred}_{\pi}(u)|$ by $d$ for vertices in $R$). Thus, $P_G \leq d\cdot U_G$.
Now consider an optimal solution $\pi$ for $\cal P$. For every vertex $u$, either $|\mathrm{pred}_{\pi}(u)| \leq d/2$ or $|\mathrm{succ}_{\pi}(u)| \leq d/2$. In the former case, mark edges from $u$ to $\mathrm{pred}_{\pi}(u)$ as bad; in the latter case, mark edges from $u$ to $\mathrm{succ}_{\pi}(u)$ as bad. Note that when we process $u$, we mark $\min(|\mathrm{pred}_{\pi}(u)|, |\mathrm{succ}_{\pi}(u)|)$ edges. We have,
$$\min(|\mathrm{pred}_{\pi}(u)|, |\mathrm{succ}_{\pi}(u)|) \leq |\mathrm{pred}_{\pi}(u)| \times |\mathrm{succ}_{\pi}(u)| / (d/2).$$
Adding up this inequality over all $u$, we get that the total number of bad edges is at most $2P_G/d$. Now let $E'$ be the set of bad edges. Clearly, $P_{G- E'} = 0$. From Observation, we get that $G-E'$ is bipartite. Thus, $E'$ is a feasible solution for $\cal U$. We conclude that $U_G \leq 2P_G/d$.
We have proved that
$$\frac{d}{2} U_G \leq P_G \leq d\cdot U_G.$$
QED
We see that in regular graphs, $\cal P$ and $\cal U$ are essentially equivalent. Note that it was shown in

Chawla, Shuchi, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D.
Sivakumar. "On the hardness of approximating Multicut and
Sparsest-cut." Computational Complexity 15, no. 2 (2006): 94-114.

that there is no constant factor approximation for $\cal U$ if the Unique Games Conjecture holds. On the other hand, there is an $O(\sqrt{\log n})$ approximation algorithm for $\cal U$; see

Agarwal, Amit, Moses Charikar, Konstantin Makarychev, and Yury
Makarychev. "$O(\sqrt{\log n})$ approximation algorithms for Min UnCut, Min
2CNF Deletion, and directed cut problems." In Proceedings of STOC 2005, pp. 573-581.

What about the regularity assumption?
The regularity assumption is not really necessary and was made above to simplify the exposition.
Hardness of approximation. We can start with any (not necessarily regular) instance $G = (V, E)$ of $\cal U$. Let $d$ be the maximum degree of $G$. Attach $d - \deg u$ new vertices to every vertex $u\in V$. We will obtain a new graph $G' = (V', E')$, in which every vertex has degree $d$ or $1$. Clearly, $U_{G} = U_{G'}$. Now we apply the reduction from Claim to $G'$. It's easy to see that the reduction still works for $G'$, even though it's not regular (since $\deg u\in\{1, d\}$ for every $u$).
Algorithm. Given an instance $G = (V, E)$ of $\cal U$, we create a weighted graph $G'$; $G' = (V, E, w)$ is the same graph as $G$ except that edge $(u,v)$ has weight
$$w(u,v) = \min(\deg u, \deg v).$$
We solve $\cal U$ in $G'$, and get a partition $(L,R)$ of $V$. We define $\pi$ as follows: first put vertices from $L$ and then vertices from $R$. Importantly, the order of vertices in $L$ and in $R$ is not arbitrary now. We put vertices with smaller degrees closer to the boundary between $L$ and $R$. (In other words, vertices in $L$ and $R$ are sorted by their degrees in the descending and ascending orders, respectively.) It's not hard to see that this algorithm gives $O(\sqrt{\log n})$ approximation.
Conclusion:

There is no constant factor approximation for $\cal P$ if the Unique
Games Conjecture holds.
There is an $O(\sqrt{\log n})$ approximation algorithm.
In order to get a better approximation factor, one needs to improve the best known approximation algorithm for Min Uncut (which would be a breakthrough result in the field, especially since the problem is closely related to Sparsest Cut and Balanced Cut).

(Informal note: we will not get any better algorithms if we assume that the graph has a high average degree or a relatively low average degree.)
Generalization: The proof can be adapted in a straightforward way to this problem, where instead of looking for a permutation of the nodes, we look for an orientation of the edges (that is a less constrained problem where the edge orientation does not have to induce a DAG).
It can also be adapted in a straightforward way to the case where the objective to minimize is $\sum_{v\in V} ~\min(\left|\text{succ}_{\pi}(v)\right|,
\left|\text{pred}_{\pi}(v)\right|)$ instead of $\sum_{v\in V} ~\left|\text{succ}_{\pi}(v)\right|\times
\left|\text{pred}_{\pi}(v)\right|$. Interestingly, with that new objective we have $U_G = P_G$.


How powerful is POSIX regex The set of languages recognized by POSIX regex is a true superset of type 3 languages. But how powerful is POSIX regex really? Is it in an already known class? Is it its own class? If so, what is the next bigger class (for some context)?

Proof that POSIX regex is more powerful than type 3:

(a+)b(\1) which recognizes $\{ a^nba^n | n \geq 1 \}$

I haven't found a really good description of what features POSIX regex allows but this is one link that lists all features (as far as I know): regex manual

Emil Jeřábek mentioned that POSIX regex is not even completely contained in type 2 languages because (.*)\1 is $\{ ww | w \in \Sigma^* \}$. So, it recognizes all type 3 languages, some type 2 languages and some type 1 languages, maybe even some type 0 languages.

In [1], the authors formally define the notion of an "extended regex" with the intent of capturing the back-reference capability of POSIX/perl/emacs/etc style regexes. Exactly how closely their definition matches the exact POSIX specification is an exercise left to the reader.

Under their definition, extended regexes are a proper subset of Type 1 (context-sensitive) languages and incomparable with Type 2 (context-free) languages. They show that extended regexes are a subset of Type 1 languages by showing how to construct an equivalent LBA for any extended regex. They prove that they're incomparable with Type 2 languages by showing that $\{a^nba^nba^n|n \geq 1\}$ (which is not context-free) can be recognized by an extended regex while $\{a^n b^n | n \geq 0\}$ (which is context-free) cannot.

Câmpeanu, Cezar, Kai Salomaa, and Sheng Yu. "A formal study of practical regular expressions." International Journal of Foundations of Computer Science 14.06 (2003): 1007-1018.


Is the longest trail problem easier than the longest path problem? The longest path problem is NP-hard. The (typical?) proof relies on a reduction of the Hamiltonian path problem (which is NP-complete). Note that here the path is taken to be (node-)simple. That is, no vertex can occur more than once in the path. Obviously it is thus also edge-simple (no edge will occur more than once in the path).

So what if we drop the requirement of finding a (node-)simple path and stick to finding an edge-simple path (trail). At first glance, since finding a Eulerian trail is much easier than finding a Hamiltonian path, one might have some hope that finding the longest trail would be easier than finding the longest path. However, I cannot find any reference proving this, let alone one that provides an algorithm.

Note that I am aware of the argument made here:
https://stackoverflow.com/questions/8368547/how-to-find-the-longest-heaviest-trail-in-an-undirected-weighted-graph
However, the argument seems flawed in its current form, as it basically shows you could solve the edge-simple case by solving the node-simple case on a different graph (so the reduction is the wrong way around). It is not clear that the reduction could easily be changed to work the other way as well. (Still, it does show that at the very least the longest trails problem is not harder than the longest paths problem.)

So are there any known results for finding longest trails (edge-simple paths)? Complexity (class)? (Efficient) algorithm?

From the comments above: the Hamiltonian cycle problem remains NP-complete even in grid graphs with max degree 3 [1], but in these graphs every traversal of a node requires two edges and at most one edge remains unused, so a node cannot be traversed twice by an Eulerian path.

So apparently there is an immediate reduction from the Hamiltonian cycle problem to your problem:
given a grid graph with max degree 3 $G = (V,E)$, just ask for a trail of length $|V|$.

But all three edges of the node at the end of the trail can be used; to avoid this situation you can pick the top-left node $u$ of the grid graph (which has degree two) and add two nodes: $V' = V \cup \{u',u''\}$ and a new edges $E = E \cup  \{(u,u'), (u,u'')\}$ and ask for a trail of length $|V'| = |V|+2$: informally the added edge forces $u',u''$ to be the endpoints of the trail.

[1] Christos H Papadimitriou, Umesh V Vazirani, On two geometric problems related to the travelling salesman problem, Journal of Algorithms, Volume 5, Issue 2, June 1984, Pages 231-246, ISSN 0196-6774


Recent progress on the next-to-shortest-path problem for directed graphs? In the paper "Computing strictly-second shortest paths" (1997), Lalgudi and Papaefthymiou consider the following problem:

Let $G$ be a directed graph with edge-weighting $w$. Let $u,v$ be vertices in $V(G)$. Let $p_1$ be a path of minimum weight from $u$ to $v$. Compute a simple path $p_2$ from $u$ to $v$ with $w(p_2) > w(p_1)$ and such that for any other path $p$ from $u$ to $v$ with $w(p) > w(p_1)$, we have $w(p) \ge w(p_2)$.

They prove that this problem is NP-hard. Their proof involves choosing a weight function that takes value $1$ on a certain edge and $0$ elsewhere, so it relies in a fundamental way on the possibility of there being edges of weight $0$.

Is anything known about whether the problem remains NP-hard when one restricts to unit-weight graphs, that is graphs for which $w(e) = 1$ for each $e \in E(G)$?

My first intuition is certainly naive. What's wrong with it?

Since $p_2$ is different from $p_1$ on at least one edge, repeatedly remove one edge in $p_1$ from the graph and solve the shortest path problem, which would be at worst $n$ times the complexity of the shortest path problem.


Deciding whether the sum of independent random variables exceeds a threshold a majority of the time, PP-hard? Say I have $n$ independent Bernoulli random variables, with parameters $p_1,\ldots,p_n$. Say, also, that I wish to decide whether their sum exceeds some given threshold $t$ with probability at least $0.5$. What is the computational complexity of this decision problem, when $p_1,\ldots,p_n$ and $t$ are represented in binary and given as input?

More generally, I'm interested in the generalization of this problem to (non-Bernoulli) discrete distributions. Specifically, there are $n$ independent random variables, each supported on at most $m$ rational numbers, with each variable's probability histogram given explicitly in the input. In this case, also, I want to decide whether the sum of these variables exceeds $t$ with probability at least $0.5$.

I have a feeling this problem is PP-hard, though I can't quite prove it. I wonder what the answer is, and whether it's already known.

Note that I'm not looking for approximation algorithms for this problem. It's clear that monte carlo methods yield positive answers to approximate versions of this decision problem. I'm interested in the exact decision problem as stated above.

The general (non-bernoulli) problem is #P hard, via a reduction from #Knapsack.

#Knapsack is the problem of counting the solutions to an instance of the knapsack problem. This problem is known to be #P complete. An equivalent way to think of the #Knapsack problem is the following: You are given a set of integers $a_1,\ldots,a_n$ and a threshold $t$. Let $x_i$ be a random variable which is either $0$ or $a_i$ with equal probability, and assume those random variables are independent. Compute the probability that $\sum_i x_i \leq t$.

It is not too hard to see that the #Knapsack problem could be equivalently defined as the problem of computing the probability that $\sum_i x_i \geq t$ (simply flip the sign of all the integers and add a large constant). Therefore, had I stated my problem with an arbitrary probability $p$ rather than $0.5$, the problem stated in the question can be interpreted as the decision version of #knapsack. A reduction of #knapsack to its decision version via binary search would then complete the #P hardness proof.

The way I defined the problem, however, fixed a particular threshold 0.5. It's not too hard to see that this doesn't make the problem easier. We can reduce the decision problem with probability $p\leq 0.5$ to the problem with $p=0.5$ by simply adding an additional random variable $x_0$ which is equal to the threshold $t$ with probability $\frac{0.5-p}{1-p}$ and $0$ the rest of the time. For $p > 0.5$, a similar reductions lets $x_0$ be $-M$ for a sufficiently large $M$ with probability $\frac{p-0.5}{p}$ and $0$ otherwise; if you don't like negative numbers, simply shift all random variables and the threshold $t$ up by a suitable constant.


Finding a minimum "node" weight path Suppose a graph with node weights only (no edge weights). For a given source-sink pair, how can I find a path with the minimal sum of node weights? Does this problem have a name? Is it possible to reformulate this to a shortest-path problem?

If both nodes and edges are weighted, is it still possible to find a min-weight path?

You can treat this as a directed graph problem, where the weights of all edges coming into a node are equal to that node's weight.

If the edges are weighted too, add the node's weight and the edge's weight together to find the incoming edge's weight in the directed graph.


What is theoretical computer science? What exactly is theoretical computer science? Is it learning to code in various language and making apps in platforms? Or is it just thinking about faster and faster algorithms so that you can achieve a task more efficiently by the computers? Or is it programming and thinking of new life situations which can be simulated on a computer? What exactly are we trying to do here ?

For example, physics is trying to find all the laws of nature that govern it; mathematics is a tautology based to model reality and used as a very precise language by other subjects.

What exactly is theoretical computer science? When computers were designed by us humans for application purposes, hence it must all drop down to mathematics and physics in the end? Then where is the "theory" in computer science itself.

Sorry for being too naive but I want to know what does a theoretical computer scientist do ?

Your question itself is not naive but the type of answer you ask for is. It is rare for any line of work or intellectual enquiry to have an elevator pitch explanation. Not all would agree with your characterizations of mathematics and physics because they ignore the depth and nuances of those fields.

Theoretical computer scientists are concerned with studying and applying computation. The computational perspective is a deep and all encompassing one so the study of computation is also deep and has a bearing on many other areas of study. Every single process, whether arising in nature or synthetic, manipulates information. They compute. As in mathematics, there are different languages and types of structures involved in computation, as in physics, there are fundamental laws about computation that we are trying to discover, as in chemistry, fundamental elements of computation can be classified. Theoretical computer science is broad and robust enough to be amenable to any perspective you bring to it. Some of the questions studied are:

What is computation and how can it be characterized? (Turing machines, lambda calculi, tiling systems, register machines, DNA computers etc.)
What is the computational model underlying a process? (Biological, chemical, economic, sociological processes, etc.)
What is efficient computation? (complexity via time, space, communication, amortized, smoothed, etc.)
What are characterizations of efficient computation? (Turing machines, algebraic notions, logic, type systems, etc.)
What is the most efficient way to  compute a solution to a problem? (algorithms)
How efficient are existing algorithmic processes (analysis of algorithms, statistical phenomena, market equillibria, etc.)

These are a small and non-representative sample of the questions that one may ask. As in any field, answers to some questions generate new questions and drive enquiry about other questions. You can find a rather dated view of the field by browsing the articles in the Handbook of Theoretical Computer Science.

Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, 1990
Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics, 1990


Are there any distributions with only polynomially many non-zero Fourier coefficients and a small support? For a distribution X over $\{0,1\}^n$, we can define the Fourier coefficient of the distribution as $\hat{Y}(s)= \textbf{E}_{y\in Y}({\chi_s(y)})$.
The question I have is, do there exist distributions that can be efficiently computed such that at most polynomially many Fourier coefficients are non-zero?

If you want $Y$ to have entropy less than $0.99 n$ bits, the answer is no, by the uncertainty principle: Either $Y$ has high entropy or its Fourier transform has large support.

Theorem. Let $H(Y)$ be the Shannon entropy of $Y$ and let $F  \subset \{0,1\}^n$ be the support of $\hat{Y}$. Then $H(Y) \geq n - \log |F|$.

Proof. Consider the collision probability of $Y$ (the probability that two independent samples of $Y$ are the same). By Parseval's identity,
$$CP(Y) = \sum_y \text{Pr}[Y=y]^2 = 2^{-n} \sum_s \hat{Y}(s)^2 \leq 2^{-n} |F|,$$ as $|\hat{Y}(s)| \leq 1$. On the other hand, $CP(Y) = 2^{-H_2(Y)}$, where $H_2(Y)$ is the Renyi entropy of $Y$. Noting that $H_2(Y) \leq H(Y)$ gives the result. Q.E.D.

If $|F| = \mathrm{poly}(n)$, then $H(Y) = n-O(\log n)$. So, if $Y$ is the output of a pseudorandom generator, the seed length is at least $n-O(\log n)$.


Is $\{0,1\}$-Vector bin packing NP-Hard when vectors have constant dimension? The paper https://cs.brown.edu/people/seny/pubs/vbponline.pdf discusses $\{0,1\}$-Vector Bin packing in the online setting and give lower bounds. However, they do not mention anything about the complexity of the problem in the offline setting. I could not find any other papers mentioning this either.

Formally, the problem is as follows: Given a set of vectors $V=\{x_1,x_2,\ldots,x_n\}$, where each $x_i\in\{0,1\}^d$, and a vector $\textbf{b}=(b_1,b_2,\ldots,b_d)\in \mathbb{Z}_+^d$, partition $V$ into $V_1,V_2,\ldots,V_l$ such that $\forall~j,\sum_{x_i\in V_j} x_i \leq \textbf{b}$. Then the objective is to minimize the number of partitions, $l$.

While the problem in general can easily be seen to be NP-Hard from Independent set or, as Yonatan pointed out, $k$-colouring, I'm interested in the case when the vectors are from $\{0,1\}^d$, where $d=O(1)$. It is known that $[0,1]$-vector packing is NP-Hard even under this restriction, because it is a generalization of bin packing. However, I did not find anything for the $\{0,1\}$ case. Is this problem NP-Hard?

Neal Young has given an excellent answer for the case when the vector $\textbf{b}$ has $\forall ~i,b_i=O(1)$. This leaves the case where $b_i$ is not constant. In particular, $b_i=\Omega(n)$ seems to remain hard.

Edit: It seems that the problem has been considered, at least in the knapsack context, here. Their algorithm for the $d=2$ case seems very non-trivial. This seems to suggest that the ILP approach suggested by Gamow wouldn't work.

EDIT: Merged the two answers.

Here's the problem statement:

The input is $(V, \mathbf b, \ell)$, where $V=\{x_1,x_2,\ldots,x_n\}$ with each $x_i\in\{0,1\}^d$ (where $d$ is constant), vector $\textbf{b}=(b_1,b_2,\ldots,b_d)\in \mathbb{Z}_+^d$, and $\ell$ is an integer.
The problem is to decide whether $V$ can be partitioned into $\ell$ parts $V_1,V_2,\ldots,V_\ell$ such that $\forall~j,\sum_{x_i\in V_j} x_i \leq \textbf{b}$.

Lemma 1. The problem (with $d=O(1)$) reduces to a sparse language, so is not NP-hard unless P=NP.

Lemma 2. For $d=O(1)$ and $\ell=O(1)$, the problem can be solved in polynomial time via dynamic programming (EDIT: or an ILP of constant dimension).

Lemma 3. For $d=O(1)$ and $\max_j b_j=O(1)$, the problem can be solved in linear time (in the real RAM model) via an ILP of constant dimension.

This leaves open the complexity of the case when $\ell$ and $\max_j b_j$ are both allowed to grow (while $d=O(1)$).  This case could be in P, or not in P but not NP-hard.

Proof of Lemma 1. One can faithfully re-encode any problem instance given in the form above into a representation that uses only $O(\log n)$ bits, as follows. For each of the $2^d$ possible vectors in $\{0,1\}^d$, write down the number of times that vector occurs in $V$.  Write down $\ell$ and each entry of $\mathbf b$.

There are $2^d + d + 1$ numbers written, and each number is at most $n$, so the encoding size is $\Theta(2^d\log n)$ bits.)  It follows that (for fixed $d$) the number of distinct instances of size $n$ is polynomial in $n$.  This implies (details next) that the decision problem cannot be NP-hard unless P=NP.

In more detail, let $L$ denote the language for the problem encoded as first defined.  Assume that $L$ is NP-hard.  Define $L' = \{(f(V, \mathbf b, \ell), 1^{|V|}) : (V, \mathbf b, \ell) \in L\}$, where $f(V, \mathbf b, \ell)$ is the re-encoding of the instance as described above (into $O(\log |V|)$ bits), and $1^{|V|}$ is $|V|$ in unary.

$L$ reduces in poly-time to $L'$, so $L'$ is also NP-hard.  But $L'$ is sparse (the number of elements of size $n$ is polynomial in $n$), so P=NP (by Mahaney's theorem). $~~~\Box$

Proof of Lemma 2.
The algorithm will solve the following more general problem.
The input is $(V, \mathbf B)$ where $V=\{x_1,\ldots,x_n\}$ (as before) and $\mathbf B = (B_1, B_2, \ldots, B_\ell)$ is a collection of $\ell$ vectors,
where each $B_j$ is in $\{0,1,\ldots,n\}^d$.
The problem is to decide whether there is a partition of $V$ into parts
$(V_1, V_2, \ldots, V_\ell)$ such that $\forall j,~\sum_{x_i\in V_j} x_i = B_j$.

This differs from the original problem in two ways.  First, each part $V_j$ in the partition can have a different required sum $B_j$ (instead of $\mathbf b$).  Second, equality must hold (the sum must equal $B_j$, rather being $\le \mathbf b$).

A given instance $(V, \mathbf b, \ell)$ of the original problem poly-time reduces to this one by considering all instances of this one of the form $(V, \mathbf B)$ where each $B_i$ is in $\{0,1,\ldots,n\}^d$ and $B_i \le b$.  There are $O(n^{d\ell})$ such instances, which is polynomial since $d$ and $\ell$ are constant.  The original instance will have a solution if and only if at least one of the latter instances does.

The algorithm solves the variant using the following dynamic program.  Fix an instance $(V,\mathbf B)$ of the problem.  Let $V=\{x_1,\ldots,x_n\}$ and $\mathbf B = (B_1,\ldots,B_\ell)$. So $x_i\in\{0,1\}^d$ and $B_j\in \{0,1,\ldots,n\}^d$ for each $i$ and $j$.

Define the signature of the instance $(V, \mathbf B)$ (following the proof of Lemma 1) to be obtained by replacing $V$ by the natural encoding of the function $f_V$ such that, for each $x\in\{0,1\}^d$, $f_V(x)$ is the number of times $x$ occurs in $V$.  Note that any two instances with the same signature are equivalent, in that they have the same answer.

The signature is determined by $2^d + d\ell$ numbers, each in $\{0,1,\ldots,n\}$, so the number of possible signatures (among instances with the given parameters $d,\ell, n$) is $O(n^{2^d+d\ell})$, which (given that $d$ and $\ell$ are constant) is polynomial in $n$.  Furthermore, the number of possible signatures of all "smaller" instances (meaning those where $n$ is smaller than the given $n$) is at most a factor of $n$ larger, so also polynomial in $n$.

Now we can proceed via dynamic programming.  Fix the given instance $(V, \mathbf B)$. For the base case, if $V=\emptyset$ (that is, $n=0$), then the instance is feasible iff each $\mathbf B \equiv \mathbf 0$.  Otherwise $x_n$ can go into one of the parts $V_j$ for $j\in\{1,2,\ldots,\ell\}$, such that removing $x_n$ from that part gives a solution to the problem obtained by subtracting $x_n$ from $\mathbf B_j$ (as long as $x_n\le \mathbf B_j$; if not $x_n$ cannot go in $V_j$).

For each of the (at most) $\ell$ possible ways of placing $x_n$, recursively determine whether the resulting subproblem has a solution.  The original problem will have a solution if and only if one of these subproblems does.

Furthermore, memoize -- keep a cache of the answers to already-solved subproblems, indexed by signature.  When encountering a given subproblem, check whether any subproblem with the same signature has already been answered, and if so use that answer instead of recursing.  Because there are only polynomially many distinct signatures of smaller subproblems, the dynamic-programming algorithm will solve only polynomially many subproblems, so will run in time polynomial in $n$. $~~\Box$.

EDIT: As pointed out in the comments, an easier approach is (similarly to the proof of Lemma 3 below) to formulate an ILP of constant dimension, with a variable $y_{xj}$ for each $x\in\{0,1\}^d$ and $j\in\{1,\ldots,\ell\}$ representing the number of vectors in $V$ that are equal to $x$ and are assigned to part $V_j$.

The proof above raises the question of whether the variant defined in the proof is NP-hard when $\ell$ is not constant.  (It might be, even if the original problem is not.)

Proof of Lemma 3.
The proof is an elaboration of @Gamow's answer in the comments.

Use the following equivalent problem formulation: Given a collection $V=(S_1, S_2, \ldots, S_n)$ of subsets of $\{1,2,\ldots, d\}$, where $d$ is constant, partition $V$ into a minimum number of parts, such that within each part each element $j$ occurs in more than $b_j$ subsets.  Here is the algorithm.

Fix an input $V=(S_1, \ldots, S_n)$ of subsets of $\{1,2,\ldots, d\}$.
Let $\mathcal S_d$ denote the set of non-empty subsets of $\{1,2,\ldots,d\}$.
Let $\mathcal P_d$ denote the set of possible parts, that is, multi-subsets of $\mathcal S_d$ in which each element $j$ occurs at most $b_j$ times.
The goal is to partition the input $V$ into a minimum number of parts, each of which is in $\mathcal P_d$.

Note that $|\mathcal S_d| < 2^d$ and $|\mathcal P_d| \ll (bd)^{bd}$, so (as $b$ and $d$ are constant) there are constantly many possible subsets, and constantly many possible parts.

For each subset $S\in\mathcal S_d$ and possible part $p\in\mathcal P_d$, let $n(S, p)$ (either 0 or 1) denote the number of times that $S$ occurs in $p$.

For each possible subset $S\in\mathcal S_d$, count the number of times that $S$ occurs in the input $V$. Let $n(S, V)$ denote this number.

Finally, construct and solve the following integer linear program (ILP), with an integer-valued variable $x_p$ for each possible part $p\in\mathcal P_d$:

$$\text{minimize} \sum_{p\in\mathcal P_d} x_p \text{ subject to }$$

$$\begin{align}
(\forall S\in \mathcal S_d) && \sum_{p\in\mathcal P_d} n(S, p)\,x_p &{} = n(S, V) \\
(\forall p\in \mathcal P_d) && x_p &{} \in \{0,1,2,\ldots\} \\
\end{align}$$

For $\max_j b_j = O(1)$ and $d=O(1)$, the ILP has constant dimension (and a constant number of constraints) so can be solved in constant time in the real RAM model (by Megiddo's algorithm or subsequent improvements).  The optimal value is the answer for the given instance $V$. $~~\Box$

The real RAM model does not account for bit complexity of arithmetic operations.  But in each feasible solution to this ILP each coordinate has $O(\log n)$ bits, so presumably the ILP can be solved in polylog$(n)$ time in the standard RAM model,
so this approach should also yield a linear-time algorithm in the standard RAM model.


Terminology for complete k-partite graph where k is not fixed Is there a better term for "complete k-partite graph" in the case where k is not fixed?  If I say "complete k-partite graph", people tend to assume "for some particular k".

In other words, what's a term for any graph for whom each connected component in the complement graph is a clique?

I asked this before, but it was as part of another question, so it was ignored.

I believe the most standard term is complete multipartite graph.


Is it possible to test if a computable number is rational or integer? Is it possible to algorithmically test if a computable number is rational or integer?
In other words, would it be possible for a library that implements computable numbers to provide the functions isInteger or isRational?

I am guessing that it is not possible, and that this is somehow related to the fact that it is not possible to test if two numbers are equal, but I don't see how to prove it.

Edit: A computable number $x$ is given by a function $f_x(\epsilon)$ that can return a rational approximation of $x$ with precision $\epsilon$: $|x - f_x(\epsilon)| \leq \epsilon$, for any $\epsilon > 0$. Given such function, is it possible to test if $x \in \mathrm{Q}$ or $x \in \mathrm{Z}$?

It is easy to get confused about what it means to "represent" or "implement" a real number. In fact, we are witnessing a discussion in the comments where the representation is contentious. So let me address this first.

How do we know that an implementation is correct?

The theory which explains how to represent things in a computer is realizability. The basic idea is that, given a set $X$, we pick a datatype $\tau$ and to every $x \in X$ a set of values of type $\tau$ which realize it. We write $v \vdash x \in X$ when $v$ is a value that realizes $x$. For example (I shall use Haskell for no good reason), a sensible implementation of $\mathbb{N}$ might be the datatype Integer where $v \vdash k \in \mathbb{N}$ when $v$ evaluates to the numeral $\overline{k}$ (thus in particular -42 does not represent a natural number, and neither does a diverging program). But some joker could walk by and suggest that we use Bool to represent natural numbers with $\mathtt{True} \vdash 42 \in \mathbb{N}$ and $\mathtt{False} \vdash n \in \mathbb{N}$ for $n \neq 42$. Why is this incorrect? We need a criterion.

In the case of "joker numbers" the easy observation is that addition cannot be implemented. Suppose I tell you I have two numbers, both represented by $\mathtt{False}$. Can you give a realizer for their sum? Well, that depends on whether the sum is 42, but you cannot tell. Since addition is an "essential part of what natural numbers are", this is unacceptable. In other words, implementation is not about sets, but about structures, i.e., we have to represent sets in such a way that it is possible to also implement the relevant structure. Let me stress this:

  We implement structures, not bare sets. Therefore, we have to be able to implement the entire structure, together with operations and all the axioms, in order for the implementation to be correct.

If you do not abide by this principle, then you have to suggest an alternative mathematical criterion of correctness. I do not know of one.

Example: representation of natural numbers

For natural numbers the relevant structure is described by Peano axioms, and the crucial axiom that has to be implemented is induction (but also $0$, successor, $+$ and $\times$). We can compute, using realizability, what the implementation of induction does. It turns out to be a map (where nat is the yet unknown datatype which represents natural numbers)

  induction : 'a -> (nat -> 'a -> 'a) -> 'nat -> 'a

satisfying induction x f zero = x and induction x f (succ n) = f n (induction x f n). All this comes out of realizability. We have a criterion: an implementation of natural numbers is correct when it allows an implementation of Peano axioms. A similar result would be obtained if we used the characterization of numbers as the initial algebra for the functor $X \mapsto 1 + X$.

Correct implementation of real numbers

Let us turn attention to the real numbers and the question at hand. The first question to ask is "what is the relevant structure of the real numbers?" The answer is: Archimedean Cauchy complete ordered field. This is the established meaning of "real numbers". You do not get to change it, it has been fixed by others for you (in our case the alternative Dedekind reals turn out to be isomorphic to the Cauchy reals, which we are considering here.) You cannot take away any part of it, you are not allowed to say "I do not care about implementing addition", or "I do not care about the order". If you do that, you must not call it "real numbers", but something like "real numbers where we forget the linear order".

I am not going to go into all the details, but let me just explain how the various parts of the structure give various operations on reals:

the Archimedean axiom is about computing rational approximations of reals
the field structure gives the usual arithmetical operations
the linear order gives us a semidecidable procedure for testing $x < y$
the Cauchy completeness gives us a function lim : (nat -> real) -> real which takes a (representation of) rapid Cauchy sequence and returns its limit. (A sequence $(x_n)_n$ is rapid if $|x_n - x_m| \leq 2^{\min(n,m)}$ for all $m, n$.)

What we do not get is a test function for equality. There is nothing in the axioms for reals which asks that $=$ be decidable. (In contrast, the Peano axioms imply that the natural numbers are decidable, and you can prove that by implementing eq : nat -> nat -> Bool using only induction as a fun exercise).

It is a fact that the usual decimal representation of reals that humanity uses is bad because with it we cannot even implement addition. Floating point with infinite mantissa fails as well (exercise: why?). What works, however is signed digit representation, i.e., one in which we allow negative digits as well as positive ones. Or we could use sequences of rationals which satisfy the rapid Cauchy test, as stated above.

The Tsuyoshi representation also implements something, but not $\mathbb{R}$

Let us consider the following representation of reals: a real $x$ is represented by a pair $(q,b)$ where $(q_n)_n$ is a rapid Cauchy sequence converging to $x$ and $b$ is a Boolean indicating whether $x$ is an integer. For this to be a representation of the reals, we would have to implement addition, but as it turns out we cannot compute the Boolean flags. So this is not a representation of the reals. But it still does represent something, namely the subset of the reals $\mathbb{Z} \cup (\mathbb{R} \setminus \mathbb{Z})$. Indeed, according to the realizability interpretation a union is implemented with a flag indicating which part of the union we are in. By the way, $\mathbb{Z} \cup (\mathbb{R} \setminus \mathbb{Z})$ is a not equal to $\mathbb{R}$, unless you believe in excluded middle, which cannot be implemented and is therefore quite irrelevant for this discussion. We are of forced by computers to do things intuitionistically.

We cannot test whether a real is an integer

Finally, let me answer the question that was asked. We now know that an acceptable representation of the reals is one by rapid Cauchy sequences of rationals. (An important theorem states that any two representations of reals which are acceptable are actually computably isomorphic.)

Theorem: Testing whether a real is an integer is not decidable.

Proof. Suppose we could test whether a real is an integer (of course, the real is realized by a rapid Cauchy sequence). The idea, which will allow you to prove a much more general theorem if you want, is to construct a rapid Cauchy sequence $(x_n)_n$ of non-integers which converges to an integer. This is easy, just take $x_n = 2^{-n}$. Next, solve the Halting problem as follows. Given a Turing machine $T$, define a new sequence $(y_n)_n$ by
$$y_n = \begin{cases}
x_n & \text{if $T$ has not stopped within $n$ steps}\\
x_m & \text{if $T$ stopped in step $m$ and $m \leq n$}
\end{cases}$$
That is, the new sequence looks like the sequence $(x_n)_n$ as long as $T$ runs, but then it gets "stuck" at $x_m$ if $T$ halts in step $m$. Very importantly, the new sequence is also a rapid Cauchy sequence (and we can prove this without knowing whether $T$ halts). Therefore, we can compute its limit $z = \lim_n y_n$, because our representation of reals is correct. Test whether $z$ is an integer. If it is, then it must be $0$ and this only happens if $T$ runs forever. Otherwise, $z$ is not an integer, so $T$ must have stopped. QED.

Exercise: adapt the above proof to show that we cannot test for rational numbers. Then adapt it to show we cannot test for anything non-trivial (this is a bit harder).

Sometimes people get confused about all this testing business. They think we have proved that we can never test whether a real is an integer. But surely, 42 is a real and we can tell whether it is an integer. In fact, any particular real we come up with, $\sin 11$, $88 \ln 89$, $e^{\pi \sqrt{163}}$, etc., we can perfectly well tell whether they are integers. Precisely, we can tell because we have extra information: these reals are not given to us as sequences, but rather as symbolic expressions from which we can compute the Tsuyoshi bit. As soon as the only information we have about the real is a sequence of rational approximations converging to it (and I do not mean a symbolic expression describing the sequence, but a black box which outputs the $n$-th term on input $n$) then we will be just as helpless as machines.

The moral of the story

It makes no sense to talk about implementation of a set unless we know what sort of operations we want to perform on it.


Bin packing approximation with different bin sizes Is there any greedy solution with an approximation bound for the bin-packing problem when we have bins of different size?

More formally, there are $n$ bins of size $b_i$ for $i=1,\dotsc,n$, and $m$ objects, each of size $o_j$ for $j=1,\dotsc,m$.

Is there a solution that can pack all of these items into the bins?

I started a project under MIT license to try to solve this problem.  Currently it uses the 'best fit' approach.  Sorts 'items' from largest to smallest and sorts bins from smallest to largest.  Finds first bin that is large enough to use that has ALREADY been used (if possible).  Let's see if we can make it a good enough solution for all.

https://github.com/asharif/packit4.me


What is the best place to get BibTeX entries for computer science articles ? Other than ACM, IEEE computer Society, Google Scholar which is the best site to get bibtex entries for computer science related articles ?

You don't get correct TCS Bibtex entries from anywhere.

CiteSeer, Google Scholar, etc.: the Bibtex entries are garbage, worse than useless.

Examples: Many conference papers in Google Scholar are exported as an @article, with (some version of) the title of the book in the journal field. Google Scholar abbreviates the first names of the authors. And then of course we have ridiculous things like author = {Submission, H.C.F.} – Google Scholar populates the fields by picking some words from the cover page of the paper.

Publishers: the entries are a bit better, but you cannot rely on them – you must check every single field manually anyway. IEEE tends to be worst, ACM and Springer are little bit better, but even with the latter, you need to do manual editing and cross-checking. Springer has a strange idea of what is the title of a proceedings book. ACM gives book titles in a strange mixture of upper-case and lower-case letters. And, as usual, if there are accents in the authors' names, or any math in the title, all bets are off.

Examples of booktitle fields for conference papers: Springer might produce something like booktitle = {Distributed Computing} for a proceedings volume – it requires a lot of imagination to figure out that it actually means "Proc. 23rd International Symposium on Distributed Computing (DISC 2009)". IEEE exports unreadable titles such as booktitle = {Sensor, Mesh and Ad Hoc Communications and Networks, 2007. SECON '07. 4th Annual IEEE Communications Society Conference on}. ACM is usually fairly good, but you need to fix the mixture of upper and lower case letters: booktitle = {Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures}.
Examples of titles with math: ACM might produce (\&\#948;+1) instead of {$(\Delta+1)$}. IEEE might produce Otilde(radic(log n)) instead of {$\tilde{O}(\sqrt{\log n})$}. I am not kidding you.

MathSciNet: high-quality Bibtex entries for journal articles, but the coverage of TCS is poor, and conference papers are not necessarily that well indexed.

"Core TCS" conferences such as FOCS, STOC, and SODA seem to be covered fairly well, but anything else is more patchy. For example, there seem to be few papers indexed from PODC or SPAA.
The entries of the conference papers are not perfect. You can find something like @incollection instead of @inproceedings, or proceeding books such as BOOKTITLE = {Distributed computing}.

DBLP: reasonably good, but once again, a lot of data comes from the publishers, and you need to double-check it anyway (beware of accents).

Examples of accents: Michal Hanckowiak instead of Micha{\l} Ha{\'n}{\'c}kowiak.

As JɛﬀE pointed out in the comments, the correct title of a conference volume is a matter of taste (and a matter of interpretation). For example, LNCS volumes may have useless main titles and ridiculously long subtitles; therefore even if you had pedantically correct bibliographic entries, you most likely would like to edit some of them slightly, for readability and for consistency.

But as soon as you start to tweak the titles of the conference volumes, it becomes obvious that even for your own purposes, there are many possible right answers. When you are running out of space, you might prefer "Proc. STOC 2010" to "Proceedings of the 42th ACM Symposium on Theory of Computing (STOC, Cambridge, MA, USA, June 2010)". This answer at the TeX site gives one example of how to deal with multiple versions of the titles, so that you can easily switch between different variants.


Good codes decodable by linear-sized circuits? I'm looking for error-correcting codes of the following type:

binary codes with constant rate,
decodable from some constant fraction of errors, by a decoder implementable as a Boolean circuit of size $O(N)$, where $N$ is the encoding length.

Some background:

Spielman, in Linear-Time Encodable and Decodable Error-Correcting Codes, gave codes decodable in $O(N)$ time in the logarithmic-cost RAM model, and also decodable by $O(N \log N)$-sized circuits.
Guruswami and Indyk gave an improved construction in Linear Time Encodable/Decodable Codes with Near-Optimal Rate.  They don't analyze the resulting circuit complexity, although I believe it is also $\Theta(N \log N)$.

Thanks in advance!

You should look at Tornado codes {1}, which, for any $R$ and $\epsilon>0$ and large enough $n$ can be designed to recover (with high probability) from a loss of a $(1-R)(1-\epsilon)$ fraction of bits in time proportional to $n \ln \frac{1}{\epsilon}$ (see Theorem 1 in {1}).

{1} Luby, Michael G., et al. "Practical loss-resilient codes." Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. ACM, 1997:  http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/losscodes.pdf


Why have we not been able to develop a unified complexity theory of distributed computing? The field of distributed computing has fallen woefully short in developing a single mathematical theory to describe distributed algorithms. There are several 'models' and frameworks of distributed computation that are simply not compatible with each other. The sheer explosion of varying temporal properties (asynchrony, synchrony, partial synchrony), various communication primitives (message passing vs. shared memory, broadcast vs. unicast), multiple fault models (fail stop, crash recover, send omission, byzantine, and so on) has left us with an intractable number of system models, frameworks, and methodologies, that comparing relative solvability results and lower bounds across these models and frameworks has become arduous, intractable, and at times, impossible.

My question is very simply, why is that so? What is so fundamentally different about distributed computing (from its sequential counterpart) that we haven't been able to collate the research into a unified theory of distributed computing? With sequential computing, Turing Machines, Recursive Functions, and Lambda Calculus all truned out to be equivalent. Was this just a stroke of luck, or did we really do a good job in encapsulating sequential computing in a manner that is yet to be accomplished with distributed computing?

In other words, is distributed computing inherently unyielding to an elegant theory (and if so, how and why?), or are we simply not smart enough to discover such a theory?

The only reference I could find that addresses this issue is: "Appraising two decades of distributed computing theory research" by Fischer and Merritt DOI: 10.1007/s00446-003-0096-6

Any references or expositions would be really helpful.

My take is that the abstractly-motivated Turing machine model of computation was a good approximation of technology until very recently, whereas models of distributed computing, from the get-go, have been motivated by the real world, which is always messier than abstractions.

From, say, 1940-1995, the size of problem instances, the relative "unimportance" of parallelism and concurrency, and the macro-scale of computing devices, all "conspired" to keep Turing machines an excellent approximation of real-world computers.  However, once you start dealing with massive datasets, ubiquitous need for concurrency, biology through the algorithmic lens, etc., it is much less clear if there is an "intuitive" model of computation.  Perhaps problems hard in one model are not hard -- strictly less computationally complex -- in another.  So I believe that mainstream computational complexity is finally catching up (!) with distributed computing, by starting to consider multiple models of computation and data structures, motivated by real-world considerations.


Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$? $CFL$ is the class of context-free languages.

  Question

  Is $CFL$ known to be solvable in $o(log^{2}(n))$ non-deterministic space?  What about $DCFL$?

Yes. This is Theorem 4 in the following paper.

Philip M. Lewis II, Richard Edwin Stearns, Juris Hartmanis:
Memory bounds for recognition of context-free and context-sensitive languages. SWCT (FOCS) 1965: 191-202.

Edit: I am sorry. My answer is not helpful. I missed the "small o". Stupid...
I am not sure what to do. Delete the answer?


List of complexity classes closed under complement Is there a list of 'natural' complexity classes closed under complement? Some that I could think of are P, ZPP, BPP, NP $\cap$ co-NP, PH, PP and PSPACE but surely there are others. Wikipedia and the Complexity-Zoo don't have such a list as far as I can tell but perhaps there are other resources?

Nonderministic Logspace (NL) is closed under complement. That is, $NL=coNL$. This non-trivial result is known as (or rather, is the consequence of) the Immerman–Szelepcsényi theorem.


Implementation of partition trees? Have partition trees ever been implemented?

Here, I'm talking about the partition trees from computational geometry.  The earliest (near-)optimal versions of which were due to Matousek and others, and most recently Timothy Chan:

https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf

It sounds crazy to me that these have never been implemented, but googling turned up no implementations that anyone has ever reported on.

By the definition in the linked paper on page 5, the statement is wrong. Binary space partition (BSP) trees have been used for decades on computer graphics to speed up spatial queries, as have quadtrees and octrees. K-d trees are used extensively in machine learning to speed up nearest-neighbor searches. If you squint just a little, decision trees also fit the general definition.


Compute lowest dimensional polytope from a given set of sign vectors Given a set of hyperplanes determined by the normal vectors $h_1,\dots,h_m \in \mathbf R^d$, its cell types (or sign vectors) are all vectors $t\in\{+,-\}^m$ for which there exists a vector $v\in\mathbf R^d$ so that $\langle v,h_i \rangle \neq 0$ and $t_i = \text{sign}( \langle v,h_i \rangle )$ holds for all $i$. Here, $\langle u,v\rangle$ denotes the inner product and $\text{sign}(x)$ denotes the sign ($+$ or $-$) of the non-zero real number $x$.

Question: What is the fastest known algorithm for the inverse operation? Given a set $t_1,\dots,t_n$ of cell types, we want to compute some set of hyperplanes in as few dimensions as possible, so that its cell types are a superset of $t_1,\dots,t_n$.

This is equivalent to computing the sign rank of a matrix, which is NP-hard as shown in this paper. So you cannot expect too efficient of an algorithm.


Hardness of exact binomial tail bounds Chernoff bounds, in their various forms, bound the tails of a Binomial$(n,p)$ random variable $B$. Define the function $F(n,p,t):=P(B>t)$. Naively, computing $F$ requires exponential (in $n$) time. Suppose that $p$ and $t$ are specified with $O(n)$ bits -- this precision level is sufficient to describe all of the outputs in the range of $F$. I strongly suspect that there is no poly(n) time algorithm for computing $F$ exactly; is there any formal evidence of this?

Edit. As pointed out in the comments, the function above is of course computable in polynomial time. How about the following variant: $X_i$ are independent symmetric Bernoulli variables and $w_i\in[0,1]$ are weights specified with $O(n)$ bits each. Define the function
$$ F(w,t):=P( \sum_{i=1}^n w_i X_i > t) .$$
Hoeffding's inequality provides exponential bounds on $F$; what is the complexity of computing $F$ exactly?

Theorem Exactly computing $F(w,t)$ is #P-hard.

proof.  Reduce from the counting version of Subset Sum, the #Subset Sum problem, defined as follows. Input is a set $W = w_1, \ldots, w_n$ of non-negative integers, and an integer $t$. The task is to count the number of subsets $W' \subseteq W$ that add up to exactly $t$. This problem is known to be #P-hard, even when for all $i$, $w_i \leq t$ and $t = 2^{O(n)}$. In particular, the $w_i$'s are $O(n)$ bit integers.

Suppose now we could compute F in polynomial time. Then we could solve the #Subset Sum problem by outputting:

$$2^n \cdot \left( F(\frac{W}{t}, 1-\frac{1}{t}) - F(\frac{W}{t}, 1) \right) = 2^n \cdot P\left[\sum_{i=1}^n \frac{w_iX_i}{t} = 1 \right],$$
which is precisely the number of subsets of $W$ that add up to $t$.


Has anyone studied "polynomially compact" metric spaces? A subspace $S$ of a metric space $A$ is compact if it is complete and totally bounded. Here, complete means that every Cauchy sequence in $S$ has a limit also in $S$. For $S$ to be totally bounded,  we must have for every radius $r$, that there is a finite set $U$ of open balls of radius $r$ whose union covers $S$.

I would like to know if anyone has studied spaces where the size of $U$ is bounded by a function of $r$ -- for example, where $U(r)$ is $O(\frac{1}{r}^k)$ for some $k$.

The reason I am curious is that I am investigating models of reactive programming (ie, stream functions), where boolean streams are given the Cantor metric (two streams have a distance of $2^{-n}$ when the first position at which they differ at time $n$), and programs between streams are interpreted by functions continuous with respect to this metric. While the continuity requirement functions nicely capture causality requirements very well, it unfortunately also permits stream functions to require their whole history to compute a value (that is, functions $f(x)$ may require their whole history $x_0, \ldots, x_n$ to compute $f(x)$ at time $n$).

One idea I have for understanding this phenomenon is that the Cantor space is compact, and that at radius $2^{-n}$ you need $2^n$ balls to cover the space -- that is, there are $2^n$ length-$n$ binary sequences. So I have a vague idea that if somehow there were a way of equipping the Cantor space with an even coarser metric, I could model computations which are permitted to remember less of their input. (Eg, a polynomial bound would permit you to use space logarithmic in the elapsed time.)

The notion of bounded doubling dimension appears to be related. Specifically, assume your region S is a ball of radius \rho in the metric space. Then the space is said to have bounded doubling dimension $k$ if any such S can be covered by at most $(1/\epsilon)^k$ balls of radius $\epsilon \rho$. The difference between your definition and this one is the limitation of $S$ to be a ball though.

In essence, your parameter $k$ is acting like a kind of dimension of the space. A worthwhile reference is Ken Clarkson's review of different notions of metric space dimension.

Separately, I'm a little confused about your definition, since it appears to require a bound unrelated to the size of $S$. This is odd, because $S$ could grow arbitrarily large.


Implicit Non-deterministic Buchi determinization I am doing implicit Buchi determination for LTL logic in hardware where the combinational logic represents the set of states.

But instead of using acceptance states, I am using final state (as in NFA). Using this approach it seems that I can synthesize all co-safety  and safety properties.

Is my assumption wrong?

In their paper "Model-checking for safety properties" Orna kupferman and vardi prove that finite alternating automata which is obtained by redefining the set of accepting states as empty states can monitor all the informative prefixes for safety, co-sfety properties. So in my algorithm I construct Buchi automata for LTL property(negation) and define the accepatnce set as the empty set(unconditionally accepting state) in it.   So my question can be reframed as "Is the assumption that the definition of acceptance set as empty in alternating automaton is equivalent to defining acceptance set in Buchi automata as empty and hence the Buchi automata recognizes all the prefixes recognized by finite alternating automata"?
Thanks for all the suggestions and reply.***

If I understand your model correctly, then it's enough for you that all runs either get stuck in accepting states, or get stuck in non-accepting states.
If this is the case, you can also use deterministic weak Buchi automata, which are more expressive than $satefy\cup co-safety$.


Hierarchy theorem for circuit size I think that a size hierarchy theorem for circuit complexity can be a major breakthrough in the area.

Is it an interesting approach to class separation?

The motivation for the question is that we have to say

  there is some function that cannot be computed by size $f(n)$ circuits and can be computed by a size $g(n)$ circuit where $f(n)<o(g(n))$. (and possibly something regarding the depth)

so, if $f(m)g(n) \leq n^{O(1)}$, the property seem to be unnatural (it violates the largeness condition). Clearly we can't use diagonalization, because we aren't in a uniform setting.

Is there a result in this direction?

In fact it is possible to show that, for every $f$ sufficiently small (less than $2^n/n$), there are functions computable by circuits of size $f(n)$ but not by circuits of size $f(n)-O(1)$, or even $f(n)-1$, depending on the type of gates that you allow.

Here is a simple argument that shows that there are functions computable in size $f(n)$ but not size$ f(n)-O(n)$.

We know that:

there is a function $g$ that requires circuit complexity at least $2^n/O(n)$, and, in particular, circuit complexity more than $f(n)$.
the function $z$ such that $z(x)=0$ for every input $x$ is computable by a constant-size circuit.
if two functions $g_1$ and $g_2$ differ only in one input, then their circuit complexity differs by at most $O(n)$

Suppose that $g$ is nonzero on $N$ inputs. Call such inputs $x_1,\ldots,x_N$. We can consider, for each $i$, the function $g_i(x)$ which is the indicator function of the set $\{ x_1,\ldots,x_i \}$; thus $g_0=0$ and $g_N=g$.

Clearly there is some $i$ such that $g_{i+1}$ has circuit complexity more than $f(n)$ and $g_i$ has circuit complexity less than $f(n)$. But then $g_{i}$ has circuit complexity less than $f(n)$ but more than $f(n) - O(n)$.


Size of cuts in graphs drawn from $ G_{n,1/2}$ In Luca Trevisan's paper "Psuedorandomness and Combinatorial Constructions", he says that in a graph drawn from $G_{n,1/2}$, for every two disjoint sets A and B there are $(1/2 + o_n(1)) |A||B|$ edges between A and B.

I'm confused as to the exact meaning of this statement. Is it saying that given two disjoint subsets of n vertices selected at random, that's the expected value of the number of edges between them? If so, then doesn't linearity of expectation give |A||B|/2? What is this extra factor of o(1)?

Thanks!

Perhaps what's implicit after "there are" is "asymptotically almost surely", which means that the property holds with probability tending to 1 as n tends to infinity; this is stronger than "in expectation".  You might want to check out a standard textbook on random graphs (e.g. by Alon-Spencer, Bollobas, or Janson-Luczak-Rucinski).


Complexity zoo for unary languages Of course, some complexity results may collapse for unary languages but I wonder
if there is somewhere a survey summarizing the known results in this case: a kind of
complexity zoo for unary languages. Would you know of such a reference ?

There is no Zoo-style reference yet, but a recent automata-theoretic survey of Giovanni Pighizzini has been useful to me, especially the slides from his talk.

Giovanni Pighizzini, Investigations on Automata and Languages over a Unary Alphabet, CIAA 2014.  doi:10.1007/978-3-319-08846-4_3


Network Flow with Non-contiguous Capacities I have a problem that I can model as a minimum cost network flow. The only problem is that I need to be able to set the flow through some arcs to be either 0 or at least 5. That is, the arc cannot carry an integer flow of 1 through 4, but is otherwise okay. Can anyone point me in the direction of any pre-existing work on a problem like this?

Thank you!

I think this is NP-complete, here I try to give a reduction from 1-in-3-SAT, where we want every clause to contain exactly one true literal. Suppose we are given a 3-CNF with $n$ variables and $m$ clauses, from this we construct a DAG.

The first level consists of the source $s$.

From here you have an edge of capacity $m$ to $v_i$ for each variable $x_i$.

The third level has vertices of the form $x_i$ and $\bar x_i$, with an edge of capacity $0$ or at least $m$ from the corresponding $v_i$.

On the fourth level, there is a vertex $c_j$ for every clause with an edge of capacity $0$ or at least $1$ from its literals. We also have an extra vertex, $w$ with edges of capacity $m$ from every literal vertex.

Finally, on the fifth level we have the target, $t$ with an edge of capacity $1$ from each $c_j$ and an edge of capacity $mn-m$ from $w$.

In this graph you have a flow of size $mn$ if and only if there is a 1-in-3-SAT assignment.


Definitional function extensionality for functions out of $\mathbf{2}$ Denote by $a$ and $b$ the canonical terms of $\mathbf{2}$.
For any map $f:\mathbf{2}\to \mathcal{U}$ we have the eliminator$$\mathrm{ind}_{\mathbf{2}}(f) : \big(f(a) \times f(b)\big) \to \prod_{x:\mathbf{2}} f(x).$$
Can we add the rule that for any $f:\mathbf{2}\to \mathcal{U}$ and any $g:\prod_{x:\mathbf{2}} f(x)$ we have a definitional equality $$g=\mathrm{ind}_{\mathbf{2}}(f)(g(a)\times g(b))$$and have decidable equality checking and decidable type checking?
So for example take $f=\lambda x:\mathbf{2}.\mathbf{2}$. Then this rule would imply a definitional equality $$\lambda x:\mathbf{2}.x=\mathrm{ind}_2(f)(b\times a)\circ \mathrm{ind}_2(f)(b\times a).$$

Yes, you can. However:
The complexity issue is bad -- testing whether two $2^n \to 2$ functions are equal is NP-complete, and to make it bearable in practice would require some clever integration with a SAT solver or BDD engine in the implementation of definitional equality.
Moreover, you can potentially defeat such smartness by asking questions about Boolean functions which are free variables. For example, for any $f : 2 \to 2$, it is extensionally the case that $f(f(f(x))) = f(x)$, which you establish by exhaustive enumeration.
You can find some links to papers with algorithms for coproduct in this link:
Programming languages with canonical functions


Complexity of algorithm to test if a graph is asymmetric Counting the order of automorphism group of a graph is polynomial-time equivalent to graph isomorphism problem. But if we just want to know if the order is greater than 1, what is the complexity of this problem? Graphs which have no automorphism except for the trivial one, that is identity permutation, are called asymmetric graphs. So the problem is to check if the graph is asymmetric.

The complement of your problem is known as graph automorphism problem (GA). It is a candidate for $NP$-intermediate problems. The problem is not known to be solvable in polynomial time. Also, It is not known to be $NP$-complete. It polynomialy reduces to the graph isomorphism problem (GI) but no known polynomial reduction from GI to GA. Unique-GI is equivalent to GA.


Lower bound on maximum simple cycle in connected cubic bridgeless graphs I would like to ask if anybody knows any result on the least number of edges the maximum simple cycle of connected cubic bridgeless graphs, must have. Thanks

So you are looking for the circumference of a connected cubic bridgeless graph $G$. Since a bridgeless cubic graph is immediately 2-connected, Bondy and Entringer showed in the paper

  Longest cycles in 2-connected graphs with prescribed maximum degree,  Canadian Journal of Mathematics, 1980,

that $G$ contains a cycle of length at least $4 (\log_2 n - \log_2\log_2 n - 5)$. And a graph which meets the bound is provided in the result Über längste Kreise in regulären Graphen by Lang and Walther, so this is the best possible.

For the reference, see Longest cycles in 3-connected cubic graphs by Bill Jackson. If the graph is 3-connected, then the bound can be improved to $\Omega(n^c)$ with $c\approx 0.69$, and there are efficient algorithm approximately finding a long cycle in $G$.


Explicit set of types and terms in MLTT Whenever I read a presentation of MLTT, especially in the context of the correspondence of MLTT with LCCCs (eg. Seely's paper), they say "the type constructors/formation rules are..." and then list a bunch of rules, and at least one of the rules will refer to terms. For example, in Seely, you have:

  If $F$ is a type-valued function constant, and $a_1, a_2, \dots a_n$
  are terms of the appropriate types, then $F(a_1, \dots , a_n)$ is a
  type.

And then after, you get the term formation rules, which refer to types. This is supposed to represent some sort of mutual induction, but if you naively interpret a paper as being a sort of short-hand for formal definitions and proofs in set theory + FOL, then the definition given is circular.

Later, you get,

  Let $C(M)$ be the category whose objects are all closed types of M, and morphisms $\mathrm{hom}(A,B)$ are closed terms of type $A \to B$.

A category consists of a set of objects (modulo size issues) and a set of morphisms between each object. Lets say for the sake of argument that I am skeptical that the mutual inductive definitions like Seely's actually give a well-defined set. How do you actually construct the sets of types and terms (more) formally in set theory, and convince me that these actually do form a set?

Not just for the sake of argument, I'm skeptical that the sort of dependent type theory that you can implement on a computer and program with is the same sort of dependent type theory that has this relationship with locally cartesian closed categories.

How do you actually construct the sets of types and terms (more) formally
  in set theory, and convince me that these actually do form a set?

It's essentially the same argument that BNF grammars define sets.

Start with the set of untyped terms (conventionally dubbed the preterms), and the set of untyped contexts (sequences $x_1:A_1, \ldots, x_n:A_n$ where the $x_i$ are variables and $A_i$ are preterms).
Think of each judgement form as a predicate. Think of $\Gamma \vdash e : A$ as a three-argument predicate on precontexts, preterms, and preterms, $\Gamma \vdash A \mbox{ type}$ as a two-argument predicate on preterms, $\Gamma \vdash e \equiv e' : A$ as a four-place predicate and so on.
Interpret each rule of MLTT as a predicate transformer.
So a rule like
$$
  \frac{\displaystyle \Gamma \vdash e : \Sigma x:A.B}
       {\displaystyle \Gamma \vdash \pi_1 e : A}
  $$
is defining a new predicate $\vdash'(\_, \_, \_)$ from the old predicate $\vdash(\_, \_, \_)$ such that $\vdash'(\Gamma, \pi_1 e, A)$ holds when  $\vdash(\Gamma, e, \Sigma x:A.B)$ holds.
Observe that every rule is a Horn clause without negation.
As a result, the predicate transformer induced by the interpretation of a rule is monotone on the inclusion order on the lattice of sets of terms (or tuples of contexts and terms; or tuples of contexts, terms and terms; and so on).
Furthermore, the pointwise union of monotone predicate transformers is also monotone. So we can interpret all of the rules as jointly defining a monotone predicate transformer.
By the Knaster-Tarski theorem, there is a least fixed point to the this lattice.
That fixed point gives you the set of well-typed terms, contexts, etc.


Tree decompositions of optimal width where every vertex is in a bounded number of bags? Let $G$ be a graph on $n$ vertices whose maximum degree is at most $\Delta$ and whose treewidth is at most $k$.
Does there exist a function $f(k, \Delta)$, independent of $n$, such that it is possible to find a tree decomposition of $G$ of width $k$ (i.e. with bags of size $k+1$) with the additional property that every vertex of $G$ is in at most $f(k, \Delta)$ of the bags?

A related concept which is perhaps relevant is that of domino treewidth.
We say a tree decomposition is domino if every vertex is in at most $2$ of the bags.
Bodlaender and Engelfriet [ https://link.springer.com/chapter/10.1007/3-540-59071-4_33 ] show that there exists $c(k, \Delta)$ such that every graph with maximum degree at most $\Delta$ and treewidth at most $k$ has a domino tree decomposition of width $c(k, \Delta)$.

Thus, by increasing the size of the bags from $k$ to $c(k, \Delta)$, they can find a new tree decomposition where each vertex is in at most $2$ bags (and clearly the $2$ cannot be lowered).
It seems to me that there is a trade-off between "size of the bags" and "number of bags per vertex" for the class of graphs with bounded degree and treewidth, and my question is if it possible to control the number of "bags per vertex" if we insist on not increasing the bag size.

Answering my own question: the answer is "no". For each $k \ge 3$, Ding and Oporowski construct a graph $G_k$ on $2k$ vertices with treewidth $3$, such that in every optimal tree decomposition of $G_k$ there is a vertex which is in at least $2k-2$ bags (see Figure 1 in their paper).

Ding, Guoli; Oporowski, Bogdan, Some results on tree decomposition of graphs, J. Graph Theory 20, No. 4, 481-499 (1995). ZBL0837.05044.


Generalized Priority Queues I was wondering if there is any literature on the following problem:

Maintain a set $S$ where each element is a function from $\mathbb{R}$ to $\mathbb{R}$ supporting the following operations:

Insert a new function $f$
Given $k$, query the minimum value of $f(k)$ where $f \in S$
Given $k$, remove an element $f$ where $f(k)$ is equal to the minimum value of $g(k)$ where $g \in S$

Are there restricted classes of functions where we can query and update in $o(|S|)$ time? Are there faster solutions when we restrict to operations (1) and (2)?

You will need to make some assumptions about what kinds of functions are allowed to get anywhere with this.

The version of the problem where the elements of $S$ are linear functions from $\mathbb{R}$ to $\mathbb{R}$ has been studied, in a projectively dual form: if you think of each linear function $y=ax+b$ as being coordinatized by the pair of parameters $(a,b)$, and reinterpret that pair as the Cartesian coordinates of a point, then finding the minimizer for a given $x$ becomes the problem of minimizing a linear function over a dynamic set of two-dimensional points. This can be handled in polylog time per update by a dynamic convex hull data structure, such as the one by Overmars and van Leeuwen 1981 or its more recent improvements by Timothy Chan.

Piecewise-linear functions can be handled by using a weight-balanced segment tree on the set of breakpoints of the functions to replace each query on a set of piecewise-linear functions by logarithmically many queries on subsets of linear functions. This duality approach can also be generalized to higher degree polynomials instead of linear functions but at the expense of turning the problem into a range searching problem in more than two dimensions, for which the time per update will be significantly higher.


shortest path & max flow I am trying to improve my algorithmic knowledge during the summer break and i found this problem in a book.

We have an undirected graph $G=(V,E$) with starting node $s\in V$ and last node $t \in V$ where weight of every edge $(u,v) \in E$ is a positive number ($w(u,v)>0$).

Actually it asks to prove that finding the shortest path from $s$ to $t$ is equivalent with finding a max flow $f$ from $s$ to $t$.

$f$ minimizes the amount of $Σ_{(u,v)\in E} f(u,v)w(u,v)$ and has the value of $|f|=1$.

It seems that i am missing something. Can anyone help me with this cause i really hate leaving unsolved exercises when reading a book.

Thanks.

What you're describing, where you minimize the sum of $f(u,v)w(u,v)$ with a given flow value $|f|$ isn't, in fact, the max-flow problem—it's the min-cost flow problem. If you constrain the flow value to be 1, and all capacities are set to 1, it's pretty clear that this problem is equivalent to finding the shortest path.

Basically, unit-capacity flow problems find edge-disjoint paths. If you set the flow value to be 1, you'll find only a single path. If you're working with min-cost flow, that path will necessarily be the shortest path (and, therefore, the cheapest flow).

If this is not what the book is asking, and it's really asking you about max-flow, I suspect there must be some details missing from your description. (For example, you could easily have a single node $t'$ before $t$, with $c(t',t)=1$, so max-flow would have a flow value of 1, yielding a single path; however, that would still ignore the edge costs, and would just find any path, unless you're specifically using the Edmonds-Karp algorithm, which uses BFS to find its augmenting paths; in that case, you would, at least, find the shortest unweighted path.)


How could one define a language based on the Calculus of Constructions, but with fixed points and EAL-style duplication restrictions? Suppose that we take the Calculus of Constructions as a basis, but take away exponential functions (allowing only linear functions), and add the controlled duplication rules of EAL. That'd, I believe, give us a simple core with dependent types that can be reduced on the oracle-free fragment of Lamping's abstract algorithm.

Now, it has been shown [1] that adding type-level fixed points to EAL do not affect its complexity bounds. Doing so would make the language more interesting, as one would be able to define induction and inductive types. Problem is, the Calculus of Constructions makes no distinctions between types and values. As such, adding Fix would imply its existence on the value level (except if we make an exception of the rule, which looks inelegant), which may cause non-termination.

As such, it is not obvious to me how to add Fix to the language of the first paragraph without inhabiting all types. Perhaps a restricted version of it, with fix variables only occurring on non-application positions (i.e., only as arguments) would suffice, but I'm not sure 1. if that's true, 2. if that'd be the right way.

[1] J.-Y. Girard. Light linear logic. Information and Computation,
143:175–204, 1998.

Dependency is interesting because of equality, and equality is adjoint to contraction. As a result, substructural calculi (which in general omit contraction) do not have an obvious notion of equality.

In type-theoretic language, equality is characterized by the following inference rule[*] being valid in both directions (top-to-bottom and bottom-to-top):

$$
\begin{array}{l}
\Gamma, x:\tau, y:\tau \;|\; \Theta, x = y : \tau \vdash P \\
\hline
\Gamma, z:\tau \;|\; [z/x,z/y]\Theta : \tau \vdash [z/x,z/y]P \\
\end{array}
$$

This says that if you have two free variables $x$ and $y$, and an assumption they are equal, that lets you derive the same things are replacing them both by a variable $z$. Note that going from top to bottom is a contraction -- the number of uses of $z$ will be the sum of the uses of $x$ and $y$.

As a result, interpreting the meaning of equality in linear calculi is tricky. The obvious thing to do is to restrict your attention to types which are contractible, but it turns out there are multiple incomparable ways of doing so!

One idea, originating in the work on Linear LF by Cervesato and Pfenning, is to only permit dependency on exponential types.

I, with Nick Benton and Pierre Pradic, gave another calculus based on another version of this idea, which exploited Benton and Wadler's characterization of linear logic in terms of an adjunction between a cartesian closed category and a monoidal closed category. Basically, we just made the CCC part dependent, so that linear types could be dependent on intuitionistic types, but not vice-versa. (However, you could be dependent on closed linear terms, since they are duplicable.)

In his PhD thesis, Matthijs Vákár gave a denotational model of Linear LF. His semantics was based on Benton-Wadler adjoint models, so it should also interpret our calculus.

The other main idea is due to Conor McBride, with subsequent refinements by Bob Atkey. His idea is based on resource interpretations of linear logic, with the idea that if you forget the resource usage information on a linear term, you are left with a nonlinear term approximating it. Then, you can depend on that nonlinear term.

[*] This inference rule is for the case of first-order logic. The dependent case is more complicated, but the underlying issues are the same.


Equivalence problem for one-counter automata I know that the equivalence problem for deterministic one counter automata is decidable, however does anyone know whether it is decidable for all one counter automata or just the deterministic ones?

Any information would be useful, I don't know if this is an open problem or if it has a solution. If there is a known proof (of either decidability or undecidability) then a reference would be greatly appreciated.

I have no time to check the references in detail, but Ibarra states in http://dx.doi.org/10.1007/BF01744294 that, according to
Greibachand Baker and Book, the universe problem (is the language $\Sigma^*$?) for non-deterministic one-counter machines with at most one counter reversal is undecidable.

In addition to this, Ibarra considers even more restricted classes for which this problem is undecidable.

Hence, even a subproblem of equivalence is undecidable for a subclass of non-deterministic one-counter machines.


Connections between Graph Isomorphism and Polynomial Equivalence Are there any relations between Graph Isomorphism problem and Polynomial Equivalence problem?

In particular does a polynomial time solution to Graph Isomorphism problem provide any evidence towards derandomization of Polynomial Identity Testing?

The paper you linked in the comments - and references therein - already seems to answer your first question.

For your second question: I have little reason to think that there is a theorem of the form "If GI is in P, then [something about derandomizing PIT]." For example, it is possible that GI is in P, but Polynomial Equivalence is not. (Note that PolyEq and RingIso are relatively close to one another, and RingIso is as hard as integer factoring...)

Note that equivalence problems in general tend to be nontrivially harder than their specific instances or testing for triviality. For example, Formula Isomorphism is believed to be intermediate between the first two levels of $\mathsf{PH}$, although testing isomorphism to the trivial formula is $\mathsf{coNP}$-complete. (This is the Boolean analogue of your suggestion of trying to use PolyEq to solve PIT. Of course, one could argue that our intuition for the intermediate status of Formula Iso is largely based on Graph Iso...) As another example, testing for Knottedness is in $\mathsf{NP} \cap \mathsf{coNP}$ (assuming GRH; albeit only recently), but the current best upper bound on testing Knot Equivalence is that it can be done in time that is a tower of 2's of height $c^n$, where $n$ is the number of crossings and $c = 10^{10^6}$ (see here). Although it is possible that both Knottedness and Knot Equivalence are in $\mathsf{P}$, the latter seems significantly harder than the former.


Techniques for proving bounds on integrality gap in LP(SDP) A reference to techniques for proving that the size of an integrality gap is bounded by some expression for a particular LP(or SDP, but less important) is needed. Also it would be nice to have a reference to a place where techniques for minimizing integrality gaps are described. I am new in the area of integrality gaps, which looks rather huge, so description of classical results is more preferable than that of something hot.

This is somewhat heavy machinery for what you want, but there's been a large body of work on techniques for designing ever more refined LPs (SDPs) that get closer and closer to the desired integer program. A good reference that reviews these approaches is by Monique Laurent: A comparison of the Sherali-Adams, Lovasz-Schrijver and Laserre Relaxations for 0-1 programming.

Apart from that, I am not aware of a single good source of references: I assume you've at least perused the relevant chapters in Vijay Vazirani's book ?