How to sample from a distribution with submodular weights Is there a known algorithm for sampling a set $S \subset \{1,...,n\}$ with probability
$p_S = \frac{e^{f(S)}}{\sum_{T \subset \{1,...,n\}} e^{f(T)}}$ where $f: 2^{\{1,...,n\}} \to \mathbb{R}$ is a submodular function?

Thanks!

There is a paper by Gotovos, Hassani, and Krause (NIPS, 2015) titled "Sampling from Probabilistic Submodular Models" which describes a MCMC method based on Gibbs sampling. They show that the mixing time $t_{\text{mix}}(\epsilon)$ is bounded above by
$$ t_{\text{mix}}(\epsilon) \leq 2 n^2 \exp(\zeta_f) \log \left( \frac{1}{\epsilon p_\min} \right) $$
where $p_\min = \min_{S} p(S)$ and the quantity $\zeta_f$ is
$$\zeta_f =  \max_{A, B \subset V} \left| f(A) + f(B) - f(A \cup B) - f(A \cap B) \right| $$
which I don't know of appearing elsewhere in the literature. There is another paper by Rebeschini and Karbasi (JMLR, 2015) titled "Fast Mixing for Discrete Point Processes" which proposes a different Gibbs sampler whose mixing time is bounded using the so-called "discrete hessian" which I also haven't seen used elsewhere in the literature.

It seems that submodularity of $f$ alone isn't enough to get fast mixing times for MCMC methods. Current methods certainly need to consider other quantities of $f$ to ensure fast mixing times.


Can one-way alternating automata with one-counter recognize some unary non-regular languages? One-way alternating pushdown automata (1APDA) can recognize any language in $ DTIME(2^{O(n)}) $ (Alternation by Chandra, Kozen, and Stockmeyer, 1981). By replacing a pushdown storage of a 1APDA with a counter, we can obtain a one-way alternating automaton with one-counter (1ACA). My question is about 1ACAs on unary languages.

Can 1ACAs recognize some unary non-regular languages?

Note that one-way nondeterministic pushdown automata can recognize only unary regular languages.

Yes.
Consider the language $L = \{ a^n \mid n = 2^s, s \geq 0 \}$ and construct a one-way alternating one-counter automaton recognizing $L$ in the following way. First, the automaton starts increasing the value of the counter and guesses when to stop, that is, guesses some value $m$. Then it branches universally: the first branch checks that the length of the input is precisely $2 m$, and the second branch moves $m$ cells forward on the input and checks that the remainder is in $L$, by going to the initial control state. Now add a base case: let the device accept if the input tape is exactly of length $1$, by making a nondeterministic guess at the initial state. That completes the construction.

In a similar fashion, one can get products of the form $n = k_1^{s_1} \ldots k_r^{s_r}$, with $k_1, \ldots, k_r$ fixed and $s_1, \ldots, s_r$ arbitrary.


n irrational number whose digits are pseudo-random: conceptual mismatch? Are there irrational numbers whose digits are considered pseudo-random?

Both concepts seem to be mismatched as a pseudo-random number generator typically is periodic and therefore generates a rational sequence whereas as irrational numbers are not periodic.

This follows from the question if a pseudo-random number generator is necessarily periodic. It can be expressed as a Turing machine which itself cannot compute reals other than by recursively enumerating them. If effectively, there exists such an irrational number, then there are pseudo-random number generators, in theory, that are non-periodic.

TL;DR The decimal expansion of a fixed rational number is not pseudorandom in the cryptographic sense, but irrational numbers (are conjectured to) exhibit some weaker but interesting forms of pseudorandom behavior.

Roughly speaking, a sequence $s \in \{0, \ldots, B\}^n$ is pseudorandom with respect to distinguishers $\cal A$, if it cannot be distinguished (with non-trivial probability) from a uniformly random sequence sampled from $\{0, \ldots, B\}^n$ by any algorithm $A$ in a class of algorithms $\cal A$. Usually in cryptography, $\cal A$ is the class of polynomial-time algorithms or polynomial-size circuits. Then it is easy to see that any sequence that can be generated in polynomial time by a deterministic algorithm is not pseudorandom: the distinguisher just simulates the generator. For this reason, pseudorandom generators in cryptography are randomized, and we speak of a pseudorandom distribution rather than a fixed pseudorandom sequence.

However, there are weaker notions of pseudorandomness (corresponding to more restricted classes $\cal A$ of distinguishers) that the expansion of an irrational number in an integer basis might satisfy. For example, $\sqrt{2}$, $e$, and $\pi$ are conjectured to be normal, which is a kind of pseudorandomness: each pattern of $k$ digits in base $B$ appears with frequency $1/B^k$, in the limit. This is like pseudorandomness with respect to distinguishers which can only ask "approximately how often does this pattern appear in the expansion of $\sqrt{2}$?" However, at the moment we are unable to prove normality for any of the above fundamental constants, in any base, even though it is conjectured they are absolutely normal, i.e. normal in every base. This is a famous open problem.

Something that we understand better is sequences like $(k\sqrt{2} \bmod 1)_{k = 1}^\infty$ ($x \bmod 1$ just means the fractional part of $x$). By Weyl's ergodicity criterion, we know that for any Lebesgue integrable function $f$, the average
$$
\overline{f}_n = \frac{1}{n-1}\sum_{k = 0}^{n-1}{f(k\sqrt{2} \bmod 1)},
$$
converges to the expectation $\mathbb{E}[f(x)]$, where $x$ is a uniformly sampled random number from $[0, 1]$. We also have deviation estimates: for $f$ the indicator function of an interval $I = [a, b]$, $a, b \in [0,1]$, the average $\overline{f}_n$ deviates from the expectation $b-a$ by $O((\log n)/n)$ in the worst case, and by $O(\sqrt{\log n}/n)$ on most intervals $[a, b]$ ("most" is measured by the natural product measure). Moreover, Beck has recently shown a central limit theorem, which quantifies the statement that numbers $n$ for which the deviation is large are very rare. For an intro to  the pseudorandomness properties of these sequences, check section 2.3. of Chazelle's discrepancy book.


Minimal Cost of Eulerian Path Problem:

Given a planar (undirected and mostly sparse) graph with an Eulerian Path, we introduce a cost function f: (v, e1, e2) for all two edges e1 and e2 that share a vertex v. The function also fulfills f(v, e1, e2) = f(v, e2, e1)

For an Eulerian Path we then define the overall cost as the sum of costs of all path-neighboring edges and the vertex in-between.

The goal is to obtain an Eulerian Path that has a minimal total cost. This has to be done somewhat efficiently, so testing all paths is not an option. Ideally answers should outline an algorithm.

Background:

The goal is to find a path that is "smooth". An example here is the B point in the image below. The flow is a lot smother if we go clockwise through the loop when coming from C.

Thoughts:

I think it is important to understand how many variations exist for an Eulerian Path and how we would obtain them.

There exists one very obvious variation, which is changing the direction of the path. We don't need to consider this variation since f(v, e1, e2) = f(v, e2, e1)
For any vertex with 0,..,n incoming and n,..,0 outgoing path segments, the path can be altered by swapping the ith incoming with the ith outgoing edge for i in 0,..,n. However this needs some alterations when the start/end vertex is included as well. Maybe we can just ignore it. Example: Point B and D
We can further swap "inner pairings with outer pairings", i.e. ith incoming and ith outgoing can be swapped with jth incoming and jth outgoing respectively for i, j in 1,..,n. Again we need to ignore start/end edge. This rule only applies if >= 6 edges join in a single vertex.

It becomes more difficult when the cycles from the vertex overlap, because then we can swap between them as well. Or do we not need to consider this at all? It's getting complicated and I'm no longer sure about correctness. So I’m kind of stuck.

Can we somehow convert this into an optimization problem?
Are there any papers on this topic? I couldn't find any.
Should I approach the problem completely different?
Can we somehow achieve minimal cost while executing Fleury's or Hierholzer's algorithm?

Edit (Aug 7 '17)

This presentation seems very interesting: https://www.cs.rochester.edu/~stefanko/Talks/EULER.pdf Unfortunately I wasn't able to find a paper accompanying it. At least counting Eulerian Cycle is #P-Complete.

Considering finding a minimum Eulerian Cycle for simplicity and using the idea of the Hierholzer's algorithm, we can find all simple cycles in the graph efficiently using e.g. http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

We would then need to find the edge-disjoint edge cycle cover. But this still doesn't guarantee a minimal path or Eulerian Cycle, because we still have to fuse the sub-cycles together.

Edit (Jan 7 '18)

I've started looking at solving this for an Eulerian Cycle since we have to consider fewer edge cases and the cycle problem is easily converted into the path problem (see here).

There have been suggestions to solve this by optimizing for each node. However, as the next example shows (colors indicate Eulerian Cycle), the local optima "battle" for each other. The top node uses the local optima, however if we were to use the optimum for both nodes we would obtain two circles and no longer have an Eulerian path.

I'm thinking maybe we can break the Eulerian Cycle into several "locally optimal" walks and then fuse them together again (efficiently we could find those walks using the Hierholzer's algorithm and following the lowest cost edge). Not guaranteed to be optimal though I think (or is it if we fuse them optimally?).

What's next?
I'll try to save up for a bounty to give this question some more exposure.

Edit (Nov 6 '18)

Still looking for an answer. I will try to implement my technique suggested above next. I'm no longer looking for a perfect algorithm, but one that approximates the solution.

The Eulerian cycle problem with "transition" costs $f$ is NP-hard by reduction from the Traveling Salesman Problem (TSP). Specifically, for any TSP instance given as a complete weighted graph on vertices $V = \{v_1,v_2,...,v_n\}$, encoded via the cost function $d : V \times V \rightarrow \cal{R}$, we can transform this into your problem in polynomial time as follows.

First, create a graph with a single "anchor" vertex $x$. Then, for each vertex $v_i \in V$, create a (self-looping*) edge $e_i = (x,x)$ with cost 0 (you can envision these self-loops as the separate "petals" of a flower-like graph in two-dimensions anchored around $x$). Finally, create a transition function $f$ (as per your definition) such that $f(x, e_i, e_j) = d(v_i, v_j)$. All Eulerian cycles (with transition costs from $f$) in this case are thus in 1:1 correspondence with all Hamiltonian cycles (i.e., solutions) of the original TSP instance and have equivalent cost. So if you can find a minimum-cost Eulerian cycle with such transition costs, then you can solve TSP to optimality, completing the reduction.

*Note that the self-looping edge encoding is not necessary, but it simplifies the description somewhat for the purposes of discussion above just to give the intuition (and your encoding seems to allow this). These self-loops can actually be broken up into separate "triangle" sub-graphs ($K_3$ gadgets), all anchored at the shared node $x$ whose edge transitions to other such gadgets are assigned costs accordingly from $d$ (but in a slightly-more-detailed manner).


What is the Algorithm to find all the possible chordal graphs which can be formed by a given 'n' number of vertices A chordal Graph is a connected graph which contains no chord-less cycle of size greater than three.
They are also called as Triangulated graphs.

All Paths are Chordal Graphs (No cycles).

All Trees are chordal Graphs (No cycles).

All cliques are chordal graphs.

A Path contains the minimum no of edges and a clique contains the maximum number of edges of a given n vertices chordal graph

Wiki Link for more explanation of chordal graphs

So for a fixed number 'n', what is the algorithm to find all the possible chordal graphs of n vertices?

For example:

n= 2, Answer = 1 chordal graph.
n= 3, Answer = 2 chordal graphs,
n= 4, Answer = 5 chordal graphs,
n= 5, Answer = 15 chordal graphs.

The above are determined by drawing all possible examples. Any algorithm?

The best way to do it, if you want to generate billions of graphs is to read up on enumeration algorithms such as:

[Yasuko Matsui, Ryuhei Uehara and Takeaki Uno, Enumeration of Perfect Sequences of Chordal Graph (2008)]

However for many this may be more than what is needed.
An easier algorithm is:

Enumerate all chordal graphs on n-1 vertices.
For each chordal graph G on n-1 vertices and each clique C in G.
Create a graph G' by adding a vertex v with neighbours C.
If G' has not already been found, add G to the list of chordal graphs on n vertices.

By this algorithm you should be able to generate the chordal graphs on at most 11 vertices which means over a million graphs.


Maintaining the value of a polynomial over a dynamically updated input Let $P(x_1, x_2, \ldots, x_n)$ be a polynomial over a fixed finite field. Suppose we are given the value of $P$ on some vector $y \in \{0,1\}^n$ and the vector $y$.

We now want to compute the value of $P$ on a vector $y' \in \{0,1\}^n$ such that $y$ and $y'$ differ on exactly one position (in other words, we flip exactly one bit in $y$). What are the space and the time trade-offs for this problem?

For example, if $r$ is the number of monomials in $P$, we can store the coefficients and the values of all monomials in $P$. If $y_i$ is flipped, we fix the value of each monomial containing $y_i$ and then the value of $P(y)$ using the stored information. Overall, we need $O(r)$ time and space.

(I do not say anything about how we identify the monomials containing $y_i$ for purpose. You can choose any reasonable representation of $P$, in the example I assume that we store a list of monomials containing $y_i$ for each $i$.)

Is there anything better?

Your idea generalizes as follows: given an algebraic circuit (over the finite field) or Boolean circuit (computing the bit-wise representation of your finite field elements) computing $P$, then maintain the value at each gate in the circuit. When you change the $i$-th bit of $y$, simply propagate that change along the DAG of the circuit, starting from the input $y_i$. If the circuit has size $s$, this takes $O(s)$ time and space. This could be much smaller than the number of monomials (which corresponds to the size of algebraic circuits of depth only 2).


Sorting "k-tonic" sequences I hope somebody knows a ref to this, so I do not have to read the literature...

Consider a sequence of numbers $x_1, \ldots, x_n$. Think about the sequence as $n-1$ intervals $[x_1, x_2], [x_2, x_3], \ldots, [x_{n-1},x_n]$. Clearly, the original sequence is bitonic if any point on the real line stabs at most 2 intervals. We will refer to a sequence where a point stabs at most $k$ intervals as being $k$-idiotic. Visually, if you draw the graph of the sequence (i.e., connect the points $p_i =(i,x_i)$ in order), then the above corresponds to the condition that no horizontal line intersects the graph more than $k$ times.

It is not too hard (but not too easy, either) to see that $k$-idiotic sequences can be sorted in $O( n \log k )$ time, which is clearly optimal.

Question: This result should be known. Do you know any appropriate ref?

Here's a Levcopoulos-Petersson sorting algorithm reference, but a different one somewhat older than the one in Andreas' answer:

Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Adapted for Presorted Files", WADS '89: Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, 382, London, UK: Springer-Verlag, pp. 499–509, doi:10.1007/3-540-51542-9_41.

There's a description of the algorithm in http://en.wikipedia.org/wiki/Cartesian_tree#Application_in_sorting from which the O(n log k) bound is easy to see. More precisely the time for the algorithm is $O(\sum\log k_i)$ where $k_i$ is the number of intervals containing input item $x_i$. In a $k$-idiotic sequence, each $k_i$ is uniformly bounded by $k$ so the total time is just $O(n\log k)$.


Benefits for syntactic and semantic classes This is a post separated from Consequences of UP equals NP, and also a follow-up question to Semantic vs. Syntactic Complexity Classes.

In the above post we learned about the semantic and syntactic classes. Briefly stated, when a class can be characterized as a leaf language class $\mathsf{L}[L_1|L_2]$, then a class is syntactic if $L_1 \cup L_2 = \Sigma^*$, that is, accepting language $L_1$ is the complement of rejecting language $L_2$; otherwise we called it a semantic class.
One can see that $\mathsf{P}$, $\mathsf{NP}$ and $\mathsf{PP}$ are syntactic classes,
while classes like $\mathsf{BPP}$ and $\mathsf{IP}$ are semantic classes.

Classical result like $\mathsf{PSPACE} = \mathsf{IP}$ and conjecture $\mathsf{P} \stackrel{?}{=} \mathsf{BPP}$ both can be view as semantic classes turns out to have syntactic characterizations. It seems to me that the syntactic classes are easier to handle, since they have natural complete problems. Also techniques like diagonalization is easier to be applied on syntactic classes, since they have a natural machine enumeration. But still $\mathsf{BPP}$ as a semantic class seems to have much more nice properties than the syntactic class $\mathsf{PP}$.

  What benefits do we have if we have a syntactic representation of a semantic class, or vice versa? Are there results or proof techniques only applied to syntactic/semantic classes?

Here are a couple of advantages.

Syntactic classes give you time hierarchies. Zak's proof of the nondeterministic time hierarchy works for any syntactic class. For semantic classes (like UPTIME($n^3$)?$=$UTPIME($n^2$)) these are open questions.
It's easier to create oracles that separate syntactic classes since you only need to diagonalize infinitely often and you don't care what happens on the other input lengths. Conversely it's easier to collapse semantic classes since you can eliminate machines that don't fulfill the promise.


Program reasoning about own source code The inspiration for this question is the following (vague) question: What are the programming language/logical foundations for having an AI which could reason about its own source code and modify it?

This isn't at all rigorous, so here is my attempt to extract a concrete question out of it. There are two things I'm interested in:

(A) A programming language P that can represent and manipulate its own programs as a datatype Program (e.g., as an AST). (If desired, a object of type Program can be converted into a String, which is the text of a valid program in that language. This would be the opposite of what a compiler does.)

(B) A method to reason about what a program in language P does. Here are two levels I'm thinking about it:

Another language Q (with theorem proving capabilities) which models what a P-program does. It should be able to express and prove statements like "the outcome of running Program p is foo."
A way to reason about what a program p:Program does in the language P itself. (So we are taking P=Q above.)

To what degree has something like this been implemented, or what is progress in this direction? What are the practical obstacles? In light of the original intention of the question, what is the best way to formalize the problem?

*

As the answers show (thanks!), both (A) and (B1) can be done separately, though it seems doing them together is more of a research question.

Here were some of my first thoughts on the question (warning: rather vague). See also my comments on Martin Berger's answer.

I'm interested in the programming language modeling the same programming language, rather than a simpler one (so P=Q above). This would be a "proof of concept" of a program being able to "reason about its own source code." Dependently typed programming languages can give guarantees about the outputs of its functions, but this doesn't count as "reasoning about its own source code" any more than a "Hello world!" counts as a quine in a language that will automatically prints out a naked string---there needs to be some kind of quoting/self-reference. The analogue here is having a datatype representing Program.

It seems like a rather large project - the simpler the language, the harder it is to express everything within it; the more complicated the language, the more work has to be done to model the language.

In the spirit of the Recursion Theorem, a program can then "get" its own source code and modify it (i.e., output a modified version of itself). (B2) then tells us that the program should be able to express a guarantee about the modified program (this should be able to recurse, i.e., it should be able to express something about all future modifications-?).

I think you are asking about two different things.

The ability of a programming language to represent all its programs as data.
Reasoning about programs as data.

For analytical purposes it's useful to keep them apart. I will focus on the former.

The ability of a
programming languages to  represent, manipulate (and run) its programs
   as data  goes under terms such as meta-programming or
   homoiconicity.

In an (awkward) way, all well-known programming languages can
   do meta-programming, namely by using the string data type together with the ability of invoking
   external programs (compiler, linker etc) on strings (e.g. by
   writing them to the file system first). However, that's probably not
   what you mean.  You probably have nice syntax in mind. Strings are not nice syntax for program representation because almost all strings don't represent programs, i.e. the string data type contains a lot of 'junk' when seen as a program representation mechanism. To make matters worse, the algebra of string operations has essentially no connection with the algebra of program construction.

What you probably have in mind is something much nicer. E.g. if $P$ is
a program, then  $\newcommand{\QUOTE}[1]{\langle #1\rangle}\QUOTE{P}$ is $P$, but
as data, at hand for manipulation and analysis. This is often called quotation.
In practise, quotation is inflexible, so we use quasi-quotation instead, which
is a generalisation of quotation where the quote can have 'holes' in which programs can be run that provide data to 'fill' the holes.
For example $$\newcommand{\SYNTAX}[1]{\mathsf{#1}}
\newcommand{\IF}[3]{\SYNTAX{if}\; #1 \; \SYNTAX{then}\; #2\; \SYNTAX{else}\; #3}\QUOTE{\IF{[\cdot]}{7}{8+9}}$$ is a quasi-quote representing a conditional where instead of a condition we have a hole $[\cdot]$. If the program $M$ evaluates to the data $\QUOTE{x > 0}$, then the quasi-quote $$\QUOTE{\IF{[M]}{7}{8+9}}$$ evaluates to
the data $$\QUOTE{\IF{x > 0}{7}{8+9}}.$$

(Note that $M$ is a normal program (not a program as data) that returns a quoted program, i.e. program as data.)
In order for this to work, you need a data-type to represent programs. Typically that data-type is called AST (abstract syntax tree), and you can see (quasi-)quotes as abbreviation mechanisms for ASTs.

Several
programming languages offer quasi-quotes and other feature for meta-programming. It was Lisp with its
macroing functionality that pioneered this ability to treat programs as data.  Perhaps
unfortunately, the power of Lisp-based macros was long seen to rest
largely on Lisp’s minimalistic syntax; it was not until MetaML (1)
that a modern, syntactically rich language was shown to be capable of
meta-programming. Since then, MetaOCaml (2) (a descendant
of MetaML, important for its breakthrough in the still ongoing quest to solve the problem of how to type programs as data), Template Haskell (3)  and Converge (4) (the first language to get all key meta-programming features right in my opinion) have shown that a variety of modern programming languages can house
meta-programming. It is important to realise that we can take any programming
language $L$ and turn it into a meta-programming language $L_{mp}$
that is $L$ together with the ability of representing (and evaluating)
its own programs as data.

Representing the outcome of running program, given as data, is
achieved by adding an $\newcommand{\EVAL}{\mathsf{eval}}\EVAL(\cdot)$ function that takes a program (given as
data) as input and runs it, returning its result. E.g. if $P$ is a
program evaluating to 17 and $\QUOTE{P}$, the (quasi-)quoted version of $P$,
i.e. $P$ as data, then $\EVAL(\QUOTE{P})$ also returns 17. There are all
manner of subtleties here that I'm ignoring here such as the question when meta-programmed
programs are being evaluated (giving rise to the distinction between
compile-time and run-time meta-programmed), what to do with types or
failing evaluations, what happens to bound and free variables in the
process of going from $P$ to $\QUOTE{P}$ or vice versa.

As to the second dimension, reasoning about programs given as data. As soon as you can convert programs into data, they are 'normal' data and can be reasoned about as data.  You can
use all manner of prover technology, e.g. dependent types or contracts
or interactive theorem provers or automated tools, as Joshua has
pointed out. However you will have to represent the semantics of your language in the reasoning process. If that language, as you require, have meta-programming abilities, things can become a bit tricky and not much work has been done in this direction, with (5) being the only program logic for this purpose. There is also Curry-Howard based work on reasoning about meta-programming (6, 7, 8). Note that these logic-based approaches, and the type-based approach (2) can indeed express properties that hold for all future meta-programming stages. Apart from (2) none of those papers have been implemented.

In summary: what you asked for has been implemented, but it's quite subtle, and there are still open questions, in particular to do with types and streamlined reasoning.

W. Taha. Multi-Stage Programming: Its Theory and Applications.
W. Taha and M. F. Nielsen. Environment classifiers.
T. Sheard and S. Peyton Jones. Template meta-programming for Haskell.
L. Tratt. Compile-time meta-programming in a dynamically typed OO language.
M. Berger, L. Tratt, Program Logics for Homogeneous Meta-Programming.
R. Davies, F. Pfenning, A modal analysis of staged computation.
R. Davies, A Temporal-Logic Approach to Binding-Time Analysis.
T. Tsukada, A. Igarashi. A logical foundation for environment classifiers.


Was bombe machine turing complete? In the recent movie called The Imitation Game, there is a affirmation that Turing was building his theoretical machine.
That machine is the Bombe Machine. Is this machine really equivalent to a Turing Machine ?

No, the bombe was very specific. It consisted of a bunch of enigma machines hooked together. It was very limited in its use. A more interesting question is whether the Colossus computer, also used in Bletchely Park, was Turing-complete.

When asking such a question, it should be understood that no physical computer is Turing-complete, since it cannot handle arbitrarily large inputs. But even if we abstract this issue away (in any reasonable way), bombes are not Turing-complete. It could be fun to come up with an appropriate model and determine the exact complexity class covered by bombes.


Solid applications of category theory in TCS? I've been learning a few bits of category theory. It certainly is a different way of looking at things. (Very rough summary for those who haven't seen it: category theory gives ways of expressing all kinds of mathematical behavior solely in terms of functional relationships between objects. For example, things like the Cartesian product of two sets are defined completely in terms of how other functions behave with it, not in terms of what elements are members of the set.)

I have some vague understanding that category theory is useful on the programming languages/logic (the "Theory B") side, and am wondering how much algorithms and complexity ("Theory A") could benefit. It might help me get off the ground though, if I know some solid applications of category theory in Theory B. (I am already implicitly assuming there are no applications in Theory A found so far, but if you have some of those, that's even better for me!)

By "solid application", I mean:

(1) The application depends so strongly on category theory that it's very difficult to achieve without using the machinery.

(2) The application invokes at least one non-trivial theorem of category theory (e.g. Yoneda's lemma).

It could well be that (1) implies (2), but I want to make sure these are "real" applications.

While I do have some "Theory B" background, it's been a while, so any de-jargonizing would be much appreciated.

(Depending on what kind of answers I get, I might turn this question into community wiki later. But I really want good applications with good explanations, so it seems a shame not to reward the answerer(s) with something.)

I can think of one instance where category theory was directly "applied" to solve an open problem in programming languages: Thorsten Altenkirch, Peter Dybjer, Martin Hofmann, and Phil Scott, "Normalization by evaluation for typed lambda calculus with coproducts".  From their abstract: "We solve the decision problem for simply typed lambda calculus with strong binary sums, equivalently the word problem for free cartesian closed categories with binary coproducts. Our method is based on the semantical technique known as 'normalization by evaluation' and involves inverting the interpretation of the syntax into a suitable sheaf model and from this extracting appropriate unique normal forms."

In general, though, I think that category theory is not usually applied to prove deep theorems in programming languages (of which there aren't so many), but instead offers a conceptual framework that is often useful (for example in the above, the idea of (pre)sheaf semantics).

An important historical example is Eugenio Moggi's suggestion that the notion of monad (which is basic and ubiquitous in category theory) could be used as part of a semantic explanation of side effects in programming languages (e.g., state, nondeterminism).  This also inspired some reflection on the syntax of programming languages, for example leading directly to the "Monad typeclass" in Haskell (used to encapsulate effects).

More recently (the past decade), this explanation of effects in terms of monads has been revisited from the point of view of the old connection (established by category theorists, in the 60s) between monads and algebraic theories: see Martin Hyland and John Power's, "The Category Theoretic Understanding of Universal Algebra: Lawvere Theories and Monads".  The idea is that the monadic view of effects is compatible with the (in some ways more appealing) algebraic view of effects, wherein effects (e.g., store) can be explained in terms of operations (e.g., "lookup" and "update") and associated equations (e.g., idempotency of update).  There is a recent paper building on this connection by Paul-André Melliès, "Segal condition meets computational effects", which also relies heavily on ideas coming from "higher category theory" (for example the notion of "Yoneda structure" as a way of organizing presheaf semantics).

Another, related class of examples comes from linear logic.  Soon after its introduction by Jean-Yves Girard in the 80s (with an aim of a better understanding of constructive logic), solid connections to category theory were established.  For some explanation of this connection, see John Baez and Mike Stay's, "Physics, Topology, Logic and Computation: A Rosetta Stone".

Finally, this answer would be incomplete without reference to sigfpe's illuminating blog "A Neighborhood of infinity".  In particular you could check out "A Partial Ordering of some Category Theory applied to Haskell".


Approximating #P-hard problems Consider the classical #P-complete problem #3SAT, i.e., to count the number of valuations to make a 3CNF with $n$ variables satisfiable. I am interested in the additive approximability. Clearly, there is a trivial algorithm to achieve $2^{n-1}$-error, but if $k<2^{n-1}$, is it possible to have an efficient approximation algorithm, or this problem is also #P-hard?

We're interested in additive approximations to #3SAT. i.e. given a 3CNF $\phi$ on $n$ variables count the number of satisfying assignments (call this $a$) up to additive error $k$.

Here are some basic results for this:

Case 1: $k=2^{n-1}-\mathrm{poly}(n)$

Here there is a deterministic poly-time algorithm: Let $m=2^n-2k = \mathrm{poly}(n)$. Now evaluate $\phi$ on $m$ arbitrary inputs (e.g. the lexicographically first $m$ inputs). Suppose $\ell$ of these inputs satisfy $\phi$. Then we know $a \geq \ell$ as there are at least $\ell$ satisfying assignments and $a \leq 2^n - (m-\ell)$ as there are at least $m-\ell$ unsatisfying assignments. The length of this interval is $2^n - (m-\ell) - \ell = 2k$. So if we output the midpoint $2^{n-1} -m/2 + \ell$ this is within $k$ of the correct answer, as required.

Case 2: $k=2^n/\mathrm{poly}(n)$

Here we have a randomized poly-time algorithm: Evaluate $\phi$ at $m$ random points $X_1, \cdots, X_m \in \{0,1\}^n$. Let $\alpha = \frac{1}{m} \sum_{i=1}^m \phi(X_i)$ and $\varepsilon = k/2^n$. We output $2^n \cdot \alpha$. For this to have error at most $k$ we need $$k \geq |2^n \alpha - a| = 2^n |\alpha - a/2^n|,$$ which is equivalent to $|\alpha - a/2^n| \leq \varepsilon.$ By a Chernoff bound, $$\mathbb{P}[|\alpha - a/2^n| > \varepsilon] \leq 2^{-\Omega(m \varepsilon^2)},$$ as $\mathbb{E}[\phi(X_i)]=\mathbb{E}[\alpha]=a/2^n$.
This implies that, if we choose $m=O(1/\varepsilon^2) = \mathrm{poly}(n)$ (and ensure $m$ is a power of $2$), then with probability at least $0.99$, the error is at most $k$.

Case 3: $k=2^{cn + o(n)}$ for $c < 1$

In this case the problem is #P-hard: We will do a reduction from #3SAT. Take a 3CNF $\psi$ on $m$ variables. Pick $n \geq m$ such that $k < 2^{n-m-1}$ -- this requires $n = O(m/(1-c))$. Let $\phi=\psi$ except $\phi$ is now on $n$ variables, rather than $m$. If $\psi$ has $b$ satisfying assignments, then $\phi$ has $b \cdot 2^{n-m}$ satisfying assignments, as the $n-m$ "free" variables can take any value in a satisfying assignment. Now suppose we have $\hat{a}$ such that $|\hat{a}-a| \leq k$ -- that is $\hat{a}$ is an approximation to the number of satisfying assignments of $\phi$ with additive error $k$. Then $$|b-\hat{a}/2^{n-m}| = \left| \frac{a - \hat{a}}{2^{n-m}}\right| \leq \frac{k}{2^{n-m}} < 1/2.$$
Since $b$ is an integer, this means we can determine the exact value of $b$ from $\hat{a}$. Algorithmically determining the exact value of $b$ entails solving the #P-complete problem #3SAT. This means that it is #P-hard to compute $\hat{a}$.


Maximum weight matching with classes of edges in a multi-edge bipartite graph Posted a similar question in mathoverflow, have tried to reduce this to Ford Fulkerson, but been stuck. Thought I'd ask TCS community to see if there are any ideas from individuals, here.
Consider a multi-edge bipartite graph $G = (L, R, E)$, with $|L| = |R| = n$, such that any $x \in L, y \in R$ have precisely two edges in $E$, $(x, y)_r, (x,y)_b$. We can imagine that we are assigning these edges a "color". Given that each edge $e \in E$ has a weight assigned to it $w(e)$, is it possible to find the maximum weight matching in this graph, subject to constraints on the number of $\leq r$ edges and $\leq b$ edges?
I believe I have a proof that this problem is NP hard (reduction to 3-matching) when I can freely adjust the number of colors, but in the case of two colors, I haven't been able to find anything. I've been searching for the past couple of days for any existing literature on similar problems with no avail. I would appreciate any suggestions or directions in moving forward.
Some ideas I've tested have included reductions to flow/matching problems with disjunctive constraints.
When I posted this question on Math Overflow, I received help from an individual who believed this problem was not NP. He suggested I look into path augmenting algorithms like Ford-Fulkerson, but unfortunately I have not found this to work; the idea of "backwards" flow doesn't make much sense when working with a color constraint.

Your problem is closely related to the so-called "Exact red-blue bipartite matching" problem, see for instance http://lemon.cs.elte.hu/egres/open/Exact_matching_in_red-blue_bipartite_graphs.

The case with two colors is unlikely to be NP-hard, since it is known to belong to RNC$^2$.
I think that this randomized result can be translated to your problem.

The case where the number of colors is part of the input is NP-hard,
and this hardness argument easily transfers to your problem.


What are some of the most ingenious linear programs developed for tackling hard combinatorial problems? What are some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems, especially any linear programs which had helped in getting good approximation algorithms for long standing open questions related to NP-hard optimization problems.

The relaxation of Calinescu, Karloff and Rabani for the undirected Multiway Cut problem is one my favorites. Had a big influence on subsequent work.
http://www.sciencedirect.com/science/article/pii/S0022000099916872


Hard gaps in maximum constraint satisfaction problems? An equivalent formulation of PCP theorem is: For Max 3-SAT it is $NP$-hard to distinguish between satisfiable formulas and formulas where at most $r$-fraction of the clauses are satisfiable (for some $r\lt 1$).

  Is there any known dichotomy theorem that classifies all Max CSP based on whether they have hard gaps or not?

Edit Dec 16, 2010: MAX CSP with hard gap means that the problem has optimal inapproximability factor. For instance, 3SAT has hard gap at location one since it is polynomial time approximable to a factor $7/8$ but it is $NP$-hard to obtain approximation factor $7/8+ \epsilon$ even when all clauses are satisfiable.

Prasad Raghavendra in the STOC'08 best paper proved a dichotomy conjecture for approximating Max-CSP assuming the Unique Games Conjecture. This is not how he presented it originally, but he did give talks presenting things this way a couple of years later, e.g., at the IAS, where it was videotaped:
http://www.math.ias.edu/seminars/abstract?event=36669

The difference from showing SNP-hardness is that here we talk about quantitatively optimal results.


Is there any programming language theory describing foreign function interfaces (FFI) and multiple language bindings? Is there any programming language theory describing foreign function interfaces (FFI) and multiple language bindings?

I have asked some implementation issues on stackoverflow, which is not suitable here. But I would like to ask from this site's view and see what I could possibly get from here.

Really appreciate your reply!

Thanks to Dave Clarke for his reply on meta！

The paper Operational Semantics for Multi-Language Programs
by Jacob Matthews and   Robert Bruce Findler presents two approaches for defining the semantics of programs written in two programming languages, taking particular care of data defined in one language and used in the other.  The lump embedding allows values created in one language to appear in running code of another, but these are can only be passed around, not operated on (or perhaps operated on by only a small interface).
The natural embedding  allows values in one language to be used in the other by performing a so-called cross-language cast, which converts values from one language to the other.

The paper JNI Light: An Operational Model for the Core JNI by Gang Tan presents a formal semantics of how existing JNI works. In contrast to the previous paper, this is formalises many of the low level details of what's going on, rather than trying to explore the issues from a foundational perspective.

Work on type-checking foreign function calls, such as Checking Type Safety of Foreign Function Calls by Michael Furr and Jeffrey Foster,  provide also a formal framework in which to phrase the type system and prove its soundness.

Looking at the references in these papers and finding where they are cited using google
scholar will help you discover a more thorough picture of what has been done in the area.


How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$? Can anyone help me with the following problem?

I want to find some values $a_i,b_j$ (mod $N$) where $i=1,2,…,K, j=1,2,…,K $ (for example $K=6$), given a list of $K^2$ values that correspond to the differences $a_i-b_j\pmod N$ (for example $N=251$), without knowing the concrete corresponding relation. Since the values $a_i,b_j\pmod N$ are not uniquely defined given the differences $a_i-b_j\pmod N$, we look for any  valid assignment of values.

Definitely, trying each permutation of the $K^2$ numbers in the list (totally $K^2!$ possible cases) and then solving the modular equations with $a_i,b_j$ as the variables is infeasible.

In fact, this problem arises in a paper on the cryptanalysis to an early version of NTRU signature scheme (http://eprint.iacr.org/2001/005). However, the author wrote only one sentence “A simple backtrack algorithm ﬁnds one solution…” (in Section 3.3) and so can anyone give more explanations? What’s more, the author also mentioned that “every circular shift $\{((a_i+M)\mod N,(b_i+M)\mod N\}_{i=1}^K$ or a swap $(\{(N-1-b_i,N-1-a_i)\}_{i=1}^K)$ results in the same pattern of $a_i-b_j\mod N$” and is this statement helpful?

Update: The description below is for a different problem (in which you have all pairwise distances in a set rather than pairwise distances between two distinct sets). I'll leave it up anyway since it is closely related.

This problem is called the beltway problem, and is a special case of the general $d$-torus embedding problem. It is also closely related to the turnpike problem, in which the distances differences are absolute (not modulo some number).

It is not known whether the beltway problem admits a poly-time algorithm. There are various pseudo-poly-time algorithms for related questions. The best reference (alas an old one) is the paper by Lemke, Skiena and Smith.


Early References for Transition System Semantics of Programs I am trying to trace back the origins of transition system semantics for imperative programs. I am assuming a transition system is a tuple $(\mathit{States}, \mathit{Trans})$ consisting of a set of states and a (binary) transition relation over states. By transition system semantics, I mean that there should be a mapping from programs to transition systems.

The presentation need not be exactly as I describe above and the mapping from programs to transition systems need not be completely explicit. For example, I would consider Plotkin's Structural Operational Semantics as providing transition system semantics to a formal language. Other early references I know of are due to Cousot & Cousot, and even earlier, due to Robert Keller in Formal Verification of Parallel Programs. There is earlier work by Richard Karp and Raymond Miller on reasoning about parallel programs, but their model is closer to Petri Nets and I am unsure about whether to read their paper as giving transition system semantics to programs.

Does anyone know of references from the early 80s or earlier where transition system semantics are provided for programs? Please add a few lines about the semantics and whether it is used today, and in what form.

Landin's SECD machine, originally described in The mechanical evaluation of expressions in 1964, is a transition system in the form of an abstract machine, later inspiring lots of of other abstract machines such as the CESK machine.


Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length If $a_{ij}$ is an $m \times n$ matrix of real numbers, and $b_j$ are $n$ more real numbers, then
$$\max_i  \sum_j (a_{ij} x_j + b_j)  \qquad (\ast)$$
is a convex piecewise linear function of $(x_1, \ldots, x_n) \in \mathbb{R}^n$. We can minimize it efficiently using linear programming.

I want to minimize an expression of the form
$$\sum_h \max_i  \sum_j (a_{hij} x_j + b_{hj}) \qquad (\dagger)$$
where $a_{hij}$ is an $\ell \times m \times n$ array of integers of bounded size and $b_{hj}$ is an an $\ell \times n$ array of integers of bounded size.

  Is there a method to do this, polynomially in $(\ell, m, n)$?

Note that $(\dagger)$ is equivalent to an expression of the form $(\ast)$, so it is convex and piecewise linear, but writing it that way involves the $\max$ of $m^{\ell}$ terms.

Introduce variables $y_{hi}$ together with constraints
$y_{hi}=\sum_j (a_{hij} x_j + b_{hj})$ for all $h$ and $i$.
Introduce variables $z_h$ together with constraints
$z_h\ge y_{hi}$ for all $h$ and $i$.
Then minimize $\sum_h z_h$.

The resulting linear program can be solved in time polynomially bounded in $\ell, m, n$ and the logarithm of the largest cost coefficient.

(I am not sure whether you are asking for a strongly polynomial solution.
This seems to be out of reach.)


What are some career options for someone with a computer scientist master degree? Other than going fully academic and getting a doctorate/post-doc, or going for a more or less 'standard' job in software development, what are some other career options in the full or semi theoretical C.S field?

Assuming you do not get intimidated when reading theory papers due to your training in your master's degree, which I assume is in a theoretical aspect of CS since you are asking on this site, I think it would be a great idea to try being a research programmer (usually inside some research organization, like an industrial lab or under the umbrella of a larger grant).

Why? It's not easy to implement an algorithm correctly, even if the authors sincerely meant to spell it out completely, and yet sometimes the need to run an algorithm does arise! Additionally, if you enjoy programming and measurements, later on you may even be able to further your study into a PhD in the area of algorithmic engineering, which I think is a very exciting area and wish to see more of it happening. (Check out the ALENEX conference and the DIMACS implementation challenges.)


Sum of products of all combinations? We are given a list $S$ containing $n$ numbers $S=(s_1,\ldots, s_n)$.
Let $S \choose k$ be the set of all possible $k$-combinations from $S$ (i.e. size $k$ subsets of $S$).
We want to compute the following expression:

$$ \sum_{A\in {S \choose k}} \prod_{x \in A} x$$

Is there an algorithm for this problem that works much better than the trivial one which goes over all subsets and computing and summing up all products?

Consider the polynomial $p(t) = \prod_{i=1}^n (s_i t + 1)$. Then we want to compute the coefficient of $t^k$ in $p(t)$. We can compute $p(t)$ using fast polynomial multiplication and then output the coefficient of $t^k$.

Say, partition $n$ polynomials $s_i t + 1$ into pairs and multiply the product of polynomials in each pair (using the standard fast polynomial multiplication algorithm). Then divide the obtained $n/2$ polynomials into pairs, and compute the product in each pair. Repeat this step over and over until we get one polynomial. At each step we can get rid of terms of degree higher than $k$.

Also note that if $k$ is small, we can just use dynamic programming.


Beating naive dynamic programming: examples similar to integer partitions? Let $p(n)$ denote the number of partitions of $n\in\mathbb{N}$ (briefly, number of ways to split a pile of $n$ stones into $\geq1$ unordered nonempty parts). The classical dynamic programming algorithm to find $p(n)$ is to construct a square table $A$ where
$$A_{i,j} = \text{partitions of $i$ where each part is $\leq j$}$$
and recursively fill it using the rules
$$A_{i,j} = A_{i,j-1} \text{ if }j>i$$
and
$$A_{i,j} = A_{i,j-1} + A_{i-j,j}\text{ otherwise}$$
with the appropriate conventions for the corner cases. Then $p(n)=A_{n,n}$. This takes $O(n^2)$ operations on integers (let's say we're looking for $p(n)$ modulo some big number, so the size of the numbers is $O(1)$). We can optimize the memory down to $O(n)$ by noticing that we only need the previous column to find the next one.

However, the pentagonal number theorem due to Euler says that
$$p(n) = \sum_{k\in\mathbb{Z}:g_k\leq n}(-1)^{k+1}p(n-g_k)$$
where $g_k = k(3k-1)/2$ are the pentagonal numbers. This allows us to recursively build a one-dimensional list of the $p(i)$, using only $O(n\sqrt{n})$ operations, since the above sum contains $O(\sqrt{n})$ terms.

My question: I was wondering if there are other examples of natural problems for which there is such a surprising speed-up over the standard dynamic programming algorithm, or if this is more of an isolated case complexity-wise.

One nice example is the Hamiltonian Path problem is easily solvable in $O(2^n(n+m))$ time (Bellman, 1962) by dynamic programming over vertex subsets. In 2010 Björklund gave an algorithm running in time $O(1.657^n)$ using determinants and polynomial identity testing in a field of characteristic $2$.

Another example is that of “connectivity problems”, such as Hamiltonian Path, Steiner Tree, or Feedback Vertex Set on graphs of treewidth $k$. The naive dynamic programming algorithms for these problems run in time $2^{O(k \log k)}n^{O(1)}$, and at a glance it really looks like that is what the ``correct’’ running time for these problems should be. However, in a wonderful paper, Cygan et al. showed that these problems all allow algorithms with running time $2^{O(k)}n^{O(1)}$, again cleverly using polynomial identity testing in a field of characteristic 2.


General question about pursuing TCS I am currently an undergraduate heading into my senior year. I've taken some theory/math classes (algorithms, and set theory/topology) in the past year and am taking quite a few more this year (more algorithms, abstract algebra, graph theory). My theory classes were the first classes in college I truly enjoyed. I definitely have an interest/passion for more theoretical and mathematical areas of computer science. I am pretty set on going to grad school/getting a PhD and if had the option, I would want to do research in an algorithms/theory group. However, I am wondering how can I assess if I have what it takes to succeed. Success in the case equates to getting a PhD --not necessarily at the most prestigious university -- but just making my contribution (as tiny as it may be) to the field. The reason I am asking this is because I am not some whiz kid who aces their classes with no sweat. I don't struggle by any means, but considering that algorithms/theory is a very intellectually challenging field, do you think hard work and passion for a subject can allow me to achieve my goal? Essentially, I don't want to put limitations on myself and regret not pursuing something I truly enjoy. However, at the same time, I want to be realistic with myself. Would love to hear your thoughts/experiences with this subject matter.

If TCS is something you enjoy, and you want to pursue a PhD, I wouldn't let the fear of failure stop you.  You can also mitigate some of the risk by enrolling in a program that awards you a Master's after a year or two -- that way, if you realize research isn't for you, you won't come out "empty-handed".  And if you don't succeed in landing a research job afterwards, as long as you enjoy grad school, it's not a big sunk cost.

To answer your question about "having what it takes" more directly -- I think you need to both have talent and put in the hard work to succeed.  My feeling is that most people who fail to get a PhD, however, fail not because they were not talented enough, but because they weren't disciplined enough.


Partitioning a matrix into equal-sized regions: finding the maximum I am facing the following research problem. We are given a matrix $M[1..p,1..p]$ of elements such that:

each element has value in the range $[0, \frac 1 j]$, $j <= p$, $j$ is given,
the sum of all elements in the matrix is 1.

The matrix is partitioned into $j$ axis-parallel non-overlapping rectangles. Each matrix cell with positive value is covered by exactly one rectangle. Whereas, each matrix cell with value 0 is covered by at most one rectangle. For each region, we sum the values inside it and obtain $region\_sum_i$, $i = 1..j$. We are given an optimal partitioning algorithm whose objective is to minimize the maximum $region\_sum_i$. The algorithm is Recursive Slice-and-Dice: Binary Space Partitions from Slice and Dice : A Simple, Improved Approximate Tiling Recipe. I need this algorithm due to the support for don't care regions and a general version of tiling problem. This is a DRTILE problem, but I translate this to RTILE using binary search.

The problem is to find an upper bound on $region\_sum_i$ for the optimal solution under worst-case input with given constraints. I need this as I am doing competitive analysis.

I appreciate any help! Many thanks!

In the proof of theorem 2 in Improved Approximation Algorithms for Rectangle Tiling and Packing by Berman et al, they proved an upper bound of $\frac{11}{5} \max\{W/p,y\}$, where $W$ is the sum of the weight of all elements, $p$ is the number of rectangles and $y$ is the weight of the largest element.

This implies a upper bound of $\frac{11}{5j}$ for your problem.


Reducing sorting to max-flow Is there a linear-time reduction from the sorting problem to the max-flow problem?

If so, what would such a reduction look like?

It seems unlikely to me for information-theoretic reasons. Expressing the answer to a sorting problem requires $\Omega(n\log n)$ bits of information. On the other hand, the answer to a maximum flow problem on an $m$-edge graph can be expressed (via a network simplex formulation) using only $O(m)$ bits of information (which edges are saturated, which are unused, and which form a spanning tree of used but unsaturated edges). Similar arguments apply to minimum-cost flow, etc. So to make a flow problem that has enough information in the solution to recover the sorted order, you need $\Omega(n\log n)$ edges.


Rank-robustness of the parallel complexity of linear algebra problems It is known that most computational problems related to linear algebra
can be computed in $NC^2$ - i.e. for an $n\times n$ matrix $A$, over the reals
or a finite field, we can compute the rank of $A$, $\det(A)$ or $A^{-1}$, etc. in parallel time $O(\log^2(n))$.

The complexity of these linear-algebra problems remains the same (i.e. in $NC^2$) even if the rank of $A$ is say $n^{\epsilon}$ for some small constant $\epsilon>0$ (just by padding zeros)
but what happens to the complexity of these problems when $A$ has very small rank, i.e. $r = rank(A) \leq \log(n)$?

Clearly, if $A$ is ${\it given}$ to us as a full-rank matrix of dimension $n \times r$ then the complexity drops:
Consider for example the problem of determining whether $A x = b$ for inputs $A,b$ over $\mathbf{F}_2$ for some vector $x$.

One can simply enumerate over all possible column subsets of $A$, and compute $x$ in constant parallel time ($ACC^0[2]$).
However, the problem is that we do not posses such a succinct description from the input.
Naively, trying to brute-force enumerate over all possible column combinations of size $\log(n)$ results in time ${n\choose \log(n)}$ which is quasi-polynomial.

I think the following procedure computes a basis of the column span of an $n \times n$-matrix of rank at most $\log n$ in $\mathrm{AC}_1$.

If you have a matrix of size $n \times 2 \log n$, you can find a basis of its column span in $\mathrm{AC}_0$ by running over all subsets in parallel and checking in parallel whether a nontrivial linear combination vanishes (say over $\mathbb{F}_2$). From all sets of maximal rank you select the lexicographically smallest.

Now given an $n \times n$-matrix of rank at most $\log n$, we can find a basis of its column span in $\mathrm{AC}_1$ as follows: Divide the columns into two halfves, compute a basis recursively. From these two bases we can compute a common basis using the algorithm from above.


Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$ I am trying to find results on the best known time complexity for finding $(1+\epsilon) \log n$ sized cliques in $G(n,1/2)$. More general results would be great, i.e. if $C_p$ is the constant such that the obvious greedy algorithm finds a clique of size $C_p \log n$ in $G(n,p)$ almost surely, then any results on finding a clique of size $(C_p + \epsilon ) \log n$ would be even better.

In particular, I am interested in whether we know how to find a $(C_p +\epsilon)\log n$ clique in $G(n,p)$ using $O(n^{\epsilon^2\log n})$ time and $O(n^{\epsilon^2\log n})$  space. Would a randomized algorithm that finds a $(C_p +\epsilon)\log n$ vertex clique with high probability under these time and space constraints constitute a publishable result? Any pointers to relevant literature would be greatly appreciated.

To answer the first part of your question, a conjecture in Karp'76 states that there is no efficient algorithm to find cliques of size $(1+ \epsilon)\log(n)$ for $G(n, 1/2)$. This conjecture is still open.


Category theory, computational complexity, and combinatorics connections? I have been trying to read “Pearls of Functional Algorithm design”, and subsequently “The Algebra of Programming”, and there is an obvious correspondence between recursively (and polynomially) defined data types and combinatorial objects, having the same recursive definition and subsequently leading to the same formal power series (or generating functions), as shown in the introductions to combinatorial species (I read “Species and Functors and Types, Oh My!”).

  So, for the first question, is there a way to recover the generating (recursive) equation from the power series? That’s an afterthought though.

I was more interested in the notion of initial algebras and final co-algebras as kind of “defining procedures about the data structure”. There are some practical rules in functional programming, concerning composition, products of mapping between algebras and similar, described for example in this tutorial. It seems to me that this could be quite powerful way to approach complexity and for example, it looks fairly straightforward to recover Master’s theorem in such context (I mean, you have to do the same argument, so not much gain in this instance), and the unique catamorphism from the initial algebra and the fact (am I mistaken?) that the algebras between A and FA for F-polynomial functor are isomorphic, makes it look to me that such approach could have a lot of benefits in analysing complexity of operations over data structures.

From practical standpoint, looks like fusion rules (basically, ways to compose algebra morphisms with one another, coalgebra morphisms, and general morphisms) are very powerful optimization technique for program transformation and refactoring. Am I right in thinking that full utilization of these rules can produce optimal program (no unnecessary intermediate data structures or other extra operations).

  Am I onto something (and what) here? Is it beneficiary (from learning standpoint) to try to look about computational complexity in this way? Are the structures, for which we can have "nice" initial algebras somehow too limited for some problems?

I’m mostly trying to find a way to think about complexity in terms of the structure of the search space and the way the "search space" and "search algorithm" interact through some "nice" object like the initial algebra of the functor and to understand if it's useful to try to view things this way, when looking at more complicated structures.

Dave Clarke's comment is quite important. Generally fusion doesn't change the O(-) efficiency.  However, of particular interest is Liu, Cheng, and Hudak's work on Causal Commutative Arrows. Programs written with them are necessarily optimizable, in part through stream fusion, to a single loop free of dynamic memory allocation and intermediate structures: http://haskell.cs.yale.edu/?post_type=publication&p=72


Venues for short research articles I've just completed a short (5 page) paper on proving a certain combinatorial game NP-Complete. This is in no way a result of huge significance, yet it's one that I believe is publishable. What venues would be good for a paper like this? The only one I'm aware of is Information Processing Letters; are there other ones like this?

Fun with Algorithms!  Although it is a conference not a journal that you might looking for, among other things several NP-hardness results about (combinatorial) games are published here, including this one.

However this is a triennial conference (except for 2014, where the last conference was in 2012), so if you want to publish it soon then there might be a better choice.


Hierarchy theorem for NTIME intersect coNTIME? $\newcommand{\cc}[1]{\mathsf{#1}}$Does a theorem along the following lines hold: If $g(n)$ is a little bigger than $f(n)$, then $\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap \cc{coNTIME}(f)$?

It's easy to show that $\cc{NP} \cap \cc{coNP} \neq \cc{NEXP} \cap \cc{coNEXP}$, at least. Proof: Assume not. Then $$\cc{NEXP} \cap \cc{coNEXP} \subseteq \cc{NP} \cap \cc{coNP} \subseteq \cc{NP} \cup \cc{coNP} \subseteq \cc{NEXP} \cap \cc{coNEXP},$$ so $\cc{NP} = \cc{coNP}$, and hence (by padding) $\cc{NEXP} = \cc{coNEXP}$. But then our assumption implies that $\cc{NP} = \cc{NEXP}$, contradicting the nondeterministic time hierarchy theorem. QED.

But I don't even see how to separate $\cc{NP} \cap \cc{coNP}$ from $\cc{NSUBEXP} \cap \cc{coNSUBEXP}$, as diagonalization seems tricky in this setting.

(This would've been a comment, but it doesn't render properly when I try that.)

"I don't even see how to separate" $\;\;\;$$\mathbf{U}$$\mathbf{q}$$\mathbf{uasiLIN}$ $\cap \; \mathbf{coUquasiLIN} \;\;\;$ from

$[$the linear-exponent version of QIP[2]$] \;\; \cap \;\; [$the linear-exponent version of coQIP[2]$] \;\;\;\;\;$.


What would be the consequences of PH=PSPACE? A recent  question (see Consequences of NP=PSPACE) asked for the "nasty" consequences of $NP=PSPACE$. The answers list quite a few collapse consequences, including $NP=coNP$ and others, providing plenty of reasons to believe $NP\neq PSPACE$.

What would be the consequences of the somewhat less dramatic collapse $PH=PSPACE$?

$\mathsf{PH}$ collapses. A $\mathsf{PSPACE}$-complete problem must be in some level of $\mathsf{PH}$, say it's in $\mathsf{\Sigma_k P}$. Since it's $\mathsf{PSPACE}$-complete$=\mathsf{PH}$-complete (by assumption), $\mathsf{PH} \subseteq \mathsf{\Sigma_k P}$.


Decidability of transcendental numbers I have a question, whose answer is probably well known, but I can't seem to find anything meaningful after a bit of searching, so I would appreciate some help.

My question is whether it is known that deciding whether a number is transcendental is undecidable.

Possibly, one assumes as input, say a program that returns the i^th bit of the number.
Thanks in advance for any pointers.

Kristoffer's solution can be used to show that, assuming reals are represented so that we can compute limits of sequences of reals which are computably Cauchy. Recall that a sequence $(a_n)_n$ is computably Cauchy if there is a computable map $f$ such that, given any $k$ we have $|a_{m} - a_{n}| < 2^{-k}$ for all $m, n \geq f(k)$. The standard representations of reals are like that, for example the one where a real is represented by a machine that computes an arbitrarily good rational approximation. (We can also speak in terms of computing digits, but then we have to allow negative digits. This is a well known issue in computability theory of the reals.)

  Theorem: Suppose $S \subseteq \mathbb{R}$ is a subset such that there exists a computable sequence $(a_n)_n$ which is computably Cauchy and its limit $x = \lim_n a_n$ is outside $S$. Then question "is a real number $x$ an element of $S$" is undecidable.

Proof.
Suppose $S$ were decidable. Given any Turing machine $T$, consider the sequence $b_n$ defined as
$$b_n = \begin{cases}
a_n & \text{if $T$ has not halted in the first $n$ steps,}\\
a_m & \text{if $T$ has halted in step $m$ and $m \leq n$.}
\end{cases}$$
It is easy to check that $b_n$ is computably Cauchy, therefore we can compute its limit $y = \lim_n b_n$. Now we have $y \in S$ iff $T$ halts, so we can solve the Halting Problem. QED.

There is a dual theorem in which we assume the sequence is outside $S$ but its limit is in $S$.

Examples of sets $S$ satisfying these conditions are: an open interval, a closed interval, the negative numbers, the singleton $\lbrace 0 \rbrace$, rational numbers, irrational numbers, transcedental numbers, algebraic numbers, etc.

A set which does not satisfy the conditions of the theorem is the set $S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$ of rational numbers translated by a non-computable number $\alpha$. Exercise: is $S$ decidable?


What is the Quantum Cheshire Cat experiments' import to Quantum Computing? What is the significance of the Quantum Cheshire Cat to Quantum Computing? To recap, the Quantum Cheshire Cat experiment proved it was possible to separate a neutrons' spin from the neutron. Or, in other words a particle could lose its properties in special circumstances. What would the implications be to quantum computing? Does it mean measurements to the system be more accurate, as the properties of the system are isolated from external influences? When reasoning about this experiment by way of Quantum Computing, would one look at the results of the experiment with Quantum Communication (one could always look the fidelity, or even capacity of the quantum channel as enhanced) as a model or any other models would be apt to study the experiments' effects?

The quantum Cheshire Cat experiments appear to require postselection even to exhibit. Of course, postselection is itself a computational resource (and an extremely powerful one!) for "bounded" error quantum computation, and one whose power is characterised. To wit: the class PostBQP of decision problems decideable with bounded error using poly-size quantum circuits, conditioning on some single bit having the value 1 (provided that this occurs with non-zero probability) is precisely the class PP. (Recall also that PP contains NP as a subset.)

Perhaps one might ask whether quantum Cheshire cats might somehow represent a useful idiom in the design of  PP algorithms for difficult problems. Alternatively, perhaps quantum Cheshire cats correspond to some intriguing feature of quantum mechanics that can be described without resorting to (anything equivalent to) postselection, and which has implications for quantum computation. However, it isn't obvious at the moment that either of these are the case.


What is the problem in "closest pair problem" if all points share the same x-coordinate The closest pair of points problem deals with the task to find a pair of points with the global minimum distance. There is a problem, when all points share the same x-coordinate, or at least a large number of points.

I just don't know why, I heard the running time becomes $n^2$

What about it? What is the problem, since the proof for the algorithm shows, that at max. 8 points can reside in the $2 \delta \times \delta$ area.

Points with the same x-coordinate do not cause any substantial problem.  However, if you implement the divide-and-conquer algorithm carelessly, they may cause a problem.  One way to deal with them is by using symbolic perturbation.


Can any program be implemented mechanically? Is it possible to build a single purpose (non Turing complete) mechanical implementation of say, Microsoft Word?  Is it possible to implement such things as iterators, first-order functions, the whole gamut of programming techniques?  Could gears and other mechanical parts represent data structures or even program objects?  At a certain point does this necessitate building a general purpose Turing-equivalent machine, or can each function, variable, etc, have its own unique mechanical construct in the form of flywheels and/or gears, ratchets, what have you?  In summary I wonder if any given piece of software on a standard computer could be compiled to a mechanical blueprint.

Yes, it is. Here's how you do it:

You can compile basically any program you like to circuits. See for instance the work of Dan Ghica and his collaborators on the Geometry of Synthesis, which shows how to compile programs into circuits.

Dan R. Ghica. Geometry of Synthesis: A structured approach to VLSI design
Dan R. Ghica, Alex Smith. Geometry of Synthesis II: From Games to Delay-Insensitive Circuits
Dan R. Ghica, Alex Smith. Geometry of Synthesis III: Resource management through type inference.
Dan R. Ghica, Alex Smith, Satnam Singh. Geometry of synthesis IV: compiling affine recursion into static hardware.

Circuits then turn out to reappear over and over in engineering. John Baez gives a big table of analogies of concepts, and works out a lot of connections, in This Week's Finds 288-296. So the circuit diagrams Dan's compiler generates could be instantiated as mechanical or hydraulic systems, if you really wanted to!

╔══════════════════════════════════════════════════════════════╗
║                 displacement  flow      momentum     effort  ║
╠══════════════════════════════════════════════════════════════╣
║ Mechanics      position      velocity  momentum     force    ║
║ (translation)                                                ║
║                                                              ║
║ Mechanics      angle         angular   angular      torque   ║
║ (rotation)                   velocity  momentum              ║
║                                                              ║
║ Electronics    charge        current   flux         voltage  ║
║                                        linkage               ║
║                                                              ║
║ Hydraulics     volume        flow      pressure     pressure ║
║                                        momentum              ║
╚══════════════════════════════════════════════════════════════╝

http://math.ucr.edu/home/baez/week288.html
http://math.ucr.edu/home/baez/week289.html
http://math.ucr.edu/home/baez/week290.html
http://math.ucr.edu/home/baez/week291.html
http://math.ucr.edu/home/baez/week294.html
http://math.ucr.edu/home/baez/week296.html


$P=BPP$ without good PRGs? We know that the existence of good pseudorandom generators (PRGs) does not only imply $P=BPP$, but also $PromiseP=PromiseBPP$.

Let us assume $PromiseP\ne PromiseBPP$. Then good PRGs do not exist. However it is still possible that $P=BPP$ holds. If good PRGs do not exist then does $P=BPP$ imply $P=NP$ or is there a possibility $P\neq NP$ still might be true?

Is it possible to have $P=BPP$ without good PRGs and with $P\neq NP$ and with $PromiseP=PromiseBPP$?

To put this in complexity terms, could it be possible that P = BPP and EXP has polynomial-size circuits (so no general derandomization)? Relative to a generic oracle you do get P=BPP for all input lengths, and EXP in P/poly for infinitely many lengths, a partial answer to your query. I don't know an oracle where P = BPP and EXP is in P/poly, but I'd think it should be possible.


Examples of the value of proofs for algorithms In teaching Intro. Algorithms to undergrads, one of the most difficult tasks is to motivate why they need to know how to prove things about algorithms. (For many students, at least in many US universities, they may see some basic proofs in Discrete Mathematics, but Algorithms is often the first time they have to use proofs to reason about algorithms.) While I think I can do a decent job motivating this at an abstract level, concrete examples are much more convincing, hence my question:

  I'm looking for concrete examples that show the value of proofs in algorithms.

A couple questions already address this, and if you have answers to those, please add them there:

Examples of algorithms and proofs that seem correct, but aren't
How to fool the “try some test cases” heuristic: Algorithms that appear correct, but are actually incorrect

However, I think there are other ways proofs can be valuable beyond the above. E.g., by working through the proof you can gain an insight that leads to a more efficient algorithm, or to an algorithm for a related problem, or to an idea for developing a better test suite to test your implementation, etc.

Some criteria:

Answers here ideally shouldn't fit one of the questions above (as I said, please add an answer there if you have it)
Should be presentable to Intro. Algorithms students. While the proof itself need not be presentable, the story should be presentable (e.g. the statement of the problems involved, some idea of how the proof led to something that just "eyeballing correctness" would not have). If you are unsure about this point, go ahead and add it as an answer and I'll do my best to see if it can be presented to this audience.
Should be as natural as possible. Artificial examples are kinda okay, but real examples are much more motivating to students.
Note that I am talking here about abstract proofs for abstract algorithms, not formal (/automated/etc) proofs of algorithm implementations. As a litmus test, the ideas involved should not be language-specific.

(While this question is not exactly research-level, I think it might get more answers here than on cs.SE, as I suspect the answers will come from  historical examples in the theory of algorithms that expert researchers on this site are more likely to be familiar with.)

Here is a natural problem from graph theory where the proof and the algorithm are closely intertwined. In my view, one can discover this algorithm only via thinking about the proof and the algorithm "in parallel." The task is this:

Input: An undirected graph.

Task: Find a subgraph with maximum edge-connectivity.

Note: What makes the task non-trivial is that a subgraph can have larger edge-connectivity than the whole graph. Since there are exponentially many subgraphs, it would take exponential time to check all of them to find the most connected one, even though we can compute the edge-connectivity of any graph in polynomial time.

Below is a part of a lecture note about solving this problem. It shows that the task can be solved in polynomial time, using a subroutine that finds a minimum cut (which is well know to be doable in polynomial time). For short, edge-connectivity is just called connectivity, and is denoted by $\lambda(G)$.


Is there a reduction to "door and pressure plate" games that doesn't explode solution length? This paper gives a proof that in a game with doors and pressure plates, it is PSPACE-hard to determine whether or not the (player's) avatar can reach a given location. This is proven by a reduction from TQBF, and the length of the resulting solutions depends exponentially on the number of universal quantifiers in the formula.

Is there a reduction from an NPSPACE machine to such a game for which the length of the game's solutions are polynomially related to the length of the machine's accepting paths?

Perhaps you can easily simulate a LBA; the idea is the following:

for every cell of the LBA tape add a cell gadget $G_i$ that can be entered only from the bottom and leaved only from the top;
the gadget has an entrance door $C_i$ which simulates the head position (only one $C_i$ is opened at every step);
then there are two bit doors $Z_i$ and $O_i$; $Z_i$ is opened if the cell contains a  zero, $O_i$ is opened if there cell contains a one;
both bit doors lead to a similar control structure which is made by several one-way corridors; a corridor corresponds to a state of the LBA, and the door $q_i$ of the $i$-th corridor is opened if and only if the current state of the LBA is $q_i$;
according to the (possibly non-deterministic) transition table of the LBA, a traversal of the (opened) corridor changes the current state of the LBA and the configuration of the bit-doors, closes door $C_i$ and opens $C_{i+1}$ or $C_{i-1}$.

A cell gadget is sketched in the figure below.

Non-deterministic choices can be realized splitting the corridors  in the control structures into two or more sub-corridors as shown in the figure below.

Note: if a plate can only open/close a single door, then you can add an auxiliary structure with (long) one way corridors that (de)activates the distinct state doors of each cell.


reference request for construction of expanders I'm looking for a good exposition of the explicit constructive proof of the existence of expander graph families due to Reingold Vadhan and Wigderson.  Arora/Barak has a chapter on it, but i find it to be full of typos, more serious errors, and other annoying choices (not to knock AB -- I like it generally).  I just started reading the original RVW paper, but I was wondering if there are other good sources.

You can look at this survey by Hoory, Linial, and Wigderson [1]. Chapter 9, specifically (p. 508) is on the zigzag product.

9.The zig-zag product
  9.1.   Introduction
  9.2.   Construction of an expander family using zig-zag
  9.3.   Definition and analysis of the zig-zag product
  9.4.   Entropy analysis
  9.5.   An application to complexity theory: SL=L

[1] Hoory, Shlomo, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society 43.4 (2006): 439-561.


What are the hardness results known for CSP over $\mathbb{F}_q$? I found two related papers,

There is a UGC hardness result here, https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf
A kind of a stronger result might be found in these two other papers, http://www.csc.kth.se/~austrin/papers/maxkcsp_full.pdf and http://eccc.hpi-web.de/report/2012/110/download/
There is an approximation threshold with respect to Lasserre rounds here,
http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf

Are there other important papers in this topic? Like has anyone shown SOS hardness for this? (I don't see a way to dualize Madhur's Lasserre results to get that!) I would be glad to know what other papers in this topic should one look up.

Here is a summary of what is known about approximability of $k$-CSP over a domain of size $q$:

The best known approximation algorithms for the problem give an $\Omega(q \max(k, \log q)/q^k)$ approximation [MM14 and MNT16].
For $k = \Omega(q)$, there is a matching hardness of $O(kq/q^k)$ by Håstad (UGC-hardness) and Chan (NP-hardness) [Chan13].
For $k$ between $c \log q  /  \log \log q$ and $q$, the best known NP-hardness result is $O(q^2/q^k)$ (follows from [Chan13]).
For $2 < k < c \log q  /  \log \log q$, the best known UGC-hardness is $2^{O(k \log k)} q \, (\log q)^{k/2}/q^k$ by Manurangsi et al. [MNT16].
For $k=2$, the best NP-hardness is $O(\log q/\sqrt{q})$ by Chan [Chan13], the best UGC-hardness is $O(\log q/q^k)$ by Khot et al. [KKMO07]

[Chan13] Siu On Chan. Approximation resistance from pairwise independent subgroups. In Proceedings of the Symposium on Theory of Computing, pages 447–456, 2013.

[KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproxima bility results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007.

[MM14] Konstantin Makarychev and Yury Makarychev. Approximation algorithm for non-Boolean Max $k$-CSP. Theory of Computing, 10(13):341–358, 2014.

[MNT16] Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan. Near-optimal UGC-hardness of approximating Max $k$-CSP$_r$ . In Proceedings of the Workshop on Approximation Algorithms for Combinatorial Optimization Problems (to appear), 2016.


Does every NO instance of this promise problem have a local refutation? For the following equivalent questions, you choose

whether-or-not the 3 variables in a clause must be distinct.

  Is there an integer $k$ such that for all 3-SAT formulas $\mathcal{F}$ without negations,

  if every  $(\leq k)$-clause sub-formula of $\mathcal{F}$ is 1-in-3 satisfiable then $\mathcal{F}$ is NAE-satisfiable?

  Equivalently, is there an integer $k$ such that for all

  3-SAT formulas $\mathcal{F}$ without negations, if $\mathcal{F}$ is not NAE-satisfiable then

  $\mathcal{F}$ has a  $(\leq k)$-clause sub-formula which is not 1-in-3 satisfiable?

(The Fano plane shows that $k$ can't be less than $7$.)

Motivation:    That is the "low end" of my question

on cs.stackexchange which was inspired by the

possibility of generalizing Schaefer's dichotomy theorem

to constraint satisfaction promise problems.

Specifically, for the simplest non-trivial promise-constraint,

with m being the size of the input set, I have neither managed to

find evidence for it being in  promisecoQIP[2]TIME$\hspace{-0.02 in}\big(\hspace{-0.04 in}$2o(m)$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}$q2o(m)

for infinitely many m, nor find evidence that it's not solvable

in coNTIME(O(1)) on essentially the most basic word RAM.

The former applies even when each variable occurs exactly twice

and "many m" gets replaced with "many even m" (since 3 is odd),

and the latter applies even when negative literals are allowed.

So if I understood well, your problem in the language of graph theory would be as follows:

  Is there a $k$ such that if for a $3$-uniform hypergraph for any $k$ of its edges we can select a $1$-shallow hitting set (a set of vertices that meets each of the $k$ edges in exactly one vertex), then the hypergraph is $2$-colorable?

The answer to this question is no because for any $g$ and $r$ there are $r$-uniform hypergraphs of girth $g$ with arbitrarily high chromatic number [Kostochka-Nesetril].
The girth $g$ of an $r$-uniform hypergraph is the smallest $g$ for which there are $g-1$ edges whose union has size at most $g(k-1)$.
Thus, if a hypergraph has girth $g$, then any $g-1$ edges have a $1$-shallow hitting set by induction because their union looks like a tree.
This means that locally it satisfies your 1-in-3 satisfiability condition, but it is not $2$-colorable, so there is no NAE-satisfying assignment for the whole hypergraph.


Spell Checker with BK tree and edit distance that accounts for transpositions I want to try and write code for a BK tree using a certain edit distance that accounts for transpositions for a spell corrector. I've looked into Damerau-Levenshtein distance, but the triangle inequality required for a BK tree does not hold. Any suggestions?

Actually, the Damerau–Levenshtein distance is a metric. (See, for example, §11.1 of Encyclopedia of Distances, by Deza & Deza, Springer, 2009.) That is, it does obey the triangle inequality. This can be seen quite easily if you view every possible string as a node, with the edit operations and transpositions between them as edges. The Damerau–Levenshtein distance is then a shortest-path distance between the two strings in question, and such distances (graph geodesics) are always metric (i.e., triangular): You can't take a shortcut (breaking the triangle inequality) without simultaneously discovering a shorter path (a contradiction).

The problem is that actually computing the Damerau–Levenshtein distances is tricky, and you may see algorithms that compute something similar (optimal string alignment, for example), but that don't actually find the minimal number of steps. If Damerau–Levenshtein with adjacent transpositions is OK for your application, you can use that. You'll find algorithms for computing it online (even in Wikipedia), and as long as your code computes the minimum number of steps, the triangle inequality is obeyed. (But note that, as stated, algorithms based on finding the Damerau–Levenshtein distance through optimal alignment will not obey the triangle inequality, but that is because they don't really find the true Damerau–Levenshtein distance.)

If you want the unrestricted Damerau–Levenshtein distance (without necessarily using adjacent transpositions): Fear not, there are ways of computing that as well! You could have a look at the work of Lowrance & Wagner, for example.

If you don't want to get into the details of that, you could simply use a heuristic algorithm such as $A^*$ to compute the distance, with plain Levenshtein distance as the lower-bounding heuristic, for example. Should be efficient enough for reasonably-sized strings, and will give you the corret Damerau–Levenshtein distance. And it will work with your BK-trees.


Computing size of permutation group from generators You're given $k$ permutations $a_1,\dots,a_k$. Consider closure of this set under the composition operation. What are most efficient and simple algorithms to calculate the size of this closure?

The most efficient (and also simplest) algorithms for this are based on the notion of a strong generating set, introduced by Sims. Strong generating sets can be computed efficiently using the Schreier-Sims algorithm. Essentially any introductory book that talks about computational group theory should have a decent introduction to this (and if it contains an introduction to this that isn't decent, I'd think it's not a very good book). While the standard deterministic algorithm for this takes quadratic time, there is a randomized nearly-linear time algorithm. See Seress's book "Permutation Group Algorithms," Chapter 4 (the nearly-linear time Monte Carlo algorithm is Theorem 4.5.5).


Are there any 'graphical' algebras that can describe the 'shape' of graphs? One of the main problems in graph enumeration is determining the 'shape' of a graph, e.g. the isomorphism class of any particular graph. I am fully aware that every graph can be represented as a symmetric matrix. However, to get it's shape, you'd need a collection of row/column permutations, which makes a matrix a little less suited. It's also a bit harder to 'see' the graph, once it's in that form.

My question is: Are there any 'graphical' algebras that can describe the 'shape' of graphs?

What I'm thinking of is what kinds of formal systems that algebraic topologists tend to come up with. In particular, things like the algebra for knot invariants, or notational systems like operads or polygraphs. These kind of 'doodle algebras' are not nearly as well developed, so perhaps there is a reason to believe that no such algebra exists for graphs, but I'd though I'd ask before assuming otherwise.

UPDATE:

My question is probably very narrow and not immediately answerable with a 'yes', so if the moderators don't mind, I'll broaden it by asking:

Are there any existing systems (the kind I describe above) that could be adapted (easily or otherwise) to create such a system? If there's more than one, feel free to mention all of them. And throw in the ones already mentioned as well.

Motivation

My motivation for such a question is actually about classifying asymmetric graphs. I'm only an undergrad, so my review of the current state of algebraic graph theory is pretty thin. But I've yet to see much, if any, work in trying to systematically describe all graphs in an algebraic way, and in particular, one that uses visual metaphors over symbolic ones.

Practical example where such a system would be useful

Suppose one wants to describe a proof that all Eulerian graphs must have vertices of even degree. A standard proof usually uses arguments about even and odd degrees, without mentioning the actual edges used. A typical student would find such a proof for the first time, and probably begin drawing graphs, attempting to convince himself of the argument. But perhaps a better tool than the pure 'logical' argument, would be to show that any collection of 'symbols' from such a language could not satisfy some 'completeness' condition.

Yeah, I know, I'm being hand-wavy at this last part.. If I wasn't, though I'd probably start creating such a system myself!

But ignoring my vagueness for a moment, I get a sense that many of the old and well known theorems in graph theory are not difficult but require some conceptualization that a really good framework could 'tie up' and 'package' into a unified view.

Many people have tried to find an algebraic language to describe the shape of a graph.  This question is essentially the one that motivates structural graph theory.

At the heart of this area of discrete mathematics is the study of graph decompositions.  Some of the people working in this area are Neil Robertson, Paul Seymour, Robin Thomas, Maria Chudnovsky, Kristina Vušković, and their collaborators, although this list is biased by my own research interests.

Particular kinds of graph decompositions have led to some of the most general results in graph theory.  For instance, one of the main technical tools developed for the graph minors project, which led to the Robertson-Seymour theorem, is the graph structure theorem.  This shows that classes of graphs that exclude some minor can be built up from simpler graphs.

In the proof of the Strong Perfect Graph theorem a somewhat different decomposition was used.  The key result is: For every Berge graph $G$, either $G$ is basic, or one of $G, \overline{G}$ admits a proper 2-join, or $G$ admits a balanced skew partition.

The decompositions studied to date are in some sense non-algebraic.  My personal intuition is that there are indications that there is no "nice" system such as the one you seek.  Making this glib statement precise would likely require a nontrivial enterprise in finite model theory, but I suspect it could also lead to interesting new results in graph theory (whether successful or not).


Independent iterations in Las Vegas algorithms In [Randomized Algorithms, Motwani and Raghavan] book, it is stated that the method of independent iterations to reduce the error probability in Monte Carlo algorithms (amplification according to Wikipedia) has its analogy in Las vegas algorithms. The authors then cited the following references:

Alt, Helmut, et al. "A method for obtaining randomized algorithms with small tail probabilities." Algorithmica 16.4 (1996): 543-547.
Luby, Michael, Alistair Sinclair, and David Zuckerman. "Optimal speedup of Las Vegas algorithms." Information Processing Letters 47.4 (1993): 173-180.

These suggestions of the mentioned papers are a bet very generalized in my opinion. I am wondering - are there well-known algorithms that use the concepts introduced in the previous papers ?

Rapid restarts in SAT solving are one area where the sequence introduced in Luby,Sinclair,Zuckerman is used. See for example Section 2.1 in http://www.st.ewi.tudelft.nl/~marijn/publications/rapid.pdf for some references.


What languages can be reduced to a NP-complete problem in polynomial time NP-complete: Language is NP-complete, when it is in NP and every problem in NP is reducible to it in polynomial time. But what languages are reducible to a NP-complete problem (for example SAT) in polynomial time - other than languages in NP.

NP-hard: A problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H. This is reversed reducing, so I'm not sure if this is a good candidate. We don't know whether one can solve NP-hard problem in polynomial time.

  If P ≠ NP, then NP-hard problems cannot be solved in polynomial time. (NP-hardness wiki)

So, my question is what class of languages can be transformed to a NP-complete problem in polynomial time using Turing reductions and/or many-to-one reductions.

Under Karp reductions, the answer is exactly $\mathbf{NP}$: it is not hard to see that if a language is Karp-reducible to any $\mathbf{NP}$-language, then it is in $\mathbf{NP}$ too. On the other hand, all of $\mathbf{NP}$ reduces to $\mathbf{NP}$-complete languages by definition.

Under Turing reductions, the answer is the class $\mathbf{P}^\mathbf{NP}$: languages that are decidable by a polynomial-time algorithm that has an access to an $\mathbf{NP}$ oracle. Indeed, a Turing reduction of a language $L$ to an $\mathbf{NP}$-complete language is by definition a polynomial-time algorithm deciding $L$ with oracle access to $\mathbf{NP}$. On the other hand, any such algorithm can be simulated with oracle access to an $\mathbf{NP}$-complete language, thus obtaining a Turing reduction.


Classes containing boolean closure of CFLs So I asked a similar question on MathOverflow, but I now realize I asked the wrong question and asked it in the wrong place.

Anyway, I'm searching for a class of languages containing the boolean closure of CFLs that has a 'pumping-type' condition on it. What I've found so far are:

MCFGs (multiple context-free languages), which have a nice pumping lemma and contain CFLs (though it's not obvious if they contain the boolean closure of CFLs, since they're not boolean-closed themselves),
ET0L languages (which contain CFLs, have a 'pumping-type' lemma, and are (full) AFLs themselves--but I don't think they necessarily contain the boolean closure of CFLs),
Mildly CSLs (which apparently have pumping-type lemmas?),
Indexed languages (which have a 'shrinking' lemma), etc.

Now, I'm certainly no specialist in formal language theory, so I don't know too much about these classes. Anyway, does such a class exist, and, if so, where can I find papers/etc. on it?

This is not an answer to your question per se, but might explain why finding sensible classes of languages more or less fitting your requirements will be hard: recall that the emptiness of intersection of two context-free languages is undecidable, thus the full boolean closure of CFLs is not a very interesting class... (In fact, any R.E. language $L$ can be expressed as $h(L_1\cap L_2)$ for $L_1$ and $L_2$ deterministic context-free and $h$ an homomorphism.)

More in the scope of your question, you can look at Alexander Okhotin's work on conjunctive and boolean grammars, but I don't recall any pumping results.


Simulate a process of state change with transition probability dependent on proportion in state in previous time I was thinking about a reverse single transferable vote type situation (i.e. most votes is eliminated) where the process continues until there is only on state left and at each new round there really is a new vote. My suspicion is that this could be modelled by assuming like:

50% to most similar (remaining) state, 25% to next most similar state, 25% to next most similar state if present state is the most populous state

or

90% current state; 10% most similar state

This means that for each time period the number of states is reduced by one and presumes people opt for options most similar to their preference in the previous time period. That latter character reminds me in particular of Markov chains.

I would like to know how to think about doing this or what search terms would help to find someone else who has already tried this.

My instinct that it would be a bit like if you had for t=1, n=20 bins that marbles had fallen into and then count the number of marbles in each bin. For t=2, there are still n=20 bins but the most populated bin from the previous example has a 0% destination probability for all other bins/states and the destination probabilities for the other bins depend on their relationships to each other and, in particular, the "losing" bin. And the for t=3 there are now two bins with destination probabilities of 0% and so on... Being able to look at the situation for each t would be important, too.

Any language would be greatly helpful in a conceptual sense, but on a personal level I have even a cursory understanding of just R (but also some experience with and access to SAS and a bit less again, on both counts, with Stata).

Thank you (and apologies if this is in the wrong place).

The principle of your voting system makes me think of Instant Run off, which forces the participants to vote X number of time when there's X+1 candidates on the poll. For Instant Runoff it is the choice that gather the less votes which is out of the competition, but i think you can easily adapt this system to your situation. (Inverting the max and min condition to get the right state out of the game)

I think you can figure it out in R, but you can also try to do it in Python. Take a look at this post : List sorting/modify problem if you want to see how IR can be implemented in Python. You might have to try and post what you've done (even not working) or to ask more specific questions if you want further help from the community.

You can also try other voting systems if it matches with your expectations, i would strongly recommand you the Condorcet voting method if you don't want to bother with multiple round processus : http://short.open-agora.com/m0ZQMPjMQV


Estimating the rank of a large sparse matrix Consider a large sparse n by n matrix.  Are there any methods to estimate its rank in time roughly proportional the number of elements in the matrix?

There is a very neat randomized algorithm by Cheung, Kwok, and Lau, which computes the rank of an $n\times m$ matrix $A$, $n\le m$, in time $O(\mathrm{nnz}(A) + \min\{n^\omega, n\cdot\mathrm{nnz}(A)\})$. Here $\mathrm{nnz}(A)$ is the number of nonzero elements of $A$, and $\omega$ is the matrix multiplication exponent. Not quite what you are asking for, but it does improve on fast matrix multiplication based methods for $\mathrm{nnz}(A) = o(n^{\omega - 1})$.


Is Scott's reduction sound for $\mathrm{FO}^2$ with equality? As per this paper by Grädel, Kolaitis and Moshe Vardi, they discuss computational complexity of satisfiability problem in $\mathrm{FO^2}$, In order to do this they use Scott's reduction. Which is the fact that any sentence in $\mathrm{FO^2}$ can be reduced to Scott's Normal form in polynomial time. The Scott's Normal form is given as
$$\forall x \forall y \alpha(x,y) \land \bigwedge_{i=1}^{m} \forall x \exists y \beta_{i}(x,y) $$
Now, they also say that proving decidability for scott's reduction only proves decidability for $\mathrm{FO}^2$, and then they discuss scott's class for $\mathrm{FO}^2$ with equality.
My question: Is Scott's reduction sound for $\mathrm{FO}^2$ with equality, i.e every sentence can be reduced to the form presented above, where $\alpha$ and $\beta_i$ are all binary predicates, it is not obvious to me from there discussion?

Yes. Just employ the formula $\forall{x}\forall{y} \; R(x,y) \leftrightarrow (x=y)$ (for a fresh binary predicate $R$), which allows you to "hide" the equality inside the $\forall\forall$-part of the Scott normal form. Then you proceed as usual.
EDIT: I've noticed that you wrote that $\alpha$ in $\forall{x}\forall{y} \; \alpha$ is a binary predicate. It is not true and obviously not all $\textit{FO}^2$ formulae are reducible to such a form. The aforementioned $\alpha$ should be a quantifier-free formula (line 13 of page 60 of the attached pdf). Maybe this is what made you problems while understanding the Scott reduction.