Max weight travel on a graph with deadline Given a deadline $D>0$ and a complete graph $K_n$ (with loops) in which each edge $e_{ij}$ has a weight $w(e_{ij}) \ge 0$ and a travel time $l(e_{ij}) > 0$. Starting from one of the nodes, we want to find a path $P$ so that $\sum_{e \in P}l(e) \le D$ and $\sum_{e \in P} w(e)$ is maximized.

Questions:

This problem can be solved using a pseudo polynomial algorithm by iterating over time $t=1,\cdots,D$.
Let $S_{v,t}$ be the weight of the optimal path until time $t$ ending at vertex $v$.
$$
S_{v,t}=\max(\max_u S_{u,t-l(e_{uv})},S_{v,t-1})
$$
Therefore, it seems a (weakly) NP-hard problem to me, but I have no proof for it yet. Do you have any idea?
In a more complicated version of the problem, the path can visit each vertex $v$ and each edge $e$ at most $h(v)$ and $h(e)$ times. The above algorithm does not work for this constraint version of the problem. Any better solution?

The problem can be modeled using ILP:
$$
\begin{align}
{\tt Maximize} \quad & \sum_i \sum_j w(e_{ij}) X_{ij} \\
&\sum_i \sum_j l(e_{ij}) X_{ij} \le D \\
& \sum_i X_{i0} = \sum_j X_{0j} = 1\\
& \sum_i X_{iv} = \sum_j X_{vj}, \quad {\tt for \; all \;} v = 1,\cdots,n
\end{align}
$$

Where $X_{ij}$ denotes the number of times the path goes through edge $e_{ij}$.
The first constraint enforces the deadline and the last two are the conservation law (number of times entering a node is the same as the number of times exiting it). $v_0$ is a virtual node that traveling to/from it has zero weight and zero time.

In the more complicated version of the problem,
we have the following additional constraints:
$$
X_{ij} \le h(e_{ij})
$$
$$
\sum_i X_{iv} \le h(v) \quad {\tt for \; all \; }v
$$

Since you specifically ask later about the version of the problem in which the given path is restricted in how many times it visits each vertex/edge, I assume that the original version of the problem has no such restriction. In other words, in the original version of the problem the "path" is actually a trail (i.e., any sequence of vertices such that each contiguous pair has an edge between them). Thus I will refer to the original version of the problem as the trail max-weight travel problem. The other version, in which the number of uses of each edge/vertex is limited, includes the case in which each edge/vertex can be used at most once (i.e., the trail used must be a simple path); I will call that subproblem the simple path max-weight travel problem.

Below, I prove that trail max-weight travel is weakly NP-hard and that simple path max-weight travel is strongly NP-hard.

trail max-weight travel is weakly NP-hard

We reduce from the Unbounded Knapsack problem: we are given a list of pairs of positive integers $(c_1, s_1), \ldots, (c_k, s_k)$ where pair $i$ represents a type of item with cost $c_i$ and size $s_i$, a maximum size $S$, and a minimum cost $C$, and we are asked to decide whether it is possible to choose some quantity of each item so that the total size is at most $S$ and the total cost is at least $C$.

Suppose we are given an input $(c_1, s_1), \ldots, (c_k, s_k), S, C$ to the knapsack problem. Let $H > S$ be any big ("huge") number. Then we build an instance of trail max-weight travel as follows:

Set the graph size $n$ to be $k + 1$. Let $1, \ldots, k+1$ be the vertices of graph $K_n$.
Set the deadline $D$ to be $(k+1)H + S$.
If $1 \le i < j \le k+1$ then set the weight $w(e_{ij})$ to be $0$. Set the travel time $l(e_{ij})$ to be $(j-i)H$.
If $1 \le i \le k$ then set the weight $w(e_{ii})$ to be $c_i$. Set the travel time $l(e_{ii})$ to be $s_i$.
If $i = k+1$ then set the travel time $l(e_{ii})$ to be $H$. Set weight $w(e_{ii})$ to be some number $M$ that is greater than $D (\max_{i = 1}^k \frac{c_i}{s_i})$.
Set the start node to be vertex $1$.

We will show that a trail of total travel time $D$ has a weight of at least $M + C$ if and only if the answer to the given knapsack instance is "yes". This is sufficient to show NP-hardness.

There are two possible types of trails: those that use edge $e_{ii}$ with $i = k+1$ and those that don't. Call this edge $e'$.

The maximum weight gained per unit of travel time over all edges other than $e'$ is $\max_{i = 1}^k \frac{c_i}{s_i}$. Thus, any trail that does not use edge $e'$ will have a total weight of at most $D (\max_{i = 1}^k \frac{c_i}{s_i}) < M$. Thus, trails that do not use edge $e'$ will have total weight less than $M$.

Clearly, some trail (whose travel time is at most the deadline) has total weight at least $M + C$ if and only if a trail using edge $e'$ (with travel time at most the deadline) has total weight at least $M + C$. Using edge $e'$ requires reaching vertex $k+1$ from vertex $1$. This requires using a travel time of at least $kH$. Then using edge $e'$ requires an additional travel time $H$. After that, there is not enough time left in the deadline to use edge $e'$ again. Thus, any trail whose travel time is at most the deadline and whose weight is at least $M + C$ will use edge $e'$ exactly once.

Since traveling between vertices adds no weight, it should be clear that the optimal solution will always spend the minimum possible travel time between vertices. Fortunately, this is possible without bypassing any vertex (by going through the vertices in order $1, 2, \ldots, k+1$). This means that there is always an optimal solution to the produced trail max-weight travel instance in which we pass through the vertices in order $1, 2, \ldots, k+1$ taking one self loop at vertex $k+1$ (in particular edge $e'$) and some number of self loops at the other vertices. Traveling between the vertices has travel time $kH$ and weight $0$. The self loop at vertex $k+1$ has travel time $H$ and weight $M$. Thus, in order for this optimal solution to reach a weight of at least $M + C$ within a deadline of $D = (k+1)H+S$, it must be the case that the total travel time used on the self loops at vertices $\{1, \ldots, k\}$ is at most $S$ and the total weight gained at those self loops is at least $C$. Since self loop $e_{ii}$ has travel time $s_i$ and weight $c_i$, this is exactly equivalent to the knapsack instance we started with.

simple path max-weight travel is strongly NP-hard

We reduce from the following NP-hard version of the Hamiltonian path problem: given graph $G$ and vertex $v$, decide whether there exists a Hamiltonian path in $G$ starting at $v$.

Suppose we are given an instance of this problem with graph $G = (V, E)$ and vertex $v \in  V$. Then we build an instance of simple path max-weight travel as follows:

Set the graph size $n$ to be $|V|$.
Set the deadline $D$ to be $|V| - 1$.
Identify each vertex of $K_n$ with each vertex of $G$. Then for each edge $e$ of $K_n$: (1) if $e$ corresponds to an edge of $G$, set the travel time $l(e)$ to be $1$ and (2) if $e$ does not correspond to an edge of $G$, set the set the travel time $l(e)$ to be $|V|$. In all cases, set the weight of each edge to be $1$.
Set the start node to be the node corresponding to $v$.
As always in the simple path max-weight travel problem, each vertex/edge can be used at most once: $h(\cdot) = 1$.

Each edge has the same weight, so maximizing weight is equivalent to choosing the longest simple path whose total travel time does not exceed the deadline. The only edges that can be used without exceeding the deadline exactly correspond to edges in $G$. Furthermore, each such edge has the same time limit: $1$. Thus, solving this instance is equivalent to finding the longest simple path in $G$ starting at $v$ of length at most $|V| - 1$. Such a path of length exactly $|V| - 1$ is a Hamiltonian path, so solving this problem requires being able to solve the Hamiltonian path problem in $G$. Thus the reduction is correct. Note that the size of each number in this proof is at most polynomial in the size of the input instance, so this is a proof of strong NP-hardness.


New Space Lower-Bound Techniques for Streaming Algorithms Is communication complexity (CC) the only known approach for streaming algorithms lower bounds? Are there any other techniques, even if conditional lower bounds?

In general, are we satisfied with the progress achieved via CC? Or seeking alternative techniques (even if conditional) would be an interesting direction?

A recent result of Li, Nguyen, and Woodruff shows that for any streaming algorithm in the turnstile model (where the stream consists of insertions and deletions of elements) there exists an algorithm that works by only maintaining a linear sketch and uses only slightly more space. So to prove a space lower bound in the turnstile model it is (up to some logarithmic factors) enough to prove a space lower bound for linear sketches. These can be easier to prove, for example by proving a communication lower bound in the simultaneous communication model rather than in the one-way model, or by more directly working with the linear structure of the sketch: check the paper for a lower bound on the space complexity of frequency moments proved this way.


What does "number of inputs to each neuron" mean in Neural Network terms? I am reading about a Neural Networks project that has some data like this

I am new to this, and though I think I understand what a 3:1 network mean, I do not understand what number of inputs (to each neuron) means.

I think this is what a 3:1 network would look like (please correct me if I am wrong). Does 3 inputs per neuron mean that we will have 3 inputs to each of nodes A, B and C? In that case, what would the line connecting A to Z indicate? As in out of three inputs, how is a resultant chosen?

You are bypassing the "hidden layer": A neural network consists of three layers: Input layer, hidden layer, and output layer:

You may also have more than one hidden layer:

(source: mu-sigma.com)

Though, in your case, since the number of hidden layers is not specified, it is safe to assume that there is just 1 hidden layer.

So, for example, in a 3:1 network, you have 1 output neuron, and 3 hidden neurons. The number of inputs shows the number of neurons in the input layer.


Hitting set of very restricted linear forms We say that $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$ is a {-1,0,1}-linear
form if $f=\sum_{i\in S}x_{i}-\sum_{i\in T}x_{i}$ where $S,T\subseteq[n]$.
A hitting set $H\subseteq\mathbb{Z}^{n}$ for {-1,0,1}-linear
forms is such that, for any non-zero {-1,0,1}-coef linear form $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$,
there is $\alpha\in H$ where $f(\alpha)\neq0$.

Observe that a singleton $\{(2^{1},\dots,2^{n})\}$ is already a hitting
set for $\{-1,0,1\}$-linear forms.

A hitting set is polynomially bounded if $H\subseteq\{-n^{c},\dots,n^{c}\}^{n}$
for some fixed constant $c$.

  What is the smallest size of polynomially bounded hitting set for
  {-1,0,1}-linear forms ?

By Chinese remaindering and this singleton $\{(2^{1},\dots,2^{n})\}$,
one can show a polynomially bounded hitting set of size $O(n/\log n)$.
Can we do better ?

There is a tight lower bound of size $\Omega(n/ \log n)$ by simple counting argument.

Suppose there is a hitting set $H=\{\alpha_{1},\dots,\alpha_{k}\}$
of size $k$. We will show that there is always {-1,0,1}-linear
form $f$ such that $f(\alpha_{i})=0$ for all $i$ when $k\le c_{0}n/\log n$
and $c_{0}$ is small enough.

For each $S\subseteq[n]$, let $f_{S}=\sum_{i\in S}x_{i}$ and $f_{S}(H)=(f_{S}(\alpha_{1}),\dots,f_{S}(\alpha_{k}))$.

Since $|f_{S}(\alpha_{i})|\le n^{c+1}$, there are at most $(2n^{(c+1)})^{k}$
possible distinct values of $f_{S}(H)$. But there are $2^{n}$ distinct
linear forms $f_{S}$.

Because $(2n^{(c+1)})^{k}<2^{n}$ when $k\le c_{0}n/\log n$, we have
that there are $S$ and $S'$ where $f_{S}(\alpha_{i})=f_{S'}(\alpha_{i})$
for all $i$.

So $(f_{S}-f_{S'})(\alpha_i)=0$ for all $i$, $f_{S}-f_{S'}$ is a {-1,0,1}-linear form.


On finding a chain decomposition of a Partial Order I am reading a paper by Daskalakis et al. entitled "Sorting and Selection in Posets". http://arxiv.org/abs/0707.1532

In that paper it is presented an enhancement to the algorithm Poset-BinInsertionSort by Faigle & Turan (Figure 1 in the paper) for the reconstruction of a partial order when we are allowed to invoke an oracle telling us if two elements are related or not. The enhancement consists in replacing a step of the previous algorithm with a less expensive step (Figure 2: the EntropySort algorithm).

Now, here's the question. The complexity, in terms of number of queries to the oracle, of the Feigle & Turan algorithm is $O(wn \log n)$ for a poset of width $w$ made up of $n$ elements. (For definitions please see the paper's introduction)

Algorithm in Figure 1 proceeds by incrementally adding one element at a time and in step 4.c it asks for finding a chain decomposition of the set of elements considered so far. I'm struggling with this point because, even if we keep the chain decomposition up-to-dated I am not able to reduce the number of queries to $O(\log n)$ as it would have been requested to keep the complexity of $O(n \log n + wn)$ as claimed in theorem 6 of the paper.

  In brief, here's the question. Suppose you are given a Poset $P=(A,R)$
  of width w (i.e. the cardinality of the largest antichain is w)
  suppose you have $A^\prime \subseteq A$. Is it possible to build a
  decomposition of size $q \leq w$ in time $O(\log n)$ queries as
  requested by the algorithm in the paper?

Thanks in advance.
f

Your access to $A$ (which is $P$ in the paper) is through an oracle, and you're charged for each query. But in terms of the query count, your accesses to $A'$ (which is $P'$ in the paper and is an "induced sub-poset" of $A$) are free. So the answer is that a chain decomposition of $A'$ is built without asking any new queries to $A$, only based on the relations in $A'$, which are already known. Then a new element is inserted by performing a binary search on each chain of the chain decomposition, and this is where $w\log n$ queries are performed.

Note that Theorem 6 relates to Figure 2 and not Figure 1. There the number of queries is decreased by querying asymptotically optimally, rather than blindly doing a binary search independently on each chain (which would ignore relations going between chains).


Measuring the connectedness of a graph, and applying it to NP problems I'm looking for a way to measure how interconnected a graph is.  It's well known that graphs can be broken down into connected components.  It seems, though, that even in the cases where the graph is made of only one connected component, we can measure how interconnected that component is.  Is it "almost" two components (if we would remove a small number of edges)? What is the correlation between edges (that is, if vertices A and B are each connected to C, is there a higher probability that A and B are themselves connected).  I don't know how to define this measure properly, but I'm sure there are existing measures already defined.

It would seem to me that this would be a great way to measure the difficulty of an instance of the SAT problem.  Representing variables as nodes and being in the same clause as edges, it would seem the difficulty of the problem is related to the interconnectedness of the graph.

A standard measure of "interconnectedness" is how expanding the graph is. There are several ways to define expansion that are all related. The algebraic way is by measuring the second largest eigenvalue (in absolute value) of the adjacency matrix. The largest eigenvalue is a graph in which all vertices have degree D is always D. If the second largest eigenvalue is much smaller than D, then every two sets of vertices in the graph have roughly as many edges between them as if the edges were chosen at random (this is the expanding mixing lemma).
For more info about graph expansion, see this course:
http://www.math.ias.edu/~boaz/ExpanderCourse/

If the graph is an expander, the entire graph is one big, very interconnected, component.
This is the case with random SAT instances that are believed to be hard (for the appropriate clauses ratio).


Given a type system T, and a type $A$ in that type system, is there an (effective) surjection from $\mathbb{N}$ onto the set of terms of that type? I assume that in hoping for an effective bijection, we run into undecidability issues, but intuitively, it seems like there should at least be a surjection from $\mathbb{N}$ to the terms of any type, since well-typed terms of type theories are essentially finite trees, the set of which has cardinality $\aleph_0$. So, given a type theory* $T$ and a (non-empty) type $A$ in that type theory, can we always construct such a surjection? If possible, I would like to get a reference describing such an algorithm, if anyone has explicitly described it.

* I suppose I should specify formally what I mean by type theory, but I am not aware of any name for "type theories in general," so what I mean is a system consisting of a finite number of axioms (or axiom schemas), and rules, where we say $t : T$ if any only if there is a deduction (which is a finite tree whose leaves are axioms, and whose edges are rules) with conclusion $t:T$. So, examples would be simple type theory, homotopy type theory, one of the various forms of Martin-Lof type theory, etc...

This question is related to mine, but what I am asking is more general.

One could ask the same of set theory: isn't the set of terms that can be written down countable? Why isn't there a surjection from $\aleph_0$ to any set?

The answer, of course, is in the difference between internal truth and external truth.

Externally, the set of well typed terms of type $A$ (say in the empty context) is recursively enumerable in any reasonable type theory (like MLTT), so there is an effective surjection from $\mathbb{N}$ to that set iff it is non-empty, by a classical result in recursion theory.

Internally however, it is generally not possible to prove that such a surjection exists. In particular, a bijection between say, $\mathbb{N}$ and $\mathbb{N}\rightarrow\mathbb{N}$ implies a contradiction by a simple diagonalization argument (see, e.g., here).

In fact the proof works even if we only require a retract instead of a bijection. However this doesn't preclude a surjection from $\mathbb{N}$ to $\mathbb{N}\rightarrow\mathbb{N}$! It's only necessary that this surjection does not have a right inverse (in set theory, these right inverses always exist, but the proof of that requires the axiom of choice).

It is in fact consistent, but not provable, to assume that such a surjection exists.


What is the best approximation for majority vote? The majority vote operation comes up fairly often in fault-tolerance (and no doubt other places), where the function outputs a bit equal to which ever value appears most frequently in the value of the input bits. For simplicity, let's assume that whenever the input contains an equal number of bits in state 0 and state 1, it outputs 0.

This can be generalized to dits where there are more than 2 possibilities for each input by returning the value which occurs most frequently in the input, and in the case of a tie, returning the most frequent value which comes first lexicographically. Let's call this function "plurality vote".

I am interested in the output of such a function when each input has a fixed probability distribution (and the distribution is the same for each dit in the input). Specifically I care about the following question.

  Given a set $S=\{S_1, S_2,... ,S_n\}$, if the set is independently
  randomly sampled $N$ times, with probability $p_i$ of choosing the
  $i^{th}$ element of $S$ each time, for a fixed choice of $v$ what
  is the probability that the plurality vote of these outputs $S_v$?

Now, it is straight forward to calculate the exact answer to the above question as a sum over multinomial distributions. However, for my purposes, this is less than ideal, and a closed for approximation would be better. So my question is:

  What closed form approximation to the above probability has the
  tightest bound on the maximum distance from the exact value?

If $p_v > p_i$ for all $i \ne v$, then

$$
\mathrm{Pr}[\mbox{outcome is different from $v$}] \leq \min_T \left(Pr[B(N, p_v) \leq T] + Pr[\forall i \ne v \quad B(N, p_i) \geq T]\right),
$$

where $B(n, p)$ is binomial distribution, and $T$ is an arbitrary threshold. Plugging $T = N (p_v + \max_{i \ne v} p_v) / 2$ and using Chernoff bounds, one can upper-bound this probability as $e^{-\Omega(N)}$.

Of course, if $p_v$ is not maximum, then you get the opposite picture. With overwhelming probability $v$ is not outcome.


Has anyone mixed linear algebra with formal language theory in this way? Let $G$ be the grammar:
$$
S \rightarrow aAb \\
A \rightarrow aA + a + \epsilon
$$

where $\epsilon$ is the empty string, $a,b$ are terminals and $S,A$ non-terminals with $S$ the start symbol.  Consider vectors of grammar rule RHS's, for instance the basic one $\nu = \begin{pmatrix} S\\A\\a\\b\\\epsilon\end{pmatrix}$.  Then $\nu$ is an eigenvector of some matrix that transforms vectors of grammar rule RHS's into the same.

Let $T =
\begin{pmatrix}
0 & 0 & 0 & aA & 0\\
0 & a & \epsilon & 0 & \epsilon \\
0 & 0 & \epsilon & 0 & 0 \\
0 & 0  & 0 & \epsilon & 0 \\
0 & 0 & 0 & 0 & \epsilon
\end{pmatrix} $

Then if we let $0$ represent the empty set and concatenation by it equals $0$, then $\nu \rightarrow T\nu$ is an eigenvector with eigenvalue $\epsilon$.

Unrelated, but a regular language is represented by $T$ with only terminals and $\epsilon$ in the matrix.

Edit

I'm interested in any ideas.  Thanks.

The approach you're describing is the generating function approach. By solving systems of polynomial equations, one can calculate the number of words of given length (generated by any non-terminal), and through it the corresponding asymptotics.

For regular languages one can directly use linear algebra to estimate the number of words of given length. The result is described in the Wikipedia article as well as here; see also this question.


In the context of regular languages, must the alphabet be finite? In The Theory of Parsing, Translation, and Compiling, Volume I, Section 0.2.1 (p.15 / 1972), Aho and Ullman casually write that "[a]n alphabet need not be finite or even countable, but for all practical applications alphabets will be finite."

However, in Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Section 1.5.1 (p.28 / 2007), Hopcroft, Motwani and Ullman state that "[a]n alphabet is a finite, nonempty set of symbols." Further, Sipser "define[s] an alphabet to be any nonempty finite set." (Introduction to the Theory of Computation, 3rd Edition, Section 0.2 (p.13 / 2013).)

Is it correct that an alphabet may be infinite, even uncountably so? If so, are there any resources that discuss infinite alphabets?

It makes sense in some contexts in mathematics to consider strings or languages over infinite alphabets. For instance, this concept is used in the strong version of Higman's lemma. But a finite automaton requires a finite alphabet, and only finitely many symbols can actually appear in a single regular expression. So, specifically for the context of regular languages, alphabets must be finite.

It's not important whether you achieve this by declaring that "alphabet" means a finite set (as HMU and Sipser do) or whether you allow infinite alphabets and instead put the requirement of finiteness elsewhere than the definition of that word (as AU do).


Is there a 'process algebra' to describe ACID transactions on a database? There appears to be this beautiful algebra to help you think through the implications of Communicating Sequential Processes by Hoare.

What I'm wondering, is there an equivalent algebra that helps you think through ACID transactions on a database, where one suceeds and another rolls back?

There is a paper by Van Beek called An Algebraic Approach to Transactional Processes which describes adding transactions to process algebra:

(a :~ 0 . a:~ a + 2) II (a:~ 1 a:~ a X 2) ((a :~ 0 . a:~ a + 2)) II ((a:~ 1 a:~ a X 2))

This paper even delves into isolation levels.

The author describes how in Communicating Sequential Processes (CSP), if you have a write blocked on a read, you can get into a deadlock scenario.

The author references another paper J.A. Bergstra, A. Ponse, and J.J. van Warne. Process algebra with backtracking which allows for rollback of a failed CSP operation.

There is discussion on the nature of transactions in K.P. Eswaran, J .N. Gray, R.A. Lorie, and 1.1. Traiger. On the notions of consistency and  predicate locks in a data base system. Communications of the ACM, 19(11)

The properties of transactions are described in ] J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques.

The acid properties of transactions are described in J. Gray. The transaction concept: Virtues and limitations and in T. Haerder and A. Reuter. Principles of transaction-oriented database recovery


Notable examples of the square root idea in complexity analysis There are a number of algorithms and data structures which exploit the idea that $\max \left\{k, n/k\right\}$ gets its minimum value at $k=\sqrt n$. Common examples include

baby-step giant-step algorithm for computing discrete logarithm in $O(\sqrt n)$,
static 2D orthogonal range counting in $O(\sqrt n)$ time and $O(n)$ memory,
priority queue with EXTRACT-MIN in $O(\sqrt[k] n)$ and DECREASE-KEY in $O(1)$,
colouring a 3-colourable graph with $O(\sqrt n)$ colours in polynomial time,

just to name a few.

While such algorithms often are suboptimal, they are easy to understand by students and good to quickly show that naive bounds aren't optimal. Also, square-root-idea data structures are sometimes more practical than their binary tree based counterparts because of cache friendliness (not considering cache-oblivious techniques). That's why I give a nice bit of attention to this topic while teaching.

I'm interested in more distinctive examples of this kind. So I'm looking for any (preferably elegant) algorithms, data structures, communication protocols etc which analysis relies on the square root idea. Their asymptotics do not need to be optimal.

There are $O(m^{3/2})$ triangles in any $m$-edge graph and that they can be found in $O(m^{3/2})$ time. There are many ways of doing this but I think one of the earliest is Itai and Rodeh (STOC 1977) who provide an algorithm that goes through a sequence of linear-time iterations, each of which removes a spanning forest from the graph. In the early iterations when the remaining forest has at least $n-k$ components, the algorithm removes at least $k$ edges per step, and in the late iterations when it has at most $n-k$ components, the maximum degree is $k$ and shrinks by at least one in each step. So the total number of iterations is at most $m/k+k$ and choosing the right tradeoff gives the overall bound of $O(\sqrt m)$ on iterations and $O(m^{3/2})$ on time.


Can a fully homomorphic encryption be used for oblivious code execution? After reading this answer a while ago, I took an interest in fully homomorphic encryption. After reading the introduction of Gentry's thesis, I started wondering if his encryption scheme could be used for oblivious code execution as defined in the third paragraph.

In a fully homomorphic encryption scheme we typically encrypt some data, send it to a hostile environment where a certain function is computed on the data, the result of which is then sent back (encrypted), without the adversary finding out what the received data or the result of the function is.

With oblivious code execution I mean that we encrypt a piece of code $C$ designed to solve some problem $P$ and send it to a hostile environment. The adversary wants to use $C$ to solve $P$, but we don't want him to know how $C$ works. If he has an input $I$ for $P$, he can encrypt $I$ and then use (some encryption scheme on) $C$ with $I$, which then returns the (not encrypted) output $O$ (the solution of $P$ for the input $I$). The encryption scheme makes sure the adversary never finds out how the piece of code works, ie to him it works like an oracle does.

The main practical use (I can think of) for such an encryption scheme would be to make piracy more difficult or even impossible.

The reason I think this may be possible using a fully homomorphic encryption scheme is because we can execute arbitrary circuits on encrypted data, in particular an universal Turing machine. We could then encrypt the code as if it were data and then use the circuit for an universal Turing machine on this encrypted data to execute the code.

I pose this as a question here because I don't know whether this idea is usable: I never got much further than the introduction of Gentry's thesis, and my knowledge about cryptography is limited. Also, I don't know if there already is a often-used term for oblivious code execution: I tried searching Google for the idea but not knowing the proper term I found nothing.

There are multiple problems I can think of which may cause problems with this approach. Firstly, if we use a fully homomorphic encryption without modification, the result of the computation ($O$) would be encrypted. It would therefore be useless for the adversary who wishes to use your code to solve $P$. While this could still be useful for, say, cloud computing, this is not what I want to achieve.

Secondly, because we're using circuits and not arbitrary Turing machines, we can't use arbitrary amounts of memory: we're limited to a predetermined amount of memory. This means that if we want to run a program in this way, it's memory footprint will always be the same, namely it's peak memory usage.

Lastly, the constants involved would almost certainly kill off any practical use of such a system, but I think the idea is interesting nonetheless.

Unfortunately, there is a result that theoretically forbids "oblivious code execution":
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (Im)possibility of Obfuscating Programs, ADVANCES IN CRYPTOLOGY — CRYPTO 2001.
Here are the links:

http://www.wisdom.weizmann.ac.il/~oded/p_obfuscate.html
http://eprint.iacr.org/2001/069
http://www.springerlink.com/content/telalqdcx3n600uf/

The abstract reads:

Informally, an obfuscator $\cal O$ is an (efficient, probabilistic) "compiler" that takes as input a program (or circuit) $P$ and produces a new program $\cal O(P)$ that has the same functionality as $P$ yet is "unreadable" in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice's theorem. Most of these applications are based on an interpretation of the "unreadability" condition in obfuscation as meaning that $\cal O(P)$ is a "virtual black box," in the sense that anything one can efficiently compute given $\cal O(P)$, one could also efficiently compute given oracle access to $P$.
In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible. We prove this by constructing a family of functions $\cal F$ that are inherently unobfuscatable in the following sense: there is a predicate $\pi$ such that (a) given any program that computes a function $f$ in $\cal F$, the value $\pi(f)$ can be efficiently computed, yet (b) given oracle access to a (randomly selected) function $f$ in $\cal F$, no efficient algorithm can compute $\pi(f)$ much better than random guessing.
We extend our impossibility result in a number of ways, including even obfuscators that (a) are not necessarily computable in polynomial time, (b) only approximately preserve the functionality, and (c) only need to work for very restricted models of computation $\rm{TC}$ $0$). We also rule out several potential applications of obfuscators, by constructing "unobfuscatable" signature schemes, encryption schemes, and pseudorandom function families.


NEXPTIME-completeness with more time for reductions One thing that surprised me when learning about complexity theory is that for a complexity class C, we tend to define C-complete using polynomial time reductions, even when C is a very large complexity class.

This definitely makes sense for P and NP, but how about EXPTIME and NEXPTIME?

So my question is this: What is the subset of NEXPTIME comprised of problems exp-time reducible from every other problem in NEXPTIME? If EXPTIME != NEXPTIME, is this class distinct from both NEXPTIME and NEXPTIME-complete?

The trouble with exponential-time reductions is that they may exponentially expand the input, and this leads to all sorts of weirdness.
So, to begin with, neither EXP nor NEXP is closed under exp-time reductions in the first place. The languages exp-time reducible to EXP-languages comprise EEXP (doubly exponential time, also written as 2-EXP) by an obvious padding argument, and likewise, the languages exp-time reducible to NEXP comprise NEEXP.
A related fact is that exp-time reductions are not closed under composition, hence the corresponding relation $\le_{\exp}$ between languages is not transitive: for example, if $L_0$, $L_1$, and $L_2$ are languages complete for P, EXP, and EEXP (respectively) under poly-time reductions, then $L_2\le_{\exp} L_1\le_{\exp}L_0$, but $L_2\nleq_{\exp}L_0$.
(The transitive closure of exp-time reductions consists of all Kalmár-elementary reductions, and likewise, the smallest class containing EXP or NEXP that is closed under exp-time reductions is ELEMENTARY.)
To answer the question, the classs of problems NEXP-complete under exp-time reductions is unconditionally different from either NEXP or from the class of usual NEXP-complete problems:
On the one hand, SAT is NEXP-complete under exp-time reductions, but since it belongs to $\mathrm{NP}\subsetneq\mathrm{NEXP}$ by the nondeterministic time-hierarchy theorem, it is not NEXP-complete under poly-time reductions.
(More generally, the class of languages NEXP-time complete under exp-time reductions includes all languages in NEXP that are NP-hard in the usual sense.)
On the other hand, the trivial languages $\varnothing$ and $\Sigma^*$ are not NEXP-complete under any kind of many-one reductions. If you want a nontrivial example, you have to assume $\mathrm{EXP\ne NEXP}$ (as any language in EXP exp-time reduces to any nontrivial language), but that is clearly also sufficient: if you take any nontrivial language $L\in\mathrm{P\subseteq NEXP}$, then $L$ is not NEXP-complete under exp-time reductions unless $\mathrm{EXP=NEXP}$.
If we restrict the exp-time reductions to time $2^{O(n)}$ (rather than $2^{n^{O(1)}}$) and refer to NE instead of NEXP, there is a simple characterization. The following are equivalent:

$L$ is NE-complete under exp-time (i.e., time-$2^{O(n)}$) reductions.

$L\in\mathrm{NE}$, and $L$ is hard for unary NP languages under poly-time reductions.

For 1→2, if $L_1\in\mathrm{NP}$ is a unary language, let $L_2=\{w\in\{0,1\}^*:1^w\in L_1\}$ be its binary encoding; then $L_2\in\mathrm{NE}$, thus there is a time-$2^{cn}$ reduction $f$ of $L_2$ to $L$. Then $x\mapsto f(|x|)$ is a reduction of $L_1$ to $L$ working in polynomial time $2^{c(\log n)}=n^c$.
For 2→1, if $L_2\in\mathrm{NE}$, its unary encoding $L_1=\{1^w:w\in L_2\}$ is in NP, thus $L_1$ reduces to $L$ via a poly-time reduction $f$. Then $w\mapsto f(1^w)$ is a $2^{O(n)}$-time reduction of $L_2$ to $L$.
For NEXP and time-$2^{n^{O(1)}}$ reductions, a similar characterization should work using hardness for unary nondeterministic quasipolynomial-time languages under quasipolynomial-time reductions.


Separation between coarse correlated equilibria and correlated equilibria I am looking for examples of techniques for proving price of anarchy bounds that have the power to separate the price of anarchy over coarse correlated equilibria (the limiting set of no-external-regret dynamics) from the price of anarchy over correlated equilibria (the limiting set of no-swap-regret dynamics). Are natural separations of this type known?

One obstruction towards separating these two classes is that the most natural (and common) way to prove price of anarchy bounds is to observe only that at equilibrium, no player has any incentive to deviate to playing his action at OPT, and to somehow use this to connect the social welfare at some configuration to the social welfare of OPT. Unfortunately, any proof that the price of anarchy over coarse correlated equilibria is small that only considers deviations of each player to a single alternative action (say the action from OPT) necessarily also holds for correlated equilibria, and so cannot provide a separation. This is because the only difference between a coarse correlated equilibrium and a correlated equilibrium is the ability of a player in a correlated equilibrium to simultaneously consider multiple deviations, conditioned on his signal of the play profile drawn from the equilibrium distribution.

Are such separations known?

Fix M>>1>>e and look at the following two player coordination game (both players get the same utility):

M   | 1+e  | 2e   |  e

1+e |  1   |  e   |  0

2e  |  e   |  M   | 1+e

e   |  0   | 1+e  | 1

The second and fourth row and column are strictly dominated so any correlated equilibrium cannot have them in its support, thus it would be on the sub-game:

M  |  2e

2e |  M

for which every correlated equilibrium would give each player more than M/2 utility.

On the other hand, consider the joint probability distribution giving probability 1/2 to each of the 1's, and thus utility 1 to each player.  The claim is that this is a coarse equilibrium.  In a coarse equilibrium the possible deviations of the row player are to one of the pure strategies independently of the outcome of the joint distribution.  Now if it is only known that the column player is mixing evenly between the 2nd and 4th column, then the maximum utility the row player can get is 0.5+e < 1, so deviation is not profitable.


Find an approximate argmax using only approximate max queries Consider the following problem.

  There are $n$ unknown values $v_1, \cdots, v_n \in \mathbb{R}$. The task is to find the index of the largest one using only queries of the following form. A query is specified by a set $S \subseteq \{1,\cdots,n\}$ and the corresponding answer is $\max_{i \in S} v_i$. The goal is to use as few queries as possible.

This problem is easy: We can use binary search to find the argmax with $O(\log n)$ queries. i.e. Build a complete binary tree with $n$ leaves corresponding to indices. Start at the root and walk down to a leaf as follows. At each node, query the maximum value in the right and left subtrees and then move to the child on the side with the larger answer. Upon reaching a leaf, output its index.

The following noisy version of this problem has come up in my research.

  There are $n$ unknown values $v_1, \cdots, v_n$. These can be accessed with queries in which a set $S \subseteq \{1, \cdots, n\}$ is specified and a sample from $\mathcal{N}(\max_{i \in S} v_i,1)$ is returned. The goal is to identify $i_* \in \{1, \cdots, n\}$ such that $\mathbb{E}[v_{i_*}] \geq \max_i v_i - 1$ using as few queries as possible. (The expectation is over the choice of $i_*$, which depends on both the coins of the algorithm and the noisy query answers.)

Suppose we try to solve this using the same binary search strategy as before (but with noisy answers). It is reasonably easy to show that this achieves $\mathbb{E}[v_{i_*}] \geq \max_i v_i - O(\log n)$ and that this is tight in the worst case. We can reduce the error to the desired $1$ by repeating each query $O(\log^2 n)$ times and using the average (which drives down the variance). This gives an algorithm using $O(\log^3 n)$ queries.

Is there a better algorithm? I conjecture that $O(\log^2 n)$ queries suffice. And I believe I can prove a $\Omega(\log^2 n)$ lower bound. Also, the problem becomes easy -- i.e. $\tilde{O}(\log n)$ queries via binary search -- under the promise that there is a $\Omega(1)$ gap between the largest value and the second-largest value.
If it helps, you can assume all the values are between $0$ and $O(\log n)$.

Extended comment of an idea or two toward a lower bound. Let $B = \Theta(\log n)$, say (though the best choice may be different), and let $\{v_1,\dots,v_n\} = \{\frac{1}{n}B, \dots, \frac{n-1}{n}B, B\}$. Consider drawing the input by picking a permutation of these values uniformly at random.

The idea should be that if we fix the indices of all values except for values $B$ and $\frac{n-1}{n}B$, then we should be able to show the difference in the algorithm's probability of picking one versus the other is very small: The variation distance between the results of the algorithms' queries is very small given the 50-50 distribution on assignments of these values to the two available indices and the results of any sequence of queries.

This argument holds for each pair of adjacent values, so we get a chain of constraints on the probability the algorithm picks the highest, second-highest, ... values. This gives an upper bound on the expected value of the algorithm, so we set that upper bound to $B-1$ and see what the number of queries has to be.

I couldn't improve on $\log n$ with the above approach yet, but I think you might get $(\log n)^2$ if you can leverage the fact that queries can't help with multiple steps at once. I.e. if a query changes when we move the highest value to a different index, then one of those times it it doesn't change when we move any other value to a different index.

Differential privacy might be helpful for one of these steps, e.g. if we only think about the case where we swap the location of the two highest values, the "sensitivity" of this query is just $\frac{B}{n}$ and then advanced composition might be helpful.

Sorry this is half-baked, but hope it can be useful!


Shortest path on a hypergraph with no leftovers In quantum computing, determining the code distance of a stabilizer code is similar to the shortest path problem on a hypergraph. Each node in the graph would be some sort of parity check performed by the code, and each hyperedge would be a set of parity checks a particular physical error flips. If you construct the graph correctly, paths between certain nodes will correspond to logical errors and the code distance will correspond to a shortest path because the shortest path corresponds to the minimum number of errors.
So that's the motivation for being interested in the shortest path problem on a hypergraph.

I did some preliminary searching for existing algorithms that solve this problem. Unfortunately, it seems that existing research is actually referring to a slightly different problem than what I had in mind. In particular, existing work seems to be happy to pass through edges that touch unrelated nodes an odd number of times. In the context of a code distance calculation this would be a bad idea, because it would cause parity check violations elsewhere in the graph. The "minimum length path" wouldn't successfully get back into the desired codespace.

The variant of the shortest hyperpath problem that I care about is as follows.
Let $n$ and $m$ be the start and end nodes.
Let $E$ be a set of hyperedges.
$E$ is a hyperpath between $n$ and $m$ if $n$ appears in an odd number of the hyperedges of $E$, $m$ also appears in an odd number of the hyperedges of $E$, and all other nodes appear an even number of times in the hyperedges of $E$.
I want $n$ and $m$ to be the only nodes whose corresponding parity check triggers when the corresponding errors from $E$ are applied.
The goal is to find the hyperpath with the minimum number of hyperedges.

Has there been previous work on this problem? Note that I'm mostly interested in the case where the hyperedge degree is bounded (e.g. the error graph of the surface code typically has no hyperedges with degree larger than 4, even with circuit level noise and two qubit gate errors).

This answer doesn't answer the question about previous work, but it does show the problem is NP-complete.

Lemma 1. Finding a shortest $s$-$t$ hyperpath (as defined in the post) in a given hypergraph is NP-complete, even in hypergraphs of hyperedge degree 3.

Proof. Clearly the problem is in NP.  It is NP-hard by the following reduction from 3D-matching.

Fix an instance of 3D matching -- a set of triples $X$ from universe $U=\{1,2,\ldots,3n\}$.  Given the instance, the reduction outputs the instance of Shortest $s$-$t$ Hyperpath in the hypergraph $G=(V,E)$ defined as follows.

First create the vertex set $V=\{b_0, a_1, b_1, a_2, b_2, a_3, b_3, \ldots, a_{3n}, b_{3n}\}$.  Define the hyperpath source and destination to be $s=b_0$ and $t=b_{3n}$.  Next, add $3n$ "path" hyperedges $$(b_0,a_1,b_1), (b_1,a_2,b_2), (b_2, a_3, b_3), \ldots, (b_{3n-1}, a_{3n}, b_{3n}).$$  Finally, for each triple $(i, j, k)$ in $X$, add hyperedge $(a_i, a_j, a_k)$.  This completes the reduction.

We'll show that there is an $s$-$t$ hyperpath of length at most $4n$ if and only if there is a 3D matching.

First suppose that there is a 3D matching $M$ (that is, an $n$-subset of $X$ such that each element in $\{1,\ldots,3n\}$ occurs in exactly one triple in $M$).  Then the $3n$ "path" hyperedges, together with the $n$ hyperedges $\{(a_i, a_j, a_k) : (i, j, k) \in M\}$ form the desired hyperpath.

Conversely, suppose there is such a hyperpath (from $b_0$ to $b_{3n}$).  By induction on the $b_i$ vertices, each of the $3n$ path hyperedges $(b_i, a_{i+1}, b_{i+1})$ must be in the hyperpath.  Then, since each vertex $a_1,\ldots,a_{3n}$ is in one such path hyperedge, each such vertex must also be in an odd number of other hyperedges in the hyperpath.  Those hyperedges must correspond to triples in $X$.  Each such hyperedge contains $3$ of the $a_i$ vertices, and the hyperpath has length $4n$ (or less), so there must be $n$ such hyperedges, and their corresponding triples must form a 3D matching. $~~\Box$

I suspect that even determining whether there exists any $s$-$t$ hyperpath is also NP-complete.

EDIT: I think the existence of an $s$-$t$ hyperpath can be determined in polynomial time by checking feasibility of this set of linear equations over $\mathbb{Z}_2$: introduce an indicator variable $x_e$ for each hyperedge $e$, then, for every vertex $v$ constrain $$\sum_{e \ni v} x_e = \begin{cases} 1 & \text{if } v\in\{s,t\} \\ 0 & \text{otherwise}.\end{cases}$$


Vector Addition Systems with finite "obstacles" A Vector Addition System (VAS) is a finite set of actions $A \subset \mathbb{Z}^d$. $\mathbb{N}^d$ is the set of markings. A run is a non-empty word of markings $m_0 m_1\dots m_n$ s.t. $\forall i \in \{0, \dots, n-1\}, m_{i+1}-m_i \in A$. If such a word exists we say that $m_n$ is reachable from $m_0$.

The problem of reachability for VASs is known to be decidable (but its complexity is an open problem).

Now let us assume that a finite set of forbidden markings (the obstacles) is given. I would like to know if the problem of reachability is still decidable.

Intuitively, the finite set of obstacles should interfere with paths only locally, so the problem should remain decidable. But it does not seem trivial to prove it.

EDIT. I will keep @Jérôme's answer as the accepted one, but I would like to add a follow-up question: what if the set of markings is $\mathbb{Z}^d$?

The idea is based on a discussion I got with Grégoire Sutre this afternoon.

The problem is decidable as follows.

A Petri net $T$ is a finite set of pairs in $\mathbb{N}^d\times\mathbb{N}^d$ called transitions. Given a transition $t=(\vec{u},\vec{v})$, we denote by $\xrightarrow{t}$ the binary relation defined on the set of configurations $\mathbb{N}^d$ by $\vec{x}\xrightarrow{t}\vec{y}$ if there exists a vector $\vec{z}\in\mathbb{N}^d$ such that $\vec{x}=\vec{u}+\vec{z}$ and $\vec{y}=\vec{v}+\vec{z}$. We denote by $\xrightarrow{T}$ the one step reachability relation $\bigcup_{t\in T}\xrightarrow{t}$. The reflexive and transitive closure of this relation is denoted by $\xrightarrow{T^*}$.

Let $\leq$ be the classical componentwise partial order over $\mathbb{N}^d$ and defined by $\vec{u}\leq \vec{x}$ if there exists $\vec{z}\in\mathbb{N}^d$ such that $\vec{x}=\vec{u}+\vec{z}$. The upward closure of a set $\vec{X}$ of $\mathbb{N}^d$ is the set ${\uparrow}\vec{X}$ of vectors $\{\vec{v}\in\mathbb{N}^d \mid \exists \vec{x}\in\vec{X}.\,\vec{x}\leq\vec{v}\}$. The downward closure of a set $\vec{X}$ is the set ${\downarrow}\vec{X}$ of vectors $\{\vec{v}\in\mathbb{N}^d \mid \exists \vec{x}\in\vec{x}.\,\vec{v}\leq\vec{x}\}$.

Notice that if $\vec{U}={\uparrow}\vec{B}$ for some finite set $\vec{B}$ of $\mathbb{N}^d$ and if $T$ is a Petri net, we can compute a new Petri net $T_{\vec{B}}$ such that for every configurations $\vec{x},\vec{y}$, we have $\vec{x}\xrightarrow{T}\vec{y}$ and $\vec{x},\vec{y}\in\vec{U}$ if, and only if, $\vec{x}\xrightarrow{T_{\vec{B}}}\vec{y}$. In fact, if $t=(\vec{u},\vec{v})$ is a transition, then for each $\vec{b}\in\vec{B}$, let $t_{\vec{b}}=(\vec{u}+\vec{z},\vec{v}+\vec{z})$ where $\vec{z}$ is the vector in $\mathbb{N}^d$ defined componentwise by $\vec{z}(i)=\max\{\vec{b}(i)-\vec{u}(i),\vec{b}(i)-\vec{v}(i),0\}$ for every $1\leq i\leq d$. Notice that $T_{\vec{U}}=\{t_{\vec{b}} \mid t\in T\,\vec{b}\in\vec{B}\}$ satisfies the requirement.

Now, assume that $T$ is a Petri net, $\vec{O}$ the set of obstacle. We introduce the finite set $\vec{D}={\downarrow}\vec{O}$. Observe that we can compute effectively a finite set $\vec{B}$ of $\mathbb{N}^d$ such that ${\uparrow}\vec{B}=\mathbb{N}^d\backslash\vec{D}$. Let $R$ be the binary relation defined over $\mathbb{N}^d\backslash \vec{O}$  by $\vec{x} R \vec{y}$ if $\vec{x}=\vec{y}$, or there exists $\vec{x}',\vec{y}'\in \mathbb{N}^d\backslash \vec{O}$ such that $\vec{x}\xrightarrow{T}\vec{x}'\xrightarrow{T_{\vec{B}}^*}\vec{y}'\xrightarrow{T}\vec{y}$.

Now, just observe that if there exists a run from the initial configuration $\vec{x}$ to the final one $\vec{y}$ that avoid the obstacle $\vec{O}$, then there exists one that avoid the obstacle in $\vec{O}$ and that passes by configurations in $\vec{D}\backslash \vec{O}$ at most the cardinal of that set. Hence, the problem reduces to select non-deterministically distinct configurations $\vec{c}_1,\ldots,\vec{c}_n$ in $\vec{D}\backslash \vec{O}$, fix $\vec{c}_0$ as the initial configuration $\vec{x}$, $c_{n+1}$ as the final one $\vec{y}$, and check that $\vec{c}_j R \vec{c}_{j+1}$ for every $j$. This last problem reduces to classical reachability questions for Petri nets.


How to write a negative review for a conference paper? This is related to the general question of "How do I referee a paper?". I am reviewing a paper for a conference, and this paper should be rejected, because it is not significant enough for publication and has flaws in some of its technical details. The paper is not wrong, but the ways in which it is right are not very interesting. How do I write a negative review in such a settings? More importantly, how do I do this as a non-senior researcher?

As an example, they make part of their argument through numerics, but I can prove the same result analytically. The analytic treatment is longer than what I can include in a review. I know the author's emails (the review process is not blind both ways), should I email them? This is a conference, so there is no time for revisions, will they be mad at me for rejecting their paper? Should I email them before or after they receive the reviews?

The paper is also sparsely cited, and does not connect strongly to existing literature. I am familiar with many aspects of the relevant literature, how detailed should I make my recommendations on further reading/references?

To extract the general questions:

How does a junior researcher write a negative review?
What should you do if you have specific technical comments/improvements that are too long for a standard review?

I think this is too much of a duplicate of the other question, but my comment got too long.

Firstly, the review process is blind, so you simply have to do the best that you can. Be objective, be polite, give good reasons – see other question.
There is probably no such thing has having technical comments/improvements that are too long for the standard review, unless you will end up rewriting the paper. Authors tend to appreciate comments, even if they mean more work. If the paper is borderline and is worth improving, then give as many comments as you have time for.
If you have additional comments that you want to send to the authors, consult with the chair/editor before contacting the authors. Perhaps your comments can be sent anonymously via the chair/editor.
Papers get rejected, we learn to live with it. The best you can do is provide good comments to help the authors improve the paper for next time round. Authors may get mad, but they don't get even.
If the paper is terrible, just save your time and don't bother with all the comments. Write a sufficiently convincing review giving reasons why the paper should be rejected, point out that there are many typos and other mistakes, but don't enumerate them all.
On the other hand, if you are presenting and proving an alternative axiomatisation of their results to the degree that you are not only rewriting their paper, but lifting their results to a whole new level, then you should consult the chair/editor to see what to do. Maybe you should get credit for your contribution. You certainly should never write up your results independently, not until the paper has appeared in print.


Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$? Background

  We know that $P^{\#P} \subseteq PSPACE$.

  In addition, we known from
  Toda's theorem that $PH \subseteq P^{\#P}$.

  For more background on $\#P$, see here:
  https://en.wikipedia.org/wiki/Sharp-P

Question

  Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

On popular request, here is my comment as an answer:

There is an oracle separating $\mathrm{PP}$ from $\mathrm{PSPACE}$: Jacobo Toran, A combinatorial technique for separating counting complexity classes, ICALP 1989. The best result for $\mathrm{P}^\mathrm{PP}$ that I know is a conditional result by Heribert Vollmer: Relating polynomial time to constant depth. TCS, 207: 159-170, 1998.


Irreducible languages This is not necessarily a research question. Just a question out of curiosity:

I am trying to understand if one can define "irreducible" languages.
As a first guess I call a language L "reducible" if it can be written as
$L = A \cdot B$ with $A \cap B = \emptyset$ and $|A|,|B|>1$, otherwise call the language "irreducible". Is it true:

1) If P is irreducible, A,B, C are languages such that $A\cap B = \emptyset$, $P \cap C = \emptyset$ and $A\cdot B = C\cdot P$, then there exists a language $B' \cap P = \emptyset$ such that $B = B'\cdot P$? This would correspond in integers to the lemma of Euklid and would be usefull to prove uniqueness of "factorization".

2) Is it true that every language can be factored in a finite number of irreducible languages?

If someone has a better idea on how to define "irreducible" language, I would like to hear it. (Or is there maybe already a definiton of this, which I am unaware of?)

There is the notion of primality of a language. It asks whether L can be written as $L_1 \cdot L_2$ where neither factor contains the empty word. A language is prime if it cannot be written in this form.

For a given regular language, represented by a DFA, it is shown in [MNS] that it is PSPACE-complete to decide primality.

[MNS] Wim Martens, Matthias Niewerth and Thomas Schwentick,
"Schema design for XML repositories: complexity and tractability", 2010. doi:10.1145/1807085.1807117


Linear Time Maximum Clearance Computation on a Grid Graph? I have a uniform NxN grid with a non-empty subset of vertices marked as obstacles.  My goal is to compute, for each non-obstacle vertex, the "maximum clearance" from the obstacle set.  In other words, the radius of the largest circle center at the vertex not overlapping with any obstacle.  Or the nearest "gas station" for each vertex.  [sorry if there is some standard terminology I should have used]

I would like a linear-time algorithm to compute this.  Can anyone help?

My gut feeling is that it is possible.  I have searched but didn't get a straight answer, but I know the following:

(1) if the distance metric is Manhattan, this can be solved by a simple flooding.

(2) I know a little bit about Level Set, and it may help, but is there something simpler?

(3) I understand Fortune's elegant sweeping algorithm to calculate Voronoi diagram in O(n log n), where n is the number of points.  For my particular application, since the wavefront never contains more than N vertices, the complexity is O(N log N).  The O(log N) is due to updates to a binary tree.  I hope this can be reduced from O(N log N) to O(N) because of the nature of my problem?

I am willing to do this in multiple passes in order to get linear time.  For example, one pass each for N, E, S, W, which hopefully somewhat simplifies Fortune's algorithm.  Also I am not interested in the Voronoi vertices but rather the distances of the grid vertices from the obstacles.

Is this a known, solved problem?  If so, source code or (more detailed) pseudo code?

If not, so far what I have in mind is to do this in two passes (Eastbound sweep and Westbound sweep):

Consider the East-bound sweep, I update one column of N vertices at a time.  There is a set of exactly N "back" vertices (each is assigned an X coordinate, or -infinity if they are out of scope (OOS)) such that a partition is defined by the bisecting lines between immediate non-OOS neighbors (similar to Fortune).  In other words, each non-OOS vertex is given a range [ys, ye] which together partitions [0, N - 1].  I don't maintain a binary tree of non-OOS vertices.  Instead, I always keep them in an array of size N.

When we move to the next column, the partition changes.  The partition is recalculated, and if a vertex's range becomes negative (ys > ye), the vertex is marked as OOS accordingly.  Hopefully, this can be done in O(N) time and hence the total runtime is O(NxN).

Am I going in the right direction?  Actually by spelling it out it already helps a bit :D

All the sites are themselves grid points too, right? So I think it should work to compute the Delaunay triangulation of the sites in linear time using the word-model algorithm of Buchin and Mulzer (FOCS 2009), dualize to get the Voronoi diagram, and then fill out the grid neighbors within each Voronoi cell. The Delaunay part should be linear in the number of sites (its bottleneck is integer sorting, but for the magnitude of the integers in your problem sorting is easily done in time linear in the grid size).

To fill out the grid points within a single Voronoi cell, partition the cell along the lines connecting the cell's site to its neighbors and then find the grid points within each of the resulting quadrilaterals. That way it requires only a constant number of comparisons to determine whether any particular grid point belongs to the quadrilateral. Some quadrilaterals may be empty of grid cells but the total number of quadrilaterals formed in this way is linear so there isn't too much wasted work in the empty ones.


Deterministic communication complexity vs partition number Background:
Consider the usual two-party model of communication complexity where Alice and Bob are given $n$-bit strings $x$ and $y$ and have to compute some Boolean function $f(x,y)$, where $f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$.
We define the following quantities:

$D(f)$ (the deterministic communication complexity of $f$): The minimum number of bits that Alice and Bob need to communicate to compute $f(x,y)$ deterministically.
$Pn(f)$ (the partition number of $f$): The logarithm (base 2) of the smallest number of monochromatic rectangles in a partition (or a disjoint cover) of $\{0,1\}^n \times \{0,1\}^n$.

A monochromatic rectangle in $\{0,1\}^n \times \{0,1\}^n$ is a subset $R \times C$ such that $f$ takes the same value (i.e., is monochromatic) on all elements of $R \times C$.
Also note that the partition number is different from the "protocol partition number", which was the subject of this question.
See the text by Kushilevitz and Nisan for more information. In their notation, what I have defined to be $Pn(f)$ is $\log_2 C^D(f)$.
Note: These definitions are easily generalized to non-Boolean functions $f$, where the output of $f$ is some larger set.

Known results:
It is known that $Pn(f)$ is a lower bound on $D(f)$, i.e., for all (Boolean or non-Boolean) $f$, $Pn(f) \leq D(f)$.
Indeed, most lower bound techniques (or perhaps all?) for $D(f)$ actually lower bound $Pn(f)$. (Can anyone confirm that this is true of all lower bound techniques?)
It is also known that this bound is at most quadratically loose (for Boolean or non-Boolean functions), i.e., $D(f) \leq (Pn(f))^2$. To summarize, we know the following:

$Pn(f) \leq D(f) \leq (Pn(f))^2$

It is conjectured that $Pn(f) = \Theta(D(f))$. (This is open problem 2.10 in the text by text by Kushilevitz and Nisan.)  However, to the best of my knowledge, the best known separation between these two for Boolean functions is only by a multiplicative factor of 2, as shown in "The Linear-Array Conjecture in Communication Complexity Is False" by Eyal Kushilevitz,    Nathan Linial, and Rafail Ostrovsky.
More precisely, they exhibit an infinite family of Boolean functions $f$, such that $D(f) \geq (2 - o(1)) Pn(f)$.

Question:

What is the best known separation between $Pn(f)$ and $D(f)$ for non-Boolean functions? Is it still the factor-2 separation referenced above?

Added in v2: Since I haven't received an answer in a week, I'm also happy to hear partial answers, conjectures, hearsay, anecdotal evidence, etc.

This question has just been resolved! As I mentioned, it was known that

  $Pn(f) \leq D(f) \leq (Pn(f))^2$,

but it was a major open problem to show that either $Pn(f) = \Theta(D(f))$ or that there exists a function for which $Pn(f) = o(D(f))$.

A few days ago this was resolved by Mika Göös, Toniann Pitassi, Thomas Watson (http://eccc.hpi-web.de/report/2015/050/). They show that there exists a function $f$ which satisfies

  $Pn(f) = \tilde{O}((D(f))^{2/3})$.

They also show an optimal result for the one-sided version of $Pn(f)$, which I'll denote by $Pn_1(f)$, where you only need to cover the 1-inputs with rectangles. $Pn_1(f)$ also satisfies

  $Pn_1(f) \leq D(f) \leq (Pn_1(f))^2$,

and they show that this is the best possible relation between the two measures, since they exhibit a function $f$ which satisfies

  $Pn_1(f) = \tilde{O}((D(f))^{1/2})$.


How can I reduce this kind of BinPack algorithm? ("MinBreak-BinFill") I have a special variant of BinPack problem.
Does anyone know how to reduce this problem to something known?

The problem:
There are items $I$ and bins $B$ in specific quantity and size.

$|I| ∈ ℕ, |B| ∈ ℕ$

$s : (I ∪ B) → ℕ$

The sum of all item-sizes is not less than the sum of all bin-sizes.

$∑ _{i∈I} s(i) ≥ ∑ _{b∈B} s(b)$

Each bin has to be filled with items or parts of items so that it is filled completely. $s(b,i)$ is the size of that part of $i$ that is in $b$, or $0$ iff not.

$∀ b ∈ B, i ∈ I: s(b,i) ∈ ℕ ∪ \{0\}$

$∀ i ∈ I: ∑ _{b∈B} s(b,i) ≤ s(i)$

$∀ b ∈ B: ∑ _{i∈I} s(b,i) ≥ s(b)$

The goal is to minimize the number of item-parts used to fill all bins.

$numparts = |\{ (b,i) ∈ B×I\ |\ s(b,i)>0 \}|$

$minimize\ numparts$

Example 1:

$I=[100,5]$

$B=[10,10,7]$

$allparts=[10,10,7,73,5]$ after partitioning the first item

$usedparts=[10,10,7]$ because we do not need the other parts anymore

$numparts=3$

Example 2:

$I=[8,14,5]$

$B=[10,10,7]$

$allparts=[8,10,2,2,5]$ after partitioning the second item

$usedparts=[8,2,10,5,2]$ because we need all to fill the bins

$numparts=5$

Perhaps the corresponding decision problem is NP-complete; given an instance of SUBSET-SUM:

Given $K, x_1,...,x_n$ does exist $A \subseteq \{x_1, x_2, ..., x_n\}$ s.t. $\sum_{x_i \in A}x_i = K$?

Suppose that $k > 0, x_i > 0$ and let $k' = \sum_{i=1..n} x_i - K$

Now, if you pick two bins $B_1, B_2$ with sizes $k$ and $k'$, then $n$ items of sizes $x_i$ can be packed with cost $numparts = n$ if and only if the corrsponding SUBSET-SUM problem has a solution.


Holant problems and holographic reduction: simple graphs or multigraphs? From what I can understand, Holographic reductions for Holant problems are used to show #P-hardness or polynomial time computability of certain counting problems on undirected graphs that have very restricted forms (for instance, 3-regular graphs, or 2-3-regular bipartite graphs).

My concern is about the confusion between the use of the word "graph" to mean either a) a simple graph, without self-loops and parallel edges or b) a multigraph, that can have self-loops and parallel edges (i.e., multiple edges between the same pair of vertices). I will first expose my problem by examples, then ask more precisely my questions.

Examples:

In the paper Cai, Lu and Xia, Holographic Reduction, Interpolation and Hardness, 2012, the authors provide a dichotomy for all problems of the form $\mathrm{Holant}([x,y,z][t_1,t_2,t_3,t_4])$, so over 2-3-regular bipartite graphs. They do not specify if they talk about simple graphs or multigraphs. A search for "self loops" reveals that they might be using graphs with self loops, but this is not very explicit (and what about parallel edges?). However nowhere else in the paper this distinction is discussed, and all the gadgets they use seem to be simple graphs (in the Appendix).
In Tyson Williams' thesis, by default the graphs considered are multigraphs (see page 4). He also says that Holant problems always consider multigraphs, suggesting that the first paper I cited considers multigraphs. In some of his results, he mentions the distinction between the two notions of graphs: for instance, Theorem 10.2.7 states that some problem is hard on 3-regular multigraphs, and he shows in Theorem 10.2.8 that the same problem is aslo hard on 3-regular simple graphs. By looking at the proof you see that the trick used is specific to this particular problem.
In the paper Xia, Zhang and Zhao, Computational complexity of counting problems on 3-regular planar graphs, 2007, the abstract talks about 3-regular graphs. When I first read it I thought that they are considering simple graphs, but actually I did not find a place where they say this.

At this point, I want to say that this post is not a critic to the authors of all these papers (I know that this kind of details can be annoying to present rigorously), the goal is just to clarify what is happening here.

Questions:

1) Do all the PTIME results of, say, the first paper I cite, work for multigraphs?

2) Do all the hardness results of that paper work for 2-3-regular simple bipartite graphs?

3) If not, is there a simple general fix so that the hardness results work for simple graphs, or does one have to find an ad hoc patch for each one of these problems? (for example, as in Theorem 10.2.8 of Tyson Williams' thesis)

4) If yes, do they also work for 2-3-regular simple graph that also satisfy this special property: no two nodes of the partition of degree 2 have the same neighbors. This condition would insure that, when you take a 2-3-regular simple graph that satisfies this, then contracting the nodes in the partition of degree 2 would always give a 3-regular simple graph. (without this condition, we could end up with parallel edges.)

This post is also related to this post and this one, where the same kind of confusion arose (a positive answer to question 4) would solve these problems). I decided to create a new question because I realized that the problem is more general that the ones exposed in these posts.

My concern is about the confusion between the use of the word "graph" to mean either a) a simple graph, without self-loops and parallel edges or b) a multigraph, that can have self-loops and parallel edges (i.e., multiple edges between the same pair of vertices).

In the literature about Holant problems, the word "graph" should be read as "multigraph" unless otherwise stated.  As you noticed, I tried to be more explicit about this in my thesis.  In my experience, different areas of math use terms mostly consistently within their own area but in ways that would be contradictory when considering multiple areas and read strictly.

In your first example, the proper notation is $\mathrm{Holant}([x,y,z]|[t_1,t_2,t_3,t_4])$.  This means that the input graphs are bipartite with one part having only vertices of degree 2 (and assigned the symmetric binary function $[x,y,z]$) and the other part having only vertices of degree 3 (and assigned the symmetric ternary function [t_1, t_2, t_3, t_4]).

Also (and I am sure you know this, but to be clear), a bipartite graph cannot have self loops.  So if a bipartite graph is not a simple graph, then it is because it has parallel edges.

1) Yes

2) Not immediately.  I think you have correctly observed that their reductions work for simple graphs.  It remains to verify if the hard problems that they were reduced from are also hard when further restricted to simple graphs.

3) There is no general fix.  In general, you have to reduce from problems that are hard for simple graphs.

4) Gadget 2 does not satisfy your condition.  Consider $N_1$.  The only two vertices of degree 2 without dangling edges have the same neighbor set.


What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$ What is the complexity of the following problem? (e.g. best-known running time, space, best upper bound in terms of complexity classes, etc.)

Input: A multivariate polynomial $f$ with coefficients over $\mathbb{Z}$
Decide: Is there a rational zero of $f$?

What about the complexity where $f$ is the translation of a Boolean formula under the standard translation? (viz. $t(x) = x$, $t(f \vee g) =  1-(1-t(f))(1-t(g))$ and $t(f \wedge g) = t(f) t(g)$; thus, a $\{0,1\}$ assignment satisfies $f$ iff it satisfies the polynomial equation $t(f)=1$.)

As already pointed out by Emil Jeřábek in the comments, this is Hilbert's Tenth Problem over the rationals, whose computability is a notorious open question.
In this case, note that the Boolean formula $f$ is satisfiable iff $t(f)$ has an integer zero: a satisfying assignment, when treated as 0s and 1s, gives an integer zero, and conversely, given an integer zero $\vec{\alpha}$, taking it mod 2 gives a satisfying Boolean assignment (this follows from the form of the translation $t(\bullet)$). Now, given a rational solution to $t(f)=0$, if all of the denominators involved are odd, then we may still take it mod 2 to get a Boolean solution, so we have

  Boolean solution iff integer solution iff rational solution w/ odd denominators

Therefore, deciding the existence of integer roots or of rational roots with odd denominators for polynomials of the form $t(f)$ is $\mathsf{NP}$-complete.

This leaves us with the question of how hard it is to decide existence of a rational root of $t(f)$ in general (that is, without restriction on the denominators). I do not know anything more about this question than about Hilbert's Tenth Problem over $\mathbb{Q}$ (addressed in Q1).


Formalization of dependent record types/kinds in MLTT or variant thereof? Has anyone formalized Pollack's Dependently Typed Records in Type Theory ? Agda would be preferred, but anyone close to MLTT would work.  Weaker versions would be fine too, i.e. what Luo dubs 'dependently kinded records would be appreciated as well.

Full reference:

@Article{Pollack2002,
author="Pollack, Robert",
title="Dependently Typed Records in Type Theory",
journal="Formal Aspects of Computing",
year="2002",
month="Jul",
day="01",
volume="13",
number="3",
pages="386--402",
abstract="The language Pebble of Burstall and Lampson proposed dependent types as the underlying principle in a unified framework to explain facilities for programming in the large, such as modules and signatures, as well as for programming in the small. This proposal soon extended to large scale formal proof development as well. In fact, the functional approach to modularity has turned out to be a hard problem, which is still far from a fully satisfactory solution. This paper discusses aspects of this approach, including representations of records, informative signatures, sharing, and subtyping. My main contribution in this paper is to show that structures with dependent types and manifest fields (roughly ML style modules) are internally definable in a type theoretic framework extended with inductive-recursive definition. This shows that powerful modules follow from general principles without module-specific assumptions.",
issn="1433-299X",
doi="10.1007/s001650200018",
url="https://doi.org/10.1007/s001650200018"
}

I do not know how much of the paper it covers but we do have a module based on it in the standard library:

https://agda.github.io/agda-stdlib/Data.Record.html


Numerical accuracy of superpositions in quantum computers I am new to the topic of quantum computers (though I am very familiar with both quantum and computers, and I have studied Shor's paper about his eponymous algorithm at some point). Still, I have the following question, which pertains to the practical realizability of quantum computers and is probably related to qubit error correction:

To set up the question, note that classical computers are typically built on the principle that information is best encoded digitally, e.g. by two discrete bits 0 and 1. Every now and then, however, somebody claims that analog computing is better, where information is encoded in a continuous quantity $a \in [0,1]$, e.g. a voltage between $0V$ and $1V$. If this quantity were an exact real number, then it is well known that we could solve many problems really fast. However, such schemes do not work in practice, because continuous quantities are always subject to measurement error and do not allow arbitrary precision.

Quantum computers, on the other hand, rely on the principle that information is encoded in qubits $|0\rangle$, $|1\rangle$ and arbitrary superpositions thereof, like $0.6|0\rangle + 0.8|1\rangle$. In light of the above remark about analog computers, the appearance of arbitrary precision real numbers in the superposition raises a red flag. Of course, typical models of quantum computation account for this problem by allowing only a fixed (select) set of universal gates (e.g. the Hadamard gate and a few others). Then, the precision required in the coefficients of the superposition need not be larger than the number of gates used in the computation.

However, this still leaves open the question of what happens if we increase the number of gates. Then, the precision needed to represent the coefficients of the superposition will also increase. But due to unavoidable random fluctuations, it seems inevitable to me that an intermediate calculation might use slightly inaccurate results, e.g. one qubit may take the value $0.0447|0\rangle + 0.999|1\rangle$ instead of $1.0|1\rangle$ as desired. Further manipulations with gates may distort the end result drastically.

  How can I make sure that errors in intermediate qubit results do not propagate?

The problem I perceive is that the precision per qubit superposition is fixed, and may at some point be too low to accommodate more gates, very similar to the problem of precision of an analog computer.

Apologies if this is a standard question in a misguided disguise, this has probably been answered already. I would appreciate any pointer.

EDIT: Let me try to reformulate my question. Consider the following model of computation: Just like with a quantum computer, each qubit is a superposition $a|0\rangle + b|1\rangle$. However, we now postulate that the computer has only finite precision, i.e. that the superposition coefficients $a$,$b$ must be contained in a discrete set of values, for example $a,b,\in \{0.1,0.2,\dots,1.0\}$. This is equivalent to a "rounding error", where each unitary operation "rounds" the coefficients to the ones from the discrete set of values. Clearly, this model of computation is entirely classical, as each qubit can only take a finite number of superpositions, which we can encode by a classical bit string.

  How do quantum computers go beyond the "finite precision coefficients" while avoiding the "analog computers with infinite precision are too powerful" problem?

It appears that my question about "numerical accuracy" / error correction for qubits is nicely answered in the bible of quantum computation, M.A. Nielsen and I.L. Chuang, "Quantum Computation and Quantum Information", Oxford Univ. Press, 2010, chapter 10, in particular section 10.3.1. This book is great, I think that it is both very readable and very thorough!

The key point is the following: Yes, errors may be introduced during the calculation so that the superpositions becomes more and more "inaccurate" in small ways. Then, it may seem very strange that in many papers on error correction in quantum computation, authors often only correct for a few types of errors, in particular bit flip errors ($|0\rangle\leftrightarrow|1\rangle$) and sign flip errors ($|1\rangle\to -|1\rangle$). What about small deviations in superposition coefficients? The answer is: If you correct for the former kind of error, then the latter ones are accounted for as well! (Theorem 10.2 in the book.) The reason is that if you account for bit and sign flip errors, then you automatically account for any linear combination of these errors, which now includes small deviations in the coefficients as well. Hurray!

In general, when thinking about qubits, it is not a good idea focus on the fact that the superposition coefficients can be arbitrary real numbers. Sure, Shor's algorithm requires a fairly precise cancellation of these coefficients. But a better point of view is to think of a qubit as something much closer to a classical bit, which has only two discretes states $0$ and $1$, than to a high precision real number from the interval $[0,1]$. The point is that when we try to physically measure a qubit, we only ever get one of two discrete answers (albeit with interesting probabilities), so it's pretty much discrete.

If we compare analog and quantum computers, then it is fair to say that an analog computer tries to encode as much information as possible in high precisions real numbers, whereas a quantum computer has essentially just discrete bits with a little bit of "quantum extra". Then the key point to the computational power of quantum computers is not that a qubit contains real numbers, but that qubits combine by taking the tensor product of Hilbert spaces ($H_1 \otimes H_2$) whereas analog computers combine by just adding more real numbers, corresponding to the direct sum of vector spaces ($V_1 \oplus V_2$). The "little quantum extras" combine into something useful if we add many of them.

Also note that at the time of this writing, it is totally unclear whether quantum computers are really more powerful than classical computers. As far as I am aware of, there is no "genuine" (no oracles) problem that can be solved efficiently only with a quantum computer, i.e. where we have proof that a classical computer can't do it efficiently. Quantum computers certainly don't solve the $NP = P$ problem.


Is relativization well-defined? According to BGS theorem [1], there is an oracle $A$ such that $P^A\neq NP^A$.

If the relativization operation $B\mapsto B^A$ was a well-defined function,
one would expect that from $B^A\neq C^A$ one would be able to conclude that $B\neq C$,
e.g. $P\neq NP$ would follow from BGS. However, $P\neq NP$ is still open.

Does that mean that relativization is not a well-defined function?

If so, do we have any example of two provably different relativizations of the same complexity class?

[1] T. P. Baker, J. Gill, and R. Solovay, "Relativizations of the P =? NP Question"

You are exactly right. The relativization operation $B\mapsto B^A$ is not well defined.
P and PA are independently defined objects. The names are suggestive, but you cannot formally define PA from the set P. (You can define P from PA by setting A to be the empty set.)

Think of PA as being some kind of generalization of P, which equals P when A is empty, but otherwise may be different. Now if you only know the set P, it is not clear how to generalize this to get PA. As an analogy, if I asked you to generalize the real numbers, it's not clear what generalization I'm looking for. Am I thinking of fields, rings, vector spaces, etc.? The reason this happens is that while P is merely a set of languages, PA is defined in terms of a machine. This machine has the property that when A is empty it decides exactly the same languages as P. You could come up with some other machine, let's call it QA, which also has the property that when A is empty decides the same languages as P. This does not mean that PA = QA for all A. This would be analogous to asserting that if f(0)=g(0), then f and g are the same function.

Perhaps this post by Terence Tao will be helpful.


What is the fastest way to check for set inclusion? Given $n$ subsets $S_1,\ldots,S_n$ of $\{1,\ldots,d\}$.

Check whether there are sets $S_i,S_j$ with $S_i \subsetneq S_j$. (If so, find an example, if not, simply say "no")

The trivial solution to this problem goes through all pairs of sets and checks inclusion for a pair in time $O(d)$, so the overall runtime is $O(n^2 d)$. Can this problem be solved faster? Is there a name for it in the literature?

You cannot solve it in $O(n^{2-\epsilon})$ time for any constant $\epsilon>0$ unless the Strong Exponential Time Hypothesis is false.

That is, if we had such an algorithm, we could solve $n$-variable CNF Satisfiability in $O((2-\epsilon')^{n})$ time for some $\epsilon'>0$.
The reason is that we could divide the variables in two equal parts $P_1$ and $P_2$ of $n/2$ variables each. For each part we construct
a family $F_1$ and $F_2$ respectively of subsets of the clauses in the following way. For each assignment we add a subset consisting of the
clauses not satisfied by the assignment. This construction runs in $poly(n)2^{n/2}$ time.

To finish the construction, we note that the original CNF instance has a solution iff there is a subset in $F_1$ which is disjoint to some subset in $F_2$.

Adding some extra elements to your ground set in addition to the ones for each clause, it is not too hard to embed this disjointness problem as a question of
set inclusion. You basically take the complements of the subsets in $F_1$. To make sure two sets in $F_1$ isn't counted as an inclusion you add a code from an anti-chain
on the extra elements. Another anti-chain code (on other extra elements of the ground set) is used on the subsets of $F_2$ to make sure no pair of subsets from $F_2$ form an inclusion.
Finally, all sets formed from $F_1$ includes all elements of $F_2$'s anti-chain codes.

This is a set inclusion question on $2^{n/2+1}$ subsets on a $d=poly(n)$ ground set. The argument basically goes back to some early paper of Ryan Williams (can't remember which).


directed or bidirected in relation to mssp (Multiple source shortest path) Firstly I wanted to ask. If I have a undirected graph and split all the edges into two directed edges is it still called directed or does it become bi-directed?

The main question is i have a graph with n sources all in the same graph until now I thought I could use the mssp method provided by Klein in this paper but it says that the graph must be a directed graph. Yet if I have an undirected graph and split each edges into two components with same weight I don't think it will be able to solve the problem or it does not matter?

Due the bidirection of the graph,  will it have the first source visit each and every node without the other sources implying that I can't adapt the graph such that I can have a Shortest path tree as if I ran a dijkstra on the other sources does it?

Also I wanted to make sure does this method gets all the shortest path trees? because i was getting confused.

Klein algorithm is able to compute all the shortest path trees for specific starting nodes found on a single face (lets agree on that). Its secret is that it will do adaptations of specific darts found in the dual graph. if it is an undirected graph turning it into directed graph will become a bi directed graph by the following:
can you still state that such graph is directed and also bi directed?

A directed graph is called bi-directed if the there is a mapping reversal() that maps each edge e=(v,w) to a reversal edge (denoted as reversal(e)) such that the following holds:

reversal(e)=(w,v), that is, the reversal edge of e indeed is reversely directed, so reversal() deserves its name.

reversal(reversal(e))=e, that is, also in the presence of multiedges always two edges correspond to one another.

e is different from reversal(e), that is, also in the presence of self-loops each self-loop edge has a different self-loop edge as its reversal edge. (don't have self loops)

Each edge e occurs as the reversal edge reversal(e') of a different edge e', that is, the mapping is bijective.

would you still be able to state that a I directed graph is also a directed graph?

First, let's be completely clear about the definition of the multiple-source shortest path problem.  The input consists of the following:

a directed planar graph $G = (V,E)$ with $n$ vertices;
a non-negative weight $w(e)$ for every directed edge $e$;
an embedding of $G$ into the plane; and
a distinguished face $f$ of this planar embedding (the "outer" face).

Klein's algorithm computes a compressed representation of all shortest-path trees rooted at vertices of the designated face $f$, in $O(n\log n)$ time and space.  This representation allows us to retrieve the shortest-path distance from any vertex on $f$ to any other vertex in $O(\log n)$ time.

An explicit representation of these shortest-path trees would require $\Theta(kn)$ space, where $k$ is the number of vertices in $f$; in the worst case, this space bound is $\Theta(n^2)$.  Klein's observation, at least intuitively, is that the shortest-path trees for two adjacent source vertices are nearly identical; his data structure stores only the differences between adjacent trees.

Klein's algorithm works just fine for bidirected and undirected graphs.  For purposes of the algorithm, a bidirected graph is just a directed graph where the reversal of every arc is another arc, and an undirected graph is jut a bidirected graph where every arc has the same weight as its reversal.  In other words, a bidirected graph is a directed graph whose adjacency matrix is symmetric, and (in this context) an undirected graph is just a directed graph whose weighted adjacency matrix is symmetric.  Klein's algorithm requires no modifications whatsoever to handle these special cases.

Klein's algorithm does not compute shortest-path distances between arbitrary pairs of vertices; in every pair, the source vertex must lie on the designated face.  For a solution to the more general problem, see Sergio Cabello's paper "Many distances in planar graphs" [SODA 2006 and Algorithmica 2012].

You might also check out my upcoming journal paper with Sergio Cabello and Erin Chambers, which describes a different multiple-source shortest-path algorithm, which also works for higher-genus graphs.


Complexity of the Schönhage–Strassen algorithm In the Wikipedia article, the complexity is listed as $O(n \cdot \log (n) \cdot \log (\log (n)))$, where $n$ is the number of bits.

Would the real bound be given by setting $n=\frac{b}{w}$, where $b$ is the number of bits and $w$ is the word length in the computer? i.e., if I assume that numbers of size $\log (n)$ can be multiplied in $O(1)$ time, then can two numbers of size $r \log (n)$ be multiplied in $O(r \cdot \log (r) \cdot \log( \log (r)))$?

What you are actually asking is for the performance of the Schönhage–Strassen algorithm in the unit cost RAM (rather than its bit complexity). This is covered in Fürer's paper How Fast Can We Multiply Large Integers on an Actual Computer?, likely written with similar motivation to yours.


Flow networks: Push flow on either edges but not both! I have a flow network with random capacities on edges, is there some way to add a constraint of the type (push flow on either one of these two edges but not on both)?

I'm not sure if this is correct or not, but I think the maximum independent set problem can be reduced to the problem I stated above, let's call our graph $S$ and make a flow network $G$ with a source node $src$ and sink node $sink$.

For each vertex $v \in V(S)$ we make an edge $(src \rightarrow sink)$ with capacity 1 in $G$ and for each edge $(A \rightarrow B) \in E(S)$ we add the constraint to pass flow on either the edge that corresponds to $A$ or $B$ in $G$ . The resulting maximum flow on $G$ is the cardinality of the maximum independent set on $S$ and the set of saturated edges in $G$ are the nodes in the maximum independent set of $S$ .

Is my intuition correct or not?

You can model the constraint of not using two edges (u,v) and (u,w) of capacity one simultaneously in a flow network by introducing a vertex u' and an edge (u',u) with capacity one, but I'm not aware of a more general way to do this without extending the concept of a flow network.

If your idea for reducing the maximum independent set problem to a network flow problem worked, you'd have the basis for a proof that P=NP, which is extremely unlikely.


Difference between Stencil -structures and Cellular Automata Category-theoretically? Definitions

  Stencil =
  "For a given point, a stencil is a pre-determined set of nearest
  neighbors (possibly including itself)."
  (source)

  Wikipedia's definition (source) =

It looks like CA (cellular automata) is a broader (and perhaps more sexy fuzzy populist) concept while the stencil (S) is more rigorous. Suppose a torus -topology in a grid and a simple structure where each state depends only on the next state (some transition rule, 4 neighbors but only next state matters). This I think is a Stencil, Cellular automaton, a grid, a mesh, easily described with Markov Chain -- and a structure. Now I am confused! So many different words for the same thing? Please, add references to quantify this concept, many authors seem to use different words for the same thing -- not sure what it is, some structure with function -definitions -- perhaps there exists some easy category-theoretic description for them?

If this is too elementary question, I would be happy about some reference covering definitions rigorously and doing some comparisons.

Perhaps related

Automatic Stencil Code Generation Ph.D. Thesis Proposal here. The author behind the last paper here, researching something about stencil things and a lot of perhaps related publications here, related to the last author.
Fey, Dietmar et al. (2010) Grid-Computing: Eine Basistechnologie für Computational Science. Page 439. (Source)
Complex Systems from the Perspective of Category
Theory: I. Functioning of the Adjunction Concept here

Judging from the source you provided, there appear to be two key differences:
(1) stencils have numeric values in each cell and update the cells with functions defined numerically (typically using continuous functions) while cellular automata typically have only a finite set of values per cell and use functions that in general do not arise from numerical methods, and (2) stencils are updated by a sweep across the grid while in cellular automata generally all cells are updated simultaneously.


Smoothed analysis of approximation algorithms Smoothed analysis has been applied many times to understand the runtime of exact algorithms for many problems like linear programming and k-means. There are fairly general results in this realm, for example Heiko Röglin and Berthold Vöcking, Smoothed analysis of integer programming, 2005.
Some of these general results seem to rely on isolation lemmas in order to produce an instance with a unique optimal solution.
Assuming $\mathsf{NP}\ne \mathsf{ZPP}$, this paper rules out the existence of smoothed polynomial time algorithms for $\mathsf{NP}$-hard problems.
Some work has been done on smoothed analysis for approximation algorithm ratios.
There is Rao Raghavendra, Probabilistic and Smoothed Analysis of Approximation Algorithms, 2008 which attempts to give an improved approximation bound for the Christofides algorithm with smoothed analysis. No explicit approximation ratio is given, though.
Is there any reason for why hardness of approximation results should limit the approximation ratios of algorithms that run in smoothed polynomial time? Do the results in Heiko Röglin and Berthold Vöcking's paper also apply for approximation algorithms?

The paper by Bläser, Panagiotou, and Rao deals with concentration of the tour produced by Christofides' algorithm. No average-case approximation ratio is claimed, except for some experimental results.

The paper by Röglin and Vöcking (Math. Program., 2007) and an earlier paper by Beier and Vöcking (SIAM J. Comput., 2006) roughly state that smoothed polynomial time is equivalent to randomized pseudo-polynomial time. Here, pseudo-polynomial means running-time polynomial in the input size and the magnitude of the coefficients that are perturbed. This rules out smoothed polynomial complexity for strongly NP-hard optimization problems (unless NP=ZPP).

Concerning smoothed analysis and approximation, there are only very few papers that address specific problems or algorithms (Englert, Röglin, and Vöcking for the 2-opt heuristic for TSP; Bläser, Manthey, and Rao as well as Curticapean and Künnemann for partitioning heuristics; Karger and Onak for multi-dimensional packing). However, I am not aware of any structural connections between inapproximability and smoothed analysis.


what does "lifting" mean? I see in certain places "lifting computation" or "lifting" mentioned. I haven't been able to accurately define for myself what is meant by that.

This usually comes up in computer science context. Any ideas what it means?

Computer science (especially theory B) has many connections to category theory, and that is the usual context for lifting. The basic idea is that you might have two objects $X$ and $Y$ that interact in a very intuitive way for you, and so it is easy to define a good morphism $f: X \rightarrow Y$. You might have a more complicated object $Z$ that is easy to relate to $Y$, but it is not obvious how it relates to $X$. So you will look at a morphism $g: Z \rightarrow Y$ and then use category theory to lift $f$ to $Z$ using $g$.

In other words, you will find a morphism $h: X \rightarrow Z$ such that $gh = f$. For more info, see these slides.


Polynomial approximation algorithm for set cover with assumption We want to cover $n$ elements with some sets from $S_1, …, S_m$ (classical set cover).

We furthermore suppose that any element belongs to at least $k$ sets and want to find a set cover with cardinal at most $\mathcal{O}\left(\frac{m \cdot log(n)}{k}\right)$.

For $k=1$, the classical greedy algorithm works, but after that I'm stuck.

I ended up finding the answer.

I'm going to prove the greedy algorithm yields the correct answer.

Count the number of membership relationships. There are at least $n\cdot k$, so one set must contain more than $\frac{n\cdot k}m$ elements.

After one step of greedy algorithm, there are less than $n_1 = n - \frac{n\cdot k}m = n \left(1 - \frac km\right)$ elements left.

At the second step we remove at least $n_1(1-\frac{k}{m-1})$.

We are guaranteed to terminate when $n~\Pi_{i=0}^j \left( 1-\frac{k}{m-i}\right) < 1$, ie $\log(n) + \sum_{i=0}^j \log\left(1-\frac{k}{m-i}\right) < 0$.

Since $\log(1-x) < -x$, $\log(n) < \sum_{i=0}^j \frac{k}{m-i}$ is sufficient.

We are looking for the smallest $j$ such that:

$ m-j < \exp(\log(m) - \frac{\log(n)}{k}) = \frac{m}{n^\frac1k}$

$\Longleftrightarrow j > m\left(1-\frac{1}{n^\frac1k}\right) = m\left(1-\frac{1}{\exp(\frac{log(n)}{k}}\right)$

Now, $1-\frac{1}{\exp(x)} ≤ x$ by convexity, hence $j > \frac{m \log(n)}{k}$ is sufficient.


Milestones in counting complexity I want to prepare a small presentation with some of the most important results in Counting complexity, continue with recent ones and finish with some interdisciplinary results ,probably with other complexity theory areas. I have some thoughts already. Any paper propositions that should definitively be in?

There has been a series of breakthroughs on Dichotomy Theorems by Professor Jin-Yi Cai https://rjlipton.wordpress.com/2012/01/20/is-it-time-to-declare-victory-in-counting-complexity/
Another dichotomy theorem https://rjlipton.wordpress.com/2014/06/23/counting-edge-colorings-is-hard/

https://rjlipton.wordpress.com/2011/02/14/classifying-papers-on-classifying-problems/

https://rjlipton.wordpress.com/2009/06/09/computing-very-large-sums/