Why does randomness have stronger effect on reductions than on algorithms? It is conjectured that randomness does not extend the power of polynomial time algorithms, that is, ${\bf P}={\bf BPP}$ is conjectured to hold. On the other hand, randomness seems to have a quite different effect on polynomial time reductions. By the well known result of Valiant and Vazirani, $SAT$ reduces to $USAT$ via randomized polynomial time reduction. It is not likely that the reduction could be derandomized, since it would yield ${\bf NP}={\bf UP}$, which is thought unlikely.

I wonder, what could be the reason for this asymmetric situation: derandomization seems quite possible in probabilistic polynomial time algorithms, but not in  probabilistic polynomial time reductions?

First, let me comment on the specific case of the Valiant-Vazirani reduction; this will, I hope, help clarify the general situation.

The Valiant-Vazirani reduction can be viewed/defined in several ways.  This reduction is "trying" to map a satisfiable Boolean formula $F$ to a uniquely-satisfiable $F'$, and an unsatisfiable $F$ to an unsatisfiable $F'$.  All output formulas are always obtained by further restricting $F$, so unsatisfiability is always preserved.  The reduction can be defined either as outputting a single $F'$, or as outputting a list of $F'_1, \ldots, F'_t$. In the latter case, "success" in the case $F \in SAT$ is defined as having at least one uniquely satisfiable $F'_i$ in the list.  Call these two variants the "singleton reduction" and "list-reduction" respectively (this is not standard terminology).

The first point it's important to note is that the success probability in the singleton reduction is quite small, namely $\Theta(1/n)$ where $n$ is the number of variables.  The difficulties in improving this success probability are explored in the paper

"Is Valiant-Vazirani's Isolation Probability Improvable?"  by Dell et al.

http://eccc.hpi-web.de/report/2011/151/#revision1

In the list-reduction, the success probability can be made large, $1 - 2^{-n}$ say, with a poly$(n)$-sized list. (One can simply repeat the singleton reduction many times, for example.)

Now, it is not at all evident or intuitive that we should be able to directly derandomize a reduction that only has success probability $1/n$.  Indeed, none of the hardness-vs-randomness results give hypotheses under which we can do so in this case.  It is much more plausible that the list-reduction can be derandomized (with a somewhat larger list).  Note though that this would not imply $NP = UP$: our output list of formulas may have many uniquely-satisfiable formulas, and perhaps some with many satisfying assignments, and it seems hopeless to try to define a uniquely-accepting computation over such a list.

Even if we could somehow give a  list-reduction in which a satisfiable $F$ always induced a list $F'_1, \ldots, F'_t$ where most of the $F'_j$'s are uniquely satisfiable, there is no clear way to turn that into a deterministic singleton reduction for isolation.  The real underlying difficulty is that we don't know of any "approximate-majority operation for uniquely-satisfiable formulas", that is, a reduction $R(F'_1, \ldots, F'_t)$ whose output is uniquely satisfiable if most $F'_j$'s are uniquely satisfiable, and unsatisfiable if most $F'_j$'s are unsatisfiable.  This also seems like a general phenomenon: reductions output more complex objects than decision algorithms, and the properties of these objects are harder to check, so it's harder to combine many of these objects into a single object that inherits some property of the majority.

For the Valiant-Vazirani case, it does not even seem likely under plausible derandomization assumptions that we'd be able to obtain $NP = FewP$, that is, to deterministically reduce satisfiable formulas to satisfiable formulas with $\leq$ poly$(n)$ solutions.  Intuitively this stems from the fact that the isolating procedure has no idea of even the rough size of the solution set of the formula $F$ it is given.


Optimizing $\epsilon$ in $\epsilon$-kernel The notion of $\epsilon$-kernel, as defined by Agarwal et al. ("Approximating extent measures of points"), is the following.

Let $S^{d−1}$ denote the unit sphere centered at the origin in $R^d$. For any set $P$ of points in $R^d$ and any direction $u \in S^{d−1}$, we deﬁne the directional width of $P$ in direction $u$, denoted by $\omega(u, P)$, to be

$\omega(u, P)=\max_{p\in P} \langle u, p \rangle  - \min_{p\in P} \langle u, p \rangle$

where $\langle \cdot, \cdot\rangle $ is the standard inner product. Let $\epsilon > 0$ be a parameter. A subset $Q \subseteq P$ is called an $\epsilon$-kernel of $P$ if for each $u \in S^{d−1}$, $(1 − \epsilon)\omega(u, P) \leq \omega(u, Q)$.

It was shown that one can compute an $\epsilon$-kernel of $P$ of size $O(1/\epsilon^{(d−1)/2})$ in time $O(n + 1/\epsilon^{d−(3/2)})$. (Chan, "Faster coreset constructions and data stream algorithms in ﬁxed dimensions".)

I am looking at the problem that is the reverse of this: Let $k$ be a parameter. I want to find an $\epsilon$-kernel of size at most $k$ such that $\epsilon$ is minimized. The running time could be exponential in $d$ but should be polynomial in $k$.

My general question is whether there is anything known for this problem. Some specific questions:
1. Is the problem NP-hard when d=2? (Any clue what problem we can reduce from?)
2. Is there any approximation algorithm for d=2?

Any general comments are also welcomed.

Jeff Philips has a related result showing the stability of kernels: http://www.cs.utah.edu/~jeffp/papers/stable-kernel.pdf.

As for the problem itself, it can be formulated as a hitting set problem. Indeed, you need to pick a point into the kernel for each "complement of a slab" that contains $\geq \epsilon_k$ fraction of the input points. Here $\epsilon_k$ is the minimum $\epsilon$ that has a kernel of size $k$. Since this is just a hitting set problem, it can be approximated up to $O( \log k)$ factor in geometric settings. You need to guess the value of $\epsilon_k$, but naively just do a binary search on epsilon. As such, one can get two results:

A set of size $O( k \log k)$ that is an $\epsilon_k$ kernel.
A set of size k that is  an $\epsilon_{O(k/\log k)}$ kernel.

The algorithm for computing the set cover is the reweighting algorithm. In fact, the original paper by Clarkson solves a related problem about polytope approximation:

@inproceedings{c-apca-93,
  author       = "Kenneth L. Clarkson",
  title        = "Algorithms for Polytope Covering and Approximation",
  booktitle    = "Proc. 3rd Workshop Algorithms Data Struct.",
  series       = LNCS,
  volume       = 709,
  publisher    = "Springer-Verlag",
  year         = 1993,
  pages        = "246--252"
}

As for what to implement, i would use an incremental algorithm that performs quite well in practice, and add points an incremental fashion. See for example, the paper "Robust Shape Fitting via Peeling and Grating Coresets" and references therein.

it seems believable BTW that one should be able to do constant factor approximation instead of logarithmic.

I dont know of a formal proof that this problem is NP-hard, but it would be very surprising if it is not, IMHO.

The problem is probably solvable exactly in the plane using dynamic programming, I think....


Which results in complexity theory make essential use of uniformity? A complexity class separation proof uses uniformity of complexity classes essentially if the proof does not prove the result for nonuniform version, for example proofs based on diagonalization (like time and space hierarchy theorems) make essential use of uniformity as they need to simulate the programs in the smaller class.

  Which results in complexity theory (other than diagonalization proofs) use uniformity essentially?

I have asked many experts essentially this question, and the answer I always get is: none.  Diagonalization proofs obviously use uniformity, and these are at the heart of the time and space hierarchy theorems, as well as Fortnow-Williams type of time-space lower bounds.  As far as I know, all the other lower bounds we know of, both for complexity class separations and for data structures, seem to be non-uniform.  It would be great to hear that I'm wrong though :).


Constructive proof of the Halting Problem Does there exist any constructive (indeed, computable) proof of the Halting Problem? All the ones I have encountered make use of proof by contradiction.

As an aside, some proofs I have encountered make use of Cantor's diagonal argument, but this seems to be purely extraneous (e.g. the proof in Sipser).

I think if we want to answer this problem constructively, then we should be able propose problem constructively.
Let language of arithmetic be $L=\{0,S,+,\cdot \}$ and $\phi(n,x,y)$ be kleene predicate in $L$. Now the first problem is:

  Is there any $m\in \mathbb{N}$ such that $$H_1(m):=\forall x\in\mathbb{N}:\forall y \in \mathbb{N} \neg \phi(x,x,y)\leftrightarrow \exists z\in \mathbb{N} \phi(m,x,z)$$
  ?

Proof. Suppose there exists such $m$, so by above definition we have:
$$\forall y \in \mathbb{N} \neg \phi(m,m,y)\leftrightarrow \exists z\in \mathbb{N} \phi(m,m,z)$$
and this leads to a contradiction, therefore there does not such $m$. (note that $\neg \exists A(x)\rightarrow \forall x \neg A(x)$ has a constructive proof.)

Define $$H_2(m):=\forall x\in \mathbb{N}\exists ! y\in\{0,1\} \phi(m,x,y) \land \forall x\in\mathbb{N}:\exists u \in \mathbb{N}\phi(x,x,u)\leftrightarrow \phi(m,x,1)$$

  Is there any $m$ such that $H_2(m)$ satisfied in natural numbers?

proof. If there exists such m, we can construct number $m'$ from $m$ such that  $H_1(m')$ satisfied in natural numbers and this lead to a contradiction, therefore we have $\forall n\in \mathbb{N}\neg H_2(n)$.

We can see that $H_2(n)$ means that "partial recursive function with code $n$ is a solution for halting problem". Actually we can not deduce constructively that $$\neg H_2(n)\leftrightarrow \neg(\forall x\in \mathbb{N}\exists ! y\in\{0,1\} \phi(n,x,y)) \lor \neg(\forall x\in\mathbb{N}:\exists u \in \mathbb{N}\phi(x,x,u)\leftrightarrow \phi(n,x,1))$$, but $\neg H_2(n)$ means
there exists a time in tmeline that we figure out $\neg\forall x\in \mathbb{N}\exists ! y\in\{0,1\} \phi(n,x,y)$ or $\neg\forall x\in\mathbb{N}:\exists u \in \mathbb{N}\phi(x,x,u)\leftrightarrow \phi(n,x,1)$ although maybe we don't know which of them is true this moment.


Is the half-filled magic square problem NP-complete? Here is the problem:

We have a square with some numbers from 1..N in some cells. It's needed to determine if it can be completed to a magic square.

Examples:

2 _ 6       2 7 6
_ 5 1  >>>  9 5 1
4 3 _       4 3 8

7 _ _
9 _ _  >>>  NO SOLUTION
8 _ _

Is this problem NP-complete? If yes, how can I prove it?

Crosspost on MS

Filling a partially-filled Latin square is NP-Complete. "The complexity of completing partial Latin squares" Charles J. Colbourn. Discrete Applied Mathematics, Volume 8, Issue 1, April 1984, Pages 25-30 http://dx.doi.org/10.1016/0166-218X(84)90075-1

Can a Latin square problem be turned into a magic square problem via modular arithmetic? My intuition says yes, but the rest of my brain says "Get back to grading!"


What makes a language (and its type-system) capable of proving theorems about its own terms? I've recently attempted to implement Aaron's Cedille-Core, a minimalist programming language capable of proving mathematical theorems about its own terms. I've also proven induction for λ-encoded datatypes on it, which made clearer why his extensions would be necessary.

Nether less, I'm still left wondering where those extensions came from. Why they are what they are? What justifies them? I know, for example, that some extensions, such as recursion, ruin the language as a system for proofs. If I decided to also extend CoC with other primitives, how would I justify? I understand a proof of normalization is necessary, but that doesn't prove those primitives "make sense".

In short, what specifically what qualifies a language (and its type-system) as a system capable of proving theorems about its own terms?

[Self-advertising follows, but I think that this is relevant.]

There are several possible approaches to this questions. One of the ways (that I explored during my PhD thesis in the context of an ML-like language) is to extend the type system with a first-order layer, so that terms of the language can be manipulated as objects of the underlying logic. Of course, you also need to include some predicates so that there is something to observe. In the case of my system, these predicates are term equivalences. In particular, if $t$ and $u$ are terms of the language, then the type $t \equiv u$ is only inhabited if $t$ and $u$ are indeed (observationally) equivalent. You can use first-order quantifiers to encode properties such as $\forall v, (\lambda x.x)\;v \equiv v$ in types, and they are proved by constructing programs inhabiting them.

Of course you can also assume equivalences, and there are several different forms of quantifiers (typed / untyped, universal / existential). This mechanism can be used to reason about any program (they do not have to be proved terminating or even typed). The only constraint is that programs that are used as proofs must be proved terminating by the system (arbitrary general recursion leads to inconsistency).

Here are a couple of references if you want to check this out:

https://lepigre.fr/files/docs/lepigre2017_pml2.pdf (recent paper with examples)
https://tel.archives-ouvertes.fr/tel-01590363 (PhD thesis in English)
https://github.com/rlepigre/pml (language implementation)


Is there a definitive reference for Turing machines with multiple oracle tapes? Most of the literature seems to be concerned with machines with single oracles for specific problems, however there appear to be a few papers that consider machines with multiple oracles. Is there a good paper or thesis which provides an overview of what is known about such machines? In particular I am interested in P with multiple oracles.

Here is a more recent paper giving a difference between single vs. multiple oracles motivated by cryptography:

Donald Beaver and Joan Feigenbaum.  Hiding instances in multioracle queries.  STACS 1990.  Springer Lecture Notes in Computer Science, 1990, Volume 415/1990, 37-48, DOI: 10.1007/3-540-52282-4_30


Approximating Min-Sum Set Multicover Approximations for the set multicover problem have been studied (Rajagopalan & Vazirani (section 5)), as have approximations for the min-sum set cover problem (Feige et al.). The greedy heuristic gives a $\log(n)$-approximation for the set multicover problem and a 4-approximation for min-sum set cover.

Consider the min-sum set multicover problem, i.e. for each ground element $e_i$ with coverage requirement $r_i$, let $f(e_i)$ be the step in which the coverage requirement is met; we then wish to minimize $\textstyle\sum_{i=1}^n f(e_i)$.

By extending the 4-approximation in Feige et al., it is trivial to get a $4r$-approximation for min-sum set multicover, where $r=\max r_i$. It is most likely that a better approximation ratio can be achieved.

Does anyone know of any work that has been done on the min-sum set multicover problem? Any pointers to other names for the problem would also be very helpful. Thanks in advance!

Yes, this has been studied. It was called the multiple intents re-ranking problem by Azar, Gamzu, and Yin who gave a $\log n$ approximation using a cleverly modified greedy algorithm (the point is being greedy with respect to a clever metric). Bansal, Gupta, and Krishnaswamy had the good sense to rename the problem to generalized min-sum set cover and gave a constant approximation via LP rounding. The constant is very large, more than 400. Skutella and Williamson improved this to 28.

BTW you state the problem as finding an ordering on the sets to satisfy a coverage requirement on the elements. Some of the above papers state the problem in the equivalent dual form: find an ordering on the elements to satisfy hitting requirements on the sets.


Reference for Levin's optimal factoring algorithm  ? In Manuel Blum's "Advice to a Beginning Graduate Student":

  LEONID LEVIN believes as I do that whatever the answer to the P=NP? problem, it won't be like anything you think it should be. And he has given some wonderful examples.
  For one, he has given a FACTORING ALGORITHM that is proVably optimal, up to a multiplicative constant.
  He proves that if his algorithm is exponential,
  then every algorithm for FACTORING is exponential.
  Equivalently, if any algorithm for factoring is poly-time,
  then his algorithm is poly-time.
  But we haven't been able to tell the running time of his algorithm because, in a strong sense, it's running time is unanalyzable.

Levin's publications page returns a 404, DBLP shows nothing related to factoring, and a search for "leonid levin factoring" on Google Scholar returns nothing of interest that I could find. AFAIK the generalized sieve is the fastest algorithm known for factoring. What is Manuel Blum talking about? Can anyone link me to a paper?

Manuel Blum is talking about applying Levin's universal search algorithm to the Integer Factorization problem. The idea of Levin's Universal search algorithm is equally applicable to any problem in $NP$.

Here is a quote from lectures notes given by Blum on SECURITY and CRYPTOGRAPHY:

  Leonid LEVIN's OPTIMAL NUMBER-SPLITTING (FACTORING) ALGORITHM.
  Let SPLIT denote any algorithm that computes
  INPUT:  a positive composite (i.e. not prime) integer n.
  OUTPUT: a nontrivial factor of n.

  THEOREM: There exists an "optimal" number-splitting algorithm, which we
  call OPTIMAL-SPLIT. This algorithm is OPTIMAL in the sense that:
   for every number-splitting Algorithm SPLIT
   there is a (quite large but fixed) constant C such that
   for every positive composite integer input n,
  the "running time" of OPTIMAL-SPLIT on input n is at most C times the
  running time of SPLIT on input n.

Here is Levin's optimal factoring algorithm:

  The OPTIMAL-SPLIT ALGORITHM:
  BEGIN
   Enumerate all algorithms in order of size, lexicographically within each size.
   Run all algorithms so that at any moment in time, t, the ith algorithm
  gets  [1/(2^i)] fraction of the time to execute.
   Wnenever an algorithm halts with some output integer m in the range 1 < m
  < n, check if m divides n (i.e. if n mod m = 0).
  If so, return m.
  END


Example demonstrating the power of non-deterministic circuits A non-deterministic Boolean circuit has, in addition to the ordinary inputs $x = (x_1,\dots,x_n)$, a set of "non-deterministic" inputs $y=(y_1,\dots,y_m)$. A non-deterministic circuit $C$ accepts input $x$ if there exists $y$ such that the circuit output $1$ on $(x,y)$.
Analogous to $P/poly$ (the class of languages decidable by polynomial size circuits), $NP/poly$ can be defined as the class of languages decidable by polynomial size non-deterministic circuits. It is widely believed that non-deterministic circuits are more powerful than deterministic circuits, in particular $NP \subset P/poly$ imply that the polynomial hierarchy collapses.

  Is there an explicit (and unconditional) example in the literature
  showing that non-deterministic circuits are more powerful than
  deterministic circuits?

  In particular, do you know of a function family $\{f_n\}_{n > 0}$
  computable by non-deterministic circuits of size $cn$, but not
  computable by deterministic circuits of size $(c+\epsilon)n$?

If this problem has no progress, I have an answer.

--

I also have considered this problem since my COCOON'15 paper (before your question).

Now, I have a proof strategy, and it immediately gives the following theorem:
There is a Boolean function $f$ such that the nondeterministic $U_2$-circuit complexity of $f$
is at most $2n + o(n)$ and the deterministic $U_2$-circuit complexity of $f$ is $3n - o(n)$.

I apologize that I haven't written the paper.
The proof sketch below might be enough to explain my proof strategy.
I aim to write the paper with more results by the STACS deadline (Oct. 1).

[Proof Sketch]

Let $f = \lor_{i=0}^{\sqrt{n}-1}{Parity_{\sqrt{n}}(x_{\sqrt{n} \cdot i + 1}, \ldots, x_{\sqrt{n} \cdot i + \sqrt{n}}})$.

The deterministic lower bound proof is based on a standard gate elimination method with a little modification.

The nondeterministic upper bound proof is a construction of such nondeterministic circuit.

Construct a circuit computing $Parity_{\sqrt{n}}$. (The number of gates is $o(n)$.)
Construct a circuit selecting $\sqrt{n}$ inputs nondeterministically. (The number of gates is $2n + o(n)$.)
Combine the two circuits.


Reasoning about non-deterministically terminating loops Here's a "track B" question if there ever was one. Summary: the first thing I think of when I try to give a semantics to non-deterministic programs results in a semantics where I can't prove things about loops that only terminate non-deterministicaly. Surely someone has worked out what to do in this situation, or at least pointed out that it's hard, but I don't know how to go about looking for it (hence the "reference request" tag).

Background

I want to model an while-language with non-determinism. I think this is the obvious (or at least the naive) way to model such a language with a Smyth powerdomain, but correct me if I'm wrong. We will model the meaning of a command in this language is as a function whose domain is the set $S$ of states and whose codomain is the set ${\cal P}(S)_\bot = \{ \bot \} \cup {\cal P}(S)$, where $\bot$ is a least element representing non-termination and ${\cal P}(S)$ is the powerset of states.

We interpret commands as maps from states $\sigma$ to either the non-termination event $\bot$ or to sets of states $\{ \sigma_1, \sigma_2, \ldots \}$ which represent possible outcomes. $P \circledast Q$ is non-deterministic choice.

$⟦\mathbf{skip}⟧\sigma = \{ \sigma \}$
$⟦x := E⟧\sigma = \{ \sigma[(⟦E⟧\sigma)/x] \}$
$⟦\mathbf{abort}⟧\sigma = \bot$
$⟦\mathbf{if}~E~\mathbf{then}~P~\mathbf{else}~Q⟧\sigma = ⟦P⟧\sigma$ if $⟦E⟧\sigma = \mathit{true}$, otherwise $⟦Q⟧\sigma$
$⟦P \circledast Q⟧\sigma = \bot$ if $⟦P⟧\sigma = \bot$ or $⟦Q⟧\sigma = \bot$, otherwise $⟦P⟧\sigma \cup ⟦Q⟧\sigma$
$⟦P; Q⟧\sigma = \bot$ if $⟦P⟧\sigma = \bot$ or $⟦Q⟧\tau = \bot$ for some $\tau \in ⟦P⟧\sigma$, otherwise $\bigcup_{\tau \in ⟦P⟧\sigma} ⟦Q⟧\tau$

There's a directed complete partial order $\sqsubseteq$, where $\bot \sqsubseteq S'$ for any $S' \in {\cal P}(S)_\bot$ and $S_1 \sqsubseteq S_2$ if both $S_1$ and $S_2$ are proper sets and $S_1 \supseteq S_2$, and we can extend this to functions $f$ from $S$ to ${\cal P}(S)_\bot$ pointwise: $f_1 \sqsubseteq f_2$ if $f_1(\sigma) \sqsubseteq f_2(\sigma)$ for every $\sigma$, and $f_\bot$ is the function that maps every state to $\bot$.

The meaning of a loop is $⟦\mathbf{while}~E~\mathbf{do}~P⟧\sigma$ is the least upper bound of the chain $f_\bot \sqsubseteq f(f_\bot) \sqsubseteq f(f(f_\bot)) \sqsubseteq \ldots$, where $f(g)(\sigma) = \{\sigma\}$ if $⟦E⟧(\sigma) = \mathit{false}$, otherwise $\bot$ if $⟦P⟧\sigma = \bot$ or $g(\tau) = \bot$ for some $\tau \in ⟦P⟧\sigma$, otherwise $\bigcup_{\tau \in ⟦P⟧\sigma}g(\tau)$. (This definition assumes that the $f$ I just defined is Scott continuous, but I think it's safe to leave that aside.)

Question

Consider this program:

$x := 0;$
$b := \mathsf{true};$
$\mathbf{while}~b~\mathbf{do}$
$\qquad x := x + 2;$
$\qquad b := \mathsf{false} \circledast b := \mathsf{true}$

Intuitively, this is a loop that can return any positive even number or not terminate, and that corresponds to what we can prove about this loop using the weakest liberal precondition (it is possible to show that $\exists n. x = 2n$ is a loop invariant). However, because the loop has the ability not to terminate (we can refine the non-deterministic choice by the program that always takes the right-hand branch), the meaning of this program given any initial state is $\bot$. (Less informally: the function that maps any state where $b$ is false to itself and any state where $b$ is true to $\bot$ is a fixed point of the $f$ used to define the loop.)

This means that the naive semantics I proposed doesn't correspond in the way I expect to be able to reason about programs. I blame my semantics, but don't how to fix them.

In [dB80] Hitchcock and Park's analysis of the termination properties
of recursion is proven to correspond to a semantic analysis based on
the so-called Egli-Milner interpretation of relations [Egl75, Plo76],
which expresses erratic nondeterminism. This notion captures
that a nondeterministic union of relations is correct if it generates
at least one computation leading to a desired result (even in the
presence of a nonterminating computation). This appears to correspond
to what you are trying to do.

Next characterize the meaning of a statement $S$ as a function $f_S$
mapping each initial state $\sigma$ to some nonempty set of states,
possibly containing $\bot$, such that $f_S$ is strict in the sense
that $f_S(\bot) = \{\bot\}$. The nondeterministic choice between
statements $S_1$ and $S_2$ is described by the function mapping each
initial state $\sigma$ to the union of the individual results $f_{S_1}
(\sigma) \cup f_{S_2} (\sigma)$. Thus, whenever $S_1$ or $S_2$ has the
nondeterministic possibility of producing an undesirable result, then
so does their nondeterministic choice. As the resulting sets of final
states one obtains in this analysis the so-called Egli-Milner
powerset of states:

${\cal P}_{\text{E--M}}(S) = \{ ~s\subseteq S_\bot ~|~ s$ is finite and nonempty, or contains $\bot\}$

Why are infinite subsets of $S$ not considered possible sets of final
states in this model? Under the assumption that all basic building
blocks of relational terms produce only finite, nonempty sets of
possible final states, an infinite set of possible final states can
only be generated when an infinite computation is possible. This can
be seen as follows. Structure the set of all possible computations
starting in a given state $\sigma_0$ as a tree with root $\sigma_0$
and states as nodes. The set of leaves is then exactly the set of
possible final states reachable from $\sigma_0$, except for $\bot$,
which might be missing among the leaves but is represented in the set
of final states by the fact that there is an infinite path in the
tree. By the assumption above, and since only finite nondeterministic
choice is available, this tree is finitely branching. Thus, there is
only a finite number of leaves at any given finite depth. Consequently
an infinite number of possible final states can only be generated in
the presence of an infinite computation (an application of König's
lemma [Kön32]).

$({\cal P}_{\text{E--M}}(S),\sqsubseteq_{\text{E--M}})$ is a poset for
$\sqsubseteq_{\text{E--M}}$ defined by: for $s,t\in{\cal
  P}_{\text{E--M}}(S)$,

$
  s\sqsubseteq_{\text{E--M}} t\quad = \quad
  (\bot\in s \land s\setminus\{\bot\}\subseteq t)
  \lor (\bot\notin s \land s=t)~.
$

Here, $\bot$ can be seen as a placeholder through which
$\sqsubseteq_{\text{E--M}}$-greater sets can be generated by inserting
more states in lieu of $\bot$. Therefore, $\{\bot\}$ is the least
element of $({\cal P}_{\text{E--M}}(S),\sqsubseteq_{\text{E--M}})$.
Furthermore, the poset $({\cal
  P}_{\text{E--M}}(S),\sqsubseteq_{\text{E--M}})$ possesses lub's for
$\omega$-chains. Similarly, the strict functions from $S\cup\{\bot\}$
to ${\cal P}_{\text{E--M}}(S)$ are partially ordered by the pointwise
extension of $\sqsubseteq_{\text{E--M}}$. Moreover, the least such
function is $\lambda\sigma.\{\bot\}$ and lub's of $\omega$-chains of
such functions exist, too.

[dB80] JW de Bakker. Mathematical Theory of Program Correctness.
Prentice Hall, 1980.

[Egl75] H Egli. A mathematical model for nondeterministic
computations. Technical report, ETH Zürich, 1975.

[Kön32] D König. Theorie der endlichen und unendlichen Graphen.
Technical report, Leipzig, 1932.

[Plo76] GD Plotkin. A powerdomain construction. SIAM Journal on
  Computation, 5(3):452-487, 1976.

Disclaimer: this is taken almost verbatim from a book I once co-authored:

WP de Roever and K Engelhardt. Data Refinement: Model-Oriented
  Proof Methods and their Comparison. Cambridge University Press, 1998.


On reducing the hardness of CNF-SAT to k-Clique CNF-SAT refers to the following problem:

  Given a boolean formula $\phi$ in conjunctive normal form, does there
  exist an assignment to the variables that satisfies $\phi$.

There are several parameters that one can associate with $\phi$:

$n$ will denote the number of variables in $\phi$.
$m$ will denote the number of clauses in $\phi$.
$N$ will denote the number of variable occurrences in $\phi$.

  Claim: For every fixed $k$, we can reduce an arbitrary instance $\phi$ of CNF-SAT to an instance $G$ of $k$-Clique with roughly
  $2^{\frac{N}{k}}$ vertices and $2^{\frac{2 N}{k}}$ edges.

  Proof Idea: Any clause in $\phi$ can be split into two clauses by adding an
  additional variable.  The positive literal gets added to one of the
  new clauses and the negative literal gets added to the other new clause.

  We make at most $k$ splits to the clauses of $\phi$ to get a new
  formula $\phi'$ such that:

  $\phi'$ has at most $N+2k$ variable occurrences.
  $\phi'$ can be expressed as $\bigwedge_{i\in[k]} \phi_{i}'$ where each $\phi_{i}'$ is a CNF formula with at most $\frac{N}{k} + 2$
  variable occurrences.
  $\phi$ is satisfiable if and only if $\phi'$ is satisfiable.

  We can look at each $\phi_{i}'$ independently and build up a list of
  all the satisfying assignments.  There are at most $2^{\frac{N}{k}+2}$
  satisfying assignments for each $\phi_{i}'$.

  The satisfying assignments for the $\phi_i'$'s will represent the
  vertices of the graph $G$.  In total, $G$ will have at most $k \cdot 2^{\frac{N}{k}+2}$ vertices.

  Vertices $v$ and $u$ are adjacent in $G$ if the following are true:

  $v$ and $u$ represent assignments for $\phi_i'$ and $\phi_j'$ respectively where $i \neq j$.
  For the variables that are in both $\phi_i'$ and $\phi_j'$, the assignments for $v$ and $u$ agree on their respective bit values.

  Now, if a $k$-Clique exists in $G$, then we get an assignment for each
  $\phi_i'$ where no two assignments disagree on bit values for the same
  variables.  As a result, these assignments can be joined to form a
  satisfying assignment for $\phi'$.

  Conversely, if a satisfying assignment exists for $\phi'$, then we can
  remove variables from this assignment to get a satsfying assignment
  for each of the $\phi_i'$'s where no two assignments have any bit
  mismatches making them form a $k$-Clique in $G$.  $\square$

Using fast matrix multiplication, we can solve $k$-Clique in $O(n^{.792 k})$ time.  Therefore, we can solve CNF-SAT in $2^{.792 N}$ time.  In fact, there is a trivial algorithm for solving CNF-SAT in $2^{.5 N}$ time.

However, it is not known if we can solve CNF-SAT in $poly(N) \cdot 2^{(1-\epsilon) \cdot n}$ time.

Question: Does there exist a constant $c$ such that for every fixed $k$, we can reduce an arbitrary instance $\phi$ of CNF-SAT to an instance $G$ of $k$-Clique with roughly $2^{\frac{c \cdot n}{k}}$ vertices and $2^{\frac{2 \cdot c \cdot n}{k}}$ edges.

Relevant Links:

Exponential Time Hypothesis: https://en.wikipedia.org/wiki/Exponential_time_hypothesis
Algorithms for $k$-Clique: http://theory.stanford.edu/~virgi/combclique-ipl-g.pdf
Sparsification Lemma: https://cseweb.ucsd.edu/~russell/ipz.pdf

I don't know the answer to your specific question (it seems related to the question of whether W1=W[2]).

But the algorithm you give in your question is subsumed by several other results. Using your definition of $N$, CNF-SAT is basically solvable in $O(1.1279^N)$ time, as in the paper by Wahlstrom (link goes to a google scholar page of papers that cite it). In particular, Wahlstrom shows that if $d$ is the average number of occurrences of a variable in the CNF, and no variable appears at most once, then CNF-SAT can be solved in $O(1.1279^{n(d - 2)})$ time. (There are other references with similarly strong running times.)

Update: Another reference is:

Hirsch, E.A.: New worst-case upper bounds for SAT. J. Autom.
Reason. 24(4), 397–420 (2000)

This gives faster algorithms in terms of $m$ and your $N$ (which is typically called $\ell$). Namely, Hirsch gets $2^{0.30897m}$ and $2^{0.10299\ell}$ time.


Hardness of Computing Weisfeiler-Lehman labels The 1-dim Weisfeiler-Lehman algorithm (WL) is commonly known as canonical labeling or color refinement algorithm. It works as follows :

The initial coloring $C_0$ is uniform, $C_0(v) = 1$ for all vertices $v \in V (G) \cup V (H)$.
In the $(i + 1)$ st round, the color $C_{i+1}(v)$ is defined to be a pair consisting of the preceding color $C_{i−1}(v)$ and the multiset of colors $C_{i−1}(u)$ for all $u$ adjacent to $v$. For example, $C_1(v) = C_1(w)$ iff $v$ and $w$ have the same degree.
To keep the color encoding short, after each round the colors are renamed.

Given two undirected graphs $G$ and $H$, if the multiset of colors (aka labels) of the vertices of $G$ is distinct from the multiset of colors of the vertices of $H$, the algorithm reports that the graphs are not isomorphic; otherwise, it declares them to be isomorphic.

It is well-known that the 1-dim WL works correctly for all trees and requires only $O({\log}n)$ rounds.

My question is :

  What is the hardness of computing 1-dim WL labels of a tree ? Is a lower bound better than logspace known ?

The problem of deciding whether two graphs have equivalent labelings and hence also the problem of computing the canonical labeling are PTIME complete. See

M. Grohe,  Equivalence in finite-variable logics is complete for polynomial time.
Combinatorica 19:507-532, 1999. (Conference version in FOCS'96.)

Note that colour refinement equivalence corresponds to equivalence in the logic C^2.

-Martin


Is SAT with two "opposite" solutions NP-hard? Here is a variant of the SAT problem in which a satisfying assignment must have additional properties.
Input: A 3-CNF formula $f$ with variables $x_{1\dots k}$.
Output:
For an assignment $S$ of $x_{1\dots k}$, let $\overline S$ be defined such that $x_i=true$ in $\overline S$ if and only if $x_i=false$ in $S$.
Is there an assignment $S$ such that both $f(S)$ and $f(\overline S)$ hold?

Is this problem still NP-hard?

Examples:

$f=(x_1\lor x_2\lor x_3)\land(x_1\lor x_2\lor \neg x_3)\land(x_1\lor \neg x_2\lor x_3)\land(x_1\lor \neg x_2\lor \neg x_3)$
This requires $x_1=true$ in $S$, but then $x_1=false$ in $\overline S$, so $f(S)$ and $f(\overline S)$ cannot simultaneously hold.
$f=(x_1\lor x_2\lor x_3)\land(x_1\lor x_2\lor \neg x_3)\land(x_1\lor \neg x_2\lor x_3)$
$S=\{x_1:true,~x_2:false,~x_3:false\}$
$\overline S=\{x_1:false,~x_2:true,~x_3:true\}$
Then both $f(S)$ and $f(\overline S)$ hold.

Turning my comment to an answer:
The problem you describe is known as Not All Equal SAT (NAE-SAT), but is phrased differently. A NAE assignment for a CNF-formula $\phi$ over variables is one where in each clause there is at least one false variable and one true variable.

It is easy to see that an assignment is NAE iff its inverse is also NAE.

Showing that NAE-SAT is NP-complete is a well-known exercise, and it can be easily solved by splitting it to two parts.

First, given a 3-CNF formula, we can convert it to a 4-CNF formula by adding a variable $w$ and converting every clause of the form $(x\vee y\vee z)$ to $(x\vee y\vee z\vee w)$.

It is easy to see that the original formula is satisfiable iff the resulting formula is in NAE-SAT.

Then, standard techniques can be used to convert this formula back to 3-CNF, while maintaining the NAE property.


Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in a digraph Note: I posted a similar question regarding undirected graph.

Given

A digraph $G$ with no multiple-edges or loops
A source node $s$
A target node $t$
Maximal path length $l$

I am looking for $G'$ - A subgraph of $G$ that contains any node and any edge in $G$ (and only those), that are part of at least one simple path from $s$ to $t$ with length $\leq l$.

Note that I don't need to enumerate the paths.

As the question is stated, having $l$ as part of the input, the problem is $\mathsf{NP}$-hard. This follows as a special case of the classification of the class of patterns for which the directed subgraph homeomorphism problem is $\mathsf{NP}$-complete by Fortune, Hopcroft, and Wyllie's paper: The directed subgraph homeomorphism problem.

In particular the following problem is $\mathsf{NP}$-complete: Given a directed graph $G$ and vertices $s,t,v$, does there exist a (simple) $(s,t)$-path through $v$?


Complexity of linear programming It is known that Linear Programming (LP) is P-complete.
I am interested in approximation algorithms for LP.

There are numerous inapproximability results for NP optimization problems,
e.g. it is NP-hard to achieve approximation ratio better than 7/8 for MAX-3SAT.

  Are there similar P-hardness results for approximation optimization problems in P?
  In particular, is it known if LP is P-hard to approximate?

See the paper "A parallel approximation algorithm for positive linear programming." by Luby and Nisan. (Some kinds of) linear programs can be approximated in log^(O(1)) n time.


What's "pseudo time" when used in comparison with semaphores I'm currently listening to Alan Kays' talk "Is it really complex or did we just make it complicated ?" (https://www.youtube.com/watch?v=ubaX1Smg6pY&= ) where he says that "semaphores were a bad idea and there was something called pseudo time that was superior" (at 51:40 on the linked video).
Maybe I misunderstood the word "pseudo time", but do you know anything about those ?

I believe he may be referring to this paper: NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM.


The complexity of determining if a fixed graph is a minor of another The result by Robertson and Seymour demonstrates an $O(n^3)$ algorithm for testing whether a fixed graph $G$ is a minor of $H$. I have two and a half questions on this topic:

1) It appears that there have been improvements to this algorithm since. What is the best-known algorithm at present?

2a) What do people conjecture to be the optimal bound?

Mohar's algorithm for embedding on a fixed surface and Kawarabayashi's algorithm for recognizing $k$-apex graphs decide membership of graphs characterizable by forbidden minors in linear time, motivating the last question:

2b) Is there any reason to suspect that we can do this in linear time?

Of course, if someone already came up with a linear-time algorithm, the last two questions are silly. :)

There is a preprint by Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed that claims a quadratic time algorithm: "The disjoint paths problem in quadratic time". It is formatted as a conference submission rather than a journal paper so I'm not sure it's possible to verify the details, though (I haven't really tried, myself).

A very recent survey by Kawarabayashi cites this as the best known result for the closely related disjoint paths problem: Ken-ichi Kawarabayashi (2011), "The Disjoint Paths Problem: Algorithm and Structure", WALCOM: Algorithms and Computation, LNCS 6552, pp. 2–7, doi:10.1007/978-3-642-19094-0_2.

I don't know whether this means that the $O(n\log n)$ claim in Kothari's comment is vapor or whether it means that it's still at an earlier stage of being written up.


Sketches, using ideal hash functions I've been reading about sketches for processing streaming data (the CountMin sketch, the Count sketch, the tug-of-war sketch, FM sketches, etc.).  They use hash functions that are required to be 2-independent or 4-independent or $k$-independent for some small $k$.

However from cryptography we have fast hash functions that are very good candidates to essentially perfect: $k$-independent for every value of $k$ you could ever wish for, and so on.  We can essentially treat them as uniformly chosen from the set of all functions: as far as we know, no polynomial-time computation can tell that this is not the case.  I suspect many practitioners might be happy to use these cryptographic hash functions, if it led to improved performance or better parameters for the sketches.

Does it change anything about the design and analysis of sketches, if we assume we have perfect hash functions like this?  Can we get asymptotically better parameters if we assumed our hash function was perfect?  Or, can we get simpler sketch constructions?

(For instance, I've noticed that the analysis of existing sketches is often somewhat conservative: e.g., it uses the Markov bound or Chebyshev bound.  If we had a perfect hash function we could use a Chernoff-style bound.  Are there any sketches where this makes a significant difference, or is it just a small constant factor in the bound?)

The obvious problem is that if you use a cryptographic pseudorandom number generator (PRNG), the correctness of your algorithm is conditional on a complexity conjecture. However, usually this can be avoided, because the full strength of cryptographic pseudorandmness is usually a huge overkill for streaming. If your streaming algorithm uses a small amount of space, then what you need from your PRNG is that its output cannot be distinguished from a stream of random bits by a small space algorithm. Such a PRNG was constructed by Nisan, and the proof of pseudorandomness is unconditional.

A seminal paper in streaming algorithms that used Nisan's generator is Indyk's work on sketches of $L_1$. Since the sketch uses Cauchy random variables for which the mean and the variance do not exist, the usual moment calculations do not work, so it is hard to imagine how to use $k$-wise independence. That's why the heavy hammer of Nisan's generator comes handy.

A problem with these heavy hammers is that they come at a cost in space. The seed needs to be stored in memory, and for Nisan's generator the seed length is roughly $S\log R$ where $R$ is the number of random bits and $S$ is the space complexity of the algorithm. So you end up multiplying the space complexity by roughly the logarithm of the stream length $n$. If you can use $k$-wise independence you usually add a term like $O(k\log n)$ to the space complexity.


Generalizing the FFT Can the divide and conquer nature of the FFT be generalized to other transforms (z Transform, chirp, etc) automatically?

Is there an algorithm that takes in a description of transform (I don't know what information would be needed) and can produce a fast FFT like function?

While this is not a direct answer, the following discussion on MO (Mathoverflow) relates to finding convolution operations that admit fast FFT-like operations on other algebraic structures.


Checking if a polynomial factors into linear factors Let $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial given
by an arithmetic circuit $C$ of size $s$. Given $C$ as the input,
is there a deterministic algorithm to check whether all the irreducible
factors of $f$ in $\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ are linear
forms? On a related note, given a linear form $l=\sum_{i=1}^{n}l_{i}\cdot x_{i}$,
can we check deterministically whether $l$ is factor of $f$. Of
course, we want running time to be polynomial in both the cases.
By size, we mean the total bit size. Also, it can be assumed that degree of $f$ is polynomial in $n$.

As far as I know, the best algorithm we have currently to check if $f$ (given by an arithmetic circuit) can be factorized into linear factors is via the randomized algorithm of Kaltofen (PDF) which actually produces blackboxes for all the irreducible factors of $f$, and works over any large enough field. In fact, this problem of polynomial factorization for general circuits was recently shown by Kopparty, Saraf and Shpilka to be equivalent to the problem of blackbox-PIT for general circuits.

As mentioned by Bruno, if you are interested in checking a the given circuit is divisible by a given $\ell$, then this reduces to a specific PIT problem. We don't know how to do this deterministically in general but I know of one special case where we know how to do this PIT. There is a deterministic poly-time algorithm (PDF) to check if a given $\ell$ divides a given sparse polynomial $f$.

(Another trivial special case when $f$ is given by a bounded top fan-in depth three circuit. There, $f \bmod \ell$ is also a bounded fan-in depth three circuit and we know how to do PIT in deterministic polynomial time.)


What are the problems in EXPSPACE \ EXPTIME? Based on the diagram below (from Papadimitriou's book) we can see that PSPACE ⊆ EXPTIME ⊆ EXPSPACE. We know that PSPACE ⊊ EXPSPACE, which means that there are problems that can be solved in polynomial bounded space and problems that are only solvable in exponential bounded space. These latter problems are outside PSPACE, so they must be either inside EXPTIME or outside of it. The ones inside are problems that need exponential time to be solved, but not necessarily exponential space. The ones outside are problems that require exponential space to be solved and, since a machine can only do a constant number of movements per transition, they also require exponential time. So my question is: shouldn't this put them all back inside EXPTIME? It doesn't make sense to me that there are problems inside EXSPACE but outside EXPTIME, i.e. problems that require exponential space without requiring exponential time. What are the problems in EXPSPACE outside EXPTIME?

Your argument proves that $\mathsf{NEXPTIME}\subseteq\mathsf{EXPSPACE}$, since if a TM terminates in (nondeterministic) exponential time it cannot write to more than an exponential number of tape cells.

On the contrary, if a TM uses exponential space it can still run in doubly-exponential time, e.g. a TM that increments a binary counter of $2^n$ bits until wrapping uses exponential space but runs in $\mathcal{O}(2^{2^n})$ steps.

So the problems that you’re looking for are those that require at most exponential space but whose running time cannot be bounded by an exponential (even though it can be bounded by a double exponential since $\mathsf{EXPSPACE} \subseteq 2 \mathsf{EXPTIME}$). I don’t have a specific example problem in mind though.


PARITY $\notin$ $AC^0$ with bounded fanout: easy proof? $AC^0$ is the class of constant-depth polynomial-size circuits with NOT gates and  unbounded fan-in AND and OR gates, where inputs and gates also have unbounded fanout.

Now consider a new class, call it $AC^0_{bf}$ which is like $AC^0$ but for which inputs and gates have fanout at most $O(1)$.  This class is clearly in $AC^0$.  In fact, it is strictly contained in $AC^0$, as noted here.  Therefore, PARITY is obviously not in $AC^0_{bf}$.

Is there a proof of PARITY $\notin AC^0_{bf}$ which does not also go through for $AC^0$? In other words, is there a proof which does not use powerful techniques like the switching lemma or the Razborov/Smolensky method?

I might miss something, but isn't $AC^0_{bf}$ the same as a Formula? Since every input bit can have an effect on at most a bounded number of gates, we can simply suppose that every gate has only one output (after possibly duplicating a few things) and we can push down not gates as well. We know that the formula size of parity is n^2 (see Troy J. Lee, "The formula size of PARITY", 2007) and since on every level of our circuit we can only have O(n) gates, this shows that parity is not in $AC^0_{bf}$.


Simplification of weighted NFA What options does one have for the simplification (meaning reduction in the number of states) of weighted NFA over the probability semiring? From my understanding one can determinize, and then minimize an automaton, but

The minimal DFA can actually have more states than the original NFA
Not every weighted NFA is determinizable (in fact, most of them aren't)

My aim, however, is not necessarily to minimize an automaton, but simply reduce its complexity. So, what I'm looking for is a simplification algorithm that works directly with NFA and, while it doesn't guarantee to find the optimal solution, can simplify the automata in some cases significantly, and, presumably, has time complexity polynomial in the number of states. Are there any such algorithms known in literature?

By simplification I understand either minimization or determinization. I'll try to sum up what I know about both problems, in the quite general setting of weighted automata over arbitrary semiring. The original works were done by Marcel-Paul Schützenberger (who introduced them), and you'll find a nice account of what is known about them in the book Elements of Automata Theory by Jacques Sakarovitch (also available in French):
For shorter explanations, check out the lecture notes by Jacques Sakarovitch again:

For both minimization and determinization (called "sequentialization") there are nice theoretical answers. For instance, every weighted automaton over a field can be minimized in polynomial time (see for instance this lecture note).


Existing implementation of Scott's reduction? As per this paper by Grädel, Kolaitis and Moshe Vardi, they discuss computational complexity of satisfiability problem in $\mathrm{FO^2}$, In order to do this they use Scott's reduction. Which is the fact that any sentence in $\mathrm{FO^2}$ can be reduced to Scott's Normal form in polynomial time. The Scott's Normal form is given as
$$\forall x \forall y \alpha(x,y) \land \bigwedge_{i=1}^{m} \forall x \exists y \beta_{i}(x,y) $$
Does anyone know of existing code base where scott's reduction is implemented, i.e I input an arbitrary $\mathrm{FO^2}$ sentence and get it's Scott's Normal Form?

You might check the FO2 solver by Tomer Kotek: https://forsyte.at/alumni/kotek/fo2-solver/
This is the only existing FO2 solver (Tony Tan with his student are working on developing something too).
Answering the question, the authors implemented an improved version of Scott Normal Form, called therein "Skolemized Scott Normal Form". All the details are available here: https://arxiv.org/pdf/1610.02101.pdf


Can three stacks be implemented in one array, with O(1) push/pop time? Two stacks can be efficiently implemented using one fixed sized array: stack #1 starts from the left end and grows to the right, and stack #2 starts from the right end and grows to the left. Is the same possible for three stacks?

More specifically, is it possible to implement three stacks given the following conditions:

You have a fixed size array that can hold N objects.
As long as the sum of the three stack sizes is < N, push() should not fail.
Both push() and pop() operations should take O(1) time.
In addition to the array, you can use only O(1) additional space.

Here are examples of solutions that do not satisfy these requirements:

Splitting the array into 3 fixed parts and using each part for a stack (violates 2).
Similar to the above but with movable boundaries between stacks (violates 3).
Simple linked-list based implementations (violates 4).

I'll accept non-trivial algorithms or impossibility proofs even if they don't meet all the conditions (1)-(4) exactly, for example, an algorithm where push/pop take O(1) amortized time, or where the additional memory is smaller than O(N), eg O(log N). Or an impossibility proof that shows that for example, accessing fewer than 5 elements of the array per push/pop is impossible.

Fredman and Goldsmith showed in "Three Stacks" (Journal of Algorithms, 1994) that $\Theta(n^\varepsilon)$ bits of wasted space is achievable. It is also the minimum needed for arrays of size at least 16 quattuordecillion yottabytes. I described a simple algorithm wasting $\Theta(\sqrt{n})$ words of space in my StackOverflow answer to this question. As @dmitri-urbanowicz mentioned in the comments, this is basically just treating the array as $\sqrt{n}$ blocks of size $\sqrt{n}$, where each block is used for exactly one stack and contains a single pointer to the next block in that stack.


Can multipebble automata decide all deterministic context-sensitive languages? A MPA (multipebble automaton) is a 2DFA (two-way deterministic finite automaton) that can use arbitrary number of pebbles (actually at most $ |w|+2 $ pebbles on a given input $ w $ - the input is written on the tape between two end-markers as $ \# w \# $ ). During the computation, a MPA can detect whether the symbol under the head has a pebble, and then it can put a pebble (remove the pebble) if there is no pebble (a pebble).

$ h_k(\sigma) = \underbrace{\sigma \cdots \sigma}_{k \mbox{ times}} = \sigma^k $ is a homomorphism, where $ \sigma $ is a symbol and $ k>0 $.

For any deterministic context-sensitive language $ \mathtt{L} ~~ \left( \mathtt{L} \in \mathsf{DSPACE(n)} \right), $ it is not hard to show that there exists a $ k>0~ $ such that $  h_k( \mathtt{L} ) $ can be recognized by a MPA. So, loosely speaking, we can say that

  any "problem" decidable by a linear-space DTM (deterministic Turing machine) can be decidable by a MPA.

Is it also true for any language in $ \mathsf{DSPACE(n)} $? Can MPAs decide all deterministic context-sensitive languages?

$ |w| $ is the length of $ w $.

$ w_i $ is the $ i^{th} $ symbol of $ w $, where $ 1 \leq i \leq |w| $.

$ h_k(\mathtt{L}) = \left\lbrace h_k(w_1) h_k(w_2) \cdots h_k(w_{|w|}) \mid w \in \mathtt{L} \right\rbrace $.

No. Counterexample: the halting problem for MPAs is decidable in linear space: if the MPA has N states, we need |k|+2 bits of space to store the pebble locations, log N bits to store the current state and $\log(N(|k|+2))+|k|+2$ bits to store a counter; if the counter cycles, the simulated machine will never halt. This is linear in |k| (ignoring the O(N \log N) space required to describe the machine), as required.

Since this language is decidable in linear space, it is also expressible as a DCSL.


How is the VP=VNP question in char 2 different from other char? What is the current frontier in regards to this question? What are the caveats one should be aware of when pursuing VP=VNP question in char 2 compared to other char? What is the current frontier in regards to this question?

In terms of these complexity classes as a whole, not much is known that distinguishes characteristic 2 from other characteristics. The most frequently arising difference is that the permanent is easy in characteristic 2 (so not VNP-complete unless VP=VNP). (In contrast, the Hamiltonian Cycle polynomial is VNP-complete in all characteristics.)

The relationship of the VP vs VNP question in different characteristics to Boolean complexity classes depends on the characteristic, but in an obvious way (e.g. Boolean complexity classes defined in terms of a similar characteristic, like $\mathsf{Mod_n P}$).

Aside from these (and a few other similar examples like permanent), I'm not sure I know of any proven differences between the different characteristics. I'd be interested to see some!

(Another caveat to be aware of is the distinction between functions over $\mathbb{F}_2$ and formal polynomials over $\mathbb{F}_2$. As functions, $x^2 - x$ and $0$ are the same, but as formal polynomials over $\mathbb{F}_2$ these are distinct. VP and VNP are usually defined in terms of formal polynomials.)


Is a software implementation of a PCP encoder available? We all know the PCP Theorem. Is there any software package availalbe taking a CNF in e.g. DIMACS format as input, and producing a PCP encoding in the same format as output? It might be interesting to run existing SAT solvers on such encoded instances and compare the performance relative to plain instances.

There has been some recent effort to make PCPs practical for use in verifying outsourced computation. Check the work by this UT Austin group for example: http://www.cs.utexas.edu/pepper/.


Question on ascending $k$-tuples of naturals whose sum is less or equal than $S$ Let $k$ and $S$ be fixed non-negative integers. Let us regard the following set of tuples

$\{ (x_1,\dots,x_k)| x_i \leq x_{i+1}, \sum_j x_j \leq S \}$

I have got some questions on this set.

Is there are name for this set? It is similiar to an arbitrary partition of an integer.
Is there a nice formula that provides the number of elements in this set? It may be recursive.
Is there an easy to compute index for each of the elements, such that in turn any element can be computed from the index (easily)?

Of course, there are brute force algorithms for the last two questions. I am looking for something neater.

Let's add one more number $x_{k+1} = S - \sum_i{x_i}$ and assume none of the $x_i$ is zero. Now $(x_1, \ldots, x_{k+1}$) is what is called an $k+1$-part integer partition of $S$. So your tuples are integer partitions of the numbers $0, \ldots, S$ into at most $k$ parts (at most because some $x_i$ could be 0).
Counting partitions is a big topic but a recurrence is not very hard to formulate. Let $q(n,k)$ be the number of partitions of $n$ into at most $k$ parts. The number of your tuples is then $1 + \sum_{n = 1}^{S}{q(n, k)}$. For the recurrence you have two cases:

a) There are $k$ nonzero $x_i$. Then if you subtract one from each $x_i$ you get a partition of $n-k$ with at most $k$ parts. So there is a bijection between partitions of $n$ with exactly $k$ parts and partitions of $n-k$ with at most $k$ parts.

b) There are less than $k$ nonzero $x_i$. The number of such tuples is $q(n, k-1)$.

The recurrence you get is $q(n, k) = q(n-k, k) + q(n, k-1)$. The initial conditions are $q(0, k) = 1$ and $q(n, 0) = 0$ for $n>0$.

As to 3., I think $q(n, k)$ is at least on the order of $n^k$ which would imply that there aren't very succinct representations.


Type classes vs object interfaces I don't think I understand type classes. I'd read somewhere that thinking of type classes as "interfaces" (from OO) that a type implements is wrong and misleading.
The problem is, I'm having a problem seeing them as something different and how that is wrong.

For example, if I have a type class (in Haskell syntax)

class Functor f where
  fmap :: (a -> b) -> f a -> f b

How is that different than the interface [1] (in Java syntax)

interface Functor<A> {
  <B> Functor<B> fmap(Function<B, A> fn)
}

interface Function<Return, Argument> {
  Return apply(Argument arg);
}

One possible difference I can think of is that the type class implementation used at a certain invocation is not specified but rather determined from the environment -- say, examining available modules for an implementation for this type. That seems to be an implementation artifact that could be addressed in an OO language; like the compiler (or runtime) could scan for a wrapper/extender/monkey-patcher that exposes the necessary interface on the type.

What am I missing?

[1] Note the f a argument has been removed from fmap since given it's an OO language, you'd be calling this method on an object. This interface assumes the f a argument has been fixed.

In their basic form, type classes are somewhat similar to object interfaces. However, in many respects, they are much more general.

Dispatch is on types, not values. No value is required to perform it. For example, it is possible to do dispatch on the result type of function, as with Haskell's Read class:

class Read a where
  readsPrec :: Int -> String -> [(a, String)]
  ...

Such dispatch is clearly impossible in conventional OO.
Type classes naturally extend to multiple dispatch, simply by providing multiple parameters:

class Mul a b c where
  (*) :: a -> b -> c

instance Mul Int Int Int where ...
instance Mul Int Vec Vec where ...
instance Mul Vec Vec Int where ...

Instance definitions are independent from both class and type definitions, which makes them more modular. A type T from module A can be retrofitted to a class C from module M2 without modifying the definition of either, simply by providing an instance in module M3. In OO, this requires more esoteric (and less OO-ish) language features like extension methods.
Type classes are based on parametric polymorphism, not subtyping. That enables more accurate typing. Consider e.g.

pick :: Enum a => a -> a -> a
pick x y = if fromEnum x == 0 then y else x

vs.

pick(x : Enum, y : Enum) : Enum = if x.fromEnum() == 0 then y else x

In the former case, applying pick '\0' 'x' has type Char, whereas in the latter case, all you'd know about the result would be that it's an Enum. (This is also the reason why most OO languages these days integrate parametric polymorphism.)
Closely related is the issue of binary methods. They are completely natural with type classes:

class Ord a where
  (<) :: a -> a -> Bool
  ...

min :: Ord a => a -> a -> a
min x y = if x < y then x else y

With subtyping alone, the Ord interface is impossible to express. You need a more complicated, recursive form or parametric polymorphism called "F-bounded quantification" to do it accurately. Compare Java's Comparable and its use:

interface Comparable<T> {
  int compareTo(T y);
};

<T extends Comparable<T>> T min(T x, T y) {
  if (x.compareTo(y) < 0)
    return x;
  else
    return y;
}

On the other hand, subtyping-based interfaces naturally allow the formation of heterogeneous collections, e.g. a list of type List<C> can contain members that have various subtypes of C (although it is not possible to recover their exact type, except by using downcasts). To do the same based on type classes, you need existential types as an additional feature.


Does $VP \neq VNP$ imply $P \neq NP$? As far as I understand, the geometric complexity theory program attempts to separate $VP \neq VNP$ by proving that the permament of a complex-valued matrix is much harder to compute than the determinant.

The question I had after skimming through the GCT Papers: Would this immediately imply $P \neq NP$, or is it merely a major step towards this goal?

The short answer is 'no'. No such implication is known. There are two main obstacles: Going from arithmetic circuit complexity to boolean complexity (VP≠VNP implies P/poly≠NP/poly) and then going from boolean circuit complexity (P/poly≠NP/poly) to uniform complexity (P≠NP). Neither of these steps is known. I believe that P/poly≠NP/poly implies VP≠VNP, however.


What is a good Category Theory-Domain Theory dictionary? When dealing with the domain theoretic categories (say CPO and $\omega$CPO), I frequently wish for a dictionary for the language of category theory in domain theory.

That is, given a concept, say monic arrow, I could look it up in the dictionary and see what are the known characterisations of it in the different domain categories.

I realise this wish is too much to hope for, but is there any text or resource approximating it?

The best resource for this is Abramsky and Jung's handbook chapter. I recall they had a table which cross-referenced various constructions and categories of domains, with the entries saying whether the construction worked in that category and what properties it had. However, properties of arrows like being a monic tended not to have terribly slick characterizations, because the availability of flat domains tends to ensure that they are often not terribly different from their set-theoretic counterpart. OTOH, properties that make some use of the order structure (like being an embedding-projection pair) tend to have fairly pretty characterizations.

A minor point to watch out for is that there are actually two definitions of CPO in common use! Consumers of domain theory (like me) often prefer to work with omega-chains, since chains are pretty concrete objects; whereas producers of domain theory (like, er, your advisor) tend to prefer to work with directed sets, which are more general and have better algebraic properties. (Offhand I'm not sure if restricting to directed sets having countable base is equivalent to the omega-chain condition.)

Something I found very helpful in building this kind of dictionary is to work through the solution of recursive domain equations in some category of things that aren't exactly domains. Two good choices are categories of PERs (eg, in models of polymorphism) and presheaves (eg, for name allocation). Metric spaces are another possibility, but I found them to be too similar to domains to help me build intuition.


Sperner family that maximizes the subsets of a partition Let $A$ be a set of size $k$ and $B$ be a set of size $\ell$, for fixed $k$ and $\ell$, and such that $A\cap B=\emptyset$.
What is the (or a) Sperner family $\mathcal{F}$ on $A\cup B$ for which $\mathcal{F}_B=\{C\cap B ~:~ C\in\mathcal{F}\}$ is maximized?

I actually just need an upper bound to $|\mathcal{F}_B|$ (possibly something better than $2^\ell$, which seems to be loose if $2^k<\ell$)

Any hint or reference where this kind of information or relevant material could be found would be much appreciated. Thanks.

The correct upper bound is the sum of the $2^k$ most central binomial coefficients:
$$|\mathcal{F}_B|\leq\binom \ell {\lfloor (\ell - 2^k)/2+1\rfloor} + \dots + \binom \ell {\lfloor(\ell + 2^k)/2\rfloor},$$
or just $|\mathcal{F}_B|\leq 2^\ell$ if $2^k\geq \ell+1$. The sets $\{B\cap C\mid C\in\mathcal F\text{ and }A\cap C=A'\}$ are antichains. By the LYM inequality the union of $2^k$ antichains cannot be larger than the sum of the largest $2^k$ binomial coefficients. To achieve the bound, let $A=\{a_0,\dots,a_{k-1}\}$, and let
$$\mathcal F=\left\{C\subseteq A\cup B \mid \lfloor(\ell + 2^k)/2\rfloor- \sum_{i\colon a_i\in C} 2^i=|C\cap B| \right\}.$$


Goldberg&Tarjan: How to find a blocking flow in a graph I want to implement the Goldberg & Rao algorithm for finding a maxflow in a graph. My problem is the update step where every paper and report is stating "In the resulting graph, find a blocking flow or a flow of value Delta." They all refer to Goldberg & Tarjan for finding a blocking flow. There are two things I don't understand:

How am I supposed to find a flow of value Delta?
But more important: how can I find a blocking flow?

Regarding questions 2: I read the two papers (the one by Goldberg & Tarjan "A New Approach to the Maximum-Flow Problem" and the one about dynamic trees - both were not that hard to understand). Every paper/report/book about Goldberg & Rao refers to the paper by Goldberg & Tarjan and highlight that Goldberg & Rao do not use the push/relabel algorithm but find blocking flows. But in my opinion, Tarjan only explains the push/relabel algorithm, I cannot find anything about blocking flows.

T. Cormen, "Introduction to algorithms", 3rd edition
The asymptotically fastest algorithm to date for the maximum-flow problem, by Goldberg and Rao, runs in time $O(min(V^{2/3}, E^{1/2}) E \lg{(V^2/E + 2)} * \lg{C})$, where $C = \max c(u,v)$. This algorithm does not use the push-relabel method but instead is based on finding blocking flows.
A. Goldberg & S. Rao, "Beyond the Flow Decomposition Barrier" (the original paper)
Using the blocking flow algorithm of Goldberg and Tarjan [1988], we get an $O (\Lambda m log(n^2/m)\log{U})$ bound.

They gave the wrong reference, for whatever reason, as have you have found out by yourself.

The blocking flow method you are supposed to use is the one given in

http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-333.pdf,
Section 8.3.


Enumeration of discrete objects for which recognition problem is coNP-complete Is there any problem of enumeration of discrete objects for which problem of recognizing of these discrete objects is coNP-complete (or NP-complete), but it is possible to enumerate all these objects in output polynomial time?

For example (but I don't know about the complexity of enumeration) the problem of enumeration (generation) all Hamiltonian graphs with no more than n vertices.

This is not a complete answer, but let me try to explain the case for the Hamiltonian graphs and the non-Hamiltonian graphs with $n$ vertices.

There are $2^{\binom{n}{2}}$ graphs on $n$ vertices, and each of them is either Hamiltonian or non-Hamiltonian.  So one of the following is true.

There are at least $2^{\binom{n}{2}}/2$ Hamiltonian graphs.
There are at least $2^{\binom{n}{2}}/2$ non-Hamiltonian graphs.

I don't know which is true, but suppose 1 is true.  Let $H(n)$ be the number of Hamiltonian graphs with $n$ vertices.  Then $H(n)\geq 2^{\binom{n}{2}}/2$.  In this case, listing all the Hamiltonian graphs with $n$ vertices can be easily done in output polynomial time: Look through all the $2^{\binom{n}{2}}$ graphs, check the Hamiltonicity for each of them (in $2^{O(n)}$ time), and output if it is Hamiltonian.  The running time is $O(2^{\binom{n}{2}}\times 2^{O(n)}) = O(H(n)^2)$, since $2^{O(n)} = O(H(n))$.  If 2 is true, then by the same argument we can list all the non-Hamiltonian graphs with $n$ vertices in output polynomial time.

Namely, if the output size is polynomial in $2^{\binom{n}{2}}$, then such a trivial algorithm runs in output polynomial time (assuming that the verification can be done in $\text{poly}(2^{\binom{n}{2}})$ time).  So the only interesting cases are when the output sizes are subpolynomial in $2^{\binom{n}{2}}$.


What is the best way to get a close-to-fair coin toss from identical biased coins? (Von Neumann gave an algorithm that simulates a fair coin given access to identical biased coins. The algorithm potentially requires an infinite number of coins (although in expectation, finitely many suffice). This question concerns the case when the number of coin tosses allowed is bounded.)

Suppose we have $n$ identical coins with bias $\delta=P[Head]-P[Tail]$. The aim is to simulate a single coin toss while minimizing bias.

The simulation must be efficient in the following sense: An algorithm running in polynomial time looks at $n$ random bits and outputs a single bit. The bias of the algorithm is defined as $Bias(A)=|E[A=0]-E[A=1]|$ where the expectation is taken over the distribution defined by $n$ i.i.d bits ${x_1,\ldots,x_n}$ such that $Prob[x_i=1]-Prob[x_i=0]=\delta$.

  Which algorithm $A$ running in polynomial time has the least bias $Bias(A)$?

This question seems very natural to me and it is very likely that it has been considered before.

What is known about this problem? Is anything known when a weaker class (in $AC_0$, etc.) of algorithms is considered?

Tossing n biased coins and taking the parity of heads gets exponentially close to $\frac{1}{2}$.

[For a proof, consider a random variable that is -1 when heads and 1 when tails, then
the probability that there are an odd number of heads is just the $E\left[\frac{1}{2} + \frac{1}{2}\prod_i X_i\right] = \frac{1}{2} + \frac{1}{2}\delta^n$]

Perhaps this is also optimal for the following reason. Let $f$ be any composition function of these bits. Then, the $\text{Bias}(f) = \sum_S \hat{f}(S) \delta^{|S|}$ and the best $f$ seems to be the parity function (isn't it?).

If you are interested in composition functions of lower complexity, then perhaps a paper of Ryan O'Donnell on `Hardness amplification within NP' would be very relevant. There he uses monotone composition functions for hardness amplifications and the functions that work are characterized by their noise sensitivity.


Proofs, Barriers and P vs NP It is well known that any proof resolving the P vs NP question must overcome relativization, natural proofs and algebrization barriers. The following diagram partitions the "proof space" into different regions. For example, $RN$ corresponds to the set of proofs that relativize and naturalize. $GCT$ (Geometric Complexity Theory) is of course the strictly outside region.

Name some proofs along with the best known regions they belong to. Place them in a best possible way i.e., if a proof is known to relativize, naturalize and algebrize then it should be placed in $RNA$ not just in $RN$. If a proof relativizes but does not naturalize it belongs to $R$ ${\setminus}$ $N$ and so on.

I think you need to redraw your Venn diagram... any containment of complexity classes which relativizes will also algebrize, at least in the sense of Aaronson and Wigderson. That is, access to the "low-degree extension" of an oracle is only more powerful than access to the oracle. Similarly, any oracles showing that a separation requires "non-algebrizing" techniques implies that "non-relativizing" techniques are also required.


Tool for translating PDAs to CFGs We know that all push down automata are representable using context-free grammars. Furthermore, there is an algorithm to construct a CFG from any PDA (e.g. Sipser's proof in intro to theory of computation).

Are there any tools which do this translation? I.e. I can put in a set of transition functions and it will return an equivalent CFG.

jflap is pretty nice and can do this. See here: http://www.cs.duke.edu/csed/jflap/.


The source of the modular decomposition graph When introducing graph modular decomposition, most authors use the 11-vertex graph, which I copy from wikipedia.

The question is who is (are) the original designer of it. (I'm not asking who drew this graph for wikipedia, but the original source of it.)

The wikipedia page was created in December 2006. The earliest source I can find is the Habilitation thesis of Christophe Paul dated on May 17, 2006. (I didn't search intensively.)

Upon the suggestion of Louis Esperet, I contacted Philippe Gambette  and Christophe Paul, who confirmed promptly. Paul designed this graph for his Habilitation thesis. When they created a Wikipedia page for modular decomposition, they used this graph. Maybe it's the beginning of its wide adaption. It's also featured in the well known survey of Michel Habib and Christophe Paul (DOI:10.1016/j.cosrev.2010.01.001).

Some nice properties of this graph include:

it is a permutation graph
its prime node (the bull) is a prime graph containing a vertex that avoids every induced P4. When such a node exists, it is unique.


Conclusions from reverse mathematical strength of graph minor theorem Say we have a graph property which can be checked in nondeterministic polynomial time, and a proof in a weak formal system (say RCA0) that the property is minor closed. Can we say anything about the strength of a formal system, which is able to prove that a given finite set of excluded-minors characterises the given graph property?

Context It is well known that already a simple version (without well-quasi-ordered set of labels) of Kruskal's tree theorem is unprovable in ATR0 and the graph minor theorem is a generalisation of that theorem which isn't even provable in Π11-CA0. Friedman used that simple version of Kruskal's tree theorem to construct the fast growing TREE(n) function, and used the graph minor theorem to construct the even faster growing SSCG(n) function. Those are nice demonstrations of conclusions about computational content from reverse mathematical strength, but those leave the more direct question posed above unanswered.

Namely, related to the graph minor theorem is the proof that minor closed properties can be tested in deterministic cubic time, if one knows the list of excluded minors for that property. Hence it is natural to wonder just how "impossible" it is to prove that one has found all excluded minors for a given "easy" (as made precise in the question) minor closed property. Since this is a "non-uniform" task, it is not clear to me whether the "impossibility" of this task is related at all to the "difficulty" (i.e. reverse mathematical strength) of proving the graph minor theorem itself.

Since the simple version of Kruskal's tree theorem poses exactly the same questions as the graph minor theorem, answers may focus on that simpler problem, if they want. I just used the graph minor theorem, because the question feels more natural that way. (It is possible that this question might have been more suitable to MSE or MSO, at least with respect to getting a definite answer. But the motivation of this question is more related to TCS, so I decided to ask it here.)

I am not sure I understood your question, but if you are asking how difficult it is to compute the set of obstructions, you may be interested in the following http://www.jucs.org/doi?doi=10.3217/jucs-003-11-1194 where the non computabubility is proved even if the graph class is MSOL-definable. In this paper http://www.sciencedirect.com/science/article/pii/S0012365X97830798?via%3Dihub the computability is proved when the graph class is given by the HR grammar.


Decision version of matrix multiplication problem Is there any known decision version of matrix multiplication problem such that the time complexity of the best known algorithm for this decision problem is $O(n^k)$ for $n \times n$-dimensional matrices, where $k$ is bigger than 2 and preferable very close to $ \omega $ or the best known candidate of $\omega$ ($\omega$ is the optimal matrix-product constant)?

P.S. I am aware of matrix product verification problem (e.g. this post).

Let $H$ be some complex hash function (almost any function will do), mapping long bit strings down to a single bit. Then to decide whether $H( A \times B ) = 0$, you will basically need to multiply $A \times B$ and compute $H$ on the resulting product. Unless $H$ has very special properties, there won't be any short cut to this.


Computing a transitive completion / path existence oracle There has been a few questions (1, 2, 3) about transitive completion here that made me think if something like this is possible:

Assume we get an input directed graph $G$ and would like to answer queries of type "$(u,v)\in G^+$?", i.e. asking if there exists an edge between two vertices in the transitive completion of a graph $G$? (equivalently, "is there a path from $u$ to $v$ in $G$?").
Assume after given $G$ you are allowed to run preprocessing in time $f(n,m)$ and then required to answer queries in time $g(n,m)$.

Obviously, if $f=0$ (i.e. no preprocessing is allowed), the best you can do is answer a query in time $g(n)=\Omega(n+m)$. (run DFS from $u$ to $v$ and return true if there exists a path).
Another trivial result is that if $f=\Omega(min\{n\cdot m,n^\omega\})$, you can compute the transitive closure and then answer queries in $O(1)$.
What about something in the middle? If you are allowed, say $f=n^2$ preprocessing time, can you answer queries faster than $O(m+n)$? Maybe improve it to $O(n)$?
Another variation is: assume you have $poly(n,m)$ preprocessing time, but only $o(n^2)$ space, can you use the preprocessing to answer queries more efficient than $O(n+m)$?

Can we say anything in general about the $f,g$ tradeoff that allows answering such queries?

A somewhat similar tradeoff structure is considered in GPS systems, where holding a complete routing table of all pairwise distances between locations is infeasible so it's using the idea of distance oracles which stores a partial table but allow significant query speedup over computing the distance of the whole graph (usually yielding only approximated distance between points).

Compact reachability oracles exist for planar graphs,

Mikkel Thorup: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6): 993-1024 (2004)

but are "hard" for general graphs (even sparse graphs)

Mihai Patrascu: Unifying the Landscape of Cell-Probe Lower Bounds. SIAM J. Comput. 40(3): 827-847 (2011)

Nevertheless, there is an algorithm that can compute a close-to-optimal reachability labeling

Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick: Reachability and Distance Queries via 2-Hop Labels. SIAM J. Comput. 32(5): 1338-1355 (2003)

Maxim A. Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan: Algorithms for Hub Label Optimization. ICALP 2013: 69-80

Building on the work of Cohen et al. and others, there is quite a bit of applied research (database community) see e.g.

Ruoming Jin, Guan Wang: Simple, Fast, and Scalable Reachability Oracle. PVLDB 6(14): 1978-1989 (2013)

Yosuke Yano, Takuya Akiba, Yoichi Iwata, Yuichi Yoshida: Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. CIKM 2013: 1601-1606


Better approximation for special case of 3-hitting set I have a question based on 3-Hitting Set problem. In this problem, we are given a universal set U of size n and a set of subsets S such that $\forall $ s $\in$ S |s|<=3.
FOr this problem, Integer programming formulation is given by
$x_{a}+x_{b}+x_{c} >=1 $ (a,b,c) $\in$ S

$\forall x_{i} \in $(1,0) where $i=1,2 \ldots n $

minimize $\sum x_{i} $

where each variable $x_i$ corresponds to element $i\in$ U.

A Linear programming relaxation would be
0<=$x_{i}$=<1 instead of $x_{i} \in$ {1,0}

After performing linear  programming we know that
In Every s $\in$S x_{a}+x_{b}+x_{c} >=1  at least one of  $x_{i}>=\frac{1}{3}$
so $x_{i}>=\frac{1}{3}$   is made as 1 and the corresponding elements are selected in the solution. There may exist a set s such that  $x_{a}+x_{b}+x_{c} >=1$ so that $x_{a},x_{b},x_{c}>=\frac{1}{3}$ and we will be picking all three elements. This way, we will get a three approximation after rounding $x_{a},x_{b},x_{c}$ to 1.

My question is

I look at a  special case of 3 -hitting set H' in which size of each set s is exactly 3 and optimal solution for linear programming problem is $ \forall x_i  =\frac{1}{3} $. Now, is it possible to improve the approximation factor to less than 3

What you've defined is the vertex cover problem for 3-uniform hypergraphs. Khot and Regev showed that if the unique games conjecture is true, then it is NP-hard to get an approximation of $3-\epsilon$ for this problem.


Consequences of NP=PSPACE What would be the nasty consequences of NP=PSPACE? I am surprised I did not found anything on this, given that these classes are among the most famous ones.

In particular, would it have any consequences on the lower classes?

If $\mathsf{NP} = \mathsf{PSPACE}$, this would imply:

$\mathsf{P^{\#P}} = \mathsf{NP}$That is, counting the solutions to a problem in $\mathsf{NP}$ would be polytime reducible to finding a single solution;
$\mathsf{PP} = \mathsf{NP}$That is, polynomial-time randomized algorithms with success probability arbitrarily close to 1/2 is polynomial-time reducible to polynomial-time randomized algorithms with one-sided error, where YES instances are accepted with arbitrarily small probability;
$\mathsf{MA} = \mathsf{NP}$That is, for any problem which is verifiable in polynomial time, randomization provides a polynomial-time speedup at best (but this is just a corollary of the polynomial-time hierarchy collapsing);
$\mathsf{BQP} \subseteq \mathsf{NP}$That is, any problem which is solvable by a quantum computer has easily verified certificates for its answers; this would be an important positive result in the philosophy of quantum mechanics, and would probably be helpful to the effort to construct quantum computers (for verifying that they are doing what they are meant to be doing).

All of these are due to containments of the classes on the left-hand sides in $\mathsf{PSPACE}$ (though we also have $\mathsf{BQP \subseteq PP}$).


Linear Programming with Modulo Linear Constraints Given $G = (V,E)$ I can formulate a relaxation of graph $K$-coloring as:

find feasible point s.t.

$\min \sum_{ij}v_{ij}$

for all $(i,j)$ in $E$

$z_{ij} \le (c_i - c_j) \bmod k$ (i)

$z_{ij} \le (c_j - c_i) \bmod k$ (ii)

$z_{ij} + v_{ij} \ge 1$ (iii)

Think of the last as something like the soft margin constraint for an SVM.

In other words, all $c_i$ are real numbers and the absolute modulo $k$ difference between all adjacent $c_i,c_j$ must be greater than 1. It seems like a sensible notion of an update to de-violate constraints is to increase a given variable $c_i$ to make minimize the objective, then hop to a neighbor with infeasible edges and do the same, repeat, etc. Each greedy local update is natural.

What sort of issues would this formulation encounter if I tried to put it into practice? Could I get a reasonable approximation procedure from it, or would I be stuck with a heuristic, or is it likely to fall into some sort of weird cyclic behavior.

In general, what can I do and not do with modulo constraints for linear programming?

If one uses the standard notion of a "linear program", i.e., minimization of a linear functional over a polyhedral set, then it is not clear to me if your problem is actually a linear program. The constraint with the modulo function is equivalent to a disjunction of several affine constraints. This would in general make your problem nonconvex, and thus quite hard.

If you are willing to deal with an integer program, you can exploit the structure. You can write the modulo constraints as  e.g.,
$c_i - c_j -\alpha_{ij} k \geq z_{ij}$, where $\alpha_{ij}$ is an integer for all $i,j$ and a new variable added to your problem. The resulting problem is a mixed integer linear program. Results/algorithms for these are based on the structure of the linear constraints. I am not an expert in MILPs, but I thought this may give you some pointers.


Sparse subgraph preserving rooted edge connectivity up to $k$ For a graph $G=(V,E)$ with $n$ vertices and $m$ edges, a subgraph of $O(kn)$ edges   is an $r$-rooted-$k$-sparsifier if it preserves the local edge connectivity from $r$ to every other vertex up to $k$. Namely, it is a subgraph $G_k$, such that $\lambda(r,x,G_k)\geq \min(\lambda(r,x,G),k)$ for all $x\in V$. Here $\lambda(x,y,G)$ is the maximum number of edge disjoint paths from $x$ to $y$.

For undirected graphs, Nagomochi and Ibaraki shows such graph exist and has an algorithm to find a $r$-rooted-$k$-sparsifier in $O(m)$ time. In fact, it finds a subgraph preserves all local edge and vertex connectivity.

Are there similar results for directed graphs? Or are there a proof that a $r$-rooted-$k$-sparsifier cannot exist for some directed graph?

Let $d^+_G(x)$ be the in-degree of $x$ in graph $G$.

Theorem (Lovász 1973):
For a directed graph $G$ and a specified vertex $r$, there exist a subgraph $G'$ with the property that $d^+_{G'}(x) = \lambda(r,x,G') = \lambda(r,x,G)$.

The desired sparse graph exists, as we can keep removing edges to reach a minimal graph with the desired connectivity property.


Lower bounds on #SAT? The problem #SAT is the canonical #P-complete problem. It's a function problem rather than a decision problem. It asks, given a boolean formula $F$ in propositional logic, how many satisfying assignments $F$ has. Which are the best lower bounds on #SAT?

To my knowledge, no one has figured out how to exploit the "counting solutions" property of #SAT in any lower bound on deterministic algorithms, so unfortunately the best known lower bounds for #SAT are basically the same as that for SAT.
However, there has been a little progress. Note that the decision version of #SAT is called "Majority-SAT": given a formula, do at least $1/2$ of the possible assignments satisfy it? "Majority-SAT" is $PP$-complete, and given an algorithm for Majority-SAT, one can solve #SAT with $O(n)$ calls to the algorithm.
The closest that people have gotten to new lower bounds for #SAT (that are not known to hold for SAT) is with lower bounds for "Majority-of-Majority-SAT": given a propositional formula over two sets of variables X and Y, for at least $1/2$ of the possible assignments to $X$, is it true that at least $1/2$ of the assignments to $Y$ make the formula satisfiable? This problem is in the "second level" of the counting hierarchy (the class $PP^{PP}$). Quantum time-space lower bounds (and more) are known for this class.
The survey at http://pages.cs.wisc.edu/~dieter/Papers/sat-lb-survey-fttcs.pdf gives an overview of results in this direction.
UPDATE: As of 2019, the first paragraph in the above is obsolete. It is known that #SAT requires a time-space product that is basically $n^2$. See for example
"Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle" https://drops.dagstuhl.de/opus/volltexte/2018/10149/


Complexity status of restricted k-clique Restricted $k$-clique:

Input: $(G,v,k)$ where $v$ is vertex in $V$

Output: k-clique containing vertex $v$.

What is the space and time complexity status of this Restricted $k$-clique problem?

Is it same as $k$-clique problem?

I trying to show this problem is in $L$ or $NL$

Yes. It is essentially same as the Clique problem. Imagine a clique containing $n$ nodes. Your problem is then asking for a Clique containing $n-1$ nodes, such that all of them are adjacent to vertex $v$. $v$ is connected to all vertices in the graph. The problem is still NPComplete.


Chordal graph and its clique tree A graph $G$ is chordal if it is the intersection graph of subtrees of a tree $T$. In particular $T$ can be chosen such that each node of $T$ corresponds to a maximal clique of $G$ and the subtrees $T_v$ consist of precisely those maximal cliques in $G$ that contain $v$. $T$ is then called the clique tree of $G$.

Now my question is the following.

  Is any tree can be represented as a clique tree of some chordal graph?

Any counter example or hint of proof is welcome.

Chordal graphs can be defined as intersection graph of subtrees of any tree.  So the answer to your decision question is trivially YES.  On the construction side, for each subtree $T_v$ of bags (it's convenient and conventional to call the nodes of the tree as bags), you'll have a unique new vertex $v$, which is put into all bags of the $T_v$.


Is this "subgroup packing" polytope integral? Let $\Gamma$ be a finite abelian group, and let $P$ be the polytope in $\mathbb{R}^\Gamma$ defined to be the points $x$ satisfying the following inequalities:

$$\begin{array}{cl}
\sum_{g\in G} x_g \le |G| & \forall G \le \Gamma \\
x_g \ge 0 & \forall g \in \Gamma
\end{array}$$

where $G \le \Gamma$ means $G$ is a subgroup of $\Gamma$. Is $P$ integral? If so, can we characterize its vertices?

My question originally arose with $\Gamma = \mathbb{F}_2^n$, where some small examples ($n = 2,3$) suggest that the answer is "yes" and "maybe, but it's not simple". I also tried the cyclic group on 9 and 10 elements, as well as $\mathbb{F}_3^2$, where again the polytope is integral. The polytope is not integral when $\Gamma$ is any of $S_3$, $D_4$, and $D_5$, so abelianness is apparently essential.

I should mention that if you write the first set of equations as $Ax \ge b$, then $A$ is not necessarily totally unimodular (which would imply the polytope is integral). When $\Gamma = \mathbb{F}_2^3$, you can choose three linearly independent $g$ and take the three $G$'s spanned by each pair of the selected elements $g$. The resulting submatrix is
$$\begin{bmatrix}0&1&1\\1&0&1\\1&1&0\end{bmatrix}$$
up to permutation, and so has determinant $\pm 2$.

It's easy (if tedious) to characterize the vertices for prime-order groups and observe that they're integral. I'm pretty sure this can be extended to cyclic groups with order a prime-power. I'm not sure what happens when taking products.

This system is very reminiscient of those defining polymatroids, but rather than a submodular set function, the constraints are a "subgroup function" that I suspect is 'submodular' once that's been defined the right way. Still, the techniques for showing certain polymatroids are integral might work here, too, but I don't see how.

Also, Fourier analysis may be relevant: when $\Gamma = \mathbb{F}_2^n$, it seems that the vertices maximizing $\sum_g x_g$ are exactly the point with $x_g = 1$ for all $g$, as well as those with $x_g = 1 - \chi_S(g)$ where $\chi_S$ is the $S$-th Fourier character (following standard notation from analysis of boolean functions), and $S$ is nonempty. (When $S$ is empty, the corresponding point is $x_g = 0$, which is also a vertex.)

Andrew(the asker) and I had discussed this over email, and we have shown the conjecture is false. The polytope is not integral for Abelian groups, not even for cyclic groups.

On the positive side.

Theorem:
For cyclic groups with order $p^kq$, where $p$ and $q$ are primes and $k\in \mathbb{N}$, the incidence matrix of elements and subgroups is totally unimodular.

This is because the family of subgroups is a union of two laminar families.

Hence, this shows the smallest counterexample for cyclic groups must have order at least $2\times 3\times 5 =30$. This actually explains why no small counterexample was found.

Andrew ran some computations, and found a counterexample for cyclic group of order $30$.

Counterexample: $x_0=1/2$, $x_2=\frac{30}{2}-\frac{1}{2}=29/2$, $x_3=\frac{30}{3}-\frac{1}{2}=19/2$, $x_5=\frac{30}{5}-\frac{1}{2}=11/2$, and $0$ everywhere else.
It's not hard to check the point is feasible. Here I rephrase Andrew's proof that this is actually a vertex.
There are $30$ tight constraints. The whole group constraint, the three
subgroups generated by $2,3$ and $5$ respectively, and non-negativity constraints. Because we have $30$ variables, $x$ is a vertex.

One might wonder if the polytope for $\mathbb{F}_2^n$ is integral for all $n$. Unfortunately, Andrew also found a non-integral of the polytope for $\mathbb{F}_2^4$.


Is there a "lambda cube" for interaction nets? The lambda calculus is an untyped language that is often extended with logical frameworks such as the vertices of the λ-cube. Is there something similar to it, but for interaction nets? What about interaction combinators?

Like Martin said, nothing like an equivalent for the $\lambda$-cube has ever been developed for interaction nets or interaction combinators.

The only work that considers types for interaction nets is Lafont's original paper [1].  (My own CONCUR 2005 paper also considers types but adds nothing new to what Lafont did).  It is an extremely simple system: only basic types plus a polarity, no type constructors at all.  Nevertheless, it is enough to obtain a desirable safety property: a well typed net cannot reduce to a net containing a "clash" (an active pair which does not have a corresponding reduction rule and is therefore "stuck").

Of course, since multiplicative linear logic proof nets are a particular system of interaction nets, it is defintely possible to equip certain systems of interaction nets with more complex types, using non-trivial type constructors.  But nothing has ever been studied, mostly because the interest of such an endevour is unclear.

[1] Yves Lafont, Interaction Nets.  In Proceedings of POPL, 1990.


Complexity of computing the order of a permutation group Given two permutations $g$ and $h$ over $n$ elements (i.e., members of $S_n$), what is the complexity of computing the order of the subgroup generated by $g,h$? Or just of deciding whether the subgroup is of order $n!$ (i.e., all of $S_n$)?

The order of permutation groups can be computed in polynomial-time. In fact, I believe even in $\mathsf{NC}$ and also nearly linear Las Vegas time. See, e.g., the book by Seress.

For reference, subgroups of $S_n$ (and algorithms related thereto) are typically called "permutation groups" rather than merely "subgroups (of $S_n$)". So you can google "permutation group algorithms" etc.


Generating graphs of girth $g$ such that the minimum cycles form a double edge cover Let $g\geq 3$. I need to generate simple graphs $G$ of girth $g$ such that the set of all $g$-cycles forms a double edge cover of $G$ (that is, every edge is shared by exactly two $g$-cycles), and such that the intersection of any two $g$-cycles is either a vertex, an edge, or empty. The generated graphs should be arbitrarily large.

The method of generation should have some randomness to it, but not in a trivial sense. I want to be able to obtain fairly complicated graphs. For example, imagine an $n\times m$ rectangular grid in the plane. If we identify the opposite sides of the bounding rectangle, we obtain a graph that satisfies all of the above requirements for $g=4$. I would qualify this graph as simple.

Is there any such method?

Any references to similar problems are also appreciated.

My half-baked idea was a little too ambitious.  I'm including it below for reference, but the distance condition I specified is not actually sufficient to guarantee large girth.

There are arbitrarily large highly symmetric surface maps with large girth, but published existence proofs are largely based on group theory rather than topology or geometry per se.

Specifically, for any integers $g$, $d$, and $r$ such that $1/g + 1/d < 1/2$, there is a regular surface map in which every face has $g$ edges, every vertex has degree $d$, and every non-contractible cycle on the surface crosses at least $r$ edges.  Here "regular" means both that every vertex has the same degree and that for any pair of directed edges, there is an automorphism of the embedding that sends directed edge to the other.  Setting $r$ large enough in this construction guarantees that the girth of the graph is $g$.  See, for example:

Roman Nedela and Martin Škoviera.  Regular maps on surfaces with large planar width.  European J. Combinatorics 22(2):243--262, 2001.
Jozef Širáň.  Triangle group representations and constructions of regular maps. Proc. London Math. Soc. 82(3):513-532, 2001.

Once you have one such surface map, larger maps with the same girth and degree can be generated by constructing covering spaces.

Here is one (half-baked) way to generate such graphs. Let $G$ be a plane graph with the following properties:

Every bounded face of $G$ has exactly $g$ edges.
The outer face of $G$ has an even number of edges; call these the boundary edges of $G$.   (This condition holds automatically when $g$ is even; if $g$ is odd, $G$ must have an even number of bounded faces.)
It is possible to pair the boundary edges of $G$, so that the distance in $G$ from any boundary edge to its partner is at least $g$.  This condition is not actually enough; the exact condition needed here is unclear.

Arbitrarily large plane graphs with these properties can be constructed by taking a sufficiently large finite portion of a regular tiling of the hyperbolic plane by $g$-gons.

Finally, to obtain a surface graph $G'$ where every face has length $g$, identify pairs of boundary edges in $G$ according to the pairing described above.  The bounded faces of $G$ become the faces of a cellular embedding of $G'$ on some closed surface without boundary.  The distance condition on the pairing guarantees that the girth of $G'$ is $g$.

By choosing both $G$ and the pairing more carefully, once can construct arbitrarily large $d$-regular graphs satisfying your girth condition, for any integers $d$ and $g$ such that $1/d + 1/g < 1/2$.  Even within these constraints, the construction has lots of degrees of freedom.