The Relationship between P^NP and the Permanent In the lecture notes Introduction to Complexity Theory by Goldreich, there is a section called "How close is $\#P$ is to $NP$". It is stated there that a $P^{NP}$ machine would approximate $\#P$ in random polynomial time. In fact I interpret this random approximation as a $FPRAS$ for any function in $\#P$.

Now in the seminal paper: M. Jerrum, A. Sinclair, and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries (JACM version), on page 31, there is an binary search algorithm which takes an $FPRAS$ for the Permanent to a $BPP$ algorithm for the Permanent.

Taking both algorithms together, this suggest that one could exponential approximation with high probability the Permanent leading to $P^{NP} \ge \#P$.

This clearly cannot be right! So the question is what mistake have I made?

My apologies if this question is stupid.

I think you misunderstood the definition of $\mathsf{FPRAS}$.

  Let $f: \Sigma^*\rightarrow Z^+$ be a
  function in $\#\mathsf{P}$. An
  algorithm $A$ is an $\mathsf{FPRAS}$
  for $f$ if for each $x\in \Sigma^*$,
  and error parameter $\epsilon >0$,
  \begin{align*} Pr[|A(x)-f(x)] \le \epsilon f(x)] \ge 3/4 \end{align*} and the running time of $A$
  is polynomial in $|x|$ and
  $1/\epsilon$.

So if you want to reduce the error to exponentially small, then the running time will also become exponential!

Note that both of the results you mentioned show that approximating counting can be done within the second level of the polytime hierarchy $\mathsf{PH}$ or so. On the other hand, $\#\mathsf{P}$ is the class of exact counting, which is widely believed to be harder than approximate counting. Otherwise, $\#\mathsf{P}$ is also contained in  $\mathsf{FP}^\mathsf{NP}$, which implies that $\mathsf{PH}$ will collapse at least to the second level.


Good examples for how to write well in TCS I was editing a student manuscript. The student remarked that it would be nice to see examples of quality writing in published work, and I realized that I couldn't really come up with good examples off the top of my head

  What are the best examples of quality mathematical writing you've seen
  ?

Rules:

I'd prefer TCS papers as far as possible. Our style is different enough from standard math papers that I think it's better to focus on TCS (also why I'm asking here and not on MO)
it would help if you mentioned what exactly you thought the paper did well. Not all exposition is good at everything - some papers have great proof outlines, some use notation really effectively and others convey intuition masterfully.
if possible, please link to the paper.

I'm hoping this can become a resource, like many of our other broad questions. I'm marking it CW for that reason.

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.


Algorithm to Bulk Delete nodes from a Treap I have a Treap, and want to bulk delete nodes in a given key range (i.e. the nodes to be deleted are consecutive nodes in an in-order walk of the tree). If I have $n$ nodes in the Treap, and $k$ nodes are to be deleted, is there an algorithm that can let me do this in $O(k + \log n)$. Or maybe provide a lower-bound proof that shows that that is impossible?

The obvious algorithm seems to be the one where the following steps are performed:

The treap is first split into 2 treaps by rotating the predecessor of the first node to be deleted to the root: $O(\log n)$
Detach the right child of the root: $O(1)$
Rotate the successor of the last node to be deleted in the detached treap and throw away the left subtree of this treap: $O(\log n)$
Meld the 2 remaining treaps: $O(\log n)$

However, I'm worried that the treap will get skewed (or will they)?

Section 2 of the original treaps paper ("Randomized Search Trees" by Aradon and Seidel), as well as the journal version of the same paper (also called "Randomized Search Trees"), explains how to split and join treaps without affecting the validity of the randomized balancing. That's all you need to bulk delete.

  In order to split a treap storing $X$ according to some $a$, simply insert an item with key $a$ and "infinite" priority.
  By the heap-order property the newly inserted item will be at the root of the new treap.
  By the in-order property the left subtree of the root will be a treap for $X_1$ and the right subtree will be a treap for $X_2$.
  In order to join the treaps of two sets $X_1$ and $X_2$ as above, simply create a dummy root whose left subtree is a treap for $X_1$ and whose right subtree is a treap for $X_2$, and perform a delete operation on the dummy root.


Problem in BPP but not known to be in RP or co-RP Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?

Moved my comment here after Suresh's request.

An example of a natural problem for which we only know algorithms that require error on both sides is the following: given three algebraic circuits, decide whether exactly two of them are identical. This comes from the fact that deciding whether two algebraic circuits are identical is in co-RP.

Reference: see the post How Many Sides to Your Error? (Dec 2, 2008) about the very same question on Lance Fortnow's blog and the comments below his post for a discussion about the naturalness of the problem.


Reference for the undefinability of modulus of continuity functional in PCF? Can someone point me to the reference for the non-definability of the modulus of continuity functional in PCF? $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\bool}{\mathsf{bool}}$

Andrej Bauer has written a very nice blog post exploring some of the issues in more detail, but I'll summarize just a bit of his post to lend some context to this question. The Baire space $B$ is the set of natural number sequences, or equivalently the set of functions from naturals to naturals $\N \to \N$. For this question, we will restrict our attention only to the streams which are computable.

Now, a function $f : B \to \bool$ is continuous if for every $xs \in B$, the value of $f(xs)$ depends only a finite number of the elements of $xs$, and it's computably continuous if we can actually compute an upper bound on how many elements of $xs$ are needed. In some models of computation, it's actually possible to write a program  $\mathsf{modulus} : (B \to \bool) \to B \to \N$ which takes a computable function on the Baire space and an element of the Baire space, and gives back the upper bound on the number of elements of the stream.

One trick for implementing this is to use local storage to record the maximum index into the stream seen:

let modulus f xs =
  let r = ref 0 in
  let ys = fun i -> (r := max i !r; xs i) in
    f ys;
    !r

Of course, the ys argument is no longer a purely functional program. My interest in this program comes from the fact that it only makes use of local store, and is therefore extensionally pure. I work on (among other things) higher-order imperative programming, and am designing type theories which could classify this as a pure function.

There are more practical examples as well, involving things like memoization and connection pooling, but I find this a particularly beautiful example.

The proof is hidden somewhere in Troelstra and van Dalen, Constructivism in mathematics, volume 2, I suppose. More likely, it can be found in Troelstra's investigations, if you can lay your hands on it.

It goes like this. Suppose we could define the modulus of continuity in typed $\lambda$-calculus with fixpoint operators. Then we could interpret it in a domain-theoretic realizaiblity model, for example in $\mathsf{PER}(\mathcal{P}\omega)$ where $\mathcal{P}\omega$ is Scott's graph model. In this model the choice principle $AC_{2,0}$ is valid. But it is known that $AC_{2,0}$ together with extensionality of functions (which holds in every realizability model) is incompatible with existence of modulus of continuity. If I get a moment, I will fill in the details later.

See also M. Escardo, T. Streicher: In domain-realizability not all functionals are continuous, published in Mathematical Logic Quarterly, volume 48, issue Supplement 1, pages 41-44, 2002.


Random functions of low degree as a real polynomial Is there a (reasonable) way to sample a uniformly random boolean function $f:\{0,1\}^n \to \{0,1\}$ whose degree as a real polynomial is at most $d$?

EDIT: Nisan and Szegedy have shown that a function of degree $d$ depends on at most $d2^d$ coordinates, so we may assume that $n \leq d2^d$. The problems as i see are the following:
1) On one hand if we pick a random boolean function on $d2^d$ coordinates, then its degree will be close to $d2^d$, much higher than $d$.
2) On the other hand, if we pick each coefficient of degree at most $d$ at random, then the function will not be boolean.

So the question is: is there a way to sample a low degree boolean function that avoids these two problems?

Here's an algorithm that beats the trivial attempts.

The following is a known fact (Exercise 1.12 in O'Donnell's book) : If $f:\{-1,1\}^n\to\{-1,1\}$ is a Boolean function which has degree $\le d$ as a polynomial, then every Fourier coefficient of $f$, $\hat{f}(S)$ is an integer multiple of $2^{-d}$.
Using Cauchy-Schwarz and Parseval one gets that there are at most $4^d$ nonzero Fourier coefficients and $\sum_{S}{|\hat{f}(S)|}\le 2^{d}$.

This suggests a sampling method -

Choose random non-negative integers $a_S$ for all sets $S\subseteq[n]$ of size at most $d$, which sum up to $\le 4^d$.
Let $f(x) = \sum_{S}{\frac{a_S}{2^d} \chi_S(x)}$.
Verify that $f$ is Boolean. If so, return $f$. Else, go back to $1$.

Note that for every degree $\le d$ polynomial $f$ exactly one choice of random integers in Step 1 will generate the polynomial $f$. The probability of getting a specific degree $\le d$ polynomial is
$$1/\binom{\binom{n}{\le d}+4^d}{4^d} =1/O(n/d)^{d4^d}.$$
Hence, we need to repeat this process at most $O(n/d)^{d4^d}$ times, in expectation, before halting.

It remains to show how to perform step 3. One can define $A = \bigcup\{S:a_S\neq 0\}$. Check that $|A| \le d 2^d$ (which should hold by Nisan-Szegedy for every Boolean function) and then evaluate $f$ on all possible assignments to the variables in $A$. This can be done in time $2^{d 2^d}$.
Gur and Tamuz offer a much faster randomized algorithm for this task, however since this part doesn't dominate the time complexity this is enough.

Overall the algorithm produces a random sample of a degree $\le d$ polynomial in time $O(\frac{n}{d})^{d4^d}$.
Under the assumption that $n \le d2^d$ the time complexity is $2^{O(d^2 4^d)}$.

This is not a polynomial time sampling algorithm, although it is much faster then sampling a completely random function (in which case the probability of getting a specific degree $\le d$ polynomial is $1/2^{2^n}$).


What are the theoretical limits of the Stratego Programming Language? Stratego is a programming transformation language/Rewriting DSL.

Anthony Sloane has done some work doing an implementation that runs on Scala.

What are the theoretical limits of Stratego as a functional language? (regardless of implementation). Could one write an applicative order ycombinator in Stratego?

I'll have a go at the answer, though I do not have a concrete program for you to try. In one Eelco Visser blog entry you can see a screen shot containing essentially the lambda calculus encoded in Stratego (I'm sure this code is available elsewhere). He presents an interpreter for the lambda calculus in Stratego. Presumably, this is sufficient to show that Stratego is Turing-complete.

If you are interested in a more specific notion of expressiveness, then I suggest that you rephrase your question.

In terms of practical usage, I found Stratego's main limitation that it operated over only one data structure, namely, the tree being transformed. Using other data structures such as a table of symbols was unnatural (at least in Stratego from 5+ years ago). Even though Stratego is ideal for transformations on a single tree, performing operations on two trees simultaneously is not easy.


Can reversible computations alone be used to create a computer? We are able to perform universal computations with the reversible model. Basically, during the computations, no information should be erased, so that no involved entropy increase would occur.

Are reversible computations alone sufficient to create a complete computer? The machine should be able to:

load programs,
handle user input,
provide an output.

I suspect that, for example reading user's input requires information deletion which cannot be avoided.

You need workspace (registers set to 0) to read the user's input. Once you've read it, and completed the program, the user needs to erase the input and the output in order to restore the workspace. However, if you assume that the user wants to keep a copy of the input and the output, this is possible to do reversibly.

Similarly for the program, to erase the program from the computer there needs to be another copy stored somewhere.

If you don't allow any reversible operations between the user and the computer, and you insist that everything be done reversibly, then you can't load input into the computer, and you have a useless machine.


What is the application of combinatorial game theory I find Combinatorial Game Theory very interesting as my primary interest is mathematics. My question is why do Computer Scientists (who tend to have a more practical approach) study it as well? Are there some applications of it? This question is similar to this one but I am asking about combinatorial games such as nim. Could someone provide me with a reference?

I think Kaveh's comment is the correct answer: applications? We don't need no applications.

But despite all that, combinatorial game theory does appear to have some applications in error correcting codes. See Conway and Sloane, "Lexicographic codes: Error-correcting codes from game theory", IEEE Trans. Inf. Th. 1986.

More simply, if you are willing to think of nim-addition (bitwise exclusive or) as something that came out of combinatorial game theory, then there are plenty of applications, for instance in tabulation hashing, or as one of the components of Schieber and Vishkin's lowest common ancestors data structure, or as one of the components of some block cipher systems.


Where can I seek help when I cannot understand a research paper? Where can I seek help when I cannot understand a research paper? Instead of emailing the author since the paper is long time ago, I am preferring some discussion forum that people exchange ideas on the paper.

I am not a student in university so I cannot ask my professor but a software engineer in the industry.

There are a couple options within this site alone, and a couple other options that I’ve heard people having success with.

First of all, there have been several excellent answers on different stack exchanges about how to read papers in general, such as how to read a mathematics paper, how to take notes on research papers, how to remember what you read, and how to choose what to read.

Second of all, the stack exchange network is a great place to get answers to specific questions that you have about a paper or about reading papers.

If you have a general question about reading an academic paper that can be answered without reference to the paper, that will be on-topic on Academia SE.

If you have a specific question about the content of a paper about theoretical computer science, that can be on-topic here, at Math Overflow, and at Math SE depending on precisely what the question is. math.stackexchange is notably the only one on this list that accepts non-research level questions, so if you have a question that comes up in you’re reading that’s more foundational than research level, that’s a better place to ask it. There’s also CS SE  Which doesn’t have the “research-level” requirement but I’m not sure how strong their theory participation is.

The best sorts of questions for these SEs would be a question that can be answered in one go, rather than a question that starts a conversation. For example, questions along the lines of “I don’t understand the motivation/proof/concept in [passage],” would be on-topic. If you’re ever unsure if a question is appropriate, you can ask if you can ask that question on the corresponding meta site. To access the meta, click the meta button or add go to meta.[name].stackexchange.com

All of the aforementioned sites also have a chat that you can check out, and maybe find someone who is willing to sit down and talk about a paper with you for a bit.

Finally, if your question requires significant back-and-forth then a forum is potentially a better site. There are subreddits dedicated to mathematics and computer science, and there are a number of CS-oriented blogs or blogs with substantial CS readership that have open threads that invite people to raise questions that interest them. Slatestarcodex has such threads every other week, and I believe Scott Aaronson’s blog  has them occasionally too. I’m not an avid reader of the later, but it’s quite common for people tor raise papers that interest or confuse them for discussion and explanation on SSC. You used to be able to do this on lesswrong.com as well, though that community is largely defunct now from what I understand. I’m sure there are other blogs or communities that support such activities, and you can probably find them via simply asking around at those two blogs.


Simulating quantum measurements by unitaries I have seen many papers in which quantum measurements are assumed to be replaced by unitaries. See this quotation from [KW00] for instance:

  Often we will describe quantum circuits in a high-level manner that suggests that measurements are performed at various times as the circuits are applied to some collection of qubits. In fact, as all of our circuits are assumed to be unitary, such measurements do not occur, but rather are assumed to be simulated by unitary gates as described in [AKN98].

I have read [AKN98] but it points to other papers (lemmas 1 and 4). It seems to be a standard result in quantum computing that just requires to add ancilla qubits. Could someone explain how it's done?

The basic idea here is that any operation that uses measurement can be replaced by an operation that instead CNOTs qubits onto ancillae.

Any circuit with an intermediate measurement can be converted to a circuit that only has measurement as the last step. Doing so involves performing three simple transformations again and again:

Moving measurements onto a fresh ancilla qubit.

Using fresh qubits instead of resets

Deferring measurements until later.

Once you have a circuit where all the measurements happen at the end, replace the measurements with CNOTs onto fresh ancillae and throw away the ancillae without doing anything to them (or do stuff to them, it doesn't matter).

(Note that, if you do any classical post-processing of the measurement results, that post-processing should be moved into the quantum circuit. We're taking away the mechanism by which information was reaching the classical computer.)

The resulting circuit is unitary, and a black-box drop-in for the original circuit (except for all the extra clean ancillae that must be fed in).


Is there an explanation for the difficulty of proving quadratic lower bounds for interesting NP problems? This is a follow up to my previous question:

Best known deterministic time complexity lower bound for a natural problem in NP

I find it bewildering that we haven't been able to prove any quadratic deterministic time lower bound for any interesting NP problem that people care about and try to design better algorithms for. Our Exponential Time Hypothesis conjecture states that SAT cannot be solved in subexponential deterministic time, yet we cannot even prove SAT (or any other interesting NP problem) requires quadratic time!

I know interesting is somewhat subjective and vague. I don't have a definition. But let me try to describe what I consider to be an interesting problem:
I am talking about problems which more than a few people find interesting. I am not talking about isolated problems mainly designed to answer some theoretical question. If people are not trying to find faster algorithms for a problem then it is an indication that the problem is not that interesting.
If you want concrete examples of interesting problems consider the problems in Karp's 1972 paper or in Garey and Johnson 1979 (most of them).

  Is there any explanation for why we haven't been able to prove any quadratic deterministic time lower bound for any interesting NP problem?

Here is an explanation from Lipton's blog: Bait and Switch: Why Are Lower Bounds so Hard?

As Grochow observed, Rudich's insight applies equally well to $n^2$ lower bounds as to super-polynomial lower bounds.

Rudich's insight explains why any lower bound proof that it is based on the following method cannot work.

  "any computation that computes $f$ must make slow progress toward $f$. Each computational step can only get you a little bit closer to the final goal, thus the computation will take many steps."

Basically, there is no measure of progress that can survive the Bait and Switch trick of Rudich and successfully leads to a lower bound.


What bound can we get using $k$-th moment inequality under 3-wise independence? Let $X_1,\dots, X_n$ be 0-1 random variables, which are $3$-wise independent. We want to give a upper bound to $\Pr(|\Sigma_iX_i-\mu|\geq t)$. Can we get better bound than $\Theta\left(\frac{1}t\right)$ derived by Chebyshev's inequality?

If we get a little more information, say $4$-wise independence, then we can use the $4$-th moment to get a $\Theta\left(\frac{1}{t^2}\right)$ bound. Let $Y_i = X_i - \mu$ , $Y = \Sigma_iY_i$,
$$\Pr(|Y|\geq t) = \Pr(Y^4\geq t^4) \leq\frac{\mathbb{E}(Y^4)}{t^4}=\frac{t\mathbb{E}(Y_1^4)+3\cdot t\cdot (t-1)\mathbb{E}(Y_1^2)}{t^4}=\Theta\left(\frac{1}{t^2}\right).$$

If we only have $3$-wise independence, the numerator in the RHS will be $$t\mathbb{E}(Y_1^4)+3\cdot t\cdot (t-1)\mathbb{E}(Y_1^2)+24\cdot\sum_{i<j<k<l}\mathbb{E}(Y_iY_jY_kY_l).$$ I don't know how to deal with the summation.

I guess the answer may lie around $\Theta\left(\frac{1}{t^{1.5}}\right)$?

I guess that the number of random variables $t$ and the threshold $t$ are different parameters, as otherwise $\Pr[|Y| \geq t] = 0$.

Let $a_1, \dots, a_k, b_1, \dots, b_k\in_U \{\pm 1\}$ be iid random variables sampled uniformly at random from $\{\pm 1\}$ and $n=2^k$. Consider random variables $W_1,\dots, W_n$ of the form $c_1 \cdot c_2\cdot \dots \cdot c_k$ where each $c_i$ is either equal to $a_i$ or $b_i$ (e.g., one of random variables $W_i$ equals $a_1b_2b_3a_4b_5  \dots a_k$). We defined $n$ random variables $W_i$; note that they are $3$-wise independent.

Let $X_i = (W_i+1)/2$.
Then $X_i\in\{0,1\}$ and ${\mathbb E}[X_i] = 1/2$. Let $t=n/2$. We have,
$$\Pr(|\sum X_i - n/2| \geq t) = \Pr(|\sum W_i| \geq n) = \Pr(|\prod_{i=1}^k(a_i+b_i)| \geq n) = \Pr(a_i+b_i\neq 0 \text{ for every }i) = \frac{1}{2^k} = \frac{1}{2t}.$$
Here, we used that $\prod_{i=1}^k(a_i+b_i)$ equals $0$ if $a_i+b_i=0$ for some $i$, and equals $-n$ or $n$, otherwise.

Answer: in general, we cannot obtain a stronger upper bound than $O(1/t)$.

Update: here is an explanation why $W_1,\dots, W_n$ and consequently $X_1,\dots, X_n$ are 3-wise independent. Each of the words $W_i$ is encoded by a word of length $k$: the $r$-th letter in the word is $a$ if $c_r=a_r$ in the definition of $W_i$, and $b$, if $c_r=b_r$. Consider three random variables $W_i$, $W_j$ and $W_k$. Consider the corresponding words; denote them by $I$, $J$ and $K$. Let $r_1$ be the first position where they differ. Without loss of generality $I_{r_1} = a$, $J_{r_1} = b$, and $K_{r_1} = b$. Then let $r_2$ be the first position where $J$ and $K$ differ. WLOG, $J_{r_2} = a$ and $K_{r_2} = b$. Write $W_i = a_{r_1} \cdot W'_i$, $W_j = a_{r_2}\cdot W_j'$ and $W_k = b_{r_2}\cdot W_k'$. Note that $W_j$ and $W_k$ are independent since for $x,y\in\{\pm 1\}$, we have
$$\Pr(W_j = x, W_k = y) = \Pr(a_{r_2} = (x/W_j'), b_{r_2} = (y/W_k')) = 1/4.$$
Now we prove that $W_i$, $W_j$, and $W_k$ are independent. For  $x,y,z\in\{\pm 1\}$, we have
$$\Pr(W_i = x, W_j = y, W_k = z) = \frac{1}{4}\Pr(W_i = x| W_j = y, W_k = z) =
\frac{1}{4}\cdot \Pr(a_{r_1} = (x/W'_i)| W_j = y, W_k = z) =  \frac{1}{4}\cdot \frac{1}{2} = \frac{1}{8}.$$


straight-line simulatability Does any body know any good reference for meaning of straight-line simulatability?
I am currently deep into Universal Composability (UC) framework of Canetti but I can't find any good reference for meaning of straight-line simulatability.
Any help is appreciated.

Here, "straight-line" is contrasted with "rewinding". A simulator is "straight-line" if it does not "rewind" the party it is doing the simulation for.

For instance, in a zero-knowledge protocol, the simulator usually rewinds the "verifier". In the "straight-line" sense, this rewinding does not happen.

I first saw the term "straight-line simulator" in Rafael Pass's paper (On Deniabililty in the Common Reference String and Random Oracle Models. (CRYPTO'03)) and M.Sc. thesis (Alternative Variants of Zero-Knowledge Proofs).

Edit: I found an earlier paper: Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints by Cynthia Dwork and Amit Sahai, which dates back to 1998. For more pointers, see Alon Rosen's comment below.


What is the theoretical basis of imperative programming? Functional programming has a theoretical basis in lambda calculus and combinatory logic.  As someone involved with statistical computing, I find these concepts to be very useful for modeling.

Is there an equivalent mathematical basis of imperative programming, or did it simply grow out of practical hardware application in machine language and the subsequent development of FORTRAN?

In general, when mathematics is used to study some X, one first needs a model of X, and then develops a theory, a set of results about that model. I guess that theory may be said to be a "theoretical basis" for X. Now set X=computation. There are many models of computation, many involving "state". Each model has its own "theory" and it is sometimes possible to "translate" between models. I believe it's hard to say which model is more "basic"---they are simply designed with different goals in mind.

Turing machines were designed to define what is computable. So they make a good model if you care about whether there exists an algorithm for a certain problem. This model is sometimes abused to study the efficiency of algorithms or the hardness of problems, under the pretext that it's good enough, at least if you only care about polynomial/non-polynomial. The RAM model is closer to a real computer and therefore better if you want a precise analysis of an algorithm. To put lower bounds on the hardness of problems it is better to not use a model that resembles too much today's computers because you want to cover a wide range of possible computers, while still being more precise than just polynomial/non-polynomial. In this context, I saw for example the cell-probe model used.

If you care about correctness, then still other models are useful. Here you have operational semantics (which I'd say is the analogue of lambda calculus for statefull computations), axiomatic semantics (developed in 1969 by Hoare based on Floyd's inductive assertions from 1967, which are popularized by Knuth in The Art of Computer Programming, volume 1), and others.

To summarize, I think you are after models of computation. There are many such models, developed with various goals in minds, and many have state, so they correspond to imperative programming. If you want to know if something can be computed, then look at Turing machines. If you care about efficiency look at RAM models. If you care about correctness look at models that end in "semantics", such as operational semantics.

Finally, let me mention that there is a big book online only about Models of Computation by John Savage. It is mostly about efficiency. For the correctness part I recommend you start with the classic papers of Floyd (1967), Hoare (1969), Dijkstra (1975), and Plotkin (1981). They are all pretty cool.


Fast algorithm for linear context finding I am trying to figure out a quick algorithm which solves the following problem.

For the rest of this question, assume $0\in\mathbb{N}$.

Denote by $\mathbb{R}^\mathbb{N}$ the set of all real sequences and by $\mathbb{N}^\mathbb{N}$ the set of all natural sequences. The algorithm should emulate a function $F:\mathbb{R}^\mathbb{N}\to\mathbb{N}^\mathbb{N}$ which can be defined as follows: given a real sequence $\{x_n\}$, $F(\{x_n\}) = \{y_n\}$, where $y_n$ is the maximum natural number for which both $y_n\le n$ and $x_{n-i} < x_n$ for all $0<i\le y_n$.

The emulation is of the following sense: the algorithm should receive floats, one by one, and for the float $x_n$ return the integer $y_n$. By quick I mean of linear speed. The naive algorithm is $O(n^2)$.

Note: there is a similar (?) algorithm which for a given positive integer $n$, receives a sequence of floats and returns for each the maximal value among the last $n$ received values, which is linear.

You can solve this in $O(n \lg^2 n)$ time.

Build a (balanced) binary tree with $n$ nodes, where the leaves are annotated with the values $x_1,x_2,\dots,x_n$, and $x_i$ is placed on the $i$th leaf from the left.  Annotate each internal node $v$ in the tree with the maximum value over all the leaves in the subtree rooted at $v$.  For instance, the root is annotated with $\max(x_1,x_2,\dots,x_n)$.  The tree and the annotations can be built in $O(n)$ time.

Next, note that, for any $j,k$, a sequence $x_j, x_{j+1}, \dots, x_k$ of consecutive leaves can be covered by some union of $O(\lg n)$ subtrees.  In particular, given any $j,k$, we can compute $\max(x_j,x_{j+1},\dots,x_k)$ in $O(\lg n)$ time, by traversing the tree and using the annotations on the internal nodes at the top of those $O(\lg n)$ subtrees.

Now, to compute $y_k$, we do a binary search to find the largest $j$ such that $\max(x_j,x_{j+1},\dots,x_{k-1})<x_k$ but $\max(x_{j-1},x_j,x_{j+1},\dots,x_{k-1})\ge x_k$.  Each iteration of the binary search takes $O(\lg n)$ time, and the binary search takes at most $O(\lg n)$ iterations, so this allows us to compute each $y_k$ in $O(\lg^2 n)$ time.

Finally, there are $n$ $y$-values that we want to compute, so the total running time is $O(n \lg^2 n)$.

This can be adjusted to work in an incremental/online/streaming fashion, with $O(\lg^2 n)$ running time per value of $x$ received, by tweaking the structure of the binary tree appropriately.

It's possible you might be able to get a slightly better solution by using 2-D range trees, where you store the $n$ points $(i,x_i)$ in the tree (for $i=1,2,\dots,n$).  However, I'm not certain.


Growth rate of primitive recursive functions Pardon me for asking a question whose answer is surely well-known, but
is beyond my expertise:

  Q. Is the growth rate of each primitive recursive function $f(n)$ bounded by some exponential $O(c^n)$, or $O(n^n)$, or ...?

I know Ackermann's function grows faster than exponential, but it is not primitive recursive.

The answer is no, there is no exponential bound on PR.
PR contains Knuth's up-arrow functions, Elementary functions, etc.
PR is equal to the union of Grzegorczyk hierarchy.
Exponential functions appear at the third level of the Grzegorczyk hierarchy.

PR can alternatively be defined using the iteration function in place of recursion.

A good reference for information about these classes is the first chapter of second volume of "Classical Recursion Theory".

Also have the general function growth hierarchies like
Grzegorczyk hierarchy,
slow-growing hierarchy, and
fast-growing hierarchy.


Are there any public synchronous discussion forums (slack, discord, etc.) for TCS I'm a 2nd year masters student studying theoretical CS (algorithms to be precise). I would like to know if there are any public synchronous discussion groups (slack, discord, etc.) for TCS. CSTheory StackExchange works well when someone has a specific question/query, but I felt it would be awesome to have an online forum for people interested in TCS to discuss about various developments of the field and also talk about interesting papers and concepts.

If enough people are interested we could create one in discord.

EDIT 1

As we have gained enough traction, I would like to know your opinions on how to proceed further. Some questions on top of my mind -

How should it be structured and what is the scope of the discussion
As I'm still an amateur, I would need some guidance from mods on how to go about this in general. And preferably some more volunteers.
Also I would like to know what platforms do the people up-voted prefer.

EDIT 2

Interested people, please fill this poll

EDIT 3

I have created a group in Zulip

CSTheory is now live at Zulip.

Thanks to everyone who participated in the above discussion and for sharing your opinion.


Weighted Metric Graph: ratio of sum of wts of edges to the wt of MST I am working on complete metric graph (V,d) where shortest distance is used as metric. The question is how large can be the ratio of the sum of weights of all edges to the weight of the MST (minimum spanning tree). Also if anyone of you can post some lecture note or paper links so that i can study these graphs.

If the weight of the MST is $W$, then the weight of all edges is $\le \binom n 2 \cdot W$, because every edge in the graph is bounded by the unique path in the MST connecting the two nodes of the edge by the triangle inequality.

This is tight: Consider a line with edge weights all being equal to $1$ and let the metric be the shortest path metric induced by this line. Then the MST is this line and has weight $n-1$, on the other hand there are $\Omega(n^2)$ pairs of nodes with a distance of $\Omega(n)$.


What is the "question" that programming language theory is trying to answer? I've been interested in various topics like Combinatory Logic, Lambda Calculus, Functional Programming for a while and have been studying them. However, unlike the "Theory of Computation" which strives to answer the question of "computability" i.e., things that can/cannot be computed with various constraints, I'm struggling to find the analog for "Theory of Programming"

Wikipedia describes it as:

  Programming language theory (PLT) is a branch of computer science that
  deals with the design, implementation, analysis, characterization, and
  classification of programming languages and their individual features.

This is like saying "everything" which isn't really specific.

The common progression of the topics is usually like so:

  Combinatory Logic > Lambda Calculus > Martin Lof Type Theory > Typed Lambda Calculus > (Something happens here) > Programming languages developed - that have very little connection with CL/$\lambda$

I can see the underlying "math" involved with CL/$\lambda$ and interesting proofs that come out as a result including the Church-Rosser theorem and that's neat. However, I'm struggling to understand the "end goal" of all this undertaking? What's the holy grail of PLT if you will? For now it seems to just be scratching an intellectual itch but I can't really cross the bridge from research/theory to anything practical.

Note: I do get it up until using the $\lambda$-calc for undecidability proofs. But beyond its applicability to "computability" I just don't get it and am having a hard time even understanding the need for research in PLT from this narrow POV. Any existing books, references that can throw light on the "big picture" of PLT?

The overall purpose of PLT is to make industrial software
engineering (in a general sense) cheaper (also in a general sense), through optimising the most
important tool (programming languages) and associated tooling
ecosystem.

Some reasons why maths is involved:

PLs are highly non-trivial, and it's not clear that  they
do the right thing without proof. The maths gives a simplified model
of real programming languages. This model lets us study real programming languages in a much simplified setting, removing (hopefully) most problems already at the model level. Real programming languages are currently mathematically intractable. In other words: lambda-calculus is the fruit-fly, the E.Coli, the spherical cow of PLT.
PLT lacks suitable empirical methods, which would be nice / better
to have, so maths is done as a substitute.
The maths is beautiful and deep.
The maths gives a simple, tried and tests research methodology, which  is  important for helping one's  PhD students graduate. Typically, some variant of e.g.:
Investigate PL feature XYZ through adding it to lambda-calculus.
Add simple types for XYZ and prove type-soundness.
Add generics for XYZ and prove type-soundness.
Prove a parametricity theorem for XYZ generics.
Add dependent types for XYZ and prove type-soundness.
Develop a partial type-inference for XYZ dependent types.
Add gradual types for XYZ and prove type-soundness.
Add contracts for XYZ.
Each of those is a paper.  You can stop if your PhD student or postdoc runs out of time.  Each of the above is interesting and will yield insight about generics, parametricity, type inference etc.  This pipeline is a great way of navigating the difficult waters of all possible programming languages. A second way of learning is implementing languages in a compiler, but that's less tractable for an individual.

Whether PLT is needed is an interesting question. Most working
programmers seem to think it's not. They are wrong: most languages developed by
working programmers without a PLT background    (e.g. Javascript, PHP)
start out terrible, and make all the mistakes that PL theorists
long learned how to avoid. If a PL developed by an amateur hits the
mainstream, PL theorists need a decade or so fixing the obvious flaws
(e.g retrofitting a static typing system, see Typescript). Let me summarise this situation:

 Every successful programming language ends up being ML! Either because
 it was designed by a PL theorist as ML from the start, or because a
 decade of painful evolution removes all the obvious flaws, leaving ML. ;-)

Aside:
This state of affairs is entirely   the fault of PLT because because most of them have no industrial programming
experience, so don't really know what the pain points of working
software engineers are. In particular, for sociological reasons, most
PL theorists think that pure functional programming in languages like
Agda is the solution to all problems, which does not stand up to scrutiny.


What is the maximal load of a "latency-bounded" Cuckoo Hash? Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time.

They use two hash functions $h_1,h_2:\mathbb K\to [n]$, where $\mathbb K$ is the set of keys, and $[n]=\{1,\ldots,n\}$ are indices of the array in which we store the data.

Whenever we wish to insert a key $k$, we first check if there is either $h_1(k)$ or $h_2(k)$ are free. Otherwise, we insert it into $h_2(k)$ by replacing the key $k'$ that was stored there. If $h_1(k')$ is free then we're done, otherwise, we replace the key that is there $k''$ which then looks for $h_2(k'')$ and so forth.

This operation may fail if there is a loop of keys trying to evict each other.

It is known that if the load of the hash table is at most half (i.e., we don't insert more than $n/2$ keys), with high probability all operations succeed.

I'm interested in the load I can use without making more than $T$ evictions for some $T\in\mathbb N$.

Clearly, smaller $T$ will allow smaller load. For example, if $T=0$ (no eviction permitted), then we cannot load more than $O(\sqrt n)$ elements without getting a colision.

  How many elements can we insert for larger $T$ so that we succeed, say, with probability 9/10?

Section 4 of the journal version of the original Cuckoo Hashing paper shows that to have insertion succeed with probability $p$, your numbers $T$, $n$, and $\epsilon$ must satisfy

$$
\frac{13}{n^2 \epsilon}
+
2(1+\epsilon)^
{1-(2T-1)/3}
<p
$$

where the two sub-tables are of size $n(1+\epsilon)$.

So for $p = 9/10$, $T=8$, and $n=1,000,000$, we get $\epsilon \approx 0.221$. The first term is basically negligible.


Sample complexity for learning Boltzmann Distribution parameters I am trying to think through the number of samples that I would need to estimate the parameters of a Boltzmann partition function to a desirable precision.
Suppose that there are $N$ possible states of the world, with the probability of state $i$ being observed equal to
$$Pr(i | \theta) = \frac{e^{-\theta_i}}{ \sum_{i=1}^N e^{-\theta_i}}.$$
I don't know what the values of $\{\theta_i\}_{i=1}^N$ are, but I can sample independent observations from the set $\{1,\dots,N\}$ of possible states of the world, distributed according to the distribution $Pr(i)$ given above.
Let's say I draw $m$ observations $X_1,...,X_m \in \{1,...,N\}$, and define  the maximum likelihood estimator
$$\widehat{\theta} = \arg \max_{\theta'}  \sum_{j=1}^m  \log Pr(X_j | \theta)$$
When $m \to \infty$, then  $\widehat{\theta} = \theta$. However, I'm not sure how many samples $m$ I would need to ensure that the estimate $\widehat{\theta}$ is probably approximately correct. That is, how large does $m$ need to be in terms of $\epsilon,N,\delta$ to ensure that   $Pr ( \| \widehat{\theta} - \theta \|_{\infty} > \epsilon ) < \delta$?

Under appropriate smoothness conditions (satisfied by the Boltzmann distribution), the maximum likelihood is asymptotically normal. Meaning: the vector $\sqrt n(\theta-\hat\theta)$ will have approximately normal distribution, with mean $0$ and covariance matrix given by the inverse Fisher matrix, see Section 9 here:
http://www.stat.cmu.edu/~larry/=stat705/Lecture9.pdf


Difference between weak duality and strong duality? For an optimization problem $(P)$ and its dual $(D)$, I have read about two concepts: Weak Duality, and strong Duality. What I don't understand is how they are different:

Weak  duality:
If $\bar{x}$ is a feasible solution to $(P)$ and $\bar{y}$ is a feasible solution to $(D)$, then:

$c^T \bar{x} \le b^T\bar{y}$
if equality holds in the above inequality, then $\bar{x}$ is an optimal solution to $(P)$ and $\bar{y}$ is an optimal solution to $(D)$.

Strong duality:
If there exists an optimal solution $x'$ for $(P)$, then there exists an optimal solution $y'$ for $(D)$ and the value of $x'$ in $(P)$ equals the value of $y'$ in $(D)$.

Are these two statements not saying the same thing? In other words, isn't the second statement (2.) in definition of Weak duality saying the same thing as strong duality?

Let's say we are given an LP $(P)$ and we find a dual $(D)$. Then can the same dual be used to deduce either strong duality or weak duality?

Weak duality is a property stating that any feasible solution to the dual problem corresponds to an upper bound on any solution to the primal problem. In contrast, strong duality states that the values of the optimal solutions to the primal problem and dual problem are always equal.
Was this helpful enough?


What are the relationships between those hypotheses in Fine-Grained Complexity Theory? Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" complexity aims to refine this qualitative distinction into a quantitative guide as to the exact time required to solve problems. More details can be found here: http://simons.berkeley.edu/programs/complexity2015

Here are some important hypotheses:

ETH: $3$-$SAT$ requires $2^{\delta n}$ time for some $ \delta > 0$.

SETH: for every $\varepsilon > 0$, there is a $k$ such that $k$-$SAT$ on $n$ variables, $m$ clauses cannot be solved in $2^{(1-\varepsilon)n}~poly~m$ time.

It is known that SETH is stronger than ETH and they both are stronger than $P \neq NP$,and both stronger than $FTP\neq W[1]$.

Four other important conjectures:

3SUM Conjecture: 3SUM on $n$ integers in $\{-n^3,…,n^3\}$ requires $n^{2-o(1)}$ time
OV Conjecture: Orthogonal vectors on $n$ vectors requires $n^{2-o(1)}$ time.
APSP Conjecture: All Pairs Shortest Path on $n$ nodes and $O(\log n)$ bit weights requires $n^{3-o(1)}$ time.
BMM Conjecture: Any "combinatorial" algorithm for Boolean matrix multiplication requires $n^{3-o(1)}$ time.

It is known that SETH implies the OV Conjecture (Ryan Willams, 2004). Besides Ryan’s proof that SETH $\implies$ OV Conjecture, there are no other reductions relating the conjectures known.

My question: Do you know other related hypotheses or conjectures in this area? What are the relationships between them?

Acknowledgement: results listed are from the slides of  Virginia Vassilevska Williams, she also gave me partial answers to this question.

Link to slides: http://theory.stanford.edu/~virgi/overview.pdf

This is a recent paper introducing Nondeterministic Strong Exponential Time Hypothesis (NSETH), which is an extension of SETH.

NSETH: For every $\epsilon >0$, there is a $k$ such that $k$-DNF-TAUT cannot be solved in nondeterministic time $2^{(1-\epsilon)n}$.

NSETH implies SETH. If NSETH is true, then some problems do not have SETH lower bounds (because they have nondeterministic algorithms faster than deterministic algorithms).

This paper also introduced Non-uniform Nondeterministic Strong Exponential Time Hypothesis (NUNSETH), a hypothesis stronger than NSETH and SETH.

NUNSETH: For every $\epsilon >0$, there is a $k$ such that $k$-DNF-TAUT cannot be recognized by nondeterministic circuit families of size $2^{(1-\epsilon)n}$.


Noisy Parity (LWE) lower bounds/hardness results Some background:

I'm interested in finding "lesser-known" lower bounds (or hardness results) for the Learning with Errors (LWE) problem, and generalizations thereof like Learning with Errors over Rings. For specific definitions, etc., here is a nice survey by Regev: http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf

The standard type of (R)LWE-style assumption is via (perhaps, quantum) reduction to the Shortest Vector Problem on (perhaps, ideal) lattices. The usual formulation of SVP is known to be NP-hard, and it's BELIEVED to be hard to approximate to small polynomial factors. (Related: It's hard to approximate CVP to within /almost-polynomial/ factors: http://dl.acm.org/citation.cfm?id=1005180.1005182 ) I've also heard it mentioned that (in terms of quantum algorithms) approximating certain lattice problems (like SVP) to small polynomial approximation factors is related to the non-Abelian hidden subgroup problem (which is believed to be hard for its own reasons), though I've never seen an explicit, formal source for this.

I'm more interested, however, in hardness results (of any type) that come as a result of the Noisy Parity problem from Learning Theory. These could be complexity class hardness results, concrete algorithmic lower bounds, sample complexity bounds, or even proof size lower bounds (e.g. Resolution). It is known (perhaps, obvious) that LWE can be viewed as a generalization of the Noisy Parity/Learning Parity with Noise (LPN) problem, which (from Googling) appears to have been used in hardness reductions in areas like coding theory and PAC learning.

From looking around myself, I've only found (mildly subexponential) UPPER BOUNDS on the LPN problem, e.g. http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf

Question:

I know LPN is BELIEVED HARD in the learning community. My question is: Why?

Is it because everyone tried really hard, but no one's found a good algorithm yet? Are there known lower bounds of the italicized variety above (or others I left out)?

If the answer is very clear-cut, a succinct summary of what's known and/or references to surveys/lecture notes would be great.

If much is unknown, the more "state-of-the-art" papers, the better. :) (Thanks ahead of time!)

The LPN problem is indeed believed to be hard, but like most problems we believe are hard, the main reason for it is that many smart people have tried to find an efficient algorithm and failed.

The best "evidence" for LPN's hardness comes from the high statistical query dimension of the parity problem.  Statistical queries capture most known learning algorithms, except for gaussian elimination (which fails whenever noise is introduced), hashing, and techniques similar to these two.  It is hard to design non statistical-query algorithms, and this is the main bottleneck.  Other evidence of LPN's hardness is its relationship to other hard problems (like LWE, SVP as you've pointed out).

For the SQ-hardness, here is the link to Kearns's ('98) paper.

For progress on the upper bounds on this problem, there are several results:

Probably the most famous is the Blum-Kalai-Wasserman ('00) result which beats the $2^N$ SQ barrier by a little, giving an algorithm that runs in time $2^{n / \log n}$. (link)
Lyubashevsky ('05) found an algorithm with worse running time $O(2^{n / \log\log n})$ but better sample complexity of $O(n^{1 + \epsilon})$. (link)
In the sparse case, where we know the parity is on $k$ variables, Grigorescu-Reyzin-Vempala ('11) gave a $\approx O(n^{0.5 k})$ algorithm, beating the $O(n^k)$ brute-force.  However, this bound decays toward $O(n^k)$ as the noise rate $\eta$ approaches $1/2$. (link)
Valiant ('12) recently gave a $\approx O(n^{0.8 k})$ algorithm for the sparse case.  This bound is stronger because it does not decay in the exponent with the noise rate (unlike the GRV result). (link)


Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite? I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically:

  Problem. For a given system of $m$ linear equations in $n$ unknowns modulo $k$, do there exist any solutions?

In the abstract to their paper Structure and importance of logspace-MOD classes on the classes ModkL,  Buntrock, Damm, Hertrampf, and Meinel claim that they  "demonstrate their significance by proving that all standard problems of linear algebra over the finite rings $\mathbb Z/k\mathbb Z$ are complete for these classes". On closer inspection, the story is more complicated. For instance, Buntrock et al. show (by a proof-sketch in an earlier and freely accessible draft found by Kaveh, thanks!) that solving systems of linear equations is instead in the complementary class coModkL, for k prime. This class is not known to be equal to ModkL for k composite, but never mind that — what I'm concerned about is the fact that they don't make any remarks about whether solving systems of linear equations mod k is even contained in coModkL for k composite!

  Question: Is solving systems of linear equations modulo k contained in coModkL for all positive k?

If you can solve systems of equations modulo a higher power q of a prime p, you can solve them modulo p as well; so solving systems of equations modulo q is coModpL-hard. If you could show that this problem is in ModqL, you would end up showing ModkL = coModkL for all k. That's likely to be difficult to prove. But is it in  coModkL?

I'm happy to say that I think we can answer this question in the affirmative: that is, deciding whether a linear congruence is feasible modulo k is coModkL-complete.

We can actually reduce this problem to the special case of prime powers. One may show that:

  Normal Form. The class coModkL consists of langauges L of the form L = Lp1 ∩ Lp2 ∩ ... ∩ Lpr , where Lpj ∈ coModpj L and where pj ranges over the prime factors of k.

By the Remainder Theorem, any solution to a system of equations modulo each of the prime powers $p_{\!j}^{e_j}$ dividing k gives rise to a solution to the same system, mod k.
So if solving systems of linear equations over $p_{\!j}^{t_j}$ is contained in coModpj L, it follows that solving systems of equations mod k is contained in coModkL.

There's a standard algorithm, described by McKenzie and Cook for reducing linear congruences modulo a prime power to constructing a spanning set for its nullspace (namely, for Ax = y over a given ring, construct a basis for the nullspace of [ A | y ] and see if any solutions exist with a final coefficient of −1); and subsequently for reducing the construction of nullspaces modulo prime powers to constructing nullspaces modulo primes, and matrix multiplication modulo prime powers. Both of the latter tasks are problems which are feasible for coModkL, provided that you can construct the matrices involved.

It turns out that the matrices involved in the reduction of McKenzie and Cook can themselves be computed by matrix multiplication, and (crucially) division by a constant factor. Fortunately, for prime powers, the coefficients of the matrices involved can be computed on the work-tape using an oracle for coModpL-machines; and the division by a constant can be performed in NC1, which is again feasible in coModpL. So it turns out that the whole problem is ultimately doable in coModkL.

For complete details, see [arxiv:1202.3949].


Applications and benchmarks for binary quadratic program algorithms I have an algorithm that on all examples I was running finds an  arbitrary approximation of global minimum of binary quadratic program. The algorithm find the minimum in polynomial time. Binary quadratic program is NP-complete, and I cannot prove theoretically, that the algorithm always finds the right solution (it always does in practice). The memory requirement for the algorithm is in current implementation $ n^8 $, where n is the dimension of the problem, it can be reduced to $ n^4 $ leading to possibility to solve the problem in about 50 dimensions, although running time is large - the algorithm have to solve the semi-definite program in $ n^4 $ dimension.

Question:  Is there any practical application this algorithm can be used? What benchmarks tests should be performed to demonstrate practical usefulness of the algorithm?

I'm not sure I'm allowed to post the link, so you can find details of the algorithm, and its python implementation though the link in my profile, or  here, if link works.

PS. I apologize if this is off topic question, I got algorithm by a complete chance, and have no idea where and how to communicate it.

PPS. I know it goes completely against the public opinion, but this is a testable objective, so give it a chance to survive, at least to the moment when it finds counterexample, or can be used as a practical application without a proof.

The Biq Mac library provides a collection of instances four your problem.


Number of binary gates needed to compute AND and OR of n input bits simultaneously What is the minimal number of binary gates needed to compute AND and OR of $n$ input bits simultaneously?
The trivial upper bound is $2n-2$. I believe that this is optimal, but how to prove this? The standard
gate elimination technique does not work here as by assigning a constant to any of the input variables
one trivializes one of the outputs.

The problem is also given as an exercise 5.12 in the book "Complexity of Boolean Functions" by Ingo Wegener
in a slightly different form: "Let $f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$. By the elimination method one
can prove only a lower bound of size $n+\Omega(1)$. Try to prove larger lower bounds."

This paper of Blum & Seysen may be useful:

N.Blum, M. Seysen. Characterization of all Optimal Networks for a Simultaneous Computation of AND and NOR. Acta Inf. 21: 171-181 (1984)

I have thought that for $x_1\dots x_n\vee \bar{x}_1\dots\bar{x}_n$ $2n-c$ lower bound can be obtained using methods of Blum & Seysen, but it seems this is not the case.


How to start studying topics Hardness of approximation and PCP's Recently I have done an introductory course on complexity theory ( which covered 90% of sipser text book). Now I would like to study the topics Hardness of approximation and PCP's. Can you please suggest me the best available sources (lecture notes or video lectures) to study these topics from the basics.

I recommend Lectures on Proof Verification and Approximation Algorithms,  E.W.Mayr and H.J.Prömel and A.Steger (Eds.), Lecture Notes in Computer Science, vol. 1367, Springer Verlag 1998. These lectures are very suitable for studying these topics from the basic.


Implementation of surreal numbers for games There is a very nice construction by Conway of surreal numbers. They are "numbers" that contain both real numbers and ordinals, are totally ordered, and have all the properties of a field (except they do not form a set but a class).

See for instance this pdf or Wikipedia for an introduction.

They can be even more generalized to so-called "games", which are originally introduced to study combinatorial games. The original motivation of Conway was to analyze the game of Go, in particular the endgame is especially suited to be modeled with "surreal games".

My question is: do you know if anybody has implemented this approach in an AI (i.e. computer player) to improve its level at a game? I am especially interested in the case of Go, but others as well. If not, is there an obstacle or a reason why it would not be a good idea?

I don't have an answer to your question of whether the theory of Conway games has been used in building game-playing programs, but still you might be interested in the Combinatorial Game Suite, "an open-source program to aid research in combinatorial game theory" (which I first learned about here).  It includes an implementation of various standard operations on Conway games in canonical form, as well as a scripting language for describing new games.


Existence of an algorithm I need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting the letters of w.

Would appreciate any help.

A language $L$ is said to be commutative if the following property holds:

  for every  word $a_1 \dotsm a_n \in L$ and any permutation $\sigma$ on
  $\{1, \ldots, n\}$, the word $a_{\sigma(1)} \dotsm a_{\sigma(n)}$ is
  also in $L$.

Now, my understanding of your question is the following:

  given a finite deterministic automaton $\mathcal{A}= (Q, A, \cdot)$, decide whether
  the language accepted by $\mathcal{A}$ is a commutative language.

There is a polynomial algorithm to answer this question.
Indeed a language is commutative if and only if its syntactic monoid is commutative. But the syntactic monoid $M(L)$ of $L$ is equal to the transition monoid of its minimal automaton. It follows that, $L$ is commutative if and only if the generators of $M(L)$ commute. In terms of automata, this is equivalent to check, for every pair of letters $(a, b)$, whether $q \cdot ab = q \cdot ba$ for all $q \in Q$.

Now, given $\mathcal{A}$, you can compute the minimal automaton of $L$ in $O(|Q|\log |Q|)$ and then check commutativity in $O(|Q||A|^2)$.


Category theory and parsers --- references wanted Since I'm interested in parsers (mainly in parser expression grammars), I'm wondering if there's some work that gives a categorical treatment of parsing. Any reference on applications of category theory to parsing is highly appreciated.

Best,

One of the very first applications of category theory to a subject outside of algebraic geometry was to parsing! The keywords you want to guide your search are "Lambek calculus" and "categorial grammar".

In modern terms, Joachim Lambek invented noncommutative linear logic in order to model sentence structure. The basic idea is that you can give basic parts of speech as having types, and then (say) ascribe English adjectives a function type taking noun phrases to noun phrases. (eg, "green" is viewed as function taking nouns to nouns, which means that "green eggs" is well-typed, since "eggs" is a noun).

Linearity arises from the fact that an adjective takes exactly one noun phrase as an argument, and the noncommutativity arises from the fact that the order of words in sentences matters. For example, an adjective's noun argument comes after the adjective ("green eggs"), whereas a prepositional phrase's noun phrase comes before the prepositional phrases ("green eggs with ketchup"). In categorical terms, you want a (non-symmetric) monoidal category which is closed on the left and the right. So the type $A\setminus{}B$ is the type of a phrase which has type $B$, when it is preceded by an $A$ on the left, and $B/A$ is the type of a phrase which has type $B$ when succeeded by $A$ on the right, and the type $A \ast B$ is the type of a phrase made by concatenating something of type $A$ with something of type $B$.

It turns out that Lambek grammars are equivalent to context free languages, though apparently this quite a difficult result -- showing CFGs are a subset of Lambek grammars is easy, but the other direction was only established in 1991 by Pentus.

A good exercise^H^H^Hpublication for the reader (ie, I haven't tried it, but think it would be cool to try) is to use Lambek calculus to reformulate Valiant's presentation of CYK parsing via boolean matrix multiplication, in categorical terms. As motivation, I quote from Lambek's 1958 paper The Mathematics of Sentence Structure:

  The calculus presented here is formally identical with a calculus constructed by G.D. Findlay and the present author for a discussion of canonical mappings in  linear and multilinear algebra.


What is known about the H-factor problem? Background
The $\mathcal{H}$-factor problem (a.k.a. the degree prescribed factor problem, or the degree prescribed subgraph problem) is defined as follows:
Given a graph $G=(V,E)$ and a set $H_v \subseteq \mathbb{N}$ for each vertex $v \in V$, does $G$ contain a spanning subgraph $F$ such that $\operatorname{deg}_F(v) \in H_v$ for all $v \in V$?
(I would also say that $H_v \in \mathcal{H}$ for all $v \in V$, but I have never seen it stated this way. Thus, the $\mathcal{H}$-factor problem is defined by $\mathcal{H}$ and the input is a graph $G=(V,E)$ and a mapping $f : V \to \mathcal{H}; v \mapsto H_v$.)
A spanning subgraph is also known as a factor, hence the name. This framework of problems captures many classic problems. For example, when $H_v = \{1\}$ for all $v \in V$, the problem is to determine if $G$ contains a perfect matching, also called a 1-factor.
Question
What is currently known about the complexity of this problem for different $\mathcal{H}$?
What about the special case when $\mathcal{H}$ is a singleton set (so $H_v$ is the same for all $v \in V$)?
Strongest Results I Know
Tractability:
If each set in $\mathcal{H}$ does not contain two consecutive gaps, then the $\mathcal{H}$-factor problem is in P (Cornuejols 1988). A integer $h$ is a gap in $H \subseteq \mathbb{N}$ if $h \not\in H$ but $H$ contains an element less than $h$ and an element greater than $h$.
Hardness: There exist some $\mathcal{H}$ such that the $\mathcal{H}$-factor problem is NP-hard (Lovasz 1972).
See (Szabo 2004) for a modern reference that cites these two results.

This can be considered as a type of read-twice constraint satisfaction problem. Unless I'm mistaken, it is quite easy to construct an "equality" gadget whenever $H$ has a double gap, if you allow constant constraints (requiring an edge to be in or out). Then you can use Schaeffer's Boolean CSP classification. So the problem then comes down to whether constants are important.

There is a big generalisation:

"Fanout limitations on constraint systems", Tomás Feder, Theoretical Computer Science, Volume 255, Issue 1-2, March 28, 2001, Pages 281 - 293.

http://www.sciencedirect.com/science/article/pii/S0304397599002881

Basically, for constraint languages $\Gamma$ (i.e. a finite set of Boolean relations) such that $\Gamma$ contains the constant relations $\{(0)\}$ and $\{(1)\}$, Feder considers the following problem: the input is a conjunction of constraints of the form $(v_{i_1},\dots,v_{i_k})\in R$ for some $R\in\Gamma$, such that each variable appears at most twice, and we ask if there is a satisfying assignment. Feder shows that if the constraint language contains a non-delta-matroid, the problem is equivalent to the unbounded-degree CSP. A set $H$ that has gaps (i.e. whenever Cornuejols' algorithm doesn't work) is a non-delta-matroid.

You can reduce read-once-or-twice to read-twice by doubling the instance and identifying the variables that were read exactly once.

Added later:

For your particular problem, I believe the assumption about constants is easy to get around. Let $\mathbb{N}=\{0,1,2,\dots\}$. For all $\mathcal{H}\subseteq 2^{\mathbb{N}}$ and all $d\in\mathbb{N}\cup\{\infty\}$, the following problem is either in P or NP-complete.

Name: Factor$(\mathcal{H},d)$.
Input: a simple graph $G$ of maximum degree at most $d$, and a set $H_v\in\mathcal{H}$ for each $v$.
Output: Is there a spanning subgraph of $G$ in which the degree of each vertex $v$ is in $H_v$?

Sketch proof:

If for all $H\in\mathcal{H}$, there are no gaps of length $\geq 2$ in $H\cap\{0,\dots,d\}$, the problem is tractable by Cornuejols' algorithm.
If for $H\in\mathcal{H}$ we have $0\in H$ or $H\cap\{0,\dots,d\}=\emptyset$, the problem is trivial: every graph has a 0-factor so all inputs are accepted.
Otherwise, since (2.) fails, there is a non-empty set $H\in\mathcal{H}$ with $0\notin H$ and $\min(H)\leq d$.
So if a vertex $v$ has degree $\min(H)$ and $H_v$, then all its edges must be in. So we can force edges to be in, and simulate constants,
and appeal to Feder's result.

This kind of gadgetry fails if we restrict the degrees of the input graph. For example let $H=\{1,4\}\subset\{0,1,2,3,4,5\}$,
and restrict the inputs to graphs that are regular of degree five. By symmetry, one cannot simulate constants.


Locating a set of 5 geometrically constrained points within a cloud of points What is the most efficient way to find a set of 5 geometrically constrained, non-collinear points within a 3D point cloud of, for example, 100 points?

All points are expressed with respect to a single world coordinate system.

Upper bound:

Make three sorted lists of point pointers, one for each dimension O(nlogn)

Pick a point in your reference template to be the "origin" and make 4 vectors to the other points O(1)

For each vector

Scan the list of all points to see if a sister point exists at this vector, if not throw it out as not an origin candidate.  O(n)

If you allow rotations you are probably going to have to throw it in a quadtree and do some range queries; but after the first few are matched to the template it will be oriented allowing you to go back to vector lookups.


How do you get the Calculus of Constructions from the other points in the Lambda Cube? The CoC is said to be the culmination of all three dimensions of the Lambda Cube. This isn't apparent to me at all. I think I understand the individual dimensions, and the combination of any two seems to result in a relatively straightforward union (maybe I'm missing something?). But when I look at the CoC, instead of looking like a combination of all three, it looks like a completely different thing. Which dimension do Type, Prop, and small/large types come from? Where did dependent products disappear to? And why is there a focus on propositions and proofs instead of types and programs? Is there something equivalent that does focus on types and programs?

Edit: In case it isn't clear, I'm asking for an explanation of how the CoC is equivalent to the straightforward union of the Lambda Cube dimensions. And is there an actual union of all three out there somewhere I can study (that is in terms of programs and types, not proofs and propositions)? This is in response to comments on the question, not to any current answers.

First, to reiterate one of cody's points, the Calculus of Inductive Constructions (which Coq's kernel is
based on) is very different from the Calculus of Constructions. It is
best thought of as starting at Martin-Löf type theory with universes,
and then adding a sort Prop at the bottom of the type hierarchy.  This
is a very different beast than the original CoC, which is
best thought of as a dependent version of F-omega. (For instance, CiC
has set-theoretic models and the CoC doesn't.)

That said, the lambda-cube (of which the CoC is a member) is typically presented as a pure type system for reasons of economy in the number of typing rules. By treating sorts, types, and terms as elements of the same syntactic category, you can write down many fewer rules and your proofs get quite a bit less redundant as well.

However, for understanding, it can be helpful to separate out the different categories explicitly. We can introduce three syntactic categories, kinds (ranged over by the metavariable k), types (ranged over by the metavariable A), and terms (ranged over by the metavariable e). Then all eight systems can be understood as variations on what is permitted at each of the three levels.

λ→ (Simply-typed lambda calculus)

 k ::= ∗
 A ::= p | A → B
 e ::= x | λx:A.e | e e

This is the basic typed lambda calculus. There is a single kind ∗, which is the kind of types. The types themselves are atomic types p and function types A → B. Terms are variables, abstractions or applications.

λω_ (STLC + higher-kinded type operators)

 k ::= ∗ | k → k
 A ::= a | p | A → B | λa:k.A | A B
 e ::= x | λx:A.e | e e

The STLC only permits abstraction at the level of terms. If we add it at the level of types, then we add a new kind k → k which is the type of type-level functions, and abstraction λa:k.A and application A B at the type level as well. So now we don't have polymorphism, but we do have type operators.

If memory serves, this system does not have any more computational power than the STLC; it just gives you the ability to abbreviate types.

λ2 (System F)

 k ::= ∗
 A ::= a | p | A → B  | ∀a:k. A
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

Instead of adding type operators, we could have added polymorphism. At the type level, we add ∀a:k. A which is a polymorphic type former, and at the term level, we add abstraction over types Λa:k. e and type application e [A].

This system is much more powerful than the STLC -- it is as strong as second-order arithmetic.

λω (System F-omega)

 k ::= ∗ | k → k
 A ::= a | p | A → B  | ∀a:k. A | λa:k.A | A B
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

If we have both type operators and polymorphism, we get F-omega. This system is more or less the kernel type theory of most modern functional languages (like ML and Haskell). It is also vastly more powerful than System F -- it is equivalent in strength to higher order arithmetic.

λP (LF)

 k ::= ∗ | Πx:A. k
 A ::= a | p | Πx:A. B | Λx:A.B | A [e]
 e ::= x | λx:A.e | e e

Instead of polymorphism, we could have gone in the direction of dependency from simply-typed lambda calculus. If you permitted the function type to let its argument be used in the return type (ie, write Πx:A. B(x) instead of A → B), then you get λP. To make this really useful, we have to extend the set of kinds with a kind of type operators which take terms as arguments Πx:A. k , and so we have to add a corresponding abstraction Λx:A.B and application A [e] at the type level as well.

This system is sometimes called LF, or the Edinburgh Logical Framework.

It has the same computational strength as the simply-typed lambda calculus.

λP2 (no special name)

 k ::= ∗ | Πx:A. k
 A ::= a | p | Πx:A. B | ∀a:k.A | Λx:A.B | A [e]
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

We can also add polymorphism to λP, to get λP2. This system is not often used, so it doesn't have a particular name. (The one paper I've read which used it is Herman Geuvers' Induction is Not Derivable in Second Order Dependent Type Theory.)

This system has the same strength as System F.

λPω_ (no special name)

 k ::= ∗ | Πx:A. k | Πa:k. k'
 A ::= a | p | Πx:A. B | Λx:A.B | A [e] | λa:k.A | A B
 e ::= x | λx:A.e | e e

We could also add type operators to λP, to get λPω_. This involves adding a kind Πa:k. k' for type operators, and corresponding type-level abstraction Λx:A.B and application A [e].

Since there's again no jump in computational strength over the STLC, this system should also make a fine basis for a logical framework, but no one has done it.

λPω (the Calculus of Constructions)

 k ::= ∗ | Πx:A. k | Πa:k. k'
 A ::= a | p | Πx:A. B | ∀a:k.A | Λx:A.B | A [e] | λa:k.A | A B
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

Finally, we get to λPω, the Calculus of Constructions, by taking λPω_ and adding a polymorphic type former ∀a:k.A and term-level abstraction Λa:k. e and application e [A] for it.

The types of this system are much more expressive than in F-omega, but it has the same computational strength.


Bounds on approximating frequency moments Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in \{1,2,\dotsc,n\}$. For $i \in \{1,2,\dotsc,n\}$, let $m_i = |\{j : a_j = i\}|$. The $k$th frequency moment is defined to be

$\displaystyle F_k = \sum_{i=1}^n m_i^k.$

In their well-known paper, The space complexity of approximating the frequency moments, Alon et al. give a streaming algorithm that approximates $F_k$ using roughly $O(n^{1-\frac{1}{k}}(\log n + \log m))$ space. They also use communication complexity techniques to obtain a lower bound of $\Omega(n^{1-\frac{5}{k}})$ for $k > 5$. For $k = 0,1,2$, they provide more or less matching upper and lower bounds.

Have there been improvements to these bounds since then, and has there been progress for $k = 3,4,5$?

There's been a fair bit of progress. On the specific problem of $F_k$, there is a matching upper and lower bound of $n^{1-2/k}$ for $k > 2$. The upper bounds come from this paper by Indyk and Woodruff (which appeared in STOC 2005) and the lower bounds are via the information complexity framework, due to Bar-Yossef et al and Chakrabarti et al.


Minimizing the gaps with incremental capacity There are a single job, a machine and a set of $n$ slots. The machine has a capacity that increments by $\zeta(t)$ every slot $t=1,2,\ldots,n$. Initially (before the first slot), the machine has 0 capacity i.e., the available capacity $C(t)$ at slot $t$ is $C(t):=\sum_{s\leq t}\zeta(s)$ (if the job was not scheduled at $t$ or before $t$). If the job is scheduled at slot $t$, then it will consume $c(t)$ units of the available capacity $C(t)$. If the job is not scheduled for a period of $x$ consecutive slots, then a penalty of $\lfloor x/2\rfloor$ occurs.
EDIT

We have to guarantee that $C(t)=\sum_{s\leq t}\zeta(s)-\sum_{s\in S}c(s)\geq 0$ for all $t$ where $S\subseteq\{1,2,\ldots,t\}$ is the set of slots where the job was scheduled.

For the penalty: there is a penalty for every contiguous unused block.

Here, is an example to illustrate the problem. Say $n=8$ and the job is scheduled at time $1$, $4$, and $8$. Here, we have a penalty of $\lfloor{2/2}\rfloor=1$ between time $1$ and $4$ since the job is not scheduled for a period of 2 consecutive slots ($2$ and $3$). Also, we have a penalty of $\lfloor{3/2}\rfloor=1$ between time $4$ and $8$ since the job is not scheduled for a period of 3 consecutive slots ($5$, $6$ and $7$). Thus, the objective here is $1+1$.
Given $\zeta(t)$, $c(t)$ for all $t=1,2,\ldots,n$, the objective is to schedule the job during the $n$ slots in order to minimize the sum of penalties while respecting the capacity of machine in all scheduled slots.
Is this problem NP-hard?
I tried to reduce the knapsack problem to it but I did not succeed yet. Also, I tried to solve the problem in polynomial-time using dynamic programming but failed also due to the incremental capacity.

Here's a poly-time dynamic-programming algorithm.
Lemma 1. The problem in the post has a poly-time dynamic-programming algorithm.
Proof sketch. Fix an input $(\zeta, c)$ over time slots $\{1,2,\ldots, n\}$.
For each $t, p\in \{0, 1,\ldots, n\}$, define subproblem $M(t, p)$ as follows.  Consider the problem restricted to the first $t$ time slots.  (That is, the problem over time slots $\{1,2,\ldots, t\}$, with $\zeta$ and $c$ restricted to those time slots.)  For this restricted problem, consider just those solutions that have total penalty $p$ and (if $t\ge 1$) do use slot $t$.  Define $M(t, p)$ to be the maximum, over all such solutions, of the capacity $C(t)$ achieved by that solution.  (Or $-\infty$ if there are no such solutions.)
The desired answer is $\min \{ p + \lfloor (n-t)/2\rfloor : t,p\in\{0,\ldots,n\},\, M(t, p) \ne -\infty\}$.
Then $M(0, 0) = 0$ and $M(0, p) = -\infty$ for $p>0$.  For $t>0$,  the following recurrence relation holds.
$M(t, p)$ is the maximum, over $s\in\{0,1,\ldots,t-1\}$, of
$$\begin{cases}
M(s, p-\lfloor(t-s-1)/2\rfloor) -c(t) + \sum_{i=s+1}^t \zeta(i)
& \scriptsize\textit{ (if that quantity is well-defined and non-negative)} \\
-\infty & \scriptsize\textit{ (otherwise). }
\end{cases}
$$
Here's the intuition.  Consider the possible solutions for the first $t$ time slots that use slot $t$ and achieve total penalty $p$.  Partition these solutions according to their last slot used, say, slot $s$, before slot $t$.  (Or $s=0$ if slot $t$ is the first slot used.)  Given $s$, such a solution consists of some solution $S_s$ for slots $1,2,\ldots, s$ (with slot $s$ used if $s>0$), followed by unused slots $s+1,s+2,\ldots, t-1$, followed by the used slot $t$.
The penalty incurred for the size-$(t-s)$ block of unused slots $s+1,\ldots, t-1$ is $\lfloor (t-s)/2\rfloor$.  So the cumulative penalty incurred by $S_s$ must be $p$ minus this.  The capacity $C(t)$ at time $t$ must be the capacity $C(s)$ achieved by $S_s$ at time $s$ plus the additional capacity added for unused slots $s+1,\ldots, t$, minus $\zeta(t)$ for using slot $t$.  So $C(t)$ will be maximized when $C(s)$ is maximized (over all solutions $S_s$ with appropriate penalty).  This is why the recurrence relation holds.
There are $O(n^2)$ subproblems, and for each the right-hand side of the recurrence can be evaluated in time $O(n)$ (with appropriate preprocessing), so this yields an $O(n^3)$-time dynamic-programming algorithm. $~~\Box$.


Natural examples of context-sensitive languages from practice I am looking for natural examples of context-sensitive languages from practice. For example, reasonable answers could include grammar syntax of a programming language, or encoding of certain properties of a program. In particular, please draw analogy from call-string-based context sensitive interprocedural dataflow analysis where the matching parentheses context-free language is used to encode the matching of calls and returns. That is an example where context-free language is useful in practice, or at least to explain a practical problem in a nice little theoretical way. Now, how can a context-sensitive language be useful in a similar context/scenario? That is my question.

Please note that I am not looking for artificial encoding into CSL (made up just to answer this question).

There are two ways your question can be interpreted: the complexity
theorist view and the application programmer view, which is a bit caricaturing the
situation, but should get my meaning across.

People in complexity theory will mainly wonder whether an actual
problem, practical or theoretical, can be encoded into CSL
recognition.  As noted in the comments of Marzio De Biasi and of user
vzn, a large number of real world problems may be encoded as CSL, as
CSL are recognized by non-deterministic linear bounded automata (LBA), and
conversely . It means that all these algorithms belong to the powerful
class of problems solvable non-deterministically in linear space.

But I strongly doubt that a single one of them is actually solved in
this way for practical purposes. Which brings us to the other view.  I
guess everyone knows that context-free (CF) or regular languages are
used as theoretically defined for various purposes, such as the syntax
of programming languages, or string pattern matching. Since it is also
known that CF and regular languages are context-sensitive languages
(CSL), they do stand as excellent answer to the question.

But since you must have known that, I must conclude that this is not
the answer you were looking for. And the alternative is a more
restrictive question: whether the theoretical formalisation of CSL is
actually used as such for some "real-world" purpose.

Actual use of a formalism in the real world usually entails 2
properties:

the formalism must be perspicuous, and express appropriately the
structural properties of the problem for which it is used.
the formalism must be computationally tractable (in a pragmatic sense).

My impression is that neither is an obvious characteristic of CS
languages. I am no expert on this, and you should not trust me too
much, but there does not seem to be structural organisation that can
be associated to all CSL, like parse-trees can be associated to
strings of CFL, or like regular expressions, even though many closure
properties are known for CSL (which are AFLs). Also, the associated
automaton, the LBA, is not the most obvious computing device to use as it is
non deterministic, and probably too powerful to be simulated
efficiently in specific application. But I insist this is just informal
intuition, not hard facts.

The fact is that many problems, like CF and regular languages, do not
need the full power of CSL and can be better dealt with more
specialized formalism, computationally easier to use, and expressing
more closely the problem at hand.

A typical example is in natural language processing. There are
linguistics structures (such as cross-serial dependency) that are not
naturally expressed with CF languages. Thus scientists have been
defining more powerful syntactics formalisms, such as tree-adjoining
grammar (TAG), Combinatory categorial grammars, ..., and the whole hierarchy
of linear context-free rewriting system (LCFRS), sometimes called
collectively mildly context-sensitive languages.

Another way to venture into context-sensitivity is to use a
context-free backbone and attach to the non-terminals various
attributes that must satisfy equations associated with rules.  This
lead to the attribute grammar formalism in compiler technology, and to
the use of so called feature structures in formalisms like lexical functional
grammar.

In other word, people do venture in the realm of context sensitivity,
but with specialized formalisms that are well adapted for expressing
the problems adressed. Actually, the two form of venturing into
context sensitivity described above can be combined and are combined.

Natural and programming languages are not the only application. For
example TAGs and equivalent formalism have been considered in biology
the explain DNA structures related to specific types of folding of DNA or RNA strands.

So the answer is yes, context-sensitivity is used, both in the
complexity sense and in real applications.  But no, it is not, as far
as I know, by direct use of the CSL formalism.

Note: Marzio De Biasi pointed to a genetics article that claims to
use a context sensitive grammar.  This is probably to be taken
informally as "more powerful than context-free". Indeed, the claim
later concerns "a context-sensitive deterministic grammar", which is
both undefined and significantly restrictive. Later description shows
that it seems actually a minimal extension of CFL, probably less powerful
than the use of TAGs (but I would need more work to see precisely
where it stands: it may just be CF in power).


Terminology for types of universal computation Some models of computation are universal in the sense they can compute any arbitrary computable function $f:\mathbb{N} \rightarrow \mathbb{N}$.

Other models are universal only as far as the input and output are encoded:
$\exists$ a set $A$ such that $\forall$ computable functions $f:\mathbb{N} \rightarrow \mathbb{N}$ the model can compute a function $f':A \rightarrow A$, such that $\forall n \in \mathbb{N},\ f(n)\ = \ d(f'(e(n)))$, for some encoding and decoding functions:
$e:\mathbb{N} \rightarrow A$
$d:A \rightarrow \mathbb{N}$
with suitable constraints on the computability (and possibly the complexity) of these functions.

What are the names for these two types of universality?
Is there any further relevant distinction to be made?

If I understand correctly, there are proofs of universality of systems, such as the Wolfram's 2-state 3-symbol Turing machine which are controversial because of subtleties regarding enconding.

The key words you should search for are "naming systems", "representation", "notation", "numbering", ...

The usual concepts of computability are defined over strings (either unary which is usually stated as $\mathbb{N}$ or binary which is state as computability over $\Sigma^*$ where $\Sigma = \{ 0,1 \} $). (They can be extended to $\Sigma^\omega$ but here I will stick to the countable case.) A model of computation is called universal if it is Turing-complete (i.e. it can compute any Turing computable function).

If we want to talk about computability over other sets, then we need a naming system. A naming system for $M$ is a partial function from $\Sigma^*$ onto $M$. If we have two sets $Y$ and $M$, and a naming system for each of them, then we can talk about computability of functions from $Y$ to $M$.

One can define a partial order over naming systems of a set $M$. $\gamma \leq \gamma'$ iff some computable function can translate $\gamma$-names of objects in $M$ to $\gamma'$-names of them.

Let me give a simple example. Assume that $M$ is the set of Turing machines, and $\gamma$ is one of the common ways of encoding Turing machines as explained in computability/complexity books. Let $\gamma'$ be defined by adding a bit to the names telling if the corresponding TM halts. Then $\gamma'$-names can be translated to $\gamma$-names by a computable function but not vice versa. $\gamma'$-names contain more information. If fact, we we can solve the halting problem for Turing machines if we use $\gamma'$ as our encoding.

Obviously we don't want to have non-computable information coded inside the names of objects as above, so we use names which have the least amount of information in computability (assuming that they exist). (In complexity, the complexity of a problem can depend on the naming system that is used for the inputs, and different naming systems can be more suitable for different purposes. There is no least if we change the requirement for translation from being computable to say poly-time computable as is shown by padding arguments.)

After defining the computability over other sets using naming systems, one can talk about a universal model of computation over them w.r.t. fixed naming systems.

Now, if the names in a naming system contain non-trivial information, then it is not very interesting for a machine to be universal w.r.t. that naming system anymore.

For further information:

Yuri L. Ershov, Sergei S. Goncharov, Anil Nerode, "Handbook of Recursive Mathematics", vol I and II, 1998
Klaus Weihrauch, "Computable Analysis", 2000


Circuit complexity of group actions Suppose that $G$ is a group with $|G|=n$. Suppose that $G$ is generated by elements $g_{1},\dots,g_{k}$. Let $\iota:G\rightarrow S_{2^{N}}$ be an injective group homomorphism such that $\iota(g_{i}):\{0,1\}^{N}\rightarrow\{0,1\}^{N}$ is computed by a reversible circuit consisting of $t_{i}$ reversible gates and where $t=t_{1}+\dots+t_{k}$ (for definiteness, assume that we can use any reversible gate on three bits). Then we shall say that $G$ has action complexity at most $t$.

Let $\delta_{n}$ be the maximum action complexity of a group $G$ with $|G|\leq n$. What are some bounds on $\delta_{n}$?

To obtain a trivial lower bound, we observe that if $|G|=n$, then
$|G|\leq|S_{2^{N}}|=(2^{N})!$ and without loss of generality, $t\geq N/3$, so
$t\geq\sqrt[1+\epsilon]{\log_{2}(\log_{2}(n))}$.

For a trivial upper bound, we can set $k\leq\log_{2}(n)$ and by Cayley's theorem, $G$ embeds into $S_{2^{N}}$ where $N=\lceil\log_{2}(n)\rceil$. Let $\iota:G\rightarrow S_{2^{N}}$ be an embedding. Now, the functions $\iota(g_{1}),...,\iota(g_{k})$ along with their inverses can each by computed by circuits of size $O(2^{N})=O(n)$ which gives an upper bound of
$\delta_{n}\leq O(n\cdot\log_{2}(n))$.

There is a large gap between the lower bounds and the upper bounds which I gave, so I am looking for better bounds for $\delta_{n}$.

Since this is CSTheory and not MathOverflow, I am interested in upper bounds which are not be obtained simply by finding smaller $r$ such that $G$ embeds in $S_{2^{r}}$ or by finding a smaller generating set for $G$.

Note: I could have formulated this question in terms of conventional Boolean circuits since if $f$ is a bijective function and both $f,f^{-1}$ can be computed by conventional circuits on $n$ gates, then $f$ can be computed by a reversible circuit on $O(n)$ gates.

The number of isomorphism classes of groups of order $\leq n$ is asymptotically $n^{\Theta(\log^2 n)}$, so to even specify all such groups requires strings of length $\Omega(\log^3 n)$, so this is also a lower bound on your action complexity.


True Bit Complexity of matrix multiplication is $O(n^{4})$ Matrix multiplication using regular (row - column inner product) technique takes $O(n^{3})$ multiplucations and $O(n^{3})$ additions. However assuming equal sized entries (number of bits in each entry of both matrices being multiplied) of size $m$ bits, the addition operation actually happens on $O(n^{3}nm) = O(n^{4}m)$ bits.

So it seems that the true complexity of matrix multiplication if measured via bit complexity should be $O(n^{4})$.

$(1)$Is this correct?

Supposing if one creates an algorithm which reduces the bit complexity to $O(n^{3+\epsilon})$ rather than total multiplications and additions, this might be a sounder approach than say reducing the total multiplications and additions to $O(n^{2+\epsilon})$ as attempted by researchers such as Coppersmith and Cohn.

$(2)$ Is this a valid argument?

No, the bit complexity of matrix multiplication on $M$-bit entries is $n^{\omega} (\log n)^{O(1)} \cdot M (\log M)^{O(1)}$, where $\omega < 2.4$ is the best known matrix multiplication exponent. Multiplication and addition of $M$-bit numbers can be done in $M (\log M)^2$ time. Multiplying two $M$-bit numbers yields a number which has no more than $2M$ bits. Adding $n$ numbers of $M$ bits each, yields a number which has no more than $M+\log n+O(1)$ bits. (Think about it: the sum is at most $n 2^M$, so the bit representation takes no more than $\log (n 2^M)+O(1)$ bits.)

References to fast integer multiplication algorithms can be found with a web search or wikipedia.


Hardness of computing circles with max number of lattice points You're given an $n\times n$ lattice $\mathcal{L}$, and you're asked to compute the maximum number of points in $\mathcal{L}$ that can belong to the same circle (the circle has to be enclosed by the outer sides of $\mathcal{L}$ and its center does not need to be in $\mathcal{L}$). How hard is this problem? Is it harder than factoring $n$? Are there decent bounds or estimates on the max number defined above?

It's probablyly much easier than factoring $n$, because you're looking for smooth numbers smaller than $n$ rather than for difficult factorizations; a smooth number is one that has many small factors, and these are the distances which will give you the most points on the lattice. If the center has to be at $(0,0)$, then you calculate how many lattice points are at distance $5^{a/2}13^{b/2}17^{c/2}29^{d/2}37^{e/2} \ldots$ using the formula for the number of ways of expressing a number as the sum of two squares. You can do the same thing for the circle centered at $(0,\frac{1}{2})$ or $(\frac{1}{2},\frac{1}{2})$. You can then do an optimization to find the largest value where this distance is less than $n/2$. I expect that this will be possible in polynomial time using dynamic programming.

I cannot imagine that the largest value would not correspond to the center having coordinates other than $0$ or $\frac{1}{2}$, but this should be proved.


Non-isomorphic minimal non-deterministic finite automata Can somebody provide an example of two equivalent (recognizing the same language) minimal non-deterministic automata (NFA) which are not isomorphic?

See the paper (postscript)

Arnold, Dicky, Nivat. A note about minimal non-deterministic automata


Reachability in Dynamic Line Graph Given a directed line graph $G = v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n$, there are two operators, namely

  $\mathsf{move}(v_i, v_j)$:  this operator moves $v_i$ to the position immediately after $v_j$; that is, after calling this function, the graph $G$ becomes (if $i > j$)
  $$
v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_j \rightarrow v_i \rightarrow v_{j+1} \rightarrow \cdots \rightarrow v_{i-1} \rightarrow v_{i+1} \rightarrow \cdots
$$
  $\mathsf{reachable}(v_i, v_j)$: whether $v_j$ is reachable from $v_i$ in $G$; that is, whether there is a path from $v_i$ to $v_j$

My current idea is to arrange $v_1$, $v_2$, $\cdots$, $v_n$ in a balanced binary tree such that if $v_j$ is reachable from $v_i$, then either one of below holds:

$v_j$ is in the right subtree of $v_i$;
$v_i$ is in the left subtree of $v_j$;
there is a node $v_k$ such that $v_i$ is in the left subtree of $v_k$ and $v_j$ is in the right subtree of $v_k$.

Using a balanced BST, we can get the rank of each node and by comparing the ranks of two nodes, we can know whether a node is reachable from another.  Therefore, two operations above can be implemented in $O(\log n)$ time.

  Q: Is there a better data structure with better complexity please?

Nomenclature aside (a line graph is something different than what you describe), you appear to be describing the problem of ''maintaining order in a list''. You have a list of items $v_i$ (your graph), you can remove an item from one point in the list and re-insert it elsewhere, and you want to check whether one item appears earlier than another in the list. This problem has a constant-time solution; see Dietz and Sleator, "Two algorithms for maintaining order in a list", STOC 1987, https://www.cs.cmu.edu/~sleator/papers/maintaining-order.html and https://en.wikipedia.org/wiki/Order-maintenance_problem


Separation of AM and SZK Are any results on the separation of AM from SZK known (e.g. relativized separation, or a separation assuming one-way functions exist, etc.)?

An oracle separation is easy to show. I'm not sure which paper showed it first, but for example you can already show that there exists an oracle $X$ such that

  $\mathsf{NP}^X \not\subset \mathsf{QSZK}^X,$

which implies

  $\mathsf{AM}^X \not\subset \mathsf{SZK}^X$

because $\mathsf{NP}$ is in $\mathsf{AM}$ and $\mathsf{SZK}$ is in $\mathsf{QSZK}$.
See arXiv:1801.08967 for one way to prove this. See the comment on page 3 of arXiv:1902.03660 for another way to show this.

Also note that in the unrelativized world $\mathsf{AM=SZK}$ would collapse the polynomial hierarchy, because $\mathsf{SZK}$ is closed under complement, and hence this implies $\mathsf{AM=coAM}$, which collapses $\mathsf{PH}$.


What is the complexity of distinguishing a true Fourier spectra from a fake one? A $PH$ machine is given oracle access to a random Boolean function $f:\{0,1\}^n \to \{ -1,1 \}$ , and two Fourier spectra $g$ and $h$.

The Fourier spectra of a function $f$ is defined as $F:\{0,1\}^n \to R$:

$F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x)$

One of $g$ or $h$ is the true Fourier spectra of $f$ and the other one is just a fake Fourier spectra belonging to an unknown random Boolean function.

It is not hard to show that a $PH$ machine, cannot even approximate $F(s)$ for any $s$.

What is the query complexity of deciding with high success probability which one is the true one ?

It is interesting to me, since if this problem is not in $PH$, then one can show that there exists an oracle relative to which $BQP$ in not a subset of $PH$.

Sorry I'm late -- it's a wonderful question!  As others have already pointed out, that's exactly why I asked the question in my BQP vs. PH paper, and why I spent 4 or 5 months working on it without success back in 2008.  One way to answer the question would have been to prove a much more general statement that I called the "Generalized Linial-Nisan Conjecture"---but unfortunately, that conjecture turned out to be false, at least for circuits of depth 3 and higher.  (I still think it's probably true for depth-2 circuits, which would at least yield an oracle separation between BQP and AM.)  For more recent ideas (the latest, as far as I know) toward an oracle separation between BQP and PH, see the nice followup paper by Fefferman, Shaltiel, Umans, and Viola.