Is there a formal proof that quantum computing is or will be faster than classical computing? Rather than empirical evidence, by what formal principles have we proved that quantum computing will be faster than traditional/classical computing?

This is a question that is a little bit difficult to unpack if you are not familiar with computational complexity. Like most of the field of computational complexity, the main results are widely believed but conjectural.

The complexity classes typically associated with efficient classical computation are $\mathsf{P}$ (for deterministic algorithms) and $\mathsf{BPP}$ (for randomized). The quantum counterpart of these classes is $\mathsf{BQP}$. All three classes are subsets of $\mathsf{PSPACE}$ (a very powerful class). However, our current methods of proof are not strong enough to definitively show that $\mathsf{P}$ is not the same thing as $\mathsf{PSPACE}$. Thus, we do not know how to formally separate $\mathsf{P}$ from $\mathsf{BQP}$ either — since $\mathsf{P \subseteq BQP \subseteq PSPACE}$, separating those two classes is harder than the already formidable task of separating $\mathsf{P}$ from $\mathsf{PSPACE}$. (If we could prove $\mathsf{P \ne BQP}$, we would immediately obtain a proof that $\mathsf{P \ne PSPACE}$, so proving $\mathsf{P \ne BQP}$ has to be at least as hard as the already-very-hard problem of proving $\mathsf{P \ne PSPACE}$).  For this reason, within the current state of the art, it is difficult to obtain a rigorous mathematical proof showing that quantum computing will be faster than classical computing.

Thus, we usually rely on circumstantial evidence for complexity class separations. Our strongest and most famous evidence is Shor's algorithm that it allows us to factor in $\mathsf{BQP}$.  In contrast, we do not know of any algorithm that can factor in $\mathsf{BPP}$ — and most people believe one doesn't exist; that is part of the reason why we use RSA for encryption, for instance.  Roughly speaking, this implies that it is possible for a quantum computer to factor efficiently, but suggests that it may not be possible for a classical computer to factor efficiently.  For these reasons, Shor's result has suggested to many that $\mathsf{BQP}$ is strictly more powerful than $\mathsf{BPP}$ (and thus also more powerful than $\mathsf{P}$).

I don't know of any serious arguments that $\mathsf{BQP = P}$, except from those people that believe in much bigger complexity class collapses (which are a minority of the community). The most serious arguments I have heard against quantum computing come from stances closer to the physics and argue that $\mathsf{BQP}$ does not correctly capture the nature of quantum computing. These arguments typically say that macroscopic coherent states are impossible to maintain and control (e.g., because there is some yet-unknown fundamental physical roadblock), and thus the operators that $\mathsf{BQP}$ relies on cannot be realized (even in principle) in our world.

If we start to move to other models of computation, then a particularly easy model to work with is quantum query complexity (the classical version that corresponds to it is decision tree complexity). In this model, for total functions we can prove that (for some problems) quantum algorithms can achieve a quadratic speedup, although we can also show that for total functions we cannot do better than a power-6 speed up and believe that quadratic is the best possible. For partial functions, it is a totally different story, and we can prove that exponential speed ups are achievable. Again, these arguments rely on a belief that we have a decent understanding of quantum mechanics and there isn't some magical unknown theoretical barrier to stopping macroscopic quantum states from being controlled.


Complexity of finite-state partial information games Given a deterministic partial-information zero-sum game with only finitely many states,

  whose possible outcomes are [lose,draw,win] with values [-1,0,+1] respectively,

  what is the complexity of approximating the value of such a game additively within $\epsilon$?

In particular, I can't come up any algorithm whatsoever for doing that.
The rest of this post is devoted entirely to giving a more thorough description

of the problem, so if you can already figure out what the question at the top

of this post means, then there's no reason for you to read the rest of this post.

Given a referee machine with states $\{1,2,3,...,S\}$, with a designated initial state $s_0$, a state $s_a$
whose score pair is $[-1,+1]$, a state $s_b$ whose score pair is $[+1,-1]$, and states of the form

$[\mbox{p1_info,p2_info,num_of_choices,player_to_move,next_state_table}]$ where:

$\mbox{player_to_move} \in \{1,2\}$
$\mbox{next_state_table}$ is a function from $\{1,2,3,...,\mbox{num_of_choices}\} \to \{1,2,3,...,S\}$
$\mbox{p1_info},\mbox{p2_info}, \mbox{num_of_choices} \geq 1$

When the machine is in a state of that form:

sends $\mbox{p1_info}$ to Player_1 and sends  $\mbox{p2_info}$ to Player_2,
sends $\mbox{num_of_choices}$ to the indicated player, waits for an element of $\{1,2,3,...,\mbox{num_of_choices}\}$
as input from that player,
then goes to the state indicated by $\mbox{next_state_table}$

When the machine enters one of the other two states $s_a$ or $s_b$,

halts with that state's score pair as its output

There is a natural two-player game: the referee machine is started in state $s_0 = 1$,

the players provide the inputs that the referee machine waits for, if the referee machine

halts then Player 1 scores the first value of the machine's output pair and Player 2

scores the second value of the machine's output pair, otherwise both players score 0.

  What is the complexity of the following problem?

  Given such a referee machine and a positive integer N, output a rational number

  that is (additively) within 1/N of the value of the natural game for Player 1.

As mentioned earlier in this question, I can't come

up with any algorithm whatsoever for doing that.

NOTE: my purported algorithm was incorrect; I deleted it.

One thing to realize is that it doesn't matter whether the game is deterministic or not. To randomize, the referee can ask each of the players to contribute a random number mod $p$, and then add them. It's easy to show that if the players use their optimal strategy, the sum is a random number mod $p$, which the referee can then use to randomize his strategy. This doesn't greatly increase the number of states in the game.

For a lower bound on the complexity, the question of approximating the value of a simple stochastic game is not known to be in P. Using the randomization trick I gave above, it is easy to write a simple stochastic game as a refereed game with a polynomial-size lookup table.


How can you encode natural numbers operations on interaction combinators? The church-encoding for natural numbers is a natural mean of implementing addition, multiplication and so on on the lambda calculus. Interaction nets are said to be an alternative universal computation system, yet, nothing is published as to how one could encode simple data structures and algorithms on the interaction nets directly. What are the natural encodings of numbers and numeric algorithms on interaction combinators?

Contrarily to the $\lambda$-calculus, the interaction combinators have no underlying logical system (i.e., there is no Curry-Howard correspondence for them), it is therefore hard to say that a numeral system is more "natural" than another.

(In the $\lambda$-calculus, Church numerals may be claimed to be "natural" because their type is the erasure of the second order definition of natural number, i.e.

$\mathsf{Nat}(x) := \forall X.(X(0)\Rightarrow\forall y.(X(y)\Rightarrow X(Sy))\Rightarrow X(x)).$

If you erase all quantifiers and first-order terms, you get $X\to(X\to X)\to X$, which is exactly the simple type of Church integers, perhaps modulo a permutation, i.e. $(X\to X)\to X\to X$ also works. But even in the $\lambda$-calculus there are lots of other numeral systems which may be preferred to the Church integers in some cases).

Anyhow, there are at least a couple of reasons why no-one bothered to explicitly define a numeral system for the interaction combinators:

the interaction combinators are studied more as an abstract model of computation than an actual programming language in which one wants to explicitly code algorithms; more general interaction net systems, in which one defines the agents and the interaction rules arbitrarily, are much more suitable for explicit programming (as shown for instance in Lafont's very first paper on interaction nets, POPL 1990), just like a functional language with a primitive integer type and fixpoint definitions (a la PCF) is better for real-life programming than the bare $\lambda$-calculus.
if you really want to, it is fairly straightforward to find numeral systems in the interaction combinators.  It is well known (see for instance Barendregt's The Lambda Calculus book, Sect. 6.4) that in a language allowing arbitrary recursive definitions (such as the interaction combinators), Turing-completeness is ensured as soon as one is able to define zero, successor, if-then-else (with test for zero) and predecessor. It doesn't take much to find a numeral system satisfying the above. The quickest solution I came up with in 5 minutes is to mimick Scott numerals (another numeral system in the $\lambda$-calculus). Scott numerals have the advantage of being linear, so they may be encoded in multiplicative proof nets, which in turn are essentially the $\gamma\varepsilon$ fragment of the interaction combinators. This is nice because these numerals will be duplicable without problems (by $\delta$ cells). Here are the definitions:

where $\mathbf M_3$ and $\mathbf M_3^\ast$ are the multiplexor and demultiplexor of rank 3 as defined in Lafont's Interaction Combinators paper (I&C, 1995). They both consist of two $\gamma$ cells and they annihilate with each other generating 3 parallel wires.


Can abstract syntax trees be unparsed in subexponential time? Abstract problem description

The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST, i.e. parse(unparse(AST)) = AST should hold.

This is the equal to finding a valid parse tree which would produce the same AST.

The language is described by a context free S-attributed grammar using a eBNF variant.

So the unparser has to find a valid 'path' through the traversed nodes in which all grammar constraints hold. This bascially means to find a valid allocation of AST nodes to grammar production rules. This is a constraint satisfaction problem (CSP) in general and could be solved, like parsing, by backtracking in $O(e^n)$.

Fortunately for parsing, this can be done in $O(n^3)$ using GLR (or better restricting the grammar). Because the AST structure is so close to the grammar production rule structure, I was really surprised seeing an implementation where the runtime is worse than parsing: XText uses ANTLR for parsing and backtracking for unparsing.

Questions

Is a context free S-attribute grammar everything a parser and unparser need to share or are there further constraints, e.g. on the parsing technique / parser implementation?
I've got the feeling this problem isn't $O(e^n)$ in general -- could some genius help me with this?

The question has been posted on StackOverflow and Computer Science without any answers.

If the synthesized attributes compute a parse tree, then unparsing can be done in time linear in the size of the parse tree, assuming that string concatenation happens in constant time -- the obvious recursive algorithm on the parse tree will do the job.

I would guess XText is doing backtracking in order to minimize the number of parentheses in arithmetic expressions, line breaks, or some other pretty-printing criteria. However, for most languages it's possible to do that in linear time, as well.

See Norman Ramsey, Unparsing Expressions With Prefix and Postfix Operators. Software—Practice and Experience, 28(12):1327–1356, October 1998.


Why do we need a sphere to graphically represent a qubit? Bloch sphere is a common visualisation of possible qubit values, but I fail to understand why do we need a sphere to represent them. Assuming we want to represent the single qubit a|0> + b|1> theoretically we know both a and b coefficients may be complex. However, we also know that the global phase factor is insignificant (we treat two unit vectors related by a global phase as equivalent) so we may treat a or b to be a real number. Wouldn't a circle be enogh to represent a qubit then (like taking axis y away from the original Bloch sphere)?

I feel like I am missing something simple (or some basic information I should know), any suggested read or explanation would be appreciated. Thank you in advance.

If we have $a|0\rangle + b|1\rangle$, there are two quantities we need to know to specify the qubit:

the ratio $a/b$, which is encoded by the latitude: $\left|0\right\rangle$ is the north pole and $\left|1\right\rangle$ the south,
the relative phase of $a$ and $b$, which gives the longitude.

That is, you can treat either $a$ or $b$ as a real number, but not both.

A circle can only specify one quantity.


What separates easy global problems from hard global problems on graphs of bounded treewidth? Plenty of hard graph problems are solvable in polynomial time on graphs of bounded treewidth. Indeed, textbooks typically use e.g. independet set as an example, which is a local problem. Roughly, a local problem is a problem whose solution can be verified by examining some small neighborhood of every vertex.

Interestingly, even problems (such as Hamiltonian path) of a global nature can still be solved efficiently for bounded treewidth graphs. For such problems, usual dynamic programming algorithms have to keep track of all the ways in which the solution can traverse the corresponding separator of the tree decomposition (see e.g. [1]). Randomized algorithms (based on so-called cut'n'count) were given in [1], and improved (even deterministic) algorithms were developed in [2].

I don't know if it's fair to say that many, but at least some global problems can be solved efficiently for graphs of bounded treewidth. So what about problems that remain hard on such graphs? I'm assuming they are also of a global nature, but what else? What separates these hard global problems from global problems that can be solved efficiently? For instance, how and why would known methods fail to give us efficient algorithms for them?

For example, one could consider the following problem(s):

  Edge precoloring extension Given a graph $G$ with some edges colored, decide if this coloring can be extended to a proper $k$-edge-coloring of the graph $G$.

Edge precoloring extension (and its list edge coloring variant) is NP-complete for bipartite series-parallel graphs [3] (such graphs have treewidth at most 2).

  Minimum sum edge coloring Given a graph $G=(V,E)$, find an edge-coloring $\chi : E \to \mathbb{N}$ such that if $e_1$ and $e_2$ have a common vertex, then $\chi(e_1) \neq \chi(e_2)$. The objective is to minimize $E'_\chi(E) = \sum_{e \in E} \chi(e)$, the sum of the coloring.

In other words, we have to assign positive integers to the edges of a graph such that adjacent edges receive different integers and the sum of the assigned numbers is minimal. This problem is NP-hard for partial 2-trees [4] (i.e. graphs of treewidth at most 2).

Other such hard problems include the edge-disjoint paths problem, the subgraph isomorphism problem, and the bandwidth problem (see e.g. [5] and the references therein). For problems that remain hard even on trees, see this question.

[1] Cygan, M., Nederlof, J., Pilipczuk, M., van Rooij, J. M., & Wojtaszczyk, J. O. (2011, October). Solving connectivity problems parameterized by treewidth in single exponential time. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on (pp. 150-159). IEEE.

[2] Bodlaender, H. L., Cygan, M., Kratsch, S., & Nederlof, J. (2013). Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In Automata, Languages, and Programming (pp. 196-207). Springer Berlin Heidelberg.

[3] Marx, D. (2005). NP‐completeness of list coloring and precoloring extension on the edges of planar graphs. Journal of Graph Theory, 49(4), 313-324.

[4] Marx, D. (2009). Complexity results for minimum sum edge coloring. Discrete Applied Mathematics, 157(5), 1034-1045.

[5] Nishizeki, T., Vygen, J., & Zhou, X. (2001). The edge-disjoint paths problem is NP-complete for series–parallel graphs. Discrete Applied Mathematics, 115(1), 177-186.

Most algorithms for graphs of bounded treewidth are based on some form of dynamic programming. For these algorithms to be efficient, we need to bound the number of states in the dynamic programming table: if you want a polynomial-time algorithm, then you need a polynomial number of states (e.g., n^tw), if you want to show that the problem is FPT, you usually want to show that the number of states is some function of treewidth. The number of states typically corresponds to the number of different types of partial solutions when breaking the graph at some small separator. Thus a problem is easy on bounded-treewidth graphs usually because partial solutions interacting with the outside world via a bounded number of vertices have only a bounded number of types. For example, in the independent set problem the type of a partial solution depends only on which boundary vertices are selected. In the Hamiltonian cycle problem, the type of a partial solution is described by how the subpaths of the partial solution match the vertices of the boundary to each other.
Variants of Courcelle's Theorem give sufficient conditions for a problem to have the property that partial solutions have only a bounded number of types.

If a problem is hard on bounded-treewidth graphs, then it is usually because of one of the following three reasons.

There are interactions in the problem not captured by the graph. For example, Steiner Forest is NP-hard on graphs of treewidth 3, intuitively because the source-destination pairs create interactions between nonadjacent vertices.

Elisabeth Gassner: The Steiner Forest Problem revisited. J. Discrete Algorithms 8(2): 154-163 (2010)

MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Dániel Marx: Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth. J. ACM 58(5): 21 (2011)

The problem is defined on the edges of the graph. Then even if a part of the graph is attached to the rest of the graph via a bounded number of vertices, there could be many edges incident to those few vertices and then the state of a partial solution can be described only by describing the state of all these edges. This is what made the problems in [3,4] hard.
Each vertex can have a large number of different states. For example, Capacitated Vertex Cover is W[1]-hard parameterized by treewidth, intuitively because the description of a partial solution involves not only stating which vertices of the separator were selected, but also stating how many times each selected vertex of the separator was used to cover edges.

Michael Dom, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger: Capacitated Domination and Covering: A Parameterized Perspective. IWPEC 2008: 78-90


Find a string with minimal edit distance from a set of given strings Input: a bunch of binary strings: x_0, x_1, ... , x_n

Output: a binary string y that minimizes edit(x_0, y) + edit(x_1, y) + ... edit(x_n, y) where edit(x, y) denotes the levenshtein distance, i.e. the minimum number of insertions, deletions, and substitutions to transform x into y.

What complexity class is this problem in? Does it have an efficient exact or approximation algorithm?

Your problem is called the Median string problem. Nicolas and Rivals proved that the Median String problem (under the Levenshtein distance) is NP-complete even for binary strings.


Hardest known natural problem in P? I wonder, what is (currently) the largest number $k$, such that a natural problem is known with the following properties:

An $O(n^k)$ algorithm has been already found for the problem.
For any fixed $\epsilon>0$ no $O(n^{k-\epsilon})$ algorithm is known for the same problem. (Note that a faster algorithm $may$ exist, just it is not known yet, so I am not looking for a proven lower bound.)
The problem description itself does not depend on $k$. (This condition is needed to exclude parametrized cases like "find a clique of size $k$ in an input graph, for a constant $k$.")

In a sense, such a problem might qualify as the hardest, known, natural, problem in $\bf P$ (regarding the exponent of the fastest known algorithm).

The AKS Primality testing algorithm may be a good candidate, where the best algorithm currently known version of the algorithm has $\tilde{O}(n^6)$ running time.  See Primality testing with Gaussian periods (Lenstra and Pomerance).


Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs? Following the equivalent questions regarding NP-Completeness (see the weight question and the directed question), I was wondering how parameterized problems are affected by these attributes.

  Which $NP$-hard graph problems are $W[1]$-Hard on directed graphs, but fixed parameter tractable on undirected graphs?

  Which $NP$-hard graph problems are $W[1]$-Hard on weighted graphs, but fixed parameter tractable on unweighted graphs?

OK, so we have problems which becomes harder on the directed version. What about weights? Can they make parameterized problem harder?

The disjoint paths problem: given $G$ and $k$ pairs of nodes, are there node disjoint paths connecting the given pairs. Parameterized by $k$, in FPT when $G$ is undirected from the seminal work of Robertson and Seymour. NP-Hard for $k=2$ when $G$ is directed - from work of Fortune, Hopcroft and Wylie (1980).


Resources for mathematicians hoping to learn more computer science Background:

I'm coming to the end of my masters degree in Mathematics and will be starting a PhD in Logic in August. The more logic I study, the more theoretical computer science I am exposed to, e.g. recursion theory, lambda calculus, but the underlying CS is brushed under the rug. My main areas of interest - set theory and category theory - also have applications in computer science, but so far I've only studied them from the point of view of pure mathematics.

Problem:

My lack of any computer science background sometimes makes it difficult to see the motivation or intuition behind what is going on, or how it could be applied. I get by, but I feel like it would be healthier to branch out a little bit... it occurs to me that, for the benefit of my future research, I should learn some computer science.

Most CS books I've looked at haven't been very suitable for my purposes, either being too basic and untechnical, or presupposing the kind of CS background that I don't have. They seem to be aimed at people who are quite computer-savvy but who have little in the way in mathematical background - my situation is the opposite.

Question:

  What books or other resources are there which could help a mathematician-turned-logician in their goal of gaining a working knowledge of (theoretical) computer science?

I'm looking for something more wholesome than a few seminar talks and more in-depth than The New Turing Omnibus, but I don't have the time or resources to do another undergraduate degree. (It may be that I'm asking for something that doesn't exist.)

Sorry if the question is too vague or ill-posed. I felt it was more suitable here than on MSE but I'll be happy to migrate it if needs be.

You're essentially asking for resources that will let you turn your existing knowledge of logic, recursion theory, and category theory into knowledge about theoretical computer science.I would suggest looking at realizability theory, especially via its connections to topos theory and categorical proof theory.

Here are a handful of suggestions; my advice is to pick one and go into depth. With the exception of Taylor's book (which explains this), my suggestions assume you have been exposed to enough lambda calculus and category theory to have seen categorical interpretations of the simply-typed lambda calculus.

Paul Taylor's book Practical Foundations of Mathematics

IMO, this is probably the single best technical introduction to the relationship between logic, category theory and computation. It assumes almost no pre-requisites, but it gets into quite deep waters very quickly, and is sure to tax (and greatly improve) your mathematical maturity.
Wesley Phoa's notes An Introduction to Fibrations, Topos Theory, the Effective Topos, and Modest Sets

These are some lecture notes that Wesley Phoa wrote up. If you are categorically fluent, then these notes offer a really fast path into understanding some of the most  important constructions in realizability and topos theory (namely, the construction of the effective topos).
Bart Jacobs' book Categorical Logic and Type Theory

This is one of the definitive references on the categorical semantics of type theory. It is also very large.

At the same time you are reading one of these books, I would advise downloading and learn how to use the Agda programming language. This language implements the sophisticated type theories described above, and IMO it is incredibly helpful to see how the often quite subtle semantic constructions cash out in type theory.

Andrej Bauer can probably give you even better advice. Perhaps he can be persuaded to post. :)


How to recognize safe queries in tuple relational calculus? How do I determine whether query in tuple relational calculus is a safe query?

I attended a course on database theory some time ago, but I’m a bit rusty on the topic, so take what follows with a grain of salt.

If by “safe” you mean “domain independent”, then I think you’re out of luck: domain independence is undecidable, as unsatisfiability of relational calculus queries reduces to it.

I believe you can find the details on the slides for the above-mentioned course, and in the book Foundations of Databases by Abiteboul, Hull, and Vianu.


Positive 1-in-3 SAT FPT or Fixed Parameter Intractable There are a number of satisfiability problems that are difficult to solve even in the fixed parameter sense. For example, Weighted q-CNF Satisfiability is W[1]-complete when parameterized by the number of variables that are set to true.

My question is: is there any literature on whether Positive 1-in-3 is W[1]-hard or fixed parameter tractable when parameterized by the number of variables that are set to true? Positive 1-in-3 SAT is the problem where all literals in an expression are positive and exactly one literal in each clause is true.

No, since even the generalization to 1-in-at-most-3 is FPT for the same reason as vertex cover.

(With at most 3 variables per clause, there will be at most 3 cases for each step.)

I feel like that generalization should have a simple

poly-size kernel, but can't figure out any way of showing that.

The corresponding problem for at-most-1-in-3 constraints, where one wants

exactly k variables to be true, is W[1]-hard by reduction from independent set:

If k<2 then brute force, else:

There's a variable for each vertex and one other variable.

The constraints are  u , other_variable , v  for edges u,v.

Since 2≤k and other_variable is in every constraint, other_variable must be false, so

the satisfying assignments with exactly k Trues correspond to the independent k-sets.


What is the intuition behind "hardness of approximation"? I am reading a paper about graph matching problem. Which is, to some extent, an optimization version of the graph isomorphism problem.

To my surprise, some closely related NP-hard problems are quite different in terms of approximation.

Can anyone give me some intuition behind this phenomenon?

Thanks in advance!

One important reason why problems that look equally hard to compute exactly might be very different to approximate relates to the fragility of NP-completeness reductions.

The simplest example I can think of the relation between VERTEX COVER and MAX INDEPENDENT SET. The two problems are complementary: given a graph $G = (V, E)$ with a vertex cover $S$, the set $V\setminus S$ is an independent set. This is why it's easy to show that one problem is NP-hard by reduction from the other.

But suppose I can get "close" to a good vertex cover, in that instead of finding the smallest cover $S$, I find a worse cover $S'$ where $|S'| = 2 |S|$. This means that instead of finding the maximum independent set of size $n - |S|$, I've found one of size $n - 2|S|$.

Suppose in this graph the max independent set size was $n/2$. Then essentially my approximation to the vertex cover found nothing at all.

In other words, the NP-hardness reduction only preserved the exact solution relationship, not the approximate solution relationship.

To preserve approximations, you need a different kind of reduction called an $L$-reduction, and once you limit yourself to such reductions, you realize that the two problems are indeed quite different.


Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates Let $(X,+,\cdot)$ be a commutative ring. Let $|\cdot|\colon X\to \mathbb{N}$ be a function that satisfies $|x+y|\leq |x|+|y|$ and $|xy|\leq |x|+|y|$. We call the function length, and length is always positive.
We are given an arithmetic formula(arithmetic circuit with outdegree 1) of size $n$, over $X$ with gates $+$ and $\cdot$. There are no constant terms.

The time to evaluate a gate with input $x$ and $y$ is $O(|x|+|y|)$.

Is it possible to evaluate the formula in $O(m\log n)$ time? where $m$ is the total length of the input.

EDIT: I was wrong about the implication to arithmetic circuits.

I think it is possible. It uses ideas in parallel evaluation of arithmetic expressions and tree contraction.

Consider the arithmetic formula, it is an arithmetic circuit that forms a directed tree. Consider each gate as a function of the form $f(x,y) = a(x\square y)+b$ for constant $a,b$ and operation $\square$. So, a $\square$ gate is $1(x\square y)+0$.
We call $a$ the linear part, and $b$ the constant part.
One can evaluate the formula by a "tree contraction" operation. It takes 3 vertices $u,v,w$ and returns one new vertex in this tree. Here $u,v$ are children of $w$, and $u$ is a leaf.
That is, we can delete node $u$, contract $w$ and $v$ into to a new vertex $w'$, and the gate for $w'$ is a function of the form $a(x\square y)+b$ for some constants $a$ and $b$, and we have the tree evaluates to the same value.

Here is an example:

Let $\ell(v)$ be the labels of $v$, defined as all the input used to compute the linear and constant part of the gate $v$.

Facts:

One can apply tree contraction to a constant fraction of vertices in
parallel. Let such parallel operation be called a single iteration.
At any moment of the computation, $\{\ell(v) | v\in V_t\}$ forms a partition of the input, where $V_t$ is the vertices of the formula after the $t$th contraction.
The coefficient of the linear term and constant term on each node can be expressed as a single-use expression (i.e. each variable in the input is used at most once). It implies if $y$ is the constant part or linear part of the vertex $v$, then $|y| \leq \sum_{x\in \ell(v)} |x|$. Note this fact is only used to bound the size of the coefficient. The computation of the coefficient itself is not related to the single-use expression.

Consider an algorithm that does $O(\log(n))$ iterations of tree contraction in parallel, and get a constant size tree. We evaluate the final tree directly. In each iteration, the running time is bounded by the sum of the size of the labels for each node, which is $O(m)$ due to disjointness of the label sets over the vertices.

Together the running time is $O(m\log n)=O(m\log n)$.


What's the approximation factor of this Max k-Cut approximation? I'm thinking about an approximation algorithm for Max k-Cut. One simple and more involved approximation algorithms can be found here. The Max k-Cut problem is defined as follows.

Input is a graph G = (V, E) and an integer k, n = |V|, the question asks for partitioning G
into k disjoint sets such that the total number of edges between disjoint parts is maximized.

My algorithm is a greedy strategy and works as follow (maybe someone else already had a similar idea but I'm not aware of):

Start with each vertex in a group by
itself, and at each step, combine the
two groups that have a minimum number
of edges between them. Repeat this until the number of groups shrinks to $k$.

Is there a known approximation guarantee for this algorithm?

This is called the edge-contraction heuristic, in which an upper bound $(k-1)/(k+1)$ on the approximation ratio can be shown. See section 3 of the work by Kahruman et al. for reference.
Imagine whenever we combine two nodes u, v into a group, instead of forming a group we contract the edge (u, v) between these two nodes, and updates the weight of all the edges incident to the newly formed node. Repeat the procedure until there are only k nodes left. Lemma 3.1 in the above paper shows that the sum of weights of the first $i$ edges being contracted (denoted as $W_i$) satisfies the following inequality:
$$W_i \leq \frac{2iW}{(n-1)(n-i-1)} \text{,}$$
where $W$ is the sum of weights of all edges.
This can be derived from
$$W_{i+1} \leq W_i + \frac{W-W_i}{({n-i\atop 2})} \text{,}$$
since we always contract the lightest pair, the weight of the contracted edge cannot surpass the average weight.
One can see that the cut formed by this algorithm has weight $W_C = W-W_{n-k}$,
and by observing that $W \geq W^*$ where $W^*$ is the weight of the optimum cut,
we have our desired approximation ratio:
$$W_C \geq W-\frac{2(n-k)W}{(n-1)(k-1)} \geq \frac{k-1}{k+1}W^* \text{.}$$
For k=2, the algorithm gives a 1/3-approximation to the Max cut problem.


vertex in a degeneracy ordering of a undirected graph There is a step in Bron–Kerbosch algorithm

for each vertex v in a degeneracy ordering of G:

what is "a degeneracy ordering of G"?  For example what is vertex in a degeneracy ordering  in

this graph

See http://en.wikipedia.org/wiki/Degeneracy_(graph_theory)

Essentially, a degeneracy ordering is an ordering on the vertices that you get from repeatedly removing a vertex of minimum degree in the remaining subgraph. The degeneracy of the graph is the smallest number d such that every vertex has at most d neighbors that are later than it in the ordering. Among all possible orderings, the degeneracy orderings minimize this number.


Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning? I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics).

I am particularly interested in algorithms (specially their application to machine learning, and whenever possible, proving theoretical guarantees for them, wether these guarantees are in complexity or learnability).

I'd be interested in knowing if there are any "heuristic" algorithms out there in the area of sub modularity and machine learning, with unknown guarantees. From my current knowledge of the topic, the most common heuristic seems to be the "greedy" heuristic, and it seems to be quite well understood. Hence, I was wondering if there was any open problems in the area of designing new algorithms (or improving current ones) or algorithms that already exists, that don't have any guarantees. Is there anything open questions related with theoretical guarantees that is open in sub modularity?

Or of if there aren't any such open question, are there any open question in the intersection of sub modularity and machine learning?

There are many open algorithmic problems. All problems below (other than the last bullet) are NP-hard, so we are interested in the best approximation ratio we can achieve in polynomial time. The following are just a sample:

Given a non-negative submodular function on a universe $U$, find a set $A$ of size at most $k$ maximizing $f(A)$. The best known approximation ratio is $1/e+0.004$ (BFNS14). When "at most" is replaced by "exactly", the best known approximation ratio is 0.356 (also BFNS14).
Given a non-negative monotone submodular function and $k$ matroids, find a set $A$ belonging to all different matroids and maximizing $f(A)$. When $k=1$ the best approximation ratio is $1-1/e$, and this is optimal. For larger $k$, LSV give a $1/k$ approximation, but this is probably not tight.
There are two algorithms for maximizing a non-negative monotone submodular function over a matroid that give the optimal approximation ratio $1-1/e$: the continuous greedy algorithm and the non-oblivious local search algorithm. Both are randomized. The best known deterministic algorithm is the greedy algorithm, giving a $1/2$ approximation. Can we separate deterministic and randomized algorithms in this oracle setting? A similar question arises in the non-monotone unconstrained case, in which BFNS12 give an optimal randomized $1/2$ approximation algorithm, but the best known deterministic algorithms (one in BFNS12 and an earlier local search algorithm due to FMV) give only a $1/3$ approximation.
Both the continuous greedy algorithm and the non-oblivious local search algorithm are rather slow. Is there a fast, $\tilde{O}(n)$ algorithm for maximizing a monotone submodular function over a matroid? (see BV for the case of a uniform matroid)
Algorithms for minimizing submodular functions are also a bit slow, the fastest running in time $O(n^5)$ (see Iwata's survey).


Arithmetic circuits over $GF(p)$ for computing $x \bmod 2$ given input $x \in GF(p)$ Let $p$ be a prime.  Suppose we consider the function $f: GF\left(p \right) \rightarrow \left\{0, 1 \right\}$ where $f(x) = x \bmod 2$ for all.

The question is the following:  are there any known circuit bounds or results on computing $f$ using arithmetic circuits over $GF(p)$?

In other words, we'd like to evaluate $f$ using only field additions and multiplications.

It's simple to do this with arithmetic circuits of size $O \left(p \right)$ and also probably straightforward to show that it cannot be done with arithmetic circuits of size $o\left( \log p \right)$.  However, it has been difficult for us to say anything concrete other than these simple bounds.  Any literature or references on this problem (or similar types of problem) would be greatly appreciated!  Thanks!

It's not clear if this is directly useful, but lower bounds are known for depth-3 circuits computing an $n$-variate version of your function over $\mathrm{GF}(p)$ for $p \neq 2$. See Theorem 3.7 in the survey of Shpilka and Yehudayoff for details and references.

I don't believe lower bounds of the form $\omega(\log d)$ are known for general circuits computing an explicit univariate polynomial of degree $d$, so proving an $\omega(\log p)$ lower bound for your problem will likely be difficult.


Tree-decomposition with clique interfaces Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that:

For every edge $\{v_1,v_2\} \in E$, there exists a node $n$ of $T$ such that $v_1,v_2 \in \lambda(n)$.
For every vertex $v \in V$, the set $\{n \in T \mid v \in n\}$ forms a connected subtree of $T$.

For my purposes (namely, showing the tractability of model-checking for a particular logical fragment), I am interested in a restricted kind of tree decompositions, that satisfies an additional condition. I call a tree-decomposition with clique interfaces a tree decomposition $(T,\lambda)$ of $G$ that respects the following additional property:

For every two adjacent nodes $n_1$ and $n_2$ of the tree decomposition $T$, we require that the interface $\lambda(n_1) \cap \lambda(n_2)$ forms a clique in $G$. In other words, for every pair of distinct elements $a,b$ occurring both in $n_1$ and $n_2$, we must have $\{a, b\} \in E$.

As usual, the width of such a decomposition is $max_{n \in T}|\lambda(n)|-1$ and the width of $G$ is the minimal width of such a decomposition.
Note that, of course, the width of $G$ according to this definition is necessarily greater than its treewidth in the usual sense.

My question is to know if this notion of width has already been studied and has an established name. In particular, I am interested in alternative characterization of graphs whose width is low in this sense, in the complexity of computing it, etc.

This could be related to the notion of $k$-trees. In k-trees, we impose in tree decompositions that $\lambda(n)$ forms a clique for all $n$ and that the interfaces are of size $k$. However not all graphs have such a decomposition, while for the notion that I propose, all graphs would have a decomposition (at worst the trivial one with width $|V|-1$) so it looks like this notion could have been studied in a general context.

See "Decomposition by clique separators", Robert E. Tarjan, Discrete Mathematics 55 (2): 221–232, 1985.

If I understand correctly, your notion of width is essentially the size of the largest piece in Tarjan's decomposition.


Major unsolved problems in theoretical computer science? Wikipedia only lists two problems under "unsolved problems in computer science":

P = NP?
The existence of one-way functions

What are other major problems that should be added to this list?

Rules:

Only one problem per answer
Provide a brief description and any relevant links

Can multiplication of $n$ by $n$ matrices be done in $O(n^2)$ operations?

The exponent of the best known upper bound even has a special symbol, $\omega$. Currently $\omega$ is approximately 2.376, by the Coppersmith-Winograd algorithm.  A nice overview of the state of the art is Sara Robinson, Toward an Optimal Algorithm for Matrix Multiplication, SIAM News, 38(9), 2005.

Update: Andrew Stothers (in his 2010 thesis) showed that $\omega < 2.3737$, which was improved by Virginia Vassilevska Williams (in a July 2014 preprint) to $\omega < 2.372873$.  These bounds were both obtained by a careful analysis of the basic Coppersmith-Winograd technique.

Further Update (Jan 30, 2014): François Le Gall has proved that $\omega < 2.3728639$ in a paper published in ISSAC 2014 (arXiv preprint).


Canadian CS University Positions? Does anyone know if there is a centralized source of Canadian positions advertised by universities for computer science? I conjecture that this might exist since there are websites advertising math jobs for Canada, plus websites advertising CS jobs in general (CRA, Higher Ed). Additionally, there exists at least one such opening currently.

This is a special case of a previously studied problem, where it was asked on cstheory without the Canadian constraint.

The Canadian CS community is seriously under-server and under-organized.  The ACM (in the US) completely overshadows us, and since it (nominally anyways) tries to be international, that leaves little room for Canadians to get organized.  So typical community-driven issues, like aggregating jobs, does not happen.  The community is (now) large enough to be able to sustain such an organization (I know, I belong to the CMS, the Canadian Mathematical Society, and it manages just fine, and the sizes involved are in the same ballpark).

I realize that this answer is a bit of a non-answer.  But the (unfortunate!) answer to your question is 'no'.  So rather than just saying that, I figured I would elaborate.

Ok, so apparently my Google-fu was not good enough.  I just stumbled upon the CACS/AIC, which is the Canadian Association of Computer Science.  But the web site is astonishingly bare bones, with no real sign of the purpose, etc.  So still a 'no', but not quite exactly as I had said.  And CIPS is different, as it really focused on the IT side of things, not so much on the CS.


What are the morphisms of Adj(C,T) - the category whose objects are the adjunctions of a given monad? The Wikipedia page for Monad says just that for a monad $(T,\eta,\mu)$ we can define the category of all adjunctions that define the monad:

  Let ￼$\textbf{Adj}(C,T)$ be the category whose objects are the adjunctions ￼$(F,G,e,\varepsilon)$ such that $(GF,e,G\varepsilon F)=(T,\eta,\mu)$￼ and whose arrows are the morphisms of adjunctions which are the identity on ￼$C$. Then this category has

  an initial object $(F_T,G_T,\eta,\mu_T) : C\to C_T$￼, where $C_T$￼ is the Kleisli category,
  a terminal object $(F^T,G^T,\eta,\mu^T) : C\to C^T$￼, where ￼$C^T$ is the Eilenberg-Moore category.

What are the morphisms of adjunctions in $\textbf{Adj}(C,T)$ and what is meant by ... which are the identity on $C$?

The definition of morphism of adjunctions may be found in MacLane's book. Let $F:\mathcal C\rightarrow\mathcal D$, $G:\mathcal D\rightarrow\mathcal C$, $F':\mathcal C'\rightarrow\mathcal D'$, $G':\mathcal D'\rightarrow\mathcal C'$, and let $(F,G,\eta,\varepsilon)$, $(F',G',\eta',\varepsilon')$ be adjunctions. A map of adjunctions from the first to the second is a pair of functors $L:\mathcal C\rightarrow\mathcal C'$, $K:\mathcal D\rightarrow\mathcal D'$ such that $KF=F'L$, $LG=G'K$ and $L\eta=\eta'L$ (or, equivalently, $\varepsilon K=K\varepsilon'$).

In the case of the category of adjunctions of a monad, the category $\mathcal C$ on which the endofunctor of the monad acts is fixed, so $\mathcal C'=\mathcal C$ and one considers the above definition only in case $L=Id_{\mathcal C}$.


Incomplete basis of combinators This is inspired by this question. Let $\mathcal{C}$ be the collection of all combinators which only have two bound variables. Is $\mathcal{C}$ combinatorially complete?

I believe the answer is negative, however I was not able to find a reference for this. I would also be interested in references for proofs of combinatorial incompleteness of sets of combinators (I can see why the set $\mathcal{D}$ consisting of combinators with only one bound variable is incomplete, so these sets ought to contain more than just elements of $\mathcal{D}$).

[Expanding the comment into an answer.]

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

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

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

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

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

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

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

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


Difficulty of "learning" rare instances Is there any result showing that models (say SVM, Neural-Net, kNN, etc) will have difficulty in learning "rare" instances/tail phenomena?

In the classic PAC learning (i.e., classification) model, rare instances are not a problem. This is because the learner's test points are assumed to come from the same distribution as the training data. Thus, if a region of space is so sparse as to be poorly represented in the training sample, its probability of appearing during the test phase is low.

You'll need a different learning model, which explicitly looks at type-I and type-II errors, or perhaps some combined precision-recall score. Here again, I don't think there are any results indicating that a specific class of algorithms is particularly poorly suited for this task, but I could be wrong.

The closest I can think of is sensitivity to outliers --- AdaBoost is known to have this property, for example.


Fast approximate middle of points in a metric space? Given $N$ points $X_i$ in a metric space
and a measure of "middleness"
$ \qquad \qquad \mathsf{middle}( X_i ) \equiv
\frac{1}{N} \sum_j \mathsf{metric}( X_i, X_j ) $
can one find an $X_i$ near the middle of all $N$ points,
i.e. roughly minimizing $\mathsf{middle}( X_i )$,
in time and space both better than $O( N^2 )$ ?
If not in general, are there cases that can be done — trees, Euclidean metrics ?

Clarification: by "space better than $O(N^2)$" I mean,
are there approximate methods that give many nearby pairs
after looking at $O(N^{1+\epsilon})$ of all pairs ?
This is broader than just middles.
Of course, guarantees are then gone, or empirical or statistical.
But methods that work for $N$ 10000 or 1000000
would have broad application.
(Is that clear, is it worth a separate question ?)

There's a rather large literature on this problem. In brief, the problem you're looking at is called the $1$-median problem for a metric space. Since you're allowing for things "near" the middle, I'll assume approximations are ok. I also don't know what you mean by space less than $n^2$, since the input size itself is $n^2$.

Having said that, for an arbitrary metric space you can get a "sublinear" approximation (i.e one that runs in $o(n^2)$ time. Specifically, Piotr Indyk showed that you can get a $(1+\epsilon)$ approximation in time linear in $n$ and polynomial in $1/\epsilon$.

For structured spaces you can also do quite well. In Euclidean space, core-set techniques for the $k$-median problem (of which the 1-median is a special case) give you similar bounds (linear in n) to get arbitrarily good approximations. The caveat in this case is that the solution you get might not be one of the input points.


Self-referentially defined graph structures It is possible to define graphs $G$ such that whether an edge exists between two vertices $v_1$ and $v_2$ depends on non-local properties of $G$.

In particular, I am interested in directed graphs where an edge $(v_1, g(v_1, w))$  exists for each leaf vertex $w$ that is reachable from $f(v_1)$. Here, $f$ maps vertices to vertices, $g$ maps pairs of vertices to vertices.

Is there research on data structures and algorithms for working with such self-referentially defined graph structures?

"Dangerous reference graphs and semantic paradoxes", Rabern, Rabern & Macauley, Journal of Philosophical Logic.Here

http://philpapers.org/rec/RABDRG


Is there any programming language in which any equivalent program has a unique, decidable normal representation? Is there any programming language in which any equivalent program has a unique normal representation, and that normal representation is decidable?

Is other words, suppose A and B are programs written on that hypothetic language. Suppose, too, that for any input x, A(x) = B(x) - that is, those programs are equivalent. There should, then, be an algorithm Z for which Z(A) = Z(B).

Finally, that language should be able to encode boolean logic.

Is there such a language?

What you are asking for does not exist for a general-purpose programming language (by which we mean that the language can simulate Turing machines, and that Turing machines can simulate the language). Let me first recall the proof, and then turn the question around to discover something interesting.

We have to make your question just a bit more precise. Let us suppose that when you speak of inputs and outputs you mean strings, and that your programs are total (defined on all inputs). Now suppose there were an algorithm $Z$ which maps programs to programs (that is, strings to strings) such that, given any two valid programs $A$ and $B$ which map strings to strings, $Z(A)$ and $Z(B)$ are defined and
$$Z(A) = Z(B) \iff \forall x \in \mathtt{string} . A(x) = B(x).$$
Notice that I did not even require that $Z(A)$ be a program equivalent to $A$, it can be any string whatsoever, the important thing is that it maps $A$ and $B$ to the same string if, and only if, they represent equivalent programs. We can now solve the halting oracle as follows.

Let $A$ be a program which always outputs the string 0, i.e., $A(x) = 0$ for all $x \in \mathtt{string}$, and let $x_0 = Z(A)$. Consider any Turing machine $M$ and an input $y$. Because we assumed our language is Turing-complete, from a description of $M$ and a given input $y$ we can construct a program $B_{M,y}$, which computes as
$$B_{M,y}(n) = \begin{cases}
1 & \text{if $M(y)$ halts in fewer than $n$ steps of simulation}\\\\
0 & \text{otherwise}
\end{cases}$$
Notice that $B_M$ and $A$ are equivalent if, and only if, $M(y)$ diverges. But now we can decide whether $M(y)$ halts: if $Z(B_{M,y}) = x_0$ then $M(y)$ does not halt, otherwise it halts.

The above argument shows that programs of type $\mathtt{string} \to \mathtt{string}$ do not have canonical codes. How about other kinds of programs? Well, in some cases we obviously can produce canonical codes. For instance, a program $A$ of type $\mathtt{bool} \to \mathtt{bool}$ can be represnted canonically by the list $[A(\mathtt{false}), A(\mathtt{true})]$, from which the corresponding $Z$ can be easily constructed. If we replace $\mathbb{bool}$ with some other finite datatype, we also obtain canonical codes by simply listing the values of $A$.

But did you know that there are canonical codes for programs of type $(\mathtt{nat} \to \mathtt{bool}) \to \mathtt{bool}$? That is, given a program $A$ which takes as input infinite binary streams and outputs a bit, we can compute a corresponding canonical code $Z(A)$. See my blog post on juggling double exponentials where I explicitly construct $Z$.

We could also ask whether it is possible to make Turing machines somehow more powerful so that we can compute canonical code, and thereby solve the Halting problem. Well, adding an oracle will not help because exactly the same reasoning goes through. But we use infinite-time Turing machines (ITTM), then canonical codes for maps $\mathtt{string} \to \mathtt{string}$ are computable. The ITTM's therefore can solve the Halting problem for ordinary Turing machines, but they still cannot solve their own halting problem (which is not reducible to comparison of two functions $$mathtt{string} \to \mathtt{string}$). See my paper on embedding $\mathbb{N}^{\mathbb{N}}$ into $\mathbb{N}$ for details.

P.S. Apologies for blatant self-propaganda.


What's the difference between Moggi's computational metalanguage and Moggi's lambda calculus? This is a reference confusion. Sometimes I see people use the term "Moggi's computational metalanguage" to refer to the calculus presented by Moggi, and sometimes to "Moggi's computational lambda calculus". Sometimes they use $\lambda_{ml}$ and sometimes $\lambda_c$.

I've always assumed they are both the same thing, but reading the abstract from a talk by Katsumata and Moegelberg, it says:

  we show the fullness of Moggi's monadic translation from the computational lambda calculus $\lc$ with sums to the computational metalanguage $\lml$ with sums using TT-lifting and TT-closure operator.

Aren't these languages the same thing? Where are they introduced specifically with these names? It seems like Moggi sometimes talks about $\lambda_c$ model for what he calls a metalanguage, but then in other paper he talks about computational lambda calculus.

The terminology can be a bit confusing but yes there are two languages
in for instance Moggi's "Notions of Computations as Monads" (free link
here: https://core.ac.uk/download/pdf/21173011.pdf).

In that paper, the languages are called $\lambda_{ml}$, the
metalanguage, and $\lambda_{pl}$ the "programming language". I believe
$\lambda_{pl}$ plays the role of the computational lambda calculus but
I may be mistaken.
One confusing aspect is that both languages have an explicit type
constructor $T$ representing the monad, but they are used differently.

$\lambda_{ml}$ is a "pure" language with a monad $T$, i.e., all
manipulation of the monad is explicit in the types and the function
type $\tau_1 \to \tau_2$ is the type of pure functions. Observe the
bind rule (from figure 3 on page 9):

$$\frac{x   : \tau \vdash_{ml} e_1 : T \tau_1 \quad
        x_1 : \tau_1 \vdash_{ml} e_2 : T \tau_2 }
       {x :\tau \vdash_{ml} let_T x_1 \Leftarrow e_1 in e_2 : T \tau_2}$$

$e_1$ and $e_2$ are explicitly typed as terms of $T \tau_1, T\tau_2$
to mark that they are effectful. Every effectful expression is really
a pure term with monadic type. This is similar to how we program with
monads in Haskell where Haskell plays the role of the metalanguage and
the monad encodes effects but really we are always manipulating "pure"
terms (I put "pure" in quotes as Haskell has its own effects of
divergence and error).

We can see this in the semantics of the metalanguage: a term $x:\tau
\vdash_{ml} e : \tau'$ denotes a morphism $[\tau] \to [\tau']$, the
monad doesn't arise unless we mention it.

On the other hand, $\lambda_{pl}$ is intended to be an effectful
call-by-value programming language. As such a term $x : \tau
\vdash_{pl} e : \tau'$ is a possibly effectful term that returns
values of type $\tau'$, similar to languages like SML and OCaml. That
is why in the paper the function type is written $\tau \rightharpoonup
\tau'$ because it is the type of effectful functions, not pure
functions.

Compare the bind rule here (from figure 5 on page 11):
$$\frac{x   : \tau \vdash_{pl} e_1 : \tau_1 \quad
        x_1 : \tau_1 \vdash_{pl} e_2 : \tau_2 }
       {x :\tau \vdash_{pl} let x_1 \Leftarrow e_1 in e_2 : \tau_2}$$

The monad doesn't appear explicitly, but in the semantics this uses the
Kleisli extension of $e_2$.
In the semantics, we see that the terms of the programming language
are interpreted in the Kleisli category of the monad, so a term $x :
\tau \vdash_{pl} e : \tau'$ denotes a morphism $[\tau] \to T[\tau']$.

$\lambda_{pl}$ does include an explicit monad constructor $T$, which
SML and OCaml don't have as a primitive type constructor because $T a$
is equivalent to unit -> a because -> means effectful function.


What's the difference between the Actor Model of Concurrency and Communicating Sequential Processes I'm trying to wrap my head around what the real differences between the Actor Model of concurrency and Communicating Sequential Processes (CSP) model of concurrency.

So far the best that I have been able to come up with is that the Actor Model allows the number and layout of nodes to change while CSP has a fixed structure of nodes.

I believe one core difference is that in CSP, processes synchronize when messages are received (i.e. a message cannot be sent from one process unless another process is in a receiving mode), while the Actor model is inherently asynchronous (i.e. messages are immediately sent to other processes' address, irrespective of whether they're actively waiting on a message or not).

There should be another answer that is more well-developed, however.


Deciding whether a 2nfa halts on every input on every branch A 2nfa is a nondeterministic finite automaton that can move its head left or right on the input tape, or not.  Is the following language known to be decidable?
$$
\textit{H}_{\mathsf{2nfa}} = \{ \langle M \rangle \mid M \textit{ is a } \mathsf{2nfa} \textit{ that halts on every input and on every branch} \}
$$

Note:
This is not the same as the halting problem on 2nfa's:
$$ \mathit{HALT}_{\mathsf{2nfa}} = \{ \langle M, x \rangle \mid M \textit{ is a } \mathsf{2nfa} \textit{ that halts on every branch, running on } x \} $$
Albeit the two are related, and as follows:
$$ \langle M \rangle \in \textit{H}_{\mathsf{2nfa}} \iff \forall x, \langle M, x \rangle \in \textit{HALT}_{\mathsf{2nfa}} $$

I have attempted to write an algorithm deciding $\textit{H}_{\mathsf{2nfa}}$.  It looks for the sequence of transitions of $M$, that start and end at the same state and the overall displacement of the head along the sequence is $0$.  If there is such a loop, and some further details are satisfied, the algorithm decides that $M$ is not halting.
The problem is that I could not establish any bound on the length of the sequences to look for.  I guess that looking for sequences of length up to some function of $M$'s number of states should be enough.
Is there perhaps another, more elegant way? Even better, a known result to refer?

Lemma 1. $H_{\textsf{2nfa}}$ is decidable.

Proof.  Decide it as follows.  Given as input a two-way non-deterministic finite automaton $M_{\textsf{2nfa}}$:

Convert $M_{\textsf{2nfa}}$ into a two-way alternating finite automaton $M_{\textsf{2wafa}}$ such that the language of $M_{\textsf{2wafa}}$ is
$$L(M_{\textsf{2wafa}}) = \{x \in \Sigma^* : \text{ all execution paths of $M_{\textsf{2nfa}}$ on input $x$ halt }\},$$
that is, the set of inputs $x$ to $M_{\textsf{2nfa}}$ such that all execution paths of $M_{\textsf{2nfa}}$ on $x$ halt.  (An alternating finite automata has $\exists$-transitions and $\forall$-transitions.  Here we make every (non-deterministic) transition of $M_{\textsf{2nfa}}$ into a $\forall$-transition in $M_{\textsf{2wafa}}$, we don't use $\exists$-transitions, and we make the accept states of $M_{\textsf{2wafa}}$ be the halting states of $M_{\textsf{2nfa}}$.)
Convert $M_{\textsf{2wafa}}$ into an equivalent one-way NFA $M_{\textsf{nfa}}$. (See e.g. here.  I assume but have not verified that this conversion is computable. It appears to be computable, see the proof of Lemma 1, p. 296.)
Convert $M_{\textsf{nfa}}$ into an equivalent DFA $M_{\textsf{dfa}}$, and check whether $L(M_{\textsf{dfa}}) = \Sigma^*$ (all using standard techniques). Accept if so.  $~~\Box$


Attempted proofs of P vs NP What are the most recent (say in the last 3 years) attempts at disproving $P = NP$, and where can I find the papers?

Gerhard Woeginger has an up-to-date page with all attempts to (dis)prove the P vs NP question:
https://www.win.tue.nl/~gwoegi/P-versus-NP.htm


Solving a linear diophantine equation approximately Consider the following problem:

Input: a hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$, given by a vector $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ in standard binary representation.

Output: $\mathbf{x} \in \mathbb{Z}^n = \arg \min d( \mathbf{x}, H)$

In the above notation $d(\mathbf{x}, S)$ for $\mathbf{x} \in \mathbb{R}^n$ and $S \subseteq \mathbb{R}^n$ is defined as $d(\mathbf{x}, S) = \min_{\mathbf{y} \in S}{\|\mathbf{x} - \mathbf{y}}\|_2$, i.e. it's the natural euclidean distance between a set of points and a single point.

In words, we're given a hyperplane and we're looking for the point in the integer lattice that is closest to the hyperplane.

The question is:

  What is the complexity of this problem?

Note that polynomial time here will mean polynomial in the bitsize of the input. As far as I can see the problem is interesting even in two dimensions. Then it's not hard to see that it's enough to consider only those solutions $(x_1, x_2)$ with $0\leq x_1 \leq |a_1|/\mathsf{gcd}(a_1, a_2)$ but that's superpolynomially many options.

A closely related problem is solving a linear diophantine equation, i.e. finding an $\mathbf{x} \in \mathbb{Z}^n$ such that $\mathbf{a}^T\mathbf{x} = b$ or determining that no such $\mathbf{x}$ exists. So, solving a linear diophantine equation is equivalent to determining whether there exists a solution of value 0 to the problem I defined above. A linear diophantine equation can be solved in polynomial time; in fact even systems of linear diophantine equations can be solved in polynomial time by computing the Smith normal form of the matrix $\mathbf{A}$ giving the system. There are polynomial time algorithms that compute the Smith normal form of an integer matrix, the first one given by Kannan and Bachem.

To get intuition about linear diophantine equations we can consider the two dimensional case again. Clearly, there is no exact solution if $\mathsf{gcd}(a_1, a_2)$ does not divide $b$. If it does divide $b$, then you can run the extended GCD algorithm to get two numbers $s$ and $t$ such that $a_1s + a_2t = \mathsf{gcd}(a_1, a_2)$ and set $x_1 = sb/\mathsf{gcd}(a_1, a_2)$ and $x_2 = tb/\mathsf{gcd}(a_1, a_2)$. Now you can see how the approximate version is different: when $\mathsf{gcd}(a_1, a_2)$ does not divide $b$, how do we find integers $x_1, x_2$ such that distance between $(x_1, x_2)$ and the line $a_1x_1 + a_2x_2 =b$ is minimized?

The problem to me sounds a little like the closest vector problem in lattices, but I do not see an obvious reduction from either problem to the other.

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

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

This suggests the following procedure:

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

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


Where to learn more about what Theoretical Computer Science is? I am a graduate student in math, and theoretical computer science is a domain which I never understood what it is about because I couldn't find a good read about the topic. I want to know what this domain is actually about, what kind of topics it is concerned with, what prerequisites are needed to embark into it, etc. For now, I just want to know:

  What is a good introductory book to theoretical computer science?

Given that there is such a thing. If not, where should a mathematician who has basic knowledge about computer science (i.e. they know the basics of one or two programming languages) start if they want to understand what theoretical computer science is about? What do you recommend?

thanks!

First, "theoretical computer science" means different things to different people. I think for most users on this site, a historical caricature (which reflects some modern sociological tendencies) is that there is "Theory A" and "Theory B" (with no implied order relation between them): Theory A consists of the theory of algorithms, complexity theory, cryptography, and similar. Theory B consists of things like the theory of programming languages, theory of automata, etc. Depending on your tastes in mathematics, you may prefer one over the other (or like both equally). I am more familiar with "Theory A," so let me give some references there:

Start with Sipser's book. This will give you a good introduction to automata, Turing machines, computability, Kolmogorov complexity, P vs NP, and a few other complexity classes. It is very well-written (in my opinion, it is one of the best-written technical books ever)
For algorithms, I have a slighty preference for Kleinberg-Tardos, but there are many good introductory books out there. You might be especially interested in computational geometry, which has its own set of great books.
Given that you are a mathematics graduate student, a major branch of TCS that is missing from these books is algebraic complexity theory, which often is closely related to algebra (both commutative and non-commutative), representation theory, group theory, and algebraic geometry. There is a canonical text here, which is Burgisser-Clausen-Shokrollahi. It is somewhat encyclopedic, so may not be the best introduction, but I'm not sure there is a really introductory book in this area. You might also check out the surveys by Chen-Kayal-Wigderson and Shiplka-Yehudayoff.

After that, I'd suggest browsing through more advanced books on particular topics, depending on your mathematical taste:

Arora-Barak is more modern complexity theory (continues on where Sipser's book ends, so to speak), giving you a flavor of the techniques involved (mix of combinatorics and algebra, mostly)
Jukna's book on Boolean function complexity does similar, but more in-depth for Boolean circuit complexity in particular (very combinatorial in flavor)
Geometric complexity theory. See here or Landsberg's introduction for geometers.
O'Donnell's book Analysis of Boolean Functions has a more Fourier-analytic bent.
Cryptography. The more advanced mathematical aspects here are typically number theory and algebraic geometry. While these pure mathematical aspects represent only a small portion of cryptography, they are an important one that you might find interesting. Not being my area, I'm not sure of what a good starting book is here.
Coding theory. Here, the mathematical theory ranges from sphere-packing (see the book by Conway and Sloane) to algebraic geometry (e.g., the book by Stichtenoth). Again, not my area, so I'm not sure if these are the best starting points, but flipping through them you will quickly get the flavor and decide if you want to delve deeper.

And then there are many other mathematical topics that only appear in the research literature, like connections with foams, graph theory, C*-algebras (let me just point you to the Kadison-Singer conjecture), invariant theory, representation theory, quadratures, and on and on. See also these related questions

Resources for mathematicians hoping to learn more computer science
Are there any topics in theoretical CS that are more about pure math?
Applications of TCS to classical mathematics?
Solid applications of category theory in TCS?


Relationship between symmetry and computational intractability? The $k$-fixed point free automorphism problem asks for  a graph automorphism which moves at least $k(n)$ nodes. The problem is $NP$-complete if $k(n)=n^c$ for any $c$>0.

However, If $k(n)=O(\log n)$ then the problem is polynomial time Turing reducible to Graph Isomorphism Problem. If $k(n)=O(\log n/\log \log n)$ then the problem is polynomial time Turing-equivalent to the Graph Automorphism problem which is in $NPI$ and is not known to be $NP$-complete. The Graph Automorphism problem is Turing reducible to the Graph Isomorphism problem.

On the Complexity of Counting the Number of Vertices Moved by Graph Automorphisms,
Antoni Lozano and Vijay Raghavan

Foundation of Software Technology, LNCS 1530, pp. 295–306

It appears that computational  hardness increases as we increase the symmetry of the object we are trying to find (as indicated by the number of nodes that must be moved by the automorphism) . It seems this may explain the lack of polynomial time Turing reduction from the NP-complete version to Graph Automorphism (GA)

  Is there another example of a hard problem which supports this relationship between symmetry and hardness?

This isn't exactly the "same" relationship between symmetry and hardness, but there is a close relationship between the symmetries of a Boolean function and its circuit complexity.  See:

  Babai, L., Beals, R., and Takácsi-Nagy, P.  Symmetry and complexity, STOC 1992.

Here's what they show. Let $G_{i} \leq S_{i}$ be a sequence of permutation groups. Let $s(G_{i})$ denote the number of orbits of $G_{i}$ in its induced action on $\{0,1\}^{i}$ (by permutation of the coordinates).  Let $\mathcal{F}(G)$ denote the class of languages $L$ such that $L \cap \{0,1\}^{n}$ is invariant under $G_{n}$.  Then all languages in $\mathcal{F}(G)$ have circuits of size at most $poly(s(G))$ and depth at most $poly(\log(s(G))$, and this is essentially tight.

In the opposite direction, several $NP$ problems whose witness sets have lots of symmetries end up being in $coAM$ (like $GI$), and so are not $NP$-complete unless $PH$ collapses.  In fact, the following paper shows that $NP$ problems whose witness sets have lots of symmetries are low for $PP$:

  Arvind, V., Vinodchandran, N. V. The counting complexity of group-definable languages. Theoret. Comput. Sci. 242 (2000), no. 1-2, 199--218.

(Note: whether or not "low for $PP$" indicates "unlikely to be $NP$-complete" is a little up in the air, as far as I know. Toda and Ogiwara showed that $PP^{PH} \subseteq BP \cdot PP$.  So under the "derandomization" assumption $BP \cdot PP = PP$, $NP$ is in fact low for $PP$, so being low for $PP$ is no obstacle to being $NP$-complete.  On the other hand, there is an oracle due to Beigel relative to which $NP$ is not low for $PP$.)

In a similar vein as the above, if every polynomial-time decidable equivalence relation has a polynomial-time complete invariant (function $f$ such that $f(x) = f(y)$ iff $x \sim y$), then any $NP$ problem whose witnesses have lots of symmetries reduces to the hidden subgroup problem for the automorphism group of its witnesses.  Admittedly, the hypothesis here is rather unlikely to hold, but it does give some connection between symmetry and quantum complexity.

Finally, the Mulmuley-Sohoni Geomectric Complexity Theory program is essentially about using symmetry to prove hardness, though the symmetry-hardness connection there is more subtle and less direct.


Factoring semiprimes whose factors very close to a power of two Are there any factorization algorithms that run well on numbers $N = pq$ where $p,q$ are prime and $p = 2^b - k_p, q = 2^b - k_q$ for very small $k_p,k_q$? What about $p = 2^b + k_p, q = 2^b + k_q$ for very small $k_p,k_q$?

If $0 \le k_p < 2^{b/2}$ and $0 \le k_q < 2^{b/2}$, it's easy to factor such numbers.  Consider:

$$N = pq = (2^b-k_p)(2^b-k_q) = 2^{2b} -(k_p+k_q) 2^b + k_p k_q.$$

Under the stated conditions, you can read off the values of $k_p k_q$ and $k_p+k_q$ from the binary representation of $N$, since $0 \le k_p k_q < 2^b$ and $0 \le k_p+k_q < 2^b$.  In particular, $k_p k_q$ can be obtained as $N \bmod 2^b$, and then you can compute $k_p + k_q$ as $(2^{2b} - N + k_p k_q)/2^b$.  Once you know those values, you can solve for $k_p,k_q$ by solving a quadratic equation (you have a system of 2 equations in 2 unknowns; simple algebra can be used to recover the value of the unknowns).  Once $k_p,k_q$ are known, the factorization of $N$ is immediately revealed.


Techniques for showing that problem is in hardness "limbo" Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this is difficult:

Show that the problem is GI-complete (GI = Graph Isomorphism)
Show that the problem is in $\mathsf{co-AM}$. By known results, such a result implies that if the problem is NP-complete, then PH collapses to the second level. For example, the famous protocol for Graph Nonisomorphism does exactly this.

Are there any other methods (maybe with different "strengths of belief") that have been used ? For any answer, an example of where it has actually been used is required: obviously there are many ways one might try to show this, but examples make the argument more convincing.

Showing that your problem is in coAM (or SZK) is indeed one of the main ways to adduce evidence for "hardness limbo."  But besides that, there are several others:

Show that your problem is in NP ∩ coNP.  (Example: Factoring.)
Show that your problem is solvable in quasipolynomial time.  (Examples: VC dimension, approximating free games.)
Show that your problem is no harder than inverting one-way functions or solving NP on average.  (Examples: Lots of problems in cryptography.)
Show that your problem reduces to (e.g.) Unique Games or Small-Set Expansion.
Show that your problem is in BQP.  (Example: Factoring, though of course that's also in NP ∩ coNP.)
Rule out large classes of NP-completeness reductions.  (Example: The Circuit Minimization Problem, studied by Kabanets and Cai.)

I'm sure there are others that I'm forgetting.


Ramsey's theorem for collections of sets While exploring different techniques of proving lower bounds for distributed algorithms, it occurred to me that the following variant of Ramsey's theorem might have applications – if it happens to be true.

Parameters: $k$, $K$, $n$ are given, and then $N$ is chosen to be sufficiently large. Terminology: an $m$-subset is a subset of size $m$.

Let $A = \{1,2,...,N\}$.
Let $B$ consist of all $k$-subsets of $A$.
Let $C$ consist of all $K$-subsets of $B$.
Assign a colouring $f\colon C \to \{0,1\}$ of $C$.

Now Ramsey's theorem (the hypergraph version) says that no matter how we choose $f$, there is a monochromatic $n$-subset $B'$ of $B$: all $K$-subsets of $B'$ have the same colour.

I would like to go one step further and find a monochromatic $n$-subset $A'$ of $A$: if $B' \subset B$ consists of all $k$-subsets of $A'$, then all $K$-subsets of $B'$ have the same colour.

Is this true or false? Does it have a name? Do you happen to know any references?

If it is false for some trivial reasons, is there a weaker variant that resembles this claim?

Observed that the question is non-trivial only when k, K both larger than 1;
for the case k = 1 or K = 1, it is just the normal Ramsey theorem, which is true for all n.
Also, we only have to deal with the case that ${n \choose k}$ > K, otherwise the theorem is true since there is at most one ${n \choose k}$-subset of B' constructed by an n-subset A' of A.

First we prove the theorem is false for all k > 1, K > 1, and any n satisfies ${n \choose k}$ > K > $({n-1 \atop k})$.

In order to construct a counterexample, for any large N and A = [N], we have to construct a coloring function f such that for all n-subset A' of A, if B' consists of all k-subsets of A', some of the K-subsets of B' have different colors. Here we have the following observation:

  Observation 1. Under the conditions that k, K > 1 and ${n \choose k}$ > K > $({n-1 \atop k})$, any K-subset of B is a subset to at most one B' constructed by a n-subset A' of A.

The observation can be easily seem by representing as hypergraphs. Let A be nodes of the graph G, an n-subset A' of A is the node set of a complete n-subgraph in G. B' is the set of k-hyperedges in the complete subgraph (a 2-hyperedge is a normal edge), and K-subsets of B' are the every combinations (there are $({|B'| \atop K})$ in total, where |B'| = ${n \choose k}$) of K k-hyperedges. The observation states: any K-tuple of hyperedges in G belongs to at most one complete n-subgraph, which is obvious for ${n \choose k}$ > K > $({n-1 \atop k})$, since any two complete n-subgraphs intersect at most n-1 nodes, with at most $({n-1 \atop k})$ hyperedges.

Then we can assign different colors within K-subsets C' of a particular B' constructed by a n-subset A', since any element in C' will not occur as another K-subset of B'' constructed by a n-subset A''. For any K-subset of B not constructed by any n-subset of A, we assign random color on it. Now we have a coloring function f, with the property that no B' constructed by n-subset of A is monochromatic, that is, some of the K-subsets of B' have different colors.

Next we show that the theorem is also false for all k > 1, K > 1, and any n satisfies ${n \choose k}$ > K. Here the only difference is n may be chosen so large, that K > $({n-1 \atop k})$ is not true. But by another simple observation:

  Observation 2. If some B' constructed by an n-subset A' of A is monochromatic, then every B'' constructed by an n'-subset A'' of A' for n' < n is also monochromatic.

Hence we can assume the theorem holds on the larger n, apply the second observation, and concludes a contradiction by the first case, by setting n' satisfies $({n' \atop k})$ > K > $({n'-1 \atop k})$; such n' must exist by the fact that $({n \atop k})$ > K and K > $({k \atop k})$, n' must lie between n and k+1.


In the neutral zone between polynomial and sub-exponential What are examples of problems that are known to be sub-exponential, but

are known to be non-polynomial, or
are not known to be polynomial?

EDIT. Here is what I mean by sub-exponential (apologies for leaving this open). A function $f:\mathbb{N}\to\mathbb{N}$ is subexponential if $$f(n) = 2^{n^{o(1)}}.$$ (Thanks to Emil Jerabek for his help in the comment section below!)

Graph Isomorphism is known to be in quasipolynomial time but not known to be in polynomial time: https://arxiv.org/abs/1512.03547
You can also come up with synthetic problems by the time hierarchy theorem, which essentially states that there are problems at any (deterministic) time complexity but not below: https://en.wikipedia.org/wiki/Time_hierarchy_theorem


Upper bound on the pseudoentropy of any distribution From here:

  The notion of pseudoentropy is only useful, however, as a lower bound on the computational entropy in a distribution. Indeed, it can be shown that every distribution on $\{0,1\}^n$ is computationally indistinguishable from a distribution of entropy at most $poly (\log n)$.

How is that any distribution on $n$-cube can be computationally indistinguishable from one with entropy at most $poly(\log n)$?

Take any distribution $D$ on $\{0,1\}^n$. Sample $k(n)$ points $x_1, \cdots, x_{k(n)}$ independently from $D$ and let $\tilde D$ be the uniform distribution that gives a random $x_i$. Then, if $k(n)$ is super-polynomially large e.g. $k=n^{\log n}$, you cannot distinguish $D$ and $\tilde D$ using only $\mathrm{poly}(n)$ samples. Hence $D$ is computationally indistinguishable from a distribution $\tilde D$ with entropy $\mathrm{poly}\log(n)$.


Conjecture about two counters automata I would like to prove (or disprove) the following conjecture:

Conjecture: a two counter automata (2CA) cannot decide the following language:

$L = \{ n \mid $ the ternary and binary representations of $n$ have both even length or odd length$\}$

A 2CA can easily check if the binary representation has even or odd length (just keep dividing by two and update an "even length" flag after each division); in the same manner it can check if the ternary representation has even or odd length (just keep dividing by three and update an "even length" flag after each division).

But in order to calculate one of them it must destroy its input, and cannot recover it to calculate the other; so it seems that there is no way to decide $L$.

Do you know a technique that can be used to prove the conjecture?
Or can you disprove the conjecture building a 2CA that decides $L$?

I tried the same approach followed by Ibarra to prove that a 2CA cannot decide $\{n^2\mid n \geq 1\}$, but it seems not the right way.

Note: for simplicity a 2CA is equivalent to a program with one variable $c$  that initially contains the input and the following instruction set:

INC: add one to the variable;
DEC: decrement $c$ (only if it is greater than zero);
JZ  $lab$: if $c$ is zero jump to label $lab$ otherwise continue;
MUL $K$: multiply $c$ by the costant $K$;
DIV $K [, lab_0, lab_1,...,lab_{K-1}]$: divide $c$ by the constant $K$ and store the  quotient to $c$ ($c = \lfloor c / K \rfloor$); possibly jump to different labels according to the remainder ($c \bmod K$);
GOTO $lab$: unconditional jump;
HALT Accept|Reject: halt and accept or halt and reject.

For example a program to check if the binary representation of $n$ has even length is:

   loop: JZ even   // test if n = 0
         DIV 2
         JZ odd    // test if n = 0
         DIV 2
         GOTO loop
   even: HALT Accept
    odd: HALT Reject

(we can build an equivalent 2CA)

So people keep nagging me to post this even though it only solves a simplified
version of the problem.  Okay then :)

At the end of this, I will put some of what I learned from the paper of Ibarra and Trân, and why that method breaks down on our general problem, but perhaps still gives some useful information.

But first, we'll look at the simpler problem of trying to decide the set

$L = \{ 2^n \mid $ the ternary and binary representations of $2^n$ have both even length or odd length$\}$

Note how this has $2^n$ rather than $n$ as in the original problem.  In particular if the input number is not a power of 2, we want to reject it rather than attempt to calculate its length in any base.

This greatly simplifies matters: If the original number is written prime factorized as $2^{v_2} 3^{v_3} 5^{v_5} 7^{v_7} ...$, then for all the $v_i$ except $v_2$ we just need to check that they are all $0$.

This allows us to solve this simplified problem by using a wrapper around the old method (by Minsky I assume) of encoding the state of a $k$-counter automaton in the exponents of the prime factorization of the single variable of a multiplication/division automaton, which as noted in the OP above is pretty much equivalent to a 2-counter automaton.

First, we need a $k$-counter automaton to wrap.  We will use 3 counters, named $v_2$, $v_3$ and $v_5$.

The automaton will accept iff for the initial counter values, the ternary and binary representations of $2^{v_2}$ have both even length or odd length, and both $v_3$ and $v_5$ are zero.  When it accepts it will first zero all its counters.

Here is some code for that, in an assembly format similar to the OP (I've just added variables to the instructions).  I haven't actually tested it, since I have nothing to run it with, but I consider this a formality: 3-counter automata are well known to be Turing-complete, and to be able to construct any computable function of one of their initial values.

// Check that v3 and v5 are both zero.
                JZ v3, check5
                GOTO reject
check5:         JZ v5, init3
                GOTO reject
// Decrement v2 until it is zero, constructing 2^n in the process.  If 2^n
// was even, we will then pass to even2 with 2^n in v3; If 2^n was odd, we
// will pass to odd2 with 2^n in v5.
init3:          INC v3          // Set v3 to 1 = 2^0 to start with.
even1:          // We have decremented v2 an even number of times so far.
                // 2^decremented amount is in v3.
                JZ v2, odd2
                DEC v2
dup3to5:        JZ v3, odd1
                DEC v3
                INC v5
                INC v5
                GOTO dup3to5
odd1:           // We have decremented v2 an odd number of times so far.
                // 2^decremented amount is in v5.
                JZ v2, even2
                DEC v2
dup5to3:        JZ v5, even1
                DEC v5
                INC v3
                INC v3
                GOTO dup5to3
// The second part checks the ternary length of 2^n, which starts out in v3
// or v5 according to whether the *binary* length of 2^n (i.e. n+1) was odd
// or even.
odd2:           // v3 needs to have odd ternary length to accept.
                // It is simplest to consider 0 to have even length in both
                // binary and ternary.  This works out as long as we're
                // consistent.
                JZ v3, reject
trisect3to5:    DEC v3
                DEC v3
                JZ v3, even2
                DEC v3
                INC v5
                GOTO trisect3to5
even2:          // v5 needs to have even ternary length to accept
                JZ v5, accept
trisect5to3:    DEC v5
                DEC v5
                JZ v5, odd2
                DEC v5
                INC v3
                GOTO trisect5to3
accept:         HALT Accept
reject:         HALT Reject

The next step is then to re-encode the above in the exponents of a single variable automaton.  As the result is pretty long, I'll just describe the general method, but a full version (slightly "optimized" in spots) is on my website.

                JZ vp, label
                DEC vp
next:           ...

becomes (basically divide by p, and then do cleanup to undo if the division wasn't even):

                DIV p, next, ..., newlabel.fp-1
newlabel.f1:    MUL p
                GOTO newlabel.i1
...
newlabel.fp-1:  MUL p
                INC
newlabel.ip-2:  INC
...
newlabel.i1:    INC
                GOTO label
next:           ...

INC vp becomes MUL p. Individual JZ and DEC can first be changed into the combined form.  GOTO label and HALT Reject are unchanged.

HALT Accept would be unchanged, except that in our case we still have one final check to do: we need to ensure that there are no prime factors in the number other than 2,3 and 5.  Since our particular 3-counter automaton zeros the counters it uses when it accepts, this is simple: just test that the final variable is 1, which can be done by jumping to the code

                DEC     // BTW it cannot be zero before this.
                JZ accept
                HALT Reject
accept:         HALT Accept

The code on my website also has an initial check that the number isn't zero, which I've just realized is redundant with the v3, v5 zero checks, oh well.

As I mentioned, the above method works for the simplified problem, but it really has no chance of working for the general one, because:  In the general problem the precise value of every prime's exponent counts for deciding its general size and thus which lengths it has in various bases.  This means that:

We have no "free" primes to use for counters.
Even if we did have free primes for counters, we don't really have a way to extract all the necessary information from the infinitely many other primes whose exponent values do matter.

So let's end with an explanation of the gist of the general method from the above linked paper by Ibarra and Trân (freely downloadable version) for how to prove that certain problems aren't solvable by a 2CA, and how it annoyingly breaks down in our case.

First, they modify every 2CA into a "normal form", in which the two counters switch in "phases" between one only increasing and the other only decreasing until it reaches zero.  The number of states $s$ of this normalized automaton plays an important role in the estimates.

Then, they analyze this automaton to conclude that they can construct certain arithmetic sequences of numbers whose behavior are linked.  To be precise (Some of this is not stated as theorems, but is implicit in the proof of both of their two main examples):

If a number x is accepted by the automaton, without the size $v^x_i$ of the nonzero counter at the beginning of a phase $i$ ever going $\leq s$, then there exists an integer $D>0$ such that all the numbers $x + n D$, $n\geq 0$ are accepted.
If a set $X$ contains at least $s^2+1$ accepted numbers such that for each number $x\in X$ there is a phase $i$ such that $v^x_i\leq s$, then we can find $p, r\in X$, and integers $K_1,K_2$ such that

For every integer $n\geq 0$, either $p + n K_1$ and $r + n K_2$ are both accepted by the automaton, or both are rejected.

(Thoughts:

They require $x>s$ for $x\in X$ but I think this is actually unnecessary.  Actually so is that they are accepted.
Most of this should also hold for rejected numbers, as long as the rejection is by explicit halting rather than nontermination.)

For their own examples they also frequently use the fact that $D,K_1,K_2$ have no prime factors $>s$.  To prove impossibility, they then derive contradictions by showing that such arithmetical sequences cannot exist.

In our problem, getting a contradiction from this breaks down with the second case.  If we have $K_1 = K_2 = 6^k$, where $k$ is large enough that no number between $p$ and $r$ is divisible by either $2^k$ or $3^k$, then there will also be no powers of 2 or 3 between $p + 6^k n$ and $q + 6^k n$, so they are either both accepted or both rejected.

Point 1 can still be shown to be impossible, because powers of 2 and 3 mostly grow further and further apart.  And I believe I can show the second case impossible if $K_1\neq K_2$ (I've emailed @MarzioDeBiasi the argument).  So perhaps someone could use this information to restrict the form of the automaton further, and finally derive a contradiction from that.


Does Approx Carathéodory's theorem implies dimensionality reduction Carathéodory's theorem says that if a point $x$ of $R^d$ lies in the convex hull of a point set $P$, then there is a subset $P′ \subseteq P$ consisting of $d + 1$ or fewer points such that $x$ can be expressed as a convex combination of $P′$.

A recent result by Barman (see paper) shows an approximate version of the above theorem.
More precisely,  given a set of points $P$ in the $p$-unit ball with norm $p \in [2,\infty)$, then for every point $x$ in the convex hull of $P$ there exists an $\epsilon$-close point $x'$ (under the $p$-norm distance) that can be expressed as a convex combination of $O\left(\frac{p}{\epsilon^2} \right)$ many points of P.

Now, my question is that does the above result implies (or have some connection with) some kind of dimensionality reduction for the points in the convex hull of $P$. It seems intuitive to me (however I don't have a formal proof of it) - as for any  point $x$ inside the $P$ there is a point (say) $x'$ in a close neighborhood of $x$ which can be written as convex combination of constant many points of $P$, which in some sense dimensionality reduction of $x'$.

Pls let me know if I am able put my question clearly.

Thanks.

The approximate Caratheodory theorem goes back to the 60s, and probably way earlier than that (it follows for example from the mistake bound of the preceptron algorithm analysis). As for the dimensionality reduction, the answer is no - the supporting subsets are different subsets, and their number is too large. In particular, the number of possible subsets is $n^{O(1/\epsilon^2)}$ - but there is some connection...

Specifically, let $P$ be a set of $n$ points in high dimenionsional Euclidean space of diameter $1$. Let $Q$ be an $\epsilon$-net in the convex-hull of $P$. That is, any pair of points of $Q$ is in distance at least $\epsilon$ from each other, and every point of $CH(P)$ is in distance at most $\epsilon$ from some point of $Q$.

Now, by the approximate Caratheodory theorem, we know that $|Q| = n^{O(1/\epsilon^2)}$. Now, imagine that you do some experiment, and with probability half the experiment succeeds for half the points of $Q$ (or, more formally, half the pairs of $Q \times Q$ -- since we look on vectors formed by differences of points of $Q$). How many times do you have to repeat the experiment till all the points are served? Well, roughly $\log_2 |Q| = O(\epsilon^{-2} \log n)$, which is, surprise surprise, the target dimension in the JL lemma. This is of course, does not imply the JL lemma - it is somewhat of a "coincidence" - a wrong calculation that gives the right bounds...

There is a useful lesson here however - a set of $n$ points in high dimensions, induces roughly $n^{O(1/\epsilon^2)}$ points that are $\epsilon$-distinct, independent of the ambient dimension.


Complexity of Comparative Independent Set Decision Problem Consider the following problem:

Input: (G1, G2) where G1 and G2 are undirected graphs

Question:  Is the size of the max independent set of G1 at least as large as the size of the max independent set of G2?

This seems like a fairly natural question to ask, and yet I have been unable to find a complexity class for which this problem is complete.  Does anyone know of such?  As a starting point, it is readily seen that the problem is NP-hard and contained in P with access to an NP oracle with log many queries.

This problem is indeed complete for the class of polynomial time Turing machines with access to an NP oracle with log many queries (also known as $\Theta_2^p$).  The result appears in a 2000 FST TCS paper by Spakowski and Vogel titled "$\Theta_2^p$-Completeness: A Classical Approach for New Results."  The proof presented there and a proof that I arrived at independently both rely on the $\Theta_2^p$-completeness criterion of Wagner ("Bounded Query Classes" SIAM Journal on Computing archive Volume 19 Issue 5, Oct. 1990).