Information spread in a social graph I'm interested in studying how information spreads in a social network. The basic problem is as follows.

Let's say we have a large graph of people, with directed edges connecting them. Let's also assume that based on the links, we can robustly identify influential people using something like Pagerank, etc.

Within this setting, suppose we want to inform the people in the network of some important piece of news, and that we can only do so by face-to-face contact with individual people. Also, we have limited resources -- suppose, because of limited resources, we can only have face-to-face contact with n people, out of a total of N people in the whole graph.

Question: how do we choose this subset of n people from the graph?

One easy solution is to use Pagerank and identify the most influential people. However, this doesn't exploit the idea of redundancy: if the top 3 most influential people according to Pagerank have let's say 80% of their neighbors in common, then we're essentially wasting resources by marketing to each of these three people.

Any insight on this problem would be helpful -- it seems that this situation would occur often enough that someone must have come up with a formal treatment with efficient algorithms, etc. I can think of a few ways to do this, but they involve inefficient traversals, etc.

This isn't a full answer, but a partial one since there's a lot of literature out there.

To answer the question, we need some model of how information spreads in a social network. You seem to maybe be assuming that everyone we talk to tells their friends, but their friends don't tell anyone (so we just want to pick the set that maximizes the number of neighbors). But many other dynamics are possible. Usually, one thinks of the problem as finding an initial set of nodes to "infect", and assuming that all nodes have some rule for when they get infected as a function of the number of infected neighbors. For example, you could have a threshold which says that I get infected as soon as I have 3 or more infected neighbors; or that $i$ has a probability $p_{ij}$ of getting infected from $j$ in the timestep after $j$ is first infected.

The original/classic paper for this problem is Maximizing the Spread of Influence Through a Social Network by Kempe, J. Kleinberg, and Tardos in 2003.1 If you search it on Google Scholar you'll see something like 1500 citations, so there is a lot of work in this area. You can see some on Jon Kleinberg's homepage under "Information Flow and Cascading Behavior in Networks"; he gave a survey talk on the area at this year's EC, but I don't know if the slides are available anywhere.

In 1, the authors show that, under several models of influence like those mentioned above, the "influence" of a set of vertices is a submodular function ; this allows greedy algorithms to find a set of initial nodes that gives a $1-1/e$ approximation to the best total influence. (However, solving the problem exactly is NP-hard.)

1 http://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf


Razborov-Smolensky polynomial argument on $\textrm{ACC}[q]$ where $q$ is a prime power It seems to be a folklore that we can "handle" $\textrm{ACC}[q]$ circuits not only for prime $q$ but prime power $q$.
For example, authors of this paper say that

  ... any constant
  depth circuit consisting of only $MOD_q$ gates, $q=p^k$
  , is
  equivalent to a constant degree polynomial over $\mathbb{Z}_p$ and
  therefore cannot compute the $AND$ function at all regardless
  of its size.

However, the original Razborov-Smolensky polynomial argument seems to consider only the case where $q$ is a prime.
How can we extend this to cover the case where $q$ is a prime power?
I'm a bit embarrassed that I was not able to follow the quote above, although it appears to give the answer already...

Or in brief:

  How to prove that $MOD_p \notin \mathrm{ACC}[q]$, where $(p,q)=1$ and $q$ is a prime power?

The result appears as Theorem 7 in the following paper by Smolensky:

Smolensky, Roman. "On representations by low-degree polynomials." Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. IEEE, 1993.
https://doi.org/10.1109/SFCS.1993.366874

The techniques in this paper are still algebraic but slightly different (and more general) than what people usually teach as the "Razborov-Smolensky polynomial argument".

Yuval Filmus has a nice set of notes on the above paper as well, with more exposition and details in some places:
http://www.cs.toronto.edu/~yuvalf/Smolensky.pdf

Update: Given that Smolensky's paper is quite terse, let me say a few words about how the implied proof proceeds. Since Filmus' notes, linked above, are fairly thorough, I won't try to be completely precise, but instead give the main technical ideas.

1) The connection between $ACC[q]$ and polynomials seems to indeed be the standard one. More precisely, if there is a constant-depth circuit computing $F$, then there exists a polynomial $P$ of polylogarithmic degree that approximates $F$, where the degree depends on the depth. Unless I'm mistaken, it is actually straightforward to see that this result works even when $q$ is a prime power. See for example section 4 in these lecture notes from MIT.

2) Then, the goal is to prove that such low-degree polynomials cannot approximate the $MOD_p$ function when $(p,q) = 1$, which shows that $MOD_p \notin ACC[q]$.

3) To prove this, Smolensky establishes in Theorem 4 a relationship between
 (i) the Hilbert function for the one-set of $F$, that is, the set $S = \{x \mid F(x) = 1\}$, and
 (ii) the ability of any low-degree polynomial $P$ to approximate $F$, where $F = MOD_p$ for this question.
Theorem 4 is proved in the paper (albeit in quite a terse way, hence the pointer to Filmus' notes).

4) The final step is to analyze the Hilbert function of the one-set of $F$. Smolensky refers to his proof for Parity for the "proof" of $MOD_p$ case. What actually needs to be shown is that the Hilbert function on $S$ is as large as possible, for all degrees less than $n/2$. In his words "...we proved that over $S$ there is no linear relation among monomials of degree smaller than $n/2$. Hence for $m < n/2$, $l^a_m(S)$ are as large as possible." The reason he omits the formal proof is that it is indeed the same as the case for parity, once you have the equation (8) that he provides.

I hope this makes sense, with the omitted details being medium-hard exercises.


How can I randomly generate bounded height spanning trees? For a project that I am working on, I should generate random spanning trees with bounded height.

Basically I do the following:
1) Generate a spanning tree
2) Check the feasibility, if feasible keep it.

1) Starting from a minimum spanning tree (Prim's or Kruskal's) I add a non-existing edge and this creates a cycle, I detect this cycle and remove one of the edges of this cycle that gives me a new spanning tree and I continue with this spanning tree by adding a new edge...

2) Suppose there is a special vertex $v_{center}$. For every vertex $v$, the length of the path from $v$ to $V_{center}$ should be less then $\delta$, where $\delta$ is a given parameter.

Is there any better(clever) way of doing this?

P.S. I forgot to specify the other constraint (my mistake): the degree of the vertices should also be bounded.

I was working on bounded-depth spanning trees a few years ago, they're really interesting.  Some of my colleagues came up with message passing algorithms that did a great job, but I can't find any of their code available.  We wrote it up in a physics style here:  http://iopscience.iop.org/1742-5468/2009/12/P12010/.  They've told me that it also works with degree bounds, although that didn't make it into the paper.

The approach you propose, which I would call Markov Chain Monte Carlo, is often a competitor to the message passing approach.  If you are interested in sampling approximately uniformly at random from the set of bounded-degree, bounded-depth spanning trees of a given graph, I suggest altering your approach to use "soft" bounds.  I.e. instead of rejecting an edge swap that makes the tree violate the depth bound, accept it, but with lower probability than a swap which does not violate the bound.  If you have a parameter that controls how much lower this probability is, you can make the constraint violating configurations less and less probable until you arrive at a feasible solution that is nearly uniformly random.

The big question is how long do you need to run the chain.  Since a spanning tree with degree at most 2 is a Hamiltonian path, you should expect any generic bound to be exponential in the size of the graph.  But maybe the graphs you are interested in are special in some way.


P-complete problems on trees This question is related to one of my previous questions, NP-hard problems on trees.

  I am looking for problems that are P-complete on trees.

A recent one, presented at ICALP is

Markus Lohrey, Christian Mathissen: Isomorphism of Regular Trees and Words. ICALP (2) 2011: 210-221

You will find the paper both on arxiv
and here.

Another example is  Mostowski epimorphism (see P-completeness and efficient parallelization by Satoru Miyano, and the paper by Dahlhaus):

Dahlhaus E, Is SETL a suitable language for parallel programming - a theoretical approach, Computer science logic, 1st Workshop, CSL ’87, Karlsruhe/FRG 1987, Lect. Notes Comput. Sci. 329, 56-63, 1988)

Instance: a directed acyclic graph $D = (V, A)$ satisfying the axiom of extensionality and two vertices $x_1, x_2 \in V$

Problem: Decide whether $M_D(x_1) = M_D(x_2)$, where $M_D$ is the Mostowski epimorphism for $D$.


How can I model this usage scenario mathematically? I want to create a fairly simple mathematical model that describes usage patterns and performance trade-offs in a system.

The system behaves as follows:

clients periodically issue multi-cast packets to a network of hosts
any host that receives the packet, responds with a unicast answer directly
the initiating host caches the responses for some given time period, then discards them
if the cache is full the next time a request is required, data is pulled from the cache not the network
packets are of a fixed size and always contain the same information
hosts are symmetic - any host can issue a request and respond to requests

I want to produce some simple mathematical models (and plotted X/Y graphs) that describe the trade-offs available given some changes to the above system:

What happens where you vary the amount of time a host caches responses? How much data does this save? How many calls to the network do you avoid? (clearly depends on activity)
Suppose responses are also multi-cast, and any host that overhears another client's request can cache all the responses it hears - thereby saving itself potentially making a network request - how would this affect the overall state of the system?
Now, this one gets a bit more complicated - each request-response cycle alters the state of one other host in the network, so the more activity the quicker caches become invalid. How do I model the trade off between the number of hosts, the rate of activity, the "dirtyness" of the caches (assuming hosts listen in to other's responses) and how this changes with cache validity period? Not sure where to begin.

I don't really know what sort of mathematical model I need, or how I construct it. Clearly it's easier to just vary two parameters, but particularly with the last one, I've got maybe four variables changing that I want to explore.

Help and advice appreciated.

I think you want a Petri net with transition guards and a global clock.  (Other formalisms would also work, but I'm going with this one because it relates to the discussion on your other question.)

Draw a graph -- vertices and directed edges -- where the vertices are your nodes, and the edges are the communication channels from one node to another.  It sounds as though there's an edge between every node, if all nodes are capable of broadcast, but perhaps I'm misreading.  In any case, the important thing is that you decorate each edge with a rule or set of rules, and the edge only "opens" when the rules are satisfied.  (These rules are called guard expressions.)

For example, to make "vary the amount of time a host caches responses" rigorous, you could make the rule for an edge, "if I receive a message, I wait 3 seconds according to the global clock before I pass it on."  I don't understand your dirty-cache issue well enough to offer anything yet, but I think the conceptual point you need first is this notion of enabling or disabling a transition according to the rules of the system.


What machine learning classifiers are the most parallelizeable? What machine learning classifiers are the most parallelizeable? If you had a difficult classification problem, limited time, but a decent LAN of computers to work with, what classifiers would you try?

Off hand it looks to me like some standard classifiers I know of stack up as follows but I could be totally wrong:

Random Forests - Very parallelizeable as long as each machine can hold all the data (i.e. can't divide up the training data per se, but otherwise parallelizeable).

Boosting - ?

Support Vector Machine - Not very parallelizable.

Decision trees - Can be divided up in part, but not very efficiently.

There have been efforts to parallelize most of the well-known classifiers, including boosting [a paper], SVM [a paper], and even decision trees [a paper].  Of course, by admitting parallelism, you sometimes lose out on other aspects, whether it be algorithm implementability, sample complexity, or other usual suspects.

From the theory end, the question is harder because when you talk about learning you have to think about the target function.  For example, we don't even know decision trees to be PAC-learnable, so if the target (as well as the method) is a decision tree, then we can't even learn it (yet) without introducing extra facets to the problem.  Boosting gets around that by assuming a weak learning condition, SVM a margin, etc. I think those assumptions transfer to the parallel case to give you PAC learning.

But as always, there's a big gap between the frontiers (and thereby concerns) of theory and of practice.   For example, in practice, it matters whether the parallelism is over cores or clusters.  One algorithm developed especially for practical use in large-data settings is VW, and it's starting to support parallelism.  You might be interested in the papers in the NIPS 2010 workshop on practical parallel learning.


Min Hamming distance of a given string from substrings of another string Let $U$ be a small finite set.
Consider the following problem:
Input: two strings $u \in U^k$ and $v\in U^n$ with $k \leq n$.
Output: a (contiguous) substring of $v$ of length $k$
with the minimum Hamming distance from $u$.
In other words I want to compute the following function:
$$f(u,v) = \arg\min_{j < n-k} d_H(u, v[j,j+k])$$
where $n = |v|$ and $k = |u|$.

What is the fastest algorithm for this problem?
Can this problem be solved in time $O(n\log n)$?

I think I can solve the problem if I have a data structure as follows:
Let $B = \{0, 1 \}$ and $k \le n$ be fixed numbers.
We want a data structure $D$ with the following properties:

Build: for $v \in B^n$ and $u \in B^k$, $D.Build(v, u)$ builds an instance of $D$ in time $O(n \log n)$.

Query: for $1 \le q \le n - k + 1$, $D.Query(q)$ returns $\langle u, v[q, q + k - 1]\rangle$ in time $O(\log n)$.

Is there a data structure with these properties?

$\langle \cdot , \cdot \rangle $ is the dot product and
$v[i, j]$ = $(v_i,\ldots, v_{j})$ is the subsequence of $v$ from $i$ to $j$.

Elaborating Paul's suggestion for a $O(n \log n)$-time algorithm:

Input: Let $u \in [m]^k$ and $v \in [m]^n$ with $k \leq n$, where $U=[m]=\{1,2,\cdots,m\}$.

Define polynomials $$p(x,y) = \sum_{i \in [n]} x^i y^{v_i} \qquad \text{and} \qquad q(x,y) = \sum_{j \in [k]} x^{k-j} y^{m-u_j}.$$
Compute the polynomial $$r(x,y) = p(x,y) q(x,y).$$ Then $$r(x,y) = \sum_{t,s} x^t y^s \left|\left\{ (i,j) \in [n]\times[k] : i+k-j=t \wedge v_i + m - u_j =s \right\}\right|. $$
In particular, for $k \leq t \leq n$, the coefficient of $x^{t} y^m$ in $r(x,y)$ is $$\left|\left\{ (i,j) \in [n]\times[k] : i=j+t-k \wedge v_i = u_j\right\}\right| = k-d_H(u,v[t-k+1,t]).$$
Thus, the coefficients of $r(x,y)$ provide a lookup table for $d_H(u,v[t-k+1,t])$ for $k \leq t \leq n$.
So, given the coefficients of $r(x,y)$, we can easily solve the problem by picking the $t$ such that $x^{t}y^m$ has the largest coefficient:

Output: $f(u,v)+k=\mathrm{arg}\max_{k \leq t \leq n} \mathrm{coefficient}_{r(x,y)}(x^{t}y^m)$

So how fast is this algorithm? I claim it can be implemented in $O(nm \log (nm))$ time (assuming arithmetic operations with $O(\log (nm))$ bits of precision take constant time) using the Fast Fourier Transform.

The core of the problem is computing $r(x,y)=p(x,y)q(x,y)$, where the degree of $p(x,y)$ is at most $n$ in $x$ and $m$ in $y$ and the degree of $q(x,y)$ is at most $k$ in $x$ and $m$ in $y$.

We can first reduce it to univariate polynomial multiplication by defining $$p'(z) = p(z^{m+1},z) \qquad \text{and} \qquad q'(z)=q(z^{m+1},z),$$ computing $r'(z)=p'(z)q'(z)$, and then extracting $r(x,y)$ from the identity $r'(z)=r(z^{m+1},z)$.

I won't go through the FFT algorithm (even though it's one of my favourite algorithms), but the general idea is:

Pick $\ell = O(nm)$ special points $w_1, \cdots, w_\ell \in \mathbb{C}$, namely $w_j=\exp(2\pi\sqrt{-1}j/\ell)$ and $\ell$ is a power of $2$ with $\ell > \mathrm{degree}(r'(z))=O(nm)$.
Evaluate $p'(w_j)$ and $q'(w_j)$ for all $j \in [\ell]$ in $O(\ell \log \ell)$-time using a divide and conquer algorithm.
Compute the values $r'(w_j)=p'(w_j)q'(w_j)$ for all $j$ in $O(\ell)$-time.
Interpolate the coefficients of $r'(z)$ from the values $r'(w_j)$ in $O(\ell \log \ell)$-time using essentially the same divide and conquer algorithm.

The observation that makes the divide and conquer algorithm work is that we can write $p'(z) = p'_\text{even}(z^2) + z \cdot p'_\text{odd}(z^2)$, where $p'_\text{even}$ and $p'_\text{odd}$ have half the degree of $p'$. It then suffices to recursively evaluate $p'_\text{even}(w_{2j})$ and $p'_\text{odd}(w_{2j})$ for $j \in [\ell/2]$.


Boolean as subtype of integer In languages oriented towards systems programming, digital logic and hardware design, it's common to treat boolean as a subtype of integer. In languages oriented towards mathematics and type theory, it's more usual to treat them as disjoint types.

Being from more of a systems programming background, it has always seemed to me appropriate to take the former approach. I would have thought it appropriate even from a mathematical viewpoint, since we already have a hierarchy of numeric types (natural numbers are a subtype of integer which is a subtype of rational etc.) so it would fit neatly at the start of that hierarchy; but then I'm not a real mathematician, so I may be missing something.

Apart from a little bit of extra error checking (catching the mistake if you pass a boolean to a function expecting an integer and you didn't mean to), is there any advantage to having them be disjoint types?

If you only think of Booleans as 0 and 1, then it is natural to include them as subtypes of natural numbers and integers. But as soon as you start applying operations to them, then things start to fall apart.

Consider what happens when you define the + operation on Booleans. You have two choices:

Make + the same as OR, so 1+1=1. But then you have the problem that + on Booleans is no longer the same as + on Integers, which it should be.  More precisely, we have the following $(Integer)1_{Bool}+ (Integer)1_{Bool}\neq (Integer)(1_{Bool}+1_{Bool})$, where $1_{Bool}$ is true and $(Integer)\_$ is performing a cast from Bools to Integers. This means that there is a problem with coherence in the subtyping relation is we make this choice.
The second choice is to define + on Booleans so that 1+1=2. But now the operation takes you out of the world of Booleans. Semantically, this is not problematic ($\sqrt{-1}$ takes you out of the world of Real numbers), but it does suggest that you do not gain much by treating Booleans as numbers.

Generally, the way Booleans/Integers are treated in languages like C is that Integers can be used in places where Booleans are expected, which does not really follow the usual subtyping rules.

Ultimately, the operations you apply to Booleans are not the same as the ones you apply to Naturals and Integers, so, from the perspective of coherence, you should not really consider them to be related by subtyping.

Edit:
A third alternative, suggested by Peter Taylor in comments, is to make + be XOR. This results in the subtype relation boolean < short < integer < long, where + is addition-modulo-overflow. That's fairly natural, programmatically.


Questions regarding SETH I read about the strong exponential time hypothesis, which states (as far as I understand) that SAT problem cannot be solved in running time $O(2^{\epsilon n})$ for any $\epsilon < 1$, where $n$ is the number of variables in the formula.

However, for other NPC problems, it is known that such algorithms exist (for example, Hamiltonian cycle).

My question is as follows: it is possible to create a polynomial reduction from Hamiltonian cycle to SAT - proving that Hamiltonian cycle is "harder" than SAT (this is how we were proven that Hamiltonian cycle is NPC). This allegedly imply that when given a SAT instance, I can use the reduction and the Hamiltonian cycle algorithm to achieve exponential algorithm with smaller exponent, in contrast to SETH. Clearly I miss something here.

Regardless of this question:  are there any current research efforts towards progress in this problem?

The subtlety comes in where we introduce the notion of "harder". The reduction showing that SAT can be reduced to Hamiltonian Cycle shows that the latter is "harder" up to polynomial factors. In doing the reduction, we may very well increase the variable $n$ in question substantially (by some polynomial). And the canonical reductions do blow it up quite substantially.

So what's the upshot? Suppose that the reduction from a SAT instance with $t$ variables yields a HamCycle instance with $n = p(t)$ vertices for some polynomial $p$. Running some $O(2^{\epsilon n})$ time algorithm on this HamCycle instance takes time $O(2^{\epsilon p(t)})$. If $p(t) \ll t/\epsilon$, you just broke SETH. But in general, $p$ may be larger than that (often not even linear), in which case your reduction takes longer than the naive brute force approach.

Some recent papers actually work asking the same line of reasoning that you do to establish SETH hardness. For example, consider the graph diameter problem, where we are asked to determine how far apart the two furthest nodes on a graph lie (that is, we're asked to compute the maximum over all (u,v) pairs the length of the shortest path between u and v). Roditty and Williams showed that even in the unweighted case, where all edge lengths are 1, the problem is difficult to solve in time $O(n^{1+\epsilon})$ (using your notation with $\epsilon<1$). The way they do this, roughly, is by finding an exponential-time reduction from SAT to GraphDiameter that blows up the number of vertices from $t$ to $O(2^{t/2})$. In this new giant instance, the diameter is 3 if the instance is satisfiable, 2 if not. Thus, if they can solve GraphDiameter in time $O(n^{1+\epsilon})$ (and if the original exponential time reduction is fast enough, which it is), then they can solve SAT with $t$ variables in time $O((2^{t/2})^{1+\epsilon}) = O(2^{\frac{1+\epsilon}{2}t}) = O(2^{\epsilon't})$ for $\epsilon'<1$, breaking SETH. In reality, their reduction works through dominating set first, but the key ideas remain the same.


How to go about finding the most "complex" function? Intro

Hi, I'm a hobbyist, with no formal education, tinkering with SAT solving and boolean algebra minimization. So expect bad terminology. I hope you will forgive me I'm asking a wrong question in a wrong place. I'll give it a shot.

Question

Essentially I'm trying to find the most "complex"/"chaotic"/"highest entropy" truth tables of some sizes (>32 bits / >5 vars). I'm asking if it would be possible to find such functions without enumeration and how to go about getting there?

Complex in what context? Complexity would mean the size of some representation other than the truth table itself. So let's say the complexity of a function is the size of the function's optimal CNF/DNF or NNF representation with "temp vars"(to avoid the exponential growth in certain cases like XORs).

Number of clauses in case of CNF/DNF, number of temp vars in case of NNF. Don't know if those can be called CNF and NNF anymore but I hope you get what I mean.

I'm more used to a NNF-like representation without ORs. Where (a+b).(a'+b') would be described in the following way:

0 = a'.b'
1 = a.b
2 = 0'.1'

Application / Why I'm asking?

I'm looking for a way to find and analyse cases (preferably similar) where the optimal representation in the And-inverter graph structure would start to grow exponentially as the size of the truth table increases and it would get way bigger than the truth table itself. Just like it happens with XORs in CNF/DNF structure.

Pick one at random.

If it is random, then there is no way to compress the representation. You have to store the entire truth table.

http://en.wikipedia.org/wiki/Kolmogorov_complexity


Complexity of the problem of words with fewest distinct letters accepted by a finite automaton Given a finite (deterministic or nondeterministic, I don't think this has much importance) automaton A and a threshold n, does A accept a word containing at most n distinct letters?

(By k different letters I mean that aabaa has two distinct letters, a and b.)

I showed this problem to be NP-complete, but my reduction produces automata in which the same letter appears on many transitions.

I'm rather interested in the cases where each letter appears at most k times in A, where k is a fixed parameter. Is the problem still NP-complete?

For k=1 the problem is just shortest path, so is P. For k=2 I've neither been able to show membership in P nor to find a proof of NP-hardness.

Any idea, at least for k=2 ?

It is NP-hard for $k=3$.
The reduction is from 3-SAT-(2,2), which means that every clause contains $3$ literals and every literal occurs in at most $2$ clauses.

First of all, for simplicity, let's admit honestly that this problem has not much to do with automata.
Your problem is equivalent to the following:
Given an edge-colored digraph where each color occurs at most $k$ times, is there an $st$ path that uses at most $n$ colors?

For the reduction, the graph starts from $s$ with a path of length $n$, where $n$ is the number of variables of the 3-SAT-(2,2) input.
Each edge of this path is present twice, and all $2n$ edges have a different color.
The colors used when traversing this path correspond to which variables are true.
After this path, there is another path whose length is the number of clauses.
Here every edge is thrice, where the colors correspond to the literals of the clause.
We can get to the end of this path using no extra colors (thus in total $n$) if and only if the 3-SAT-(2,2) input is satisfiable.


2FA state complexity of k-Clique? In simple form:

  Can a two-way finite automaton recognize $v$-vertex graphs that contain a triangle with $o(v^3)$ states?

Details

Of interest here are $v$-vertex graphs encoded using a sequence of edges, each edge being a pair of distinct vertices from $\{0,1,\dots,v-1\}$.

Suppose $(M_v)$ is a sequence of two-way finite automata (deterministic or nondeterministic), such that $M_v$ recognizes $k$-Clique on $v$-vertex input graphs and has $s(v)$ states.
A general form of the question is then:
Is $s(v) = \Omega(v^k)$?

If $k = k(v) = \omega(1)$ and $s(v) \ge v^{k(v)}$ for infinitely many $v$, then NL ≠ NP.
Less ambitiously, I am therefore stipulating that $k$ is fixed, and the $k=3$ case is the first nontrivial one.

Background

A two-way finite automaton (2FA) is a Turing machine which has no workspace, only a fixed number of internal states, but can move its read-only input head back and forth.
In contrast, the usual kind of finite automaton (1FA) moves its read-only input head in one direction only.
Finite automata can be deterministic (DFA) or nondeterministic (NFA), as well as having one-way or two-way access to their input.

A graph property $Q$ is a subset of graphs.
Let $Q_v$ denote the $v$-vertex graphs with property $Q$.
For every graph property $Q$, the language $Q_v$ can be recognized by a 1DFA with at most $2^{v(v-1)/2}$ states, by using a state for every possible graph and labelling them according to $Q$, and transitions between states labelled by edges.
$Q_v$ is therefore a regular language for any property $Q$.
By the Myhill-Nerode theorem there is then a unique up to isomorphism smallest 1DFA that recognizes $Q_v$.
If this has $2^{s(v)}$ states, then standard blowup bounds yield that a 2FA recognizing $Q_v$ has at least $s(v)^{\Omega(1)}$ states.
So this approach via standard blowup bounds only yields at most a quadratic in $v$ lower bound on the number of states in a 2FA for any $Q_v$ (even when $Q$ is hard or undecidable).

$k$-Clique is the graph property of containing a complete $k$-vertex subgraph.
Recognizing $k$-Clique$_v$ can be done by a 1NFA that first nondeterministically chooses one of $\binom{v}{k}$ different potential $k$-cliques to look for, and then scans the input once, looking for each of the required edges to confirm the clique, and keeping track of these edges using $2^{k(k-1)/2}$ states for each of the different potential cliques.
Such a 1NFA has $\binom{v}{k}2^{k(k-1)/2} = (c_v 2^{(k-1)/2}/k)^k.v^k$ states, where $1 \le c_v \le e$.
When $k$ is fixed, this is $\Theta(v^k)$ states.
Allowing two-way access to the input potentially allows an improvement over this one-way bound.
The question is then asking for $k=3$ whether a 2FA can do better than this 1FA upper bound.

Addendum (2017-04-16): see also a related question for deterministic time and a nice answer covering the best known algorithms.
My question focuses on nonuniform nondeterministic space.
In this context the reduction to matrix multiplication used by the time-efficient algorithms is worse than the brute-force approach.

It seems to me that triangles can be done by a 2FA $A$ with $O(n^2)$ state (n being the number of vertices).

For $k=3$ the idea is as follows:

In phase 1, $A$ chooses some edge $(i,j)$ and stores $(phase 1,i,j)$ in its state
In phase 2 it moves to some edge of the form $(i,m)$ or $(m,i)$ and assumes a state of the form $(phase 2,j,m)$
In phase 3, it checks that there is some edge $(j,m)$ or $(m,j)$ and assume an accepting state if it finds one.

This can actually almost be done in a left to right fashion (then $A$ might nondeterministically decide to go first for $(j,m)$ or $(m,j)$ in phase 2). However, if the 2nd edge comes in the form $(m,i)$, $A$ needs to first read $i$ and then $m$, i.e., a single left-step is needed here.

This should result in automata with $O(n^{k-1})$ states for $k$-Clique for $k>3$ by first guessing a set $S$ of size $k-3$ and testing, that he nodes of $S$ are pairwise connected by edges and, for each of  i,j,m in the above, checking that they have edges to all nodes in $S$.


Unique Identifier Creation and Invalidation A colleague of mine recently interviewed for a software engineering job, and he was given a problem regarding unique identifier creation and testing for validation.

So, the problem is: if a generated  unique-identifier, let's say an order id provided online by an ecommerce site, is provided to a customer, and when the customer attempts to lookup the order, they have inadvertently transposed two characters, how to quickly test that the id is invalid, and how to create an id such that the transposition of two characters does not represent another valid id.

I want to know what class of problem is this (not in the complexity sense but categorically) and what are general methods that attempt to solve it. Looking for variations on the theme of unique identifier and invalidation on google has not produced interesting results. I am hoping someone here might lead me in the right direction to learn more about this kind of problem.

I hope I have found the right forum for posing the question, and apologies if I have not.

Looks like some Data integrity check stuff.
For example adding something like CRC16 (4hex digits) will allow filter ID with typos


Minimum number of transpositions to sort a list In trying to devise my own sorting algorithm, I'm looking for the optimal benchmark to which I can compare it.  For an unsorted ordering of elements A and a sorted ordering B, what is an efficient way to calculate the optimal number of transpositions to get from A to B ?

A transposition is defined as switching the position of 2 elements in the list, so for instance

1 2 4 3

has one transposition (transposition 4 and 3) to make it

1 2 3 4

Something like

1 7 2 5 9 6

requires 4 transpositions (7, 2), (7, 6), (6,5), (9, 7)

Update (9/7/11): question changed to use "transposition" instead of "swaps" to refer to non-adjacent exchanges.

If you're only dealing with permutations of $n$ elements, then you will need exactly $n-c(\pi)$ swaps, where $c(\pi)$ is the number of cycles in the disjoint cycle decomposition of $\pi$. Since this distance is bi-invariant, transforming $\pi$ into $\sigma$ (or $A$ into $B$, or conversely) requires $n-c(\sigma^{-1}\circ\pi)$ such moves.


Support Vector Machines and privacy-preservation suppose we have data matrix A m-by-n (m observations and n features) which I want to Apply SVM on it achieving privacy (Privacy-Preserving SVM)

the questions are:-

1 - Is applying kernel trick considered as Privacy-Preserving SVM?

2 - Is converting the data matrix into D = A.Transpose[A] and learning from *D m-by-m * considered as Applying a kernel?

thnq .. :)

Before giving some detail, I'll briefly say: regarding (1), kernel trick is basically the worst thing for privacy, and regarding (2), you have replaced each vector with a vector of kernel products (via the linear kernel), and this is non-equivalent to replacing inner products with kernel products inside the algorithm.

Some background on (1) for those who asked.  Suppose you want to learn a linear predictor; among those consistent with the data (i.e. correct on all examples), which do you choose?  The SVM solution is to pick the one which maximizes the minimum distance to any example (maximizes the 'margin').  In the case that no consistent predictor exists, small penalization is assigned to margin violations (learning the best linear predictor, in the presence of noise, is NP-hard).

now say your data is a set of records for some group of people (for instance, each "point" is a vector of medical parameters for some person).  You want to release a predictor (say, a website where someone can put in some info and see if they have some disease or not), but don't want anyone to be able to reconstruct properties of the people in your data set.  Here's an example; let's say I know someone is the only person in some remote part of saskatchewan, and I want to see if they were used to learn this predictor.  And say, one of the attributes in the web form is location.  For privacy ignorant algorithms, I can see how sensitive the algorithm is to queries with this personal data, and infer things about the person in question (for instance, if saying I'm from remote-part-of-saskatchewan but varying all other parameters always says I have the disease (and the answer is sensitive to location), that means that guy has the disease).  Said another way, if I know some unique characteristics of a person, I can see how the algorithm reacts to them in order to determine other properties of that person.

Anyway, here's why the kernel trick is the worst thing for this.  The kernel trick just means you store your predictor as
$$
p(x) = \sum_{i=1}^m a_ik(v_i, x),
$$
where $\{v_i\}_1^m$ are your support vectors.  This means the predictor for any kernelized linear classifier (not just SVM) will explicitly store a set of records!  Therefore, if you manage to plug in a support vector for $x$, you can
expect it to strongly affect the value of the predictor.  Going back to the remote-part-of-saskatchewan example, suppose the kernel is gaussian, and you fix all other parameters, and see the effect of the saskatchewan input.  Since distances are all huge in high dimension, that means, if the guy is in the dataset, the predictor value will be strongly affected by matching the remote-part-of-saskatchewan fields or not.  Thinking geometrically, each support vector plops a gaussian in the space (color them white or black based on their label), and if this guy is really the only person in that remote part of saskatchewan (and if he was a support vector), that means his gaussian will basically entirely control the value of the predictor.

EDIT. I should say that research in privacy preserving learning is all about taking privacy-ignorant algorithms and making them output privacy-secure predictors.  There are definitely strategies to make kernelized algorithms more privacy preserving--for instance, don't let any region of the space be "covered" by just one support vector (some sort of smoothness condition, i.e. how much the predictor is affected by removing or adding in this example); this in turn usually means.. have TONS of support vectors.  Another strategy is to inject perturbations in places, but notice this is delicate--if you just perturb this saskatchewan record, it is still basically the only gaussian in that region of space, so you've done nothing.  Anyway all I am saying is that kernelized algorithms are a difficult starting point for privacy preservation.  (and the "have TONS of support vectors parts" starts to mitigate the benefits of the kernel trick..)

About (2).. let $A$ contain all points as columns; a linear predictor can be written as
$$
p(x) = x^\top Av
$$
where $v$ is a vector of weights (in the linear case, you can "compress" this and just keep weights $w=Av$ around).  (to be explicit, you also check the predicate $p(x)\geq 0$.)  In your case, you have replaced $A$ with $AA^\top$, and also you must map any input vector $x$ to $Ax$, thus your predictor is
$$
p'(Ax) = x^\top A^\top AA^\top v'.
$$
For general matrices $A$, it is possible that some choice $v$ does not have a choice $v'$ which makes these equivalent...... thus, this is not the same as simply "kernelizing" the algorithm.

That said, it is reasonable to replace your data with kernel products in this way, but that is a feature selection issue; i've attempted to discuss the math part...........


Partitioning a square for optimal queries I have a square plate of size 1x1, full of lots of skittles. I want to eat all of the skittles, but the only way I can get the skittles is through these two oracles:

$f(x, y, r)$ tells me how many skittles are in the circle of radius $r$ centered about the point $(x,y)$ on my plate

$q(x, y, r)$ gives me all of the skittles that are in the circle of radius $r$ centered about the point $(x,y)$ on my plate

However, my plate is very big, and my oracles are very small. So the $r$ given to $f$ and $q$ must be less than or equal to a given value $R$.

Oracles don't come free these days: I have to pay a cost of 1 each time I call $f$. Each time I call $q(x, y, r)$, I must pay a cost of $f(x, y, r)/P$: 1 for each $P$ skittles that my oracle brings to me (rounded up). The $P$ is an input to this problem. Then those skittles are eaten.

There are $N$ skittles on my plate. What is a strategy that doesn't cost very much to eat all of my skittles, in terms of $N, R$, and $P$?

I'm curious about two cases:

If an adversary is placing skittles, what is the most they can make me pay?
If all the skittles are each independently placed according to a uniform distribution over the entire plate, what is a strategy that does "sorta well", and what is the expected amount I would need to pay?

A good idea seems to be to use nonoverlapping circles in the densest circle packing in 2d. Please check the corresponding Wiki-page: https://en.wikipedia.org/wiki/Circle_packing. This way you reach up to $C = 0.907$ coverage. Assuming the scittles are uniformly distributed and $N \gg \frac{1}{S_c}$, where $S_c$ is the surface of the cricles you use, we may estimate that you'll have to pay $\frac{CN\#circles}{P} = C^2N/S_cP$ for fetching and roughly $\#circles = C/S_c$ for looking in thustly covered area. We may cover the gaps, which cover about $1-C$ of the square, by correspondingly smaller cirlces again, the cost of looking should be just as before. The cost of fetching is hard to estimate, without delving into geometry to much at this point, but i guess it may be roughly $(1-C)N/P$. Also, you may terminate one you reach $N$.

A smart adversary would start placing the scittles in the gaps. I assume it's a good idea to pick a random reference for the lattice of circle placing. Also you could randomly pick the areas to  check for scittles from the main lattice (covering $C$) and from the minor lattice (covering $1-C$).

Now we are stuck with the decission which radius to pick in $[0,R]$. I assume as large as possible under the placed constrains makes sense. There is probably space for optimization by choosing some radius $r$ so that your main lattice has little overflow over your plate.

Alternatively you may use the densest packing, but with circles overlapping. This way all the gaps vanish and you skip the cost for lookups on the secondary lattice.

Hope this input helps you somewhat.


Constructing subfields of a finite field Suppose we have a finite field $\mathbb{F}_{p^n} = \frac{\mathbb{F}_{p}[x]}{<f(x)>}$. I want a deterministic polynomial algorithm to compute all subfields of this field. I think we can do something using linear algebra.

Can someone suggest a reference of this problem? I am unable to find it in standard texts.

This problem is in BPP.

All finite fields of order $p^n$ are identical, and there is a generator element $g$ whose multiplicative order is $p^n-1$, so every non-zero field element is expressible as $g^r$ for some $r$.

Now, there is a subfield of order $p^j$ iff $j$ divides $n$, and this subfield has a generator element $h$ whose multiplicative order is $p^j-1$.

This means that we can take $h = g^{(p^n-1)/(p^j-1)}$.

What this means, in effect, is that once we have an algorithm for finding a generator of the finite field, everything else is straightforward.

The easy way to find a generator is to pick a field element at random, and test whether it is a generator. The expected number of elements you need to test is indeed polynomial. Doing this test efficiently might require knowing the prime factors of $n$. (But if you can write down all the coefficients of $f(x)$ without using sparse polynomial notation, then $n$ is small and this is easy.)

But you asked for a deterministic algorithm and not a randomized one.
A quick search shows that there is no known efficient deterministic algorithm for finding a generator. See this question on math.SE.

So the question is: can you find a deterministic algorithm for finding the subfields which doesn't actually compute a generator for the subfields? (Because that's probably as hard as finding a generator for the field itself, and so is an open problem.)

Much of this is explained in Wikipedia.


NP-hard problem on planar unit disk graph I am curious to know whether there are problems which are np-hard even on planar unit disk graphs.

A unit disk graph is the intersection graph of a collection of unit disks in the plane, where we draw a vertex for each unit disk.

Maybe some problem on a accordingly restricted grid graph?

alex

Did you try doing a search for "planar unit disk graphs"? According to this paper the problem of finding the largest possible induced matching is NP-complete for planar unit disk graphs, according to this paper so is the minimum connected dominating set, and according to this paper so is the maximum number of disjoint dominating sets.


Lower bound proof for compressive sensing (Gel'fand widths)? Let $x \in \mathbb{R}^n$ have $k$ non-zero entries. The main insight of compressive sensing is that there exist $m\times n$ matrices $A$ with $m = O(k \log n/k)$ such that any $x$ can be recovered from $Ax$ in polynomial time.

A little thought shows that $Ax$ must have at least $\log \binom{n}{k} = \Theta(k \log n/k)$ bits. I believe a stronger statement is true as well, namely, that we must have $m =\Omega(k \log n/k)$ measurements as well.

I know the lower bound on $m$ has something to do with Gel'fand widths, but am having a hard time finding a resource that lays out the argument explicitly. Either pointers to write-ups or a rough summary of the argument would be helpful.

$m = \Omega(k \log(n/k))$ is a lower bound for any compressive sensing scheme, not just $\ell_1$-minimization using RIP guarantees on the measurement matrix. In fact, the recovery algorithm need not be polynomial time, and the measurement matrix may be adaptive (in the sense that the $i$'th row of the matrix can depend on the inner product of the input vector with rows $1$ through $i-1$).

Let me sketch the argument for non-adaptive measurements. If $K$ is a subset of $\ell_p^n$, then the Gelfand $m$-width of $K$ is defined to be:
$$d^m(K) = \inf_{A: \mathbb{R}^{m \times n}} \sup_{x \in K \cap \ker(A)} \|x\|_p$$
Define the compressive $m$-width as:
$$E^m(K) = \inf_{A: \mathbb{R}^{m \times n}, \Delta: \mathbb{R}^m \to \mathbb{R}^n} \sup_{x \in K}\|x - \Delta(A x)\|_p $$
Note that $\Delta$, the reconstruction procedure, can be arbitrary.

Lemma 1: If $K$ is symmetric ($K = -K$), then $E^m(K) \geq d^m(K)$.

Proof: Take some arbitrary matrix $A \in \mathbb{R}^{m \times n}$ and function $\Delta: \mathbb{R}^m \to \mathbb{R}^n$. By definition, $d^m(K) \leq \sup_{x \in K \cap \ker(A)} \|x\|$. On the other hand, for any $x \in K \cap \ker(A)$:
$$\|x\| \leq \frac12 \|x-\Delta(0)\| + \frac12 \|-x-\Delta(0)\| \leq \sup_{x \in K} \|x-\Delta(Ax)\|$$
So, we have $d^m(K) \leq \sup_{x \in K \cap \ker(A)} \|x\| \leq E^m(K)$. $\blacksquare$

Now, for the connection with compressive sensing, suppose we have an integer $k \geq 1$,  matrix $A \in \mathbb{R}^{m \times n}$ and a function $\Delta: \mathbb{R}^m \to \mathbb{R}^n$ such that for all $x \in \mathbb{R}^n$:
$$\|x - \Delta(Ax)\|_p \leq \frac{C}{k^{1-1/p}} \min_{k\text{-sparse } z} \|x - z\|_1$$
where $C$ is a constant. Let $B_1$ be the unit $\ell_1$-ball, viewed as a subset of $\ell_p^n$, for $1< p\leq 2$. We clearly have that:
$$E^m(B_1) \leq  \frac{C}{k^{1-1/p}} \sup_{x: \|x\|_1 \leq 1} \min_{k\text{-sparse } z} \|x - z\|_1 \leq \frac{C}{k^{1-1/p}}$$

But we also have a lower bound for the Gelfand width of $\ell_1$-balls.

Theorem 2: There exists a constant $c_1$ such that: $$d^m(B_1) \geq c_1 \min\left(1, \frac{\log(n/m)}{m}\right)^{1-1/p}$$

Combining with the above, we have that:
$$c' \min\left(1, \frac{\log(n/m)}{m}\right) \leq \frac1k$$
Thus, if $k$ is large enough, this gives the lower bound, $m = \Omega(k \log(n/k))$.

The proof can be extended without much difficulty to the adaptive setting. The assumption that $k$ is sufficiently large can also be removed.

I learnt of this argument from Chapter 10 of Foucart and Rauhut's recent book, "A Mathematical Introduction to Compressive Sensing". It's due to Cohen, Dahmen and Davenport ("Compressed sensing and best k-term approximation", 2009). Theorem 2 is due to Garnaev and Gluskin ("On widths of the Euclidean ball", 1984). Foucart, Pajor, Rauhut and Ullrich ("The Gelfand widths of $\ell_p$-balls for $0<p\leq 1$", 2010) give a relatively simple proof of it. In fact, this latter proof is based on a lower bound for the number of measurements needed for exact-recovery of $k$-sparse vectors.


Cycle cover for structured graph Consider the undirected graph $G=(V,E)$ example below.
More precisely, the vertices in $V$ are labelled with $(x,y)$-coordinates and there is an edge between every vertices sharing the same $x$ and $y$ (not shown on the figure). For instance: $(1,1)-(1,2)$, $(1,1)-(1,3)$ and $(1,1)-(1,4)$

First question: Does this graph structure has a name?
Note that the sketch is only an example and can be generalized, but I am not sure whether the generalized graphs would still be planar.

(1,1) --- (1,2) --- (1,3) --- (1,4)
  |         |         |         |
  |         |         |         |
  |         |         |         |
(2,1) --- (2,2)       |         |
  |         |         |         |
  |         |         |         |
  |         |         |         |
(3,1) --- (3,2) --- (3,3) --- (3,4)
  |         |
  |         |
  |         |
(4,1) --- (4,2)

Second question: I'm interested in finding short-cycle covers of this graph (length 4 or 6 typically). Two solutions of the problem for cycles of length 4 would be:

(1,1)-(1,2)-(2,1)-(2,2)
(3,1)-(3,2)-(4,1)-(4,2)
(1,3)-(1,4)-(3,3)-(3,4)

and

(1,1)-(1,3)-(3,1)-(3,3)
(1,2)-(1,4)-(3,2)-(3,4)
(2,1)-(2,2)-(4,1)-(4,2)

And one solution for cycles of length 6:

(1,1)-(2,1)-(2,2)-(3,2)-(3,4)-(1,4)
(1,2)-(1,3)-(3,3)-(3,1)-(4,1)-(4,2)

I know that the general case for 3-cycle cover is NP-complete, but does the special structure of this graph enables to get a simple algorithm solving the cycle cover problem?

Re your first question, re whether this type of graph has a name: it is the line graph of a bipartite graph (the bipartite graph that has a vertex for each nonempty row or column and an edge for each point). Line graphs of bipartite graphs are an important subclass of the perfect graphs. They are generally not planar (e.g. if you have five points on the same row or column you get a $K_5$ subgraph).


Human intelligence and algorithms Have there been any studies to determine whether human intelligence can outperform algorithms (i.e. test whether the No Free Lunch Theorem applies to human intelligence)?

Along the same lines, has anyone developed a technical method to take advantage of any unique, supra-computational properties of human intelligence?

Check out Luis Von Ahn at CMU. He is the original Captcha guy. You will find enough videos like this  google techtalk on the subject of Human Computation.


Why it's impossible to declare an induction principle for Church numerals Imagine, we defined natural numbers in dependently typed lambda calculus as Church numerals. They might be defined in the following way:

SimpleNat = (R : Set) → R → (R → R) → R

zero : SimpleNat
zero = λ R z _ → z

suc : SimpleNat → SimpleNat
suc sn = λ R z s → s (sn R z s)

SimpleNatRec : (R : Set) → R → (R → R) → SimpleNat → R
SimpleNatRec R z s sn = sn R z s

However, it seems that we can't define Church numerals with the following type of Induction principle:

NatInd : (C : Nat -> Set) -> (C zero) -> ((n : Nat) -> C n -> C (suc n)) -> (n : Nat) -> (C n)

Why is it so? How can I prove this? It seems that the problem is with defining a type for Nat which becomes recursive. Is it possible to amend lambda calculus to allow this?

The question you are asking is interesting and known. You are using the so-called impredicative encoding of the natural numbers. Let me explain a bit of the background.

Given a type constructor $T : \mathsf{Type} \to \mathsf{Type}$, we might be interested in the "minimal" type $A$ satisfying $A \cong T(A)$. In terms of category theory $T$ is a functor and $A$ is the initial $T$-algebra. For example, if $T(X) = 1 + X$ then $A$ corresponds to the natural numbers. If $T(X) = 1 + X \times X$ then $A$ is the type of finite binary trees.

An idea with long history is that the initial $T$-algebra is the type
$$A \mathrel{{:}{=}} \prod_{X : \mathsf{Type}} (T(X) \to X) \to X.$$
(You are using Agda notation for dependent products, but I am using a more traditional mathematical notation.) Why should this be? Well, $A$ essentially encodes the recursion principle for the initial $T$-algebra: given any $T$-algebra $Y$ with a structure morphism $f : T(Y) \to Y$, we get an algebra homomorphism $\phi : A \to Y$ by
$$\phi(a) = a \, Y \, f.$$
So we see that $A$ is weakly initial for sure. For it to be initial we would have to know that $\phi$ is unique as well. This is not true without further assumptions, but the details are technical and nasty and require reading some background material. For instance, if we can show a satisfactory parametricty theorem then we win, but there are also other methods (such as massaging the definition of $A$ and assuming the $K$-axiom and function extensionality).

Let us apply the above to $T(X) = 1 + X$:
$$\mathsf{Nat} =
  \prod_{X : \mathsf{Type}} ((1 + X) \to X) \to X =
  \prod_{X : \mathsf{Type}} (X \times (X \to X)) \to X =
  \prod_{X : \mathsf{Type}} X \to (X \to X) \to X.
$$
We got Church numerals! And we also understand now that we will get a recursion principle for free, because the Church numerals are the recursion principle for numbers, but we will not get induction without parametricity or a similar device.

The tehcnical answer to your question is this: there exist models of type theory in which the type SimpleNat contains exotic elements that do not correspond to numerals, and moreover, these elements break the induction principle. The type SimpleNat in these models is too big and is only a weak initial algebra.


Which model of computation is "the best"? In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and analyse algorithms.

As a result, we have dozen of algorithms for, e.g., SORT-problem for different models of computation. Unfortunately, we even cannot be sure that an implementation of an algorithm with running time O(n) in a word RAM with bit-vector operations allowed will run faster than an an implementation of an algorithm with running time O(n⋅logn) in a word RAM (I am talking about "good" implementations only, of course).

So, I want to understand which of existing models is "the best" for designing algorithms and I am looking for an up-to-date and detailed survey on models of computation, which gives pros and cons of models and their closeness to reality.

I have always considered the standard Word RAM model to be "the best" in your sense. Everybody who learned to program in a language like C (or any loose equivalents like Java, etc) has precisely this model in mind when they think of a computer.

Of course, you sometimes need generalizations depending on the regimes in which you work. The external memory model is an important one to keep in mind. It applies not only when you work with disks, but also in understanding (forcing you to care about) cache. Of course, treating it too seriously can also lead to nonsensical results, since the pure external memory model doesn't count computation. Another generalization of the Word RAM is to parallelism, but there we are all a bit confused at the moment :)

An algorithm with an $O(n)$ running time will certainly run faster than one with $O(n \lg n)$ running time. It is a mathematical fact that the former is faster for large $n$ :) Your problem size may simply not be large enough for this to matter. Since you bring up sorting, let me assure you it will be very hard to beat radix sort with a comparison-based algorithm for reasonable $n$.

A final remark on algorithms and "reality": always keep in mind what you're trying to achieve. When we work in algorithms, we are trying to solve the hardest problems out there (e.g. SAT on 50 variables, or sorting a billion numbers). If you're trying to sort 200 numbers or solve SAT on 20 variables, you don't need any fancy algorithm. That's why most algorithms in reality are kind of trivial. This doesn't say anything bad about algorithmic research — we just happen to be interested in that unusual 1/1000 of the real problems that happen to be hard...


Lower Bound on the difference between uniform and prefix-free complexity The uniform Kolmogorov complexity (also known as decision complexity) of a string $\sigma$ is defined as follows: let $\phi: 2^{<\omega} \times \mathbb{N} \rightarrow {0,1}$ be a partial computable function. A string $\tau$ is called a description of $\sigma$ relative to $\phi$ if $\phi(\tau,i) = \sigma_i$ for $i = 1 \cdots l(\sigma)$, where $l(\sigma)$ denotes the length of $\sigma$. The uniform complexity $Ku(\sigma)$ of $\sigma$ is defined as the length of the shortest description of $\sigma$ relative to a universal machine.

It is clear that $Ku(\sigma) \le K(\sigma) + O(1)$ when $K$ is the prefix-free complexity. But how good is this inequality? More specifically I look for infinitely many strings $\tau_i$ with $Ku(\tau_i) \ge K(\sigma) - O(1)$. I can find such strings if the uniform complexity is replaced by the a priori complexity (sometimes denoted by $KM$), but I can't find these strings for $Ku$ (which would be a stronger statement).

The existence of such strings is equivalent to the existence of strings $\tau_i$ with $\sum_i 2^{-Ku(\tau_i)} \le c$ for some constant $c$.

I think that these string have to be incomparable relative to the prefix ordering (take for example the strings $0^n1$), but I don't know how proof the claim.

Thanks and
aurevoir

Lance Forthnow's example works to separate decision complexity and prefix-complexity: $Ku(0^n) \le O(1)$ for all $n$, and at the same time $K(0^n) > \log n$ for infinitely many $n$.

Note that $Ku(x) \le C(x) + O(1)$ where $C(x)$ denotes the plain complexity of $x$.

Decision complexity can also be lower than the logarithm of a priori probability. The argument is similar as the standard argument to separate plain and prefix complexity: we take advantage of the length of a program to encode an initial segment of a string. More formally, consider a long anough string $x$ such that for each $i < |x|$ we have $M(x_1...x_i) \le M(x_1...x_{i-1})/2$. Clearly we have $KM(x_1...x_i) \ge i$. Let $n \le |x|$ be a number whose binary representation is an initial segment of $x$. A uniform program of length $n - \log n + O(\log \log n)$ is obtained as follows: if $i \le \log n$ return the $i$-th bit of $n$ in binary, if $i \ge \log n$, return the corresponding bit in a literal representation of $x_{1 + \log n}...x_n$. For this program, we need to encrypt $\log n$ and $x_{1 + \log n}...x_n$. [The value $n$ can be recovered from $\log n$ and the length of the program.]


Two DFA intersection emptiness connections to SETH & L vs P (re "fine grained complexity") Wehar has proved that

  Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false.

does anyone see any particular key proof difficulty, challenge, implication etc in the inverse of that? ie

  if two DFA intersection emptiness is $\Omega(n^2)$ then SETH is true?

this two DFA intersection emptiness problem seems like a key problem to analyze/ resolve because Wehar has also shown that solving the intersection problem for $k$ DFA's in $n^{o(k)}$ time → $NL \subsetneq P$. (are there any other known problems like that? which relate L,P,NP,ExpTime?) the problem also seems similar to an old important problem complete for ExpSpace analyzed by Meyer/ Stockmeyer, "emptiness of regular expressions with squaring."

also, what is known on the best lower space bounds on this problem? (will regard partial answers on these presumably hard questions as ok.)

The "inverse" is almost the same as

  SAT is solvable in $O(2^{(1-\epsilon)n})$ time implies the intersection problem is solvable in
  $O(n^{2-\epsilon})$ time.

To show this, it seems that you would need to provide a reduction from an intersection problem instance of size $n$ to a SAT instance of size $2\cdot log_2(n)$.

This kind of reduction would be very interesting because it would take an instance of one problem to a much smaller instance of another problem.  As a result, this reduction would not be one-to-one.  Actually, there would be exponentially many inputs that map to the same output.

If you know of any interesting reductions of this form, please provide a reference.  Thank you.  :)


Autoencoders and information compression Disclaimer: I know very (very) little about deep nets, besides what an introductory course on machine learning would teach on neural networks, and skimming some paper abstracts and introductions.

If I understood correctly the concept, an autoencoder is a specific case of neural networks with as many input nodes than output nodes (say $d$), whose goal is to approximate the identity function
$$
\operatorname{id}\colon \mathbb{R}^d \to \mathbb{R}^d\,.
$$
The trick is that this net can be broken into two parts, "encoder" and "decoder" of the form $\Phi\colon \mathbb{R}^d \to \mathbb{R}^k$ and $\Psi\colon \mathbb{R}^k \to \mathbb{R}^d$, such that $k\ll d$. Therefore, there has to be something non-trivial going on for $\Psi\circ \Phi$ to approximate the identity, given the restricted width of the middle layers.

This struck me as begging the question:

  Can one (and has one already?) formalize and analyze this rigorously in terms of information theory, and specifically compression?

I realize the problem itself would need a more thorough and precise formulation to be tackled, as in the above we deal with full real numbers (so "hiding" information in a single real number, say the weight of a node in the middle layer, would give a very easy way out). But with this dealt with appropriately, hopefully there are non-trivial statements to be made with regard to what compression can be achieved, with respect to some distribution over the inputs?

Has this type of question been looked at from a theoretical viewpoint, in our community or another?

In the other situation when in your notation $k>>d$, in one of our papers we did analyze one such autoencoder in details to be able to say something about what you are asking. Does our Theorem 3.2 here, https://arxiv.org/pdf/1708.03735.pdf help? It took us about 15 pages of laborious calculation to get this - hopefully its helpful! :D

The "??" in the statement is a LaTeX error. It was meant to refer to the previous Theorem 3.1.


Banaszczyk's theorem Banaszczyk's theorem states that if $\Lambda$ is a rank-$m$ lattice with dual lattice $\Lambda^*$, then $\lambda_1(\Lambda) \cdot \lambda_m(\Lambda^*) \leq m$.

Can someone point me to a clean proof of this theorem? The proofs I am aware of in various lecture notes all lose a factor of 2 in the bound. And while Banaszczyk's paper is available, it is hard to read and seems to have this theorem buried among other results.

Divesh Aggarwal and Noah Stephens-Davidowitz very recently posted a preprint improving the constant in the upper bound of Banaszczyk's theorem: https://arxiv.org/abs/1907.09020. Specifically, they show that $\lambda_1(\Lambda)\mu(\Lambda^*) \leq (0.1275 + o(1)) n$, which combined with the upper bound $\lambda_n(\Lambda^*) \leq 2 \mu(\Lambda^*)$ implies that $\lambda_1(\Lambda)\lambda_n(\Lambda^*) \leq (2 \cdot 0.1275 + o(1)) n$. (Here $\mu$ denotes the covering radius of a lattice.)

Note that you state the upper bound with constant 1 (as is commonly done for convenience), whereas Banaszczyk's original work already shows that the bound holds with the improved constant $1/\pi$. In other words, the bound that you state is already off by a factor larger than 2.

Oded Regev's lecture notes also give a self-contained proof without worrying about getting the best possible constant. (It seems that you're likely already aware of these notes.)


Introductory notes on parallelization, in particular patterns of problems and algorithms I am looking for online available Lecture notes or other resources that give a good introduction into parallel programming, just like parallel analog of basic classes in computer science.

My focus is the following: while I am able to talk about divide&conquer, greedy algorithms, dynamic programming and the like, i.e. basic patterns of sequential algorithms (and problems), and I do not have the appropiate language to classify approaches in parallel algorithms.

For example, I would like to acquire the appropiate terms to express the fact that the obvious parallel approaches to each of the following problems have different qualitative behaviour:

setting an array of integers all-zero (scales perfectly.)
summing an array of integers (the more threads you use, the more overhead.)
Given an array, list the products of each entry with each other entry (if we parallelize the canonical double-for-loop, the running-time will scale to the sqrt of the number processors.)

A shared memory enviroment suffices, and interprocess communication is not so relevant for me (in fact, I am interested in algorithms that avoid it at all). Furthermore, the technical aspects are neglegible for me.

If you do not want to delve into the gory details, a very good introduction to parallelization design patterns is provided by the book Patterns for Parallel Programming by Mattson, Sanders and Massingill.

You will find general, widely applicable solutions to parallelization and even a brief introduction to both  OpenMP and MPI. The book starts by introducing design patterns and concurrency. Then, the authors proceed to illustrate how to exploit the concurrency, how to structure the algorithm, and how to actually implement the algorithm taking into account synchronization and communication.

Again, this is not a textbook on parallel algorithms. It does a very good job of presenting materials strictly related to parallel software engineering, with both a practical and theoretical focus. Therefore, it should suit perfectly your needs.


Maximum computational power of a C implementation If we go by the book (or any other version of the language specification if you prefer), how much computational power can a C implementation have?

Note that “C implementation” has a technical meaning: it is a particular instantiation of the C programming language specification where implementation-defined behavior is documented. A C implementation doesn't have to be able to run on an actual computer. It does have to implement the whole language, including every object having a bit-string representation and types having an implementation-defined size.

For the purpose of this question, there is no external storage. The only input/output you may perform is getchar (to read the program input) and putchar (to write the program output). Also any program that invokes undefined behavior is invalid: a valid program must have its behavior defined by the C specification plus the implementation's description of implementation-defined behaviors listed in appendix J (for C99). Note that calling library functions that are not mentioned in the standard is undefined behavior.

My initial reaction was that a C implementation is nothing more than a finite automaton, because it has a limit on the amount of addressable memory (you can't address more than sizeof(char*) * CHAR_BIT bits of storage, since distinct memory addresses must have distinct bit patterns when stored in a byte pointer).

However I think an implementation can do more than this. As far as I can tell, the standard imposes no limit on the depth of recursion. So you can make as many recursive function calls as you like, only all but a finite number of calls must use non-addressable (register) arguments. Thus a C implementation that allows arbitrary recursion and has no limit on the number of register objects can encode deterministic pushdown automata.

Is this correct? Can you find a more powerful C implementation? Does a Turing-complete C implementation exist?

As noted in the question, standard C requires that there exists a value UCHAR_MAX such that every variable of type unsigned char will always hold a value between 0 and UCHAR_MAX, inclusive.  It further requires that every dynamically-allocated object be represented by a sequence of bytes which is identifiable via pointer of type unsigned char*, and that there be a constant sizeof(unsigned char*) such that every pointer of that type be identifiable by a sequence of sizeof(unsigned char *) values of type unsigned char.  The number of objects that can be simultaneously dynamically allocated is thus rigidly limited to $UCHAR\_MAX ^{sizeof(unsigned\ char*)}$.  Nothing would prevent a theoretical compiler from assigning the values of those constants so as to support more than $10^{10^{10}}$ objects, but from a theoretical perspective the existence of any bound, no matter how large, means something isn't infinite.

A program could store an unbounded quantity of information on the stack if nothing that is allocated on the stack ever has its address taken; one could thus have a C program that was capable of doing some things which could not be done by any finite automaton of any size.  Thus, even though (or perhaps because) access to stack variables is much more limited than access to dynamically-allocated variables, it turns C from being a finite automaton into a push-down automaton.

There is, however, another potential wrinkle: it is required that if a program examines the underlying fixed-length sequences of character values associated with two pointers to different objects, those sequences must be unique.  Because there are only $UCHAR\_MAX ^{sizeof(unsigned\ char*)}$ possible sequences of character values, any program that created a number of pointers to distinct objects in excess of that could not comply with the C standard if code ever examined the sequence of characters associated with those pointers.  It would be possible in some cases, however, for a compiler to determine that no code was ever going to examine the sequence of characters associated with a pointer.  If each "char" was actually capable of holding any finite integer, and the machine's memory was a countably-infinite sequence of integers [given an unlimited-tape Turing machine, one could emulate such a machine although it would be really slow], then it would indeed be possible to make C a Turing-complete language.


Complexity of unique coloring of graphs The Isolation lemma of Mulmuley, Vazirani, and Vazirani  can be used to show that certain $\mathsf{NP}$-complete problems can be reduced via randomized polytime reductions to the unique solution version of the problem. This hints that  the promise of a unique solution is not likely to make the problem significantly easier.

A specific example for such a reduction in the Mulmuley, Vazirani, and Vazirani paper (pdf)
 is that CLIQUE can be reduced to UNIQUE CLIQUE via randomized polynomial time reductions. In this sense,  UNIQUE CLIQUE is (almost) as hard as CLIQUE.

  Is there anything similar known about the UNIQUE $k$-COLORABILITY of graphs?

It is worth noting that the promise of unique colorability seems to involve more structural consequences than the uniqueness of the maximum clique.

This paper by Régis Barbanchon might be of interest. From the abstract:

We prove that the Satisfiability (resp. planar Satisfiability) problem
is parsimoniously P-time reducible to the 3-Colorability (resp. Planar
3-Colorability) problem, that means that the exact number of solutions
is preserved by the reduction, provided that 3-colorings are counted
modulo their six trivial color permutations. In particular, the
uniqueness of solutions is preserved, which implies that Unique
3-Colorability is exactly as hard as Unique Satisfiability in the
general case as well as in the planar case...


Are there any known implementations for quantum computing constructs? Quantum Computation is an active area of research that aims to take advantage of quantum physics (e.g. quantum entanglement) to advance the efficiency capabilities of computers (does not alter the Church-Turing thesis).

What are the most significant experiments that have been conducted to demonstrate quantum-computing theory (such as qubits and teleportation)?

At this stage progress on experimental quantum computing is relatively slow, but there are now a wide variety of systems that can be used to implement one or more qubits.

At the moment the most developed systems as

Ion traps
Liquid state NMR
Linear optics quantum computing
Superconducting qubits

There has also been a lot of recent work with defects in solid state, solid state NMR, endohedral fullerenes, neutral atom traps, atom chips, etc.

The highest numbers of qubits tend to be in ion traps and NMR, though linear optics is doing well too.

As regards significant experiments, that really depends what constitutes progress to you. There was a very nice experiment back in 2007 where two separate ion traps were coupled optically, and some nice recent work on segmented ion traps, which demonstrate ways of scaling ion trap computation beyond 10 or so qubits. There has also been some very nice implementations of measurement based computation using optics, which is also important for scalability. If you have a better idea of the type of experiments you have in mind it would make the task of answering much easier.

The US quantum computing roadmap, available here, provides an excellent, though slightly dated overview of the state of the art circa 2004.


Do natural generalizations of P versus NP exist? Accepted Answer

Scott Aaronson's answer has been "accepted" (mainly because it's the only answer!)

One-sentence summary of answer  Plausibly natural generalizations of the P versus NP question are not obviously easier to resolve than P versus NP itself.

One obstruction to a general answer  The original question assumed that every complexity class A associates "naturally" to a nondeterministic generalization NA — however a general complexity class A can be defined in so many ways, that the class-map N$\colon\,$A$\,\to\,$NA cannot (apparently) be readily given a completely general and manifestly natural specification.

However …  dkuper's comment (below) provides a link to a talk by by Christos Kapoutsis (LIAFA), titled Minicomplexity, that describes a research strategy along the lines indicated.

For further discussion, a recommended resource is the Dick Lipton/Ken Regan Gödel's Lost Letter and P=NP essay titled We Believe A Lot, But Can Prove Little.

The question finally asked

  The question  What trait shared by every complexity class A ⊂ P that is richer than NTIME(n ln n), acts to obstruct proofs of A ⊂ NA?

This question was motivated by Scott Aaronson's recent weblog comments (see below), and the complexity-theoretic richness of this question has subsequently been illuminated by comments/answers/essays by Robin Kathari, Scott Aaronson, Ryan Williams, Dick Lipton and Ken Regan, and previous TCS StackExchange questions.

  Observations  (1) For all known complexity classes A ⊂ P that are sufficiently large as to include NTIME(n ln n) ⊂ A, the problem A $\overset{?}{\subset}$ NA is open, and (2) the reason(s) for this near-universal complexity-theoretic obstruction are not presently well-understood.

Like many folks, I had long appreciated the immense difficulty of proving P ⊂ NP, but had not previously appreciated that proving A ⊂ NA is an open problem for (essentially) all computational complexity classes.

The question originally asked

On his weblog Shtetl Optimized, Scott Aaronson issued the following TCS challenge:

  The Shtetl Optimized TCS Challenge   If you believe P vs. NP is undecidable, then you need to answer:

  The Shtetl Optimized TCS Question   Why does whatever intuition tells you that [P vs NP is undecidable] not also tell you that the P versus EXP, NL versus PSPACE, MAEXP versus P/poly, TC0 versus AC0, and NEXP versus ACC questions are similarly undecidable?

  (In case you don’t know, those are five pairs of complexity classes that have been proved different from each other, sometimes using very sophisticated ideas.)

Answers to the following specific question will be accepted:

  Q1 (TCS literature question)   Do any known complexity classes A and B provably satisfy A ⊂ B and NA ⊇ B, for NA the natural non-deterministic extension of A?

Supposing that the answer to Q1 is "yes", an explanation is desired of how it happens that the strict inclusion A ⊂ B has been proved, while the (superficially similar) strict inclusion P ⊂ NP is hard to prove.

Alternatively, if the answer to Q1 is "no", one further question is asked:

  Q2 (The Extended Shtetl Optimized TCS Question)   Are complexity-class inclusions of the general form A ⊂ B and NA ⊇ B provable — in ZFC or any finite extension of ZFC — for any "natural" complexity classes whatsoever? (if "yes" construct examples; if "no" prove the obstruction).

PostScript   Appreciation and thanks are extended to TCS StackExchange for sustaining this wonderfully inspiring and helpful mathematical community, and to Scott Aaronson for sustaining his admirable weblog Shtetl Optimized!

John, while your kind comments are appreciated, I confess that I don't understand how your question relates to the simple point I was making in the quoted remark.  All I was saying was that we do know various separations between complexity classes, like P≠EXP, MAEXP⊄P/poly, NEXP⊄ACC, etc.  So, if you believe that a particular separation, like P≠NP, is "too deep to be either proved or disproved in ZF set theory" (or whatever), then it seems to me that the burden falls on you to explain why you think that separation has to be independent of ZF, while other separations turned out not to be.  For this argument to have force, I see no necessity for the other separations to have the particular form you specified.

But to address your question anyway: well, the obvious challenge in answering is to find any complexity class A for which we can prove that A is strictly contained in NA, where NA is "the natural non-deterministic extension of A"!  (Indeed, as Robin points out above, finding such an A is equivalent to answering your question as you've stated it.)  And the only examples of such A's that I can think of are things like TIME(f(n)) (it was proved in the 1970s that TIME(f(n))≠NTIME(f(n)) for f(n)≤n log*n, since NTIME(f(n)) can simulate time slightly greater than f(n)).  (An earlier version of this post claimed that was known for all f(n).  Thanks to Ryan Williams for the correction!)  So setting A=TIME(n) and B=NTIME(n) would indeed answer your question in the affirmative.  A more "natural" example will probably need to await a breakthrough in complexity theory.

[Endnote: I wish to clarify that I didn't give things portentous names like "The Shtetl Optimized this or that"---those were Sidles's elaborations!]


Lower bounds on monotone space complexity The monotone space complexity of a language $L \subseteq \Sigma^*$ can be defined in terms of monotone switching networks (see e.g. "Average Case Lower Bounds for Monotone Switching Networks" by Filmus et al.). This notion is linked to the monotone $NC$ hierarchy and may have applications to the non-monotone setting for which most questions are open.

Here is an equivalent definition in term of circuits. Let $K$ be a circuit (or dag) whose arcs are labelled by elements of $[n] \times \Sigma$, and which has a single root node $r$. We say that $K$ accepts a word $w \in \Sigma^n$ iff there is a root-leaf path $P$ in $K$ whose sequence of labels matches $w$, i.e. for each label $(i,a)$ in $P$ we have $w[i] = a$. Now, given a language $L$, for each integer $n$ we define its $n$-slice complexity $C_L(n)$ as the minimum size of a circuit accepting exactly the words in $L \cap \Sigma^n$. We can put some restrictions on this notion, for instance by requiring that the circuits are read-once, meaning that each accepting path makes a single access to a given position. This leads to a second complexity measure $C'_L(n)$ which seems easier to analyze, as illustrated below.

An example is the Perfect Matching problem ($PM$), which can be shown to have monotone complexity $C'_{PM}(n) = 2^{\Omega(n)}$ as follows. Let $PM_n$ denote the slice of the language corresponding to bipartite graphs $G$ with $n$ vertices on each side of the bipartition (denoted by $A,B$). Consider a circuit $K$ accepting it. Given an integer $k$, let $\mathcal{P}_k$ denote the set of paths of length $k$ in $K$ starting from the root, and let $\mathcal{T}_k$ denote the pair of sets $(S,T)$ with $S \subseteq A, T \subseteq B$ and $|S| = |T| = k$. By monotonicity, we can make the following assumption:

(*) for each node $u$ of depth $k$, there is a tuple $t = (S,T) \in \mathcal{T}_k$ such that each path $P \in \mathcal{P}_k$ leading to $u$ is labeled by a permutation $\sigma_P : S \rightarrow T$.

Indeed, if there were two different paths leading to $u$ corresponding to different tuples, one of them could be extended to a function that is not a permutation (and thus would recognize an $n$-edges graph that is not a matching).

Now observe that we must have the following "coverage" property: for each permutation $\sigma : A \rightarrow B$, there should exist some path $P \in \mathcal{P}_k$ such that $\sigma$ extends $\sigma_P$. Observe that a given permutation $\sigma_P$ can be extended to at most $(n-k)!$ different permutations, and that a given tuple in $\mathcal{T}_k$ can induce at most $k!$ different permutations. This implies that the number of nodes at depth $k$ is at least $\frac{n!}{k! (n-k)!}$. In particular, the number of nodes at level $\frac{n}{2}$ is at least $\frac{n!}{(\frac{n}{2})!^2} = 2^{\Omega(n)}$.

There are two things I would like to understand: (i) why does this reasoning break down for read-many / nonmonotone space complexity, (ii) how does it relate to known lower bounds for the monotone space complexity of $PM$.

This not quite an answer, but rather an "extended comment".

To question (i): property (*) holds because of read-once, not because of the monotonicity, and this is why the argument fails in the read-many (even monotone) case: then the combined paths need not be PMs, they can be arbitrary graphs containing a PM.

In the read-once case, even the Exact PM (accept a graph iff it is a perfect matching) requires exponential size (by the same argument as yours). But if we allow negations, then EPM can be computed by a circuit of size $O(n^3)$: check if every node in A has degree at least one, and if every node in B has degree at most one. The resulting switching network is "almost read-once": every consistent path is read -once. Search term "null-path" here for more information.

To question (ii): I haven't understood what "it" here refers to? But as far as I know, the $n^{\Omega(\log n)}$ lower bound of Razborov (for monotone circuit size of PM) remains the strongest one. Even though monotone switching networks constitute a special case of monotone circuits (where one input of each AND gate must be a variable), no stronger lower bounds for PM are known here.


What does consistency mean for "computational theories" corresponding to inductive types? I am currently reading the book by Luo on computation and reasoning. In the book he contrasts inductive types considered as computational theories with axiomatic theories widespread in "standard" mathematics.

However, if we have axiomatic theories, then they can be inconsistent. It seems to be impossible with inductive types. But why this is so?

P.S. As far as I understand from an answer to my previous question "Correctness" of type theory we can create an inductively defined set and consistency of the type theory + inductive type will be equivalent to the consistency of set theory. Am I right?

With inductive types consistency is manifested as a termination property. Functions from inductive types are defined by structural recursion. How do we know they are well-defined, i.e., that they are total?

Here is an example:

Inductive nat :=
  | Z : nat
  | S : nat -> nat.

Inductive omega1 :=
  | zero : omega1
  | succ : omega1 -> omega1
  | sup  : (nat -> omega1) -> omega1.

Intuitively, omega1 consists of well-founded countable trees. Given a type A, an element a : A, a map f : A -> A and a map g : (nat -> A) -> A we can define a map F : omega1 -> A by recursion:

fix F (t : omega1) : A :=
  match t with
  | zero => a
  | succ x => f (F x)
  | sup s => g (fun n : nat => F (s n))
  end

The principle that every such F is well defined is equivalent to induction on well-founded countable trees. In terms of ordinal strength that's induction up to $\omega_1$. If you keep everything syntactic and/or computable so that you only use computable trees, you might get away with $\omega_1^{\mathrm{CK}}$, which isn't really better. Therefore, if $\omega_1$ does not exist we have a problem, and existence of $\omega_1$ is pretty strong in terms of consistency.

Concretely, suppose we came up with a new kind of inductive type I that were inhabited and it allowed us to write a non-terminating function. We could use it inhabit the empty type void by defining a non-terminating function f : I -> void. This actually happened in history. Originallly Martin-Löf proposed a type theory with Type : Type and Girard proved it to be inconsistent by simulating the Burali-Forti paradox. This gives us an idea: suppose we define a type WellOrder of all well-orders. Because well-orders themselves are well-ordered, WellOrder has an induction principle -- it is a kind of inductive type, and in fact is itself a well-order. If we now also posit that WellOrder is an element of WellOrder (by which I mean that there is wt : WellOrder which encodes WellOrder) we will hit the Burali-Forty paradox, define a non-terminating function, and inhabit False. In fact, much less is needed and is included in the standard Coq library under Pardoxes.BuralliForti_ex, see theorem Burali_Forti : False.


Is this a knapsack problem? I have a set of $K$ keywords. Each of this keywords can have a set of bids from $1\$,\ldots, N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost are monotonic in bids. Now, the problem is:

Select a bid for each of the keyword such that overall clicks across the keywords are maximized such that the cost is still within a given budget $B$. Let $\text{Clicks}(W_i)$ and $\text{Cost}(W_i)$ denote the clicks and cost on the keyword $i$. Then (informally) the problem is to select a value of bid for each keyword such that \begin{align}\max\sum_{i=1}^{K}&\text{Clicks}(W_i) \\s.t.&~~\sum_{i=1}^{K}\text{Cost}(W_i)\leq B\end{align} Is this a type of knapsack problem? Are there any known heuristic in the literature.

Following is not important for the question (and thus can be skipped), but is for the curious ones to know how I am solving this currently.

Let $S_{ij}$ denote the cost for using bid $j$ for keyword $i$ and let $C_{ij}$ be the clicks for the same. Let $x_{ij}$ be the indicator variable for using bid $j$ for keyword $i$. Then among variables $x_{i1},\dots,x_{iN}$ only one can be non-zero (i.e. $x_{ij}=1$) whereas the rest is zero (since only one bid can chosen for keyword).

Thus, the whole problem can be formulated mathematically as

\begin{align}\max_{x_{ij}}~&\sum_{i=1}^{K}\sum_{j=1}^{N}x_{ij}C_{ij} \\s.t.~~\sum_{i=1}^{K}\sum_{j=1}^{N}&x_{ij}S_{ij}\leq B\\\sum_{j=1}^{N}x_{ij}=1&~~\forall i\in \{1,\dots,K\}~~,~~x_{ij}\in\{0,1\}\end{align}

Last, two constraints ensure they are indicator variables and only one bid is chosen for a given keyword. Solving this should solve the original problem.

Yes, it is called a multiple-choice knapsack problem. It can be solved in time $O(N B)$ by dynamic programming. The state of the dynamic program is given by a pair $(i, b)$ and the associated value is the maximum value (clicks) you can get with keywords from $1$ to $i$ with a budget at most $b$.

Source: S. Martello, P. Toth. Knapsack Problems. Wiley, 1990.


Hamiltonian cycle on graphs without small cycles While answering this question on cstheory, I (informally) proved on the fly the following theorem:

Theorem: For any fixed $l \geq 3$ the Hamiltonian cycle probem remains NP-complete even if restricted to planar bipartite undirected graphs of maximum degree 3 that don't contain cycles of length $\leq l$.

It seems very unlikely that it has not already appeared somewhere.
But it allows to settle many Hamiltonian cycle/path problems on graphclasses.org that are marked as "Unknown to ISGCI" (see for example this one); indeed a direct corollary is that Hamiltonian cycle and path problems are still NP-complete if restricted to $(H_1,...,H_k)\text{-free}$ graphs, where each of the $H_i$ contains at least one cycle.

  Can you give me a reference of the paper/book where it appeared?

(then I'll contact people at graphclasses.org)

This unpublished manuscript by Hougardy, Emden-Weinert and Kreuter in 1997
provided a simple proof for the following result which is much stronger than the result pointed out in
Kristoffer Arnsfelt Hansen's answer:

  For any given rational number $0\le r <1/2$, the Hamiltonian cycle probem remains NP-complete even if restricted to bipartite planar $n$-vertex graphs of maximum degree 3 and girth $\ge n^r$.

The manuscript contains also similar results for other problems such as Dominating set, Max cut, VFS, etc.


Qubit gates in google supremacy The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment with a smaller computer than Summit/OLCF-$4$ in a reasonable time and if not why not?

Based on a fairly cursory inspection of their paper, IBM is clearly aware of the spatial locality. They seem to in fact have taken spatial locality into account when designing their simulation. They use spatial locality to put the states of local systems into primary memory, and record the whole state in secondary memory. If you can't contain the whole state of the quantum machine in your computer, you will have to keep recomputing pieces of the state, which is going to take much more time.

You have to trust both IBM and Google to have thought about the best way to do the simulation, and give accurate answers for how long a simulation would take. The researchers working at both these places are not stupid, and although it's quite possible that people will come up with better simulation methods eventually, they have indeed taken spatial locality into account.

Consider the paragraphs below taken from their paper, where it's clear that IBM uses spatial locality to make their simulation as fast as it is. Their simulation method is based on reference [14], which is turn is an extension of a simulation method discussed in [9]:

  The simulation method in [9] can be seen as a tensor slicing approach. Qubits (and the corresponding
  tensor indices) are divided into “global” qubits, which are sliced and used to address across processing
  nodes, and “local” qubits, corresponding to tensor indices used to address tensor slices stored on each
  processing node. In [9], circuits are partitioned so that all gates within a subcircuit can be applied to the
  local slice of the quantum state, without communicating quantum state information among processing
  nodes. Such zero-communication updates of a local quantum state are possible when all non-diagonal
  gates in a subcircuit are applied to local qubits only. ...

  The in-memory method that we presented in [14] considers circuit partitionings in which the resulting tensors either fit in available aggregate primary memory in their entirety, or their slices can be
  computed using available primary memory (using other tensors already computed and stored in primary memory). With this approach, the resulting tensors and/or their slices will generally be larger than the
  primary memories of individual processing nodes; this represents a difference between [14] and [9].

  As discussed in [14], we combine the zero-communication strategies of [9] with our own tensor
  partitioning strategy to leverage secondary storage when quantum states are too large to fit in aggregate primary memory.

  [9] T. Haner and D. S. Steiger. 0.5 petabyte simulation of a 45-qubit quantum circuit. In ¨ Proceedings of
  the International Conference for High Performance Computing, Networking, Storage and Analysis,
  SC ’17, pages 33:1–33:10, New York, NY, USA, 2017. ACM.

  [14] E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, T. Magerlein, E. Solomonik, and R. Wisnieff. Breaking the 49-qubit barrier in the simulation of quantum circuits. arXiv preprint
  arXiv:1710.05867, 2017.

Of course, it's quite possible that you could design a better simulation by using more information about Google's Sycamore architecture. But you may need to use more sophisticated information about it than just locality.


Stochastic gradient methods and risk of neural nets Under many situations it is currently provable that we can minimize the risk of neural nets using stochastic gradient based algorithms. For example : https://arxiv.org/abs/1811.03804, https://arxiv.org/abs/1811.04918 https://arxiv.org/abs/1811.03962, https://arxiv.org/abs/1810.12065, https://arxiv.org/pdf/1810.02054.pdf, https://arxiv.org/abs/1705.04591 and dozens more!

Is the focus on stochastic gradient based methods for this question purely motivated by the fact that this is pretty much the only thing used in practice?

Or is there a fundamental/complexity-theoretic reason why there cant be an algorithm (or its improbably hard to find an algorithm) that does not use stochastic gradients (is maybe deterministic!) and yet minimizes the risk of neural nets as fast as one can using SGD-like methods?

The question has changed somewhat in the comments, so I'll address its new version: "Given a class of algorithms $A$ and an $\epsilon >0$ and a loss class $L$ and a data distribution $D$, one cannot use algorithms of type $A$ to find a member of $L$ whose generalization error is below $\epsilon$ unless running time is $f(\epsilon)$"... .

One such lower bound I'm aware of is for the case of Statistical Query based algorithms. See, for example, the paper by Yang, "New lower bounds for statistical query learning",
https://www.sciencedirect.com/science/article/pii/S0022000004001291
where, in particular,
it is shown that "any SQ-based algorithm needs running time $\Omega(2^n)$".


What are the relations between Alternative, MonadPlus(LeftCatch) and MonadPlus(LeftDistributive)? Following up What’s an example of a Monad which is an Alternative but not a MonadPlus?:

Assume $m$ is a monad. What are the relations betweem $m$ being an Alternative, a MonadPlusCatch and a MonadPlusDistr? For each of the six possible pairs, I'd like to have either a proof that one implies another, or a counter-example that it doesn't.

(I'm using

MonadPlusCatch to distinguish a MonadPlus that satisfies the Left-Catch rule:

mplus (return a) b = return a

MonadPlusDistr to distinguish a MonadPlus that satifies Left-Distribution rule:

mplus a b >>= k = mplus (a >>= k) (b >>= k)

see MonadPlus on HaskellWiki.)

My current knowledge + intuition is that:

MonadPlusDist $\rightarrow$ Alternative - likely true - it seems straightforward, I believe I have sketch of a proof, I'll check it and if it's correct, I'll post it AndrewC answered this part.
Alternative $\rightarrow$ MonadPlusDist - false - as AndrewC showed in his answer: Maybe is an Alternative, but it's known it's not MonadPlusDist (it's MonadPlusCatch).
MonadPlusCatch $\rightarrow$ Alternative - likely false - I believe that MaybeT (Either e) (or basically anything MaybeT m') should serve as a counterexample. The reason is that

((pure x) <|> g) <*> a =    -- LeftCatch
    (pure x) <*> a
-- which in general cannot be equal to
((pure x) <*> a) <|> (g <*> a)

again I'll check and post. (Interestingly, for just Maybe it's provable, because we can analyze if a is Just something or Nothing - see the aforementioned AndrewC's answer.)
Alternative $\rightarrow$ MonadPlusCatch - likely false - if we prove that MonadPlusDist $\rightarrow$ Alternative then [] will server as a counter-example. (Or we could explicitly prove Alternative laws for [].)
MonadPlusDist $\rightarrow$ MonadPlusCatch - false - [] is a known counter-example.
MonadPlusCatch $\rightarrow$ MonadPlusDist - false - Maybe is a known counter-example.

MonadPlusDist $\rightarrow$ Alternative is true.

Corollary: Alternative $\rightarrow$ MonadPlusCatch is false

(because as Petr Pudlák pointed out, [] is a counterexample - it doesn't satisfy MonadPlusCatch but does satisfy MonadPlusDist, hence Applicative)

Assumed: MonadPlusDist Laws

-- (mplus,mzero) is a monoid
mzero >>= k = mzero`                             -- left identity >>=
(a `mplus` b) >>= k  =  (a >>=k) `mplus` (b>>=k) -- left dist mplus

To prove: Alternative Laws

-- ((<|>),empty) is a monoid
(f <|> g) <*> a = (f <*> a) <|> (g <*> a) -- right dist <*>
empty <*> a = empty                       -- left identity <*>
f <$> (a <|> b) = (f <$> a) <|> (f <$> b) -- left dist <$>
f <$> empty = empty                       -- empty fmap

<*> expansion lemma
Assume we use the standard derivation of an applicative from a monad, namely (<*>) = ap and pure = return. Then

mf <*> mx = mf >>= \f -> mx >>= \x -> return (f x)

because

mf <*> mx = ap mf mx                                  -- premise
          = liftM2 id mf mx                           -- def(ap)
          = do { f <- mf; x <- mx; return (id f x) }  -- def(liftM2)
          = mf >>= \f -> mx >>= \x -> return (id f x) -- desugaring
          = mf >>= \f -> mx >>= \x -> return (f x)    -- def(id)

<$> expansion lemma
Assume we use the standard derivation of a functor from a monad, namely (<$>) = liftM. Then

f <$> mx = mx >>= return . f

because

f <$> mx = liftM f mx                    -- premise
         = do { x <- mx; return (f x) }  -- def(liftM)
         = mx >>= \x -> return (f x)     -- desugaring
         = mx >>= \x -> (return.f) x     -- def((.))
         = mx >>= return.f               -- eta-reduction

Proof

Assume (<+>,m0) satisfy the MonadPlus laws. Trivially then it's a monoid.

Right Dist <*>

I'll prove

(mf <+> mg) <*> ma = (mf <*> ma) <+> (mg <*> ma) -- right dist <*>

because it's easier on the notation.

(mf <+> mg) <*> ma = (mf <+> mg) >>= \forg -> mx >>= \x -> return (forg x) -- <*> expansion
                   =     (mf >>= \f_g -> mx >>= \x -> return (f_g x))
                     <+> (mg >>= \f_g -> mx >>= \x -> return (f_g x))      -- left dist mplus
                   = (mf <*> mx) <+> (mg <*> mx)                           -- <*> expansion

Left Identity <*>

mzero <*> mx = mzero >>= \f -> mx >>= \x -> return (f x) -- <*> expansion
             = mzero                                     -- left identity >>=

as required.

Left Dist <$>

f <$> (a <|> b) = (f <$> a) <|> (f <$> b) -- left dist <$>

f <$> (a <+> b) = (a <+> b) >>= return . f              -- <$> expansion
                = (a >>= return.f) <+> (b >>= return.f) -- left dist mplus
                = (f <$> a) <+> (f <$> b)               -- <$> expansion

empty fmap

f <$> mzero = mzero >>= return.f   -- <$> expansion
            = mzero                -- left identity >>=

as required