What are the current best upper bounds of #P? #P is the class of counting problems for problems in NP.  In other words, a solution to #P returns the number of solutions to a particular problem in NP.

I'm wondering if there have been any studies on the worst-case behaviors of current best solutions to problems in NP.  My focus in the past has been on 3-SAT, so I am particularly interested in the time it takes to count 3-SAT solutions in the worst case.  However, I ask in general, What are the current best upper bounds for any (#P-complete) problem in #P?

One such algorithm for $\#3\operatorname{SAT}$ is due to Kutzkov.


Generalization and instantiation of types in Hindley-Milner type inference I’m currently reading Heeren, B., Hage, J., & Swiestra, D. (2002). Generalizing Hindley-Milner Type Inference Algorithms in an attempt to understand Hindley-Milner-style type inference.

I'm struggling with two concepts early in the paper, the first is
generalization of a type. From the article:

  Generalizing a type $\tau$ with respect to a type environment $\Gamma$
  entails the quantification of the type variables that are free in
  $\tau$ but do not occur in $\Gamma$:

  $$generalize(\Gamma,\tau) =_{def}\;\forall\vec{\alpha}.\tau
 \;\;\text{ where } \vec{\alpha} = freevars(\tau)-freevars(\Gamma)$$

  In the literature, generalization is sometimes referred to as
  determining the closure of a type. In fact, these different notations,
  e.g. $\Gamma$($\tau$) in [DM82] and Clos$\Gamma$($\tau$) in [LY98], all express the same.

Another explanation is that generalize “abstracts a type over all type variables which are free in the type but not free in the given type environment.”

However, I fail to see what this accomplishes and when you want to do this, and would be very grateful if someone can point me in the right direction.

Another concept is instantiation, explained in the following manner:

  An instantiation of a type scheme is obtained by the replacement of
  the quantified type variables by fresh type variables:
  $$instantiate(\forall \alpha_1\ldots\alpha_n.\tau =_{def}\; [\alpha_1 := \beta_1,\ldots,\alpha_n := \beta_n]\tau \;\;\text{ where } \beta_1,\ldots,\beta_n \text{ are fresh}$$
  A type
  $\tau_1$ is a generic instance of a type scheme $\sigma = \forall\vec{\alpha}.\tau_2$ if there exists
  a substitution S with S$\beta$ = $\beta$ for all $\beta \in freevars(\sigma)$ such that $\tau_1$ and
  S$\tau_2$ are syntactically equal.

Does this simply mean that you replace all bound type variables with globally unique variables in order to avoid accidental collisions, or is there more to it?

However, I fail to see what this accomplishes and when you want to do this, and would be very grateful if someone can point me in the right direction.

When you define the function x -> x and first apply it to an integer you don't want the type of that identity function to be specialized to int -> int. That's why you generalize it. Note that this is done at let bindings.


The complexity of a multi-objective shortest path problem I have the following shortest path problem.

Consider a directed graph with $n$ levels.  Each level has $m$ nodes.  Each node at level $i$ is connected to all nodes at level $i+1$.  Let us also make a starting node that is connected to all nodes at level $1$ (the first level).

Each edge is labelled by a pair of non-negative integer weights.  Each level $i$ has a single non-negative integer label which we call $L_i$.

The goal is to minimize the shortest path with respect to the first weight in each edge weight pair from the starting node to the last level while ensuring that the weight of the path from the starting node with respect to the second weight in each edge weight pair is no more than $L_i$ at each level $i$.

Has this problem been studied? Is it known to be NP-hard?

It is NP-hard by reduction from Partition.

Let $x_1,\dots,x_n$ be the partition instance.

Create a graph on levels $0,1,\dots,n$ with level $0$ containing the start vertex $s$, and level $i$ containing two vertices, $a_i$ and $b_i$.

Every path from $s$ to a vertex in the last level corresponds to a partition of $x_1,\dots,x_n$ into two blocks, $A$ and $B$, as follows:
If the path goes through $a_i$, then $x_i$ is placed in $A$, otherwise the path must go through $b_i$, and $x_i$ is placed in $B$.
Conversely, every partition is realized by some path in this way.

For every edge to $a_i$ from the level below, let the cost be $(x_i,0)$, and for every edge to $b_i$ from the level below, set the cost to $(0,x_i)$.
Finally, set $L_i = \sum_{i=1}^n x_i/2$.
Now the partition instance has a balanced partition if and only if there is a solution to the path problem with cost $\le \sum_{i=1}^n x_i/2$.

(Edit: I originally gave a reduction from the shortest weight-constrained path problem, and then to answer a comment; a reduction from partition to the shortest weight-constrained path problem. However, the last reduction is enough by itself.)


List of strongly NP-hard problems with numerical data I am looking for strongly NP-hard problems for a reduction.
So far I have found the following problems:

3-partition problem
bin-packing problem
Numerical 3-dimensional matching
TSP
Any NP-complete problem without numerical data, e.g., SATISFIABILITY, HAMILTONIAN
CYCLE, 3-COLOURABILITY.

Does anyone know of a list of strongly NP-hard problems?

If not, let's build one here.
Do you know of other problems with numerical data that are strongly NP-hard?

I'm particularly interested in strongly NP-hard problems on weighted graphs.

Here is a strongly $NP$-complete problem (with numerical data as you requested):

Schur Triples problem:

Input: list of 3N distinct positive integers

Question: Is there a partition of the list into N triples $(a_i, b_i, c_i)$ such that $a_i + b_i= c_i$ for each triple $i$?

The condition that all numbers must be distinct makes the problem very interesting and McDiarmid calls it a surprisingly troublesome .


What constitutes denotational semantics? On a different thread, Andrej Bauer defined denotational semantics as:

  the meaning of a program is a function of the meanings of its parts.

What bothers me about this definition is that it doesn't seem to single out what is commonly thought of as denotational semantics from what is commonly thought of as non-denotational semantics, namely structural operational semantics.

More precisely, the key ingredient here is modularity, or compositionality, of the semantics, or put differently, the fact that they are defined according to the abstract structure of the program.

As most (all?) formal semantics nowadays tend to be structural, is this the required definition?

So, my question is: What is denotational semantics?

The distinction I personally make between denotational and operational semantics is something like this:

denotational semantics is mathematical and equational. The details of the reduction matter less than the end result, which is a timeless value in some mathematical space.
operational semantics is algorithmic. It unfolds in individual steps in time.  The process is part of the the meaning, and the end result is just a distinguished step in that process.

The difference can sometimes be quite subtle, and it can be hard to tell if it is just a difference in style, or in substance.

However, we can see how Andrej's compositional definition follows more naturally from the denotational definition, and we can also easily imagine a non-confluent, non-compositional semantics that still meets the operational definition.


Longest circuit in a directed graph I have a very large directed graph (1M nodes) I am wondering what is the best algorithm for finding the longest (most number of nodes) cycle in the graph?

One million nodes is far too much for any exact method that I know. This being said, I expect your graph does not have a very large number of edges, so the best is to begin by applying repeatedly this algorithm :

If you have a vertex in your graph that has not outgoing edge, or that has no incoming edge, remove it from your graph as no cycle can go through it. Take care, as removing such vertices can lead to remove other vertices that had edges in both direction before !

This should reduce dramatically the size of your graph (look at what is called "topological sort"). Once this is done, you can compute the different strongly connected componets, as your cycle is included in one of them. Then, you can do the computations separatedly. Perhaps the splitting of your graph will have created new vertices that you can remove.

Iterate through these two algorithms until you can do no other operation in your graph. When it is done, come back here and ask your question again giving the new number of vertices.

When you do so, do not count the number of vertices having exactly one incoming edge and one outgoing edge. They do not change the complexity of the problem.

If after all this your graph is still 1M vertices large, it begins to really be desperate :-)

Nathann


PCVRP with prizes reduced over time Hej guys,

I'm working on customizing a Vehicle Routing Problem for a practical case, which is characterized as follows:

The set of customers does not change over time, but their respective prizes are degressing in a  non-linear fashion (deterministic).
Traveling costs do not change.
Need to visit every customer exactly once.

So I've been digging through tons of papers and such, but I can't find anything similar to the given case .. The Dynamic VRP goes way too far, with stochastics and redefining the routes in an ongoing fashion, which I do not need in this special case, because the degression of prizes is deterministic. I thought about the Traveling Repairman Problem, but I can't come up with a way to use it .. The VRP with Time Windows seems to be a completely different case as I have no opening or closing times.

Maybe someone got any hints for me ? I'm pretty sure this case has been dealt with, as it seems to be practically relevant.

Any help is appreciated !

Edit: as mentioned in the comments I should provide a sufficient version of the VRP:

Input:
N: given set of customers,
D: given set of demands of said customers,
C: given set of traveling costs, where c_ij is the weight of the arc (i,j),
M: maximum number of vehicles that may be used,
V: fixed costs of using a vehicle,
Q: capacity of a vehicle,
P: set of prizes for every customer,
f(t): a function describing the degression of the prizes,
(I'm not sure yet whether I want to visit every customer or not)

Output:
Optimal routes with the following objective:

minimize total costs of travel,
minimize number of vehicles used,
maximize sum of prizes.

Whether finding the optimal solution is possible or not is not really of interest in the first place.

[As I looked for questions related to the VRP, TSP and similar models, these were posted in theoretical CS, but now I see that this section is definitely not the right one for me ..]

This has been called "Discounted Reward." In my brutish opinion, steer toward the CS guys and away from the OR guys. I just like the lit better.

See: "Approximation Algorithms for Orienteering and Discounted-Reward TSP." FOCS 2003 Which I just stole from my colleague's desk.

They model reward as $\lambda^{-t}$, where $t$ is time, and $\lambda$ is constant, but otherwise it is the standard orienteering formulation: Maximize reward, subject to a budget, or minimize budget subject to a reward constraint.


Approximating max degree $3$ perfect matching count? We do not have a deterministic constant factor approximation scheme for general $n\times n$ $0/1$ permanent.

What is the best factor in deterministic approximation schemes if we only care counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?

Dagum and Luby show (using a construction credited to Dahlhaus and Karpinski) how to construct, given a bipartite graph $G$, a bipartite graph $G'$ of maximum degree $3$ such that $G'$ has exactly as many perfect matchings as $G$ (see Theorem 6.2.). Then from $G'$ you can construct a graph $G''$ with average degree arbitrarily close to $2$ and twice as many perfect matchings as $G'$, as I explained here. Both constructions are in polynomial time. Therefore, the best polytime deterministic approximation to the number of perfect matchings of a graph of maximum degree 3, and average degree in $[2,3]$ is equal to the best polytime deterministic approximation to the permanent of a 0-1 matrix. As far as I know, this is the factor $2^n$ approximation achieved by Gurvits and Samorodnitsky.

(It may be helpful to note that a $\exp(n^\varepsilon)$ approximation for $\varepsilon < 1$ would imply an FPTAS.)


"Interesting" categories whose internal logic is a dependent-linear type theory Dependent-linear type theories may be a functional programmer's dream, but is it categorically interesting, i.e. is it the internal language of an "interesting" category? By "interesting", I mean a category that arises naturally in mathematics or computer science, similar to how intuitionistic type theory is the internal logic of toposes or linear logic is the internal logic of $\mathbf{PShMod}_X$, which is ubiquitous in algebraic geometry. In other words, can we give an interesting and "natural" categorical model of a dependent-linear type theory?
Any (reasonable) flavor of dependent-linear type theory is fine, as long as it has a linear layer and a dependent layer. Examples include Atkey's quantitative type theory and Krishnaswami, Pradic & Benton's dependent-linear calculus (POPL '15).
(Sorry, but I don't know whether this site or MathOverflow would be a better forum for this question. But it seems that I might attract more experts on this site...)

Take any small symmetric monoidal category $V$.
Then the category of $V$-valued presheaves will (a) have closed monoidal structure (via Day convolution), and (b) have enough stuff (inherited from $\mathrm{Set}$) to interpret dependent types.  This gives you enough structure to interpret something like our LNL calculus pretty easily, because there is a nice adjunction between $\mathrm{Set}$ and this category given by the constant functor ($F(X) = V \mapsto X$) and the global elements functor ($G(A) = \Pi X : Obj(V). A_X$).
Matthijs Vakar wrote a nice paper, A Categorical Semantics for Linear Logical Frameworks, which describes the categorical models of this style of calculus in detail.


Probabilistic (randomized) algorithms before "modern" computer science appeared Edit: I choice the answer with highest score by December 06, 2012.

This is a soft question.

The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms?

In this wiki entry, Rabin's algorithm for the closest pair problem in computational geometry was given as the first randomized algorithm (year???). Lipton introduced Rabin's algorithm as the start of the modern era of random algorithms here, but not as the first one. I also know many algorithms for probabilistic finite automata (a very simple computational model) discovered during 1960s.

Do you know any probabilistic/randomized algorithms (or method) even before 1960s?

or

Which finding can be seen as the first probabilistic/randomized algorithm?

This is discussed a bit in my paper with H. C. Williams, "Factoring Integers before Computers"

In a 1917 paper, H. C. Pocklington discussed an algorithm for finding sqrt(a), modulo p, which depended on choosing elements at random to get a nonresidue of a certain form.  In it, he said, "We have to do this [find the nonresidue] by trial, using the Law of Quadratic Reciprocity, which is a defect in the method.  But as for each value of u half the values of t are suitable, there should be no difficulty in finding one."

So this is one of the first explicit mentions of a randomized algorithm.


Major mistakes in accepted FOCS/STOC papers Have you come across an occasion like that in the past? Well, there is a possibility for everything but I would like to know how realistic this incidence can be. I am referring to serious mistakes altering the target of the paper and not minor mistakes, of course. Thanks

One case is Blum-Feldman-Micali's STOC '88 paper. The flaw was pointed to them by Mihir Bellare (private communication). You can find the relevant discussion here.
The Petri net reachability problem has a rich history where incomplete or flawed proofs later lead to new results.  G.S. Sacerdote and R.L. Tenney presented an incomplete decidability proof at STOC '77, which was however instrumental in the later proof of E.W. Mayr at STOC '81 and its improvement by S.R. Kosaraju at STOC '82.  These decidability proofs did not come with complexity upper bounds (they employ well quasi-orderings for termination).  Z. Bouziane later claimed to have found a 2ExpSpace algorithm at FOCS '98.  A flaw was pointed by P. Jančar (and finally published in a note), but Bouziane's work has helped renewing the interest into this old question.  Although there are still no known upper bounds on the complexity of this problem, J. Leroux has recently presented a new decidability proof at POPL '11.

Not in STOC/FOCS:

Another case happened in Structure in Complexity Theory (1988) conference (If I'm not mistaken, it's now called Conference on Computational Complexity.) The paper's title was On the power of multi-power interactive protocols. Two years later, the authors (Fortnow, Rompel, and Sipser) published a two-page paper "Errata for On the Power of Multi-Prover Interactive Protocols" in the same conference. Unfortunately, IEEE does not offer this paper for download.


Gowers "discretized Borel determinacy" approach Gowers has recently outlined a problem, which he calls "discretized Borel determinacy," whose solution is related to proving circuit lower bounds.

Can you provide a summary of the approach that is tailored to an audience of complexity theorists?
What would it take for this approach to prove anything, including re-proving known lower bounds?

Let me give a summary of my understanding of the motivation for the approach. Be warned that I am fairly new to the concept of Borel determinacy, and not at all an expert in set theory. All mistakes are mine. Also I am not sure reading this is all that much better than reading Gowers' posts.

I think what Gowers has in mind is not a finitary analogue of the Borel determinacy theorem, but a finitary analogue of the following: Borel determinacy follows from ZFC, while determinacy of analytic games requires the existence of (essentially) measurable cardinals. I will very briefly describe what games we're talking about and what Borel determinacy is, and then I will tie this in with the approach to proving lower bounds. The very high-level idea is to consider the property "allows a finitary analogue of a proof of Borel determinacy to work" as a property that can separate P\poly from NP.

We think of games where two players I and II take turns "playing" an integer. The game goes on forever, so they produce a sequence $x= x_1, x_2, \ldots$. The game is defined by a winning set $A \subseteq \mathbb{N}^\mathbb{N}$ (i.e. a set of sequences). If $x \in A$ then player I wins, otherwise player II wins.

A game is determined if either player I or player II has a winning strategy: a way to decide a next move based on the play so far that guarantees a win. Whether all games are determined turns out to have intimate connections to the foundations of set theory (they are not, if you believe in the axiom of choice). In any case, one  simple example when games are in fact determined is when $A$ is open in the product topology on $\mathbb{N}^\mathbb{N}$, which is a fancy way of saying that membership $x \in A$ can be decided based only on a finite number of elements of $x$. For example the game in which player I wins if she is the first to play an even number is open. Another simple example of determined games is closed games, i.e. games where $x \not \in A$ can be decided based on a finite subsequence of $x$. Closed games are open games with the roles of players inverted.

Now we can come to Borel determinacy, and right after I will try to tie this in with circuits and complexity. A Borel set is a set that can be derived from open and closed sets by repeatedly applying a countable number of unions and intersections. You should think of open and closed sets as your basic sets, and Borel sets as derived from basic sets using several levels of a "small" (= countable) number of simple operations in each level. It turns out that you can prove in ZFC that Borel sets are determined, and there is a precise sense in which this is the best you can do.

The analogy that I think Gowers is drawing here is that Borel sets are like small circuits. In the finite world, we replace the "universe" $\mathbb{N}^\mathbb{N}$ by the hypercube $\{0,1\}^n$. Our basic sets become facets of the cube: $\{x \in \{0,1\}^n: x_i = b\}$ for $b \in \{0,1\}$; these are equivalent to literals $x_i$ and $\bar{x}_i$. You can write AND and OR of literals as unions and intersections of such sets. So, for a boolean functions $f:\{0,1\}^n \rightarrow \{0,1\}$, being able to produce $f^{-1}(1)$ out of $s$ unions and intersections of basic sets is equivalent to having a size $s$ circuit for $f$.

Let me throw a word in about analytic sets. An analytic set is a projection of a Borel set: if $S \subseteq X \times Y$ is a Borel set, then $T = \{x: \exists y\ (x,y) \in S\}$ is analytic. By our correspondence between Borel sets and functions of small circuit complexity, analytic sets are like NP/poly.

Now he draws inspiration from a proof of Borel determinacy to come up with a property (in the Razborov-Rudich sense) to distinguish functions of small circuit complexity from functions of large circuit complexity. The hope of course is that the property avoids the natural proofs barrier.

Martin's proof of Borel determinacy uses a conceptually very neat approach: Martin shows that every Borel game is a the image of an open (in fact clopen) game under a map $\pi$, so that $\pi$ preserves winning strategies -- let's call this a "lift". So what Martin shows is that each Borel game is the image of a game in which the winning set is a basic set. Since open games are easily seen to be determined, this proves Borel determinacy. The proof is inductive, with the base case showing that closed games can be lifted. The important part is that each step of the induction "blows" up the universe: getting rid of one level of the Borel set construction requires lifting a game to a game over a universe that is essentially the power set of the universe of the original game. Interestingly, this is unavoidable: Borel sets that require more levels to define can only be lifted to games over much larger universes. Analytic sets require universes that are so large, that their existence requires large cardinal axioms.

Drawing inspiration from this, Gowers formulates a game in which player I and player II must jointly specify some $x$; player I wins if $f(x) = 1$, otherwise player II wins. Player I can specify the first half of the coordinates, and player II the second half. The intuition now is that games corresponding to simple $f$, i.e. $f$ with small circuit complexity, should allow a Martin-style lift to a relatively small universe, just like Borel games do. On the other hand random $f$ should require double exponential size universes, and hopefully NP-hard $f$ should as well, because they would correspond to analytic games.

Let me be just slightly more concrete about what a Martin-style lift is, but do check Gowers' posts for technical definitions. A Martin-style (in Gowers' terminology, "Ramsey") lift is a lift to a game of specifying some $y \in U$ coordinate by coordinate, where $U$ is the universe and is potentially larger than $2^n$, but now the winning condition is very simple: whether player I or II wins is decided based on the value of a single coordinate of $y$. As in Martin's proof, a lift must preserve winning strategies.

The hope that this may avoid the natural proofs barrier is based on the intuition that the property "has Martin style lift to a small universe" is probably not easy to compute. But at this point it's not clear if the parity function has a lift to a small universe. I worry that the appropriate analogy to Borel sets may be functions $f$ in AC0: finding a small lift for parity would put at least that worry to rest.


Inferring the Kolmogorov complexity of a string from its substrings' complexity I know that the Kolmogorov complexity of a substring $v$ of an incompressible string $x$ has $C(v)\geq |v|-O(\log{|x|})$ , but I'm wondering if it is also possible to infer the complexity of a string given its substrings' complexity:
Specifically, If $x$ is a string of length $n$ and every substring $v$ of $x$ having length $m$ has complexity $C(v)\geq k$, is it possible to infer any general lower bound for $C(x)$ in terms of $n$, $m$, and $k$? I'm thinking that $C(x)$ cannot be much smaller than $k$ or else the $C(v)$ would not have $k$ as a lower bound. On the other hand, since $n$ can be much larger than $m$ this might balance things out.

A simple bound is that we could use a program generating $x$, a starting index $1 \leq i \leq n$ and length $m$ to get a program generating any choice of $v$, and thus $C(v)$ is bounded as
$$\forall v: k \leq C(v) \leq C(x) + \log(n) + \log(m) + c,$$
where $c$ is some constant overhead independent from $x,v$ that represents the steps necessary to take a Turing machine, a starting index and length and return the requested substring.
This in turn gives us a lower bound for $C(x)$,
$$C(x)  \geq k - \log(n) - \log(m) - c.$$


approximating problems described by multiple parameters If I am given an optimization problem $L$, and a problem instance of $L$, which is of size $(m,n)$ (i.e. it depends on more than one parameter) then what does it mean to have, let's say, a linear-approximation algorithm?

Do I then mention whether it is linear in $m$ or $n$?

On the other hand I might be allowed to set $m$ equal to $n$ and thereby I would be obsolete to mention in which parameter the problem is linearly approximated.

This is not an answer, but rather a personal experience.  I'll post it as an answer since it's too long to be a comment.

If I would be an author, I wouldn't use the expression like "linear-approximation" since it's confusing.

I haven't seen an expression like "linear-approximation" or "logarithmic-approximation" for referring to approximation ratios.  For example, the greedy algorithm for the minimum set cover problem is an $H(n)$-approximation algorithm, where $H(n)$ is the $n$-th Harmonic number, but I haven't seen it's called a logarithmic-approximation algorithm.  Here, $n$ is the size of a universe, and this should be explained in the definition of the problem.  Please note that $n$ is not the input size.

There's one exception.  In the book "Complexity and Approximation" by Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, and Protasi, I can find expressions like log-APX, poly-APX and exp-APX.  For example, log-APX refers to the class of NP optimization problems that have an $O(\log n)$-approximation algorithm, where $n$ is the input size.

Some authors use "a linear approximation algorithm" to mean a linear-time approximation algorithm.  I feel this is still confusing, and I would write linear-time approximation.  People tend to omit "time", and for example when they write "a polynomial algorithm", they often mean a polynomial-time algorithm.


Definition for MSO2 for arbitrary structures I am not able to find a rigorous definition of MSO_2 logic for arbitrary structures (which I can cite). MSO_2 for graphs is often used and defined, i.e. in On the Parameterised Intractability of Monadic Second-Order Logic - Stephan Kreutzer. The only "definition" for MSO2 on structures I found was in A logical approach to multicut problems - Gottlob, Lee.

"The definition of MSO2 can be easily
generalized to arbitrary structures by allowing quantifi-
cation over subsets of the input relation (notice that in
the case of a graph, the input relation is just the edge re-
lation). Thus, for example, if a relational symbol R is
part of the signature, then a subformula (∃X ⊆ R)φ(X),
expressing that there exists a subset X of the relation R
such that φ(X) holds for some formula φ, could be part
of an MSO2 formula."

While this is enough explanation to know what MSO2 on arbitrary structures is, I really would appreciate if someone could give me a pointer to a formal, rigorous definition somewhere in the literature.

If I understand correctly, you just want a definition of the logic; then you can find a definition of MSO$_j$ (where 2 is a special case) by example in ''Elements of Finite Model Theory'' of Leonid Libkin.
Even if you are interested in infinite model, the definition of the logic is the same.

Quickly is just the set of formulae with existantial quantification over sets of the elements of the universe, then existantial quantifications over those sets; then a first-order formula.


Advanced techniques for determining complexity lower bounds Some of you may have been following this question, which was closed due to not being research level. So, I'm extracting the part of the question which is at a research level.

Beyond the "simpler" techniques, such as reducing to sorting or an EXPTIME-complete problem, what techniques have been used to prove lower bounds for the time complexity of a problem?

In particular:

What are the "cutting-edge" techniques that have been developed in the last decade?
Can techniques from Abstract Algebra, Category Theory, or other branches of typically "pure" mathematics be applied? (For example, I often hear mention of the "algebraic structure" of sorting, without any real explanation of what this means.)
What are significant but lesser-known results for lower-bound complexity?

Lower bounds for algebraic circuits
In the setting of algebraic circuits, where a lower bound on circuit size is analogous to a lower bound on time, many results are known, but there are only a few core techniques in the more modern results. I know you asked for time lower bounds, but I think in many cases the hope is that the algebraic lower bounds will one day lead to Boolean/Turing machine lower bounds. These results often use deeper techniques from "pure math" as you put it.
I. The degree bound.
Strassen showed that the log of the degree of a certain algebraic variety associated to a (set of) function(s) is a lower bound on the algebraic circuit size of computing those functions.
II. Connected components (or more generally the dimension of any higher homology group).
Ben-Or showed that the size of a real algebraic decision tree deciding membership in a (semi-algebraic) set is at least $\log C$ where $C$ is the number of connected components of that set. Ben-Or used this to prove an $\Omega(n \log n)$ lower bound on sorting (well, element distinctness, but element distinctness reduces to sorting) in the real algebraic decision tree model. Yao extended this from connected components to the sum of the Betti numbers and proved optimal lower bounds for other problems (like $k$-equals)). In a different paper Yao extended this to algebraic decision trees over the integers.
III. Partial derivatives.
This has been the workhorse of many of the modern algebraic circuit lower bounds. I believe partial derivatives were first used to prove a lower bound by Baur-Strassen, where they showed that computing all the first partials of $f$ can be done in size $5s$ where $s$ is the size needed to compute $f$. Combined with Strassen's degree bound, this gave $\Omega(n \log n)$ size lower bounds on various functions, which are still the strongest lower bounds on the size of unrestricted arithmetic circuits for an explicit function.
The more recent use of partial derivatives seems to stem from a paper of Nisan's in which he proved lower bounds on noncommutative circuits by considering the dimension of the space of all partial derivatives. This was used to prove lower bounds on restricted kinds of depth-3 circuits by Nisan-Wigderson, and similar ideas were used to prove lower bounds on multilinear formula size by Raz (and related models by Raz and collaborators). The very recent depth 4 and depth 3 lower bounds by Gupta, Kayal, Kamath, and Saptharishi use a generalization of this idea, to count the dimension of the space of "shifted partial derivatives" - where you can take partial derivatives and then multiply by any monomials of a given degree.  Improving the GKKS result to a super-polynomial size lower bound on permanent (which would imply $\mathrm{VP} \neq \mathrm{VNP}$) may "just" be a matter of getting a better understanding of the ideal generated by permanental minors (see the conjecture at the end of their paper).
IV. Defining equations for varieties.
The idea here is to associate to "easy functions" a certain algebraic variety, find equations that vanish on this variety, and show that these equations do not vanish on your "hard function." (Hence proving that your hard function is not in the variety of easy functions, so that it's actually hard.) Especially useful in lower bounds on matrix multiplication. See Landsberg--Ottaviani on the arXiv for the latest, and references to prior lower bounds.
(In fact, I, II, and III above can all be viewed as special cases of finding defining equations for certain varieties, though the proofs that use I,II,III are essentially never phrased that way, as there wasn't really a need to.)
V. Representation theory, esp. as in geometric complexity theory.
Actually, also used by Landsberg--Ottaviani to find some equations for a certain variety. Also used by Burgisser-Ikenmeyer to get a "purely" representation-theoretic proof of a slightly weaker lower bound on matrix multiplication. Conjectured by Mulmuley and Sohoni (cf. "Geometric Complexity Theory I & II") to be useful to resolve $\mathrm{VP}$ vs $\mathrm{VNP}$ and ultimately $\mathrm{NP}$ vs. $\mathrm{P/poly}$.


Sample complexity of distinguishing two Gaussian distributions? Below is a description of the problem:

Suppose I have two $p$-dimensional Gaussian distributions with the same covariance matrix $\Sigma$ and means $\mu_1$, $\mu_0$.

And I can get $n$ samples $X_1^{(1)}, X_1^{(2)}, \dots, X_1^{(n)}$ from $\mathcal{N}(\mu_1, \Sigma)$, and another $n$ samples $X_0^{(1)}, X_0^{(2)}, \dots, X_0^{(n)}$ from $\mathcal{N}(\mu_0, \Sigma)$.

Then I flip an unbiased coin $b\in\{1,0\}$, and take a sample $s$ from $\mathcal{N}(\mu_b,\Sigma)$.

I then give the samples $X_1^{(1)}, X_1^{(2)}, \dots, X_1^{(n)}$ and $X_0^{(1)}, X_0^{(2)}, \dots, X_0^{(n)}$ to an algorithm with the sample $s$. The algorithm outputs a bit $b'$ to indicate that the algorithm thinks that $s$ is from $\mathcal{N}(\mu_{b'},\Sigma)$.

Note that the algorithm does not know $\Sigma$, $\mu_1$, $\mu_0$.

The question is: How large should $n$ be so that $\Pr[b=b'] \geq \frac{1}{2}+\epsilon$?

(The bound should be given in terms of $\epsilon$, $\Sigma$, $\mu_1$, $\mu_0$.)

Are there any papers that have solutions to this problem?

I don't have a solution to this problem, but the analogous case where the two distributions are discrete has been analyzed in the cryptographic literature.

Suppose we want to distinguish between two distributions $\mathcal{D}_0$, $\mathcal{D}_1$, where these two distributions are "close".  Suppose we have $n$ observations (i.e., a sequence of $n$ numbers that are sampled from either i.i.d. $\mathcal{D}_0$ or i.i.d $\mathcal{D}_1$), and we want to distinguish whether they came from $\mathcal{D}_0$ or from $\mathcal{D}_1$.  Let $d = 0.5 n/D(\mathcal{D}_0 ||\mathcal{D}_1)$, where $D(\mathcal{D}_0 ||\mathcal{D}_1)$ is the Kullback-Leibler divergence between these two distributions.  Then the optimal distinguisher has a probability of error approximately $\Phi(-\sqrt{d}/2)$, where $\Phi(t)$ is the pdf of the standard normal distribution.

See Theorem 6 from How Far Can We Go Beyond Linear Cryptanalysis?, Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.

I have no proof that this is valid for multivariate Gaussian distributions as well, but it seems reasonable to conjecture that it might.

Stepping away from discrete distributions, in your particular case of normal distributions, the one-dimensional case ($p=1$) has also been studied in the cryptographic literature.  If you want to distinguish $\mathcal{N}(\mu_0,\sigma_0^2)$ from $\mathcal{N}(\mu_1,\sigma_1^2)$ given a single observation, the optimal distinguisher has probability of error $\text{erfc}(z)$ where $z = (\mu_1-\mu_0)/(\sigma_0+\sigma_1)$.  I don't recall what happens when you get to see $n$ samples from either $\mathcal{N}(\mu_0,\sigma_0^2)$ from $\mathcal{N}(\mu_1,\sigma_1^2)$, but I imagine this case has been worked out before as well.

See https://cstheory.stackexchange.com/a/22339/5038.

In the multivariate case, the Kullback-Leibler divergence between two multivariate Gaussians is known: see https://en.wikipedia.org/wiki/Multivariate_normal_distribution#Kullback.E2.80.93Leibler_divergence.

Also, the Kullback-Leibler divergence is additive when you have $n$ i.i.d. samples, so the Kullback-Leibler divergence of the product distribution will be $n$ times the KL divergence for a single sample: $D(\mathcal{D}_0^n ||\mathcal{D}_1^n) = n \times D(\mathcal{D}_0 ||\mathcal{D}_1)$.  This is a very handy property of the KL divergence, and it will let you calculate the KL divergence between $n$ samples of $\mathcal{N}(\mu_0,\Sigma)$ vs $n$ samples of $\mathcal{N}(\mu_1,\Sigma)$.  (As a conjecture, I would guess that the distinguishing advantage becomes significant only when this KL divergence becomes significant, though I don't know any proof of this.)

Finally, you might be interested in Pinsker's inequality, which connects the total variation distance to the Kullback-Leibler divergence.  The total variation distance measures (twice) the advantage of the optimal distinguisher.

Unfortunately, depending on your goals, Pinsker's inequality might "go the wrong way".

See also https://stats.stackexchange.com/q/17300/2921 and https://math.stackexchange.com/q/72721/14578 and https://stats.stackexchange.com/q/42992/2921

Update: All of this assumes the two distributions are known.  I just noticed that you want to consider a version of the problem where the distributions are not known to the algorithm.  This can only make the problem harder, but I don't know how much harder, and I don't know of anyone who has studied that variant.


"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org? Do you believe this paper is worthy of arXiv.org? I have searched via Google, and to my knowledge, no one else has this result. I'm not asking you to fully scrutinize the paper, I'm just asking if you find it worthy of archiving.

The paper appears to be my first interesting result ... ever. I'm totally new to archiving/publishing. And, relative to others, I am rather green in the logical disciplines. I produced this paper on my own; I am not studying at any institution.

If you do find it worthy of arXiv.org, and if you do have endorser privileges for Computer Science, would you be willing to endorse me? My account name is "JakeT".

I am hoping that others will find this interesting. I do.

I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and there is an oracle relative to which the Berman-Hartmanis conjecture is true and NP = EXP.

The main issue is that you can't do self-reference for time-bounded machines since you can't simulate and stay within the time bound.


Proof assistant for writing mathematics I'd like to write mathematical proofs using some proof assistant. Everything will be written using first order logic (with equality) and natural deduction. The background is set theory (ZF). For example, how could I write the following proof?

Axiom: $\forall x\forall y(x=y\leftrightarrow\forall z(z\in x\leftrightarrow z\in y))$

Theorem: $\forall x\forall y(\forall z(z\notin x)\land\forall z(z\notin y)\rightarrow x=y)$

That is, the empty set is unique.

It's trivial for me to accomplish that using paper and a pen, but what I really need is a software to help me checking proof for correctness.

Thank you.

Both Coq and Isabelle can do this.

[Coq]
Here is a paper discussing how to encode ZFC in CIC, on which Coq is based.

Benjamin Werner: Sets in Types, Types in Sets (1997).
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.1709

[Isabelle]
There is a library for ZF.

http://www.cl.cam.ac.uk/research/hvg/Isabelle/dist/library/ZF/index.html


Can machine learning algorithms be trained to discard nonsense? Afaik, the problem with many machine learning algorithms is that they will often label nonsense into some categories.

What measures can one take to discard nonsense results?

Eg. if you have a bot that is supposed to label stuff as either orange or an apple, how can you gurantee that it won't label a random image of noise as either of the two?

Or label a car as either of the two?

Do you have to train your neural network to have 3 categories, "apple", "orange" and "neither"?

The problem you're describing can perhaps be treated as "anomaly detection". Google the term in quotes, you'll get a ton of references. So the idea would be to first train an anomaly detector to separate the "apples, oranges, and other fruits" from non-fruits (or "nonsense" in OP terminology). Then train a classifier on the fruits.

Update. In light of additional answers -- and too long for a comment.
The problem with declaring a "non-fruit" category highlights the distinction between classification and anomaly detection. In classification, we assume 2 or more coherent classes. Apples, oranges, bananas -- these all have well-defined common characteristics. On the other hand, "non-fruit" is not a coherent category. It can only be meaningfully defined as something like "not fulfilling enough of the fruit characteristics". Anomalous objects are not a coherent class; they are by definition anything that is not sufficiently close to a "normal" object. We do not expect examples of anomalous objects to be informative for training. After all, you can just generate random pixel-images and get tons of anomalous examples for free!

This is why anomaly detection requires techniques distinct from classification.


Computational complexity of counting induced subgraphs which admit perfect matchings Given an undirected and unweighted graph $G=(V,E)$ and an even integer $k$, what is the computational complexity of counting sets of vertices $S\subseteq V$ such that $|S|=k$ and the subgraph of $G$ restricted to the vertex set $S$ admits a perfect matching? Is the complexity #P-complete? Is there a reference for this problem?

Note that the problem is of course easy for a constant $k$ because then all the subgraphs of size $k$ can be enumerated in time ${|V| \choose k}$. Also note that the problem is different from counting the number of perfect matchings. The reason is that a set of vertices which admits a perfect matching may have multiple number of perfect matchings.

Another way to state the problem is as follows.
A matching is called a $k$-matching if it matches $k$ vertices.
Two matchings $M$ and $M'$ are ``vertex-set-non-invariant'' if the sets of vertices matched by $M$ and $M'$ are not identical. We want to count the total number of vertex-set-non-invariant $k$-matchings.

The problem is #P-complete. It follows from the last paragraph of page 2 of the following paper:

C. J. Colbourn, J. S. Provan, and D. Vertigan, The complexity of computing the Tutte
polynomial on transversal matroids, Combinatorica 15 (1995), no. 1, 1–10.

http://www.springerlink.com/content/wk55t6873054232q/


An exponentially-ambiguous weighted automaton without an equivalent polynomially-ambiguous automaton A min-plus weighted automaton (WFA) is a nondeterministic automaton with a weight function that assigns each transition a weight in $\mathbb{N}$. The weights along a run are summed, and the value of a word is the value of the minimal accepting run of the automaton on it.

In a beautiful paper, Kirsten and Lombardy show that deciding unambiguity and sequentiality (i.e. determinizability) for WFAs is decidable for polynomially ambiguous WFA (the general case has been open for years).

Working on related problems, I am trying to tackle the following:

  Is there an example of an exponentially-ambiguous WFA for which there is no equivalent polynomially ambiguous WFA?

Note that by "equivalent" we mean that they represent the same (perhaps partial) function $f:\Sigma^*\to \mathbb{N}$.

Some side-notes:

It is known that exponentially-ambiguous NFAs are exponentially more succinct than polynomially-ambiguous NFAs. But this is non-trivial. This suggests that in the WFA case this would also be not easy.
It is well known that WFAs are, in general, non-determinizable. For example, it is easy to construct a WFA for the function that returns the minimal number of occurrences of a certain letter in a word, but this cannot be done with a deterministic WFA. This suggests that the hierarchy between different classes of ambiguity might also be proper (hence my question).
Exponentially ambiguous automata have a very simple syntactic structure: an automaton is exponentially ambiguous iff there is a state $q$ and a word $w$ such that $q$ is reachable from itself using $w$ in at least two different paths.

Here is a natural candidate: the alphabet is $\{a,b,c\}$, and to a word $v=u_1cu_2c\dots cu_k$ with each $u_i\in\{a,b\}^*$, you want to associate $$f(v)=\sum_{i=1}^k \min(|u_i|_a,|u_i|_b)$$

There is a straigthforward exponentially ambiguous automaton for this $f$: each time you see a $c$, guess if you go to a state counting $a$'s or to a state counting $b$'s.
It should not be too hard to prove that only exponentially ambigous automata recognize this function $f$. As a very sketchy argument, consider the fact that between two $c$'s, you must either count the number of $a$ or the number of $b$, so you need two different states to do so. Since you must be able to oscillate between these states, it means that you have distinct paths of the form $p\stackrel{w}{\longrightarrow} p$ for some state $p$ and word $w$ (containing some $c$'s).


Poly time superset of NP complete language with infinitely many strings excluded from it For any arbitrary NP complete language is there always a polytime superset the complement of which is also infinite?

A trivial version which does not stipulate the superset to have infinite complement has been asked at https://cs.stackexchange.com/q/50123/42961

For purposes of this question, you can assume that $P \ne NP$.  As Vor explained, if $P = NP$ then the answer is "No".  (If $P = NP$, then $X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$ is NP-complete. Clearly there is no superset of $X$ which is infinite and has an infinite complement, as the complement of $X$ has only a single element.)  Thus we can focus on the case $P \ne NP$.

Every $\mathsf{coNP}$-complete set contains an infinite subset in $\mathsf{P}$ assuming that

pseudorandom generators exist, and
secure one-way permutations exist.

In other words, assuming that these two conjectures are true,
no $\mathsf{coNP}$-complete set is P-immune.
As pointed out in the comments by Lance,
this is implied by Theorem 4.4 of

Glasser, Pavan, Selman, and Sengupta, "Properties of NP-complete sets",
SIAM J. Comput. 36(2), 516–542.

(Kaveh has already shown that your question is equivalent to
whether every $\mathsf{coNP}$-complete sets
contains an infinite $\mathsf{P}$ subset.
In other language,
this is saying that no $\mathsf{coNP}$-complete set is "$\mathsf{P}$-immune." This is the language used in the above-referenced theorem.)


Approximating Random MAX-k-SAT It is known [de la Vega & Karpinski 2002] that random instances of MAX-3-SAT on $n$ variables can be approximated up to fraction at least 8/9 w.h.p. tending to 1 as $n$ tends to infinity.

Should one expect this to be close to optimal?
In fact, is it possible, that random MAX-k-SAT instances can be approximated within any desirable fraction w.h.p.?
At least on the face of it - this should not contradict the PCP theorem, whose output SAT instances are very construction-specific (Dinur) and are thus sets with negligible probability in this respect.

Their result is not optimal. First, it was improved upon by Yannet Interian. She obtained a 20/19 approximation (if I recall correctly). See the reference:

  Y. Interian. Approximation algorithm for Random MAX-kSAT. Theory and Applications of Satisfiability Testing (SAT 2004), Revised Selected Papers. LNCS 3542, 2005.

Her result has apparently been improved further by Fernandez de la Vega and Karpinski to 1.0957, but I cannot find an online preprint of this paper.

Given such a low approximation ratio, I wonder if it is reasonable to conjecture that there is a PTAS.


Google quantum supremacy experiment data I don't know if this is the right place to ask.
Still, I vaguely remember that there was a desire expressed by some people in this community to get access to the data of the 53 qubit Google quantum supremacy experiment, given that the data released for Google previous experiments, which was sometimes cited as evidence,  regarded much smaller number of qubits.
So I want to ask if since then the data for the 53 qubits original experiment was released and, if yes, where one can find it.

Yes, it seems to be available on this link.


An Anthology of Complexity Assumptions In the paper The Random Oracle Hypothesis Is False, the authors (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi) discuss the implications of the random-oracle hypothesis. They argue that we know very little about separations between complexity classes, and most results involve either using reasonable assumptions, or the random-oracle hypothesis. The most important and widely believed assumption is that PH does not collapse. In their words:

  In one approach, we assume as a working hypothesis that PH has infinitely many levels. Thus, any assumption which would imply that PH is finite is deemed incorrect. For example, Karp and Lipton showed that if NP ⊆ P/poly, then PH collapses to $\Sigma^P_2$. So, we believe that SAT does not have polynomial sized circuits. Similarly, we believe that the Turing-complete and many-one complete sets for NP are not sparse, because Mahaney showed that these conditions would collapse PH. One can even show that for any k ≥ 0, $P^{\mathrm{SAT}[k]} = P^{\mathrm{SAT}[k+1]}$ implies that PH is finite. Hence, we believe that $P^{\mathrm{SAT}[k]} \ne P^{\mathrm{SAT}[k+1]}$ for all k ≥ 0. Thus, if the polynomial hierarchy is indeed infinite, we can describe many aspects of the computational complexity of NP.

Apart from the assumption about PH not collapsing, there have been many other complexity assumptions. For instance:

Yao deems the following assumption plausible:
$RP \subseteq \bigcap\limits_{\epsilon > 0} DTIME(2^{n^\epsilon})$.
Nisan and Wigderson make several assumptions related to derandomization.

The main idea of this question is what its title says: To be an anthology of complexity-theoretic assumptions. It would be great if the following conventions were adhered to (whenever possible):

The assumption itself;
The first paper in which the assumption is made;
Interesting results in which the assumption is used;
If the assumption has ever been refuted / proved, or whether its plausibility has ever been discussed.

This post is meant to be a community wiki; if an assumption is already cited, please edit the post and add new information rather than making a new post.

Edit (10/31/2011): Some cryptographic assumptions and information about them are listed in the following websites:

Wiki of Cryptographic Primitives and Hard Problems in Cryptography.
Helger Lipmaa's Cryptographic assumptions and hard problems.

Assumption: Exponential time hypothesis.
First cited in: While being folklore, it was first formalized in the following paper: Russell Impagliazzo and Ramamohan Paturi. 1999. The Complexity of k-SAT. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity (COCO '99). IEEE Computer Society, Washington, DC, USA, 237-240.
Use(s): It assumes that no NP-complete problem can be decided in sub-exponential time, and therefore implies that P ≠ NP.
Status: Open.


Techniques for proving that a sentence relativizes I am interested in how one proves that a sentence relativizes.  Of course, proving that a sentence does not relativize is simple, as seen in the Baker-Gill-Solovay result; but how does one prove that a sentence does relativize, i.e., that it is true relative to any oracle?  Are there known techniques for achieving this for arbitrary sentences?

If you know of any references that address this question, I would like to hear of them.  Thanks.

Normally, the way people prove that a complexity theorem relativizes is using the following two-step procedure:

Prove the theorem.
Observe that your proof relativizes!  In other words, that nothing in the proof changes at all if all the machines mentioned in the proof get access to the same oracle A.

Yes, it's really as simple as that.  To make it rigorous, you should rewrite the whole proof adding superscripts of "A" all over the place.  In practice, though, if people notice this issue at all, they'll usually just add a remark like "this result is easily seen to relativize."

If people seem cavalier about this, it's because they've learned, from experience, that only certain techniques (such as arithmetization) can possibly cause a proof not to relativize.  So if your proof doesn't use those techniques, then it relativizes.

(A close analogy: suppose you prove a theorem about real numbers, but your proof never uses anything about the reals other than the fact that they're a field.  Then it suffices to note that fact, to show that an analogous theorem must hold for complex numbers, p-adics, etc.  There's no need to redo the proof.)

The one situation where more discussion is necessary, is where it's not even obvious what it means to relativize your theorem.  (E.g., what's the oracle access mechanism?)  As Kaveh pointed out above, there's no well-defined mathematical operation of "relativizing" a complexity theorem, just like there's no well-defined mathematical operation of "complexifying" a theorem about real numbers.  Notice that, in the latter case, it's not enough to replace every occurrence of R by C: you probably also need to replace x2 by |x|2 (in some places, not others!), and make other changes that are "obvious" to a mathematician but hard to list formally.  Likewise, in complexity theory, it's usually obvious what it means to "relativize" a theorem (i.e., who should get access to A, and what does it mean for them to access it?), but in some cases it can be quite subtle.  See here for more about this issue.

Turning your question on its head, one could ask:

Is there any example of a relativizing complexity theorem, for which it's significantly harder to prove that the theorem relativizes than that the theorem is true?

Interestingly, I can't come up with a single indisputable example (though maybe someone else can)!  Here's the best I can do:

Recent work on blind and authenticated quantum computing (by Broadbent-Fitzsimons-Kashefi, Reichardt-Unger-Vazirani, and others) might lead to examples.  In those cases, the situation is that we don't know whether the theorems relativize or not---but if they do relativize, then certainly a new idea will be needed beyond what's in the existing proofs.
Arguably, another example might be the random self-reducibility of #P.  If you asked most complexity theorists why that was true, they'd probably say it's because the permanent is both #P-complete and random self-reducible.  That's true, but it doesn't answer the question of whether #P is rsr relative to any oracle.  Well, it turns out that #P is rsr relative to any oracle, and it's not even hard to prove it---but you need to give a direct argument using polynomials, rather than appealing to properties of the permanent.
In Section 8 of my and Avi Wigderson's algebrization paper, we showed that the GMW theorem (that NP has computational zero-knowledge proofs) is algebrizing.  And that really did take new ideas: not "dramatically" new, but certainly nowhere to be found in the usual proofs of the GMW theorem.  Of course, this is for algebrization rather than for relativization.

Addendum: In answer to a further question of the OP, I don't know of any techniques whatsoever for showing that, if you could prove a certain complexity conjecture (which you haven't yet), then your proof would necessarily relativize.  Yes, as long as you restrict your "search for a proof" to relativizing techniques only, you can be sure that, if you ever succeed in finding a proof, then your proof will necessarily relativize.  And in practice, that's often what people do (e.g., because they have certain ideas about what a proof would look like, and those ideas relativize).  But I don't know of any way to guarantee, a priori, that by broadening your search to include non-relativizing techniques, you couldn't find a proof that had eluded you before.


How is the inner ring chosen in the Schönhage–Strassen algorithm? I've been trying to implement the Schönhage–Strassen integer multiplication algorithm, but hit a stumbling block in the recursive step.

I have a value $x$ with $n$ bits and I want to compute $x^2 \pmod {2^n+1}$. I originally thought the idea was to pick a $k$ such that $4^k \geq 2n$, split $x$ into $2^k$ pieces each with $2^{k-1}$ bits, apply SSA's convolution while working modulo $2^{2^k}+1$, a ring with $2^k$ bits of capacity per value, then put the pieces back together. However, the convolution's output has slightly more than $2n$ bits (i.e. $>2^k$ bits per output value, which is more than the capacity of the ring, due to each output value being a sum of several products) so this doesn't work. I had to add on an extra factor of 2 of padding.

That extra factor of 2 in the padding ruins the complexity. It makes my recursive step too expensive. Instead of an $F(n) = n \lg n + \sqrt{n} F(2 \sqrt{n}) = \Theta(n \; \lg n \; \lg \lg n)$ algorithm, I end up with an $F(n) = n \lg n + \sqrt{n} F(4 \sqrt{n}) = \Theta(n \lg^2 n)$ algorithm.

I read a few references linked from wikipedia, but they all seem to gloss over the details of how this issue is solved. For example, I could avoid the extra padding overhead by working modulo $2^{p 2^k} + 1$ for a $p$ that's not a power of 2... but then things just break later, when I have only non-power-of-2 factors remaining and can't apply Cooley-Tukey without doubling the number of pieces. Also, $p$ may not have a multiplicative inverse modulo $2^p+1$. So there's still forced factors of 2 being introduced.

How do I pick the ring to use during the recursive step, without blowing the asymptotic complexity?

Or, in pseudo code form:

multiply_in_ring(a, b, n):
  ...
  // vvv                          vvv //
  // vvv HOW DOES THIS PART WORK? vvv //
  // vvv                          vvv //
  let inner_ring = convolution_ring_for_values_of_size(n);
  // ^^^                          ^^^ //
  // ^^^ HOW DOES THIS PART WORK? ^^^ //
  // ^^^                          ^^^ //

  let input_bits_per_piece = ceil(n / inner_ring.order);
  let piecesA = a.splitIntoNPiecesOfSize(inner_ring.order, input_bits_per_piece);
  let piecesB = b.splitIntoNPiecesOfSize(inner_ring.order, input_bits_per_piece);

  let piecesC = inner_ring.negacyclic_convolution(piecesA, piecesB);
  ...

This answer is taken from the paper "Asymptotically fast algorithms for the numerical muitiplication and division of polynomials with complex coefficients" that Markus linked in the comments.

You want to square an $n$-bit number, modulo $2^n + 1$. Here's what you do:

Find $p$ and $s$ that satisfy $n = (p-1) 2^s$ and $s \leq p \leq 2s$.
Pick the number of pieces $2^m$ to split the $n$ bits into, and the corresponding parameters for the piece sizes:

$$\begin{align} m &= \lfloor s/2 \rfloor + 1 \\s_2 &= \lceil s/2 \rceil + 1 \\ p_2 &= \lceil p/2 \rceil + 1 \end{align}$$

Note that $s_2$ and $p_2$ continue to satisfy the $s_2 \leq p_2 \leq 2 s_2$ invariant. Also note that $2^m 2^{s_2} p_2 \geq 2n + m + 1$ is satisfied, so the input fits with room for carries.
Perform the FFT-based negacyclic convolution on the pieces, and the rest, as usual.

So that's the overarching idea: a logarithmic padding factor $p$. Now for the complexity analysis. The FFT will take $n m$ work to do, and we're recursing on $2^m$ pieces of size $(p_2-1) 2^{s_2}$, so now we can do extremely rough math with the recurrence relation w.r.t. $s$:

$$\begin{align}
F(s)
&(\leq)\; (p-1)2^sm + 2^m F(\lceil s/2\rceil+1)
\\
&(\leq)\; 2s2^s (\lfloor s/2\rfloor+1) + 2^{\lfloor s/2\rfloor+1} F(\lceil s/2\rceil+1)
\\
&(\leq)\; s^2 2^s + 2 \cdot 2^{s/2} F(s/2+1)
\\
&(\leq)\; s^2 2^s + 4 (s/2)^2 2^s + 16(s/4)^2 2^s + ...
\\
&(\leq)\; 2^s s^2 \lg(s)
\\
&(\leq)\; \frac{n}{\lg n} \left(\lg \frac{n}{\lg n}\right)^2  \lg \lg \frac{n}{\lg n}
\\
&(\leq)\; \frac{n}{\lg n} (\lg^2 n) \lg \lg n
\\
&(\leq)\; n \;(\lg n) \lg \lg n
\end{align}$$

Which seems about right, although I cheated quite a lot in those steps.

The 'trick' seems to be the fact that we end up with $s^2$ instead of $s$ in the base cost. There's still two multiplications by two per recursive level, like I was complaining about in the question, but now the halving of $s$ is paying double-dividends so it all works out. Then, at the end, we cancel the extra factor of $s$ (which is actually a factor of $\log n$) thanks to making $p$ logarithmically large relative to $s$ initially.


Finding k shortest Paths with Eppstein's Algorithm I'm trying to figure out how the Path Graph $P(G)$ according to Eppstein's Algorithm in this paper works
and how I can reconstruct the $k$ shortest paths from $s$ to $t$ with the corresponding heap construction $H(G)$.

So far:

$out(v)$ contains all edges leaving a vertex $v$ in a graph $G$ which are not part of a shortest path in $G$. They are heap-ordered by the "waste of time" called $\delta(e)$ when using this edge instead of the one on a shortest paths. By applying Dijkstra I find the shortest paths to every vertex from $t$.

I can calculate this by taking the length of the edge + (the value of the head vertex (where the directed edge is pointing to) - the value of the tail vertex (where the directed edge is starting). If this is $> 0$ it is not on a shortest path, if it is $= 0$ it is on a shortest path.

Now I build a 2-Min-Heap $H_{out}(v)$ by heapifying the set of edges $out(v)$ according to their $\delta(e)$ for any $v \in V$, where the root $outroot(v)$ has only one child (= subtree).

In order to build $H_T(v)$ I insert $outroot(v)$ in $H_T(next_T(v))$ beginning at the terminal vertex $t$. Everytime a vertex is somehow touched while inserting it is marked with a $*$.

Now I can build $H_G(v)$ by inserting the rest of $H_{out}(w)$ in $H_T(v)$. Every vertex in $H_G(v)$ contains either $2$ children from $H_T(v)$ and $1$ from $H_{out}(w)$ or $0$ from the first and $2$ from the second and is a 3-heap.

With $H_G(v)$ I can build a DAG called $D(G)$ containing a vertex for each $*$-marked vertex from $H_T(v)$ and for each non-root vertex from $H_{out}(v)$.

The roots of $H_G(v)$ in $D(G)$ are called $h(v)$ and they are connected to the vertices they belong to according to $out(v)$ by a "mapping".

So far, so good.

The paper says I can build $P(G)$ by inserting a root $r = r(s)$ and connecting this to $h(s)$ by an inital edge with $\delta(h(s))$. The vertices of $D(G)$ are the same in $P(G)$ but they are not weighted. The edges have lengths. Then for each directed edge $(u,v) \in D(G)$ the corresponding edges in $P(G)$ are created and weighted by $\delta(v) - \delta(u)$. They are called Heap Edges. Then for each vertex $v \in P(G)$, which represents an edge not in a shortest path connecting a pair of vertices $u$ and $w$, "cross edges" are created from $v$ to $h(w)$ in $P(G)$ having a length $\delta(h(w))$. Every vertex in $P(G)$ only has a out going degree of $4$ max.

$P(G)$'s paths starting from $r$ are supposed to be a one-to-one length correspondence between $s$-$t$-paths in $G$.

In the end a new heap ordered 4-Heap $H(G)$ is build. Each vertex corresponds to a path in $P(G)$ rooted at $r$. The parent of any vertex has one fewer edge. The weight of a vertex is the lenght of the corresponding path.

To find the $k$ shortest paths I use BFS to $P(G)$ and "translate" the search result to paths by using $H(G)$.

Unfortunately, I don't understand how I can "read" $P(G)$ and then "translate" it through $H(G)$ to receive the $k$ shortest paths.

It's been long enough since I wrote that, that by now my interpretation of what's in there is probably not much more informed than any other reader's. Nevertheless:

I believe that the description you're looking for is the last paragraph of the proof of Lemma 5. Basically, some of the edges in P(G) (the "cross edges") correspond to sidetracks in G (that is, edges that diverge from the shortest path tree). The path in G is formed by following the shortest path tree to the starting vertex of the first sidetrack, following the sidetrack edge itself, following the shortest path tree again to the starting vertex of the next sidetrack, etc.


Quantum computing project ideas I'm undergraduate computer science student and I'm currently planning for my graduation project. I need some ideas in quantum computing field. any help?

I posted some quantum complexity theory project ideas at http://scottaaronson.com/blog/?p=471

(But beware, most of these are problems that have been open for years!  My suggestion for an undergraduate project would be to break off a chunk of one of the problems.)


Number of "3-edge" triangles in a planar triangulation I'm working on a triangle partitioning problem, and I'm trying to find and prove some properties of specific triangulations. The triangulations I'm dealing with are constrained delaunay triangulations in which every constraint is at least an edge (there are no single vertex constraints). Here is an example of such a triangulation:

The red lines represent edge constraints and the blue lines represent the unconstrained edges produced to create the triangulation. Notice how all vertices are in some edge constraint and that there will never be a vertex that is not connected to a constrained edge.

Now let us create a graph from this triangulation. Every triangle is a vertex, and edges are defined by $(v_1,v_2)$ where $v_1$ and $v_2$ are triangles that share an unconstrained edge. Notice that every vertex in this graph has degree at most 3.

My problem is that I want to say something about the number of 3 degree vertices in such a graph. I believe that at least half the vertices have less than degree 3 (just from a hunch) but I have no idea how to go about proving such a thing. What I'm asking is, what is the upper bound of the ratio degree 3 vertices to total vertices in a triangulation with these properties.

EDIT: I found this on the delaunay triangulation wikipedia page. Delaunay triangulations have $O(n^{d/2})$ simplicies, so a planar DT would have $O(n)$ triangles where $n$ is the number of vertices. This isn't the same as the set of constrained delaunay triangulations we're working with, but it seems to suggest that there could be a relationship degree-3 triangles and the total number of triangles.

http://www.sciencedirect.com/science/article/pii/092577219500013Y

I think only those vertices corresponding to triangles sharing an edge with boundary or holes of the polygon will be of degree less than 3. Now the number of triangles in the triangulation is fixed. So you can always get the exact ratio of the number of degree 3 vertices for a polygon.

If the polygon has $k$ vertices and $l$ holes vertices and the number of triangles in the total triangulation is $N$
then the upper bound should be $(N-K-l)/N$.


Number of bits required for encoding variables with fixed sum? Assume we'd like to be able to encode variables $x_1,x_2,\cdots,x_r\in \mathbb{N}$, such that $\forall i\in[r]:1\leq x_i\leq N$ and $$\sum_{i=1}^{r}x_i=M$$

It's easy to store the variables using $r\log N$ bits, but this doesn't take advantage of the fact that their sum is bounded.

Furthermore, in my application $r$ is not fixed and could vary from $\frac{M}{N}$ to $M$, so I would need $M\log N$ bits in the worst case if I use the naive encoding.

So the questions are as follows:

How many bits are required to encode the variables, given that an adversary picks the values of $r$ and $x_1,x_2,\cdots,x_r$?

Is there an data structure that uses close-to-optimal space for this that supports efficient replacement operations (where replace$(i,j)$ increases the value of $x_j$ by 1 and decrements the value of $x_i$ by 1)?

If it helps, you may assume $M=N$ (which is what I need for my application), but I think it's interesting for general $M,N$.

Answer to question 1: $\left\lceil \log_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode the variables.

Proof: Count how many ways there are to choose $y_1,\ldots,y_r$ such that $y_i \ge 0$ and $\sum y_i = M-r$. There are exactly $\binom{M-1}{r-1}$ such ways (see e.g. here). Now, if there are only $k$ possible values for a variable, then $\lceil \log k \rceil$ bits suffice to encode that variable. Therefore, $opt=\left\lceil \log_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode our input.

Answer to question 2: This is a bit more tricky. The best approach is to check the literature on succinct rank-select or other succinct data structures: I suspect you can match the results for succinct rank-select, so to get something like $opt+o(M)$ space and $O(\log M)$ running times for all operations. If you're interested, tell me in the comments and I'll try to look it up and tell you my best guess on what's possible. You might also want to check out Dodis-Patrascu-Thorup for some ideas.


Number of Vertex Covers and Permanent Is there any relationship between the number of vertex covers of a graph $G$ and the permanent of $G$'s adjacency matrix?

If $G$ has an isolated node, the permanent will be equal to 0.

If you know that permanent is 0, it tells extremely little about the number of vertex covers in $G$. You can take any graph $G$ and construct $G'$ by adding an isolated node; the number of vertex covers in $G'$ is exactly 2 times the number of vertex covers in $G$ – which can be virtually anything – while the permanent of $G'$ is 0.

Conversely, if you know the number of vertex covers, you can't tell if the permanent is 0 or not. For example, you can take any graph $G$ with a non-zero permanent and construct two new graphs: $G_1$ is $G$ + a triangle, and $G_2$ is $G$ + two isolated nodes. Both $G_1$ and $G_2$ have exactly 4 times as many vertex covers as $G$. However, $G_1$ will have a non-zero permanent while $G_2$ will have permanent 0.


Bit complexity of integer factorization? Integer Factorization problem: Given integers $N, M$, find an integer $d< M < N$ that divides $N$. Is it easier to find the value of a single bit? This problem is at least as hard as integer factorization.

  What is the best known upper bound on the complexity of finding the value of $i^{th}$ bit of $d$ ?

I'm interested in algorithms that are asymptotically better than the best known integer factorization algorithm.

Not a full answer, but hopefully a useful partial answer.

First of all, there is an obvious barrier. How do you specify $d$? If we simply wish to find this for any factor $d$ then there are several legitimate values for some of the bits. This means that really from a single bit you can't always tell where you have a trivial factor (say 1 or N) or a non-trivial factor. This means that in general the problem is likely to be as hard as factoring. If for example you there was a factor of hamming weight 2 with the last bit as 1, you would need to obtain all the bits to be sure that it was non-trivial (if for example the first $n-1$ bits you try are all 0 except for the very least significant bit).

However it is possible to obtain relationships between bits in two factors.

This is easy to do for less significant bits, but becomes harder as you move up. If the complexity didn't increase in one direction, it would obviously lead a more efficient algorithm for factoring.

For example, take $N=pq$. Then $p=2p' + p_0$ and $q=2q' + q_0$. where $p_0$ and $q_0$ are single bits. Then $N=4p'q' + 2(p'q_0 + q'p_0) + p_0q_0$, so $N \equiv p_0 q_0 \mbox{ mod }2$. If N is odd, then $p_0 = q_0 = 1$, and so $N=4p'q' + 2(q' + p') + 1$. Now, if instead it was 0, 2 would have been a non-trivial factor, so lets ignore that case, and consider only $p_0 = q_0 = 1$. We can take $p= \sum_{i=0}^n 2^i p_i$ and $q= \sum_{i=0}^n 2^i q_i$.

Then we have $N = \sum_{i,j=0}^n 2^{i+j} p_i q_j$. This implies that $N \equiv \sum_{i=0}^n \sum_{j=0}^{m-i-1} 2^{i+j} p_i q_j \mbox{ mod }2^m$. This then gives you a relationship between the $m$ least significant bits of $p$ and $q$. Since we can also obtain similar relationships for $(m-1) ... 1$ this gives us a set of $m$ constraints that the bits need to satisfy, each containing at most $m$ terms in the sum. Naively, one could consider testing all possible values of $p_{m-1}...p_0$ and $q_{m-1}...q_0$,but in practice it is more efficient to simply find all possible pairs for the $2^1$ constraint, than use only these as the less significant bits when checking which pairs satisfy the $2^2$ constraint and so on up to the $2^m$ constraint. Unfortunately, how effective this is will depend on the number of factors, as well as other things, since if a number has a large number of small factors, there will be a huge number of possible ways of combining these, and so a huge number of legitimate strings for the least significant bits.

For example, if we consider $N = x!$, then we have $\ln{N} \approx x \ln x - x$. So the number of bits in $N$ scales roughly as $x$ times the number of bits in $x$. Now, if we consider how many different possible ways there are to find a factor of $N$ there are, we know that it must be at least $2^{x-1}$, since this is the number of ways of multiplying a subset of ${2 ... x}$, so there are an exponential number of factors. Even if we consider factors less than $\frac{x}{2} \ln x$ bits (less than approx $\sqrt{n}$) we find that there are more than $2^{\frac{x}{2}}$ possibilities, and thus more than $2^{\frac{x}{2}}$ unique bit strings satisfying all constraints up to $2^{\frac{x}{2}\ln x}$. Thus this approach is necessarily exponential in the worst case.

In the worst case to enumerate all such pairs (testing each possible pair) takes time $O(m^2 2^{2m})$.

Hope this is useful.


Paritioning a graph into clique and independent set I am interested in the complexity of the following problems:

Input: an undirected graph $G = \langle V, E \rangle$

Query 1: is there a partition of $V$ into two a clique $C$ and an independent set $I$ of equal size?

Query 2: are there a clique $C \subseteq V$ and an independent set $I \subseteq V$ whose sizes are at least $\frac{|V|}{4}$?

Question (1) is easy polynomial time. As Juho has already mentioned in comments, the graphs that can be partitioned into a clique and an independent set are the split graphs. They can be recognized and partitioned in polynomial time, and all valid partitions (if there are more than one) differ by only a single vertex and can also be found in polynomial time (see the Wikipedia article for details). So you simply test whether any of these partitions satisfies your additional constraint.

As for Question (2), it seems you already know that HALF-CLIQUE is NP-complete, so taking an n-vertex hard instance for this problem and adding another n independent vertices produces a hard instance for your problem. That is, the answer is that it is indeed NP-complete.
One could more-or-less mechanically compose this with the hardness reduction for HALF-CLIQUE to get a reduction from a SAT-like problem, but why is that an interesting or useful thing to do?


Effect of constraints Density on the hardness of Betweness problem Betweeness problem is well known NP-complete permutation problem. Given a family $M$ of triples $(a_i, a_j, a_k)$, the problem is to decide whether a permutation $\Phi$ of elements $a_1, a_2, ..., a_n$ exists which satisfies all betweeness constraints.  For each triple $(a,b,c)$ in $M$, it holds that either $\Phi(a) \lt \Phi(b) \lt \Phi(c)$ or $\Phi(c) \lt \Phi(b) \lt \Phi(a)$.

Motivated partialy by this CS Theory post, I am interested in the relation between density of constraints and hardness of betweeness problem. I am looking for for a classification of problem's hardness based on the number of triples $|M|$ for these cases:

1-$|M|=O(\log n)$, 2-$|M|=o(n)$ , 3-$|M|=\Theta(n)$,  4-$|M|=\Omega(n^2)$, 5-$|M|=\Omega(n^3)$.

Please classify it to PTIME solvable, Quasi-polynomial solvable, Subexponential time solvable, and NP-complete.

As mentioned in the comments, the case with $\Theta(\log n)$ clauses is in PTIME. The other cases are NP complete.

From Chor&Sudan, we know that solving Betweenness instances with $m\in\Theta(n)$ clauses is NP complete (as they present a gadget reduction from gap-E3SAT instances with a linear number of clauses). We also know that there are trivially-satisfiable instances with up to $\Theta(n^3)$ constraints. We can therefore reduce the hard language of Betweenness instances with $m \in \Theta(n)$ to the language with $m \in \Theta(n^c)$ clauses, for any rational $0 < c \le 3$, simply by composing the hard instances with trivially-satisfiable instances of suitable density.

Chor and Sudan, 1998, A Geometric Approach to Betweenness.


Complexity class for Optimization problems over #P functions Is there any complexity class which contains problems that can be expressed as an optimization over polynomially many #P functions ? i.e:

$$\tilde{f}(x) = \text{Max}_{f \in F}f(x)$$

where $f\in\# P$.

Moreover, if I can reduce a #P-Complete function to this, by means of a polynomial time Turing reduction, am I allowed to say formally that:

$$\tilde{f} \in \#P-\text{Complete}$$

OR

$$FP^{\tilde{f}} \in FP^{\#P} $$

The latter seems more plausible to me than the former, but could anyone please tell me if I could use the former claim.

It's in $\mathrm{FP^{\#P}}$, since you can compute it in poly time using oracle calls to compute the $f$s.  If you can poly-time Turing reduce a $\mathrm{\#P}$-complete problem to it, then $\tilde{f}$ is $\mathrm{\#P}$-hard but you can't say it's $\mathrm{\#P}$-complete unless you can show that it's in $\mathrm{\#P}$. That seems unlikely, to me, as I can't see any way of building a nondeterministic Turing machine to have that many accepting paths.

Since $\tilde{f}\in\mathrm{FP^{\#P}}$ and $\mathrm{FP^{FP^{\#P}}}=\mathrm{FP^{\#P}}$ (just compose the reductions), $\mathrm{FP}^{\tilde{f}}\subseteq \mathrm{FP^{\#P}}$.  Note that $\mathrm{FP}^{\tilde{f}}$ is a complexity class (all problems that are poly-time Turing reducible to $\tilde{f}$), not a problem.


Number of SAT checks that are needed to find all combinations of subset of boolean variables of a propositional formula Please mind that I sometimes lack formal mathematical knowledge and English is not my first language, so I might miss the right words. Please change the tile if needed. Also, I have choosen this site as for me the question is loosely related to complexity.

Assume there is a randomly generated propositional formula f that includes n_total number of boolean variables.

I am not interested in all boolean variables, but only in a small subset of n boolean variables of the formula f (thus n < n_total). I want to find all possible combinations that the subset of n boolean variables can take that are part of some model of f.

What is the expected number of SAT calls that are needed to calculate all the combinations of the n boolean variables that I am interested in?

Exmaple:

Assume my formula f has 50 boolean variables and I am only interested in a subset of three (thus n = 3) boolean variables a1, a2, a3. What different truth values can a1, a2 and a3 take where the result is an assigment that is part of a model of f?

Naive solution:

a1 a2 a3
0 0 0
=>  check with a SAT solver, if the formula f has a model where all three variables a1, a2, a3 are false.

a1 a2 a3
0 0 1
=> check with a SAT solver, if the formula f has a model where a3 is true and a1 and a2 are false

a1 a2 a3
0 1 0
==> check with a SAT solver, if the formula f has a model where a2 is true and a1 and a3 are false

... etc. ...

a1 a2 a3
1 1 1
=> check with a SAT solver, if the formula f has a model where a1, a2 and a3 are true

Concerning the naive solution,
If I am interested in a subset of n boolean variables of f, all the combinations of the n variables can be calculated with 2^n and thus 2^3 = 8  SAT calls.

Optimizations over the naive solution:
My preliminary ideas: But what if two variables a1 and a2 are "xor", thus can never be true together in a model of f. In the set of the variables I am interested in (a1...a3 in the example), I can first try to find two boolean variables that are "xor". Or perhaps check all combinations of two variables whether they are "xor" and then proceed.

If I am interested in the expected number of SAT checks, is there an improvement over the 2^n number of checks of the naive solution? Assume the propositional formula f is randomly generated and has random characteristics.

If you really want to enumerate all the assignments, then you really need to find a satisfying assignment and then block it by a clause. E.g. if you find a satisfying assignment $a_1=a_2=a_3=0$ you'd block it by $a_1\lor a_2\lor a_3$.

One, relatively easy improvement, is to reduce the found assignment to a (prime) implicant. For instance, if $a_1\rightarrow f$, then you know that all assignments with $a_1=1$ are satisfying ($a_1$ is an implicant). You can reduce an existing satisfying assignment to an implicant by throwing one variable at a time. Similar approach published first (I think) here [1].

Somewhat more general problem is quantifier elimination, i.e. you're given $\exists X. f$ with some free variables $Y$, where $X$ and $Y$ are sets of variables. The output is a formula $f'$ that has only free variables $Y$ and has the same set of satisfying assignments as $\exists X. f$. Some recent  papers on the problem [2][3].
(am a coauthor of the [3]).

[1] McMillan: Applying SAT Methods in Unbounded Symbolic Model Checking. CAV 2002

[2] Goldberg,Manolios: Quantifier elimination via clause redundancy. FMCAD 2013

[3] Klieber et: al Solving QBF with Free Variables. CP 2013


Notation for a Conditional Hamiltonian Evolution Operator I am reading Harrow, Hassidim, and Lloyd's paper Quantum algorithms for linear systems of equations. On the third page of that paper, they write

  Next we apply the conditional Hamiltonian evolution $\sum_{\tau=0}^{T-1} \left|\tau\right>\left<\tau\right|^{C}\otimes e^{iA\tau t_{o}/T}$ on $\left|\Psi_{0}\right>^{C}\otimes\left|b\right>\dots$

For the life of me, I cannot figure out the meaning of the $C$. What is it doing there? How would $\sum_{\tau=0}^{T-1} \left|\tau\right>\left<\tau\right|^{C}\otimes e^{iA\tau t_{o}/T}$ act on (say) $\left|0\right>\otimes \left|0\right>$ or $\left|1\right>\otimes \left|0\right>$?

I remember struggling with this very same question! Ultimately I concluded that the $C$ is just a notational device (it doesn't represent any mathematical operation), just to indicate that, for a specific $\tau$, the Hamiltonian evolution operator $e^{iA\tau t_0/T}$ is performed on $\left|b\right>$, but only when conditioned on $\left|b\right>$ being tensored with $\left|\tau\right>$.

If you ignore the $C$'s, I think a calculation will show that you just apply the operator $\sum_{\tau=0}^{T-1} \left|\tau\right>\left<\tau\right|\otimes e^{iA\tau t_{o}/T}$ "as-is". I hope this helps.


Author ordering in TCS papers While the rule of thumb is that in TCS papers the authors are ordered alphabetically, there are some notable counterexamples that comes to mind, wherein the authors are ordered in a different way, e.g.,

Algebraic Methods for Interactive Proof Systems [Lund, Fortnow, Karloff, Nisan]
A Method for Obtaining Digital Signatures and Public-Key Cryptosystems [Rivest, Shamir, Adleman]
Word Problems Requiring Exponential Time [Stockmeyer, Meyer]

What is the story behind the unusual author ordering in these papers?

Are there any other examples of major TCS papers in which the order of the authors is not alphabetical?

A quick bit of googling gives this for the RSA paper:

Rivest stayed up all night, preparing the manuscript describing the code before he handed it to Adleman. He had listed the paper's authors in alphabetical order - Adleman, Rivest, Shamir. Adleman demurred:
I told Ron, 'Take my name off the paper. It's your work'.
But Rivest insisted and eventually prevailed upon him.
I thought, 'Well, it's going to be the least important paper I've ever been on, but in a few years I will need so many lines on my vita to get tenure, ... on the other hand, I did do a substantial amount of intellectual work breaking the codes 1 through 42. So the reasonable thing to do is be the third author'.


What does x.y notation mean? In Harper's PFPL (Ed. 2, top of page 8), this notation is used but I don't see a definition. What does $x.y$ mean?

This is the notation for Harper's "abstract binding structures": x.t represents the binding site of a variable x and the term t the variable scopes over.
Apparently you are in the parts that define variable bindings. $\mathcal{B}[\mathcal{X}]_s$ appears to be the set of terms, or binding structures at sort $s$ whose free variables are among $\mathcal{X}$. So I would expect (but I don't have the book) that there is in fact an explanation for this notation close by.


Is there a theory that combines category theory/abstract algebra and computational complexity? Category theory and abstract algebra deal with the way functions can be combined with other functions.  Complexity theory deals with how hard a function is to compute.  It's weird to me that I haven't seen anyone combine these fields of study, since they seem like such natural pairs.  Has anyone done this before?

As a motivating example, let's take a look at monoids.  It's well known that if an operation is a monoid, then we can parallelize the operation.

For example in Haskell, we can trivially define that addition is a monoid over the integers like this:

instance Monoid Int where
    mempty = 0
    mappend = (+)

Now if we want to compute the sum of 0 to 999, we could do it sequentially like:

foldl1' (+) [0..999]

or we could do it in parallel

mconcat [0..999] -- for simplicity of the code, I'm ignoring that this doesn't *actually* run in parallel

But parallelizing this monoid makes sense only because mappend runs in constant time.  What if this weren't the case?  Lists, for example, are monoids where mappend does not run inconstant time (or space!).  I'm guessing this is why there is no default parallel mconcat function in Haskell.  The best implementation depends on the complexity of the monoid.

It seems like there should be a convenient way to describe the differences between these two monoids.  We should then be able to annotate our code with these differences and have programs automatically choose the best algorithms to use depending on a monoid's complexity.

[Computational complexity and category theory] seem like such natural pairs.

Given the prominence of computational complexity as a research field, if they were such natural bedfellows, maybe somebody would have brought out the
connection already?

Wild speculation.
Let me entertain the reader with thoughts about   why a categorical rendering of computational complexity is hard.  Arguably, the
key concept cluster in category theory is centering around universal
constructions / properties (with the associated apparatus of functors,
natural transformations, adjunctions and so on). If we can show that a
mathematical construction has a universal property, that gives a lot
of insight.
So if we wanted a categorical approach to computational complexity, we'd
need to find a convenient category and exhibit how key concepts of complexity theory (e.g. LOGSPACE
or NP-hardness) can be given by universal constructions using that category.  This has not
yet been done, and I think that this is because it's a really difficult problem.

I suspect that the reason for this difficulty is that the key object of
complexity theory, the Turing machine, is not well understood algebraically.  The
problem with TMs is that they are not naturally equipped with a nice
algebra that allows building up programs in a compositional way. By
that I mean that we don't usually program TMs by saying our target
program is the TM T which is composed as e.g. $T = T_1 \oplus T_2
\otimes T_3$ where the $T_i$ are 'smaller' TMs and $\oplus, \otimes$ are
algebraic operators on TMs: we just don't have (natural) algebraic operations on TMs that
enable us to build up TMs in stages in an insightful way1.  Instead, we construct TMs by specifying their two
components separately: the  control (a FSM) and the tape.
Neither control nor tape have good algebras
themselves.

Let's look at tapes first.  There are a couple of natural
ways to compose tapes, none of which appear to work for a compositional
description of TMs.

Glue them together like ordinal addition.
This isn't the right notion, because tapes are infinite and by
sticking them together like ordinal addition we obtain a double
infinite object that goes beyond finite computability, leading to
infinite computation / hypercomputation, which are interesting as
mathematical but don't correspond to feasible computation.
Stick them in parallel, e.g. two 3-head machines turn into a 6-head
machine. This doesn't tell us how the component machines interact
with each other.
Interleave tapes. One problem with this approach is that it's
unclear what the canonical interleaving might be, if any. Moreover,
interleaving will 'confuse' existing control, which tends to be
finely tuned towards a specific tape layout. So we can't reuse control directly.

With FSMs the situation is a bit better, because we do have computationally meaningful algebraic
theories of automata construction, the most well-know of which might
be process algebras like CSP, CCS, $\pi$-calculus, ACP and so on. But
none of them is a calculus of tape-head movements, which is what we'd
need if we wanted to compose TMs.

All in all, we are quite far away form a substantial algebraic /
categorical treatment of computational complexity, and we'd need
several conceptual advances to get there.

1 Note that this is
quite different from other computational formalisms like
$\lambda$-calculus and $\pi$-calculus, which are algebraic
calculi. Because they are algebraic, it has been easy to develop
type-theories for $\lambda$-calculus and $\pi$-calculus as a way to
constrain programs. However these calculi have powerful operations like
new-name generation, scope extrusion, $\alpha$-conversion and unlimited copying of terms, which
make them a priori unsuitable as basic formalisms for complexity theory.  Indeed one can easily show e.g. P = NP if one isn't careful. It was only in 2014 that Accattoli and Dal Lago showed  (in: Beta Reduction is Invariant, Indeed) that $\lambda$-calculus can be used for defining time-complexity if one is careful. No corresponding results are known for space complexity, or for $\pi$-calculus.


What characterizations exist for the grammars that can express subsets of the context-free languages? It is well known that CFGs and PDAs are equivalent, and there has been extensive research about the relationship between deterministic pushdowns and $LR(1)$ grammars, as $DCFL$ is a subset of $LR(1)$.

I'm wondering, what results are known about classes of grammars that can generate the languages accepted by other restricted versions of pushdown automata?

In particular, I'm interested in:

Pushdown Automata with a bound on the number of reversals the stack can make.
Pushdown Automata with a unary stack alphabet (i.e. counter machines)

Every context free language over a one letter alphabet (or equivalently every langauge recognized by unary PDAs, unary DPDAs or 1 counter machines) is regular.

See: S. Ginsburg, H. Rice: "Two families of languages related to ALGOL", Journal of the
ACM, 9: 350–371, 1962.

For what regards PDAs with bounded stack reversals they are equivalent to bounded context-free languages. In general a language $L$ over alphabet $\Sigma$ (with $|\Sigma|\geq 2$) is bounded if and only if there exists non empty words $w_1,w_2,...,w_n$ such that $L\ \subseteq w_1^*w_2^*...w_n^*$; but not all bounded languages are context-free (for a characterization of bounded CFG languages by finite union of stratified linear sets see Ginsburg's theorem). I don't know much about them, but they have been studied intensively, see for example: Oscar H. Ibarra, Bala Ravikumar , On Bounded Languages and Reversal-Bounded Automata (citing and cited articles).

EDIT: another result is that linear LR(1) languages are equivalent to the class of languages accepted by deterministic one-turn PDA (M. Holzer, K. J. Lange, On the Complexities of Linear LL(1) and LR(1) Grammars)


XOR Resilient Encoding I am looking for an efficient encoding algorithm $E:\{0,1\}^n\to\{0,1\}^m$ such that given $E(x)\oplus E(y)$ for $x\neq y$, we can reconstruct $x$ and $y$.
One example of such an algorithm would be mapping from $\{0,1\}^n$ to $\{0,1\}^{2^n}$ using a unit vector with $1$ only at the input coordinate. However, this is not an efficient solution in $n$.
I thought of maybe working over $GF(2^n)$ and mapping $x$ to $x^2,x$ or something of the sort, but I do not know if we can reconstruct efficiently and with certainty $x,y$ from $x^2+y^2,x+y$.
What do you think?
Thanks

It turns out that $m=2n$ is possible, and this can be done explicitly in a very related fashion to your idea. It's not hard to see that this is basically optimal. In essence, what you are asking for is an injective map $E:\mathbb{F}_2^n\to \mathbb{F}_2^m$ such that the set of elements $\{E(\mathbf{x})\}_{\mathbf{x}\in \mathbb{F}_2^n}$ forms a Sidon set in the group $(\mathbb{F}^m_2,+)$ (a Sidon set of an abelian group $(G,*)$ is a set of elements $A$ such that $\vert A + A\vert$ is maximal, meaning that for $i\neq j$, $a_i+a_j=a_{i'}+a_{j'}$ if and only if $\{i,j\}=\{i',j'\}$).
It turns out that the size of the largest Sidon set in $\mathbb{F}_2^{2k}$ is at least $2^k$, and can be explicitly obtained from the following construction of Lindström (see also this more recent paper by Sidorenko on related topics): consider all elements of the form $(\mathbf{x},\mathbf{x}^3)$ where we express $\mathbf{x}\in GF(2^k)$ as a $k$-dimensional vector over $\mathbb{F}_2$ with respect to some basis. It turns out that this forms a Sidon set, and moreover, given $(\mathbf{x},\mathbf{x}^3)+(\mathbf{y},\mathbf{y}^3)=(\mathbf{u},\mathbf{v})$, one can solve for $\mathbf{x}$ (and therefore $\mathbf{y}$) by solving a quadratic equation in $GF(2^k)$. I'm guessing this can be done in $\text{poly}(k)$ time if you're principled about the construction/representation of $GF(2^k)$, but note that this isn't super trivial because the field has characteristic two so the quadratic formula won't help (see this for potentially more info).
Moving back to your case, this means that the encoding $\mathbf{x}\mapsto (\mathbf{x},\mathbf{x}^3)$ when interpreting $\mathbf{x}\in GF(2^n)$ should give you what you want.


Is the following optimization problem (another variant to a previous problem) NP-hard? This problem is a following up question on  this one. The only difference is the addition of $3^{rd}$ constraint "$\sum_{i} x_{ij} \le M$", where M is a constant number. This constraint essentially states that each "node" can only take M incoming edges at most.

Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$ and is also a transitive closure, is given. E.g. $S=\{(1,2), (2,3), (1,3), (2,4), (1,4)\}$. For each element $(i,j)$, we have weight $w_{ij}=c(i)>0$, where $c$ is some benefit function, and a binary decision variable $x_{ij}$. The optimization problem is defined as follows:

$$\text{maximize} \sum_{(i,j)\in S} w_{ij}x_{ij} $$
$$\text{s.t.} x_{ij}+x_{ik} \le 1 $$
$$x_{ij}+x_{jk} \le 1 $$
$$\sum_{i} x_{ij} \le M$$

Note this problem is not the Maximum Weighted  Matching problem as edges that share the same end point are allowed.

Lemma. The problem is NP-hard.

Proof. The proof is by reduction from Set Cover with sets of size at most 3 (which itself is NP-hard by an easy reduction from 3D-matching).  Given a collection of sets, each of size at most 3, and an integer $k$, the reduction outputs an instance of your problem where the set $S$ contains the edges of the following DAG: For each element $x$, create an element-vertex $v(x)$.  For each set $s$, create a set-vertex $v(s)$.  Create a root vertex $r$.  Add edges from every vertex (except the root) to the root.  For each set $s$ and element $x\in s$, add edge $(v(x), v(s))$.  All edges have weight 1, and $M\ge 3$ is the number of sets minus $k$.

To show that the reduction is correct, we show that there is a set cover of size $k$ if and only if there is a solution to your problem of cost $M+n$, where $n$ is the number of elements.

(only if). Assume there is a set cover of size $k$.  For the instance output by the reduction, consider a solution with the following edges.  From each element-vertex $v(x)$, take the edge to some $v(s)$ such that $x\in s$ and $s$ is in the set cover.  (Note that each $v(s)$ has at most $3\le M$ edges into it.) From each set-vertex $v(s)$ where $s$ is not in the cover, take an edge from $v(s)$ to the root.  In this solution, the root has $M$ chosen edges into it, and each element-vertex has an edge leaving it, so the total number of edges in the solution is $M+n$.

(if). Conversely, suppose the instance output by the reduction has a solution with $M+n$ edges.  Among these edges (by the ILP constraints), the root has at most $M$ (incoming) edges.  Likewise, the solution has at most one edge out of each of the $n$ element-vertices.  Since the solution has $M+n$ edges, and every edge either enters the root or leaves an element vertex, it follows that the solution has exactly $M$ edges entering the root, and exactly one edge leaving each element-vertex, and that no edge in the solution does both, that is, no edge goes from an element-vertex to the root.

It follows that the solution consists of exactly $M$ edges from set-vertices to the root, and exactly $n$ edges from element-vertices, which (by the ILP constraints) must go to the set-vertices that don't have edges to the root in the solution.  There are $k$ of those set-vertices.  Hence, there is a set cover of size $k$. $~~\Box$