How to homomorphically and "efficiently" evaluate $$(a_1 + b_1) \cdot c_1 + (a_2 + b_2) \cdot c_2 + \ldots + (a_n + b_n) \cdot c_n$$ Can i evaluate a formula $(a_i + b_i) \cdot c_i$ if i have the encryption of $a_i,b_i,c_i$ respectively using a homomorphic encryption scheme that supports multiplications and additions, supposing that each value is a small integer? I am aware of BGN scheme that evaluates 2-DNF formulas but in my scheme i want the other way around. Instead of $a_1 \cdot b_1 + a_2 \cdot b_2 + \ldots +a_n \cdot b_n$ i want to evaluate $(a_1 + b_1) \cdot c_1 + (a_2 + b_2) \cdot c_2 + \ldots + (a_n + b_n) \cdot c_n$

The original question seems to assume that the BGN scheme is the state-of-the-art for problems like this (correct me if I'm wrong :)), so for what it's worth:

The BGN scheme scheme is a prototypical version of a somewhat homomorphic encryption scheme -- the bilinear map gives you a single multiplication on any ciphertext still in the source group $\mathbb{G}$, and (of course) unbounded additions.

It's worth noting that the additively homomorphic property (ie, the unbounded additions) comes from the algebraic representation of the ciphertexts. For similar reasons, El Gamal has multiplicatively homomorphic ciphertexts (unbounded multiplications, no additions), and Paillier has additively homomorphic ciphertexts (no multiplications, unbounded additions).

I think around a year after BGN, Craig Gentry came out with the first fully homomorphic encryption scheme (unbounded multiplications, unbounded additions).

The current state-of-the-art for FHE schemes is some combination of:

((Below are PDF links to ePrint.))

Fully Homomorphic Encryption without Modulus Switching
from Classical GapSVP
Fully Homomorphic Encryption with Polylog Overhead
Somewhat Practical Fully Homomorphic
Encryption

Another Thought:

In case the word "efficiently" in the title was intended to be interpreted as "not FHE," here's an independent observation of mine that might be useful for situations like you ran into just now -- i.e. "I think I need more multiplications than the bilinear map in BGN allows, but I don't want to take the huge hit of FHE..."

If you implement a BGN-like scheme, but substitute a multilinear map for the bilinear map..

See: Candidate Multilinear Maps from Ideal Lattices

..then you should be allowed up to $\kappa$ multiplications, for multilinearity parameter $\kappa$.

The complexity of the GGH multilinear map depends on $\kappa$, but so long as $\kappa=O(1)$, I have a feeling there wouldn't be much difference between the resulting scheme and the BGN scheme in terms of concrete efficiency. (In fact, it's an interesting question on its own!)

In any case, suppose you ran into a situation where you needed.... THREE multiplications per plaintext... Think about using a multilinear map.

A few more details for intuition about what multilinear maps are, if they're new to you:

BGN uses groups $(\mathbb{G}, \mathbb{G}_T)$ and a map $e: \mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_T$.

IIRC, the GGH multilinear map with, say, $\kappa = 2$ can be seen as reducing (in the simplest case) to groups $(\mathbb{G}_0, \mathbb{G}_1, \mathbb{G}_2)$ and a set of bilinear maps, written generally as $e = \{e_i\}_{i\in [0,...,\kappa-1]}$ where for all $i$, $e_i : \mathbb{G}_i\times\mathbb{G}_i\rightarrow\mathbb{G}_{i+1}$.


Best bounds for the longest path optimization problem in cubic Hamiltonian graph? optimization problem

Input: cubic Hamiltonian graph

feasible solution: A simple path

measure to optimize: length of the simple path

Design a polynomial-time algorithm that outputs the longest path it can find.

To my knowledge, longest path problem does not have polynomial-time constant-factor approximation in cubic Hamiltonian graphs unless P=NP. This problem is interesting since the input is cubic graph and has a n-length Hamiltonian cycle.

On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs, Journal of Algorithms 31, 249-268, 1999.

Check out
"Finding long paths and cycles in sparse Hamiltonian graphs"
by Feder, Motwani, and Subi from STOC 2000. AFAIK, this is the best algorithm known to date.


Graph with minimum number of edges having given sets of nodes as its paths Consider the following problem:

Input: a list of subsets $P_1, P_2, \ldots, P_k \subseteq V = \{1, \ldots, n\}$
Output: a graph $G = (V,E)$ with minimum number of edges such that

for every $P_i$ there is a path in $G$ which has $P_i$ as its set of vertices.

Has this problem been studied?
Does it have a name?
What is the fastest known algorithm for solving it?

This problem is NP-complete, even for the special case $|P_k|\le 3$. I will give a reduction from Vertex Cover. I will refer to the sets $P_1,\ldots,P_k$ in the question as constraints: binary or ternary, depending on their cardinality.

Let $(V',E',k)$ be an instance of Vertex Cover: Is there a subset $S$ of $k$ vertices from $V'$ such that $S$ covers (that is, intersects) all edges in $E'$?

We add a distinguished vertex $\bullet$; that is, $V=V'\cup\{\bullet\}$. We add binary constraints for all pairs of vertices in $V'$: for each $\{i,j\}\subseteq V'$, we add the constraint $\{i,j\}$. We then add ternary constraints for each edge in $E'$: for each $\{i,j\}\in E'$, we add the constraint $\{i,j,\bullet\}$.

We ask whether there is a graph with $\binom{|V'|}{2}+k$ edges that satisfies the above constraints. The answer (yes or no) is an answer to the Vertex Cover question.

Why would that work? Because of the binary constraints, we know that edge $\{i,j\}$ is selected. So, the only task that remains is to pick between $\{i,\bullet\}$ and $\{j,\bullet\}$. That's exactly the task we have in the original Vertex Cover problem: Pick which endpoint of an edge we use to cover it.


Selection algorithm on depth-$\text{O}(\log n)$ sorting network Is there a sorting network of depth $\text{O}(\log n)$ for selecting the $i$th order statistic?

Remark: I've already asked a related question in a different context.  Although the two questions are related, this is not a duplicate of the other one.

You can construct selection networks of depth O(log n) using graph expanders or using variants of the AKS sorting network.

S. Jimbo and A. Maruoka, A Method of Constructing Selection Networks with $O(\log n)$ Depth,SIAM J. Comput. 25, pp. 709-739, http://dx.doi.org/10.1137/S0097539793248329


Transitivity check vs. Transitive Closure Is checking transitivity of a digraph not easier than (in terms of asymptotic complexity) taking the transitive closure of the digraph? Do we know any lower bound better than $\Omega(n^2)$ to determine if a digraph is transitive or not?

Below I'll show the following: if you have an O($n^{3-\varepsilon}$) time algorithm for checking if a graph is transitive for any $\varepsilon>0$, then you have an O($n^{3-\varepsilon}$) time algorithm for detecting a triangle in an $n$ node graph, and hence (by a paper from FOCS'10) you'd have an O($n^{3-\varepsilon/3}$) time algorithm for multiplying two boolean $n\times n$ matrices, and hence by a result of Fischer and Meyer from the 70s, this also implies an O($n^{3-\varepsilon/3}$) time algorithm for transitive closure.

Suppose that you want to detect a triangle in an $n$ node $G$. We can now create the following graph $H$. $H$ is tripartite with partitions $I,J,K$ on $n$ nodes each. Here each node $x$ of $G$ has copies $x_I,x_J,x_K$ in the parts $I,J,K$. For each edge $(u,v)$ of $G$ add directed edges $(u_I,v_J)$ and $(u_J,v_K)$. For each nonedge $(u,v)$ of $G$ add the directed edge $(u_I,v_K)$.

First, if $G$ contains a triangle $u,v,w$, then $H$ is not transitive. This is since the edges $(u_I,v_J),(v_J,w_K)$ are in $H$ but $(u_I,w_K)$ is not. Second, if $H$ is not transitive, then there must exist some directed path from some node $s$ to some node $t$ in $H$ such that $(s,t)$ is not a directed edge in $H$. However, the longest paths in $H$ have $2$ edges, and so any such path must be of the form $(u_I,v_J),(v_J,w_K)$ and $(u_I,w_K)$ is not in $H$, hence $u,v,w$ form a triangle in $G$.


Lower bounds for noncommutative arithmetic circuits with exact division? It is known that for general arithmetic circuits there is not much of a difference between standard model and one with division: any circuit with divisions that computes a polynomial can be simulated by a circuit without divisions with only polynomial blow-up.

However, in the non-commutative world, such a reduction is unknown. In fact, although exponential lower bounds are known for noncommutative formulas without division, proving lower bounds for noncommutative formulas with division is a big open question.

  Are we aware of lower bounds for noncommutative circuits with division, but where every gate computes a polynomial (and not just a rational function)?

To my knowledge, such a reduction is in fact known: Hrubes and Wigderson ITCS 2014 show how division gates can be eliminated from non-commutative circuits and formulas which compute polynomials.

They also provide exponential-size lower bounds for non-commutative formulas with division (not circuits) that compute any entry of the matrix inverse function $X^{-1}$.

Moreover, your main question about lower bounds for non-commutative circuits, is not known (while for formulas it is known as mentioned above), because non-commutative circuits in which each gate computes a polynomial (not a rational function) with division constitutes a class which is at least as strong as non-commutative circuits. But there is no known super-polynomial non-commutative circuit lower bound (see [Hrubes, Yehudayoff and Wigderson STOC 2010] on this).


Linear time algorithm for finding shifted max Assume that we are given an array $A[1..n]$ containing nonnegative integers (not necessarily distinct).

Let $B$ be $A$ sorted in the nonincreasing order.
We want to compute
$$m = \max_{i\in [n]} B[i]+i.$$

The obvious solution is sorting $A$ and then compute $m$. This gives an algorithm that runs in time $O(n \lg n)$ in the worst case.

  Is it possible to do better? Can we compute $m$ in linear time?

My main question is the one above.
But it would be interesting to know about the following generalization of the problem.

Let $B$ be $A$ sorted according to some comparison oracle $\leq$
and $f$ a function given by an oracle.
Given $A$ and oracles for $\leq$ and $f$, what can we say about the time needed to compute $m = \max_{i \in [n]} f(B[i],i)$?

We can still compute $m$ in $O(n \lg n)$ time. But can we prove a super-linear lower-bound for this generalized case?

If the answer is yes does the lower-bound hold if we assume that $\leq$ is the usual order on integers and $f$ is a "nice" function (monotone, polynomial, linear, etc.)?

We can compute $m$ in linear time.

For simplicity suppose that the arrays are 0 based: $A[0..n-1]$, $B[0..n-1]$.
We want to compute $m = \max_i B[i]+i$.

Let $max = \max_i A[i]$.
Obviously $max \leq m$.

Let $A[j]$ be $B[k]$ after sorting. If $A[j] \leq max - n$ we have
$$B[k] + k \leq B[k] + (n-1) = A[j] + (n-1) \leq (max-n) + (n-1) = max-1 < max \leq m.$$

Therefore we can ignore $A[j]$ when $A[j] \leq max - n$.
We only need to consider the numbers in the range $[max-n, max]$.

We can use counting sort to sort the numbers in $A$
which are in the range $[max-n, max]$ in linear time and
use the sorted list to compute $m$.


Inductive definition of ECTL*: how are recursive formulas forbidden? In [1], the extended computation tree logic ECTL* is inductively defined as the propositional formulas over all E($A(F_1,..F_n)$), where E is the existential path quantifier and $A$ some Büchi automaton whose alphabet is $2^{\{F_1,..,F_n\}}$ for some ECTL* formulas $F_1,..F_n$.

Obviously E($A(F_1)$) with $F_1=$E$(A(F_1)$) is not well-defined for some Büchi automata. So what does inductively defined exactly mean in this case?

Maybe that no $F_1,..,F_n$ may use $F_1,..,F_n$ in their respective Büchi automata, but the Büchi automata may occur recursively if the alphabet is correctly exchanged. Or may, e.g., $F_1$ use $F_2,..,F_n$, as long as there is no mutual recursion between the $F_i$?

Update: Does the following define ECTL*'s syntax?

$\langle\text{sf}\rangle::=\;
  \langle\text{atomic prop}\rangle\;\big\vert\;
\langle\text{sf}\rangle \vee \langle\text{sf}\rangle\;\big\vert
\neg\langle\text{sf}\rangle\;\big\vert\; \text{E
}\langle \text{Buechi}\;\mathcal{A}\rangle (\langle\text{sf}\rangle,\dots,\langle\text{sf}\rangle);
$

(as opposed to
$\langle\text{sf}\rangle::=\;
  \langle\text{atomic prop}\rangle\;\big\vert\;
\langle\text{sf}\rangle \vee \langle\text{sf}\rangle\;\big\vert
\neg\langle\text{sf}\rangle\;\big\vert\; \text{E
}\langle \text{Buechi}\;\mathcal{A}\rangle (F_1,\dots,F_n);
$ where the $F_i$ are ECTL* formulas).

 In detail,

[1] says

  Formulas of ECTL* are inductively defined as usual and built from
  propositional variables using boolean connectives and containing the
  formula $E(A)$ for each Büchi automaton $A$ over an alphabet
  $2^{\{F_1,..,F_n\}}$ where the $F_i$ are ECTL* formulas.

[1] CTL* and ECTL* as fragements of the modal $\mu$-calculus by Mads Dam

The formula in your statement

  Obviously E(A(F1)) with F1=E(A(F1)) is not well-defined for some Büchi automata. So what does inductively defined exactly mean in this case?

cannot arise if you built ECTL* inductively. This means, in standard academic parlance, we would present a syntax definition of the form below.

Let $Prop$ be a set of propositions and $p$ range over $Prop$. If $\varphi_1, \ldots, \varphi_n$ are formulae of ECTL* let $\mathcal{A}[\varphi_1, \ldots, \varphi_n]$ denote an automaton $\mathcal{A}$ over the alphabet $\mathcal{P}(\{\varphi_1, \ldots, \varphi_n\})$ of subsets of the $n$ formulae shown.

$ \varphi ::= p ~\mid~ \varphi \land \varphi ~\mid~ \neg \varphi ~\mid~ \mathsf{E}(\mathcal{A}[\varphi_1, \ldots, \varphi_n])$

I believe there is some confusion in how you may be reading the presentation above. In academic terms this qualifies as BNF. I see that the Wikipedia page gives a slightly different presentation.
However, the definition above
is equivalent to the BNF grammar you give below. It is not a "relaxed BNF" to use your terminology. It is just an inductive definition where some BNF is used where convenient.

  BNF: $\langle\text{sf}\rangle::=\;   \langle\text{atomic prop}\rangle\;\big\vert\; \langle\text{sf}\rangle \vee
\langle\text{sf}\rangle\;\big\vert
\neg\langle\text{sf}\rangle\;\big\vert\; \text{E }\langle
\text{Buechi}\;\mathcal{A}\rangle
(\langle\text{sf}\rangle,\dots,\langle\text{sf}\rangle); $

Academic writing mixes English and BNF when we make inductive definitions because it is convenient. To see the need for convenience, consider your grammar. It does not inform the reader what $\langle\mathrm{atomic~prop}\rangle$ and what $\langle \mathrm{sf}\rangle$ are. You have chosen an intuitive naming convention, so one can guess the first represents atomic propositions. But in general, we want to have short symbols in our papers, so we prefer a one-time cost of verbose English, which is why we write something like "where $\varphi$ is an ECTL* formula". This text does not in any way change the language being defined.

To your specific question:
Your formula $F$ with $F = E(A(F))$ is not a formula of ECTL*. This type of formula cannot arise as the result of an inductive of the form above. This impossibility has nothing to do with the difference in presentation between BNF as you write it and inductive definitions in papers. To derive your formula, you need some atomic propositions, and a sequence of syntactic compositions to build up the more complex formula.

Now about fixed points. There is some confusion here too. BNF grammars are specific ways to present certain inductive definitions. They are not the only way and they do not cover all inductive definitions. Inductive definitions are a more general class and can be presented in many ways. Least fixed points are a strict generalisation of inductive definitions. Below I will only give an example of how both the BNF grammar above and the inductive definition I gave define a least fixed point. I emphasise that both definitions give rise to the same least fixed point.

Let's assume that $Prop = \{q,r,s\}$ is a set of atomic propositions and $p$ ranges over $Prop$. Consider a lattice $L$ which contains all sets of sequences of symbols appearing in the definitions above. The formulae of ECTL* are one specific element of this lattice. Consider a function $G:L \to L$, which is generated by the definitions above.

$G(\emptyset) = Props$, which accounts for $q$, $r$ and $s$ being formulae, or for the instantiation of $\langle \mathrm{atomic~prop}\rangle$ in BNF.

$G(G(\emptyset)) = G(Props)$, which is the set containing elements, $q \land r$, $q \land s$, $r \land s$, $\neg q$, $\neg s$, $\neg r$, $E(\mathcal{A}(\{q\}))$, $E(\mathcal{A}(\{r\}))$, $E(\mathcal{A}(\{s\}))$, $E(\mathcal{A}(\{q,r\}))$, $E(\mathcal{A}(\{q,s\}))$, $E(\mathcal{A}(\{r,s\}))$, $E(\mathcal{A}(\{q,r,s\}))$.
This is equivalent to applying the formation rules $\langle \mathrm{sf} \rangle \lor \langle \mathrm{sf} \rangle$, $\neg \langle \mathrm{sf} \rangle $ and the others with $\langle \mathrm{sf} \rangle$ being replaced by $\langle \mathrm{atomic~prop}\rangle$. Alternatively, this is equivalent to one unwinding of the inductive definition where we say, if $\varphi_1$ and $\varphi_2$ are atomic propositions, then $\varphi_1 \land \varphi_2$, $\neg \varphi_1$, $E(\mathcal{A}(\{\varphi_1, \varphi_2\}))$, etc are formulae.

The set $G(G(G(\emptyset)))$ contains $q \land r\land  s$, $r \land \neg s$, $\neg (q \land s)$, $\neg E(\mathcal{A}(\{r\}))$,  $E(\mathcal{A}(\{q \land s, \neg r\}))$ and so on.

The set of ECTL* formulae is the least fixed point of the function $G$ above. Note that I have not explicitly defined it, but this is possible to do and might be an insightful exercise to work out the details. Equivalently, you can obtain exactly the same fixed point by the BNF grammar or the inductive definition I give.

The kind of formula you suggest will occur in a fixed point that is not a least fixed point. I emphasise that both the BNF grammar and the inductive definition I give generate the same function $G$, hence they have the same least fixed point and the same set of fixed points. So, if the inductive definition allows for a certain formula, your BNF must allow for the at formula, and vice versa.


Weighted cycles in weighted line graphs Assume a planar graph G, and all its vertices have degree at most 4.
 Consider a cycle in G. The weight of cycle c is the total weight of its vertices, and a vertex is weighted with the following manner:

For example look at vertex v, if cycle c traverses vertex v by passing through e2 and e4 then it would cost w1 and if it traverses v by passing through e4 and e3 then it would cost w2 and so on! (G is undirected, so traversing v by passing through e4 and e3 costs the same as traversing v by passing through e3 and e4, and all possible traversal from a vertex contain weights; some of them are showed with pink curves in pic.)

1-What is the complexity of finding a cycle with total weight k? (k is a given value)
2-Is finding weighted cycles in G harder than finding cycles in general weighted graphs?

this is also the link of pic:
http://rapidshare.com/files/435859757/a.bmp

For the second problem, this question is no harder than finding a cycle of a specific weight k in a general weighted graph in the following sense: consider the line graph of G, that is, a graph L(G) with V(L(G)) = E(G), and two nodes u,v in L(G) are adjacent if the corresponding edges in G are incident to each other. By assigning weights to the edges of L(G) according to your definition, it reduces to the normal weighted cycle problem.

Thus to the first problem, in general if we do not have any constrain on k, we can assign 1/|V(G)| to each edge in an unweighted graph G, and reduced the Hamiltonian cycle problem to the weighed cycle problem by asking k=1, thus it is NP-hard. If you are asking non-negative integral weights, then the algorithm mentioned in the MO post again works since we can subdivide the edges into an unweighted graph. But be careful since the size of the subdivided graph will depends on the total weight on the original graph.


On 1-dimensional cellular automata I'm interested in linear 2-state cellular automata (with local rules only) that could compute the majority function. Say the state of a cell is either 0 or 1. Is it possible to have a cellular automaton that sets all cells to 1 if the majority of initial states is 1 and sets all cells to 0 if the majority of initial states is 0? The cellular automaton could be synchronous or asynchronous. I tend to believe that the answer is negative (mainly because of rule locality). Any literature on this problem? I also believe that one could approximate it in the sense that one could devise a cellular automaton that fails only on a small fraction of its inputs (purely experimental at this point).

This is a well known problem. It's known to be impossible to solve exactly, but either approximable in the sense you describe or solvable exactly if you relax the conditions under which it recognizes a majority: see http://en.wikipedia.org/wiki/Majority_problem_(cellular_automaton)


Minimal clique edge cover vs minimalist (assignment-minimum) ones Given a graph $G=(V,E)$, a clique edge cover is a collection $C$ of subsets of $V$ such that each element $c$ of $C$ is a clique ($c \times c \subseteq E$) and $G$ is the union of these cliques ($E = \bigcup_{c\in C} c\times c$).
The cover is said to be minimal if $|C|$ is minimal, i.e. the number of cliques used to cover the graph is minimal.
Let us say that the cover is minimalist if $\sum_{c\in C} |c|$, i.e. the sum of clique sizes, is minimal.
(Is there a better term than minimalist here? Does it appear in the literature?)
There exists minimal covers that are not minimalist covers.
Consider for instance, the graph where $V=\{a,b,c,d,e\}$ and $E$ is covered by $C = \{\{a,b,c\}, \{b,c,d\}, \{c,d,e\}\}$. This is a minimal covering of the graph, but not a minimalist one, since it is also covered by $\{\{a,b,c\}, \{b,d\}, \{c,d,e\}\}$.
Question:
Is the converse true? Is there any graph having a minimalist cover that contains more than the minimal number of cliques needed to cover it?

Consider a graph on vertex set $V_1\cup V_2\cup V_3\cup V_4\cup \{a,b,c,d\}$ where $|V_1|=|V_2|=|V_3|=|V_4|=n$. The edge set $E$ is covered by $C=\{V_1\cup\{a,c\},V_2\cup\{a,d\},V_3\cup\{b,c\},V_4\cup\{b,d\},\{a,b\},\{c,d\}\}$.
When $n$ is large enough, any minimalist cover must contain the four maximum cliques $V_1\cup\{a,c\}$ and so on, so it is not hard to show that $C$ is minimalist. However replacing the two edges $\{a,b\}$ and $\{c,d\}$ with a single clique $\{a,b,c,d\}$ results in less number of cliques.


Relation between Kleene star, union and difference in relation algebra So I'm wondering about some finer points of relation algebra, a field in which I'm not an expert:

Given relations $A$, $B$ and $C$ over the same set $S$, is it always true that $A^*\subseteq (B\cup C)^*$ iff $(A\setminus B)^*\subseteq C^*$ ?

Here, $A^*$ denotes the reflexive, transitive closure of $A$, $\cup$ is set union, and $\setminus$ is set difference.


What would be a complete QC circuit? In classical computing NAND is a complete set (functionally complete) of binary operations, namely any Boolean circuit can be expressed using NAND gates.

Is there an equivalent for quantum computing circuit? It should be possible imho to have such a complete set because any rotation ob Bloch sphere is reducible to Euler angles based rotation matrices: $R=X(\alpha)Y(\beta)Z(\gamma)$.

Are there any universal quantum gates?

Not for single gates.

{NAND} may also be represented as two gates {AND, NOT}, and remains a minimally functionally complete set of classical gates.

The Hadamard gate and Toffoli gate are one minimal set of universal quantum gates.


Formal Representation of Haskell Data-Types I come from Haskell programming and currently writing my (Diploma/Master) thesis. I'm having trouble finding a formal/mathematical notation for a Haskell data-type.

The Haskell data type is:

data ARE = ARE [(ARF, ARF)] [ARF]   -- Haskell form
type ARE = ( [(ARF, ARF)], [ARF] )  -- alternate form

An ARE is an affine randomized encoding and an ARF is an affine randomized function. You can think of an ARF just as an abstract entity, just like a field or group element. My problem is how to formally notate a definition for an ARE.

First, I'll try to describe what an ARE is in english: An ARE is a tuple (in the "alternate form", in my Haskell program it's represented as in the "Haskell form") containing:

a list (not a set since it could contain duplicates) containing tuples. Each of these tuples is just two ARFs
a list of ARFs

What I'm looking for is a formal notation of such an ARE.

(edit: removed nonsense notation proposal...)

About the expected audience (and their knowledge domain) of my thesis: I will provide Haskell code, but the entire thesis should be understandable by someone who is not a programmer (and in particular no Haskell programmer). The reader will need some knowledge in cryptography, computer science (but not programming) and basic mathematics (some field theory, especially the finite fields $\mathbb{F}_{2^n}$). In the text I simply want to tell the reader what AREs are and how I transform general expressions to AREs.

Unter the assumption, that lists simply represents arbitrary sets, the mathematical notation should probably read:

  An ARE is an element of the following set:

  $\{ (P, Q) \mid P \subseteq ARF \times ARF, Q \subseteq ARF \} $

But as you stated, lists in your domain are always finite, ordering is not important, but multiplicity is. Thus, I would model the lists as finite multisets. Using an explicit notation for mulitsets, a possible definition would be:

  An ARE is an element of the following set:

  $\{ (P_\chi, Q_\xi) \mid P \subseteq ARF \times ARF,
                           P~\text{finite},~
                           \chi \in (P \to \mathbb{N}^+),
                           Q \subseteq ARF, Q~\text{finite},~
                           \xi \in (Q \to \mathbb{N}^+) \} $

Here, the notation $P_\chi$ denotes a multiset with P being the underlying ordinary set and $\chi \in P \to \mathbb{N}^+$ being the multiplicity function of the multiset.


Secure MAC when the adversary has a verification oracle A message authentication code (MAC) is defined by a triple of efficient algorithms $(\mathsf{Gen}, \mathsf{MAC}, \mathsf{Verif})$, which satisfy the following (the definition is taken from section 4.3 of the Katz-Lindell book):

On input $1^n$, the algorithm $\mathsf{Gen}$ generates a key $k \ge n$.
On input $k$ generated by $\mathsf{Gen}$, and some message $m \in \{0,1\}^*$, the algorithm $\mathsf{MAC}$ generates a tag $t$. We write $t \gets \mathsf{MAC}_k(m)$.
On input a triple $(k,m,t)$, the algorithm $\mathsf{Verif}$ generates a single bit $b$. We write $b \gets \mathsf{Verif}_k(m,t)$.

It is required that for all $k$ output by $\mathsf{Gen}$ and all $m \in \{0,1\}^*$, we have $\mathsf{Verif}_k(m, \mathsf{MAC}_k(m)) = 1$.

The security requirement is defined via the following experiment, between the challenger and the adversary $A$:

$k \gets \mathsf{Gen}(1^n)$.
$(m,t) \gets A^{\mathsf{MAC}_k(\cdot)}(1^n)$.
Let $Q$ denote the set of all queries that $A$ asked to its oracle.
The output of the experiment is defined to be 1 if and only if:

$\mathsf{Verif}_k(m, t) = 1$, and
$m \notin Q$.

The MAC is considered secure if the probability that the experiment outputs 1 is negligible in $n$.

The experiment above resembles a "chosen plaintext" experiment against a symmetric encryption scheme, where the adversary can obtain ciphertexts corresponding to messages of his choice. In a more powerful attack, called "chosen ciphertext" attack, the adversary is allowed access to a decryption oracle as well.

So, my question is:

  What happens if we allow the MAC-adversary to access a verification oracle as well? In other words, what if line 2 of the experiment is replaced with the following:

  $(m,t) \gets A^{\mathsf{MAC}_k(\cdot),\ \ \mathsf{Verif}_k(\cdot, \cdot)}(1^n)$.

  Notice that in the new experiment, $Q$ only includes queries $A$ asks from the $\mathsf{MAC}_k$ oracle.

If there is a secure message authentication code according to either definition,

  then there is a system that the book's definition classifies as a secure

  message authentication code and your definition classifies as insecure.

Let $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.02 in},\hspace{-0.05 in}\operatorname{Verif}\hspace{.02 in}\rangle\:$ be secure according to either definition. $\;\;$ Since the book's definition

is weaker than your definition, it is in particular secure according to the book's definition.

Fix some efficiently-computable and efficiently-invertable coding of

ordered pairs, for example, concatenating an efficiently-computable and

efficiently-invertible prefix-free representation  of the left entry to the right entry.

Let $\operatorname{MAC}_k\hspace{-0.09 in}'$ work by pairing the output of $\operatorname{MAC}_k$ with the empty string.

Let $\operatorname{Verif}_k\hspace{-0.09 in}'$ accept if and only if [[$\operatorname{Verif}_k$ would accept the message and the left entry

of the tag] and [the right entry of the input is a prefix of $k$]]. $\;\;$ $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ is clearly efficient and satisfies the requirement. $\;\;\;$ Since [pairing the tags with the empty string for]

and [taking the left entry of the output of] a feasible adversary attacking the book's

definition of the security of $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ cannot have a non-negligible probability

of breaking the book's definition of security for $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.02 in},\hspace{-0.05 in}\operatorname{Verif}\hspace{.03 in}\rangle\:$, $\:$ the book's

definition also classifies $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{-0.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ as a secure message authentication code.

However, once an adversary gets any valid message-tag pair for $k$, $\:2\hspace{-0.03 in}\cdot \hspace{-0.03 in}(\operatorname{length}(k)\hspace{-0.04 in}+\hspace{-0.05 in}1)\:$

adaptive queries to $\operatorname{Verif}_k\hspace{-0.09 in}'$ is sufficient to learn $k\hspace{.01 in}$, which would allow forgeries on any message.

Thus your definition classifies $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{-0.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ as insecure. $\;\;\;$ QED

  The strong unforgeability versions of the two definitions are equivalent.

(The "strong unforgeability" versions are obtained by replacing $Q$ with

the set $Q^+$ given in my next sentence, and that is needed to make the

encrypt-then-mac construction provide ciphertext integrity and be IND-CCA2.)

Initialize $\:Q^+\:$ as the empty set, and put $\: \langle m,\hspace{-0.03 in}t\rangle \:$ into $\:Q^+$

each time $\operatorname{MAC}_k$ outputs $t$ on a query of $m$ .

Define a query to be trying if and only if it is submitting

to $\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$ a pair that was already put in $\:Q^+\:$.

Define a query to be early-trying if and only if it is trying and

did not come after any trying query that $\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$ accepted.

$B^{\hspace{.02 in}\operatorname{MAC}_k(\cdot)}\hspace{-0.02 in}\left(\hspace{-0.03 in}1^n,\hspace{-0.02 in}q,\hspace{.02 in}j\hspace{-0.01 in}\right) \;$ interacts with $A$ as follows:

Using less than $\hspace{.02 in}j$ random bits, choose $\;\; r \: \in \: \left\{\hspace{-0.03 in}1,\hspace{-0.03 in}2\hspace{.02 in},\hspace{-0.03 in}3,...,\hspace{-0.02 in}q\hspace{-0.04 in}-\hspace{-0.04 in}2\hspace{.02 in},\hspace{-0.02 in}q\hspace{-0.04 in}-\hspace{-0.05 in}1,\hspace{-0.02 in}q\hspace{-0.02 in}\right\} \;\;$ almost uniformly.

"Forward" all of $A$'s $\:\operatorname{MAC}_k(\cdot)\:$ queries to $\:\operatorname{MAC}_k(\cdot)\:$ and give that oracle's

(actual) output to $A$, give $0$ as the outputs on the first up to $r\hspace{-0.04 in}-\hspace{-0.05 in}1$ trying queries,

and give $1$ as the outputs of $\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$ on queries to it that are not trying.

If $\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$ makes an $r$-th trying query, then output what that query was.

If $\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$ gives output, then give that same output.

With everything's randomness fixed, if $\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$ makes exactly $\:r\hspace{-0.03 in}-\hspace{-0.04 in}1\:$ early-trying queries and succeeds in the strong unforgeability version of your experiment, then

$B^{\hspace{.02 in}A,\operatorname{MAC}_k(\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n,\hspace{-0.02 in}q,\hspace{.02 in}j\hspace{-0.01 in}\right)\:$ succeeds in the strong unforgeability version book's experiment.

  Therefore $B$ is a constructive straight-line reduction from succeeding in the strong unforgeability version of your experiment with probability at least $\epsilon$ in a way that

  makes less than $q$ early-trying queries, to succeeding in the strong unforgeability

  version of the book's experiment with probability greater than $\;\; \left(\hspace{-0.03 in}\frac1q\hspace{-0.03 in}-\hspace{-0.03 in}\frac{q}{2\text{^}j}\hspace{-0.04 in}\right)\cdot \epsilon \;\;\;$.

  $B$ uses less than $\hspace{.02 in}j$ random bits, has to handle insertions into and membership

  testing for [a set with less than $q$ elements, each of which is an ordered pair whose

  left entry is one of the inner algorithm's queries to $\:\operatorname{MAC}_k\:$ and whose right entry is

  $\operatorname{MAC}_k\hspace{-0.02 in}$'s$\:$ response to that query], and has only trivial additional complexity beyond that.

Clearly, "ignore the $\operatorname{Verif}_k$ oracle" is a constructive straight-line reduction from succeeding

in the strong unforgeability version of the book's experiment to succeeding in the strong unforgeability version your experiment, and that reduction is almost perfectly tight.

Therefore the strong unforgeability version of your definition gives the same

asymptotic MACs as the strong unforgeability version the book's experiment.


How many negations do we need to compute monotone functions? Razborov proved that the monotone function matching is not in mP. But can we compute matching using a polynomial size circuit with a few negations? Is there a P/poly circuit with $O(n^\epsilon)$ negations that computes matching? What is the trade-off between the number of negations and the size for matching?

Markov proved that any function of $n$ inputs can be computed with only $\lceil \log (n+1)\rceil$ negations. An efficient constructive version was described by Fisher. See also an exposition of the result from the GLL blog.
More precisely:

Theorem: Suppose $f : \{0,1\}^n \to \{0,1\}^m$ is computed by a circuit $C$ with $g$ gates, then it is also computed by a circuit $C^*$ with $2g + O(n^2 \log^2 n)$ gates and $\lceil \log (n+1) \rceil$ negations.

The main idea is to add for each wire $w$ in $C$ a parellel wire $w'$ in $C^*$ that always carries the complement of $w$. The base case is for the input wires: Fisher describes how to construct an inversion circuit $I(x) = \overline x$ with $O(n^2 \log^2 n)$ gates and only  $\lceil \log (n+1) \rceil$ negations. For the AND gates of circuit $C$, we can augment $a = b \land c$ with $a' = b' \lor c'$, and likewise for OR gates. NOT gates in $C$ cost nothing, we just swap the roles of $w$ and $w'$ downstream of the NOT gate. In this way, the entire circuit besides the inverter subcircuit is monotone.

A. A. Markov. On the inversion complexity of a system of functions. J. ACM, 5(4):331–334, 1958.
M. J. Fischer. The complexity of negation-limited networks - A brief survey. In
Automata Theory and Formal Languages, 71–82, 1975


Is the Chomsky-hierarchy outdated? The Chomsky(–Schützenberger) hierarchy is used in textbooks of theoretical computer science, but it obviously only covers a very small fraction of formal languages (REG, CFL, CSL, RE) compared to the full Complexity Zoo Diagram. Does the hierarchy play any role in current research anymore? I found only little references to Chomsky here at cstheory.stackexchange, and in Complexity Zoo the names Chomsky and Schützenberger are not mentioned at all.

Is current research more focused on other means of description but formal grammars? I was looking for practical methods to describe formal languages with different expressiveness, and stumbled upon growing context sensitive language (GCSL) and visibly pushdown languages (VPL), which both lie between the classic Chomsky languages. Shouldn't the Chomsky hierarchy be updated to include them? Or is there no use of selecting a specific hierarchy from the full set of complexity classes? I tried to select only those languages that can be fit in gaps of the Chomsky hierarchy, as far as I understand:

REG (=Chomsky 3) ⊊ VPL ⊊ DCFL ⊊ CFL (=Chomsky 2) ⊊ GCSL ⊊ CSL (=Chomsky 1) ⊊ R ⊊ RE

I still don't get where "mildly context-sensitive languages" and "indexed languages" fit in (somewhere between CFL and CSL) although there seems to be of practical relevance for natural language processing (but maybe anything of practical relevance is less interesting in theoretical research ;-). In addition you could mention GCSL ⊊ P ⊂ NP ⊂ PSPACE and CSL ⊊ PSPACE ⊊ R to show the relation to the famous classes P and NP.

I found on GCSL and VPL:

Robert McNaughton: An Insertion into the Chomsky Hierarchy?. In: Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa. S. 204-212, 1999
http://en.wikipedia.org/wiki/Nested_word#References (VPL)

I'd also be happy if you know any more recent textbook on formal grammars that also deal with VPL, DCLF, GCSL and indexed grammars, preferable with pointers to practical applications.

In short: yes.

More particularly: Chomsky was one of the first to formalize a hierarchy relating languages, grammars, and automata. This insight is still very relevant and is taught in all intro courses on automata theory. However, the specific hierarchy Chomsky came up with and the names for the elements of the hierarchy aren't really significant anymore. We've since invented numerous formalisms which fall between levels of Chomsky's hierarchy, above it, or below it. And the names Chomsky used aren't particularly interesting, i.e. they aren't based on an interesting measure of complexity or anything, they're just numbers. Should mildly context sensitive languages be Type-1.5 or Type-1.7 or Type-1.3? Who cares. "Mildly context sensitive" is a much more informative name.

The Complexity Zoo is a bit different because it's full of all sorts of conditional equivalences and the like. A more modern hierarchy for automata theory wouldn't be linear (e.g., compare CFG vs PEG) but it would still have a well-known topology. To get a perspective on modern automata theory you should look at work on parser combinator libraries and some of the stuff on unification and type theory (though those both branch out far afield).


Poly-time Algorithm for Non-Linear Optimization As we know, linear programming is one of the most basic area of optimization theory, and computing an optimal solution can be excuted within poly-time. My question is about an extention of this notion.

Let $\vec{x}^T Q\vec{y} \geq \vec{d}$ be a system of multilinear constraints ,where $\vec{x},\vec{y} \in \mathbb{R}_{+}^n$

Question:
Under some limitations on the matrix $Q$, can the task of minimizing(maximizing) a function $f(\vec{x},\vec{y})$, be solved within poly-time ,or is there any case where this optimization is NP-hard ?

In general, even approximating a global optimum of a quadratic program, the simplest case of a nonlinear program, is NP-Hard (http://web.cs.ucdavis.edu/~rogaway/papers/qp.pdf), not to mention finding an exact solution of it (http://www.sciencedirect.com/science/article/pii/002001909090100C).

The polynomial-time solvability of a nonlinear program depends on its convexity, which means that your matrix $Q\in R^{n\times n}$ should be positive semidefinite (i.e. $\forall x\in R^n,\,x^TQx\geq 0$). An easy way to check this in polynomial time is to check the sign of the smallest eigenvalue of $Q$. In the case of a convex quadratic program, you can simply deploy an interior-point algorithm for quadratic programming, which has a poly-time worst case complexity.  These facts can be generalized for nonlinear programming.

As @Austin pointed, there's a way to convert your program to a Quadratically Constrained Quadratic Form. These problems are NP-Hard in general, but you can achieve an $\frac{4}{7}-$approximation of it's solution using an algorithm by Yinyu Ye, which solves an SDP-relaxation of the program.


Is Escardó's metric semantic for PCF+timeouts fully abstract ? In his 1999 workshop paper "A Metric Model of PCF", Martín Escardó  showed that it is possible to give a simple interpretation of PCF in the category of complete ultrametric spaces and nonexpansive maps.

He showed this model was adequate, and that it could model the addition of a timeout construct (i.e., an operator which would run its argument for some finite number of steps, and either yield an answer or signal an error if it failed to terminate within the time limit). He then suggested that it would be natural to investigate whether the metric model was fully abstract with respect to PCF+timeouts.

Has anyone investigated this, and if so, what's the answer?
Does PCF+timeouts realize the same functions as Turing machines, including at higher type?

(As an aside, how do you put accents into the text? I've dropped an accent from both  his first and last names. EDIT: Name fixed. I'm leaving this parenthetical in so that the comments to the post continue to make sense.)

Regarding your second question, I seem to remember that for higher-order types the question was linked closely to whether PCF+timeout was equivalent to Type Two Effectivity (Turing machines with infinite inputs and outpus), i.e., Kleene's second partial combinatory algebra. John Longley claimed for a while that Kleene's second algebra was equivalent to PCF+timeout+catch, but in the end he never published a detailed result.

On the other hand, I am pretty sure that John Longley opus magnum "On the ubiquity of certain total type structures" (Mathematical Structures in Computer Science 17(5) (2007), 841--953) implies that the higher-order functionals definable in PCF+timeout are precisely the hereditarily effective ones.


Majority function stability under deletion and addition of entries It is well known that the majority function is stable under random flipping of bits. That is, if $v$ is a random binary vector, and then we re-sample each bit of $v$ with probability $\delta$ and get $v^{'}$, then $\Pr[Maj(v) = Maj(v^{'})] = 1 - \frac{arccos(\delta)}{\pi}$

However, how will the majority function behave under addition or substruction of entries? Say we delete t random bits of v and add s random bits to get $v^{'}$. Is there any similar connection between $Maj(v)$ and $Maj(v^{'})$ in this scenario?

I conjecture that yes because the two cases are of course equivalent when s=t, however, I'm not sure how the connection behaves as a function of s,t, nor how to formally start to prove such connection.

Thanks!

$\newcommand{\bm}{\boldsymbol}$The two scenarios are not equal even when $s = t$. In the $s,t$ case you always re-sample the same number of bits, while in the $\delta$ case you get a binomial distribution in the number of bits flipped.

Let us define $\text{Maj}$ in a slightly different way than you might be used to, but assure yourself it is correct.

$$\text{Maj}(\bm{v}) := \left[\text{Sign}(\bm v) \geq 0\right]\\
\text{Sign}(\bm{v}) = \sum_i (-1)^{\bm v_i}$$
Now because $\bm v$ is a uniform random boolean vector, if we remove an element (say $v_i$) from it to from $\bm v'$ we can we can see that

$$\text{Sign}(\bm v') = \text{Sign}(\bm v) - (-1)^{v_i}$$

but this is very similar to the expression we'd get when adding a new bit $u_i$:

$$\text{Sign}(\bm v') = \text{Sign}(\bm v) + (-1)^{u_i}$$

Since $u_i$ is sampled from the uniform distribution of bits, we can replace it with random variable $u'_i = 1 - u_i$ which has an equivalent distribution, giving:

$$\text{Sign}(\bm v') = \text{Sign}(\bm v) - (-1)^{u'_i}$$

In other words, removing a bit from the vector is not distinguishable from adding a new bit from the perspective of the majority function. Therefore we can just assume $k = s+t$ and only add $k$ bits to the original $n$ in $v$.

So what is the chance that when we add those bits our majority function doesn't change? If $\bm v$ contained $n$ bits originally, that question is equivalent (again using $\text{Sign}$ as insight) to starting a simple symmetric random walk on the unit line and asking what the chance is that we are at the same side of the origin after $n + k$ steps as we were at $n$ steps. If we let $X_n$ be our random walk at step $n$ this works out to (for the positive side):

$$\Pr[X_n \geq 0, X_{n+k} \geq 0] = \Pr[X_n \geq 0]\Pr[X_{n+k} \geq 0 \mid X_n \geq 0]$$

With $Y$ being an independent random walk (and thus identical to $X$), we can say due to a random walks lack of memory that:

$$\Pr[X_{n+k} \geq 0 \mid X_n \geq 0] =\\ \sum_{i = 0}^n\Pr[X_n + Y_k \geq 0 \mid X_n = i] =\\ \sum_{i = 0}^n\Pr[X_k \geq -i]\Pr[X_n = i]$$

And thus:

$$\Pr[X_n \geq 0, X_{n+k} \geq 0] = \Pr[X_n \geq 0]\sum_{i = 0}^n\Pr[X_k \geq -i]\Pr[X_n = i]$$

We can apply a similar series of steps to find $\Pr[X_n < 0, X_{n+k} < 0]$. Then finally

$$\Pr[\text{Maj}(\bm v') = \text{Maj}(\bm v)] = \Pr[X_n \geq 0, X_{n+k} \geq 0] + \Pr[X_n < 0, X_{n+k} < 0]$$

Now as an exercise to the reader, fill in $\Pr[X_n = q], \Pr[X_n \geq q]$ and $\Pr[X_n < q]$ and simplify. These probabilities for random symmetric walk $X$ are well-known (see any textbook on random walks).


Finding a minimal DFA whose language has a desired intersection with another Suppose I have regular languages $B \subseteq A$, with corresponding (known) minimal deterministic finite automata $M_A, M_B$.

I would like to find another regular language $C$ such that $B = A \cap C$ that minimizes the size of $M_C$ (the minimal DFA corresponding to $C$).

In general $M_C$ can be much smaller than $M_B$. e.g. if we let $B$ the set of strings in $A$ that have even length, $M_C$ can be a two-state machine, while $M_B$ may be about as complex (or more) as $M_A$.

This feels like it should be an easy application of existing automaton minimization algorithms, but I'm not seeing it if so.

What looked liked the obvious thing to try to do is to to try and distinguish strings using an analogue of the Myhill-Nerode theorem, with the distinguishing relationship being that $x, y$ are distinct if there is some $s$ such that $xs, ys \in A$ but $xs \in B \neq ys \in B$, but the problem is that the corresponding indistinguishability relation is no longer transitive (I think) - Given $a$ indistinguishable from $b$ indistinguishable from $c$, there might be $s$ such that $as, cs \in A$ with $as \in B \neq cs \in B$, but $bs \not\in A$, so $s$ cannot be used to distinguish $a$ from $c$.

I think this arises from some genuine ambiguity in the problem - unlike normal DFA minimization, there's no reason to expect $M_C$ to be unique - two non-equivalent machines could represent languages $C \neq C'$ such that $A \cap C = A \cap C'$. It might be that those ambiguities don't matter and you can just resolve them arbitrarily, but I haven't been able to convince myself of that.

The problem is at least "reasonably tractable", as the corresponding decision problem is in NP, because such an automaton has size at most $|M_B|$, and we can determine whether a given automaton is a solution by testing its equivalence with the intersection automaton with states $M_A \times M_B$, and testing equivalence is in $P$. There's almost certainly some nice transformation into SAT or ILP that I haven't worked through yet because I'm hoping for a better solution.

Is this some well studied problem? Or can it be reduced to one?

$M_C$ must accept every word of $S^+ = B$ and reject every word of $S^- = A \setminus B$.

Let $A$ and $B$ be finite and such that both $S^+$ and $S^-$ are non-empty. Then exact computation of $M_C$ is NP-hard. [1]

[1] E.M. Gold. Complexity of Automaton Identification from Given Data. Information and Control, 37, 302-320 (1978)


Is minimax problem NP-Hard when the inner problem is NP-Hard ? Consider a minimax problem of the form:

$\min_{x\in X} \max_{u\in U} f(x,u)$

The outer problem $\min_{x\in X} f(x,u)$ for any given $u$ is polynomially solvable.

If the inner problem $\max_{u\in U} f(x,u)$ for any given $x$ is NP-Hard, is the entire problem also NP-Hard?

The answer to your question is "no", although for natural problems that you might be thinking about, it may be a good heuristic that if the inner problem is NP hard, the whole problem is probably hard as well. But you can come up with the following contrived counterexample.

Let $X = \{0,1\}$ and $U = \{0,1\}^n$, and let $\phi$ and $\theta$ be two 3SAT instances with the promise that exactly one of them is satisfiable. Let $f(0,u) = \phi(u)$ and let $f(1,u) = \theta(u)$. Then the minmax value is always 0, so computing it is in P, but for any fixed $x$, the problem is 3SAT and is NP hard.


iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation A question partly inspired by a recent question[1] on the utility of FSMs: Years ago noticed the following property of FSM transducers with $\epsilon$-transitions (which allow an "empty" transition without an output symbol). Its not complicated but not trivial either; it seems to be rarely taught, and also shows a close relationship between FSMs and TMs. It also shows up as a somewhat/seemingly natural mechanism for studying the Collatz conjecture by linking to questions on automata.[2]

Take any TM and consider the sequence of IDs, instantaneous description strings, associated with the TM tape and current state, also called a "computational tableau". (Details of the ID format/encoding are not nec so important but one simple method is to have the current TM state located embedded in the string at the current head position.) The sequential results of the TM after each TM step, $d_1, d_2, ... d_n$ can be computed by a FSM transducer with $\epsilon$-transitions, working left-to-right. am interested in answers to any of the following questions.

  What are some refs that refer to this correspondence/construction (computation of TM tableaus by FSM transducer iterations)?
  What is the earliest one to point it out?
  What are some notable results (if any) related to it?

Note, FSM transducers were also called "generalized sequential machines" in early automata theory from the 1960s.

[1] What is the enlightenment I'm supposed to attain after studying finite automata?

[2] Collatz Conjecture & Grammars / Automata

Yes, it is a lovely observation. At first it might be a little surprising, but it is widely known, in disguise.

If we write the instantaneous description of a Turing machine as $vqw$, where $q$ is the state, $v,w$ are the segments left and right of the head, then the next ID of the TM is obtained by just a local transformation of the string $vqw$ (namely $q$, the letter next to $q$ that the TM is reading, and one or two neighbouring letters). This observation is used when showing that every TM accepted language can be generated by a type-0 grammar. Such a grammar can only transform a local part of the string (and thus this can be simulated by a FST/GSM). Applying consecutive derivation steps then is iterating the transducer.


Bootstrapping results that really bootstrap There is a type of results in TCS usually called bootstrapping results. In general, it is of the form

  If proposition $A$ holds, then proposition $A'$ holds.

where $A$ and $A'$ are propositions that look similar, and $A$ is seemingly "weaker" then $A'$, which is the reason we name this type of results.
Let me give a few concrete examples:

  Theorem. [Chen and Tell, STOC'19] Fix any problem $\Pi \in \{\mathsf{BFE,W_{S_5},W5STCONN}\}$
  . Assume that for every $c>1$ there exist infinitely many $d\in \mathbb{N}$ such that $\mathcal{TC}^0$ circuits of depth $d$ need more than $n^{1+c^{-d}}$ wires to solve the problem $\Pi$. Then for any $d_0,k \in \mathbb{N}$, $\Pi$ cannot be solved by $\mathcal{TC}^0$ circuits of depth $d_0$ and $n^k$ wires, and therefore $\mathcal{TC}^0 \subsetneq \mathcal{NC}^1$.

  Theorem. [Gupta et al., FOCS'13] Suppose that computing the permanent requires depth-$3$ arithmetic circuits of size more than $n^{\Omega(\sqrt{n})}$, over fields of characteristic $0$. Then computing the permanent requires arithmetic circuits of superpolynomial size, and therefore Valiant's Conjecture holds.

Well, a more famous but not-so-appropriate example comes from fine-grained complexity:

  Theorem. [Backurs and Indyk, STOC'15] If we can compute EDIT DISTANCE in $O(n^{2-\epsilon})$ time (on the RAM model), then we will get a SAT solver faster than any one that currently exists.

Update. (July 10, 2019) The edit distance example may be a little confusing. Refer to Ryan’s answer for a “standard” example.

As you may have imagined, (to my  best knowledge) all results of this type are proved by taking the contrapositive (I have taken the contrapositive in the edit distance one). So in some sense these are all algorithmic results.

Usually there are two ways to understand a bootstrapping result. 1. We only need to prove $A$ and then apply the result, if we want to prove $A'$; 2. Proving $A$ may be difficult because a priori we think proving $A'$ difficult.

The problem is that, one (or more exactly, I) may be hardly optimistic and take the first understanding, if there does not exist any positive use of bootstrap results after all!
So my question is

  Do we know any bootstrapping result in which $A$ is proven?

A classic result provable by bootstrapping (and applicable to proving real lower bounds) is that in any computational model where we have $TIME(n) \neq TIME(n^c)$ for some constant $c > 1$, we in fact have  $TIME(n) \neq TIME(n^{1+\epsilon})$, for every $\epsilon > 0$.

The idea is that if $TIME(n) = TIME(n^{1+\epsilon})$, we can apply a  padding argument repeatedly to obtain $TIME(n) = TIME(n^c)$ for every constant $c$. You can even use such an argument to slightly improve known time hierarchy theorems in various cases.


Nondeterministic speed-up of deterministic computation Can nondeterminism speed-up deterministic computation? If yes, how much?

By speeding-up deterministic computation by nondeterminism I mean results of the form:

  $\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n)$

E.g. something like

  $\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$

What is the best known speed-up result of deterministic computation by nondeterminism?
What about $\mathsf{\Sigma^P_kTime}(n)$ or even $\mathsf{ATime}(n)$ in place of $\mathsf{NTime}(n)$?

Assume that complexity classes are defined using multiple-tape Turing machines
to avoid the well-know peculiarities of
the sub-quadratic time single-tape Turing machines.

You should not expect an exciting speed-up. We have

$$\mathrm{DTIME}(f(n))\subseteq\mathrm{NTIME}(f(n))\subseteq\mathrm{ATIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)),$$

and the best known simulation of deterministic time by space is still the Hopcroft–Paul–Valiant theorem

$$\mathrm{DTIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)/\log f(n)).$$

Thus, nondeterminism or alternation is not known to give speed-up by more than a logarithmic factor. (I suspect no super-linear speed-up is known either, though I’m not sure if the HPV theorem can’t be made to work with ATIME in place of DSPACE.)


Deciding DDH based in partial information Decisional Diffie–Hellman assumption, or DDH in short, is a famous problem in cryptography.
The DDH assumption holds on a cyclic group $(G,*)$ of (prime) order $q$, if for a generator $g \in G$, and for randomly chosen $a,b,c \in $\mathbb{Z}_q$$, the following pairs are indistinguishable (for probabilistic poly-time algorithms):

Type 1: $(g,g^a,g^b,g^{ab})$
Type 2: $(g,g^a,g^b,g^{c})$

Now, assume that $G$ is a group on which DDH is hard, and consider the following informal question:

  Do we know of a probabilistic poly-time (PPT) algorithm, which gets a Diffie-Hellman pair, along with some partial information about $a$ (say, $a$ is odd), and can correctly output whether the input pair is "Type 1" or "Type 2" (with non-negligible probability)?

By partial information, I mean a string $z$, such that given $z$ and a Diffie-Hellman pair, no PPT algorithm can compute $a$, with non-negligible probability.

It's possible to formalize the above question. However, since the amount of notation required is tedious, I try to use an analogy.

A famous, non-standard cryptographic assumption is called Knowledge-of-Exponent (KEA).

  For any adversary A that takes input $q$, $g$, $g^a$ and returns $(C,C^a)$, there exists
  an "extractor" B, which given the same inputs as $A$ returns $c$ such that $g^c = C$.

Intuitively, it states that, since the adversary cannot solve discrete log to obtain $a$, the only way to output a pair $(C,C^a)$ is to "know" the exponent $c$ where $g^c = C$.

Now, I'm asking a similar question, based on DDH (rather than discrete log): to distinguish "Type 1" and "Type 2" Diffie-Hellman pairs, should we "know" either $a$ or $b$?

A bit more formally (but still not fully formal):

  Let $(G,*)$ be a group of prime order $q$, and let $f(\cdot)$ be an arbitrary function whose output length is polynomial in the length of its input.
  Pick $a$, $b$, and $c$ randomly from $\mathbb{Z}_q$, and let $z=f(a)$.
  Toss a coin, and let $X = ab$ if the result is heads. Otherwise let $X=c$.

  For any PPT adversary A that takes input $(q,g,g^a,g^b,g^X,z)$, and correctly decides between Type 1 and Type 2 with non-negligible probability, there exists
  a PPT "extractor" B, which takes the same input as A, outputs either $a$ or $b$ (with non-negligible probability).

Given the latest formulation of your question, this appears to be impossible. Consider the case where you have (families of) cyclic groups $\mathbb{G}$ and $\mathbb{H}$, where $\mathbb{G} \ne \mathbb{H}$ and we have a bilinear map $e: \mathbb{G} \times \mathbb{H} \to \mathbb{T}$. Under the XDH assumption we can suppose that DDH is hard in $\mathbb{G}$ and discrete log is hard in $\mathbb{H}$.

Let $g$ be a generator of $\mathbb{G}$ and $h$ be a generator of $\mathbb{H}$.
Then define $f : \mathbb{Z}_{|\mathbb{G}|} \to \mathbb{H}$ as $f(a) = h^a$.

Now given $(g, g^a, g^b, g^X, z=f(a)=h^a)$, we can easily determine whether $X = ab$ by checking $e(g^b, z) \overset{?}= e(g^X,h)$. (You can also similarly verify the correctness of $z$ if you like.) Yet, it would seem unlikely that an extractor could extract $a$ or $b$ from such a tuple. Extracting $b$ is obviously equivalent to discrete log; if there is a distortion map from $\mathbb{H}$ to $\mathbb{G}$ (there cannot be one in the other direction) then extracting $a$ is equivalent to discrete log (in $\mathbb{H}$).


Justification of log f in DTIME hierarchy theorem If we look at DTIME hierarchy theorem, we've got a log due to the overhead in simulation of a deterministic Turing Machine by a universal machine :

$DTIME(\frac{f}{\log f}) \subsetneq DTIME(f)$

We haven't this kind of overhead for NTIME of DSPACE. A basic justification comes from the details of the proof by considering the difference between simulators.

My question is the following: without considering the detail of the proof of DTIME hierarchy theorem, is there a justification of this log or it could be just a consequence of the proof and it would be reasonable to imagine that if $f = o(g)$ then

$DTIME(f) \subsetneq DTIME(g)$

In my opinion, considering that the simulation explanation is a good justification should be itself justified by proving that if we had a better result, then we could create a better simulation.

For n-tape TMs a tight time hierarchy result similar to the space hierarchy theorem is proven by Furer in 1982. The $\lg$ factor is not needed.

The $\lg$ factor for the time hierarchy theorem stated in your post is only for single-tape TMs. Unless you are very committed to the single-tape model for some reason there is not a difference between space and time regarding the hierarchy theorems.

There are some reasons and arguments for using single-tape TMs for defining time complexity classes, but the usage of single-tape TMs for defining complexity classes is not universal, e.g. see Lance Fortnow and Rahul Santhanam's [2007] where they use multiple-tape TMs.

The original reference for the time hierarchy theorem is Hennie and Stearns [1966]. They prove the theorem for two-tape machines. Odifreddi's Classical Recursion Theory cites them and Hartmanis [1968] and describes a proof that looks similar to the one in Sipser's book.

However the proof for single tape TMs in Hartmanis's paper does not use simulation simply. It distinguished between two cases: 1. running-time being $\Omega(n^2)$ and 2. running-time being $o(n^2)$.

For the first case it uses a simulation, and it seems that one can get rid of the $\lg$ factor if the simulations can be done more efficiently.
For the second case, the paper directly gives a language for the separation and doesn't use simulation at all. This uses particular properties of single-tape TMs with sub-quadratic running-time.

One should note that single-tape TMs with time $o(n^2)$ are not as robust and there are quadratic lowerbounds (e.g. for Palindroms) on single-tape TMs whereas a two-tape TM can solve such problems in linear time.

As I said above, unless you are committed to single-tape TM model for some reason, even when time is sub-quadratic, there is not a gap to fill, the time hierarchy theorem is as tight as possible.

PS: if we are using multiple-tape TMs, i.e. a Turing machine in the class can have fixed but arbitrary number of tapes Fürer's result does not apply.

Martin Fürer, "The Tight Deterministic Time Hierarchy", 1982
Piergiorgio Odifreddi, "Classical Recursion Theory", vol. II, 1999
(page 84)
Juris Hartmanis, "Computational Complexity of One-Tape Turing Machine Computations", 1968
F.C. Hennie and R.E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", 1966
Lance Fortnow and Rahul Santhanam's paper "Time Hierarchies: A Survey", 2007


Protocol partition number and deterministic communication complexity Besides (deterministic) communication complexity $cc(R)$ of a relation $R$, another basic measure for the amount of communication needed is the protocol partition number $pp(R)$. The relation between these two measures is known up to a constant factor. The monograph by Kushilevitz and Nisan (1997) gives

$$cc(R)/3 \le  \log_2(pp(R)) \le cc(R).$$

Regarding the second inequality, it is easy to give (an infinite family of) relations $R$ with $\log_2(pp(R)) = cc(R)$.

Regarding the first inequality, Doerr (1999) showed that we can replace the factor $c=3$ in the first bound by $c=2.223$. By how much can the first bound be improved, if at all?

Additional motivation from descriptional complexity: Improving the constant $2.223$ will result in an improved lower bound on the minimum size of regular expressions equivalent to a given DFA describing some finite language, see Gruber and Johannsen (2008).

Although not directly related to this question, Kushilevitz, Linial and Ostrovsky (1999) gave relations $R$ with $cc(R)/(2-o(1)) \ge  \log_2(rp(R))$, where $rp(R)$ is the rectangle partition number.

EDIT: Notice that the above question is equivalent to the following question in Boolean circuit complexity: What is the optimum constant $c$ such that every boolean DeMorgan formula of leafsize L can be transformed into an equivalent formula of depth at most $c \log_2L$?

References:

Kushilevitz, Eyal; Nisan, Noam: Communication Complexity. Cambridge University Press, 1997.
Kushilevitz, Eyal; Linial, Nathan; Ostrovsky, Rafail: The Linear-Array Conjecture in Communication Complexity is False, Combinatorica 19(2):241-254, 1999.
Doerr, Benjamin: Communication Complexity and the Protocol Partition Number, Technical Report 99-28, Berichtsreihe des Mathematischen Seminars der Universität Kiel, 1999.
Gruber, Hermann; Johannsen, Jan: Optimal Lower Bounds on Regular Expression Size using Communication Complexity. In: Foundations of Software Science and Computation Structures 2008 (FoSSaCS 2008), LNCS 4962, 273-286. Springer.

Ok, so let me try to prove that two is enough, that is $cc(R)\le 2\log_2(pp(R))$. Sorry but sometimes I write leaves instead of number of leaves/pp(R), whenever the number is smaller than 1, I obviously mean this. Also, I usually write < instead of $\le$ to enhance non-tex readability.

Indirect suppose that there is an R for which this is not true and let us take the R with the smallest possible pp(R) that violates the inequality. We basically have to show that using two bits, we can halve the number of leaves in all four outcomes of the protocol tree, then we are done using induction.

Denote the possible set of inputs of Alice by X and of Bob by Y.
Take the center of the protocol tree that achieves pp(R) leaves, i.e. the node deleting which the tree falls into three parts, each having at most 1/2 of the pp(R) leaves, and denote the corresponding inputs by X0 and Y0.
Without loss of generality we can suppose that Alice speaks at the center and she tells whether her input belongs to XL or XR, whose disjoint union is X0.
Denote the ratio of the leaves to pp(R) in XL $\times$ Y0 by L, in XR $\times$ Y0 by R and in the rest by D.
Now we divide the rest into three more parts, similarly to Doerr, denoting the leaves whose rectangle intersect Y0 $\times$ X by A, whose rectangle intersect X0 $\times$ Y by B and the rest by C.
Notice that A+B+C=D.

Now we know that L+R>1/2, L,R<1/2 and without loss of generality we can suppose that L is at most R. We also know D=A+B+C<1/2. It follows that 2L+A+B<1, from which we know that either L+A<1/2 or L+B<1/2, these will be our two cases.

Case L+A<1/2: First Bob tells whether his input belongs to Y0 or not. If not, we have at most D<1/2 leaves left. If it does, then Alice tells  whether her input belongs to XR or not. If not, we have at most L+A<1/2 leaves left. If it does, then we have R<1/2 leaves left.

Case L+B<1/2: First Alice tells whether her input belongs to XR or not. If it does, then Bob tells whether his belongs to Y0 or not, depending on this we have R or B leaves remaining. If the input of Alice is not in XR, then Alice tells whether her input is in XL or not. If it is, then we have L+B<1/2 leaves remaining. If not, we have at most D<1/2 leaves remaining.

In all cases we are done. Let me know what you think.


Covering by disjoint sets We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$.

I'm interested in the approximability of two problems, or in general, what is known about them.

Given a number $k'\in[m]$, is there a set $\mathcal{S'} \subseteq \mathcal{S}$,  $|\mathcal{S'}|=k'$ such that all of the sets in $\mathcal{S'}$ are disjoint.
Given a number $k''\in[n]$, is there a set $\mathcal{S''} \subseteq \mathcal{S}$ such that $|\cup_{s\in\mathcal{S''}}s|\geq k''$ (i.e. it covers at least $k$ elements) and the sets in $\mathcal{S''}$ are disjoint.

The problems are NP-complete:
The first has a straight forward reduction from 3-dimensional matching, and the second answers exact cover directly.

The first problem seems $APX-hard$ if we use the hardness results from k-dimensional matching.
Both problems can be viewed as a special case of Independent Set over the graph whose vertices are $\mathcal{S}$ and there's an edge $(s_i,s_j)$ iff $s_i\cap s_j$ isn't empty ( (2) has vertices weights $w(s_i)=|s_i|$), but I don't see any easy reduction from $IS$ to either that doesn't require exponential size blowup.

What can we say about the approximability of the two problems? maximal k-dimensional matching is known to be approximable within a factor of $\frac{k}{2}$, does it have an analogue for the first problem?

Both of these problems seems natural, so I'm tagging this question as a reference request, assuming they have been looked at under different name, rings a bell to anyone?

Problem 1 is known as SET PACKING. Like other packing problems, it's annoyingly hard. The best known bound is a $O(\sqrt{|S|})$ approximation and it is indeed APX-hard.


sum versus maximum in computer science I would be interested in some References (books or articles) concerning an answer to the following question :

what is more difficult to calculate from the viewpoint of a computer : the "sum" or the "maximum" of a finite set of numbers ?

My guess is that "sum" and "maximum" are of the same level of difficulty, but I would like very much to know References concerning this question.

Thank you in advance.

George

The sum of finitely many binary numbers can be computed in $TC^0$ and is in fact complete for $TC^0$ under $AC^0$ reductions.

The maximum of finitely many binary numbers can be computed in $AC^0$.

So from the circuit-complexity perspective, sum is more difficult.


Aren't Monads F-Algebra's? And then if that could be said are Comonad's F-Coalgebra's? So considering a Monad to be a Triple (T:C -> C, η, µ) with eta and mu as the Natural transformations with appropriate signatures, isn't this in essence an F-Algebra?

My thinking is that being both (Monad and F-Alg) centered around some particular action(s) on|of a given Endofunctor, what stops Monads NOT just being special cases of F-Algebra's? (Also for some context I've been reading a bit of Homotopy theory & Bart Jacobs so I like could just be you know not seeing clearly and making connections where there are none...) I'm seeing a Monad as an F-Algebra of some Monoidal category or Quasicategory with the action of the Endofunctor or alternatively the operations definable on the Algebra of the Endofunctor as the particular semantics of that F-Algebra (e.g. what makes a Monad the State Monad or the Identity Monad or what have you instead...)

Examples, Proofs etc. in Scala or Haskell are good, but I might need clarification if it's in Haskell.

The paper with a rather suggestive title "Algebras, Coalgebras, Monads and Comonads" (2001)
by Neil Ghani, Christoph Lüth, Federico De Marchi, John Power addresses this topic.


Is multiprocessing possible on a Turing Machine? I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on Turing Machine?

This is a subtle question.

TMs are very much a sequential model of computation. So in some sense, TMs cannot (directly) model multiprocessing. However, TMs can do step-by-step simulations of the reductions a multiprocessor is carrying out. So TMs can do a sequential simulation of a parallel computation. Whether this a genuine model of parallel computation is debatable.

See also the discussion Applicability of Church-Turing thesis to interactive models of computation.


Probability of random variable $X$ less than $max(Y_i)$ For $\lambda > \mu$, consider independent random variables (i)  $X \sim Pois(\mu)$ and (ii) $Y_i \sim Pois(\lambda),\;i\in{1,2}$.

Question : Can we upper-bound the following?
$$\mathbb{P}\big(X\geq\max(Y_1, Y_2)\big)$$

We have $\Pr[\max(Y_1,Y_2) \leq k] = \Pr[Pois(\lambda) \leq k]^2 = e^{-2\lambda}(\sum_{j=0}^k\frac{\lambda^j}{j!})^2$.

Therefore, $\Pr[X \geq \max(Y_1,Y_2)] = \sum_{k \in \mathbb N} \Pr[X = k] \cdot \Pr[\max(Y_1,Y_2) \leq k] = e^{-(2\lambda+\mu)} \bigg (\sum_{k = 0}^\infty\frac{\mu^k}{k!} \cdot (\sum_{j=0}^k \frac{\lambda^j}{j!})^2 \bigg)$.

From this, if you have some concrete values of $\lambda$ and $\mu$, you can try to see which terms are important, and which are negligible.

I guess the important terms are $k < O(\lambda)$.


Sorting algorithm, such that each element is compared $O(\log n)$ times, and doesn't depend on a sorting network Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times?

As far as I know, the only way to sort with $O(\log n)$ comparison on each element is to construct an AKS sorting network for $n$ inputs, and run the input on the sorting network.

AKS is not easy to implement and has an impractical constant factor, so there are motivations to search for other algorithms.

An algorithm with $O(\log^2 n)$ comparisons per item which does not seem to imply a sorting network is presented here. (iirc, this was first presented by Rob Johnson at Stony Brook's algorithm seminar).

Upon discussing this with Michael T. Goodrich, it seems that the parallel sorting algorithm by Cole for EREW PRAM does the job. See

Richard Cole: "Parallel Merge Sort". SIAM J. Comput. 17(4): 770-785 (1988).

In that algorithm there are $O(\log n)$ rounds and in each round each element participates in $O(1)$ comparisons. (One has to understand the algorithm to see that we do not abuse of making copies of each element.)

An extension of that algorithm for parallel pointer machine is given in

M.T. Goodrich, S.R. Kosaraju: "Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation". J. ACM 43(2): 331-361 (1996).


Packing $n$ objects into $m$ bins whose size is variable Assume we have $n$ fixed size objects with sizes $O_1$ to $O_n$. Also, assume we have $m$ bins with size $a \times B_1$ to $a \times B_m$ in which $a$ is a real number and $a\ge1$. We want to put these objects into bins. If in the process of putting an object to bins, there is a step where there is not enough room in any of the bins to put the object, we can increase $a$ so that we have larger buckets. Starting at $a=1$, the problem is to find the smallest $a$ where all objects can go to bins. Obviously, if $a$ is very large, we can put all objects in one bin.

Is this similar to a known problem in computer science?
Can this be modeled using some variation of bin-packing?
Can you suggest a heuristic?

Thank you.

EDIT:

I implemented the following heuristic and also the optimal version using the integer programming. The average ratio of $a_{heuristic}/a_{optimal}$ is 1.02 (worst case was 1.23) over 200 runs of the simulation for 20 objects, varying number of bins and randomly generated ball and bin sizes. The heuristic is as follows:

$(1)$ Sort objects from largest to smallest using a priority queue. Set $a = 1$. Assume $U_i$ is the total size of all objects in $B_i$.

$(2)$ Remove the biggest object and call it $O$.

$(3)$ For all bins, find the $1 \le i \le m$ for which $(U_i+O)/B_i$ is the least. Add $O$ to $B_i$ and $U_i = U_i + O$.

$(4)$ $a = max(a, U_i/B_i)$.

$(5)$ Goto $(2)$ if there are more balls.

One simple "bad" input that needs to be considered for worst-case analysis of this problem is as follows.

Let $c=(\sqrt{17}-1)/2 \approx 1.56$.
There are three objects of size $c$, $1$, and $1$.
There are two bins of size $2$ and $c$.
Initially $a=1$.
Some heuristics will place the largest object into the big bin, necessitating $a$ increasing from 1 to at least $(c+1)/2 = 2/c > 1.2807$.
An optimal packing leaves $a=1$, placing the two small objects into the big bin and the big object into the smaller bin, with no waste.
Hence such heuristics will have a worst-case actual-to-optimal ratio of more than 1.2807.

Notwithstanding this worst-case analysis, a heuristic like the one described in the edited question is likely to work well for practical examples, even if its worst-case performance is at least 28% worse than optimal.
Similar heuristics are often used in practice, sometimes with adjustments like "instead of the general criterion, prefer a bin that is only a tiny bit larger than the object to be placed, if one such exists".
Most implemented heuristics I'm familiar with are a big mess of such case analysis, but work extremely well in practice.
However, it is often quite hard to come up with badly behaved inputs for such complex algorithms, and it is even harder to prove that they are the worst possible.


2D Cutting Stock Problem for Glass - Details mentioned I am trying to work on Cutting Stock Problem. I have seen some algorithm. Can anybody suggest the best 2D cutting stock problem algorithm?

I am looking for kind of best acceptable solution for 2D Glass Cutting problem. The constraints/features for this are as follows: Input to this problem is a set of Large Rectengular Glass Sheets (say approximately 100) with varied Length and Breaths called stocks. Requirement is cut Rectengular Glass pieces out of them (say approximately 200) with varied length and breadth. All (stocks & output sheets) are rectangular. Also,cuts has to be guillotine cuts that mean each cut has to be end to end.

Example of input:Stock (200 X 100 X 10, 200 X 90 X 5, etc), Required Glasses (50 X 50 X 8, 50 X 40 X 8, etc) in format of (Length X Width X No of sheets)

Here is small history of my approach for the problem:
I wrote algorithm which would in following 4 passes:

Pass1: Take One Stock. Create a tree with all cuts possible for all the public required glasses. Also, I could rotate the glass. This step created a huge tree and is exponential.

Pass2: Iterate Pass2 for all the stocks.

Pass3: Iterate each of the tree and covert the problem into ILP problem, as is done for 1D-CSP.

Pass4: Solve the ILP to get the best solution.

The problem with this approach is that at the first step itself the tree becomes so huge for big number of required glasses that it could not be completed in desired amount of time.

Hope this helps, please let me know if extra information is required.

Regards Sandeep Jindal

It sounds like your glass cutting problem is exactly like the 2D guillotine stock cutting problem -- am I correct that there is no difference?

I think Macleod et al's O(n^3) approximation algorithm from the 1990s is still the best known result with proven optimality bounds for very large instances of this problem, but for only 100-200 pieces the exact algorithm by Christofides and Hadjiconstantinou should be able to find the optimal solution in reasonable time.  There are also good heuristics for this problem via dynamic programming.

A survey on software solvers for the cutting stock problem was written by Macedo et al here in case you're looking for practical solutions.


Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy The $\mathsf{W}$-hierarchy is a hierarchy of complexity classes $\mathsf{W}[t]$ in parameterized complexity, see the Complexity Zoo for definitions. An alternative definition defines $\mathsf{W}[t]$ using weighted Fagin definability for $\Pi_t$-formulas of first-order logic, see the textbook by Flum and Grohe.

For the lowest classes $\mathsf{W}[1]$ and $\mathsf{W}[2]$, many natural complete problems are known, e.g. Clique and Independent Set are complete for $\mathsf{W}[1]$ , and Dominating Set and Hitting Set are complete for $\mathsf{W}[2]$, where each of these problems is defined as the corresponding well-known $\mathsf{NP}$-complete problem with the size of the required solution set as the parameter.

Are there any known natural complete problems for classes higher up in the $\mathsf{W}$-hierarchy, in particular for $\mathsf{W}[3]$ and $\mathsf{W}[4]$?

I believe the title of this paper is self-explanatory and answers your question:
On product covering in 3-tier supply chain models: Natural complete problems for W[3] and W[4]


Can the optimal minimum cost two-commodities flow be fractional on this special case? Suppose that we have a two commodities flow network $N=<G=(V,E), s_1,s_2,t_1,t_2\in V>$.

The problem is to find a minimum cost two-commodity flow in which there a flow $f_1$ from $s_1$ to $t_1$ of 2 units and a flow $f_2$ from $s_2$ to $t_2$.

All edges has capacities 1 and cost 1.

(In two-commodity flow the two flows share the edges capacities, that is $\forall e\in E, f_1(e)+f_2(e)\leq 1$, and the cost is defined as $\Sigma_{_{e\in E}}f_1(e) + f_2(e)$ ).

In the general case, multi-commodity flow can have fractional optimum flow even if the capacities/costs are integers, but I was wondering if there's an example for it which doesn't use negative weights and only 2 commodities, so my question is: Is there be a network with my specifications that doesn't have an optimal integer solution?

The following example (taken from Idan Maor's presentation) shows that that 3-MCF can have only a fractional optimal flow:

I have two motivations here: if such network exists, it can be used to show a very simple example for which using LP for solving this problem can't work, and if there isn't such network, this might allow us to develop an efficient method for finding disjoint paths in a graph (if we can find the optimal solution in poly time).

Edit: as Suresh have mentioned, 2-commodity flow is NP-hard in the general case, so I'm only looking at the unit capacities/costs case, which I couldn't find a mentioning for it as being NP-hard (Intuitively, I believe an integer solution does exist for every such network)

Even, Itai, and Shamir proved that the undirected integral two-commodity flow is NP-hard even if all capacities are one. As far as I understand, the following is an example of what you ask for. It has a fractional solution twice as large as the integer one (All edge capacities are one. The costs don't really matter, as they only come in play to break ties between several optimum flows.):


Can we perform an n-d range search over an arbitrary box without resorting to simplex methods? Suppose I have some set of points in d-dimensional space, each with some mass. Our problem size will be the number of points in this set. After some roughly (within polylog factors) linear initialisation using roughly linear storage, I would like to know the total mass of all the points that fall within various queried subspaces in polylogarithmic time.

If our queries are all axis-parallel boxes, ie sets of points defined by a cartesian product of intervals on each axis, we can apply some standard, easily-googleable range searching methods and achieve this without too much difficulty.

If our queries are all simplices, there are currently no known methods which satisfy both these criteria, either we use polynomial space and initialisation to achieve a polylog query time, or we use roughly linear space and have sublinear, but not logarithmic, query times.

What if our queries are all boxes, but each is rotated in some way? We can define such a box in a few ways, but for the sake of concreteness suppose I will give you a sequence of sets of hyperplanes, each with exactly one parallel partner, intersecting all others orthogonally, defining some boxey subspace between them. Is there a way of solving this slightly simpler problem with roughly linear initialisation and storage but polylogarithmic queries? Alternatively, if I were to give you a method of doing this, would you be able to use it to solve the simplex case of this problem in a similarly easy way?

No.

Rotated-box queries and simplex queries are both generalizations of slab queries, where a slab is the volume between two parallel hyperplanes.  Most lower bound proofs for simplex range searching actually assume that all query simplices are slabs of constant thickness.  In particular, Chazelle [2] proved the following theorem.

  Let $P$ be a random set of $n$ points, generated independently and uniformly in the unit hypercube $[0,1]^d$.  With probability at least $1/2$, any data structure of size $s$ that answers queries in $P$ for slabs of width $1/24$ in time $t$ in the semigroup arithmetic model must satisfy the inequality $st^d = \Omega((n/\log n)^d)$, or $st^2 = \Omega(n^2)$ when $d=2$.

The constants $1/2$ and $1/24$ are not particularly important here; different choices merely change the constant hidden in the $\Omega(\,)$ notation.  Thus, if you are allowed only linear space, your query time must be $\Omega(n^{1-1/d} / \operatorname{polylog} n)$; on the other hand, if you require polylogarithmic query time, you must use $\Omega(n^d / \operatorname{polylog} n)$ space.

More recently, Arya, Mount, and Xia [2] proved nearly identical lower bounds (under some reasonable assumptions about the underlying semigroup) for the even simpler case of halfspace queries, where a halfspace consists of all points on one side of a single halfplane.

tl;dr: Don't rotate your boxes.

Sunil Arya, David M. Mount, and Jian Xia.  Tight lower bounds for halfspace range searching.  Discrete & Computational Geometry 47:711–730, 2012.
Bernard Chazelle.  Lower bounds on the complexity of polytope range searching.  Journal of the AMS 2(40):637–666, 1989.


Has the semantics of TeX (as a programming language) ever been formalized? It seems to me that the macro language employed by $\TeX$ can maybe be seen as some kind of term rewriting system or some kind of programming language with call-by-name scoping.

Even modern implementations of the $\TeX$ engine (e.g. $\mathit{Xe}\TeX$) interpret code in a quite direct way and I'm not aware of any attempt at optimizing the execution (like modern optimizing interpreters can do). However, devising correct optimization passes for a language like $\TeX$ is going to be very difficult because of the "action at a distance" that macro redefinitions can have, and the ability of redefining macros by calling them by name.

So implementing an hypothetical optimizing interpreter for $\TeX$ sounds a very difficult problem in practice but also a very useful one, since $\TeX$ is used all over math and science and slow compilation times are a known drawback of the system. Note that the majority of time is spent interpreting code, not computing the actual typesetting, especially when computationally heavy packages are used (such as tikz).

Maybe a formal semantics for the language could be a start to address the problem. So has the semantics of the $\TeX$ programming language ever been formalized?

No, to my knowledge there has been no work on formalizing TeX of the kind you are interested in.

(What follows is a subjective and personal commentary). I think it is an intriguing and well-posed idea, and your motivation of using it to perform optimizations sounds reasonable -- another related question is whether you could define a bytecode format for it to speed up interpretation. On the other hand, the idea has two downsides.

First, it is not clear to me that there is a large potential for optimizations (for example, what kind of program-preserving transformations could one perform to speed up computation?), as it may be that the language semantics is intimately related to parsing the character flow, and thus not very accommodating to the design of optimization-friendly intermediate representations.

Second, the need for improvements in TeX interpretation speed is not well-established: the speed of batch speed building has remained reasonable thanks to hardware improvements. Cases where speedups could be welcome are complex graphics package (beamer presentations can take quite some time to build), packages embedding rich computations (but then another language may be more appropriate), and use cases requiring fast rebuild for instant user feedback (but then incrementality, rather than optimization, may be the point; a formal semantics would certainly help reason about incremental implementations as well).

That is to say: this sounds like a fun, instructive topic, but it is not clear to me that the practical justifications for doing the work are strong. If someone was interested in doing it out of curiosity, that sounds like an excellent adventure, but otherwise there may be other ways to employ the same skillset whose impact would be more sought-after by end-users.


Is Locality preserving projections (LPP) method the same as Laplacian eigenmap method? Are "Locality Preserving projections(LPP)" and "Laplacian eigenmap" one method for dimension reduction, only under different names? I have not seen any article refer to them as the same method, in fact in LPP paper, they cite Laplacian eigenmap as a non-linear dimension reduction and say that LPP is a linear dim reduction method. But both algorithms have exactly same description. Are they a same method, or am I missing something?

There is a subtle difference, which can be difficult to recognize. They both minimize the same objective:

$\sum_{i,j} w_{ij} || y_i - y_j ||^2_2$

However, they parametrize the predictor on y differently. Locality preserving projections is linear because the parameterization is linear: $y_i = x_iW$. Laplacian eigenmaps is non-linear because the parametrization uses a kernel: $y_i = k_iA$. Kernel LPP is equivalent to Laplacian eigenmaps.

For a good description and a summary showing the connections between all these different dimensionality reduction algorithms, see the paper:

TRACE OPTIMIZATION AND EIGENPROBLEMS IN DIMENSION REDUCTION METHODS, KOKIOPOULOU et al.

or the summary table in Section 2.7 in the thesis:

Regularized Factor Models, Martha White


What are the widely used notations for quickly referring to a single component of a multi-component object? I have the need to define a multi-component object type for which I provide numerous definitions throughout the text.
However, in most of these definitions, I only need to refer to one or two of the components constituting the object type.
Therefore, I am looking for a widely used notation that allows to quickly refer to only a single component of the object type without having to introduce the entire object.

I have identified four possible notations for defining multi-component objects. which I do introduce below using the object type transition system as an example.
The first notation is the classical one where the object type is defined as a tuple. The drawback of this definition is that anytime that I want to express properties on the object type I need to re-introduce the entire tuple.
The other three notations (2-4) avoid this issue, but I am not sure whether they are widely used and accepted.

Here are a few options

  A transition system $TS$ is a tuple $(S,\Sigma,\delta, s_0)$ where

  $S$ is a set of states
  $\Sigma$ is a set of Actions
  $\delta \subseteq S \times \Sigma \times S$ is the state transition relation
  $s_0 \in S$ is the initial state

Usage example

  A transition systems $TS = (S,\Sigma,\delta, q_0)$ is finite if $S$ is finite

  A transition system $TS$ is consists of

  a set of states $S(TS)$
  a set of actions $\Sigma(TS)$
  a transittion relation $\delta(TS) \subseteq S(TS) \times \Sigma(TS) \times S(TS)$
  the initial state $s_0(TS) \in S(TS)$

Usage example

  A transition systems $TS$ is finite if $S(TS)$ is finite

  A transition system $TS$ is consists of

  a set of state $S^{TS}$
  a set of action $\Sigma^{TS}$
  the transition relation $\delta^{TS} \subseteq S^{TS} \times \Sigma^{TS} \times S^{TS}$
  the initial state $s_0^{TS} \in S^{TS}$

Usage example

  A transition systems $TS$ is finite if $S^{TS}$ is finite

  A transition system $TS$ is consists of

  a set of states $TS.S$
  a set of actions $TS.\Sigma$
  a transittion relation $TS.\delta \subseteq TS.S \times TS.\Sigma \times TS.S$
  the initial state $TS.s_0 \in TS.S$

Usage example

  A transition systems $TS$ is finite if $TS.S$ is finite

Papers I've seen that have this issue often present 1 as the initial definition and then also define 2 (or 3 with subscripts) as an additional definition that is used when necessary for clarity.

A common abuse of notation—common enough that I've seen it in multiple places, although it makes my skin crawl every time I see it—is to write something like $S = S(TS)$.

3 with superscripts is unacceptable because superscripts have other widely-understood standard meanings; however, it would be fine if the superscripts were changed to subscripts. 4 is never used outside of programming contexts.

I would also recommend avoiding the two-letter variable name $TS$ in mathematical notation, especially since you are also using $S$ as a separate symbol. Use single letters, resorting to Greek if necessary, for anything in the standard italic "variable" font. Special functions and classes of languages usually get straight font or boldface to distinguish them from surrounding text for this reason.


Damas-Milner-like subset of the calculus of constructions with global type inference Damas-Milner is a subset of System Fω that gives up expressivity (type-level computation) for usability (type inference). The experience with Haskell and ML attests to the practical value of this tradeoff.

Does a similar Damas-Milner-like subset of the calculus of constructions exist, for which global type inference is possible? I expect the answer to be “yes” based on the following clues:

1ML's abstract syntax already unifies terms and types, in a way reminiscent of System Fω's definition as a pure type system, and then makes type inference work for a subset of the language.
AFAICT, Damas-Milner type inference only requires that the type language be first-order, pure, terminating and confluent. First-order unification doesn't require that all unification variables range over a single sort (namely, that of types). A first-order, pure, terminating language can be carved out of a higher-order, effectful, potentially nonterminating language, by means of syntactic restrictions on terms in the latter.

But is there a definitive answer?

As far as I can tell, there is no prime candidate for an analogue of Damas-Milner for CoC. Certainly there is no definitive answer.

Arguably, Damas-Milner isn't even a perfect inference system for $\mathrm{F}_\omega$, as in general it can't infer types with higher kinds in them (though it is an open question as to whether higher kinds are really necessary, see this problem).

At any rate, here's a rather simple argument against a definitive system for the CoC: unification modulo $\beta$ conversion is undecidable in general, even for terms with simple types. But for a given unification problem $t\approx u$ it is rather easy to set up a term which can be typed if and only if $t$ unifies with $u$:

$$ A : \Pi \vec{x}.C\ t\rightarrow \mathrm{nat},\ B:\Pi\vec{x}.C\ u\vdash A\ B$$

where the $\vec{x}$ are the free (unification) variables in $t$ and $u$, as well as the "implicit arguments" which are the analogue of the polymorphic type variables in Damas-Milner.

That being said, there are restrictions of the unification problem which are decidable, most notably Miller patterns which have good properties (uniqueness of solutions), so it's common to restrict implicit argument resolution to Miller patterns and reject the term otherwise.

In practice every dependently typed language does have to solve this problem, if only because giving every single type annotation is unworkably tedious. However, that inference is usually designed to fail in which case the user is asked to supply additional annotations, something which is absent from usual programing language type inference systems.

More background in this cs.stackexchange answer: https://cs.stackexchange.com/questions/12691/what-makes-type-inference-for-dependent-types-undecidable

and this one, more centered on the unification problem:

https://stackoverflow.com/questions/1936432/higher-order-unification

And (tooting my own horn further, I guess), I recommend the article Elaboration in Dependent Type Theory by de Moura et al, as a discussion of the issues involved.


Understanding the talks in Conferences and Workshops I am a graduate student from India. I am very much interested in attending the Workshops, conferences, and invited lecturers given by prominent professors.

At the end of the talk as usual some people will ask questions and speaker will answer them. But my problem is I am not understanding most of the questions and answers. Even if I ask any question I am unable to understand the answer which given by speaker.

Can somebody share their experience and suggestions to my problem.

This may seem strange at first, but one way I've found to understand an area better is to write in it.

Every area of any discipline has its own mini-language. It consists most obviously of specialized terminology---but there is also a certain structure and order to how people in that area prefer to give and receive information. There are also particular ways of understanding certain difficult concepts, especially abstract or nonobvious concepts.

Reading is obviously key, and it will help you understand the terminology. But to really climb into the heads of those who present in your area, you have to write. You'll then be forced to learn good ways to structure information and ways to understand difficult concepts---and discover how and why the other researchers in your area think and talk the way they do.


Seeking for a game for modelling a problem using game thoery I have a problem which I want to formulate it as a game, using game theory. In this problem there is several agents, we can consider the agents as the employees of different offices, these agents have some information about the clients and these information are updates and increases over time. the problem is persuading the agents to present their information to a central office over time. the problem have a continous nature. I am seeking for a game to model this problem using game theory. May you please tell me which kind of games is sufficient for this problem?

Best Regards

The game you're describing is a continuous-time principal-agent problem. See A continuous-time version of the principal-agent problem (Sannikov 2008). Technically the goal there is to induce optimal effort from the employee, but, by the revelation principal, that's equivalent to having him reveal his private information.