How many induced subgraphs does $G$ have of specific size Let $G$ be a connected graph with $n$ vertices and $O(nk)$ edges, ($k$ is parameter).
Then how many connected induced subgraphs of size $l$  does $G$ have?

The simple case when $l=2$, The number of subgraphs is number of edges which is $O(nk)$. How can we generalize this one.

Consider a star graph, if we take a center of star union with $l-1$ arbitrary vertices then the corresponding subgraph is induced connected subgraph. So the maximum number is about $n-1\choose l-1$. We can extend this class of graphs by connecting arbitrary vertices together to have more edges. It's also possible to achieve closer to $n \choose l$ if $l$ is much smaller than $k$, or $k$ is big enough.


Complexity of a certain leaf language with Prime & Composite number of accepting paths. Given a non-deterministic Turing Machine that runs in polynomial time, it accepts if the number of accepting paths are composite, it rejects if the number of accepting paths are prime and it outputs I do not know if the number of accepting paths are {0,1}.

Lets call the Above language CA-PR (Composite Accept - Prime Reject).

Then we have co-CA-PR = PA-CR(Prime accept, composite reject).

Both of the above languages output DON'T KNOW when the number of accepting paths are {0,1}.

Questions:

Do CA-PR & PA-CR not contain UP?
A #P Oracle can definitely solve these problems, can a PP oracle too? How about a ParityOracle?
What can we say about the intersection and union of these languages?
Where can we place this complexity class? Is it in the polynomial hierarchy?

@Tayfun Pay, you are trying to get us to solve a problem for you!

As it turns out, you only need to apply primality on the count of the number of accepting paths and this count requires polynomial number bits to write down. But the concatenated string on the paths of the NP machine is exponentially long. It is as if the primality algorithm is run on a "padded/unary" version. So it is quite weak and runs within logspace and hence the whole things is within PSPACE.

Now, if you refer to the table (Figure 1) in this paper by [Jenner et al], (or directly to [Hertrampf et all 93]), you will notice that classes within PSPACE (ModP/PH etc) emerge only when the leaf language is a subset of regular languages such as solvable/aperiodic etc. But as is well known, unary PRIMES is not regular (by standard application of pumping lemma).

This much I know. Now to your question. I would suspect PSPACE is the right bound and the proof should not be too difficult, given the techniques from the papers quoted above. If you spend some time thinking, I am sure you will be able to prove the correct bound one way or the other. And especially if these are your first steps into research, I will say, go for it!


An example where smallest normal lambda term is not fastest Let the $size$ of $\lambda$-terms be defined as follows:

$size(x) = 1$,
$size(λx.t) = size(t) + 1$,
$size(t s) = size(t) + size(s) + 1$.

Let the complexity of a $\lambda$-term $t$ be defined as
the number of parallel beta reductions from $t x$ to its normal form
(using an optimal evaluator in Levy's sense).

I am looking for an example of two normal $\lambda$-terms for the same function where
the larger term has lower complexity.

...

Edit for clarity

since it seems that it is not obvious what I'm asking, I'll try to give a solid example. There is often a belief that the "naive"/"simplest" definition of a function is slow and not optimal. Better performance increase the complexity of the term, since you need added data-structures, formulas, etc. A great example is fibonacci, which can be "naively" defined as:

-- The fixed fibonacci definition
fib_rec fib n =
    if (is_zero x)
        then 1
        else fib (n - 1) + f (n - 2)

-- Using church numbers instead of the λ-combinator to get a normal form
fib n = n fib_rec 0 n

This is often regarded as the "simplest" definition of fib, and is very slow (exponential). If we expand the dependencies of fib (the usual definitions for church-number addition, pred, is_zero), and normalize it, we get this term:

fib = (λa.(a(λbc.(c(λdef.f)(λde.d)(λde.(de))
      (λde.(b(λfg.(c(λhi.(i(hf)))(λh.g)(λh.h)))
      d(b(λfg.(c(λhi.(i(h(λjk.(k(jf))))))(λhi.g)
      (λh.h)(λh.h)))de)))))(λbc.c)a))

Improvements such as memoization tables would make this term bigger. Yet, there exists a different term that is much smaller...

fib = (λa.(a(λb.(b(λcde.(e(λfg.(cf(dfg)))c))))
      (λb.(b(λcd.(cd))(λcd.d)))(λbc.b)))

and, curiously, is also asymptotically superior to the naive one, running in O(N). Of all definitions I'm aware, this is both the fastest and the simplest. The same effect happens with sort. "Naive" definitions such as bubble sort and insertion sort often get expanded to huge terms (20+ lines long), but there exists a small definition:

-- sorts a church list (represented as the fold) of church numbers
sort = λabc.a(λdefg.f(d(λhij.j(λkl.k(λmn.mhi)l)(h(λkl.l)i))
       (λhi.i(λjk.bd(jhk))(bd(h(λjk.j(λlm.m)k)c))))e)(λde.e)
       (λde.d(λfg.g)e)c

Which also happens to be faster, asymptotically, than every other definition I know. This observation leads me to believe that, as opposed to common belief, the simplest term, with smallest Kolmogorov complexity, is usually the faster. My question is basically wether there is any evidence of the opposite, although I'd have a hard time in formalizing it.

Blum’s speedup theorem is usually stated in the language of partially recursive functions, but up to trivial differences in notation, it works just the same in the language of $\lambda$-calculus.

It says that given any reasonable complexity measure $M$ (for example, the optimal number of reductions as in the question) and a recursive function $f(x,y)$ (for example, $2^y$), we can find a recursive predicate $P(x)$ such that:

  For every algorithm (i.e., $\lambda$-term in normal form here) $g$ computing $P$, there is another algorithm $h$ for $P$ that has $f$-speedup over $g$:
  $$f(x,M(h,x))\le M(g,x)\text{ for all large enough inputs }x,$$

where $M(g,x)$ denotes the complexity of the computation of $g$ on input $x$ according to measure $M$.

Consequently:

$P$ has no asymptotically optimal algorithm in the given measure
in particular, the shortest algorithm for $P$ is not asymptotically optimal
for any algorithm for $P$, there is an asymptotically faster algorithm whose normal form is longer (because up to renaming of variables, there are only finitely many normal terms of a given length)


Multidimensional knapsack STRONGLY NP-complete Who can point me to a reference where it is actually shown that multidimensional knapsack is strongly NP-complete? I have found loads of papers where they claim it is, without citation; I have found another load where they cite Garey & Johnson, although it is not in their list of strongly NP-complete problems (Sec. 4.2); many actually cite Garey & Johnson as "An introduction to" instead of "A guide to", so these authors probably copied from one another. In fact, some authors claim that it is not strongly NP-complete, an example is "The multidimensional 0–1 knapsack problem: An overview" by Freville, but the argument (generalize the DP for single-dimension knapsack) is obviously bogus, see below.

Multidimensional knapsack tries to maximize $\sum_j c_j x_j$ such that $\sum_j a_{ij} x_j \le b_j$ for $i=1,...,m$, with $x_i$ being integer $\ge 0$ (and all $c_j, a_{ij}, b_j$ being $\ge 0$). We can also demand $x_i \in \{0,1\}$, the 0/1-version of the problem. I would be happy for a proof of either of the two to be hard (hardness of the other should follow easily).

Strongly NP-hard applies only to number problems, and restricts the (some) maximum of the numbers to be polynomial in the size of the problem instance (bits needed to encode it). Strongly NP-hard rules out the existence of a pseudopolynomial algorithm for the problem, with running time polynomial in the numbers that appear in the instance. The usual knapsack (single-dimensional) obviously has a pseudopolynomial algorithm (DP), but this algorithm cannot be generalized to multidimensional KP, as the dimension of the KP appears in the exponent of the running time. I hope that I did not mess up anything in my definitions...

In the paper titled "ON MULTIDIMENSIONAL PACKING PROBLEMS" that appeared in SODA and then in SICOMP (http://epubs.siam.org/doi/abs/10.1137/S0097539799356265) we considered several packing problems where items are d-dimensional vectors. We discuss PIPs which are the same as as multidimensional knapsack (we mention this) and their approximability when d is not fixed. You can find hardness results as function of d in that paper.


Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average? In this question, a 3CNF formula means a CNF formula where each clause involves exactly three distinct variables.  For a constant 0<s<1, Gap-3SATs is the following promise problem:

Gap-3SATs
Instance: A 3CNF formula φ.
Yes-promise: φ is satisfiable.
No-promise: No truth assignments satisfy more than s fraction of the clauses of φ.

One of the equivalent ways to state the celebrated PCP theorem [AS98, ALMSS98] is that there exists a constant 0<s<1 such that Gap-3SATs is NP-complete.

We say that a 3CNF formula is pairwise B-bounded if every pair of distinct variables appears in at most B clauses.  For example, a 3CNF formula (x1∨x2∨x4)∧(￢x1∨￢x3∨x4)∧(x1∨x3∨￢x5) is pairwise 2-bounded but not pairwise 1-bounded because e.g. the pair (x1, x4) appears in more than one clause.

  Question.  Do there exist constants B∈ℕ, a>0, and 0<s<1 such that Gap-3SATs is NP-complete even for a 3CNF formula which is pairwise B-bounded and consists of at least an2 clauses, where n is the number of variables?

The pairwise boundedness clearly implies that there are only O(n2) clauses.  Together with the quadratic lower bound on the number of clauses, it roughly says that no pair of distinct variables appears in significantly more clauses than the average.

For Gap-3SAT, it is known that the sparse case is hard: there exists a constant 0<s<1 such that Gap-3SATs is NP-complete even for a 3CNF formula where each variable occurs exactly five times [Fei98].  On the other hand, the dense case is easy: Max-3SAT admits a PTAS for a 3CNF formula with Ω(n3) distinct clauses [AKK99], and therefore Gap-3SATs in this case is in P for every constant 0<s<1.  The question asks about the middle of these two cases.

The above question arose originally in a study of quantum computational complexity, more specifically two-prover one-round interactive proof systems with entangled provers (MIP*(2,1) systems).  But I think that the question may be interesting in its own right.

References

[AKK99] Sanjeev Arora, David Karger, and Marek Karpinski.  Polynomial time approximation schemes for dense instance of NP-hard problems.  Journal of Computer and System Sciences, 58(1):193–210, Feb. 1999.  http://dx.doi.org/10.1006/jcss.1998.1605

[ALMSS98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and the hardness of approximation problems.  Journal of the ACM, 45(3):501–555, May 1998.  http://doi.acm.org/10.1145/278298.278306

[AS98] Sanjeev Arora and Shmuel Safra.  Probabilistic checking of proofs: A new characterization of NP.  Journal of the ACM, 45(1):70–122, Jan. 1998.  http://doi.acm.org/10.1145/273865.273901

[Fei98] Uriel Feige.  A threshold of ln n for approximating set cover.  Journal of the ACM, 45(4):634–652, July 1998.  http://doi.acm.org/10.1145/285055.285059

Not a full answer, but hopefully close. This is very close to Luca's comments above. I believe the answer is that at least there do exist constants B∈ℕ, a>0, and 0<s<1 such that Gap-3SATs is NP-complete even for a 3CNF formula which is pairwise B-bounded and consists of at least $an^{2-\epsilon}$ clauses, for any constant $\epsilon$.

The proof is as follows. Consider a GAP-3SAT$_s$ instance $\phi$ on $N$ variables in which each variable appears at most 5 times. This is NP-complete, as you say in the question.

Now we create a new instance $\Phi$ as follows:

For every variable $x_i$ in $\phi$, $\Phi$ has $n$ variables $y_{ij}$.
For every set of indices $i$, $a$ and $b$ with $a\neq b$, $\Phi$ has a pair of clauses $y_{ia}∨￢y_{ib}∨￢y_{ib}$, and $y_{ib}∨￢y_{ia}∨￢y_{ia}$. I'll refer to these as comparison clauses since they ensure that $y_{ia} = y_{ib}$ if they are satisfied.
For every clause in $\phi$ acting on variables $x_i$, $x_j$ and $x_k$, for every $a$ and $b$, $\Phi$ contains an equivalent clause, where $x_i$ is replaced by $y_{ia}$, $x_j$ is replaced by $y_{jb}$ and $x_k$ is replaced by $y_{k(a+b)}$  (here addition is done modulo $n$). I'll refer to these as inherited clauses.

The total number of variables is then $m = nN$. Note $\Phi$ has $2Nn^2$ comparison clauses and $\frac{5}{3}Nn^2$ inherited clauses, for a total of $\frac{11}{3}Nn^2$ clauses. Taking $n = N^k$ we have $m = N^{k+1}$ and the total number of clauses $C = \frac{11}{3}N^{2k+1} = \frac{11}{3}m^{2-\frac{1}{k+1}}$. We take $k = \epsilon^{-1} - 1$, so $C \propto m^{2-\epsilon}$.

Next, $\Phi$ is pairwise 8-bounded (max of 2 from the comparison clauses and 6 from the inherited clauses).

Finally, if $\phi$ is unsatisfiable, then at least $(1-s)N$ clauses are unsatisfied. Now, if $y_{ia} \neq y_{ib}$ for any $a,b$ then at least $n-1$ clauses are unsatisfied. Note that in order to satisfy the $(1-s)N$ unsatisfied clauses in a set of inherited clauses for fixed $a,b$ then the assignment of variables $y_{:a}$, $y_{:b}$ and $y_{:(a+b)}$ must differ at at least $\frac{1-s}{5}N$ positions, leaving at least $\frac{1-s}{5}N(n-1)$ comparison unsatisfiable clauses. This must hold for every choice of $a$ and $b$, so at least $\approx \frac{1-s}{5}Nn^2 = \frac{3(1-s)}{11}C$ comparison clauses must remain unsatisfied in total for enough inherited clauses to be satisfied.  If however you look at the other extreme where all comparison clauses are satisfied, then $(1-s)Nn^2 = (1-s)m^{\frac{2k+1}{k+1}} = (1-s)C$ clauses are unsatisfiable. Hence a gap remains (although reduced) with $s' = \frac{4+s}{5}$.

The constants probably need to be double checked.


A Lambda calculus for invertible (r-Turing computable) functions I'm interested in the concept of "r-Turing completeness", as defined by Axelsen and Glück (2011). A system is r-Turing complete if it can compute the same set of functions as a reversible Turing machine, without producing any "garbage" data. This is the same as being able to compute every function that is both (a) computable, and (b) injective.

I would like to computationally explore the space of computable injective functions. In order to do this I'm looking for the "most minimal" reversible programming language --- something that can play the equivalent role for r-Turing computability that the lambda calculus plays for Turing computability.

I know that there are many reversible languages that people have developed and proven to be r-Turing complete. However, these are being developed with practical applications in mind, and so their authors concentrate on giving them expressive features rather than making them minimal.

Does anyone know if such a minimal invertible language has been described, or whether there is any research in such a direction? I'm fairly new to the literature on this topic, so I could easily have missed it. Alternatively, does anyone have any insight into how such a language could be created?

Below is a summary of what I'm looking for. I do not know whether it can be created by modifying the lambda calculus itself, or whether a completely different type of language would have to be used.

r-Turing complete language - computes all computable invertible functions, and can only computes invertible functions
Syntax and semantics as minimal as possible. (E.g. Lambda calculus has only function definitions and applications, and nothing else.) It isn't necessary for the syntax or semantics to be related to those of the lambda calculus, although they could be.
Program = data. That is, the programs operate on expressions rather than any other kind of data. This guarantees that a program's output can always be interpreted as a program. This probably implies that it has to be a functional rather than an imperative style of language.
There is some systematic way to convert a program into its inverse, which doesn't involve substantially more computation than that involved in actually performing the inverse computation. (Not all invertible languages have this property, but some do.)

I should emphasise that Axelsen and Glück's approach to reversible computing is quite different from the well-known approach due to Bennett, where an (in general non-invertible) program is made invertible by returning some information about the computation's history along with the output. r-Turing completeness is about being able to compute injective functions without any additional output. There are several things called variations of "reversible lambda calculus" that are reversible in Bennet's sense - those are not what I'm looking for.

I am not very familiar with the area, but there is some recent work from the programming languages community that might interest you, based on the idea of restricting to a language of type isomorphisms.  In particular, you could have a look at

Fractional Types by Roshan P. James, Zachary Sparks, Jacques Carette, and Amr Sabry

as well as various related publications which you can find on Amr Sabry's website.


Difference between syntax and semantic error in programming languages When compilers generate errors for a specific programming language, there's distinction between syntax & semantic errors. E.g. ) + f 3 has ill-formed syntax, but type checking is considered as part of semantic analysis.

My intuition tells me that, by setting more constraints on the language syntax, some semantic errors can become syntax errors. And my question is if there are any intrinsic differences between syntax and semantics? Or are they just checking performed on different levels, for example syntax checking is a rather local checking while semantic checking is global? Is there anything fundamental that makes semantics checking different from syntax checking? Is it possible to embed all semantic checking within syntax? Are there any theories related to these questions?

It may also be the case that my intuition is wrong - if that's the case, please also explain to me why that is wrong.

In the strictest sense, there is no real difference between syntax errors and semantics errors, at least as far as language theory is concerned: the only salient difference is the complexity of the automaton required to recognize that language, with, e.g.

Context-free languages only requiring pushdown automata (PDA)
General recursive languages requiring full Turing machines (TM)

If every "syntactic task" merely required pushdown automata and every "semantic task" something more, then the matter would be settled, but unfortunately there are many tasks that are associated with programming language syntax that cannot be handled by PDA alone, and conversely, some semantic tasks which seem to require only weak computation power. Still, the distinction provides some intuition.

Pragmatically, compilers are designed in phases, which makes managing the task of generating executable code manageable. I particularly like this diagram from the Compcert website.

Typically, the first 1-3 phases turn what is essentially a stream of bytes or tokens into something more naturally seen as a tree structure. Everything before the tree creation will be labelled as "syntax" and everything after as "semantics".

In C, the syntactic phases are typically tokenization, macro expansion and parsing, everything after that will be semantics. Again, opinions may differ, since there is no accepted formal distinction.

I think there's a larger discussion to be had about how to distinguish syntactic notions from semantic notions in the field of formal logic, but I'm not sure I feel qualified to have it.


Help in understanding Symbolic Execution I am an undergraduate CS student and currently reading on software security, particularly on static analysis of programs. I am particularly interested in understanding Symbolic Execution - an implementation technique under static analysis.

So far, I am unable to understand some of the research papers on the same, because of the lack of deep understanding of Symbolic Execution and its applications and uses.

There aren't many resources on the web, and the ones that are, assume a considerable formal knowledge on this domain from the reader beforehand.

I would appreciate if somebody can explain in depth the concept of Symbolic Execution and how it can be possibly used in program analysis - identifying bugs/vulnerabilities in softwares.
Any links to some helpful resources on the same that would enable a security enthusiast to get started would be highly appreciated.

Don't worry too much about understanding everything in one source. Try reading several different articles and from their summaries and technical details, you may build up your own understanding.

Symbolic Execution for Software Testing: Three Decades Later, Cristian Cadar and Koushik Sen, 2013.
All You Ever Wanted to Know about Dynamic Taint Analysis and Forward Symbolic Execution (but Might Have Been Afraid to Ask), Edward J. Schwartz, Thanassis Avgerinos, David Brumley, 2010.
Symbolic Execution for Software Testing in Practice – Preliminary Assessment, Cristian Cadar, Patrice Godefroid, Sarfraz Khurshid, Corina S. Pasareanu, Koushik Sen, Nikolai Tillmann, Willem Visser, 2011
From Program to Logic: An Introduction, Patrice Godefroid and Shuvendu Lahiri, 2012
Talk on concolic testing, Koushik Sen
Summary of DART, Koushik Sen
Summary of CUTE, Koushik Sen
Automated Whitebox Fuzz Testing with SAGE, Patrice Godefroid
A Lab exercise, Koushik Sen

If you are looking to develop your understanding by starting from a security context, I recommend this excellent summary of pointers to program analysis material from the Reverse Engineering reddit.


Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness? Assume that for a given minimization problem with only integer solutions, it is $NP$-hard to decide if the optimal solution is 5 or 6. I.e., a polynomial-time algorithm with an approximation ratio better than 6/5 would imply $P=NP$.

1) Does this imply that the problem is $APX$-hard as well?

2) Is there a common way of stating this inapproximability fact, besides stating that "it is $NP$-hard to approximate with an approximation ratio strictly better than 6/5"?

Thank you!

The answer for (1) is "unlikely".

It is simple to show (reduce from $Partition$) there exists no $\alpha$-approximation for Bin Packing, for any $\alpha<\frac{3}{2}$, unless $P=NP$.

That said, Crescenzi et al. have shown that unless the polynomial hierarchy collapses, Bin Packing is not APX-Hard.

As for (2), perhaps you could phrase it as "Does not admit $PTAS$ unless $P=NP$".


Three questions about finite state machines Suppose a finite state machine, FSM, has a fixed set of states $S$ and input/output channels $C$, and is uniquely specified by the fixed map $m : S\times D \to S\times D\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it enters a loop and cant exit.

Clearly, if we join together pairwise any of the input/output channels of one or more FSM's, we obtain a new FSM.

Is there a finite set of FSM's, by which any other FSM can be built (using a finite number of each), by connecting channels pairwise?

Can every FSM be built by the two state, 3 channel, FSMs specified by the map:
(A,1)->(B,2),(B,2)->(A,1),(B,1)->(B,1),(A,2)->(C,1),(C,1)->(A,2),(C,2)->(C,2)

Is there a general algorithm, given a set of FSMs, and a target FSM, to determine if the target can be built by any combination of any number of FSM's in the set?

No there are some FSA which are irreducible, I believe the 2 state 3 input FSA you give is the flip-flop, every reducible FSA can be made by this one. Start by looking here and the references given http://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory


Is there a candidate for a natural problem in $P/poly - P$? I want to know if non-uniformity helps computing functions in practice. It is easy to show that there are functions in $P/poly - P$, take any uncomputable function $f$ and consider the language {$0^{f(n)}:n\in \omega$}, which clearly has simple non-uniform circuits, but is not computable uniformly at all, but this is not the kind of functions I am interested in.

Is there a function that we know it can be computed non-uniformly but we don't know if it can be computed uniformly (or at least proving that it can not be computed uniformly is not obvious)?
How can non-uniformity of circuits be used for computing functions that are not known to be computable uniformly (with almost the same amount of resources)?

Please note that I don't want pathological functions like uncomputable one mentioned above, I want natural functions that people are really interested in computing and it is plausible that can be or could have been computed uniformly.
Edit:
I know that $BPP \subseteq P/poly$. So an answer which is not a derandomizations result is more interesting for me.
Edit 2:
As András Salamon and Tsuyoshi Ito have said in their answers, $Sparse \subset P/poly$, and there are interesting problems in $Sparse$ that are not known to be in $P$, so formally they have answered what I have asked, but that does not help with what I am really interested in since the reason that they are in $P/poly$ is the possibility of hard coding a sparse language into the circuit. A language which is not sparse would be more interesting.

I do not know if this satisfies your requirements, but Bill Gasarch’s blog post in July 2010 asks about languages in SPARSE∩NP which are not thought to be in P, giving an example from Ramsey Theory.  Any such languages belong to (P/poly)∩NP.

Related to this, For any language L∈NP, the language TL={1n: L contains some string of length n} is in TALLY∩NP ⊆ SPARSE∩NP ⊆ (P/poly)∩NP.  Depending on the choice of the language L, TL may not have an obvious reason to belong to P.


Algorithms for creating a directed network with a given 3-node motifs distribution I am looking for algorithms to create directed networks with an arbitrary distribution of 3-node network motifs (i.e. subgraphs of the order 3), see this picture from O. Sporns, R. Kotter, Motifs in Brain Networks, (2004).

It should work in a reasonable time for up to 10,000 nodes with total graph density of $p=0.1$ (probability of every connection + no self-connectivity). Of course, some distributions are impossible because motifs in the network overlap with each other. Thus, it should work for distributions relatively close to a random-network distribution  (let's say, it should give a result for input motif numbers of $50-200\%$ of mean numbers in random networks).

As I understand, you are interested in an approximate solution. I have two heuristic ideas, maybe they can serve as a starting point.

However, if you want more (e.g. randomness in the Haar-measure sense or fixing other properties (graph diameter, spectrum, number of connected components, ...)) they are not sufficient.

Rewiring

Especially when you want to have distributions of network motifs close to a 'random' one.

Generate a graph with desired distribution of in-degrees and out-degrees.
For each pair of nodes $(x,y)$ calculate the number of each motif $m_i(x,y)$
Now, in each step:

Randomly draw two edges.
Perform rewiring (i.e. $(a\rightarrow b, c \rightarrow d) \mapsto (a\rightarrow d, c \rightarrow b) $) if it is possible and if it results in distribution of motifs closer to the desired one (e.g. in the sense of the Kullback-Leibler divergence or perhaps the Euclidian distance). Modify $4\times13$ affected $m_i(x,y)$.

As variance is of order $\sqrt{n}$, each rewiring takes a fixed time, you need roughly $n^3/\sqrt{n}$ steps, so I guess that it should scale as $O(n^{2.5})$.

Addition

Alternatively, you can try to add edges to an empty graph in such way it produces the desired distribution. Also, one need to hold $m_i(x,y)$.

For each step one randomly draws a pair of nodes and put an edge if it results in a desired distribution at this step (perhaps with some randomness).

Then the time cost is $O(n^2)$ (or rather $O(\#\text{edges})$ ), so better by $\sqrt{n}$ than the rewiring.

The tricky part is to calculate the desired distribution at each step (or rather - at each edge count). For example, even if one wants to have only $(\bullet\leftrightarrows \bullet\quad \bullet)$ and $(\bullet\quad \bullet\quad \bullet)$ 3-motifs, then when starting one needs to create mostly $(\bullet\rightarrow \bullet\quad \bullet)$ 3-motifs.

I would guess that the desired distribution at a given edge count $E$ is the one resulting from the final motif distribution with removed edges with the probability $1-\frac{E}{E_{final}}$.


Transition monoid membership for DFAs Given a complete DFA $A=(Q, \Gamma, \delta, F)$, we can define a collection of functions $f_a$ for each $a\in \Gamma$and with $f_a:Q\rightarrow Q$, $f_a(q)=\delta(q, a)$. We can generalize this notion to a word $w=a_1, \cdots, a_m$ and $f_w=f_{a_1}\circ \cdots \circ f_{a_m}$ where $\circ$ denotes function composition. Furthermore we denote $G=\{f_w\mid w\in \Gamma^*\}$ and $G$ is monoid.

[$G$ is usually called transition monoid in the standard textbook, but here I reproduce the definition for clarity.]

The question is, given a function $f:Q\rightarrow Q$, can we decide $f\in G$ (ideally in polynomial time), and if this is the case (i.e., there exists a $w$ such that $f=f_w$), whether $w$ is only polynomially long, or can be exponentially long?

[I guess that indeed such a word could be exponentially long, but I am looking for a simple example.]

Decidability

It's decidable.  There are only finitely many possible functions $f:Q \to Q$, so you can model this as a graph reachability problem, with one vertex per function and an edge $g \to h$ if there exists $a \in \Gamma$ such that $h = f_a \circ g$.  Then, testing whether a function $g$ is in $G$ reduces to testing whether $g$ is reachable in the graph from $f_\epsilon$.  You can find the shortest such word using breadth-first time.  The running time might be exponential in $Q$, though.

Length of the word

The shortest such word might be exponentially long.  Here is an example of such a DFA.  Let $p_1,\dots,p_k$ be the first $k$ primes.  Then a state will be of the form $(i,x)$ where $i \in \{1,\dots,k\}$ and $x_i \in \{0,1,\dots,p_i-1\}$.  Define a DFA with unary alphabet $\Gamma=\{0\}$ and the transition function $\delta((i,x),0 = (i,x+1 \bmod p_i)$.  The function $f_0 :Q \to Q$ is given by

$$f_0(i,x) = (i,x+1 \bmod p_i).$$

Now consider the function $g:Q \to Q$ given by

$$g(i,x) = (i,x-1 \bmod p_i).$$

It is possible to use the Chinese remainder theorem to show that $g = f_{0^n}$ where $n=p_1 \times p_2 \times \cdots \times p_k -1$, and that $0^n$ is the shortest such word.  Moreover, $|Q|= p_1 + \dots + p_k$, so $n$ is exponentially large in $Q$.

Consequently, there is no hope for a polynomial-time algorithm that outputs such a word.  This still leaves open the possibility of a polynomial time algorithm for deciding whether $g$ is in $G$, though.


Would a purely topological computational model be useful in decision problems in topology? If one were to develop a purely topological computational model based upon the equivalence of information in knots and the model would perform transformations of that information. This would be the way that model would compute. Would such a model be useful in understanding computational problems in topology or would algebraic models suffice? If one already exists please provide a reference.

Avishy Carmi and Daniel Moskovich have been developing tangle machines very recently, which is a topological model to describe information. There are two papers on the arXiv, as well as three introductory posts on the blog "Low Dimensional Topology" :

http://ldtopology.wordpress.com/2014/05/04/low-dimensional-topology-of-information/


Hardness of node partitioning under shortest path constraint Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \in R$ (negative weight is possible). A label $l(i)$ is associated with each node $i \in V$. How to assign $k$ (or less) distinctive values to $l(i)$ such that
$$l(j) \leq l(i) + w(i,j),\quad \forall (i,j) \in E ?$$
Notice that when $k=|V|$, this problem is easily solvable by Shortest path algorithm (Bellman-Ford). But what's the hardness is this problem for $k < |V|$?

Let’s call an assignment of vertex labels feasible if it satisfies all the inequality constraints, ignoring the condition on the number of distinct labels.

Here is what I think is a proof that it is NP-complete to decide whether a given directed graph G=(V, E) with integer (possibly negative) edge weights has a feasible assignment of labels which uses at most k distinct labels, for k=|V|/2.  We construct a reduction from the following NP-complete problem [WY92].

Equal Subset Sum
Instance: A finite set S of positive integers.
Question: Do there exist two disjoint nonempty subsets S1 and S2 of S whose sums are equal to each other?

Let S={a1, …, an} be a set of positive integers, where n=|S|.  Construct a directed graph G with 2n vertices u1, …, un, v1, …, vn by connecting ui and vi in both directions for each i.  Give the weight ai to the edge (ui, vi) and −ai to the edge (vi, ui).

Consider the instance (G, n) of the current problem.  Note that an assignment l of labels is feasible if and only if for each i, it holds l(vi)=l(ui)+ai.  From this, we can prove the following, establishing that the above transformation is a reduction from Equal Subset Sum to the current problem.

Claim.  G has a feasible assignment which uses at most n distinct labels if and only if there exist two disjoint nonempty subsets S1 and S2 of S whose sums are equal to each other.

Proof.  First observe that if we are given a feasible assignment l (which might use any number of distinct labels), we can construct a directed graph Hl from G by removing the edges with negative weights and merging vertices with equal labels.  Note that Hl has exactly n edges whose weights are a1, …, an.  Also, note that the number of vertices of Hl is equal to the number of distinct labels used in l.

For the “only if” direction, given a feasible assignment l which uses at most n distinct labels, consider the directed graph Hl.  Since Hl has at most n vertices and exactly n edges, Hl contains a cycle C ignoring the direction of edges.  Let S1 be the set of weights of edges appearing in C in one direction, and S2 be the set of weights of edges appearing in C in the other direction.  It is easy to see that the sum of S1 is equal to the sum of S2.

For the “if” direction, fix S1 and S2 be the subsets of S satisfying the condition.  Without loss of generality, assume that S1={a1, a2, …, as} and S2={as+1, as+2, …, as+t}, where s=|S1| and t=|S2|.  Then we assign the following labels to the vertices of G:

l(u1)=l(us+1)=0.
l(ui)=l(vi−1) for 2≤i≤s and s+2≤i≤s+t.
l(ui)=0 for s+t+1≤i≤n.
l(vi)=l(ui)+ai for 1≤i≤n.

It is easy to verify that this assignment is feasible and uses at most n distinct labels.  (The graph Hl in this case consists of two edge-disjoint paths from the vertex labeled 0 to the vertex labeled $\sum_{i=1}^s a_i = \sum_{i=s+1}^{s+t} a_i$ and n−s−t edges originating at the vertex labeled 0.)  QED.

References

[WY92] Gerhard J. Woeginger and Zhongliang Yu.  On the equal-subset-sum problem.  Information Processing Letters, 42(6):299–302, July 1992.  http://dx.doi.org/10.1016/0020-0190(92)90226-L


GI-hard graph problem not known to be $NP$-complete Graph Isomorphism ($GI$) is good candidate for $NP$-intermediate problem. $NP$-intermediate problems exist unless $P=NP$. I'm looking for natural problem that is hard for $GI$ under Karp reduction (A graph problem $X$ such that $GI <_p^m X$).

  Is there a natural $GI$-hard graph problem that is neither $GI$-equivalent nor known to be $NP$-complete?

After extensive search, I found the Legitimate Vertex Deck problem (LVD) which is related to the famous Graph Reconstruction conjecture. A deck of graph $G(V, E)$ is a multi-set of graphs $F = \{G_1,G_2, . . . , G_n\}$ such that $G_i$ is isomorphic to $G−v_i$ ($G-v$ is a graph obtained from $G$ by removing $v$ and its incident edges). ($|V|=n$)

The k-LEGITIMATE VERTEX-SUBDECK problem, given multi-set of graphs $F= \{G_1,G_2, . . . , G_k\}$, Decide whether there is a graph $G$ such that $F$ is a subset of its vertex-deck (k-LVD =$ \{[G_1, . . . , G_k]|(∃G)[[G_1, . . . , G_k] ⊆ vertex-deck(G)]\}$)
where $k \ge 3$

k-LVD problem is $GI$-hard and is not known to be $GI$-equivalent. It is open problem whether k-LVD is $NP$-complete (for $k \ge 3$). See the open problems section of Complexity results in graph reconstruction.

Also, the paper suggests the existence of a problem of intermediate complexity between $GI$ and k-LVD. The problem is LVD= n-LVD where all $n$ candidate cards are given (Input for LVD is $F= \{G_1,G_2, . . . , G_n \})$.


Computational Model in SETH Impagliazzo, Paturi and Calabro, Impagliazzo, Paturi introduced Exponential-Time Hypothesis (ETH) and Strongly Exponential-Time Hypothesis (SETH). Roughly, SETH says that there is no algorithm which solves SAT in time $1.99^n$.

I was wondering what would that mean to break SETH. We definitely need to find an algorithm which solves SAT in fewer than $2^n$ steps, but I don't quite understand what computational model we should use. As far as I know, results based on SETH (see, e.g., Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, Wahlstrom) don't need to make assumptions about the underlying model of computation.

Assume, for example, that we found an algorithm which solves SAT in time $1.5^n$ using space $1.5^n$. Does it automatically imply that we can find a Turing Machine which solves this problem in time $1.99^n$? Does it break SETH?

SETH says that for all $\delta < 1$ there is a $k$ such that $k$-SAT requires $2^{\delta n}$ time to be solved in the worst-case. The computational model is generally taken to be the random-access machine or pointer machine model, which allows for $O(\log N)$ time access to a storage of $N$ items, and is generally assumed to also be probabilistic with bounded error.

As far as I know, it is open whether $2^{\delta n}$ time algorithms on such a model can be translated into two-tape Turing machines running in $2^{\delta n} \cdot poly(n)$ time. Nevertheless, proving that such a translation is not possible would separate multitape Turing machines from random access machines, which would have several very intriguing implications. For one, it would prove that SAT is not solvable in quasi-linear time on multitape Turing machines (because, if SAT could be solved with such multitape machines, then random-access machines can be efficiently simulated with multitape Turing machines). Note that many computational primitives (such as sorting, circuit evaluation, simple dynamic programming) can be implemented efficiently on multitape Turing machines. One relevant reference for these issues is Regan, "On the Difference Between Turing Machine Time and Random-Access Machine Time."

To address your specific questions: no, a multitape Turing machine is not automatically implied here, but yes, such an "algorithm" for SAT (under the usual random-access model) would break SETH.


Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in? A recent question asks whether relativization is well-defined. This question wonders how to put one use of it on firmer ground.

  In the BGS 1975 proof that there exists a language $B$ such that $P^B \neq NP^B$. To best available knowledge, what complexity class is $B$ in?
  Fill in the blank ("$?$") if possible, or analyze as best possible: if there existed a $B'$ in class "$?$" such that $P^{B'} \neq NP^{B'}$, then $P \neq NP$.

For question 1, the BGS construction can be performed in exponential time, so you can construct such $B \in \mathsf{EXP}$.

(For question 2: Sasho Nikolov's answer was originally only for $\mathsf{\Sigma_k P}$-complete languages, and I pointed out that one can also take any $B' \in \mathsf{NP} \cap \mathsf{coNP}$, since $\mathsf{NP}^{\mathsf{NP} \cap \mathsf{coNP}} = \mathsf{NP}$. But Sasho's updated answer subsumes this case.)


Longest stack-sortable subsequence Given an array of $n$ pairwise-different positive integers, the problem is to find the longest subsequence that is stack-sortable, i.e. avoiding the permutation pattern $231$.

How fast can this problem be solved? Can it be solved in polynomial time and linear space?

There's a polynomial-time dynamic programming algorithm in section 3.2 of https://ajc.maths.uq.edu.au/pdf/28/ajc_v28_p225.pdf (Albert et al, "Longest subsequences in permutations", Australas. J. Combin. 28 (2003), 225–238)


Advances in program verification? While trying to check what is the state of art in formal verification, it seemed to me that there were actually no breakthroughs in decades. For example, here http://www.comp.nus.edu.sg/~hobor/Publications/2011/logicfs.pdf it is stated, that 5-line (imperative) factorial program needs something like 100 lines of Coq code. And I consider Coq to be one of the best tools out there! Adam Chlipala's book (http://adam.chlipala.net/cpdt/) tries to convince, that Coq is much easier, than many think.

So, the first question goes, are there any advances in the field (and what they are), which would make formal methods practical any time soon?

If no, then has any researcher explained this seeming discrepancy between the fact, that programming languages become easier to use (become higher and higher level, handle specific domains better), while formal verification methods seemingly remain in the seventies of last century? (I guess, on the functional programming front situation is a bit better, but still.)

My own speculation on this paradox is that maybe some fundamental, powerful computation formalism is yet to be discovered (that is, the problem lays with the language). Another answer could be, that the complexity gap is inherent in the mathematics, and no development of the theory could destroy it. Personally, I do not believe in the latter case, because all the history of development in mathematics. Added: Third possibility is that for some reason re-use of formal proofs and tactics, finding new axioms is difficult. In "normal" software it is possible to share libraries, which are used to build more complex structures, and these components are stacked together to form even bigger systems. "Normal" software is times easier to develop now than 30-40 years ago.

Would be interesting to know, if I have overlooked something.

EDIT: It may well be, that some narrow problem domains enjoy nice, easy-to-use verification tools, for example, languages with regular grammars may be easy to deal with. This question is not about such cases.

To narrow my question, lets consider one toy example, which is surely broadly known, and which I consider general enough kind of programming problem. Suppose, I want to implement an ADT Queue using two Stacks (another ADT). I write down a solution (it's a couple of methods: enqueue and dequeue). Now, I want a formal proof, that my solution is indeed a Queue (suppose, I have some kind of description of it's behavior). I can program it from assembler to, say, APL and get a size from 2 lines to 100. Now, how long will be the proof? I bet, it's about a page on paper. But what if I have semi-automatic tool? I guess, the proof will be (for imperative case) almost as long as assembler program, will need several insights to come with and the result is much more cryptic in case one needs to manually re-check. And of course, I am not sure how type-checking is going to help in this case.

EDIT2: Some notable results from comments, thanks to commenters:

Conflict-Driven Clause Learning - makes SAT powerful (year 1999)
Separation Logic - "local reasoning" (2002)

The powerful formalism you are looking for cannot exist, for otherwise we could solve the halting problem. Here is the sketch of an argument why.

Consider Hoare triples $\{A\} P \{B\}$ for partial correctness. If  we had a (computable) upper bound that related program length to the lengths of correctness proofs, then we could apply it to the  assertion

$$\{\mathsf{True}\} P \{\mathsf{False}\}.$$

This assertion is true exactly when $P$ loops. Since we have assumed a (computable) upper bound for proof length, we can find such a proof, were it to exist, in finite time by brute force search, giving an algorithms for deciding the halting problem. Contradiction. The argument can be adapted for other formal methods.

That means, regardless of the specifics, there will always be short programs with long proofs.  One way to find such programs is to look at difficult or open number theoretic questions like Fermat's last theorem or the twin prime conjecture: you can write short programs that diagonialise over the natural numbers, looking for counterexamples. Proving that such programs  do or do not terminate is likely to be highly involved.

All that being said, the last decade has seen an explosion of work on formal verification and a great deal of progress.


Super Mario Galaxy problem Suppose Mario is walking on the surface of a planet.  If he starts walking from a known location, in a fixed direction, for a predetermined distance, how quickly can we determine where he will stop?

More formally, suppose we are given a convex polytope $P$ in 3-space, a starting point $s$ on the surface of $P$, a direction vector $v$ (in the plane of some facet containing $p$), and a distance $\ell$.  How quickly can we determine which facet of $P$ Mario will stop inside?  (As a technical point, assume that if Mario walks into a vertex of $P$, he immediately explodes; fortunately, this almost never happens.)

Or if you prefer: suppose we are given the polytope $P$, the source point $s$, and the direction vector $v$ in advance.  After preprocessing, how quickly can we answer the question for a given distance $\ell$?

It's easy to simply trace Mario's footsteps, especially if $P$ has only triangular facets.  Whenever Mario enters a facet through one of its edges, we can determine in $O(1)$ time which of the other two edges he must leave through.  Although the running time of this algorithm is only linear in the number of edge-crossings, it's unbounded as a function of the input size, because the distance $\ell$ could be arbitrarily larger than the diameter of $P$.  Can we do better?

(In practice, the path length isn't actually unbounded; there is a global upper bound in terms of the number of bits needed to represent the input.  But insisting on integer inputs raises some rather nasty numerical issues — How do we compute exactly where to stop? — so let's stick to real inputs and exact real arithmetic.)

Is anything nontrivial known about the complexity of this problem?

Update: In light of julkiewicz's comment, it seems clear that a real-RAM running time bounded purely in terms of $n$ (the complexity of the polytope) is impossible.  Consider the special case of a two-sided unit square $[0,1]^2$, with Mario starting at $(0,1/2)$ and walking in direction $(1,0)$.  Mario will stop on the front or the back of the square depending on the parity of the integer $\lfloor \ell \rfloor$.  We can't compute the floor function in constant time on the real RAM, unless we're happy equating PSPACE and P.  But we can compute $\lfloor \ell \rfloor$ in $O(\log \ell)$ time by exponential search, which is an exponential improvement over the naive algorithm.  Is time polynomial in $n$ and $\log \ell$ always achievable?

This problem is very very difficult.  We could simplify it to make it easier, as follows.

We can add the assumption that the angle sum about every vertex of the polytope $P$ is a rational multiple of $\pi$.  This gets rid of most "polytopes" but there are still many interesting possibilities: for example, the platonic solids.
We can assume that the polytope is not truly three-dimensional, but instead is the "double" of a polygon; this looks a bit like a pillowcase. We can simplify even further and suppose that the polygon has equal and parallel sides; for example a square, as in the game Astroids.

If we make both of these assumptions then there is a large theory.  (Finding an $O(\log(\ell))$ algorithm for the square is a difficult exercise involving the continued fraction expansion of the angle of Mario's path.  To achieve a similar result for the regular octagon is possible but harder.  The solutions for the square and the octagon involve thinking about how to efficiently encode a "cutting sequences for a geodesic on a translation surface".  Most other rational polygons will quickly lead to open problems.)  An initial reference, which includes a further reference to Caroline Series's discussion of the square torus, are these talk slides by Diana Davis.

If we do not assume rationality, but do assume that the polytope is the double of a polygon, then we are discussing the theory of "cutting sequences in irrational billiards".  It seems that essentially nothing is known here; for example see the final sentence of this talk by Corinna Ulcigrai.

If we make neither assumption, well, I can't think of anything in the literature.

Finally - I'll guess that there is an $O(\log(\ell))$ solution to the Super Mario Galaxy problem for the platonic solids.  This is a good problem for a graduate student getting started in rational billiards.  For example, the case of the dodecahedron "should" follow from Diana Davis's thesis.  (But start with the tetrahedron - that will follow from an analysis of cutting sequences for the hexagonal torus.)


What is the status of fuzzy logic for TCS in 2011? I am reviewing the Handbook of Nature-Inspired and Innovative Computing for SIGACT News.  It's a very interesting read.  Each chapter, though, has the flavor, "This is my research area, and damn it's awesome!"  So part of what I am trying to do is to separate out the hype, and make a sober assessment of the book's contents.

One chapter is on fuzzy logic and fuzzy systems, and how frikkin awesome they are.  And maybe they are, I frankly don't know.  The intuitive sense I've gotten from hanging around computer scientists is that fuzzy logic and fuzzy modeling of control systems, etc., are "dead."  I don't know if that's true, though -- and, even if it is true, I don't know if it's true for a "good reason."

Would anyone like to weigh in here?  What's the current status of research into fuzzy systems?  Does fuzzification see real-world applications?  Did it used to and people moved away because of problems?  Or do people "in the trenches" use it all the time, and it's just that theorists have moved away from it?  Or... something else?  (I have no idea what is true.)

I will probably cite answers to this question in the book review, unless an answerer specifically asks me not to.

Thanks.

I wouldn't consider fuzzy logic dead. For control systems, I don't know. However, there's been a lot of activity in fuzzy logics for proof theorists for the last several years: look for papers by Ciabattoni, Olivetti, Fermüller, Metcalfe, and Baaz for starters.

Edit: Some specific references from my BibTeX file:

D. Galmiche and Y. Sahli, Labelled Calculi for Łukasiewicz Logics, Int. Workshop on Logic, Language, Information and Computation, WoLLIC'08, Edinburgh, LNAI 5110, 2008.
M. Baaz and G. Metcalfe, Proof Theory for First Order Łukasiewicz Logic. TABLEAUX 2007.
D. Galmiche and D. Larchey-Wendling and Y. Salhi, Provability and Countermodels in Gödel-Dummett Logics, DISPROVING'07: Workshop on Disproving Non-Theorems, Non-Validity, and Non-Provability, 2007.
S. Bova and F. Montagna, Proof search in Häjek's Basic Logic, ACM Trans. Comput. Log., 2007.
D.M. Gabbay and G. Metcalfe, Fuzzy logics based on [0,1)-continuous uninorms, AML 46(5), 2007.
G. Metcalfe and F. Montagna, Substructural fuzzy logics. JSL 72(3), 2007.
R. Dyckhoff and S. Negri, Decision methods for linearly ordered {H}eyting algebras. AML 45, 2006.
G. Metcalfe and N. Olivetti and D. Gabbay, Sequent and Hypersequent calculi for Abelian and Łukasiewicz Logics. ACM Trans. Comput. Log. 6(3), 2005.
M. Baaz and A. Ciabattoni and F. Montagna, Analytic calculi for monoidal t-norm based logic, Fund. Inf. 59(4), 2004.
S. Negri and J. van Plato, Proof systems for lattice theory, Math. Struct. in Comp. Science 14(4), 2004.
A. Ciabattoni and
           C.G. Fermüller and
           G. Metcalfe, Uniform Rules and Dialogue Games for Fuzzy Logics. LPAR 2004.
A. Ciabattoni, Automated Generation of Analytic Calculi for Logics with
           Linearity. CSL 2004.
F. Montagna and L. Saccetti, Kripke-style semantics for many-valued logics, Math. Log. Q. 49(6), 2003. Correction in MLQ 50(1), 2004.
D. Larchey-Wendling, Countermodel search in Gödel-Dummett logics, IJCAR 2004, LNAI 3097, Springer, 2004.
G. Metcalfe, Proof Theory for Propositional Fuzzy Logics, PhD Thesis, Department of Computer Science, King's College, 2004.
D. Gabbay and G. Metcalfe and N. Olivetti, Hypersequents and Fuzzy Logic, Revista de la Real Academia de Ciencias 98(1), 2004.
A. Ciabattoni and G. Metcalfe, Bounded Łukasiewicz Logics. TABLEAUX 2003.
M. Baaz and
           A. Ciabattoni and
           C. G. Fermüller, ypersequent Calculi for Gödel Logics---a Survey. JLC 13(6), 2003.
M. Baaz and
           A. Ciabattoni and
           C. G. Fermüller, Sequent of Relations Calculi: A Framework for Analytic Deduction in Many-Valued Logics. Beyond Two: Theory and Applications of Multiple-Valued Logic, M. Fitting and E. Orlowska, eds., Physica-Verlag, 2003.
N. Olivetti, Tableaux for Łukasiwicz Infinite Valued Logic. Studia Logica  73(1), 2003.
G. Metcalfe and N. Olivetti and D. Gabbay, Analytic Sequent Calculi for Abelian and Łukasiewicz Logics. TABLEAUX 2002.
A. Ciabattoni and C. G. Fermüller, Hypersequents as a Uniform Framework for Urquhart's C, MTL and Related Logics.Proceedings of the 31th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2001), 2001.
F. Esteva and L. Godo, Monoidal t-norm based logic: towards a logic for
       left-continuous t-norms, Fuzzy Sets and Systems 124(3), 2001.
M. Baaz and R. Zach, Hypersequent and the Proof Theory of Intuitionistic Fuzzy
           Logic. CSL 2000.
A. Avron, A Tableau System for Gödel-Dummett Logic Based on a
           Hypersequent Calculus. TABLEAUX 2000, LNAI 1847, 2000.
A. Ciabattoni and M. Ferrari, Hypertableau and Path-Hypertableau Calculi for some families of intermediate logics. TABLEAUX 2000, LNAI 1847, 2000.
R.L.O. Cignoli and I.M.L. D'Ottaviano and D. Mundici, Algebraic Foundations of Many-Valued Reasoning, Kluwer, London, 2000.
S. Aguzzoli and A. Ciabattoni, Finiteness in Infinite-Valued Łukasiewicz Logic. J. Logic, Language and Information 9, 2000.
R. Dyckhoff, A Deterministic Terminating Sequent Calculus for Gödel-Dummett logic, IGPL 7(3), 1999.
M. Baaz and
           A. Ciabattoni and
           C. G. Ferm{\"u}ller and
           H. Veith, Proof Theory of Fuzzy Logics: Urquhart's C and Related Logics. Mathematical Foundations of Computer Science 1998, 23rd
           International Symposium, MFCS'98, Brno, Czech Republic,
           August 24-28, 1998, Proceedings, 1998.
P. Häjek, Metamathematics of Fuzzy Logics, Kluer, 1998.
R. Hähnle, Proof theory of many-valued logic--linear optimization--logic
           design: connections and interactions. Soft Comput. 1(3), 1997.

These are largely proof-theory and automated deduction references, though,


Simple and cache-oblivious tries on fixed-length strings Is there a simple and cache-oblivious data structure that solves the dynamic predecessor problem for strings of length exactly $k$ over an alphabet $A$ in worst-case $O((k\log A)/B + \log n)$ memory transfers and $O(k\log A)$ letter comparisons, where $B$ is the block size?

By predecessor problem I mean the problem of maintaining a set under insertion, deletion, and predecessor, where predecessor(k) finds the largest key in the set that is $\leq k$.

Ternary search trees achieve the letter comparison bound and are very simple, but can require $\Theta(k\log A)$ memory transfers.

String B-trees do better than the I/O bound I'm looking for, but they are not simple, and the cache-oblivious ones are even more complex and do not achieve the I/O bound in the worst-case. (String B-trees might achieve the comparison bound I'm looking for; I'm not sure.)

My intuition is that by fixing the size of the keys and relaxing the I/O bound, a simpler structure might be possible.

Update: An idea very similar to this one is described in "Digital Access to Comparison-Based Tree Data Structures and Algorithms".

Here's an idea for a structure that might meet these bounds.
It uses an balanced binary search tree where each node is annotated with a pair of integers in $[-1,k-1]$ to indicate how much of the prefix of the key does not need to be compared again with the search key.

Notation

A shared prefix pair is a pair of integers associated with a key, called the focus, and a set of string keys not containing the focus, called the context.
For a focus $f$ and context $c$, if $\forall y \in c, f < y$, then the left shared prefix (the left value in the shared prefix pair) of $f$ and $c$ is $-1$.
Otherwise, let $g$ be the largest key in $c$ such that $g < f$.
This is called the left neighbor of $f$ in $c$.
Then the left shared prefix $i$ is the largest integer such that $f[i] > g[i]$ and $\forall j < i, f[j] = g[j]$.
The right shared prefix and right neighbor are defined symmetrically.

Search

Annotate each node in a balanced binary search tree with a shared prefix pair, using the key at that node as the focus and they keys of its ancestors in the tree as the context.
I'll first describe how to search for a string key (the needle, as in "needle in a haystack") in an annotated tree, then describe insertion and deletion.

During search, maintain a shared prefix pair with the needle as the focus and the keys of the nodes inspected during the search as the context.
By the definition above, we start with a shared prefix pair of $(-1,-1)$.

Assume we are searching for the needle $d$ with shared prefix pair $(i,j)$ in a tree with root $v$ with key $z$ and shared prefix pair $(p,q)$.
Since the search proceeds from parent to child, the prefix pairs share the same context and the same left and right neighbors, $a$ and $b$.

Now, if $i < p$, then $z[i] = a[i] < d[i]$, and $z < d$.
In this case, the search proceeds recursively to the right child of $v$.
$z$ is the new left neighbor of $d$ and $d$'s prefix pair stays the same.

If $i > p$, then $d[p] = a[p] < z[p]$, and $d < z$.
In this case, the search proceeds recursively to the left child of $v$.
$z$ is $d$'s new right neighbor and $p$ is the new right shared prefix of $d$.

For $j \neq q$, proceed similarly.

In the remaining case, $i = p$ and $j = q$.
Assume w.l.o.g., that $i \geq j$.
Find the first $i^{\prime} > i$ such that $d[i^{\prime}] \neq z[i^{\prime}]$ but $\forall n < i^{\prime}, d[n] = z[n]$.
If $d[i^{\prime}] < z[i^{\prime}]$, then $d < z$, so proceed to the left child of $v$.
The new right neighbor of $d$ is $z$ and the new right shared prefix of $d$ is $i^{\prime}$.
If $d[i^{\prime}] > z[i^{\prime}]$, then $d > z$, so proceed to the right; $z$ is the new left neighbor of $d$, and $i^{\prime}$ is $d$'s new left shared prefix.
The $j > i$ case is symmetric.

Search Performance

Letters are not compared unless $i=p$ and $j=q$.
At each step in which letters are compared, either the sum of the shared prefix pair increases or only one letter comparison is made.
We will discuss these two separately.

If only one letter comparison is made, a child pointer is immediately followed.
Since paths from the root to leaves are $O(\lg n)$ and $n \leq A^k$, fewer than $O(k \lg A)$ single-letter-comparison steps are taken.

If $p > 1$ letter comparisons are made in a step, the sum $i+j$ of the shared prefix pair increases by at least $p-1$.
Since the maximum possible sum is $2k$, $O(k)$ letter comparisons are made in comparisons that result in larger shared prefix pair sums.
However, shared prefix pair sums may seemingly decrease in non-letter-comparison steps when $i > p$ and $j$ is replaced by $p$ or $j > q$ and $i$ is replaced by $q$.
This is not the case, though:
If $i > p$ then $d < z$, so $j \leq q$.
If $j < q$, then $d$'s new right shared prefix is $j$, so $j = p$ and the shared prefix pair sum is not decreased.
Similarly, if $j = q$, then $d$'s new right shared prefix is $\geq j$, and the sum is not decreased.

Similarly, each step requires $O(1+p/B)$ block transfers if it makes $p-1$ letter comparisons.

Insertion and Deletion

To perform an insertion, first locate where the node with the key $d$ would be found if it were in the tree.
After modification, perform the necessary $O(\log n)$ restructuring necessary to restore balance.
Rotations might invalidate shared prefix pairs.

Consider the case of a left rotation:

  B
 / \
A   D
   / \
  C   E

    D
   / \
  B   E
 / \
A   C

The shared prefix pairs at A, C, and E all remain valid.
The left shared prefix of B and the right shared prefix of D also remain valid.
The right shared prefix at B is the left shared prefix at D from before the rotation.
The left shared prefix of D is the minimum of the left shared prefixes of D and B from before the rotation.

The right rotation and deletion cases are the same, mutatis mutandis.


How hard is it to learn a linear modular function? Let $k$ be a fixed number.
Consider the following task $Q$:

  We are given a sequence of numbers $(x_0,x_1,\cdots,x_k)$. We know they satisfy $x_{k+1}=f(x_k)$, and $f(x)=(ax+b \mod p) \mod m$ where $a,b,m,p \in [2^n]$ are some unknown values.
  The task is to find $f$.

I have a couple of questions about this problem:

How hard is this problem?
If we choose $a,b,p,m$ randomly but "wisely" will $f$ be a pseudorandom number generator secure against TC0 or AC0 circuits?
What is the smallest value of $k$ where $Q$ can be solved?
What is the fastest known algorithm for $Q$?

I assume you want an efficient algorithm, e.g., one whose running time is polynomial in $n$.  (If you don't care about running time, then heuristically about $4n/\lg m$ samples should suffice to uniquely determine $a,b,m,p$, and you can use exhaustive search over all possible $2^{4n}$ parameter choices to find the correct one.  Of course, the running time of this method is exponential in $n$, so I assume it is not what you are looking for.)

In the case where $p=m$, this generator is known as a linear congruential generator.  It is known to be weak.  See my answer to Cracking a linear congruential generator (on IT Security.Stack Exchange) for an efficient algorithm that breaks this pseudorandom generator.

To summarize the  security of the generator (when $p=m$): A constant number of samples is enough to break the generator.  The algorithm requires only simple arithmetic and requires only a constant number of additions and multiplications, followed by a gcd operation.  I don't know whether this generator going to be pseudorandom for any particular complexity class, like TC0 or AC0; perhaps others will have insights on that.

Note that if you are picky about requiring a cryptanalysis algorithm to succeed with probability 1, and run in polynomial time without any randomness, then you won't like my algorithm.  My algorithm runs in polynomial time, and succeeds in recovering $f$ on an overwhelming majority of inputs; as a consequence, it succeeds in distinguishing the output of this pseudorandom generator from a true-random stream with advantage close to 1.  In the cryptographic world, this constitutes a "break" of the security of the generator.  However, if you wanted a learning algorithm that succeeds (in recovering $f$) on all problem instances, and has a fixed running time, my algorithm isn't it.  (Then again, from an engineering perspective, if you want something that is guaranteed to succeed on all problem instances, you won't find it, since any real-life implementation always has some small chance of producing an incorrect answer, e.g., due to a cosmic-ray bit flip.  My algorithm infers $f$ correctly for all but an exponentially small fraction of inputs. You can choose parameters so the probability of error due to unlucky choice of inputs is smaller than the probability of error due to a cosmic ray causing a bit flip error. So from an engineering perspective, it's essentially as good as deterministic, for all practical purposes.  But it's possible it might not be what you are looking for, if you care more about complexity classes than about whether the generator is usefully secure in an engineering sense.)

In the general case, I don't know what the most efficient cryptanalysis algorithm will be, but I would be pretty surprised if this is secure.  Linear congruential generators are notorious in the cryptographic community for being insecure.  However, you might enjoy the following paper, which while it does not address the specific question you asked, is somehow related:

Inferring sequences produced by a linear congruential generator missing low-order bits.  J. Boyar.  J. ACM 36(1), pp.129--141, Jan 1989.

Also, since $m$ is not a divisor of $p$, note that there will be a statistical bias of the outputs of this generator.  In particular, values in the range $0 .. b-1$ will be slightly more likely than values in the range $b .. p-1$, where $b= p \bmod m$.  The magnitude of this bias depends (roughly) upon the size of $p/m$; the larger $p/m$ is, the greater the bias.  More precisely, the statistical variation distance between pseudorandom and random, due to this effect, is $\delta = 2b(m-b)/mp$, for a single sample.  Therefore, I would expect that $O(1/\delta^2)$ samples should suffice to distinguish the pseudorandom stream from a truly random stream, simply by exploiting this bias.  This attack does not take into account all of the available structure in the output of the generator, so I would expect that better attacks are probably possible.


Why don't the critters ever age? So the two-dimensional reversible cellular automaton Critters (which you can simulate online at https://dmishin.github.io/js-revca/index.html#) on the Torus does not seem to follow the second law of thermodynamics. For example, if a $10\times 10$ block in the torus is filled with random data and the cells outside of this $10\times 10$ block are all zero, then there is a good chance that after several million generations on a $256\times 256$ grid, one can see the cellular automaton return to its original state. Why is the Poincare recurrence time for the reversible cellular automata Critters so small in this case? The rule Critters is universal for reversible computation, and it exhibits chaotic behavior that one would expect in a reversible cellular automaton. Therefore, one would expect that after running the cellular automaton for enough generations, the entropy would constantly increase and hence one would need to wait a very long time (much longer than several million generations) to observe the Poincare recurrence. Is there any explanation for this phenomenon? Are there other chaotic, reversible, universal cellular automata of dimension 2 that exhibit this phenomenon?

Edit: Please see the comments for why this does not address the question, however, I think I should not delete it in order to preserve the discussion...

--

Not an expert, but my impression is that reversible computation does not by itself result in a change in entropy: the amount of information in the system has not changed, only the format in which it is stored. In other words such processes obey the second law with only a weak inequality, not a strict one. To get a strict increase in entropy, one has to erase or destroy information, i.e. irreversible computation. I don't see why the rest of the details in your question -- two dimensions, cellular automata, chaos, recurrence -- would affect this.

Happy to be corrected by any experts, however.


Interesting programs on small machines I am teaching a course and have a tiny implementation of a counter-style machine that has the following instructions and two registers, r0 & r1

INC ri   ; ri <- ri + 1
DEC ri  ; ri <- r1 - 1
JNZ  address    ; if (r0 != 0) then jump to <address>. Else, skip.
LDR ri, address  ; load value at <address> into ri
STR ri, address  ; store the value in <ri> to <address>

What interesting programs can I make using this instruction set using no more than 16 instructions (the range of my address space).

So far, the best I have is "check if memory contains an odd value in the range 0-7"

Also, does it help if I add the following instruction:

JLT address ; if (r0 < 0) then jump to <address>. Else, skip.

even many simple counter machines have been proven Turing complete and this result might be surprising to nonresearchers (or researchers who dont specialize in the area). suggest a more relevant research question would be to review the existing models (many listed on wikipedia), determine if yours fits into them anywhere, and if it does not, describe the precise difference with one of the "nearest" models analyzed in the literature.


Where does the modern canonical version of the Turing machine come from? Turing's original 1936 description of his a-machine differs in several respects from the Turing machine I studied at university, leading me to questions:

The Turing machine I learned about was essentially a recognizer: it would either accept or reject input having specified characteristics.  It has an accept or halt final state.  By contrast, Turing describes a computing machine proper--his model computations involve producing and outputting numbers--without any particular halt state--although, for the proof that the Entscheidungsproblem has no solution, he does propose a machine D that would mark as "s" or "u" some other machine based on whether it is circular ("u").  Where does the recognizer view of the Turing machine come from?  Is it the result of later theorists focusing in on the imaginary machine D in Section 8 of Turing's paper?
The version of the Turing machine I got--e.g., from Sipser--required a definition of language as a "set of strings," where a Turing machine would recognize a given input string as belonging or not to some language L.  Where does this idea come from?  Turing's model of computation makes no reference to this concept of "language."  Is it due to Sipser?  Or Penrose?
Turing defines "circular" in a way that seems surprising and counterintuitive today:  "If a computing machine never writes down more than a finite number of symbols of the first kind [i.e., symbols from {0, 1}], it will be called circular."  Suppose you want the machine to compute a + b, where a and b are integers.  This sounds as if a machine that halts when finished computing a number with a finite representation is circular.  Moreover, Turing never explains what is circular in the common sense of the word about such a machine.  Is he just leaving out an argument that the reader is supposed to infer?  Presumably, the argument would go thus:  if we assume (but why?) that the machine should compute a number whose representation is infinite, then, if the machine halts, this can only result from a circularity in the state diagram--either one state leads to itself, without any motion or change of written symbol, or the states follow in a circular sequence with an equivalent result.  That seems to me to presuppose a lot--for instance, that the circularity does not result in any motion beyond the squares already written and that the written symbols remain the same as before.

Was there published work leading up to Turing's 1936 paper already introducing the concept of circularity, so that he could merely allude to it?

Thanks!

Is it due to Sipser? Or Penrose?

Sorry, that made me laugh out loud.  Penrose?

Today's notion of formal language (a language is a set of words or strings) can be traced at least as far back as Frege in the late 1800's and Thue in the early 1900's.  Chomsky's 1956 paper was very influential, and definitely uses the term "language" for a set of strings.

There is also the 1961 paper of Bar-Hillel, Perles, and Shamir.  I would check that.

This 1963 paper by Evey (https://www.computer.org/csdl/proceedings/afips/1963/5063/00/50630215.pdf ) uses the term "language" in the modern sense in relation to machines.  Perhaps earlier explicit references can be found in the work of Emil Post.


Are there websites for TCS announcements that maintain mailing-lists  or web feeds? For a while, I have been wondering if there exists some site where you can subscribe to receive TCS-conference announcements via e-mail, or, alternatively, that offers some periodically-updated web-feed. This is obviously very useful, but I have been unable to find one myself. Does anyone know of some reliable options?

Two examples of what I had in mind, which I use to look for conferences in quantum information/quantum physics and to keep track of their deadlines.

Quantum Meetings, has a RSS channel.
QUROPE, for European events, has a mailing list.

Related posts: List of TCS conferences and workshops.

I think dmanet is one of a good sites for this, it also emails open positions for job and education in CS. But it's good for Europe.


Distributed Elections using Logical Clocks (hints and tips) I need to implement one of the logical clock algorithms (described here), to allow me to coordinate an election protocol for a distributed system. I'm struggling to work out how I might go about using the clock to enforce a total ordering on a sequence of events in practice. i.e. I don't see a problem in implementing the data structures in practice, but I can't work out how to ensure that my election is not being duplicated elsewhere in the network.
For example, if my 'master' machine goes down, I expect several machines to notice at round about the same time. There will be contention for the 'master' position as several machines try to take it over. My plan is for each machine to broadcast a 'grab the master position' message. Using a logical clock, I should be able to decide what was the globally first machine that sent the message. It will then be acclaimed the master. What I can't work out is how (and where) I will be able to create that ordering over the network messages.
Has anyone out there implemented this sort of algorithm and can offer me some guidance on how I should go about solving the problem?
Thanks in Advance.

Your example mostly needs the machines to agree on a "consensus" for which machine should be the leader. There are a lot of consensus protocols (proven to be correct). On top of consensus (with a proper failure detector) you can construct a "total ordering broadcast". I am no expert in this field so I can't recommend a particular paper but you can pick up one from this google search result
http://scholar.google.com/scholar?hl=en&q=total+ordering+broadcast+consensus&btnG=Search&as_sdt=2000&as_ylo=&as_vis=0


Does $\mathsf{P/poly}$ have subexponential-size bounded-depth circuits? Is there any plausible complexity/crypto hypothesis that rules out the possibility that polynomial size circuits have subexponential-size (i.e. $2^{O(n^\epsilon)}$ with $\epsilon<1$) bounded-depth ($d = O(1)$) circuits?

We know that every function computable by a $\mathsf{NC^1}$ circuit can be computed by a size $2^{O(n^\epsilon)}$ depth $d$ circuit (using AND, OR, and NOT gates, unbounded fan-in) (for every $0 <\epsilon$ there is a $d$ and $d$ can be taken to be $O(1/\epsilon)$).

The question is:

  is there a reason that would make the existence of such circuits for general polynomial size circuits unlikely?

What you ask for should have bad consequences but I cannot think of any immediately. So I have only some pointers to what we know.

Check out Viola's On the power of small depth computation The best we know is Valiant's construction for boolean circuits: log depth linear sized circuits to depth 3 subexp circuits. (We know better for arithmetic circuits.)
There are also some results of Beigel/Tarui on ACC begin contained in bounded depth circuits of superpoly size. I don't recall it being extended to all of $NC^1$ though.


Justifying asymptotic worst-case analysis to scientists I've been working on on introducing some results from computational complexity into theoretical biology, especially evolution & ecology, with the goal of being interesting/useful to biologists. One of the biggest difficulties I've faced is in justifying the usefulness of asymptotic worst-case analysis for lower bounds. Are there any article length references that justify lower bounds and asymptotic worst-case analysis to a scientific audience?
I am really looking for a good reference that I can defer to in my writing instead of having to go through the justifications in the limited space I have available (since that is not the central point of the article). I am also aware of other kinds and paradigms of analysis, so I am not seeking a reference that says worst-case is the "best" analysis (since there are settings when it very much isn't), but that it isn't completeletely useless: it can still gives us theoretically useful insights into the behavior of actual algorithms on actual inputs. It is also important the writing is targeted at general scientists and not just engineers, mathematicians, or computer scientists.
As an example, Tim Roughgarden's essay introducing complexity theory to economists is on the right track for what I want. However, only sections 1 and 2 are relevant (the rest is too economics specific) and the intended audience is a bit more comfortable with theorem-lemma-proof thinking than most scientists[1].

Details
In the context of adaptive dynamics in evolution, I've met two specific types of resistance from theoretical biologists:
[A] "Why should I care about behavior for arbitrary $n$? I already know that the genome has $n = 3*10^9$ base pairs (or maybe $n = 2*10^4$ genes) and no more."
This is relatively easy to brush-off with the the argument of "we can imagine waiting for $10^9$ seconds, but not $2^{10^9}$". But, a more intricate argument might say that "sure, you say you care about only a specific $n$, but your theories never use this fact, they just use that it is large but finite, and it is your theory that we are studying with asymptotic analysis".
[B] "But you only showed that this is hard by building this specific landscape with these gadgets. Why should I care about this instead of the average?"
This is a more difficult critique to address, because a lot of the tools people commonly use in this field are coming from statistical physics where it is often safe to assume a uniform (or other specific simple) distribution. But biology is "physics with history" and almost everything isn't at equilibrium or 'typical', and empirical knowledge is insufficient to justify assumptions about distributions over input. In other words, I want an argument similar to that used against uniform distribution average-case analysis in software engineering: "we model the algorithm, we can't construct a reasonable model of how the user will interact with the algorithm or what their distribuition of inputs will be; that is for psychologists or end users, not us." Except in this case, the science isn't at a position where the equivalent of 'psychologists or end users' exists to figure out the underlying distributions (or if that is even meaningful).
Notes and related questions

The link discusses cognitive sciences, but the mindset is similar in biology. If your browse through Evolution or Journal of Theoretical Biology, you will seldom see theorem-lemma-proof, and when you do it will typically be just a calculation instead of something like an existence proof or intricate construction.
Paradigms for complexity analysis of algorithms
Other kinds of running time analysis besides worst-case, average-case, etc?
Ecology and evolution through the algorithmic lens
Why economists should care about computational complexity

My personal (and biased) take is that asymptotic worst-case analysis is a historical stepping stone to more practically useful kinds of analysis.  It therefore seems hard to justify to practitioners.

Proving bounds for the worst case is often easier than proving bounds for even "nice" definitions of average case.  Asymptotic analysis is also often much easier than proving reasonably tight bounds.  Worst-case asymptotic analysis is therefore a great place to start.

The work of Daniel Spielman and Shanghua Teng on smoothed analysis of Simplex seems to me a harbinger of what can happen when we start to gain a better understanding of the shape of a problem: tackling the worst-case first enables a more nuanced understanding to be developed.  Further, as Aaron Roth suggested in the comments, if the "usual" behaviour of a system is significantly different from its worst case, then the system is not yet completely specified and more work is needed to improve the model.  So going beyond worst-case generally seems important as a long-term goal.

As far as asymptotic analysis is concerned, it usually serves to keep a long and messy proof clear of distracting details.  Unfortunately there currently does not seem to be a way to reward the tedious work of filling in the details to obtain the actual constants, so that seldom seems to get done.  (Page limits also work against this.)  Careful analysis of the details of an asymptotic bound has led to actual algorithms, with good bounds on the constants, so I personally would like to see more of this kind of work.  Perhaps if more proofs were formalised using proof assistant systems, then the constants could be estimated with less additional effort.  (Or bounds on the constants, along the lines of Gowers' bound for the Szemerédi Regularity Lemma, might become more routine.)  There are also ways to prove lower bounds that are free of constants, by using more explicit machine models (such as deterministic finite-state automata).  However, such (near-)exact lower bounds for more general models of computation may require a lot of work, or be out of reach altogether.  This seems to have been pursued in ~1958–73 during the first heyday of automata theory, but as far as I can tell has since largely been left alone.

In short: in future, I think we'll see worst-case analysis as just a first step, and I hope we'll see expressions like $O$*$(n^k)$ with galactic hidden constants as just the first step.  I find it difficult to justify the current focus on worst-case asymptotic analysis to practitioners, but perhaps it is useful to see this as the beginning steps of a longer journey.


Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model) I know the Blum-Shub-Smale model. It is claimed to provide a theoretical framework for algorithms in real and complex algebra and analysis.

A very general question:
Most algorithms compromise of
finite input - finite computation steps - finite output

However, in mathematics most schemes which one could call algorithmic actually compromise infinitely many iterations. Just to name a few:

Iteration to construct fix-points of contractive maps
Iterative solvers in numerical analysis
Newtons method

I know the last one is treated in the classical book "Complexity and Real Computation" by Blum, Cucker, Shub & Smale, but there does not seem to exist a generalization which puts "iterative" algorithms onto solid foundations.

Edit:
Yes, the question:

  How can you deal with these iterative algorithms (which as such are not necessarily supposed to finish)?

Addendum:
I always wondered whether there might be something like a BSS-like model, which is tailored for numerical analysis - in that it does formalize errors, inexactness, approximate solutions, and does not allow for "unreasonable" computing power. And is easy to access.

The book mentioned above is concerned about this gap, too:
"There is not even a formal definition of algorithm in the subject [of numerical analysis]" (p. 23). However, it does not seem their approach suits this need. On the other hand, the monograph Andrej mentions does include a book which heads towards this direction.

Questions regarding real-number computation and infinite iteration, especially in analysis and topology, are studied in constructive and computable analysis. Most people who work in this area will tell you that while the BSS model can be useful for certain kinds of computational complexity, it does not properly reflect computability on real numbers. The trouble is with the decidable $<$ relation on the reals, which is a basic building block in the BSS model.

There are several computational models which capture both computation of (exact) real numbers and infinite computation. Your examples all reduce to computation of the limit of a convergent sequence whose rate of convergence is explicitly known. This is a well-studied situation.

Here is one possible way of understanding computation on real numbers. I will use Haskell just for fun (usually these things get explained in terms of Turing machines). Let us think of a real number as a convergent sequence of rational approximations,

  type R = Int -> Rational

where we require that the $k$-th approximation is at most $2^{-k}$ away from the limit (we could have chosen some other rate of convergence, too, or we could have equipped each approximation sequence with information about the rate of convergence--the important thing is that the rate of convergence has to be provided explicitly).

Addition can be defined as follows:

  add x y = \k -> x (k+1) + y (k+1)

Exercise: define multiplication and other arithmetic operations.

Now to get infinite iteration going, we need an operation lim which takes a Cauchy sequence and computes its limit. More precisely, lim takes two arguments: a Cauchy sequence $(a_n)_n$ and its modulus of convergence $m$, which is a map $m : \mathbb{N} \to \mathbb{N}$ such that $a_{m(k)}$ is at most $2^{-k}$ away from the limit of $(a_n)_n$. In Haskell:

  lim :: (Int -> R) -> (Int -> Int) -> R

  lim a m = \k -> a (m (k+1)) (k+1)

Exercise: compute $\sqrt{r}$ as the limit of the sequence obtained by Newton's method for finding the positive root of $x^2 - r$.

This is just a very brief outline on how to do things. To find out more, visit the CCA net web site, especially the Texts and Monographs page.


Examples where insight from geometry was useful for solving something completely non-geometric One of the nice things about having evolved in a universe with three spatial dimensions is that we have developed problem solving skills pertaining to objects in space. Thus, for example, we can think of a triplet of numbers as a point in 3-d and hence computation about triplets of numbers as computation about points in 3-d, which can then be solved using our intuition about space. This seems to suggest that it should be possible at times to solve a completely non-geometric problem using techniques from geometry. Does anyone know of such examples?

Of course, the terms 'geometric' and 'non-geometric' are slightly vague here. One can argue that any geometric problem is actually non-geometric if you replace all points with their co-ordinates. But intuitively, the definition is clear. Let's just say that we call something geometric if we would consider sending a paper about it to SoCG.

A few more examples:

Sleator, Thurston and Tarjan used a geometric representation of trees as partitions of polygons, and hyperbolic geometry, to prove lower bounds for binary tree rotation. (Also, I believe the history of a dynamic binary search tree can be represented as a tetrahedralization.)

The reduction of least common ancestor to range minimum queries, due to Berkman and Vishkin, relates a data structures problem on trees to an arguably-geometric problem. (and thanks for the article David)

The reduction of a scheduling problem to max weight independent set of axis-parallel rectangles [1] or the reduction of a different scheduling problem to geometric set cover [2] might qualify.

The reduction of the largest common subsequence problem to finding layers of maxima is well-known (meaning, I'm too lazy to look up who actually thought of it).

[1] (Liane Lewin-Eytan, Joseph Seffi Naor and Ariel Orda)

[2] Nikhil Bansal, Kirk Pruhs. The Geometry of Scheduling, FOCS 2010.

[later edit] A couple more cases where a "geometric" view seemed surprising (though the "submission to SoCG" or "makes something to visualize" standards are probably not met):

algebraic topology applied to lower bounds for distributed computing

incorporating computability into Hausdorff dimension

defining a notion of distance for groups, then volume, then growth of volume as a function of distance, then using "polynomial growth"


What's the expected length of the shortest hamiltonian path on a randomly selected points from a planar grid? $k$ distinct points are selected randomly from a $p\times q$ grid. (Obviously $k\leq p\times q$ and is a given constant number.) A complete weighted graph is built from these $k$ points such that weight of the edge between vertex $i$ and vertex $j$ equals the Manhattan distance of two vertices on the original grid.

I am looking for an efficient way to calculate the expected length of the shortest (minimum total weight) hamiltonian path passing through these $k$ nodes. More precisely, the following naive approaches are not desired:

$\bullet$ Calculating the exact path length for all combinations of k nodes and deriving the expected length.

$\bullet$ Calculating the approximated path length for all combinations of k nodes using the basic heuristic of using minimum spanning tree which gives up to 50% error. (A better heuristic with less error may be helpful)

Assuming that $p$ and $q$ are fairly large, one would expect that the expected length would mainly depend on the density, with some correction term depending on the perimeter. So it would, to first order, be a function of the following form.

$$ L \approx (pqk)^{1/2} f(k/pq) + (p+q) g(k/pq).$$

Now, you could use experiments on smaller-size problems to figure out what $f$ and $g$ are. First, to estimate $f$, you want to do experiments on a sample without a boundary: the easiest way to do this is to use a $p\times p$ grid with the left side connected to the right and the top to the bottom, forming a torus. To estimate $g$, you can use experiments on a $p \times q$ grid.

For estimation, you need to solve (exactly or approximately) relatively large TSPs, since the larger the ones you use for the estimation, the better your results will be. You could either use heuristics that come within a few percent, or exact TSP code. See here for some good heuristics. Bill Cook's Concorde TSP solver will find the exact optimum for reasonably large instances (it's the best TSP code available), and can be used without charge for academic research.


Applications of Spectral Graph Theory in Information and Coding Theory I wanted to find out what are some application of SGT in the area of information and coding theory and maybe communications. The most related that comes to mind is the work on Expander Codes

Michael Sipser and Daniel Spielman, "Expander Codes", IEEE Transactions on Information Theory, Vol 42, No 6, pp. 1710-1722. 1996

Other examples?

Cayley graphs of codes and derandomized code products can be a good example. See the following thesis (Chapter 6) for details and references: http://library.epfl.ch/en/theses/?nr=3816


Careers for theoretical computer scientists What are the typical careers for theoretical computer scientists (people with graduate degree in theoretical computer science)?

What kind of industries and institutions look for theoretical computer science knowledge?
What careers do theoretical computer scientists typically peruse?

There are the obvious academic positions. Apart from that, many industrial research (or research-like) labs are very interested in hiring theoreticians who are comfortable applying theoretical foundations to solving problems as well as coming up with new theorems. Theoreticians also find positions (though may be not as many) in financial institutions as "quants".


The unreasonable power of non-uniformity From the common sense point of view, it is easy to believe that adding non-determinism to $\mathsf{P}$ significantly extends its power, i.e., $\mathsf{NP}$ is much larger than  $\mathsf{P}$. After all, non-determinism allows exponential parallelism, which undoubtedly appears very powerful.

On the other hand, if we just add non-uniformity to $\mathsf{P}$, obtaining  $\mathsf{P}/poly$, then the intuition  is less clear (assuming we exclude non-recursive languages that could occur in $\mathsf{P}/poly$). One could expect that merely allowing different polynomial time algorithms for different input lengths (but not leaving the recursive realm) is a less powerful extension than the exponential parallelism in non-determinism.

Interestingly, however, if we compare these classes with the very large class $\mathsf{NEXP}$, then we see the following counter-intuitive situation. We know that $\mathsf{NEXP}$ properly contains $\mathsf{NP}$, which is not surprising. (After all, $\mathsf{NEXP}$ allows doubly exponential parallelism.) On the other hand, currently we cannot rule out $\mathsf{NEXP}\subseteq \mathsf{P}/poly$.

Thus, in this sense, non-uniformity, when added to polynomial time,  possibly makes it extremely powerful, potentially more powerful than non-determinism. It might even go as far as to simulate doubly exponential parallelism! Even though we believe this is not the case, but the fact that currently it  cannot be ruled it out still suggests that complexity theorists  are struggling with "mighty powers" here.

  How would you explain to an intelligent layman what is behind this  "unreasonable power" of non-uniformity?

A flip answer is that this isn't the first thing about complexity theory that I'd try to explain to a layperson!  To even appreciate the idea of nonuniformity, and how it differs from nondeterminism, you need to be further down in the weeds with the definitions of complexity classes than many people are willing to get.

Having said that, one perspective that I've found helpful, when explaining P/poly to undergraduates, is that nonuniformity really means you can have an infinite sequence of better and better algorithms, as you go to larger and larger input lengths.  In practice, for example, we know that the naïve matrix multiplication algorithm works best for matrices up to size 100x100 or so, and then at some point Strassen multiplication becomes better, and then the more recent algorithms only become better for astronomically-large matrices that would never arise in practice.  So, what if you had the magical ability to zero in on the best algorithm for whatever range of n's you happened to be working with?

Sure, that would be a weird ability, and all things considered, probably not as useful as the ability to solve NP-complete problems in polynomial time.  But strictly speaking, it would be an incomparable ability: it's not one that you would get automatically even if P=NP.  Indeed, you can even construct contrived examples of uncomputable problems (e.g., given 0n as input, does the nth Turing machine halt?) that this ability would allow you to solve.  So, that's the power of nonuniformity.

To understand the point of considering this strange power, you'd probably need to say something about the quest to prove circuit lower bounds, and the fact that, from the standpoint of many of our lower bound techniques, it's uniformity that seems like a weird extra condition that we almost never need.


Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$ I have part of a proof attempt of $\oplus \mathbf{P} \subseteq \mathbf{NP}$. The proof attempt consists of a Karp reduction from the $\oplus \mathbf{P}$-complete problem $\oplus$3-REGULAR VERTEX COVER to SAT.

Given a cubic graph $G$, the reduction outputs a CNF formula $F$ having both the following properties:

$F$ has at most $1$ satisfying assignment.
$F$ is satisfiable if and only if the number of vertex covers of $G$ is odd.

  Questions

  Which would be the consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$ ? A consequence which I'm already aware of is the following: $\mathbf{PH}$ would be reducible to $\mathbf{NP}$ via two-sided randomized reduction. In other words we would have $\mathbf{PH}\subseteq\mathbf{BPP}^{\mathbf{NP}}$ (using Toda's Theorem, which states that $\mathbf{PH}\subseteq\mathbf{BPP}^{\oplus\mathbf{P}}$, by merely replacing $\oplus\mathbf{P}$ with $\mathbf{NP}$). I do not know if $\mathbf{BPP}^{\mathbf{NP}}$ has been shown to be contained in some level $i$ of the Polynomial Hierarchy: if yes, a further consequence would be that $\mathbf{PH}$ collapses to such level $i$. Moreover, under widely accepted derandomization assumptions ($\mathbf{BPP} = \mathbf{P}$), the Polynomial Hierarchy would collapse between the first and the second level, as we would have $\mathbf{PH} = \mathbf{P}^\mathbf{NP} = \Delta_2^\mathbf{P}$ (I'm told this is not true, however I will not erase this line until I fully understand why).
  If I'm not mistaken, the aforementioned reduction would actually prove more than $\oplus \mathbf{P} \subseteq \mathbf{NP}$. It would prove $\oplus \mathbf{P} \subseteq \mathbf{UP}$. Which would be the consequences of $\oplus \mathbf{P} \subseteq \mathbf{UP}$, in addition to those already implied by $\oplus \mathbf{P} \subseteq \mathbf{NP}$ ? I do not know exactly whether $\oplus \mathbf{P} \subseteq \mathbf{UP}$ would add more surprise to the already surprising consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$, nor to what extent. Intuitively I presume it would, and to a pretty wide extent.

There are two oracle sets defined in T88 such that ${\bf NP^A \not \subseteq \oplus P ^A}$ and ${\bf \oplus P^B \not \subseteq NP^B}$.