Is Eulerian Path (or Eulerian Cycle) definable in Monadic Second Order Logic?

Parity cannot be expressed in MSOL (see for instance http://www.cs.technion.ac.il/~janos/COURSES/236331-15/Lec-1.pdf), but connectedness Yes. Using instead $C_2$MSOL, one can express the existence of an eulerian cycle by using the equivalent characterisation : connected and every vertex has degree even.


Do you know this problem of deciding whether a given 0-1 matrix contains k pairwise disjoint “column-paths”?

(from comments, per request)

Here is a sketch of a polynomial-time solution.

First, interpret matrix $A$ as a bipartite graph $G=(V \cup U,E)$, with $m$ nodes in part $V$ and $n$ nodes in part $U$, $n \le m$. Then column-paths are $U$-saturating matchings, i.e., matchings of size $n$ (each node of $U$ is incident to precisely one edge in the matching).

The union of $k$ such matchings is a simple $k$-matching of size $kn$ (each node of $U$ is "covered" precisely $k$ times). Conversely, if there is a simple $k$-matching of size $kn$, by Hall's theorem there are also $k$ disjoint $U$-saturating matchings.

Hence to solve the problem it is enough to find a maximum-size simple $k$-matching. This is possible in polynomial time.

Some background:

A simple $k$-matching is a subset $M \subseteq E$ such that each node is incident to at most $k$ edges in $M$. A simple $1$-matching is a matching in the usual sense. For more information on (simple) $k$-matchings and algorithms for finding them, see, for example:

Korte & Vygen (2008): Combinatorial Optimization—Theory and Algorithms, 4th edition, Chapter 12.


Reading Baier and Katoen closely, they are considering both finite and infinite transition systems. See page 20 of that book for definitions.

First, take the simple transition system $EVEN$:

Lemma: No LTL formula recognizes the language $L_{even} = $Traces$(EVEN)$. A string $c \in L_{even}$ iff $c_i = a$ for even $i$. See Wolper '81. You can prove this by first showing that no LTL formula with $n$ "next-time" operators can distinguish the strings of the form $p^i\neg p p^\omega$ for $i> n$, by a simple induction.

Consider the following (infinite, non-deterministic) transition system $NOTEVEN$. Note that there are two different initial states:

Its traces are precisely $\{a,\neg a\}^\omega - L_{even}$.

Corollary to the Lemma: If $NOTEVEN \vDash \phi$ then $EVEN \not\vDash \neg\phi$

Now, consider this simple transition system $TOTAL$:

Its traces are clearly $\{a,\neg a\}^\omega$.

Thus, $NOTEVEN$ and $TOTAL$ are not trace equivalent. Suppose they were LTL inequivalent. Then we would have an LTL formula $\phi$ such that $NOTEVEN \vDash \phi$ and $TOTAL \not\vDash \phi$. But then, $EVEN\vDash \neg\phi$. This is a contradiction.

Thanks to Sylvain for catching a stupid bug in the first version of this answer.


One way randomised communication complexity of disjointness

The answer is $\Theta(m\log m + \log\log |U|)$.  In the public coins model, we have (as described above) $\Theta(m\log m)$.  As Yuval suggested above, for the upper bound in the private coins model we need only an additive $O(\log n)=O(\log m + \log\log |U|)$ bits (see theorem 3.14 in the K&N book), where $n$ is the length of the encoding of the input ($n=m\log|U|$).  For the additional lower bound of $\Omega(\log\log |U|)$ in the private coin model, it is enough to concentrate on the case $m=1$ (as the other items can be fixed to be all different), which is just the equality function on $\log |U|$-bit strings, whose private coin complexity is logarithmic in that (example 3.9 in K&N).


Efficiently computable function as a counter-example to Sarnak's Mobius conjecture

There have been interesting developments on this problem, however Replacing $AC^0$ with ACC(2) (Namely allowing mod 2 gates as well) is still well out-of-reach. Some progress beyond Ben Green's theorem can be found in this MO question https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function as well as this one https://mathoverflow.net/questions/97261/mobius-randomness-of-the-rudin-shapiro-sequence . In addition, Jean Bourgain proved Mobius randomness for every monotone function $f$ (in terms of the binary-digit expansion).


To what extent, computational ability for hard tasks helps in solving easy tasks

By counting you should be able to compute about $2^{2^m \cdot s}$ functions with such circuits of size $s$ so I'd guess $s=2^{n-m}$ should be enough to compute all functions.


What are some algorithms where space complexity tends to be the limiting factor in practice?

Most computations in algebraic geometry / commutative algebra.
Most involve computing Grobner bases, which are EXPSPACE-hard in general. There are some parameter regimes where this improves and thus some computations can reasonably be done in practice (e.g. using Macaulay2 or SINGULAR), but very often it quickly eats up all the space and crashes.  I think one of the first papers to look at this was Bayer & Mumford "What can be computed in algebraic geometry?".
(FWIW, my recent experience with these programs has been that there is a trichotomy: either the answer returns in (1) seconds, (2) a few minutes, or (3) so long that you give up / so much memory that it crashes.)


What are the pros and cons for type cases in dependent type theories?

The basic idea is clearest when you think about things in terms of Tarski-style universes. There, you have a data type of codes, and an interpretation function which maps codes to types. In this case, it is obvious that you can discriminate on type codes, even though this is a much more questionable operation on types. For example, $\mathbb{N} \to 0$ and $\mathbb{R} \to 0$ are equal as sets, which means that injectivity of type constructors is obviously false — $\mathbb{R} \neq \mathbb{N}$!
-- A Tarski-style universe in Agda
—-
-- Declarations.
data TypeCode : Set
El : TypeCode → Set

-- Definitions.
data TypeCode where
  nat : TypeCode
  pi  : (a : TypeCode) (b : El a → TypeCode) → TypeCode

El nat      = Nat
El (pi a b) = (x : El a) → El (b x)

A definition very similar to this Agda code is pretty typical when building PER models of type theory — the main difference is just that everything is valued in PERs.
Distinguishing type codes and types is not “normal mathematics", which is a strike against it, but on the other hand, the stricter, more decidable, equality on type codes can make various forms of automation easier to implement.
Which is better? It’s unclear! As Edwin Brady says, we don’t know how to do dependent types wrong yet.


Here's how to do (2) for Dominating Set. Since Dominating Set is contraction-bidimensional, we need to show the solution value is $\Omega(r^2)$ on a partially triangulated $r*r$ grid. So consider a partially triangulated $r*r$ grid. There might be vertices on the outer cycle of the grid of large degree (for example, one vertex might be adjacent to all other vertices on the outer cycle). Therefore, we are going to ignore the outermost 2 cycles of the grid, so we look at the $(r-4) * (r-4)$ partially triangulated subgrid "in the center", which has $\Omega(r^2)$ vertices, and we consider which vertices may be used to dominate this subgrid. Due to planarity, no vertex in this inner grid can be adjacent to a vertex on the outer cycle. All vertices which do not lie on the outer cycle have degree at most 8, as the partial triangulation has to keep the graph planar and can only make edges to the 8 vertices which are above, below, left, right, and diagonally adjacent to a vertex. So the $\Theta(r^2)$ vertices of the inner $(r-4)*(r-4)$ grid must be dominated by vertices which have degree at most 8 each. So when it comes to this inner grid, at best each vertex can dominate 8 other vertices and itself, for a total of 9. So you need at least $(r-4)^2 / 9$ vertices to dominate the inner grid, so a dominating set on the partially triangulated grid has size $\Theta(r^2)$.


Partitioning a square for optimal queries

A good idea seems to be to use nonoverlapping circles in the densest circle packing in 2d. Please check the corresponding Wiki-page: https://en.wikipedia.org/wiki/Circle_packing. This way you reach up to $C = 0.907$ coverage. Assuming the scittles are uniformly distributed and $N \gg \frac{1}{S_c}$, where $S_c$ is the surface of the cricles you use, we may estimate that you'll have to pay $\frac{CN\#circles}{P} = C^2N/S_cP$ for fetching and roughly $\#circles = C/S_c$ for looking in thustly covered area. We may cover the gaps, which cover about $1-C$ of the square, by correspondingly smaller cirlces again, the cost of looking should be just as before. The cost of fetching is hard to estimate, without delving into geometry to much at this point, but i guess it may be roughly $(1-C)N/P$. Also, you may terminate one you reach $N$.

A smart adversary would start placing the scittles in the gaps. I assume it's a good idea to pick a random reference for the lattice of circle placing. Also you could randomly pick the areas to  check for scittles from the main lattice (covering $C$) and from the minor lattice (covering $1-C$).

Now we are stuck with the decission which radius to pick in $[0,R]$. I assume as large as possible under the placed constrains makes sense. There is probably space for optimization by choosing some radius $r$ so that your main lattice has little overflow over your plate.

Alternatively you may use the densest packing, but with circles overlapping. This way all the gaps vanish and you skip the cost for lookups on the secondary lattice.

Hope this input helps you somewhat.


Interesting!  I don't know of any nontrivial result of that kind -- neither one that says "if [XYZ] then BPP=BQP", nor one that says "if [XYZ] then BQP ⊆ BPTIME(2o(n))."  The closest I can think of is a result of Terhal and DiVincenzo, who showed that if constant-depth quantum sampling can be efficiently classically simulated then BQP ⊆ AM.  (Later work, by Bremner-Jozsa-Shepherd and myself and Arkhipov, shows that the same assumption would even imply P#P = BPPNP.)  Combining that with some assumption that gave AM ⊆ BPTIME(2o(n)) would then yield what you wanted.


Minimum-Cost Flow Problem with Constraint on the Total Incoming/Outgoing Flow for the Vertices

This is a standard variant (if not the standard variant) of the minimum-cost flow problem.  The "flow requirements" are sometimes called balance conditions and sometimes called vertex supplies/demands.  It can be solved in polynomial time using any number of algorithms.

In particular, you can reduce to the single-source single-target variant in polynomial time as follows:

Compute a conservative upper bound $M$ on the cost of any flow in your network; for example, let $M = \sum_e cap(e)\cdot |cost(e)|$.  Alternatively, treat $M$ as a symbolic infinite value.
Add new nodes $s^*$ and $t^*$.
Add arcs $s^*\to s$ and $t\to t^*$ with infinite capacity and zero cost.
For every node $v_i$ with $r_i>0$, add an arc $s^*\to v_i$ with capacity $r_i$ and cost $-M$.
For every node $v_i$ with $r_i<0$, add an arc $v_i\to t^*$ with capacity $-r_i$ and cost $-M$.
Set all vertex requirements to zero.

The minimum-cost feasible flow from $s^*$ to $t^*$ in this modified network saturates every arc $s^*\to v_i$ and $v_i\to t^*$, and the remaining arcs carry the minimum-cost flow from from $s$ to $t$ in the original network that meets all the flow requirements.


The question is usually taken to be moot, for the following reason.  Grover's algorithm is a combinatorial search algorithm to find a solution to an arbitrary predicate.   While, yes, $\Theta(\log N)$ is the quantum gate complexity in each stage of the black-box algorithm, the predicate needs to be computed too.  The quantum gate complexity of that is $\Omega(\log N)$, because otherwise it wouldn't read the whole input and you could discard some of the input bits from the search.  On the other hand, an interesting predicate could take a lot more time than that.  Hence, the number of calls to the predicate is taken to be the standard coin, just as it is for the classical analogue of Grover's algorithm, namely random guessing.


Can Scheme's call/cc implement all known control flow structures?

In this answer, I'll take "expressible" to mean "macro-expressible" in the sense of Felleisen 1991, On The Expressive Power of Programming Languages. (Intuitively, a language feature is macro-expressible if you can define it as a local source transformation, without using a whole-program transformation.)

With this definition, the answer is no: delimited control is not macro-expressible in the lambda-calculus + call/cc. To express delimited control operators using call/cc. In order to implement the control delimiters (the reset part of shift/reset), you need some state to simulate the continuation marks, essentially to encode a stack to simulate the dynamic lifetimes of the continuation marks.

However, delimited control is a universal effect, in the following sense. In his PhD thesis, Andrzej Filinski showed that any expressible side effect is encodable using either delimited continuations, or call/cc and a single cell of state. Roughly, an "expressible side effect" is any effect whose monadic type can be defined in terms of the types of the programming language.

Surprisingly, this idea seems quite interesting in practice. Over the last decade, Gordon Plotkin and John Power have advocated the idea of taking an algebraic semantics of effects theories: the idea is that you specify the side-effecting operations you are interested in, and the equations you expect them to satisfy, and then you can generically get a semantics by taking the free monad over this theory.

Matija Pretnar and Andrej Bauer took this mathematical approach, and then implemented it in their Eff language to invent a new language construct dubbed "effect handlers": you can write code that uses a set of imperative features, and then give the imperative features a semantics by writing a set of handlers which say how to implement each effectful operation.


Storage requirements for median selection (two passes algorithms)

The first paper to prove bounds for more than 1 pass was my paper with Jayram and Amit from SODA'08. Then there is the paper that Warren mentioned, which improves the bounds by a cleaner proof.

In short, we understand the dependence if you allow constants in front of the number of passes. Of course, these constants are in the exponent, so you can ask for a precise understanding. My main complaint is that the model of multipass streaming is not all that well motivated.

The more intriguing question is whether we can prove a branching program lower bound. Can it be that even for a bounded space algorithm that can access memory as it pleases, the best strategy is to just do multipass streaming?

The answer appears to be affirmative, and we have some partial progress towards proving it.


Search for all nearest neighbors within a certain radius of a point in 3D?

My recommendation is NOT to roll your own for now. There are two software packages that I'd recommend you try first.

ANN (by Arya and Mount) is state-of-the-art for low dimensional near neighbor search and includes the "fixed radius" search that you're looking for.
Nearpt3 (Wm Randolph Franklin) is another package that is specifically optimized for 3D, and supposedly can handle 100s of millions of points. I'm not entirely sure it handles fixed radius queries as well as regular nearest neighbor search, but you can look into it.

If neither of these is appropriate, then you can return and ask :).


More efficient non-uniform derandomization ?

I don't think something much better is known.  Because for example, if it were possible to derandomize circuits with only a sublinear blowup, then I think it would also be possible to non-trivially (but non-uniformly*) derandomize communication protocols.  And I don't believe the latter is known.  Adleman's proof gives a linear blowup as you say, so that the derandomization of communication protocols is trivial because it would give a linear blowup in the communication complexity.

*: By "non-uniform" in the context of communication protocols, I mean the algorithm for the two parties to compute the next bit to send to the other is not explicit.  I recall reading a discussion about this in some paper, but I can't seem to find a reference now...


Can chess simulate a Universal Turing Machine?

I also think that a very similar question has been asked before, I think first here: https://mathoverflow.net/questions/27967/decidability-of-chess-on-an-infinite-board/63684
Here is my updated and modified opinion.

I think the problem is not solved completely, but the answer is almost surely yes. I do not have a proof for chess, as I lack the ability to design certain configurations but I think they must exist. And even if they don't, for some chess-like game they certainly do which shows that the attempts to prove decidability should be incorrect. Later I realized that there is a very similar argument to mine here: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006 but my proof shows that in fact two counters are enough and maybe mine is more detailed.

The reduction relies on the notion of a stack machine. A stack machine with only two stacks using a stack alphabet of only one letter can simulate any Turing-machine. (Some people would call this deterministic finite automaton with two counters.) So our goal would be to simulate any such machine with a chess position. I can see two ways for this.

i, Build two separate configurations, such that both have a starting part and a moving part that can change (to store the state). Also, the moving parts would be connected, eg. by rooks, which could checkmate, if released, so this is why if one states moves 1, the other has to move k, and so on.

ii, Build a single configuration, that depending on its state, moves l horizontally and -k vertically. Also, place a rook at (0,0) that would never move but could guarantee that the configuration can "sense" when it gets back to an empty counter.

So all left to do is to design such configurations, which I guess should be possible with some effort and knowledge of chess. Also, note that in both cases the construction uses a piece whose range is not bounded, I wonder if this is really necessary. As a first step, I proposed to give a position equivalent to the Collatz conjecture:
https://mathoverflow.net/questions/64966/is-there-a-chess-position-equivalent-to-the-collatz-conjecture


Turing degree of Solomonoff semi-measure

Note that from $ m (0) $ you can compute a version of Chaitin's $\Omega $. Moreover $ m (x) $ is left-c.e. uniformly in $ x $. So $ m $ has Turing degree $0'$.


Complexity lower bound of finding the factorial of a number

One approach on this question, related to complexity-theoretic questions, is due to Shub and Smale [1] who proved that if $n!$ is ultimately hard to compute, then $\mathsf{VP}\neq\mathsf{VNP}$ over some field. Their model of computation is the straight-line programs: The goal is to compute $n!$ from the constant $1$, using only additions, subtractions and multiplications. That $n!$ is ultimately hard means that the number of operations needed is asymptotically not bounded by some polynomial in $\log n$.

For more recent results in this direction (and pointers to the relevant literature), you can read a paper of Cheng [2]. The paper contains also a very brief remark about the standard complexity of the problem, that has to be exponential in $\log n$ (because of the output size), and of the modular variant of it (computing $n! \bmod m$) and its relations with integer factoring.

[1] Mike Shub and Stephen Smale. On the intractability of Hilbert’s nullstellensatz and an algebraic version of “P=NP?”. Duke Math. J., 81:47–54, 1995.

[2]  Qi Cheng, On the Ultimate Complexity of Factorials, Theoretical Computer Science, Volume 326, Issues 1-3, Pages 419-429.


Uniqueness of the distribution maximizing the channel capacity

Suppose we have a binary symmetric channel:

$x_1 \rightarrow y_1$ with probability $1-\epsilon$ and $y_2$ with probability $\epsilon$,

$x_2 \rightarrow y_2$ with probability $1-\epsilon$ and $y_1$ with probability $\epsilon$.

Now add a third input $x_3$ that goes to $y_1$ and $y_2$ with probability $\frac{1}{2}$ each.

Then the optimal input probability distribution is $(\frac{1}{2}, \frac{1}{2}, 0)$.

Proof: Let $X$ be the random variable describing the input, and $Y$ be the random variable describing the output. The capacity $C = H(Y) - H(Y|X)$, where $H(Y)$ is the entropy of $Y$, and $H(Y|X)$ is the conditional entropy of $Y$ given $X$.

If you have an input distribution $(p_1, p_2, p_3)$ for $X$, you can replace it by the distribution $(p_1+p_3/2, p_2 + p_3/2, 0)$. This keeps $Y$ the same, so $H(Y)$ is unchanged, and it reduces $H(Y|X)$. Thus, capacity strictly increases.


Some useful criteria for evaluating string hashing functions are discussed here:

Performance in Practice of String Hashing Functions
Choosing Best Hashing Strategies and Hash Functions
Evaluating Hash Functions
Hash Function properties

There's an empirical comparison of some popular string hashing functions here which looks at some of the criteria you mentioned. The appropriateness of various hashes would depend on the application and data characteristics. Uniformity and efficiency are usually the major concerns.

If you know the input set in advance, you can generate a perfect hash function that is collision-free. Something like CMPH or gperf can automatically generate a PHF for a set of strings.

If the input isn't known in advance, it still might be biased toward a particular distribution that makes one hash more favorable than other. Benchmarking can be useful.

For a cryptographically secure hash, you'd want something that has good avalanche effect characteristics.

Bernstein's hash is often used in string dictionary data structure implementations, but of course there are many to choose from. (Also MurmurHash.)

I misunderstood the question - this is for integers that are word-sized. For a secure crypto hash like SHA-2, see Kaveh's comments.


Secure multiparty computation of number of 1s times number of 0s in a shared string

This answer is about feasible solutions based on homomorphic encryption that is NOT fully-homomorphic, as the latter may be extremely inefficient (if there are efficient fully homomorphic cryptosystems that are comparable with those provided below in terms of efficiency, I'd be glad to hear about them).

Since you only need one multiplication then there are solutions that are potentially less expensive than fully homomorphic encryption: [1] and [2]. The latter works on encrypted bit-decompositions of the input so it will need a bit-decomposition protocol like [3] and [6], but the former works on whole values. Just for completeness, the former has been extended to $d$-operand multiplication in [4], even though the OP may not need this. These solutions are non-interactive and should work in the two-party case.

If you have more than two parties and could afford some interaction then [5] provides a "secure multiplication gate" which is potentially more efficient and allows unbounded number of multiplications. It works basically by converting the homomorphically-encrypted values to some sort of secret-sharing, multiplies the result (interactively), then convert it back to homomorphic encryption.

[1] Evaluating 2-DNF Formulas on Ciphertexts

[2] Non-interactive cryptocomputing for NC1

[3] Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation

[4] Additively Homomorphic Encryption with d-Operand Multiplications

[5] Multiparty Computation from Threshold Homomorphic Encryption

[6] Efficient Binary Conversion for Paillier Encrypted Values


What's the complexity of counting odd nodes in graph?

Well, at least $\#\mathsf{P}$-hard. Given a SAT formula, construct a graph with two vertices, $v_x$ and $v_x'$, for every possible assignment of variables $\vec{x}$. If $x$ is a satisfying assignment for the formula, draw an edge between $v_x$ and $v_x'$; these are the only edges. It is easy to construct the circuit for this graph from the SAT formula, and the number of odd vertices is exactly twice the number of satisfying assignments.


Single-pass streaming quantile estimation using moments

Gan et al. address this in Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries. The answers are rather nuanced.


The unreasonable power of non-uniformity

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

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

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

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


How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?

There is even a stronger result than your request:

There are exponentially-ambiguous NFAs for which the minimal polynomially-ambiguous NFAs are exponentially larger, and in particular the minimal UFAs.

Check this paper by Hing Leung.


Pop desired elements on stacks of bounded capacity

Here's a simple algorithm:

We repeatedly pick a stack with a red element and execute a subroutine (to be described below) that tries to pop the topmost red element out of the stack. Either we will end up popping every red element or at some point every stack with a red element will have the subroutine failing. In the former case, it is clearly possible to pop all the red elements. In the later case, every topmost red element can't be popped, so in fact no more red elements can be popped, and so popping all the red elements is impossible.

The subroutine:

Simply pop elements out of the stack in question (pushing blue elements into other stacks) until either a red element is popped (success) or until the blue elements being popped cannot fit into the other stacks (failure).

Runtime

The subroutine requires at most $n$ operations, and the subroutine must be executed at most $k$ times in order to either conclude that a solution is impossible or to pop one red element. Since there are at most $n$ red elements. The overall runtime is $O(kn^2)$, which is polynomial in $n$ and $k$.

Correctness

Certainly if this procedure pops all the red elements then popping all the red elements is possible.

Now suppose the subroutine fails on a stack. Define the "blocking" elements in a stack to be all blue elements above the topmost red element. Subroutine failure can only happen if all the blocking elements in the stack and all the elements in all other stacks cannot fit in the other stacks. Thus, this topmost red element cannot be removed until the count of blocking elements plus elements in other stacks decreases. In other words, the topmost red element cannot be the next red element popped.

If the subroutine fails for every stack with a red element, then no red element can be the next red element popped. In other words, no remaining red element can be popped at all.

Since every operation is either reversible (moving a blue element between stacks) or purely beneficial (popping a red element), reaching a state where the subroutine fails for every stack implies that all along the problem could not be solved.


I am not sure what you are referring to when you say "this is not covered in theory in general." The specific example that you give has been studied and is called antecedent failure.

  Formally verifying a microprocessor using a simulation methodology., D. L. Beatty and R. L. Bryant, 1994

  One of the principal dangers of formal verification is what we have called antecedent failure. Formally, implications have an extensional meaning: they are also true if the antecedent condition is not true. Antecedent failure means that we can speak nonsense and not realise it.

The problem of detecting more general forms of such logical pitfalls is called vacuity detection. The introduction of the paper below has an excellent overview. You will also find examples of formulae.

  Enhanced Vacuity Detection in Linear Temporal Logic, Roy Armoni, Limor Fix, Alon Flaisher, Orna Grumberg, Nir Piterman, Andreas Tiemeyer, and Moshe Y. Vardi, 2003

There are lots of courses where people teach temporal logic and those notes and exercises have lots of examples. I would also suggest Manna and Pnueli's book for examples.


It seems your upper bound can be improved as follows: On input $x$ of length $n$, let $y_1,\dots,y_m$ be the oracle queries. Note that $|y_1|+\dots+|y_m| \leq c_1n^a$. The time to simulate the oracle machine to answer query $y_i$ is $c_2|y_i|^b$. Note now that $c_2(|y_1|^b+\dots+|y_m|^b) \leq c_2 (|y_1|+\dots+|y_m|)^b \leq c_2(c_1n^a)b = c_1c_2n^{ab}$. Thus the time to simulate the computation without the oracle is $c_1n^a + c_1c_2n^{ab} = O(n^{ab})$, which matches your lower bound.


About the small set expansion conjecture

I think the following should answer your questions, even though it's not exactly in the same order.

The original formulation of the small set expansion conjecture states that, analogously to the Unique Games Conjecture, for every $\epsilon >0$ there exists $\delta>0$ so that it is NP-hard to determine whether in a graph $G$ it's the "YES" case where there exists a $\delta$-sized set with expansion less than $\epsilon$ or it's the "NO" case where every $\delta$-sized set has expansion at least $1-\epsilon$. The paper of Raghavendra, Steuerer, and Tulsiani https://www.cs.cornell.edu/~dsteurer/papers/ssereductions.pdf showed that this is equivalent to the case where $\epsilon = O(\log (1/\delta))$ and in fact the case where in the NO case, for every $\delta' \geq \delta$, sets of size $\delta'$ have at least the same expansion as they would in the "$\epsilon$-noisy Gaussian graph" (see the paper for the precise statement).  The reason for the relation $\epsilon = O(\log (1/\delta))$ is because this is the relation between those parameters in the Gaussian noise graph. This result of Raghavendra et al can be thought of as the small-set expansion analog for the paper of Khot, Kindler, Mossell and O'Donnell who showed a similar result for unique games, giving a very precise relation between the parameters $1/\delta$ (which in the unique games setting is known as the alphabet size) and $\epsilon$.

The result you mention discussed in my lecture notes is from Section 8 in my paper with Brandao, Harrow, Kelner, Steurer and Zhou ( https://www.cs.cornell.edu/~dsteurer/papers/hypercontract.pdf ). What we show there, roughly speaking, is that a graph is a small set expander if and only if the span of eigenvectors corresponding to low eigenvalues of its Laplacian does not contain an "analytically sparse" vector.

The intuition is the following: consider the following two extremes:

1) A random vector $w$. In this case, the distribution of entries of $w$ is approximately the Gaussian distribution, and so this satisfies that $\mathbb{E}_i w_i^4 = O(\mathbb{E}_i w_i^2)^2$.

2) A vector $w$ that is the characteristic vector of a set of measure $\delta$ (i.e. it has $1$ in the coordinates belonging to the set, and $0$ in the others). In this case, $\mathbb{E}_i w_i^4 = \delta \gg \delta^2 = (\mathbb{E}_i w_i^2)^2$.

Now, roughly speaking, the subspace $W$ corresponding to eigenvalues smaller than $\epsilon$ of the Laplacian corresponds to set which have expansion at most $\epsilon$ in the graph. So, if there exists a $\delta$-sized set with such expansion then there would be a vector $w$ (namely the projection of the characteristic vector of this set to $W$) with $\mathbb{E}_i w_i^4 \gg (\mathbb{E}_i w_i^2)^2$. The other direction (which is more challenging to prove but turns out to be true) is that if there is a vector $w$ with this property then we can also find a set with $o(1)$ measure with not too good expansion.


Regarding Pfaffian Methods in Counting and Combinatorics

(This is an interesting question for me because I'm also reading about the Pfaffian.)

I suggest the following references:

Chapter 8 of the awesome book Matching Theory by Lovasz and Plummer.
The paper Division-Free Algorithms for the Determinant and the Pfaﬃan: Algebraic and Combinatorial Approaches by Rote. This paper relates the Pfaffian with the combinatorial object called alternating closed walk sequence (aka. alternating clow sequence), which gives us a dynamic (division-free) algorithm for computing the Pfaffian.
The paper Nonintersecting paths, pfaﬃans, and plane partitions by Stembridge, which shows how to use the Pfaffian to enumerate configurations in combinatorics. The paper also gives combinatorial proofs of basic identities, e.g.,

  If $A$ is a skew-symmetric matrix, then $\mathsf{pf}(A)^2 = \mathsf{det}(A)$.


Primal Dual model in the continuous domain

Your question may be answered in the following paper:

@article{strang1983maximal,
  title={Maximal flow through a domain},
  author={Strang, G.},
  journal={Mathematical Programming},
  volume={26},
  number={2},
  pages={123--143},
  year={1983},
  publisher={Springer}
}


Smallest axis-aligned box that contains $k$ points

For $n$ points there are $O(n^3)$ empty boxes, see introduction of this paper http://www.cs.uwm.edu/faculty/ad/maximal.pdf. One can compute these boxes in roughly this time (see intro for refs).

For your problem, take a random sample of points, where every point is picked with porbability $1/k$. Such a random sample has size (in expectation) $n/k$ [and for the sake of contradiction assume it is]. There are $O((n/k)^3)$ empty boxes having points from $R$ on their sides, by the above. For each such box, use an orthogonal range searching data-structure to compute how many points exactly it contains. Repeat this process $O(k^6 \log n)$ times. With high probability, one of the boxes you tried is the desired box.

Overall, the running time of this is $O((n/k)^3 * k^6 * polylog n) = O(n^3 k^3 \log^{O(1)} n )$.

To see why this work, consider the optimal box. It has 6 points of P on its boundary. The probability that the random sample pick these six points, and none of the points inside the box is at least $\frac{1}{k^6} ( 1-1/k)^{k-6} \approx 1/k^6 = p$. Thus, if you repeat the process $O( (1/p) \log n)$ times, with high probabilty one of the random samples would induce the desired box as an empty box.

Since $\Theta(n^3)$ is tight for the number of empty boxes (see intro the above paper for relevant refs), it seems unlikely that a significnatly faster algorithm is possible.

[In the ref I gave, they mention that [17] provides an algorithm that enumerates all maximal empty boxes among point in 3d in $O(n^3 \log^2 n)$ time, which is the black box you need for the above.]


Do there exists polynomial size CFG that describe this finite language?

Chomsky normal form

A CFG is in CNF (Chomsky normal form) if the only productions are of the form $A \rightarrow a$ and $A \rightarrow BC$; a grammar can be brought to CNF with only quadratic blowup.

For a grammar $G$ in CNF, we have the nice Subword Lemma:  If $G$ generates a word $w$, then for each $\ell \leq w$, there is a subword $x$ of $w$ of length $\ell/2 \leq |x| < \ell$ which is generated by some non-terminal of $G$. Proof: Descend the (binary) syntax tree, always going to the child which generates the longer subword. If you started with a subword of size at least $\ell$, you can't have gone below $\ell/2$.

 Solution

Without loss of generality, we can assume that a grammar for $L_n$ (such a language with specific $\pi_1,\pi_2 \in S_n$) is in Chomsky Normal Form. The language $L_n$ consists of the words $w(x) = x\pi_1(x)\pi_2(x)$ for all $x \in \{0,1\}^n$.

Using the Subword Lemma, for each $w(x)$ we can find a substring $s(x)$ of length $$\frac{n}{2} \leq |s(x)| < n$$ generated by some symbol $A(x)$ and occurring at position $p(x)$.

Suppose that $p(x) = p(y)$ and $A(x) = A(y)$. Since $|s(x)|<n$, the subword $s(x)$ cannot intersect both the $x$ part and the $\pi_2(x)$ part of $w(x)$; we can assume it is disjoint from the $x$ part. Thus $w(x)$ is of the form $x \alpha s(x) \beta$. This implies that $A(x)$ generates exactly one string, namely $s(x)$. Therefore $s(x) = s(y)$.

Now $s(y)$ intersects either $\pi_1(y)$ or $\pi_2(y)$ in at least $n/4$ places, and thus determines at least $n/4$ bits of $y$. Therefore at most $2^{3n/4}$ strings $y \in \{0,1\}^n$ can have $p(x) = p(y)$ and $A(x) = A(y)$. Since there are at most $3n$ possibilities for $p(y)$, we get that there are at least $$\frac{2^{n/4}}{3n}$$ different non-terminals in the grammar.

Comment: The same proof works if $\pi_1,\pi_2 \in S_{\{0,1\}^n}$, i.e. are arbitrary permutations on the set of all $n$-bit words. Given $n/4$ bits of $\pi_i(y)$, there are exactly $2^{3n/4}$ preimages $y$.

 More examples

Using the same method, one can prove that the language where each character appears exactly twice requires exponential-size CFG in the size of the alphabet. We can replace "twice" with any subset of $\mathbb{N}$ other than four trivial ones (ignoring $0$, either containing none of $\mathbb{N}_{\geq 1}$ or all of it).

I would appreciate a reference for this proof method.


Combining (block)-sensitivity and Lipschitz conditions?

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

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


Sum of Independent Exponential Random Variables

For concreteness, say that the pdf of the r.v. $X_i$ is

$$p(X_i = x) = \frac{1}{2} \lambda_i e^{-\lambda_i|x|}.$$

This is the Laplace distribution, or the double exponential distribution. Its variance is $\frac{2}{\lambda_i^2}$. The cdf is

$$
\Pr[X_i \leq x] = 1 - \frac{1}{2}e^{-\lambda_i x}
$$
for $x \geq 0$.

The moment generating function of $X_i$ is

$$
\mathbf{E}\ e^{uX_i} = \frac{1}{1 - u^2/\lambda_i^2},
$$
for $|u| < \lambda_i$. Using this fact and the exponential moment method which is standard in the proof of Chernoff bounds, you get that for $X = \sum_i X_i$ and $\sigma^2 = 2\sum_i \lambda_i^{-2}$, the following inequality holds

$$
\Pr[X > t\sigma] < e^{-t^2/4},
$$
as long as $t \leq 2\sigma \min_{i}{\lambda_i}$. You can find a detailed derivation in the proof of Lemma 2.8 of this paper.


Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)

Yes, an example is:
Accept $0^k 1^m$ iff $k>0$ and the $k$th Turing machine halts in less than $2^{m/k}$ steps on the empty input.  Other strings are rejected.  See question Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$? for the proof.

I expect that there is a relativization barrier against proving equivalence of ETH with its weakening using $2^{o(n)}$, and that there are oracles relative to which (note that this is not ETH) for every $ε>0$ every relativized NP-complete problem can be solved in time $O(2^{n^ε})$ but not in time $2^{n^{o(1)}}$.


Partition graph into 2 or more claw-free subgraphs

It is NP-hard, even for $k=2$.

This is a special case of a theorem by Farrugia (Alastair Farrugia, Vertex-partitioning into fixed additive
induced-hereditary properties is NP-hard, The electronic journal of combinatorics 11 (2004), #R46),
stating that it is NP-complete to test if the vertex set a graph can be partitioned into two subsets
A and B such that G(A) belongs to the graph class P and G(B) belongs to the graph class Q, provided
P and Q are closed under taking vertex-disjoint unions and talking induced subgraphs, and at least
one of P and Q is non-trivial (meaning not all graphs in the class are edgeless).


Computational topology encompasses an enormous body of research.  A complete summary of every complexity result would be impossible.  But to give you a small taste, let me expand on your example.

In 1911, Max Dehn posed the word problem for finitely presented groups: Given a string over the generator alphabet, does it represent the identity element?  One year later, Dehn described an algorithm for the word problem in fundamental groups of orientable surfaces; equivalently, Dehn described how to decide whether a given cycle on a given orientable surface is contractible.  Properly implemented, Dehn's algorithm runs in $O(n)$ time.  In the same 1912 paper, Dehn opined that “Solving the word problem for all groups may be as impossible as solving all mathematical problems.”

In 1950, Turing proved that the word problem in finitely presented semigroups is undecidable, by reduction from the halting problem (surprise, surprise).

Building on Turing's result, Markov proved in 1951 that every nontrivial property of finitely-presented semigroups is undecidable.  A property of groups is nontrivial if some group has the property and some other group does not.  Theoretical computer scientists know the similar result about partial functions as "Rice's Theorem".

In 1952, Novikov proved that the word problem in finitely presented groups is undecidable, thereby proving that Dehn's intuition was correct.  The same result was independently proved by Boone in 1954 and Britton in 1958.

In 1955, Adyan proved that every nontrivial property of finitely-presented groups is undecidable.  The same result was proved independently by Rabin in 1956.  (Yes, that Rabin.)

Finally, in 1958, Markov described algorithms to construct 2-dimensional cell complexes and 4-dimensional manifolds with any desired fundamental group, given the group presentation as input.  This result immediately implied that a huge number of topological problems are undecidable, including the following:

Is a given cycle in a given 2-dimensional complex contractible? (This is the word problem.)
Is a given 2-complex simply connected?  ("Is this group trivial?")
Is a given cycle in a given 4-manifold contractible?
Is a given 4-manifold contractible?
Is a given 4-manifold homeomorphic to a particular 4-manifold (constructed by Markov)?
Is a given 5-manifold homeomorphic to the 5-sphere (or any other fixed 5-manifold you choose)?
Is a given 6-complex a manifold?

My favorite corollary of these results is more recent and more subtle: It is undecidable whether a given finitely-presented group is the fundamental group of a 3-manifold.  Perelman's recent proof of Thurston's geometrization conjecture implies the existence of an algorithm to determine whether a given 3-manifold has a trivial fundamental group.  (As @SamNead points out, results of Rubenstein and Casson imply an algorithm that runs in exponential time.)  If a given group $G$ is not a 3-manifold group, then $G$ cannot be trivial, because $\pi_1(S^3)$ is trivial.  Thus, if you could decide whether $G$ is a 3-manifold group, you could decide whether $G$ is trivial, which is impossible.


Maximal non-reducible vertex cover of a graph

What you call a non-reducible vertex cover is commonly known as a minimal vertex cover. So, what you are looking for is a minimal vertex cover of maximum cardinality, i.e a maximum minimal vertex cover.

I'm not aware of any literature on this problem per se, however the equivalent Independent Dominating Set problem is quite well studied. An independent dominating set in a graph $G$ is an independent set $I$ such that every vertex not in $I$ has a neighbor in $I$. In the Independent Dominating Set problem input is a graph $G$ and the task is to find a smallest possible independent dominating set. This problem is known to be NP-complete.

The two problems are equivalent because a set $S$ is a minimal vertex cover if and only if $V(G) \setminus S$ is an independent dominating set.


Is the dual of a polyhedral embedding a polyhedral embedding?

You need to specify that $G$ is a simple graph (else the trigonal hosohedron is a counterexample) but then the answer is yes. What can go wrong? If a dual face is not a simple cycle then one of its edges is repeated, giving a self-loop in the primal, or a vertex but not an edge is repeated, in which case this face and vertex form a configuration of the same type in the primal. If two dual faces meet at more than one edge then there is a multiple adjacency in the primal. If the dual has a self-loop or multiple adjacency then we get a face with a repeated edge or two dual faces meeting at more than one edge in the primal. If two dual faces meet at two vertices but do not share an edge between these two vertices then a configuration of the same type happens in the primal. And if two dual faces meet in an edge and a third vertex then in the primal we have three faces sharing the same two vertices and they can't all three contain the edge connecting these two vertices.


Give a simple way to augment Van emde boas tree, to find/delete median in O(log log u) time

I agree with Kaveh that this looks like an exercise, but I disagree that adapting the idea of rank-augmented binary search trees is the way to solve it. And 2.5 years later there should be no issue with accidentally spoiling someone's homework assignment.

The trick is to maintain, separately from the VEB-tree, the value of the median, and the total number of elements in the tree (from which you can also calculate the rank of the median value that you're storing). Then, when you insert or delete in the VEB-tree, you can compare the changed value to the median you are storing to determine how the change affects its rank. If this change causes it to stop being the median, then the new median is only a successor or predecessor query away, and those sorts of queries are what the VEB-tree is good at.

Unlike rank-augmented binary search trees, I don't know of a good way to do more general queries for finding the kth smallest element in a VEB-tree.


Maximizing a monotone supermodular function s.t. cardinality

I think this is an example showing no kind of approximation is possible except with exponential$(k)$ value queries.

Let $f(S) = 0$ if $|S| \leq k$, otherwise $f(S) = |S| - k$. Now pick a special set $S^*$ uniformly at random from all sets of size $k$, and let $f(S^*) = 0.5$.

I'm claiming that this function is supermodular because every element initially has $0$ marginal value, then possibly $0.5$, then $1$ thereafter. So marginal value of any element only increases in a superset.

$S^*$ maximizes the function subject to a cardinality constraint of $k$, with an objective value of $0.5$.

Meanwhile any algorithm making subexponentially many value queries will be unable (except with tiny probability) to find a feasible set with nonzero value.


Why can Lambda Calculus not represent some combinators?

There are several things that one may want to do in practice and that cannot be directly expressed in the lambda calculus.

The SF calculus is an example. Its expressive power is not news; the interesting part of the paper (not shown in the slides) is the category theory behind it. The SF calculus is analogous to a lisp implementation where you allow functions to inspect the representation of their argument — so you can write things like (print (lambda (x) (+ x 2))) ⟹ "(lambda (x) (+ x 2))".

Another important example is Plotkin's parallel or. Intuitively speaking, there's a general result that states that lambda calculus is sequential: a function that takes two arguments must pick one to evaluate first. It's impossible to write a lambda term or such that (or ⊤ ⊥) ⟹ ⊤, (or ⊥ ⊤) ⟹ ⊤ and or ⊥ ⊥ ⟹ ⊥ (where ⊥ is a non-terminating term and ⊤ is a terminating term). This is known as “parallel or” because a parallel implementation could make one step of each reduction and stop whenever one of the argument terminates.

Yet another thing you can't do in the lambda calculus is input/output. You'd have to add extra primitives for it.

Of course, all these examples can be represented in the lambda calculus by adding one level of indirection, essentially representing lambda terms as data. But then the model becomes less interesting — you lose the relationship between functions in the modeled language and lambda abstractions.


I think you are asking about two different things.

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

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

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

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

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

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

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

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

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

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

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


Good examples for how to write well in TCS

In the 'Great proof outline' category, these are my favorites:

"Undirected Connectivity in Log-Space" by Omer Reingold.

"Geometry, Flows, and Graph-Partitioning Algorithms" by Sanjeev Arora, Satish Rao, and Umesh Vazirani.


Is there an array structure that allows for O(1) complexity for reverse, zip, slice etc operations?

This is not completely useless, and this sort of thing does indeed see a few niche uses, for instance when we want to access an array backwards it's faster to loop over array[n-i-1] rather than calling reverse(array) followed by a loop over array[i].

The flaw I'm seeing here is that this sort of thing will cause access times to scale with the number of times the data in the list have been fiddled with. After $k$ modifications to the data, you'll naturally take at least $O(k)$ time to access the data. If I want to perform $O(n^2)$ non-lookup list transformations I'm not going to be happy unless you flatten it back down to an array first. Changing the data from a function representation, proposed by you, to an array representation takes one access per element, so $O(nk)$ time.

How frequently should we change the representation back? If we rebuild the array after every $l$ operations on it, we need to spend $O(nl)$ time to rebuild every $l$ operations, so the amortised complexity of each operation becomes $O(n)$. The complexity of a lookup becomes $O(l)$ in the worst case. This is worse than an array representation in general.


Longest path among all pairwise shortest paths in unweighted undirected biconnected planar graphs

$l_{max}$ is called diameter of a graph.
I hope this paper will be helpful


Can strong NP-hardness really be shown using plain polytime reductions?

According to the terminology in the paper by Garey and Johnson, polynomial-time transformations are not necessarily pseudo-polynomial transformations because it may violate item (d) in Definition 4.


Existing technique to detect the clique and biclique cover the edges in a graph?

In case the input graph is bipartite, all cliques in the cover must be bicliques. Thus for bipartite graphs the problem that you are describing is the biclique partition problem. The biclique partition problem (and hence the more general problem that you describe) is NP-complete, and is NP-hard to approximate within $n^{1-\epsilon}$ for every $\epsilon>0$.

See here for more details:
P. Chalermsook, S. Heydrich, E. Holm, A. Karrenbauer:
Nearly Tight Approximability Results for Minimum Biclique Cover and Partition. In:
Proceedings of 22th Annual European Symposium on Algorithms (ESA), LNCS 8737, 2014, pp. 235-246

EDIT: Some easy combinatorial bounds: Let $opt(G)$ denote the minimum number of cliques/bicliques in an edge partition. Then $opt(G)$ is at most the chromatic number of the complement graph $\overline G$. Also, if $bp(G)$ denotes the number of bicliques in a minimum biclique edge partition of $G$, then $opt(G)\le bp(G)$.

If you are interested in implementing a solution... Whereas you cannot resort to approximations, then you can still use some preprocessing and a greedy heuristic. In a preprocessing step, you can put all twin vertices, i.e. pairs of vertices that have the same set of neighbors, into equivalence classes. For the heuristic, call a heuristic for maximum clique, and one for maximum biclique. If the number of edges in the biclique we found is larger than that of the found clique, add the biclique to the edge cover, remove all edges in the biclique, and continue with the remaining graph. Otherwise, we add the clique to the edge cover and proceed in a similar manner.


Strong Normalization of Extended Calculus of Constructions (CC with cumulative universes)

I guess this is just an extension of my comment, but I've heard Luo cite Goguen's paper The metatheory of UTT which uses typed operational semantics. I'm afraid I can't find a free online version though, and typed operational semantics doesn't exactly take all the sting from the technical hassles.

A completely different, and IMO under-appreciated paper is Sacchini & Gregoire's On Strong Normalization of the Calculus of Constructions with Type-Based Termination, which treats a system with Prop + 1 universe and natural numbers. Already a feat!

Addressing your other concerns: Weak normalization does imply consistency! I don't think it's significantly easier to prove than strong normalization, though, so usually people will go for gold and try to prove SN directly. It's a well-known conjecture that weak normalization implies strong normalization in "reasonable" theories anyways.

If you're only interested in consistency, you might try building a model of your theory directly! This seems to be quite a bit easier than normalization, and might be seen as a stepping stone if you're going to try to build a proof yourself. One reference I enjoy is  Werner and Lee Proof-irrelevant model of CC with predicative induction and judgmental equality
. I think this easily generalizes to cumulative universes. And if you think their construction is technical, imagine the full normalization proof!


Recovering the slope of a digitized line

The computational geometry approach would replace each pixel (i,j) with vertical segment (i, j+[-1/2,1/2]), take the convex hulls of the upper and lower sets of endpoints, and compute the inner common tangents -- these delimit the range of slopes that produce this digital line. This is just the geometric interpretation of the linear program that you mention in your slides.  O(n) time suffices for the LP by Meggiddo, or for the hulls and tangents by Graham-Yao.


What is the complexity of this path problem?

This problem was studied in:

Shiri Chechik, Matthew P. Johnson, Merav Parter, David Peleg: Secluded Connectivity Problems. ESA 2013: 301-312.

http://arxiv.org/pdf/1212.6176v1.pdf

They called it secluded path problem. It's indeed NP-hard, and the optimization version has no constant-factor approximation.

The motivation the authors provide is a setting where the information is sent over the path, and only the neighbors and the nodes in the path can see it. The goal is to minimize the exposure.


What does consistency mean for "computational theories" corresponding to inductive types?

With inductive types consistency is manifested as a termination property. Functions from inductive types are defined by structural recursion. How do we know they are well-defined, i.e., that they are total?

Here is an example:

Inductive nat :=
  | Z : nat
  | S : nat -> nat.

Inductive omega1 :=
  | zero : omega1
  | succ : omega1 -> omega1
  | sup  : (nat -> omega1) -> omega1.

Intuitively, omega1 consists of well-founded countable trees. Given a type A, an element a : A, a map f : A -> A and a map g : (nat -> A) -> A we can define a map F : omega1 -> A by recursion:

fix F (t : omega1) : A :=
  match t with
  | zero => a
  | succ x => f (F x)
  | sup s => g (fun n : nat => F (s n))
  end

The principle that every such F is well defined is equivalent to induction on well-founded countable trees. In terms of ordinal strength that's induction up to $\omega_1$. If you keep everything syntactic and/or computable so that you only use computable trees, you might get away with $\omega_1^{\mathrm{CK}}$, which isn't really better. Therefore, if $\omega_1$ does not exist we have a problem, and existence of $\omega_1$ is pretty strong in terms of consistency.

Concretely, suppose we came up with a new kind of inductive type I that were inhabited and it allowed us to write a non-terminating function. We could use it inhabit the empty type void by defining a non-terminating function f : I -> void. This actually happened in history. Originallly Martin-Löf proposed a type theory with Type : Type and Girard proved it to be inconsistent by simulating the Burali-Forti paradox. This gives us an idea: suppose we define a type WellOrder of all well-orders. Because well-orders themselves are well-ordered, WellOrder has an induction principle -- it is a kind of inductive type, and in fact is itself a well-order. If we now also posit that WellOrder is an element of WellOrder (by which I mean that there is wt : WellOrder which encodes WellOrder) we will hit the Burali-Forty paradox, define a non-terminating function, and inhabit False. In fact, much less is needed and is included in the standard Coq library under Pardoxes.BuralliForti_ex, see theorem Burali_Forti : False.


For any space-constructible function $f$ such that $f(n)=\omega(n)$, we have $\mathrm{NSPACE}(f(n)\log n)\nsubseteq\mathrm{SIZE}(n)$. This follows by simple brute force: you can compute the predicate

  $\exists$ a truth-table $t$ of a Boolean function in $O(\log f(n))$ variables such that ($\forall$ circuit $C$ of size $f(n)$, $C$ does not compute $t$) and ($\forall$ truth-tables $t'$ lexicographically smaller than $t$, $\exists$ a circuit of size $O(f(n))$ that computes $t'$) and $t(x)=1$

(where $x$ is the given input of length $n$) on an alternating TM with space $O(f(n)\log n)$ and $O(1)$ alternations, hence in $\mathrm{NSPACE}(O(f(n)\log n))$ by the Immerman–Szelepcsényi theorem. (The $\log n$ factor comes from the fact that a description of a circuit of size $f(n)$ takes $O(f(n)\log f(n))$ bits; we may assume $f(n)\le n^2$, thus $\log f(n)=O(\log n)$.)

The same kind of argument shows that $\mathrm{TIME}(n^{f(n)})^\mathrm{NP}\nsubseteq\mathrm{SIZE}(n)$ for any function $f(n)$ as above. However, this is really overkill. For example, it is known that oblivious $S_2^\mathrm P$ is also not contained in $\mathrm{SIZE}(n)$ (or $\mathrm{SIZE}(n^k)$ for any fixed $k$, for that matter), and it sits fairly low in the polynomial-time hierarchy, hence it is “almost” a much smaller class than $\mathrm{E^{NP}}$.


Teaching end-course material in a computational-models course

If I'm a student, I would've liked to learn more about other computational models (primarily, lambda calculus and recursive functions). More and more programming languages are incorporating functional features, and learning these subjects would give a great insight into this perspective of thinking about computation.


How to design a secret sharing scheme for matrix-like positioned participants

For an m x n matrix, you can simply create m+n independent sharings (using any n-out-of-n or m-out-of-m secret sharing scheme, such as the XOR scheme), one for each row and for each column.

Each participant will get tow shares, one for his row and one for his column. His total share size is 2s, where s is the length of the secret. Since you can't get share size less than s, this simple scheme is within a factor of 2 of the optimum.


Number of Automorphisms of a graph for graph isomorphism

Wormald has shown that if $G$ is a connected $3$-regular graph with 2n vertices then the number of automorphisms of $G$ divides $3n\cdot 2^n$. In particular this gives a non-trivial exponential upper-bound for the $3$-regular case. Maybe there are results in this line for general $k$-regular graphs.

For a lower bound, consider formula $F$ with $n$ inputs whose gates are addition $\mod k$ gates of fan-in 2.  Then using a resut of Toran one can construct a $k$-regular graph $G(F)$ with $O(k^2\cdot n)$ vertices whose automorphism group encodes all possible evaluations of $F$. This implies that the number of automorphisms of
$G(F)$ is at least $k^n$. This shows that the there is an exponential lower bound for the number of automorphisms of $k$-regular graphs in function of its number of vertices.


Big-O bounds on the k-th largest element of iid Gaussians

This is not a complete answer by any means, but just a quick estimate on $\mathbb{E}[\sum_{i=1}^k X_{[i]}]$ that is slightly better than the trivial bound of $O(k\sqrt{\log n})$. If this is your goal, I would think it is easier to go directly for it than consider any given $X_{[k]}$. Let $X_S=\sum_{i\in S} X_i$ for a subset $S\subseteq [n]$ and $Y_k=\sum_{i=1}^k X_{[i]}$. Using the same technique as in the first link,
\begin{align}
\exp(t\mathbb{E}[Y_k])&\leq \mathbb{E}[\exp(tY_k)]\\
&=\mathbb{E}\bigg[\max_{S\subseteq [n]:\vert S\vert=k}\exp(tX_S)\bigg]\\
&\leq \sum_{S\subseteq [n]:\vert S\vert=k}\mathbb{E}[\exp(tX_S)]\\
&=\sum_{S\subseteq [n]:\vert S\vert=k}\exp\bigg(\frac{kt^2}{2}\bigg)\\
&={n \choose k}\exp\bigg(\frac{kt^2}{2}\bigg).
\end{align}
Taking (natural) logarithms, we find
$$
\mathbb{E}[Y_k]\leq \frac{\log{n \choose k}}{t}+\frac{kt}{2}.
$$
Optimizing gives $t=\sqrt{\frac{2\log{n \choose k}}{k}}$ so we deduce
$$
\mathbb{E}[Y_k]\leq \sqrt{2k\log{n \choose k}}.
$$

For $k=o(n)$, it is known that $\log{n \choose k}=(1+o(1))k\log(n/k)$, so in this regime, we get
$$
\mathbb{E}[Y_k]\leq k\sqrt{2(1+o(1))\log(n/k)},
$$
which for $k=\log n$, say, is a bit better than the naive bound.

When $k=\alpha n$ for some constant $\alpha$, one instead has $\log{n \choose k}=(1+o(1))H(\alpha)n$, where $H(p)=-p\log p-(1-p)\log(1-p)$ is the entropy function. So in this regime, that would give
$$
\mathbb{E}[Y_k]\leq n\sqrt{2(1+o(1))\alpha H(\alpha)}.
$$

Lower bounds added for completeness: for linear $k$, one can get decent linear lower bounds that degrade as $\alpha\to 0$ but is tight at $\alpha=1/2$. Let $\alpha<1/2$, then by the Chernoff bound,
$$
\Pr(X_{\alpha n+1}\leq 0)\leq \exp\bigg(\frac{-(1/2-\alpha)^2n}{2}\bigg).
$$
It is known that for $i<j$, the conditional distribution of $X_{[i]}$ given $X_{[j]}=x$ is the same as the unconditional distribution of $X_{[i]}$ taken from a sample of size $j-1$ conditioned to be larger than $x$. As we are summing over all $i\leq \alpha n$ and taking expectations, we find that
$$
\mathbb{E}[\sum_{i=1}^{\alpha n} X_{[i]}\vert X_{\alpha n+1}\geq 0]\geq \mathbb{E}[\sum_{i=1}^{\alpha n} Y_i],
$$
where the $Y_i$ are normal random variables conditioned to be larger than $0$, which are known to have expectation $\sqrt{2/\pi}$. We also find that
$$
\mathbb{E}[\sum_{i=1}^{\alpha n} X_{[i]}\vert X_{\alpha n+1}\leq 0]\geq 0,
$$
as for each $x<0$, conditioning on $X_{\alpha n}=x$, by the same reasoning we are now taking expectations over a sample of size $\alpha n$ normal random variables conditioned to be at least $x$, which by symmetry of the normal distribution is at least $0$ (formally, we are using that the sum over the whole sample makes the labelling of the order statistics irrelevant). We conclude that
$$
\mathbb{E}[\sum_{i=1}^{\alpha n} X_{[i]}]\geq \bigg(1-\exp\bigg(\frac{-(1/2-\alpha)^2n}{2}\bigg)\bigg)\alpha n\sqrt{2/\pi}=(1-o(1))\alpha n \sqrt{2/\pi}.
$$
This holds for all $\alpha<1/2$, and by monotonicity of the left hand side in $\alpha$ for $\alpha<1/2$ and taking limits, we can further conclude using the upper bound in the comments
$$
\mathbb{E}[\sum_{i=1}^{n/2} X_{[i]}]=(1-o(1))n\sqrt{1/(2\pi)}.
$$

Obviously similar lower bounds hold for $k=o(n)$ but these aren't super useful as they are of vastly different order than the upper bound.

Numerical Simulations: Numerical simulations suggest that these bounds are surprisingly decent in the two regimes mentioned in the post. Note that for any $k$, the function $f(x_1,\ldots,x_n)=\sum_{i=1}^k x_{[i]}$ is Lipschitz, so by Gaussian concentration, one expects simulations to roughly approximate the expectation. For instance, for $k=\log(n)$, here is a plot of the upper bound with that of simulation, with the top curve being the naive bound of $\sqrt{2}\log(n)^{3/2}$ and the lower curve the given bound:

In the linear $k$ regime, for the few values I tried, the constant of the upper bounds seems to be off by a factor of at most $3$ (at $\alpha=1/2$, where we have computed the exact asymptotics). For instance, for $k=n/4$, the plot with the bound looks like:

The upper bounds seem pretty good for small constant $\alpha$, while the lower bounds degrade. For instance, here is $\alpha=.001$:

Here's one more plot (because I can't resist) with $k=\sqrt{n}$: Hope this helps!


Is the collapse of $PH$ known to extend downward to classes in-between its levels?

I don't have a good answer, but in the spirit of complexity, I have some answers which suggest that a good answer may be hard to come by :).

Note that the generalized version of Ladner's Theorem implies that there are infinitely many poly-time degrees strictly in between $\mathsf{\Sigma_i P}$ and any poly-time degree strictly above it. In particular, if the hierarchy collapses to the $i+1$-st level but not the $i$-th, then there are infinitely many p-degrees between $\mathsf{\Sigma_i P}$ and $\mathsf{\Sigma_{i+1} P} \cap \mathsf{\Pi_{i+1} P}=\mathsf{\Sigma_{i+1} P}$.
If I recall correctly, constructing an oracle for which $\mathsf{PH}$ looks like the arithmetic hierarchy is still an open problem. By "looks like the arithmetic hierarchy," I mean that $\mathsf{PH}$ does not collapse, and $\mathsf{\Sigma_{k} P} \cup \mathsf{\Pi_k P} \subsetneq \mathsf{\Delta_{k+1} P} = \mathsf{\Sigma_{k+1} P} \cap \mathsf{\Pi_{k+1} P}$ for all $k$. This at least suggests that the answer to your question may not be known.
Ker-I Ko gives oracles in which he separates the levels of $\mathsf{BPH}$ from those of $\mathsf{PH}$. As these two hierarchies intertwine one another, this gives you at least some information about relativizable collapses of problems between the levels of $\mathsf{PH}$.
This next reference is the wrong direction, but you might also be interested in the result and its techniques. Chang and Kadin showed that if the Boolean hierarchy (which lives entirely below the second level of $\mathsf{PH}$, but extends $\mathsf{DP}$ to a whole hierarchy) collapses to its $k$-th level then $\mathsf{PH}$ collapses to the $k$-th level of the Boolean hierarchy over $\mathsf{\Sigma_2 P}$.


How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?

[I'll answer the question as stated in the title, leaving the litany of other questions about GCT for other threads.] Proving the conjectures arising in GCT seems like it will crucially use the fact that the functions under consideration (determinant and permanent, and other related polynomials for P/poly and NP) are characterized by their symmetries.  This necessity is not a formal result, but an intuition expressed by several experts.  (Basically that in the absence of characterization by symmetries, understanding the algebraic geometry and representation theory that arises is far harder.)

This should bypass Razborov-Rudich because very few functions are characterized by their symmetries (bypassing the largeness condition in the definition of natural proofs).  Again, I have not seen a proof of this, but it is an intuition I have heard expressed by several experts.

Now, over the complex numbers, it's not clear to me that there's an analog of Razborov-Rudich.  Although most of GCT currently focuses on the complex numbers, there are analogs in the finite characteristic (promised in the forthcoming paper GCT VIII).  In finite characteristic, one might actually be able to prove a statement of the form "Very few functions are characterized by their symmetries."

[In response to Ross Snider's comment, here's an explanation of characterization by symmetries.]

First, an explanation-by-example.  For the example, define an auxiliary function $q$.  If $A$ is a permutation matrix, then $q(A)=1$ and if $A$ is diagonal, then $q(A)=det(A)$ (product of the diagonal entries).  Now, suppose $p(X)$ is a homogeneous degree $n$ polynomial in $n^2$ variables (that we think of as the entires of an $n \times n$ matrix $X$).  If $p$ has the following symmetries:

$p(X) = p(X^t)$ (transpose)
$p(AXB) = p(X)$ for all pairs of matrices $(A,B)$ such that $A$ and $B$ are each either permutation matrices or diagonal matrices and $q(A)q(B) = 1$

then $p(X)$ is a constant multiple of $perm(X)$ for all matrices $X$.  Hence we say the permanent is characterized by its symmetries.

More generally, if we have a (homogeneous) polynomial $f(x_1, ..., x_m)$ in $m$ variables, then $GL_m$ (the group of all invertible $m \times m$ matrices) acts on $f$ by $(Af)(x_1,...,x_m) = f(A^{-1}(x_1),...,A^{-1}(x_{m}))$ for $A \in GL_m$ (where we are taking the variables $x_1,...,x_m$ as a basis for the $m$-dimensional vector space on which $GL_m$ naturally acts).  The stabilizer of $f$ in $GL_m$ is the subgroup $\text{Stab}(f) = \{ A \in GL_m : Af = f\}$.  We say $f$ is characterized by its symmetries if the following holds: for any homogeneous polynomial $f'$ in $m$ variables of the same degree as $f$, if $Af' = f'$ for all $A \in \text{Stab}(f)$, then $f'$ is a constant multiple of $f$.


Minimum shortest path cover of $n$ vertices in $R^m$

Without further assumptions about the point set, the answer can be anywhere between $1$ and $n/(k+1)$.

Lower bound: Consider the 1-dimensional point set in which $v_i = 2^i$.  For every  index $i > 1$, the nearest neighbor of $v_i$ is $v_{i-1}$.  So the directed $1$-nearest-neighbor graph can be covered by a single shortest path $v_n \to v_{n-1} \to\cdots \to v_1$.
Upper bound:  Consider the 1-dimensional point set where
$$v_i = n^2 \lfloor i/(k+1) \rfloor + (i\bmod (k+1)).$$  This point set consists of $n/(k+1)$ tight clusters of $k+1$ points, with large gaps between the clusters.  The $k$ nearest neighbors of any point $v_i$ are in the same cluster as $v_i$.  Thus, the $k$-nearest-neighbor graph has $n/(k+1)$ components.  It follows that we need at least  $n/(k+1)$ shortest paths to cover the graph.


Shortest Path Algorithm for large graph but short paths

Assuming that you’re using BFS — or, more likely, a bidirectional BFS — and that you have no guiding heuristic (for an A* search or the like), what you’d probably like to optimize is the time it takes to consider the neighbors of each newly discovered node. After all, if each node has 100 000 neighbors, but there are only about 1 000 000 nodes in total, most nodes will be irrelevant (i.e., already visited) really fast.

The “normal” approach would be to have, say, adjacency lists for every node, and some global set data structure (e.g., a hash) for determining whether you’ve already seen a given node. This would keep the “already visited” checks fast, but you’d have to wade through lots of irrelevant neighbors.

One alternative would be to do it the other way around. Keep a global structure (like a linked list) that lets you iterate over the remaining relevant nodes (and remove the ones you visit), and then have a lookup-table for every node instead. If the node you’re looking at in the global list is found in the local lookup-table, you add it to your queue and remove it from the global list. That way, the number of potential nodes you’d look at would (probably) decrease quite a bit.

This approach would only help after a while, though; at least in the first iteration, it would be better to iterate over the neighbors of a given node, and to look them up in a global look-up table. You can do both, however…

For the local tables, you could use some compact (possibly perfect) hash tables that would let you efficiently check for membership, as well as iterate over the neighbors in linear time. Or, if you’d like to keep things simple (probably a good idea in this case), just keep the neighbor IDs in a sorted array, and use bisection for lookup checks.

For the global list/table you need something more, however. You’d like the structure to do several things:

Let you look up membership efficiently;
Iterate over the members in linear time (as a function of the number of remaining members);
Remove members efficiently; and
Reset the table efficiently, for running multiple searches.

I’m sure there are several ways of dealing with this, but one I’ve come up with for my current research code lets you do 1., 3. and 4. in constant time with a really small memory overhead. The structure assumes that every member is represented by an integer $0\ldots n-1$, and that you have two tables of size $n$ that can accomodate such integers; let's call these $\pi$ and $\pi^{-1}$. You can then use these to represent a permutation of the members — as well as the inverse permutation. Basically, the inverse permutation $\pi^{-1}$ is simply an array of members (answering the question “Which member is in position $k$?”), while the permutation ($\pi$) gives you the location of any given member. In addition, you store the number of remanining members, $m$.

Initially, you need to fill these two arrays so that $\pi = \pi^{-1} = \langle 0, 1, 2, \ldots, n-1\rangle$, as well as set $m=n$. To reset it, though, you only need to set $m=n$ (constant time).

Adding and removing elements only requires you to swap the given member into the position just inside/outside the “cutoff point” given by $m$ (updating both $\pi$ and $\pi^{-1}$), and then to increment or decrement $m$, as needed.

To make best use of this setup, you would only have to compare $m$ to size of the neighbor array of the current node in your BFS. Iterate over whichever is smaller, and do the lookups in the other one.


Using an interval tree and sorting results is a great solution.  It will have quite good running time.  You can add, remove, or find an interval in $O(\log n)$ time and change the depth of an interval in $O(1)$ time once you've found it.  Also, you can process an intersection query (report all intervals that overlap a given interval) in $O(\log n + m \log m)$ time, where $n$ is the total number of intervals and $m$ is the number of results.

Can you do better?  It seems clear that you can't do very much better.  Obviously, no comparison-based data structure can beat $\Omega(\log n + m)$ running time for intersection queries, so this trivial lower bound shows you are at most $\log m$ times slower than optimal.

Also, we can prove that no comparison-based data structure can beat $\Omega(\log n + m \log m)$ time for an intersection query in general, if you can change the depth of an interval in $O(1)$ time.  Consider the case $n=m$, and where all intervals overlap and should be returned.  If you could answer the intersection query faster than $O(m \log m)$ time, you could sort $m$ numbers faster than $O(m \log m)$ time, which we know is impossible for comparison-based algorithms.  (Well, more precisely, if you have $t$ arrays of length $m$, and if you knew how to answer intersection queries in $O(\log n + m)$ time and change depths in $O(1)$ time, you could sort all $t$ of those arrays in $O(m \log m + t (m + \log m)) = O(m (t+ \log m))$ time using your data structure by adding $m$ copies of the same interval, changing all their depths based on the first array, doing an intersection query, then changing all of their depths based on the second array, and so on.  However $O(m(t+\log m))$ running time is provably impossible for this task: the standard lower bound on comparison-based sorting shows that this takes $\Omega(t m \log m)$ time, and when $t$ is large enough, this is a contradiction -- e.g., when $t=m$, this would give a way to sort $m$ arrays of length $m$ in $O(m^2)$ time, when we know it actually takes $\Omega(m^2 \log m)$ time.)

So, if you want to hope for a data structure that allows intersection queries to run strictly faster than $\Theta(\log n + m \log m)$, you either need to allow changing the depth of an interval to take longer than $O(1)$ time, or you need to consider non-comparison-based data structures.

If you knew that your depths were all small integers, you could speed up this algorithm by using a faster sorting algorithm optimized for that case (e.g., counting sort).  However in practice existing sorting algorithms are already very fast so it's not clear whether this would make a big difference in practice.

So this algorithm already seems quite good, and it seems unlikely that we can beat it using comparison-based data structures.  If you want to do better, you'll have to specify a model of computation (e.g., the RAM model), but it's unclear that algorithms with a better asymptotic running time will lead to something that is faster in practice.


Is there any work done on developing difference-calculus of Turing Machines (or simpler Formal Languages)

As it turns out, there is some fascinating work done in this direction.

In particular, in 2003, Michael Howard, Jon Pincus, and Jeannette M. Wing's Measuring Relative Attack Surfaces in proceedings of Workshop on Advanced Developments in Software and Systems Security, Taipei, December 2003.

Further work by the same authors over the years is quite interesting ... For anyone who found my question of interest you can check their work out at http://www.cs.cmu.edu/~pratyus/as.html ... And if you find them interesting, i hope that you will find my work interesting too :)


Seeking for a game for modelling a problem using game thoery

The game you're describing is a continuous-time principal-agent problem. See A continuous-time version of the principal-agent problem (Sannikov 2008). Technically the goal there is to induce optimal effort from the employee, but, by the revelation principal, that's equivalent to having him reveal his private information.


Does this pairwise independent random process have expected max load $\sqrt{n}$?

The hash family you give has expected max load $\tilde{O}(n^{1/3})$, as shown in this recent paper:

Mathias Bæk Tejs Knudsen, "Linear Hashing is Awesome"


Need a good overview for Succinct Data Structure algorithms

I assume that you are interested in succinct external memory data structures that are efficient in practice. In that case, you can probably get what you want with a few basic techniques and some engineering.

For trees, I would start with reading Arroyuelo et al.: Succinct Trees in Practice. The paper deals with trees in main memory, but most of the techniques can be used in external memory with similar choices as below.

As for your second question, the most important choice is deciding which encoding you use for the items. Given the distribution you describe, I would first try using $\gamma$-codes or $\delta$-codes. When you have chosen the encoding, the next step is to encode the array in blocks of size $B$, where the block size is chosen so that random disk reads of size $B$ are efficient in practice.

To find the correct block quickly, you need a rank dictionary that resides in main memory. Assuming that you have $n$ items, you build a binary sequence $S$ of length $n$, where $S[i] = 1$ iff item $i$ starts a new block. Gap encoding compresses the sequence well; Gupta et al.: Compressed data structures: dictionaries and data-aware measures gives one example of such index. If you want to find item $j$, then you need to retrieve block $rank(j)$ and decode it to get the item.

If you want to keep the rank index small, you have to make the block size quite large (probably kilobytes or tens of kilobytes), making the above basic solution CPU-intensive. This can be solved by adding a little overhead to the blocks stored on disk. Basically you apply the same solution recursively, so that each disk block stores a number of small blocks as well as another rank index. When you have retrieved the correct disc block, you use the rank index within it to find the right small block to decode, instead of decoding the entire block. With this secondary index, random accesses probably become I/O-bound even with the fastest solid-state drives available.


Drawing graphs of bounded crossing number

If a graph has bounded crossing number it can be drawn with that number of crossings in the polyline model (i.e. each edge is a polygonal chain, much more common in the graph drawing literature than bounded-degree algebraic curves) with a bounded number of bends per edge. It's also true more generally if there is a bounded number of crossings per edge. To see this, just planarize the graph (replace each crossing by a vertex) and then apply Fáry.

Now, to use this to answer your actual question, what you need to do is to find an algebraic curve that is arbitrarily close to a given polyline, with degree bounded by a function of the number of polyline bends. This can also be done, fairly easily. For instance: for each segment $s_i$ of the polyline, let $e_i$ be an ellipse with high eccentricity that is very close to $s_i$, and let $p_i$ be a quadratic polynomial that is positive outside $e_i$ and negative inside $e_i$. Let your overall polynomial take the form $p=\epsilon-\prod_i p_i$ where $\epsilon$ is a small positive real number. Then one component of the curve $p=0$ will lie a little outside the union of the ellipses and can be used to substitute for the polyline; its degree will be twice the number of ellipses, which is linear in the number of crossings per edge.


I don't have a specific recommendation for your reading list, but I want to alert you to the excellent survey on "Rewrite Systems" by Dershowitz and Jouannaud in Handbook of Theoretical Computer Science, volume B.


How hard is it to count the number of factors of an integer?

This isn't my answer, but Terrence Tao gave a beautiful answer to this question on MathOverflow.

Here are the first few lines of his answer. To read the complete answer, follow the link.

  There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n completely. So the counting-prime-factors problem is believed to have comparable difficulty to factoring itself.

(I wasn't sure whether this should be an answer or a comment. But it is really an answer, although it isn't written by me. I've made the answer Community Wiki so that it may be upvoted or accepted without unnecessarily giving me reputation.)


Alternating tree automata for arbitrary arity tree

An alternating tree automaton for arbitrary degree trees has a transition function of the following type:
$$\delta:Q\times \Sigma\times D\to {\cal B}(\mathbb{N}\times Q)$$ where ${\cal B}$ is the set of Boolean functions over the given set.

This has a limitation that $\delta(q,\sigma,d)$ only outputs values between $1,...,d$ (so it fits the degree of the tree).

Thus, the transition function is defined separately for each degree, so it's effectively a family of automata. In particular, this means that if you want to handle arbitrary degrees, you need an infinite description (or a finite description of an infinite object). While this is mathematically possible, it can of course make things undecidable, if (for example) your transition function is given by a TM.

In your example, you can clearly construct such an automaton, since you can construct one for every degree.


Yes. Stack heights.  $\mathsf{SAC^1} = \mathsf{NAuxPDA}(\log n, \log n)$, that is, with $O(\log n)$ space and $O(\log n)$ stack height; this implies $\log n$ configurations and therefore $\log^2(n)$ bits.  We have

$$\mathsf{SAC^k} = \mathsf{NAuxPDA}(\log n, \log^k n);$$

these machines will run in time $2^{\log^{k}(n)}$.  Without restriction on stack height, we will get exactly $\mathsf{P}$.  The result should follow from: W. Ruzzo, Tree-size bounded alternation. JCSS 1980.


Costs of performing approx. nearest neighbor search in a skip quadtree

Like David, I don't know why Jonathan put in that remark about the 2^d pointers. They are not needed. As David mentioned above, the essential property is that when we are doing a point location to a leaf v in Q_0, it is sufficient to remember the sibling nodes (and their boxes) in the skip quadtree. When we process a box from P, we do a point location for the leaf box closest to our query point, inserting the sibling boxes as we go down. It sounds like this would be more or less the same as your answer. In addition, this procedure is very similar, for instance, to how approximate point location is done in the following paper:
Arya, Sunil and Mount, David M. and Netanyahu, Nathan S. and Silverman, Ruth and Wu, Angela Y., "An optimal algorithm for approximate nearest neighbor searching fixed dimensions", JACM, 1998.
Indeed, the skip quadtree (without those extra pointers) satisfies their conditions (a)-(e) that allow for fast approximate nearest-neighbor searching.


In order to reason about inductively defined objects (numbers, lists, trees...), one needs to use induction, or some principle that is at least as powerful as induction.

But explicit induction rules cause huge difficulties for automatic proof search, because they typically force you to invent the necessary induction schema and induction hypotheses at the beginning of the proof.  For some discussion of these difficulties, see this paper by Bundy.

Cyclic proof is an alternative to explicit induction; that is, instead of using a standard proof system with explicit induction rules, one can use a cyclic proof system without explicit induction rules.  This allows a somewhat more exploratory approach to proof search, where the induction argument is essentially created implicitly through the discovery of a cyclic proof. See this paper for a comparison between cyclic and non-cyclic proofs (for first-order logic with inductive predicates).


Can we design our own `if` clause in Normal Order evaluation

To answer your question we need some machinery and concepts from the theory of programming languages, so that we can actually make your question well posed, and then answer it.

You are asking whether two pieces of code are observationally equivalent.

It is usually quite hard to determine observational equivalence with direct methods (and the sort of arguments you attempted will not work). A common one is to use adequate denotational semantics. Adequacy means: "If $p$ and $q$ have the same denotation then they are observationally equivalent".

In your case, the traditional domain-theoretic denotational semantics, for instance using $\omega$-cpos, will do the job. In the denotational semantics the difference between the two evaluation orders is manifested by the fact that in the applicative order (also known as call-by-value) every function is strict (it maps the bottom element to the bottom element), while under the normal order evaluation (also known as call-by-name) one may define non-strict function.

First method

A simple calculation shows that for the call-by-name semantics the denotation of if is a map $f : \{0,1,\bot\} \times D \times D \to D$, where $D$ is a domain, defined by
$$f(b,x,y) =
\begin{cases}
\bot & \text{if $b = \bot$}\\
x & \text{if $b = 0$}\\
y & \text{if $b = 1$}
\end{cases}
$$
while the denotation of if-new is exactly the same. Because denotational semantics is adequate, we may conclude that if and if-new are observationally equivalent.

It is instructive to see what the denotation is for the strict semantics (applicative order). The semantics of if remains the same, while the semantics of if-new is a map $g : \{0,1,\bot\} \times D \times D \to D$, where $D$ is a domain, defined by
$$g(b,x,y) =
\begin{cases}
\bot & \text{if $b = \bot$ or $x = \bot$ or $y = \bot$}\\
x & \text{if $b = 0$}\\
y & \text{if $b = 1$}
\end{cases}
$$
This is not sufficient to conclude that if and if-new are observationally inequivalent (because the denotational semantics is not fully abstract), but you already gave a specific example which shows that they are different under applicative order.

Second method

The first method is an application of the general rule that denotationally equal programs are observationally equal. It requires us to always deal with domain theory. Another method is to derive useful general laws that we can then use to argue about observational equivalence. In your case we need the law of $\beta$-equivalence, which says that
((lambda (x) e1) e2) is observationally equal to e1 with e2 substituted for x. This law does not hold under applicative order, but it does for normal order. So we may calculate:

(if-new p a b) is observationally equivalent to
((lambda (x y z) (if x y z)) p a b) is observationally equivalent to
((lambda (y z) (if p y z)) a b) is observationally equivalent to
((lambda (z) (if p a z)) b) is observationally equivalent to
(if p a b)

Caveat: I am doing all this under the assumption that we are working in a fragment of Scheme which is purely functional (no side effects other than divergence).


The standard reference for such a positive result is Piotr Indyk's paper on stable distributions:

http://people.csail.mit.edu/indyk/st-fin.ps

He shows a dimension reduction technique for $\ell_1$ where the distance between any pair of points does not increase (by more than factor $1+\epsilon$) with constant probability and distances do not decrease (by more than factor $1-\epsilon$) with high probability. The dimension of the embedding will be exponential in $1/\epsilon$.

There are probably follow up works that I'm not aware of.


reference request for construction of expanders

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

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

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


Are arithmetic circuits weaker than boolean?

The permanent would seem to qualify, at least conditionally (that is, assuming $\mathsf{VP}^0 \neq \mathsf{VNP}^0$). Note that the Boolean version of the permanent is just to decide whether a given bipartite graph has a perfect matching, which has poly-size circuits.

[Summarizing the comments below:] Despite this example being conditional, nothing more than a logarithmic gap can be expected unconditionally at the moment, since $\Omega(n \log n)$ is still the best known lower bound on general algebraic circuits. As pointed out by Stasys, this logarithmic gap is achieved by the function $\sum_{i=1}^n x_i^n$ (requires algebraic circuits of size $\Omega(n \log n)$ by Baur-Strassen), whose Boolean-ized version is just $x_1 \vee x_2 \vee \dotsb \vee x_n$.


When have we found better bounds for known algorithms?

The Union-Find algorithm, which Tarjan1 showed had complexity $n \alpha(n)$, where $\alpha(n)$ is the inverse Ackermann function, had been analyzed previously by several people. According to Wikipedia, it was invented by Galler and Fischer2, but this seems to be incorrect, as they did not have all the components of the algorithm needed to make it run that quickly.

Based on brief scans of the papers, it appears that the algorithm was invented by Hopcroft and Ullman3, who gave an (incorrect) $O(n)$ time bound. Fischer4 then found the mistake in the proof and gave an $O(n \log\log n)$ time bound. Next, Hopcroft and Ullman5 gave an $O(n \log
^*n)$ time bound, after which Tarjan1 found the (optimal) $O(n \alpha(n))$ time bound.

1 R.E. Tarjan, "Efficiency of a good but not linear set union algorithm" (1975).
2 B.S. Galler and M.J. Fischer, "An improved equivalence algorithm" (1964).
3 J.E. Hopcroft and J.D. Ullman, "A linear list merging algorithm" (1971).
4 M.J. Fischer, "Efficiency of equivalence algorithms" (1972).
5 J.E. Hopcroft and J.D. Ullman, "Set-merging algorithms" (1973).