What is the contribution of lambda calculus to the field of theory of computation? I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with functions/reductions (crudely speaking). Some questions keep nagging at me though:

What's the point of lambda calculus? Why go through all these functions/reductions? What is the purpose?
As a result I'm left to wonder: What exactly did lambda calculus do to advance the theory of CS? What were it's contributions that would allow me to have an "aha" moment of understanding the need for its existence?
Why is lambda calculus not covered in texts on automata theory? The common route is to go through various automata, grammars, Turing Machines and complexity classes. Lambda calculus is only included in the syllabus for SICP style courses (perhaps not?). But I've rarely seen it be a part of the core curriculum of CS. Does this imply it's not all that valuable? Maybe not and I maybe missing something here?

I'm aware that functional programming languages are based on lambda calculus but I'm not considering that as a valid contribution, since it was created much before we had programming languages. So, really what is the point of knowing/understanding lambda calculus, w.r.t. its applications/contributions to theory?

$\lambda$-calculus has two key roles.

It is a simple mathematical foundation of sequential, functional, higher-order
computational behaviour.
It is a representation of proofs in   constructive
logic.

This is also known as the Curry-Howard correspondence.  Jointly,
the dual view of $\lambda$-calculus as proof and as (sequential,
functional, higher-order) programming language, strengthened by the algebraic feel
of $\lambda$-calculus (which is not shared by Turing machines), has lead
to massive technology transfer  between logic, the foundations of mathematics, and programming.
This transfer is still ongoing, for example in homotopy type theory.  In
particular the development of programming languages in general, and
typing disciplines in particular, is inconceivable without
$\lambda$-calculus. Most programming languages owe some degree of debt to
Lisp and ML (e.g. garbage collection was invented for Lisp), which are direct descendants of the $\lambda$-calculus. A
second strand of work strongly influenced by $\lambda$-calculus are
interactive proof assistants.

Does one have to know $\lambda$-calculus to be a competent programmer, or
even a theoretician of computer science?    No. If you are not interested
in types, verification and programming languages with higher-order
features, then it's probably a model of computation that's not
terribly useful for you. In particular, if you are interested in complexity theory, then
$\lambda$-calculus is probably not an ideal model because the basic
reduction step $$(\lambda x.M) N \rightarrow_{\beta} M[N/x]$$ is powerful: it can make an arbitrary number of copies on $N$, so
$\rightarrow_{\beta}$ is an unrealistic basic notion in accounting for
the microscopic cost of computation. I think this is the main reason why
Theory A is not so enamoured of $\lambda$-calculus. Conversely, Turing machines are not terribly inspirational for programming language development, because there are no natural notions of machine composition, whereas with $\lambda$-calculus, if $M$ and $N$ are programs, then so is $MN$. This algebraic view of computation relates naturally to programming languages used in practice, and much language development can be understood as the search for, and investigation of novel program composition operators.

For an encyclopedic overview of the history of $\lambda$-calculus see History of Lambda-calculus and Combinatory Logic by Cardone and Hindley.


Context Sensitive Grammars and Types 1) What, if any, is the relationship between static typing and formal grammars?

2) In particular, would it be possible for a linear bounded automaton to check whether, say, a C++ or SML program was well typed? A nested stack automaton?

3) Is there a natural way to express static typing rules in formal grammar terms?

It is not possible for linear bounded automata to check whether C++ programs, and unlikely to be possible for and LBA to check whether SML programs are well-typed. C++ has a Turing-complete type system, since you can code arbitrary programs as template metaprograms.

SML is more interesting. It does have decidable type checking, but the problem is EXPTIME-complete. Hence it is unlikely an LBA can check it, unless there is a very surprising collapse in the complexity hierarchy. The reason for this is that SML requires type inference, and there are families of programs the size of whose type grows much faster than the size of the program. As an example, consider the following program:

fun delta x = (x, x)        (* this has type 'a -> ('a * 'a), so its return value
                               has a type double the size of its argument *)

fun f1 x = delta (delta x)  (* Now we use functions to iterate this process *)
fun f2 x = f1 (f1 x)
fun f3 x = f2 (f2 x)        (* This function has a HUGE type *)

For simpler type systems, such as C or Pascal's, I believe it is possible for an LBA to check it.

In the early days of programming languages research, people sometimes used van Wingaarden grammars (aka two-level grammars) to specify type systems for programming languages. I believe Algol 68 was specified in this way. However, I am told this technique was abandoned for essentially pragmatic reasons: it turned out to be quite difficult for people to write grammars that specified what they thought they were specifying! (Typically, the grammars people wrote generated larger languages than they intended.)

These days people use schematic inference rules to specify type systems, which is essentially a way of specifying predicates as the least fixed point of a collections of Horn clauses. Satisfiability for first-order Horn theories is undecidable in general, so if you want to capture everything type theorists do, then whatever grammatical formalism you choose will be stronger than is really convenient.

I know there has been some work on using attribute grammars to implement type systems. They claim there are some software engineering benefits for this choice: namely, attribute grammars control information flow very strictly, and I am told this makes program understanding  easier.


Does the infinite graph of diagonals have an infinite component? Suppose we connect the points of $V = \mathbb{Z}^2$ using the set of undirected edges $E$ such that either $(i, j)$ is connected to $(i + 1, j + 1)$, or $(i + 1, j)$ is connected to $(i, j + 1)$, independently and uniformly at random for all $i, j$.

(Inspired by the title and cover of this book.)

What is the probability that this graph has an infinitely large connected component?
Similarly,
consider $\mathbb{R}^2 \setminus G$, the complement of the planar embedding of the graph.
What is the probability that the complement has an infinite connected component?

Clearly, if all the diagonals point the same way, both the graph and its complement have an infinite component. How about a uniform random graph of the above kind?

The probability is 0.

This follows from the following theorem (see Theorem 5.33 in Grimmett's Probability on Graphs, http://www.statslab.cam.ac.uk/~grg/books/USpgs-rev3.pdf):

Theorem Consider bond percolation on $\mathbb Z^2$, where each edge between lattice points is open with probability $\frac12$. The probability that the origin is in an infinite connected component is 0.

We can reduce from our problem to this problem: basically it is just 2 disjoint (but dependent) copies of bond percolation on $\mathbb Z^2$. Consider the configuration $D_1$ where the edges form an infinite lattice of diamonds containing the origin. If we flip all edges, we get another infinite lattice of diamonds $D_2$. Consider the intersection of the actual configuration with $D_1$ and with $D_2$. Each of these is exactly the model of bond percolation on $\mathbb Z^2$, just rotated $45^{\circ}$. The probability that any point is in the infinite cluster is hence 0 (No edge in $D_1$ can be connected to an edge in $D_2$.).

To conclude, note that the sum of a countable number of events with probability 0 has probability 0; sum over the probability that any lattice point is in an infinite cluster.

(The existence of arbitrarily large components is a red herring. One should fix a point, and ask if it's in an unbounded component.)


Is semantic language complexity class UP Turing equivalent to syntactic language complexity class US? ${\sf UP}$ is defined in terms of unambiguous-SAT which asks if there exits at most one solution or no solution. On the other hand, ${\sf US}$ is defined in terms of unique-SAT which asks if there exists exactly one solution. I would like to know whether it is known that they are Turing equivalent, ${\sf P^{UP}}={\sf P^{US}}$. Any references would be appreciated.

[Since it's been a while and no one has added any further answers, I'm reposting my comment as an answer.]

${\sf US}$ contains ${\sf coNP}$, so ${\sf P^{US}}$ is at least as powerful as ${\sf P^{coNP}} = {\sf P^{NP}}$. The (mostly) common wisdom suggests that ${\sf P^{UP}}$ is strictly contained in ${\sf P^{NP}} \subseteq {\sf P^{US}}$.


Kolmogorov Complexity of an arbitrary string For an arbitrary string sampled from $\{0,1\}^n$, what would be the probability that the string has a Kolmogorov Complexity $\geq$ length of the string, $n$.

In other words, how many strings are there in the above set that satisfy the definition of random, as defined in Kolmogorov Complexity.

A string $x$ is $c$-compressible if $K(x) \leq |x| + c$. If $x$ is not compressible by $1$, $x$ is  said to be incompressible (or random, if you will).

There are $2^n$ bit strings of length $n$, and there are $\sum_{i=0}^{n-1} 2^i = 2^n-1$ descriptions that are of length less than $n$. Because each description describes at most one string, there is at least one incompressible bit string for each length $n$.

Also, at least $2^n-2^{n-c+1}+1$ strings of length $n$ are incompressible by $c$. Once again, at most $2^{n-c+1}-1$ strings of length $n$ are $c$-compressible, because we have at most that many descriptions of length at most $n-c$. Then the remaining $2^n-(2^{n-c+1}-1)$ strings are incompressible by $c$.


Sample graph dataset for testing algorithms I hope I'm addressing the right community. For a project for my students, I need to find some weighted graphs (oriented or not) to benchmark their algorithms (shortest paths, flows...).
There are a few samples on the companion site of the ALGS4 course from R. Sedgewick (Shortest Paths), but I would like some more datas, encoded in this simplest way (or easily convertible).
Maybe someone here is aware of some samples and could point me to it.
Thanks in advance.

The Stanford Large Network Dataset Collection appears to include a few weighted graphs. Unfortunately the road networks are apparently unweighted - I'm not sure if shortest-paths is motivated on any of the weighted graphs there.


Decidability in Extensional Type Theory What are the ways in which one can add a decidable equivalence relation in a type system with undecidable type checking/extensional equality?

Your question is very brief, so my answer will be as well:

Structure DecidableEquivalenceRelation :=
  {
    carrier :> Type ;
    rel :> carrier -> carrier -> Prop ;
    reflexive : forall x, rel x x ;
    symmetric : forall x y, rel x y -> rel y x ;
    transitive : forall x y z, rel x y -> rel y z -> rel x y ;
    decidable : forall x y, (rel x y) + ~ (rel x y)
  }.


Are there "small" machines which can efficiently match regular expressions? It's well-known that a regular expression can be recognized by a nondeterministic finite automaton of size proportional to the regular expression, or by a deterministic FA which is potentially exponentially larger. Furthermore, given a string $s$ and a regular expression $r$, the NFA can test membership in time proportional to $|s| \cdot |r|$, and the DFA can test membership in time proportional to $|s|$. The slowdown for the NFA arises from the fact that essentially we need to track the sets of possible states the automaton could be in, and the exponentially blowup for the DFA arises from the fact that its states are elements of the powerset of the states of the NFA.

Is it possible to efficiently (ie, in time better than $O(|r| \cdot |s|)$, and space better than $O(2^{|r|})$) recognize regular expressions, if we allow using more powerful machines than finite automata? (For example, are there succinctness gains to recognizing regular languages with pushdown automata, or counter machines?)

It's easy enough to trade off time for space, as follows.

Convert the regular expression to an NFA — for concreteness in comparing algorithms, we'll assume that $r$ is the number of NFA states, so that your $O(rs)$ time bound for directly simulating the NFA is valid and your $O(2^r)$ space bound for running the converted DFA are also valid whenever you're working in a RAM that can address that much memory.

Now, partition the states of the NFA (arbitrarily) into $k$ subsets $S_i$ of at most $\lceil r/k\rceil$ states each. Within each subset $S_i$, we can index subsets $A_i$ of $S_i$ by numbers from $0$ to $2^{\lceil r/k\rceil}-1$.

Build a table $T[i,j,c,A_i]$ where $i$ and $j$ are in the range from 0 to $k-1$, $c$ is an input symbol, and $A_i$ is (the numerical index of) a subset of $S_i$. The value stored in the table is (the numerical index of) a subset of $S_j$: a state $y$ is in $T[i,j,c,A_i]$ if and only if $y$ belongs to $S_j$ and there is a state in $A_i$ that transitions to $y$ on input symbol $c$.

To simulate the NFA, maintain $k$ indices, one for each $S_i$, specifying the subset $A_i$ of the states in $S_i$ that can be reached by some prefix of the input. For each input symbol $c$, use the tables to look up, for each pair $i,j$, the set of states in $S_j$ that can be reached from a state in $A_i$ by a transition on $c$, and then use a bitwise binary or operation on the numerical indices of these sets of states to combine them into a single subset of states of $S_j$. So, each step of the simulation takes time $O(k^2)$, and the total time for the simulation is $O(sk^2)$.

The space required is the space for all the tables, which is $O(k^2 2^{r/k})$. The time and space analysis is valid on any RAM that can address that much memory and that can do binary operations on words that are large enough to address that much memory.

The time-space tradeoff you get from this doesn't perfectly match the NFA simulation, because of the quadratic dependence on $k$. But then, I'm skeptical that $O(rs)$ is the right time bound for the NFA simulation: how do you simulate a single step of the NFA faster than looking at all of the (possibly quadratically many) transitions allowed from a currently active state to another state? Shouldn't it be $O(r^2 s)$?

In any case by letting $k$ vary you can get time bounds on a continuum between the DFA and NFA bounds, with less space than the DFA.


Examples of hardness phase transitions Suppose we have a problem parameterized by a real-valued parameter p which is "easy" to solve when $p=p_0$ and "hard" when $p=p_1$ for some values $p_0$, $p_1$.

One example is counting spin configurations on graphs. Counting weighted proper colorings, independent sets, Eulerian subgraphs correspond to partition functions of hardcore, Potts and Ising models respectively, which are easy to approximate for "high temperature" and hard for "low temperature". For simple MCMC, hardness phase transition corresponds to a point at which mixing time jumps from polynomial to exponential (Martineli,2006).

Another example is inference in probabilistic models. We "simplify" given model by taking $1-p$, $p$ combination of it with a "all variables are independent" model. For $p=1$ the problem is trivial, for $p=0$ it is intractable, and hardness threshold lies somewhere in between. For the most popular inference method, problem becomes hard when the method fails to converge, and the point when it happens corresponds to the phase transition (in a physical sense) of a certain Gibbs distribution (Tatikonda,2002).

What are other interesting examples of the hardness "jump" as some continuous parameter is varied?

Motivation: to see examples of another "dimension" of hardness besides graph type or logic type

I'm not exactly sure if this is the type of problem you were looking for, but the phase transition of NP-Complete problems is a (by now) well known phenomenon.  See Brian Hayes's articles "Can't Get No Satisfaction" about the 3-SAT phase transition and "The Easiest Hard Problem" about the Number Partition Phase transition, for some popular articles on the subject.

Selman and Kirkpatrick were first to show numerically that the phase transition for 3-SAT was when the ratio of clauses to variables was at around 4.3.

Gent and Walsh were first to show numerically that the phase transition for the Number Partition Problem happened when the ratio of bits to list length was about 1.  Later this was proved analytically by Borgs, Chayes and Pittel.

Travelling Salesman, Graph Coloring, Hamiltonian Cycle, amongst others, also appear to have phase transitions for a suitable parameterization of problem instance creation.  I think it's safe to say that it is a commonly held belief that all NP-Complete problems exhibit a phase transition for a suitable parameterization.


Feynman and the logarithm The following quote describes an algorithm invented by Feynman to compute the logarithm of a fractional number (presumably a dyadic one).

  Consider the problem of finding the logarithm of a fractional number between 1.0 and 2.0 (the algorithm can be generalized without too much difficulty). Feynman observed that any such number can be uniquely represented as a product of numbers of the form (1 + 2^{-k}), where k is an integer. Testing each of these factors in a binary number representation is simply a matter of a shift and a subtraction.

Unfortunately, there are many numbers that cannot be represented as advertised above, for example 7/4, 11/8.
There must be something wrong with the quote.

What was the algorithm proposed by Feynman ?

You can multiply $r$ by $(1+2^{-k})$ by adding $r$ to $r$ shifted right by $k$ positions. To find the factors of a number $s$, you can start setting $r:=1$ and for $k=0,1,2,\ldots$, test if $r(1+2^{-k})\leq s$. If the test succeeds, set $r:=r(1+2^{-k})$. Along the way you can calculate $\log s$ by summing $\log 1+2^{-k}$ for every factor found.


Looking for papers and articles on modal substructural logics I am looking for papers and articles on modal substructural logics-- not on the semantics of linear logic modalities, but on substructural logics augmented with standard modal operators, e.g. substructural K (something like MALL with box operator, necessitation and K rules).

I know of work adding temporal modalities to linear logic to produce what has been called temporal linear logic (in contrast to LTL = linear-time temporal logic). This is quite interesting: a formula (without a modality) is interpreted as resources being available now. The next time modality $\bigcirc-$ is interpreted as resources being available in the next time step. The box modality $\Box-$ means that the resources can be consumed at any point in the future,
determined by the holder of the resources, whereas $\lozenge-$ means that the resources can be consumed at any point in time determined by the system. Notice the duality between the holder of the resource and the system.

Banbara, M., Kang, K.-S., Hirai, T., Tamura, N.: Logic programming in a fragment of intuitionistic temporal linear logic. In: Codognet, P. (ed.) ICLP 2001. LNCS, vol. 2237, pp. 315–330. Springer, Heidelberg (2001)
Hirai, T.: Propositional temporal linear logic and its application to concurrent systems. EICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Special Section on Concurrent Systems Technology) E83- A(11), 2219–2227 (2000)
Hirai, T.: Temporal Linear Logic and Its Application. PhD thesis, The Graduate School of Science and Technology, Kobe University, Japan (September 2000).
Kamide, N.: Temporalizing Linear Logic Bulletin of the Section of Logic Volume 36:3/4 (2007), pp. 173–182

There are a few papers adding all sorts of modalities to linear and affine logic:

Kamide, N.: Linear and affine logics with temporal, spatial and epistemic logics. Theoretical Computer Science 252, 165–207 (2006).
Kamide, N: Combining Soft Linear Logic and Spatio-Temporal Operators. J Logic Computation (2004) 14 (5): 625-650.

The work on temporal linear logic has been applied in agent-oriented programming and coordination, making essential use of the interpretation of the modalities described above:

Kungas, P.: Temporal linear logic for symbolic agent negotiation. In: Zhang, C., W. Guesgen, H., Yeap, W.-K. (eds.) PRICAI 2004. LNCS, vol. 3157, pp. 23–32. Springer, Heidelberg (2004)
Pham, D.Q., Harland, J., Winikoff, M.: Modelling agent’s choices in temporal linear logic. In: Baldoni, M., Son, T.C., van Riemsdijk, M.B., Winikoff, M. (eds.) DALT 2007. LNCS, vol. 4897, pp. 140–157. Springer, Heidelberg (2008)
Clarke, D. Coordination: Reo, Nets and Logic.
FMCO proceedings, LNCS, vol.  5382. (2008)


First order expression for functional dependency I'm puzzled with functional dependency formula in first order logic. It is triggered by

http://rjlipton.wordpress.com/2010/01/17/a-limit-of-first-order-logic/

where there seems to be a confusion between dependency and functional dependency. The expression

$\displaystyle \forall x \exists y : S(x, y) .$

is anything but functional dependency. The formula for functional dependency is

$\displaystyle \forall y_{1} \forall y_{2} \forall x : S(x, y_{1}) \wedge S(x, y_{2}) \implies y_{1} = y_{2} .$

Now, suppose we have ternary predicate Q(x,y,z). How does one express functional dependency y=f(x)?

Apparently, we must project away variable z from ternary relation Q, which is done via existential quantifier:

∀y1∀y2∀x:(∃z:Q(x1,y,z))∧(∃z:Q(x2,y,z))⟹x1=x2.

This is equivalent to standard textbook FD definition:

∀y1∀y2∀x∀z1∀z2:Q(x1,y,z1)∧Q(x2,y,z2)⟹x1=x2.


Completeness spanning trees A spanning tree of a graph is called a completeness tree if the set of
its leaves induces a complete subgraph in the host graph. Given a graph $G$
and an integer $k$, what is the complexity of deciding if $G$ contains a
completeness tree with at most $k$ leaves?

A reason for asking this question is that the corresponding problem for
independency trees
is NP-complete, here an independency tree is a spanning tree such that the set of its
leaves is an independent set in the host graph.

Another reason is this question
(and the corresponding answers). It turns out that every spanning tree of $G$ is a completeness tree
if and only if $G$ is a complete graph or a cycle.

In a triangle-free graph, a completeness tree must be a Hamiltonian cycle (minus one of its edges). ISGCI says Hamiltonian cycle is NP-complete in triangle-free graphs. Therefore, so is finding a completeness tree (regardless of any restriction on max number of leaves).


Proof techniques for string algorithms? I'm currently reading through the tome "Algorithms on Strings, Trees, and Sequences" by Dan Gusfield, and I find the proofs to be extremely case analysis heavy and full of finicky +-1s. This seems very error prone to program.

I was hoping for a more "conceptual" way to build string algorithms, where we first construct a toolkit of basic objects that we then use. I was hoping that prefixes, suffixes, and the Z algorithm would be those. But they seem too level to construct something like Boyer-Moore or Aho-Corasick.

As an analogy for some kind of abstract algebraic flavoured approach, like using matroids for greedy algorithms to capture the "hard" part of the analysis.

So my question is, are there nice algebraic structures that govern string algorithms which can be used to present and implement them more elegantly?

There is some work on developing an algebraic or grammar-based view of string algorithms, for example

Robert Giegerich, Carsten Meyer, Peter Steffen:
A discipline of dynamic programming over sequence data. Sci. Comput. Program. 51(3): 215-263 (2004)

Robert Giegerich, Hélène Touzet:
Modeling Dynamic Programming Problems over Sequences and Trees with Inverse Coupled Rewrite Systems. Algorithms 7(1): 62-144 (2014)

These approaches deal with string problems that are solved by dynamic programming such as the computation of edit distance or local alignments or comparison of RNA secondary structures. These problems are more difficult in terms of the running time of the best algorithms than the exact pattern matching problem that is solved by Boyer-Moore.

A more conceptual or programmer-friendly approach for exact pattern matching would be to use the right data structures such as suffix arrays or suffix trees. Many pattern matching algorithms become simpler when these data structures are used as a black box or augmented in some relatively easy way.


Graph classes with a "jump property" Let us say that a graph class has the jump property, if it either contains all $n$-vertex graphs for every large enough $n$, or else the fraction of $n$-vertex graphs that belong to the class approaches 0, as $n\rightarrow\infty$.

The answers to an earlier question (see
here) show that every hereditary graph class has this jump property.

Question: What are some other (nontrivial) examples of graph classes with this  property?

Note: It would be good to see natural examples, that is, classes that arise from independent considerations, not created just for the sake of the jump property.

It's not quite the same, but you may be interested in the 0-1 law for first order properties of graphs. A first order property is something you can describe by a logical formula with existential and universal quantifiers, in which the variables refer to vertices of a graph and there are two two-argument predicates: equality, and another predicate $\sim$ that tests whether two vertices are adjacent. For example, whether there is a universal vertex adjacent to all other vertices can be tested by the first-order formula $\exists v\forall w\,v\ne w\rightarrow v\sim w$.

Then, for every first-order property, the fraction of all $n$-vertex graphs that satisfy the property, as $n\to\infty$, approaches either 0 or 1. More strongly, there exists an infinite graph, the Rado graph, such that this fraction approaches 0 or 1 exactly when the Rado graph does not or does have the same property, respectively. But when the fraction approaches 1, it still might not be the case that the property holds for all graphs, so this differs somewhat from what you're asking.


Quick Sampling from Probability Distribution: Is there a name for this algorithm? I'm trying to quickly sample from a near-uniform discrete probability distribution exactly once without calculating the entire CDF. Here's the algorithm.

Givens:

$N,$ the number of elements to sample from
$p : \{n \in \mathbb{N} | n < N\} \to \mathbb{R}[0,1],$ the probability distribution function
$M : \mathbb{R} = \max_{\forall n < N} p(n)$, the maximum probability

The algorithm is as follows (pseudocode):

define select(N, p, M):
    LET i := a random natural number < N
    WITH PROBABILITY p(i) / M:
        return i
    ELSE:
        return select(N, p, M)

The distribution that this algorithm selects is

$$\mathbf{q} = \frac{1}{N}\sum_{i=0}^N\left(\frac{p_i}{M}\mathbf{e_i} + \left(1-\frac{p_i}{M}\right)\mathbf q\right)$$

Solving for $\mathbf q$:

$$N\mathbf{q} = \frac{1}{M}\mathbf p + N\mathbf q - \frac{1}{M}\mathbf q$$

$$\mathbf p = \mathbf q$$

And the time complexity is

$$t = \frac{1}{n}\sum_{i=0}^n \left(\frac{p_i}{M} \cdot 1 + (1 + t)\left(1-\frac{p_i}{M}\right)\right)$$

$$Nt = \frac{1}{M} + N(1+t) - \frac{t+1}{M}$$

$$0 = N - \frac{t}{M}$$
$$t = MN$$

So for a near-uniform distribution, where $M = O(N^{-1})$ then the algorithm is $O(1)$.

My question is: is there a name for this algorithm?


Asking optimal questions to differentiate object in set I have a problem in mind and I am sure this is likely an area of active research, but am at a loss as to the correct terminology and thus unable to find any reference literature.  It is best explained by example:

Say I have several objects, for example mahogany chairs.  For each of these chairs I know a number of attributes about them such as their weight, texture, colour, age, etc.

If you contact me inquiring about one of my chairs and tell me some incomplete information, e.g. "dark brown, 60's era chair"  I want to decide optimally what further information (if any) do I require from you to identiy the chair of interest, i.e. what questions do I need to ask to obtain the required attribute information.  Additionally, in the likely case that there are many questions I will need to ask you, how can I optimise the questions I ask you.  Optimisation could mean minimising the expected number of quesitons I need to ask you, or asking questions I think you are most likely to be able to answer.

So I would appreciate some information or references for this kind of problem.  It's worth noting I am interested in implementing this computationally (hence posting here) as opposed to a purely abstract problem.

On the one hand, what you're asking sounds like binary search. On the other hand, the adaptivity makes it feel more like active learning: think of the "thing you're trying to learn" as a hypothesis and the "queries" as being labels of objects. Since this question is primarily about finding the right terminology, do look at the active learning literature and see if it captures the spirit of what you want.


Are there temporal logics linear time properties that only have counterexamples that are more complex than a lasso? Are there linear time temporal logics that can express some property $P_{nonlasso}$ that does have a counterexample, but none that is a lasso (or finite)?

Details:

One advantage of model checking over other formal methods is their ability to return a counterexample, a (finite path or a) path in form of a lasso. This is sufficient up to (extended) Büchi automata, since an infinite accepting path can be transformed to a lasso that infitely visits some accepting state.

But is this still the case for more complex linear time logics? Or a non-linear time logic that does have counterexamples, e.g. ACTL*? Can the $\mu$-calculus or MCRL2 express such a linear time property $P_{nonlasso}$?

For instance, having the Kripke structure $s_1 \leftrightarrow init \leftrightarrow s_2$, can I express the counting property "repeat $(init \rightarrow s_1 \rightarrow init)^i \cdot (init \rightarrow s_2 \rightarrow init)^i$ for infinitely increasing $i$"? This path does have a very simple schema...

Update: I am looking for linear time temporal logics without any relationship between multiple paths (see Makus's answer for other logics).

Pierre Wolper defined in 1983 extended temporal logic (ETL, in Information and Computation 56, 72–99, doi:10.1016/S0019-9958(83)80051-5), where a temporal operator $\mathcal A(\varphi_1,\dots,\varphi_n)$ can be introduced for a finite-state automaton $\mathcal A$.  The formula is satisfied in an infinite word $u$ at position $i$, i.e. $u,i\models\mathcal A(\varphi_1,\dots,\varphi_n)$, if there exists a finite word $a_{i_1}\cdots a_{i_n}$ in the language of the automaton $\mathcal A$, such that for every $1\leq j\leq n$, $u, i+(j-1)\models\varphi_{i_j}$.  Extended temporal logic has the same expressive power as the linear-time $\mu$-calculus or MSO on infinite words, so it does not answer your question.

One can however go further and allow other languages instead of regular ones in the operator $\mathcal A(\dots)$.  Paul Gastin and Stéphane Demri consider the case of context-free languages at the end of their chapter Specification and Verification using Temporal Logics of Modern applications of automata theory (IISc Research Monographs 2, chapter 15, pages 457–494, World Scientific, 2012, http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DG-iis09.pdf).  You can certainly express non-lasso properties in such a logic.  It is shown by Gastin and Demri to have (highly) undecidable satisfiability and model-checking problems.


Efficient and simple randomized algorithms where determinism is difficult I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most prominently

Randomized Quicksort (and related geometric algorithms, e.g. for convex hulls)
Randomized Mincut
Polynomial Identity Testing
Klee's Measure problem

Among these, only polynomial identity testing seems to be really hard without the use of randomness.

Do you know more examples of problems where a randomized solution is very elegant or very efficient, but deterministic solutions are not? Ideally, the problems should be easy to motivate for laymen (unlike e.g. polynomial identity testing).

Sorting nuts and bolts

The following problem was suggested by Rawlins in 1992:  Suppose you are given a collection of n nuts and n bolts.  Each bolt fits exactly one nut, and otherwise, the nuts and bolts have distinct sizes.  The sizes are too close to allow direct comparison between pairs of bolts or pairs of nuts.  However, you can compare any nut to any bolt by trying to screw them together; in constant time, you will discover whether the bolt is too large, too small, or just right for the nut.  Your task is to discover which bolt fits each nut, or equivalently, to sort the nuts and bolts by size.

A straightforward variant of randomized quicksort solves the problem in $O(n \log n)$ time with high probability.  Pick a random bolt; use it to partition the nuts; use the matching nut to partition the bolts; and recurse.  However, finding a deterministic algorithm that even runs in $o(n^2)$ is nontrivial.  Deterministic $O(n\log n)$-time algorithms were finally found in 1995 by Bradford and independently by Komlós, Ma, and Szemerédi.  Under the hood, both algorithms use variants of the AKS parallel sorting network, so the hidden constant in the $O(n\log n)$ time bound is quite large; the hidden constant for the randomized algorithm is 4.

Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Noar, and Rafail Ostrovsky. Matching nuts and bolts. Proc. 5th Ann. ACM-SIAM Symp. Discrete Algorithms, 690–696, 1994.
Noga Alon, Phillip G. Bradford, and Rudolf Fleischer. Matching nuts and bolts faster. Inform. Proc. Lett. 59(3):123–127, 1996.
Phillip G. Bradford. Matching nuts and bolts optimally. Tech. Rep. MPI-I-95-1-025, Max-Planck-Institut für Informatik, 1995. http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-025
Phillip G. Bradford and Rudolf Fleischer. Matching nuts and bolts faster.  Proc. 6th. Int. Symp. Algorithms Comput., 402–408, 1995. Lecture Notes Comput. Sci. 1004.
János Komlós, Yuan Ma, and Endre Szemerédi. Matching nuts and bolts in $O(n\log n)$ time. SIAM J. Discrete Math. 11(3):347–372, 1998.
Gregory J. E. Rawlins. Compared To What? : An Introduction to The Analysis of Algorithms. Computer Science Press/W. H. Freeman, 1992.


A partition problem in which some numbers may be cut In the standard partition problem, we are given some numbers whose sum is $2s$ and have to decide whether they can be partitioned into two subset whose sum is $s$. It is known to be NP-hard.

However, assume that we are allowed to designate one of the numbers to be a "soft number" that can be cut it into an arbitrary number of pieces, where different pieces may be put into different subsets.
Then the problem becomes easy: just arrange all numbers on a line in an arbitrary order, and cut the line into two sub-lines with the same sum.

  QUESTION: Suppose we are given some numbers whose sum is $3s$, and have to decide whether they can be partitioned into three subsets whose sum is $s$, while using at most one soft number. What is the complexity of this problem?

If we are allowed to use two soft numbers, then the problem is again easy - we can solve it by arranging the numbers on a line as above.
If we are allowed to use zero soft numbers, then the problem is obviously hard - it is at least as hard as the problem of partitioning into two subsets.
If we are allowed to use one soft number, my guess is that the problem should still be hard, and we can somehow reduce to it from the standard partition problem, but I could not find the right reduction. So, is it easy or hard?

Another question: in case the problem is indeed NP-hard, can it be solved in pseudo-polynomial time like the two-subset partition problem?

The largest number is the soft number

I claim that for any instance of your problem, if the instance is solvable (it is possible to partition the numbers using one soft number) then it is possible to solve the instance using the largest number as the sole soft number. This is easy to prove: any solution can be modified into a solution with the largest number as the soft number; simply place the number that is currently the soft number into the partition that contains the largest number and split the largest number among the parts of the partition instead.

Packing problem

Here is a problem that I will call the packing problem:

The input consists of a list of positive numbers $a_1, a_2, \ldots, a_k$ and one final number $\ell$ such that $\ell \ge a_i$ for all $i$. Define $s = \frac{1}{3}\left(\ell + \sum_{i = 1}^ka_i\right)$. Then the problem is to partition the list of $a_i$s into three parts such that each part has sum at most $s$.

I claim that the packing problem with inputs $a_1, \ldots, a_k$ and $\ell$ is equivalent to your problem with input list $a_1, \ldots, a_k, \ell$. If it's possible to pack the numbers $a_1, \ldots, a_k$ into three groups each of sum at most $s$ then you can use $\ell$ as a soft number to round out each of the sums to exactly $s$; thus you have a partition of $a_1, \ldots, a_k, \ell$ into three groups of sum $s$ using one soft number. If on the other hand $a_1, \ldots, a_k, \ell$ can be partitioned into three groups of sum $s$ using one soft number then the list can be partitioned into three groups of sum $s$ using $\ell$ as the soft number (by the result from the previous section). In this case the grouping of the $a_i$s into three parts satisfies the condition that each part has sum at most $s$.

The packing problem with no small numbers

Say that an instance of the packing problem "has no small numbers" if for every $i$, $a_i > \frac{\ell}{2}$. I claim that you can reduce the packing problem to the packing problem with no small numbers.

Suppose that in packing problem instance $(a_1, \ldots, a_k), \ell$ some $a_i$ has $a_i \le \frac{\ell}{2}$. WLOG suppose $a_k$ is this $a_i$. Then I claim the packing problem instance $(a_1, \ldots, a_{k-1}), \ell+a_k$ is equivalent to the original instance. Notice that the value $s$ remains the same in both instances.

Certainly if you can pack the numbers $a_1, \ldots, a_k$ into three groups with each group having sum at most $s$ then you can pack the numbers $a_1, \ldots, a_{k-1}$ into three groups with each group having sum at most $s$.

On the other hand, suppose you can pack the numbers $a_1, \ldots, a_{k-1}$ into three groups with each group having sum at most $s$. For each of the three groups, consider the value $s$ minus the sum of the elements in the group. Call these values $e_1, e_2, e_3$; here $e_i$ is the amount of "empty space" in group $i$. We know that $e_1 + e_2 + e_3$, the total empty space, is equal to $3s - \sum_{i = 1}^{k-1}a_i$ (total space $3s$ minus space used $\sum_{i = 1}^{k-1}a_i$). But $3s - \sum_{i = 1}^{k-1}a_i = a_k + \ell$ by the definition of $s$. Thus, the three groups have $a_k + \ell$ empty space in total. Then since $a_k < \frac{\ell}{2}$, we know that the total empty space is more than $3a_k$. By the pigeon hole principle, at least one of the groups has $a_k$ or more empty space in it. Thus, we can add element $a_k$ to one of the groups and end up with a packing of the numbers $a_1, \ldots, a_k$ into three groups with each group having sum at most $s$.

Thus, in order to solve your problem, it is sufficient to solve just the packing problem with no small numbers.

Lemma 1

Lemma statement:

Suppose we can partition $a_1, \ldots, a_k$ into groups 1 and 2 such that group 2 has an even number of elements and the sum of the elements in group 1 is in the interval $\left[s - \frac{\ell}{2}, s\right]$. Then it is possible to further partition group 2 into two subgroups 2a and 2b each of which has sum at most $s$. Notice that groups 1, 2a, and 2b are a solution of the packing problem instance.

Here's a proof.

Tentatively assign half of the elements of group 2 to subgroup 2a and the other half to subgroup 2b. Create a matching between the elements of the two subgroups. Swap these pairs between the two groups, one pair at a time. If there are $2n$ elements in group 2 then this process passes through exactly $n+1$ possible partitions of group 2 into subgroups 2a and 2b. I claim that at least one of those partitions has both subgroups with sum less than $s$.

Let $S_{2a}$ and $S_{2b}$ be the sums of the two subgroups (we allow these values to change as the groups change).

At each step of the above process, group 2a gains one element and loses another. Since each element has value between $\frac{\ell}{2}$ and $\ell$, we can conclude that at each step of the above process, $S_{2a}$ changes by at most $\frac{\ell}{2}$.

Also, the final value of $S_{2a}$ is equal to the initial value of $S_{2b}$ since by the end of the process the groups have entirely swapped.

Let $A$ be the average value of $S_{2a}$ and $S_{2b}$. Note that this is constant as the groups change. We know that the initial and final values of $S_{2a}$ average to $A$ (since the initial and final values of $S_{2a}$ equal the initial values of $S_{2a}$ and $S_{2b}$). Thus, $A$ must be between the initial and final values of $S_{2a}$. As we change the groups, the value of $S_{2a}$ takes steps of size at most $\frac{\ell}{2}$ from one side of $A$ to the other. From this, we can conclude that at some point, the value of $S_{2a}$ must be within half of the maximum step size ($\frac{\ell}{4}$) of $A$. Since $S_{2b}$ always has the same distance from $A$ as $S_{2a}$, we can conclude that at some point, both sums $S_{2a}$ and $S_{2b}$ are within $\frac{\ell}{4}$ of $A$.

$3s - \ell - (S_{2a} + S_{2b})$ is the sum of the elements of group 1; thus, $3s - \ell - (S_{2a} + S_{2b}) \ge s - \frac{\ell}{2}$ (by the condition on the sum of group 1). Rearranging, we have that $(S_{2a} + S_{2b}) \le 2s - \frac{\ell}{2}$. Therefore, the average of $S_{2a}$ and $S_{2b}$ is at most $s - \frac{\ell}{4}$. Then at the time that both $S_{2a}$ and $S_{2b}$ are within $\frac{\ell}{4}$ of $A$, we see that they are both at most $s$ as desired.

Case 1: $k = 3n$

Sum the $n$ smallest $a_i$s and also the $n$ largest $a_i$s.

If the $n$ smallest $a_i$s sum to more than $s$, then no group can have $n$ or more elements (as any choice of $n$ elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least $n$ elements. Thus, in this case there is no solution to the packing problem instance.

If the $n$ largest $a_i$s sum to at most $s$, then every choice of $n$ elements has a sum of at most $s$. In this case, simply partitioning the elements into three groups of equal size solves the packing problem instance.

The only remaining case is that the smallest $n$ elements sum to at most $s$ and the largest $n$ elements sum to more than $s$. As in the lemma, we can slowly transition between these two sets: start with a group initialized with the smallest $n$ elements and swap elements until the group has the largest $n$ elements. Each step moves the sum of the group by at most $\frac{\ell}{2}$ (by the same logic as in the proof of the lemma) and the sum crosses the value $s$ at some point in this process. Therefore, either immediately before or immediately after crossing the value $s$, the sum is less than $s$ but less by at most $\frac{\ell}{2}$. In other words, at some point in this process, the group has a sum in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

Case 2: $k = 3n+1$

Sum the $n+1$ smallest $a_i$s and also the $n+1$ largest $a_i$s.

If the $n+1$ smallest $a_i$s sum to more than $s$, then no group can have $n+1$ or more elements (as any choice of $n+1$ elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least $n+1$ elements. Thus, in this case there is no solution to the packing problem instance.

If the $n+1$ largest $a_i$s sum to at most $s$, then every choice of $n+1$ elements has a sum of at most $s$. In this case, simply partitioning the elements into three groups of size $n$, $n$, and $n+1$ solves the packing problem instance.

The only remaining case is that the smallest $n+1$ elements sum to at most $s$ and the largest $n+1$ elements sum to more than $s$. As in the previous case, we can slowly transition between these two sets: start with a group initialized with the smallest $n+1$ elements and swap elements until the group has the largest $n+1$ elements. Each step moves the sum of the group by at most $\frac{\ell}{2}$ (by the same logic as in the proof of the lemma) and the sum crosses the value $s$ at some point in this process. Therefore, either immediately before or immediately after crossing the value $s$, the sum is less than $s$ but less by at most $\frac{\ell}{2}$. In other words, at some point in this process, the group has a sum in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

Case 3: $k = 3n+2$ first easy subcase

Sum the $n$ smallest $a_i$s and the $n$ largest $a_i$s.

If either value is in the interval $[s-\frac{\ell}{2}, s]$, immediately apply the lemma with that choice of $n$ elements as group 1 and the remaining $2n+2$ elements as group 2. This allows us to find a solution to the packing problem instance.

If the $n$ smallest $a_i$s sum to less than $s-\frac{\ell}{2}$ and the $n$ largest $a_i$s sum to more than $s$ then we can start with the $n$ smallest $a_i$s and swap elements until we end up with the $n$ largest $a_i$s. At each step the sum moves at most $\frac{\ell}{2}$, so at some point in this process we have a group of $n$ elements whose sum is in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n+2$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

If the $n$ smallest $a_i$s sum to more than $s$, then no group can have $n$ or more elements (as any choice of $n$ elements will result in the sum being too large). But the pigeon hole principle tells us that at least one group has at least $n+1$ elements. Thus, in this case there is no solution to the packing problem instance.

The only remaining case is that both the $n$ smallest and $n$ largest $a_i$s add to less than $s-\frac{\ell}{2}$.

Case 3: $k = 3n+2$ second easy subcase

Sum the $n+2$ smallest $a_i$s and the $n+2$ largest $a_i$s.

If either value is in the interval $[s-\frac{\ell}{2}, s]$, immediately apply the lemma with that choice of $n+2$ elements as group 1 and the remaining $2n$ elements as group 2. This allows us to find a solution to the packing problem instance.

If the $n+2$ smallest $a_i$s sum to less than $s-\frac{\ell}{2}$ and the $n+2$ largest $a_i$s sum to more than $s$ then we can start with the $n+2$ smallest $a_i$s and swap elements until we end up with the $n+2$ largest $a_i$s. At each step the sum moves at most $\frac{\ell}{2}$, so at some point in this process we have a group of $n+2$ elements whose sum is in the interval $[s-\frac{\ell}{2}, s]$. Take that group as group 1 and the remaining $2n$ elements as group 2. The lemma applies, allowing us to find a solution to the packing problem instance.

If the $n+2$ largest $a_i$s sum to at most $s$, then every choice of $n+2$ elements has a sum of at most $s$. In this case, simply partitioning the elements into three groups of size $n$, $n+1$, and $n+1$ solves the packing problem instance.

The only remaining case is that both the $n+2$ smallest and $n+2$ largest $a_i$s add to more than $s$.

Case 3: $k = 3n+2$ hard subcase

Suppose neither of the above two subcases handled the instance. Then we know the following:

both the $n$ smallest and $n$ largest $a_i$s add to less than $s-\frac{\ell}{2}$.
both the $n+2$ smallest and $n+2$ largest $a_i$s add to more than $s$.

Since the $n+2$ smallest $a_i$s add to more than $s$, no group can have $n+2$ or more elements. The only way this is possible to accomplish is if the groups have sizes $n$, $n+1$, and $n+1$.

Note that since the $n$ largest $a_i$s add to less than $s-\frac{\ell}{2}$, it doesn't matter what elements are in the group of size $n$: that group will have sum less than $s$ anyway. Clearly, we can modify any solution by swapping the $n$ largest $a_i$s into the group of size $n$. These swaps only decrease the sums of the other two groups, so there exists a solution to the packing problem instance if and only if there exists a solution in which the $n$ largest $a_i$s form one of the groups.

Thus, the task at hand is simply this: is it possible to partition the $2n+2$ smallest $a_i$s into two groups of size $n+1$ such that each of those two groups has sum at most $s$. WLOG suppose that the $a_i$s are in increasing order so that the $2n+2$ smallest $a_i$s are $a_1, \ldots, a_{2n+2}$

Let $v$ be the average of the $n$ largest $a_i$s. Let $x_i = v - a_i$ for each $i$. Then $3s = \ell + \sum_{i = 1}^{3n+2}a_i = \ell + \sum_{i = 1}^{2n+2}a_i + \sum_{i = 2n+2}^{3n+2}a_i = \ell + \sum_{i = 1}^{2n+2}(v - x_i) + nv = \ell + (3n+2)v - \sum_{i = 1}^{2n+2}(x_i) = (\ell-v) + (3n+3)v - \sum_{i = 1}^{2n+2}(x_i)$.

Then $s = (n+1)v + \frac{\ell - v}{3} - \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i)$.

If we choose some set $I$ of $n+1$ indices, then the sum of the $a_i$s with $i \in I$ is equal to $\sum_{i\in I}a_i=\sum_{i\in I}v - x_i = (n+1)v-\sum_{i\in I}x_i$. A set of indices $I$ is a valid choice for one of the groups provided this sum is at most $s$. In other words, using the alternate definition of $s$ derived above, the condition we are interested in is $\sum_{i\in I}x_i \ge \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i) - \frac{\ell - v}{3}$. Obviously, the remaining $n+1$ indices $I' = \{1,\ldots, 2n+2\} \setminus I$ must also satisfy this condition: $\sum_{i\in I'}x_i \ge \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i) - \frac{\ell - v}{3}$. Since $\sum_{i\in I'}x_i = \sum_{i = 1}^{2n+2}x_i - \sum_{i\in I}x_i$, we can rewrite the second condition as $\sum_{i\in I}x_i \le \frac{2}{3}\sum_{i = 1}^{2n+2}(x_i) + \frac{\ell - v}{3}$.

Thus we have restated this subproblem using an equivalent alternative: we are trying to choose a set $I$ of $n+1$ indices among $\{1, \ldots, 2n+2\}$ such that $\frac{2}{3}\sum_{i = 1}^{2n+2}(x_i) + \frac{\ell - v}{3} \ge \sum_{i\in I}x_i \ge \frac{1}{3}\sum_{i = 1}^{2n+2}(x_i) - \frac{\ell - v}{3}$.

Note that $\ell \ge v$ (and therefore $\ell-v \ge 0$) since $v$ is the average of some $a_i$s and $\ell$ is an upper bound on all $a_i$s. Let $X = \sum_{i = 1}^{2n+2}(x_i)$. Our condition above can be rewritten as follows: choose a set $I$ of $n+1$ indices among $\{1, \ldots, 2n+2\}$ such that $\sum_{i\in I}x_i$ is in the interval $[cX, (1-c)X]$ where $c = \frac{1}{3} - \frac{\ell - v}{3X} \le \frac{1}{3}$.

Suppose that for some $j$, $x_j$ has value at least $\frac{X}{3}$. In this case, let $I$ consist of the index $j$ and also of the $n-1$ indices corresponding to the smallest $x_i$s. If these $x_i$s add to at most $(1-c)X$ then this choice of $I$ satisfies the above constraint: the sum $\sum_{i\in I}x_i$ is at least $x_j \ge \frac{X}{3} = \frac{1}{3}X \ge cX$ and at most $(1-c)X$. Thus, this set of indices $I$ can be used to select one of the groups of size $n+1$ in a solution to the packing problem instance. On the other hand, if these $x_i$s add to more than $(1-c)X$ then the instance cannot be solved: one of the two halves will include $x_j$ and the sum of that half is always going to be more than $(1-c)X$ (since it was more than that even when we put the smallest elements with $x_j$).

Thus, we have handled the case that some $x_j$ has value at least $\frac{X}{3}$. The remaining case is that every $x_i$ has value at most $\frac{X}{3}$. Then assign the $x_i$s to two groups, 1 and 2, arbitrarily. Create a matching of the elements of the two groups and swap those pairs one pair at a time. Over the course of this process, the sum of the elements of group 1 will move from it's initial sum to the initial sum of group 2's elements. In other words, the sum of group 1 will cross the average value $\frac{X}{2}$. Each step in this process involves group 1 losing an $x_i$ and gaining one; since the $x_i$s have value at most $\frac{X}{3}$, a pair of $x_i$s differs by at most $\frac{X}{3}$ and so each step moves the sum of group 1 by at most $\frac{X}{3}$. Thus, there will be some point in the process when the sum of group 1 is within half the maximum step size of the average. Thus, at some point the sum of group 1 will fall within $\frac{X}{2} \pm \frac{X}{6}$. But this is the interval $[\frac{1}{3}X, \frac{2}{3}X]$, which is a subinterval of $[cX, (1-c)X]$. Thus, at some point during this process, the group 1 at the time will satisfy our desired condition. We can use this group of $x_i$s to select a corresponding group of $a_i$s; these $a_i$s form one of the two groups of size $n+1$ needed to solve the packing problem instance.

Conclusion

The above exhaustive casework can be used as an algorithm to partition a list into three groups of the same sum using one soft number. The casework will also identify when this is impossible. The runtime of this algorithm is polynomial.


Is the 2016 implementation of Shor's algorithm really scalable? In the 2016 Science paper "Realization of a scalable Shor algorithm" [1], the authors factor 15 with only 5 qubits, which is fewer than the 8 qubits "required" according to Table 1 of [2] and Table 5 of [3]. The 8-qubit requirement comes from the end of [4] which states that the number of qubits needed for factoring an $n$-bit number is $1.5n+2$ which for 15 is $1.5\cdot 4 + 2=8$.

The paper that uses only 5 qubits states that their algorithm "replaces a QFT acting on M qubits with a semiclassical QFT acting repeatedly on a single qubit", but the consequences of this on the complexity of the  algorithm was never mentioned in the paper.

Now there has been harsh criticism of the paper claiming to factor 15 in a "scalable" way, as they say in Section 2 that the complexity argument for Shor's algorithm no longer holds. However, this criticism has not been corroborated anywhere, and the Science paper keeps getting celebrated as a "scalable" version of Shor's algorithm. What is the complexity of the "scalable" Shor algorithm?

[1] Monz et al. (2016) Science. Vol. 351, Issue 6277, pp. 1068-1070
[2] Smolin et al. (2013) Nature. 499, 163–165
[3] Dattani & Bryans (2014) arXiv:1411.6758
[4] Zalka (2008) arXiv:quant-ph/0601097
[5] Cao & Luo "Comment on: Realization of a scalable Shor algorithm"

The main thrust of Cao and Luo's argument is that in the variant of the algorithm that was implemented, the first register—that eventually contains the output—contains only 1 bit. And if you only get 1 bit of output from the algorithm, that's insufficient for factorization. (For one thing, although this isn't their argument, 1 bit clearly does not contain enough information to determine the factors.)

What Cao and Luo seem not to realize is that for the variation of the Fourier transform with only one bit in the first register, the same value of $c$ is output as in the standard factoring algorithm; it's just output one bit at a time.
This change doesn't affect the $O(\log^3 N)$ running time.

To try to be fair to Cao and Luo, they say that they don't think this algorithm works, and if it does work, then it isn't Shor's algorithm because it doesn't exactly match the algorithm described in the original factoring paper. A quote from their paper:

  Finally, we would like to stress that if the implementation is indeed credible then it would be a new quantum factoring algorithm, not the Shor algorithm, because all requirements of the original Shor’s algorithm are not satisfied.

And indeed, it's not the algorithm from my original factoring paper. It uses the phase estimation procedure from Kitaev's factoring algorithm, and a variant on that, discovered by Griffiths and Niu (not by Parker and Plenio, as I said in a previous edit of this answer) that lets the algorithm output the estimate of the phase one bit at a time.


What is the minimal class of subshifts for which conjugacy is known to be undecidable? The question of whether two finite one directional shifts are conjugates is known to be decidable.

The same question for sofic shifts is famously open.

I have seen that some works manage to prove undecidability of related problems for cellular automata. My question is what is the known undecidability landscape?

Do we know that it's undecidable if the shift corresponds to e.g., a context-free grammar? A one counter automaton? Something else?

To keep things focused, I am more interested in undecidability results that step from the underlying computational model, rather than an increased dimension.

I didn't bother writing the definitions, since I assume anyone not familiar with them will not likely be able to answer the question anyway...

Consider the class of subshifts defined by a forbidden context-free language. For this class, equality and non-conjugacy are recursively inseparable, i.e.

  Theorem. There is no algorithm that given two context-free languages, says "same" if they define the same subshift, and says "non-conjugate" if they are not conjugate.

Note that no requirement, even on halting, is made when they are distinct and conjugate.

Proof. Note that CFL are closed under unions and contain all regular languages, so we can forbid finitely many regular and CFL languages. We will forbid a bunch of things to force our configurations to simulate Turing machines.

Let $M$ be a Turing machine with state set $Q$ and alphabet $A$, suppose $Q \cap A = \emptyset$ and $\#, @ \notin A \cup Q$, and $0 \in A$. Let $q_0 \in Q$ be the initial state of $Q$ and $q_f$ the unique halting state.

We will construct two subshifts $X$ and $Y$ over the alphabet $Q \cup A \cup \{\#, @\}$ such that if $M$ reaches the halting state $q_f$ from the initial configuration $q_0 0^\omega$ then $X$ and $Y$ are not conjugate, and if $M$ does not, then $X = Y$ as sets.

I won't list the precise forbidden patterns since it's a lot of programming, but I'll explain what they accomplish. I'll say what needs to be true about subwords of a certain form, which you can turn into forbidden patterns by forbidding the complement of these conditions. First, with a regular set of forbidden patterns we force that $\#$ and $@$ alternate, and the word between any consecutive appearance of $\#$ and $@$ (in either order) is an element of $A^* Q A^*$ (so there's a Turing machine configuration between $\#$ and $@$).

Next, with a context-free set of forbidden patterns we force that in every pattern $u@v$ where $u, v \in (Q \cup A)^*$, we have $u = v^R$ where $v^R$ denotes reversal. We also force that in every word $\#u@va$ with $|u| = |v|$, $u, v \in (Q \cup A)^*$ and $a \in Q \cup A \cup \{\#, @\}$, we have $a = \#$, and the three symmetric conditions that together force that $\#$ and $@$ appear in a single arithmetic progression.

Next, the main trick. It's the one used in the standard proof of undecidability of whether two given context-free languages intersect: we require that in every word $@ v \# u @$, if $v$ does not contain $q_f$, then $u$ is the configuration that follows $v^R$ in the rule of $M$. If $v$ does contain $q_f$, then we require that $u^R$ is the unique word in $q_0 0^*$ of the correct length.

Finally, require that in every word $@ v \# w \# v^R @$ where $v \in (Q \cup A)^*$, the state $q_f$ appears somewhere in $w$. These patterns define the subshift $X$.

Let us analyze what kind of configurations appear in $X$. First, no matter whether $M$ halts on input $q_0 0^\omega$, in $X$ you have all configurations of the form $x @ y$ and $x \# y$ where $x$ and $y$ are over the alphabet $Q \cup A$, and all the limits of such configurations under the shift action, namely the full shift $(Q \cup A)^{\mathbb{Z}}$. Let $Y \subset X$ be this subset. It's a sofic subshift.

Suppose then that both $\#$ and $@$ appear in a configuration of $X$ (recall that they must alternate, so this happens unless the configuration is in $Y$), then the rules force that $@$ and $\#$ appear periodically in an arithmetic progression, and the configuration is of the form
$$ \ldots v_{-1} \# u_0 @ v_0 \# u_1 @ v_1 \# u_2 @ v_2 \# u_3 @ \ldots $$
with all the $|u_i|$ and $|v_i|$ of the same length, $u_i = v_i^R$ and the $M$-successor of $u_i$ is $u_{i+1}$. Since the lengths are the same, the computation must enter a loop starting from any $u_i$, i.e. $u_m = u_k$ for some $m < k$. The last rule then forces an appearance of $q_f$ somewhere between $u_m$ and $u_k$. But this means there is an occurrence of $q_0 0^n$ between them as well. Another application of this argument shows that the computation from $q_0 0^n$ reaches the halting state $q_f$.

We see that any configuration not in $Y$ is periodic, and must periodically repeat the accepting computation of $M$ on some $q_0 0^n$, where $n$ is any integer large enough that he computation has time to halt. (And if $M$ does halt on $q_0 0^n$, then periodically repeating the computation gives a valid configuration of $X$.)

In conclusion, if $M$ never halts on $q_0 0^\omega$, $X = Y$, and if $M$ does, then $X$ contains an isolated periodic point while $Y$ does not, so $X$ and $Y$ are not conjugate. So an algorithm with the properties listed in the statement would solve the halting problem, thus cannot exist. Square.

  Corollary: Equality and conjugacy of subshifts given by forbidden context-free languages are both undecidable problems.

Proof. Let's do conjugacy. If conjugacy were decidable by algorithm $A$, then it would give an algorithm $B$ that accomplishes what we claimed cannot be done: given $X$ and $Y$, if $A$ says they are conjugate, $B$ claims they are the same, and if $A$ says they are not conjugate, $B$ claims they are not conjugate as well. Now if $X = Y$, certainly $A$ says they are conjugate, so $B$ says they are the same. If $X$ and $Y$ are not conjugate, $A$ detects this, so $B$ also says they are not conjugate, contradicting the previous theorem. Square.

You can ask many follow-ups: can you make this topologically mixing (or some stronger gluing notion), can you use something weaker than CFL, and can you have the language be CFL rather than the forbidden patterns, etc. Have at it.


What is the formalism behind ?- (query) in Prolog? I am in general interested in a more formal (better be logical, as in related to mathematical logic) definition of a query.  As an example, there's Prolog operator ?- which takes as its argument a sentence in first order logic + meta-logical operators specific to Prolog and produces an "answer".

I'm interested to know what kind of logic deals with this (kind of) operator.

Prolog embodies the idea of computation as proof search. That is: a program is a formula which we would like to satisfy, the computation is the proof search, and the result is the witness for the formula.

To make this idea work we need to reformulate the rules of first-order logic so that they can be read as instructions for execution of a proof search. We may have to give up certain essentially non-computational parts of logic, such as excluded middle. We may further have to restrict the formulas that are allowed to appear, or else we will get something that looks like a general theorem prover insetad of a programming language.

I recommend chapter 8 of Frank Pfenning's notes on Computation and Deduction where these ideas are explained in detail.


Halting problem for finite tape TM If we have a primitive CPU/computer with small amount of registers and/or RAM, it is easy to check if the program will loop endlessly: just write down all registers/RAM cells states at each state and wait for repeating one.
If we reached repeating state, we got to know that the program will loop inifinitely and will never terminate.
We just need a CPU/computer with bigger RAM for the task.

If so, does it mean that halting problem exists only for TM with infinite tape/RAM, so it is not possible to write down all tape states?

"Easy to check" is the understatement of the century: can you actually carry out your proposed plan of "just" writing down all the registers/RAM cells, etc? You're right that it takes finite time, but a large amount of finite time. Our best algorithms for performing this check are exponential in the size of the input on the tape, and a strong version of the $P\neq NP$ conjecture states that there is no algorithm that achieves a faster (subexponential) runtime uniformly over all inputs.

So the P=NP problem is a finitary version of the halting problem. The latter has no algorithmic solution when input length is unbounded. The former admits a brute-force solution, but the amount of time required to find it is so large that for all practical purposes it's as good as unsolvable.

Edit: My statement that the halting problem can't be decided by any algorithm because the "input length is unbounded" is inaccurate, since for DFAs the latter also holds but the languages they accept are of course decidable. But certainly when the number of configurations is finite -- as is the case for a finite-tape TM -- a brute-force search solves the halting problem. Somewhat confusingly, the finiteness of the number of configurations is actually not necessary for decidability, as the DFA example shows.


Computing spanning trees with low crossing number using simplicial partitions I'm reading a paper that uses the following result:

  Let $S$ be a set of $n$ points in the plane. Then a spanning tree for $S$ with crossing number $O(\sqrt{n})$ can be computed in $O(n^{1+\epsilon})$ time for any $\epsilon > 0$.

The paper refers the reader to Matoušek's paper [1] for this result. However, Matoušek does not discuss spanning trees of points in [1], rather several methods for computing simplicial partition trees.

So I've been trying to track down where the result comes from. I finally found, in [2], the following statement:

  So-called simplicial partitions ([Mat91b], see Section 5) can be used to obtain a spanning tree with crossing number $O(\sqrt{n})$ in time $O(n^{1+\epsilon})$ for any $\epsilon > 0$ (where the constant in the crossing numbers depends on $\epsilon$), [Mat91a].

The reference [Mat91b] in the quote is my reference [1], and the reference [Mat91a] is a private communication between Wezl and Matoušek. It seems that this sentence from [2] is most likely why [1] is referenced in the paper I'm currently reading. I think this is a slight mistake, since [Mat91b] appears to be included as a reference for simplicial partitions, and [Mat91a] (the private communication) is the reference for the entire section and hence the claim. I must admit the first time I read this sentence I made the same mistake, but after searching in vain for the result in [1], have come to the conclusion above.

So my question is this: has the proof of this result appeared in the literature? Perhaps it is obvious (it is not yet obvious to me, but I am still learning about these algorithms). If it is not obvious, I am hoping someone can either provide me with a reference to where it has appeared, or a (rough?) explanation of how a simplicial partition of a point set can be used to construct a spanning tree of the point set with stabbing number $O(\sqrt{n})$ in $O(n^{1 + \epsilon})$ time (or any other $O(n^{1+\epsilon})$ time method, really)?

Thanks.

References

[1] Matoušek, J. Efficient Partition Trees. Discrete Comput. Geom., 8:315-334, 1992.

[2] Wezl, E. On spanning trees with low crossing numbers. Data Structures and Efficient Algorithms, LNCS 594:233-249, 1992.

If I get it correctly, the result you need appears in Section 4 of this paper (a draft here). We also needed to join pieces of different papers, as the comments here tell.


Sampling from the Voronoi cell of a point Fix a set of $n$ points $P \subset \mathbb{R}^d$. Now a query point
  $q$ arrives, and the goal is produce a point $r$ sampled uniformly
  at random from the Voronoi cell of $q$ in the set $P \cup \{q\}$.

For the purpose of this question, you can assume that $q$'s Voronoi cell is always bounded (for example $q$ always lies in the convex hull of $P$).

Is there anything known about this problem ?

Some constraints:

I might want more than one sample from $q$'s Voronoi cell. These should be IID.
I am allowed to preprocess the points, but I cannot spend time exponential in $d$.
The sample should be generated in time sublinear in $n$ and polynomial in $d$ ideally.

Note that the above rule out computing the Voronoi cell explicitly. Also note that while a rejection sampling approach would yield a uniform sample, it's not clear how to do it efficiently.

Too short for a comment... The following is intuitive bla bla, and feel free not buy it.

That seems extremely unlikely - assuming the points are uniformly distributed, the number of neighbours of the cell of $q$ is going to be $2^d$. Here is maybe a more formal argument. Pick a set of points on the unit hypersphere such that angle between any two points is at least, I dont know, 80 degrees. We know, that one can pick an exponential number of such points on the sphere without too much effort if the dimension is sufficiently large. Now, intuitively, for any subset of half the points, the Voronoi cell of the center of the sphere should have almost double the volume when compared to the cell volume with all the points. This inituitively implies you have to inspect all the points to get a good volume estimate. Which seems to imply, again intuitively, that sampling uniformly is going to be impossible, since the problems seems to be polynomially equivalent...


Image processing algorithms Is there any place, where description of formalized image processing algorithms can be found? Like creating hdr images, bluring images, etc.

I know of two semi-related trends that may be of interest (so this would be an extra answer to your question, but not the answer).

First, some progress has been made recently on the problem known as "Affine Image Matching", given two images A and B, how much an affine transformation can make A look like B (see 10.1007/978-3-642-13509-5_2 which proves that Affine Image Matching is uniform-TC0 complete).

Second, there has been studies of image transformations in the context of weighted automata.  A weighted automaton, which weights a word by an element of a semiring, describes fractal like images (intuitively, because of the loops of the automaton).  Nonetheless, actual algorithms have been invented to compress real-world pictures in weighted automata; a rational (weighted) transduction on such representations is then an image transformation.  See Chapter 11 of the Hanbook of Weighted Automata or the older Chapter 10, Volume 3 of the Hanbook of Formal Languages.


Is there a systematic method for constructing lambda calculus terms that can distinguish between inputs? For example, finding terms $\vec{a}$ such that:

$\vec{a}(\lambda x.x) = T\\\vec{a}(\lambda xy.x) = F$

Is there a systematic method for finding terms with these types of constraint?

The Böhm-out technique can construct term contexts that can distinguish between terms iff they are distinct in the beta-eta theory (i.e., a term context $C[-]$ so that $C[s]=T$ and $C[t]=F$). See, e.g., http://www.di.unito.it/~dezani/papers/dgp.pdf - it is exceedingly systemtic.

If the terms are closed, as in your example, the context you construct using the Böhm-out technique will be a term M that you apply to the two terms (so $M s = T$, $M t=F$).  Otherwise the term context will include capturing substitutions so that it can work at the sites of the free variables.


Agnostic query learning for DFAs Angluin's membership+equivalence query algorithm allows to efficiently and exactly learn a target $n$-state DFA. But what if the target DFA is huge, or the target concept is not even a regular language -- can we still learn a small DFA that approximates the target concept well?

Here's the formal setting. We have a target concept $f^\star$ and distribution $D$ over $\Sigma^*$. A membership query $MQ:\Sigma^*\to\{0,1\}$ returns the value of $f^\star(x)$. An "accuracy query" $AQ$ takes a DFA $f$ as input and returns
$$\mathrm{err}(f):=\sum_{x\in\Sigma^*}D(x)\boldsymbol{1}[f(x)\neq f^\star(x)]$$ a output.

The goal is to efficiently produce a small (up to $n$-states) DFA $f$ with small (or minimum) $\mathrm{err}(f)$ using the oracles $MQ$ and $AQ$. [A trivial solution is to brute-force search over all $n$-state DFAs.]

Have similar problems been considered in the literature? Pointers much appreciated. What is the status of the learning problem I posed?

Edit: It was pointed out off-line that for parity-type concepts, $\mathrm{err}(f)$ might be close to $1/2$. So to clarify:
the question seeks not a bound on the worst-case $\mathrm{err}(f)$,
but rather an efficient procedure of attaining it via an $n$-state DFA.

As mentioned in the comments, if you allow some extra additive slack of $\varepsilon\in(0,1]$ (an input parameter) in the error guarantee, and relax the success probability from one to $1-\delta$ (another input parameter), then the question becomes equivalent to agnostic PAC-learning the class $\mathcal{C}_n$ of $n$-state DFAs with membership queries.

Indeed, while you do not have accuracy queries $\mathrm{AQ}$, those can be easily simulated by sampling in the PAC setting (leading to the $\pm\varepsilon$ and $1-\delta$ relaxation).

However, this paper by Vitaly Feldman [Feldman09] shows that then, one may as well forget about the membership queries and focus on honest-to-goodness agnostic PAC learning:

  [...] we give a simple proof that any concept class learnable agnostically by a distribution-independent algorithm with access to membership queries is also learnable agnostically without membership queries.

In this light, provided you are willing to proceed with the error slack and high-probability guarantee, then your question boils down to agnostic PAC learning of $n$-state DFAs.

[Feldman09] Vitaly Feldman. On The Power of Membership Queries in Agnostic Learning. Journal of Machine Learning Research (JMLR) 10(Feb):163--182, 2009.


Node-weighted steiner problem with few terminals Consider the node-weighted steiner problem:

Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$.
Output: a minimum weight subset $S \subseteq V\setminus T$ of vertices such that $G[T\cup S]$ is connected.

Is this problem polytime solvable when the number $|T|$ of terminals is a constant?

An algorithm with a run-time of $n^{poly(k)}$ should be easy where $n = |V|$ and $k = |T|$. Think of an optimum solution which is edge-minimal. It will be a tree and one can see that the number of nodes with degree $\ge 3$ in this tree will be $O(k)$. We can guess those nodes $A$. Once we guess those nodes we create a graph on $A \cup T$ with edge-lengths between two nodes $u,v$ equal to the shortest node-weighted path between $u$ and $v$ in $G$ (we do not include the end points in this calculation). Then find a min-cost spanning tree in the resulting graph.


Efficient logspace algorithms It is easy to see that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). Many known logspace algorithms (For example : undirected st-connectivity, planar graph isomorphism) run in $O(n^k)$ where $k$ is insanely large.

I am looking for examples of natural problems that are known to be solvable simultaneously in deterministic logspace and $O(n^k)$ time where $k \leq 10$. There is nothing special about 10. Looking at the currently known logspace algorithms, I think $k \leq 10$ is interesting enough.
Aleliunas et al. showed that undirected st-connectivity is in $RL$ (randomized logspace). The running time of their algorithm is $O(n^3)$. Are there natural problems that can be solved simultaneously in $RL$ and linear time (or) near linear time i. e., $O(n{\log}^i{n})$ time ?

Edit : To make things more interesting let's look at problems that are at least $NC^1$-hard.

I guess Single-source Single-sink Planar DAG (SSPD) reachability has logspace algorithm with a modest running time ($O(n^2)$?). I am not so sure about
Single-source Multiple-sink Planar DAG Reachability (SMPD) algorithm.

Ref: Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Planar and Grid Graph Reachability Problems. Theory Comput. Syst. 45(4): 675-723 (2009)

Also, a new logspace algorithm for planarity testing and embedding runs in modestly polynomial time (modulo undirected reachability, of course)

Ref: Samir Datta, Gautam Prakriya: Planarity Testing Revisited CoRR abs/1101.2637: (2011)

Finally, here is a simple toy problem which has a logspace algo with a modest
running time (modulo undirected reachability) viz. Outerplanar Isomorphism.


Is the complement of { www | … } context-free? It is well-known that the complement of $\{ ww \mid w\in \Sigma^*\}$ is context-free. But what about the complement of $\{ www \mid w\in \Sigma^*\}$?

Still CFL I believe, with an adaptation of the classical proof.  Here's a sketch.

Consider $L = \{xyz : |x|=|y|=|z| \land (x \neq y \lor y \neq z)\}$, which is the complement of $\{www\}$, with the words of length not $0$ mod $3$ removed.

Let $L' = \{uv : |u| \equiv_3 |v| \equiv_3 0 \land u_{2|u|/3} \neq v_{|v|/3}\}$.  Clearly, $L'$ is CFL, since you can guess a position $p$ and consider that $u$ ends $p/2$ after that.  We show that $L = L'$.

$L \subseteq L'$: Let $w = xyz \in L$.  Assume there's a $p$ such that $x_p \neq y_p$.  Then write $u$ for the $3p/2$ first characters of $w$, and $v$ for the rest.  Naturally, $u_{2|u|/3} = x_p$.  Now what is $v_{|v|/3}$?  First:

$$|v|/3 = (|w| - 3p/2)/3 = |w|/3 - p/2.$$

Hence, in $w$, this is position:
$$|u|+|v|/3 = 3p/2 + |w|/3 - p/2 = |w|/3 + p,$$
or, in other words, position $p$ in $y$.  This shows that  $u_{2|u|/3} = x_p \neq y_p = v_{|v|/3}$.

If $y_p \neq z_p$, then let $u$ be the first ${3\over2}(|w|/3 + p)$ characters of $w$, so that $u_{2|u|/3}$ is $y_p$; $v$ is the rest of $w$. Then:
$$|u| + |v|/3 = 2|w|/3 + p$$
hence similarly, $v_{|v|/3} = z_p$.

$L' \subseteq L$: We reverse the previous process.  Let $w = uv \in L'$. Write $p = 2|u|/3$. Then:
$$p+|w|/3 = 2|u|/3+|uv|/3 = |u| + |v|/3.$$
Thus $w_p = u_{2|u|/3} \neq v_{|v|/3} = w_{p + |w|/3}$, and $w \in L$ (since if $w$ is of the form $xxx$, it must hold that $w_p = w_{p+|w|/3}$ for all $p$).


Graph Theory Fun Problem Show that in any graph $G$ with min-degree $k$ ($k \geq 1$ duh!) you can find as its subgraph any tree on $k+1$ vertices.

I have not been able to solve the question so far. However, I would like if someone can invoke the probabilistic method to prove the above statement (as in if someone can show that the probability of not finding some tree on $k+1$ vertices as some subgraph of $G$ is less than $1$. My earlier efforts aimed at trying to show that we can somehow show that this graph contains $K_{k+1}$ which was obviously false. Next, I tried showing that a sequence of edge contractions can give a $K_{k+1}$. Though I have not shown it so far, I was wondering what good that result might have been. So far, sadly, I have gotten nowhere :(

Sorry, if the question is too dumb.
)

Let $G$ be the host graph and $T$ the tree. Try "growing" $T$ in $G$. At each step, mark in $G$ the subtree $T'$ of $T$ that has been grown so far. Using the bounds on $\delta(G)$ and $\vert V(T)\vert$, argue that we can always expand the marked subgraph if it is not yet isomorphic to $T$.

Oh, but you wanted the Probabilistic Method. Here we go: Toss a coin $k$ times, throw out the results, and then do the above (old joke).


Using SAT for Computer Vision tasks Could anyone please point to both introductory and advanced papers/books showing how to use SAT technology to solve Computer Vision tasks (e.g. edge detection, object recognition, facial recognition, ...)?

More precisely: I'm looking for SAT-based techniques to extract knowledge from images and reason about such knowledge (e.g. is object $X_1$ in front of object $X_2$? Is object $X_3$ partially hidden by object $X_4$? Is person $X_5$ in image $I_1$ the same as person $X_6$ in image $I_2$?).

Many problems in computer vision are naturally expressed as constraint satisfaction problems.  There is a history going back several decades of applying constraint programming to such problems.  One of the key early papers in constraint satisfaction was completely motivated by problems from computer vision.

Ugo Montanari, Networks of constraints: Fundamental properties and applications to picture processing, Information Sciences 7 95–132, 1974. doi: 10.1016/0020-0255(74)90008-5

See this book for a recent overview of the application of constraints to particular problems in computer vision.

Martin Cooper, Line Drawing Interpretation. Springer-Verlag, 2008. (publisher's site)

If you really do want SAT and would like to avoid constraint satisfaction, then you can translate the constraint formulation into SAT, either manually or using an automated translation tool like Sugar.  Note that Chapter 2 of the recent Handbook of Satisfiability claims that it is common to first express one's problem as a constraint satisfaction problem, and only then to translate this formulation to SAT.  So constraint satisfaction should probably be considered even when one wants to work with SAT.

There is one big advantage of staying within a more expressive paradigm.  The constraint satisfaction framework allows the use of interval and numeric constraints.  These often occur in computer vision, but can lead to SAT instances that are infeasibly large.  Specialised constraint solvers may be greatly preferable to SAT solvers in such cases.

(A final aside: I have heard that the computer vision community tends not to be aware of constraint satisfaction approaches, and that this has led to the reinvention of well-known constraints techniques and results.  I do not know if this is a correct assessment, but if it is, then it would be worth translating constraints results to the terminology and specific concerns of computer vision.)


Commonest Subsequence A string has $2^n$ subsequences, but they are usually not all distinct. What is the complexity of finding the maximum frequency of any subsequence?

For example, the string "subsequence" contains 7 copies of the subsequence "sue" and this is the maximum.

Sample brute-force code at http://ideone.com/UIp3t

Are there related structural theorems? Both of these turn out to be false:

the longest of the maximum-frequency subsequences is unique
the maximum frequency of any length-$k$ subsequence is unimodal in $k$

Possibly related links:

Counting # distinct subsequences $\in \mathbf{P}$ http://11011110.livejournal.com/254164.html
Related contest problem for multiple sources http://www.spoj.pl/problems/CSUBSEQS/
Related paper http://dx.doi.org/10.1016/j.tcs.2008.08.035

Edit 10 days later: thanks for taking a look! I had wondered if this would make a nice polynomial-time solvable programming contest problem. I guess not, but I hope to think about it again later.

from a search, here is a paper with some research & findings for graduate level research but (caveat) no references. it has some heuristics, estimates, empirical results & commentary on the problem and some ideas on proving its (approximation) complexity etc.

Identification of Most Frequent Subsequences
CSE 549 Computational Biology Project Final Report
Mikhail Bautin 2006

(while there are some standard subsequence problems that are somewhat similar & studied eg in the Elzinga et al paper, is it possible this particular subsequence problem has not been studied too much?)


Regular Graphs and Isomorphism I would like to ask whether there is an already published result on that:

We take all possible different paths between each pair of nodes of two connected regular (with degree $d$ let's say, and number of nodes $n$) graphs and write down their lengths. Of course this number of distinct paths is exponential. My  question is, if we sort the lengths and compare them (the lists obtained by the two graphs) and they are exactly the same, can we say that the two graphs are isomorphic?

Of course, even if this is a result we cannot use it to reply for Graph Isomorphism, since the number of distinct paths is exponential, as said

By distinct paths, I refer to paths having at least one different node, obviously.

Thanks in priori for your help.

I believe the answer to your question is "no" because an equivalent condition would imply a polynomial time solution to GI.

For $A$, the adjacency matrix of the graph $G$, note that the number of paths from $i$ to $j$ of length $k$ is $(A^k)_{i, j}$ (with repetition of vertices and edges allowed).  For two graphs $G_1$ and $G_2$ (with adjacency matrices $A_1$ and $A_2$) and $k \ge 1$, if you sorted the elements of $A_1^k$ and $A_2^k$ then in order for $G_1$ to be isomorphic to $G_2$, it is a necessary condition that the lists be identical for all $k$.

I believe your conjecture is equivalent to:

If the sorted lists of elements of $A_1^k$ and $A_2^d$ are identical for $k = 1$ to $n - 1$ (upperbound on the longest path with non-repeating vertices) then $G_1$ and $G_2$ are isomorphic.

So to solve GI, one only has to perform $n - 1$ multiplications of $n \times n$ matrices (and a little extra time to sort and compare $n^2$ elements).  This would take less than $n^4$ time.

I admit two possible flaws in my argument.  First, it is totally possible that GI has a polynomial time algorithm and that we just discovered it together, just now (hooray, we're famous!).  I find this highly unlikely.  Second (and much more probable), what I've proposed is not actually equivalent to your conjecture.

Final thought.  Have you tried this out for all, say, 3-regular graphs for size 8 or so?  I would think that if your conjecture is false, that there should be a counter example in 3-regular graphs of fairly small size.


Monomorphic vs Polymorphic type theory I am currently reading the book Programming in Martin-Löf type theory by Nordström et al. In the book they have two important parts, one about monomorphic set theory and the other about polymorphic set theory. Why do they do this? What are important differences. As far as I understand from the book monomorphic version reduces to polymorphic but not vice versa. Why is this so?

As far as I understand it, the notion of polymorphic set denotes sets which are primitive, in other words which are first-order objects that can be manipulated, and such that set membership is a predicate, elements can be members of multiple sets. In monomorphic sets, sets are interpreted as predicates on types, and membership of a type is a jugement. In particular, a term can only be a member of a single set (up to equality of types).

While polymorphic sets are the more traditional view, there is an argument that the way mathematicians actually reason is mostly monomorphic e.g. $\mathbb{R}\in 2$ is not a proposition that should make sense. These notes by Martin Löf may clarify matters a bit.


What is the point of calling $\lambda$-calculus an algebra? What is the difference of calling $\lambda$-calculus an algebra instead of a calculus? I raise this question because I read somewhere the line "$\lambda$-calculus is not a calculus but an algebra" (iirc, attributed to Dana Scott). What is the point? Thanks.

A calculus is a system of computation based on the manipulation of symbolic expressions. An algebra is a system of symbolic expressions and relations between them[*]. That is, a calculus is a system for figuring out answers, and an algebra is a way of expressing the relations between terms.

The $\lambda$-calculus is either a calculus or an algebra, depending on whether you want to think of the $\beta$ and $\eta$ rules as oriented reduction rules or unoriented equations. If you think of the rules as being oriented, then you have fixed an evaluation order, and the rules tell you how to take a term and produce a normal form. If you think of the rules as being unoriented, then they give you the equality relation on $\lambda$-terms.

[*] There is also a categorical definition of algebra, which is a formal definition somewhat more restrictive than the informal idea. Loosely speaking, the difference is that the formal definition of algebra encompasses just those systems without variable binding. So SKI combinators form an algebra, but the $\lambda$-calculus doesn't.


Sample Complexity for Order Statistics I have a sample complexity question which seems fairly basic, but for which I'm having trouble finding a reference.

Let $F$ be an unknown distribution over $[0,1]$. Denote by $X_{k:n}$ the $k$th of $n$ order statistic of $F$. That is, $X_{k:n}$ is a random variable distributed according to the $k$th highest of $n$ IID draws from $F$. Let $\mu_{k:n}=E[X_{k:n}]$ denote the mean of $X_{k:n}$.

For an arbitrary $k$ and $n$, I am interested in the number of samples required to estimate $\mu_{k:n}$. In other words, I'm interested in estimators that take $m$ (distinct from $k$ and $n$, probably much larger) IID samples from $F$ and output an estimator $\hat \mu_{k:n}$ that is as close to $\mu_{k:n}$ as possible. I would be happy with either a guarantee in terms of mean absolute deviation (i.e. minimizing $E[|\hat \mu_{k:n}-\mu_{k:n}|]$) or a PAC-style guarantee that $\text{Pr}[|\hat \mu_{k:n}-\mu_{k:n}|\geq \epsilon]\leq \delta$.

One naïve approach would be to divide your $m$ samples into $m/n$ blocks of $n$ samples, and average the $k$th sample from each block. The performance of this estimator could be analyzed fairly easily using Chernoff bounds. I'm wondering if there's something smarter one can do. Lower bounds would also be of interest.

One way to approach this problem is via the CDF transformation. Consider $Z=F(X)$. We know $Z$ is uniformly distributed in $[0,1]$. Let $Z_{(1)},...,Z_{(m)}$ be the order statistics of these $m$ samples (after transforming to Z).

It can be shown that $Z_{(t)}\sim \text{Beta}(t,m+1-t)$. Using this, $Z_{(m\cdot k/n)}=F(X_{(m\cdot k/n)})$ is a consistent estimator for $F(\mu_{k:n})$.

As to the rates, since the exact distribution of $Z_{(t)}$ is known, it can be shown that ${E}[|F(X_{(m\cdot k/n)})-F(\mu_{k:n})|]\approx \sqrt{\frac{2}{\pi}}\sqrt{\frac{\min\{k/n,1-k/n\}}{m}}$. Now if you have some kind of constraint on $F$, say $F$ is Lipschitz with constant $c$, ${E}[|X_{(m\cdot k/n)}-\mu_{k:n}|]\le \frac{1}{c}\cdot {E}[|F(X_{(m\cdot k/n)})-F(\mu_{k:n})|]\approx \frac{1}{c}\sqrt{\frac{2}{\pi}}\sqrt{\frac{\min\{k/n,1-k/n\}}{m}}$. Therefore $X_{(m\cdot k/n)}$ is a reasonable estimator for $\mu_{k:n}$.

On the other hand, if there is no constraint on $F$ whatsoever, there is no way one can estimate $\mu_{k:n}$ consistently even with $m\rightarrow \infty$.


Combining (block)-sensitivity and Lipschitz conditions? If we're given a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, we can define its sensitivity as follows. The sensitivity $s(f, w)$ with respect to input $w$ is the number of ways of flipping a single bit of $w$ and changing the value of $f$. The sensitivity of $f, s(f)$ is then the maximum sensitivity with respect to any $w \in \{0,1\}^n$.

If on the other hand we're given a real-valued function $f : \mathbb{R}^n \rightarrow \mathbb{R}$, we can talk about its Lipschitz constants: specifically, the maximum value (wrt $x,\epsilon$) of the ratio $\frac{|f(x+\epsilon) - f(x)|}{\epsilon}$ as a kind of "smooth sensitivity".

What if we combine the two ? Suppose we have a function that takes parameters in a continuous domain, but whose output is discrete (one example might be a binary classifier, where the function is the sign of an appropriate hyperplane evaluation for example). Is there a natural notion that captures sensitivity in such a setting ? Boolean sensitivity doesn't work itself because you have to choose how much to perturb the inputs. Smooth perturbations don't quite work because the function is not continuous, and so any ratio would be rather unstable.

I suspect that either such a notion is very well known, or follows directly from the above, and so I'd be grateful for suggestions to reformulate the question/make it more precise.

One possible definition for a given point and ϵ would be the following: perturb each coordinate of the input independently with a Gaussian with mean 0 and variance $\epsilon^2/n$ and then look at the variance of the function's value with respect to this input distribution. It's also possible to perturb a specific coordinate this way and keep the rest fixed, depending on your application.

You may also find this paper of interest: "Noise stability of functions with low influences: invariance and optimality" by E. Mossel, R. O'Donnell, K. Oleszkiewicz.


Is finding whether k different perfect matchings exist in a bipartite graph co-NP? Few definitions first. The co-NP problem is a decision problem where the answer "NO" can be verified in polynomial time. The perfect matching in a bipartite graph is a set of pairs of nodes (a pair is an edge in the graph) and where every node occurs in this set exactly once.

I am given an n x n bipartite graph, and I am trying to find out if the problem of finding whether k different perfect matchings exist in the graph, where k= polynomial(n), is a co-NP problem.

Work done so far

To initially simplify the problem, I believe that if k=2, then this is a co-NP problem. I think this is true, because the bipartite graph does not have 2 different perfect matchings, if there does not exist an exchange of neighbors between 2 nodes. I define the exchange of neighbors as the following. Let G1 be the first set in the graph, and G2 be the second set in the graph. The exchange occurs when we have a subset of G1, S1={A,B}, and a second subset of G2, S2={X,Y}, where {(A,X),(A,Y),(B,X),(B,Y)} belongs to the set of edges E. I call it exchange because if A was initially matched with X, and B with Y, then when A gets paired with Y, and B with X, A and B have exchanged their neighbors. I believe that the only way to have 2 different perfect matchings is to have at least one such exchange.

Now, we can verify that no such exchange exist, in polynomial time. This is true since getting all the possible subsets S1 and S2 has O(n^4) time complexity. This because we need (n choose 2) from G1 multiplied by (n choose 2) from G2, and this gives us an upper bound of n^4.

Yes, cause the problem lies in P. Look at paper Fukuda, Matsui ''Finding All The Perfect Matchings in Bipartite Graphs''


Efficient generation of permutational invariant quantum states Starting from $|00\cdots 0\rangle$, can permutational invariant quantum states, i.e. the following one:
$$
|\psi_n\rangle = \frac1{n!} \sum \prod_{\pi\in S_n} |\pi(0)\rangle|\pi(1)\rangle\cdots|\pi(n-1)\rangle,
$$
where $\pi$ runs over all permutations of the symmetric group $S_n$, e.g.
$$
|\psi_3\rangle = \frac16\left(|012\rangle+|021\rangle+|201\rangle+|210\rangle+|201\rangle+|210\rangle\right)
$$
be generated efficiently, i.e. in polynomial time? If so, how?

Choose $n$ to a power of $2$ if you need...

Yes, they can. Recall that any reversible classical function can be computed in superposition. Now, generate the state
$$
\frac{1}{\sqrt{n!}}\left(\sum_{i=1}^n |i \rangle \right) \left( \sum_{i=1}^{n-1} |i \rangle \right)\left(\sum_{i=1}^{n-2} |i\rangle \right) \ldots \left(\sum_{i=1}^2 |i\rangle \right) \bigg(| 1\rangle \bigg) . $$
This is the superposition of all sequences where the $i$'th position contains a number between 1 and $n+1-i$. It's easy to generate because it's a tensor product of $n$ registers.

Then, find a reversible classical mapping from these sequences to permutations. One way of doing this is as follows. If there is an $i$ in the $t$'th position, take the $i$'th unused number available for the permutation. For example: suppose we have the sequence 24211. This gets mapped to the permutation as follows:

$$\begin{array}{r|l}
24211 & \ \ \ \emptyset \\
4211 & 2 \\
211 & 25 \\
11 & 253 \\
1 & 2531 \\
\emptyset \ \ \  & 25314
\end{array}
$$
To illustrate, the third element of the permutation is $3$ because at the third step, the available numbers are $1$, $3$, $4$, ($2$ and $5$ are already in use) and the second of these is $3$. You can easily check that each of these steps is a reversible computation, and so implementable in superposition on a quantum computer.