Efficient Algorithm for bilinear pairing on ECC Bilinear Pairing in the elliptic curves is a wonderful mathematical mapping which is usually defined by the map $e:G_{1} \times G_{1} \rightarrow G_2$ for some groups of $G_{1}$ and $G_{2}$. For better understanding of pairing and its properties see the wikipedia.

Question1: Are there any efficient bilinear pairing or efficient pairing algorithms? If so, is this algorithm applicable to all kind of pairings, I mean is it a general approach for efficiently computing any pairing or just an algorithm specific pairing? Meanwhile, I am familiar with Weil and Tate pairing, but efficiency of implementation and performance is my concern.
Question2: Is there any article in which the efficient computability of pairing-based approaches are discussed? Or may be an article in which a comparison between pairing based approaches and discrete logarithm based approaches is discussed.

I have read some pairing-based approaches for group key exchange in which there is no clue on how efficient they are and also there is no comparison of this kind with their previous algorithms. So I doubted may be there is a nice article on this which has paved the way.

I realize this does not do justice to the breadth of your questions but as a starting reference, you may be interested in the benchmark times for various pairings implemented in the pairing-based cryptography (PBC) library:

http://crypto.stanford.edu/pbc/times.html

They reference RSA decryption to give a sense of time relative to a standard operation (although it isn't as useful as knowing a DL or ECC-DL operation). The main developer, Ben Lynn, also did his PhD on PBC implementations—the dissertation may answer some of your questions.


Family of functions with properties similar to k-wise independent hash functions I am looking for a family of functions that has similar properties to a family of $\ell$-wise independent hash functions. The goal is to hash $\ell$ pairwise different bit strings of length $k$ to a set of size $\approx \ell$ such that the probability for the last hash value to collide with any former hash value is almost identical for all possible inputs.

More formally, let $k, \ell \in \mathbb{N}$, where $\ell \gg k$ is polynomial in $k$. Now let $\mathcal{S} := \{(x_1, \ldots, x_{\ell}) \in (\{0,1\}^k)^\ell \text{ with } x_i \neq x_j \forall i \neq j\}$ be the set  of all sequences of length $\ell$ of pairwise different elements from $\{0,1\}^k$.

The question then is whether there is a family of functions $ \mathcal{H} := \{h : \{0,1\}^k \to \{0,1\}^m\} $, for some $m = \mathcal{O}(\log(\ell))$ such that

the upper and lower bounds on a collision for the last hash are almost identical, meaning
$$
\max_{(x_1, \ldots, x_{\ell}) \in \mathcal{S}}\{ \Pr_{h \in \mathcal{H}}[\forall i \in [\ell-1]: h(x_i) \neq h(x_{\ell})]\} -
\min_{(x_1, \ldots, x_{\ell}) \in \mathcal{S}}\{ \Pr_{h \in \mathcal{H}}[\forall i \in [\ell-1]: h(x_i) \neq h(x_{\ell})]
\} \leq 2^{\Omega(k)}
$$
and there is some constant $c \in (0,1]$, such that
$$
c \leq \min_{(x_1, \ldots, x_{\ell}) \in \mathcal{S}}\{ \Pr_{h \in \mathcal{H}}[\forall i \in [\ell-1]: h(x_i) \neq h(x_{\ell})]
\},
$$
independently from $k$ and $\ell$.
Furthermore, a function in $\mathcal{H}$ should be representable by $\mathcal{O}(k \log(k))$ many bits.

While a family of (almost) $\ell$-wise independent hash functions would fulfill conditions 1 and 2, all such families I am aware of would not fulfill condition 3 since they require at least $\Omega(\ell)$ many bits to represent a function from the family.

There is already this question on this Stackexchange, but it is only concerned with the lower bound and the size of the representation, not with the difference between upper and lower bound. There are also several publications that show that in many cases $k$-wise independence suffices to achieve results very close to full independence:

Schmidt, Jeanette P.; Siegel, Alan; Srinivasan, Aravind, Chernoff-Hoeffding bounds for applications with limited independence, SIAM J. Discrete Math. 8, No. 2, 223-250 (1995). ZBL0819.60032.

Dietzfelbinger, Martin; Rink, Michael, Applications of a splitting trick, Albers, Susanne (ed.) et al., Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-02926-4/pbk). Lecture Notes in Computer Science 5555, 354-365 (2009). ZBL1248.68166.

Celis, L. Elisa; Reingold, Omer; Segev, Gil; Wieder, Udi, Balls and bins: smaller hash families and faster evaluation, SIAM J. Comput. 42, No. 3, 1030-1050 (2013). ZBL1275.68075.

However, the publications mostly consider the probability in a balls into bins experiment for the maximal load of a bin to be greater than a threshold. While there is some similarity between the two questions, I fail to preciesly map my question to the maximum load of a bin.

Let $m = 1 + \log \ell$. Identify a hash function $h \colon \{0, 1\}^k \to \{0, 1\}^m$ with its $n$-bit truth table $h \in \{0, 1\}^n$ where $n = m \cdot 2^k$. Our hash family $\mathcal{H} \subseteq \{0, 1\}^n$ consists of an $\varepsilon$-biased set for a suitable $\varepsilon = \ell^{-\Theta(k)}$. Explicit constructions of such a hash family are known with
$$
\log |\mathcal{H}| = O(\log(n/\varepsilon)) = O(k \log \ell) = O(k \log k).
$$
See e.g. this paper.
To prove that this works, fix any $\vec{x} = (x_1, \dots, x_{\ell}) \in \mathcal{S}$. Let $f_{\vec{x}} \colon \{0, 1\}^n \to \{0, 1\}$ be the function indicating whether there is a collision on the last hash, i.e.,
$$
f_{\vec{x}}(h) = \bigwedge_{i = 1}^{\ell - 1} (h(x_i) \neq h(x_{\ell})).
$$
We will show that $\mathcal{H}$ fools this function, i.e., $|\Pr_{h \in \mathcal{H}}[f_{\vec{x}}(h) = 1] - \Pr[f_{\vec{x}}(U_n) = 1]| \leq 2^{-k}$. Conditions 1 and 2 will follow.
For each $z \in \{0, 1\}^m$, define $f_{\vec{x}}^{(z)} \colon \{0, 1\}^n \to \{0, 1\}$ by
$$
f_{\vec{x}}^{(z)}(h) = \left(\bigwedge_{i = 1}^{\ell - 1} (h(x_i) \neq z)\right) \wedge (h(x_{\ell}) = z).
$$
For a fixed $z$, the function $f_{\vec{x}}^{(z)}$ can be computed by a read-once CNF with $\ell-1+m=O(\ell)$ clauses that reads the bits of the truth table of $h$. For a suitable $\varepsilon = \ell^{-O(\log(1/\delta))}$, an $\epsilon$-biased distribution fools such read-once CNFs with error $\delta$ -- see this paper. Therefore, $\mathcal{H}$ fools $f_{\vec{x}}^{(z)}$ with error $\delta$. Now, $f_{\vec{x}} = \sum_z f_{\vec{x}}^{(z)}$, so by the triangle inequality, $\mathcal{H}$ fools $f_{\vec{x}}$ with error $\delta \cdot 2^m$. Choosing $\delta = 2^{-k - m}$, we have $\varepsilon = \ell^{-O(k + m)} = \ell^{-O(k)}$ as promised.
Now let's see how conditions 1 and 2 follow. For any $\vec{x} \in \mathcal{S}$, we have $\Pr[f_{\vec{x}}(U_n) = 1] = (1 - 2^{-m})^{\ell - 1}$. This value is independent of $\vec{x}$, and it changes by at most $2^{-k}$ when we use $\mathcal{H}$ instead of $U_n$, so for every two $\vec{x}, \vec{x}' \in \mathcal{S}$, we have $|\Pr_{h \in \mathcal{H}}[f_{\vec{x}}(h) = 1] - \Pr_{h \in \mathcal{H}}[f_{\vec{x}'}(h) = 1]| \leq 2 \cdot 2^{-k}$, verifying condition 1. Meanwhile, by the union bound, $\Pr[f_{\vec{x}}(U_n) = 0] \leq \ell 2^{-m} \leq 1/2$. Again, when we switch to $\mathcal{H}$, this value increases by at most $2^{-k}$, verifying condition 2.


lower bound of majority function? If a circuit ({AND OR NOT} circuit) with depth d computes the majority function, what's the best lower bound for majority function?
I know the lower bound for parity function is $ 2^{\Omega (n^{1/d})} $

You haven't specified exactly what kind of circuits, but in general since parity $\oplus$ is in $\mathsf{TC^0}$ and majority $Maj$ is complete for $\mathsf{TC^0}$, you get a similar subexponential size lower-bound for majority.

A simple reduction would go through counting function $NumOnes$ that counts the number 1s in the input in binary. This would give $2^{n^{\Omega(1/d)}}$ where constant in the exponent comes from the size of $\mathsf{AC^0}[Maj]$ circuit computing $numones$. I don't know the best value of the constant but it shouldn't be big.

On the other hand, there are $2^{n^{O(1/d)}}$ circuits for majority as majority is in $\mathsf{NC^1}$ and any $\mathsf{NC^1}$ circuits can be converted into a subexponential-size bounded-depth $\mathsf{AC^0}$ circuit (by performing a layered brute-force).


Deciding bound on Tensor Rank for a fixed value This question is related to a previous unanswered question of mine.  Please see that question for background.

When Håstad proved that computing tensor rank is NP-complete, the rank in question was allowed to be part of the input.  Specifically, given a Boolean formula with $n$ variables and $m$ clauses, Håstad constructed a tensor that has rank exactly $4n+2m$ if the formula is satisfiable and has some larger rank otherwise.

What if we fix the bound on the rank to some constant?  For example...

  What is the complexity of deciding if a tensor has rank at most 3?

The tensor should be defined over an infinite field, otherwise the problem is trivial (...only a finite number of things to check).  Answers for the natural infinite fields $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$ would be best.  I am personally interested in this question using the complex numbers.

Testing for constant border-rank can be done in polynomial-time, I'm pretty sure, if you're talking about tensors of fixed arity. More precisely, testing for border-rank $\leq r$ in $\mathbb{C}^{d_1} \otimes \dotsb \otimes \mathbb{C}^{d_k}$ can be done in something like $k(d_1 d_2 \dotsb d_k)^{2(r+1)}$ evaluations of $(r+1) \times (r+1)$ determinants plus some additional constant work (constant depending on $r$).

Theorem 3.7.1.1 of Landsberg's tensor book ("Inheritance") says that the equations for the variety of tensors of border-rank $\leq r$ in $\mathbb{C}^{d_1} \otimes \mathbb{C}^{d_2} \otimes \dotsb \otimes \mathbb{C}^{d_k}$ are given by the equations for border-rank $r$ in $\mathbb{C}^r \otimes \mathbb{C}^r \otimes \dotsb \otimes \mathbb{C}^r$ together with all $(r+1) \times (r+1)$ minors of flattenings. Since $r = O(1)$, there are only finitely many equations of the former type.

Border-rank 1 = rank 1, and more generally rank $\leq r$ implies border-rank $\leq r$. But border-rank 2 can have rank anywhere from $2$ to the arity $k$, and border-rank $3$ in arity 3 can have ranks 3, 4, or 5. Beyond that I don't know about testing for rank.


Collaborative tools for dummies/professors Suppose that coauthors from two or more different institutions are writing a paper in latex, and would like to do better than repeatedly emailing drafts back and forth.

They realize they can open for free a dropbox account, share the password, and synch the version of the paper on their computer with the one on dropbox. If two people are simultaneously editing the same section, however, they'll overwrite each other changes.

They have also heard that version-control systems like SVN and Git have tools to merge concurrent changes, which work reasonably well. The documentation of these products, however, is rather hard to read, and it is more focused on how to undo changes and how to manage different "branches" rather than on the basic needs of coauthors writing a paper.

Is there a simple step-by-step exposition on how to use a version-control system in this setup:

 central repository
 local copies
 "smart" merge
 no branches

?

Of the standard version-control systems, which one is the easiest to use? (We are talking theoretical computer science professors here.)

Are there even simpler tools that  only do synch with smart merge, without version control?

Conversely, do people who use version-control systems to even write a single-authored paper really feel that the unlimited-undo capability is worth the extra complexity?

First off: If your are interested in real-time collaborative editing, try something like gobby. It lets you literally edit a document at the same time.

As for revision systems, I am only familiar with SVN. This is what you do, after installing subversion, of course:

Get someone to set you up a repository and give you URL, username and password
Go to where you want to have your lokal copy
In a shell (command line?), type: svn co url://to.your/repository (check-out). Now a new folder with the repository's contents appears.

That's all. Now the most basic commands:

Whenever you add a new file foo, enter: svn add foo
Whenever you want to remove a file, enter: svn rm foo
Whenever you have made changes, enter: svn ci (check-in)
Whenever you want to get the newest stuff, enter: svn up (update)

There are also commands for moving, copying, branching, resolving conflicts,  ... but as long as you do not try funny stuff, you are fine with the above. If anything breaks or seems to, backup your edits, delete the whole folder and checkout the whole thing anew. That's for svn like rebooting for Windows.

Addendum: I see you seem to be concerned about "smart merges". I assume that you refer to have to different versions of a file merged, with the assumption that two people added things in disjoint parts of the paper. As far as I know, svn would treat that as a conflict, and probably rightly so. I don't think that there is a general procedure that ensures you get what you want after two people manipulated the same source. There are graphical svn clients that visualise such conflicts and help you resolving them; they are pretty much diff-viewers were you can choose which version to keep for every conflicting line). It will require work, though.


Funding opportunities for non-european people going to Europe for a PhD in TCS There are two chinese students who would like to come to Spain to pursue a PhD in TCS in our group. I know of course the funding possibilities in my country but wonder if you know any European and non-European and Chinese funding calls or opportunities for doing PhD.

An extension of this questions; is it there around any funding/grant stack exchange site or which ones do you use to track grants?

Never having worked or studied in Spain, I can not really help with local information. However, as I mentioned in the comments, the most obvious source for such funding in European universities (aside from internal university or departmental sources and local research councils) would be funding from the European Research Council. The ERC has many different kinds of grants, including training networks and personal grants, which can often be used to fund overseas students from. Additionally, the European Commission offers funding for postgraduates and postdocs via Marie Curie actions.

Further, there is the China Scholarship Council which also offers support for students wishing to study abroad.

Then there are the industry scholarships: Google, IBM, Microsoft, etc.

If either of the students is female, then there are more options (see Google's Anita Borg scholarship, etc.).

Lastly, many European countries have bilateral agreements with China or Chinese institutions which may be another potential source of funding.


Is there higher-dimensional generative grammar? I'm interested in computer music, where there are approaches to treat pieces of music as sentences in generative grammars or L-systems. Instead of composing, one could then specify a grammar and let the computer generate the music. E.g. the Yale group around the late Paul Hudak are very strong in that.

It has struck me that we use seemingly one-dimensional representations of information to represent higher-dimensional things, like plant growth with L-systems. Music, to me, seems to have at least two dimensions: The obvious time dimension and the "instrument" dimension, i.e. the ability to have several different sounds at the same time. And indeed, music notation has exactly these two dimensions.

There are 2-dimensional programming languages like Befunge, which didn't strike me as very useful (yet), but I couldn't find anything about generative grammars, where the sentences are 2-dimensional.

By a 2-dimensional sentence I mean that the characters are spread on a 2-dimensional grid, e.g. like this:

ab cde
 aabce
dca  b

Production rules could have 2-dimensional sentences on either side of the rule as well:

a -> bc
     e

b -> cd
e    ab

Has something like this been studied before?

For example in computer music, this could be quite useful. Pieces like Ravel's Boléro could be generated by a 2-dimensional production rule like this:

t -> tt
      t

This should be read as "If in a piece, the theme t is played by instrument 1 at some time, then we can produce a new piece in which t is played by instrument 1 at the same time, and immediately after by instrument 1 and 2."

Yes, there are n-dimensional grammars and in some cases specifically applied to music, see for example Grammar-based music composition by Jon McCormack, which talks about parametric extensions to L-grammars, or more generally, Regulated Array Grammars of Finite Index, Part I: Theoretical Investigations by Henning FERNAU, Rudolf FREUND and Markus HOLZER which talk about n-dimensional array grammars.


On bandwidth of graphs I am trying to find references on algorithms for graphs of bounded bandwidth, in the same way as it is done with treewidth for instance.
I could only find research related to  computing the bandwidth, or properties of this measure, but not using it as assumption for better algorithms.

Also, I am very interested in a generalization of bandwidth in higher dimensions. For instance this paper studies 2-dimensional bandwidth, but considering only the $L^1$ and $L^\infty$ norms on $\mathbb N\times \mathbb N$, whereas I am more interested in the euclidean norm $L^2$. It seems natural to consider graphs of $n$-dimensional bandwidth for euclidean norm. Formally, the $n$-dimensional bandwidth of a graph $G=(V,E)$ is defined as :
$$\min_{\alpha} ~\max_{(x,y)\in E}||\alpha(x)-\alpha(y)||_2$$
where $\alpha$ ranges over injective functions $V\to \mathbb N^n$.

This is pretty natural, for instance graphs coming from discretizations of real-life systems following differential equations would likely have bounded bandwidth. Indeed, if an edge takes you to the state of the system at the next time instant, it can not be too far from your current state if the time step is small enough and the system evolves continuously. It seems that this special structure could be used to design better algorithms (in particular for solving games on these graphs), but I could not find anything on this kind of graphs.

As you mentioned that "My main goal is to solve different kinds of games on these graphs, but I'm curious about other problems too", you can have a look at the thesis by Morgan Chopin -- "Optimization problems with propagation in graphs: Parameterized complexity and approximation" (https://tel.archives-ouvertes.fr/tel-00933769).
Here, author shows some results with "bandwidth" for "Firefighter" problem and "Target Set Selection" problem which can be thought of as a discretized version of "Influence Maximization".


Comparing $\mathbf{NP}$ and $\mathbf{E}$ We know that $\mathbf{NP} = \mathbf{NTIME}(n^{O(1)})$ and $\mathbf{E} = \mathbf{DTIME}(2^{O(n)})$.

The complexity zoo states that $\mathbf{E}$  does not equal $\mathbf{NP}$, and cites the following paper:

R. Book. On languages accepted in polynomial time. SIAM Journal on Computing, 1(4):281–287, 1972.

I have not read the formal proof; though I want to know why the following "intuition" fails:

Intution: Every $\mathbf{NP}$ language is solvable in $O(2^n)$ time, where $n$ is the size of the input.

Proof: Assume that $L \in \mathbf{NP}$. There's a poly-time Karp reduction from $L$ to $3SAT$, and a $3SAT$ formula with $n$ variables can be decided via exhaustive search in $O(2^n)$ time.

This was a comment, but it became too long. I want to give an explicit example where the input size increases. Take the classic reduction from CircuitSAT to 3SAT. The usual idea is to assign a variable to every gate in the circuit. The variable's value is the output of the gate. The you add the constraints that make a gate's output reflect the gate's input and gate type. So if a gate (whose variable is g_1) is an AND gate and has input wires coming from gates g_2 and g_3, you'll get a constraint like g_1 = g_2 AND g_3. We also have variables for the inputs, of course.

With this reduction, even though there are n inputs, if the size of the circuit is, say, $O(n^5)$, then the resulting SAT instance will have $O(n^5)$ variables, which will require $O(2^{n^5})$ time to solve by brute forcing on a deterministic TM.

You also asked why E is not closed under Karp reductions. That's easy. Take a problem that only be solved in $O(2^{n^2})$ time, and therefore it is not in E.  Now we can Karp-reduce this to a language in E by padding the input with $O(n^2)$ zeros. The language in E to which we're reducing is the original language with each input of size n padded with $O(n^2)$ zeros. Now since the input size is $O(n^2)$ and we know an algorithm that solves this in $O(2^{n^2})$ time, this problem is in E.  So we reduced a problem not in E to a problem in E, showing that E is not closed under Karp reductions.


Indistinguishability complexity of a subset Given set $S = \{0,1\}^n$, consider a subset $S' \subseteq S$. By determine we mean there is a deterministic TM $A_{S'}$ which always halts and defines a mapping $\{0,1\}^n \rightarrow {0,1}$ such that $A_{S'}(x) = 1$ iff $x \in S'$.

If $S_1'$ contains all even numbers in $S$, $\forall x \in S$, we can determine whether $x \in S_1'$ in polynomial time.
If $S_2'$ contains all numbers in $S$ which are smaller than $2^{n-1}$, $\forall x \in S$, we can determine whether $x \in S_2'$ in polynomial time.
If $S_3'$ contains $2^{n-1}$ randomly chosen numbers in $S$, $\forall x \in S$, intuitively, it may not be possible to determine whether $x \in S_3'$ in polynomial time using a polynomial-size TM.

Note that the set $S'$ itself is not part of the input. In this way the running time of $A_{S'}$ doesn't depend on the size of $S'$.

Intuitively, the size and running time (which have some trade-off) of the most efficient TM $A_{S'}$ (that can determine whether $x \in S'$ correctly) can be viewed as the indistinguishability complexity (defined by me) of the subset $S'$.

Question:

Is there any formal theory that exactly defines this idea?
How to measure this trade-off between the size and the running time?
For $S = \{0,1\}^{n}$, what is the subset $S'$ that has the largest indistinguishability complexity?

I assume $S'$ is parametrized by $n$, i.e.~it is not defined only for a single $n$ but for infinitely many $n$ (otherwise statements like "polynomial time" do not make sense). If so, you are merely defining the fundamental problem of the complexity of deciding membership in a language (i.e. the problem of complexity theory). I am not sure what you mean by "uniform": if you mean that there could be a different algorithm for different $n$, then this is the usual non-uniform complexity.


Remove unneeded atoms in CNF minimalization (SAT preprocessing) This might be a very basic question.

I am interested in all atoms of a propositional formula that can be removed from a particular formula, while the derived formula has the same satisfiability characteristics.

Consider:

$(\lnot a\lor b) \land (a \lor b)$

Here the atom a can be removed, as the formula can be reduced to simply b.

Is there a name for atoms that can be removed from a formula? I.e., atoms like a that can be removed from a formula? (Informally I would call them "don't care" atoms.)

There are certain tools like lingeling and minisat2 that can simplify or preprocess a SAT problem, given a CNF formula (see another answer).
Do this approaches reliably remove all atoms (like aabove) from the formula that can be removed? My rough guess would be that finding a minified formula is as complex as finding all the prime implicants of a formula? (Minification in my sense would be a formula with the least number of atoms.)

As Kyle Jones has mentioned, the example you provided is called (restricted) resolution.

Beside that, pure literals can also be safely removed from a SAT problem. Unit clauses can be assigned a truth value. Check this paper:

The Puzzling Role of Simplification in Propositional Satisfiability.  Inês Lynce and João Marques-Silva.

It discusses several preprocessing techniques for SAT, and its experiments showed that applying preprocessing for SAT leads to mix results. However, this paper might not be state-of-the-art.


Finding a permutation $p$ of $x_1, x_2, \dots, x_n$ which maximises $\sum_{i=1}^{n-1}|x_{p_{i+1}}-x_{p_i}|$ Here is the algorithmic problem I'm trying to solve:

Given a list of integers $x_1, x_2, \dots, x_n$ find a permutation $p_1, p_2, \dots, p_n \in [n]$ that maximises the sum $\sum_{i=1}^{n-1}|x_{p_{i+1}} - x_{p_i}|$.

I think this can be solved in $O(n\log n)$, I thought of sorting the list and returning a list where first element is maximum element, next element is minimum, next is maximum of those which are left, etc. But this leads to nowhere, I cannot prove that it's correct, so probably it isn't. So, any tips how to tackle this problem?

I found that the problem has been used in a student programming contest.

... if you still want to try to solve it by yourself don't move the mouse over the area below !!! :-)

  The programmingn contest is the Bubble Cup 7DC, Belgrade 2012.The key idea to solve it is to consider the middle element of the given array after sorting it in increasing order (if the number of elements is even then pick the value between the two middle elements); it splits the set in two halves $A$ and $B$.Then it is easy to prove that an optimal solution cannot contain three consecutive elements in increasing (or decreasing) order $... x_i < x_j < x_k ...$ because it is enough to move the middle element at the end of the array and the sum cannot decrease after the trasformation. So an optimal solution must proceed in a zig-zag style. Then we can prove that the optimal solution cannot contain two consecutive elements from the same side. Suppose that we have somewhere $... x_i, x_j, x_k ...$ with $x_i> x_j < x_k$ and $x_i, x_j, x_k \in B$. Then then the remaining sequence must contain three consecutive elements from $A$  $...x'_i,x'_j,x'_k...$ ordered as $x'_i < x'_j > x'_k$. Then $A \ni x'_j < x_j \in B$ can be swapped preserving the inequalities and strictly increasing the value of the sum.For the detailed proof see: Bubble Cup 7DC - Problem C: MaxDiff(it contains other nice problems)


When to use the Johnson-Lindenstrauss lemma over SVD? The Johnson-Lindenstrauss lemma allows one to represent points in a high dimensional space into points in lower dimension. When finding lower dimensional spaces of best fit, a standard technique is to find the singular value decomposition and then take the subspace generated by the largest singular values. When is it of interest to use Johnson-Lindenstrauss over the SVD?

The two approaches provide very different guarantees.

The JL Lemma says essentially "you give me the error you want, and I'll give you a low dimensional space that captures the distances upto that error". It's also a worst-case pairwise guarantee: for each pair of points, etc etc

The SVD essentially promises "you tell me what dimension you want to live in, and I'll give you the best possible embedding", where "best" is defined as on average: the total error of true similarity versus projected similarity is minimum.

So from a theoretical perspective they solve very different problems. In practice, which one you want depends on your model for the problem, what parameters are more important (error or dimension), and what kind of guarantees you need.


Threshold Fully Homomorphic Cryptosystems recently, Craig Gentry published the first public key encryption scheme (over plaintext space {0,1}) which is fully homomorphic, meaning that one can efficiently and compactly evaluate AND and XOR on encrypted plaintexts without knowledge of the secret decryption key.

I am wondering if there is any obvious way to turn this public key cryptosystem into a threshold public key cryptosystem such that everybody can encrypt, AND and XOR, but decryption is only possible if some (all) people sharing the key team up.

I would be interested in any ideas about that subject.

Thanks in advance

fw

A new paper by Steven Myers, Mona Sergi, and Abhi Shelat on eprint, "Threshold Fully Homomorphic Encryption and Secure Computation", claims a threshold fully homomorphic encryption scheme.
From their abstract:

...
Gentry [Gen09a] shows how to combine both ideas with fully homomorphic encryption in order to construct secure multi-party protocol that allows evaluation of a function $f$ using communication that is independent of the circuit description of $f$ and computation that is polynomial in $|f|$. This paper addresses the major drawback's of Gentry's approach: we eliminate the use of non-black box methods that are inherent in Naor and Nissim's compiler.
To do this we show how to modify the fully homomorphic encryption construction of van Dijk et al. [vDGHV10] to be threshold fully homomorphic encryption schemes.
...
Altogether, we construct the first black-box secure multi-party computation protocol that allows evaluation of a function $f$ using communication that is independent of the circuit description of $f$.


What's the simplest noncontroversial 2-state universal Turing machine? I'm wanting to encode a simple Turing machine in the rules of a card game. I'd like to make it a universal Turing machine in order to prove Turing completeness.

So far I've created a game state which encodes Alex Smith's 2-state, 3-symbol Turing machine. However, it seems (admittedly based on Wikipedia) that there's some controversy as to whether the (2, 3) machine is actually universal.

For rigour's sake, I'd like my proof to feature a "noncontroversial" UTM. So my questions are:

Is the (2,3) machine generally regarded as universal, non-universal, or controversial? I don't know where would be reputable places to look to find the answer to this.
If the (2,3) machine isn't widely accepted as universal, what's the smallest N such that a (2,N) machine is noncontroversially accepted as universal?

Edited to add: It'd also be useful to know any requirements for the infinite tape for mentioned machines, if you happen to know them. It seems the (2,3) machine requires an initial state of tape that's nonperiodic, which will be a bit difficult to simulate within the rules of a card game.

This is not a real answer to your question (I don't know much about the (2,3) machine debate); but I suggest you the paper "Small Turing machines and generalized busy beaver competition". I quickly read it some time ago, and it has a nice graph with the borderlines between the 4 types of small TMs:

decidable
open Collatz-like problem
$3x + 1$ simulation
universal

(perhaps some results have been improved).

The notion of TM used in the paper is the standard definition of TM used in papers on small universal Turing machines :

... They have a unique one-dimensional tape infinite in both directions, and a unique twoway
read–write head. There is a blank symbol denoted by 0. Initially, a
finite word, the input, is written on the tape, other cells contain the blank
symbol, the head reads the leftmost symbol of the input, and the state is the
initial state. At each step, according to the current state of the machine and
the symbol read by the head, the symbol is modified, the head moves left or
right (and cannot stay reading the same cell), and the state is modified. The
computation stops when a special halting state is reached. ...


Number of non-isomorphic connected graphs of $n$ nodes and $m$ edges Let $G( n, m )$ be the set of all possible connected graphs of $n$ nodes and $m$ edges such that, for each $g_1 \in G( n, m )$, $g_2 \in G( n, m )$, if $g_1 \neq g_2$ then $g_1$ and $g_2$ are non-isomorphic.

  Question

  How large can $|G( n, m )|$ be? Is it polynomial in both $n$ and $m$? Or is it superpolynomial in either $n$ or $m$?

According to Bollobas (Random Graphs), if you make "natural assumptions" on $n$ and $m$ there are $n!$ times more labelled graphs on $n$ vertices and $m$ edges than random unlabelled graphs on $n$ vertices and $m$ edges, so roughly $\frac{1}{n!}{{n \choose 2} \choose m}$ unlabelled graphs on $n$ vertices and $m$ edges. If you pick something like $m = \frac{1}{2}{n \choose 2}$, all those graphs should be connected with high probability, so I'd say --> massively superpolynomial !

Of course, you can break those "natural assumptions" by setting $m = 0$, or $m<n-1$ in your case...

Nathann


Best known joint containments for/by NP and Parity-P? Parity-P is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero number of acceptance paths). Thus Parity-P is basically PP's stunted younger sibling: while PP counts whether or not the number of accepting paths of an NP-machine is a majority or not (i.e. the most-significant bit of that quantity), Parity-P indicates the least-significant bit of the number of accepting paths.

Like NP, Parity-P contains UP (which contains P, "probably" strictly so); and like NP, Parity-P is contained in PSPACE.

Question. What are the best known joint upper and lower bounds for NP and Parity-P?

By Valiant-Vazirani, NP is contained in BP dot Parity-P (which obviously contains Parity-P).
Moreover, Toda showed that PH is in BP dot Parity-P which is in P^(#P) (which is in PSPACE).

For lower bounds, I think both classes contain a class known as FewP which contains UP and is like NP but you ask that strings in the language have at most polynomially many accepting paths.

[Update: corrected typo BPP instead of BP]


Hardness of parameterized CLIQUE? Let $0\le p\le 1$ and consider the decision problem

  CLIQUE$_p$
  Input: integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges
  Question: does $G$ contain a clique on at least $s$ vertices?

An instance of CLIQUE$_p$ contains a proportion $p$ out of all possible edges.  Clearly CLIQUE$_p$ is easy for some values of $p$.  CLIQUE$_0$ contains only completely disconnected graphs, and CLIQUE$_1$ contains complete graphs.  In either case, CLIQUE$_p$ can be decided in linear time.  On the other hand, for values of $p$ close to $1/2$, CLIQUE$_p$ is NP-hard by a reduction from CLIQUE itself: essentially, it is enough to take the disjoint union with the Turán graph $T(t,s-1)$.

My question:

  Is CLIQUE$_p$ either in PTIME or NP-complete for every value of $p$?  Or are there values of $p$ for which CLIQUE$_p$ has intermediate complexity (if P ≠ NP)?

This question arose from a related question for hypergraphs, but it seems interesting in its own right.

If $p$  can be a function of $t$, then the problem can be intermediate. Set up $p$ so that the number of edges will be say $\log^4 t$. Then obviously $s$ can be at most $\log^2 t$ and hence there is a $t^{\log^2 t}$ algorithm for this problem, meaning that the problem (under standard assumptions, say SAT doesn't have subexponential algorithms) cannot be NP hard.

On the other hand, this problem is harder than the standard clique problem on $\log^2 t$ vertices (you can always place all the edges on those vertices and ignore the rest). And so again, under the same assumption the problem doesn't have a polynomial time algorithm.

If $p$ is a constant then it's always NP hard as gphilip said.


What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model? Background
The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore real numbers can not be faithfully represented by finite strings over a finite alphabet.
Unlike the classical computability over finite strings where different models of computation like: lambda calculus, Turing machines, recursive functions, ... turn out to be equivalent (at least for computability over functions on strings), there are various proposed models for computation over real numbers which are not compatible. For example, in the TTE model (see also [Wei00]) which is the closest one to the classical Turing machine model, the real numbers are represented using infinite input tapes (like Turing's oracles) and it is not possible to decide the comparison and equality relations between two given real numbers (in finite amount of time). On the other hand in the BBS/real-RAM models which are similar to RAM machine model, we have variables that can store arbitrary real numbers, and comparison and equality are among the atomic operations of the model. For this and similar reasons many experts say that the BSS/real-RAM models are not realistic (cannot be implemented, at least not on current digital computers), and they prefer the TTE or other equivalent models to TTE like effective domain theoretic model, Ko-Friedman model, etc.
If I understood correctly, the default model of computation which is used in Computational Geometry is the BSS (a.k.a. real-RAM, see [BCSS98]) model.
On the other hand, it seems to me that in the implementation of the algorithms in Computational Geometry (e.g. LEDA), we are only dealing with algebraic numbers and no higher-type infinite objects or computations are involved (is this correct?). So it appears to me (probably naively) that one can also use the classical model of computation over finite strings to deal with these numbers and use the usual model of computation (which is also used for implementation of the algorithms) to discuss correctness and complexity of algorithms.

Questions:

What are the reasons that researchers in Computational Geometry prefer to use the BSS/real-RAM model? (reasons specific Computational Geometry for using the BSS/real-RAM model)
What are the problems with the (probably naive) idea that I have mentioned in the previous paragraph? (using the classic model of computation and restricting the inputs to algebraic numbers in Computational Geometry)

Addendum:
There is also the complexity of algorithms issue, it is very easy to decide the following problem in the BSS/real-RAM model:

Given two sets $S$ and $T$ of positive integers,
is $\sum_{s\in S} \sqrt{s} > \sum_{t\in T}\sqrt{t}$?

While no efficient integer-RAM algorithm is known for solving it. Thanks to JeffE for the example.

References:

Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale, "Complexity and Real Computation", 1998
Klaus Weihrauch, "Computable Analysis, An Introduction", 2000

First of all, computational geometers don't think of it as the BSS model.  The real RAM model  was defined by Michael Shamos in his 1978 PhD thesis (Computational Geometry), which arguably launched the field.  Franco Preparata revised and extended Shamos' thesis into the first computational geometry textbook, published in 1985.  The real RAM is also equivalent (except for uniformity; see Pascal's answer!) to the algebraic computation tree model defined by Ben-Or in 1983.  Blum, Shub, and Smale's efforts were published in 1989, well after the real-RAM had been established, and were almost completely ignored by the computational geometry community.

Most (classical) results in computational geometry are heavily tied to issues in combinatorial geometry, for which assumptions about coordinates being integral or algebraic are (at best) irrelevant distractions.  Speaking as a native, it seems completely natural to consider arbitrary points, lines, circles, and the like as first class objects when proving things about them, and therefore equally natural when designing and analyzing algorithms to compute with them.

For most (classical) geometric algorithms, this attitude is reasonable even in practice.  Most algorithms for planar geometric problems are built on top of a very small number of geometric primitives: Is point $p$ to the left or right of point $q$?  Above, below, or on the line through points $q$ and $r$?  Inside, outside, or on the circle determined by points $q,r,s$?  Left or right of the intersection of segments $qr$ and $st$?  Each of these primitives is implemented by evaluating the sign of a low-degree polynomial in the input coordinates.  (So these algorithms can be described in the weaker algebraic decision tree model.)  If the input coordinates happen to be integers, these primitives can be evaluated exactly with only constant-factor increase in precision, and so running times on the real RAM and the integer RAM are the same.

For similar reasons, when most people think about sorting algorithms, they don't care what they're sorting, as long as the data comes from a totally ordered universe and any two values can be compared in constant time.

So the community developed a separation of concerns between the design of “real” geometric algorithms and their practical implementation; hence the development of packages like LEDA and  CGAL.  Even for people working on exact computation, there is a distinction between the real algorithm, which uses exact real arithmetic as part of the underlying model, and the implementation, which is forced by the otherwise irrelevant limitations of physical computing devices to use discrete computation.

Within this worldview, for example, the most important open problem in computational geometry is the existence of a polynomial-time algorithm for linear programming.  No, the ellipsoid and interior-point methods don't count.  Unlike the simplex algorithm, those algorithms aren't guaranteed to terminate unless the constraint matrix happens to be rational.  (There are combinatorial types of convex polytopes that can only be represented by irrational constraint matrices, so this is a nontrivial restriction.)  And even when the constraint matrix is rational, the running times of those algorithms aren't bounded by any function of the input size (dimension$\times$#constraints).

There are a few geometric algorithms that really do rely heavily on the algebraic computation tree model, and therefore cannot be implemented exactly and efficiently on physical computers.  One good example is minimum-link paths in simple polygons, which can be computed in linear time on a real RAM, but require a quadratic number of bits in the worst-case to represent exactly.  Another good example is Chazelle's hierarchical cuttings, which are used in the most efficient algorithms known for simplex range searching.  These cuttings use a hierarchy of sets of triangles, where the vertices of triangles at each level are intersection points of lines through edges of triangles at previous levels.  Thus, even if the input coordinates are integers, the vertex coordinates for these triangles are algebraic numbers of unbounded degree; nevertheless, the algorithms for constructing and using cuttings assume that coordinates can be manipulated exactly in constant time.

So, my short, personally biased answer is this: TTE, domain theory, Ko-Friedman, and other models of “realistic” real-number computation all address issues that the computational geometry community, on the whole, just doesn't care about.


Why can't codes be defined over infinite fields? In Coding Theory, people use $q$-ary alphabets: why do we need a finite set? Why can't we define codes over infinite sets. such as $\mathbb{R}$ or $\mathbb{C}$?

Sphere packings give a nice analogue of codes over $\mathbb{R}$. A sphere packing is a set $\mathcal{P} \subset \mathbb{R}^n$ such that $d_{\mathcal{P}} := \inf_{x,y \in \mathcal{P}, x \neq y} \|x - y\| > 0$, where $\|\cdot \|$ is the Euclidean norm. This is called a sphere packing because we can place a(n open) sphere of radius $d_{\mathcal{P}}/2$ at each point in $\mathcal{P}$, and the spheres will not overlap.

There are many nice simple analogies between a code $\mathcal{C} \subseteq \mathbb{F}_q^n$ and a sphere packing $\mathcal{P} \subset \mathbb{R}^n$:

$d_{\mathcal{P}}$ is the minimum distance of the sphere packing, and it is the obvious analogue of the minimum distance of the code: $d_{\mathcal{C}} := \min_{x, y \in \mathcal{C}, x \neq y} \|x - y\|_H$, where $\|\cdot\|_H$ is the Hamming weight. In both cases, this can be viewed as a measure of "how correctable errors are when we encode messages via $\mathcal{C}$ or $\mathcal{P}$ over a noisy channel." E.g., $d_{\mathcal{P}}/2$ is the smallest Euclidean noise that we can add to a point in $\mathcal{P}$ so that we are unable to identify the original point uniquely, while $\lceil d_{\mathcal{C}}/2 \rceil$ is the minimal Hamming noise that can be added to a codeword so that we cannot identify the original codeword uniquely.
The analogue of a linear code is a lattice, $\mathcal{L} := \{ z_1 b_1 + \cdots + z_n b_n \ : \ z_i \in \mathbb{Z}\}$, where the $b_i$ are linearly independent vectors in $\mathbb{R}^n$. The minimum distance of a lattice is just the minimal length of a shortest non-zero vector in $\mathcal{P}$, just like the minimal distance of a linear code is the minimal Hamming weight of a non-zero codeword.
The analogue of the rate of the code $\alpha_{\mathcal{C}} := \log |\mathcal{C}|/\log q^n$ is $\delta_{\mathcal{P}} := \lim_{r \to \infty} \log|\mathcal{P} \cap B(r)|/\log \mathrm{vol}(B(r))$, where $B(r)$ is the Euclidean ball of radius $r$. For a lattice $\mathcal{L}$, we have $|\mathcal{L} \cap B(r)| \sim \mathrm{vol}(B(r))/\det(\mathcal{L})$, where $\det(\mathcal{L})$ is the absolute value of the determinant of the matrix given by the basis vectors $(b_1,\ldots, b_n)$. So, $\delta_{\mathcal{L}} = 1-\log \det(\mathcal{L})$.
For codes $\mathcal{C}$, we're often interested in maximizing the minimum distance $d_{\mathcal{C}}$ for a fixed rate $\alpha_{\mathcal{C}}$. For sphere packings $\mathcal{P}$, we are similarly interested in maximizing $d_{\mathcal{P}}$ for fixed $\delta_{\mathcal{P}}$. Notice that we can always scale a sphere packing $\mathcal{P}$ so that, say, $\delta_{\mathcal{P}} = 0$. So, we can assume without loss of generality that a sphere packing satisfies $\delta_{\mathcal{P}} = 0$. In contrast, it seems that codes with rate $\alpha$ and codes with rate $\alpha'$ are fundamentally distinct objects for $\alpha \neq \alpha'$.

Sphere packings are still an active area of research, both in fixed dimensions and in asymptotically large dimension. E.g., the optimal sphere packings are only known in dimensions 1, 2, 3, 8, and 24 (all achieved by lattices), with 8 and 24 dimensions solved only very recently by Viazovska et al (see http://arxiv.org/abs/1603.04246 and http://arxiv.org/abs/1603.06518). In arbitrarily high dimensions, the current record is held by Venkatesh (http://math.stanford.edu/~akshay/research/sp.pdf). A table of the densest known packings in various dimensions is available here: http://www.math.rwth-aachen.de/~Gabriele.Nebe/LATTICES/density.html.

One can also consider packings of objects other than spheres. E.g., one can replace the Euclidean norm in the definition of $d_{\mathcal{P}}$ by any norm.


Two rectangles whose sum of areas is given Given is $\mathcal{P} \in \mathbb{Z}$. Are sought two rectangles which edges have integer, positive value and sum of their areas is $\mathcal{P}$. Find this two rectangles, if you know that sum of their perimeters is the smallest possible. If there are many possible answers, find any of them.

This question was on pre-olympic polish computer science workshops and I'm looking good, well proven solution. Below I put solution, which received maximal number of points, I believe it will help, but it is illogical (a little bit) and no one knows, why it works...

Task has limitation $\mathcal{P} \leq 10^{18}$ and was at most ten questions per actuation, but I'm interested in general solution. We had 256MB of memory
and not more than 1.5 second to answer at ten questions (and pre-process).

Solution:
We are looking for $x_1, x_2, y_1, y_2 \in \mathbb{Z}$, such that $x_1\cdot y_1+x_2\cdot y_2 = \mathcal{P}$ and sum $x_1+x_2+y_1+y_2$ is minimal.
Let start from small observation, one of rectangles will be very small, second will be very big. If both were similar, sum will be $2 \cdot 4\sqrt{\frac{\mathcal{P}}{2}} = 4\sqrt{2\mathcal{P}}$, otherwise it is $4\sqrt{\mathcal{P}}$ from big one and something near zero from second, so sum is near $4\sqrt{\mathcal{P}}$.

In our algorithm, we will choose the largest rectangle (and big implicate small) and we will check if it is best, so far. So, we want answer question "best perimeter for area $\mathcal{P}'$" in $\mathrm{O}(1)$ time, where $\mathcal{P}'$ is small.

We can (in $\mathrm{O}(n \lg n)$ time) pre-process table $A[2..10^6]$, in which $A_i$ is best (smallest) perimeter of rectangle with area $i$.

set A[i] = 2*(i+1)
for i in (1, 1KK) :
    while j <= 1KK :
        A[j] = min(A[j], 2*(i, j/i))
            #it is well to keep i, j/i value for best perimeter in B table
        j += i

If we have this table, we can easily answer to above question. And rest of algorithm is easy.
If $\mathcal{P}$ is small, we are using just brute-force. Otherwise we are checking all $x_1$ in range $[\sqrt{\mathcal{P}} - 10^6; \sqrt{\mathcal{P}})$, as $y_1$ we are taking biggest integer, such that $x_1\cdot y_1 < \mathcal{P}$. Now $x_2y_2$ is imposed. We are taking $x_2, y_2$ from $B$ table. $(x_2, y_2) = B_{\mathcal{P} - x_1y_1}$. If $\mathcal{P} - x_1y_1 > 10^6$ we are assuming that such pair of rectangles is incorrect and we are taking the next value of $x_1$.
If we aren't, we will calculate best second triangle in $\mathrm{O}(\sqrt{\mathcal{P}'})$, we receive TLE (Time Limit Exceeded). Unfortunately we have no time for it.

Pseudocode (skipping all special cases, and small input):

def fun(P) :
answer = inf
for i in range(sqrt(P)-1KK, sqrt(P)) :
    j = floor(P/i)
    perimeter = i + j + best_perimeter(P - (i*j))
    answer = min(answer, perimeter)
      #we have to keep somewhere size of edges of best rectangles
return answer

My live C++ code (100/100 points).
I don't fully believe in this solution. I will be glad, if someone share with me good, correct, well proved solution. Is here any good solution for any range of $\mathcal{P}$?

Thank you for any advices!

Example:
If $\mathcal{P} = 6$, then $(x_1,y_1,x_2,y_2) = (2,2,1,2)$ is correct answer (perimeter is $14$) and $(5,1,1,1)$ is incorrect ($5 \cdot 1 + 1 \cdot 1 = 6 = \mathcal{P}$, but perimeter is equal to $16 > 14$).

Assume all integers involved are even. This can be ensured by multiplying $P$ by 4. Here is an idea that should speed up the search. Let $p = \left\lceil\sqrt{P}\right\rceil$. If $p*p = P$ we are done. Otherwise, let $k$ be the minimum such that $\alpha =p*p-k*k \leq P$. If $\alpha=P$, we are done as $(p-k)\times(p+k)$ is the desired solution with perimeter $$4p$$. Otherwise, clearly $1 \leq k^2 \leq 4p$ (otherwise, $p$ would be smaller). But this implies that $k \leq c*P^{1/4}$, where $c$ is some small constant. This implies that $P - \alpha \leq c'*P^{1/4}$.  Thus, the solution with rectangles $$(p-k)\times(p+k) \text{ and } 1\times(P-\alpha)$$ has perimeter $4p + O(P^{1/4})$. Since $4(p-1)$ is a lower bound on the solution by the argument below (intuitively, the isoperemeteric inequality), this implies that search range is only of size $O(P^{1/4})$ (as far as the overall perimeter is concerned).

It definitely feels like this argument can be pushed even further...

And Jeff is right - this is not necessarily too interesting as far as pure theory. But it is fun...

Lower bound. Observe that if the two rectangles are $x_1\times y_1$ and $x_2\times y_2$, then the rectangle $(x_1+x_2)\times(y_1+y_2)$ must have area larger than $P$. But then, the minimum perimeter rectangle of a given area is a square. This implies that $2(x_1+x_2+y_1+y_2) \geq 4\sqrt{P}$.


Solving a Min/Max equation set In solving a certain game, I've ended up with a set of equalities like these:

a == Max[b,c]/2+Max[d,e]/2
b == Min[f,g]/2+Min[h,i]/2
...
o == (1-d)/2+r/2
p == (1-d)/2
q == s/2+1/2
r == Max[1-h,1-i]/2+Max[t,u]/2
...

I create 2^N different equation sets, where N is the number of Max statements, and try to solve them individually using gaussian elimination or something like that. That would be something like $O(2^N*n^3)$.

By considering disjoin cycles and other heuristics, I could perhaps get it a bit faster, but I would still only be able to solve very simple games.

Are you aware of any algorithms, deterministic or approximate, that could make the above problem feasible for 30-50 or maybe even more Max statements?

Update:

Each equation is a simple linear combination of variables, constants and Max/Mins of two (or more) variables. The number of terms in each equation is constant
It is known, that there is an unique solution {a,b,c,...}
All variables are fractions in (0,1).

I can reduce the system by using Max[a,b] = (a+b-|a-b|)/2 and Snowie showed how to eliminate Max[a,b] by adding two inequalities and a binary variable. The complexity still seams to be O(2^N).

To follow up on Snowie's post:

For each term max(v1, v2) introduce a new variable $x_i$, subject to the constraints $x_i \geq v_1, x \geq v_2$

For each term min(v1,v2) introduce a variable $y_i$ subject to $y_i \leq v_1, y_i \leq v_2$.

Next, minimize the linear constraint $l = \sum x_i - \sum y_i$
subject to the inequations $x \geq v, y \geq v$, the linear equations $0 \leq v \leq 1$, AND the original linear system of equations.

This is a linear program, hence solvable in polynomial time. As the number of such constraints is polynomial, the entire system is solved in polynomial time.


Sorting a programs instructions until it works Lets say I have a computer program below.

(define (factorial x)
   (if (= x 0)
       1
       (else (* x (factorial (- x 1)))))

I then take each line of the program and create a random permutation.

       1
   (if (= x 0)
       (else (* x (factorial (- x 1)))))
(define (factorial x)

Now I give you a set of valid values that the program must return.
    1,2,6,24

Your task is to sort the permutations of the program until it gives you the result.

Is this a new problem? I haven't found anything remotely like the problem I proposed above.

What is the runtime to solving this problem?

This can be done by running all the $n!$ permutations in parallel and wait for one of them to output $1,2,6,24$ on inputs $1,2,3,4$.

(Of course, that does not guarantee that you found the correct permutation for input 5.)

Specific running time estimates may depend on the programming language being used. For instance, in BASIC each line is supposed to start with a line number which makes this solvable in polynomial time.


Break text evenly into certain number of lines There is a linear time algorithm for breaking text evenly into lines of maximum width. It uses SMAWK (or Knuth & Plass) and "evenly" means:
http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness

Is there an algorithm or a concave cost function for algorithm above which would take into account the number of lines I would like the text break into, instead of the maximum line width? Also in linear time?

In other words, I'm looking for a line breaking (or paragraph formation, or word wrapping) algorithm where the input is the desired number of lines, not the desired line width.

Just to describe a practically unusable approach: There are N words and N-1 spaces in-between each word pair, M is the desired number of lines (M <= N). After each space there might be at most one (possibly zero) line-break. Now, the algorithm would try to place the breaks in each possible combination, calculating the "raggedness" and return the best one. How to do it much faster?

Also, does such a problem have a name? What "family" of problems does it belong to? (E.g. "bin packing") If I wouldn't need the perfectly optimal solution, just a very good one, is it possible to solve it much faster? (some form of heuristics could be usable, if for a given input there were always the same, possibly sub-optimal, solution).

Update

Chandra Chekuri suggested bellow "a problem in Kleinberg and Tardos chapter on dynamic programming". It was a good read but it deals with line breaking based on width rather than line count. It might be adaptable to this problem which is something I'm trying to figure out now. Here is a good link to the solution, they even claim to solve it in linear time:
http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf

Also, there is a chapter "8.5 The Partition Problem" in The Algorithm Design Manual by Skiena which seems to be exactly on-topic, I'm still reading it, tough. (Unfortunately, from what I understood it has quadratic time complexity)

If you can compute the raggedness of a line without knowing anything about the other lines, then you can model the problem as finding a minimum-weight $M$-link path in a graph. With concave integer weights for edges, there is an algorithm that solves the problem in $O(N \log U)$ time, where $U$ is the largest absolute edge weight. Another algorithm solves the problem in $N 2^{O(\sqrt{\log M \log \log N})}$ time for any concave edge weights, assuming $M = \Omega(\log N)$. Both algorithms assume that you can compute the weight of an edge in constant time.

You could also use binary search to find a line width such that SMAWK uses $M$ lines with it. In some cases, this algorithm does not guarantee a solution with exactly $M$ lines, however.


Solver for uniform matroid isomorphism I want to solve the following coNP-complete problem efficiently in practice: Given a linear matroid represented as $k \times n$ matrix over a finite field $\mathbb{F}_p$ (where $p$ is large prime), test if the matroid is isomorphic to the uniform matroid with $n$ elements and rank $k$. In other words, test if all $k \times k$ submatrices have rank $k$.
Is there some algebraic software that can solve this problem potentially much faster than brute-force? In particular I am interested in methods that are able to beat the ${n\choose k}$ brute-force on at least some yes-instances.
I have tried reducing to integer programming and solving with CPLEX, but it is worse than brute-force already on two-digit primes.

You can get a square-root speed-up with a time-space tradeoff if you are working in $\mathbb{F}_2$.
The matrix $M$ is a no-instance iff there exists a non-zero vector $v$ of Hamming weight $\le k$ (i.e., with at most $k$ non-zero coordinates) such that $Mv=0$.  This is equivalent to saying that there exist $t,u$ of Hamming weight $\le k/2$ such that $Mt=Mu$ (since then $M(t-u)=0$ and $t-u$ has Hamming weight $\le k$).
Now you can enumerate all such $t$ and store $Mt$ in a hashtable, and look for collisions (or, sort the values $Mt$ and look for repeats).  This requires approximately ${n \choose k/2}$ time and space, which is better than your brute-force method.  But again it only works over $\mathbb{F}_2$.
You can improve this a bit further as follows.  Randomly partition the $n$ coordinates into two groups of $n/2$ coordinates, and restrict $t$ to be non-zero only on the first group (its zero on the second group), and $u$ to be non-zero only on the second group (it is zero on the first group).  Then if such $v$ exists, with probability ${k \choose k/2}/2^k \approx 1/\sqrt{\pi k/2}$, there exist $t,u$ that satisfy this restriction.  So, enumerate all such $t$, store $Mt$ in a hashtable, and for each $u$, look up $Mu$ in the hashtable (or, merge a sorted list of $Mt$ values and a sorted list of $Mu$ values).  If you repeat $40 \sqrt{\pi k/2}$ times, with a different partition each time, then you'll have an overwhelming probability of finding a solution if one exists.
This requires $40 \sqrt{\pi k/2} {n/2 \choose k/2}$ time and space, which is better than the above.
It's possible you might be able to apply other algorithms for finding a low-weight codeword in a linear code to this problem, if you are working in $\mathbb{F}_2$.
If you are working over $\mathbb{F}_p$ with $p>2$, then you can still do this method, and the running time will be something like $40 \sqrt{\pi k/2} {n/2 \choose k/2} (p-1)^{k/2}$ time and space.  We can compare this to the brute-force approach of enumerating all subsets of $k$ of the columns, then using Gaussian elimination to compute its rank; that will have running time ${n \choose k} k^3$.  The brute-force approach is better when $n/k \ll p$, and my approach is better when $n/k \gg p$.


Base extension in residue number systems with low space Suppose I have a number $x$ represented in a residue number system, so $x = (x_1, \ldots, x_m)$, where $x_i \equiv x \pmod{p_i}$, and the $p_i$'s are all relatively prime (they can be distinct primes if it helps).

I would like to compute $x \bmod{p^*}$ for some $p^* \not\in \{p_1, \ldots, p_m\}$, but with low space.

Of course I could reconstruct $x$ itself, but this would require $\log (\prod_i p_i) = \sum_i \log p_i$ bits of working space. Rather, I would like the computation to use something more like $\max_i \log p_i$ bits of space. Is this possible?

As a concrete example, suppose $\{ p_1, \ldots, p_m\}$ are the first $m$ primes and I would like to compute $x \bmod 4$. Or $\{ p_1, \ldots, p_m\}$ are the first $m$ odd primes, and I would like to compute $x \bmod 2$.

By a result of Chiu, Davida, and Litow [1], improved by Hesse, Allender, and Barrington [2], Chinese remainder representation base extension is computable in logarithmic space, and in fact in DLOGTIME-uniform $\mathrm{TC}^0$, when all the $p_i$ are “small” (i.e., given in unary). Since the effective size of the input is here $p^*+\sum_ip_i\le p^*+m\max_ip_i\le p^*+(\max_ip_i)^2$ (using the fact that the $p_i$ are distinct), this means it is computable in space
$$O\bigl(\max\{\log p^*,\log p_i:i=1,\dots,m\}\bigr).$$

References:

[1] A. Chiu, G. Davida, B. Litow, Division in logspace-uniform $\mathit{NC}^1$, RAIRO – Theoretical Informatics and Applications 35 (2001), no. 3, pp. 259–275.

[2] W. Hesse, E. Allender, D. Mix Barrington, Uniform constant-depth threshold circuits for division and iterated multiplication, Journal of Computer and System Sciences 65 (2002), no. 4, pp. 695–716.


Algorithms for Polygon triangulation I had hard time finding algorithm or published papers on Self intersecting polygon(also polygon with hole structure) triangulation.

Can any one guide me to find published paper/algorithm, please?

PS: someone tag this question appropriately please, I do not have enough reputation points to do it.

Have you considered Seidel's algorithm ?


Minimal directed circles partition cover of a directed graph We are given a $G(V,E)$ digraph and a $c:E \rightarrow \mathbb{R}$ weight function. We are searching for a set of $C_{1}(V_{1},E_{1}),C_{2}(V_{2},E_{2}),\ldots,C_{k}(V_{k},E_{k})$ directed circles such that $V_{1},\ldots,V_{k}$ form a partition of $V$ and $\sum_{i = 1}^{k}\sum_{e \in E_{i}}c(e)$ is minimal among all such covers.

I know there is a polynomial algorithm which solves this problem. I just don't know what that algorithm is. Anyone knows this problem and can give a hint or a solution?(hint preferred)

This is done by using minimum cost flow. See section 17.4 here.


In what fields does a knowledge of formal semantics prove useful? (If this is better for programmers SE, let me know, but I imagined you guys would have more thorough answers)

I'm a mathematics major, but I have a pretty deep interest in CS (especially in compiler design, reverse engineering, etc).

This site recommended a book on formal semantics. I imagine that a knowledge of semantics is useful there (but I'm not quite sure how, yet). Are there other fields in which this knowledge is directly useful, other than academic treatments of programming languages?

Formal semantics is useful primarily when you want to reason about programs.

In the past this was mainly done in programming language development (and to a lesser degree in compiler construction). Increasingly formal semantics is also used in automatic and interactive program verification, which is beginning to see industrial use. Since you are interested in compiler design, verified and certifying compilation is a hot research topic now that is based heavily on formal semantics. Check out the following systems.

X. Leroy's CompCert. This was the first verified compiler: a realistic, moderately-optimizing compiler for a large subset of the C language down to PowerPC and ARM assembly code.
The MPI's Pilsner, the first multi-pass compiler for a higher-order imperative language to be compositionally verified. Most prior work (such as CompCert) has focused on verifying whole-program compilers.
CakeML. A compiler for an ML dialect. The focus of CakeML is on minimising the trusted computing base, not on optimisation or on breadth of source language features.
Cogent. A certified compiler from a simple functional language with linear types (useful for reasoning about memory management) to C.

Progress on such compilers has been much swifter than many (including myself) anticipated, and I expect to see more and more of this work to seep into industrial compilers.

The problem with formal semantics is rarely to write down the semantics of a language. That's usually simple.  The real issue is how efficiently to prove theorems about programs in a language using the semantics.


Local updates in weight-balanced search trees In Kurt Mehlhorn's monograph "Data Structures and Algorithms 1: Sorting and Searching", he poses the following question  (III.9.22):

  Design a balanced tree scheme where the worst case rebalancing cost after an insertion or deletion is $O(\log \log n)$. Hint: Use weight-balanced trees. If $n$ elements are stored then rebalance up to height  $O(\log \log n)$ as described in the text. With every node $v$ of height $\log \log n$ associate a pointer which points to an ancestor $p(v)$ of $v$ in the tree. If a transaction goes through $v$ then we also rebalance $p(v)$, if necessary, and advance $p$ one step towards the root. Show that the root balance of nodes of height $\log \log n$ or more cannot deteriorate too much.

It is not obvious to me how a slowly-moving $p(v)$ can keep nodes of height $\Omega(\log \log n)$ but $o(\log n)$ balanced. My intuition is that these nodes must be cared to more frequently than I can manage with the "one ancestor pointer" system.

Any ideas on how to maintain $p(v)$?

There has been some work on reducing the cost of updates at a known location in weight-balanced trees, but I'm not aware of any weight-balanced tree with $o(\lg n)$ worst-case updates. (Treaps are weight balanced and have $O(1)$ expected-time updates.)

Mehlhorn's monograph is available electronically in an updated form that unfortunately leaves out III.9.

Section 3 of Brodal et al.'s "D$^2$-Tree: A New Overlay with Deterministic Bounds" shows how to update a weight-balanced tree in $O(1)$ amortized time, but the worst-case time is still $\Omega(\lg n)$.


3-SAT mixed with 2-SAT formulas Context: Refering to the  question: Complexity of the $(3,2)_s$ SAT problem? and since the paper by Porshen and Speckenmayer : Satisfiability of mixed Horn formulas, we know that even when $F_3$ is Horn, the problem of deciding the satisfiability of $F_3 \wedge F_2$ is NP-complete - where $F_3$ and $F_2$ are respectively 3-CNF and 2-CNF formulas.
I am wondering if there exist some cases where $F_3 \wedge F_2$ is easy to decide.
Hence my question:
Let $F_3$ a 3-CNF containing only clauses with exactly 3 different literals and $F_2$ a 2-CNF defined on the same variables as $F_3$.
What is the complexity of deciding the satisfiability of $F_3 \wedge F_2$ when $F_3$ and $F_2$ are both monotone?
Thank you.

If $F_3$ and $F_2$ are both monotone, satisfiability can be checked in polynomial time (or even in coNLOGTIME), as $F_3\land F_2$, which is also monotone, is satisfiable iff it is satisfied by the $\vec1$ assignment, that is, iff it does not contain the empty clause.
If one of the formulas is allowed to be monotone and the other one negated monotone (i.e., having only negative literals), then satisfiability of $F_3\land F_2$ is NP-complete: given a 3-CNF $F$ in variables $x_1,\dots,x_n$, let $F_3$ be the monotone 3-CNF obtained from $F$ by replacing all negative literals $\neg x_i$ with new variables $y_i$, and let $F_2=\bigwedge_i(\neg x_i\lor\neg y_i)$. Then $F$ is equisatisfiable with $F_3\land F_2$.
In particular, if $(\vec x,\vec y)$ is a satisfying assignment for $F_3\land F_2$, then for each $i$, at most one of $x_i$ or $y_i$ gets value $1$, that is, $y_i\le\neg x_i$. Thus, if we modify the assignment so that $y_i:=\neg x_i$, it will still satisfy $F_3$ as it is monotone. It follows that $\vec x$ satisfies the original formula $F$.


Asymptotically good codes In short my question is what are all known explicit constructions of asymptotically good codes over finite alphabet?

In more details: A sequence of codes codes $C_i: F^{k_i}\rightarrow F^{n_i}$ with distances $d_i$ is asymptotically good iff exists constants $R,\delta$ such that
 $\frac{k_i}{n_i}\geq R, \frac{d_i}{n_i}\geq \delta$.
My question is what are all known ways to construct such asymptotically good codes.
(Note the question is about finite alphabets)

I can give two examples:

1) Goppa AG codes: http://en.wikipedia.org/wiki/Goppa_code

2) Expander codes: http://en.wikipedia.org/wiki/Expander_code

3) Justesen codes:  http://en.wikipedia.org/wiki/Justesen_code

I would like to know an other examples of asymptotically good codes.

Usually the question is interesting for constant alphabet sizes, since otherwise Reed-Solomon codes obviously achieve the Singleton bound.

For constant (but still large) alphabet sizes, there are explicit codes that "approximately" achieve the Singleton bound, and are thus also asymptotically good. See

Venkatesan Guruswami and Piotr Indyk. Linear time encodable and list decodable codes Proceedings of STOC 2003.

Also there are several flavors of Expander and Concatenated Codes (rather than the famous constructions) that are asymptotically good. For example see

"Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs" by Alon et al.

Also there are more sophisticated "concatenated-like" constructions that achieve much more than asymptotic-goodness, for example:

V. Guruswami and A. Smith. Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate, FOCS 2010.

Finally, any construction of codes for stochastic errors (that is, the channel BSC(p)) that achieves constant rate and exponentially small error must be asymptotically good. However, I'm not aware of any such explicit constructions other than concatenated codes (Forney/Justesen and similar variations).


Is anyone aware of a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm? At http://www.dharwadker.org/tevet/isomorphism/, there is a presentation of an algorithm for determining if two graphs are isomorphic. Given a number of shall we say, "interesting" claims by A Dharwadker, I am not inclined to believe it.

In my investigation, I find that the algorithm will definitely produce the correct answer and tell you that two graphs are not isomorphic when in fact that is correct. However, it is not clear that the algorithm will consistently tell you if two graphs are isomorphic when they actually are. The "proof" of their result leaves something to be desired.

However, I am not aware of a counter-example. Before I start writing software to test out the algorithm, I thought I would see if anyone was already aware of a counter-example.

Someone requested a synopsis of the algorithm. I will do what I can here, but to really understand it, you should visit http://www.dharwadker.org/tevet/isomorphism/.

There are two phases to the algorithm: A "signature" phase and a sorting phase. The first "signature" phase (this is my term for their process; they call it generating the "sign matrix") effectively sorts vertices into different equivalence classes. The second phase first orders vertices according to their equivalence class, and then applies a sort procedure within equivalence classes to establish an isomorphism between the two graphs. Interestingly, they do not claim to establish a canonical form for the graphs - instead, one graph is used as a kind of template for the second.

The signature phase is actually quite interesting, and I would not do it justice here by attempting to paraphrase it. If you want further details, I recommend following the link to examine his signature phase. The generated "sign matrix" certainly retains all information about the original graph and then establishes a bit more information. After collecting the signatures, they ignore the original matrix since the signatures contain the entire information about the original matrix. Suffice to say that the signature performs some operation that applies to each edge related to the vertex and then they collects the multiset of elements for a vertex to establish an equivalence class for the vertex.

The second phase - the sort phase - is the part that is dubious. In particular, I would expect that if their process worked, then the algorithm developed by Anna Lubiw for providing a "Doubly Lexical Ordering of Matrices" (See: http://dl.acm.org/citation.cfm?id=22189) would also work to define a canonical form for a graph.

To be fair, I do not entirely understand their sort process, though I think they do a reasonable job of describing it. (I just have not worked through all the details). In other words, I may be missing something. However, it is unclear how this process can do much more than accidentally find an isomorphism. Sure, they will probably find it with high probability, but not with a guarantee. If the two graphs are non-isomorphic, the sort process will never find it, and the process correctly rejects the graphs.


For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$? In a related question, Saeed and Super8 have mentioned the Robertson-Seymour theory which enables us to find $k$ disjoint paths between pairs of vertices $\{s_i,t_i\}_{i=1}^k$ in poly time for fixed $k\in \mathbb{N}$.

Suppose now that we are trying to find $k$-disjoint-paths, such that the sum of their lengths is minimal.

Related results:

Using a similar reduction to the one I proposed here, it is possible to show that if there's a single source (and $k$ targets), the problem is in $P$.
There's a known algorithm(with the unusual runtime of $O(|V|^8)$) for a related problem, where only shortest $s_i\to t_i$ paths are to be considered. In this variant, $k=2$ is in $P$ .
In the same paper, they state that (notice it's not the same problem):

  "the complexity for fixed $k \geq 3$ remains an open  problem. "

What can we say about the "short-$k$-disjoint-paths" problem?

We just answered this for $k=2$:

Andreas Björklund and Thore Husfeldt, Shortest two disjoint paths in polynomial time, ICALP 2014, to appear.
PDF of proceedings version, rev. e5d5661


Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists? Peter Shor commented on this post:

years of experience in theoretical computer science says that the thermodynamic behavior of two NP complete problems are in general not similar.

What can we say about the distribution/thermodynamics of $A$ w.r.t. $B$ if we know that $A \le_M B$ (there is a reduction from $B$ to $A$), or if we know that $A, B \in C$ where $C$ is some complexity class ($P$, $NP$, co-$NP$, etc.)?

What can we say on the thermodynamics if there isn't a reduction from $A$ to $B$, or given their complexity classes?

I am not sure if it is a wicked idea to use complexity theory whose main concern is the worst-case scenarios while discussing thermodynamics, or statistical physics, whose general aim is to characterize phase transitions and describe the average case (principle of maximum entropy). Here is somehow a related work that states "NP problems" in terms of an Ising model.

With thermodynamics you have to be careful with the kind of reductions you allow, or (as Peter Shor pointed out) there can be essentially no thermodynamic relationship implied by a reduction. For example, if we consider not just the complexity of languages, but also the complexity of functions, every language is equivalent (under pretty simple reductions) to a permutation of $\Sigma^*$, and permutations can in principle be computed with zero thermodynamic cost.


Random restrictions and the connection to total influence of Boolean functions Say we have a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$ and  we apply $\delta$-random restriction on $f$. In addition, say that the decision tree $T$ that computes $f$ shrinks to size $O(1)$ as a result of the random restriction. Does this imply that $f$ has a very low total-influence?

Claim: If $\delta$-random restriction of $f$ has decision tree of size $O(1)$ (in expectation), then the total influence of such $f$ is $O(\delta^{-1})$.

Proof sketch:
By definition of influence we have
$Inf(f) = n \cdot \Pr_{x,i}[f(x) \neq f(x+e_i)]$.
Let us upper bound $\Pr_{x,i}[f(x) \neq f(x+e_i)]$ by first applying a $\delta$-restriction, then picking $i \in [n]$ among the remaining coordinates, and fixing at random everything except for $x_i$.

Now, if $\delta$-restriction reduces the decision tree of $f$ to size $O(1)$,
then in particular the $\delta$-restriction of $f$ depends on $r = O(1)$ coordinated.
Let us now pick one random unfixed coordinate (among $\delta n$), and fix all others randomly. Since the $\delta$-restriction of $f$ depends on at most $r$ coordinates, we get a function (on one bit) that is not constant with probability at most $\frac{r}{\delta n}$.
Therefore $Inf(f) = n \cdot \Pr_{x,i}[f(x) \neq f(x+e_i)] \leq \frac{r}{\delta}$, as required.

Remark: The claim above is tight by taking a parity function on $O(1/\delta)$ bits.


What is schema theory within Genetic Algorithms I understand (some) of the workings behind schema theory in genetic algorithms, for example:

*****0 would match the genome 010100

But could anyone explain what schema theory (in Genetic Algorithms) is used for, and how it's used?

If I remember correctly (it's years since I last studied this), schema theory isn't really used for anything.  Rather, it's an attempt to explain why genetic algorithms seem to work well.  As I'm not an expert, I can only point you to a book that I remember reading about schemata, Melanie Mitchell's book


Superpolynomial Simulator One method for proving a protocol secure is through simulation-based models. This simulator uses ideal/real paradigm in which a protocol is secure in the real model if it is proven secure in an ideal model using a trusted third party (you can refer to the Canetti's UC framework to realize what is the power and use of this simulator, although use of this simulator dates back to 80s). This simulator is often given polynomial power to simulate the ideal world and if an external entity (observer) cannot distinguish between a real run and a simulated run with probability at most half plus negligible, we say that the protocol is secure or following UC terminology for realizing a functionality, the protocol securely realizes the functionality. It is good to mention that the simulator is also simulating the attacker, so the power of the simulator is essentially power of the attacker. There is often times that the simulator has superpolynomial power.

  Question: Does superpolynomial simulator has any advantage over a polynomial simulator? I need a good article on cons and pros of such a simulator.

A good article in which the author have used a polynomial simulator is Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions of Canetti.

Well, your edited version of the question revealed a reference to the following paper:

Rafael Pass. 2003. Simulation in quasi-polynomial time, and its application to protocol composition. In Proceedings of the 22nd international conference on Theory and applications of cryptographic techniques (EUROCRYPT'03), Eli Biham (Ed.). Springer-Verlag, Berlin, Heidelberg, 160-176. (See also this version.)

The paper discusses and justifies the need for such simulators.
The abstract reads:

  We propose a relaxation of zero-knowledge, by allowing the
  simulator to run in quasi-polynomial time. We show that protocols satisfying this notion can be constructed in settings where the standard definition is too restrictive. Specifically, we construct constant-round straight-line concurrent quasi-polynomial time simulatable arguments and show
  that such arguments can be used in advanced composition operations without any set-up assumptions. Our protocols rely on slightly strong,
  but standard type assumptions (namely the existence of one-to-one one-way functions secure against subexponential circuits).

For a more thorough discussion, I suggest taking a look at Rafael Pass's M.Sc. thesis.


graphs where vertex coloring is in P but independent set is NP complete Is there an example of a class of graphs for which the vertex coloring problem is in P but the independent set is problem is NP complete?

Supposedly the reference "NP-complete problems on a 3-connected cubic planar graph and their applications" by Uehara (a paper I haven't actually seen) proves that independent set is NP-complete even for triangle-free planar graphs. But by Grötzsch's theorem they are always 3-colorable, and testing for smaller numbers of colors than 3 is easy in any graph, so they can be optimally colored in P.

Circle graphs have the opposite property: for them, coloring is NP complete but the independent set problem is easy.


Tool for specifying operational semantics for given formally specified programming language I am trying to translate code from one programming language into another (to be specific - from RuleML to Drools, but other pairs can be expected as well) and it would be nice to know - whether there exists more general workbenches for this.

E.g. one can formally specify programming language, that is clear. But are there any tools that can be used for capturing the formal semantics for formally specified language. It is obvious that the operational semantics is the most suitable for industrial programming languages. And - if semantics is specified then the translation from one programming language into other can be done at the meta-level. I guess, that this maybe too hard for C-to-Java translation, but it should work for more modest, recent languages that are created by academia.

I have heard about Maude, but I guess that there can be something more. My experience is that Google can not replace bibliographies or suggestions from community. Thanks.

We have been working on one for the last few years: Lem, a higher-order, typed language with backends for OCaml, Coq, Isabelle/HOL, HOL4, LaTeX and HTML.  Lem has been used internally in the group to formalise various machine models (PowerPC, ARM, and so on), memory models (the C memory model, etc.), programming language semantics (OCaml Light), and so on.


Characterisation of P in terms of register machines It is a well-known result that Turing machines and random access machines (RAMs) can simulate each other with a polynomial slowdown.

It is relatively straightforward to prove that indirect addressing and binary shift (or, equivalently, division by two) are actually redundant when working in polynomial time, i.e., that polynomial-time Turing machines are equivalent to polynomial-time Minsky-like register machines with a constant number of registers, augmented with constant-time addition and subtraction instruction (rather than just increment and decrement).

This can be showed by encoding the sequence of symbols on the tape of the Turing machine as a single large integer stored in one of the registers; the individual symbols can be accessed by performing multiplications and divisions (implemented via repeated doubling).

(Incidentally, register machines without constant-time addition and subtraction are provably slower than Turing machines on certain problems.)

I have the feeling that this result must have been published a long time ago, but I seem unable to find it in the literature. Does anyone know a reference (possibly the first published one) for it?

The classic reference for these kind of results is the survey by Peter van Emde Boas, "Machine Models and Simulations", the first chapter of Handbook of Theoretical Computer Science, Vol. A.

For simulations between RAM and Turing machines see Theorems 2.5 and 2.6, pp. 26--27. It also contains pointers to historic references.


What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper I have been going through Kempe-Kitaev-Regev's paper The Complexity of the Local Hamiltonian Problem. In the first paragraph of page 3, the authors point out that:

  To the best of our knowledge, this is the ﬁrst reduction inside QMA (i.e., not from the circuit problem).

What does 'not from the circuit problem' mean and what does the circuit problem refer to?

QMA is defined as the set of problems for which there is a polynomial quantum "verifier" circuit. So I guess the "circuit problem" refers to deciding whether such a verifier circuit has an accepting input. QMA-completeness of the $k$-local Hamiltonian problem is typically proven by encoding this circuit in a Hamiltonian (i.e., "by reduction from the circuit problem"). In this paper instead they prove QMA-completeness of 2-local Hamiltonians by reduction from 3-local Hamiltonians (hence, "not from the circuit problem").


Dynamic Upper Envelope of lines in the plane There are easy algorithms to calculate the upper envelope of an arrangement of lines in the plane. See e.g. section 2.3 in the survey
Davenport-Schinzel sequences and their geometric applications.

Are there any known algorithms / data structures for the dynamic version of the same problem? That is, we want to maintain the upper envelope of a set of lines in the plane under the following operations:

insert$(\ell$): adds line $\ell$ to the set
delete$(\ell)$: removes line $\ell$ from the set
query$(x)$: return the line with $x$ coordinate in the upper envelope. In other words, return the line in the set which is first hit by a vertical downward ray from the point $(x, \infty)$.

"someone" is right.  Timothy Chan's paper "Dynamic Planar Convex Hull Operations in
Near-Logarithmic Amortized Time" appears to solve the problem with insertions/deletions taking $O(\log ^{1+\epsilon}n)$ amortized time, and queries taking $O(\log n)$ time.  He solves your problem which is dual to the convex hull problem.


In a cryptosystem, why does the message space need to be finite? I am learning cryptography through Douglas Stinson's book: Cryptography -- Theory and Practice (3rd ed.).  The first definition in the text is

A cryptosystem is a five tuple (M,C,K,E,D) where
 - M is a finite set ...

That is the set of "plaintexts" or unencrypted messages must be finite.  My question is: how reasonable of a definition is this?  For any natural language, there are an infinite number of messages that one can send.  It seems this is incomplete to me.  It seems that M is the alphabet we are encrypting, and to encrypt a string in M* (what I would call the message space) we encrypt by
   $$e_k(m_1 \cdots m_j) = e_k(m_1) \cdots e_k(m_j)$$
(where $e_k \in E$ is an encryption function -- note that elements of $E$ can be viewed as functions $e : K \to M \to C$).
But I feel this is a bad idea because we are reusing a key.

One reason for this is that one can first define a cryptosystem having a small finite message space, and then on top of that, construct another cryptosystem that can handle longer message spaces. This is a very reasonable modular design methodology.

A couple of examples:

given a block cipher with a finite message space, one can use a
block cipher mode (like CBC or CTR) to extend the message space
to be essentially infinite.
given the Paillier public-key cryptosystem, one can institute a
specific length-parameter (as done by Damgård and Jurik) and allow
to efficiency encrypt messages of arbitrary length.

One caveat though is that if messages are of arbitrary length, then also the time to encrypt increases accordingly. If we want to be the cryptosystem to be secure against adversaries working in some time $t$, it is better to restrict the message length so that encrypting any messages of that length takes considerably less time than breaking the cryptosystem (with a small message length).

Remark: one can obviously try to define security in a way that breaking small messages can be easier than breaking long messages, but this does not make sense in practice.


Explanation of 1-generic to prove undecidability of halting problem This question is about an answer in question

  Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

Bjørn Kjos-Hanssen answer states that:

  You can first show that the halting problem (the set $0'$) can be used
  to compute a set $G\subseteq\mathbb N$ that is 1-generic meaning
  that in a sense each $\Sigma^0_1$ fact about $G$ is decided by a
  finite prefix of $G$. Then it is easy to prove that such a set $G$
  cannot be computable (i.e., decidable).

I have trouble understanding this sentence as I am new to forcing. For example, what does "finite prefix" mean here? Can someone explain this sentence? (I know what $\Sigma^0_1$ means.)

Can someone explain the general idea behind forcing? I am also looking for easy to read introductions articles and books about forcing.

edit: So, how can we prove that each $\Sigma_1^0$ fact about $G$ being decided by a finite prefix leads to the fact that $G$ cannot be computable?

A finite prefix of  $G$ is $G \cap \{0,1,\ldots n\}$ for some $n$. It is easier if you look at the characteristic function of $G$ which can we viewed as an infinite word in $2^\omega$. Then a finite prefix is a finite initial part of $G$.

For forcing, there are many resources, depends on what you want to learn. A point to start is the Wikipedia pages and the references listed there: Forcing (set theory), Forcing (recursion theory). Timothy Chow's article A Beginner's Guide to Forcing is a good introduction.


Maximizing strictly increasing convex function Let the objective be to maximize the sum of $f_i(x_i)$ where all $f_i$ are strictly increasing convex functions. Maximizing a convex function is hard as a local maximum might not be a global one. However for the special case described above, since $f_i$ are strictly increasing, from what I understand, the local maximum should be the global one.

If so, are there any special techniques that can optimize the objective (or maybe a piecewise approximation of it) subject to linear inequality constraints quickly?

Thanks

I'm sorry I don't fully understand the question, but if the point is to find the maximum, considering the local maximum is the global, then any gradient based method is going to take you directly to it. For instance artificial neural networks (gradient backpropagation).


Sparse Walsh-Hadamard Transform The Walsh-Hadamard transform (WHT) is a generalization of the Fourier transform, and is an orthogonal transformation on a vector of real or complex numbers of dimension $d = 2^m$. The transform is popular in quantum computing, but it's been studied recently as a kind of preconditioner for random projections of high-dimensional vectors for use in the proof of the Johnson-Lindenstrauss Lemma. Its main feature is that although it's a square $d\times d$ matrix, it can be applied to a vector in time $O(d \log d)$ (rather than $d^2$) by an FFT-like method.

  Suppose the input vector is sparse:
  it has only a few nonzero entries (say
  $r \ll d$). Is there any way to
  compute the WHT in time $f(r,d)$ such
  that $f(d,d) = O(d \log d)$ and
  $f(r,d) = o(d \log d)$ for $r = o(d)$
  ?

Note: these requirements are merely one way of formalizing the idea that I'd like something that runs faster than $d \log d$ for small $r$.

Index the WHT rows by an integer x, for $0 \le x \lt d$.  So x has log d bits.  Similarly, index the columns.  The (x,y) position is $(-1)^{\langle x,y \rangle}$ where the exponent is the dot product of length log d.  Assume r is a power of 2, rounding up if necessary.  Break the dxr matrix into rxr blocks by letting the first log r bits vary and fixing the other log(d/r) bits in each of the d/r ways. This rxr block is a smaller WHT matrix of size r, except there may be some columns missing, repeated, or negated.  In any case, preprocess the vector easily then do an rxr WHT in time r log r, then repeat d/r times for total time d log r.

Example:

d = 4.

WHT H is

++++
+-+-
++--
+--+

Arbitrary set of columns is 00 and 10 (leftmost and two over from that):

++
++
+-
+-

Row blocks are

++
++

and

--
--

In each block, there are repeated columns, missing columns and, in the second block, negated columns.  Preprocess a vector $(a,b)^T$ into $(a+b,0)^T$ and multiply by 2x2 WHT:

++
+-

Then preprocess $(a,b)^T$ into $(-a-b,0)^T$ and multiply by 2x2 WHT:

++
+-


How high are the higher types that appear in practice? This is admittedly a rather naively put and vague question, and I'm not sure how much more specific I want or can make it, but I'll try.

By "practice" I mean surely in actual programming practice (of which I embarrassingly don't know much), but also in mathematical practice, whenever certain higher-type objects are employed as examples or counterexamples within arguments.

By the "height" of a type, I don't mean to include the obvious and natural arbitrariness involved in objects like, say, the fixpoint functional (in fact, in the spirit of the question, I would prefer to understand this as a type $2$ object "up to parameter types", so to speak). A better example of what I mean would be the well-known (from mathematical practice, at least) fan functional, of type $((\mathbb{N} \to \mathbb{B}) \to \mathbb{N}) \to \mathbb{N}$, given by
$$
\lambda f. \mu m. \forall_{\alpha, \beta}
\left(
\forall_{n < m} \alpha(n) = \beta(n) \to f(\alpha) = f(\beta)
\right) \ ,
$$
where $f : (\mathbb{N} \to \mathbb{B}) \to \mathbb{N}$ and $\alpha, \beta : \mathbb{N} \to \mathbb{B}$.

My questions: Are there any objects of yet higher type than $3$ (possibly "up to parameter types") that are naturally used in the literature? In practice?

Okasaki's Functional Pearl, "Even Higher-Order Functions for Parsing or Why Would Anyone Ever Want To Use a Sixth-Order Function?" answers this question with a type of order 6.


A word anticorrespondence problem A problem instance is a finite list of 4-tuples $(\alpha_1, u_1, v_1, \beta_1), ..., (\alpha_N, u_N, v_N, \beta_N)$, where $\alpha_i, \beta_i \in X$ come from a finite set, and each $u_i,v_i \in A^*$ are words over a finite alphabet $A$.

A solution to the problem is a sequence of indices $i_1, i_2, ..., i_K$ such that

For all $1 \leq k \leq K-1$, we have $\alpha_{i_k} = \beta_{i_{k+1}}$.
The words $u' = u_{i_1} u_{i_2} \cdots u_{i_K}$ and $v' = v_{i_1} v_{i_2} \cdots v_{i_K}$ are not prefixes of each other

That is, an instance is like an instance of PCP, but with restrictions on how "dominoes" can be composed, and instead of finding strings that are equal, we need strings that differ by at least one symbol.

It is not immediately obvious to me how to decide this problem, and I have not been able to find an example of it in the literature.

Update: Origin of the problem

Given a finite state transducer over input/output alphabets $\Sigma, \Gamma$ and with initial state $p^{-}$, two states $q_1, q_2$ are said to be twinned iff for all $u,v \in \Sigma^*$ and $y_1,y_2,z_1,z_2 \in \Gamma^*$ if

$$ p^{-} \stackrel{u/y_1}{\to} q_1 \stackrel{v/z_1}{\to} q_1 \text{ and } p^{-} \stackrel{u/y_2}{\to} q_2 \stackrel{v/z_2}{\to} q_2$$

then either $z_1=z_2=\varepsilon$ or $|z_1|=|z_2| \neq 0$ and one of $y_1, y_2$ is a prefix of the other. [Weber & Klemm, Economy of description for single-valued transducers, 1995]. This is equivalent to the "algebraic" definition given in [Berstel, Transductions and Context-free languages, 1979].

There are effective procedures for deciding whether all states are twinned or not. I am interested in computing all pairs of states that are not twinned. Applying the method of squaring transducers [Beal, Carton, Prieur, Sakarovitch, 2000], this reduces to deciding the problem in my question for all pairs of states.

Isn't the solution a one-counter language?

The succession of the domino's is easily seen as a finite state restriction. For the unequality of $u'$ and $v'$ you have to find a single position where these strings differ. Keep track of $|u'|-|v'|$ during computation on the stack. You just nondeterministically choose such a letter, on a position of the longest of $u'$ and $v'$. Then keep simulating until the shortest string comes alongside with that same position.

I know this construction from a short paper (Prefix and equality languages of rational functions are co-context-free IPL 28 (1988) 77-79): "Theorem. For every two rational functions F and G, the complement of their prefix language Pref(F,G) is a one-counter language".
However that technique is a slight variation from an earlier result by J. Berstel: Every iterated morphism yields a co-cfl, Inform. Process. Lett. 22 (1986) 7-9.

Provided of course, I read your definition in the right way.