On-policy/Off-policy Offline/Online Evaluation: Which would be an example of Online Off-Policy Evaluation? In the context of the following question:
off-policy and offline policy reinforcement learning
, it can be concluded that off-policy/on-policy learning can be orthogonal to an online/offline sampling scenario.

I am having trouble connecting these concepts to the idea of evaluating an RL approach (target/behavior policy) aimed to be deployed in a real-world environment (e.g. a web application).

In this case, I believe that the online evaluation would be to test the RL approach when deployed and that the offline evaluation would be to use historical data or a simulation of the real-world environment.

Following this assumption, examples of the different evaluation combinations can be:

Off-policy/offline evaluation: evaluate the target policy using a historical dataset collected with a policy other than the target policy.
On-policy/online evaluation: experience used to evaluate is collected by following the target policy sampling directly from the real-world environment.

But it is hard for me to think of examples for the other combinations:

On-policy/offline evaluation: data used to evaluate the target policy is collected by following the target policy on a simulation of the real-world environment. Does this make sense?
Off-policy/online evaluation: I can't think of an example that makes sense, i.e., if the target policy can be evaluated directly with the real-world environment, why use a different behavior/target policy to sample experience?

Note that my question is in the context of evaluation, i.e. the goal is only to evaluate the target policy and not to learn a new policy.

I am wondering if any of these ideas make sense and if anyone can think of an example for the case of Off-policy/online evaluation?

Online/Offline learning

Whether your algorithm learns online or offline is governed by when the agent's experience is able to contribute to its learning.

For example, consider value iteration algorithms for action values. If you use Monte Carlo methods to calculate your value updates, then you'd be performing offline learning as the agent will have to reach the end of an episode to calculate the full MC return for any action value. The full Monte Carlo return and the action value definition (expected return) is given by

$G_t = R_{t+1} + γ R_{t+2} + γ^2 R_{t+3} + … + γ^{T-t-1} R_T$, and

$ q(s,a) = E[R_{t+1} + γ R_{t+2} + γ^2 R_{t+3} + … + γ^{T-t-1} R_T \ |\ S_t = s, A_t = a]$

where $T$ signifies last time step of the episode, and $\gamma$ is the discount factor

On the other hand if you use Temporal Difference methods, the action values can be updated right away by bootstrapping to already calculated values, making the learning online. We use the recursive definition of return to get recursive definition of value (expected return) in TD methods.

$G_t = R_{t+1} + γ G_{t+1}$, and

$ q(s,a) = E[R_{t+1} + γ\ q(S_{t+1}, a') \ |\ S_t = s, A_t = a]$

On-policy/Off-policy learning

This depends on the update function you're using to move your state/action value estimates towards the real expected return of the defintion.

For example, in case of SARSA (update action values to evaluate behavior policy) with 1-step TD updates, we have the update function as

$Q_{t+1}(S_t, A_t) = Q_t(S_t, A_t) + α (R_{t+1} + γ\ Q_t(S_{t+1}, A_{t+1}) - Q_t(S_t, A_t))$

Since this method uses the action value for that action which is actually performed in the next state ($a' = A_{t+1}$ for $q(s,a)$ estimate), the estimates will converge to action values for the behavior policy, and not for the optimal policy. Hence, it is a form of on-policy learning.

Now if you consider Q-learning, the update function is

$Q_{t+1}(S_t, A_t) = Q_t(S_t, A_t) + α (R_{t+1} + γ\ max_{a'} Q_t(S_{t+1}, a') - Q_t(S_t, A_t))$

Here, we don’t need to know what action is to be taken from the next state, $S_{t+1}$.
We use the maximum q-value across all actions for the next state to calculate our estimate ($a' = argmax_{a'} Q_t(S_{t+1}, a')$ for $q(s,a)$ estimate).
Because of this, the agent learns q-values for the optimal or greedy policy, regardless of the one it is following currently ($A_{t+1}$ doesn’t affect the q-value update). Hence, it is an example of off-policy learning.

Given this information, an example of On-policy/offline evaluation would be simple Monte Carlo learning, where action values are calculated as the average of Monte Carlo returns over multiple episodes.

And an example of Off-policy/online evaluation would be Q-learning with 1-step TD updates. Because of bootstrapping in TD updates, it is online, and due to the nature of the update function (given above), it estimates optimal values.


A Combinatorial algorithm for trivalent graph isomorphism (except some small subclass) I am currently working on the isomorphism of graphs, hyper-graphs. The graph isomorphism of graphs of degree at most three (trivalent) known to be in $P$. E.M Luks has given an algorithm for trivalent graph isomorphism, which is algebraic in nature.

  Question : Is there a known graph isomorphism algorithm for graphs of degree at most three other than E.M Luks algorithm? Is there exist a combinatorial algorithm for trivalent graph isomorphism?

I thought of using Weisfeiler-Lehman procedure, but it fails on regular graphs.

Edit : I will use $k$-Weisfeiler-Lehman procedure; it is going to fail on the very small class of graphs called iso-regular graphs, Now I will divide this class into two classes;bounded tree width and unbounded tree width. For bounded tree width we already have a polynomial time (FPT algorithm) algorithm, unbounded tree-width class can be further divided into two subclasses; planar and non-planar, for planar, we already have a combinatorial algorithm that runs in $O(n^2)$ time, Now we are left with non-planar unbounded tree width iso-regular graphs. One thing is that I am not able to come up with an example of a graph, which is  a non-planar unbounded tree width iso-regular graph of degree at most three.

$k$-iso-rgular graphs or $k$-tuple regular graphs :  Graphs in which the number of common neighbours of any k-tuple of a given isomorphism type is constant (for instance, strongly regular graphs are 2-isoregular).

Even higher-dimensional WL is known not to work in poly time on graphs of degree 4 (Cai-Furer-Immerman). I do not know if higher-dimensional WL might work on graphs of degree 3, but I also don't know of a result ruling this out either. Aside from Babai's general algorithm (which is quasi-polynomial, not polynomial), I do not know another algorithm for degree 3 other than the one you mention.


Maximize the expected number of "losers" - Is it NP-hard? I am trying to find a reduction for a problem that seems NP-hard:

Let me start from a toy example. Consider 3 elements, $a$, $b$, and $c$.
You want to choose two pairs out of the three pairs and compare the
two elements of each pair. There is a true underlying ordering of
the elements, which we don't know. Our objective is to pick the comparisons
that will maximize, in expectation, the number of elements that
will "lose" at least one comparison.

For example, lets assume that we choose $(a,b)$ and $(b,c)$.
There are four possibilities:

(1) $a>b$ and $c>b$ with probability $\frac{2}{6}$ ($2$ out of the $3!$ possible permutations respect $a>b$ and $c>b$)

(2) $a>b$ and $c<b$ with probability $\frac{1}{6}$

(3) $a<b$ and $c>b$ with probability $\frac{1}{6}$

(4) $a<b$ and $c<b$ with probability $\frac{2}{6}$

In the case of (1), only $b$ loses at least one comparison, in (2), $b$ and $c$ lose at least one comparison, and so on.
The expected number of elements losing at least one comparison is:

$\frac{2}{6} * 1 + \frac{1}{6} * 2 + \frac{1}{6} * 2 + \frac{2}{6} * 2 = 1\frac{2}{3}$

Note that the outcome of each comparison is based on the true ordering, which we don't know..

In this toy example, any two pairs give the same expected number of "losers".
In its general form, the problem states that we have $n$ elements, and we can ask
for $b$ comparisons (the problem becomes interesting when $b>\frac{n}{2}$). Making
it even more general, we can have the outcome of previous comparisons as input and try to maximize the "losers" out of those elements that still haven't lost any comparison. I am interested in the second, more general, case but I feel that even without the previous comparisons' outcome, the problem is still NP-hard.

The most helpful result I have found until now, is that counting linear extensions of a partially ordered set is #P-complete [1].

I would greatly appreciate any ideas about a reduction, or any obvious reduction that I can not see.

Thank you!

[1] Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order 8 (3): 225–242, paper

Look at the graph that is formed by the comparisons. Each element corresponds to a vertex. If an element is a vertex of degree $d$, then the probability that it will be the lowest in at least one of these comparisons is the probability that it is not larger than all of its neighbors. This probability is $d/(d+1)$.

Now, expectation is linear. This means that the expected number of losers is $$ \sum_{v \in G} \frac{d_v}{d_v+1}.$$ To illustrate, with your example there is one vertex of degree 2 and two of degree 1, so the expected number of losers is $\frac{2}{3} + \frac{1}{2} + \frac{1}{2} = \frac{5}{3}.\ $

It is easy to prove that this quantity is maximized when the degrees of the vertices are all as close to equal as possible, so the vertex degrees all are either $d$ or $d+1$ for some $d$.


2-NEXPTIME-complete problems We have a problem and we found an algorithm that appear to be 2-nexptime.

I would like to find known 2-nexptime-complete problems in order to find a lower bound.

I found in literature mainly two such problems:

whether PCP as a solution of size less than $2^{2^n}$
and the tilling problem for a square of size $2^{2^n}$

However I was unable to encode these problems in mine. So I would like to know other 2-NEXPTIME-complete problems, first to have more intuition on this class, and second in the better case prove a lower bound.

I do not provide here the problem on purpose in order to have a broad overview of 2-NEXPTIME.

Thanks

The obvious N2Exp problem is of course the word acceptance problem for 2exp time bounded nondeterministic Turing machines. Using this might be as hard/easy as 2exp tiling, because the simulation of such a Turing machine computation in essence also requires you to define a double-exponentially large grid (2exp many configurations of memory tapes of length 2exp each) that is then filled in a non-deterministic way. In practice, showing N2Exp lower bounds often boils down to constructing such a grid (and making sure that it is not a tree or something else of insufficient structure). The "N" (nondeterminism) is often an inherent part of the problem and not so difficult to get once you have a large enough grid (if not, one would maybe shoot for 2exp at first).

Another practical N2ExpTime-complete problem is reasoning in expressive description logics (DL). In particular, the DL $\mathcal{SROIQ}$ that is underlying the W3C OWL 2 Web Ontology Language standard is N2ExpTime-complete (Yevgeny Kazakov: RIQ and SROIQ Are Harder than SHOIQ. KR 2008: 274-284). Now this is probably not a problem you want to use in reductions, since the definition of the logic is a bit unwieldy because of its many features. The actual lower bound proof for $\mathcal{SROIQ}$ has also been done by reduction to 2-exp tiling. However, depending on your problem, the construction given for $\mathcal{SROIQ}$ could be inspiring to see how to craft such large grids.

The tiling also shows another general pattern: N2Exp really is like NP, you just need to find a way to encode even larger problem instances very efficiently. In principle, you could try to scale up any NP problem. The reason why tiling is nice is that you only need to scale the size of the grid in this case (which is rather uniform).

On the other hand, if your problem is possibly only 2ExpTime-complete, then you could get away with an exponentially space-bounded alternating Turing machine simulation. If you have troubles building a 2exp grid, but you can get to exponential sizes, then this might be worth a try.


How hard is it to count the number of local optima for a problem in PLS? For a polynomial local search problem, we know that at least one solution (local optimum) must exist. However, many more solutions could exist, how hard is it to count the number of solutions for a PLS-complete problem? I am particularly interested in the decision problem: does this PLS-complete problem's instance have two or more solutions?
Does the complexity depend on which PLS-complete problem we choose? If so then I would be particularly interested in weighted 2SAT (as defined in [SY91] and [Rou10]). I know that counting the number of satisfying solutions for 2SAT is #P-complete, but at first glance it seems like local optima of weighted 2SAT and solutions for 2SAT don't have all that much in common.
I also know that for PLS's cousin PPAD, [CS02] shows that counting the number of Nash equilibria is #P-hard. This suggests that similar PLS problems like counting the number of pure-strategy equilibria in congestion games, would also be hard.
References
[CS02] Conitzer, V., and Sandholm, T. (2002). Complexity results about Nash equilibria. IJCAI-03. cs/0205074.
[Rou10] T. Roughgarden. (2010). Computing equilibria: A computational complexity perspective. Economic Theory, 42:193-236.
[SY91] A.A. Schaeffer and M. Yannakakis. (1991). Simple local search problems that are hard to
solve. SIAM Journal on Computing, 20(1):56-87.

Consider the maximum matching problem in bipartite graphs. The family of feasible solutions consists of all matchings, and local search is performed via finding augmenting paths. The problem belongs to PLS since an augmenting path can be found in polynomial time if a current matching is not maximum, and maximality can be checked in polynomial time. Any local optimum is a maximum matching (i.e., global optimum). However, it is #P-hard to compute the number of maximum matchings in a bipartite graph.

Since a local optimum can be found in polynomial time, the problem is unlikely to be PLS-complete. So, I'm afraid this is not an intended answer (your question restricts to PLS-complete problems). However, I should point out that counting the number of local optima can be hard even though one local optimum can be found efficiently.


Reverse Chernoff bound Is there an reverse Chernoff bound which bounds that the tail probability is at least so much.

i.e if $X_1,X_2,\ldots,X_n$ are independent binomial random variables and $\mu=\mathbb{E}[\sum_{i=1}^n X_i]$. Then can we prove $Pr[\sum_{i=1}^n X_i\geq (1+\delta)\mu]\geq f(\mu,\delta,n)$ for some function $f$.

Here is an explicit proof that a standard Chernoff bound is tight up to constant factors in the exponent for a particular range of the parameters. (In particular, whenever the variables are 0 or 1, and 1 with probability 1/2 or less, and $\epsilon\in(0,1/2)$, and the Chernoff upper bound is less than a constant.)

If you find a mistake, please let me know.

Lemma 1. (tightness of Chernoff bound)
Let $X$ be the average of $k$ independent, 0/1 random variables (r.v.).
For any $\epsilon\in(0,1/2]$ and $p\in(0,1/2]$,  assuming $\epsilon^2 p k \ge 3$,

(i)
If each r.v. is 1 with probability at most $p$, then
$$\displaystyle
\Pr[X\le (1-\epsilon)p]
~\ge~
\exp\big({-9\epsilon^2 pk}\big).$$

(ii)
If each r.v. is 1 with probability at least $p$, then
$$\displaystyle
\Pr[X\ge (1+\epsilon)p]
~\ge~
\exp\big({-9\epsilon^2 pk}\big).$$

Proof.
We use the following observation:

Claim 1. If $1\le \ell \le k-1$, then
$\displaystyle {k \choose \ell} ~\ge~ \frac{1}{e\sqrt{2\pi\ell}} \Big(\frac{k}{\ell}\Big)^{\ell} \Big(\frac{k}{k-\ell}\Big)^{k-\ell}$

Proof of Claim 1.
By Stirling's approximation,
$i!=\sqrt{2\pi i}(i/e)^ie^\lambda$ where $\lambda\in[1/(12i+1),1/12i].$

Thus, $k\choose \ell$, which is  $\frac{k!}{\ell! (k-\ell)!}$, is at least
$$
\frac{\sqrt{2\pi k}\,(\frac{k}{e})^k}
{  \sqrt{2\pi \ell}\,(\frac{\ell}{e})^\ell
~~\sqrt{2\pi (k-\ell)}\,(\frac{k-\ell}{e})^{k-\ell} }
\exp\Big(\frac{1}{12k+1} - \frac{1}{12\ell} - \frac{1}{12(k-\ell)}\Big)$$
$$
~\ge~
\frac{1}{\sqrt{2\pi\ell}} \Big(\frac{k}{\ell}\Big)^{\ell} \Big(\frac{k}{k-\ell}\Big)^{k-\ell}e^{-1}.
$$
QED

Proof of Lemma 1 Part (i).
Without loss of generality assume each 0/1 random variable in the sum $X$
is 1 with probability exactly $p$.
Note $\Pr[X\le (1-\epsilon)p]$ equals the sum $\sum_{i = 0}^{\lfloor(1-\epsilon)pk\rfloor} \Pr[X=i/k]$,
and $\Pr[X=i/k] = {k \choose i} p^i (1-p)^{k-i}$.

Fix $\ell = \lfloor(1-2\epsilon)pk\rfloor+1$.
The terms in the sum are increasing,
so the terms with index $i\ge\ell$
each have value at least $\Pr[X=\ell/k]$,
so their sum has total value at least
$(\epsilon pk - 2) \Pr[X=\ell/k]$.
To complete the proof, we show that
$$(\epsilon pk - 2) \Pr[X=\ell/k] ~\ge~ \exp({-9\epsilon^2 pk}).$$

The assumptions $\epsilon^2pk\ge 3$ and $\epsilon\le 1/2$
give $\epsilon pk \ge 6$,
so the left-hand side above is at least $\frac{2}{3}\epsilon pk\, {k \choose \ell} p^\ell(1-p)^{k-\ell}$.
Using Claim 1,
to bound $k\choose \ell$,
this is in turn at least $A\, B$
where
$A =  \frac{2}{3e}\epsilon p k/ \sqrt{2\pi \ell}$
and
$
B=
\big(\frac{k}{\ell}\big)^\ell
\big(\frac{k}{k-\ell}\big)^{k-\ell}
p^\ell (1-p)^{k-\ell}.
$

To finish we show $A\ge \exp(-\epsilon^2pk)$ and $B \ge \exp(-8\epsilon^2 pk)$.

Claim 2.  $A \ge \exp({-\epsilon^2 pk})$

Proof of Claim 2.
The assumptions $\epsilon^2 pk \ge 3$ and $\epsilon\le 1/2$
imply
(i) $pk\ge 12$.

By definition, $\ell \le pk + 1$.
By (i), $p k \ge 12$.
Thus, (ii) $\ell \,\le\, 1.1 pk$.

Substituting the right-hand side of (ii) for $\ell$ in $A$ gives
(iii) $A \ge \frac{2}{3e} \epsilon \sqrt{p k / 2.2\pi}$.

The assumption, $\epsilon^2 pk \ge 3$,
implies $\epsilon\sqrt{ pk} \ge \sqrt 3$,
which with (iii) gives (iv) $A \ge \frac{2}{3e}\sqrt{3/2.2\pi} \ge 0.1$.

From $\epsilon^2pk \ge 3$ it follows that (v) $\exp(-\epsilon^2pk) \le \exp(-3) \le 0.04$.

(iv) and (v) together give the claim. QED

Claim 3.   $B\ge \exp({-8\epsilon^2 pk})$.

Proof of Claim 3.
Fix $\delta$ such that $\ell=(1-\delta)pk$.
The choice of $\ell$ implies $\delta\le 2\epsilon$,
so
the claim will hold as long as $B \ge \exp(-2\delta^2pk)$.
Taking each side of this latter inequality to the power $-1/\ell$ and simplifying,
it is equivalent to
$$
\frac{\ell}{p k}  \Big(\frac{k-\ell}{(1-p) k}\Big)^{k/\ell-1}
~\le~
\exp\Big(\frac{2\delta^2 pk}{\ell}\Big).
$$
Substituting $\ell= (1-\delta)pk$ and simplifying, it is equivalent to
$$
(1-\delta)  \Big(1+\frac{\delta p}{1-p}\Big)^{\displaystyle \frac{1}{(1-\delta)p}-1}
~\le~
\exp\Big(\frac{2\delta^2}{1-\delta}\Big).
$$
Taking the logarithm of both sides and using $\ln(1+z)\le z$ twice,
it will hold as long as
$$
-\delta\, +\,\frac{\delta p}{1-p}\Big(\frac{1}{(1-\delta)p}-1\Big)
~\le~
\frac{2\delta^2}{1-\delta}.
$$
The left-hand side above simplifies to $\delta^2/\,(1-p)(1-\delta)$,
which is less than $2\delta^2/(1-\delta)$ because $p\le 1/2$.
QED

Claims 2 and 3
imply $A B \ge \exp({-\epsilon^2pk})\exp({- 8\epsilon^2pk})$.
This implies part (i) of the lemma.

Proof of Lemma 1 Part (ii).
Without loss of generality assume each random variable is $1$ with probability exactly $p$.

Note $\Pr[X\ge (1+\epsilon)p] = \sum_{i = \lceil(1-\epsilon)pk\rceil}^n \Pr[X=i/k]$.
Fix $\hat\ell = \lceil (1+2\epsilon)pk \rceil - 1$.

The last $\epsilon pk$ terms in the sum
total at least  $(\epsilon pk-2)\Pr[X=\hat\ell/k]$,
which is at least $\exp({-9\epsilon^2 pk})$.
(The proof of that is the same as for (i), except with $\ell$ replaced by $\hat\ell$
and $\delta$ replaced by $-\hat\delta$ such that $\hat\ell = (1+\hat\delta)pk$.)
QED


Are the Actor Model and Process Algebra "equivalent"? I often see casual mention that the Hewit/Agha Actor Model is equivalent in capability to process algebra, like CSP, CCS and ACP. Ie, one can be implemented in the other. Is there a paper that actually contains the proof of this? I'm specifically looking for a citable reference.

This question is too vague to admit a clearcut answer, but it points towards a fascinating research field. The key problem is that neither is the actor model formally well-defined, nor is the notion of equivalency between (formalised) models of computation clear. Defining what expressivity of programming languages means precisely is a wide open problem, particularly for models of concurrent computation. It's unlikely that there is one clearcut notion of expressivity. Instead, language expressivity would appear to be parametric in properties of interest. Joachim Parrow's paper Expressiveness of Process Algebras gives an overview of the problem area, and explains some approaches that have been used to tackle it. There's even an annual conference -- Express -- dedicated to this question.

Process calculi such as CCS, CSP or π-calculi were developed in parts to offer a formalisation of actors, but are themselves of varying expressivity w.r.t. various elaborations of the latter concept. Even seemingly small variations in the operations a process calculus offers leads to huge expressivity gaps w.r.t.  various notions of expressivity.


Counting words of length $n$ in an inherently ambiguous CFG? There is a polynomial-time algorithm for computing the number of words of length $n$ in an unambiguous CFG $G = (V, \Sigma, R, S)$ (via a dynamic programming approach). However, for ambiguous CFGs, the algorithm only computes the number of parse trees resulting in strings of length $n$. Therefore, this result is not the number of words of length $n$ in an ambiguous CFG.

Is there a result (other than testing all possible strings of length $n$) for inherently ambiguous CFGs?

It seems that this problem is NP-hard, if both the grammar and $n$ (in unary notation) are considered to be parts of the input.
There is a classical construction that is used to show that universality of a CFG is undecidable. The construction takes a Turing machine $M$ and outputs a grammar $G_M$, such that all strings in $L(G_M)$ are not valid accepting computations of $M$ in some encoding.
Sections 1 and 3 of this overview do a decent job of explaining the main ideas, though they skip over a lot of details (how to deal with tape extensions, e.t.c.).
Said construction should work for non-deterministic Turing machines as well (the construction does not use determinism anywhere, I think). Now, consider a polynomial time non-deterministic Turing machine $M$ that solves SAT by guessing a satisfying assignment. Construct a grammar $G_M$ that corresponds to $M$.
I claim that a polynomial time algorithm to compute the number of strings in $G_M$ with a given length yields a polynomial time algorithm for solving SAT. Indeed, consider a given SAT-formula $\varphi$, it corresponds to some initial configuration $x_\varphi$ of $M$. Then, the language $L' = L(G_M) \cup \overline{(x_\varphi\#)(\Gamma \cup Q \cup \{\#\})^*}$ is the language of all strings that are either not valid accepting computations of $M$ or valid accepting computations of $M$ that do not start in configuration $x_\varphi$.
Hence, if $\varphi$ is satisfiable, there is a string of polynomial length from $(\Gamma \cup Q \cup \{\#\})^*$ that does not belong to $L'$. This string correspond to $M$ guessing some satisfying assignment correctly. On the other hand, for unsatisfiable $\varphi$, there are no accepting computations of $M$, hence there will be no short strings (or any strings, really) that do not belong to $L'$.
The last thing to note is that $L'$ is a union of a CFL $L(G_M)$ and a regular language $\overline{(x_\varphi\#)(\Gamma \cup Q \cup \{\#\})^*}$. Therefore, it is recognised by a grammar $G_M'$ of size $|G_M| + O(|\varphi|)$. Hence, computing the number of strings with a given length in $G_M'$ is NP-hard, because SAT can be reduced to this problem.
UPD. In fact, this problem is #P-complete, because every satisfying assignment of $\varphi$ corresponds to exactly one short string not in $L'$, yielding a reduction from #SAT.


Information-theoretic Diffie-Hellman The following non-standard description of Diffie-Hellman is entirely my own, by which I mean that I came up with it having not read about it anywhere else beforehand.

In Diffie-Hellman Alice and Bob choose numbers $x$ and $y$ in a fine representation and publish $x$ and $y$ in a coarser form from which they can both determine $xy$ in coarse form. A form is considered coarse if the product of two numbers in the coarse form is (practically) uncomputable, but the product of a number in the coarse form and another number in the fine form is computable.

So is there an information-theoretic analogue? My thoughts are that a number $x \in [0,1] \subset \Bbb R$ can be represented:

In a fine way using an upper-bound and lower-bound oracle.
In one coarse form by using an upper-bound oracle.
In another coarse form by using a lower-bound oracle.

Is there any literature on this?

Cheers

No, there is no information-theoretic analog that is secure against computationally-unbounded adversaries.

To form an analog, we'd need an injection $\varphi$ that maps $x$ in fine representation to $x$ in coarse representation.  But then Diffie-Hellman involves Alice sending $\varphi(x)$ publicly, and Bob sending $\varphi(y)$ publicly.  An eavesdropper can see $\varphi(x),\varphi(y)$.  Since $\varphi$ is an injection, information-theoretically this reveals $x,y$, which is enough to reveal the negotiated key.

What if we consider a function $\varphi$ that is non-injective?  This doesn't help.  Consider the equivalence relation $\sim$ where $x \sim x'$ if $\varphi(x)=\varphi(x')$, and let $[x]$ be the equivalence class of $x$.  Then for the scheme to work, the negotiated secret has to depend only on $\varphi(x),y$, i.e., only on $[x],y$ (since Bob has to be able to compute it).  Similarly, the negotiated secret has to depend only on $x,[y]$.  It follows that the negotiated secret depends only on $[x],[y]$.  Why?  Let $f(x,y)$ denote the secret negotiated if Alice uses fine value $x$ and Bob uses fine value $y$.  Suppose $x \sim x'$ and $y \sim y'$.  Then since $[x]=[x']$, it follows that $f(x,y)=f(x',y)$ (since $f(x,y)$ depends only on $[x],y$).  Also since $[y]=[y']$, it follows that $f(x',y)=f(x',y')$ (since $f(x,y)$ depends only on $x,[y]$).  Therefore $f(x,y)=f(x',y')$ whenever $x=x'$ and $y=y'$.  In other words, the final negotiated secret depends only on $[x],[y]$.  However, the eavesdropper can observe $\varphi(x),\varphi(y)$, from which $[x],[y]$ are uniquely determined and thus the negotiated secret is uniquely determined and thus information-theoretically cannot be hidden from the eavesdropper.

Public-key exchange can only be secure computationally -- you can't achieve information-theoretically secure public-key exchange.


Subset sum with many targets Take a set $S = \{a_1, a_2, ..., a_n\}$ of integers $a_i$ and a set $G = \{b_1, b_2, ..., b_m\}$ of integers $b_j$.

If we ask the question, is there a subset $C \subseteq S$ such that the sum $(\sum_{a_i \in C} a_i) \in G$, and $m = 1$ this is the traditional subset sum problem. We add an additional restriction (so that this is a promise problem) that all $b_j \in G$ must be between the minimum sum and the maximum sum of subsets of $S$.

I have three questions regarding the case where $m \gt 1$.

1.) Is there a known name for this problem and has it been studied?

2.) Are there threshold results for this problem, or can threshold results from k-SAT problems be reduced to this problem?

3.) Are there known or obvious instances where this problem is trivial? Or in general does it remain NP-Complete?

Edit: Threshold results - for a uniformally random selected set $S$ and $G$ of given sizes whose integer members are limited in size (under the usual binary encoding) of $b$ bits, and for a fixed ratio $k = |G|/|S|$, is there a $k$ for which the multiple target subset sum problem becomes almost certainly satisfiable or unsatisfiable (in the manner of 3-SAT)?

For what regards point 3:  the problem remains NP-complete:

if $m$ is a parameter, then it is simply a generalization of SUBSET SUM;
if $m$ is fixed, then given an instance of SUBSET SUM, simply multiply every $a_i$ and the target sum $B$ by $p = 2^k$ s.t. $2^k>m(m+1)/2$ and set $m$ target integers in this way:

$G = \{ b_1=B,b_2=a_1+1,b_3=a_1+2,...,b_m=a_1+(m−1)\}$.

In both cases the problem remains solvable in pseudo-polynomial time.

For what regards point 2) you can find some information related to the density analysis for the ("simpler") SUBSET-SUM problem (it is usually defined in terms of $n/m$ where  $n$ is the number of elements of the input set and $m$ is its maximum);  e.g.: O'Neil, Thomas E. "On Clustering in the Subset Sum Problem." Proceedings of the 44th Midwest Instruction and Computing Symposium (Duluth, MN, 2011).


Find the most/least repeated group of N-members in given draws Can someone suggest a good algorithm for the following problem (or a reference to look up)?
You have a set of numbers from 1 to $m$ (m=80) (inclusive). $n$ (=20) non-repeating numbers will be drawn from the set in an increasing order in a single draw. There will be 2 to N draws, and you will have the results of those draws. Design an algorithm, which will find the most and the least repeated group ($N$-members) of numbers in the draws.

Sample draws
1) 4   5   7   19  28  32  39  40  43  44  46  47  48  49  55  56  59  69  73  79
2) 1   10  11  19  20  27  32  35  41  42  46  49  51  54  58  61  63  67  68  76
3) 3   4   5   8   11  16  24  25  27  34  37  48  49  50  57  58  59  68  71  73
4) 1   8   10  13  18  26  27  30  32  35  45  46  49  52  53  61  66  72  75  78
5) 7   14  20  21  25  26  38  40  43  46  49  53  54  58  60  61  66  68  74  80

Further explanation
The algorithm should find the most repeating group of N-numbers (say 3 numbers). So, basically a tuple of three numbers that is repeated the most in the draws must be found. it is also possible that there will be a most/least common group of $N$-members, but it is quite as possible that there won't.

First, count the occurences of each number overall, and call it C(x):

1: 2
2: 0
3: 1
4: 2
etc ...

Next, we want to find the most common pairs. We know that any pairs C(x, y) <= Min(C(x), C(Y)). Using this we can find the Y "most likely" pairs. We then run through the sequences and count these most likely pairs. As long as the C(most likely pair) is greater than the estimate for the Y'th most likely pair, we know we have found the most common pair. If it isn't, we generate the next Y most likely pairs and then count those as well.

We can extend this to sets of three: C(x, y, z) <= Min(C(x, y), C(x, z), C(y, z)). So for this to work, we need to keep calculating the most common pairs until we find three pairs that we can chain into a triplet. We then need to keep going until we prove that all other triples must have a lower count, following the same logic as used by pairs.

It's basically a heuristic guided search of the possible solutions.


Placing points far away from each other in simple polygon I am sure the following problem has been studied before, but I did not find any literature about it.

Place m points in a simple polygon such that
the minimum geodesic distance among those points is maximized.

Does anybody know the name of this problem, or has any references?

Maybe the problem corresponds to a known special case of the facility location problem?

This does not answer your (interesting) question, but it may be worth mentioning that
this variant (which does not use geodesic distance) has been studied:

Thomas Shermer, "Hiding people in polygons,"
Computing,
Volume 42, Numbers 2-3 (1989), 109-131 (Springer link):

  A hidden set is a set of points such that no two points in the set are visible to each other. A hidden guard set is a hidden set which is also a guard set. In this paper we consider the problem for finding hidden sets and hidden guard sets in and around polygons. In particular, we establish bounds on the maximum size of hidden sets, and show that the problem of finding a maximum hidden set is NP-hard.

To more directly address your question, perhaps this is the most natural interpretation for $m=1$:

Pollack, Sharir, Rote, "Computing the Geodesic Center of a Simple Polygon,"
Discrete Comput. Geom. 4:611-626 (1989):

  The geodesic center of a simple polygon is a point inside the polygon which minimizes the maximum internal distance to any point in the polygon. We present an algorithm which calculates the geodesic center of a simple polygon with $n$ vertices in time $O(n \log n)$.


Maximum Polyhedron Volume in Given $n$ Points Suppose we are given $n$ points $v_1,v_2,\cdots, v_n\in \mathbb{R}^k$, I want to find $k+1$ points $v_{i_1}, v_{i_2},\cdots,v_{i_{k+1}}$ such that the volume of the convex body spanned by them maximized (where any $k$ vectors in $v_{i_j}$s should be linear independent, otherwise the volume can simply be $0$).

I know the Minimizing version of this problem can be shown to be NP-Hard, e.g. one can reduce the subset sum problem to it as follows:

For given $n$ distinct reals $a_1,a_2,\cdots, a_{n-1}$, we want to know if there are $k$ numbers in $a_i$s that sum to $\beta$
Define $v_i=[1,a_i,a_i^2,\cdots,a_i^{k-1}]$ and $v_n=[0,\cdots,0,1,\beta]$, one can show (by Vandermonde matrix) that the problem in $1$ is true iff there are $k$ vectors in $v_i$s are linear dependent

  My question is: does the Maximizing version of this problem also NP-Hard? or Can one find a polynomial algorithm for it?

I was trying to find a similar reduction as above, but there seems to be a lot difficulty.

Edit: Actually, this paper provided a rather simple reduction from X3C as follows:

let $Q=\{q_1,q_2,\cdots, q_m\}$ and $C=\{c_1,c_2,\cdots, c_n\}$ be an instance of X3C, we want to find $C'\subset C$ such that $c_1'\cap c_2' =\phi$ for all $c_1'\not=c_2'\in C'$ and $\bigcup_{c'\in C'}c'=Q$.
for each $q_i$, define $v_i[j]=1/\sqrt{3}$ if $q_i\in c_j$ and $v_i[j]=0$ otherwise.

clearly, the instance in 1 is true iff the maximal volume is 1. (though this approach only gives a hardness result with constant approximate ratio)

This was shown to be hard (more precisely $\mathsf{NP}$-hard to approximate to better than exponential in $k$) by Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, Carsten Moldenhauer, "On largest volume simplices and sub-determinants", arXiv:1406.3512 and SODA 2015. (They talk about the largest volume simplex contained in the convex hull, rather than the one that has the given points as vertices, but it amounts to the same thing since there is always an optimal contained simplex that has the given points as vertices.) They cite earlier hardness results on the same problem by Packer (ref.37 of the arXiv preprint) and Papadimitriou (ref.38).


Approximating Independent Dominating set on bipartite graphs I'm interested in the following problem: given a bipartite graph, find the smallest independent set of vertices which dominate all other vertices.
My question is: are there any positive results in the litterature regarding polynomial time guarenteed approximations for this problem?
On the negative side, we know that no constant factor approximation exists unless $\mathrm{P}=\mathrm{NP}$. Moreover there is some constant $\delta>0$ for which there is no $\delta B$ factor approximation on bipartite graphs with maximum degree bounded by $B$ (for large enough $B$, assuming $\mathrm{P}\neq\mathrm{NP}$). See [M. Chlebík and J. Chlebíková, Approximation Hardness of Dominating Set Problems in Bounded Degree Graphs]. The problem is also more or less inaproximable when not restricted to bipartite graphs.
I was however unable to find anything implying a positive result about polynomial time approximations on bipartite graphs.

After a bit more searching, it appears that what I'm looking for is unlikely to exist.
In [1], it is proven that approximating the minimum maximal independence number (which is equivalent to the minimum size of an independent dominating set) within a factor of $O(n^{1-\epsilon})$ is $\mathrm{NP}$-hard for any $\epsilon > 0$. This remains true even when restricted to bipartite graph (this is the part I missed when I first came across this paper).
[1] Halldórsson, Magnús M., Approximating the minimum maximal independence number, Inf. Process. Lett. 46, No. 4, 169-172 (1993). ZBL0778.68041.


Why has hypercomputation research died down? I see a lot of research on hypercomputation in the 1990's, but in more recent years there seems to be little work on the topic. Is it true that research in this area has died down? If so, what could be the reasons for it? Was this area convincingly shown to be unpromising?

It would be better if you specified what you mean exactly by hyper-computation and gave evidence for why you think it has "died down".

In any case, assuming that you are talking about computation of functions over natural numbers (and finite strings) (since I think it is clear that models for higher type computation is a very active area, e.g. CCA) and models of computation not equivalent to computability defined by Turing machines, I don't think the claim is correct, for example see CiE'05 and CiE'11. Also see the criticisms made against the claim that hyper-computation is something new:

Martin Davis, "Why there is no such discipline as hypercomputation", 2006.
Martin Davis, "The Myth of Hypercomputation", in "Alan Turing: Life and Legacy of a Great Thinker", 2004.

If you are interested, there is also some discussion on FOM mailing list starting by Timothy Chow's email about Martin Davis' article.


What is the name of a graph with local clustering coefficients equal to zero? I am struggling to find in literature a name for a kind of graph where all local clustering coefficients are equal to zero (or, at least, bounded).
For instance, domino, a subset of cacti and all linear graphs belong to this class.
I do not know if such objects are named.

As pointed out in comments by Joshua Grochow, this is a definition of triangle-free graph.


How to construct a special data structure that allows for "fast" subset operation? If I have a set S = {1,2,3,4,5} that represents a universe and the following subsets of S:

U1 = {1,2}

U2 = {3,4,5}

C1 = {3,5}

C2 = {2}

The above sets are guaranteed to be subsets of S, however they may not be subsets of each other. To check if C1 is subset of U2 I need to iterate through both sets and check if all elements of C1 are in U2.  In this case 3 and 5 are elements of U2 thus C1 is a subset of U2.

But this operation is O(n) at best if you keep everything sorted.  I'm wondering, is it possible to select the elements of S wisely or construct a data structure in such a way to perform fast (like O(1)) subset check operations ?

If this means I need to look into parallel algorithms I am open to that as well.

Represent sets as Bit Sets. Java has built-in implementation. A is subset of B if A & B = A. These operations on bit sets are fast (O(1) ).


Can someone suggest a recent survey on product form Markov chains? I'm especially interested in their use in model checking applications.  I have Open, Closed and Mixed Networks of Queues with Different Classes of Customers by Baskett et al.  Any other suggestions for reading material?  Thanks.

There is this unpublished book by Aldous and Fill, two experts in the field. You'll find walks on product of chains there.


How can non-terminating $\lambda$-terms be turned into fixed-point combinators? I've been thinking about these questions:

Is there a typed lambda calculus which is consistent and Turing complete?

https://cs.stackexchange.com/questions/65003/if-%CE%BB-x-x-x-has-a-type-then-is-the-type-system-inconsistent

and there are already some hard to answer related questions in the untyped setting! More specifically, I'm curious to know whether we can recover Turing-completeness from non-termination in the following way:

  Question: Given a (pure) $\lambda$-term $t$ with no weak head normal form, does there always exist a fixed-point combinator $Y_t$ such that
  $$ Y_t\ (\lambda x.x) = t$$

Equalities are all taken modulo $\beta\eta$.

I actually suspect this version of the question to be false, so one can relax the question to looping combinators, where a looping combinator $Y$ is defined to be a term such that for every $f$
$$ Y\ f=f\ (Y'\ f)$$
where $Y'$ is again required to be a looping combinator. This is enough to define recursive functions as usual, of course.

More generally, I'm interested in finding "natural" ways to go from a non-terminating $t$ to a looping combinator, even if the above equation isn't satisfied.

I'm also interested in weaker versions of the above question, e.g. $t$ may be taken to be an application $t\equiv t_1\ t_2\ldots t_n$ with each $t_i$ in normal form (though I'm not sure that really helps).

So far: the natural approach is to take $t$ and "pepper" applications of $f$ throughout, e.g.

$$ \Omega:=(\lambda x.x\ x)(\lambda x.x\ x)$$

becomes the usual

$$Y_\Omega:= \lambda f.(\lambda x. f\ (x\ x))\ (\lambda x.f\ (x\ x))$$

The idea is to reduce the head of $t$ to a lambda application $\lambda x. t'$ and replace it with $\lambda x.f\ t'$, but the next step is unclear (and I'm skeptical that this can lead to anything).

I'm not sure I understand enough about Böhm trees to see whether they have anything to say, but I highly doubt it, since $\Omega$'s Böhm tree is simply $\bot$, which looks nothing like the one for $Y_\Omega$: an infinite tree of abstractions.

Edit: A friend of mine remarked that this naive approach does not work with the term:
$$ (\lambda x.x\ x\ x)(\lambda x.x\ x\ x)$$
The naive approach would give
$$ (\lambda x.f\ (x\ x\ x))(\lambda x.f\ (x\ x\ x))$$
But this is not a fixed point combinator! This can be fixed by replacing the second application of $f$ by $\lambda y z.f\ y$, but then $f\mapsto \mathrm{I}$ does not give the original term. It's not clear whether this term is a counter-example to the original question though (and it certainly is not a counter example to the more general one).

There are several aspects to this very nice question, so I will structure this answer accordingly.
$\newcommand{\setof}[1]{\{#1\}}$
$\newcommand{\thra}{\twoheadrightarrow}$
$\newcommand{\codeof}[1]{\lceil #1 \rceil}$

1.
The answer to the boxed question is no.  The term $\Omega_3 = (\lambda x.xxx)(\lambda x.xxx)$ suggested by your friend is indeed a counterexample.

It was earlier noticed in the comments that one has counterexamples like the "ogre" $K^\infty=Y K$, until the question is restricted to terms without weak head normal form.  Such terms are known as zero terms.  These are terms which never reduce to a lambda, under any substitution.

For any fixed point combinator (fpc) $Y$, $Y I$ is a so-called mute (AKA "root-active") term: every reduct of it reduces further to a redex.

$K^\infty$ is not mute; neither is $\Omega_3$ $-$ as is manifest by inspecting its set of reducts, which is
$$\setof{\Omega_3 \underbrace{(\lambda x. xxx) \cdots (\lambda x. xxx)}_k \mid k \in \mathbb{N}}$$

Rather than give a precise argument why $Y I$ is mute for all fpcs $Y$ (indeed, for any looping combinator) $-$ which may be laborious yet hopefully clear enough $-$ I will treat the obvious generalization of your question, restricting to mute terms as well.

Mute terms are a subclass of zero terms which are a subclass of unsolvable terms.  Together these are perhaps the most popular choices for the concept of "meaningless" or "undefined" in the lambda calculus, corresponding to the trivial Berarducci, Levy-Longo, and B\"ohm trees, respectively.  The lattice of notions of meaningless terms has been analyzed in detail by Paula Severi and Fer-Jan de Vries. [1] The mute terms constitute the bottom element in this lattice, i.e., the most restrictive notion of "undefined".

2.
Let $M$ be a mute term, and $Y$ be a looping combinator with the property that $YI = M$.

First we argue that, for a fresh variable $z$, $Yz$ actually looks a lot like the $Y_M$ you described, obtained by "sprinkling $z$ around" some reduct of $M$.

By Church-Rosser, $YI$ and $M$ have a common reduct, $M'$.  Take a standard reduction $R : YI \thra_s M'$.  Every subterm of $M'$ corresponds to a unique subterm of $YI\equiv Yz[z:=I]$ under this reduction.  For any subterm $C[N]=M'$, $R$ factors as $YI \thra C[N_0] \thra_{wh} C[N_1] \thra_i C[N]$, where the middle leg is a weak head reduction (and final leg is internal).  $N$ is "guarded" by a $z$ iff this second leg contracts some redex $I P$, with $I$ a descendant of the substitution $[z:=I]$.

Obviously, $Y$ has to guard some subterms of $M$, for otherwise it would be mute as well.  On the other hand, it must be careful not to guard those subterms which are needed for non-termination, for otherwise it could not develop the infinite B\"ohm tree of a looping combinator.

It thus suffices to find a mute term in which every subterm, of every reduct, is needed for non-normalization, in the sense that putting a variable in front of that subterm yields a normalizing term.

Consider $\Psi = W W$, where $W = \lambda w. w I w w$.  This is like $\Omega$, but at every iteration, we check that the occurrence of $W$ in the argument position is not "blocked" by a head variable, by feeding it an identity. Putting a $z$ in front of any subterm will eventually yield a normal form of shape $zP_1\cdots P_k$, where each $P_i$ is either $I$, $W$ or a "$z$-sprinkling" of these.  So $\Psi$ is a counterexample to the generalized question.

THEOREM.  There is no looping combinator $Y$ such that $YI = \Psi$.

PROOF.  The set of all reducts of $\Psi$ is $\setof{WW,WIWW,IIIIWW,IIIWW,IIWW,IWW}$.  In order to be convertible with $\Psi$, $YI$ must reduce to one of these.  The argument is identical in all cases; for concreteness, suppose that $YI \thra IIWW$.

Any standard reduction $YI \thra_s IIWW$ can be factored as
\begin{align*}
YI \thra_w P N_4, P \thra_w Q N_3, Q \thra_w N_1 N_2, \text{thus }
YI \thra_w N_1 N_2 N_3 N_4\\
N_1 \thra I, N_2 \thra I,
N_3 \thra W, N_4 \thra W
\end{align*}

Let us refer to the reduction $YI \thra_w N_1 N_2 N_3 N_4$ as $R_0$, and the reductions starting from $N_i$ as $R_i$.

These reductions can be lifted over the substitution $[z:=I]$ to yield
\begin{align*}
R^z_0 : Yz \thra z^k(M_1 M_2 M_3 M_4)\\
N_i \equiv M_i[z:=I]
\end{align*}
so that $R_0$ is the composition $YI \stackrel{R^z_0[z:=I]}{\thra} I^k(N_1 \cdots N_4) \thra^k_w N_1 \cdots N_4$.

Similarly, we can lift each $R_i : N_i \thra N \in \setof{I,W}$ as
\begin{align*}
R^z_i : M_i \thra N^z_i\\
R_i : N_i \stackrel{R^z_i[z:=I]}{\thra} N^z_i[z:=I] \thra_I N
\end{align*}

The second leg of this factorization of $R_i$ consists precisely of contracting those $I$-redexes which are created by the substitution $N^z_i[z:=I]$.  (In particular, since $N$ is a normal form, so is $N^z_i$.)

$N^z_i$ is what we called a "$z$-sprinkling of $N$", obtained by placing any number of $z$s around any number of subterms of $N$.  Since $N \in \setof{I,W}$, the shape of $N^z_i$ will be one of

\begin{align*}
&z^{k_1}(\lambda x. z^{k_2}(x))\\
&z^{k_1}(\lambda w.
  z^{k_2}(
    z^{k_3}(
       z^{k_5}(
         z^{k_7}(w)
         z^{k_8}(\lambda x. z^{k_9}(x))
       )
       z^{k_6}(w)
    )
    z^{k_4}(w)
  ))
\end{align*}

So $M_1 M_2 M_3 M_4 \thra N^z_1 N^z_2 N^z_3 N^z_4$, with $N^z_i$ a $z$-sprinkling of $I$ for $i =1,2$ and of $W$ for $i=3,4$.

At the same time, the term $N^z_1 N^z_2 N^z_3 N^z_4$ should yet reduce to yield the infinite fpc Bohm tree $z(z(z(\cdots)))$.  So there must exist a "sprinkle" $z^{k_j}$ in one of the $N^z_i$ which comes infinitely often to the head of the term, yet does not block further reductions of it.

And now we are done.  By inspecting each $N^z_i$, for $i \le 4$, and each possible value of $k_j$, for $j \le 2+7\lfloor \frac{i-1}{2} \rfloor$, we find that no such sprinkling exists.

For example, if we modify the last $W$ in $IIWW$ as $W^z = \lambda w. z(wIww)$, then we get the normalizing reduction
$$ IIWW^z \to I W W^z \to WW^z \to W^z I W^z W^z
\to z (I I I I) W^z W^z \thra z I W^z W^z $$

(Notice that $\Omega$ admits such a sprinkling precisely because a certain subterm of it can be "guarded" without affecting non-normalization.  The variable comes in head position, but enough redexes remain below.)

3.
The "sprinkling transformation" has other uses.  For example, by placing $z$ in front of every redex in $M$, we obtain a term $N = \lambda z. M_z$ which is a normal form, yet satisfies the equation $N I = M$.  This was used by Statman in [2], for example.

4.
Alternatively, if you relax the requirement that $Y I = M$, you can find various (weak) fpcs $Y$ which simulate the reduction of $M$, while outputting a chain of $z$s along the way.  I am not sure this would answer your general question, but there are certainly a number of (computable) transformations $M \mapsto Y_M$ which output looping combinators for every mute $M$, in such a way that the reduction graph of $Y_M$ is structurally similar to that of $M$.  For example, one can write
$$
 Y \codeof{M} z =
\begin{cases}
z (Y \codeof{P[x:=Q]} z)
&M\equiv (\lambda x.P)Q\\
Y \codeof{N} z &M \text{ is not a redex and }M \to_{wh} N
\end{cases}$$

[1] Severi P., de Vries FJ. (2011) Decomposing the Lattice of Meaningless Sets in the Infinitary Lambda Calculus. In: Beklemishev L.D., de Queiroz R. (eds) Logic, Language, Information and Computation. WoLLIC 2011. Lecture Notes in Computer Science, vol 6642.

[2] Richard Statman. There is no hyperrecurrent S,K combinator. Research
Report 91–133, Department of Mathematics, Carnegie Mellon
University, Pittsburgh, PA, 1991.


Super-polynomial time approximation algorithms for MAX 3SAT The PCP theorem states that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = NP$.

There is a trivial polynomial time algorithm that satisfies $7/8$ of the clauses. So, Can we do better than $7/8+ \epsilon $ if we allow super-polynomial algorithms?  What approximation ratios can we achieve  with quasi-polynomial time algorithms ( $n^{O(\log n)}$) or with sub-exponential time algorithms($2^{o(n)}$)? I'm looking for references to any such algorithms.

One can get a $7/8+\varepsilon/8$ approximation for MAX3SAT that runs in $2^{O(\varepsilon n)}$ time without too much trouble. Here is the idea. Divide the set of variables into $O(1/\varepsilon)$ groups of $\varepsilon n$ variables each. For each group, try all $2^{\varepsilon n}$ ways to assign the variables in the group. For each reduced formula, run the Karloff and Zwick $7/8$-approximation. Output the assignment satisfying a maximum number of clauses, out of all these trials.

The point is that there is some variable block such that the optimal assignment (restricted to that block) already satisfies a $\varepsilon$-fraction of the maximum number of satisfied clauses. You'll get those extra clauses exactly correct, and you'll get $7/8$ of the the remaining fraction of the optimum using Karloff and Zwick.

It is an interesting question if one can get $2^{O(\varepsilon^2 n)}$ time for the same type of approximation. There is a "Linear PCP Conjecture" that 3SAT can be reduced in polynomial time to MAX3SAT, such that:

if the 3SAT instance is satisfiable then the MAX3SAT instance is completely satisfiable,
if the 3SAT instance is unsatisfiable then the MAX3SAT instance isn't $7/8+\varepsilon$ satisfiable, and
the reduction increases the formula size by only a $poly(1/\varepsilon)$ factor.

Assuming this Linear PCP Conjecture, a $2^{O(\varepsilon^c m)}$-time $7/8+\varepsilon$ approximation, for all $c$ and $\varepsilon$, would entail that 3SAT is in $2^{\varepsilon n}$ time, for all $\varepsilon$. (Here $m$ is the number of clauses.) The proof uses the Sparsification Lemma of Impagliazzo, Paturi, and Zane.


Sorting array of distances by proximity to each other I was playing with geolocation on maps and stumbled on an interesting problem:
I retrieve data from the db ordered by increasing distance from a user input, like a postcode or street, which makes sense as long as I don't use a combination of paging and map browsing, at which point the dataset no longer makes sense. Since the data on the map will be represented in concentric circles, if a user starts browsing the map needs to zoom out in order to accommodate for changing pages.
So I thought a better way of sorting data would be by elements' proximity to each other, rather than the user, which is a logical representation of a map I guess (in a geographical sense). But how then given any point on this map can we retrieve an equivalent 1D array that would convey this information?

EDIT: Thanks for your comments. I think it may be that my problem isn't as theoretical as you answers, it's been a few years since I had to cram for my algorithm exams and I've forgotten a whole lot. I'll to give some details, perhaps that will make it clearer:

In this particular case I am looking at around 350 points on the map, and page of around 10. (I think that makes k in Suresh's comment about 20, because on/after the second page distance from q - in this case position of user's query - is not the only relevant factor)

I had a, possibly a not so smart an idea, which I would like to try to explain with the of a crudely drawn diagram in paint:

So diagram A is what I have now, where concentric red circles represent paged results as points get further and further away from the centre red dot. I'd like to be able to drag the map, so that paged results get updated with what's currently closest to the centre of the screen (much like Google results) but with current sorting it's impossible without zooming out to accommodate all the points.
A possible solution is to apply some clustering to get a bunch of probably overlapping areas that represent pages as shown in diagram B. That would mean there is some duplication in the returned dataset, but the duplication factor could be tweaked. The green spiral in both diagram indicates roughly increase in distance.

Having said all that, I'm now beginning to think it would be much easier to just use viewport to determine what's currently visible to the user and simply show the results on the page as that. :S

Although it's hard to discern a precise question here, evidently it concerns spatial data structures for efficient local searches of objects.  Hanan Samet's books on the subject are classics and almost encyclopedic.  He wrote a brief overview of the subject available here.  I suspect a simple quadtree would be an attractive solution.  In many cases, exploiting a pre-sorting by one of the coordinates provides fine performance and is simple to code.


Is there a list of canonical problems in distributed systems? Last week, I was reading again Leslie's Lamport's 1982 trasncript of a conference he gave about Solved Problems, Unsolved Problems and Non-Problems in Concurrency. The paper is easily readable, but one of the things that got me thinking is the following assertion:

  Can any problem be regarded as a mutual exclusion problem or a
  producer- consumer problem, or a combination of the two?

I would like to know if this question has been answered for the distributed systems case.

Is there a set of canonical distributed systems problems from which all the possible distributed system problems can be reduced to? What is this canonical list?

If there is not a canonical list what is the current list of problems and what reductions exist?

For example, I would say very naively that the leader election and mutual exclusion problems can be reduced to the consensus problem. I would also say that a distributed snapshot can be reduced to a distributed clock. It it true or plain wrong?

If possible, I would prefer that the answers provide a reference to a published paper/book supporting its claims :)

Is there a set of canonical distributed systems problems from which all the possible distributed system problems can be reduced to?

I'm unaware of such a published list of problems.

Keep in mind that there are many different (and somewhat incomparable) models in distributed computing, ranging from the "benign" synchronous (fault-free) model where nodes execute in lock-step rounds and all messages are delivered
reliably in each round, to the asynchronous model where there are no bounds on
processing speeds and message delays and nodes themselves might crash or send
corrupted messages.
To further add to this variety, there are other requirements and assumptions
that are orthogonal to synchrony and faults: the initial knowledge of nodes
(network size, diameter of the network, maximum node degree, etc.), the ability
to query a failure detectors, whether nodes have unique identifiers, atomicity
of send & receive steps, the maximum size of a single message, and many more.

The actual model at hand often implies a very different nature of
question. (See [1] for more elaboration on these $2$ sub-communities in distributed computing.)
In models that are close to the fault-free synchronous model, researchers often
look at the complexity of local computation, for example, "What is the time and message
complexity for computing a vertex coloring?"

When looking at failures on the other hand, the questions are more related to solvability issues like "Is consensus solvable in this model?" or "Can we implement this fancy
failure detector under these assumptions?"

  If there is not a canonical list what is the current list of problems and what reductions exist?

There are many examples of such reductions in certain distributed computing
models, I'll limit my answer to the following 2:

Local computation in the (fault-free) synchronous model

[2] show reductions between many optimization problems, for example, Minimum Dominating
Set, Maximal Independent Set (MIS), Maximal Matching (MM), and Minimum Vertex
Cover (MVC): In particular, [2] show a lower bound of $\Omega(\sqrt{\log n} +
\log\Delta)$, where $n$ is the network size and $\Delta$ the max degree, for
computing a constant approximation of an MVC. From this, the same bound follows
for computing an MM, since any maximal matching is also a $2$-approximation of
an MVC. From this, you also get a bound on computing an MIS, because an
MIS-algorithm $A$ can be used to compute MM by simulating the execution of $A$
on the line graph.

Asynchronous Model with Crash Failures

Here the most studied problem is
fault-tolerant consensus and its many variations, since implementing basic primitives like atomic broadcast and or a synchronizer themselves require consensus.

For example, assuming access to failure detectors [3], gives rise to a classification of problems by looking at
the power of their respective failure detector.
We say that failure detector $S$ is the weakest failure detector for problem $P$, if, given any failure detector $T$ for $P$, you can also implement $S$.

Using this relation, we can define problem $P$ as being harder than problem $Q$, if
the weakest failure detector for solving $P$ can implement the weakest failure
detector for solving $Q$.
It has recently been shown that every problem has a weakest failure detector [4]; note however, that [4] is an existential result. For some problems, e.g., consensus, the weakest failure detector is known [5], while for other problems, e.g., $k$-set agreement, the weakest falure detector is still open [6].

  For example, I would say very naively that the leader election and mutual
  exclusion problems can be reduced to the consensus problem.

Sure, if you can solve consensus, you immediately have an algorithm for leader
election: Simply use the ID of each node as the input for the consensus
algorithm. The opposite way only holds in models where it is  guaranteed that the leader is eventually known to all.

[1] Pierre Fraigniaud: Distributed computational complexities: are you volvo-addicted or nascar-obsessed? PODC 2010.
http://doi.acm.org/10.1145/1835698.1835700

[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Local Computation: Lower and Upper Bounds. CoRR abs/1011.5470 (2010)
http://arxiv.org/abs/1011.5470

[3] Tushar Deepak Chandra, Sam Toueg: Unreliable Failure Detectors for Reliable Distributed Systems. J. ACM 43(2): 225-267 (1996).
http://doi.acm.org/10.1145/226643.226647

[4] Prasad Jayanti, Sam Toueg: Every problem has a weakest failure detector. PODC 2008: 75-84.
http://doi.acm.org/10.1145/1400751.1400763

[5] Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg: The Weakest Failure Detector for Solving Consensus. J. ACM 43(4): 685-722 (1996)
http://doi.acm.org/10.1145/234533.234549

[6] Michel Raynal: Failure Detectors to Solve Asynchronous k-Set Agreement: a Glimpse of Recent Results. Bulletin of the EATCS 103: 74-95 (2011)
http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/61


Finding a Travelling Salesman/Vehicle Routing with cheap and expensive distances If I need to find a shortest road (not great-circle) route between ~11,000 real world lat, long coordinates within a reasonable period of time. To further complicate things, there is no necessary starting point (however starting on one of the points at the edge would be beneficial), and the route shouldn't return to the initial location.

Clearly it is impractical to poll an online api with 11,000^2 requests for the distance between every point. Google maps is limited to 1000 objects per day (Presumably 2 objects required per distance) as a casual user, and 100,000 as a business user. Bing maps does not list a casual limit (although its likely after a point they would blacklist you), and the business limit is 100,000 requests per day.

To accomplish this using a heuristic algorithm I expect that I would need to utilise two tiers of distance using the great-circle algorithm for a cheap cost and an API request for an expensive cost. To provide greater accuracy than calculating the route using great-circle and finding the accurate distance of that route.

There are numerous heuristic approaches to the travelling salesman, however I have not yet found any that would support a two tier cost approach. Does anyone have experience with implementing a similar algorithm? or Suggestions of how you would implement it?

Thanks

Here's the first approach that occurs to me.  Build a complete graph on 11,000 vertices, and label all edges with the great-circle distance.  Apply some travelling salesman algorithm to choose the best route you can find.  Then, for every edge on that route, query the map service for the road distance and replace the label on that edge with the road distance.  Then, apply the travelling salesman algorithm again on the modified graph.  Repeat this basic process until it converges.

I think the great-circle distance should be a lower-bound on the road distance, so I suspect this should be correct (in the sense that it doesn't miss out on a better solution).

One possible complication is that this might cause triangle-inequality violations, so if you are relying upon a heuristic that assumes the triangle inequality, this approach might screw things up.  I don't know; you could try it out and see.

If you wanted to reduce the number of queries for the road distance even further, here's one more idea you could try.  I suspect that the smaller the great-circle distance, the closer it is to the road distance; or, in other words, I suspect the gap between the distances might be largest for points that are far away.  That's something you'd need to validate yourself.  If it is correct, then a variant of the algorithm I suggested above is: only query the map service to obtain the road distance for edges where the great-circle distance is above some threshold.  (You could even gradually reduce this threshold in each iteration of the above algorithm.)


Is the problem of finding the "all-terminal connectivity polynomial" polynomially bounded? I want to proof whether the problem of finding the "all-terminal connectivity polynomial" of a given graph G(V,E) is checkable in a polynomial time. In order to do so I should first proof that it is polynomially bounded, i.e $|y| < p(|x|)$.
In this case I guess that $|x| \text{~} n^2$
but I am not sure about $|y|$ .

Note - Definition
For a given graph $G(V, E)$ each edge $E_{ij}$ has a $p_{ij}$-probability of being reliable and $(1 - p_{ij})$ probability of failure. Considering that each edge fails independently and nodes are perfectly reliable, the function

$Rel(G)$ = $Pr[$ for each pair of nodes $x_{i}$ and $x_{j}$ there exists at least one reliable path between them $]$

is called all-terminal connectivity (or reliability) function of the network.

I'll convert my comment to an answer.

The problem of computing the Rel(G) is #P-Complete (see this paper by Karger), and there's also an FPRAS for 1-Rel(G) (also in the Karger paper). Note that if you could verify whether Rel(G) was less than any fixed number $k$, then you could binary search for an approximate solution for Rel(G) that would run in P-time, which seems a little unlikely.


From $PIT\in P$ to $P=BPP$ If $PIT$ has been derandomized then still how far would we be from showing $P=BPP$? What additional barriers need to be climbed?

If PIT over a finite field $F$ is in P, then there is a family of multilinear polynomials whose graph is decidable in $\mathsf{NE}$ but which does not have poly-size $F$-algebraic circuits (Carmosino-Impagliazzo-Kabanets-Kolokolova APPROX-RANDOM '15). (And a similar result holds over $\mathbb{Z}$.) This is an algebraic circuit lower bound on $\mathsf{NE} \subseteq \mathsf{NEXP}$.

To get $\mathsf{P} = \mathsf{BPP}$ out of, e.g., Nisan-Wigderson (& Impagliazzo-Wigderson), one needs a Boolean (sub)exponential circuit lower bound on functions in (deterministic) $\mathsf{EXP}$.

So, on the one hand, an algebraic circuit lower bound on $\mathsf{NEXP}$ is a lot closer to $\mathsf{P} = \mathsf{BPP}$ than we are today, but still seems pretty far in some absolute sense: algebraic -> Boolean*, super-poly lower bound -> exponential, and $\mathsf{NEXP}$ -> $\mathsf{EXP}$.

(Of course, as discussed by Emil Jerabek in the comments, if one uses Impagliazzo-Kabanets to get PIT in $\mathsf{quasiP}$ by giving an exponential algebraic circuit lower bound, then the "super-poly -> exponential" gap goes away. But I took the question to mean "Suppose $PIT \in \mathsf{P}$ by any arbitrary method...")

*Over a fixed finite field this is probably the easiest one to overcome.


Is bitcoin cryptographically secure I am trying to understand the bitcoin protocol in the context of computational cryptographic security.

The question is a reference request to foundations of cryptography articles on bitcoin.

My first question is what abstract cryptographic protocol bitcoin is trying to implement? Do we have a definition of electronic money/digital currency in cryptography that captures bitcoin? What are the security requirements for a secure electronic money?

If the answer is yes, companies like eBay provide a centralized mean of electronic money transfer. Does considering a decentralized electronic money changes the definition of abstract cryptographic protocol for electronic money? Or is it just the same concept but in a model where there is no trusted third party?

Can the adversary break the protocol if it has more computational power than the combined computational power of other (honest) parties?

Assume that we have $n$ parties $P_i$ for $1 \leq i \leq n$ plus an adversary $A$ networked and the adversary wants to break the bitcoin protocol. For simplicity let's assume that the network graph is $K_{n+1}$ and adversary does not control the network and simply is a party like others. What would be the exact mathematical claim about the security of the protocol in this simple case?

I guess there is no consensus among researchers and academics on the security of Bitcoin protocol. Thanks to Stack Exchange Network, The following links should help you to answer some of your questions:

1- Bitcoin research at Cryptography StackExchange

2- How secure is the Bitcoin protocol? at Cryptography StackExchange

3- Are there any fundamental security vulnerabilities in Bitcoin? at Bitcoin Stackexchange

Here is a comprehensive list of research publications at Bitcoin wiki that include research and analysis of Bitcoin.


Is there an alternate proof or an exposition of: Exponential lower bound for $\Sigma\Pi\Sigma$ circuits [Grigoriev-Karpinski(1998)]? Is there an alternate proof or an exposition of the result of Grigoriev and Karpinski (STOC 1998, doi:10.1145/276698.276872) on the exponential lower bounds for Depth 3 arithmetic circuits computing $\mathsf{DET}_{n\times n}$ over a fixed finite field?

I could not understand section 2 of the paper. What is the intuition behind considering the F-linear operator $T_g$?

There was a subsequent extension by Grigoriev and Razborov (PS) that has a shorter exposition of proof.


Best book on Simplex Method implementation? I'm interested in implementing SM for LP task, however I've heard about possible pitfalls: Cormen's book says that it is possible to have input data which will make naive implementation to behave in exponential time. I've also heard that naive implementation can loop for some kind of data.

Is there a book/paper/source which explains nuances of practical implementation of SM?

Thanks in advance.

I strongly recommend the paper by Bixby, the "father" of CPLEX, that surveys not only on implementing aspects of the (revised) simplex algorithm: Robert E. Bixby, Solving Real-World Linear Programs: A Decade and More of Progress, Operations Research (50) 2002, 3-15.


A reduction proof of SK-security for the Needham-Schroeder-Lowe protocol The Needham-Schroeder-Lowe protocol works as follows between the initiator I and responder R:

$I \longrightarrow R : \text{Enc}_{pk_R}(r_I, I)$

$R \longrightarrow I : \text{Enc}_{pk_I}(r_I, r_R, R)$

$I \longrightarrow R : \text{Enc}_{pk_R}(r_R)$

(I assume throughout that the encryption scheme is CCA-secure.)

Upon receiving their messages, both parties decrypt using the corresponding private key and finally output $r_I$ as their session key.

I understand others have proven that this protocol is SK-secure protocol, based on the CK01 model for SK-security.  (As a reminder, the protocol is secure in this model if no adversary can distinguish, with probability strictly greater than $1/2$, between the output $r_I$ of the protocol and a random bit.)  Security was proven using formal methods.  My question: is there a proof of this using an explicit reduction?

I am not an expert on this subject, but it looks to me like the question makes some assumptions that may or may not be valid.  The question claims that the Needham-Schroeder-Lowe protocol is SK-secure.  However, I don't know whether there is any known proof that Needham-Schroeder-Lowe is SK-secure.  The paper that was cited in the question does not appear to claim that it is SK-secure.  You might want to start by first checking whether there's a known proof of its SK-security.

It's possible you might find the following paper of some relevance:

A Computational Analysis of the Needham-Schroeder-(Lowe) Protocol.  Bogdan Warinschi.  Computer Security Foundations Workshop 2003.

It gives a computational, reduction-oriented proof of security for the Needham-Schroeder-Lowe protocol, assuming that the encryption algorithm is CCA-secure.  However, I don't know what notion of security for key exchange algorithms this paper uses; I don't know if it proves SK-security, or something else.


What is the most efficient algorithm for deciding if an element is the least in its orbit? Given a group $G$ acting on a set $X$ with a total order $\leq$ and an $x\in X$, what is the most efficient algorithm for deciding whether or not x is the least element in its orbit, in other words, deciding if $ min(Gx) = x$?

My motivation comes from SMT solving where there has been some interest in automatically breaking symmetries. Adding symmetry breaking predicates often result in a large clause set therefore I am interested in the possibility of handling this as a lazy theory propagation.

The above description is perhaps too general, and as noted by sid, NP-hard. A possible simpler task is, given a group of permutations of strings of length $n$ encoded as a set of generators and a string $x$ of length $n$. What is the most efficient algorithm for deciding if that string is the lexicographically smallest in its orbit?

For general equivalence relations, not those arising from permutation group actions, even finding lexicographically least is still "too" general. Finding the lexicographically smallest element in an equivalence class can be $NP$-hard (in fact, $P^{NP}$-hard) - even if the relationship has a polynomial-time canonical form [1].

However, for permutation group orbit problems as you describe, deciding whether two points lie in the same orbit is not likely to be $NP$-hard: it is in $NP \cap coAM$, and hence not $NP$-hard unless the polynomial hierarchy collapses to the second level.

A canonical form for graph isomorphism is also a special case of the second problem you state. The best known canonical form for graph isomorphism runs in time $2^{\tilde{O}(\sqrt{n})}$ [2].

Since you said in the comments that any canonical form will do, you might also be interested in my paper with Lance Fortnow [3]: in its currently generality, I think your question is related to our results. We show that if every equivalence relation decidable in $P$ has a canonical form in $P$, then "bad" consequences result, such as $NP = UP = RP$, which in particular implies that the polynomial hierarchy collapses down to $BPP$. On the other hand, the equivalence relations you're interested in may not be in $P$, but this result suggests that even if it lies in a higher complexity class other hard problems may still stand in your way.

So I think if you want some better upper bounds you really need the problem to be more specific.

[1] Andreas Blass and Yuri Gurevich. Equivalence relations, invariants, and normal forms. SIAM J. Comput. 13:4 (1984), 24-42.

[2] László Babai and Eugene M. Luks. Canonical labelings of graphs. STOC 1983, 171-183.

[3] Lance Fortnow and Joshua A. Grochow. Complexity classes of equivalence problems revisited. Inform. and Comput. 209:4 (2011), 748-763. Also available as arXiv:0907.4775v2.


Graph theoretic restriction to Proofs in Proof Complexity Theory Proof complexity is a most basic area of computational complexity theory. An ultimate purpose of this area is to prove $NP\neq coNP$, that is, any prover cannot give a proof of unsatisfiability of given input formula.
A graph is one of formal model of proofs.  My question is about further restriction to this model.
A proof is represented as a DAG. Nodes with fan-in 0 have axiom-labels. The unique node with fan-out 0 corresponds to "false." For given input rules of deduction, each node which has both in-degree and out-degree has the  label representing proposition.
My question is:

Are there proof systems and related researches in the case that the class of proof-DAGs are restricted?
Papers, survey, and lecture note are welcome.
Do Proof Systems which are previously studied such as Nullstellensatz, Resolution, LS, AC0 Frege, RES(k), Polynomial Caluculus, and Cutting Planes, have some graph theoretic characterization??

The most natural restriction on the proof DAG is that it be a tree – that is, any "lemma" (intermediate conclusion) is not used more than once. This property is called being "tree-like". General resolution is exponentially more powerful than tree-like resolution, as shown for example by Ben-Sasson, Impagliazzo and Wigderson. The concept has also been considered for other proof systems – just search for "tree-like X", where X is a proof system interesting you. In the particular case of resolution, there are other restrictions that can be considered. See for example a paper of Alekhnovich, Johannsen, Pitassi and Urquhart regarding regular resolution.

Tree-like resolution is especially important since traditional implementations of DPLL correspond to tree-like resolution refutations. The technique of clause learning, which is important in practice, corresponds to allowing general DAGs. Hence the structure of the proof DAG is also strongly dependent on the algorithm generating it.


"Linear" hashing function Say we have two chunks of data $X$ and $Y$, which may be of different sizes, is there a non-trivial function $hash$, and operation $*$, such that:

$$hash(X+Y) = hash(X) * hash(Y)$$

...where $+$ is concatenation, and $*$ is associative (but not necessarily commutative)?

Clearly $hash$ being the identity function, with $*:=+$, satisfies this. However, what if we put usual constraints on $hash$ -- say, its output is always $n$-bits, where $n$ is small -- and $*$ has to be reasonably economical?

My intuition is saying that no such $(hash,*)$ exists, because:

In the general case, there would be a loss of entropy in hashing and I don't believe this can be deterministic.
Merkle trees are a thing, which implies there's no better option.

(n.b., I realise "linear", in the linear algebra sense, isn't the correct word to use here, but for want of a better term!)

Sure.  These are known as homomorphic hash functions.  There are many schemes: see e.g., https://crypto.stackexchange.com/q/6497/351 for one possible entry point into the literature.

One example construction is to let $\mathbb{G}$ be a group with group operation $*$ and let $h:\{0,1\} \to \mathbb{G}$ be an arbitrary function, then extend $h$ to a function $h:\{0,1\}^* \to \mathbb{G}$ by associativity, i.e.,

$$h(x_1 x_2 \dots x_n) = h(x_1) * \cdots * h(x_n).$$

Then you can choose any group $\mathbb{G}$ of your choice.  If you want $*$ to be non-commutative, choose a non-abelian group $\mathbb{G}$.  One plausible choice is $\mathbb{G} = SL_2(\mathbb{F})$ over some finite field $\mathbb{F}$; see https://crypto.stackexchange.com/q/17730/351.

Your reasons why it can't exist are not valid.  I don't know what "there would be a loss of entropy" means; any hash function always causes a loss  of entropy (if the domain is larger than the range), thanks to the pigeonhole principle, but that doesn't mean hash functions don't exist or can't be deterministic.  The existence of Merkle trees doesn't preclude the existence of other solutions.


Assignment problem with sum replaced by max In the assignment problem, one tries to find $f$ such that the cost function
$$
\sum_{a\in A} C(a,f(a))
$$
is minimized. Here $f$ is a bijection between sets $A$ and $B$ of equal finite cardinality, and $C$ is a cost function $A\times B \to \mathbb R$.

My question: is there a name for the problem to minimize
$$
\max_{a\in A} \, C(a,f(a))
$$
over bijections $f$ as above?

Thanks in advance for any replies or references.

In the geometric setting, where $C(x,y) = \|x - y \|$, this formulation is called the bottleneck matching problem. It's possible that this is the generic term for it (I've seen this formulation used in the Kleinberg-Tardos algorithms book for MSTs).


Curriculum: Logical/Formal Methods in Security At present I teach a small course (Four two hour lectures at the Masters level) on Logical Methods in Security, though the title Formal Methods in Security might be more apt. It covers briefly the following topics (with associated logical methods):

Digital Rights Management and Policy Enforcement (general formalisation, modal logic, enforcement via automata)
Proof-carrying code and proof-carrying authentication (proof theory, logical systems, Curry-Howard Isomorphism, verification)
Access Control (non-classical logics, proof theory)
Stack Inspection (programming language semantics, contextual equivalence, bisimulation)

Naturally, the course has multiple goals, where one of them is attracting potential graduate students.

In the coming years the course may be expanded to a regular course, which will need more content. Given that the background of people here is quite different from mine, I would like to know what content you would include in such a course.

I suggest familiarizing the students with the following logics:

Epistemic logic: Used to model the knowledge of various parties participating in the protocol, and prove that an adversary cannot gain knowledge of some secret.
BAN logic: An old logic for proving various properties of authentication protocols. (Other belief logics are appropriate as well.)
Logics for transition systems: This includes logics like LTL, CTL, and LTL*. (such logics act on Kripke-like models of the protocol.)
Process Algebras: Several process algebras, like Spi-calculus (or CSP, and its security-related tool, Casper) are useful for modeling security protocols.
Introducing tools like AVISPA of NuSMV are very useful.
I also suggest Formal Correctness of Security Protocols as one of the course textbooks.

A friend of mine, Morteza Amini, has recently got his Ph.D. on modeling access control with logic. He devised a new logic, named $MA(DL)^2$, which stands for "multi-authority deontic logic and description logic." As the name suggests, it combines two non-classical logics (deontic logic + description logic) to decide whether an entity has access to an object. If you like, I can encourage him to provide more information.


Why is combinational logic called so? What is the significance of the word "combinational" in combinational logic?

This source states that it comes from the concept of a combination set, which is backed up by Hennesy & Patterson's explanation in "Computer Organization and Design", p.340.

The reasoning behind it seems to be as follows. In a combination the order of elements is irrelevant: in (n choose k) it doesn't matter in which order you pick the k elements. Similarly, a combinational logic circuit is a logic circuit where the order of inputs doesn't matter for the outputs. Note here that "an input" refers to the entire input to the circuit, not the individual lines. So, the intuition is that you give a combinational circuit some sequence of inputs, and "order doesn't matter" is true in the sense that the output for each input is the same, even if you permute the sequence.

This is to be understood in opposition to sequential logic, where the order of inputs does matter, because sequential circuit can have internal state (e.g. flip-flops) that can and usually influence individual outputs.


Proof that circuit upper bounds for $E$ imply $P \neq NP$ In the official Clay problem description for P versus NP it's stated that $P \neq NP$ would follow from showing that "every language in $E$ [the class of languages recognizable in exponential time with a deterministic Turing machine] can be computed by a Boolean circuit family $<B_n>$ such that for at least one $n$, $B_n$ has fewer gates than the maximum needed to
compute any Boolean function $f: \{0,1\}^n \longrightarrow \{0,1\}$." However, the only reference is that this "is an intriguing observation by V. Kabanets." Could someone please point me to a published version of this implication with the proof?

I don't think the paper in the other answer contains an answer to your question. Indeed I am not really sure a proof has been published, because the result follows from other well known results.

The proof of the statement you want is as follows:

$\Sigma_3 E$ contains a function of maximum possible circuit complexity on every input length, by simply defining a function which proves itself (using alternation) to be different from all functions with non-maximum circuit complexity. This is standard and the proof idea can be found in sources such as Arora and Barak's textbook.
If $P = NP$ then $\Sigma_3 E = E$, by padding and the collapse of the polynomial time hierarchy to $P $.
Therefore if $P = NP$ then there is a language in $E$ with maximum circuit complexity. This is the contrapositive of what you want to prove.


List of NP-Complete graph problems/ properties? Is there a good source to find various decision problems on graph and networks? For a project I'm doing it'd be useful to be able to look at lots of different problems. Is there a good source for finding them?

A general list of NP-complete problems can be found in Garey & Johnson's book "Computers and Intractability". It contains an appendix that lists roughly 300 NP-complete problems, and despite its age is often suggested when one wants a list of NP-complete problems.

I haven't read the book, but based on its reputation it would be a quite good start to any investigation.


Minimum number of columns making each row different I'm curious whether this problem is NP-hard: suppose you are given an arbitrary $m\times n$ 0-1 matrix (each element is either 0 or 1, for the simplicity of the problem), and any pair of rows (i.e. a 0-1 vector of dimension-$n$) are different (in other words, there are no repetitive rows). I'd like to select a minimum number of columns such that each row within these columns are different.

To make sure you understand it correctly, there is a firm lower bound, $\log_2m$, of the number of columns to be selected, but you don't know whether a solution of size $\log_2m$ exists. In addition, there must be a feasible solution of size $n$ since each row is different.

Is there an efficient algorithm for solving this? Or I need to solve it in a brute-forth way by checking every possible combinations of columns from $\log_2m$ to $n$?

Your problem is known to be NP-hard. See for instance

  Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge:
  "Exploiting hidden structure in selecting dimensions that distinguish vectors."
  Journal of Computer and System Sciences 82, pp 521-535 (2016).


Publishing short and simple results I have a manuscript that has been conference-rejected 3 times up to this point.
Just to clear things up, I am by no means a senior researcher but I am not a junior who cannot judge the strength of my own work either (I have published in some top conferences such as STOC, PODC, etc.). For this manuscript, I haven't submitted it to any venue that is clearly inappropriate with respect to its strength.
In particular, what usually happened was that I get a mix of accept/weak-accept/weak-reject. Even in the reviews that recommended a rejection, they said the paper was decent (my point is that I did not submit a junk paper!). In general, even though I disagree with some of the reviews, I respect the PC's decision.
Now, I don't want to keep submitting it to conferences because while the paper is publishable, it usually does not fall into the top percentage of conferences' acceptance allocation. It will keep wasting people's time (i.e., reviewing). Improving the paper is also unclear because I have matching upper and lower bounds.
I have someone suggest submission to Information Processing Letters since they sort of accept short and simple contributions. I wonder if there is any alternative since I don't really like the idea of publishing with Elsevier.

There are two natural strategies:

Put it on the arxiv, forget about publishing it somewhere else. I have several such writeups - people see them and cite them.

Go to lower venue conferences. Don't give up. I had a paper rejected 5 times before it got accepted, and it was a strong result that later appeared in a good journal. Rejection is just acceptance to the complement, etc.


Can modern SAT-Solvers utilise the symmetry of First Order Logic? Apologies if the question is trivial or is wrongly stated, I am a Physicist!
Assuming that we have a universally quantified first-order logic sentence, all variables are universally quantified, defined over a finite domain $\mathcal{D}$. Then what are the most efficient ALL-SAT (algorithms that enumerate all models of a formula) algorithms in literature? In my understanding, DPLL and CDCL  based algorithms have no way of discerning symmetries which would be inherent to a grounded FOL formula.
Trivial Example:
Let the domain $\mathcal{D} = \{a,b\}$
$$\forall x F(x)$$
Then the grounding of this sentence is,
$$F(a)\land F(b)$$
So the brute force idea would be to just check all $2^{\#ground atoms}$ assignments and in this case, only {F(a): True , F(b): True} is the model. But obviously this is a trivial example, if we ground the formula for more complex sentence then, do SAT-solvers solve this as just another propositional case or are there methods to use the "symmetry" from the First Order sentence?

There exist first order (FO) logic systems that allow you to actually write FO constraints, and to reason with them in very intricate ways. E.g., see the IDP system.
For instance, I took a small variation of your example and coded it up in the online IDP editor:
vocabulary V{
    type D
    P(D)
}

theory T: V{
    ?x: P(x).
}

structure S:V{
    D = {a;b}
}

procedure main(){
    //stdoptions.symmetrybreaking="static"
    printmodels(allmodels(T,S))
}

If you press the run button, it will print all the models (==solutions) of the FO specification, which in this case amounts to three models. The system uses a SAT solver under the hood.
Now, if you uncomment the //stdoptions.symmetrybreaking="static" line, its automatic symmetry detection and breaking kicks in. Run again, and only two models will be printed, as the third is removed by symmetry breaking. Here is a reference to how this is done under the hood.
Now, can modern SAT solvers exploit this symmetry, without knowing the high level FO specification?
Not completely. The problem is that it seems hard to extract the interchangeability of first-order domain elements in the propositional logic formula. While the SAT solver typically can find permutations of variables that represent symmetries, it can not detect the particular structure of the symmetry group imposed by interchangeable FO domains. However, a succesful preprocessor for SAT solvers that partially detects FO interchangeability symmetry is described here and is available for download.


Is F<: with bottom undecidable? We all know that F<: is undecidable: http://www.cse.chalmers.se/~abela/lehre/SS07/Typen/pierce93bounded.pdf

However, I have difficulties finding that anyone claiming the version with bottom added being also undecidable: https://www.cs.indiana.edu/pub/techreports/TR492.pdf

Intuitively F<: with bottom should be undecidable, but if one claims that without proving it, I feel it's just a sloppy belief. In particular, I think that the proof must involve showing S-BOT rule from the version with bottom must be either non-existent, or can be removed from the derivation tree, which doesn't seem immediate to me.

So I am wondering if there is any source actually showing adding bottom doesn't turn the calculus decidable (as expected)?

OK, fine. Since people seem to keep liking this question, I decide to answer this question myself.

TLDR : yes, F<:+bot is undecidable, as shown a proof of translation from it to F<: in the following link by myself: https://gitlab.com/JasonHuZS/AlgDotCalculus/blob/master/agda/FsubBot.agda

bot⇒full : ∀ {Γ S U} → List.map _* Γ ⊢ S * <: U * → Γ ⊢F S <: U
full⇒bot : ∀ {Γ S U} → Γ ⊢F S <: U → List.map _* Γ ⊢ S * <: U *

Despite such intuitive fact, I have to emphasize that, in the presence of subtyping, a syntactical extension of an undecidable language does not have to generate yet another undecidable language. More specifically, the decidability is a very global property of a language which depends on every interaction of the rules, and should not be assumed if a proof is not present.

In the case of F<:, the proof can easily discharge all usage of bot, merely because in F<:+bot, there isn't other creative way of using bot, to a point that it turns the translation of derivation tree to a non-trivial level.

In particular, I am working on another calculus (D<: in another source code), in which bot has so creative behavior to a point that the translation from it to F<: does not generally hold, and therefore, the calculus could be decidable, or, if it's undecidable, F<: does not reside in it as a sub-language.


Matrix multiplication algorithms for research I am implementing a matrix library for use in my research. This should support 2D matrices of size 100x100 (or more perhaps later on). I am a little confused about the algorithm I should be using for matrix multiplication.

I am extremely curious to know what kind of algorithms my peers use?
The following are the possible choices:

Naive $O(n^3)$
Strassens Algorithm $O(n^{2.807})$
Coppersmith Winograd Algorithm $O(n^{2.375})$

Obviously (3) is quite complicated and may take quite a few tries to get right. Is it worth the effort ? I must mention here that speed is paramount for my usage as I will have a number of multiplication calls.

The fastest way to multiply dense matrices on a modern computer is to call BLAS.


Is a CEK machine an implementation of a CESK machine? We know that a CESK machine can be defined as:

  a state-machine in which each state has four components: a (C)ontrol component, an (E)nvironment, a (S)tore and a (K)ontinuation. One might imagine these respectively as the instruction pointer, the local variables, the heap and the stack.

Ed Kmett writes

  Video from my recent twitch stream on CEK machines is up!

Matt Might writes:

  Writing CEK-style interpreters (or semantics) in Haskell

To Matt's credit - he also writes about CESK machines in racket and Java.

But when we read the original paper ("A Calculus for Assignments in Higher Order Languages") by Matthias Felleisen and Dan Friedman - we find that the original paper describes a CESK machine.

The paper also describes a CS machine - but not a CEK machine. The point being the Continuation and the Store are essential, but the Environment and the Continuation are negotiable.

My question is: Is a CEK machine an implementation of a CESK machine? (ie isn't the Store Essential?)

The store in a CESK machine is the "heap", where mutable pointer-based data structures live.

If your language is purely functional, then its operational  semantics don't need a store. Take it out, and you get the CEK machine.
If your language does not have control operators (such as call/cc or exceptions), then you can get away with the K (the continuation).
If you don't want to model environments and closures explicitly -- that is, you don't mind a substitution-based semantics -- then you don't need the E (the environment). Calculi for classical logic (which have control operators but no state) often end up looking like CK machines.
If you have a purely functional language without control effects, then you can use the program itself as the abstract machine state, and the reduction rules will be the small-step operational semantics for that language.