Why isn't it "enough" to prove induction with one extra "INat" argument? It is well known that it is impossible to prove the induction principle for Natural numbers on the Calculus of Constructions. That is,

Nat =
  ∀ P : *
  ∀ S : P -> P
  ∀ Z : P
  P

Zero =
  λ P : *
  λ S : P -> P
  λ Z : P
  Z

Succ =
  λ n : Nat
  λ P : *
  λ S : P -> P
  λ Z : P
  S (n P S Z)

NatInd :
  ∀ P : Nat -> *
  ∀ S : ∀ (n : Nat) -> P n -> P (Succ n)
  ∀ Z : P Zero
  ∀ n : Nat
  P n

There is no term of type NatInd on CoC, for either this or any other representation of Nat. But I've noticed that the following slightly different type can be constructed:

INat =
  λ n : Nat
  ∀ P : Nat -> *
  ∀ S : ∀ (n : Nat) -> P n -> P (S n)
  ∀ Z : P Zero
  P n

NatInd2 :
  ∀ P : Nat -> *
  ∀ S : ∀ (n : Nat) -> P n -> P (Succ n)
  ∀ Z : P Zero
  ∀ n : Nat
  ∀ i : INat n
  P n

Here, we first define a new type, INat : Nat -> *. That type is isomorphic to Nats and can be easily constructed for any natural number. Then, NatInd2 is a term that, given a proposition indexed on Nats, a base case Z, a step case S, for any nat n and its corresponding INat n, proves P(n) holds for every n. Or, in simpler words, NatInd2 is essentially induction, except that you must provide an additional argument i of type INat n, which you can always construct anyway. You could as well use dependent pairs to conveniently store Nat, INat pairs together.

It seems like this accomplishes the same one would expect from induction, i.e., you prove all cases from a base and a step case. Of course, there is an extra argument, but that argument is trivial to construct. For a "human reader", any proof using the method above would be equally convincing that some property holds for all n. So, my question is: is there any reason for the above method to be insufficient in general? Why is it so important to have the former unaltered definition of NatInd?

Let us spell out the informal meaning of INat, IntNat and IndNat2. Suppose we have a predicate P on natural numbers. Say that P is inductive if we can inhabit P Zero and ∀ k . P k -> P (Succ k). Then we have:

NatInd P states "if P is inductive then, for all j : Nat, we have P j"
INat n P states "if P is inductive then P n"
NatInd2 P states: "if P is inductive and for every n we have an i which allows us to inhabit inductive predicates at n, then we can inhabit P n".

As you can see, NatInd2 just sweeps the problem under the rug, because it essentially asks that we give it a way of implementing induction. It is true that we can inhabit INat Zero, INat (Succ Zero), INat (Succ (Succ Zero)), ... but that does not imply that we can inhabit ∀ k . INat k! If you think otherwise, provide a term that does so.

In essence, you just hid the problem a little deeper by introducing a level of indirection. You could have already asked this: I can inhabit an infinite sequence of types NatInd P S Z Zero, NatInd P S Z (Succ Zero), NatInt P S Z (Succ (Succ Zero)), ... – why is this not sufficient to have induction? The answer: because you are suposed to inhabit ∀ n : Nat, NatInd P S Z n, which is not the same thing! The former is truth at the meta-level and the latter is an internal induction principle inside the calculus.

The question revolves around the difference between having an infinite sequence of terms inhabiting

t0 : Q 0
t1 : Q 1
t2 : Q 2
t3 : Q 3
...

versus having a single term

t : ∀ n : Nat, Q n

Given t, we can of course produce t0, t1, t2, etc. But there is generally no way to produce a t if we know that we have the infinite sequence of terms t0, t1, t2, ..., even in the case when there is an algorithm generating the sequence, for such an algorithm may not be expressible in the language (CiC in our case). Is that clear?

In fact, we can show that, given any (sufficiently expressive) strongly normalizing calculus (and a total language in general), there will be an instance of Q : Nat -> * such that we can inhabit each of Q 0, Q 1, Q 2, ... separately, but not ∀ n : Nat, Q n. This just says that no strongly normalizing calculus can express all total computable functions.

Supplemental: The OP is aksing why one needs, ought, or should internalize universal quantifiers. From a programmer's point of view the answer is simply that this is what is needed. Let us consider the practical difference between having an infinite sequence of terms

t0 : P 0
t1 : P 1
t2 : P 2
...

versus a single term

u : ∀ n : Nat, P n

Suppose you want to write a program which reads from the standard input a natural number k and outputs a witness of the statement P k. If we have u then we can do it easily (I am inventing syntax as I go here):

print "Please enter a natural number" ;
let k = input() in
print (u k)

How could we write such a program if instead of u we had a sequence of terms t0, t1, t2, as above? One could attempt something like

print "Please enter a natural number" ;
let k = input() in
if k = 0 then print t0
else if k = 1 then print t1
else if k = 2 then print t2
...

but this will not do because programs cannot be infinite. One could also try to do it as follows, assuming there is an algorithm A which produces the sequence t0, t1, t2 (but this algorithm is not expressible in our programming language):

The programmer asks the user to tell him a natural number.
The user provides a natural number k.
The programer runs A to get the expression tk of type P k.
The programer writes down the program print (u tk) and runs it.

We can see quite plainly that the programmer is now doing the job of the program, i.e., everything has moved to the meta-level, which is not what we want. We want the machines to do the job for us. You could also use a programming language which can express the algorithm A, but then you've switched to a different programming language and your algorithm A will correspond to the original program u.

The program u is needed because we must be able to compose and combine it with other pieces of code where it is not known in advance how u will be used.

We can also take the logical point of view. What is the difference between having at our disposal an infinite sequence of proofs

t0 : P 0
t1 : P 1
t2 : P 2
...

versus a single proof

u : ∀ n : Nat, P n

When we inspect u and verify that it is valid, we have provided evidence that P holds for all numbers. In contrast, the sequence of proofs t0, t1, t2, ... is not a finite amount of information, and so it cannot be verified and validated in finite time. Such infinite amount of information does not provide evidence that P holds for all numbers, at least not according to the standard that evidence in mathematics means proof. A proof by definition is finite and verifiable.

You may try to save the day by saying something like "but if we verify the algorithm that produces the sequence t0, t1, t2, ... then we will know that P holds for all n". This is true, but again, you're switching to the meta-level in which the verification that the algorithm works corresponds to having the proof u.


Polynomial time approximation algorithms for machine scheduling: how many open problems are left? In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, reviews which would concern very the same list of problems haven't appeared. Thus it would be great and useful if each of us could make such summary on some of the ten open problems and contribute it here.

Makespan minimization on identical machines under precedence constraints

  Open problem 1. Provide a $4/3+\delta$ inapproximability result for $P|prec|C_{max}$.

Here what comes first to mind is the paper of this year by Ola Svensson "Conditional Hardness of Precedence Constrained Scheduling on Identical Machines". In his paper Ola proves that

  "if the single machine problem is hard to approximate within a factor of $2-\epsilon$ then the considered parallel machine problem, even in the case of unit processing times, is hard to approximate within a factor of $2-\zeta$, where $\zeta$ tends to 0 as $\epsilon$ tends to 0."

In 2008 there was published the paper "Precedence constrained scheduling in $(2−\frac{7}{3p+1})$ · optimal" describing an algorithm for $P|prec,p_j=1|C_{max}$ with the performance ratio, mentioned in its title. This improves upon Coffman-Graham algorithm with bound $2-\frac{2}{p}$, where $p$ is the number of machines.

The paper "Approximation algorithms for scheduling jobs with chain precedence constraints" by Jansen and Solis-Oba contains PTAS for $Qm|chains|C_{max}$, and, as a consequence, for $Pm|chains|C_{max}$ as a special case of the former problem.

This year there was appeared the article "Approximation schemes for scheduling jobs with chain precedence constraints" by Jansen and Solis-Oba (journal version of the previous one), which concerns PTAS for $P|chains|C_{max}$ with a fixed number of jobs in every chain and $P|prec|C_{max}$ with a constant number of jobs in every order's connected component.

Makespan minimization on uniform machines under precedence constraints

The 2003 year's paper "Approximation algorithms for scheduling jobs with chain precedence constraints" by Jansen and Solis-Oba contains PTAS for $Qm|chains|C_{max}$.

Makespan minimization under precedence constraints with communication delays

Makespan minimization on unrelated machines

Makespan minimization in open shops

Makespan minimization in flow shops

In the paper of Nagarajan and Sviridenko from 2008 "Tight Bounds for Permutation Flow Shop Scheduling" we can find the upper bound on the ratio between optimal makespan and the makespan of the best permutation schedule. This bound is the approximation ratio of an algorithm proposed, and it is the best possible among algorithms based on the trivial lower bounds, up to $2\sqrt{2}$ factor. Incidentally, the algorithms proposed are currently the ones with the best approximation ratios.

Makespan minimization in job shops

  Open problem 7. Decide whether there exists a polynomial time approximation algorithm
  for $J||C_{max}$ whose worst-case performance is independent of the number $m$ of machines and/or independent of the maximum number $\mu$ of operations. Provide a $5/4+\delta$ inapproximability result for $J||C_{max}$. Provide an inapproximability result for $J||C_{max}$ whose value grows with the number $m$ of machines to infity.

  Design a PTAS for $J2||C_{max}$ for the case where $\mu$ is part of the input; or disprove the existence of such a PTAS under P$\ne$NP.

Dissertation by Svensson "Approximability of Some Classical Graph and Scheduling Problems" contains results showing that $J||C_{max}$ cannot be approximated within $O((\log lb)^{1-\epsilon})$ assuming $NP\subseteq ZTIME(2^{\log n^{O(1/\epsilon)}})$ and that $J2||C_{max}$ has no PTAS unless $NP\subseteq DTIME(n^{O(\log n)})$.

Total job completion time without precedence constraints

Total job completion time under precedence constraints

  Open problem 9. Prove that $1|prec|\sum C_j$ and $1|prec|\sum w_jC_j$ do not have polynomial time approximation algorithms with performance guarantee $2−\epsilon$ unless P=NP.

In "Optimal long code test with one free bit" Bansal and Khot proved that it is so, but assuming a new variant of the unique games conjecture.

Flow time criteria

  Open problem 10. Design polynomial time approximation algorithms with constant performance guarantees for $1|pmtn;r_j|\sum w_jF_j$ and for $P|pmtn;r_j|\sum F_j$.

In "Weighted ﬂow time does not admit $O(1)$-competitive algorithms" Bansal and Chan proved that $1|pmtn;r_j|\sum w_jF_j$ "does not admit $O(1)$-competitive algorithms". Interestingly, the authors don't cite the paper of Schuurman and Woeginger.

In "Minimizing Average Flow-time: Upper and Lower Bounds" Garg and Kumar proved a lower bound $\Omega(\sqrt{\frac{\log P}{\log\log P}})$ on the approximation ratio for $P|pmtn;r_j|\sum F_j$. Later this bound was improved to $\Omega(\frac{\log P}{\log\log P})$ in "Minimizing Total Flow-Time: The Unrelated Case" by Garg, Kumar and Muralidhara.


What Books Should Everyone Read? [Timeline]

This question has the same spirit of what papers should everyone read and what videos should everybody watch. It asks for remarkable books in different areas of theoretical computer science.

The books can be math-oriented, yet you may find it great for a computer scientist.
Examples:

Probability
Inequalities
Logic
Graph Theory
Combinatorics
Design & Analysis of Algorithm
Theory of Computation / Computational Complexity Theory

Please devote each answer to books of the same subject (e.g. books on combinatorics).

Note: The title might be misleading. Here's a clarification: Let X and Y be two fields in computer science. There are books that everyone

in field X should read.
in field Y should read.
in both fields should read.

This question seeks all 3 cases. In other words, it is NOT specific to the latter case.

Edit: As suggested by Dai Le, please highlight the reason(s) you like the book as well.

Related topics:

References for TCS proof techniques
Books on automata theory for self-study
Books for probability
Favorite popular math book
Beginner's guide to derandomization
References on circuit lower bounds
Survey article on the theory of recursive functions
Books on Programming Language Semantics
What are the recent TCS books whose drafts are available online
Books on probability

Computational Complexity:

If you are looking for recent complexity textbooks. The following two are must have.

Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak (Textbook homepage)
Computational Complexity: A Conceptual Perspective by Oded Goldreich (Textbook homepage)

The majority of the content between these two books is comparable. However, some key differences exist: Goldreich devotes more space to exploring the conceptual and philosophical basis of complexity theory, whereas Arora/Barak covers a wider selection of topics, including concrete models of complexity, quantum computation, and circuit lower bounds that are mostly absent from the former.

Another option, an older but timeless textbook in complexity is:

Computational Complexity by Christos Papadimitriou

Papadimitriou's book is notable for chapters covering first-order logic as well as the classes SNP, MaxSNP$_0$, and APX (the theoretical foundations of hardness of approximation), which are missing from the more modern texts.

Another (comparatively) old, but quite notable classic is:

Introduction to the Theory of Computation by Michael Sipser

This is one of the few/first textbooks that explicitly includes "Proof Idea:" between "Theorem:" and "Proof:", and is one of the best-written mathematical textbooks on any topic. On the other hand, it is only an intro to complexity, devoting only one 50-page chapter to "advanced topics" (including approximation, probabilistic algorithms, IP=PSPACE, and crypto). As a first book on complexity, or as an example of truly excellent writing, this book is great.

The Nature of Computation by Cristopher Moore and Stephan Mertens

Scott Aaronson writes that this book has "the fun of a popular book with the intellectual heft of a textbook." It tells stories and gives lots of entertaining examples and references (Game of Life, and lots of other examples for Turing-complete machines).
It doesn't go too deep into complexity theory but has great breadth. Especially of note are its connections to statistical physics.


complexity of finding a cycle with total weight k in a graph when you know no hamiltonian cycle in graph satisfies the given weight k Assume a weighted graph G and a positive value k are given, and you are looking for the complexity of finding a cycle with total weight k; beside you know that no Hamiltonian cycle in G has total weight k. (G is an arbitrary weighted graph, beside you know no hamiltonian cycle would satisfy the total weight k)

1-can someone use reduction from knapsack to conclude that the complexity of finding a cycle with total weight k In G is NP-com? (I guess no!)
2-Is there any idea about the complexity of finding a cycle in G with total weight k when you know no Hamiltonian cycle in G convinces total weight k?

I don't know about knapsack problem, but it isn't too hard to reduce from Hamiltonian Cycle to this problem (assuming you mean a simple cycle). We start with an arbitrary graph $G$ with $n$ nodes for which we want to find a Hamiltonian cycle. Then we construct $G'$, which is $G$ with the addition of a single node $v$, a single edge from $v$ to an arbitrary node in $G$ with arbitrary weight, and every other edge has weight 1. We then ask if there is a cycle with weight $n$ in $G'$.

If we have a Hamiltonian cycle in $G$, this corresponds to a cycle in $G'$ with weight $n$. This is not a Hamiltonian cycle in $G'$, since it doesn't go through our added vertex $v$. If we have a (simple) cycle with weight $n$ in $G'$, then it must include exactly n nodes. It can't include $v$ since it has degree 1, and can't be part of a cycle. Therefore, this goes through all the nodes in $G$, and thus is a Hamiltonian Cycle in $G$.

Therefore this problem is $\mathcal{NP}$-Complete, unless I misinterpreted your question.


Definition of Rabin acceptance condition for omega automatons I've been trying hard to understand something. According to wikipedia and this paper, the definition of the Rabin acceptance condition involves a set of pairs of states. I've been told that the left set in a pair must not be empty, but I cannot figure out why. Since the condition requires that at least one of the pairs will have none of the states on the left being visited infinitely often, and at least one of the state on the right be visited infinitely often, an empty left set seems to mean just that for every pair in the condition it is true that none of it's states is being visited infinitely often.
So my question is: why can't the left side of the pair be empty?

As Emil explained in a comment:
The sides are interchangable when defining the Rabin condition - my professor defined the left side as the one that is required to be visited infinitely often while Wikipedia and the paper I've mentioned define the right side as the one that is required to be visited infinitely often.
Whichever the side that has to be visited infinitely often is, it can be required to be non-empty, since if it is empty, the pair is meaningless - it cannot be visited infinitely often.
It is okay not to require it to be non-empty, because if it is empty, the pair simply accepts the empty language without causing any contradiction or changing any of the desired results of the definition.


Did "Where the really hard problems are" hold up? What are current ideas on the subject? I found this paper to be very interesting. To summarize: it discusses why in practice you rarely find a worst-case instance of a NP-complete problem. The idea in the article is that instances usually are either very under- or very overconstrained, both of which are relatively easy to solve. It then proposes for a few problems a measure of 'constrainedness'. Those problems appear to have a 'phase transition' from 0 likelihood of a solution to 100% likelihood. It then hypothesizes:

That all NP-complete (or even all NP-problems) problems have a measure of 'constrainedness'.
That for each NP-complete problem, you can create a graph of the probability of a solution existing as a function of the 'constrainedness'. Moreover, that graph will contain a phase-transition where that probability quickly and dramatically increases.
The worst case examples of the NP-complete problems lie in that phase-transition.
The fact whether a problem lies on that phase-transition remains invariant under transformation of one NP-complete problem to another.

This paper was published in 1991. My question is was there any follow-up research on these ideas the last 25 years? And if so, what is the current mainstream thinking on them? Were they found correct, incorrect, irrelevant?

Here is a rough summary of the status based on a presentation given by Vardi at a Workshop on Finite and Algorithmic Model Theory (2012):

It was observed that hard instances lie at the phase transition from under- to over-constrained region. The fundamental conjecture is that there is strong connection between phase-transitions and computational complexity of NP problems.

Achlioptas–Coja-Oghlan, found that there is a density in the satisfiabe region
where the solution space shatters into exponentially many small clusters. Vinay Deolalikar based his famous attempt to proof $P \ne NP$ on the assumption that shattering implies computational hardness. Deolalikar’s Proof was refuted by the fact that XOR-SAT is in $P$ and it shatters. Therefore, shattering can not be used to prove computational hardness.

The current mainstream thinking seems to be (as stated by Vardi) that phase-transitions are not intrinsically connected to computational complexity.

Finally, Here is an article published in Nature which investigates the connection between phase-transitions and computational hardness of K-SAT.


Finding the identity with permutation chains I have the following problem: I'm given a list of size $K$ of random integer permutations of $[1..n]$, named $P_1$ to $P_K$, and an additional random permutation $Q$.

How hard is to find a sequence $s(j)$ of $U$ subscripts in $[1..K]$, such that $P_{s1}(P_{s2}(...(P_{sU}(Q(i))))) = i$  for every $1\leq i \leq n$, where Q is an initial random permutation.

In other words, the composition of a subset of the given permutations must be the inverse of $Q$.

I suppose this problem, as $n$ grows, is exponential.

Note: the result must be the list of $s(j)$ values, and that list should be polynomial to $n$ in size. I cannot accept something like "apply P1 2^456 times" as an answer.

It is related to any $\sf{NP}$-Complete problem?

Any idea? Thanks!

Just a note: if the $K$ permutations can be arbitrary, and if you want to find the shortest possible solution, a quick reduction from the Pancake flipping problem shows that finding the shortest possible sequence is NP-hard.

The reduction: Given an instance of the Pancake flipping (i.e. a permutation of $[1..n]$), add to the list the $K = n$ possible prefix permutations.
The application of a $P_i$ corresponds to a pancake flip, and $U$ of them can generate the identity permutation if and only if the pancake of the original problem can be sorted using $U$ flips.

However, this doesn't apply directly to the problem as you stated it.  If we don't need the shortest possible solution, it's easy to find a solution of length $O(n)$ to the pancake flipping problem.  Since this question asked for any solution (rather than the shortest possible solution), there's no proof that this problem is NP-hard.


Clique cover problem Consider the following graph problem. We are given a graph $\mathcal{G} = (\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges. For each vertex $V \in \mathcal{V}$, there is a weight $W(V)$.

For a clique $Q=(Q_V,Q_E)$ where $Q_v \subset \mathcal{V}$ and $Q_E \subset \mathcal{E}$, the weight of clique $Q$ is defined as $W(Q) = \max_{V \in Q_V}W(V)$.

Now, we want to find a set of cliques covering all vertices $\mathcal{V}$ such that the sum of weights of these cliques are minimum.

In this problem NP-hard?
I think since the graphs are general, when the weights are equal, then the problem become minimum clique cover problem in which we want to cover the graph $\mathcal{G}$ with minimum number of cliques. Since this problem is NP-hard, the problem with arbitrary weights is also NP-hard. Am I right?

How can we find an approximation algorithm for this problem?
I think the most trivial algorithm that comes to mind is this but I don't know how good it is.

Sort the vertices based on their weights in decreasing order (the first one has the highest weight) and if two have the same weight we sort them based on the number of edges of them. Assume the sorted list of vertices is $V_1, \ldots, V_{10}$. Now, we start from the clique $C = V_1$ and check the list $V_2, \ldots, V_{10}$ from left to right. For each element, we check whether adding $V_j$ to $S$ results in a clique or not. If yes, we form a clique of $S$ and $V_j$, and remove $V_j$ from the list. We continue this process (now for $S = \{V_1,V_j\}$) until we reach the end of list $V_2, \ldots, V_{10}$. Now we remove the vertices of set S, from $V_1, \ldots, V_{10}$, and repeat the above procedure for the first element of $V_1, \ldots, V_{10}$ minus the set $V$.

I don't know if there is a suitable approximation algorithm for this problem, but I can provide a counter-example for your heuristic algorithm:
Assume G has 2*n vertices with weights
$$W(v_i) = w - \epsilon * i$$
Which in your algorithm will be sorted by this order:
$$v_1, v_2, ... v_{2n}$$
And there's an edge between $v_i$ and $v_j$ iff $\exists k : i-j = 2*k$
The resulting graph is the union of 2 cliques with size n
The algorithm alternates between these two, which means in every step a clique with exactly one vertex will be returned, yielding a final answer with weight:
$$2*n*w - \epsilon * n * (2*n+1)$$
But we know that the optimum weight is just $2*w - 3*\epsilon$
So the approximation factor can be as big as $n/2$ (assuming that the graph has $n$ vertices) which is not very interesting because the obvious algorithm "Pick each vertex as a clique" has an approximation factor of $n$


Can testing show the absence of bugs? $(n + 1)$ points are required to uniquely determine a polynomial of degree $n$; for instance, two points in a plane determine exactly one line.

How many points are required to uniquely determine a computable function $f : N \rightarrow N$, given the length of a program that computes $f$ in a fixed language? (i.e. a bound on the Kolmogorov complexity of $f$).

The idea is that, at least theoretically, one could prove the correctness of a program by making enough tests.

If one has a program $P$ of length $L$ that computes $f$, there is a bound on the number of functions that can be computed with a source length of at most $L$.

Therefore one would "only" need to prove that:

$f$ can be computed with a source length $\leq L$
$P$ does not compute any other function computable in $L$ bytes or less (by testing)

This idea has probably no practical consequences (the bounds are surely bound to be exponential).

(This was meant as a comment, but went long).
Very interesting question.
If you are willing to think about other complexity measures besides Kolmogorov's, then there are some answers in Learning theory that might satisfy you. I leave it for the experts in the area.

For example, if I'm not mistaken, in "A theory of the learnable" Valiant proved that a boolean function can be reconstructed given a polynomial number of "positive points" on the size of its k-CNF formula (for any fixed k, and I mean
with "positive points" those of the form $(x_1,\ldots,x_n,1)$).

In Knuth's TAOCP 7.2.1.6 it is shown in an astonishing way (using the Christmas tree pattern) that to reconstruct a monote boolean function (i.e. non-decreasing in each variable) you need exactly ${n+1 \choose \lfloor n/2\rfloor+1}$ points.


Motivation for volume estimation What are some concrete and compelling applications for estimating the volume of convex polyhedra of the sort considered in the more recent papers on random walk methods?

These papers on volume estimation mention numerical integration as one motivation. What are examples of integrals that people want to compute in practice which are very hard to compute using previous methods?  Or is there some other compelling practical application for computing the volume of a 1000-dimensional polytope?

Estimating the volume of a convex polytope and the closely related task of sampling from it have applications in private data release.

Roughly, the problem you want to solve is: given a collection of numeric valued queries on a database, come up with answers to those questions that are as close as possible to the real answers, while satisfying differential privacy. In some range of parameters, the optimal algorithm for solving this problem has a geometric description, and implementing it involves sampling from a convex polytope. See here: http://arxiv.org/pdf/0907.3754v3.pdf


Hereditary substitution with a universe hierarchy I've read about hereditary substitution for the Simple Lambda Calculus and for The Logical Framework with distinct terms and types.

I'm wondering, are there any examples of hereditary substitution in a dependently typed system with a universe hierarchy? i.e. where $ True : Set_0 : Set_1:Set_2$ etc.

I'm wondering in particular how to establish an induction measure in such a system. The simply typed version is structurally decreasing in the type of the variable being replaced. This doesn't work work with dependent types, to for LF the paper I linked uses the simply-typed erasure of the terms, performing induction on the shape of the type.

However, erasing to simple types doesn't work with a universe hierarchy, since if you have something like this:

$ f : (x : Set_1)\to x \to True$ implies that
$ f\ ((y : True) \to True \to True ): True \to True \to True$

i.e. applying a function resulted in a structurally larger type.

I'm assuming the solution has something to do with the universe indexes, but if there's an existing technique for establishing that the induction is well founded, I'd prefer to cite it rather than coming up with something up on my own.

As of November 2018, how to do this for dependent type theories with large eliminations is an open question.

Establishing that the recursion is well-founded is not too bad; you can use Pataraia's theorem to prove the fixed point you want exists. See Robert Harper's *Constructing Type Systems Over an Operational Semantics for a how-to. (You can also do this via an inductive-recursive definition.)

The hard part is actually formulating the hereditary substitution in a nice way -- the natural direction leads you towards substituting not one term, but an entire substitution for a context, and this raises a lot of questions about when and how to establish properties of things like compositions of (hereditary) substitutions.

If it turned out to be impossible, I would be utterly shocked. However, at present no one has done it. If you want to work on this, I would suggest getting in touch with Andreas Abel, Dan Licata and Mike Shulman. (Or me, for that matter.)


What is the k-SAT problem? First of all I am of course aware of the wikipedia article: http://en.wikipedia.org/wiki/Boolean_satisfiability_problem

However I still do not understand exactly what the problem is. To demonstrate that I've tried, I think it is as follows but I am not sure:

  The problem of checking whether a given boolean equation with k distinct
  variables is satisfiable.

For example, is this an instance of the 3-sat problem?

x OR y OR z

No, that's not what you thought!

The "K" in K-SAT is not related to the number of variables in the formula; rather, it limits the number of "literals" in each "clause".

Let's define the terms:

atom = the same thing you called variable; e.g. "x", "y", "z", etc.

literal = an atom or its negation; e.g "x" or "$\neg$x".

clause = a disjunction of literals; e.g. $(x \vee y \vee \neg z \vee w)$.

CNF: A formula is said to be in Conjunctive Normal Form (CNF) if it consists of AND's of several clause. For instance, $(x \vee y) \wedge (y \vee \neg z \vee w)$ is a CNF formula.

The followin problem is K-SAT:
Given a CNF formula $f$, in which each clause has exactly K literals, decide whether or not $f$ is satisfiable. That is, whether there is a an assignment to the atoms such that $f$ evaluates to TRUE.

See also Mike Jason B Punkt's answer in this post.


High probable polynomial time algorithm for NP-hard problems? Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed. However, it is not true for real world applications. One example is the SAT problem. Randomly generated SAT problems are greatly different from industry collected SAT problems. The solvers behave quite different.

I am thinking about an approximation scheme that given an unknown distribution $D$ over the problem instances, there exists a polynomial time algorithm $A$ that solves the problems drawn from $D$ successfully with a probability $1-\eta$. $\eta$ somehow relates to the divergence between the $D$ and the random distribution.

Furthermore, if we have samples from $D$, we can estimate $A$, and address the sample complexity and the consistency issue.

I wonder whether such a scheme already exists or not. If so, what is the name and what are the milestones?

Fernandez de la Vega and Karpinski in their paper 9/8-approximation algorithm for
random max-3sat give, as the title suggests, such an algorithm under the uniform distribution over 3sat clauses. Håstad showed that no deterministic 7/8 approximation algorithms exists for max-3sat (unless ...)

I don't know of any clear-cut decision problems, i.e. ones where the algorithm beats an inapproximability result for an optimization problem.


Finite automata that accept binary strings divisible by n I'm working on a problem set for a class, and thought of a question related to what I was working on. Is there a minimum number of states that a finite automaton must have in order to accept binary strings that represent numbers divisible by an integer n? In an earlier problem set, I was able to construct a DFA that accepted binary strings divisible by 3 with 3 states. Is this a coincidence, or is there something inherent to the general problem of detecting strings divisible by n that suggests a minimum number of states?

I promise this will not answer a homework question for me! :)

There is a known formula for minimum number of states for such a finite automaton. This depends on $n$ as well as the radix $R$ of the underlying positional representation.

If $n$ is coprime to $R$, then the minimal number of states is $n$. However, when $n$ shares a factor with the radix then the situation is rather complicated. See Mathematica Journal Vol 3 Issue 11. "Divisibility and State Complexity" by Klaus Sutner.


Proving the set of powers of 2 over ternary alphabet to be non regular. It's simple to see that the powers of 2 over alphabet {0,1} is regular because $10^*$ is a regular expression for it.

But the powers of 2 represented in ternary appears to be non regular. Pumping lemma or residue classes is hard to apply as there seems to be very little pattern among the strings. How do I solve it?

In general, for what powers of $k$ represented in base $r$, is the set regular?

Here's an alternative solution (with detailed explanation) using Myhill-Nerode Theorem. I'll use base $3$ and $2$ for readibility, but the proof generalizes for arbitrary bases $r,k$ that are not powers of the same integer.

(1) Show that given any ternary string $x$, there exists another string $y$ such that $xy$ is a power of $2$.

Proof: Given any $x$ (letting $n$ be the number it represents), $\forall k$ and $c\in \{0,\ldots,3^k-1 \}$, there exists $y$ such that $xy$ represents $3^kn + c$. In fact, this characterizes all the numbers $xy$ can represent. Hence, finding the minimal $y$ such that $xy$ is a power of $2$ is depends on finding the smallest integer $k$ such that we have some power of $2$ in the interval $[3^kn,3^k(n+1)-1]$. Taking log base $2$, we need to find $k$ such that we have an integer in the interval $[k\log 3 + \log x, k\log3 + \log(x+1)]$ (dropping the $-1$ here is iffy, but simplifies calculations which do not rely on it). Notice that changing $k$ only affects the $k\log 3$ portion, so we can find a $k$ that gets us arbitrarily close to some integer.

(2) Given some $x$ and the corresponding minimal $y$, show that there exists a string x' such that the corresponding minimal $y'$ has to be larger than $y$. Repeating this gives us infinitely many equivalence classes of strings.

Proof Outline: Since $\log 2^m x = m + \log x$, given an $x$ and its corresponding $y$ and $k$ we can always find some $x' = 2^m x$ where $\log(2^m x + 1) - \log (2^m x)$ is sufficiently tiny such that no integer is contained in $[k\log 3 + m +\log x, k\log3 + \log(2^mx+1)]$. Note that we are implicitly using the fact that $k\log 3 + \log x$ can never be an integer.


Indications that strengthen the conjecture: NEXP ⊊ EXP^NP I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP.

Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper.

Some Examples:
1.  A paper by Shuichi Hirahara: “Identifying an honest EXP^NP oracle among many”, which states that “No instance checker for EXP^NP -complete languages exists unless EXP^NP = NEXP” https://arxiv.org/abs/1502.07258

A paper by Laszlo Babai, Lance Fortnow and Carsten Lund: “NON-DETERMINISTIC EXPONENTIAL TIME HAS TWO-PROVER INTERACTIVE PROTOCOLS” which states that we do not know whether NEXP provers are sufficient to prove any NEXP language to a verifier, but the best upper bound we know on the power of the provers for NEXP is EXP^NP
http://people.cs.uchicago.edu/~fortnow/papers/mip2.pdf

Are there any additional known results on the conjecture of NEXP ⊊ EXP^NP?
What are its implications on the separation of other classes?

Thanks

Being pulled down by the gravitational force from $\mathrm{BPP}$, hardly any convincing evidence can be lurking on the surface of $\mathrm{EXP}^{\mathrm{NP}}$ for you to see.

Only after proving $\mathrm{BPP}\subseteq \mathrm{P}^\mathrm{NP}$, this class would give up on $\mathrm{EXP}^\mathrm{NP}$. But then, $\mathrm{EXP}$ and $\mathrm{NEXP}$ would have their chances to thrive (on their own).


Are there any classes of functions which require provably different resources to compute versus computing their inverse? Apologies in advance if this question is too simple.

Basically, what I want to know is if there are any functions $f(x)$ with the following properties:

Take $f_n(x)$ to be $f(x)$ when the domain and codomain are restricted to $n$-bit strings. Then

$f_n(x)$ is injective
$f_n(x)$ is surjective
$f_n(x)$ takes strictly less resources (either space/time/circuit depth/number of gates) to compute under some reasonable model than $f^{-1}_n(y)$, where $y=f_n(x)$.
The resource difference for $f_n(x)$ vs $f^{-1}(y)$ scales as some strictly increasing function of $n$.

I can come up with examples where the function is either surjective or injective, but not both unless I resort to a contrived computational model. If I choose a computational model which allows left shifts in unit time on some ring, but not right shifts, then it is of course possible to come up with a linear over head (or higher if you consider some more complicated permutation as a primitive). For this reason I am interested only in reasonable models, by which I mostly mean Turing machines or NAND circuits or similar.

Obviously this must be true if $P\neq NP$, but it would seem that this is also possible if $P=NP$, and so should not amount to deciding that question.

It is entirely possible that this question has an obvious answer or an obvious obstacle to answering which I have missed.

I was asked to repost my comment.  I pointed out this paper by Hastad, which shows that there exist permutations in $NC^0$ that are P-hard to invert:

http://dx.doi.org/10.1016/0020-0190(87)90053-6 (PS)


what is known about efficient set intersections Say you have a number of sets of integers ($S_1, S_2 ... S_n$), and you want to calculate intersections of some of them ($\cap S_1, S_3, S_7$ might be a query, but you want to support many such queries, or maybe even all possible queries)

There is an obvious way to do this in linear time. Are there data-structures that allow for sub-linear time ? (of course, that is not be possible in general: the answer itself might have linear size. But an algorithm might have some other useful properties, like being linear on the answer size, or running on sub-linear time and giving just part of the intersection)

In general, what is the state of the problem? What approaches are known, and what is known to be hard ?

When you want to know about a specific problem, it is always good to start with reading a recent paper.  I recommend you to read this paper and the references therein.

Bolin Ding, Arnd Christian König: Fast Set Intersection in Memory. PVLDB 4(4): 255-266 (2011)


Gap between $BB(n)$ and "second largest" $BB(n)$ If $HT(n)$ is the set of halting times of $n$-state Turing machines on a binary alphabet with empty initial tape, then $BB(n) = \max HT(n)$.

What can we say about the second largest number in $HT(n)$?  Call this $BB_2(n)$.

$BB_2(n)$ is trivially uncomputable, since it lets one compute $BB(n)$: just wait for one more machine to halt.  Naively, I would expect the gap $BB(n) - BB_2(n)$ to be "busy beaver-like", growing faster than any computable function.  Is this provable?

The number of states is just a notion of complexity of the description of computable functions in a model, you can pick any model of computation and any encoding of them as binary strings and then take the length as n and define BB(n) based on that and all the interesting results about BB(n) would still be true, there is boring special about TM model and number of states.
There is nothing that prevents them from picking any modified model of TMs. Generally the questions which are not invariant under such changes of representation of TMs are not about computability or TMs but about the particular representation (like BB(n) mod 2, etc. ) and unless there is some particular reason for them being interesting they don't worth pursuing imho. They are nice puzzles but not of much value.
l
Note that "BB(n) is not computable" is invariant under change of representations of TMs.
So is this question invariant under change of representation of computable functions? The answer I think is no.

i. Consider a representation where we have two special states 0 and 1 and either 0 is initial and just can transition to 1 or 0 is unreachable and 1 is initial. In this encoding the difference is 1.

ii. Consider another representation where we have a UTM plus a part that writes n bits on tape before transitioning to UTM. So the question becomes max f(x) - 2ndmax f(x) where maxes are over n bits strings and where f is an arbitrary computable function. We only need to find a computable function where this is not computable. I haven't thought about it much but my gut says there is such a computable function.


Why is there an enormous difference between SAT solvers? SAT solvers are very important in algebraic attacks, for example walksat and minisat.

However, when solving the benchmark problems available here there is an enormous performance difference between the two - Walksat is much faster than minisat for these problems. Why is this?

This implementation of walksat appears to have some performance improvements - is there any reason it wasn't included in the international SAT Competitions?

Yes, there is a major difference between MiniSAT and WalkSAT. First, let's clarify - MiniSAT is a specific implementation of the generic class of DPLL/CDCL algorithms which use backtracking and clause learning, whereas WalkSAT is the general name for an algorithm which alternates between greedy steps and random steps.

In general DPLL/CDCL is much faster on structured SAT instances while WalkSAT is faster on random k-SAT. Industrial and applied SAT instances tend to have a lot of structure, so DPLL/CDCL is dominant in most modern SAT solvers. Instance to instance one technique may win out, though, which is one reason why portfolio solvers have become popular.

I take a lot of issue with your claim that WalkSAT is much faster than MiniSAT on the instances on that page. For one thing, there are gigabytes of SAT instances there - how many did you try comparing them on? WalkSAT is not at all competitive on most structured instances which is why it's not often seen in competitions.

On a side note - Vijay is right that MiniSAT is still relevant. Actually, because it's open source and well-written, MiniSAT is the solver to beat in order to show that a given optimization has promise. Many people tweak MiniSAT itself to showcase their optimizations - take a look at the "MiniSAT hack" category in the recent SAT competitions.


Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$? An "algorithm" for calculating $ax+b$ would take the steps

Calculate $a$ times $x$
Calculate $b$ plus the result of previous line.

But if the values of $a$ and $b$ are known, can we create a more efficient algorithm for the task?

Of course, when $a = 1$, I can optimize the previous algorithm by simply skipping the first step, and when $b = 0$, an optimization would be to skip step 2. But is there always an optimization that I can do?

More formally

Let $originalAlgorithm$ be the two-step algorithm above. What I want is a meta-algorithm, $M$ that
$$
M(a,b) = optimizedAlgorithm
$$
and, of course,
$$
optimizedAlgorithm(x) = originalAlgorithm(x) = ax+b
$$
but $optimizedAlgorithm$ is more time-efficient than $originalAlgorithm$.

I would rephrase the question as follows:

  Consider the function $F$ and the family of functions $F_{a,b}$ defined as
  $$F_{a,b}(x) = F(a,b,x) =ax+b.$$
  Can we compute $F_{a,b}$ faster than the complexity of $F$?
  If yes, given $a$ and $b$, can we algorithmically find such an algorithm?

As babou wrote I think the answer depends on your computation model.
Let me explain one case:
Consider polynomial size circuits with unbounded fan-in AND, OR, and NOT gates.
Time is defined as the depth of the circuit.

$F$ is complete for $\mathsf{TC}^0$, so it requires super-constant depth, the best known upper-bound requires roughly depth $\lg n/\lg \lg n$.

If we fix $a,b$ then $F_{a,b}$ is in $\mathsf{AC^0}$ and therefore can be computed by a constant depth circuit.
But the depth is constant only in $n$, not in $a,b$.
Can we obtain a dependence of depth on $a$ and $b$ which is better than the more uniform case? The answer is no.

Another model is algebraic circuits with binary plus and times gates and constants.
$F$ can be computed in depth $2$.
It is easy to see that $F_{a,b}$ cannot be computed in depth $1$.

Now assume a modified algebraic model where we have unbounded fan-in gates.
Now $F_{a,b}$ can be computed in depth $1$ by applying addition on $a$ copies of $x$ and one copy of $b$ in one step. $F$ still requires depth $2$.


Max flow with conditional edges Is anyone aware of a max flow algorithm where the edges are conditioned upon one another?

Meaning if I send f units of flow from vertex a --> b, then I have to send .5*f* unit from a --> c.

The problem you describe is a generalization of the equal flow problem first proposed by Sahni.  In addition to the flow network, the input specifies several disjoint sets $R_1, R_2, \dots, R_k$ of arcs; the goal is to find a maximum flow such that for each $i$, all arcs in $R_i$ have the same flow value.

While the fractional version of the equal flow problem can be solved in polynomial time by linear programming, the integer version is NP-hard, even if the capacity of each arc is $1$ and all arcs in each set $R_i$ leave the same vertex $v_i$.  Worse, Meyers and Schulz recently proved that there is no polynomial-time $2^{n(1-\epsilon)}$-approximation algorithm, for any fixed $\epsilon>0$, unless $P=NP$.  (The integrality gap of the fractional LP can be arbitrarily large.)

Carol Meyers and Andreas Schulz.  Integer equal flows.  Operations Research Letters 37(4):245-249, 2009.


Simulation of every physical quantum system on quantum computer Let me quote from the section 9.3 of Classical and Quantum Computation by Kitaev, Shen and Vyalyi.

  With high confidence, we may claim that every physical quantum system
  can be efficiently simulated on a quantum computer, but we can never
  prove this statement.

Why can't we ever prove this statement?

We will never be able to prove this statement, because we can never be able to know for sure whether we have the exact laws of physics, or just a very good approximation to them. Even if we had a satisfactory theory of everything which we could use to make good predictions about every experimentally measurable physical system, there would be no way to tell whether it was correct or a very good approximation.

Having said that, we are still quite far from even coming close to a proof of this statement. For example, we can't even prove that the Standard Model is simulable by a quantum computer. Jordan, Lee, and Preskill have two papers showing how to use a quantum computer to simulate a quantum field theory which is much simpler than the Standard Model. This turns out to be harder than it might at first appear.


Justification for the Hungarian method (Kuhn-Munkres) I wrote an implementation of the Kuhn-Munkres algorithm for the minimum-weight bipartite perfect matching problem based on lecture notes I found here and there on the web. It works really well, even on thousands of vertices. And I agree that the theory behind it is truly beautiful. And yet I still wonder why I had to go to such lengths. I find that these lecture notes don't explain why we can't simply take the primal linear program and pass it to the simplex method. Of course I suspect that it's a question of predictable performance, but since I haven't seen it explicitly stated, I'm not too sure. The polytope's extreme points of the primal are proven to be in 0-1, so it seems that we can feed it directly to a simplex implementation without even formulating the dual. Or am I being simplistic?

(Moved from a comment.)

Of course you can solve any LP by using a general-purpose LP solver, but specialised algorithms typically have a much better performance.

It is not only about theoretical asymptotic performance guarantees, it is also about practical real-world performance. Algorithms such as the Hungarian method can be extremely streamlined and they are relatively easy to implement correctly and efficiently.

You can also often avoid issues like using exact rational numbers vs. floating point numbers; everything can be done easily with integers.


Complexity of counting poset automorphisms A (finite) poset $P = (X, <)$, or partially ordered set, is a (finite) set $X$ equipped with a transitive antisymmetric relation $<$; it can be equivalently seen as a DAG $G = (X, E)$ that is transitive (whenever $(x, y) \in E$ and $(y, z) \in E$ then $(x, z) \in E$).

An automorphism of $P$ is a bijection $f$ from $X$ to $X$ such that $x < y$ iff $f(x) < f(y)$, in other words, both $f$ and $f^{-1}$ are order-preserving. The automorphism is fixed-point-free if there is no $x$ such that $f(x) = x$. Of course, the identity is always an automorphism (which is not fixed-point-free); other automorphisms are said to be non-trivial. Both automorphisms and fixed-point-free automorphisms are well-studied natural notions for posets; intuitively, posets that have non-trivial (fixed-point-free) automorphisms have a certain symmetry.

Is anything known about the complexity of determining if a poset has a non-trivial automorphism, or fixed-point-free automorphism? Or the complexity of counting the number of automorphisms, or fixed-point-free automorphisms?

For DAGs that are not transitive, determining if a DAG has a non-trivial automorphism is in NP and its complexity is unknown, like that of graph isomorphism (source). So, while the problem for transitive DAGs is still in NP, it should not be realistic to prove hardness as that would imply hardness of that open problem; but maybe the graph being transitive makes the problem easier (solvable in polynomial time)?

For other natural counting problems about posets, the problems of antichain counting (antichains are subsets of elements that are all pairwise incomparable), or of linear extension counting (linear extensions are the way to extend the partial order to a total order by adding more comparability relations), are all #P-complete to compute. (source and source). Is it also hard to count automorphisms, then?

Graph isomorphism for bipartite graphs is as hard as graph isomorphism for general undirected graphs. Considering bipartite posets (i.e., seeing bipartite graphs as Hasse diagrams of posets), you may see that counting the automorphisms of bipartite posets is as hard as counting the automorphisms of general undirected graphs.


When does an FO property kill off NL-hardness? Context:  We consider only digraphs.  Let CYCLE be the language of graphs with a cycle; it is an NL-complete problem.  Let HASEDGE be the language of graphs with at least one edge. Then trivially, $\text{CYCLE} \cup \text{HASEDGE}$ is no longer NL-hard, while $\text{CYCLE} \cup \overline{\text{HASEDGE}}$ stays so.

Actual problem: I'm wondering if the language $$\text{CYCLE} \cup \{(V, E):(\exists u,v,x,y)[E(u, v) \land E(x, y) \land \neg E(u, y) \land \neg E(x, v)]\}$$ is still NL-hard.

Question: For which FO formula $\phi$ on the vocabulary of graphs is
$$\text{CYCLE} \cup \{(V, E) : (V, E) \models \phi\}$$
NL-hard?  Is this property decidable?

Thanks for your input!

Let me call the property in your "Actual Problem" $\text{NODIAG}$. The following mapping reduces $\text{CYCLE}$ to $\text{CYCLE} \cup \text{NODIAG}$:

For a given $G=(V,E)$, replace every vertex $v$ in $G$ by two copies $v$ and $v'$, and if there is an edge $(u,v)$ in $E$, let $G'$ have edges $(u,v), (u,v'), (u',v)$ and $(u',v')$.
Thus for every $G$ the graph $G'$ satisfies $\neg \text{NODIAG}$.

Moreover, $G'$ has a cycle iff $G$ has a cycle, therefore $G'$ satisfies $\text{CYCLE} \cup \text{NODIAG}$ iff $G$ satifies $\text{CYCLE}$. Therefore $\text{CYCLE}\cup \text{NODIAG}$ is NL-hard.

I think a similar construction would work for every purely universal property.


How do I use canonical ordering to reduce symmetry in the SAT encoding of the pigeonhole problem? In the paper "Efficient CNF Encoding for Selecting 1 from N Objects", the authors introduce their "commander variable" technique for encoding the constraint, and then talk about the pigeonhole problem.
Since my error may exist in lower-level understanding, let me declare what I think I know before posing the question:

Let $m$ and $n$ be the number of pigeons and holes. The naive encoding uses a propositional variable $X_{i,j}$ that is true when the $i'th$ pigeon is to be put in the $j'th$ hole. The clause $ExactlyOne(X_{1,1}, X_{1,2}, ..., X_{1,n})$ enforces that pigeon 1 must occupy exactly one hole; identical clauses are added for the other pigeons. The clause $AtMostOne(X_{1,1}, X_{2,1}, ..., X_{m,1})$ enforces that no more than one pigeon occupies hole 1; identical clauses are added for the remaining holes.
When there are more pigeons than holes (m > n), the problem is unsolvable (obvious to humans) but the SAT solver doesn't "see" this fact. When it can't find a way to place pigeons $1,2,3,..,m$ it will search an attempt with pigeons $2,1,3,...,m$. It doesn't understand that the order of the pigeons is irrelevant. The paper, among others, calls this symmetry.
Instances where $m=n+1$ are used as a strenuous test of a SAT solver's ability to detect unsatisfiability.

The paper proposes to break the symmetry by enforcing order on pigeons. Pigeon $i$ must be placed in a hole in front of the hole of pigeon $i+1$ (i.e., the pigeon in hole $j$ must have a smaller number than of the pigeon in hole $j+1$). It then disappointingly says, "Due to space limitations, we do not explicitly describe in detail the canonical-ordering encoding, but the number of clauses generated is of order $O(n*log(n))$".
So my question is: what did they do to get these results?
I want to treat the variables $\{X_{1,1}, X_{2,1}, ..., X_{m,1}\}$ as string of bits that, numerically, identifies the choice of which pigeon went into hole 1, and so on. Follow this with $n-1$ comparators to enforce the paper's suggestion. My naive comparator construction, however, requires m clauses, one for each bit (of increasingly ugly size). Help! :)

Let $m$ be the number of pigeons and $n$ be the number of holes.  Let the propositional variables $B_{i,0}$ ... $B_{i,log(n)}$ encode the binary representation of $j-1$ if the $i$th pigeon is put into the $j$th hole. (Example, if pigeon 1 were placed in hole 10, $j - 1 = 9$, which is binary 1001.  So $B_{1,3}$ = true, $B_{1,2}$ = false, $B_{1,1}$ = false and $B_{1,0}$ = true.)

Enforce a particular ordering of the pigeons in the holes by requiring that the hole encoded by the $B_{i}$ variables is less than that of $B_{i+1}$.  The encodings are compared as you would expect:

$B_{i,log(n)}$ < $B_{i+1,log(n)}$
OR
$B_{i,log(n)}$ = $B_{i+1,log(n)}$ AND $B_{i,log(n)-1}$ < $B_{i+1,log(n)-1}$
OR
$B_{i,log(n)}$ = $B_{i+1,log(n)}$ AND $B_{i,log(n)-1}$ = $B_{i+1,log(n)-1}$ AND $B_{i,log(n)-2}$ < $B_{i+1,log(n)-2}$
OR
...

... following the pattern of allowing the most significant bits to be equivalent as long as the next bit to the right is less than that of the next pigeon.  There will be $O(log(n))$ conjunctions per comparator and $O(m)$ comparators, giving the expected $O(m * log(n))$ additional clauses.

The $B$ variable values must be implied by the $X_{i,j}$ values.  Each $B_{i,*}$ bit is implied by any one of a particular set of the $X_{i,j}$ variables being set.  Example: assuming $n = 16$, you would have:

$ExactlyOne(X_{1,9}, X_{1,10}, X_{1,11}, X_{1,12}, X_{1,13}, X_{1,14}, X_{1,15}, X_{1,16}, \overline{B_{1,3}})$

which forces $B_{1,3}$ true if pigeon 1 is placed in any of holes 9-16.  Otherwise $B_{1,3}$ is set false to satisfy the clause.  These clauses set the remaining $B_{i}$ bits.

$ExactlyOne(X_{1,5}, X_{1,6}, X_{1,7}, X_{1,8}, X_{1,13}, X_{1,14}, X_{1,15}, X_{1,16}, \overline{B_{1,2}})$
$ExactlyOne(X_{1,3}, X_{1,4}, X_{1,7}, X_{1,8}, X_{1,11}, X_{1,12}, X_{1,15}, X_{1,16}, \overline{B_{1,1}})$
$ExactlyOne(X_{1,2}, X_{1,4}, X_{1,6}, X_{1,8}, X_{1,10}, X_{1,12}, X_{1,14}, X_{1,16}, \overline{B_{1,0}})$

There will be $log(n)$ of these clauses for each pigeon.  Since there are $m$ pigeons, $m * log(n)$ clauses are added.


AI strategies for losing positions I have a card game that I am analyzing with Maple. Actually, it's a series of card games, one for every parameter k, where k is a natural number (representing the number of ranks of cards used in the game). For small k, it is feasible to completely solve the game by reverse induction. I am trying to create an AI that will play optimally from this.

Given a winning position (and it being the computer's turn) the computer can answer easily with any move that takes the position to a losing one for the player. However, what to do with a losing position? Of course, picking a random move is a terrible strategy. Is there some way to make life very difficult for the human player? One idea I had was to make it choose a move that maximizes the length of the minimum path needed for the player to win the game. That would seem to avoid getting into all the psychology of what human weaknesses are in the game etc.

I am aware that this problem is completely general (does not depend on the game). However, I had difficulty finding good references. Does anyone have any references for someone interested in learning about AI in this setting?

Let's assume all possible paths are finite to make the discussion simpler. This is the case for the vast majority of game actually played such as Chess (because of the 50-move rule) or Go (assuming superko is forbidden).

The idea you have about chosing the move maximizing the minimum path is actually an instance of the following more general idea. A proof tree for player P is a subtree of game tree starting at the current position such that for every node n of the tree

if the position corresponding to n is terminal then P has won on that position
if P is to play in the position corresponding to n, then n has exactly one child
if the opponent of P is to play, then every opponent's move leads to a child of n
A proof tree corresponds to a winning strategy for P, so if a position is a theoretical win, then it should be possible to find a proof tree.

Now, there may be several proof trees to choose from in a given won position. To decide which one should be chosen, you can define a cost for each proof tree. For instance, the fastest win is obtained by finding a proof tree of minimal depth. The simplest win is obtained by finding a proof tree of minimal size etc.
After you have decided on the definition of cost, you get a strategy for the losing player: play the move leading to a position with maximal cost.

Now, the only things that remains is finding the minimum cost for won positions and finding the maximum cost for lost positions. As you have discovered, this can be done by retrograd analysis when the cost is the depth of a tree. It turns out it's not too hard to generalize this for other cost measures still using retrograd analysis.

If your game is too large to perform retrograd analysis or you are only interested in a specific starting position, the problem becomes a little bit harder but you can to use a kind of generalization of the A* algorithm. Shameless plug: I have a paper on this very topic.


Is it decidable whether the langauge accepted by a reversal-bounded counter machine is deterministic? I'm wondering if anyone can point me to either an algorithm or an undecidability proof for the following question:

Given a non-deterministic reversal-bounded multicounter machine $M$,
is there some deterministic reversal-bounded multicounter machine $M'$
such that $L(M) = L(M')$?

For anyone interested, reversal-bounded counter machines are described at length
in Oscar Ibarra's Paper about them.

I found a similar argument for context-free languages, which can be used here.
It is not decidable, since universality for non-deterministic reversal-bounded multicounter machines is undecidable, but becomes decidable for the deterministic version.

Suppose we can decide if $M$ can be determinized, and perform the determinization if it can.
Then we can decide if $L(M) = \Sigma^*$ as follows:

If $M$ cannot be determinized, then clearly it is not universal, since there is a deterministic machine accepting $\Sigma^*$.
If $M$ can be determinized, then we determinize it and test if it is universal.

This question on CS.SE give the analogous argument for CFL vs. DCFL.


Density of multiples I have an infinite collection of positive integers $n_1,n_2,n_3,\ldots$ and I would like to find the density of the numbers divisible by one or more of these.* If the density does not exist, the algorithm can do anything (it's a promise problem).

If the numbers were pairwise coprime, this would simply be
$$
1-\prod_{i=1}^\infty1-\frac{1}{n_i}
$$
which can be approximated with partial products (and an integral for the omitted terms, if they're sufficiently well-behaved).

In the general case this doesn't work, but you can always take the terms $n_1,\ldots,n_k$, take their least common multiple $L$, and check each number $1,2,\ldots,L$ to see how many are divisible by one of the $k$ chosen numbers. But this becomes unwieldy quickly: with $n_i=i^2$ and $k=10$ the sum is about 6 million (taking maybe a second to compute), but with $k=20$ it's 50 quadrillion (taking hundreds of years).

Is this problem known? Is there a good way to approximate this number?

* The density of a subset $S$ of the positive integers
$$
\lim_{n\to\infty}\frac{|\{1,2,\ldots,n\}\cap S|}{n},
$$
that is, the expected fraction of numbers in the set as you look at larger and larger initial intervals. Sometimes this doesn't exist ("numbers starting with 1") but in this case we're promised that it does.

Here's an example of a simplification we can make to the problem. If one of the $n_i$ is prime, then you can

Remove all $n_j$ which are multiples of $n_i$, including $n_i$ itself.
Compute the new density $D_\text{new}$.
The density is $D = 1 - (1-D_\text{old})(1-1/n_i).$

This can be generalized to composite $n_i$ if all terms are either divisible by $n_i$ or else coprime to $n_i$.

This expands the size we can approach with the naive lcm algorithm, but it doesn't fundamentally alter it.

For computable functions LB from {1,2,3,...} to itself, if

1/(LB(1)) + 1/(LB(2)) + 1/(LB(3)) + 1/(LB(4)) + 1/(LB(5)) + ...  computably converges
and
there is a positive integer m such that for all integers i, if  m < i  then  LB(i) ≤ ni

then the density exists and is computable by using m and the convergence to upper-bound the

probability of being divisible by something beyond the cutoff point.  (To verify that that argument works despite density not being countably additive, do that for each {1,2,...,n} separately.)

I only have a vague suggestion for possibly speeding up the finite part:

Perhaps in most cases you can find a good-enough bound on the

sizes of most of the high-order inclusion-exclusion intersections.


Bootstrapping a Finger Tree Structure After working with 2-3 finger trees for quite a bit I have been impressed by their speed in most operations.  However, the one issue I have run into is the large overhead associated with the initial creation of a large finger tree.  Because building is defined as a sequence of concatenation operations you end up building a large number of finger tree structures that are unneeded.

Due to the complex nature of 2-3 finger trees I see no intuitive method for bootstrapping them, and all my searches have come up empty. So the question is, how could you go about bootstrapping a 2-3 finger tree with minimal overhead?

To be explicit: given a sequence $S$ of known length $n$ generate the finger tree representation of $S$ with minimal operations.

The naive way to accomplish is successive calls to the cons operation (in the literature the '$\triangleleft$' operator).  However, this will create $n$ distinct finger tree structures representing all the slices of $S$ for $[1..i]$.

GHC's Data.Sequence's replicate function
 builds a fingertree in $O(\lg n)$ time and space, but this is enabled by knowing the elements that go on the right spine of the finger tree from the get-go. This library was written by the authors of the original paper on 2-3 finger trees.

If you want to build a finger tree by repeated concatenation, you might be able to reduce the transient space usage while building by changing the representation of the spines. The spines on 2-3 finger trees are cleverly stored as synchronized singly-linked lists. If, instead, you store the spines as deques, it may be possible to save space when concatenating trees. The idea is that concatenating two trees of the same height takes $O(1)$ space by reusing the spines of the trees. When concatenating 2-3 finger trees as originally described, the spines that are internal to the new tree can no longer be used as-is.

Kaplan and Tarjan's "Purely Functional Representations of Catenable Sorted Lists" describes a more complicated finger tree structure. This paper (in section 4) also discusses a construction similar to deque suggestion I made above. I believe the structure they describe can concatenate two trees of equal height in $O(1)$ time and space. For building finger trees, is this enough space saving for you?

NB: Their use of the word "bootstrapping" means something a bit different than your use above. They mean storing part of a data structure using a simpler version of the same structure.


Techniques for Reversing the Order of Quantiﬁers It is well-known that in general, the order of universal and existential quantifiers cannot be reversed. In other words, for a general logical formula $\phi(\cdot,\cdot)$,

$(\forall x)(\exists y) \phi(x,y) \quad \not\Leftrightarrow \quad (\exists y)(\forall x) \phi(x,y)$

On the other hand, we know the right-hand side is more restrictive than the left-hand side; that is, $(\exists y)(\forall x) \phi(x,y) \Rightarrow (\forall x)(\exists y) \phi(x,y)$.

This question focuses on techniques to derive $(\forall x)(\exists y) \phi(x,y) \Rightarrow (\exists y)(\forall x) \phi(x,y)$, whenever it holds for $\phi(\cdot,\cdot)$.

Diagonalization is one such technique. I first see this use of diagonalization in the paper Relativizations of the $\mathcal{P} \overset{?}{=} \mathcal{NP}$ Question (see also the short note by Katz). In that paper, the authors first prove that:

  For any deterministic, polynomial-time oracle machine M, there exists a language B such that $L_B \ne L(M^B)$.

They then reverse the order of the quantifiers (using diagonalization), to prove that:

  There exists a language B such that for all deterministic, poly-time M we have $L_B \ne L(M^B)$.

This technique is used in other papers, such as [CGH] and [AH].

I found another technique in the proof of Theorem 6.3 of [IR]. It uses a combination of measure theory and pigeon-hole principle to reverse the order of quantifiers.

  I want to know what other techniques are used in computer science, to reverse the order of universal and existential quantifiers?

Reversal of quantifiers is an important property that is often behind well known theorems.

For example, in analysis the difference between $\forall \epsilon > 0 . \forall x . \exists \delta > 0$ and $\forall \epsilon > 0 . \exists \delta > 0 . \forall x$ is the difference between pointwise and uniform continuity. A well known theorem says that every pointwise continuous map is uniformly continuous, provided the domain is nice, i.e., compact.

In fact, compactness is at the heart of quantifier reversal. Consider two datatypes $X$ and $Y$ of which $X$ is overt and $Y$ is compact (see below for explanation of these terms), and let $\phi(x,y)$ be a semidecidable relation between $X$ and $Y$. The statement $\forall y : Y . \exists x : X . \phi(x,y)$ can be read as follows: every point $y$ in $Y$ is covered by some $U_x = \lbrace z : Y \mid \phi(x,z) \rbrace$. Since the sets $U_x$ are "computably open" (semidecidable) and $Y$ is compact there exists a finite subcover. We have proved that
$$\forall y : Y . \exists x : X . \phi(x,y)$$
implies
$$\exists x_1, \ldots, x_n : X . \forall y : Y . \phi(x_1,y) \lor \cdots \lor \phi(x_n, y).$$
Often we can reduce the existence of the finite list $x_1, \ldots, x_n$ to a single $x$. For example, if $X$ is linearly ordered and $\phi$ is monotone in $x$ with respect to the order then we can take $x$ to be the largest one of $x_1, \ldots, x_n$.

To see how this principle is applied in a familiar case, let us look at the statement that $f : [0,1] \to \mathbb{R}$ is a continuous function. We keep $\epsilon > 0$ as a free variable in order not to get confused about an outer universal quantifier:
$$\forall x \in [0,1] . \exists \delta > 0 . \forall y \in [x - \delta, x + \delta] . |f(y) - f(x)| < \epsilon.$$
Because $[x - \delta, x + \delta]$ is compact and comparison of reals is semidecidable, the statement $\phi(x, \delta) \equiv \forall y \in [x - \delta, x + \delta] . |f(y) - f(x)| < \epsilon$ is semidecidable. The positive reals are overt and $[0,1]$ is compact, so we can apply the principle:
$$\exists \delta_1, \delta_2, \ldots, \delta_n > 0 . \forall x \in [0,1] . \phi(\delta_1, x) \lor \cdots \phi(\delta_n, x).$$
Since $\phi(\delta, x)$ is antimonotone in $\delta$ the smallest one of $\delta_1, \ldots, \delta_n$ does the job already, so we just need one $\delta$:
$$\exists \delta > 0 . \forall x \in [0,1] . \forall y \in [x - \delta, x + \delta] . |f(y) - f(x)| < \epsilon.$$
What we have got is uniform continuity of $f$.

Vaguely speaking, a datatype is compact if it has a computable universal quantifier and overt if it has a computable existential quantifier. The (non-negative) integers $\mathbb{N}$ are overt because in order to semidecide whether $\exists n \in \mathbb{N} . \phi(n)$, with $\phi(n)$ semidecidable, we perform the paralel search by dovetailing. The Cantor space $2^\mathbb{N}$ is compact and overt, as explained by Paul Taylor's Abstract Stone Duality and Martin Escardo's "Synthetic Topology of Datatypes and Classical Spaces" (also see the related notion of searchable spaces).

Let us apply the principle to the example you mentioned. We view a language as a map from (finite) words over a fixed alphabet to boolean values. Since finite words are in computable bijective correspondence with integers we may view a language as a map from integers to boolean values. That is, the datatype of all languages is, up to computable isomorphism, precisely the Cantor space nat -> bool, or in mathematical notation $2^\mathbb{N}$, which is compact. A polynomial-time Turing machine is described by its program, which is a finite string, thus the space of all (representations of) Turing machines can be taken to be nat or $\mathbb{N}$, which is overt.

Given a Turing machine $M$ and a language $c$, the statement $\mathsf{rejects}(M,c)$ which says "language $c$ is rejected by $M$" is semidecidable because it is in fact decidable: just run $M$ with input $c$ and see what it does. The conditions for our principle are satisfied! The statement "every oracle machine $M$ has a language $b$ such that $b$ is not accepted by $M^b$" is written symbolically as
$$\forall M : \mathbb{N} . \exists b : 2^\mathbb{N} . \mathsf{rejects}(M^b,b).$$
After inversion of quantifiers we get
$$\exists b_1, \ldots, b_n : 2^\mathbb{N} . \forall M : \mathbb{N} . \mathsf{rejects}(M^{b_1}, b_1) \lor \cdots \lor \mathsf{rejects}(M^{b_n},b_n).$$
Ok, so we are down to finitely many languages. Can we combine them into a single one? I will leave that as an exercise (for myself and you!).

You might also be interested in the slightly more general question of how to transform $\forall x . \exists y . \phi(x,y)$ to an equivalent statement of the form $\exists u . \forall v . \psi(u,v)$, or vice versa. There are several ways of doing this, for example:

Skolem normal form,
Herbrand normal form,
Gödel's functional interpretation.


Combinatorial characterization of exact learning with membership queries Edit: Since I haven't received any responses/comments in a week, I'd like to add that I'm happy to hear anything about the problem. I don't work in the area, so even if it's a simple observation, I may not know it. Even a comment like "I work in the area, but I haven't seen a characterization like this" would be helpful!

Background:

There are several well-studied models of learning in learning theory (e.g., PAC learning, online learning, exact learning with membership/equivalence queries).

For example, in PAC learning, the sample complexity of a concept class has a nice combinatorial characterization in terms of the VC dimension of the class. So if we want to learn a class with constant accuracy and confidence, this can be done with $\Theta(d)$ samples, where $d$ is the VC dimension. (Note that we're talking about sample complexity, not time complexity.) There is also a more refined characterization in terms of the accuracy and confidence. Similarly, the mistake bound model of online learning has a nice combinatorial characterization.

Question:

I want to know if a similar result is known for the model of exact learning with membership queries. The model is defined as follows: We have access to a black box which on input $x$ gives you $f(x)$. We know $f$ comes from some concept class $C$. We want to determine $f$ with as few queries as possible.

  Is there a combinatorial parameter of a concept class $C$ that characterizes the number of queries needed to learn a concept in the model of exact learning with membership queries?

What I know:

The best such characterization I have found is in this paper by Servedio and Gortler, using a parameter they attribute to Bshouty, Cleve, Gavaldà, Kannan and Tamon. They define a combinatorial parameter called $\gamma^C$, where $C$ is the concept class, which has the following properties. (Let $Q_C$ be the optimal number of queries needed to learn $C$ in this model.)

  $Q_C = \Omega(1/\gamma^C)\qquad Q_C = \Omega(\log |C|) \qquad Q_C = O(\log |C|/\gamma^C)$

This characterization is almost tight. However, there could be a quadratic gap between the upper and lower bounds. For example if $1/\gamma^C = \log |C| = k$, then the lower bound is $\Omega(k)$, but the upper bound is $O(k^2)$. (I also think this gap is achievable, i.e., there exists a concept class for which the lower bounds are both $\Omega(k)$, but the upper bound is $O(k^2)$.)

To drive home the point of anonymous moose's example, consider the concept class that consists of functions that output 1 on only one point in {0,1}^n. The class is of size 2^n, and 2^n queries are needed in the worst-case. Take a look at worst-case Teaching Dimension (Goldman & Schapire) which provides something similar to what you're looking for.


Definitional equality of recursive function definition by "infinite unfolding" The context is checking definitional equality in dependent type theory implementations.

Consider in Coq

Fixpoint predd(a: nat): nat :=
  match a with
  | O => O
  | S b => predd(b)
  end.

Fixpoint preddd(a: nat): nat :=
  match a with
  | O => O
  | S b => match b with | O => O | S c => preddd(c) end
  end.

Fixpoint predd2(a: nat): nat :=
  match a with
  | O => O
  | S b => preddd(b)
  end.

So predd is a function that recursively call itself and return O eventually. it is popositionaly equal to _ => O

preddd is the predd unfold once inside.

predd2 is just predd but calls preddd inside.

predd2 and preddd is not definitionaly equal in Coq. But can we have another definitional equality for recursive functions?

I have an idea of definitional equality of recursive functions, such that if the infinite unfolding of recursive definition is equal, then the two value is equal. such "infinite unfolding" seems can be made precise by requiring the finite unfoldings of values always have a similarity relation.

So, is there a sound definition of "definitional equality of recursive functions by infinite expansions"?

Can this be constructively implemented?

Your predd2 is not a fixpoint; you could replace the Fixpoint by Definition. And the fact that they are not convertible is due to the lack of eta-conversion for inductive types in Coq.

The reason for this is that we want the conversion to be decidable, and it's already hard to decide beta-eta-conversion in the simply typed case (see Deciding equivalence with sums and the empty type by Gabriel Scherer).

You can more or less check that "a is convertible to b" by using the following notation:

Notation "n ~ m" := (eq_refl : n = m) (at level 70, no associativity).

(It has the expected behaviour on +:

Check fun n => 0 + n ~ n.
Fail Check fun n => n + 0 ~ n.

)

And you can check that there is no eta-conversion for booleans, for natural numbers, or even for the unit type:

Fail Check fun x : bool => if x then tt else tt ~ tt.
Fail Check fun x : nat => match x with | 0 => tt | S _ => tt end ~ tt.
Fail Check fun x : unit => match x with tt => tt end ~ tt.

(Those are specific cases of the eta conversion for those inductive types, but since they already fail, it still shows that the full eta conversion can't be included in the conversion)

Now, going back to your specific example (with the names changed). I use the names:

$f_i$ for the recursive function that returns $0$ immediately if its argument $n$ is between $0$ and $i-1$, and otherwise recursively calls its self on $n-i$. $f_1$ is your predd and $f_2$ is your preddd.
$\text{eta}\_\text{fun}\_f_i$ is the eta-expansion (as a function) of $f_i$.
$\text{eta}\_\text{fun}\_\text{eta}\_\text{nat}\_f_i$ is the result of eta-expanding the body (with the eta-expansion of natural numbers) of $\text{eta}\_\text{fun}\_f_i$.
$g_i$ is the function that returns $0$ immediately if its argument $n$ is $0$, and otherwise returns $f_i(n-1)$.

We have $g_1\equiv \text{eta}\_f_1 \not \equiv \text{eta}\_\text{fun}\_\text{eta}\_\text{nat}\_f_2 \equiv f_1$, which shows that the problem is indeed the lack of eta-conversion for natural numbers.

We have $g_1\equiv \text{eta}\_f_1 \not \equiv \text{eta}\_\text{fun}\_\text{eta}\_\text{nat}\_f_2 \not\equiv f_1$. The first $\not\equiv$ is still due to the same reason. I think the second one is more about unfolding of fixpoints.

Here is a Coq script that supports what I said above:

Fixpoint f1 n := (* predd *)
  match n with
  | O => O
  | S n' => f1 n'
  end
.

Definition eta_fun_f1 n :=
  f1 n
.

Definition eta_fun_eta_nat_f1 n :=
  match n with
  | 0 => f1 0
  | S n' => f1 (S n')
  end
.

Definition g1 n :=
  match n with
  | 0 => 0
  | S n' => f1 n'
  end
.

Check f1 ~ eta_fun_f1.
Fail Check eta_fun_f1 ~ eta_fun_eta_nat_f1.
Check eta_fun_eta_nat_f1 ~ g1.

Fixpoint f2 n := (* preddd *)
  match n with
  | 0 => 0
  | S n' =>
    match n' with
    | 0 => 0
    | S n'' => f2 n''
    end
  end
.

Definition eta_fun_f2 n :=
  f2 n
.

Definition eta_fun_eta_nat_f2 n :=
  match n with
  | 0 => f2 0
  | S n' => f2 (S n')
  end
.

Definition g2 n := (* predd2 *)
  match n with
  | 0 => 0
  | S n' => f2 n'
  end
.

Check f2 ~ eta_fun_f2.
Fail Check eta_fun_f2 ~ eta_fun_eta_nat_f2.
Fail Check eta_fun_eta_nat_f2 ~ g2.


Pathwidth of planarized drawing of $K_{3,n}$ The pathwidth of the complete bipartite graph $K_{3,n}$ with partite sets of size $3$ and $n$ is at most $3$. I am interested in planarizing this graph by the following process:

Draw it in the plane such that no edge contains a vertex in its interior, and such that no more than 2 edges cross at any point.
Replace every crossing point of two edges by a new vertex of degree 4.

Then the resulting graph is clearly planar. While $K_{3,n}$ has constant pathwidth, some preliminary investigations suggest that regardless of the drawing you use to planarize $K_{3,n}$, you cannot guarantee that the planarized graph has constant pathwidth independent of $n$; I believe the pathwidth of the planarized graph must grow with $n$. Is this known, or implied by some existing result?

On the other hand, I have a family of graphs of constant degree and bounded pathwidth, which I can planarize without increasing the pathwidth by more than a constant. Is there a general result saying that this is always possible for graphs of bounded degree and pathwidth?

A naive drawing of $K_{3,n}$ will have pathwidth $O(n)$. I think that's tight, and that the pathwidth is always $\Omega(n)$. Here's an argument why.

(1) Fix a drawing of $K_{3,n}$. Without loss of generality we can assume that no two incident edges cross and that no two edges cross twice, for otherwise we can modify the drawing to eliminate these crossings without hurting the pathwidth. Every $K_{3,3}$ subgraph of $K_{3,n}$ has a crossing, there are $n-2$ ways of extending any particular crossing to a $K_{3,3}$ subgraph, and there are $\tbinom{n}{3}$ $K_{3,3}$ subgraphs. Therefore, the number of crossings is at least $n^2/6$. (Actually a tight bound approximately $n^2/4$ is known but it doesn't change the rest.)

(2) Set $S$ to be the set of all edges in $K_{3,n}$, and consider any linear arrangement of the crossings in the whole drawing. Repeat the following steps:

(2a) Consider the point of that arrangement that bisects the crossings between pairs of edges in $S$. Define an edge of $S$ to be "cut" if all of its crossing points with other edges in $S$ are in the same half of this bisection, and "uncut" otherwise.

(2b) If there are at least $\epsilon n$ cut edges of the drawing (for some suitable constant $\epsilon$), then each of them contributes an edge of the planarization that also crosses the bisection point of the linear arrangement. This shows that the linear arrangement has vertex separation number $\Omega(n)$, but since the pathwidth is just the minimum vertex separation number of a linear arrangement, the pathwidth is also $\Omega(n)$.

(2c) In the remaining case, there are very few cut edges, so most of the crossings in $S$ come from pairs of uncut edges, which must both be on the same side of the bisection.
Almost half of the $S$--$S$ crossings are on each side of the bisection, and at least one of the two sides of the bisection has fewer than half of the edges in $S$. Replace $S$ by the subset of edges on that side and repeat.

(3) Each repetition of steps (2a)–(2c) approximately doubles the density of crossings / pairs of edges in $S$, because the number of crossings is halved and the number of pairs of edges is quartered. This density already starts out constant and can't exceed one. Therefore, after a constant number of repetitions, step (2b) will succeed in finding a linear number of cut edges, showing that the pathwidth is at least linear.

As for your suggestion that bounded-degree bounded-pathwidth graphs have layouts whose planarization has bounded pathwidth: this seems indeed to be true.

Find a linear ordering of the vertices of the given graph with bounded vertex separation number: that is, at each point in a left-to-right sweep of the ordering there should be finitely many vertices left of the sweep point that have neighbors to the right. Draw the graph in a left-to-right sweep of this ordering, with its edges placed on horizontal tracks, with each of the partially completed vertices having a set of $O(1)$ tracks for its remaining edges to be connected to the right. Thus, the total number of tracks is the product of the degree with the pathwidth, $O(1)$. When you reach a new vertex, you can add nearly-vertical connectors to the tracks of other vertices that should be connected to it, and shorter connections to its outgoing tracks. Here's an example, with vertex separation number three, degree three, and three tracks per vertex.

This layout, also, has bounded separation number, because the only crossings are on tracks so there can be at most one vertex with an incomplete neighborhood per track. So the pathwidth of the planarization is also $O(1)$, and more precisely at most proportional to the product of the degree and the original pathwidth.


$O(m+n)$ really necessary for graph algorithms? It is standard to express the running time of linear-time graph algorithms as $O(m+n)$ (such as depth-first-search, etc.).

For nearly all such algorithms, vertices of degree zero have no effect on the underlying graph problem. So a solution to the graph problem can usually treat all these unsupported vertices jointly, and does not need to process them individually. For example, in depth-first-search, it suffices to list the dfs-tree for the supported vertices, along with an auxiliary record that all other vertices are unsupported.

If the graph is presented with any kind of intelligent data structure, it should be possible to process in time $O(m)$, and to generate a data structure that encodes the solution in time $O(m)$. This applies even in the case that $n \gg m$.

My question is, what is the reason for the notation $O(m+n)$? Are there really algorithms which require this running time $\Omega(n)$ in the regime $n \gg m$? Is this basically for pedagogical purposes only?

Even when stored very efficiently, vertices with zero degree must be stored in some nonzero space (otherwise, how can we say they even exist)?  That said, they can be stored and searched more efficiently than $O(|V| + |E|)$ using similar ideas to what you describe.

For example, you could just take a standard data structure for storing graphs and store the set of nodes $V' \subseteq V$ which have degree greater than 0.  We don't need to store any information about $V_0$, the set of nodes with degree 0, except for how many there are.

In other words, in a graph with vertices $V$ and edges $E$, if we define

$V' = \{v\in V | v \mbox{ has degree} > 0\}$

$V_0 = \{v\in V | v \mbox{ has degree }  0\}$

We can store the nodes with nonzero degree in $O(|V'| + |E|)$ space, and the nodes with zero degree in $O(\log |V_0|)$ space, giving a total of $O(|V'| + |E| + \log |V_0|)$ space.

Many algorithms that run in linear time, for example BFS and DFS, will run in time $O(|V'| + |E|)$ because the algorithm can just ignore the vertices with degree zero.  Like you say, if $n >> m$, this is much more efficient than the standard algorithm.

There are many cases where algorithms are parameterized by factors in addition to the size of the input.  Other examples of this include

Output-sensitive algorithms like range queries for range trees, which run in time $O(\log n + k)$ where $k$ is the size of the query returned.
Succinct data structures, which store data in space proportional to the entropy of the stored data
Algorithms in the external memory model (section 2 of that in particular--in fact the lecture notes for Erik Demaine's class on Data Structures deal with most of these concepts) depend on the size of a cache and the size of a block transferred from the cache to the processor.
Sparse matrix data structures, and similar structures and algorithms for sparse graphs, which are probably the most similar to what you're asking about.

Most of the references here are fairly general/low level, but there are a great deal of research papers on many of these topics.  In any case, there are sometimes good reasons to use another parameter while analyzing an algorithm's running time, but for general algorithms like DFS, it's assumed that no special data structure or storage methodology is used, leading to $O(|V| + |E|)$ time.


Bipartite maximum matching size from eigenvalues Supposing we know the adjacency matrix $\mathcal{A}_{G}$ of a given regular (or irregular) bipartite graph $G$. Are there good lower and upper bounds to the size of maximum matching from the graph's adjacency matrix's or its Laplacian's eigenvalues (without using an algorithm to calculate explicitly a maximum matching)?

As an expansion of the comment I made above, here it is in answer form.

I'll just talk about maximum matchings, since that will demonstrate the point.  Suppose that we consider both $K_{1,2n-1}$ and $K_{n,n}$. The first has a maximum matching of size 1, since it's a star graph, and the other has $n$ for obvious reasons.

It's easiest to reason about the normalized adjacency matrix $D^{-1}A$, but the same applies to the normalized Laplacian.  Both of these graphs have an eigenvalue of 1, because every connected graph does. The corresponding eigenvector is the vector of all ones (this is easy enough to see because $A\mathbf{1} = D\mathbf{1}$). Since they're bipartite, they both also have eigenvalues of -1, with eigenvectors corresponding to being negative on one side and positive on the other: e.g. the column vector with parts $\mathbf{1}_L$ and $-\mathbf{1}_R)$.

The trick is to see that the other eigenvalues are zero. But this should be obvious, because the adjacency matrix of a complete bipartite graph only has two independent rows/columns. Any others are just copies of these.


Which graph parameters are NOT concentrated on random graphs? It is well known that many important graph parameters show (strong) concentration on random graphs, at least in some range of the edge probability. Some typical examples are the chromatic number, maximum clique,  maximum independent set, maximum matching, domination number, number of copies of a fixed subgraph, diameter, maximum degree, choice number (list coloring number), Lovasz $\theta$-number, tree width, etc.

Question: Which are the exceptions, that is, meaningful graph parameters that are not concentrated on random graphs?

Edit.
A possible definition of concentration is this:

Let $X_n$ be a graph parameter on $n$-vertex random graphs. We call it concentrated, if for every $\epsilon>0$, it holds that
$$\lim_{n\rightarrow\infty}\Pr\big((1-\epsilon)E(X_n)\leq X_n \leq (1+\epsilon)E(X_n)\big)=1.$$
The concentration is strong, if the probability approaches 1 at an exponential rate. But sometimes strong is used in a different sense, referring to the fact that the convergence remains true with a shrinking interval, yielding a possibly very narrow range.
 For example, if $X_n$ is the minimum degree, then, for some range of the edge probability $p$,  one can prove
$$\lim_{n\rightarrow\infty}\Pr\big(\lfloor E(X_n)\rfloor\leq X_n \leq \lceil E(X_n)\rceil\big)=1$$
which is the shortest possible interval (as the degree is integer, but the expected value may not be).

Note: One can construct artificial exemptions from  the concentration rule. For example, let $X_n=n$, if the graph has an odd number of edges, and 0 otherwise. This is clearly not concentrated, but I would not consider it a meaningful parameter.

Many parameters  of the largest connected component are not concentrated for $G(n,p)$ if $p=1/n$ and more generally if $p$ is in the critical window. Examples are the diameter and the size of the largest component, the size of the second largest component, the number of leaves the component has, etc.

See e.g.

Aldous, David. "Brownian excursions, critical random graphs and the multiplicative coalescent." The Annals of Probability (1997): 812-854.

Nachmias, Asaf, and Yuval Peres. "Critical random graphs: diameter and mixing time." The Annals of Probability 36, no. 4 (2008): 1267-1286.

Addario-Berry, Louigi, Nicolas Broutin, and Christina Goldschmidt. "The continuum limit of critical random graphs." Probability Theory and Related Fields 152, no. 3-4 (2012): 367-406.


The chromatic number of a graph as a functor I was fooling around with some concept and was wondering if this viewpoint is explored at all. Let INJ-GRAPH be the subcategory of graphs (with morphisms as homomorphisms) whose morphisms consist only of the graph homomorphisms which are injective as sets. Then clearly for such a homomorphism $f : G \to H$ of graphs, the chromatic number of $H$ is at least as large as the chromatic number of $G$. Thus one gets a covariant functor from INJ-GRAPH to the order category of $\mathbb{N}$ (i.e. the category whose objects are natural numbers and there is a unique arrow $a \to b$ if and only if $a \leq b$)

What's more is that this functor preserves coproducts. Indeed the coproduct of two graphs is given by the disjoint union of the graphs, and the chromatic number of this graph is the maximum of the chromatic number of the two graphs. I'm unsure if it preserves more general colimits, but I think at least if they are small then it should be ok.

Anyway, the question is, has this kind of category-theoretic reasoning been investigated in the literature? It currently seems like abstract nonsense, but perhaps it is indicative of something deeper.

Sure, category theorists know such things, but I think for the difficult results that graph theorists care about, the generalities of category theory may at best help as an organizing principle. This is a bit similar to the theory of combinatorial species, which is a way of doing combinatorics inspired by category theory.

Here are some other basic observations, you can read more about such things in Lawvere's Qualitative distinctions between some toposes of generalized graphs, Categories in computer science and logic (Boulder, CO, 1987), volume 92 of Contemporary Mathematics, 261–299. American Mathematical Society.

The category of directed graphs is a presheaf topos on the site consisting of two parallel arrows (so that a presheaf is given by two sets $E$ and $V$ and maps $t : E \to V$ and $s : E \to V$), see A Guided Tour in the Topos of Graphs by Sebastiano Vigna.

For any given $n$, the category of $n$-colored graphs is a topos, because it is just the slice of the topos of graphs over the complete graph on $n$ vertices (an $n$-coloring of $G$ is just a morphism $G \to K_n$).

As Lawvere explains, several other categories of graphs are toposes because they are (equivalent to) toposes of monoid actions for a suitably chosen $M$. Let's just do one. Consider the monoid $M$ of endomaps on $2 = \{0,1\}$. There are four maps $2 \to 2$, we give them names: the identity map $i$, the constant map $0$, the constant map $1$, and the twist map $t$.

An object in the topos of $M$-sets is a set $S$ with a right $M$ action, which is a map $s : S \times M \to S$ satisfying $s(x, i) = x$ and $s(x, f \circ g) = s(s(x, f), g)$. Since there are only four elements in $M$, we might as well figure out what this means. Let $S_0 = \{x \in S \mid \exists y \in S \,.\, x = s(y, 0)\}$ be the set of those elements of $S$ that arise as actions of~$0$. We define $S_1$ similarly. Because $0 \circ g = 0$, it follows for every $g \in M$ and $x \in S_0$ that
$$s(x, g) = s(s(y,0), g) = s(y, 0 \circ g) = s(y, 0) = x.$$
So, the elements of $S_0$ are fixed by the action. Similarly, the elements of $S_1$ are fixed by the action.

To every $M$-set $(S,s)$ we associate a graph $G_S$ as follows. The vertices of $G_S$ are the elements of $S_0 \cup S_1$. The half-edges of $G_S$ are the elements of $S$. Given a half-edge $e \in S$, its source is the vertex $s(e, 0)$. The opposite half-edge of $e$ is $S(e, t)$, and because $t \circ t = 1$, tit follows that the opposite of the opposite is the original half-edge. An edge is a half-edge together with its opposite. The target of a half-edge is the source of its opposite half-edge, i.e., the target of $e$ is $s(s(e,t),0) = s(e,1)$. (There is an anomaly which we allow: a half-edge may be its own opposite.)

What sort of graphs did we get? They are symmetric graphs in which each edge consists of two half-edges. An edge may be degenerate when it is composed of two copies of the same half-edge. In addition, the graphs are reflexive in the sense that each vertex has a distinguished degenerate loop starting and ending at the vertex (this is because $S_0 \cup S_1 \subseteq S$).

Exercise: figure out what the morphisms are, and then show that the description in terms of reflexive symmetric graphs gives a category that it equivalent to the topos of $M$-sets.

Is this the sort of thing you were asking about?


Is optimal equal-point graph splitting NP-Complete? The problem is "Given a graph G with kn points, divide it into k pages of n points such that the number of edges between points on different pages is minimal." (I've worked on it with undirected graphs, but I think the basic problem is the same with directed graphs and multigraphs.) I've attacked with branch and bound and linear programming, and it's behaved as an NP-complete program--a 12 point, 4 page problem is solved almost instantly, but a 40 point, 8 page problem took over a day. Then again, those are solutions you use for NP-Complete problems. I see no obvious reduction of 3SAT or Travelling Salesman into it, but it feels like an NP-Complete problem--though that may be because I took a class on solving NP-Complete problems, so hammer and nail.

Editing my answer to give a stronger result:

The problem is NP-hard for k=2 and called the Minimum Bisection Problem.