Natural candidates for NP-E and E-NP It has been known since the early 70's that  ${\bf NP}$ and ${\bf E}=DTIME(2^{O(n)})$ are not equal (because ${\bf E}$ is not closed under polynomial-time many-one reductions, in contrast to ${\bf NP}$). As far as I know, however, it is still open whether one class is a subset of the other, or they are incomparable, meaning that ${\bf NP}-{\bf E}$ and ${\bf E}-{\bf NP}$ are both nonempty.

Question: Which are some (preferably natural) problems that are candidates for being in  ${\bf NP}-{\bf E}$ or ${\bf E}-{\bf NP}$, assuming the respective set is not empty? I am particularity interested in natural problems within ${\bf NP}$ that likely require exponential time with superlinear exponent, i.e., they are in ${\bf NP}-{\bf E}$.

TQBF (True Quantified Boolean Formulas) is in E and won't be in NP unless NP = PSPACE.

A language in NP-E is trickier. Such a language would also be in NP-NTIME(n) and we don't have great examples of those. You could use a succinct representation like

$ L = \{ C \ |\ $Circuit $C$ describes a graph $G$ on $|C|^5$ nodes where $G$ is 3-colorable$\}$.

$L$ is in NP, unlikely to be in $E$ but not that natural.


To what extent can an algorithm predict the time complexity an arbitrary input program? The Halting problem states that it is impossible to write a program that can determine if another program halts, for all possible input programs.

I can, however, certainly write a program that can compute the running time of a program of  like:

for(i=0; i<N; i++)
    { x = 1; }

and return a time complexity of $N$, without ever running it.

For all other input programs, it would return a flag indicating it was unable to determine the time-complexity.

My question is this:

What conditions must hold, such that we can algorithmically determine the time-complexity of a given program?

*If there is a canonical reference or review article to this I would appreciate a link to it in the comments.

In general you cannot determine complexity, even for halting programs: let $T$ be some arbitrary Turing machine and let $p_T$ be the program (that always returns 0):

input: n
run T for n steps
if T is in halting state, output: 0
otherwise, loop for n^2 steps and output: 0

It is clear that it is undecidable in general whether $p_T$ is linear-time or quadratic-time.

However, much work has been carried out on the effective computation of program complexity. I have particular fondness for Implicit Complexity Theory which aims at creating languages that, using special constructs or type disciplines, allows one to write only programs that inhabit a certain well-defined complexity class. By what I consider to be something of a miracle, these languages are often complete for that class!

One particularly nice example is described in this paper by J.-Y. Marion, which describes a tiny imperative language, with a type discipline inspired from information-flow and security analysis techniques, which allows a characterization of algorithms in P.


Computability of infinite-dimensional vector space So there is a talk about infinite-dimensional vector space being computable. But then I find it hard to understand. Apparently, dimension is infinite, so how would the operations of the space be computable?

Is it something like $\pi$ being computable, although it has infinite number of digits?

Short answer

The general answer is that computability is easy for locally compact spaces, doable for separable spaces, and hard for non-separable spaces.

The short anwer for a particular example, namely $\ell^2$ is: in order to get computability on $\ell^2$ working, represent an element $x$ of $\ell^2$ by a program which accepts $n$ and gives (the list of coefficients of) a finite rational linear combination of the standard basis vectors which is within $2^{-n}$ of $x$ in the $\ell^2$ norm.

Long answer

One general way of equipping a space $X$ with computability is to choose a datatype $\mathtt{T}$ in your favorite programming language (it can be Turing machines and tapes if you're into 1950's memorabilia, otherwise I would recommend a reasonable programming language such as Haskell), and a realizability relation $\vdash_X$ on $\mathtt{T} \times X$, where $\mathtt{d} \Vdash_X x$ means "datum $\mathtt{d}$ represents (implements, realizes) the point $x \in X$". For instance, if $X$ is the space of all finite graphs, then $\mathtt{T}$ could be the datatype of adjancency matrices. If $Y$ is another space with a computability structure, then a map $f: X \to Y$ is said to be computable or realized if there is a program $\mathtt{p}$ such that $\mathtt{d} \Vdash_X x$ implies $\mathtt{p}(\mathtt{d}) \Vdash_Y f(x)$, i.e., $\mathtt{p}$ does to the representing data what $f$ does to points.

The most important principle to always keep in mind is that computability is about computability of structure, not computability of a bare set.

For instance, it makes no sense to ask "Is $\pi$ computable?" or even "Which elements of $\mathbb{R}$ are computable?" You must first make up your mind about what structure of $\mathbb{R}$ you want to consider, and then see if you can make it computable.
The correct computability structure on $\mathbb{R}$ turns out to be:

arithmetical operations must be computable (including the constants $0$ and $1$)
the order relation $<$ must be semidecidable,
there is a program which, given $d \vdash_{\mathbb{R}} x$ and $k \in \mathbb{N}$, computes a rational approximation of $x$ with precision $2^{-k}$,
the limit operator $\lim$ which assigns to every rapid Cauchy sequence of reals its limit, is computable. (A sequence $(x_n)$ is rapid if $|x_n - x_m| \leq 2^{-\min(n,m)}$ for all $m, n$. The point is that we need to have a known rate of convergence, any other rate would do just as well.)

If you leave out anything, or try to add more, you will get into trouble by either having many non-equivalent computability structures on $\mathbb{R}$, or none. A datatype for representing reals for which all of the above can be implemented is
$$\mathtt{nat} \to \mathtt{rational}$$
where a function $\mathtt{p}$ represents a real $x$ when, for every $n \in \mathbb{N}$, $\mathtt{p}(n)$ returns (a representatve of) a rational number $q$ such that $|x - q| \leq 2^{-n}$. (Such a function $\mathtt{p}$ may be represented by a Turing machine, or a piece of source code, or an expression in $\lambda$-calculus.)

Let us now look at an infinite dimensional space $\ell^2$. It is a real Hilbert space with a countable orthonormal basis, so the relevant structure is:

vector space structure: $0$, $+$, $-$ and scalar multiplication,
the scalar product: $\langle {-}, {-} \rangle$
completeness: given a rapid Cauchy sequence $(x_n)$ in $\ell^2$, we can compute $\lim_n x_n$
basis: for every $x \in \ell^2$ we can compute a sequence $(\lambda_n)$ of real numbers such that $x = \sum_n \lambda_n \cdot e_n$ where $$e_n = (\underbrace{0, \ldots, 0}_n, 1, 0, 0, \ldots)$$ is the canonical orthonormal basis.

Now the question is what datatype we should choose to represent $\ell^2$ so that all of the structure is computable. A simple one that works is
$$\mathtt{nat} \to \mathtt{list}(\mathtt{rational}),$$
i.e, we can represent an element $x \in \ell^2$ with a function $\mathtt{p}$ that accepts a natural number and returns a finite list of rational numbers. The realizability relation is
$$\mathtt{p} \Vdash_{\ell^2} x$$
is defined as follows: for every $n \in \mathbb{N}$, $p(n)$ is a list of rationals $[q_0, \ldots, q_m]$ such that $\|x - \sum_{i=0}^m q_i e_i\|_2 \leq 2^{-n}$. I leave it as an exercise to verify that with this representation we can indeed implement all of the structure of $\ell^2$, as stated above.

Further reading (sorry for blowing my own horn):
A. Bauer, J. Blanck:
Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions", J. UCS 16(18): 2496-2522 (2010)


Using Kolmogorov complexity to establish proof complexity lower bounds? The motivation for this question is the fact that most n-bit strings are incompressible. Intuitively, we can propose by analogy that most proofs for Tautologies are incompressible to polynomial size. Basically, my intuition is that some proofs are inherently random and can't be compressed.

  Is there a good reference on research effort related to using Kolmogorov complexity results to establish super-polynomial lower bounds on the proof size of Tautologies?

In this Ph.D. dissertation
On the Complexity of Propositional Proof Systems

  the Incompressibility method from Kolmogorov Complexity is used to obtain Urquhart's $\Omega(n/\log n)$ lower bound for a class of Tautologies. I wonder if there are stronger results using the Incompressibility method or other results from Kolmogorov complexity?

Arvind, Köbler, Mundhenk, and Torán introduced the notion of time-bounded nondeterministic instance complexity. Based on a quick reading, It seems they use Kolmogorov complexity measure that depends on the size of shortest nondeterministic TM. They were able to prove the existence of hard to prove Tautologies under a notion of hardness based on nondeterministic instance complexity.

Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán,
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies,


Any SAT/SMT formulations of the VRP/VRPTW (TSP, Job-Shop-Scheduling)? i wonder if they are any approaches formulating a Vehicle-Routing-Problem with Time-Windows (VRPTW) (as a decision problem) as a SAT/SMT instance? (alternative: TSP)

For example:
"Is there a valid solution visiting all customers within their time-windows with n=10 vehicles?"

This decision problem could be useful for a first step minimizing the number of vehicles used.

I don't have any experience with SMT, but i expect it to be necessary if we want to handle coordinates/times as real numbers.

Usually all the TSP/VRP formulations are done in the mixed-integer-programming domain, but i wonder if a sat/smt formulation could be competitive (in terms of solving time in practice) for the decision problem above.

So what do you think:

do you know any references?
do you think a sat/smt approach could be competitive?
anything else you want to mention?

Thanks for all your input.

Sascha

Edit: As i mentioned the TSP as a more common problem in TCS which is related to the VRPTW, i should also mention the Job Shop Scheduling problem, which is the other "partial problem" in the VRPTW. Maybe the researchers in this field tried something with SAT/SMT.

The big problem I see with a SAT formulation for VRPTW is that you have to discretize time to enforce the time window constraints (unless you encode arithmetic as boolean circuits which I've never seen done but might be worth trying). This means the number of variables becomes much larger as the time window increases affecting performance.

An SMT (Sat Modulo Theory) formulation however wouldn't have a similar issue, I think since you have a propagator for the time window constraints which would return redundant constraints to the SAT solver to incorporate when you branch.

While I don't know of any work using SAT formulations for VRPTW, I know that Peter Stuckey, in his paper on Lazy Clause generation used an approach almost exactly like SMT to solve Job Shop Scheduling and seemed to get good results for that.


Connection between algebraic logic and computational complexity of logics? I'm learning a bit about algebraic logic and I was wondering how knowing the algebraic semantics of a given logic might help the study of the logic itself from a computational point of view.

In particular, is there any example of a complexity (or decidability) result for the satisfiability problem for some logics that was obtained by reasoning about its algebraic semantics?

For example, the semantics of propositional logic can be given in terms of boolean algebras. Is there any connection between them and the fact that SAT is decidable and $NP$-complete?

The example you gave extends as follows:

SAT for arbitrary lattices (meaning, is a given formula satisfiable in some lattice) is polynomial-time decidable
SAT for modular lattices is Turing undecidable:
Freese, Ralph, Free modular lattices, Trans. Am. Math. Soc. 261, 81-91 (1980). ZBL0437.06006.
SAT for Boolean algebras is NP-complete

So while modular lattices are in between Boolean algebras and arbitrary lattices, they are the most complicated.


What's the bias of random polynomials with low degree over GF(2)? I have a question concerning low-degree polynomials and probability:
What is the (assyptotic behavior of the) probability that a
random* polynomial, $p$, over GF(2), with degree $\le d$ and n variables
has $bias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon$.

*When I'm writing random polynomial with degree $\le d$ and n variables, you can think of each monomials of total degree $\le d$ picked with probability 1/2.

The only relevant thing I know is a variant of Schwartz-Zippel that states that if the polynomial is nonconstant then its bias is at most $1-2^{1-d}$. Hence, for $\epsilon=1-2^{1-d}$ the probaiblity is exactly $1/{2^{{n \choose 1}+\ldots+{n \choose d}}}$ where this is the probability that $p$ is a constant. Unfortunately, this $\epsilon$ is quite big.

Your question is equivalent to tail bounds on the weight distribution of Reed-Muller codes. Understanding weight distribution of Reed-Muller codes is an old and challenging question in coding theory, and several interesting results are known about it (the weight distribution is completely understood only for $d=1$ and $d=2$). As a great starting point, see "Weight Distribution and List-Decoding Size of Reed-Muller Codes" by Tali Kaufman, Shachar Lovett, Ely Porat, and the references therein.


Reference Request: Asymptotic hardness of $hk$ coloring $k$-colorable graphs I heard of a result in approximate graph coloring, but cannot find the source. The result is:

For every constant $h$ there exists a sufficiently large $k$ such that coloring a $k$-colorable graph with $hk$ colors is NP-hard.

Could someone please point me to the relevant paper?

Here are the references:

S. Khanna, N. Linial, and S. Safra, On the hardness of approximating the chromatic number,
Combinatoria, 20 (2000), pp. 393–415.
C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, J.
ACM, 41 (1994), pp. 960–981.


Purpose and determining when to use hidden layers Following up on this question...

I am attempting to learn how to use and create neural networks for my research, and one point is somewhat escaping me.  I realize that hidden layers are a somewhat necessary portion of this, however I am stuck on two points which my references aren't explaining to my satisfaction:

What is the exact purpose of the hidden layer?
How does one determine how many hidden layers to use?

From what I gather, it is to "model" real world functionality, but if possible I'd like a bit more of an explanation.

A hidden layer is used to increase the expressiveness of the network.  It allows the network to represent more complex models than possible without the hidden layer.

Choosing the number of hidden layers, or more generally choosing your network architecture including the number of hidden units in hidden layers as well, are decisions that should be based on your training and cross-validation data.  You should train the network with a set amount of nodes (to start, try one hidden layer, with one unit per input unit) and test the model.

See this link for more help:  http://www.faqs.org/faqs/ai-faq/neural-nets/part3/section-10.html


Does there exist an extension of regular expressions that captures the context free languages? In many papers involving context-free grammars (CFGs), the examples of such grammars presented there often admit easy characterizations of the language they generate. For example:

  $S \to a a S b$
  $S \to $

generates $\{ a^{2i} b^i | i \geq 0\}$,

  $S \to a S b$
  $S \to a a S b$
  $S \to $

generates $\{ a^i b^j \mid i \geq j \geq 0 \}$, and

  $S \to a S a$
  $S \to b S b$
  $S \to $

generates $\{ w w^R \mid w \in (a|b)^* \}$, or equivalently $\{ ((a|b)^*)_1 ((a|b)^*)_2 \mid p_1 = p_2^R \}$ (where $p_1$ refers to the part captured by $(...)_1$).

The above examples can all be generated by adding indices ($a^i$), simple constraints on these indices ($i > j$) and pattern matching to regular expressions. This makes me wonder whether all context-free languages can be generated by some extension of the regular expressions.

  Is there an extension of regular expressions that can generate all of or some significant subset of the context free languages?

Yes, there is. Define a context-free expression to be a term generated
by the following grammar:

$$
\begin{array}{lcll}
g & ::= & \epsilon & \mbox{Empty string}\\
  &  |  & c        & \mbox{Character $c$ in alphabet $\Sigma$} \\
  &  |  & g \cdot g & \mbox{Concatenation} \\
  &  |  & \bot      & \mbox{Failing pattern} \\
  &  |  & g \vee g  & \mbox{Disjunction}\\
  &  |  & \mu \alpha.\; g & \mbox{Recursive grammar expression} \\
  &  |  & \alpha    & \mbox{Variable expression}
\end{array}
$$

This is all of the constructors for regular languages except Kleene
star, which is replaced by a general fixed-point operator $\mu
\alpha.\;g$, and a variable reference mechanism. (The Kleene star is
not needed, since it can be defined as $g\ast \triangleq \mu
\alpha.\;\epsilon \vee g\cdot\alpha$.)

The interpretation of a context-free expression requires accounting
for the interpretation of free variables. So define an environment
$\rho$ to be a map from variables to languages (i.e., subsets of
$\Sigma^*$), and let $[\rho|\alpha:L]$ be the function that behaves
like $\rho$ on all inputs except $\alpha$, and which returns the
language $L$ for $\alpha$.

Now, define the interpretation of a context-free expression as follows:

$$
\newcommand{\interp}[2]{[\![{#1}]\!]\;{#2}}
\newcommand{\setof}[1]{\left\{#1\right\}}
\newcommand{\comprehend}[2]{\setof{{#1}\;\mid|\;{#2}}}
\begin{array}{lcl}
\interp{\epsilon}{\rho} & = & \setof{\epsilon} \\
\interp{c}{\rho}        & = & \setof{c} \\
\interp{g_1\cdot g_2}{\rho} & = & \comprehend{w_1 \cdot w_2}{w_1 \in \interp{g_1}{\rho} \land w_2 \in \interp{g_2}{\rho}} \\
\interp{\bot}{\rho} & = & \emptyset \\
\interp{g_1 \vee g_2}{\rho} & = & \interp{g_1}{\rho} \cup \interp{g_2}{\rho} \\
\interp{\alpha}{\rho} & = & \rho(\alpha) \\
\interp{\mu \alpha.\; g}{\rho} & = & \bigcup_{n \in \mathbb{N}} L_n \\
\mbox{where} & & \\
L_0 & = & \emptyset \\
L_{n+1} & = & L_n \cup \interp{g}{[\rho|\alpha:L_n]}
\end{array}
$$

Using the Knaster-Tarski theorem, it's easy to see that the
interpretation of $\mu \alpha.g$ is the least fixed of the expression.

It's straightforward (albeit not entirely trivial) to show that you
can give a context-free expression deriving the same language as any
context-free grammar, and vice-versa. The non-triviality arises from
the fact that context-free expressions have nested fixed points, and
context-free grammars give you a single fixed point over a tuple. This
requires the use of Bekic's lemma, which says precisely that a nested
fixed points can be converted to a single fixed point over a product (and
vice-versa). But that's the only subtlety.

EDIT: No, I don't know a standard reference for this: I worked it out
for my own interest. However, it's an obvious enough construction that
I'm confident it's been invented before. Some casual Googling reveals
Joost Winter, Marcello Bonsangue and Jan Rutten's recent paper
Context-Free Languages, Coalgebraically, where they give a variant
of this definition (requiring all fixed points to be guarded) which
they also call context-free expressions.


Monotone supermodular function minimization under partition matroid constraints Is there a known approximation algorithm for the problem of minimizing
a monotone (non increasing) supermodular function under partition matroid constraints ?

Consider a graph $G=(V,E)$. Define the set function $f$ over $V$ where $f(A)$ is the number of edges with both end points in $A$. Then $f$ is supermodular and monotone. Suppose $G$ has an independent set of size $k$. Then the minimum of $f(S)$ under the constraints $|S| = k$ (the uniform matroid constraint) will be $0$. If $G$ does not have an independent set of size $k$ then the min will be at least $1$. Hence the problem is inapproximable.


How to efficiently find a loop between two nodes in a directed graph? Given two nodes in a directed graph, how can I find a loop (if exists) that pass these two nodes? The loop cannot pass a node more than once. And if there isn't such a loop, how to efficiently determines it?

This problem has been shown to be NP-complete in the following paper:

  S. Fortune, J. Hopcroft, J. Wyllie:
  "The directed subgraph homeomorphism problem"
  Theoretical Computer Science 10 (1980), pp. 111-121


Is there a geometrical picture for adiabatic quantum computation? In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily coolable initial (ground) state with Hamiltonian $H_i$ and "anneal" (adiabatically perturb) towards $H_p$, i.e.

$$
H(s) = s H_i + (1-s) H_p
$$

where $s \in [0,1]$. Details about AQC: http://arxiv.org/abs/quant-ph/0001106v1

The interesting thing about this problem is to try to understand the gap between the ground state eigenvalue and the first excited state, as this determines the problem complexity. One interesting thing to do would be to try and say something about the behavior of certain types of Hamiltonians. One can analyze the energy spectrum of small qubit cases by simulation to understand the problem complexity, but this becomes infeasible very quickly.

What I'd like to know is if there is a geometrical or topological way of looking at how certain Hamiltonians behave. Someone mentioned that the above form could be looked at as a homotopy (if the scalar functions were generalized to operators), but I'm not well-versed in higher level mathematics so I'm not sure what this implies or what I could do with it.

It might help to mention that the Hamiltonians are usually Ising spin-glass Hamiltonians (at least, that is what $H_p$ is). I'm not well-read on advanced statistical mechanics literature either, so this may be another avenue.

I wondered if anyone could provide some explanation on this, or at least provide some interesting references, keywords, etc.

a very challenging/advanced/provocative question; following, a brief/sketchy/tentative answer [maybe/hopefully better than none] considering geometry in QM computing in general & a few refs/leads. geometry is used in a variety of ways in QM in general, and it appears to be somewhat of an open question and challenging work-in-progress how to determine a coherent/natural "geometric picture" for QM, and there apparently are multiple ways to do it, and currently no generally-agreed, unified or standard approach. also, some directions can be highly abstract reflecting the direction of mathematical research developed largely independently of physics.

the 2-qubit state has been more extensively studied and there is more chance of creating a picture there 1st and maybe using it as a somewhat "toy" area that can be expanded later. (note that adiabatic QM computing is still based on qubits.) also there is a relatively new study of "quantum dischord" which is seen as promising by some (but also controversial) & might be part of the answer as in the following ref.

the Bloch sphere is a clear geometric picture for a single qubit and has some generalization for pure states.
Geometric picture of quantum discord for two-qubit quantum states Shi, Jiang, Sun, Du
Geometry of Discrete Quantum Computing Hanson, Ortiz, Sabry, Tai
Quantum computing: The power of discord Merali/Nature


What is a minimum vertex separator as in this definition? In a research paper the following definition appears that I'm not able to understand completely.

Let $G=(V,E)$ be an undirected unweighted graph with vertex set $V$ and edge set $E$, no self-loops, no parallel-edges.
Let $\{ u, v\} \in \binom{V}{2}$ be a vertex pair over the set of all vertices pairs. Let $\textrm{Sep}(u, v)$ be a minimum $u-v$ vertex separator in $G$ if $\{u, v\} \notin E$ or in $G' = (V,E \setminus \{u,v\}) $ otherwise.

It is difficult for me to figure out what this definition imply.

In particular can $\textrm{Sep}(u,v)$ be an empty set?

It seems that $Sep(u, v)$ is a vertex separator extended to graphs where $u$ and $v$ are adjacent, by ignoring their common edge.

I assume the correct definition is

  ... vertex separator in $G$ if $\{u,v\} \notin E$ or in $G′=(V,E \setminus \{\{u,v\}\})$ otherwise.

As given, the definition makes no sense. There is no point in removing $\{u, v\}$ from $E$ if $\{u, v\} \notin E$ and, of course, $\{u, v\} \not\subset E$.

In this case, $Sep(u, v)$ can be $\emptyset$ if $\{u, v\}$ is the only edge connecting two components, or if the graph had two components to begin with.


Good description of Calculus of Inductive Construction I want to learn more about Calculus of Inductive Constructions. What can you recommend to read on this topic? All the materials which I found are either in French or too basic (the Coq'Art book).

The thing I am interested the most are not definitions but the proofs of important properties.

You can try the Coq user manual, in particular this section is pretty nice (the server seems to be down at the moment though).

For meta-theory you can try some recent work of Benjamin Werner et al., see Proof-irrelevant model of CC with predicative induction and judgmental equality
 and On the strength of proof-irrelevant type theories for the most salient work.


Robustness of splitting a junta We say that a Boolean function $f: \{0,1\}^n \to \{0,1\}$ is a $k$-junta if $f$ has at most $k$ influencing variables.

Let $f: \{0,1\}^n \to \{0,1\}$ be a $2k$-junta. Denote the variables of $f$ by $x_1, x_2, \ldots, x_n$. Fix
$$S_1 = \left\{ x_1, x_2, \ldots, x_{\frac{n}{2}} \right\},\quad S_2 = \left\{ x_{\frac{n}{2} + 1}, x_{\frac{n}{2} + 2}, \ldots, x_n \right\}.$$
Clearly, there exists $S \in \{S_1, S_2\}$ such that $S$ contains at least $k$ of the influencing variables of $f$.

Now let $\epsilon > 0$, and assume that $f: \{0,1\}^n \to \{0,1\}$ is $\epsilon$-far from every $2k$-junta (i.e., one has to change a fraction of at least $\epsilon$ of the values of $f$ in order to make it a $2k$-junta). Can we make a "robust" version of the statement above? That is, is there a universal constant $c$, and a set $S \in \{S_1, S_2\}$ such that $f$ is $\frac{\epsilon}{c}$-far from every function that contains at most $k$ influencing variables in $S$?

Note: In the original formulation of the question, $c$ was fixed as $2$. Neal's example shows that such value of $c$ does not suffice. However, since in property testing we are usually not too concerned with constants, I relaxed the condition a bit.

The answer is “yes”. The proof is by contradiction.

For notational convenience, let us denote the first $n/2$ variables by $x$ and the second $n/2$ variables by $y$. Suppose that $f(x,y)$ is $\delta$-close to a function $f_1(x,y)$ which depends only on $k$ coordinates of $x$. Denote its influential coordinates by $T_1$. Similarly, suppose that $f(x,y)$ is $\delta$-close to a function $f_2(x,y)$ which depends only on $k$ coordinates of $y$. Denote its influential coordinates by $T_2$. We need to prove that $f$ is $4\delta$- close to a $2k$-junta $\tilde f(x,y)$.

Let us say that $(x_1,y_1) \sim (x_2,y_2)$ if $x_1$ and $x_2$ agree on all coordinates in $T_1$ and $y_1$ and $y_2$ agree on all coordinates in $T_2$. We choose uniformly at random a representative from each equivalence class. Let $(\bar x, \bar y)$ be the representative for the class of $(x,y)$. Define $\tilde f$ as follows:
$$\tilde f(x,y) = f(\bar x, \bar y).$$

It is obvious that $\tilde f$ is a $2k$-junta (it depends only on variables in $T_1 \cup T_2)$. We shall prove that it is at distance $4\delta$ from $f$ in expectation.

We want to prove that
$$\Pr_{\tilde f}(\Pr_{x,y}(\tilde f(x,y) \neq f(x,y))) = \Pr(f(\bar x, \bar y) \neq f(x,y)) \leq 4\delta,$$
where $x$ and $y$ are chosen uniformly at random.
Consider a random vector $\tilde x$ obtained from $x$ by keeping all bits in $T_1$ and randomly flipping all bits not in $T_1$, and a vector $\tilde y$ defined similarly. Note that
$$\Pr(\tilde f(x,y) \neq f(x,y)) = \Pr(f(\bar x, \bar y) \neq f(x,y))= \Pr(f(\tilde x, \tilde y) \neq f(x,y)).$$

We have,
$$\Pr(f(x,y) \neq f(\tilde x, y)) \leq  \Pr(f(x,y) \neq f_1(x, y)) + \Pr(f_1(x,y) \neq f_1(\tilde x, y)) + \Pr(f_1(\tilde x,y) \neq f(\tilde x, y)) \leq \delta + 0 + \delta = 2\delta.$$

Similarly, $\Pr(f(\tilde x,y) \neq f(\tilde x, \tilde y)) \leq 2\delta$. We have
$$\Pr(f(\bar x, \bar y) \neq f(x,y))  \leq 4\delta.$$
QED

It easy to “derandomize” this proof. For every $(x,y)$, let $\tilde f(x,y) = 1$ if $f(x,y) = 1$ for most $(x',y')$ in the equivalence class of $(x,y)$, and $\tilde f(x,y) = 0$, otherwise.


How is the MA version of SETH proven to be false? According to this paper, which discusses a nondeterministic extension of the Strong Exponential Time Hypothesis (SETH), "[…] Williams has recently shown related hypotheses about Merlin-Arthur complexity of k-TAUT are false". However, that paper only cites a personal communication.

How is the MA version of SETH proven to be false?

I suspect that it involves algebrizing the formula, but do not have any further idea.

You can find a preprint by following this link http://eccc.hpi-web.de/report/2016/002/

EDIT (1/24) By request, here is a quick summary, taken from the paper itself, but glossing over many things. Suppose Merlin can prove to Arthur that for a $k$-variable arithmetic circuit $C$, its value on all points in $\{0,1\}^k$ is a certain table of $2^k$ field elements, in time about $(s + 2^k) \cdot d$, where $s$ is the size of $C$ and $d$ is the degree of the polynomial computed by $C$. (We call this a "short non-interactive proof of batch evaluation" --- evaluating $C$ on many assignments.)

Then Merlin can solve $\#$SAT for Arthur as follows. Given a CNF $F$ on $n$ variables and $m$ clauses, Merlin and Arthur first construct an arithmetic circuit $C$ on $n/2$ variables of degree at most $mn$, size about $mn \cdot 2^{n/2}$, which takes a sum over all assignments to the first $n/2$ variables of the CNF $F$ (adding a $1$ to the sum when $F$ is true, and $0$ when it's false). Using the batch evaluation protocol, Merlin can then prove that $C$ takes on $2^{n/2}$ particular values on all its $2^{n/2}$ Boolean assignments, in about $2^{n/2} poly(n,m)$ time. Summing up all those values, we get the count of the SAT assignments to $F$.

Now we say at a high level how to do the batch evaluation protocol. We want the proof to be a succinct representation of the circuit $C$ that is both easy to evaluate on all of the $2^k$ given inputs, and also easy to verify with randomness. We set the proof to be a univariate polynomial $Q(x)$ defined over a sufficiently large extension field of the base field $K$ (of characteristic at least $2^n$ for our application), where $Q(x)$ has degree about $2^k \cdot d$, and $Q$ ``sketches'' the evaluation of the degree-$d$ arithmetic circuit $C$ over all $2^k$ assignments. The polynomial $Q$ satisfies two conflicting conditions:

The verifier can use the sketch $Q$ to efficiently produce the truth table of $C$. In particular, for some explicitly known $\alpha_i$ from the extension of $K$, we want $(Q(\alpha_0), Q(\alpha_1),\ldots,Q(\alpha_K)) = (C(a_1),\ldots,C(a_{2^K}))$, where $a_i$ is the $i$th Boolean assignment to the $k$ variables of $C$ (under some ordering on assignments).
The verifier can check that $Q$ is a faithful representation of $C$'s behavior on all $2^k$ Boolean assignments, in about $2^k + s$ time, with randomness. This basically becomes a univariate polynomial identity test.

The construction of $Q$ uses an interpolation trick originating from the holographic proofs, where multivariate expressions can be efficiently ``expressed'' as univariate ones. Both of the two items utilize fast algorithms for manipulating univariate polynomials.


How fast can we solve a totally unimodular integer linear program? (This is a follow-up to this question  and its answer.)
I have the following totally unimodular (TU) integer linear program (ILP). Here  $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ are all positive integers given as part of the input. A specified subset of the variables $x_{ij}$ is set to zero, and the rest can take positive integral values:

Minimize
$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$
Subject to:
$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$
$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$

The coefficient matrix of the standard form is a $(2\ell+m)\times \ell m$ matrix with entries from ${-1,0,1}$.
My question is:

What are the best upper bounds known for the running time of polynomial-time algorithms that solve such an ILP? Could you point me to some references on this?

I did some searching, but at most places they stop with saying that a TU ILP can be solved in polynomial time using polynomial-time algorithms for LP. One thing that looked promising is a 1986 paper by Tardos [1] where she proves that such problems can be solved in time polynomial in the size of the coefficient matrix. As far as I could figure out from the paper, however, the running time of that algorithm depends in turn on the running time of a polynomial-time algorithm for solving LP.

Do we know of algorithms that solve this special case (of TU ILP) significantly faster than the general algorithms that solve the LP problem?

If not,

Which algorithm for LP would solve such an ILP the fastest (in an asymptotic sense)?

[1] A strongly polynomial algorithm to solve combinatorial linear programs, Eva Tardos, Operations Research 34(2), 1986

I believe On a class of totally unimodular matrices, by Yannakakis, gives an answer to your question for a special case of TU ILP (whenever there are no odd cycles in a bipartite graph obtained by seeing the coefficient matrix as an adjacency matrix).

In that paper there is a reference to Polynomial algorithms for a class of linear programs, which seems to handle all totally unimodular matrices, but I am not sure about how much more efficient it is compared to generic algorithms for LPs.


Conservative Approximation of Kleene-Mycroft Iteration for Polymorphic Recursion? To perform type inference in the presence of polymorphic recursion, one can use a Kleene-Mycroft iteration to compute the principal type of an expression. To type $\mathsf{fix}\ f\ldotp e$, we define $F(\sigma)$ as the principal type of $e$ under the assumption that $f : \sigma$. We can then define $\sigma_0 = \forall a \ldotp a$ and $\sigma_{i+1} = F(\sigma_i)$, until we reach a fixed-point $\sigma_k$. This $\sigma_k$ is then the principal type of $\mathsf{fix}\ f\ldotp e$.

There are two key issues with this:

Inference with polymorphic recursion is undecidable, so this iteration may not always reach a fixed-point.
The approximation at each stage of the iteration is not sound: if we quit after $j<k$ iterations, not only will $\sigma_j$ not be the principal type of $\mathsf{fix}\ f\ldotp e$, but it will not be a type of $\mathsf{fix}\ f\ldotp e$ at all, since we made too strong of an assumption about the type of $f$ when checking $e$.

I'm wondering if there's a standard way to soundly approximate polymorphic recursion: that is, to iterate some number of times, and afterwards, obtain a type that is possibly less general than the principal type, but that is nevertheless a valid typing of $\mathsf{fix}\ f\ldotp e$.

For example, one can imagine the Hindley-Milner approximation, where we type $e$ under the assumption that $f$ has a monomorphic type, as being the 0-ary approximation. We may fail to find a typing for an expression that requires polymorphic recursion, but if we find a type, we know that it is a valid typing of the expression.

Does such an approximation exist?

You should have a look at the following paper -- and the previous work by Gori and Levi:

On Polymorphic Recursion, Type Systems, and Abstract Interpretation
Marco Comini, Ferruccio Damiani, Samuel Vrech, 2008

  The problem of typing polymorphic recursion (i.e., recursive function
  definitions rec {x = e} where different occurrences of x in e are used
  with different types) has been investigated both by people working on
  type systems and by people working on abstract interpretation.
  Recently, Gori and Levi have developed an abstract interpreter that is
  able to type all the ML typable recursive definitions and interesting
  examples of polymorphic recursion. The problem of finding a type
  system corresponding to their abstract interpreter was open.

  In this paper we present a type system corresponding to the Gori-Levi
  abstract interpreter. Interestingly enough, the type system is derived
  from the system of simple types (which is the let-free fragment of the
  ML type system) by adapting a general technique for extending
  a decidable type system enjoying principal typings by adding
  a decidable rule for typing recursive definitions. The key role played
  in our investigation by the notion of principal typing suggests that
  this notion might be useful in other investigations about the
  relations between type systems and type inference algorithms
  synthesized by abstract interpretation.


Discerning the best model for a problem This is a vague question. I will do my best, I think it has definite answers. I am hoping for answers of the form "Read book x, learn this specific topic, read this paper/s".

What is bothering me is that every AI system I have read about seems to have an internal model which is set up to operate in a specific way. The task of the learning algorithm is to then optimise the parameters of this model to solve the problem.

I am thinking that this is akin to setting up a custom description language which preserves or translates some structure of the thing to be modelled in such a way that it becomes amenable to solution through some understood algorithmic technique; iterative gradient descent, analytic, whatever.

The Question: Is there any framework in which the optimum model/description language can be discovered? For instance in a GA the mapping from the genome to the phenotype is critical to the effective operation of the algorithm. This mapping is manually defined and, I would posit, is the most critical component of the GA. Specifically how would one search through the space of mappings? Or going meta how would one search through the space of algorithms for finding that best mapping? It feels like you could disappear up that ladder forever. In order to solve the problem you must first solve the problem.

Neural networks seem to represent an effective model for solving real world problems, why? How would one generate another model for a different set of problems? Cellular Automata seem good for modelling traffic flows or disease transmission, why? How would I automatically generate alternative systems which also model the set of problems effectively? etc.

Is this something that is thought about and discussed? Where would I find it? This is my first question, please be gentle! :)

Unfortunately, there are many possible levels of description for a problem; choosing one among them is strictly dependent on your aims and on the tools available to you. In general, there are three possible approaches: analytical, numerical and observational. Each one is characterized by pro and cons. When you need to build a model, there are many possible decisions that must be made. For instance, you may decide among:

specific - general
model estimation - first-principles models
numerical - analytical
stochastic -deterministic
microscopic - macroscopic
discrete - continuous
qualitative - quantitative

and so on. You must understand that, in general, there are no rigorous rules of thumb when making these choices. As pointed out by @Suresh, this a matter of experience, requires a careful understanding of the domain, and some inspired guessing as well. The good news is that once you have made your choices, then there are rigorous ways to proceed. Probably, the best model overall for a given problem is the one given by the Minimum Description Length Principle (essentially the Occam's razor): the best model is the smallest one. But determining it is beyond hope. So, the best model is almost always, the one that works best for you, given your explicit and even implicit assumptions.

That said, analytical and numerical approaches allows you to explore the behavior of a model, but the assumption here is that the underlying model is known. It's up to you to derive this model. Observational approaches allows you to derive a model from the experimentally observed data.

Analytical models may lead to a closed-form solution; they are of great importance, given their power: if and when an analytical model may be successfully applied, then you will be able to deduce almost everything there is to know about a system. Their major drawback is limited applicability, since much of the world is simply too complicated to be described this way. Examples include ODE, PDE, difference equations, variational calculus and stochastic processes.

Numerical models are required when the equations in an analytical model are too complex to be solved exactly in closed-form. This usually happens as soon as we move too far from linearity to nonlinearity. It's important to remember that numerical and analytical solutions are complementary approaches rather than exclusive alternatives. Examples include Runge-Kutta methods, finite element methods, cellular automata and lattice gases.

Observational models can come from introspection or observation (or both).In some cases you may want to infer a model from experimentally measured data.This model may then be used to characterize and classify the data at hand, or to generalize from the measurements to predict the outcome of new observations etc. Examples include function fitting, SVD, Fourier and Wavelets transforms, neural networks, genetic algorithms, Expectation-Maximization algorithms, Wiener and Kalman filters, HMM, and time series.

A very good introductory book you may want to read is The nature of mathematical modeling. Of course, given the huge amount of topics covered, do not expect a detailed treatment.


Implementation of Wilf-Zeilberger and related methods The book A=B by Petkovsek, Wilf and Zeilberger describes algorithms to compute different sums of binomials. AFAIK, these algorithms are still being improved by different authors.

Do you know where we can find the most up-to-date implementations of these algorithms? And do you know if there exist implementations in some free softwares such as Sage?

It is implemented in Maxima (http://maxima.sourceforge.net/docs/manual/de/maxima_77.html#SEC400), to which Sage has interface. A few dozens of examples (ranging from very easy to very difficult) I tested today work in the exact same way as in Maple.


Is Church-pentation implementable in Agda? Inspired by suggestion in this question, I've implemented predicative Church encoding of Peano arithmetic. Exponentiation works fine, unfortunately tetration requires the level of one of the arguments to he higher, rendering pentation's type unclear.

This is the code:

module Church where
open import Agda.Primitive

Church : {l : Level} -> Set l -> Set l
Church A = (A -> A) -> (A -> A)

Nat = {A : Set} -> Church A
Nat₁ = {A : Set₁} -> Church A
Nat₂ = {A : Set₂} -> Church A

c0 : Nat
c0 = \s z -> z

c1 : Nat
c1 = \s z -> s z

c2 : Nat
c2 = \s z -> s (s z)

add : Nat -> Nat -> Nat
add a b s z = b s (a s z)

mul : Nat -> Nat -> Nat
mul a b s z = b (a s) z

-- First signs of the type growing:
-- exp : {A : Set} -> Church A -> Church (A -> A) -> Church A
exp : Nat -> Nat -> Nat
exp a b = b a

tetr : Nat -> Nat₁ -> Nat
tetr k n = n (exp k) c1

-- does not type-check
-- pent : Nat -> Nat₁ -> Nat
-- pent k n = n (tetr k) c1

Is Church-pentation implementable in Agda?

This paper: Finitely stratified polymorphism might be relevant.

I learned Agda for this task, so perhaps I don't know how to exploit its power.

According to the paper you linked, I think the answer to the question you want to ask is, "no." Pentation is not definable in a stratified version of system F.

The paper says that their system can define every super-elementary function, and all definable functions are super-elementary. The super-elementary functions are level $\mathcal{E}^4$ in the Grzegorczyk hierarchy, and according to wikipedia, moving to the next hyper-operation requires one additional step in that hierarchy. So, $\mathcal{E}^4$ contains tetration, products and sums of tetration, and finite compositions of tetration, but pentation isn't included until $\mathcal{E}^5$. So it is beyond the capabilities of the stratified system F.

This also answers your other question (of course), because the union of all levels in the Grzegorczyk hierarchy is exactly the primitive recursive functions, and the Ackermann function is not primitive recursive. So it cannot be defined.

Now, Agda of course is capable of defining pentation (and the Ackermann function), because any Church numeral can be used to get an equivalent value of the inductively defined natural numbers, and then those can be used to compute the function and converted back to a Church numeral. But presumably that's not what you're interested in.

However, there is also another possibility. Agda's predefined universes are closed under induction-recursion. This means that (in a way) they contain universes of their own, and far, far more universes than exist in the predicative system presented in the paper (which only has $\omega$ many universes, I believe). You can of course define Church numerals for each of these universes. But, I do not know what effect adding quantity of universes (and ignoring structure besides Pi types) has on the ability to define functions on the Church numerals.

Edit:

I did some additional investigation to expand on my last idea, and was able to define pentation of Church numerals. Here is some code, with explanations.

module Pent where

open import Function
open import Level hiding (suc)
open import Data.Unit

import Data.Product
import Data.Nat as N
open N using (ℕ)

Most of this is just for convenience. I won't be cheating with the natural numbers, but they're easier to visualize at the end.

The following exhibits Set as a Mahlo universe. This means that for any A : Set and B : A → Set, there is a universe U : Set that is itself closed under A and B

module Mahlo (A : Set) (B : A → Set) where
  data U : Set
  T : U → Set

  data U where
    A' : U
    B' : A → U
    Π : (s : U) (f : T s → U) → U

  syntax Π s (λ x → t) = Π[ x ∈ s ] t

  T A' = A
  T (B' a) = B a
  T (Π s f) = (x : T s) → T (f x)

  infixr 4 _⇒_
  _⇒_ : U → U → U
  a ⇒ b = Π[ _ ∈ a ] b

I haven't included any universe structure in U besides Pi types. But this means that we can define the type of Church numerals over U, and easily build up to exponentiation of such numerals:

  CH : Set
  CH = (r : U) → (T r → T r) → T r → T r

  zro : CH
  zro r s z = z

  suc : CH → CH
  suc m r s = s ∘ m r s

  one : CH
  one = suc zro

  infixl 10 _+_
  _+_ : CH → CH → CH
  (m + n) r s = m r s ∘ n r s

  infixl 20 _×_
  _×_ : CH → CH → CH
  (m × n) r = m r ∘ n r

  infixr 30 _^_
  _^_ : CH → CH → CH
  (m ^ n) r = n (r ⇒ r) (m r)

However, that is where we get stuck for 'generic' universes about which we know nothing but that they have Pi types (i.e. we don't really know anything about A and B).

Next we define Church numerals valued in arbitrary Set levels:

CHURCH : (α : Level) → Set (Level.suc α)
CHURCH α = ∀(R : Set α) → (R → R) → (R → R)

It is possible to define tetration of CHURCH zero as follows:

_↑_ : CHURCH zero → CHURCH zero → CHURCH zero
(m ↑ n) R s z = n CH (_^_ m') one R' s z
  where
  open Mahlo R (const ⊤) renaming (A' to R')

  m' : CH
  m' = m CH suc zro

So, this might not look like anything special is going on, but it's actually a bit crazier than it first appears. We have two Church numerals over Set, and R : Set that is our result type. So, we use the fact that Set is Mahlo to find a universe U inside Set that contains R. This means that Church numerals over U also live inside Set, which means we can 1) lower our big church numeral m into them, and 2) repeatedly exponentiate the lowered numeral by itself n times. And since U contains R, the numeral we construct is able to iterate the R → R function on the R value to give our answer.

Now, since tetration is defined with a uniform type, it's easy to define pentation as you defined tetration:

_⇈_ : CHURCH zero → CHURCH (Level.suc zero) → CHURCH zero
(m ⇈ n) = n (CHURCH zero) (_↑_ m) (λ R s z → s z)

If you want to visualize the results, you can use the following:

module Visualize where
  open Data.Product

  toCH : ∀{α} → ℕ → CHURCH α
  toCH 0 R s z = z
  toCH (N.suc n) R s z = s (toCH n R s z)

  fromCH : ∀{α} → CHURCH α → ℕ
  fromCH m = lower $ m (Lift _ ℕ) (lift ∘ N.suc ∘ lower) (lift N.zero)

  lift₀ : (CHURCH zero → CHURCH zero → CHURCH zero) → ℕ → ℕ → ℕ
  lift₀ op m n = fromCH (op (toCH m) (toCH n))

  lift₁ : (CHURCH zero → CHURCH (Level.suc zero) → CHURCH zero) → ℕ → ℕ → ℕ
  lift₁ op m n = fromCH (op (toCH m) (toCH n))

  2↑2 2↑3 2↑4 3↑2 3↑3 : ℕ
  2↑2 = lift₀ _↑_ 2 2
  2↑3 = lift₀ _↑_ 2 3
  2↑4 = lift₀ _↑_ 2 4
  3↑2 = lift₀ _↑_ 3 2
  3↑3 = lift₀ _↑_ 3 3

  2⇈2 2⇈3 : ℕ
  2⇈2 = lift₁ _⇈_ 2 2
  2⇈3 = lift₁ _⇈_ 2 3

  tetr : ℕ
  tetr = 3↑3

  pent : ℕ
  pent = 2⇈3

Note, I got tired of waiting for 3↑3 to finish.

So, just to go back a bit, the universe creation principle I used was basically: for every set $R$ there exists a universe $U$ with $R \in U$, which is basically the Grothendieck universe axiom, except all of these universes are themselves inside the universe Set (and the universes are much weaker than set theoretic universes). But this is actually just scratching the surface of how powerful Mahlo is, because you'll notice I essentially did nothing with the B family. So I'm confident you can go beyond pentation with this. This is just the easiest one step further.

(To expand slightly on the last paragraph, the axiom "there exists a universe $V$ such that for every set $S \in V$ there exists a universe $U \in V$ such that $S \in U$" means (if I understand correctly) that $V$ is related to a 1-inaccessible cardinal/ordinal. But Mahlo cardinals/ordinals are hyper-hyper-hyper-...-inaccessible, which is well beyond that.)

Edit 2:

Here is a simpler development showing how you can define uniform tetration with $\omega+1$ universe levels. It uses the latest Agda to be able to talk about Setω, but you might be able to do it in older Agda versions if you inline CHURCH.

module PentPoly where

open import Level
open import Function
open import Agda.Primitive

module Gen (α : Level) where
  Church : Set (suc α)
  Church = ∀(R : Set α) → (R → R) → (R → R)

  one : Church
  one R s z = s z

  _+_  : Church → Church → Church
  (m + n) R s = n R s ∘ m R s

  _×_  : Church → Church → Church
  (m × n) R = n R ∘ m R

  _^_ : Church → Church → Church
  (m ^ n) R = n (R → R) (m R)

CHURCH : Setω
CHURCH = ∀(α : Level) (R : Set α) → (R → R) → (R → R)

_↑_ : CHURCH → CHURCH → CHURCH
(m ↑ n) α R s z = n (suc α) Church (_^_ m') one R s z
  where
  open Gen α
  m' : Church
  m' = m α

I think the way to think about this is that we're taking advantage of Setω being a limit of the universes below it. So any iteration we are asked to do occurs at some particular level below it, and we can iterate exponentiation one level above that. I think this means that we can get all hyper-operations with 'only' $\omega \cdot \omega$ universes.

I also realized my Mahlo above is wrong. It says that for every family on Set there is a universe (U,T) that contains that family. But Mahlo is actually the property that for every mapping between families of sets, there is a universe such that the mapping restricts to that universe. This looks like:

module Mahlo
    (f₁ : (X : Set) → (X → Set) → Set)
    (f₂ : (X : Set) → (Y : X → Set) → f₁ X Y → Set)
  where

  data U : Set
  T : U → Set

  data U where
    Π : (x : U) → (y : T x → U) → U
    reflect₁ : (x : U) → (y : T x → U) → U
    reflect₂ : (x : U) → (y : T x → U) → f₁ (T x) (T ∘ y) → U

  T (Π x y) = (v : T x) → T (y v)
  T (reflect₁ x y) = f₁ (T x) (T ∘ y)
  T (reflect₂ x y z) = f₂ (T x) (T ∘ y) z

  res : Σ[ x ∈ U ] (T x → U) → Σ[ x ∈ U ] (T x → U)
  res (x , y) = (reflect₁ x y , reflect₂ x y)

But this is even further unnecessary power from the perspective of the original question.


Vertex disjoint simple paths of length k A lot of effort has been invested in finding simple k-paths, as well as in finding vertex disjoint paths.

Is there any known parametrized algorithm that given a graph $G=(V,E)$, decides whether there exist $p$ vertex disjoint simple paths of length $k$ in the graph?

Finding a single simple k-path is known to be single exponent $FPT$ for a long time, what about this variant (with respect to both $p,k$ as parameters)?

It appears that this problem (or a generalization of it) was considered with the Divide and Color approach yielding a $O^*(4^{(k-1)\cdot p})$ run-time algorithm for deciding the problem.


Reverse Graph Spectra Problem? Usually one constructs a graph and then asks questions about the adjacency matrix's (or some close relative like the Laplacian) eigenvalue decomposition (also called the spectra of a graph).

But what about the reverse problem?  Given $n$ eigenvalues, can one (efficiently) find a graph that has this spectra?

I suspect that in general this is hard to do (and might be equivalent to GI) but what if you relax some of the conditions a bit?  What if you make conditions that there is no multiplicity of eigenvalues?  What about allowing graphs that have "close" spectra by some distance metric?

Any references or ideas would be welcome.

EDIT:

As Suresh points out, if you allow undirected weighted graphs with self loops, this problem becomes pretty trivial.  I was hoping to get answers on the set of undirected, unweighted simple graphs but I would be happy with simple unweighted directed graphs as well.

Cvetcovic et all in Section 3.3 of "Recent results in the theory of graph spectra" goes over  algorithms for constructing graphs given spectrum in some special cases


A combinatorial version for the polynomial Hirsch conjecture Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .

Suppose that

(*)

For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$,
there is $S \in {\cal F}_j$ which contains $R \cap T$.

The basic question is:

How large can t  be???

What is known

The best known upper bound is quasi polynomial $t \le n^{\log n+1}$.

The best known lower bound is (up to a logarithmic factor) quadratic.

This abstract setting is taken from the paper Diameter of Polyhedra: The Limits of Abstraction by Friedrich Eisenbrand, Nicolai Hähnle, Sasha Razborov, and Thomas Rothvoss. The quadratic lower bound as well as a proof of the upper bound can be found in their paper.

Motivation

Every upper bound will apply to the diameter of graphs of d-dimensional polytopes with n facets. To see this associate to every vertex $v$ the set $S_v$ of facets containing it. Then starting from a vertex $w$ let ${\cal F}_r$ be the sets corresponding to vertices of the polytope of distance $r+1$ from $w$.

More

This problem is the subject matter of polymath3. But I thought it can be useful to present it here and on MO in spite it being an open problem. If the project will lead to specific subproblems I (or others) may try asking them as well.

(Update; Oct 5:) One specific problem that is of special interest is to restrict attention to sets of size d. Let f(d,n) be the maximum value of t when all sets in all families have size d. Let f*(d,n) be the maximim value of t when we allow multisets of size d.
Understanding f*(3,n) may be crucial.

Problem: Does f*(3,n) behaves like 3n or like 4n?

The known lower and upper bounds are 3n-2 and 4n-1 respectively. and since the 3 is the beggining of the sequence 'd'  while the 4 is the beginning of the sequence $2^{d-1}$ deciding if the truth is 3 or 4 nay be of importance.
See the second thread.

A friend of mine and me have decided to try the brute-force method and compute some values of $t$ for small values of $n$ and $d$. This is totally impossible without employing pruning, and we hope that the tricks we have found will give some insight in the rest of the problem. So far, we have not managed to get the doubly-exponential running time of the brute force method down significantly (roughly $3^{2^n}$ is our best bound so far) and hence we have not yet reached our original goal of somehow predicting the function behind $f$ from its first few values. We have also not studied all the comments of the previous threads in detail, so some of this may already be known - we basically had fun making our code fast and wanted to post our results somewhere, if I had a functioning LaTeX environment I would have put this on the ArXiV.

Code (it's not exactly production code...): http://pastebin.com/bSetW8JS. Values:

f(d=2, n)=2n-1 for n <= 6

f(d=3, n=3) = 6
{} {0} {01} {012} {12} {2}

f(d=4, n=4) = 8
f(d=3, n=4) = 8
{} {0} {01} {1,02,03} {2,13} {123} {23} {3}
{} {0} {01} {2,013} {1,02,03} {023} {23} {3}

f(d=5, n=5) = 11
f(d=4, n=5) = 11
f(d=3, n=5) = 11
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {012,3} {02,12,013,014} {13,023,04,124} {123,024} {23,24} {234} {34} {4}
{} {0} {01} {012,13} {02,12,013} {03,123,014,024} {023,124} {23,24} {234} {34} {4}

We say that the sequence ${\cal F}_1, ..., {\cal F}_t$ is convex if (*) holds. Our approach constructs convex sequences by appending families to shorter convex sequences, essentially using that if ${\cal F}_1, ..., {\cal F}_t$ is convex, then ${\cal F}_1, ..., {\cal F}_{t-1}$ is convex. We note that ${\cal F}_1, ..., {\cal F}_t$ is convex if and only if for all $A \in {\cal F}_t$ we have that ${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$ is convex. We say that $A$ is compatible with ${\cal F}_1, ..., {\cal F}_{t-1}$ if ${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$ is convex - we save computation time by computing the sets that are compatible with a sequence and then taking the elements of their powerset as the new ${\cal F}_t$, rather than determining if ${\cal F}_1, ..., {\cal F}_t$ is convex directly.

Our next speedup is essentially dynamic programming. We try to find an equivalence relation $\sim$ on convex sequences with the following two properties. First, if ${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$ for two convex sequences, then $A$ is compatible with ${\cal F}_1, ..., {\cal F}_t$ if and only if it is compatible with ${\cal F}'_1, ..., {\cal F}'_t$. Second, if ${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$ and ${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$ is convex, then ${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1} \sim {\cal F}'_1, ..., {\cal F}'_t, {\cal F}_{t+1}$. Furthermore, we would like it if we can determine whether a set is compatible with elements from an equivalence class, and determine a representative of the equivalence class of ${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$ given ${\cal F}_{t+1}$ and a representative of the equivalence class of ${\cal F}_1, ..., {\cal F}_t$. The ensuing dynamic programming algorithm is then obvious. The number of equivalence classes (along with the time taken by the above two operations) then gives a bound on the running time of the obvious dynamic programming algorithm.

For the equivalence we use to get our bound, we use a characterization of convexity that is based on `intervals' as follows. Given a subset $A$ of $\{ 1, \dots, n \}$, we say $A$ is contiguous with respect to a (not necessarily convex) sequence ${\cal F}_1, ..., {\cal F}_t$ if $\{ k \mid \exists B \in {\cal F}_k : A \subseteq B \} = \{ i, \dots, j \}$ for some integers $1 \leq i \leq j \leq n$. We say that $(i, j)$ is the interval for $A$ w.r.t. this sequence. It is easily seen that ${\cal F}_1, ..., {\cal F}_t$ is convex if and only if all subsets of $\{ 1, \dots, n \}$ are contiguous with respect to the sequence.

Now, given a convex sequence ${\cal F}_1, ..., {\cal F}_t$, we mark all subsets of $\{ 1, \dots, n \}$ as not touched, disallowed or active as follows: all elements of ${\cal F}_t$ are active, all elements of ${\cal F}_1, ..., {\cal F}_{t-1}$ are disallowed and all supersets $B$ of sets $A$ whose interval with respect to ${\cal F}_1, ..., {\cal F}_{t-1}$ is $(i, j)$ with $j < t - 1$ are also disallowed. It is immediate that a set $A$ is compatible with the sequence if and only if it is marked as not touched. We define two sequences as equivalent under $\sim$ if their marking is equal. It is easily seen that this equivalence relation satisfies our two properties. For computing whether a set $B$ should be disallowed by the interval condition, we can use the equivalent condition 'there exists a set $C \in {\cal F}_t$ such that for no set $D \in {\cal F}_{t+1}$, $B \cap C \subseteq D$'. $3^{2^n}$ is an immediate bound on the number of equivalence classes.

We also use various extra prunings. We only consider antichains for ${\cal F}_{t+1}$ and we require that the elements of its elements come from ${1, \dots, i}$. Lastly, we use the optimization that ${\cal F}_1 = \{ \{ 1 \} \}, {\cal F}_2 = \{ \{ 1, 2 \} \}$ for optimally long sequences (and similar for ${\cal F}_{t-1}$ and ${\cal F}_t$). We imagine that investigating the behaviour of ${\cal F}_3$ may result in more drastic savings.


NPI-candidate hereditary graph property? A graph property is called hereditary if it is closed with respect to deleting vertices. There are many interesting hereditary graph properties. Moreover,  a number of nontrivial general facts are also known about hereditary classes of graphs, see "Global properties of hereditary classes?"

Considering complexity, hereditary graph properties include both polynomial-time decidable and NP-complete ones. We know, however, that there are  a number of natural problems in NP that are candidates for NP-intermediate status, see a nice collection in Problems Between P and NPC. Among the numerous answers there, however, none of them looks like a hereditary graph property (unless I overlooked something).

  Question: Do you know a hereditary graph property that is a candidate for NP-intermediate status? Or else, is there a dichotomy theorem for hereditary graph properties?

Is there a particular style of problem you are looking for, or anything related to a hereditary graph property? Two common types of problems would be
(1) recognition: does a given $G$ have the hereditary property? or
(2) find the largest (induced or not) subgraph $H$ in $G$ having the hereditary property.

As I'm sure you are familiar, (2) is NP-complete (Mihalis Yannakakis: Node- and Edge-Deletion NP-Complete Problems. STOC 1978: 253-264) But I'm not sure if you are specifically only asking about problems of type (1) (recognition problems.)

There are a few recognition problems of hereditary graph classes which are still open. I think the one-in-one-out graphs are open to recognize and clearly in NP.

Graphclasses.org also reports that the related class of opposition graphs is still open to recognize (and these are also clearly in NP.) Apparently, so is the class of Domination graphs.

A large list of open (and unknown) recognition status can be found on that site, and pretty much all of those properties appear to be hereditary.

http://www.graphclasses.org/classes/problem_Recognition.html

There is one recognition problem they list under GI-complete, which is not a hereditary property ... so it is interesting to think that perhaps deciding a hereditary problem may indeed have a dichotomy theorem.


What is the hardest instance for the group isomorphism problem? Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows: given two groups, check whether they are isomorphic or not. There are different ways to input a group, the two mostly used are by a Cayley table and by a generating set. Here I am assuming input groups are given by their Cayley table.  More formally:

$\textbf{Group Isomorphism Problem}$

$\textbf{Input : }$ Two groups $(G,\cdot)$ and $(H,\times)$.

$\textbf{Decide : } $ Is $G \cong H$?

Let us assume that $n = |G| = |H|$

Group Isomorphism problem when input groups are given by Cayley table is not known to be in $\textbf{P}$ in general. Although there are group classes like the abelian group class for which the problem is known to be in polynomial time, groups which are the extension of an abelian group, simple groups etc. Even for nilpotent class two groups, no algorithm better than brute force is known.

A brute force algorithm for group isomorphism is given by Tarjan, which is as follows. Let $G$ and $H$ are two input groups, and let $S$ be a generating set of the group $G$. It is a well-known fact that every finite group admits a generating set of $\mathcal{O}(\log n)$ size and which can be found in polynomial time. The number of images of the generating set $S$ in the homomorphism from $G$ to $H$ is $n^{\log n}$ many. Now, check whether each possible homomorphism is bijective or not. The overall runtime will be $n^{\log n + \mathcal{O}(1)}$.

Let me first define the center of the group $G$:

$$Z(G) = \{g \in G \mid ag=ga, \forall a \in G\}$$

$Z(G)$ denotes the elements of the group $G$ which commutes with all other elements of the group $G$. Groups for which $G/Z(G)$ ( / used for quotient) is abelian are known as a nilpotent class two groups. To me it appears that nilpotent class two groups are the hardest instances to solve the group isomorphism problem. The meaning of "hardest instances" is: solving that case will allow researchers who work in group theory to solve the isomorphism problem of a large number of groups.

Initially, I thought that simple groups are the hardest instances as they are building blocks of all groups, but later came to know that the isomorphism problem for simple groups is in $\textbf{P}$.

Question:  What is the hardest instance for the group isomorphism problem?

$p$-groups of class 2 and exponent $p$ are widely believed to be the hardest case of Group Isomorphism ($p > 2$). (For $p=2$, we need to consider exponent 4, since all groups of exponent 2 are abelian - easy exercise for the reader.) Although there is as yet no reduction from general GpIso to this class of groups (though see point 0.5 below), there are several reasons for this belief. Let me outline some of them here.

0) Practical experience (see papers by Newman, Eick, O'Brien, Holt, Cannon, Wilson, ... which give the algorithms that are implemented in GAP and MAGMA).

0.5) [EDIT: added 8/7/19] Reductions. When such $p$-groups are given by generating sets of matrices over $\mathbb{F}_p$, the problem is $\mathsf{TI}$-complete [G.-Qiao '19]. Also (cf. point (4) below), isomorphism of $p$-groups of exponent $p$ and class $c < p$ reduces in poly time to isomorphism of $p$-groups of exponent $p$ and class 2 (ibid.).

1) Structure (reduce to solvable, then to $p$-group). Every finite group contains a unique maximal solvable normal subgroup, called the solvable radical, denoted $Rad(G)$. $G/Rad(G)$ contains no abelian normal subgroups, and isomorphism of such groups can be handled efficiently in practice (Cannon-Holt J. Symb. Comput. 2003) and in theory (Babai-Codenotti-Qiao ICALP 2012). Even for groups where $Rad(G)$ is abelian, some of these can be handled in $n^{O(\log \log n)}$ time (G-Qiao CCC '14, SICOMP '17) - so, not quite polynomial, but much closer than $n^{\log n}$. The main obstacle thus appears to be solvable (normal sub)groups. Now, within solvable groups, there is a lot of structure - starting with the fact that every solvable group is a knit product of its Sylow $p$-subgroups - and it seems the hardest cases are $p$-groups.

2) Counting. The number of groups of order $n$ is $\leq n^{(\frac{2}{27} + o(1))\mu(n)^2}$, where $\mu(n)$ is the largest exponent of any prime dividing $n$ (Pyber 1993). The number of $p$-groups of order $n=p^m$ is at least $p^{(\frac{2}{27} + o(1))m^2}$ (Higman 1960). So you see that the coefficient of the leading terms in the exponents match. In this sense "most" groups are $p$-groups (even of class 2 and exponent $p$). There is a long-standing conjecture which says that "most" in the preceding weak sense can be strengthened to say that proportion of groups of order $\leq n$ which are $p$-groups tends to 1 as $n \to \infty$.

3) Universality (/wildness). Giving a classification of $p$-groups would imply a classification of all modular representations of any finite group (or even Artinian algebra) in characteristic $p$ (Sergeichuk 1977).

4) Flexibility. Why $p$-groups of class 2 and not higher class? (Note that $p$-groups of nearly-maximal class, so-called "small coclass", have essentially been classified, Eick & Leedham-Green 2006, see also some of the answers here.) To any $p$-group one can associate a graded Lie ring, where bracket in the Lie ring corresponds to commutator in the group. Associativity in the group implies the Jacobi identity for the bracket, thus giving rise to a genuine Lie ring. However, note that when the group is class 2, the Jacobi identity is trivially satisfied (all its terms are automatically 0), so this puts no additional constraints on the structure. It basically just corresponds to an arbitrary skew-symmetric bilinear map. For $p$-groups of exponent $p$, there is even a reduction from class $c < p$ to class 2.


Does Dirac's theorem on Hamiltonian cycles only apply to undirected graphs? Does Dirac's theorem on Hamiltonian cycles only apply for undirected graphs? If the theorem applied to directed graphs, the graph with the following adjacency list should have a Hamiltonian cycle, but I can't find one.

  $0$: $1$ $2$ $3$

  $1$: $2$ $3$

  $2$: $1$ $3$

  $3$: $1$ $2$

While Dirac's theorem wasn't intended/proved for directed graphs, it was extended to directed graphs by GHOUILA-HOURI in 1960 ("Une condition suffisante d’existence d'un circuit hamiltonien").

Their requirements, however, were that each vertex should have both out-degree and in-degree of at least $n/2$, which is not the case in your graph.

One of the original conditions of GHOUILA-HOURI, as Saeed mentioned, is that the graph is strongly connected. In fact, the degree conditions are strong enough for only diameter $\leq 2$ graphs to be considered.


One-Way Functions vs. perfectly binding commitments If OWFs exist, then statistically binding bit commitment is possible.[1]

Is it known that if OWFs exist then perfectly binding bit commitment is possible?

If no, is there a known black-box separation between them?

[1] http://en.wikipedia.org/wiki/Pseudorandom_generator_theorem and

http://en.wikipedia.org/wiki/Commitment_scheme#Bit-commitment_from_a_pseudo-random_generator

In a recent work with Rafael Pass, it is shown that without those extra complexity assumptions of Barak-Ong-Vadhan, noninteractive commitments can not be based on one-way functions in a black-box way. In fact even with these extra assumptions (when formalized as some kind of hitting property assumed in addition to one-way-ness) still a black-box separation holds:

http://eprint.iacr.org/2012/523.pdf

(the construction of Barak-Ong-Vadhan is non-black-box).


Are deterministic context-free languages closed under outfix (or other erasing operations) Define the outfix of a language $L$ to be
$Outf(L) = \{xy \mid \exists z. xzy \in L \}$.

Are any known results about whether deterministic context-free languages are closed under this operation, or other similar "erasing" operations?

My preliminary search has not turned up anything, but I thought someone who had knowledge of the area might know of a reference.

A proof that uses closure properties:

DCF languages are not closed under union, so take,  $L_1, L_2 \in DCF$ s.t. $L = L_1 \cup L_2 \notin DCF$

Add three new symbols $\{\alpha, \beta, \#\}$ to the original alphabet $\Sigma$ and build the languages:

$L'_1 = \{ \alpha \# w \mid w \in L_1\}$
$L'_2 = \{ \beta \# w \mid w \in L_1\}$

We have $L'_1, L'_2$, but also $L' = L'_1 \cup L'_2 \in DCF$ (it is enough to add a starting state that leads to the recognition of $\#L_1$ after reading a leading symbol $\alpha$ or the recognition of $\#L_2$ after reading a leading symbol $\beta$).

Now suppose that $Outf(L') \in DCF$; we know that DCFs are closed under intersection with regular languages, so:

$$Outf(L') \cap \{ \#w \mid w\in \Sigma^*\} =  \{ \#w \mid w\in L_1 \lor w \in L_2 \} \in DCF$$

too.

But given a DPDA for $Outf(L') \cap \{ \#w \mid w\in \Sigma^*\}$ it is immediate to build a DPDA for $\{ w \mid w \in L_1 \lor w \in L_2\} = L$ (just skip the recognition of the first leading symbol $\#$), so $L \in DCF$ contradicting the hypothesis.


Sum-of-Squares Certificates We say that $f$ has a degree $2d$ sum-of-squares certificate if $f=\sum_{i=1}^r (g_i(x))^2$, where for each $i\in[r]$, we have that $g_i$ is a polynomial of degree at most $d$. Thus showing that $f$ has a sum-of-squares certificate is one way of showing that $f\ge 0$.
Let $f_G(x)=\frac{1}{4}\sum_{(u,v)\in E}(x_u-x_v)^2$ for $x_u\in\{\pm1\}$ be the cut size function for an input vector $x\in\mathbb{F}_2^n$, denoting the side of the vertices across a cut and let $\mathsf{OPT}(G)=\max_x f_G(x)$.
Why does literature (e.g., http://web.stanford.edu/class/cs369h/lectures/lec5.pdf) go through work of showing that there exists a degree 2 sum-of-squares certificate for $\frac{\mathsf{OPT}(G)}{0.878}-f_G(x)$? Isn't this vacuously true since $\frac{\mathsf{OPT}(G)}{0.878}\ge\mathsf{OPT}(G)\ge f_G(x)$ or is the input vector $x$ to $f_G(x)$ relaxed in this case, i.e., $x\in\mathbb{R}^n$? Is it correct that any algorithmic statement, such as the Goemans-Williamson algorithm, still needs a separate statement of correctness independent of the degree 2 sum-of-squares certificate? If so, is the purpose of the certificate to lay the groundwork for showing that any minimally lossy rounding algorithm achieves $0.878-\epsilon$ approximation?
Thanks in advance!

I see the confusion, but I think the document you provided pretty well explains what is meant: solving MAXCUT on a graph $G$ is equivalent to finding the smallest value of $c$ such that $c-f_G(x)\geq 0$ for every $x\in \{-1,1\}^n$. As you write, it is trivially true that $c^*=\mathsf{OPT}(G)$ is the optimal value where this holds by definition, but for one, you want to determine the value of $\mathsf{OPT}(G)$ explicitly, and equally as important, there will not in general be a degree 2 sum-of-squares proof for any $c$ better than $\mathsf{OPT}(G)/.878$ (this doesn't rely on UGC or anything fancy like that; if I remember right, there are known hard examples that basically embed vectors in a high-dimensional sphere with edges that emulate where the GW algorithm has a tough time in the rounding and uses the isoperimetric inequality on the sphere to argue about the real optimal value). The point of doing the degree 2 sum-of-squares algorithm is that there for sure exists a degree 2 sum-of-squares certificate of this polynomial inequality over $\{-1,1\}^n$ for any $c\geq\mathsf{OPT}(G)/.878$ (which is what the work in the literature you reference establishes), so by doing binary search, you can algorithmically determine this looser quantity efficiently.


Finding output with unique witness in matrix multiplication Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N \times N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C = AB$ (not boolean matrix multiplication but the entries store the count of how many $y$ generate a given output entry). My goal is to find only the output entries in $C$ which are generated by exactly one value of $y$ (i.e. a unique witness). In other words, I want to find all $(i,j)$ such that $C(i,j) = 1$. Clearly, I can simply perform the matrix multiplication and iterate over $C$ to identify the output with unique witnesses but can we do better? Is this problem as hard as matrix multiplication itself? Are there are any known reductions that consider the problem of finding output that is generated by a unique $y$ value? I am interested in deterministic algorithms but even something probabilistic may be insightful.

You can reduce Boolean matrix multiplication (BMM) to this problem. (BMM is matrix multiplication over the OR/AND semiring with 0 and 1.) Imagine adding one more column to the first matrix A and one more row to the first matrix B, both of which are all-ones. If the BMM of A and B had a 0 in an entry, your new product over the integers will have 1, and if the BMM had a 1 in an entry, your new product over the integers will have at least a 2. Thus determining these "exactly one" entries is at least as hard as BMM.
Whether or not BMM can be solved faster than matrix multiplication over a ring or field is a major open problem.


Languages that lack contraction, weakening or exchange When learning about generalized arrows, a question arised to me: Are there any languages (or potential languages) that lack one or more of the structural rules: contraction, weakeing and exchange?
Under Curry-Howard isomorphism, these rules, used frequently in logic, map into programming concepts. If we denote $A, B, C \vdash D$ a program (corresponding to a natural deduction proof) that computes a value of type $D$ from inputs of types $A$, $B$ and $C$, we get:

Contraction: $\Gamma, A, A\vdash B$ can be transformed into $\Gamma, A\vdash B$.
That is, a single input can be used twice.

Weakening: $\Gamma\vdash B$ can be transformed into $\Gamma, A\vdash B$.
That is, it's possible to add arbitrary, unused inputs.

Exchange: $\Gamma_1, A, B, \Gamma_2 \vdash C$ can be transformed into $\Gamma_1, B, A, \Gamma_2 \vdash C$.
That is, the order of inputs doesn't matter.

An example for language lacking contraction would be quantum computing. There the allowed operations can be described with unitary matrices, and duplicating a value can't be expressed as such.
It also seems to me that weakening isn't an admissible rule for quantum computing, at least in the above form, as we can't forget a value with a unitary matrix. But we could have a weaker rule such as $\Gamma\vdash B$ can be transformed into $\Gamma, A\vdash A\otimes B$, and the $A$ in the output can be dropped when extracting the results of such a computation.
The exchange rule is clearly permissible in quantum computing.
Are there any other examples, in particular a language that doesn't allow exchange, or where weakening isn't allowed even in such a weaker form?

As other commenters have mentioned what you are actually asking for is a language for planar string diagrams, aka monoidal categories.

But let me address your question purely from the point of view of quantum computation.  Clearly in any reasonable system you would want to have an introduction rule for the tensor product -- your proposed weakening rule is just a special case of this.  Note that if you have any interesting (i.e. entanglement creating) constants in your language it's not really true to say that your can just forget $A$ in the output, unless the $A$ and $B$ parts never interact.

It also not quite right to say that contraction can't be admitted.  There are (many, inequivalent) maps of type $A \to A\otimes A$ which are quantum-realisable. However none of them are natural transformations, which probably you want.

There were many attempts in the early 2000s to shoe-horn quantum computing into linear logic, which were largely unsuccessful:  too much of the LL structure becomes degenerate, and too little of what makes quantum work is present in bare LL.

However you asked for an example of a system which lacks these rules; an early example is Selinger's QPL http://dx.doi.org/10.1017/S0960129504004256.  More or less every other proposed quantum programming language that actually has a type system will disallow contraction and weakening for quantum data.

If you want to get rid of the exchange rule you might be interested in the field of topological quantum computing.  In this setting the unitary operations are constructed from braidings; so the exchange rule is replaced by the braiding.


Lower bound on probability of getting two close points in a sample of $n$ points Let $D\subseteq \mathbb{R}^k$. Assume that $Pr_{u,v\leftarrow U_D}[|u-v| <B]>p$ for some $B,p$, where $|u-v|$ is the L1 distance of the vectors.

$S\subseteq D$ is obtained by sampling $n$ elements uniformly from $D$. Give a lower bound, as tight as possible, on $P\equiv Pr_{S\leftarrow U_D}[\exists u,v\in S:|u-v|<B]$. The bound can depend on the $k$, which should be thought of as a small constant, i.e., $k<<|D|$.

Specifically, the bound has to be tighter than the following trivial one: $P\ge 1-(1-p)^{n/2}$. This is obtained by dividing the $n$ points to $n/2$ pairs that are sampled independently. Then, $1-P$, the probability that $\forall u,v\in S:|u-v|\ge B$, is at least as low as the probability that none of these pairs will have distance lower than $B$. Since these events are independent, we get $1-P\le (1-p)^{n/2}\Rightarrow P\ge 1-(1-p)^{n/2}$.

Intuitively, since $S$ has $\frac{n^2}{2}=O(n^2)$ pairs of points, each corresponding with a possible "closeness" event, we would expect to get something like $P\ge 1-(1-p)^{O(n^2)}$, following a similar calculation to the above. However, without event independence this not easy to show (and possibly not true).

We are thus looking for a bound $C$ s.t. $P\ge C, C=1-(1-p)^{\omega (n)}$. Or to show that it does not exist. $C$ can be a function of the constant $k$.

Here's a counter-example showing your desired bound is not possible, unless I am mistaken.  It's a simple variant of the example in Roei's comment.

Fix any $n$ and $N\ge 4n$.  Take $D$ to contain $N/2$ points that are all the same (or all within distance 1 from each other), and $N/2$ points that are all widely separated (at distance at least 1 from every other point in $D$).  This can be done even with $D\subset\mathbb{R}^1$.

The probability that two uniformly random points in $D$ are within distance 1 from each other is $1/4$.  In your notation, $p=1/4$ for $B=1$.

The probability that $n$ uniformly random points in $D$ don't contain some pair within distance 1 from each other is (at least) the probability that all $n$ points are in the widely separated set and distinct, which is at least $[(N/2-n)/N]^n \ge 1/4^n$.

So, in your notation $1-P \ge 1/4^n \ge (3/4)^{5n} = (1-p)^{5n}$.

So, $P \le 1 - (1-p)^{5n}$.  So your desired upper bound $P \ge 1-(1-p)^{\omega(n)}$ does not hold.

(If you generalize the example above for arbitrary (small) $p>0$, I think you get something like $P \le 1- (1-\sqrt p)^n \approx 1-(1-p)^{n/\sqrt p}$, which is not a counterexample if $p\rightarrow 0$ as $n\rightarrow \infty$.)


Simplest Machine Model Accepting $L = \{ww^Rw\;|\; w\in \Sigma^*\}$ Let $\Sigma$ be a finite alphabet.
A trivial finite automaton can accept the language $L_1 = \{w\;|\;w\in \Sigma^*\}$. A simple pushdown automaton can accept the language
$L_2 = \{ww^R\;|;w\in \Sigma^*\}$ where $w^R$ is the reverse of $w$, i.e.,
the string obtained from $w$ by reading it backwards.

What is the simplest non-universal machine model which accepts the language $L_3 = \{ww^Rw\;|\;w\in \Sigma^*\}$? Note that $L_3$ can be easily accepted by a queue automaton, but queue automata are universal.
Are there well studied classes of non-universal automata accepting non-context free languages?

You don't need nondeterminism or multiple heads.  Even a 2DPDA can accept this language:  push 2 counters per symbol while scanning from left endmarker to right; then pop 3 per symbol while scanning left until stack empty. At this point you're at the boundary between first w and w^R.  Scan left, pushing onto stack until left endmarker.  Now stack has w^R.  Play the same game again with the counters, then move right comparing stack contents to symbols read.
If success, then first 2/3 of string is w w^R.  A similar trick can be used to ensure last 2/3 of string is w^R w.  And of course, precede all of this with a single scan to make sure input is of length == 0 (mod 3).

There is an intro to 2DPDA's in my book, A Second Course in Formal Languages and Automata Theory.


Difference between abstract machines and calculi So, first of all: I'm not sure how to tag this question. Feel free to tag it differently.

I recently started reading up on CHAMs, which can express different process calculi. Slightly confused, I go to read up on abstract machines. Okay, so, abstract machines are... machines in which you can express algorithms...

My thought process then was: [...] algorithms, which are expressed in math... which is what the calculi are for.

So, from my understanding, there's some sort of implicit layering going on here where somewhere up the math-ladder there's this abstract machine which can be used to express more mathematically pure calculi, and somewhere embedded in that jumble is the concept of an algorithm expressed in the math... of the abstract machine?

What is the difference between abstract machines and calculi, if there is one?

If there is a difference, what draws the line between abstract machines and calculi?

I essentially agree with Martin's comment, I can elaborate on that to make a tentative answer, knowing that there is no general formal definition of calculus or abstract machine and that what I am going to describe cannot possibly cover the meaning of all instances of these two words found in the literature.

In brief: a calculus usually gives you the abstract spefication of the meaning of programs, whereas an abstract machine usually implements that specification.  Such an implementation is likely to be still high-level (i.e., many low-level details are not specified), hence the adjective "abstract", but it gets closer to what a phyisical machine would do to execute programs (according to the spefication given by the calculus).

More in detail: a calculus usually comes with an operational semantics, which gives you the meaning of programs in terms of the result they denote (if any). For this, one often uses the notation

$t\Downarrow v$,

which means that "the value (i.e., the final result) of the expression $t$ is $v$". Now, such a "big step" operational semantics (as it is sometimes referred to) is usually given in terms of a derivation system (i.e., a system in which you can prove judgments of the form $t\Downarrow v$), which is useful to reason abstractly about programs but is a bit far from describing how the execution of $t$ would look like on a concrete machine.

One may then move to a "small step" operational semantics, which is a set of rewriting rules on expressions (written $t\rightarrow t'$) describing how one can, step by step, compute the value of an expression (if any):

$t\Downarrow v\quad$ iff $\quad t\rightarrow^\ast v$.

Now, even the small-step semantics may be too coarse: typically, some rewriting rules may duplicate arbitrary big sub-expressions, and a chain of duplications may cause an exponential blow-up of the size of expressions in only a linear number of steps, which means that these steps are not so "small" after all...  In particular, one may want to give a more realistic description of the execution of programs, getting even closer to the machine level. This is where abstract machines come into the picture.

It is impossible to give a general description of an abstract machine, since they may differ greatly. However, these usually include low-level components (e.g. a pointer to a "code memory" where the executed program is stored, a stack, a memory for storing the values of variables, etc.) which make them look much more like physical machines executing the programs of the language underlying the original calculus.

About where to "draw the line" between calculi and machines: this is actually a tricky question. There are calculi whose small-step semantics is more or less the same thing as an abstract machine. Lambda-calculi with explicit substitutions are examples of this: in such calculi, expressions contain constructs (the explicit substitutions) which make it possible for the small-step semantics to operate at a lower level, much closer to that of the machine.

About your reasoning on how the levels of expression of an algorithm are "layered", I am not sure I follow it, so I cannot say much. But I hope that at least I gave you some elements of answer to your last two questions.


Is anyone actively researching distributed prediction models? Is there any current, ongoing, research being performed, looking specifically at implementing prediction models on a distributed system? I'm specifically interested in work where the underlying system can be modeled as a network of devices that has significant churn in terms of connections between the nodes, and nodes joining/leaving the network (for example, a peer-to-peer network).

There is no information about any particular prediction model in your request, therefore, I think you should look through the paper "PLDA: Parallel Latent Dirichlet Allocation for Large-scale Applications" (2009) of Google researchers. See also their project on Google Code.

Besides, Google Prediction API project might be valuable resource related to the topic, too.


Computing parity of a permutation in a streaming-fashion way I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of the permutation. The question I'm interested in how much memory a deterministic algorithm should use. Is there any randomized algorithm for the problem?

I know that computing number of inversions in one pass uses $\Theta(n)$ memory. The upper bound can be easily obtained with any BST. The lower bound is presented here: http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622

Alas, the proof of the lower bound in the paper can not be extended to the parity case (or it's not so obvious to me).

Also I know that computing parity in a little space with random access to a permutation can be done in $O(n \log n)$ time and $O(\log^2 n)$ memory by deterministic algorithm or in $O(n \log n)$ time and $O(\log n)$ memory by randomized one. See http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.2256

The main idea is that the parity of a permutation can be computed by formula $sgn(\pi) = (-1)^{n - c}$, where $c$ is the number of cycles and $n$ is the size. The authors make the cycle decomposition of a permutation. So one can easily compute the number of cycles.

Does anybody know an effective algorithm or lower bound on memory for computing parity in the streaming model? Randomized algorithms better than random coin are interesting to me too.

I would like to ask everyone not to upvote this, as this is not an answer, but an extended comment, in which I would like to argue why this question did not receive any answers. My main point is, that a communication complexity lower bound won't work. By this, I mean that no matter how we cut the input into two parts and give it to two players, A and B, A can transfer a single bit to B from which he can compute the parity of the permutation. (This follows simply by considering inversions.)

Proofs that use another bound are hard.
See this comment here by Noam Nisan (for the non-deterministic version): Bounds on the size of the smallest NFA for L_k-distinct,

this related question by myself answered by Hermann Gruber which shows that the communication complexity lower bound can be very far from the truth (again in the non-deterministic version)
Lower bound for NFA accepting 3 letter language.

Also related that to decide whether the permutation is a single cycle, seems to be hard, see this FOCS paper by Ran Raz and Boris Spieker:
http://www.computer.org/csdl/proceedings/focs/1993/4370/00/0366870-abs.html.

So, I am also very interested to learn the answer to this question.


Karp-like reductions vs Cook-like reductions for Functional Complexity Classes. Assume we have two counting (functional) complexity classes $A$ and $B$. Suppose that

Under Karp-like reductions $A$ is strictly inside $B$.
Under Cook-like reductions $P^A=P^B$.

  What does this tell us about the relationship between these two
  counting complexity classes?

I think this situation is too general to draw many conclusions, but here goes...

If $A$ is closed under Cook-like reductions, then (2) would imply $B \subseteq A$, contradicting (1), so it tells you that $A$ is not closed under Cook-like reductions.

One way to paraphrase the original statement is: to make the classes equal in power requires more than a single query.

One can then ask about other intermediate types of reductions to get a better sense of just how many queries are needed and in what way e.g. are the classes equivalent under truth-table (nonadaptive) reductions? What's the best bound we can put on the number of queries ($2$, $O(1)$, $O(\log n)$?) Since these are counting classes, one could also ask about parsimonious reductions.


Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it? If I understand correctly, to prove that problem $A$ is NP hard, you need to pick all possible problems $B_{i}$ that are in NP and then prove that they reduce to $A$ by using a polynomial time computable function, that maps instances of each $B_{i}$ to instances of $A$.

Once you find the first NP hard problem, by using reductions you can then find that many other problems are either NP Complete or NP Hard. However I imagine that this depends. If you are unlucky, then maybe all $B_{i}$ problems reduce to $A$, but $A$ reduces nowhere else, so your proof is essentially useless.

My question is about the motivation that Stephen Cook behind showing that the SAT problem is NP hard. Did he see a lot of potential behind this problem? Did he know that if he showed that this problem is NP hard then a lot of other problems could be shown to be NP hard as well?

In short, what is the story behind this proof? Because after studying some basic complexity theory, it really seems like this proof was one of the most significant ones in this area.

First of all, Cook actually showed that the problem of whether a logical expression is a tautology is $\mathbb{NP}$-complete under Cook reductions. The proof however works by replacing them with Karp reductions to show that $SAT$ is $\mathbb{NP}$-complete, in the modern sense of the term.

As for whether Cook understood the significance of a $\mathbb{NP}$-complete problem not being in $\mathbb{P}$, going through the actual paper  shows that he did. However, I believe it wasn't until Karp's list of 21 complete problems that the practical significance of Cook's result began to be understood.


Motivation for Dependent Type By the Curry-Howard Isomorphism we view propositions (or theorems if true/inhabited) as types.

But take the type $\mathbb{N} \implies \mathbb{N} \implies \mathbb{N} $.

We have as witnesses to this type (i.e., proofs of this theorem) both

f x y = x + y
f x y = x * y

Yet they "attest to the validity" of two very different programs. Is this the motivation for increasing the expressivity of a type system, as we see with dependent types? How would the type signature above be spoken in English - "for all naturals, x and y, it is true for all naturals"...?

Actually, the motivation for introducing dependent types goes in the opposite direction! Curry had noticed that there was a direct correspondence between typed terms in the $SK$ calculus and proofs in (minimal implicational) propositional logic, but there was no programing language known to correspond in such a way to predicate logic.

Indeed, introducing $\Pi$ types are necessary to model propositions of the form $\forall x.P$, which clearly do not admit representation as a simple type $A\rightarrow B$. (Actually, one can imagine a "forgetful" translation, where $A$ is the domain of $x$, and $B$ is the domain of "proofs of $P$", and in this way one can construct something very similar to certain forms of realizability, but this is clearly not an isomorphism.)

In summary, there is an isomorphism between functions $\mathbb{N}\rightarrow\mathbb{N}\rightarrow\mathbb{N}$ in the simply typed $\lambda$-calculus and proofs of $N\Rightarrow N\Rightarrow N$ in minimal logic, in the context $N,N\Rightarrow N$.

It is clear, however, that most programing languages have more than the STLC to define functions, and that there is more reason to care about the operational behavior of programs than that of (most) proofs.

It makes sense to use dependent types to explore these distinctions, as well as more subtle notions of types to distinguish between "computationally relevant" things and "computationally irrelevant" ones (e.g. in Coq, the $\mathrm{Prop}$ vs $\mathrm{Set}$ distinction).

But these were not the original motivation for dependent types.

As a direct answer to your question, the "statement" $\mathbb{N}\Rightarrow\mathbb{N}\Rightarrow\mathbb{N}$ should be read in English as something like

  For every pair of natural numbers, there is a natural number.

And that's it! The fact that $\lambda x y. x+y$ and $\lambda x y. x\cdot y$ are two very computationally meaningful proofs of that statement does not factor at all into the statement as it stands.