Uses of $\infty$-categories in TCS I'm not a theoretical computer scientist. I'm a stable homotopy theorist using $\infty$-categories. I've seen applications of category theory and topos theory to theoretical computer science, and I was wondering if there was any way one could use $\infty$-categories (and preferably for me, stable homotopy theory) in theoretical computer science. I think HoTT mught be one such application, but I may very well be wrong because I know close to nothing about HoTT. (So I also don't know how HoTT is used in TCS.)

Applying higher homotopy-theoretic ideas to CS is still a very nascent field! My understanding is that it's not even that old as a mathematical field.

Certainly HoTT is the central impetus for such ideas. Even there though, there only have been few applications of category theory of "dimension" higher than 2.

One nice "computer science-y" one is Homotopical Patch Theory by Anguili et al. They show that some common operations and properties inherent git like version control systems can be best understood using homotopy type theory.

Another rather unrelated train of thought is some interesting work on the relationship between (2-)Homology theory and confluence of term rewrite systems (or more complex structures such as higher algebras). Some examples are

Y. Guiraud Confluence of linear rewriting and homology of algebras .

Y. Lafont & A. Proute Church-Rosser property and homology of monoids.


A possibly new representation of DAGs I had an idea for a way of representing DAGs, it's very easy to explain:

Each node in the DAG is given an array of n integers. If it is possible to traverse from A to B then each of B's integers must be greater than each of A's respective integers.

For example the graph:

A o - > o C
    \
     ->
B o - > o D

Could be represented by:

A = [0,1]
B = [1,0]
C = [1,2]
D = [2,2]

I have a few questions:

Has such a representation been thought up before?
If no, would you help me to design an algorithm that generates the arrays of integers given a DAG?

[Revised.] I think that there has been a little confusion about what I was referring to in my original answer. I am revising it in order to better describe the result.

Note that your representation will only be capable of representing transitively-closed DAGs, i.e. partial orders; and this representation is a previously-studied one for partial orders. For instance, a paper by Mihalis Yannakakis shows that determining whether a partial order (equivalently, a transitively-closed digraph) has such a representation is NP-complete for n ≥ 3, but feasible if n ≤ 2.

Also, because the representation describes transitively closed DAGs, the body of research on the Transitive Closure problem is a reasonable place to look for related representations. My original response described a representation which, as it turned out, was strictly less general than the representation in terms of vectors. However, your representation has some similarities to the tree-cover representation of transitively closed DAGs (see Efficient management of transitive relationships in large data and knowledge bases: also described briefly in this article).

Without loss of generality, if the DAG has more than one 'source' (vertex with in-degree 0), add a virtual 'root' which can reach all of the sources. The entire DAG then has a spanning tree.
For each vertex, define an interval [ av , bv ] to each vertex v, in such a way that the interval at each node contains the intervals of all its descendants. (For instance, the upper bound bv for each v can be taken to be the post-fix order of the vertex in the tree; the lower bound av is the minimum of these post-fix values for the sub-tree.)
To represent directed edges which are not in the tree, each node keeps a list of the intervals of the different nodes which are reachable from it. (For any given sub-tree which is reachable from a given node, it suffices to record the interval belonging to the root of that sub-tree.)

Thus, the in-bound edges of each vertex is represented by the single interval [ av , bv ] , and its outbound edges are represented by a union of disjoint intervals which strictly contain the intervals of vertices that it can reach.

Some observations:

The vector representation is related to the interval nesting condition by using higher dimensional "intervals". Without loss of generality, the length n of the array xv at each vertex is even (by buffering with a final dummy co-ordinate if needed). Let m = n/2. Partition the coefficients as
$$ \mathbf x^v \;=\; [ \;a^v_1 \;,\; \ldots \;,\; a^v_m \;;\; c^v_1 \;,\; \ldots \;,\; c^v_m \;] $$
For each 1 ≤ j ≤ m , let $$ U_j = \left( \max_v \;\; a^v_j \right) + \left( \max_v \;\; c^v_j \right). $$ Then, we may define for each node an m-fold cartesian product of intervals,
$$ I^v \;=\; [\;a^v_1\;,\; U_1-c^v_1 \;] \times \cdots \times [\;a^v_m\;,\; U_m-c^v_m \;]. $$
Two such "$m$-dimensional intervals" nest if and only if the corresponding vectors have the appropriate ordering relations. It is trivial to verify that the intervals nest only if the corresponding vectors are ordered; for the converse, we depend on none of the coefficients in the graph being larger than the corresponding bounds Uj .
It is not clear to me whether the representation by vectors and by tree-covers are efficiently interconvertible; however it is easy to show that the case n = 2 corresponds exactly to the representation of directed trees in terms of tree-covers (i.e. the two representations are efficiently and reversibly inter-convertible, essentially by the technique I described above). Thus, the dimension may in some sense correspond to how tree-like the digraph is.


Super Mario Flows in NP? One classical extension of the max-flow problem is the "max-flow over time" problem: you are given a digraph, two nodes of which are distinguished as the source and the sink, where each arc has two parameters, a capacity-per-unit-time and a delay. You are also given a time horizon $T$. The goal is to compute a flow over time which gets the maximum amount of material from the source to the sink by time $T$. A flow of maximum value can be computed in polynomial time by a clever classical reduction to min-cost max-flow.

I am interested in an extension to this model where edges have a third "life-span" parameter. If an arc has life-span $\ell$, and $t$ is the earliest time at which positive flow is sent through the arc, then we destroy the arc at time $t+\ell$. You can think of this as like the platforms in Super Mario Brothers which fall away/are destroyed shortly after you step on them, or you can think of them as batteries needed to power the edges, which cannot be turned off after they are turned on. (Edit:) The decision problem is, when also given a flow value lower bound $B$, whether one can schedule a flow meeting both the time horizon upper bound and flow value lower bound.

So far I can see that this problem is strongly NP-hard (via 3-partition). But, I do not actually know if it is in NP: is there any guarantee of a way to express a solution compactly? In the classical version, some special type of optimal flow is used to circumvent this problem.

Note: the model above is a little underspecified, since you may allow or disallow the stockpiling of flow at nodes, and you may have a discrete time model or a continuous one. Resolving the question for any of these models would be excellent.

It's been a long time but I am pretty sure this problem is in P.

I wrote my PhD dissertation about this in 1995. See "Efficient Dynamic Network flow algorithms" by Bruce Hoppe submitted to Cornell CS dept. Online at http://dspace.library.cornell.edu/bitstream/1813/7181/1/95-1524.pdf

See Chapter 8 "Extensions" section 8.1 about "mortal edges"


Is #CYCLE #P-complete? We know that #SAT is #P-complete. We also know that problems with polynomial decision versions like PERMANENT are #P-complete. Is it true that finding the number of simple cycles in a graph, i.e. #CYCLE is also #P-complete? This is also a problem with decision version solved in polynomial time.

I suppose that it is either not-known or false, because it might be used a a popular example in textbooks like Arora and Barak's book, etc.

This is one of the problems (very briefly) discussed by Valiant, "The Complexity of Enumeration and Reliability Problems", SIAM J. Comput. 1979, doi:10.1137/0208032. See the mention of "elementary cycles" near the top of p. 417. Valiant gives a Turing reduction from the number of Hamiltonian cycles.


Software package for decomposing quantum circuits Is there any software package allowing decomposition of unitaries from $U(2^n)$ into quantum circuits over a predefined universal gate set?

This package (CUGates.m) was announced on the arXiv a couple of days ago which could be useful for you. It uses Mathematica. I haven't tried it out though, and it may or may not do what you need. From the abstract:

  This paper presents a highly efficient decomposition scheme and its
  associated Mathematica notebook for the analysis of complicated
  quantum circuits comprised of single/multiple qubit and qudit quantum
  gates. In particular, this scheme reduces the evaluation of multiple
  unitary gate operations with many conditionals to just two matrix
  additions, regardless of the number of conditionals or gate
  dimensions. This improves significantly the capability of a quantum
  circuit analyser implemented in a classical computer. This is also the
  first efficient quantum circuit analyser to include qudit quantum
  logic gates.


One sided approximation degree Given a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, let $P_{i,\epsilon}$ be minimum multivariate polynomial such that $P_{i,\epsilon}=i\iff f=i$,  $P_{i,\epsilon}\in(i-\epsilon,i+\epsilon)\iff f=1-i$ where $\epsilon\in(0,1)$ at each $i\in\{0,1\}$.

Is atleast for one of $i\in\{0,1\}$,  degrees of $P_{i,\epsilon},P_{i,\epsilon/2}$ polynomially always related? They should be, however I cannot find a reference.

Straight forward interpolation arguments seems to fail as $\epsilon$ gets closer to 1 (but not exactly $1$).

I don't think they are polynomially related. Consider the OR function on n bits. There is a polynomial $p(x) = \frac{1}{n} (x_1 + x_2 + \ldots + x_n)$, which approximates it with one sided error $\epsilon = 1- \frac{1}{n}$ because on the all zero input the polynomial is zero, and on any other input its value is between $\frac{1}{n}$ and 1.

However any polynomial approximating the OR function to one sided error $\epsilon/2$ (which is approximately $1/2$) is a bounded-error approximation of OR which is known to require degree $\Omega(\sqrt{n})$.


Finding optimal subset for quadratic function Given a set of $n$ elements $e_1,...e_n$ where each element $i$ is associated with two positive integers $\alpha_i$ and $\beta_i$. Given another integer $\lambda$, the goal is to find a  set $S$ of elements such that $(\lambda - \sum_{e_i \in S}\alpha_i)^2 + \sum_{e_i \in S}\beta_i$ is minimize (for $\sum_{e_i \in S}\alpha_i < \lambda, a_i >0, b_i >0$).
i'm looking for an exact or an approximate polynomial solution (my tries shows that a greedy solution (with respect to $\beta$ or the additional cost does not yield good approximation).

For all $\beta_i = 0$, asking whether one can get objective function value $1$ is equivalent to Subset Sum, and therefore NP-complete. Simple reductions from Subset Sum also prove that it is NP-complete to approximate the objective function within any factor polynomial in $n$.

We can reduce the $\beta_i = 0$ case to the case where $\beta_i = 1$ by just setting all $\beta_i$ values to $1$ and scaling both $\lambda$ and all $\alpha_i$'s by the same (large) integer factor. Then the $\beta_i$'s dont affect the objective function significantly anyway.

On the other hand, if all the integers $\alpha_i$ are small, one can solve the problem in pseudo-polynomial time - similar to the pseudo polynomial time algorithm for the Knapsack Problem. Thus for practical applications i'd expect that you can get good results by dividing down all the $\alpha_i$'s (and $\lambda$) by the same factor so that they become (relatively) small, round to the nearest integer, and solve using the Knapsack-like DP.


Is the following problem in P or in NP? Given an integer $K$, a set of tasks $T=\{a_1,b_1,\dots,a_n,b_n\}$ with sequence dependent execution times $E:T \times T \rightarrow \mathbb{N}$ and precedence constraints on $T$ of the following structure:

Does an ordering function $F:T\rightarrow \{1,2,\dots, 2n\}$ exist such that $F(b_n) \leq K$ ($b_n$ is always the last task in the ordering)?
What is the computational complexity of the problem?

If arbitrary precedence constraints (or any partial orderings) are allowed then the problem is NP-Complete (becomes Jobshop / Flowshop or their variant). The question is what is the complexity in the case when the tasks have the precedence constraints with the fixed structure?

The problem can be solved in $O(n^2)$:

Denote $A=\{a_1,\ldots,a_n\}, B=\{b_1,\ldots,b_n\}$.
We will build a graph in which every node $(i,j,x)$ will denote which $a$'s and $b$'s we have already executed and $x$ is a bit representing if the last task was $a$.

Construct the product graph $$G_p=(V_p, E_p)$$
$$V_p = A\times B\times \{0,1\}$$
$$E_p = \{((a_i,b_j,x),(a_{i+1},b_j,0))\mid x\in\{0,1\},j\leq i\in[n-1]\}$$
$$ \cup \{((a_i,b_j,x),(a_i,b_{j+1},1)\mid  x\in\{0,1\},j\leq i+1\in[n]\}$$
Assign weights:
$$w(((a_i,b_j,0),(a_{i+1},b_j,0)))=E(a_i,a_{i+1})$$
$$w(((a_i,b_j,1),(a_{i+1},b_j,0)))=E(b_j,a_{i+1})$$
$$w(((a_i,b_j,0),(a_i,b_{j+1},1))) = E(a_i,b_{j+1})$$
$$w(((a_i,b_j,1),(a_i,b_{j+1},1))) = E(b_j,b_{j+1})$$

And now simply find the shortest path with an algorithm of your choice (run time is linear in $|G_p|$, since it is a DAG).


Compared growth of the number of syntactic classes and Nerode classes. For a language L ⊆ Σ^*, define the syntactic congruence ≡ of L as the least congruence on Σ^* that saturates L, i.e. :

u ≡ v ⇔ (∀ x, y)[xuy ∈ L ↔ xvy ∈ L].

Now define the Nerode equivalence as the following right congruence :

u ∼ v ⇔ (∀ x)[ux ∈ L ↔ vx ∈ L].

Let [u] be the equivalence class of u with respect to ≡ and 〈u〉 with respect to ∼.
Now define i(n) to be the number of different [u]  for u of size n, and define j(n) in a similar fashion for ∼.

Now the question is, how do the two functions relate ?

For instance, a standard theorem (Kleene-Schützenberger, I believe) says that i(n) is bounded by a constant whenever j(n) is, and reciprocally.

Question: Is there any other result in this trend?  What if one of them is polynomial, for instance?

It seems that this paper     http://arxiv.org/abs/1010.3263  may be relevant to your question.

The abstract states:

The state complexity of a regular language is the number of states in the minimal deterministic automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the worst-case syntactic complexity taken as a function of the state complexity $n$ of languages in that class. We study the syntactic complexity of the class of regular ideal languages and their complements, the closed languages. We prove that $n^{n-1}$ is a tight upper bound on the complexity of right ideals and prefix-closed languages, and that there exist left ideals and suffix-closed languages of syntactic complexity $n^{n-1}+n-1$, and two-sided ideals and factor-closed languages of syntactic complexity $n^{n-2}+(n-2)2^{n-2}+1$.

Thus, as far as I understand, this  answers your question about the sizes of syntactic and Myhill-Nerode semigroup: in general, syntactic congruence may have exponentially many classes than Myhill-Nerode relation.

The last comment. Usually the finitness of both semigroups for regular languages is attributed to M.Rabin and D.Scott (Finite automata and their decision problems. IBM Jourmal. April 1959). In particular, it follows from the text of Rabin and Scott that the number of syntactic classes does not exceed $n^n$, where $n$ is the number of Myhill-Nerode classes.


Computing Size of Set with Particular Jacobi Symbol in Poly-Time Background

Let $(\tfrac{a}{p})$ denote the Legendre symbol, defined for all integers $a$ and all odd primes $p$ by:

$(\tfrac{a}{p}) = \begin{cases}
\;\;\,0\mbox{ if } a \equiv 0 \pmod{p}
\\+1\mbox{ if }a \not\equiv 0\pmod{p} \mbox{ and for some integer }x, \;a\equiv x^2\pmod{p}
\\-1\mbox{ if there is no such } x. \end{cases}$

For any integer $a$ and any positive odd integer $n$ the Jacobi symbol is defined as the product of the Legendre symbols corresponding to the prime factors of $n$:

$(\frac{a}{n}) = (\frac{a}{p_1})^{\alpha_1}(\frac{a}{p_2})^{\alpha_2}\cdots (\frac{a}{p_k})^{\alpha_k}\mbox{ where } n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$

Fortunately, computing Jacobi symbol can be performed efficiently, without having to know the factorization of $n$.

Let $J_n^{+1} = \{a \in \mathbb{Z}_n^* \mid (\frac{a}{n}) = +1 \}$. Deciding membership in $J_n^{+1}$ is easy. The question is,

  Given an odd $n$, can we compute $\left|J_n^{+1}\right|$ in polynomial time?

The Jacobi symbols $(\frac{a}{n})$ which are $\pm 1$ are exactly those for which gcd$(a,n) =1$, and thus the number of these is $\phi(n)$, where $\phi$ is Euler's $\phi$-function. Now, if $n$ is not a perfect square, exactly half of these are $+1$ (this can be seen using the Chinese remainder theorem). Thus, if you know |$J_n^{+1}$|, you know $\phi(n)$. And given $\phi(n)$, you can factor $n$. So there is a polynomial-time algorithm for |$J_n^{+1}$| if and only if factoring $\in$ P.


Type, operation and function, and their limits First of all, sorry for my English.

I would like to know, when I want to define a new type (I'm currently developing a computer interpreted language), how can I determine which "functions" are fundamental operations for a particular type, and which "function" are external, in the sense that, I don't need this function to define the characterization of the type?.

Let me call "operations" to the "essential functions" of the type and "functions" to anything else that simply uses the type.

For example, we all agree (I suspect), that the sum, difference, product and division are good examples of "operations" that defines the type integer for example, or number in general, but an operation like factorial is more a function.

The question is, in a more general or theoretical point of view, where is the line between "function" and "operation" for the intended purpose? For example, for more abstract types like domain-specifics data structures, auxiliary classes or something more difficult than a "number", how or which test can I perform to say: that's a good as operation, or that's better being a function.

Depends on your definition of "fundamental". As Martin said, you can do pretty much anything with the few primitives in lambda calculus, for instance, or simply anything that is Turing complete. However, would that be useful in your problem domain?

I don't know the specifics of your language, but you should have some use in mind for it. Depending on its intended use, you may want to have certain operations as builtins. For instance, MATLAB is specialised to work with matrices, so it has a lot of built-in operations for them.

In summary: decide what is your language supposed to be good for, and tweak your types and operations to that effect.

There are two kinds of operations that I'd make into built-ins:

those that can't be implemented by the user of your language without breaking the intended abstraction (i.e. accessing implementation details). For instance, I'd need something to increment an integer variable by 1.
the operations that are commonly used and that can be made much more efficient and/or convenient by taking advantage of implementation details. I could use a loop to increment something by 5, but it'd normally be much more efficient to do it in one go.


Where is the proof that Coq + Excluded Middle is consistent I've seen (and heard) it claimed that it is safe to add the classical axiom of excluded middle to Coq, but I can not seem to find a paper supporting this claim. The papers I see listed on the Coq wiki about excluded middle are showing inconsistency with impredicative Set.

Indeed, it seems that Coquand states that adding Excluded Middle (an inhabitant of $A+\neg A$) is inconsistent for CoC in section 4.5.3 of his description(PDF) of the metatheory of CoC. However, this section is a bit abstruse to me, so I may very well be misreading him.

Actually, in section 4.5.3, he doesn't quite say that EM+impredicativity is inconsistent. He says that when you assume it, the model must becomes degenerately proof-irrelevant (the interpretation of all types other than Prop can  have at most one element). Andy Pitts describes a similar phenomenon "Non-trivial Power Types Can't Be Subtypes of Polymorphic Types".

For predicative versions of type theory, it's probably easier to just do the consistency proof than to Google for it -- universe stratification gives you everything you need for the simple-minded set-theoretic model of types (i.e., types are sets, terms are maps) to work out. Just observe that sets are closed under indexed sums and products, and get cozy with the axiom of replacement when interpreting universes. This is academic bad practice, of course, but the proof is still worth doing for yourself.


Natural candidates for the hierarchy inside NPI Let's assume that $\mathsf{P} \neq \mathsf{NP}$. $\mathsf{NPI}$ is the class of problems in $\mathsf{NP}$ which are neither in $\mathsf{P}$ nor in $\mathsf{NP}$-hard. You can find a list of problems conjectured to be $\mathsf{NPI}$ here.

Ladner's theorem tells us that if $\mathsf{NP}\neq\mathsf{P}$ then there is an infinite hierarchy of $\mathsf{NPI}$ problems, i.e. there are $\mathsf{NPI}$ problems which are harder than other $\mathsf{NPI}$ problems.

  I am looking for candidates of such problems, i.e. I am interested in pairs of problems
  - $A,B \in \mathsf{NP}$,
  - $A$ and $B$ are conjectured to be $\mathsf{NPI}$,
  - $A$ is known to reduce to $B$,
  - but there are no known reductions from $B$ to $A$.

Even better if there are arguments for supporting these, e.g. there are results that $B$ does not reduce to $A$ assuming some conjectures in complexity theory or cryptography.

Are there any natural examples of such problems?

Example: Graph Isomorphism problem and Integer Factorization problem are conjectured to be in $\mathsf{NPI}$ and there are argument supporting these conjectures. Are there any decision problems harder than these two but not known to be $\mathsf{NP}$-hard?

Group Isomorphism $\leq_m$ Graph Isomorphism $\leq_m$ Ring Isomorphism. Also Integer Factoring $\leq_m$ Ring Isomorphism [Kayal and Saxena]. Also Graph Automorphism $\leq_m$ Graph Isomorphism.

Not only are there no known reductions the other way, but there is provably no
$\mathsf{AC}^0$-reduction from Graph Iso to Group Iso [Chattopadhyay, Toran, and Wagner].

Note that a reduction from Ring Isomorphism to Graph Isomorphism would also provide a reduction from Integer Factoring to Graph Isomorphism. To me, such a reduction would be surprising though perhaps not shocking.

(For Graph Automorphism vs Graph Isomorphism, their counting versions are known to be equivalent to one another and equivalent to deciding Graph Isomorphism. However, that's not necessarily saying much, as the counting version of bipartite matching is equivalent to the counting version of SAT.)

I don't think there is a real consensus as to which, if any, of these are actually in $\mathsf{P}$. If any of these problems is $\mathsf{NP}$-complete then $\mathsf{PH}$ collapses to the second level. If factoring is $\mathsf{NP}$-complete, then it collapses to the first level, i.e. $\mathsf{NP} = \mathsf{coNP}$.

Also, I seem to recall that using techniques similar to Ladner one can show that any countable partial ordering can be embedded in the ordering $\leq_{m}$ on the problems in $\mathsf{NP}$ (so it's not just a hierarchy, but an arbitrarily complicated countable partial order).


Local Smoothness vs optimisation in combinatorial problems Local smoothness is often mentioned in literature analysing different heuristics and meta-heuristics for combinatorial optimisation.  What is meant precisely by local smoothness is often left out, but one definition is "A landscape with small (average) fitness differences between neighboring points is called smooth". Additionally I have read of at least one measure (auto-correlation) that quantifies this.

I am interested however in the relationship between smoothness and optimisation processes.  The extent of the detail in literature seems to be local smoothness is good for optimisation and ruggedness is bad.  Could anyone further explain the relation between effective optimisation and local smoothness, and/or point to literature that delves into this more deeply.

It sounds like you need to make your question much more precise or pick up a good book on smooth optimization and marvel at what smoothness makes possible. See for instance "Numerical Optimization" by Nocedal and Wright (Springer).


Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$? Result 1: Linial-Mansour-Nisan theorem says that the fourier weight of the functions computed by the $\mathsf{AC}^0$ circuits is concentrated on the subsets of small size with high probability.

Result 2: The $\mathsf{PARITY}$ has its fourier weight concentrated on the co-efficient of degree $n$.

Question: Is there a way to prove(if provable) $\mathsf{PARITY}$ is not computable by $\mathsf{AC}^0$ circuits via/using the results 1 and 2 ?

LMN theorem shows that if f is a boolean function$(f:\{-1,1\}^n \rightarrow \{-1,1\})$ computable by an $\text{AC}^0$ circuit of size M,

$$\sum_{S:|S|> k} \hat f(S)^{2} \leq 2^{-\Omega(k/(\log M)^{d-1})}$$

$\Rightarrow \hat f([n])^{2} \leq 2^{-\Omega(n/(\log M)^{d-1})}$

$\Rightarrow |\hat f([n])| \leq 2^{-\Omega(n/(\log M)^{d-1})}$

$|\hat f([n])|$ is nothing but the correlation of f with the parity function $(\prod_{i = 1}^{n}x_i)$. Let $\delta$ be the fraction of inputs where $f$ differs from $PARITY$.

\begin{align}
1 -2 \delta \leq |1 - 2\delta| &= |\hat f([n])| \leq 2^{-\Omega(n/(\log M)^{d-1})}\\
\Rightarrow \delta &\geq 1 - 2^{-\Omega(n/(\log M)^{d-1})}
\end{align}

So, if M is $poly(n)$, for $f$ to be equal to $PARITY$,

\begin{align}
\delta &\leq \frac{1}{2^n}\\
\Rightarrow 2^n &\geq 2^{(cn/(\log M)^{d-1})}\\
\Rightarrow (\log M)^{d-1} &\geq (c-1)n \\
\Rightarrow M &\geq 2^{\Omega (n^{1/d-1})}
\end{align}

So, LMN theorem not only proves that $PARITY$ cannot be computed by $AC^{0}$ circuits, it also shows that $PARITY$ has low correlation with $AC^{0}$ circuits.


What is the difference between a second preimage attack and a collision attack? Wikipedia defines a second preimage attack as:

  given a fixed message m1, find a different message m2 such that hash(m2) = hash(m1).

Wikipedia defines a collision attack as:

  find two arbitrary different messages m1 and m2 such that hash(m1) = hash(m2).

The only difference that I can see is that in a second preimage attack, m1 already exists and is known to the attacker. However, that doesn't strike me as being significant - the end goal is still to find two messages that produce the same hash.

What are the essential differences in how a second preimage attack and collision attack are carried out? What are the differences in results?

(As an aside, I can't tag this question properly. I'm trying to apply the tags "cryptography security pre-image collision" but I don't have enough reputation. Can someone apply the appropriate tags?)

I can motivate the difference for you with attack scenarios.

In a first preimage attack, we ask an adversary, given only $H(m)$, to find $m$ or some $m'$ such that $H(m')$ = $H(m)$. Suppose a website stores $\{username, H(password)\}$ in its databases instead of $\{username, password\}$. The website can still verify the authenticity of the user by accepting their password and comparing $H(input) =? H(password)$  (with probability of $1/2^n$ for some large $n$ for false positives). Now suppose this database is leaked or is otherwise comprimised. A first preimage attack is the situation where an adversary only has access to a message digest and is trying to generate a message that hashes to this value.

In a second preimage attack, we allow the adversary more information. Specifically, not only do we give him $H(m)$ but also give him $m$. Consider the hash function $H(m) = m^d \mod{pq}$ where $p$ and $q$ are large primes and $d$ is a public constant. Obviously for a first preimage attack this becomes the RSA problem and is believed to be hard. However, in the case of the second preimage attack finding a collision becomes easy. If one sets $m' = mpq + m$, $H(mpq + m) = (mpq + m)^d \mod{pq} = m^d \mod{pq}$. And so the adversary has found a collision with little to no computation.

We would like one way hash functions to be resistant to second preimage attacks because of digital signature schemes, in which case $H(document)$ is considered public information and is passed along (through a level of indirection) with every copy of the document. Here an attacker has access to both $document$ and $H(document)$. If the attacker can come up with a variation on the original document (or an entirely new message) $d'$ such that $H(d') = H(document)$ he could publish his document as though he were the original signer.

A collision attack allows the adversary even more opportunity. In this scheme, we ask the adversary (can I call him Bob?) to find any two messages $m_1$ and $m_2$ such that $H(m_1) = H(m_2)$. Due to the pigeonhole principle and the birthday paradox, even 'perfect' hash functions are quadratically weaker to collision attacks than preimage attacks. In other words, given an unpredictable and irreversible message digest function $f(\{0,1\}^*) = \{0,1\}^n$ which takes $O(2^n)$ time to brute force, a collision can always be found in expected time $O(sqrt(2^n)) = O(2^{n/2})$.

Bob can use a collision attack to his advantage in many ways. Here is one of the simpliest: Bob finds a collision between two binaries $b$ and $b'$ ($H(b) = H(b')$) such that b is a valid Microsoft Windows security patch and $b'$ is malware. (Bob works for Windows). Bob sends his security patch up the chain of command, where behind a vault they sign the code and ship the binary to Windows users around the world to fix a flaw. Bob can now contact and infect all Windows computers around the world with $b'$ and the signature that Microsoft computed for $b$. Beyond these sorts of attack scenarios, if a hash function is believed to be collision resistant, that hash function is also more likely to be preimage resistant.


The computational complexity of matrix multiplication I am looking for information about the computational complexity of matrix multiplication of rectangular matrices. Wikipedia states that the complexity of multiplying $A \in \mathbb{R}^{m \times n}$ by $B \in \mathbb{R}^{n \times p}$ is $O(mnp)$ (schoolbook multiplication).

I have a case where $m$ and $n$ are much smaller than $p$, and I was hoping to get better complexity than linear in $p$, on the expense of making the dependence on $m$ and $n$ worse than linear.

Any ideas?

Thanks.

Note: the reason I am hoping for it to be possible is because of the well known result of less than cubic dependence in $p$ if $m=n=p$ (when matrices are all squares).

Classical work of Coppersmith shows that for some $\alpha > 0$, one can multiply an $n \times n^\alpha$ matrix with an $n^\alpha \times n$ matrix in $\tilde{O}(n^2)$ arithmetic operations. This is a crucial ingredient of Ryan Williams's recent celebrated result.

François le Gall recently improved on Coppersmith's work, and his paper has just been accepted to FOCS 2012. In order to understand this work, you will need some knowledge of algebraic complexity theory. Virginia Williams's paper contains some relevant pointers. In particular, Coppersmith's work is completely described in Algebraic Complexity Theory, the book.

A different strand of work concentrates on multiplying matrices approximately. You can check this work by Magen and Zouzias. This is useful for handling really large matrices, say multiplying an $n \times N$ matrix and an $N \times n$ matrix, where $N \gg n$.

The basic approach is to sample the matrices (this corresponds to a randomized dimensionality reduction), and multiplying the much smaller sampled matrices. The trick is to find out when and in what sense this gives a good approximation. In contrast to the previous strand of work which is completely impractical, sampling algorithms are practical and even necessary for handling large amounts of data.


Relation between different "complexity theories" and complex systems theory I know of at least 4 fundamentally different uses of the term "complexity theory":

the study of how hard a problem is to solve using some sort of computing machine (I am ignoring divisions within this category such as time vs space and parallel vs sequential models, etc.)
the expressiveness of a formal language
Kolmogorov complexity (which of course is uncomputable), or any attempts to define algorithms to approximate how hard it is to describe a phenomenon
complex systems theory, which honestly as far as I can tell is a little vague and imprecise about definitions, but seems to study the property of "emergence" or "the whole being greater than its parts"

Obviously it is linguistically possible that these are four completely different concepts that happen to share a name, but have there been any attempts to connect one of the first three definitions to the fourth (complex systems theory)?

For the relation between first and second look up descriptive complexity theory and finite model theory. This is a established branch of complexity theory and logic.


Hard extendability problems In extendability problem, we are given part of the solution and we want to decide whether we can extend it to a complete solution. Some extendability problems are efficiently solvable while other extendability problems transform an easy problem to hard one.

For instance, Konig-Hall theorem states that all cubic bipartite graphs
are 3-edge colorable but the extendability version becomes $NP$-complete if we are given the colors of some edges.

I'm looking for a survey paper of hard extendability problems where the the base problem is easy (or trivial as in the above example).

n-coloring the n x n Sudoku graph is trivial, but if some of the colors are given to you (the extendability version) it becomes NP-complete.

By the "Sudoku graph" I mean the natural graph whose associated coloring problem is Sudoku. Namely, suppose $n=k^2$ is a square. The graph will have $n^2$ vertices, which we will denote by $(r_1, r_2; c_1, c_2)$ for $r_1,r_2,c_1,c_2 \in [k] = [\sqrt{n}]$. For each fixed $(r_1,r_2)$, the vertices $(r_1, r_2; *, *)$ form an $n$-clique; for each fixed $(c_1, c_2)$ the vertices $(*, *; c_1, c_2)$ form an $n$-clique; and for each fixed $(r_1, c_1)$, the vertices $(r_1, *; c_1, *)$ form an $n$-clique.


What are natural examples of non-relativizable proofs? As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles).

Virtually all proofs seem to be relativizable, though.

What are good examples of non relativizable proofs, of the sort that a P=NP/P≠NP proof would need to be, that are not trivial or contrived?

(I am not a recursion theorist, so please pardon the lack of citations.)

[EDIT: better mathoverflow post]

As Steven notes, the canonical example is $\mathsf{IP} = \mathsf{PSPACE}$. This collapse does not relativize, in the sense that there is an oracle $A$, subject to which $\mathsf{IP}^A \ne \mathsf{PSPACE}^A$. The intuition why the known proof of this result avoids the relativization barrier is that it uses arithmetization (Yonatan alluded to this in a comment): an interactive protocol for the $\mathsf{PSPACE}$-complete problem TQBF is given by considering an extension of a quantified boolean formula to a low-degree polynomial over a suitably large field. If we are given a relativized boolean formula (with oracle gates), such an extension does not exist.

There is a refinement of the relativization barrier -- algebrization -- due to Aaronson and Wigderson. Generically, the arithmetization technique is not enough to circumvent the algebrization barrier. A complexity class inclusion $\mathsf{C} \subseteq \mathsf{D}$ algebrizes if for any oracle $A$ and any extension $\tilde{A}$ of $A$ to low-degree polynomials over a finite field, $\mathsf{C}^A \subseteq \mathsf{D}^{\tilde{A}}$. A separation $\mathsf{C} \not \subset \mathsf{D}$ algebrizes if for all $A$, and all extensions $\tilde{A}$, $\mathsf{C}^{\tilde{A}} \not \subset \mathsf{D}^{A}$. Aaronson and Wigderson show that $\mathsf{IP} = \mathsf{PSPACE}$ algebrizes, but many other results, including $\mathsf{NP} \not \subset \mathsf{P}$, do not.

A recent example of a technique that does not algebrize or relativize is Ryan Williams' proof that $\mathsf{NEXP} \not \subset \mathsf{ACC}$. The separation does not algebrize: there is an oracle $A$ and a low-degree extension $\tilde{A}$ such that $\mathsf{NEXP}^{\tilde{A}} \subset \mathsf{ACC}^A$.  Intuitively the reason why the proof avoids the barrier is that it relies on the existence of a faster-than-trivial satisfiability algorithm for $\mathsf{ACC}$ circuits, and the algorithm uses non-relativizing and non-algebrizing properties of such circuits. Ryan notes in the paper that all known faster-than-trivial satisfiability algorithms break down when oracles or algebraic extensions of oracles are added.

There is also an interesting approach to understanding relativization through logic. In an old manuscript, Arora, Impagliazzo, and Vazirani define a system of axioms such that the relativizing results are exactly those that follow from the axioms, while non-relativizing results are independent from the system. A paper by Impagliazzo, Kabanets, and Kolokolova does something similar for algebrization by introducing an additional axiom to the ones defined by Arora, Impagliazzo and Vazirani. They show that most known non-relativizing results follow from their axioms, while P vs NP, among others, is independent of them.

Apologies if I got something wrong, I am not quite an expert.


Does the problem "partition a vertex-weighted graph into $k$ balanced connected parts" have a standard name? Consider the following problem:

  Given an integer $k$ and a vertex-weighted graph $G=(V,E)$, find a
  partition of $V$ into $V_1,\ldots,V_k$ such that each subgraph induced by $V_i$ is connected, and such that $\max_i w(V_i)$ is
  minimized, where $w(V_i)$ is the total weight of the vertices in
  $V_i$.

It can be easily seen that this problem is NP-complete. For hardness, note that we can solve Partition by using a complete graph.

Questions: Does this problem have a standard name? Are there any papers that study this problem, or maybe slight variations of it? Is the problem still hard for sparse graphs? I am particularly interested in references that could lead to an implementation with good performance in practice.

The paper [Chlebikova, Approximating the maximally balanced connected partition problem in graphs, 1996] studies a related problem: They have $k=2$, and they maximize $\min(|V_1|,|V_2|)$. It should be a good place to start searching for related results, by following the citation graph.


Why can machine learning not recognize prime numbers? Say we have a vector representation of any integer of magnitude n, V_n

This vector is the input to a machine learning algorithm.

First question : For what type of representations is it possible to learn the primality/compositeness of n using a neural network or some other vector-to-bit ML mapping. This is purely theoretical -- the neural network could be possibly unbounded in size.

Let's ignore representations that are already related to primality testing such as : the null separated list of factors of n, or the existence of a compositeness witness such as in Miller Rabin. Let's instead focus on representations in different radices, or representations as coefficient vectors of (possibly multivariate) polynomials. Or other exotic ones as are posited.

Second question : for what, if any, types of ML algorithm will learning this be impossible regardless of the specifics of the representation vector? Again, let's leave out 'forbidden by triviality' representations of which examples are given above.

The output of the machine learning algorithm is a single bit, 0 for prime, 1 for composite.

The title of this question reflects my assessment that the consensus for question 1 is 'unknown' and the consensus for question 2 is 'probably most ML algorithms'. I'm asking this as I don't know any more than this and I am hoping someone can point the way.

The main motivation, if there is one, of this question is : is there an 'information theoretic' limit to the structure of the set of primes that can be captured in a neural network of a particular size? As I'm not expert in this kind of terminology let me rephrase this idea a few times and see if I get a Monte-Carlo approximation to the concept : what is the algorithmic complexity of the set of primes? Can the fact that the primes are Diophantine recursively enumerable (and can satisfy a particular large diophantine equation) be used to capture the same structure in a neural network with the inputs and outputs described above.

The question is, in my opinion, quite vague and involves some misunderstanding, so this answer attempts only to provide the right vocabulary and point you in the right direction.

There are two fields of computer science that directly study such problems. Inductive inference and computational learning theory. The two fields are very closely related and the distinction is a social and aesthetic one, rather than a formal one.

Fix a finite alphabet $A$ and the set of all languages $\mathcal{P}(A^*)$ consisting of finite-length words over $A$. This is everything you can express in terms of $A$. Now consider a family of languages $\mathcal{F} \subseteq \mathcal{P}(A^*)$. You can think of this as the concepts you are interested in. You often have to fix the family of concepts you care about because, as others have pointed out, the representation of the concept and presentation of data are extremely important.

Imagine a teacher who is going to teach you a concept. The teacher will choose one of the languages without your knowledge. The teacher will then present information to you about the language. There are many presentations. The simplest is to give you examples. A presentation of positive data is a function $f: \mathbb{N} \to A^*$ satisfying that

$$\bigcup_{i \in \mathbb{N}} f(i) = T, \text{ for some } T \text{ in } \mathcal{F}.$$

So, a presentation of positive data is an enumeration of the target concept, often with some additional fairness conditions thrown in. You can similarly ask for a presentation that labels words depending on whether they are in the language or not. Again, you can add additional conditions to ensure fairness and coverage of all words.

Suppose we have a family $Rep$ of representations of languages. That means every element $M$ of $Rep$ defines a language $L(M)$. Examples of representations are Boolean formulae, finite automata, regular expressions, systems of linear equations, domain specific programming languages, etc. Anything you want, really, except various condition are usually imposed to ensure the representation has basic tractability properties.

A passive learner is a function $p: \mathbb{N} \to Rep$ that makes a conjecture after seeing each word provided by the teacher. We may often require that the learner is consistent. Meaning, the language $L(p(i))$ should contain all the words $f(j)$ for $j \le i$. The learner stabilizes if the learner's guess for the target language does not change. Specifically, there should exist some index $k$ such that for all $j \ge k$, $L(p(j)) = L(p(j+1))$. The learner succeeds if the final language equals the target language.

Let me emphasise that this is only one specific formalisation of one specific learning model. But this is step zero before you can start asking and studying questions that you are interested in. The learning model can be enriched by allowing interaction between the learner and the teacher. Rather than arbitrary families of languages, we can consider very specific languages, or even specific representations (such as monotone Boolean functions). There is a difference between what you can learn in each model and the complexity of learning. Here is one example of a fundamental impossibility result.

  Gold [1967] No family of languages that contains all finite languages and at least one super-finite language is passively learnable from positive data alone.

One should be very very careful in interpreting this result. For example, Dana Angluin showed in the 80s that

  Angluin [1982] The class of $k$-reversible languages is passively learnable in the limit from positive data.

The class of $k$-reversible languages is infinite, contains super-finite languages, but interestingly, does not contain all finite languages. Now once you change the learning model, the fundamental results change.

  Angluin [1987] Regular languages are learnable from a teacher that answers equivalence queries and provides counterexamples. The algorithm is polynomial in the set of states of the minimal DFA and length of the maximal counterexample.

This is quite a strong and positive result and recently has found several applications. However, as always the details are important, as the title of the paper below already suggests.

  The minimum consistent DFA problem cannot be approximated within and polynomial
  , Pitt and Warmuth, 1989.

Now you may be wondering, how is any of this relevant to your question? To which my answer is that the design space for a mathematical definition of your problem is very large and the specific point you choose in this space is going to affect the kind of answers you will get. The above is not meant to be a comprehensive survey of how to formalise the learning problem. It's just meant to demonstrate the direction you may want to investigate. All the references and results I quote are extremely dated, and the field has done a lot since then. There are basic textbooks you could consult to obtain the sufficient background to formulate your question in a precise manner and determine if the answer you seek already exists.


A simple(?) funny combinatorial problem! Let we fix $0<E<1$ and an integer $t>0$.

for any $n$ and for any vector $\bar{c} \in [0,1]^n$ such that $\sum_{i\in [n]} c_i \geq E \times n$

  $A_{\bar{c}} :=|\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \times t \}| \geq \binom{ E \times n}{ t }$

I don't know if the statament is true o false.
I think it's true.

My intuition come from the observation that for the vectors $\bar{c} \in \{0,1\}^n$ (with the desidered property about the sum) we have $A_{\bar{c}}= \binom{ E \times n}{t}$; in this case we can only select subset from the set $\{ i ~|~ c_i = 1 \}$.

In the others case we can create good subset (s.t. the sum is greater then $E \times t$) using the coordinate in $\{ i ~|~ c_i > E \}$ but also, maybe, using few coordinate from the set $\{ i ~|~ c_i \leq E \}$ we could create other good set!

So,Prove it or find the bug! hoping that it could be a funny game for you!

Motivation of the question:

Suppose you have a random variable $X\in \{0,1\}^n$, a typical measure of "how much randomness" there is in $X$ is the min-entropy

$H_{\infty}(X) = min_{x} \{ -log(Pr[X = x]) \}$

In some intuitive sense the min-entropy is the worst case of the famous Shannon Entropy (that is the average case).

We are interested to lowerbound the min-entropy of the random variable $(Z=X \wedge Y| Y)$ where $Y$ is uniformely distributed over the set $\{ y ~|~ \sum_i y_i = t\}$.

Loosely speaking if we are lucky we can catch the bits of $X$ that have "good entropy" and so we if $H_{\infty}(X)\geq En$ then  $H_{\infty}(Z|Y)\geq Et$

  What is the probability that we are lucky?

The problem is well-studied one and there exists a lot of literature,
for example see Lemma A.3. in Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model

The conjecture in the post does not hold, but the weaker conjecture (with respect to the floor) mentioned in the comments does hold.  In fact, something stronger holds.

Lemma 1. The conjecture in the post does not hold.  That is, there is an instance satisfying the given assumptions where
$$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \, t \big\}\big| < \binom{ E \, n}{ t }.$$

Proof.
Consider the instance with $n=3$, $c=(1, 1, 0.7)$, $E=2.7/3=0.9$, and $t=2$.  Then $E\, t = 1.8$.
For the left-hand side, we have
$$\big|\textstyle\{ S \subseteq [3] : \sum_{i \in S}~ c_i \geq 1.8 \}\big| = 2$$
because any subset $S$ that does not contain both 1's sums to at most 1.7, and there are only two subsets ($\{1,1\}$ and $\{1,1,0.7\}$) containing both 1's. And the right-hand side is $\binom{ 2.7}{ 2 } = 2.7\cdot 1.7\,/\, 2 = 2.295>2. ~~~\Box$

The weaker conjecture suggested in the comments, namely the bound w.r.t. the floor, $\lfloor E\, n \rfloor$, does hold.  In fact something slightly stronger holds:

Lemma 2. Fix $0<E<1$, integers $n,t>0$,
and vector $c \in [0,1]^n$ with $\sum_{i\in [n]} c_i \geq E\, n$.
Then
$$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E\, t \big\}\big| \,>\, \binom{ \lfloor E\, n\rfloor}{ t } + \binom{ \lfloor E\, n\rfloor}{ t+1 } + \cdots + \binom{ \lfloor E\, n\rfloor}{ \lfloor E\, n\rfloor }.$$

Proof. Let $a=\lfloor E\, n\rfloor$. Assume WLOG that $a=E\,n$.  (Otherwise scale $E$ and each $c_i$ down by a uniform factor to make it so.  This maintains $\sum_i c_i \ge E\,n$ and changes neither which subsets sum to at least $E\,t$ nor the desired lower bound on the number of such subsets.)  Assume WLOG that $t\le a$ (otherwise the claim holds trivially).

Consider any subset $S\subseteq [n]$ of size at least $n-d$, where $d=a-\lceil a\,t/n\rceil \ge 0$. Since $\sum_{i\in[n]} c_i \ge a$ and $S$ contains all but at most $d$ elements (each of which is at most 1), we have $\sum_{i\in S} c_i \ge a-d = \lceil a\,t/n\rceil = \lceil E\,t\rceil \ge E\,t$, as desired.

The number of such subsets $S$ is

${n\choose n-d} + {n \choose n-d+1} + \cdots + {n \choose n-1} + {n \choose n}$

$ = {n\choose d} + {n \choose d-1} + \cdots + {n \choose 1} + {n \choose 0}$

$ > {a\choose d} + {a \choose d-1} + \cdots + {a \choose 1} + {a \choose 0}~~~$ (using $n>a$)

$ = {a\choose a-d} + {a \choose a-d+1} + \cdots + {a \choose a-1} + {a \choose a}.$

But $a-d = \lceil a\,t/n\rceil \le t$ (using $a/n = E < 1$), so the last sum is at least the desired lower bound on the number of good subsets. $~~\Box$


Knapsack with dependent profits (pairs of items) I'm working on a problem which MAY be reduced to the following version of Knapsack:

Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in the knapsack, then for some $i$ and $j$, the combined profit of $e_i$ and $e_j$ is NOT $p_i+p_j$. It could be lower or higher. Note that in general, profits could be additive, but for some pairs of elements, our new rule holds, and we know in advance the value of $profit(\{e_i\} \cup \{e_j\})$ for such pairs. As always we want to maximize total profit.

So my question is, has work been done on such a variant of knapsack? Are there papers that can I read to better understand this formulation? I am not well-versed with the entire literature of Knapsack, and I tried to search for this but came up empty.

This is a very interesting problem. But cannot be addressed in its general form. Assumptions need to be made in relation to the application domain. You may find the attached paper useful. The paper assumes strengths of value-related dependencies are imprecise.

please see this: https://link.springer.com/chapter/10.1007/978-3-319-63004-5_12


Complexity of convolution in the max/plus ring We can do convolution in $O(n\log n)$ for plus/multiply polynomials with FFT.  However, the approach doesn't seem very generalisable to rings in general.
Has there been any progress over the naive $O(n^2)$ convolution for the max/plus ring?

I should note that one can transform soft-max/plus into plus/product by doing exponentiation. Here $\text{soft-max}(x,y)=\log(e^x+e^y) = \max(x,y)  + \log(1+e^{\min(x,y)-\max(x,y)})$.

There is a more general question on mathoverflow, and I asked a similar question on CS.SE. jbapple provided a good answer. To quote:

"Necklaces, Convolutions, and X+Y", By Bremner et
al. shows a
$O\left(\frac{n^2(\lg \lg n)^3}{\lg^2 n}\right)$ algorithm
for this problem on the real RAM and a $O(n \sqrt{n})$ algorithm in
the nonuniform linear decision tree model.

Any improvement to this bound will shed light to a few tough open problems like sorting $X+Y$ and all pair shortest path.
If one of the functions is convex/concave, we can solve the problem in $O(n\log n)$ time. See "Speeding up Dynamic Programming", By Eppstein et al..


Property testing of triangular properties Several years ago I worked a few days with a collaborator on property testing of triangular property. We end up with a disappointing result that I am sharing here and for which I am asking if a better result is known, or if you have some ideas about the problem.

Let $K_n=(V,E)$ be the complete graph on $n$ vertices and $S$ be a set. Let $\phi:V\times V\rightarrow S$ be a function, and let $1>\epsilon>0$ be a real number.

We are interested in triangular properties, that is properties of triangles (sets of 3 items). Our final goal is to decide with high probability if a set violates "strongly" a triangular property (in the sense of the property testing.

definition
A triangular property $P$ is a function $P:S^3\rightarrow{0,1}$ that is invariant under permutations.
The function $\phi$ is said to have the property $P$ if for all triangles ${a,b,c}$ the value $P(\phi(a,b),\phi(b,c),\phi(c,a))$ is equal to 1.
The function $\phi$ is said to be at least $\epsilon$-far from having property $P$ if for all function $\psi:V\times V\rightarrow S$ having the property $P$ the functions $\phi$ and $\psi$ differ on at least $\epsilon\cdot n^2$ values.
Two triangles are said to be independent if their intersection is empty.
A triangle $v$ is said to be bad (with respect to $P$) if $P$ takes the value 0 on it.

Our result is a property tester for triangular properties :

Input: a function $\phi:V\times V \rightarrow S$ and a triangular property $P$.
Output: the answer to whether or not $\phi$ is $\epsilon$-far from having property $P$.

1) Select a random set of vertices $V'$ of size $\epsilon^{-1/3}n^{2/3}$.
2) Request all the values of the restriction of $\phi$ to the complete graph $K_{\epsilon^{-1/3}n^{2/3}}$ induced by $V'$
3) Check on all the triangles whether $P$ is satisfied or not.
4) Return 0 if a triangle is bad, and 1 otherwise.

How do we obtain this? the first step is a technical result that gives the proportion of disjoints triangles that violate $P$, then we use a probabilistic argument based on a balls and bins theorem, and the result follow. Clearly this algorithm is far from being optimal. The problem is in the technical result:

The technical result:
Suppose that $\phi$ is $\epsilon$-far from having property $P$. Let $B$ be a set of vertices so that $\phi$ induces a function that has property $P$ on the restriction of $K_n$ to $V-B$. Then the cardinality of $B$ is greater than $\epsilon\cdot n$.
Using a $B$ as defined before, There exists a family $C$ of independent triangles in $K_n$ such that
- each triangle in $C$ is bad,
- $|C|\geq\lfloor\frac{|B|}{3}\rfloor\geq \frac{\epsilon\cdot n}{3}-1$.

Clearly, the problem is that our lower bound on the size of $C$ is poor. It is a shame that we have no better bound since the bound on $B$ is great.
Since we have a bad lower bound on $|C|$, we cannot obtain an interesting complexity for the tester...

So, the question is : are you aware of a result on this problem ? And if not, have you got some better ideas that we have ?

Your problem is well-understood in the case $S = \{0,1\}$.  Here, the function $\phi$ can be viewed as the adjacency matrix of a graph $G_\phi$ on the vertex set $V$.  And $\phi$ satisfying a triangular property $P$ just means that $G_\phi$ is free of some collection $C_P$ of induced subgraphs, each on $3$ vertices.  Now, it is known [Alon-Fischer-Krivelevich-Szegedy '99] that any such property is testable (in the property testing sense) with query complexity, independent of $n$, bounded from above by a tower of exponentials of height polynomial in $1/\epsilon$.  In particular, when $P$ is 1 only when its input is $(1,1,1)$, the property corresponds to triangle-freeness in graphs for which the best upper-bound is the tower of exp's I mentioned and the best lower bound is slightly superpolynomial in $1/\epsilon$ [Alon '01].  If you want better dependence on $1/\epsilon$ at the cost of perhaps having some dependence on $n$, I don't believe anything much better than what you described is known.  The test you described is more or less folklore.

For arbitrary fixed $S$, I don't know if the testability question has been resolved.  I believe the framework of graph limits, especially the paper [Borgs-Chayes-Lovász-Sos-Szegedy-Vesztergombi '06], might show testability for hereditary properties of weighted graphs which would imply testability of your triangle properties.  But I don't know this fact for sure.


Factoring low-degree polynomials What is the fastest algorithm known for factoring polynomials with $n$ variables and total degree $\leq d$? Here, $n$ is growing and $d$ is fixed. Most work seem to consider the case when $d$ is growing and $n$ is fixed. I am interested in results both over finite fields and over rationals.

Let $\mathbb K$ be a field of characteristic $0$ or at least $d(d-1)+1$, and $p\in\mathbb K[x_1,\dotsc,x_n]$ be a polynomial of total degree at most $d$. If $d$ is fixed and $n$ is growing, one has the following complexity bounds for the reduction of the factorization of $p$ to the factorization of a degree-$d$ univariate polynomial: (The notation $\tilde{\mathcal O}(\cdot)$ ignores logarithmic factors.)

Deterministic algorithms:

$\tilde{\mathcal O}\left( \binom{n+d}{n}^4 \right)$ field operations, using naive multiplication algorithms;
$\tilde{\mathcal O}\left( \binom{n+2d-2}{n-1} d^\omega \right)$ field operations, if fast multiplication algorithms are availaible, where $2<\omega\le 3$ is an admissible exponent for linear algebra.¹

Probabilistic algorithms:

$\tilde{\mathcal O}\left(\binom{n+d}{n}\right)$ field operations, if fast multiplication algorithms are available.

Then, one has to factorize a univariate degree-$d$ polynomial. The complexity of this step does not depend on $n$ anymore, so the above bounds remain valid for the complete factorization algorithms. The only difference is in positive characteristic: Since no deterministic polynomial-time algorithm is known to factor a univariate polynomial, even the deterministic reduction yield a probabilistic algorithm. Nonetheless, if $d$ is really fixed and small, one can replace the probabilistic polynomial-time algorithm by a deterministic exponential-time one.

Note that the probabilistic bound $\tilde{\mathcal O}\left(\binom{n+d}{n}\right)$ is optimal up to logarithmic factors since $\binom{n+d}{n}$ is the size of the input.

More details can be found in the paper Improved dense multivariate polynomial factorization algorithms of Grégoire Lecerf (link without paywall).

Another reference, especially for fields of small characteristic, is E. L. Kaltofen & G. Lecerf, Factorization of multivariate polynomials (link without paywall), chapter 11.5 of G. L. Mullen and D. Panario, editors, Handbook of finite fields.

¹ The result needs to assume that $\omega>2$.


Using ϵ -unification and Knuth-Bendix completion to automatically proof theorems about groups This is a follow-up question. In my previous question, I presented Welder proof assistant and I stated that I want to automate proofs about basic field theory. The only answer to this post states that a combinatorial search is sufficient since the goals are easy. I'm looking for a more general technique.

I have read Equations and rewrite rules: a survey. In page 12, it reads:

  An abelian group theory unification algorithm is given by Lankford.

The idea is as follows. Given some context equations $\Delta$ from where we can deduce some other equations $\Delta \vDash \{x_i = y_i\}$, the unification process will give the neccesary substitutions to proof all the equalities in the right part using the formulas in $\Delta$.

Another interesting quote appears on page 28:

  This algorithm gave the first known solution to unification in group
  theory using for $\mathcal{B}$ the canonical set shown in the
  appendix.

In the appendix on page 33, I find a very interesting practical session. I have some questions on the power of the methods used and the actual results that I can expect after well-understanding this 30 pages heavy mathematical paper. I hope someone can give some orientation:

What is being simulated in the practical session? I describe what I think is happening. The canonical set $\mathcal{B}$ mentioned above corresponds to given axioms $R_1$, $R_2$ and $R_3$. Then some theorems about groups are deduced. I assume that this happens by application of the $\epsilon$-unification algorithm given at page 27 and the Knuth-Bendix completion. Am I right? Could you tell me what is exactly the role of each algorithm (page 27 and Knuth-Bendix) in the solution? If you think that I can use this scheme in my problem, what steps should I do, how should I integrate this algorithms?

This is going to be a somewhat incomplete answer, since you are asking some pretty broad questions about the applications of the techniques.

First let me start by saying that while the research in the field of equational logic and completion hasn't seen a complete revolution since 1980 (as compared to, say SMT) there have been substantial improvements, so bear in mind that techniques and tools have changed. My first recommendation would be to take a look at Term Rewriting and All That by Baader and Nipkow, which is slightly more up to date (but still almost 20 years old!). You might also want to check CiME as an implementation of some of these techniques.

The canonical set from the first example of the appendix is actually

$\begin{eqnarray}R1 &:& 0+X\rightarrow X\\R2&:&I(X)+X\rightarrow 0\\R3&:&(X+Y)+Z\rightarrow X+(Y+Z)\\R8&:&I(0)\rightarrow 0\\R11&:&X+0\rightarrow X\\R12&:&I(I(X))\rightarrow X\\R13&:&X+I(X)\rightarrow 0\\R14&:&X+(I(X)+Y)\rightarrow Y\\R17&:&I(X+Y)\rightarrow I(Y)+I(X)\end{eqnarray}$

For the life of me I can't understand why they adopted additive notation for non-commutative groups.

Note that the set $\{R1,R2,R3\}$ is not canonical, since e.g. $X+0$ does not reduce to $0$ (but $X+0=0$ is derivable in the equationnal system).

The canonical system was derived from the first 3 rules by application of Kuth-Bendix completion, and nothing else, $\varepsilon$-unification is not needed in this case. There are many papers that expand on this example, including, I think, the original paper which is sadly tough to find online. The wikipedia page is a good place to fish for references.

I'm not sure what advice to recommend for using these techniques in practice. I gave a reference to an existing tool, there are many others in various states of maintenance, see e.g. here.

I would also suggest taking a look at first-order theorem provers with equality and equality logic provers, e.g. Otter & Mace since they integrate these kinds of techniques and might be more suited to your needs, if you're trying to prove basic theorems in some algebraic theory.

I really suspect you might want some more specialized tools for Gröbner bases if you're trying to prove theorems about fields, since these are much more specialized (and much more powerful). Perhaps some people more familiar with computer algebra can point you in the right direction for this.


Size hierachy for uniform circuits There is the size hierarchy theorem for non-uniform circuits.

  Do we have any size hierarchy theorem for any kind of uniform circuits ?

(By uniform here, I mean DLOGTIME uniform. But I don't know if this matters.)

For example, do $O(n)$-size constant depth threshold circuits have less power than the ones with size $O(n^{10})$ or even super-polynomial ?

Regarding your last question: The paper Size-Depth Trade-offs for Threshold Circuits shows that the parity function requires depth-$d$ threshold circuits with $\ge n^{1+\epsilon(d)}$ wires, which is tight up to the function $\epsilon$.  But for gates not even $\Omega(n)$ lower bounds are known.


Why/when do we ever need transfinite loop variants? I do not understand why one would ever need a transfinite loop variant.

Why do natural-number-valued variants not suffice? My simple (but perhaps too naive) argument is: if a loop $L$ terminates from any initial state then there should be a trivial variant function $V$ which simply maps every state $s$ to the number of iterations needed for $L$ to terminate on $s$. Naturally, $V$ would be decreased by 1 with every iteration of $L$.

Can anyone provide an example of a simple deterministic while loop (no recursion, no reading of additional user provided input during runtime of the loop, no nondeterministic choices, etc.) that terminates on every initial state it is started from and yet requires a transfinite loop variant to prove its termination?

You are correct when you observe that for any particular terminating loop $L$ we may simply define the invariant "we're getting one step closer to termination". But proving that this is indeed a valid invariant may require transfinite induction!

For instance, we could write a loop that computes the Goodstein sequence. This is particular sequence of numbers which starts with any given number $n$ and it eventually terminates, but proving that it terminates for every $n$ requires transfinite induction to the ordinal $\epsilon_0$ (which is the limit of ordinals $\omega$, $\omega^\omega$, $\omega^{\omega^\omega}$, ...)! So, in order to show that a loop computing the Goodstein sequence terminates for every inital term $n$ we need an appeal to transfinite induction.

At this point we have two choices:

Use transfinite induciton to show the loop terminates, then "forget" that you used transfinite induction to show that the silly invariant "we're one step closer to the end" does the job.
Use a loop invariant which requires ordinal numbers but is informative because it is an obviously decreasing sequence that dominates the Goodstein sequence.

Take your pick.

In summary, it's not just about whether we can avoid ordinal numbers (we cannot avoid them completely), it's also whether we want to. Avoiding them might just complicate your life and lead to convoluted proofs of termination. Why would we do that?


Best way to determine the minimum dimension of a structure given only distances between points I came across this problem in an area of physics quite far removed from computer science, but it seems like the type of question that has been studied in CS, so I thought I'd try my luck asking it here.

Imagine you are given a set of points $\{v_i\}_{i=1}^n$ and list of some of the distances between points $d_{ij}$. What is the most efficient way to determine the minimum dimensionality of the space in which you need to embed these points? In other words, what is the smallest $k$ such that there exist a set of points in $\mathbb{R}^k$ satisfying the distances constraints $d_{ij}$. I would be equally happy with an answer for $\mathbb{C}^k$, but this seems harder.

I am happy to say that the distances need to match $d_{ij}$ only to within some constant accuracy $\epsilon$ and to have the points restricted to points on some lattice of constant spacing, in order to avoid issues of computing with reals.

Indeed, I would be quite happy with a solution for the decision version of this problem, where given $d_{ij}$ and $k$ you are asked whether or not such a set of vertices $\{v_i\}$ exist. Trivially the problem is in NP, since given a set of points in $\mathbb{R}^k$ it is easy to check that they satisfy the distance requirements, but it feels like there should be sub-exponential time algorithms for this particular problem.

The most obvious approach seems to be to try to build $k$-dimensional structures iteratively, by adding additional points one at a time and determining whether or not a new spatial dimension needs to be added at each iteration. The problem with this is that it seems you can run into ambiguities where there is more than one way to add a point to the existing structure, and it is not clear which one will lead to fewer dimensions as you continue to add more points.

Lastly, let me say that I know that it is easy to create lists of distances which cannot be satisfied in any number of dimensions (i.e. ones which violate the triangle inequality). However, for the instances I care about there will always be some minimum finite number of dimensions in which a satisfying set of points can be found.

This problem is sometimes called the low-dimensional Euclidean distance matrix completion or the low-dimensional Euclidean embedding of a weighted graph.

Saxe [Sax79] and Yemini [Yem79] independently showed by a simple reduction from the Partition problem that this problem is NP-complete even in the case of one dimension; that is, the following problem is NP-complete for k=1:

k-dimensional Euclidean distance matrix completion / k-dimentional Euclidean embedding of a weighted graph
Instance: A symmetric matrix M whose entries are either positive integers in binary or “unknown.”
Question: Can the unknown entries in M be filled by real numbers so that M becomes a distance matrix of points in the k-dimensional Euclidean space ℝk?
Equivalently,
Instance: A graph G where each edge has a positive integer weight written in binary.
Question: Can the vertices of G placed in the k-dimensional Euclidean space ℝk so that for each edge of G, the distance between the two endpoints equals to the weight of the edge?

Moreover, Saxe [Sax79] showed (by a more involved reduction from 3SAT) that the k-dimensional Euclidean distance matrix completion remains NP-hard even under the restriction that all known entries in M are either 1 or 2, for every positive integer constant k.  In particular, the problem is NP-complete even when the known entries in M are given in unary.  [Sax79] also contains some hardness results about approximate embedding.

By the way, I do not think that it is trivial that the problem is in NP; note that you need irrational coordinates in some cases when k>1.  I do not know if it is known to be in NP.

References

[Sax79] James B. Saxe.  Embeddability of weighted graphs in k-space is strongly NP-hard.  In Proceedings of the 17th Allerton Conference on Communications, Control, and Computing, pp. 480–489, 1979.  Also in James B. Saxe: Two Papers on Graph Embedding Problems, Department of Computer Science, Carnegie-Mellon University, 1980.

[Yem79] Yechiam Yemini.  Some theoretical aspects of position-location problems. In 20th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1–8, Oct. 1979.  DOI: 10.1109/SFCS.1979.39


Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates Let $f$ be a Boolean function and let's think about f as a function from $\{-1,1\}^n$ to $\{ -1,1 \}$. In this language the Fourier expansion of f is simply the expansion of f in terms of square free monomials. (These $2^n$ monomials form a basis to the space of real functions on $\{-1,1\}^n$. The sum of the squares of the coefficients is simply $1$ so $f$ leads to a probability distribution on square free monomials. Let's call this distribution the F-distribution.

If f can be described by a bounded depth circuit of polynomial size then we know by a theorem of Linial, Mansour and Nisan that the F distribution is concentrated on monomials of $\text{polylog } n$ size up to almost-exponentially-small weight. This is derived from Hastad switching lemma. (A direct proof would be most desirable.)

What happens when we add mod 2 gates? One example to consider is the function $IP_{2n}$ on $2n$ variables which is described as the mod 2 inner product of the first n variables and the last n variables. Here the F-distribution is uniform.

  Question: Is the F-distribution of a Boolean function described by
  bounded depth polynomial size AND, OR,
  MOD$_2$ circuit concentrated (up to
  superpolynomially small error) on $o(n)$
  "levels"?

Remarks:

One possible path to a counterexample would be to "glue somehow" various IP$_2k$ on disjoint sets of variables but I don't see how to do it. Perhaps one should weaken the question and allow assigning some weights to the variables, but I don't see a clear way for doing it either. (So referring to these two matters is also part of what I am asking about.)
I would speculate that a positive answer to the question, (or to a successful variation) will apply also when you allow mod$_k$ gates. (So asking the question was motivated by Ryan Williams' recent impressive ACC result.)
For MAJORITY the F-distribution is large (1/poly) for every "level".

  As shown by Luca, the answer to the question I asked is "no". The question that is left is to propose ways to find properties of the F distributions of Boolean functions that can be described by AND OR and mod 2 gates not shared by MAJORITY.

An attempt to save the question by talking about MONOTONE functions:

  Question: Is the F-distribution of a MONOTONE Boolean function described by
  bounded depth polynomial size AND, OR,
  MOD$_2$ circuit concentrated (up to
  superpolynomially small error) on $o(n)$
  "levels"?

We may speculate that we can even replace $o(n)$ by $\text{polylog} (n)$ so a counterexample for this strong version can be interesting.

Gil, would something like this be a counterexample?

Let $m$ be such that $n=m+\log m$, and think of an $n$-bit input as being a pair $(x,i)$ where $x$ is an m-bit string $(x_1,\ldots ,x_m)$ and $i$ is an integer in the range $1,\ldots,m$ written in binary.

Then we define $f(x,i):= x_1 \oplus \cdots \oplus x_i$

Now for each $i=1,\ldots,m$ the function f() has $1/m$ correlation with the Fourier character $x_1 \oplus \cdots \oplus x_i$, and so the "level i" has at least a $1/m^2$ fraction of the mass. (In fact more, but this should suffice)

f() can be realized in depth-3: put all the XORs in a layer, and then do the "selection" in two layers of ANDs, ORs and NOTs (not counting the NOTs as adding to the depth, as usual).


Can a term on normal form prove an illogical assertion? Suppose we take a language such as Agda and disable the features that make it consistent; for example, universe polymorphism, structural recursion checks and similar. Suppose then that we take a term in normal form, i.e., with no redex left. Could that term prove an absurd claim such as, for example, 1 = 2, despite the fact it is normalised (and, thus, doesn't include infinite loops)?

I'll turn my comments into an answer: In general, if you do not have any axioms or "stuck" terms, you cannot have a normal proof of $\mathrm{False}\simeq\forall X:*,X$ in a system like the CoC (or extensions of it). The (classical) proof I outlined here applies, crucially using inversion in several places.

I believe it's not hard to have a normal proof of $\mathrm{True}\rightarrow\mathrm{False}$ in an inconsistent system, however, by "blocking" some of the redexes with a variable. Applying this proof to any closed term of type $\mathrm{True}$ would then lead to non-termination.

This leads to a pretty natural question, which I will also outline here: is it possible to reason correctly about programs in an inconsistent language, as long as every "proof-like" term is normalized?

The answer to this seems to be mostly affirmative, though the meta-theory is quite finicky: it's easy to lose even type preservation if one is not careful!

The most comprehensive exploration of this idea to my knowledge is the PhD dissertation of Vilhelm Sjöberg: A Dependently Typed Language with Nontermination.


Solving an online problem without maximizing or minimizing an objective You have a budget $B$ and a satisfaction level $L$. An indivisible product is available for sell and you are interested in buying. The product is divided into $n$ parts. Part $i$ of the product has positive value $v_i$.

On day $i$, you get to know $v_i$ and you have to decide how much price $p_i\geq0$ you would pay for this part of the product.

After $j$ days, given the values $v_1, v_2, \ldots, v_j$ and the prices you paid $p_1, p_2, \ldots, p_j$ for each value, you know that you can reach a satisfaction level of $(1+v_1p_1)(1+v_2p_2)\cdots(1+v_jp_j)$.

Your objective is to buy the product after $n$ days while you reach the satisfaction level of $L$ and pay no more than $B$.

@orlp's intuition is correct.

lemma. No online algorithm solves the problem in the worst case.

Proof.  Consider the following instance:

$$f(p) = (1+p_1)(1+p_2)(1+p_3) \ge 8 \text{ with } B=3.$$

This instance has just one solution (one $p$ that satisfies it), namely $p=(1,1,1)$.  So, given $B=3$ and $L=8$ and just the first factor $1+p_1$, the algorithm has to choose $p_1 = 1$.

But then the adversary instead continues by defining the following instance:

$$g(p) = (1+p_1)(1+ 1.49 p_2)(1+0\cdot p_3) \ge 8 \text{ with } B=3.$$

This instance is feasible (e.g. for $p_1=p_2=3/2$ we have $g(p)\approx 8.1$). However, the algorithm committed to $p_1 = 1$, so the residual problem it is faced with is now $2(1+1.49 p_2) \ge 8$ with $p_2 \le 2$.  Since $2(1+1.49\cdot 2) < 2\cdot 4 = 8$, this residual problem is not feasible.

So the online algorithm cannot guarantee a solution, even if it knows in advance that it will face just one of the two instances above. $~~~\Box$


Prerequisite for learning GCT It seems that Geometric Complexity Theory requires much knowledge of pure maths such as algebraic geometry, representation theory.

While I am a CS student and do NOT have classes of very abstract and pure mathematics, I am interested in this program.

Is there a list of "minimum knowledge" for learning this theory ?

This list includes lecture notes of CS or math departments, surveys of any journal or conferences, and text books of pure math.

[EDIT: Added later] Thank you for your comments.

General theory of computing: I read Sipser's book with the title "Introduction to the Theory of Computation"

Complexity Theory :In particular, I am interested in concrete models for lower bounds of complexity. Thus I read the part of the "concrete lower bounds" in Arora-Barak's text book. I also have basic knowlede in the several chapers of the communication complexity book written by Nisan.

Basic Mathematics : I have learnt about proof-based linear algebra such as general definition of the vector space etc and precicely argument of calculas based on epsilon-delta argument.

Algebra: I have learned about definition and examples of group, ring, and field. I had a class for cs students, and have not learned about general thoery of this algebraic systems.

The short answer: the really minimum knowledge of math to understand the first half of the plan of GCT, once you've seen a little of groups, rings, and fields, is basically laid out in Chapter 3 of my thesis (shameless self plug). That chapter is, however, incomplete, in that I don't get to the representation theory part of things. The representation theory is crucial for the second half of the plan (which is why I'm working on extending that chapter to include it).

If you really want to get into GCT, Symmetry, Representations, and Invariants by Goodman and Wallach and Actions and Invariants of Algebraic Groups by W. Ferrers Santos are both relatively self-contained and have lots of good information that is pertinent to GCT. I'm not sure if they're the best sources to learn from, as I only learned about them after I had learned much of this material, but they are good in terms of the ratio of what they cover to what's relevant to GCT. Fulton and Harris is great for representation theory and lots of the examples/exercises in the book are relevant to GCT.

The longer answer: it really depends on what/how much you want to learn about GCT, as Vijay pointed out. The topics below are just what I think is the background needed, since that was the question. I'm not sure this is a complete list - I would recommend trying to read some of the papers on GCT, and when you get lost go look for background material. As you're learning the background material, every so often come back to the GCT papers and see if you can follow further.

(Depending on what you want to learn, I would actually disagree with Zeyu that you should try some graduate commutative algebra first, though at some point in learning GCT this will become necessary.)

If you want to understand, for example, Mulmuley's recent FOCS paper, you'll want to understand:

the hardness vs. randomness principle (see Impagliazzo--Kabanets, and also perhaps Bill Gasarch's list of papers on hardness v randomness)
basic algebraic geometry up to Hilbert's Nullstellensatz and Noether's Normalization Lemma. These can be found in any basic textbook on algebraic geometry and probably in most lecture notes on it.
some classical invariant theory (you don't really need geoemtric invariant theory, schemes and the Mumford-Fogarty-Kirwan book for this paper). Sturmfels' book Algorithms in Invariant Theory comes to mind.
For certain results in the paper, but by no means for the paper in general, you might want some of (and these references can also be found in the paper): representation theory of $SL_n$ as in Fulton and Harris,  results on matrix invariants [Artin, Procesi, Razymslov], ...

If you want to understand the general outline of the GCT approach but in some mathematical detail, I'd suggest:

The permanent versus determinant problem. #P-completeness of permanent and GapL-completeness of determinant. Agrawal has a good survey (only very slightly outdated)  on this, and the proofs of completeness can be found in Burgisser's book Completeness and Reductions in Algebraic Complexity Theory.
Groups and group actions (algebraic groups and algebraic group actions are helpful, but not necessary at this level). You should understand the Orbit-Stabilizer Theorem.
Affine algebraic geometry through Hilbert's Nullstellensatz. Basically you just need to understand the correspondence between affine algebraic varieties and their coordinate rings.
Basic representation theory of $GL_n$ as in Fulton and Harris. Aside from basic definitions, you need to know complete reducibility of these representations, and the fact that representations of $GL_n$ are classified by partitions, but you don't necessarily need to know the proof/constructions of the latter.

If you want to understand deeply what's going on (and I'm not sure I can claim to be there yet, but I think I know what I need to know to get there), you should probably also understand:

The structure of reductive algebraic groups and orbit closures in their representations. I like the book by W. Ferrers Santos for this, but also Linear Algebraic Groups by Borel, The Classical Groups by Weyl, and other classics.
The Luna-Vust machinery (Luna's Slice Theorem, Luna-Vust complexity)
Tannakian Duality (see the paper by Deligne--Milne; this will be tough reading without some background in category theory and affine algebraic groups). This essentially says that "(pro-)affine algebraic groups are determined by their representations." I don't think you need the whole paper, so much as how to recover a group from its category of representations (Cor. 3.4).
More representation theory, especially as applied to the coordinate rings of algebraic groups and their orbit closures. I really like the book by Goodman and Wallach for this, particularly because it's basically self-contained, and it has a lot of exactly what you need to understand GCT. (Also, many of the expository/side sections and exercises in Fulton and Harris are right on the mark for GCT, especially those about Littlewood-Richardson and Kronecker coefficients.)

If you want to actually work on the representation theory, you probably want to understand more algebraic combinatorics / combinatorial representation theory. I don't really know all the right references for this, but certainly understanding the Littlewood-Richardson rule is a must, and Fulton's book Young Tableaux is good for this.

The most recent papers on this side of things that I know of are Blasiak, Kumar, and Bowman, De Visscher, and Orellana.

Depending on what direction you want to go in, you may also want to look into quantum groups, though this isn't necessarily necessary (note: these are not a special case of groups, but rather a generalization in a certain direction).

On the more geometric side of things, you'll want to look into things like differential geometry for tangent and osculating spaces, curvature, dual varieties, and the like, which are underlying the best known lower bound on perm vs. det due to Mignon--Ressayre and followed by Landsberg--Manivel--Ressayre. (Mignon--Ressayre can be understood without any of these things, but you can view their paper loosely as studying the curvature of certain varieties; for a less loose view, see the use of dual varieties in Landsberg--Manivel--Ressayre.) (See also Cai, Chen, and Li, which extends Mignon--Ressayre to all odd characteristics.) See also Landsberg and Kadish.

If you're interested in the GCT approach to matrix multiplication, it's all about tensor rank, border rank, and secant varieties. I'd suggest looking at the papers by Burgisser--Ikenmeyer, Landsberg and Ottaviani, Landsberg, Landsberg's survey and book. Of course, it would also be good to know the classical stuff on matrix multiplication (both upper and lower bounds), but that's a whole separate can of worms.


Best sources on data stream algorithms I recently got interested in data stream algorithms to the point that I'd like to study the topic and then teach it to someone.

I'd be thus grateful for pointers to really good sources on the topic, t.i. papers presenting major ideas in a particularly articulate way, papers with clever proofs of clever theorems, just good overviews of the state of the art, whatever.

My two cents:

Lecture notes from the Dartmouth University, 2009. This is the best source I've found so far.
Distributing Frequency-Dependent Data Stream Computations, described in my answer to a different (also mine) question.
The book "Data streams: algorithms and applications" (I haven't read it yet)

Piotr Indyk has some lecture notes on streaming and related topics at stellar.mit.edu/S/course/6/fa07/6.895

A MADALGO summer school a few years ago also has some good notes. I would say all the papers listed in the bibliography there are good reads for anyone interested in the area.


Average message complexity for the election problem on graphs I am currently studying the election problem in distributed algorithms. There, I stumpled over one approach to implement a Chang-Roberts-like message extinction algorithm on graphs without requiring a specific topology.

The idea is simple: each initiator starts an echo-algorithm to learn about the leader (so, to find the process with the biggest unique identifier). An initiator adds his unique id to the wave to mark the wave and allow wave extinction: if two waves "hit" each other, the one with the bigger id wins. Now, to my question, which is inspired by this problem but a little bit more abstract.

Given an arbitrary topology and an algorithm like the one described above, is it possible to come up with a model to calculate the average message complexity? I apologize if I missed something obvious to answer this, but it seems to me that I am stuck with computing the best and worst case but cannot come up with an average case description without more knowledge on the actual topology. Is this conclusion true?

I don't know of any results in distributed computing that state bounds on
average message complexity that are independent of the network topology.

Let's assume you have an algorithm $A$ with average message complexity
$\Theta(f(n))$, for some function $f(n)$. While such a universal bound
sounds quite powerful, the problem (as I see it) is that this tells you
very little about $A$. If someone implemented $A$ for a specific class of
networks, the $\Theta(f(n))$ bound becomes meaningless, as it is the
average over all network topologies and unique id assignments, whereas
worst/best-case bounds would still apply.


Example where equivalence is easy but finding class representative is hard Suppose we have a class of objects (say graphs, strings), and an equivalence relation on these objects. For graphs this could be graph isomorphism. For strings, we could declare two strings equivalent if they are anagrams of each other.

I am interested in computing a representative for an equivalence class. That is, I want a function f() such that for any two objects x, y,
f(x) = f(y) iff x and y are equivalent.  (*)

For the example of anagrams, f(s) could sort letters in the string, ie. f('cabac') = 'aabcc'. For graph isomorphism, we could take f(G) to be a graph G' that is isomorphic to G and is the lexicoraphically first graph to have this property.

Now the question: Is there an example where the problem of determining whether two elements are equivalent is "easy" (poly time solvable), while finding a representative is difficult (i.e. there is no poly time algorithm to compute f() that satisfies (*)).

Ok, how about: numbers $x$ and $y$ are equivalent if either $x=y$, or both $x$ and $y$ have factorizations $x=pq$ and $y=pr$ where $p$, $q$, and $r$ are all prime and $p < \min(q,r)$. That is: products of two primes are equivalent when they share their smallest prime factor; other numbers are only equivalent to themselves.

It's easy to test whether two different numbers are equivalent: compute their gcd, test whether it's nontrivial, test whether the gcd is less than the cofactors, and test whether the gcd and its cofactors are all prime.

But it's not obvious how to compute a representative function $f$ in polynomial time, and if you add the requirement that $f(x)$ must be equivalent to $x$ then any representative function would allow us to factor most products of two primes (every one that isn't its own representative).


Permanents - Approximation and connection to integer factorization Given a non-negative integer matrix of size $n \times n$. If the permanent can be calculated in $n^{2}$ arithmetic operations but each operation is on word size $n^{k}$ bits for some constant $k$, does that imply calculating permanent is in  $P$?

We assume the maximum integer size $M$ is bound and only let $n$ grow for complexity estimates.

Actually an observation is that even if if one can calculate permanent of $n \times n$ matrix in $O(n^{k})$, then $n!$ is easy to calculate. But even then it wont bother RSA since for RSA $n ~ O(2^{256})$ and $n^k$ even for $k=1$ would be formidable. Is this correct?

Ryan Williams Answer:
"the permanent is #P-complete, due to Valiant's theorem in my answer below. It is possible in principle to reduce the factorization of a 256-bit number (which is computable in TFNP) to the Permanent on a matrix of dimension N×N where $N≤c⋅256^{c}+c$ for some hopefully small constant c. However the computation of a nice upper bound on c would probably take substantial effort. It's possible c is no more than 2 or 3."

" computing the permanent is much harder than integer factoring (to my knowledge), so I doubt someone would try to reduce factoring to permanent."

How about via approximations?

If an $\epsilon$-approximation to permanent can be found in polynomial time, then I don't think it will be not worthwhile to study such an algorithm. One can take $\epsilon$ small enough so that one has to try $O(\epsilon)$ different choices for permanents. In that case factoring should have an efficient probabilistic algorithm

Thanks for clarifying your earlier question.

In this case, we would indeed say the Permanent is in $P$. First, since addition and multiplication on $O(n^k)$ size numbers can be done in $n^k \log^{O(1)} n$ time, the $O(n^2)$ arithmetic operations would take less than $O(n^{k+3})$ time to execute. If $k$ is independent of $n$ and the numbers themselves, this is polynomial time.

Secondly, if you are computing the Permanent over the integers, then in the "hard case" you may not only assume that the integers are non-negative, but also you may assume that all integers are just $0$ and $1$! This is commonly known as Valiant's theorem. For information on how to prove this, see:

http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete#01-Matrix

This means that restricting to a non-negative matrix with bounded entries is not really a restriction of the Permanent problem. A polynomial time algorithm for this version of the problem would result in a polynomial time algorithm for the Permanent over any integer matrix.


Problems between NC and P: How many have been resolved from this list? In the paper "A Compendium of Problems Complete for P" by Greenlaw, Hoover and Ruzzo (PS) (PDF), there is a list of problems in P that are not known to be in NC and not known to be P-complete either. (This list subsumes all the open problems in the excellent survey by Karp and Ramachandran.) The open problems list starts on page 89.

How many problems from this list have been resolved (i.e., shown to be P-complete or in NC)? I'm guessing not too many have been solved in the last 19 years, so this (hopefully) shouldn't turn into a big-list.

That's the most recent list I could find. Pointers to a more up-to-date list would also be appreciated!

EDIT: András Salamon points out that there is a textbook by the same authors which has a slightly longer list. This is a PDF of the book. The open problems start on page 237.

BTW: The list of known CC-complete problems has grown since both versions of the book.   See this paper by Greenlaw and Kanlabutra.