The problem is definitely in random double exponential time, and likely in exponential space. The first result was in my original post below, and the second in my update.

ORIGINAL POST:
Can't you get a good approximation by simulation, if you're willing to spend time exponential in $k$ and $d$? The input length is logarithmic in $k$ and $d$. So clearly the problem is in random double exponential time. Since nobody knows how to compute these values efficiently in practice, it seems clear this is not known to be in random exponential time. I would be very surprised if any other complexity results were known about this problem.

ADDED UPDATE:
Actually, I think the problem is very likely in EXPSPACE. Let's fix the dimension (to make things easier, and because I don't understand the subtleties of percolation in varying dimension well at all) so the input is just $k$. Also, let's say $k$ is given in unary so that I can drop the exponentials and talk about PSPACE. I propose the following algorithm.

First, we must make the assumption that there is a class of pseudorandom functions $F_\alpha({\mathbf{x}})$ which tell you whether the bond at coordinates $\mathbf{x}$ is present, where $\alpha$ is the seed for the pseudorandom function, and for which the bonds given by $F$ behave like random bonds with respect to percolation.

Now, suppose that we have a fixed value of the pseudorandom function seed $\alpha$. Consider the following two-player game, which two players A and B play, after being given a bond probability $p$ and a seed $\alpha$ for $F$.

Player 1 gives two sites ${\bf a}$ and ${\bf b}$ within distance $2^{k\nu}$ of the origin, but which are still $\theta(2^{k \nu})$ distance apart, where $\nu$ is chosen so that if the percolation probability $p$ is within $2^{-k}$ of the critical percolation probability $p_c$, then with high probability there will be a cluster of diameter $2^{k\nu}$ near the origin ($\nu$ is called a critical exponent, and I believe its value is known with mathematical proof). Player 1 claims that there is a path of length $d$ connecting these sites with bonds in $F_\alpha$, and also gives the site that is the midpoint of this path of length $d$.  Player 2 then claims that either the first part or the second part of this path is not connected. Player 1 responds by giving the point he claims is the midpoint of this allegedly disconnected section of the path. The two players continue in this way for $\log d$ steps, until they reach a segment of path consisting of a single bond, whose presence or absence is easily verified.

This is a two-player game whose result tells whether the critical percolation probability is within $2^{-k}$ of $p_c$, and by the result that alternating polynomial time is in PSPACE, the outcome of this game can be computed in PSPACE. A PSPACE machine could then compute this outcome for all seeds $\alpha$ to find which player wins with high probability: this will tell him whether $p$ is larger or smaller or approximately equal to $p_c-2^{-k} $. It can then do a binary search on $p$ to find $p_c$.

CHALLENGE: Find a PSPACE (or EXPSPACE if $k$ is not given in unary) algorithm without using the assumption that there are good pseudorandom functions for percolation.


Have you ever realized you can't solve the homework you assigned?

Yes, sadly, I've done this several times, as well as the slightly more forgivable sin of assigning a problem that I can solve, but only later realizing that the solution requires tools that the students haven't seen.  I think the following is the most professional response (at least, it's the response I've settled on after several false starts):

Immediately and publicly admit the mistake.  Explain steps 2 and 3.
Give every student full credit for the problem.  Yes, even if they submit nothing.
Grade all submitted solutions normally, but award the resulting points as extra credit.  In particular, give the usual partial credit for partial solutions.

The first point is both the hardest and the most important.  If you try to cover your ass, you will lose the respect and attention of your students (who are not stupid), which means they won't try as hard, which means they won't learn as well, which means you haven't done your job.  I don't think it's fair to let students twist in the wind with questions I honestly don't think they can answer without some advance warning.  (I regularly include open questions as homework problems in my advanced grad classes, but I warn the students at the start of the semester.)  Educational, sure, but not fair.

It's sometimes useful to give hints or an outline (as @james and @Martin suggest) to make the problem more approachable; otherwise, almost nobody will even try.  Obviously, this is only possible if you figure out the solution first.  On the other hand, sometimes it's appropriate for nobody to even try.  (For example, "Describe a polynomial-time algorithm for X" when X is NP-hard, or if the setting is a timed exam.)

If you still can't solve the problem yourself after sweating buckets over it, relax.  Probably none of the students will solve it either, but if you're lucky, you'll owe someone a LOT of extra credit and a recommendation letter.

And if you later realize the solution is easy after all, well, I guess you screwed up twice.  Go to step 1.


Kleene Algebra for star-free regular expressions

You might be interested in bounded synchronization delay expressions.
See [1] for details on these expressions.
To sum up, they are equivalent to star-free expressions, but instead of using complement, they restrict the use of the Kleene star to certain languages: the prefix codes with bounded synchronization delay.

This way, you can have your characterization: $L(r_1)=L(r_2)$ iff we can prove $r_1=r_2$ using the axioms of Kleene Algebra, the only difference being that $r_1$ and $r_2$ are more constrained on the use of Kleene star, and only represent star-free languages.

On the other hand, axiomatization of regular expressions with complement has been done in [2], so after careful verification, you could possibly use this to axiomatize star-free expressions directly.

[1] Diekert, V.; Kufleitner, M., Bounded synchronization delay in omega-rational expressions, Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. 7th international computer science symposium in Russia, CSR 2012.

[2]
Salomaa, A.; Tixier, V., Two complete axiom systems for the extended language of regular expressions, IEEE Trans. Comput. 17, 700-701 (1968). ZBL0174.29001.


How can I model this usage scenario mathematically?

I think you want a Petri net with transition guards and a global clock.  (Other formalisms would also work, but I'm going with this one because it relates to the discussion on your other question.)

Draw a graph -- vertices and directed edges -- where the vertices are your nodes, and the edges are the communication channels from one node to another.  It sounds as though there's an edge between every node, if all nodes are capable of broadcast, but perhaps I'm misreading.  In any case, the important thing is that you decorate each edge with a rule or set of rules, and the edge only "opens" when the rules are satisfied.  (These rules are called guard expressions.)

For example, to make "vary the amount of time a host caches responses" rigorous, you could make the rule for an edge, "if I receive a message, I wait 3 seconds according to the global clock before I pass it on."  I don't understand your dirty-cache issue well enough to offer anything yet, but I think the conceptual point you need first is this notion of enabling or disabling a transition according to the rules of the system.


Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?

Nothing better than $\mathbf{BPP}/\text{poly} = \mathbf{P}/\text{poly}$ is known. On the other hand, better results are known in the space bounded setting. Fortnow and Klivans showed that $\mathbf{BPL} \subseteq \mathbf{L}/O(n)$ (see this paper for a refinement). It follows that $\mathbf{BPL}/O(n) = \mathbf{L}/O(n)$.


Deterministic communication complexity vs partition number

This question has just been resolved! As I mentioned, it was known that

  $Pn(f) \leq D(f) \leq (Pn(f))^2$,

but it was a major open problem to show that either $Pn(f) = \Theta(D(f))$ or that there exists a function for which $Pn(f) = o(D(f))$.

A few days ago this was resolved by Mika Göös, Toniann Pitassi, Thomas Watson (http://eccc.hpi-web.de/report/2015/050/). They show that there exists a function $f$ which satisfies

  $Pn(f) = \tilde{O}((D(f))^{2/3})$.

They also show an optimal result for the one-sided version of $Pn(f)$, which I'll denote by $Pn_1(f)$, where you only need to cover the 1-inputs with rectangles. $Pn_1(f)$ also satisfies

  $Pn_1(f) \leq D(f) \leq (Pn_1(f))^2$,

and they show that this is the best possible relation between the two measures, since they exhibit a function $f$ which satisfies

  $Pn_1(f) = \tilde{O}((D(f))^{1/2})$.


Trade off between width and depth of free BDDs for total functions

There are known functions on $n$ variables where depth $n$ branching programs (as non-oblivious BDDs are usually called) require exponential size.  The book to read is by Wegner.

Stronger lower bounds are given by Ajtai, and there is some newer work, but I'm not sure about which is best to read.


Simulating Turing machines (output included) with circuits

Yes, as long as we allow encoding the the result of $f$ in a basically trivial way, rather than outputting exactly $f(x)$.

To get over obstacle (2) (different output lengths for the same input length): for any given input length $n$, there is a maximum output length $m$.  $C_n$ will output $2m$ bits.  The first $2|f(x)|$ bits output by $C_n(x)$ will be the bits of $f(x)$ doubled, and the remaining $2(m-|f(x)|)$ bits will be the string 01 repeated over and over.  For example, if $m = 6$ and for some $x$ of length 10, $f(x)=0010$, then $C_{10}(x) = 00\ 00\ 11\ 00\ 01\ 01$ (spaces added for ease of reading).

To get over obstacle (1) ($f(x)$ may not halt): for any given input length $n$, there is a time $t$ such that, for all $x$ of length $n$, either $f(x)$ halts within $t$ steps, or $f(x)$ does not halt ever.  If $f(x)$ does not halt, then we make the output of the circuit be a string of 10 repeated over and over again.  Of course, such a circuit family can not in general be uniform, since deciding that halting time is in general uncomputable, but the circuit family still exists.


Any algorithmic problem has a time complexity dominated by counting?

This is a followup to Suresh's answer.  As he says, there are lots of construction problems in computational geometry where the complexity of the output is a trivial lower bound on the running time of any algorithm.  For example: planar line arrangements, 3-dimensional Voronoi diagrams, and planar visibility graphs all have combinatorial complexity $\Theta(n^2)$ in the worst case, so any algorithm that constructs those objects trivially requires $\Omega(n^2)$ time in the worst case.  (There are $O(n^2)$-time algorithms for all three of those problems.)

But similar constraints are conjectured to apply to decision problems as well.  For example, given a set of n lines in the plane, how easily can you check whether any three lines pass through a common point?  Well, you could build the arrangement of the lines (the planar graph defined by their intersection points and the segments between them), but that takes $\Theta(n^2)$ time.  One of the main results of my PhD thesis was that within a restricted but natural decision tree model of computation, $\Omega(n^2)$ time is required to detect triple intersections.  Intuitively, we must enumerate all $\binom{n}{2}$ intersection points and look for duplicates.

Similarly, there is a set of numbers where $\Theta(n^2)$ triples of elements sum to zero.  Therefore, any algorithm (modeled by a certain class of decision trees) to test whether a given set contains three elements that sum to zero requires $\Omega(n^2)$ time.  (It's possible to shave off some logs via bit-level parallelism, but whatever.)

Another example, also from my thesis, is Hopcroft's problem: Given $n$ points and $n$ lines in the plane, does any point contain any line.  The worst-case number of point-line incidences is known to be $\Theta(n^{4/3})$.  I proved that in a restricted (but still natural) model of computation, $\Omega(n^{4/3})$ time is required to determine whether there is even one point-line incidence.  Intuitively, we must enumerate all $\Theta(n^{4/3})$ near-incidences and check each one to see whether it's really an incidence.

Formally, these lower bounds are still just conjectures, because they require restricted models of computation, which are specialized to the problem at hand, especially for Hopcroft's problem).  However, proving lower bounds for these problems in the RAM model is likely just as hard as any other lower-bound problem (ie, we have no clue) — see the SODA 2010 paper by Patrascu and Williams relating generalizations of 3SUM to the exponential time hypothesis.


What algorithms exist for construction a DFA that recognizes the language described by a given regex?

There are different algorithms to convert regular expressions to finite automata. You can go directly from regular expressions to DFAs without building any other automaton first by implicitly doing the subset construction while generating the automaton. Another option to directly obtain deterministic automata is to use the method of derivatives.

Checking if a regular expression represents the language containing all strings is a PSPACE complete problem (see this answer for a reference). Checking if a DFA accepts that language can be done in polynomial time, so if you go directly from a regular expression to a DFA, there will be a blow-up somewhere.

My understanding of the literature is that we can choose translations that allow us to localise the blow-up. Meaning, there are different ways to go from a regular expression to a finite automaton, and methods that are linear, or polynomial are preferred. Usually, the exponential costs are pushed into determinization of automata.

There has been a lot of work on identifying sub-families of regular expressions from which we can efficiently generate DFAs. This line of work is dependent on the translation you use. Meaning, you fix a mapping from regular expressions to NFAs and try to characterise the regular expressions which map to DFAs.

The standard construction of automata from regular expressions is not the preferred construction in such work. The constructions of choice produce automata which closely resemble the structure of the regular expression. These constructions use the notion of a derivative of a regular expression.

  Derivatives of regular expressions, J. A. Brzozowski. 1964.

A derivative $s$ of a regular expression $r$ with respect to a symbol $a$ from the alphabet is a regular expression representing the language of $r$ with the leading $a$ removed from strings. This notion was extended to partial derivatives of regular expressions by Antimirov.

  Partial Derivatives of Regular Expressions and Finite Automata Constructions, V. Antimirov. 1995.

If you think of a state of an automaton as a representation of all strings accepted from that state, (partial) derivatives allow you to treat regular expressions as states. Contrast with the standard textbook construction which intuitively treats regular expressions as automata, not states.

  From regular expressions to deterministic automata, G. Berry and R. Sethi, 1986.

The correspondence between regular expressions and states of an automaton and determinism is discussed explicitly by Berry and Sethi, who combine the notion of Brzozowski derivatives with the idea of distinguishing between occurrences of the same symbol to give a syntax-based translation of regular expressions into finite automata.

  One-Unambiguous Regular Languages, A. Brüggemann-Klein and Derick Wood, 1998.

This paper builds on earlier work by Brüggemann-Klein and studies cases in which you can use derivatives to generate DFAs in polynomial time. There is a large amount of work following this paper. It was significant from the perspective of web technologies because regular expressions that can be manipulated efficiently (aka, corresponding to DFAs) were important for processing SGML and XML.

There has been much work studying other special cases of deterministic regular expressions. A very recent paper studying when some of these problems can be solved in linear time is from 2012.

  Deterministic Regular Expressions in Linear Time, Benoit Groz, Sebastian Maneth, Slawomir Staworko. 2012.


Computational complexity of clustering algorithms

Single linkage clustering is almost the same as minimum spanning trees in complete graphs, easy O(n^2) time. For O(n^2) time for other agglomerative clustering methods (including I'm pretty sure average and complete linkage) see my paper "Fast hierarchical clustering and other applications of dynamic closest pairs", SODA '98 and JEA '00.


Shuffling of tokens on a graph using local swaps

Suppose your graph was a path.  I think then this problem becomes equivalent to sorting a random sequence of numbers in an array by swapping adjacent entries.  Even of all nodes are topology aware, you get a n^2 lower bound on the number of swaps (cannot do better than bubble sort which is n^2 even on a random input).


$\mathbf{UL}$ is contained in $\mathbf{NL}$, which is contained in $\mathbf{DSPACE}(\log^2 n)$ by Savitch's theorem, which is strictly contained in $\mathbf{PSPACE}$ by the space hierarchy theorem, so $\mathbf{UL}$ is strictly contained in $\mathbf{PSPACE}$. It would be surprising if e.g. $\mathbf{UL} = \mathbf{DSPACE}(\log^2 n)$, but I don't think it's known to be false.


Zero Obstructed vertex induced subgraphs

Sorry this is too long for a comment :)

Maybe the complete graph is a trivial graph but it illustrates that e.g. graphs $G = (V,E)$ with large cliques of size $\Omega(\vert V \vert)$ also have exponentially many $0$ obstructed induced subgraphs. And I don't think that $N$ can be easily computed in such graphs.

I also think that 3-regularity doesnt help: Let $A$, $B$ be a partition of $V$ each of size $\vert V \vert /2$. The induced subgraph consisting of nodes from either $A$ or $B$ is a cycle and the edges between $A$ and $B$ form a perfect matching. This graph is $3$-regular and every induced subgraph consisting of at least all nodes in $A$ or all nodes in $B$ is $0$ obstructed.


Is Max-Cut APX-complete on triangle-free graphs?

Yes, by a reduction from MaxCut to triangle-free MaxCut. Here is what Wikipedia calls an L-reduction

Given an instance $G$ of Max-Cut, construct the 3-stretch $G'$ by subdividing each edge into three edges. Then the order of the maximum cut of $G'$  is the order of the maximum cut of $G$ plus twice the number of edges in $G$. Since the size of a max cut is always at least half the number of edges, the error ratio only gets worse by a constant factor.


Any polynomial which is hard to count but easy to decide?

(I am posting my comments as an answer in response to the OP’s request.)

As for Question 1, let fn: {0,1}n→ℕ be a family of functions whose arithmetic circuit requires exponential size.  Then so does fn+1, but fn+1 is easy to decide by a trivial monotone arithmetic circuit.  If you prefer to avoid constants in monotone arithmetic circuits, then let fn: {0,1}n→ℕ be a family of functions such that the arithmetic circuit for fn requires exponential size and fn(0, …, 0)=0, and consider fn+x1+…+xn.


For observing consecutive elements: pick up the best sequence of $k$ elements (depending on your proximity measure), and repeat it. Then B will always observe the same sequence (I assume that cyclical permutation doesn't affect B).

For observing random elements: how would you pick them randomly? Do you want a deterministic sequence?


To answer the first part of your question

  Modal specifications are a syntactic fragment of the Mu-calculus, Guillaume Feuillade, 2005.

From the introductory paragraph

  As a consequence, we define a syntactic fragment of the Mu-calculus, called the conjunctive modal Nu calculus, ...In this report, we prove that the conjunctive modal Nu-calculus and modal specifications have the same expressive power and that we can switch between both without loss of generality. We also prove that the set of models of a modal specification is a lattice with finite models as extrema.

You should examine the details, particularly because the notion of a modal specification is not standard, and is defined in the article.


There is the notion of primality of a language. It asks whether L can be written as $L_1 \cdot L_2$ where neither factor contains the empty word. A language is prime if it cannot be written in this form.

For a given regular language, represented by a DFA, it is shown in [MNS] that it is PSPACE-complete to decide primality.

[MNS] Wim Martens, Matthias Niewerth and Thomas Schwentick,
"Schema design for XML repositories: complexity and tractability", 2010. doi:10.1145/1807085.1807117


[Expanding the comment into an answer.]

First, just a clarification about counting bound variables in a combinator (= closed term) $t$.  I interpret the question as asking about
$$
\text{the total number of distinct bound variable names in }t
$$
so that for example the term $t = (\lambda x.x(\lambda y.y))(\lambda x.\lambda y.yx)$ counts as having two bound variables, despite having four binders (i.e., lambda abstractions).  This way of counting was initially a bit strange to me since it is not invariant under $\alpha$-conversion: for example, $t$ is $\alpha$-equivalent to $t' = (\lambda x.x(\lambda y.y))(\lambda a.\lambda b.ba)$, but $t'$ has four distinct bound variable names.  However, this is not really a problem, because the minimum number of distinct bound variable names needed to write a closed term $t$ is equal to
$$
\text{the maximum number of free variables in a subterm of }t
$$
and the latter notion is invariant under $\alpha$-conversion.

So, let $\mathcal{C}$ be the collection of all combinators which can be written using at most two distinct bound variables, or equivalently the collection of all combinators whose subterms have at most two free variables.

Theorem (Statman): $\mathcal{C}$ is not combinatorially complete.

It seems that the original proof of this is contained in a tech report by Rick Statman:

Combinators Hereditarily of Order Two. Carnegie Mellon Math Department Technical Report 88-33, August 1988. (pdf)

Statman defines an essentially isomorphic collection of combinators which he calls "HOT", for "hereditarily of order two".  The tech report actually shows that the word problem (i.e., $\beta$-equality) for HOT is still undecidable, despite the fact that it is not combinatorially complete.  Statman later wrote a short self-contained paper with the proof that HOT is not combinatorially complete in:

Two variables are not enough. Proceedings of the 9th Italian conference on Theoretical Computer Science, pp. 406-409, 2005. (acm)

In any case, as glossed in the abstract of the original tech report, the idea of the proof is to show that HOT is a "hierarchy by definitional level".  That is, he defines a notion of rank for a HOT combinator, and a family of combinators $Hn$, such that each $Hn$ has rank $n+1$ and is not $\beta$-equivalent to any combination of HOT combinators of rank $n$.  This implies that HOT is not combinatorially complete, because if the $S = \lambda x.\lambda y.\lambda z.(xz)(yz)$ combinator could be derived from a combination of HOT combinators of rank $n$ for some $n$, then so could any other combinator, in particular the combinator $Hn$ of rank $n+1$.


Solid applications of category theory in TCS?

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

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

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

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

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

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


Polynomial-time reductions between undecidable languages

Gödel's incompleteness theorem can be thought of as a reduction from the Halting problem to the language $\langle \varphi \mid \varphi \text{ is a true sentence in number theory}\rangle$, and a careful analysis of the running time would show that it is indeed a polynomial time reduction.

Not every such reduction is polynomial time, however. You can observe that a reduction from the Halting problem $\langle i \mid TM_i \text{ halts on input } i\rangle$ to the unary language $\langle 1^i \mid TM_i \text{ halts on input } i\rangle$ has exponential blowup in instance size.


Is getting post-doc difficult in theoretical computer science with few published papers?

I voted to close the question but I see that it's getting upvotes and being "favorited" so perhaps a point that seems obvious to me bears being stated explicitly. So, not to put too fine a point on it: Not all postdocs are equally competitive. What is a postdoc, after all? It's a paid academic position, non tenure track, usually for a fixed time (1-3 years), possibly involving teaching. Usually, any faculty member or department with funding available can offer a postdoc position. But not all positions are created equal, and some are definitely more competitive and prestigious than others. So the strength of your CV will definitely have a major role in determining what kind of a position you'll be offered. Note that publications (especially their quantity rather than quality) are important but not all-decisive. A few very strong publications is certainly preferred to many weak ones -- at least when I'm hiring! Also the letters of recommendation matter a great deal.


Functional Sparse-Matrix with good performance?

Buluç et al. (2009) propose a storage format called compressed sparse blocks which does not favour rows or columns. A $n\times n$-matrix is subdivided into $\beta\times\beta$ blocks and the list of nonzero elements in each block is stored in Z-Morton order. To list the nonzeros in a row or column you can process the $n/\beta$ blocks containing it, recursively finding the nonzeros in each block in $O(\beta)$.


What is the significance of abstract linear algebra in machine learning/computer vision research?

In my experience (YMMV) linear algebra is very much used as a tool in Machine Learning and Computer Vision, with little interest in the underlying mathematics.

That said, you'll need a more mathematical understanding than, say, a games programmer or a basic researcher in the natural sciences. Basically you'll need to know enough to take a method like PCA apart and put it back together again, but you don't need to worry about your matrices containing anything other than real values.

It sounds like this course is starting off deeper and more general than you want, but the list of topics suggests that you are moving in the right direction. So long as some attention is given to how to translate the mathematical methods into the computer. It's one thing to suggest that an SVD decomposition exists, and another to actually compute it.

The deep mathematical understanding won't hurt, but there's no guarantee that all of it will be useful to you.


Storage system for large quantities of unique key value pairs optimized for insert

B-trees and their various modified versions are the standard way to index arbitrary data while keeping insert times within a reasonable frame. Insertion happens in O(logn) time, which I believe cannot be improved, unless your key range is limited enough to make a bitmap usable.

That said, there a few things that can make B-trees and their variations faster:

Watch your keys. Non-random keys can cause pathological situations. You are using a hash, so key-dependent pathological situations are rather improbable.
Benchmark the application. Find out if the B-tree implementation achieves that O(logn) time for large datasets. Note: for large datasets. Only compare datasets for which the B-tree size significantly exceeds the size of your physical memory. Smaller datasets will have minimal disk seeks due to the OS cache and will seem lightning-fast. E.g. if you have 4GB of RAM, try comparing an 8GB, a 16GB, a 32GB and a 64GB index. If you do not see an O(logn) time curve, you may have a problem in your specific implementation.
Profile the application. Find out where the bottleneck is. Is it the CPU (not very probable)? Disk seeks (here's my money)? What part of the code produces the bottleneck?
Measure your B-tree index alone without the backing file. Does the application speed-up significantly without the backing file seeks? Would it make sense to store some data (e.g. the hit count) in the B-tree nodes themselves, to avoid the extra seeks? Storing some common data in the B-tree nodes should provide a major performance increase.
Use a shorter and faster intermediate hash. It does not have to be cryptography-level, just sufficiently random. I have used MurmurHash3 with pretty good results. Use that hash as the key in the B-tree, and an external mechanism (e.g. linked lists) to handle collisions. Using shorter keys will speed up your B-tree significantly, because each node can fit more ranges.
Optimise for less I/O and fewer disk seeks. In your case it's quite probable that the performance killer lies in your disk. Try using larger B-tree nodes.


Can all structurally recursive functions be written without explicit recursion using a catamorphism/fold?

Your function is completely structurally recursive on n, so it is pretty much just a change of notation to make it a catamorphism on the natural numbers.

type nat = Z | S of nat

(* cata : α → (α → α) → nat → α *)
let rec cata z s = function
  | Z -> z
  | S n -> s (cata z s n)

(* halting_search : nat → (α → bool) → (α → α) → α → α option *)
let halting_search n =
  cata (fun test next seed -> None)
       (fun recur test next seed ->
         if test seed then
           Some seed
         else
           recur test next (next seed))
       n

For languages with higher-order functions and strictly positive datatypes, having a fold is equivalent in expressive power to permitting structural recursion. However, it is not equivalent in terms of efficiency. If you just have fold, then implementing the predecessor function on the Peano natural numbers is O(n), whereas if you have a case form, it is O(1).

(* This is linear time! *)
pred : nat -> nat option
let pred n = cata None (function
                           | None   -> Some Z
                           | Some n -> Some (S n)) n


András, as you probably know, there are so many examples of what you're talking about that it's almost impossible to know where to start!  However, I think this question can actually be a good one, if people give examples from their own experience where the proof of a widely-believed conjecture in their subarea led to new insights.

When I was an undergrad, the first real TCS problem I tackled was this: what's the fastest quantum algorithm to evaluate an OR of √n ANDs of √n Boolean variables each?  It was painfully obvious to me and everyone else I talked to that the best you could do would be to apply Grover's algorithm recursively, both to the OR and to the ANDs.  This gave an O(√n log(n)) upper bound.  (Actually you can shave off the log factor, but let's ignore that for now.)

To my enormous frustration, though, I was unable to prove any lower bound better than the trivial Ω(n1/4).  "Going physicist" and "handwaving the answer" never looked more appealing! :-D

But then, a few months later, Andris Ambainis came out with his quantum adversary method, whose main application at first was a Ω(√n) lower bound for the OR-of-ANDs.  To prove this result, Andris imagined feeding a quantum algorithm a superposition of different inputs; he then studied how the entanglement between the inputs and the algorithm increased with each query the algorithm made.  He showed how this approach let you lower-bound quantum query complexity even for "messy," non-symmetric problems, by using only very general combinatorial properties of the function f that the quantum algorithm was trying to compute.

Far from just confirming that the quantum query complexity of one annoying problem was what everyone expected it to be, these techniques turned out to represent one of the biggest advances in quantum computing theory since Shor's and Grover's algorithms.  They've since been used to prove dozens of other quantum lower bounds, and were even repurposed to obtain new classical lower bounds.

Of course, this is "just another day in the wonderful world of math and TCS."  Even if everyone "already knows" X is true, proving X very often requires inventing new techniques that then get applied far beyond X, and in particular to problems for which the right answer was much less obvious a priori.


Decentralized algorithm for determining influential nodes in social networks

Decentralized algorithms for variants of this problem have been published in A distributed and privacy preserving algorithm for identifying information hubs in social networks and  Social Influence Analysis in Large-scale Networks.


Automata model with undecidable (or non-context-sensitive) languages and no $\varepsilon$-transitions.

I do not think it is possible at all. Either such automata cannot be recursively defined, or have to make local non-recursive decisions at nodes. The first case is obviously uninteresting, and the latter is equivalent to having undecidable oracles at nodes.


Are there "NP-Intermediate-Complete" problems?

I don't really have references for these results--they aren't hard to prove once you understand Ladner's theorem.

No, for any NP-incomplete set A there is another set B strictly between A and SAT.
These equivalence classes are known as polynomial-many-one degrees. You can embed any finite poset into the degrees below NP. In particular the degrees are not totally ordered or finitely branching.
This all depends on what you mean by "interesting". There is a huge theory of the degree structure of the computable sets (see Soare's book for instance) and many of those questions have not been ported down to polynomial-time sets. For instance, can you have NP sets A and B whose join is equivalent to SAT and whose meet is equivalent to the empty set?


What is the space complexity of calculating Eigenvalues?

The decision versions of many common problems in linear algebra over the integers (or rationals)
are in the class $\mathsf{DET}$, see the paper

Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Structure and Importance of Logspace-MOD Class. Mathematical Systems Theory 25(3): 223-237 (1992)

$\mathsf{DET}$ is contained in $\mathsf{DSPACE}(\log^2)$.

Computing the eigenvalues is a little more delicate:

1) In $\mathsf{DSPACE}(\log^2)$, one can compute the coefficients
of the characteristic polynomial.

2) Then you can use the parallel algorithm by Reif and Neff
to compute approximations to the eigenvalues. The algorithm runs on
a CREW-PRAM in logarithmic time with polynomially many processors,
so it can be simulated with poly-logarithmic space.
(It is not explicitely stated in the paper, but their PRAM should to be
log-space uniform.)
The space used is
 polylogarithmic in the size of
the input matrix and the precision $p$. Precision $p$ means that
you get approximations up to an additive error of $2^{-p}$.

This is a concatenation of functions computable in poly-logarithmic space.
(Output tapes are write only and oneway.)

C. Andrew Neff, John H. Reif: An Efficient Algorithm for the Complex Roots Problem. J. Complexity 12(2): 81-115 (1996)


Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals

Ryan O'Donnell (professor at Carnegie Mellon) has a wonderful undergraduate complexity theory series that goes through the fundamentals quite well, and he's an engaging lecturer. He also has a similar graduate lecture series that mostly picks up where the undergrad series left off.
(Note that this series does not cover logic, and I'm not aware of any videos that do cover that subject.)


Some streaming algorithms use expander graphs. This is a somewhat extreme form of de-randomization though (no random bits, in principle).


No such implication is known.  In particular it may be that $L \ne P = NP$ in which case all problems (including trivial ones) are NP-hard under poly-time reductions (as the reduction can just solve the problem), but trivial ones (in particular ones that lie in L) are surely not P-hard under logspace reductions (as otherwise L=P).

The same goes for NC instead of L.


Minimum Tree-width of circuit for MAJORITY

Answering half of Samir's question.

Let $G=(V,E)$ be a DAG and $V_1,V_2\subseteq V$ be two subsets of vertices of $G$. We denote by $E(V_1,V_2)$ the set of all edges in $G$ with one endpoint in $V_1$ and other endpoint in $V_2$. If $\omega = (v_1,...,v_n)$ is a total ordering of the vertices of $G$ then we let
$$\mathbf{ow}(G,\omega) =
\max_{i}\; |E(\{v_1,...,v_i\},\{v_{i+1},...,v_n\}|$$
denote the width of $\omega$. The online width of $G$ is defined as
$$\mathbf{ow}(G) = \min_{\omega}\; \mathbf{ow}(G,\omega),$$
where the minimum is taken over all topological orderings of the vertices of $G$. Note that the traditional notion of cutwidth of $G$, $\mathbf{cw}(G)$ is defined analogously, except that the minimum is taken over all possible orderings of $G$, irrespectively of whether the ordering is topological or not.
We have the following sequence of inequalities:
$$\mathbf{tw}(G) \leq \mathbf{pw}(G) \leq \mathbf{cw}(G)\leq \mathbf{ow}(G),$$ where $\mathbf{pw}(G)$ and $\mathbf{tw}(G)$ are respectively the pathwidth and the treewidth of $G$.

We claim that MAJORITY of $n$ bits can be computed in online-width $O(\log n)$, and therefore in treewidth $O(\log n)$. The circuit simulates an online algorithm that reads one input bit $b$ at a time and adds $b$ to a counter with $O(\log n)$ bits if and only if $b=1$. At the beggining, the counter is initialized to $0$. At the end the circuit accepts if and only if the value of the counter is greater than n/2. It is easy to see that the gates of a circuit ADD that adds one to the counter register can be topologically-ordered in such a way that it has constant online width, since this circuits just need to implement an carry on operation. The total circuit is a sequence of circuits $C=(ADD_1,ADD_2,...,ADD_n,COMP)$  where the output of $ADD_i$ is plugged to the input of $ADD_{i+1}$, and the output of $ADD_n$ is plugged to the input of COMP. Now if we topologically-order the total circuit $C$ in such a way that all gates of $ADD_i$ appear before the gates of $ADD_{i+1}$ and all gates of $ADD_n$ appear before the gates of COMP, then this topological order has online width $O(\log n)$. This construction is illustrated in Figure 1 of a paper of mine to show that probability amplification can be done in logarithmic online width.

Obs: The depth of the circuit C is $O(n)$.


Real world applications of quantum computing (except for security)

Efficiently simulating quantum mechanics.


Solving a linear diophantine equation approximately

All right, having thought about it more I believe I have an explicit reduction from this problem to extended GCD; I'll explain it in the $n=2$ case, but I believe that it extends to arbitrary $n$.  Note that this finds an $\mathbf{x}$ that minimizes the distance to the hyperplane, but not necessarily the smallest $\mathbf{x}$ (there are in fact infinitely many values that attain the same minimum distance) - I believe the latter problem is also feasible, but haven't given it any real thought yet.  The algorithm is based on a few simple principles:

If $g=\mathrm{GCD}(a_1, a_2)$, then the set of values taken on by $\mathbf{a}\cdot\mathbf{x} = a_1 x_1 + a_2 x_2$ is precisely $\left\{0, \pm g, \pm 2g, \pm 3g, \ldots\right\}$; furthermore, values $x_1$ and $x_2$ with $a_1 x_1 + a_2 x_2 = g$ can be found efficiently (this is exactly the extended Euclidean algorithm).
The minimum distance from the hyperplane to a point on the lattice is the minimal distance from a point on the lattice to the hyperplane (obvious, but a useful inversion of the problem).
The distance from a given point $\mathbf{x}$ to the hyperplane $\mathbf{a}\cdot\mathbf{y} = b$ is proportional to $\left|\mathbf{a}\cdot\mathbf{x}-b\right|$ (specifically, it's $1/|\mathbf{a}|$ times this value - but since multiplying all distances by this value has no effect on the location of the minimum, we can ignore the normalizing factor).

This suggests the following procedure:

Compute $g=\mathrm{GCD}(a_1,a_2)$, along with $x^0_1, x^0_2$ such that $a_1x^0_1+a_2x^0_2 = g$.
Compute $r = \left\lfloor{b\over g}\right\rfloor$ and calculate $d =\min(b-rg, (r+1)g-b)$; $d$ is the (scaled) minimal distance from the lattice to the hyperplane.  Let $s$ be either $r$ or $r+1$ ($=\left\lceil{b\over g}\right\rceil$, unless $b$ is a multiple of $g$) depending on which one attains the minimal distance.
Compute $x_1 = sx^0_1$ and $x_2 = s x^0_2$; then $\mathbf{a}\cdot\mathbf{x} = sg$ is the nearest multiple of $g$ to $b$, and thus $\left|\mathbf{a}\cdot\mathbf{x}-b\right|$ attains the minimum of this distance over all lattice points.

As far as I know, the exact same procedure should work correctly in arbitrary dimensions; the key is that the $n$-dimensional GCD still satisfies Bezout's identity, and so to find the minimum distance to a lattice point you only have to find the nearest multiple of $g$ to $b$.


Permutations with forbidden subsequences

It's NP-complete for $k=3$ by a reduction from betweenness. In the betweenness problem, one is given $n$ items to be totally ordered, and constraints on some triples of items forcing one item of the triple to be between the other two. In your problem, the same constraint can be forced by forbidding all the subsequences on three elements that do not place the middle element in the middle. But betweenness is known to be NP-complete: see J. Opatrny, Total ordering problem, SIAM J. Comput., 8 (1979), pp. 111–114.


Can relativization results be used to prove sentences formally independent?

There are no "natural" complexity-theory questions that have been proved independent of really powerful formal systems, such as ZF set theory or Peano Arithmetic.  (One could certainly construct such a question artificially, by playing games with Gödel sentences.)

On the other hand, yes, you can interpret the statement that a sentence S relativizes as meaning that S can be proved from a certain restricted set of axioms (basically, the "Cobham axioms" that characterize closure under polynomial-time reductions).  Conversely, the existence of oracles making S either true or false is equivalent to S being independent of those particular axioms.  Here's the paper to read about this, by Arora, Impagliazzo, and Vazirani.

This is a very pretty connection mathematically---but it's worth stressing that we do have techniques (such as arithmetization) that go outside the relativizing axioms.  And I don't know of any results of the form "if natural open problem P can be solved at all, then it can also be solved in a relativizing way."


$\mathsf{UP} \neq \mathsf{EXP}$ is open. A UP-generic oracle* should make $\mathsf{P} \neq \mathsf{UP} = \mathsf{EXP}$, and since $\mathsf{UP} \subseteq \mathsf{\oplus P} \subseteq \mathsf{EXP}$ relative to any oracle, this should resolve 1. (I say "should" because I haven't checked all the details...)

*UP-generic oracles are discussed, for example, by Fenner-Fortnow-Kurtz-Li (author's freely available version) and also (shameless self plug) a quick tutorial in Section 5.1 here (author's free version)


Anyone recognize this as a special type of multi-commodity flow problem?

I think you can solve this as a single shortest path problem with respect to arc weights
$$\overline{w}_{ij}=\min\{-w_{ijp}\ :\ p\in\{1,\ldots,m\}\}.$$
For every arc $(i,j)$ fix some $p(i,j)\in\{1,\ldots,m\}$ with $-w_{ijp(i,j)}=\overline{w}_{ij}$. If you have a shortest path $\pi$ with respect to $\overline{w}$, you can put
$$y_{ijp}=\begin{cases} m & \text{if }(i,j)\in\pi\text{ and }p=p(i,j),\\ 0 & \text{otherwise.}\end{cases}$$
For the $l$- and $z$-variables you do the following.

If $(1,j)\in\pi$ is the arc leaving 1 then
$$z_{1q}=\begin{cases}m-1 & \text{for } q=p(1,j)\\ 0 & \text{for } q\neq p(1,j)\end{cases}$$
$$l_{1q}=\begin{cases}1 & \text{for } q\neq p(1,j)\\ 0 & \text{for } q= p(1,j)\end{cases}$$

If $(i,n)\in\pi$ is the arc entering $n$ then
$$z_{nq}=\begin{cases}0 & \text{for } q=p(i,n)\\ 1 & \text{for } q\neq p(i,n)\end{cases}$$
$$l_{1q}=\begin{cases}0 & \text{for } q\neq p(i,n)\\ m-1 & \text{for } q= p(i,n)\end{cases}$$

If $(j,i)$, $(i,j')$ are two consecutive arcs of $\pi$ then you put $l_{ip}=z_{ip}=0$ if $p(j,i)=p(i,j')$, and otherwise
$$z_{iq}=
\begin{cases}
m & \text{for } q=p(i,j')\\
0 & \text{for } q\neq p(i,j')
\end{cases}$$
$$l_{iq}=
\begin{cases}
m & \text{for } q=p(j,i)\\
0 & \text{for } q\neq p(j,i)
\end{cases}$$

And LP duality tells you that this is optimal.


Linear Datalog has a lot of connections with the complexity of constraint satisfaction and logic. Like @ian said, the intuitive way to view a linear Datalog program is a Datalog program who's proof trees are basically paths.

In constraint satisfaction, we are interested in problems of the following form. Let $\mathbf{B} = (B, R_1^{\mathbf{B}}, R_2^{\mathbf{B}}, \ldots, R_n^{\mathbf{B}})$ be a relational structure (that is, a domain $B$ with a family of relations over that domain). We ask, what relational structures $\mathbf{A} = (A, R_1^\mathbf{A}, R_2^\mathbf{A}, \ldots, R_n^\mathbf{A})$ admit a homomorphism to $\mathbf{B}$ (i.e. a function $f: A \rightarrow B$ such that if $(a_1, a_2, \ldots, a_n) \in R_i^{\mathbf{A}}$ then $(f(a_1), f(a_2), \ldots, f(a_n)) \in R_i^\mathbf{B}$)? We will denote this decision problem by CSP($\mathbf{B}$).

It turns out that the complexity of CSP($\mathbf{B}$) can be neatly characterized by linear Datalog. Namely, if co-CSP($\mathbf{B}$) can be expressed in linear Datalog, then CSP($\mathbf{B}$) is in $\mathsf{NL}$. This characterization of the expressibility of the complement problem in linear Datalog is equivalent to a number of different properties, such as $\mathbf{B}$ having bounded pathwidth duality, a winning strategy in a certain kind of pebble game, and expressibility in certain fragments of infinitary logic (logics extended with infinite conjunctions).

For more information, see

V. Dalmau. Linear Datalog and Bounded Path Duality of Relational Structures. Available at Logical Methods in Computer Science (here), 2005.

Another good survey paper with a section devoted to this would be

A. Bulatov, A. Krokhin, B. Larose. Dualities for Constraint Satisfaction Problems. Lecture Notes in Computer Science, Vol. 5250:93-124, 2008. Available here.


Is there notation for converting a multi-set to a set?

Seeing how this question doesn't appear to be set to be moved to Math.SE (where it would properly belong), I'll answer it here.

Multisets are an awkward case of a perfectly natural mathematical object which never really got a standard notation — likely because multisets took much longer to be interesting to logicians. As a corollary, there is no standard notation for extracting a set from a multiset.

There are some natural ways to go about defining a reasonable notation for set-extraction:

Intersection. If your multiset is drawn from a universe $\mathbf U$, you can simply take the intersection of your multiset $\mathcal M$ with the universe, $\mathcal M \cap \mathbf U$. This is to me already a good notation, and is a good way of describing any other notation you might want to define. For your example, we may write $\{1,2,3\} = \{1,2,2,3\} \cap \mathbb N$.
Multiplicity filtering. Perhaps you are sometimes interested in when there are at least n of some of the elements; you can consider the set of such elements. One standard(-ish) notation for "$a$ is an element of $\mathcal M$ at least $n$ times" is $a \in^n\! \mathcal M$.
Consider defining
$$ \big.^n\!\mathcal M := \Bigl\{ a \in \mathcal M \;\Big|\; a \in^n\! \mathcal M \Bigr\} $$
in which case you have the identity $\big.^1\!\mathcal M = \mathcal M \cap \mathbf U$.
A set (forgetful) functor. Don't make things hard on yourself! You want the set associated with a multiset $\mathcal M$? Define $\mathbf{Set}(\mathcal M) = \big.^1\!\mathcal M$ to be that set!

There are any number of approaches to doing this. Of course, you should Google long and hard to see if there is any convention which your target audience is likely to be using. But if there isn't, then bear in mind that — by that very fact — there is no notation which you can assume your audience will be familiar with: so define your notation explicitly!

Remarks

The following are really extended comments...

Notation

It's pretty clear that $\{1,2,2,3\}$ can be used to represent a multiset in which there are two 2s, it will actually get in the way of how some people learned sets: not just that it has no repetition, but that repitition doesn't matter. Some schools teach that $\{1,2,2,3\} = \{1,2,3\}$, and in the standard set-theoretic construction of the ordered pair $(a,b) := \{\{a\},\{a,b\}\}$, one situation which must be addressed is the case of  where $a = b$, in which case one obtains the set $\{\{a\}\}$. Bear this in mind, if you want to use multisets and sets side-by-side, and consider using a different notations entirely for multisets:

Square brackets notation (as noted by Wikipedia):$[1,2,2,3]$
Double-square brackets or double-set braces notation (as found here and here):$ [\![1,2,2,3]\!] \qquad \{\!\{ 1,2,2,3 \}\!\}$
(bearing in mind that $\{\!\{ 1,2,2,3 \}\!\}$ looks a lot like the singleton set containing $\{1,2,2,3\}$).
Bag notation as provided by the stmaryrd LaTeX package (as illustrated here):

Multisets versus characteristic functions

You could try to treat multisets as being identical with their characteristic functions, so that $\{1,2,2,3\}$ can be identified with a function $f$ such that $f(2) = 2$, $f(1) = f(3) = 1$, and $f(n) = 0$ otherwise. Just as we sometimes identify languages $L \subset \{0,1\}^\ast$ with their characteristic functions $L: \{0,1\}^\ast \to \{0,1\}$, this is okay as an abuse of notation.
But taking this too seriously has problems. For instance, you might not be pre-occupied with sums, but does $\mathrm{Sum}(f)$ represent $\sum_n f(n)$ (the sum of the values of $f$), or $\sum_n n\cdot f(n)$ (the sum of the elements of the multiset represented by $f$)? If you intend to act as though multisets "really are" their histograms, you must be prepared for such potential confusions by people who assume you have important reasons to choose that convention.

I would recommend that you treat multisets as first-class entities, which have characteristic functions, but are not the same as characteristic functions.
That is, that you should keep the distinction between the collection and the function, unless you feel that identifying the two is very useful or important.


How does the BosonSampling paper avoid easy classes of complex matrices?

Thanks for your question!  There are two answers, depending on whether you're interested in the hardness results for exact or approximate BosonSampling.

In the exact case, we prove that given any n-by-n complex matrix A, you can construct an optical experiment that produces a particular output with probability proportional to |Per(A)|2.  This, in turn, implies that no classical polynomial-time algorithm can sample from exactly the same distribution as the optical experiment (given a description of the experiment as input), unless P#P = BPPNP.  In fact we can strengthen that, to give a single distribution Dn (depending only on the input length n) that can be sampled using an optical experiment of poly(n) size, but that can't be sampled classically in poly(n) time unless P#P = BPPNP.

In the approximate case, the situation is more complicated.  Our main result says that, if there's a classical polynomial-time algorithm that simulates the optical experiment even approximately (in the sense of sampling from a probability distribution over outputs that's 1/poly(n)-close in variation distance), then in BPPNP, you can approximate |Per(A)|2, with high probability over an n-by-n matrix A of i.i.d. Gaussians with mean 0 and variance 1.

We conjecture that the above problem is #P-hard (at the very least, not in BPPNP), and pages 57-82 of our paper are all about the evidence for that conjecture.

Of course, maybe our conjecture is false, and one can actually give a poly-time algorithm to approximate the permanents of i.i.d. Gaussian matrices.  That would be a phenomenal result!  However, the whole point of 85% of the work we did was to base everything on a hardness conjecture that was as clean, simple, and "quantum-free" as possible.  In other words, instead of the assumption

"approximating the permanents of some weird, special matrices that happen to arise in our experiment is #P-hard,"

we show that it suffices to make the assumption

"approximating the permanents of i.i.d. Gaussian matrices is #P-hard."


When studying the computational complexity of functions $\{0, 1\}^\ast \to \{0, 1\}^\ast$, is it enough to restrict to $\{0, 1\}^\ast \to \{0, 1\}$?

I think you are right that the author's phrasing doesn't seem to immediately suggest a correct formalization of equivalence, but the idea is correct. I think the easiest formalization is the following.

  Given $f: \{0,1\}^* \to \{0,1\}^*$, define:

  $\bar{f}: \{0,1\}^* \times \mathbb{N} \to \{0,1\}$ to be $\bar{f}(x,j) = 1$ iff $|f(x)| \leq j$. (Here $|\cdot|$ is string length.)
  $\hat{f}: \{0,1\}^* \times \mathbb{N} \to \{0,1\}$ to be $\hat{f}(x,j) = f(x)_j$, i.e. the $j$th bit of $f(x)$. If $j$ is larger than $|f(x)|$, the output of $\hat{f}(x,j)$ can be, let's say, always $0$.

Now I will leave it as an exercise to prove that if $f$ is computable in polynomial time, then $\bar{f}, \hat{f}$ are in P; and if $\bar{f}, \hat{f}$ are in P, then $f$ is computable in polynomial time. You do need the idea you mentioned, that $|f(x)| \leq |x|^c$ for some $c$.


What's the “smallest” complexity class for which an $\omega \hspace{.02 in}(n)$ circuit lower bound is known?

$S^p_2$ and $PP$ are both known not to have $n^k$-circuits for any fixed k and there is no known containment between them. Details in my blog post.

Update: As Rickey Demer points out, these results do not necessarily give a language with a lower bound for all $n$ in $S_2^p$. I think the $\Delta^p_3$ is probably the best known. Since $PP$ has complete sets you might be able to get a all $n$ bound but I don't have a full proof.


Is abelian group isomorphism in $\mathsf{AC^0}$?

Contrary to what is stated in the question, abelian group isomorphism is not known to be in $\mathrm{TC^0}$. Needless to say, this also means it is not known to be in $\mathrm{AC^0}$.
What is known is the following observation from [1]. Let $\mathrm{pow}$ denote the following problem: given a multiplication table of an abelian group $(A,{\cdot})$, elements $a,b\in A$, and $m$ in unary, determine if $b=a^m$. The structure theorem for finite abelian groups easily implies that if $A,B$ are two such groups of size $n$, then
$$\tag{$*$}A\simeq B\iff\forall m\le n\:\bigl|\{a\in A:a^m=1\}\bigr|=\bigl|\{b\in B:b^m=1\}\bigr|.$$
Since we can count polynomial-size sets in $\mathrm{TC^0}$, we obtain

Proposition 1: Abelian group isomorphism is computable in $\mathrm{TC^0(pow)}$.

Now, $\mathrm{pow}$ is clearly computable in L, and as shown in [2], also in the class FOLL. Thus,

Corollary 2: Abelian group isomorphism is computable in $\mathrm{L}$ and in $\mathrm{TC^0(FOLL)}$.

It is not known if $\mathrm{pow}$ is computable in $\mathrm{TC^0}$.
It seems that Corollary 2 is the best known result when it comes to the usual, “polynomial-size”, circuit classes. However, I observe that the problem is in the quasipolynomial version of $\mathrm{AC^0}$:

Proposition 3: Abelian group isomorphism is computable by a uniform sequence of quasipolynomial-size constant-depth Boolean circuits; more specifically, it is in $\Sigma_2\text-\mathrm{TIME}\bigl((\log n)^2\bigr)$.

(This translates into a uniform family of depth-3 circuits of size $2^{O((\log n)^2)}$, where the bottom disjunctions have fan-in only $O\bigl((\log n)^2\bigr)$; this is often called “depth $2\frac12$”.)
Proposition 3 is again a consequence of the structure theorem for finite abelian groups: any such group can be written as a direct sum of $O(\log n)$ cyclic subgroups, thus groups $A$ and $B$ are isomorphic iff they can be written as direct sums of cyclic subgroups with matching orders: that is, if $|A|=|B|=n$, then $A\simeq B$ iff

there exist

a sequence $\{m_i:i<k\}$ of $k\le\log n$ integers $m_i\le n$

sequences $\{a_i:i<k\}\subseteq A$ and $\{b_i:i<k\}\subseteq B$

such that

$\prod_{i<k}m_i=n$

$a_i^{m_i}=1$ and $b_i^{m_i}=1$ for each $i<k$

for all sequences $\{r_i:i<k\}$ of integers $0\le r_i<m_i$, not all zero:
$\prod_{i<k}a_i^{r_i}\ne1$ and $\prod_{i<k}b_i^{r_i}\ne 1$

The two main quantifiers are highlighted. To see that the stated bounds are not exceeded, we need to show that the identities $\prod_{i<k}a_i^{r_i}=1$ can be checked in $\mathrm{NTIME}\bigl((\log n)^2\bigr)$. This can be done by successively guessing and verifying values of the partial products $\prod_{i<l}a_i^{r_i}$ for $l=0,\dots,k$; moreover, for each $i$, we similarly guess and verify $O(\log r_i)$ partial results of the computation of $a_i^{r_i}$ by repeated squaring. In total, this makes $O\left(\sum_i\log r_i\right)\subseteq O\left(\sum_i\log m_i\right)\subseteq O(\log n)$ guesses, each of which takes $O(\log n)$ time to verify.
There is another way to prove Proposition 3: namely, note that in $(*)$, we only need to consider $m$ that are prime powers: $m=p^e$. In that case, the two offending sets that we need to count also have sizes that are powers of $p$; in particular, if they are unequal, they differ by a factor of at least $p$. Thus, it is enough to count the sizes of the two sets approximately. This can be done in quasipolynomial $\mathrm{AC^0}$ using Sipser’s coding lemma. And as I’ve already shown, $\mathrm{pow}$ can be computed in quasipolynomial $\mathrm{AC^0}$ by repeated squaring.
One consequence of Proposition 3 is that if the abelian isomorphism problem turns out not to be in $\mathrm{AC^0}$, this might be rather difficult to prove: in particular, one cannot just reduce PARITY or MAJORITY to the problem, as these require exponential-size bounded-depth circuits, not quasipolynomial. Even if we attempt to reduce PARITY on $m\ll n$ bits to the problem, there is not much room for the parameters: specifically, PARITY of super-polylogarithmically many bits is not computable by quasipolynomial-size constant-depth circuits, and PARITY of polylogarithmically many bits is already computable in $\mathrm{AC^0}$ by divide and conquer.
References:
[1] Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner: Graph isomorphism is not $\mathrm{AC^0}$-reducible to group isomorphism, ACM Transactions on Computation Theory 5 (2013), no. 4, article no. 13, doi: 10.1145/2540088.
[2] David Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie: On the complexity of some problems on groups input as multiplication tables, Journal of Computer and System Sciences 63 (2001), no. 2, pp. 186–200, doi: 10.1006/jcss.2001.1764.


What are semantic classes that have a syntactic equivalent?

FWIW, the ostensibly semantic class APP defined in [1] was shown to be syntactic in [2].

[1] Valentine Kabanets, Charles Rackoff, Stephen A. Cook, Efficiently
  approximable real-valued functions, ECCC Report TR00-034, 2000.

[2] Emil Jeřábek, Approximate counting in bounded arithmetic, Journal of Symbolic Logic 72 (2007), no. 3, pp. 959–993. doi, preprint


Counting solutions of Monotone-2CNF formulas

Some observations, not an answer.

Further to the note to the question, any combination of 3 literals can be expressed in terms of any other combination of literals on the same variables, together with a small number of terms that the oracle can provide.  This follows from looking at the Venn diagram of 3 intersecting sets, and expressing each of the 8 regions in terms of the other regions.  Note that this does not require the formula to be either monotone or 2CNF.

It is also clear that the number of solutions satisfying any 3-literal conjunct can be expressed as the sum of $2^{n-3}$ terms, each of which is either 0 or 1, expressing a particular assignment to all variables.  Each of these can be evaluated in linear time, but there are exponentially many terms to evaluate, so this doesn't satisfy the requirements.

Hence the question is really about whether it is possible to exploit the property of being monotone 2CNF to compress this exponential-size expression to polynomial size.

I tried to look at a simpler question, restricting the oracle to just an advice string with the number of solutions, when the counts for single or pairwise literal combinations are not available.  I cannot see any way to exploit knowledge of the number of solutions to obtain a quick calculation of the number of solutions with respect to any single literal.

Is there something about monotone 2CNF that would allow the number of solutions in $S$ containing $x_1$ to be obtained quickly, if one knew $|S|$?


You can reduce the SEPARATED k-SUM problem to a (k+1)-SUM problem in the following way:

Given $X_1,...,X_n$, let $b$ such that $2^b > \max( abs(X_1) \cup ... \cup \;abs(X_n))$, where $abs(X_i) = \{ |x| \mid x \in X_i \}$, and let $c$ such that $2^c > k 2^b$

For  $i = 1,...,k$ build $Y_i = \{ 2^{c+ki} + 2^{b} + x_j \mid x_j \in X_i \}$;
let $u = - \sum_{i=1}^k 2^{c+ki} -k2^b$

Build an equivalent (k+1)-SUM problem picking $X =  \{ u \} \cup Y_1 \cup ... \cup Y_k$

Note that every $Y_i$ contains only positive elements.

Informally we require a $k+1$ elements subset $C$ from $X$ whose elements sum to zero.
We cannot build a solution only with the negative element $u$; so we must include in $C$ at least one element $y$ from one of the $Y_i$; but the $2^{c+ki}$ "component" of $y$ can be balanced only if $u$ is also included; but including $u$ implies that exactly one of the elements of each $Y_i$ is included (the  $- \sum_{i=1}^k 2^{c+ki}$ component of $u$ allows to keep the separation between the elements of the original $X_i$). But we also have $\sum_{j=1}^k (2^b + x_j) = k2^b$ and this implies that the original $x_j$s (coming from distinct $X_i$s as seen above) sum to zero.


Are patents good sources for academic research?

In general, a clear NO. Typically, patents are intentionally written in a diffuse language to cover as much ground as possible (without incuring the danger of claiming something already known for oneself).  They are not written in a way that they can be used by an engineer or understood by a scholar. They are written such that the courts later can decide in favor of the patent holder or their representative.


Extensional characterization of non-deterministic finite state transductions

The best reference is probably the book Rational transductions and context-free languages by J. Berstel.

First recall that a function $f$ from $A^*$ to $B^*$ is realized by a transducer (= non-deterministic FST) if and only if it is rational, that is, if the set $\{(u, f(u)) \mid u \in A^* \}$ is a rational subset of $A^* \times B^*$.

You can find several other relevant characterizations of rational functions in Chapter 4 of Berstel's book.

(Eilenberg 1974. See Prop. 4.1 and Corollary 4.3) A function from $A^*$ to $B^*$ is rational if and only if it can be realized by a normalized unambiguous transducer.
(Schützenberger 1976. See theorem 4.5) A function is rational if and only if it admits a semimonomial representation.
(Elgot and Mezei 1965. See Theorem 5.2) A function is rational if and only if it is the composition of a left sequential transduction by a right sequential transducer.

See also A. Arnold and M. Latteux, A new proof of two theorems about rational transductions, Theoret. Comput. Sci. 2 (1979), 261–263.


Such graphs are called well-covered graphs.  Here is a recent paper on the subject that lists several useful references.  As Suresh mentioned, the recognition problem is co-NP-complete.

Note that the independent sets of a graph form an abstract simplicial complex.  Simplicial complexes that arise in this way are called "independence complexes" or "flag complexes."  A simplicial complex is said to be pure if every maximal simplex has the same cardinality.  So you may find some relevant papers by searching for "pure independence complex" or "pure flag complex."


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

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

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

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


Trade off between time and query complexity for total functions

Here is a sketch of an attempt at partial separation. I was trying to improve this over the past two weeks into a full answer, but haven't made much progress. Hopefully someone else knows how to extend it.

Let

\[f_{n,m}: \{0,1\}^n \times \{0,1\}^{{m \choose 2}} \rightarrow \{0,1\}\]

So we have a total function on tuples.

$f_{n,m}(x,y)$ returns $1$ if $x = 1^n$ and if $y$ interpreted as the edges of a graph has a clique or independent graph of size $n$. Otherwise, it returns $0$.

Thus if $R_n$ is the $n$-th diagonal Ramsey number then for $m \geq R_n$ and all $y \in \{0,1\}^{{m \choose 2}}$ we have $f(1^n,y) = 1$. Thus, if we can compute $R_n$ on an input of $1^n$ then we don't have to read the bits of $y$ if $m$ is large enough, and the query complexity of the query-optimal algorithm drops to $n$.

However, $R_n$ is harder to compute on an input of $1^n$ than it is to check if a graph given by edges $y$ has a clique of independent set of size $n$ on input $(1^n,y)$. Thus, a time-optimal algorithm can't afford to compute $R_n$. It could, instead use some approximation $\tilde{R}_n > R_n$. For $m < \tilde{R}_n$ a time-optimal algorithm will read at least some bits of $y$.

Thus, for $R_n \leq m < \tilde{R}_n$ the query-optimal algorithm will use more time to make fewer queries than the time-optimal algorithm.

This approach can be made slightly less hand-wavy (or generalized to other Ramsey-like problems) but I think even the more rigorous attempt doesn't fully answer the question.


I posted this to TYPES, but its probably worth copying here as well:

In "The system F of variable types, fifteen years later", Girard
remarks  that there was no particular reason for the name F:

  However, in [3] it was shown that the obvious rules of conversion for
   this system, called F by chance, were converging.

There may be another explanation in his thesis, but I haven't read it
since unfortunately I am not fluent in French.
However, since I am semi-literate in German, I did take a look at
Gödel's paper "Über eine noch nicht benüzte Erweiterung des finiten
Standpunktes", where System T (and the Dialectia interpretation for it)
was introduced. He names this system in a parenthetical aside:

  Das heisst die Axiome dieses Systems (es werde T genannt) sind formal
  fast dieselben wie die der primitiv rekursiven Zahlentheorie [...][1]

However, the previous page and a half were spent talking about the type
structure of system T, so it is reasonable to guess that T stands for
"types". But, no explicit reason is given in print.

[1] "This means the axioms of this system (dubbed T) are nearly
the same as those of primitive recursive number theory [...]"


Is this constrained planar triangulation algorithm $O(m \log m)$?

Unfortunately, this algorithm is $\Omega(n^2)$ even if no unnecessary vertices are generated.  If the $S_i$ form a convex polygon inside $T$, the BSP tree is degenerate regardless of the order in which segments are inserted.


What is an algorithm to find a minimum vertex cover on a bipartite graph with weighted vertices?

The weighted vertex cover problem can be formulated as an Integer Program (see http://en.wikipedia.org/wiki/Vertex_cover). When the input graph is bipartite, the constraint matrix of this IP is totally unimodular. Hence this IP can be solved in polynomial time.

For more details of total unimodular matrices and the corresponding algorithms, see the excellent (three volume) book by Alexander Schrijver.


Relation between interval temporal logic and linear temporal logic

The question you ask is more complex than it seems. ITLs have been defined in different ways and fashions, and the answer depends on the particular definition and the particular semantics. To get an intuition, you have to decide first if points are to be considered special intervals or excluded by the semantics; the second choice is more common, and it makes more difficult the comparison. I suggest to check, first, the webpages

1.http://perseo.dif.um.es/~guido/publications.html

2.https://itl.dimi.uniud.it/

to get an idea of the last 10 years of research on this topic. Second, you can contact me to discuss more in particular your question (my address is on the link number 1).

cheers


I show a reduction from positive partitioned 2-DNF assignment counting (see proof of 5.1 in [http://www.vldb.org/conf/2004/RS22P1.PDF] for details and inspiration of my proof). This problem asks to count the number of valuations that satisfy a formula of the form $\Phi: \bigvee_{(i,j) \in E} X_i Y_j$ with $E \subseteq \mathbb{N}^2$, where the $X_i$ and $Y_j$ are pairwise distinct variables.

Represent the positive partitioned 2-DNF as one vertex $x_i$ per variable $X_i$ and one vertex $y_j$ per variable $X_j$ and an edge from $x_i$ to $y_j$ for each $(i, j) \in E$.

I add a source vertex $s$ and an edge from $s$ to each $x_i$ with parameter $p=1/2$, so with probability $1/2$ the distance is $1$ and with probability $1/2$ it is $>1$. Likewise I add an edge from each $y_j$ to the target vertex $t$ with the same distribution. Up to the exact value of edges with length $>1$, is a clear probability-preserving bijection between valuations of the $X_i$ and $Y_j$ and possible worlds of this graph: for a valuation $\nu$, the corresponding graph is the one where the probabilistic edge adjacent to $X_i$ has length $1$ iff $\nu(X_i) = 1$ and length $>1$ otherwise, and likewise for the $Y_j$.

I set $k=3$. I claim that the probability that there is a path from $s$ to $t$ is the number of valuations that satisfy $\Phi$ divided by $2^N$, where $N$ is the number of variables. Indeed this is clear as a valuation is true iff some adjacent pair of $X_i$ and $Y_j$ is true iff the incident edges to the corresponding $x_i$ and $y_j$ both have length $1$ in the corresponding world.
Note that the exact length of any edge of length $>1$ is irrelevant as the structure of the graph ensures it can never be part of a path of length $3$ from $s$ to $t$: there are only edegs from $s$ to the $x_i$, from the $x_i$ to the $y_j$, and from the $y_j$ to $t$.


Regarding Beggar-My-Neighbour

Paulhus (1, p.164) wrote in 1999:

  If $C$ is a full deck of cards, does ${D_{2}}^{'}(C)$ have a cycle? We
  leave  this question unanswered except to say that we have been unable
  to find one in
  3.2 billion randomly chosen deals.

But Conway et al. (2, p.892) wrote in 2006:

  Strip-Jack-Naked, or Beggar-My-Neighbour **1

  Another problem that took almost 47 years to solve concerns this old
  children’s game. Each of the two players starts with about half of the
  cards  (held face-down), which they alternately turn over onto a
  face-upwards “stack”  on the table, until one of them (who's now “the
  commander”) first deals one of  the “commanding cards” (Jack, Queen,
  King, or Ace).

  After one of these has been dealt, the other player (now “the
  responder”) turns  over cards continuously until EITHER. **2 a new
  commanding card appears (when  the players change roles **3) or
  respectively 1, 2, 3, or 4 non-commanding cards  have been turned
  over. In the latter case, the commander turns over the stack  and
  ajoins it to the bottom of his hand. The responder then starts the
  formation  of a new stack by turning over his next card, and play
  continues as before.

  A player who acquires all the cards is the winner and in real games,
  it seems  that someone always does win. The interesting mathematical
  question, posed by  one of us many years ago, was “is it really true
  that the game always ends?”  Marc Paulhus has recently found the
  answer to be “no!”. About 1 in 150,000 games  (played with the usual
  52 cards) goes on forever.

  We are fairly confident that no one person has played the game
  anything like  that number of times, so the chance (with random
  shuffling) of experiencing a  non-terminating game in a lifetime’s
  play must be very small indeed.

  Just as surely, however, the total number of times this game has been
  played by  the World’s **4 children must be significantly larger than
  150,000, so many of  them will have been theoretically non-terminating
  ones. We imagine, though, that  in practice most of them actually did
  terminate because someone made a mistake.

Unfortunately I was not able to found in (2) any reference to the discovery of Paulhus... I would love to see a sequence of cards that gives a non-terminating game in order to say that the problem is solved.

In 2013, Lakshtanov and Aleksenko (3) wrote:

  For card games of the Beggar-My-Neighbor type, we prove finiteness of
  the mathematical expectation of the game duration under the conditions
  that a player to play the first card is chosen randomly and that cards
  in a pile are shuffled before being placed to the deck. The result is
  also valid for general-type modifications of the game rules. In other
  words, we show that the graph of the Markov chain for the
  Beggar-My-Neighbor game is absorbing; i.e., from any vertex there is
  at least one path leading to the end of the game.

but their rules are not the ones I followed when I played the game when I was a child ;-)

To the best of my knowledge the longest Beggar-my-Neighbour game was found in 2014 by William Rucklidge with 7960 cards:

1: -J------Q------AAA-----QQ-
2: K----JA-----------KQ-K-JJK

Regarding Cavacamicia

I usually played it with a 40 cards deck, simulations with an half deck (only 20 cards) gives 16 non terminating games on a total of 3.448.400 games.

Bibliography

(1)
PAULHUS, Marc M. Beggar my neighbour. American Mathematical Monthly, 1999, 162-165.
http://www.jstor.org/stable/2589054

(2)
BERLEKAMP, Elwyn R.; CONWAY, John H.; GUY, Richard K. Winning Ways for Your Mathematical Plays, Volume 4. AMC, 2003, 10: 12.
http://www.maa.org/publications/maa-reviews/winning-ways-for-your-mathematical-plays-volume-4

(3)
LAKSHTANOV, Evgenii Leonidovich; ALEKSENKO, Alena Il'inichna. Finiteness in the Beggar-My-Neighbor card game. Problems of Information Transmission, 2013, 49.2: 163-166.
http://dx.doi.org/10.1134/S0032946013020051


In what class are randomized algorithms that err with exactly 25% chance?

On a side note, it's not clear that EBPP is a robust class. For example, if instead of allowing the algorithm to flip an unbiased coin, if it were given an unbiased 3-sided coin, or a 6-sided die, it's not clear that you get the same class. BPP remains the same if you change these details.

Anyway, your primary question is whether EBPP is equal to BPP or not. It seems to me that EBPP is closer to P than it is to BPP. Consider the query complexity or oracle version of these classes where they have access to a large input string and have to make queries to learn bits of this string. If you have a P algorithm that computes a function $f$ with $Q$ queries, then there exists an exact representing polynomial of degree $Q$ for $f$ over $\mathbb{R}$. (This is the usual polynomial method argument.) On the other hand, if you have a BPP algorithm, then you get a degree $Q$ polynomial over $\mathbb{R}$ that approximates $f$ in the sense that its value is close to the value of $f$ at every input.

Given an EBPP algorithm for a function $f$, we can construct a polynomial that outputs 1/4 when the answer is NO and 3/4 when the answer is YES. By subtracting 1/2 and multiplying by 2, you can get an exact representing polynomial, just like in the case of P. This suggests to me that EBPP is closer to P.

This observation can also be used to show an oracle separation between EBPP and BPP. Consider the promise-Majority problem where you're promised that the input has either more than 2N/3 1s or less than N/3 1s and you have to decide which is the case. This is clearly in BPP. Using the polynomial argument described above it can be shown that this function requires $\Omega(N)$ queries for an EBPP machine.  But note that you can also prove an oracle separation the other way, between P and EBPP. So maybe oracle results don't say much for this problem? Or maybe what they say is that it will be hard to show equality in either direction.


Exponential blowup in Simple Proof of a theorem of Statman by Mairson

Ok, I think I've got it.

$eq_{k+1}$ calls (indirectly) $eq_k$, so, if I call $subset_{k+1}$ twice, I fall in an exponential blowup because of the two recursive calls of $eq_k$: it is simple to see with a "linear recurrence relation of constant order".


TCS conferences for undergraduate students?

The POPL-colocated PLMW, which you mentioned, certainly provides travel support for undergraduate as well as graduate students.  I personally know undergrads who've been supported. If you're interested in PL research (of any kind, not just POPL-like research) I encourage you to apply.

The ACM student research contest (of which the ICFP SRC is a part) includes categories for both undergraduates and graduates. For SRC at SIGPLAN affiliated conferences like ICFP or PLDI, you can apply to the SIGPLAN PAC program for travel support.


It depends on what kind of a "beginner" level you wish to have. I don't think there is a real good undergraduate level text on proof complexity (this is probably true for most specialized sub-areas in complexity). But for a beginner (graduate level) sources, I would recommend, something like understanding well the basic exponential size lower bound on resolution refutations of the pigeonhole principle (via random restrictions, width-size tradeoff and feasible interpolation), and to expand from that point further. This could be achieved (approximately) as follows:

Stasys Jukna, Extremal Combinatorics With Applications in Computer Science, 2001, Springer-Verlag, Section 4.8.
Eli Ben-sasson and Avi Wigderson, Short Proofs are Narrow - Resolution made Simple (2000), JACM.
P. Beame and T. Pitassi, Propositional proof complexity: Past, present, and future, Current trends in theoretical computer science: Entering the 21st century (G. Paul, G. Rozenberg, and A. Salomaa, editors), World Scientific Publishing, 2001, pp. 42--70.
Pavel Pudlák, Lower bounds for resolution and cutting planes proofs and monotone computations, The Journal of Symbolic Logic, vol. 62 (1997), no. 3, pp. 981-998.

You can also consult the more self contained and lengthy text:

Peter Clote and Evangelos Kranakis, Boolean Functions and Computation Models (Chapter 5)

For the more logical side of proof complexity, as Kaveh suggested, you can start reading the first chapters of:

Stephen Cook and Phuong Nguyen, Logical Foundations of Proof Complexity (Perspectives in Logic, Cambridge Press, 2010).


TSP in bounded tree-width (or bounded branch width) graphs

TSP is the optimization version of HAMILTONIAN CYCLE, which can be expressed by an MSO-formula (Monadic Second-Order Logic) with edge-set quantifications ($MSO_2$, also known as MSO in the incidence-graph model) as follows:  Let $hamilton(F)$ express that $F$ is a set of edges of the input graph $G = (V, E)$ such that every vertex is incident to exactly two edges in $F$, and additionally $F$ is connected.   Then
$$\min_{F \subseteq E} \{ \sum_{e \in F} w(e) : G \models hamilton(F)\},$$
where $w(e)$ denodes the weight of an edge $e$.  Hence, TSP is a Linear MSO-definable Optimization problem.   Via Courcelle's Theorem, TSP can therefore be solved  in linear time on graphs of bounded treewidth (for example, using dynamic programming as mentioned by Andrew in the comment above).


Largest rectangle not touching any rock in a square field

There is an $O(n \log^2 n)$ time algorithm. [Aggarwal and Suri 87]
It seems to be the state of the art.


complexity of deciding whether there's a small polynomial with a given root

Here is an algorithm that solves the problem in time
$$\tilde O\Bigl(\min\Bigl\{(2r+1)^{\frac{d+1}2},p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)}\Bigr\}\sqrt r\Bigl)\subseteq\tilde O(p).$$
The tildes hide $(\log p)^{O(1)}$ factors coming from operations in $\mathbb F_p$ and from implementation of sets by, say, min-heaps.

First, observe that the answer is always YES if $d+1\ge\frac{\log(p+1)}{\log(r+1)}$: there are $(r+1)^{d+1}\ge p+1$ polynomials $P$ of degree at most $d$ with coefficients in $\{0,\dots,r\}$, hence by the pigeonhole principle, there exist two such polynomials $P_0\ne P_1$ such that $\overline{P_0}(f)=\overline{P_1}(f)$. Then $P=P_0-P_1$ satisfies the requirements.

Thus, we may assume without loss of generality
$$d+1\le\left\lfloor\frac{\log p}{\log(r+1)}\right\rfloor.$$
Then (assuming $r\ge1$)
$$(2r+1)^{\frac{d+1}2}\le p^{\frac{\log(2r+1)}{2\log(r+1)}}\le p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)},$$
hence it suffices to find an algorithm working in time
$$\tilde O\Bigl((2r+1)^{\frac{d+2}2}\Bigr).$$

For any $i\le d+1$, let
$$V_i=\{\overline P(f):P\in\mathbb Z[x],P\ne0,\deg(P)<i,\|P\|_\infty\le r\}.$$
Using this notation, the problem is equivalent to finding out if $0\in V_{d+1}$, and we can compute $V_i$ using a simple recurrence. The whole algorithm looks like this:

If $r=0$, output NO.
If $d+1\ge\frac{\log(p+1)}{\log(r+1)}$, output YES.
For each $j=\lceil\log(d+2)\rceil,\dots,1$, compute $V_{\lfloor(d+1)2^{-j}\rfloor}$ and $f^{\lfloor(d+1)2^{-j}\rfloor}$ by using the recurrences
$$\begin{align*}
V_0&=\varnothing,\\
V_{2i}&=V_i\cup\bigl\{a+f^ib:a\in V_i\cup\{0\},b\in V_i\bigr\},\\
V_{2i+1}&=V_{2i}\cup\bigl\{a+f^{2i}b:a\in V_{2i}\cup\{0\},b\in\{\pm1,\dots,\pm r\}\bigr\},
\end{align*}$$
where all the arithmetic operations are modulo $p$.
If $d$ is even, compute $V_{\lceil(d+1)/2\rceil}$ from $V_{\lfloor(d+1)/2\rfloor}$ as above.
If $0\in V_{\lceil(d+1)/2\rceil}$, output YES.
For each $a\in V_{\lceil(d+1)/2\rceil}$, if $-af^{\lceil(d+1)/2\rceil}\in V_{\lfloor(d+1)/2\rfloor}$, then output YES.
Output NO.

It should be clear from the discussion above that the algorithm is correct. Moreover, we have
$$|V_i|\le(2r+1)^i,$$
and since these bounds form a geometric series, it is easy to see that the time needed to compute $V_i$ using the above recurrences is also
$$\tilde O\Bigl((2r+1)^i\Bigr).$$
Thus, the algorithm runs in time
$$\tilde O\Bigl((2r+1)^{\lceil(d+1)/2\rceil}\Bigr)\subseteq\tilde O\Bigl((2r+1)^{(d+2)/2}\Bigr).$$


Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?

I think your focus on the rigid case of GI limits you too much. Instead phrase (non-rigid) GI as an HSP in the same way, but now the goal is to determine the size of the hidden subgroup, or a generating set. The difference between the isomorphic and non-isomorphic cases will be a factor of 2 in the order of the hidden subgroup. If you phrase the problem as finding generators of the hidden subgroup, then the question is just whether any generator switches $\Gamma_1$ and $\Gamma_2$.

Now, an instance of "HSP-GA" corresponding to a graph $\Gamma$ is given by the function from $S_n \to M_n(\mathbb{C})$ defined by $f(\pi) = A(\pi(\Gamma))$ where $A(\cdot)$ denotes the adjacency matrix. In particular, $f(1) = A(\Gamma)$. Then apply the usual Karp reduction from GA to GI to get a pair of graphs $\Gamma_1, \Gamma_2$, and consider the HSP-GI instance, of the type described in the preceding paragraph, corresponding to the pair $\Gamma_1, \Gamma_2$ (that is, the disjoint union $\Gamma_1 \cup \Gamma_2$).


Completeness and Context-Sensitive Languages.

To answer your first question, a reducibility fitting your needs is log-lin-reducibility, which is logspace reducibility with the additional constraint that the size of the output string of the reduction is at most linear in the size of the input. If I remember correctly, the membership problem for context-sensitive grammars (or, if you like, linearly bounded automata) is the canonical CSL-complete problem w.r.t. log-lin reducibility.

On the applied side, the universality problem of (ordinary) regular expressions over binary alphabet, is CSL-complete w.r.t. log-lin-reducibility. The notion and the completeness result are found in  Albert R. Meyer and Larry J. Stockmeyer (SWAT 1972) also: Stockmeyer (PhD thesis, MIT 1974). For further background and similar results in that area, see also the recent survey by Holzer and Kutrib (DLT 2010).

EDIT (2017/03/06): Regarding your second question, the accepted answer to the question below cites a paper by Rounds (1973), which constructs a one-way nested stack automaton recognizing SAT. While SAT will not qualify as a "natural" CSL, it might be worth to search the literature for other examples of one-way nested stack automata or indexed grammars.

Context-sensitive grammar for SAT?


Generalisations of the Fundamental Theorem of Statistical Learning to different tasks and losses

Turns out the answer is yes and can be found in Part 3 (eg chapter 19) of Neural Network Learning: Theoretical Foundations, by Anthony and Bartlett.


I think it is possible to reduce Max Cut to this problem: given a graph $G(V,E)$, make a variable for each vertex, and for each edge $(u,v)\in E$ make the two clauses $(x_u\lor x_v)$ and $(\neg x_u\lor\neg x_v)$. In the resulting instance, $x_u$ appears $d(x_u)$ times positive and the same number of times negative. Since Max Cut is still NP-hard on regular graphs, this proves that the version for which $k$ is the same for all variables is also hard.


A model of computation allowing real numbers is the Real-RAM model. In this model, it is impossible to even decide if a number is rational. Indeed, the time-T halting sets are semialgebraic. If any one of them has a non-empty interior, then the time-T yes-set and time-T no-sets are semialgebraic subsets with no-empty interior, which is a contradiction. If none of the time-T halting sets is semialgebraic, then their union cannot be $\mathbb{R}$.

Answer to the previous version of the question:

If $a_1,\dotsc,a_k$ are algebraic numbers that are linearly independent over $\mathbb{Q}$, then $e^{a_1},\dotsc,e^{a_k}$ are algebraically independent over $\mathbb{Q}$. This is the Lindemann–Weierstrass theorem. So, if $a$'s are algebraic (as in the current version of the question), then the answer to your question is "yes".


What is the motivation behind the definition of fixed parameter tractability?

If you require only that the growth rate be a polynomial in $n$ for fixed $k$, then you get the definition of the parameterized complexity class XP, which is certainly an object of interest, so there's nothing wrong with considering it.

You get the definition of FPT if you further impose the condition that the degree of the polynomial in $n$ remains fixed as the parameter increases.  FPT turns out to be a particularly tractable subclass of XP, and intuitively, the reason is that an expression such as $2^k n^2$ doesn't explode as quickly as an expression such as $k^2 n^k$, if $k$ and $n$ are both increasing.  This intuition is supported both in practice and in theory; i.e., FPT problems tend to be noticeably more tractable in practice than arbitrary XP problems, and one can also get a nice theoretical picture of the structure of XP by starting with FPT at the bottom and constructing hierarchies of other subclasses of XP (such as the W hierarchy) above it.


Is uniform RNC contained in polylog space?

Perhaps most people think that $\mathsf{RNC}\subseteq \mathsf{DSPACE(polylog)}$ (or even that $\mathsf{RNC}=\mathsf{NC}$), but I'm skeptical about this (see the second part of my answer, below). If $\mathsf{RNC}$ is indeed contained in $\mathsf{DSPACE(polylog)}$, then it is also contained in $\mathsf{NTIME(2^{polylog})}$ (more specifically, it is in $\mathsf{DTIME(2^{polylog})}$ by exhaustive search).

Valentine Kabanets explained to me the following (folklore) argument from his paper with Russell Impagliazzo that explains why $\mathsf{RNC} \subseteq \mathsf{NTIME(2^{polylog})}$ is unlikely.

Theorem: If $\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$, then either $\mathsf{NEXP}$ is not computable by Boolean circuits of size $o(2^n/n)$ (i.e. sub-maxsize by Shannon; irrelevant but see Lupanov for tightness), or Permanent is not computable by (division-free) arithmetic formulas over ${\mathbb Z}$ of quasipolynomial size.

Proof: assume $\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$. If Permanent has a quasipolynomial size formula, then we can guess and verify such a formula for Permanent using a quasipolynomial time polynomial identity tester by assumption. This places Permanent in $\mathsf{NTIME(2^{polylog})}$.

By Toda's theorem, $\Sigma_2$ is then also in $\mathsf{NTIME(2^{polylog})}$. By padding, the linear-exponential time version of $\Sigma_5$ is also in $\mathsf{NEXP}$. Hence the linear-exponential version of $\Sigma_5$ has a circuit of size $o(2^n/n)$ (i.e. submax). But, by a simple diagonalization argument, one can show that the linear-exponential version of $\Sigma_5$ requires max circuit size, which is a contradiction (by the way, this is a variant of a mid-level question for a graduate-level complexity course; okay, maybe proving that $\mathsf{EXPSPACE}$ requires max-size circuits is a simpler one). QED.

Now the unpopular direction.

We already know that randomness read many times can do something non-obvious. An interesting example can be found in "Making Nondeterminism Unambiguous" by Reinhardt and Allender (they state it in terms of non-uniformity but in principle it is about using read-many-times randomness). Another interesting example (less directly related) is "Randomness Buys Depth for Approximate Counting" by Emanuele Viola. I guess all I'm saying is that I wouldn't be surprised if the derandomization of $\mathsf{RNC}$ is not what most people would expect it to be.

(There are also a couple of other papers, like Noam Nisan's wonderful paper on read-once vs. read-many randomness, that show how to buy two-sided error with one-sided error.)

By the way, understanding how to construct PRGs fooling space-bounded models of computation with multiple accesses to their input (e.g. linear lengths Bps) is also very related to this question.

-- Periklis


Is the decidability of a language decidable?

Sure.
There are Turing machines that always reject or always accept...
So, one of them is surely correct...


Complexity of determining unique elements of each cycle in a permutation

Even for $k=2$ when the instance may have two cycles of length $n/2$,
any sublinear algorithm can only build chains of length $\ll n/4$, so no deterministic algorithm can guarantee that the two vertices it outputs belong to distinct cycles.

I doubt (though I am not sure and do not have a proof) that the problem would admit a solution in sublinear expected time even for algorithms with probabilistic guarantees.


TCS Research Frontier with Huge Practical and Industrial Impact on our Society

There are many examples of theoretical research that had a big impact on society, e.g., the RSA cryptosystem, the algorithm behind Google search, the algorithmic ideas behind Akamai, etc.
But the thing with basic research is that it's hard to know in advance what's going to be influential, when and how.

One potential candidate could be quantum computing, which has strong ties to both physics and electronics, and could make a huge difference (allowing efficient simulations of quantum systems, breaking RSA, and more). However, it's hard to know when quantum computers will be built (if at all).