What is the difference between meaning and denotation?

"Meaning" is used in a broader way than denotation is.

The original dichotomy, inherited from logic and philosophy, is between "sense" and "denotation" (which philosophers call "reference").

This distinction can be illustrated by Frege's original example. He noted that phrases "the morning star" and "the evening star" referred to the same object --- the planet Venus --- but that the sentence "the morning star and the evening star are the same planet" actually conveys some information to a reader. He suggested that the meaning of a noun phrase can go beyond the actual object it denotes, including something about how it presents the object it denotes.

Similarly, in a programming language, the expression $8 \times 7$ is not the same as the expression $56$, even though they may be (ought to be!) completely indistinguishable by any client program. But even though they are indistinguishable, they are not the same -- when evaluating the two programs, your machine does a multiplication in the first case, and doesn't in the second.

When building a denotational semantics, we try to build a model of a language in which indistinguishable programs denote --- refer to --- the same mathematical object.  The goal is to simplify reasoning about the behavior of programs, since we can reason about the denotations, the mathematical objects, without having to worry about the details of how the program is presented. This lets us avoid having to deal with aspects of the meaning of programs that are not of interest to us.

The way sense and denotation relate to operational semantics is more complicated, and different. I may extend my answer later to cover this, but I have to run now. :)

EDIT: Okay, I'm extending this answer now.

The connection between "denotation" and "reference" is pretty much exact, and it's exact because the people who invented denotational semantics (e.g., Scott and Strachey) were quite consciously appropriating ideas from philosophical logic as part of their project.

To understand how meaning and operational semantics relate, it's helpful to recall the philosopher Michael Dummett's notion of a "meaning theory" and how it differs from a "semantic theory".

In Dummett's terminology, a semantic theory is a compositional way of relating  sentences to determinate mathematical objects. In logic, the meaning of a sentence is its truth-value, and it is determined from the truth-values of its constituents. Denotational semantics of programming languages uses a much wider variety of mathematical objects, but it works the same way -- we give the meaning of a program term in terms of the meaning of its subterms. So in Dummett's terminology, denotational semantics offer semantic theories of programming languages.

A meaning-theory is also a compositional way of relating sentences to mathematical objects, but in addition it contains an account of what justifies the relationship between the sentence and the mathematical object. He developed this idea in order to understand how intuitionistic mathematicians understood the notion of truth. In particular, they had a compositional account of the meaning of logical connectives, but did not give them semantic values in the same way that classical logicians do. For example, in the Brouwer-Heyting-Kolmogorov account of intuitionistic logic, truth is defined in the following way:

A canonical proof of $A \land B$ is a pair $(p_1, p_2)$, where $p_1$ is a canonical proof of $A$ and $p_2$ is a canonical proof of $B$.
A canonical proof of $A \vee B$ is a pair $(i, p)$, where $i$ is either $0$ or $1$, and if $i$ is $0$, then $p$ is a canonical proof of $A$, and if $i$ is $1$, then $p$ is a canonical proof of $B$.
A canonical proof of $A \to B$ is an effective procedure, that takes any canonical proof of $A$ and computes a canonical proof of $B$.
A canonical proof of $\forall x.\;A(x)$ is an effective procedure which takes a numeral $n$, and computes a canonical proof of $A(n)$.
A canonical proof of $\exists x.\;A(x)$ is a pair $(n, p)$, where $n$ is a numeral and $p$ is a proof of $A(n)$.

A proposition $A$ is said to be true when it is possible to give a canonical proof of $A$.

Now, note that this definition connects propositions and truth values, but the connection must be justified by the possibility of giving a canonical proofs.

Operational semantics enters the picture via this notion of justification. An operational semantics is just a description of what an abstract machine does. After we give a denotational semantics, we generally want to show that the denotational semantics is faithful to the operational semantics. This property is called adequacy (along with its big brother full abstraction), and it exactly amounts to giving a meaning-theory that connects abstract machine states with denotational objects, which is closed under the reduction of the abstract machine.

This is actually not the whole story, since what I've laid out here is how to connect operational and denotational approaches via a realizability model. Type theories can also have proof-theoretic semantics (indeed, this prospect was what Dummett was most interested in), but I have not explained that connection in this post.


Like many things in life, there is no one definitive definition. For an algorithm to run in real-time, some people on the theoretical side say that this means it will take constant time per 'something.' Now you have to decide what a 'something' is but let me give a concrete example. Let's say that the input arrives one symbol at a time and you want to output the answer to a query as soon as a new symbol arrives. If calculating that output takes constant time per new symbol then you might say the algorithm runs in real-time.    An example of this is real-time exact string matching, which outputs whether a pattern matches the latest suffix of a text in constant time per new symbol. The text is assumed to arrive one symbol at a time.

However, an engineering answer will be less worried about "constant time" and more worried about it happening fast in practice and in particular fast enough that the result can be used by the time it is needed. So for example in robotics, if you want to play ping-pong it is useful for the robot to be able to work out where the ball is and move to hit it as the ball arrives, and not after the ball has passed. The asymptotic time complexity of the underlying algorithms will perhaps be of less interest there than just the observation that the code works out the location quickly enough.  To give another example, if you want to render video and can do it at 25 frames per second then it is reasonable to say that the rendering is happening in real-time.

So basically you have two answers. One for the theoreticians/algorithmists and one that just says that you are doing the work as you need it on the fly.

EDIT: I should probably add that one extra feature one should require of even a constant time algorithm is that the time complexity is not amortised.  In this context, real-time == unamortised constant time.


Brakerski, Christiano, Mahadev, Vazirani, and Vidick propose a scheme for verifiable quantum computational supremacy based on a strengthening of trap-door claw-free functions (TCFs).

In the above scheme:

Vicky the classical verifier provides a description of a pair of functions $f_0$ and $f_1$ to Peggy the quantum prover, while saving the trapdoor to $f_0$ and $f_1$;
Peggy prepares, measures, and reports the results of a register in a quantum state to provide a $y$ such that $y=f_0(x_0)=f_1(x_1)$, keeping a superposition of $\vert b\rangle\vert x_b\rangle$;
Vicky asks Peggy to measure the superposition in either the computational basis to provide a bit $b$ and an $x_b$ such that $f_b(x_b)=y$, or in the Hadamard basis to provide a string $d$ orthogonal to $x_0\oplus x_1$; and
Based on Vicky's possession of the trapdoor, Vicky can validate results (she uses the trapdoor to deduce both $x_0$ and $x_1$ from $y$ and Peggy's response above).

Thus Peggy proves that she was able to execute a function in quantum superposition (or she has broken the security of the TCF).

The authors instantiate their TCFs with learning-with-errors (LWE), which is a leading candidate for post-quantum security.  That is, the functions they require Peggy to prepare and evaluate in superposition are associated with LWE.

My limited understanding is that the author's LWE scheme is out of reach of current and near-term noisy, intermediate-scale quantum computers.  The authors appear somewhat optimistic that about 50 bits of security may correspond to a machine with about 2000 or so qubits, or perhaps even 200-500 noisy qubits if they could optimize their LWE scheme.

Nonetheless the scheme is interesting and I think close to the spirit of the question.  For example, in this scheme Peggy does not actually find the claw by herself but only provides a proof that she possessed $x_0$ and $x_1$ in superposition.


Is there a relativized form of Rice Theorem?

You can prove your idea via the usual recursion theorem proof of Rice's theorem.

proof:

Suppose that $M_{yes}$ is a machine with both property $P_1$ and $P_2$ and that $M_{no}$ is a machine with property $P_1$ but without property $P_2$. Such machines must exist by the nontrivial assumption.

Then suppose there exists a decider $D$ which accepts any input $<X>$ such that machine $X$ satisfies both property $P_1$ and $P_2$, rejects any input $<X>$ such that machine $X$ satisfies property $P_1$ but not $P_2$, and has any behavior on all other inputs.

Consider the following machine:

$M =$ on input $w$:

Obtain the description $<M>$ via the recursion theorem.
Run $D$ on $<M>$
If $D$ accepts $<M>$, simulate $M_{no}$ on $w$ and output the same answer
If $D$ rejects $<M>$, simulate $M_{yes}$ on $w$ and output the same answer

This language $L(M)$ of this machine is either $L(M_{yes})$ or $L(M_{no})$ depending on whether $D$ rejects or accepts $<M>$. Notice that since $P_1$ is a semantic property shared by both $M_{yes}$ and $M_{no}$, we know that in either case, $M$ has property $P_1$. Then by definition of $D$, $D$ accepts $<M>$ if and only if $M$ has property $P_2$. Thus, we have that $L(M) = L(M_{no})$ if $M$ has property $P_2$ (i.e., $D$ accepts $<M>$) and $L(M) = L(M_{yes})$ if $M$ does not have property $P_2$ (i.e., $D$ rejects $<M>$). This, however, contradicts the fact that $M_{yes}$ has property $P_2$, $M_{no}$ does not have property $P_2$, and $P_2$ is semantic.

By contradiction, we can conclude that decider $D$ as described cannot exist. In other words, $P_2$ given $P_1$ is undecidable.


Efficient graph isomorphism for similar graph queries

This is a simple polynomial time reduction to show that the problem is GI complete: even if you know that $G_1, G_2$ are isomorphic, checking if $G_3$, built from $G_2$ deleting and adding a node, is isomorphic to $G_1$ is as hard as graph isomorphism itself (in the worst case).

Given two graphs $G = (V, E), G'= (V', E')$ build

$G_1 = ( V \cup V' \cup \{u\},\; E \cup E' \cup \{ (v_i,u) \mid v_i \in V \})$

i.e. the union of the two graphs plus an extra node $u$ connected to all the vertices of $V$

pick $G_2 = G_1$; and clearly they are isomorphic.

Now build $G_3$ deleting $u$ and adding $u'$ connected to all the vertices of $V'$:

$G_3 = ( V \cup V' \cup \{u'\},\; E \cup E' \cup \{ (v_i',u') \mid v_i' \in V'\} )$

$G_1, G_3$ are isomorphic iff $G, G'$ are isomorphic.


Minimum amount of colors preventing an equilateral uniformly colored subtriangle

Just an extended comment:

You can take a look to the approach used by Steinbach and Posthoff to find the 4-coloring of a 18x18 (and 12x21) grid without monochromatic rectangles:

Bernd Steinbach and Christian Posthoff, Solution of the Last Open Four-Colored Rectangle-free Grid an Extremely Complex Multiple-Valued Problem. In Proceedings of the 2013 IEEE 43rd International Symposium on Multiple-Valued Logic (ISMVL '13)

As proved by Gasarch et al. given a partial $c$-coloring of an arbitrary $n \times m$ rectangle, it is NP-complete to decide if the coloring can be extended to the whole rectangle without monochromatic rectangles: Daniel Apon, William Gasarch, Kevin Lawler, An NP-Complete Problem in Grid Coloring.
So there are high chances that the problem is NP-complete even for equilateral triangles .... I think it would be a nice result to prove it.

Just a side note: I spent weeks of CPU cycles on the monochromatic rectangle-free 4-coloring problem but I started from a wrong partial result (a wrong previous analysis that restricted the number of possible 1-color sub-configurations) and I used the STP constraint solver; you can achieve great improvements if you add constraints that break symmetries (e.g. an ordering on the coloring of a side of the triangle) and try to make an analysis of the possible configurations using only 1-color.

EDIT: this is the result of an STP program for n=19 (~ 1 min.)


Baker Gill Solovay $P^B \ne NP^B$ relativization, what class is $B$ in?

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

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


Information on k-SAT (Introduction, Bounds, Methods, etc.)

From the Lecture Note reference thread, we have this document.


Expected travel time for regularly departing trains

Here's a way you can find the optimal algorithm. Let's assume (for convenience) that all $x_i$ and $y_i$ are distinct.

First, we need to prove two theorems.

(1) If at time $t$, you would get on a train with travel time $y_i$, you would also get on any train with travel time less than $y_i$.

(2) If you would get on train $j$ at time $t_j$, you would also get on that train $j$ at any time $t \leq t_j$.

For (1), the proof is easy. For (2), the proof is based on the observation that the longer you wait, the higher the probability that any particular train shows up. So if there's some strategy of waiting for trains other than $j$ that has better performance than getting on a train $j$ with travel time $y_j$ at time $t_j$, that same strategy is going to give travel time $\leq y_j$ for all times $t > t_j$.

Now, if train $\alpha$ is the train with minimum $y_\alpha$, then you want to get on this train any time it arrives. Furthermore, if you've waited $x_\alpha - \epsilon$ time for sufficiently small $\epsilon$, your optimal strategy is to wait for train $\alpha$.

What we're going to do now is essentially continuous dynamic programming. If you've waited for time $t$, there are only $n$ possible optimal strategies. That is, get on any train with travel time $\leq y_i$. This optimal strategy changes at $n$ or fewer values of $t$. So, starting with time $x_\alpha$ and the strategy "wait for train $y_\alpha$", calculate the first time $t < x_\alpha$ where the strategy changes. You can do this by comparing $n$ possible strategies, each of which gives an expected travel time which is a function of $t$. Keep working to the left in this fashion, until you get to time $t= 0$.


Examples/Textbooks on amortized analysis of algorithms

For textbook references an interesting article is as follows:

https://www.geeksforgeeks.org/analysis-algorithm-set-5-amortized-analysis-introduction/

I can also refer to one recent paper which is very simple involving a straightforward application of amortized analysis:

https://arxiv.org/abs/1804.01823


I've studied the problem and I found some results.
Shortest Common Superstring (SCS) can be solved in time $2^n$ with only polynomial space(Kohn, Gottlieb, Kohn; Karp; Bax, Franklin).

The best known approximation is $2\frac{11}{30}$ (Paluch).

The best known approximation of compression is $3\over4$ (Paluch).

If SCS can be approximated by a factor $\alpha$ over the binary alphabet, then it can be approximated by a factor $\alpha$ over any alphabet (Vassilevska-Williams).

SCS cannot be approximated with a ratio better than $1.0029$ unless P=NP (Karpinski, Schmied).

Maximal Compression cannot be approximated with a ratio better than $1.0048$ unless P=NP (Karpinski, Schmied).

I would be grateful for any additions and suggestions.


Classes of graphs with superconstant treewidth

I believe that the universal graphs for trees constructed by Chung and Graham 1983 have treewidth $\Theta(\log n)$. Or for a slightly simpler but similar example consider the transitive closures of balanced binary trees.

However, there's a negative result here, too. All the examples you give of interesting graph families are minor-closed, or very closely related to minor-closed families. But a minor-closed graph family either contains all planar graphs (and hence has maximum treewidth $\Theta(\sqrt n)$) or has a forbidden planar minor (and hence has bounded treewidth).


enumerating all connected induced subgraphs

It's not difficult to show that this is polynomial per subgraph, for the connected induced subgraphs. I don't know what you mean by a maximal connected induced subgraph; isn't that just a connected component? I also don't know what has been published on this problem.

One way to solve the problem is to define a tree structure on these subgraphs as follows: choose an arbitrary assignment of distinct weights to the edges of the input graph. Define the parent of a connected induced subgraph to be the graph formed by finding its minimum spanning tree, removing the leaf edge of maximum weight, and forming the induced subgraph of the remaining vertices. For a subgraph with only one vertex, define its parent to be the empty graph (which forms the root of the tree structure)

Reverse search (essentially, DFS of this tree) will then find each connected induced subgraph in time polynomial per subgraph. You can find the children of any node in the tree by trying all ways of adding one vertex and checking which of them would form the heaviest leaf of the MST of the augmented subgraph; finding all the children of a single node takes polynomial time, which is all that's required to make this work.

The family of connected subsets of vertices of a graph, with two subsets considered adjacent to each other if they differ in the addition or removal of a single vertex, forms a partial cube structure (see the first example in my book Media Theory) and similar reverse search ideas can be used to list all states in any such structure (detailed later in the book).


Suppose you have $n$ balls. Take a random ball from each non-empty bin. Your expected weight is approximately $(1-1/e)T$. This holds because the probability that a bin is empty is $(1-1/n)^n \approx 1/e$. Thus, the expected number of balls you get is $(1-1/e)n$, and these are a random sample of all the balls.

Now, suppose you have balls whose weights are not all equal. Then the expected weight is at least $(1-1/e)T$, because you always take the largest ball from each bin. However, you never get a total weight larger than $T$. This means that at least half the time, you must get a weight of at least $(1-2/e)T$.

You're never going to get $c > 1-1/e$. That's probably the right answer for $c$, but to get it you probably need to use probability theory that's at least a little more sophisticated than I did.


Which is the limit of lossless compression data? (if there exists such a limit)

I am not sure if anyone has yet explained why the magical number seems to be exactly 1:2 and not, for example, 1:1.1 or 1:20.

One reason is that in many typical cases almost half of the digitised data is noise, and noise (by definition) cannot be compressed.

I did a very simple experiment:

I took a grey card. To a human eye, it looks like a plain, neutral piece of grey cardboard. In particular, there is no information.
And then I took a normal scanner – exactly the kind of device that people might use to digitise their photos.
I scanned the grey card. (Actually, I scanned the grey card together with a postcard. The postcard was there for sanity-checking so that I could make sure the scanner software does not do anything strange, such as automatically add contrast when it sees the featureless grey card.)
I cropped a 1000x1000 pixel part of the grey card, and converted it to greyscale (8 bits per pixel).

What we have now should be a fairly good example of what happens when you study a featureless part of a scanned black & white photo, for example, clear sky. In principle, there should be exactly nothing to see.

However, with a larger magnification, it actually looks like this:

There is no clearly visible pattern, but it does not have a uniform grey colour. Part of it is most likely caused by the imperfections of the grey card, but I would assume that most of it is simply noise produced by the scanner (thermal noise in the sensor cell, amplifier, A/D converter, etc.). Looks pretty much like Gaussian noise; here is the histogram (in logarithmic scale):

Now if we assume that each pixel has its shade picked i.i.d. from this distribution, how much entropy do we have? My Python script told me that we have as much as 3.3 bits of entropy per pixel. And that's a lot of noise.

If this really was the case, it would imply that no matter which compression algorithm we use, the 1000x1000 pixel bitmap would be compressed, in the best case, into a 412500-byte file. And what happens in practice: I got a 432018-byte PNG file, pretty close.

If we over-generalise slightly, it seems that no matter which black & white photos I scan with this scanner, I will get the sum of the following:

"useful" information (if any),
noise, approx. 3 bits per pixel.

Now even if your compression algorithm squeezes the useful information into << 1 bits per pixel, you will still have as much as 3 bits per pixel of incompressible noise. And the uncompressed version is 8 bits per pixel. So the compression ratio will be in the ballpark of 1:2, no matter what you do.

Another example, with an attempt to find over-idealised conditions:

A modern DSLR camera, using the lowest sensitivity setting (least noise).
An out-of-focus shot of a grey card (even if there was some visible information in the grey card, it would be blurred away).
Conversion of the RAW file into a 8-bit greyscale image, without adding any contrast. I used typical settings in a commercial RAW converter. The converter tries to reduce noise by default. Moreover, we are saving the end result as an 8-bit file – we are, in essence, throwing away the lowest-order bits of the raw sensor readings!

And what was the end result? It looks much better than what I got from the scanner; the noise is less pronounced, and there is exactly nothing to be seen. Nevertheless, the Gaussian noise is there:

And the entropy? 2.7 bits per pixel. File size in practice? 344923 bytes for 1M pixels. In a truly best-case scenario, with some cheating, we pushed the compression ratio to 1:3.

Of course all of this has exactly nothing to do with TCS research, but I think it is good to keep in mind what really limits the compression of real-world digitised data. Advances in the design of fancier compression algorithms and raw CPU power is not going to help; if you want to save all the noise losslessly, you cannot do much better than 1:2.


Canonical labeling of special classes of DAGs

To start with the obvious: DAGs containing a Hamiltonian path, using the uniqueness of their topological orderings, and polytrees, as an orientation-labeled variant of trees.

On the other hand, it's tempting to list multitrees (as I did in an earlier incorrect version of this answer), using canonization of trees to prioritize their topological orderings, but they're GI-complete (subdivide each edge of an undirected graph into two directed edges oriented outwards from the subdivision point), so that doesn't work.


White elephant gift exchanges: mechanisms for fair division

This isn't a complete answer, but it's an incomplete one.

Some background and related lit for those who aren't familiar --

A nice property would be envy-freeness, in which no player would like to trade with another after the mechanism is complete. Unfortunately, for indivisible goods and no money we can see that this is impossible (there might be one good that two people both think is best). The other common property is proportionality, where everyone gets what they consider to be a value of more than $1/n$; this is also clearly impossible to always obtain (there may be an item that nobody wants, but someone must end up with it).

[1] focuses on computing the minimum-envy allocation in an indivisible-goods scenario. They show that a minimum-envy mechanism cannot be truthful. However, we might still be able to design a game with a good price of stability (even though players aren't truthful).

[2] apply the criterion of "max-min fairness". The idea is to consider each player's valuation function over subsets of the items, normalizing it to one on the whole set, and to find the allocation which maximizes the minimum utility of any agent. Again, though, they don't consider our setting here with unit demand. Others study approximation algorithms for this problem, but I don't know if anyone has considered this restriction.

--

It's worth noting that usually notions of fairness are extremely worst-case: A mechanism is usually (perhaps not always?) considered envy-free if every player has a strategy that guarantees she will not envy any other's allocation. If she is playing to maximize her expected utility, she may or may not end up envious. Same goes for proportionality.

Because of this, it's tricky to try to relax these notions in a way that's natural when taken with this philosophical approach to fair division. It might be tempting to define a criterion like "ex-ante envy-freeness" where we hope to be envy-free in expectation (whatever that means). However, I think this would really be setting off on a whole new track from the current philosophy. If one were to do that, I think we should throw out notions of envy-freeness or proportionality altogether and start thinking about how expected-utility-maximizers would play these fair-division games in the first place.

Instead, we might try to extend the traditional approach in a more consistent way. One question would be how often (over the randomness of the mechanism) a player can guarantee herself a constant fraction of optimal utility. However, consider the case where only one of the $n$ items has any value; then any fair mechanism gives each player a constant-approximation to utility only $\frac{1}{n}$ of the time.

To get around this, I think we must consider ordinal criteria instead. I propose the following as a "natural" relaxation:

  A mechanism in our setting is $(\varepsilon,\delta)$-envy-free if with probability $1-\varepsilon$ an agent can guarantee herself one of her favorite $\delta n$ items.

Considering the case where everyone values each item the same amount, we see that no mechanism can possibly do better than $(\varepsilon,\varepsilon)$-envy-freeness here. (For any $\varepsilon$ -- Because only $\varepsilon n$ agents will get one of their $\varepsilon n$ favorite items.)

On the other hand, it is easy to see that your mechanism, if we order the players uniformly at random, is $(\varepsilon,\varepsilon)$-envy-free for all $\varepsilon$.[3]

I don't pretend that this captures nearly all the interesting questions about this setting or the white elephant mechanism. For example, the $(\varepsilon,\varepsilon)$-envy-free strategy for the second player is to take the first player's gift unless it is the worst of all the gifts. However, I think that this shows that our worst-case solution concepts simply don't capture a lot of what's interesting about these scenarios, so we should maybe think about something else like utility maximization instead.

--

[1] Lipton, Markakis, Mossel, Saberi. "On Approximately Fair Allocations of Indivisible Goods." EC 2004.

[2] Bezakova, Dani. "Allocating Indivisible Goods." SIGECOM 2005.

[3] Well, so is random serial dictator, but random serial dictator often has nice properties in theory. I'm also assuming that each item can only be stolen once per round.


How are side effects handled in semantics?

Building on Charles's answer, the main difficulty in the theory of programming languages is that the natural notion of equivalence of programs is typically not strict equality either in the most straightforward mathematical semantics you can give, or in the underlying machine model. For example, consider the following bit of Java-like code:

Object x = new Object();
Object y = new Object();
... some more code ...

So this program creates an object and names it x, and then creates a second object named y, and then continues executing some more code. Now, suppose that a programmer decides to flip the order of allocation of these two objects:

Object y = new Object();
Object x = new Object();
... some more code ...

Now, ask the question: does this refactoring change the behavior of the program? On the one hand, on the underlying machine, x and y will be allocated at different locations in the two runs of the program. So in this sense, the program behaves differently.

But in a Java-like language, you can only test references for equality, and not for order, so this is a difference that the "some more code" cannot observe.  As a result, most programmers will expect that reversing the order will make no difference to the final answer, and most compiler writers expect to be able to perform reorderings and optimizations on this basis. (On the other hand, in a C-like language, you can compare pointers for ordering, by casting them to integers first, and so this reordering does not necessarily preserve observable behavior.)

One of the central questions of semantics is to answer the question of when two programs are observably equivalent. Since our notion of observation depends on the features of the programming language, we end up with a definition like "two programs are equivalent when no client program can compute different answers based on receiving those programs as inputs." The quantification over all client programs is what makes this question difficult -- it seems like you end up having to say something about all possible client programs to say something about two particular pieces of code.

The trick with denotational semantics is to give a mathematical interpretation that lets you avoid this universal quantification -- you say that the meaning of a piece of code is some mathematical value, and you compare them by checking to see if they're mathematically equal or not. This is local (ie, compositional), and does not involve quantification over all possible clients. (You do need to show that the denotational semantics implies contextual equivalence for it to be sound, of course. When it is complete -- when denotational equality is exactly the same as contextual equivalence, we say the semantics is "fully abstract".)

But means that you need to ensure that the denotational semantics validates those equivalences. So for this example, if you wanted to give a denotational semantics for this Java-like language, you need to ensure not just that calling new takes a heap and gives you back a new heap with the newly-created object, but that the meaning of the program is invariant same under all permutations of the input heap. This can involve quite complex mathematical structures (eg, in this case working in a category which ensures everything works modulo a suitable permutation group).


What algorithms/reading matter would you recommend on resolving transactions / read-write locks?

The book Transactional Information Systems by Weikum and Vossen covers quite a lot of the area, both in theoretical and practical terms, from different perspectives, not just transactions. It's about 1000 pages long, so will keep you busy for a weekend or two. On the other hand, it's nearly 10 years old, so there might be something more up-to-date available. Other books in the line include Concurrency Control and Recovery in Database Systems by Bernstein, P., Hadzilacos, V., and Goodman, N, Addison-Wesley, 1987, Transaction Processing: Concepts and Techniques by Jim Gray and Andreas Reuter, and Principles of Transaction Processing by Philip A. Bernstein and Eric Newcomer, 2009. I haven't seen the latter one, but being the most recent it could be a good place to start, although your solution may well be found in older texts. A trip to the library may be worthwhile.

A monumental text in this area is Atomic Transactions by Nancy Lynch et al. It presents a formal account and proofs of a number of the kinds of algorithms you are interested in. It's rather formal, and tedious, so may not be to your taste.

A lot of recent work is devoted to Software Transactional Memory, which is applying the transaction ideas to multi-threaded applications. There are tens of publications on this topic each year: the wikipedia page provides plenty of references.


correlation in an almost independent set of random variables

I think Yury's beautiful example actually answers my question. It shows that $\delta_0$ does not go to 0 as $n\to \infty$. One can probably also use a similar construction to show that the same holds for any $\delta<1/2$.

Thanks Yury!


Potentially equal complexity classes without known contradictory relativizations

I think the biggest such example at present is $BQP $ (quantum polybomial time) vs $PH $ (the polynomial time hierarchy). Significant effort has been put into separating them relative to an oracle, with no success. (Of course a powerful enough oracle will make them equal.) And the best known containment result is that $BQP $ is in $PP $.

Some references for attacks on the oracle problem:
http://arxiv.org/abs/0910.4698
http://arxiv.org/abs/1007.0305


What are the consequences of solving XOR 3-SAT in Logspace?

Take a look at https://www.sciencedirect.com/science/article/pii/S0022000008001141 "The complexity of satisfiability problems: Refining Schaefer's theorem" by Allender et al. which answer your questions:

(1) Open

(2) $\oplus L = L$

(3) Yes


Tree decompositions of optimal width where every vertex is in a bounded number of bags?

Answering my own question: the answer is "no". For each $k \ge 3$, Ding and Oporowski construct a graph $G_k$ on $2k$ vertices with treewidth $3$, such that in every optimal tree decomposition of $G_k$ there is a vertex which is in at least $2k-2$ bags (see Figure 1 in their paper).

Ding, Guoli; Oporowski, Bogdan, Some results on tree decomposition of graphs, J. Graph Theory 20, No. 4, 481-499 (1995). ZBL0837.05044.


Is there a "lambda cube" for interaction nets?

Like Martin said, nothing like an equivalent for the $\lambda$-cube has ever been developed for interaction nets or interaction combinators.

The only work that considers types for interaction nets is Lafont's original paper [1].  (My own CONCUR 2005 paper also considers types but adds nothing new to what Lafont did).  It is an extremely simple system: only basic types plus a polarity, no type constructors at all.  Nevertheless, it is enough to obtain a desirable safety property: a well typed net cannot reduce to a net containing a "clash" (an active pair which does not have a corresponding reduction rule and is therefore "stuck").

Of course, since multiplicative linear logic proof nets are a particular system of interaction nets, it is defintely possible to equip certain systems of interaction nets with more complex types, using non-trivial type constructors.  But nothing has ever been studied, mostly because the interest of such an endevour is unclear.

[1] Yves Lafont, Interaction Nets.  In Proceedings of POPL, 1990.


Complexity Classes for Cases Other Than "Worst Case"

Although I can't quite parse your definitions, you should know that much stronger time hierarchies are known, in particular "almost everywhere" time hierarchies.

Here is the formal statement: for every time bound $T(n)$, there is a language $L \in TIME[T(n)]$ with the property that every deterministic algorithm that correctly recognizes $L$ must run in time asymptotically greater than $t(n)$ on all but finitely many inputs, for sufficiently small time $t(n)$.

"Sufficiently small" means $t(n) \log t(n) \leq o(T(n))$.

Suppose we choose $T(n)=2^n$ for an example, and obtain a hard language $L$. Then, any algorithm that correctly recognizes $L$ must take at least $2^n/n^2$ time on all inputs past a certain length. This seems to be what you're looking for in your class BestE.

Reference:

  John G. Geske, Dung T. Huynh, Joel I. Seiferas: A Note on Almost-Everywhere-Complex Sets and Separating Deterministic-Time-Complexity Classes Inf. Comput. 92(1): 97-104 (1991)


If $G$ has $n$ vertices and $m$ edges, then for any spanning tree $T$ of $G$, each of the $m-n+1$ edges that are not in $T$ may be swapped with any of the edges on the path in $T$ between the endpoints of the non-tree edge. Assuming $G$ is not a multigraph, this gives at least $2(m-n+1)$ different swaps; that is, every $T$ has degree at least $2(m-n+1)$.

This bound is tight: if $G$ has a vertex $v$ adjacent to all others, and $T$ is the spanning tree consisting of all the edges incident to $v$, then the path in $T$ between the endpoints $T$ of every non-tree edge has length exactly two, so each non-tree edge participates in exactly two swaps and $T$ has degree exactly $2(m-n+1)$.

On the other hand if $G$ has girth (shortest cycle length) $g$, then the path in any tree $T$ between the endpoints of any non-tree edge, together with that edge, forms a cycle which must have length at least $g$, so the minimum degree in the tree graph must be at least $(g-1)(m-n+1)$. This bound is tight for some graphs such as the cycle graphs, and complete bipartite graphs, and Moore graphs, since these graphs contain spanning trees for which all non-tree edges induce cycles of length equal to the girth.

However, finding the minimum degree of the tree graph for an arbitrary given graph (equivalently, finding a spanning tree minimizing the sum of lengths of the cycles induced by non-tree edges) is NP-complete: see Deo, Prabhu, and Krishnamoorthy, "Algorithms for Generating Fundamental Cycles in a Graph", ACM TOMS 1982. So finding bounds such as these that are tight for all graphs appears unlikely.


Why was there a need for Martin-Löf to create intuitionistic type theory?

Very briefly: the simply-typed $\lambda$-calculus does not have  dependent types. Dependent types were proposed by de Bruijn and Howard who wanted to extend the Curry-Howard correspondence from propositional to first-order logic. The key contribution of Martin-Löf's is a novel analysis of equality.
There are two main ways of giving Curry-Howard style account of equality.

Using Leibniz's rule of the identity of indiscernibles to encode propositional equality . This approach is used in the calculus of constructions, but it requires impredicative universes which were rejected by Martin-Löf for philosophical reasons.
A direct constructive characterisation of equality. Giving such a characterisation using identity types might be the main novelty of Martin-Löf's intuitionistic type theory.

Identity types appear deceptively simple today, but they refocussed the understanding of type-theory partly because they gave rise to intriguing semantical questions such as: are identity proofs unique? In some sense this question lead to homotopy type theory and the univalence axiom (which is incompatible with the uniqueness of identities). That the uniqueness of identity proofs is not derivable in Martin-Löf's intuitionistic type theory was shown
by Hofmann and Streicher in: "The groupoid interpretation of type theory". Incidentally, this result also shows that pattern matching is not a conservative extension of traditional type theory.


How quickly can we decompose a number into a set of residues?

If $m=2^k-t$ where $t$ is small, then you can reduce modulo $m$ faster.  In particular, $a \cdot 2^k + b \equiv at+b \pmod{m}$, so reducing an $\alpha k$-bit number modulo $m$ typically requires $\alpha$ multiplications by $t$ and $\alpha$ additions.  This can be significantly faster than the normal algorithms, if $t$ is small enough.

Something similar holds for $m=2^k+t$, too.

So, one plausible approach is to choose a modulus $m$ that is a product $m=m_1 m_2 \cdots m_n$ where each $m_i$ has the form $2^k \pm t$, where $k$ is the word size of your computer (e.g., $k=64$).


Help on the following combinatorial problem?

I've rethought this and my initial bound was correct. In the worst case, $|S| = \Theta(m \; 2^\frac{m}{\lg m})$

Proof is in two parts. Firstly, $|S| = O(m \; 2^\frac{m}{\lg m})$. Consider the possible values of $s$ of a trajectory which ends at $v_x$. Every bit $s[j]$ for $j \ge x$ is 0, and every bit $s[j]$ for $j < x - \frac{m}{\lg m}$ is 1. Therefore there are only $2^\frac{m}{\lg m}$ values which $s$ can take. Multiply up by the number of $v_x$ and we have the upper bound.

Secondly, consider

    0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
    0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
    0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1
    0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1
    0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1
    0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1
    ...
    0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

I assert that this scheme gives you $|S| = \Omega(m \; 2^\frac{m}{\lg m})$. For each column $v_x$ consider also the $(\frac{m}{\lg m}-2)$ columns to its right. Each of the $2^{\frac{m}{\lg m}-2}$ combinations of them gives a different $s$, and in each of those $s$ the top set bit is the top set bit of $v_x$, so there is no double-counting between different $v_x$.


Monotone supermodular function minimization under partition matroid constraints

Consider a graph $G=(V,E)$. Define the set function $f$ over $V$ where $f(A)$ is the number of edges with both end points in $A$. Then $f$ is supermodular and monotone. Suppose $G$ has an independent set of size $k$. Then the minimum of $f(S)$ under the constraints $|S| = k$ (the uniform matroid constraint) will be $0$. If $G$ does not have an independent set of size $k$ then the min will be at least $1$. Hence the problem is inapproximable.


Lower bounds for inversion counting in comparison model?

I'm not totally sure, but it seems you can get $\Omega(n \log n)$ lower bound.

Suppose in the worst case we use $o(n \log n)$ queries. Consider a decision tree for our algorithm. Cause of depth of the tree there should be a leaf such that there are at least two permutations which correspond to it.

Now consider all queries with answers on a path from the root to the leaf. We know that they set a partial, not total, order. Consider two elements, which can not be compared. Take any permutation, which corresponds to this order, and swap these elements.

I don't have a strict proof, but it seems to be true, that after such a swap number of inversions should be changed. If so, we broke our algorithm and obtained lower bound.


Complexity of counting integer roots of multivariate polynomials in a polyhedron?

The decision version of this problem is obviously in $\mathsf{NP}$, and Manders & Adleman showed that a specific case is NP-complete. Namely, even deciding whether there exists an integer $x \in [0, \gamma]$ such that $x^2 \cong \alpha \mod \beta$ (the input here is the triple $(\alpha,\beta,\gamma)$) is NP-complete, which is only one variable and degree 2. I haven't checked the details in a while, but I'm pretty sure their reduction is parsimonious; if so, the counting version you ask about will be $\mathsf{\# P}$-complete as well.


Distribution of variable sized images/boxes(only aspect ratio given) on a 2D area

As mentioned in the comments, the problem is called the (2-dimensional) packing problem. Your problem (Rectangle packing) is NP-complete. It can be shown with a reduction from the Bin Packing problem. See for example this paper Richard E. Korf: Optimal Rectangle Packing: Initial Results. Here's a link that describes an algorithm (the same basic idea as in the paper) in quite a bit of detail. In addition, the paper mentions the problem can be modeled as a constraint satisfaction problem (CSP), so you might be interested in using a CSP-solver if you need to solve the problem in practice. One such solver I have used is MINION.


How much memory is needed for counting distinct elements in a stream exactly with high probability

You can do $O(\log \frac n\epsilon)$ space if you only want an approximation.
The main idea is that you use the random hash function $h$ to do the same protocol as in the Goldwasser-Sipser Set Lowerbound (which you can find, e.g., in the Arora-Barak book).
So you pick a target $y$ and observe whether $h(x_i)$ holds for any $i$.
If the sequence is diverse, then whp. you can find such a $i$, otherwise you cannot.
To increase the probability of success, you can pick $O(\log \frac 1\epsilon)$ different $y$'s of length $O(\log n)$ and do the protocol for each.

If you want an exact answer, then more precise calculations are needed.
I think $O(polylog \frac n\epsilon)$ space might be still enough, but I might be wrong.


As mentioned in the comments, regular grammars are more or less a (string) rewriting system, where the arrow of a derivation is in the reverse direction of the rewriting arrow. Since you seem to be especially interested in term rewriting systems (as opposed to string rewriting systems), the automaton model that you are probably looking for is that of tree automata, that is, finite automata accepting trees instead of strings. I've heard that the following is a very good book on tree automata (although I haven't read through it yet).

H. Comon, M. Dauchet, R. Gilleron, C. Löding
and F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi: "Tree Automata: Techniques and Applications", 2007.

As far as I can tell, the question you asked is quite natural and thus has already been explored. With some googling I found out that Sophie Tison (co-author of the TATA book above) had some invited talks with "term rewriting" and "tree automata" in the title (I haven't read them either).

Tison S. (2011) Tree Automata, (Dis-)Equality Constraints and Term Rewriting. In: Ong L. (eds) Typed Lambda Calculi and Applications. TLCA 2011. Lecture Notes in Computer Science, vol 6690. Springer, Berlin, Heidelberg

Tison S. (2000) Tree Automata and Term Rewrite Systems. In: Bachmair L. (eds) Rewriting Techniques and Applications. RTA 2000. Lecture Notes in Computer Science, vol 1833. Springer, Berlin, Heidelberg


Space-time tradeoff and the best algorithm

The prototypical f and g here would probably be poly-time and polylog space.  The interesting problem here is connectivity (in directed graphs) which can be solved in polynomial time (using linear space) or in polylog space (using super-polynomial time).  It is a famous open problem whether it can be solved in TIME-SPACE(poly,polylog), a class known as SC.

I.e. your question is a well-known open problem.  I don't think that anything non-trivial is known here.


Nondeterministic speed-up of deterministic computation

You should not expect an exciting speed-up. We have

$$\mathrm{DTIME}(f(n))\subseteq\mathrm{NTIME}(f(n))\subseteq\mathrm{ATIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)),$$

and the best known simulation of deterministic time by space is still the Hopcroft–Paul–Valiant theorem

$$\mathrm{DTIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)/\log f(n)).$$

Thus, nondeterminism or alternation is not known to give speed-up by more than a logarithmic factor. (I suspect no super-linear speed-up is known either, though I’m not sure if the HPV theorem can’t be made to work with ATIME in place of DSPACE.)


Finding the minimum number of coordinates to change to get a vector inside a subspace

This problem is NP-hard in general.

This is equivalent to finding the sparsest vector $y\in \mathbb F^n$ such that
$$Ay = -Ax$$

As finding a sparsest solution vector for an underdetermined system of linear equations is NP-hard, so is your problem.


Separating DAGs using separators consisting of lists of nodes and all ancestors

In this answer i assume that $u$ is an ancestor of $v$ if $u$ can reach $v$ by a directed path.
This is basically as hard as Set Cover (Given family $F$ over a universe $U$, find smallest subfamily $F’$ of $F$ whose union is $U$). To reduce from Set Cover:
Make a vertex for every set in $F$ and for every element in $U$. Make an arc from every element to every set that contains it.
Now picking a list corresponding to a set means deleting the set and all the elements in it.
For every element add some new dummy vertices and add arcs from each element to its own private dummy vertices.
Now observe that as long as all elements have not been deleted there are still components of more than $O(1)$ vertices left - an element plus its dummies.


Are there any results on the following "generalized matching" problems?

In http://www.sciencedirect.com/science/article/pii/S0012365X13003543 , we use exactly this process of picking the largest possible clique, then the next largest available clique, and so on (without repeating any vertices). When applied to a cograph $G$, this algorithm forms a cluster graph subgraph of $G$ with the max number of edges possible. The paper contains some combinatorial results on sizes of cliques obtained during such a process.

This paper http://publicaciones.dc.uba.ar/Publications/2015/BDNV15/BDNV15.pdf generalizes our result to a class of graphs beyond cographs.

I'm not sure which way you want to generalize matchings ... towards triangle covers or clique covers, but either way, it seems you will be moving from P-territory into NP-complete land. Unless you restrict your initial graph to certain structural classes.


Your problem is a generalization of the sharing-aware virtual machine colocation problem, and so hard to approximate.

Read this paper for more information:
Michael Sindelar, Ramesh K. Sitaraman, Prashant J. Shenoy: Sharing-aware algorithms for virtual machine colocation. SPAA 2011: 367-378


Complexity of approximating a real function using queries

Not a complete answer, but hopefully a good starting point. It is very instructive to (always!) first consider the discrete analog of your question. If $X$ is some set and $f:X\to\{0,1\}$, what is the minimal number of evaluation queries needed to uniquely identify $f$? As already noted in the OP, the question only makes sense if one fixes a function class $F$ of possible candidate functions $f$ to consider.
This is a well-studied problem, where the key notion is the teaching dimension (which is the minimum size of a teaching set), see here:
https://www.cs.umd.edu/sites/default/files/scholarly_papers/NealGupta.pdf
A teaching set $S\subset X$ is such that the values of $f$ on $S$ uniquely identify $f\in F$, for a given fixed function class $F$.
Nothing is stopping you from defining an $\epsilon$-teaching dimension for real-valued functions. You can define an $\epsilon$-teaching set $S\subset X$ to be such that all $f\in F$ that agree on $S$ all lie within an $\epsilon$-tube (i.e., are all within $\epsilon$ in $\ell_\infty$ distance).
As you can see from the discussion in that paper I linked, the teaching dimension is a rather stringent notion, which motivates more "interesting" variants, such as the recursive teaching dimension. Here again, I encourage you to explore its natural real-valued extensions.


Educational Source or Survey on Analysis of Semidefinite Program?

Check Chapter 6 in the book "The Design of Approximation Algorithms" by Williamson and Shmoys. The book is available on-line here: http://www.designofapproxalgs.com/


Exact algorithms for non-convex quadratic programming

An optimal solution lies on some face.  So, we can go through all the faces of the cube, and find all stationary points on each of the faces.

Here is a more concrete procedure.  A face of the cube can be characterized by two disjoint index sets $I_0$ and $I_1$.  For $i \in I_0$, we fix $x_i = 0$, and for $i \in I_1$ we fix $x_i = 1$.  Let $\tilde{x}$ consist of the remaining unfixed entries of $x$.  This fixing turns the objective function into the following form:

$$
\tilde{x}^{\top} \tilde{A} \tilde{x} + \tilde{c}^{\top} \tilde{x} + d,
$$

with appropriate $\tilde{A}$ and $\tilde{c}$, and some constant $d$, and we want to find the stationary points of this function under the condition that $0 < \tilde{x} < 1$.

To this end, we take the differentiation of the objective function to obtain

$$
\frac{1}{2} \tilde{A} \tilde{x} + \tilde{c} = 0.
$$

Solving this system of linear equations gives you the stationary points, the candidates for optimal solutions.  We go through all of them, check the condition, and choose one with the minimum objective value.

The overall time complexity is something like $O(3^n \text{poly}(n))$ since the number of faces of the $n$-cube is $3^n$ and a system of linear equations can be solved in polynomial time.  The space complexity is polynomial in $n$.


Use Schöning's theorem:

  Let $A_1$, $A_2$ be recursive sets and $C_1$, $C_2$ be classes of recursive sets with the following properties:

  $A_1 \notin C_1$, $A_2 \notin C_2$
  $C_1$ and $C_2$ are recursively presentable,
  $C_1$ and $C_2$ are closed under finite variations.

  Then there exists a recursive set $A$ such that:

  $A \notin C_1$, $A \notin C_2$,
  if $A_1 \in \mathsf{P}$ and $A_2\notin \{ \emptyset, \Sigma^* \}$, then $A \leq^{\mathsf{P}}_m A_2$.

For the purposes of counting dichotomy theorems, the two relevant classes of decision problems are $\text{P}$ and $\text{P}^{\#\text{P}}$.


I'll share my side of the story that is mentioned in Shiva's answer.

Shiva had several questions related to my own research (space-bounded algorithms for reachability problems). We were currently putting the final touches on a full draft of the proof, and were not ready to announce the result.  However, it was clear that Shiva was very interested in this area, so I emailed him saying we had a result in the works and gave him just the theorem statement.  A week later, we had our draft complete and I sent him a copy.  A few weeks later we shared our updated draft on the ECCC.

This worked well for several reasons.

Shiva and I have never met in person, but now we know each other as colleagues interested in similar problems.
Shiva also sent me a copy of his most recent work, which is also related and interesting.
The questions gave me an extra boost of motivation to complete a full draft quickly.

I recommend this course of action in the future: partial disclosure via private communication, full disclosure, and public announcement.


An actual factual reference is

K. Ko. Some observations on the probabilistic algorithms and NP-hard problems. Information Processing Letters, 14(1):39–43, 1982.

(When I first saw this result --- I don't remember where it was now --- it was called "Ko's Theorem". Googling suggests that another theorem has that name as well...)


Approximate matching in table of integer vectors

You are asking for the near neighbor problem for the Jaccard index. If you are ok with some approximation and randomization, I think there exist subquadratic algorithms based on Locality Sensitive Hashing (LSH). LSH schemes based on MinWise independent hashing are known for the Jaccard index: see the LSH survey by Andoni and Indyk and references therein, plus the LSH webpage (which has some code, although I am not sure if there is any for Jaccard specifically). Also see the original MinWise hashing paper.


Good codes decodable by linear-sized circuits?

You should look at Tornado codes {1}, which, for any $R$ and $\epsilon>0$ and large enough $n$ can be designed to recover (with high probability) from a loss of a $(1-R)(1-\epsilon)$ fraction of bits in time proportional to $n \ln \frac{1}{\epsilon}$ (see Theorem 1 in {1}).

{1} Luby, Michael G., et al. "Practical loss-resilient codes." Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. ACM, 1997:  http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/losscodes.pdf


How to define a function inductively on two arguments in Coq?

Coq's fixpoint definitions require that inductive calls receive a structurally smaller argument. Deep down, a fixpoint construct takes a single argument: there's no built-in concept of a recursive definition over two arguments. Fortunately, Coq's definition of structurally smaller includes higher-order types, which is extremely powerful.

Your two-argument fixpoint definition follows a simple pattern: either the first argument becomes smaller, or the first argument remains identical and the second argument becomes smaller. This fairly common pattern can be handled by a simple fix-in-fix.

Fixpoint pair l := fix pair1 (r : Tree) :=
  match l with
    | Tip => match r with
              | Tip => TipTip
              | Bin rl rr => TipBin rl rr
            end
    | Bin ll lr => match r with
                    | Tip => BinTip ll lr
                    | Bin rl rr => BinBin (pair1 rl) (pair lr r)
                   end
  end.

For more complex cases, or if your tastes run that way, you can use recursion closer to the way it's taught in math courses, building the fixpoint from a step computation and a separate well-foundedness argument, often using an integer measure. You can also make your definition look more like a classical program in a non-total language with a separate termination using the Program vernacular.


I used field extensions (and Tarksi's transfer principle) to prove lower bounds for linear degeneracy problems.  Using a field extension of the reals with formal infinitesimals simplified the construction of adversarial inputs.  (But see also Ailon and Chazelle's followup paper, which generalized my result without using field extensions.)

More generally, in the algebraic decision tree model (with real coefficients), the complexity of any problem with real inputs is identical to the complexity of the same problem where the inputs are drawn from any real closed field that contains the reals.


Representation as sum of unit fractions: primitive recursive?

Consider $(p,q,m)\in R_k$ iff there is a set $S\subseteq \{\frac{1}{n}:n\in\mathbb{N}, n> k\}$ such that $|S|=m$ and $\frac{p}{q}=\sum_{s\in S} s$, so $R=R_0$.

It is easy to see that $(p,q,m)\in R_k$ iff there is an $k<\ell\le \frac {qm}p$ such that $(p\ell-q,q\ell,m-1)\in R_\ell$.


Data structure for storing points and finding a predecessor of a point

What about first computing the skyline (a.k.a. maximal vectors, etc.) of all points, then maintain a data structure for orthogonal range reporting?

The range you are interested in is the orthant with coordinates smaller in all dimensions below your query point.

Actually what you are looking for is a dynamic orthogonal range reporting datastructure. But I add the skyline in case you want to prune the set $P$ first (this answers the part you wrote about 'forgetting' point $p$ if there is some $p'\leq p$).


Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?

No, we get counterexamples by considering resource-bounded randomness. In fact the gap between c.e. and $\mathsf{CFL}$ is wide.

Let $R$ be exponential-time random. Then $R$ is $\mathsf{NP}$-immune, i.e., it has no infinite subset in $\mathsf{NP}$. In particular it has no infinite subset that is a context-free language.


What is the following variation on Set Cover known as?

To answer your second question, the Kahn-Crescenzi compendium of NP-hardness results is a valuable source for hardness results, and also covers many variants of core G&J problems. The entry for set cover is a good example of this.


Stronger version(2) of Isolation Lemma for linear forms

For your first question, if $l=1$, then $\frac{K^\frac 23}\epsilon$ is sufficient. This follows the fact that the lower envelope of some lines has the same complexity as the upper convex hull of its dual point system and if you have a convex polygon with integer vertices in $[0,K]^2$, then it can have at most $O(K^\frac 23)$ sides. I know I did not explain the details, but this is anyhow only a partial answer to your question...


How to prove the existence of a pure Nash equilibrium?

If p=q=s=t=−1, then it is easy to see that a pure NE can be reached by local search starting from (a3, a3).  So in the rest of the proof, assume that at least one of p, q, s, and t is equal to 1.

If p=q=1, then (a1, a2) is a pure NE.  Similarly, if s=t=1, then (a2, a1) is a pure NE.

In the remaining cases, at least one of the pairs (p, q), (q, p), (s, t), and (t, s) is equal to (1, −1).  By symmetry, we may assume without loss of generality that p=1 and q=−1.  By assumption, r=1.  Then (a1, a3) is a pure NE.


$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$

The case where $\epsilon$ is a fixed constant in $(0,1)$ represents a partition that each part contains at least a constant fraction of the vertices. This was proven to be NP-complete by Wagner and Wagner. This is also known as balanced minimum cut problem. Note that $|V_i| \leq (1+\epsilon)|V|/2$ if and only if $|V_i| \ge (1-\epsilon)|V|/2$ for $\epsilon$ in $(0,1)$.

Wagner D., Wagner F. (1993) Between Min Cut and Graph Bisection. In: Borzyszkowski A.M., Sokołowski S. (eds) Mathematical Foundations of Computer Science 1993. MFCS 1993. Lecture Notes in Computer Science, vol 711. Springer, Berlin, Heidelberg


I will assume you are in the honest-but-curious model.  You can't represent real numbers in finite space, so I will assume all values are represented in fixed-point arithmetic, to $d$ bits of precision; thus $x$ is represented as $x = x'/2^d$ where $x'$ is an integer.  Then $x \cdot y = x' \cdot y' / 2^{2d}$, so the problem is equivalent to computing $x \cdot y$ where $x,y \in \mathbb{Z}^n$.  Here is a scheme for that.
Pick a sufficiently large prime, and let $E$ denote a public-key encryption algorithm that is additively homomorphic modulo $p$.  Alice generates a public/private keypair for $E$, and computes $E(x_i)$ for each $i$.  She sends these to Bob, along with the public key she generated.  Bob computes $E(x_i y_i)$ for each $i$, using the homomorphic properties of $E$, and from them, computes $E(\sum_i x_i  y_i) = E(x \cdot y)$, again using the homomorphic properties of $E$.  Bob sends $E(x \cdot y)$ to Alice.  Alice decrypts, and shares the result with Bob.
Note that if $E$ is additively homomorphic, given $E(x)$ you can compute $E(2x) = E(x+x)$.  Therefore, given $E(x)$ and an integer $y$ you can compute $E(xy)$, using a double-and-add algorithm (analogous to square-and-multiply).


On the need for a self-correcting function in the PCP theorem

The probability of error when sampling $f(x)$ is $\delta$ when $x$ is chosen at random. Using self-correction, the probability of error is $2δ$ for all $x$ (not only random $x$)


Type of induction principle for fixpoint types

To answer my own question, the paper Generic derivation of induction for impredicative encodings in Cedille shows a type for induction on a fixpoint type. It can look like:

ind : ∀F T (P : Fix F -> *). ((h : F (Σ (Fix F) P)) -> P (in (map fst h))) -> (x : Fix F) -> P x

With Σ being the dependent product and map the functor map of F.


Let $D$ be the distribution on inputs that w.p. $p = 1/(1+\epsilon)$ picks $(x,x)$ for random $x$, and w.p. $1-p$ picks $(x,y)$ for random $x \neq y$. An appropriate choice of random coins leads to a deterministic protocol that never makes mistakes and outputs MAYBE w.p. at most $1/2$ with respect to $D$. In particular, it must answer YES on at least $1-(1/2)/p = 1/2 - \epsilon/2$ of the nodes $(x,x)$.

Suppose that the protocol uses $C$ bits of communications. It therefore has at most $2^C$ leaves. Each leaf is a monochromatic combinatorial rectangle, and so each of the at least $(1-\epsilon) 2^{n-1}$ YES answers must end up in a different leaf. We conclude that $C \geq n-1$.


What is the complexity of computing a compatible 3-coloring of a complete graph?

Apparently, this paper by Cygan, Pilipczuk, Pilipczuk and Wojtaszczyk (2010+) gives a faster (polynomial time) algorithm: http://arxiv.org/abs/1004.5010

It was accepted to SODA 2011.


Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$

The usual answer to "what could cause you to divide by a log?" is a combination of two things:

a model of computation in which constant time arithmetic operations on word-sized integers are allowed, but in which you want to be conservative about how long the words are, so you assume $O(\log n)$ bits per word (because any fewer than that and you couldn't even address all of memory, and also because algorithms that use table lookups would take too much time to set up the tables if the words were longer), and
an algorithm that compresses the data by packing bits into words and then operates on the words.

I think there are many examples, but the classic example is the Four Russians Algorithm
for longest common subsequences etc. It actually ends up being $O(n^2/\log^2 n)$, because it uses the bit-packing idea but then saves a second log factor using another idea: replacing blocks of $O(\log^2 n)$ bit operations by a single table lookup.


I'm not sure this question is on-topic here, and would suggest StackOverflow instead. For what it's worth, I never heard that what you are asking for is possible, but you might obtain better-looking results with Ubigraph (check out the demos, they are amazing).


Practical implementation of Hindley–Milner with typeclasses — matching vs most general unifier

Ok, so I figured it out the next day. It's all dead simple as it came out.

Let's use an example – type applications z a a and z a b where z :: * -> * -> *. The unification will yield that (without further context) z a a is the most general type for both giving substitution {b↦a}. On the other hand, z a a cannot be matched to z a b, as they are simply different.

So now let's dissect the implementations. The mgu x@(TAp l r) y@(TAp l' r') first compares l and l' giving a substitution s1 <- mgu l l'. The s1 is a knowledge of how part of x and y are different. With that knowledge, we can investigate further; that's why we use apply in s2 <- mgu (apply s1 l) (apply s1 l') which gives us next premises on how different x and y are. So the summary is to compose the knowledge: s2 @@ s1 (ordering is as in function composition, e.g. g (f (x)) can be written as (g ∘ f) (x)).

I believe (without a proof though) that it's possible to just use s2 <- mgu r r' and then try to combine s1 with s2 though some kind of recursion would be required. Also, I believe it's possible to match r with r' first and then match l with l'; the ordering is just to make error messages more obvious (order of reading in a file).

The match x@(TAp l r) y@(TAp l' r') is different. We must not approve the first example: z a a vs z a b. In order to do that we need to:

note that a from x would need to become a from y
note that a from x would need to become b from y
tell that the above two premises are contradictory

That's the reason to yielding strange substitutions like {a↦a} which is semantically equivalent to {} but allows for taking #1 into account.
The symmetric composition takes this additional information. It doesn't put apply in the second sub-matching (match (apply s1 r) (apply s1 r')) since applying a substitution would make us lose information about contradictory premises.


Checking if a polynomial factors into linear factors

As far as I know, the best algorithm we have currently to check if $f$ (given by an arithmetic circuit) can be factorized into linear factors is via the randomized algorithm of Kaltofen (PDF) which actually produces blackboxes for all the irreducible factors of $f$, and works over any large enough field. In fact, this problem of polynomial factorization for general circuits was recently shown by Kopparty, Saraf and Shpilka to be equivalent to the problem of blackbox-PIT for general circuits.

As mentioned by Bruno, if you are interested in checking a the given circuit is divisible by a given $\ell$, then this reduces to a specific PIT problem. We don't know how to do this deterministically in general but I know of one special case where we know how to do this PIT. There is a deterministic poly-time algorithm (PDF) to check if a given $\ell$ divides a given sparse polynomial $f$.

(Another trivial special case when $f$ is given by a bounded top fan-in depth three circuit. There, $f \bmod \ell$ is also a bounded fan-in depth three circuit and we know how to do PIT in deterministic polynomial time.)


Use of Process Calculi and PL Theory for modern programming language development

My answer is really just an elaboration of Gilles', that I had not
read before I wrote mine. Maybe it's nevertheless helpful.

Let me begin my attempt at answering your question with a distinction
between two dimensions of programming languages work that relate quite
differently to programming language theory in general and process
calculus in particular.

Pure research.
Product focused research and development.

The latter typically takes place in industry with the aim of providing
programming languages as a product. The teams developing Java at
Oracle and C# at Microsoft are examples.  In contrast, pure research
is not tied to products. Its aim is to understand programming
languages as objects of intrinsic interest and to explore the
mathematical structures underlying all programming languages.

Because of divergent goals, Different aspects of programming language
theory are relevant in pure research and in product focused R&D The
picture below may give an indication what's important where.

One may ask at this point why the two dimensions are so seemingly
different and how they nevertheless relate.

The key insight is that programming language research and development
has multiple dimensions: technical, social and economic.  Almost by
definition, industry is interested in the economic payoff of
programming languages. Microsoft et al don't develop languages out of
the goodness of their hearts but because they believe programming
languages give them an economic advantage.  And they have investigated
deeply why some programming languages succeed, and others, seemingly
similar or with more advanced features, don't.  And they found that
there isn't a single reason. Programming languages and their
environments are complex, and so are the reasons for adopting or
ignoring any specific language.  But the single biggest factor for the
success of a programming language is the preferential attachment of
programmers to languages that are already widely used: the more people
use a language, the more libraries, tools, teaching material are
available, and the more productive a programmer can be using that
language. This is also called the network effect. Another reason is
the the high cost switching languages for individuals and
organisation: mastering language, especially to a not-so-experienced
programmer, and when the semantic distance to familiar languages is
large, is a serious, time-consuming effort.  Given these facts, one
may ask why do new languages get traction at all?  Why do companies
develop new languages at all? Why don't we just stay with Java or
Cobol?  I think there are several key reasons for whey a language does
succeed, and displaces the originally more popular incumbents.

A new domain of programming opens up that has no incumbents to
displace.  The primary example is the web with its concomitant rise
of Javascript.
Language stickiness. By this I mean the high price of changing
language. But sometimes programmers move into different fields,
taking a programming language with them, and being successful with
the old language in the new field.
A language is pushed by a big company with serious financial
firepower. This backing reduces the risk of adoption, because early
adopters can be reasonably sure that the language will still be
supported in a few years. A good example of this is C#.
A language might come with compelling tools and eco-system. Here too
C# and it's .Net and Visual Studio eco-system could be mentioned as
an example.
Old languages pick up new features. Java comes to mind, which, in
each iteration, picks up more good ideas from the functional
programming tradition.
Finally, a new language might have intrinsic technical advantages,
e.g. be more expressive, have nicer syntax, typing systems that
catch more errors, etc.

Given this background, it should not come as a surprise that there is
somewhat of a disconnect between pure programming language research,
and commercial programming language development. While both aim to
make software construction and evolution more efficient, especially
for large-scale software, industrial programming language work must be
more interested in facilitating quick adoption to reach a critical
mass and get the network effect.  This leads to a research focus on
things that working programmers care about. And that tends to be
things like library availability, compiler speed, quality of compiled
code, portability and so on.  Process calculus as we practise it today
is of little use to programmers working on mainstream projects
(although I believe that will change in the future).

Pure programming language research is quite different. It works with
simplified models of programming languages: the $\lambda$-calculus is
a massive simplification of functional programming. In the same way
the $\pi$-calculus is a massive simplification of concurrent
programming. These massive simplifications are the key to successful
research. They enable us to focus on core computational mechanisms
(e.g. $\beta$-reduction for functional programming,
resolution/unification for logic-programming, name-passing for
concurrent computation). To understand if a language like Scala can
have viable full type-inference, we don't need to worry about the JVM.
Indeed thinking about the JVM will detract from a better understanding
of type-inference. That's why abstraction of computation into tiny
core calculi is vital and powerful.

So you can think of programming language research as a massive sandbox
where people play with toys, and if they find something interesting
when playing with a specific toy, and have investigated the toy
thoroughly, then that interesting toy begins its long march towards
mainstream industrial acceptance. I say long march because language
features first invented by programming language researcher tend to
take decades before becoming widely accepted. For example garbage
collection was conceived in the 1950s and became widely available with
Java in the 1990s. Pattern matching harks back to 1970 and is widely
used only since Scala.

Process calculus is an especially interesting toy.  But it's too new
to be investigated thoroughly. That will take another decade of pure
research.  What currently going in process theory research is to take
the single biggest success story of programming language research, the
theory of (sequential) types and develop the theory of types for
message passing concurrency.  Typing systems of moderate expressivity
for sequential programming, say Hindley-Milner, are now
well-understood, ubiquitous and accepted by working programmers.  We'd
like to have moderately expressive types for concurrent programming.
Research on this started in the 1980s by pioneers like Milner,
Sangiorgi, Turner, Kobayashi, Honda, and others, often based,
explicitly or implicitly, on the idea of linearity which comes from
linear logic.  The last few years have seen a major increase in
activity and I expect this upwards trajectory to continue for the
foreseeable future. I also expect this work to start leaking into
product focused R&D, in parts for the pragmatic reason that young
researchers who have been trained in process calculus will go and work
in industrial R&D labs, but also because of the evolution of CPU and
computer architecture away from sequential forms of computation.

In summary, I would not worry that you don't find cutting edge
programming language theory such as process calculus useful in your
own work of building languages. That's simply because cutting edge
theory does not address the concerns of current programming
languages. It is about future languages. It will take a while for the
'real world' to catch up. The knowledge you use to build languages for
today is the programming language theory of the past.  I encourage you
to learn more about process calculus because it's one of the most
exiting areas of all of theoretical computer science.


The alphabet size corresponds to the query complexity of the PCP verifier. So you need to make it a constant eventually so that the PCP has constant query complexity, as stated in the PCP theorem.

And if I am not mistaken, the alphabet size increases from $\left|\Sigma\right|$ to $\Omega(\left|\Sigma\right|^c)$ for some constant $c$ in each graph powering step. If you do not make the alphabet reduction in middle steps, the alphabet size will blow up exponentially within a logarithmic number of iterations.


When does "X is NP-complete" imply "#X is #P-complete"?

The most recent paper on this question seems to be:

Noam Livne, A note on #P-completeness of NP-witnessing relations,
Information Processing Letters, Volume 109, Issue 5, 15 February 2009, Pages 259–261
http://www.sciencedirect.com/science/article/pii/S0020019008003141

which gives some sufficient conditions.

Interestingly the introduction states "To date, all known NP complete sets have a defining relation which is #P complete", so the answer to Suresh's comment is "no examples are known".


Proof assistant usage in complexity theory research?

A general rule of thumb is that the more abstract/exotic the mathematics you want to mechanise, the easier it gets. Conversely, the more concrete/familiar the mathematics is, the harder it will be. So (for instance) rare animals like predicative point-free topology are vastly easier to mechanize than ordinary metric topology.

This might initially seem a bit surprising, but this is basically because concrete objects like real numbers participate in a wild variety of algebraic structures, and proofs involving them can make use of any property from any view of them. So to be able to the ordinary reasoning that mathematicians are accustomed to, you have to mechanize all these things. In contrast, highly abstract constructions have a (deliberately) small and restricted set of properties, so you have to mechanize much less before you can get to the good bits.

Proofs in complexity-theory and algorithms/data-structures tend (as a rule) to use sophisticated properties of simple gadgets like numbers, trees, or lists. Eg, combinatorial, probabilistic and number-theoretic arguments routinely show up all at the same time in theorems in complexity theory. Getting proof assistant library support to the point where this is nice to do is quite a lot of work!

One context where people are willing to put in the work is in cryptographic algorithms. There are very subtle algorithmic constraints in place for complex mathematical reasons, and because crypto code runs in an adversarial environment, even the slightest error can be disastrous. So for example, the Certicrypt project  has built a lot of verification infrastructure for the purpose of building machine-checked proofs of the correctness of cryptographic algorithms.


Formal notion for energy complexity of computational problems

Is there a well studied adaptation of Turing machines that account for the energy consumed during the execution of algorithms?  No!

But maybe you could come up with one. It's possible you could divide the Turing machine steps into reversible and non-reversible (the non-reversible ones are where information is lost). Theoretically, it is only the non-reversible steps that cost energy. A cost of one unit of energy for each bit that is erased would theoretically be the right measure.

There is a theorem of Charles Bennett that the time complexity increases by at most a constant when a computation is made reversible (C.H. Bennett, Logical Reversibility of Computation), but if there are also limits on space, then making the computational reversible might incur a substantial increase in time (Reference here). Landauer's principle says that erasing a bit costs $kT\, \ln 2$ of energy, where $T$ is temperature and $k$ is Boltzmann's constant. In real life, you cannot come anywhere close to achieving this minimum. However, you can build chips which perform reversible steps using substantially less energy than they use for irreversible steps. If you give reversible steps a cost of $\alpha$ and irreversible steps a cost of $\beta$, this seems like it may give a reasonable theoretical model.

I don't know how Turing machines with some reversible steps relate to chips with some reversible circuitry, but I think both models are worth investigating.


Time complexity with irrational exponent?

While admittedly I haven't done the analysis, and this is not strictly a decision problem, I am willing to wager the best known matrix multiplication algorithms (by Coppersmith, Winograd, Stothers, Williams, et al) have irrational exponent.

This can be seen more clearly in the simple case of Strassen's algorithm, which has running time $O(n^{\log_2 7})$.

And, this is not precisely what you asked, but Ryan Williams has shown that all algorithms that solve SAT in space $n^{o(1)}$ require time $n^{2 \cos(\pi/7) - o(1)}$, which is another interesting and unusual appearance of an irrational constant in TCS.


As  pointed out by Logan Mayfield, Scott Aaronson's blogpost on the topic completely resolves my question. Oracles is a fundamental tool for rigorous investigation of computational complexity classes,

  “bring out the latent strengths” of one class over another class.

The root cause of my concerns was that little (as far as I understand - nothing) can be proven unconditionally about quantum speedups in the unrelativized (compiled to physical hardware) world. Of course, this obstacle does not diminish the power of the oracle framework as a major tool enabling progress in quantum computation theory, including the celebrated example of Shor's algorithm.

Personally, it is a consolation to learn from Scott that

  This [relativized vs. unrelatized complexity] is an absolutely crucial distinction that trips up just about
  everyone when they’re first learning quantum computing.


There's a fair amount of work on stream clustering (which is slightly different to online methods, but is essentially what you want). The above reference by Guha et al is a very good one, and for a more general perspective on what kinds of techniques work, and what methods have been used in the past (both heuristic and precise), you might want to look at my survey on clustering on streams.


Number of solutions for a system of linear equations over a finite ring

The answer to (1) is yes (regardless of the properties D.W. asked for in the comments), depending on how $R$ is given: First, note that since $R$ is finite, the abelian group $(R,+)$ is of the form $\mathbb{Z}_{p_1^{k_1}} \oplus \dotsb \oplus \mathbb{Z}_{p_\ell^{k_\ell}}$, where $\ell \leq \log_2|R|$. Now, if $R$ is only given to you by generators and relations, even finding this decomposition is as hard as factoring (but given a factoring oracle, it can then be done easily). But if $R$ is fixed for all time (not part of the input), then this can be done as a once-and-for-all off-line precomputation, or if $R$ is part of the input, this can be done in $O(|R|)$ steps (even when given generators and relations).

So depending on your assumptions, the preceding step is either hard or easy. But let's suppose it's done. Now we'll use two viewpoints on the elements of $R$ to reduce to linear algebra over abelian groups.

Viewpoint 1: We may consider elements of $R$ as "vectors" with $\ell$ integer coordinates, where we consider the $i$-th coordinate modulo $p_i^{k_i}$.

Viewpoint 2: This requires a little setup. Let $Hom(\mathbb{Z}_{p_j^{k_j}}, \mathbb{Z}_{p_i^{k_i}})$ denote the set of ring homomorphisms between these two rings. In particular, when $p_i \neq p_j$, this is zero; when $p_i = p_j$ if $k_i < k_j$ then this involves taking element of $\mathbb{Z}_{p_j^{k_j}}$ modulo $p_i^{k_i}$, and possibly multiplying it by an element of $\mathbb{Z}_{p_i^{k_i}}$ (which we may represent by an integer, treated modulo $p_i^{k_i}$); if $k_i > k_j$ it involves possibly multiplying by an element of $\mathbb{Z}_{p_j^{k_j}}$ (represented by an integer), and then applying the unique embedding of $\mathbb{Z}_{p_j^{k_j}}$ into $\mathbb{Z}_{p_i^{k_i}}$ (as the multiples of $p_i^{k_i-k_j}$, modulo $p_i^{k_i}$)

Now, consider the left multiplicative action of any $r \in R$ on $R$. Then we may associate to $r$ an $\ell \times \ell$ matrix, where the $(i,j)$ entry is an element of $Hom(\mathbb{Z}_{p_j^{k_j}}, \mathbb{Z}_{p_i^{k_i}})$, which can be represented by an integer, following the conventions above.

Now, replace each entry of $A$ by the associated $\ell \times \ell$ matrix as in viewpoint 2, replace each entry of $b$ by the associated vector as in viewpoint $1$, and replace each entry of $x$ with a vector of length $\ell$ (as in viewpoint 1).

Now the original problem has been reduced to linear algebra over abelian groups, which can be solved in polynomial time (see, e.g., Mikael Goldmann and Alexander Russell. The complexity of solving equations over finite groups. Inf. Comput., 178(1):253–262, 2002).


Find the Discrete Pair of {x,y} that Satisfy Inequality Constriants

This is a rasterization problem. For linear inequalities, the regions are polygonal. The classical approach to polygon rasterization is scan conversion; you may learn about it in any textbook on computer graphics.

Preparatory to scan conversion, you will need to convert your linear inequalities (defining half-planes) into an oriented list of edges. One way is to compute the convex hull of the dualized inequalities.

For general polynomial inequalities, the problem is considerably harder. Scan conversion with plane sweeping and active edge lists will do the trick. Detecting sweep events requires you to solve systems of polynomial equations in two variables, which may be done with a combination of numerical and symbolic methods. One way uses resultants and root finding to determine the intersection events up front. Another approach is more incremental, less efficient but significantly simpler:

Assume a bounding box is given. For each y going from the maximum to the minimum, incrementally evaluate the coefficients of the polynomials as functions of y using forward differencing, yielding polynomials depending only on x for each scan-line. Their roots will serve as the rasterization bounds for that scan-line, and you can learn how to find them in a book on numerical methods (Numerical Recipes is popular).

Edit: When I wrote my answer, the last inequality had subscripts rather than superscripts, so it appeared linear. Now I see it is quadratic. That still makes it a rasterization problem although a non-polygonal one. For this specific case you can use circle rasterization to cut out the annulus. In the most general case, you will need polynomial techniques along the lines of my last paragraph. I added some more detail on this.


Relation between $AC^0$ and regular languages

The following paper seems to contain an answer:

Mix Barrington, D. A., Compton, K., Straubing, H., Therien, D.: Regular languages in $\mathsf{NC}^1$. Journal of Computer and System Sciences 44(3), 478-499 (1992) (link)

One of the characterizations obtained there is as follows. The class $\mathsf{REG} \cap \mathsf{AC}^0 \subset \{0, 1\}^*$ contains exactly those languages that can be obtained from $\{0\}$, $\{1\}$ and $\mathsf{LENGTH}(q)$ for $q > 1$ with a finite number of Boolean operations and concatenations. Here every language $\mathsf{LENGTH}(q)$ contains all strings whose length is divisible by $q$. (There is also a logical characterization and two algebraic ones.)


Reference request: Arithmetic circuit complexity

This depends on what you want to do. For more structural questions there is a relatively recent survey by Meena Mahajan:

Meena Mahajan: Algebraic Complexity Classes.

There is also the book by Bürgisser:

Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory.

For Geometric Complexity Theory, you might try the theses of Joshua Grochow or Christian Ikenmeyer. I think both of them have introduction into the field, but I must admit that I have read neither of them.


Explain Gurvits's tensor-rank interpretation of Deolalikar's paper

[I was reading something I thought was totally unrelated and then had an "aha moment" so I think I've figured out at least part of the answer.  I'm not sure if this is what Gurvits had in mind, but this makes sense to me.]

A distribution on n binary variables $x_1,...,x_n$ can be viewed as an element of the tensor product $\mathbb{R}^2 \otimes \dotsb \otimes \mathbb{R}^{2}$ (n factors) (actually the associated projective space, but we'll get to that).  If we label the basis elements of each copy of $\mathbb{R}^2$ by $|0\rangle$ and $|1\rangle$, then a basis of this tensor product space is given by the set of all n-bit strings.  If we have an element of this tensor product whose coefficients sum to 1, then we can interpret the coefficient of any given n-bit string as the probability of that string occurring -- whence, a probability distribution!  Now, since we only want probability distributions (coefficients summing to 1) we can normalize any vector in the tensor product to have that property.  By only considering normalized tensors, we are really only considering elements of the projective space of this tensor product.

Now we have to connect tensor-rank to Deolalikar's notion of polylog-parametrizability.  According to this page by Terry Tao, it seems that Deolalikar's notion of polylog-parametrizability is that the distribution $\mu$ can be "factored into potentials" as $\mu(x_1,...,x_n) = \prod_{i=1}^{n} p_i(x_i ; x_{pa(i)})$ where pa(i) is a set of polylog(n) variables, defined to be the "parents of i" and $p_i( - ; x_{pa(i)})$ is a distribution on $x_i$ that depends only on these parent variables.  Moreover, the directed graph of parents should be acyclic.

Let's start with a very simple kind of distribution. Suppose $\mu$ satisfies $\mu(x_1, ..., x_n) = \prod_{i=1}^{n} p_i(x_i)$ for some distributions $p_i$ (where $p_i$ depends only on $x_i$).  Then it is hopefully clear that the corresponding tensor is the rank 1 tensor: $(p_1(0)|0\rangle + p_1(1)|1\rangle) \otimes \dotsb \otimes (p_n(0)|0\rangle + p_n(1)|1\rangle)$.

For a slightly more complicated distribution, suppose we want to consider the uniform distribution over the strings where $x_{2i} = 1 - x_{2i+1}$ (they are each other's negation) for all $i$.  In Tao's interpretation of Deolalikar's language, this would be a $O(1)$-parametrizable distribution.  Then this corresponds to the tensor $(|0\rangle \otimes |1\rangle + |1\rangle \otimes |0\rangle) \otimes \dotsb \otimes (|0\rangle \otimes |1\rangle + |1\rangle \otimes |0\rangle)$ (needs to be normalized).  If we write this out in full, it contains $2^{n/2}$ terms, and so has tensor-rank at most $2^{n/2}$ over $\mathbb{R}^2$.  However, over $\mathbb{R}^2 \otimes \mathbb{R}^2$, it has tensor-rank 1!  I believe the latter fact corresponds to the fact that the factorization can be described by $O(n)$ numbers -- $O(1)$ for each pair of adjacent bits, for each of $O(n)$ adjacent pairs.  Significantly smaller than the $2^n$ real numbers required in theory for an arbitrary distribution mu on the Boolean cube.

I'm still having trouble formulating two issues, and would appreciate further answers on them:

Making the latter correspondence precise
Writing out the formulae for the tensor corresponding to polylog-parametrizable distribution, and getting an upper bound on its rank.


On optimality of Grover algorithm with high success probability

For the sake of completeness, here's an answer.

Let $Q_\epsilon(f)$ denote the $\epsilon$-error quantum query complexity of computing a function $f$ and $\mathsf{OR}_n$ be the OR function on $n$ bits, defined as $\mathsf{OR}_n(x_1,\ldots,x_n)=\bigvee_{i=1}^n x_i$. (Note that this is different from the problem where you are promised that the input has exactly one 1 and the objective is to find that 1. That problem can be solved with no error in $\Theta(\sqrt{n})$ queries.)

Then we have for all $\epsilon \in [2^{-n},1/3]$,

  $Q_\epsilon(\mathsf{OR}_n) = \Theta(\sqrt{n\log(1/\epsilon)})$.

This follows from Bounds for Small-Error and Zero-Error Quantum Algorithms.

In fact, we know something more general. For all symmetric functions $f$, which are functions that only depend on the Hamming weight of the input, we have that for all $\epsilon \in [2^{-n},1/3]$,

  $Q_\epsilon(f) = \Theta(Q_{1/3}(f)+\sqrt{n\log(1/\epsilon)})$.

This was shown in A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions.


Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$?

No, there is no decomposition of the entire family $\{F_{2^n}\}_{n\geqslant1}$ into a single finite gate-set. Here's why.

The QFTs involve only coefficients over $\overline{\mathbb Q}$, the complex algebraic closure of the rational numbers. In analogy to [Adleman+Demarrais+Huang–1997], if we involved any gates which included any transcendental numbers, we could choose a minimal set of transcendentals $\{\tau_1, \tau_2, \ldots\}$ and describe the gate-coefficients essentially as rational functions $\overline{\mathbb Q}(\tau_1, \tau_2, \ldots)$. To obtain the QFT as a product of such gates, we must arrange for all of the transcendental components to cancel (a similar thing must occur to ensure each of the gates are unitary); but then we might as well replace all of the transcendentals with $0$, so that all of the coefficients are algebraic. So we restrict ourselves to algebraic gate-sets without loss of generality.

The coefficients of a finite gate set over $\overline{\mathbb Q}$ can all be contained in a finite-degree extension of $\mathbb Q$, which one may construct by extending $\mathbb Q$ by those very coefficients. However, the gates $\mathrm{CZ}_{2^n}$ obviously have coefficients belonging to field extensions over $\mathbb Q$ of degree $2^{n-1}$, i.e. of unbounded degree.
Thus the family of QFTs of order $2^n$ does not decompose into any finite gate-set.

As a corollary, we cannot hope to have any algorithms in $\mathsf{EQP}$ which relies on QFTs over cyclic rings of unbounded size — note that the same problem occurs for any family of circuits which might use QFTs of arbitrary order.


Programming language supporting infinitary rewriting of regular term graphs?

Yes, Prolog.

The specification of unification in the Prolog standard omits the occurs check, and as a result variables range over rational trees. Additionally,  many Prolog (such as SWI Prolog and YAP) implementations support tabling, which permits defining and using coinductively defined predicates.


I am not sure I understand the problem correctly, but let me try a definition:
Given a graph and an integer k.
Find the subset $S$ of $k+1$ vertices with max sum of weights such that $S$ induces a connected graph (i.e. there is a tree with k edges spanning $S$).

This sounds to me like the Steiner tree problem
http://en.wikipedia.org/wiki/Steiner_tree_problem

The steiner tree problem gives as input a graph, a set of terminals and asks for a set of edges from the graph (i.e. a tree) that connects all terminals.
The goal is to minimize the sum of the edge weights.

Gary and Johnson showed this NP-complete, I believe even for all edge weights 1.

Give the terminals a high weight such that any solution would need to take all terminals.
The rest of the vertices gets weight 1. Since a tree always has 1 edge less than number of nodes the question is find a set of nodes such that all terminals will be connected.

Hence your problem is NP-complete.
Much work has been done on approximation, there has been comparison of different implementations. I seem to remember there was a DIMACS challenge on the Steiner tree problem.


Note the beginning of the sentence you quoted.  It says

  In their non-uniform versions these circuit complexity classes contain problems which are not computable at all in the ordinary sense (e.g., any unary language is in AC0).

The nonuniform version of AC0 is defined as the class of problems which are decided by a (not necessarily uniform) family of boolean circuits of polynomial size and constant depth with unbounded fan-in.  Since there is no uniformity condition, you can use completely different circuits for different lengths, implying that you can decide any unary languages (including undecidable ones).  This is the motivation of the uniformity condition.  For detail, see Proposition 11.2 of Computational Complexity by Papadimitriou.


Is there a suitable algorithm to draw a mixed constituency/dependency graph in a coordinate system?

you seem to want the following

a graph layout algorithm. many std algorithms typically use force-based methods where nodes are connected by replusive/attractive "springs" and the equilibrium/low energy state is obtained through some amt of iteration (of the corresponding globally-constructed force-related differential equation). the output of the algorithm is a set of 2-d or 3-d coordinates for nodes and (usually) edges.
ability to hand-modify the results of that algorithm. typically called a "graph editor". this starts with the coordinates from the layout algorithm and allows adjustment.

re (1) the forefront software seems to be graphviz. re (2) see eg this question "what is the best graph editor" on mathoverflow.

browsing the graphviz gallery, here are two graph types similar to what you want.

ER diagram and traffic light.

you say you have two types of edges. a simple way would be to have directed edges "toward or away" as in the traffic light example. or the edges can be labelled in two ways as in the ER diagram. both examples show two different node types using different shapes or labels, or shading etc. other approaches would be to use coloring.

as the mathoverflow Q/As indicate there are many graph editors. the std one with graphviz is "dotty". see eg pdf "editing graphs with dotty" by Koutsofious.

another technique for graphing, possibly large graphs, is to look at structural compositions eg clique decompositions.