Optimal random bits complexity for universal hashing Let $Q_N:=\{0,1\}^N$ denote the $N$-dimensional Hamming cube. Let $a\in Q^N$ and $X\sim\mathrm{Unif}(Q^M)$ be input and random bits respectively, and function $f$ maps the the joint space to the $P$-dimensional cube $f:Q^{N+M}\to Q^P$. Defining hash function as $H(a):=f(a,X)$, what is the optimal $M$ if we require hash $H$ to be universal and uniform?
\begin{align}
&\Pr(H(a)=H(b))\le 2^{-P} &&\forall a,b\in Q^N, a\neq b\\
&\Pr(H(a)=c)=2^{-P} &&\forall c\in Q^P,a\in Q^N
\end{align}I'm interested in constructive answers, where $f$ can explicitly designed.

I believe the best known bound is in Woelfel's "Efficient strongly universal and optimally universal hashing", Theorem 5, which presents a set with $M = N + \lfloor (N - P)/2 \rfloor - 1$, where $P$ is the number of bits in the codomain.


Semiring examples from formal language theory I'm learning algebraic theory of parsing. My first problem is identifying semiring examples which are specific to formal language theory. Here is an attempt to construct two examples.

1 Given CNF grammar, the elements of semiring are sets of terminal and nonterminal symbols with the operations:

i) Multiplication, joining the two sets pair-wise according to CYK rule. For example given CNF grammar

s: p p | q r
t: p q
u: q q

then

$ \{p,q,r\}\otimes \{p,r\} = \{s,t\} $

ii) Addition is set union, e.g.

$ \{p,q\}\oplus \{q,r\} = \{p,q,r\} $

Unfortunately, multiplication is not associative.

2 The elements of second semiring are sets of not symbols but grammar rules [not necessarily in CNF] amended with position. The operations are

i) Multiplication, joining all matching pairs of elements according to Earley complete rule. For example given CNF grammar

s: p q r
r: s t | u

then

$ \{s: p \bullet q r,s: p q \bullet r\}\otimes \{r: u \bullet \} = \{s: p q r \bullet \} $

ii) Addition is again the set union, e.g.

$ \{s: p \bullet q r, r: \bullet s t\}\oplus \{r: u \bullet \} = \{s: p \bullet q r, r: \bullet s t, r: u \bullet\} $

This example is also deficient.

Semiring with elements being sets of grammar rules and multiplication being rule substitution seems to work fine. Yet, this is just relation algebra in disguise. Indeed, let view each grammar rule as an equivalence class -- a set of pairs of words consisting terminal and nonterminal letters related by rule's application, e.g.

$ [t : s a] = \{ (t,sa),(ta,saa),(bt,bsa),(abt,absa),... \} $

Then, recognition of a word in a grammar is a chain of relational compositions, e.g.

$ [t:sa] \otimes [s:aa] \otimes \{(aaa,aaa)\} =  \{(t,aaa)\} $

(This monomial is reminiscent of semiring parser polynomial from Josh Goodman PhD thesis; however, let reiterate that constructing new semirings by taking polynomials and matrices is not of our interest here).

So, the question remains: is the semiring of formal languages over alphabet $\Sigma$ the only example?

There are plenty of semirings related to language theory. First of all, the Boolean semiring. Next any class of languages closed under finite union and (concatenation) product is a subsemiring of the semiring of all languages. For instance the rational (= regular) languages form a semiring. See also the related notion of Kleene algebra.

The $k \times k$ matrices over a semiring do form a semiring. In particular, matrices over the Boolean semiring encode nondeterministic finite automata and matrices over the slightly larger semiring $\{-\infty, 0, 1\}$ encode transitions of a Büchi automaton. Matrices over a semiring are used to characterize rational series.

The tropical semirings, in particular $(\mathbb{N} \cup \{+\infty\}, \min, +)$ and $(\mathbb{N} \cup \{-\infty\}, \max, +)$ play a proeminent role in automata theory. They also led to a new branch of mathematics, the tropical geometry.


Proofs techniques related to Curry–Howard correspondence I am looking for sources about formalized notion of programs. This seems to be closely related to Curry-Howard correspondence, but one could also track this back to Universal Turing Machines and its ability to read description and input of any TM.

When reading about Curry-Howard correspondece I feel that the primordiality of UTM-s can harm research on programs with the unique conclusion that any program can be reduced to symbols, states and rules. Does there exist the opposite approach, where high-level computation systems are defined and examined? What are good resources about it?

What you want exists, and is an enormous area of research: it's the entire theory of programming languages.

Loosely speaking, you can view computation in two ways. You can think of machines, or you can think of languages.

A machine is basically some kind of finite control augmented with some (possibly unbounded) memory. This is why introductory TOC classes go from finite automata to pushdown automata to Turing machines --- each class takes a finite control and adds some more memory to it. (Nowadays, the finite control is often  limited even more, as in circuit models.)  The essential thing is that the finite control is given up front, and all at once.

A language is a way of specifying a whole family of controls, in a compositional way. You have primitive forms for basic controls, and operators for building up larger controls from smaller ones. The primordial language, the lambda-calculus, in fact specifies nothing but control -- the only things you can define are function abstractions, applications, and variable references.

You can go back and forth between these two views: the $snm$-theorem is essentially a proof that Turing machines can implement function abstraction and application, and Church encodings demonstrate that the lambda-calculus can encode data. But there's nontrivial content in both of these theorems, and so you should not make the mistake of thinking that the two ways of understanding computation are the same.

Researchers in complexity and algorithms typically take machines as fundamental, because they are interested in costs and in feasibility results. To exaggerate a bit, the basic research question they have is:

  What is the least powerful machine that can solve a certain kind of problem?

Language researchers take languages as fundamental, because we are interested in expressiveness and impossibility results. With a similar exaggeration, our basic research question is:

  What is the most expressive language that rules out a certain kind of bad behavior?

As an aside, note how the two goods each kind of theoretician values are directly in conflict! Good work in algorithms and complexity lets you solve a harder problem, using less resources. Good work in languages lets programmers do more things, while forbidding more bad behaviors. (This conflict is basically why research is hard.)

Now, you might ask why more Theory A types don't use languages, or why more Theory B researchers don't use machines. The reason arises from the shape of the basic research question.

Note that the stylized basic research question in algorithms/complexity is a lower bound question -- you want to know that you have the best solution, and that there is no possible way to do better, no matter how clever you are. A language definition fixes the means of program composition, and so if you prove that a lower bound with a language model, then you might be left with the question of whether it might not somehow be possible to do better if you extended your language with some new feature. A machine model gives you the whole control in one go, and so you know everything the machine can possibly do right from the outset.

But machine specifications are exactly the wrong thing for saying interesting things about blocking bad behavior. A machine gives you a whole control up-front, but knowing that one particular program is okay or bad doesn't help you when you want to extend it or use it as a subroutine -- as Perlis's epigram states, "Every program is a part of some other program and rarely fits." Since language researchers are interested in saying things about whole classes of programs, languages are much better suited for purpose.


Hardness of approximating chromatic number of triangle-free graphs The chromatic number of graph, $\chi( G)$ is hard to approximate for general graphs.

Are there results of hardness of approximating $\chi(G)$ for triangle-free graphs?

They can be 3-colored in polynomial time, no? I didn't check the literature but here is a simple approach: take a DFS tree of the graph and color a node $u$ at depth $d(u)$ with color $(d(u)\mod 3)$. This gives a proper coloring since (1) the neighborhood of each vertex is an independent and (2) two nodes $u,v$ such that $|d(u)-d(v)| \geq 2$ cannot be adjacent.


Regular expressions without union but with backreferences As a follow-up to my question Regular expressions without alternation, I was wondering what was known about the power of regular expressions in which union is not allowed but backreferences are.

I'm familiar with a number of papers discussing regular expressions with the addition of backreferences, but none that I've seen address the union-free version. This class would be incomparable with the class of regular languages, but are they as hard to recognize as full regular expressions with backreferences?  (I've seen several terms used for this; none seem to be standard.)  In the case without backreferences, removing union seems to reduce expressibility without making membership tests much/any faster.

As before union means the same as alternation, logical OR, | (in standard regexes), / (ABNF), ∪, etc.

If you are allowed to use complementation to express $\Sigma^*$ as $\emptyset^{C}$, the resulting language class includes the pattern languages (see, e.g., this survey by Kai Salomaa).

As shown by Angluin, the membership problem for pattern languages is NP-complete. (This holds even if you consider pattern languages that are generated by patterns that do not contain terminal symbols.)

So, membership for this class is as hard as for the full class of regular expressions with backreferences.


Finding the paths through a graph that reuse as many of the nodes as possible I'm implementing an encryption algorithm which does a bunch xor operations to mix up the columns. Because I want to find the lower bound of the number of xor operations, I'm trying to figure out the best way to reuse intermediate results. I've created a graph with all the intermediate results and now want to find the paths through that graph that reuse the most nodes.

Simplified example: I want to calculate $abc$ and $bcd$ from $a,b,c,d$. I can only combine two variables at a time. Combining is commutative: the order does not matter. I've created a graph with all the possible intermediate results ($ab, bc, cd$). Obviously the best way to calculate $abc$ and $bcd$ is to do it like $abc = a (bc)$ and $bcd = d (bc)$. This way you can reuse the result of $bc$ and you end up doing 3 operations, instead of the 4 operations if you would do something like $abc = (ab)c$ and $bcd = (bc)d$.

In other words, I want fo find these paths:

       abc         bcd
        |           |
  +-----+--+--------+
  |        |        |
  | ab     bc   cd  |
  |        |        |
  |      +-+-+      |
  |      |   |      |
  a      b   c      d

Is there an algorithm suitable for finding this, or is there an algorithm that I can adapt to find this? (If there is an approach that doesn't use graphs, I'd like to learn of it as well).

Actual problem:
I have 16 inputs $x_0 \cdots x_{15}$ which are xored like this:

$$
\begin{array}{rcl}
x_0 &=& x_0 \oplus x_4 \oplus x_7 \oplus x_{10} \oplus x_{12} \oplus x_{14} \oplus x_{15} \\
x_{1} &=& x_1 \oplus x_4 \oplus x_{11} \oplus x_{12} \oplus x_{15} \\
x_{2} &=& x_2 \oplus x_5 \oplus x_8 \oplus x_9 \oplus x_{12} \\
x_{3} &=& x_3 \oplus x_6 \oplus x_9 \oplus x_{10} \oplus x_{13} \\
x_{4} &=& x_0 \oplus x_3 \oplus x_4 \oplus x_8 \oplus x_{10} \oplus x_{11} \oplus x_{14} \\
x_{5} &=& x_0 \oplus x_5 \oplus x_8 \oplus x_{11} \oplus x_{15} \\
x_{6} &=& x_1 \oplus x_6 \oplus x_8 \oplus x_{12} \oplus x_{13} \\
x_{7} &=& x_2 \oplus x_7 \oplus x_9 \oplus x_{13} \oplus x_{14} \\
x_{8} &=& x_2 \oplus x_4 \oplus x_6 \oplus x_7 \oplus x_8 \oplus x_{12} \oplus x_{15} \\
x_{9} &=& x_3 \oplus x_4 \oplus x_7 \oplus x_9 \oplus x_{12} \\
x_{10} &=& x_0 \oplus x_1 \oplus x_4 \oplus x_{10} \oplus x_{13} \\
x_{11} &=& x_1 \oplus x_2 \oplus x_5 \oplus x_{11} \oplus x_{14} \\
x_{12} &=& x_0 \oplus x_2 \oplus x_3 \oplus x_6 \oplus x_8 \oplus x_{11} \oplus x_{12} \\
x_{13} &=& x_0 \oplus x_3 \oplus x_7 \oplus x_8 \oplus x_{13} \\
x_{14} &=& x_0 \oplus x_4 \oplus x_5 \oplus x_9 \oplus x_{14} \\
x_{15} &=& x_1 \oplus x_5 \oplus x_6 \oplus x_{10} \oplus x_{15} \\
\end{array}
$$

I want to find groups such as $\{x_0, x_4\}$, $\{x_1, x_4\}$ and $\{x_{0}, x_{4}, x_{10}\}$ that are contained in several of these multiplications.

You are looking for the shortest straight-line program to compute a set of formulas involving xor.

This is NP-hard. There are papers on how to efficiently solve this problem with  SAT solver. For example, Fuhs and Schneider-Kamp had this recent paper on Synthesizing Shortest Linear Straight-Line
Programs over GF(2) using SAT.

There is a proof that this problem is MAXSNP-hard by Boyar, Matthews and Peralta, see here.


Isomorphism notion between sets of triples Graph Isomorphism is natural problem which is most widely believed to have intermediate complexity between $P$ and $NP$-complete. GI can be thought as deciding the existence of an isomorphism between two sets of node pairs. I'm trying to develop a notion of isomorphism between sets of triples.

We are given two hyper-graphs $G1$ and $G2$ such that the set of hyperedges ($E_1$ and $E_2$) consists of  triples of 3 nodes $\{t_1, t_2, t_3 \}$. We say that Hyper-graphs $G1$ and $G2$ are isomorphic if there is bijection $f$ from $V_1$ to $V_2$ such that pair $\{u,v\} \in E1 $ if and only if $\{f(u),f(v) \} \in E2 $. We say $\{u, v \} \in E $ if there is a triple (hyperedge) $\{ u, v, z\} \in E$ for some node $z$.

Is it $NP$-complete to decide the existence of such isomorphism between two hyper-graphs $G1$ and $G2$?

Your problem reduces to graph isomorphism, so is not $\mathsf{NP}$-complete unless the polynomial hierarchy collapses.

In fact, you've essentially already given the reduction in your question: given a 3-uniform (=every hyperedge has size 3) hypergraph $G$, construct from it the graph $f(G)$ which has the same vertex set, and such that $\{u,v\} \in E(f(G))$ iff there exists a $z \in V$ such that $\{u,v,z\} \in E(G)$. (When $G$ is a hypergraph, I use $E(G)$ to mean the set of hyperedges.) Then $G_1$ and $G_2$ are isomorphic-in-your-sense iff $f(G_1) \cong f(G_2)$ as graphs. It is not hard to check that this reduction only takes polynomial time (note that $|E(f(G))| \leq |V(G)| |E(G)|$).

It is also probably worth mentioning that there is already a well-established notion of hypergraph isomorphism that is different from your notion. If we consider a hypergraph $G$ as a vertex set $V$ together with a collection of hyperedges $E \subseteq P(V)$ (each hyperedge is a subset of $V$), then two such hypergraphs are isomorphic if there is a bijection $\pi\colon V_1 \to V_2$ such that $E_2 = \pi(E_1)$. (Here I am abusing notation twice: by "$\pi(E_1)$" I mean $\{\pi(e) : e \in E_1\}$ and by $\pi(e)$ for $e \subseteq V$ I mean $\{\pi(v) : v \in e\}$.) Hypergraph isomorphism in this sense is Karp-equivalent to graph isomorphism, but by a slightly less immediate reduction than from your problem. However, fast (in theory) algorithms for hypergraph isomorphism are often more difficult than those for graph isomorphism (see, e.g. Babai and Codenotti, FOCS 2008).


Translating typed functional language to untyped lambda calculus Defining a typed function in haskell,

double::Integer->Integer
double a = a + a

And we can get an untyped version of double and let's call it double' to distinguish from the typed one.
Then, we can't prevent someone from passing a non-integer value to double' and luckily retrieving a meaningless(?) value, or being stuck in infinite loop. However, we can denote a constraint that 'if a is an integer, double' a is also an integer'.

Using Church encoding, it would be 'if the normal form of a is λf.λx.f(f...f(x)), then the one of double' a is also λf.λx.f(f...f(x))'. I agree that this is not strict enough, and that's the point my questions begin.

Is there any strict and general way to describe that kind of constraints?
If so, how powerful is it compared to type systems?

I'm sorry that my question is so ambigious. But I think that there could have been some similar approaches, and only links to them would be very helpful.

There's an old way of doing what you're asking for, coming from domain theory. Let $D$ be the collection of all values of the untyped $\lambda$-calculus. We can undestand $D$ to be some sort of a domain, or the set of closed normal terms, it does not really matter. We define a type to be a retraction $r : D \to D$, i.e., a continuous map (or a closed term if you want definable types) such that $r \circ r = r$. Such an $r$ represents the collection of its fixed points $D_r = \{x \in D \mid r(x) = x\}$. The map $r$ itself is a coercion from $D$ to $D_r$. Because it is a retraction, it does not do anything to elements of $D_r$.

Now, given any map $f : D \to D$ say that it maps $D_r$ to $D_q$ when $f = q \circ f \circ r$. This equation says that:

$f$ is already determined by its restriction $f{\restriction}_{D_r}$ to $D_r$ (because $f = f{\restriction}_{D_r} \circ r$),
the image of $f$ is contained in $D_q$ (because $f = q \circ f$).

Putting these two together, we see that $f$ can be thought of as going from $D_r$ to $D_q$ (it is important that $f$ does not carry any additional information about how to map elements outside $D_r$, or else we could  have several different functions that all act the same way on $D_r$).

Actually, any map $g : D \to D$ can be coerced to a map from $D_r$ to $D_q$ by the retraction $g \mapsto q \circ g \circ r$.

Let us see how this relates to your question. You would like to have a way of saying that a map $f$ maps integers to integers (I presume you mean natural numbers since you speak of Church numerals). So what we need is a map $r$ such that $r (r x) = x$ if, and only if, $x$ represents an integer. Once we have such a map we can express the fact that $f$ maps integers to integers with the equation $f = r \circ f \circ r$.

So it remains to write down a map $r$ in the untyped $\lambda$-calculus whose fixed points are Church numerals (and also some diverging terms which denote bottom). I think this might work:
$$r(x) = \mathtt{rec}\;\mathtt{Z}\;(\lambda n\,y \,. \mathtt{S}\,y)\;x,$$
where $\mathtt{rec}$ is a simple recursor over natural numbers, $\mathtt{Z}$ is zero and $\mathtt{S}$ is successor. Intuitively, speaking, if $x$ behaves like a natural number, then $r(x)$ will "rebuild" it into standard form $\mathtt{S}(\mathtt{S}(\cdots \mathtt{Z}))$.

We need to be a bit careful about how $\mathtt{rec}$ is implemented. It has to satisfy
$$\mathtt{rec}\;x\;f\;\mathtt{Z} = x$$
and
$$\mathtt{rec}\;x\;f\;(\mathtt{S}\,n) = f\;n\;(\mathtt{rec}\;x\;f\;n),$$
and it should "crash" when we feed it something that does not behave like a numeral.


Minimum length walk from s to t covering a subset of vertices I want to find the current literature for the following problem (I have searched
on google/asked friends/some Profs didn't get much useful results yet):

  Input: weighted undirected graph G = (V,E), $S \subseteq V$, $ s, t \in V$, $ w : E \mapsto R^+$

  Output: A walk W = $(s,v_1, v_2,..,v_k, t)$ of minimum length such that:

  1) $I = \{v_i : i \ge 1 \wedge i \leq k\}$, $S \subseteq I$
  2) $ (s, v_1), (v_k, t) \in E$
  3) $ (v_{i-1}, v_i) \in E$  $\forall i \geq 2,i \leq k$
  4) Length of walk is = $w(s,v_1) + w(v_k,t)$ + $\Sigma_{i=2}^k w(v_{i-1}, v_i)$

I know this is somewhat related to TSP/Hamiltonian paths but I think that it is significantly different.
I came to investigate this problem because I am thinking about solving this problem in a special
geometric setting. So, It would be helpful If I could get to know the complexity class to which it is known to
belong and any results for planar graphs, grid graphs.

Thanks,
Rizwan.

So you are given a weighted undirected graph $G$. You want to find a shortest walk from $s$ to $t$ such that you visit all the vertices of the set $S$. You may choose to visit vertices in $V \setminus S$. You may visit vertices multiple times. You may use the edges multiple times. Let's call this problem $stSWALK$.

  $stSWALK$ is equivalent to metric Traveling Salesman Path problem ($MTSPP$).

It is easy to see that, when $S = V$ then $stSWALK$ is same as $MTSPP$.

You can convert an instance of $stSWALK$ into an instance of $MTSPP$ by simply computing the shortest paths between every pair of vertices in $S$ (and adding the corresponding "new" edges with the weights equal to the lengths of these shortest paths) and then solving $MTSPP$ on the graph induced by $S \cup \{s,t\}$ (lets call this graph $H$). To get a solution to $stSWALK$, we simply expand these newly added edges into their corresponding shortest paths in $G$.

Note that If $G$ is planar then $H$ is not necessarily a planar graph.


Logarithmic advice language in P? Is something like DTIME(poly(n))/log(n) in P? Can the log-length advice be somehow hardwired into a DTM for P?

As pointed in the comments, You cannot do this in general,
However, if you're willing to restrict the class and add some some structure you can achive this. For example, you can use the self-reducibility of SAT to remove the advice, i.e if
$NP\in P/log$ then $NP=P$.

In general, the same is true for complexity classes with self-reducible complete problem, and similar arguments for complexity classes with instance checkers $(EXP,PSPACE,P^{\#P})$ will allow you to remove even larger advices (polynomial) with the difference that now you need to use  probabilistic machines.


Example of an context-sensitive language with a specific number of words of length $n$ Let $s_L(n)$ denote the number of words of length $n$ in $L$.
For context-free languages it is known that $s_L(n)$ is either polynomial or exponential.
For context-sensitive languages this is probably not true and I would like to study counterexamples.
I am interested in an example of a context-sensitive language that has $s_L(n)=\Theta(r^{(n^\delta)})$ for a real $r>1$ and $\delta<1$ or $s_L(n)=\Theta(r^{(log^c(n))})$ for $c>1$.

The language
$$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor n^\delta\rfloor}0^{n-\lfloor n^\delta\rfloor}$$
is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\lfloor n^\delta\rfloor}$.
The language
$$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor(\log n)^c\rfloor}0^{n-\lfloor(\log n)^c\rfloor}$$
is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\lfloor(\log n)^c\rfloor}$.
You can construct any number of examples like this. Basically, if $f\colon\mathbb N\to\mathbb N$ is any function such that given $n$ in binary, $f(n)$ (in binary) is computable in space $O(n)$ (which is exponential space in terms of the length of its input) and $f(n)\le2^n$, then there exist languages $L\in\mathrm{DSPACE}(n)\subseteq\mathrm{CSL}$ such that $s_L(n)=f(n)$, such as
$$L=\bigcup_{n\in\mathbb N}\bigl\{w\in\{0,1\}^n:w<_\mathrm{Lex}\operatorname{bin}(f(n))\bigr\},$$
where $<_\mathrm{Lex}$ denotes lexicographic order, and $\operatorname{bin}(f(n))\in\{0,1\}^n$ is the binary expansion of $f(n)$.


I dreamt of a data structure, does it exist? I haven't managed to find this data structure, but I'm not an expert in the field.

The structure implements a set, and is basically an array of comparable elements with an invariant. The invariant is the following (defined recursively):

An array of length 1 is a merge-array.

An array of length 2^n (for n > 0) is a merge-array iff:

the first half is a merge-array and the second half is empty
or
the first array is full and sorted, and the second half is a merge-array.

Note that if the array is full, it is sorted.

To insert an element, we have two cases:

If the first half is not full, insert recursively in the first half.
If the first half is full, insert recursively in the second half.
After the recursive step, if the whole array is full, merge the
halves (which are sorted), and resize it to the double of its original
length.

To find an element, recurse in both halves, using binary search
when the array is full. (This should be efficient since there are
at most $O(\log(n))$ ascending fragments).

The structure can be thought as a static version of mergesort.

It's not clear what one should do to erase an element.

Edit: after improving my understanding of the structure.

You're describing the classical Bentley-Saxe logarithmic method, applied to static sorted arrays.  The same idea can be used to add support for insertions to any static data structure (no insertions or deletions) for any decomposable searching problem.  (A search problem is decomposable if the answer for any union $A\cup B$ can be computed easily from the answers for the sets $A$ and $B$.)  The transformation increases the amortized query time by a factor of $O(\log n)$ (unless it was already bigger than some polynomial in $n$), but increases the space by only a constant factor.  Yes, it can be deamortized, thanks to Overmars and van Leeuwen, but you really don't want to do that if you don't have to.

These notes cover the basics.

Cache-oblivious lookahead arrays are the mutant offspring of Bentley-Saxe and van Emde Boas trees on steroids.


Reducing #SAT to #MONOTONE-2SAT The problem #MONOTONE-2SAT is known to be #P-complete. This means that #SAT can be reduced to it. My question is: given a #SAT instance $F$, which is the transformation that converts $F$ to its corresponding #MONOTONE-2SAT instance $F'$?

A second question is: let $K'$ be the number of solutions of $F'$, and let $K$ be the number of solutions of $F$. Does $K' = K$? Or we must use a back transformation that converts $K'$ to $K$?

As for the first question, that is what a reduction does.  For how to reduce #3SAT to #Monotone-2SAT, see the proof of #P-completeness of #Monotone-2SAT [Val79b], which is based on the #P-completeness of Permanent [Val79a].  To reduce #SAT to #3SAT, Cook’s reduction from any problem in NP to 3SAT is parsimonious and therefore reduces #SAT to #3SAT.

The answer to the second question is no.  The reduction in [Val79a] from #3SAT to Permanent does not preserve the number of solutions.  Moreover, if a reduction from #SAT to #Monotone-2SAT (or Permanent) which preserves the number of solutions were known, the same reduction would reduce the decision version of SAT to the decision version of Monotone-2SAT (or Bipartite Matching), implying P=NP.

References

[Val79a] Leslie G. Valiant.  The complexity of computing the permanent.  Theoretical Computer Science, 8(2):189–201, 1979.  http://dx.doi.org/10.1016/0304-3975(79)90044-6

[Val79b] Leslie G. Valiant.  The complexity of enumeration and reliability problems.  SIAM Journal on Computing, 8(3):410–421, Aug. 1979.  http://dx.doi.org/10.1137/0208032


String theory based computations I was reading Arora and Barak's book on computational complexity and in the section on 'criticism on Turing machine model and the class P' along with quantum computer it also mentions possibilities of other physical systems for computation such as string theory based computing. Are there any models that use string theory in particular?

No, as far as I know, there are no models that use string theory.

Given that quantum field theories seem to be simulatable in polynomial time by a quantum computer (Jordan, Lee, and Preskill, 2012), the only possible more powerful physical system would be quantum gravity. This is because physicists generally believe that quantum field theory gives an excellent approximate description of the universe if gravity is neglected; however, general relativity seems incompatible with quantum mechanics. Thus, to get a full description of the universe, we need a theory of quantum gravity.  Many physicists believe this theory is given by string theory; however, physicists currently don't understand string theory well enough to use it as a basis for a model of computation.


Shortest Equivalent CNF Formula Let $F_1$ be a satisfiable CNF Formula with $n$ variables and $m$ clauses. Let $S_{F_1}$ be the solution space of $F_1$.

Consider the problem of determining, given $F_1$, another CNF Formula $F_2$ with the same set of variables as $F_1$, with $S_{F_2} = S_{F_1}$ (same solution space as $F_1$), but with as few clauses as possible (the only aim is to minimize the number of clauses, so how many literals each clause may have is not relevant).

  Question

  Did anyone already investigated this problem? Are there any results in the literature concerning it?

As an example, consider the following CNF Formula $F_1$ (each row is a clause):

$x_1 \lor x_2 \lor x_3$
$x_2 \lor x_3 \lor x_4$
$\lnot x_1 \lor x_2 \lor x_4$
$\lnot x_1 \lor x_2 \lor \lnot x_3$
$\lnot x_1 \lor x_3 \lor x_5$
$\lnot x_1 \lor x_2 \lor \lnot x_5$

and the following formula $F_2$:

$x_1 \lor x_2 \lor x_3$
$x_2 \lor x_3 \lor x_4$
$\lnot x_1 \lor x_3 \lor x_5$
$\lnot x_1 \lor x_2$

both have the same solution space, but while $F_1$ has $6$ clauses, $F_2$ only has $4$.

Finally, consider the following formula $F_3$:

$x_2 \lor x_3$
$\lnot x_1 \lor x_3 \lor x_5$
$\lnot x_1 \lor x_2$

The solution space is again the same, but with only $3$ clauses.

The problem of determining whether there is an equivalent CNF formula with at most a given number of literals is $\Pi_2^p$-complete.  The version minimizing the number of clauses is within a factor of $n$ of the formula size, where $n$ is the number of variables.  See section 6 of:

Christopher Umans, The Minimum Equivalent DNF Problem and Shortest Implicants, JCSS 63(4), 597–611, 2001.  doi:10.1006/jcss.2001.1775 (preprint)

A recent result shows that computing a particular lower bound for the size of the shortest equivalent CNF formula (measured by number of clauses, as you specify) is NP-complete.  This paper also states that your problem of minimizing the number of clauses is $\Pi^p_2$-complete as well, citing the Umans paper above, although why this follows is not immediately obvious to me.

Ondřej Čepek, Petr Kučera and Petr Savický, Boolean functions with a simple certificate for CNF complexity, DAM 160(4–5), 365–382, 2012.  doi:10.1016/j.dam.2011.05.013


Complexity of generating a pseudo-Boolean function A pseudo-Boolean function is a mapping from $\mathcal{B}^n = \{0, 1\}^n$ to
$\mathbb{R}$.

Following is a pseudo-Boolean function.

$$s_1 s_4 - s_2 s_3 - s_3 s_5 - s_2 s_5 + s_1 + s_4 - s_1 s_3 - s_1 s_5 - s_3 s_5 +
 s_2 s_4 + s_2 + s_4 - s_1 - s_2 + 3 s_1 s_2$$

Here, $s_i$'s are the Boolean variables taking values from $\{0, 1\}$. It has two solutions for the global minima, $01101$ and $10101$.

I would like to know what is the best known algorithm to generate a pseudo-Boolean function from a given list of solutions.

There's a straightforward way to construct a function $f_z:\{0,1\}^n \to \mathbb{R}$ that is zero at only a single point $z=(z_1,\dots,z_n)$ and strictly positive everywhere else: namely,

$$f_z(x_1,\dots,x_n) = (x_1-z_1)^2 + (x_2-z_2)^2 + \dots + (x_n-z_n)^2.$$

Based on this, we can easily construct a function $g : \{0,1\}^n \to \mathbb{R}$ that is zero at only the points $z[1],\dots,z[k]$ and strictly positive elsewhere: namely,

$$g(x) = f_{z[1]}(x) \cdot f_{z[2]}(x) \cdots f_{z[n]}(x).$$

It follows immediately that the pseudo-Boolean function $g$ has global minima at exactly the points $z[1],\dots,z[k]$ and no others, so it meets all your criteria.  This "algorithm" is simple and efficient.


Finding islands of vertices in a network of roads containing one-way streets I am working on GIS project where we are making use of road maps that may contain one-way streets.

We are writing some debugging tools one of which I want to design to find "Islands".  This would list out all the sets of vertices such that for each pair of vertices A, B in a set you would be able to get from A to B and from B to A.

Here is an example:

A<----------------------> B
\                        /
 \                      /
  \                    /
   \                  /
    \                /
     \              /
      \            /
       \          /
        \        /
         \      /
         v     v
            C

In this case the islands are {c} and {a,b}.

I expect that this reduces to some well-known graph-theory algorithm, but I don't see it.

Does anyone have any pointers for me to do further research or some ideas about a solution?

As Robin says, you want strongly connected components.  They can be easily found using Tarjan's algorithm, Gabow's algorithm, or several others.


Relation between REG and NLOGTIME? What is known about the relation between the class of regular lanuages and NLOGTIME? Is any class contained in another one?

You have some choice of how to define NLOGTIME to get one or both inlcusions; cf., e.g., Regan & Vollmer, Gap-languages and log-time complexity classes, TCS 188 (1997), pp. 101–116.

Parity is a regular language not computable in NLOGTIME, or even in nonuniform AC^0. The set of all strings whose length is a power of 2 is a non-regular language computable in DLOGTIME.


What is the formal definitions of the reduction related to the "call/cc" (call with the current continuation) operator? In lambda calculus or in combinatory logic we formally define reduction/expansion rules for terms (and in their typed variants reductions must preserve the type). Then we can talk about properties of such systems, in particular about the normalization property or confluence.

How could one formally define reductions for the call/cc (call with the current continuation) operator in terms of a rewrite system?

The semantics of the operator allows to abandon the current evaluation context and return to the point where the continuation was captured, effectively allowing the evaluation state to become explicit.

I'd be interested in such a definition that'd allow to formally talk about  confluence of such a system (and showing it doesn't hold, as the behavior of the operator depends on the evaluation order).

The definition is straightforward and can be found e.g. in (1, 2), see also (3). Here is a short summary, using a typed $\lambda$-calculus as basis. Types are not really needed for the presentation of reductions, but clarify the presentation in my opinion.
Let's assume your language is given by
the following grammar.
$$
\newcommand{\PROGRAM}[1]{\mathsf{#1}}
\newcommand{\FV}[1]{\mathsf{fv}(#1)}
\newcommand{\DOM}[1]{\mathsf{dom}(#1)}
\newcommand{\VERTICAL}{\;  \mid\hspace{-3.0pt}\mid \; }
\newcommand{\CALLCC}{\PROGRAM{callcc}}
\newcommand{\CONT}[1]{\mathsf{Cont}(#1)}
\newcommand{\THROW}{\PROGRAM{throw}}
\newcommand{\infer}[2]{\frac{\displaystyle{ #1 }}{\displaystyle{ #2 }}}
\newcommand{\ZEROPREMISERULE}[1]{\infer{-}{#1}}
\newcommand{\FS}{\rightarrow}
\newcommand{\RED}{\rightarrow}
\newcommand{\ONEPREMISERULE}[2]{\infer{#1}{#2}}
\newcommand{\TYPES}[3]{#1 \vdash #2 : #3}
\newcommand{\TWOPREMISERULE}[3]{\infer{#1 \quad #2}{#3}}
   M ::= x \VERTICAL \lambda x.M \VERTICAL MM \VERTICAL ... \VERTICAL \CALLCC \VERTICAL \THROW
$$
Here $\CALLCC$ and $\THROW$ are seen as constants although we could also have defined them in different ways.
Let us denote by $\FV{M}$ the free variables of the program $M$.
Types could be something like this:
$$
        \alpha\
                ::=\
        \alpha \FS\alpha
\VERTICAL \PROGRAM{Int} \VERTICAL
        ...
                \VERTICAL
        \CONT{\alpha}
$$
Here $\CONT{\alpha}$ is the type of continuations with final answer
type $\alpha$.
The constants $\CALLCC$ and $\THROW$ are values and have the following types.
$$
        \ZEROPREMISERULE
        {
          \TYPES{\Gamma}{\CALLCC}{(\CONT{\alpha} \FS \alpha) \FS \alpha}
        }
                \qquad
        \ZEROPREMISERULE
 {
                \TYPES{\Gamma}{\THROW}{\CONT{\alpha} \FS \alpha \FS \beta}
        }
$$
Depending on your use-case, the type variables may be quantified.
Reductions are defined with the help of configurations.
A configuration is a pair $(M, \sigma)$ such that $M$ is a
program and $\sigma$, the continuation map, ranged over by
$\sigma, ...$, maps each $k \in \FV{M}$ of type $\CONT{\alpha}$ to an appropriately typed program.
Then
reductions are of the form $(M, \sigma) \RED (N,
\sigma')$. For  call-by-value, the reductions are generated as usual, with the following additions for $\CALLCC$
and $\THROW$.
$$
        \ONEPREMISERULE
        {
                k, x\ \text{fresh}
        }
        {
                (E[\CALLCC\ V], \sigma) \RED (E[V\;k], \sigma \cdot k \mapsto \lambda x.E[x])
        }
                \quad
        \ONEPREMISERULE
        {
                \sigma(k) = M
        }
        {
                (E[\THROW\ k\ V], \sigma) \RED (MV, \sigma)
        }
$$
Here $V$ over ranges over values, and
$E[\cdot]$ over the usual call-by-value reduction contexts. The two new constants give rise to the following evaluation contexts: $\CALLCC\ E[\cdot]$, $\THROW\ E[\cdot]\ M$
and $\THROW\ V\ E[\cdot]$.

Note that (1) does not use continuation maps to define the CBV semantics of $\CALLCC$
 and $\THROW$. Instead a run-time value is introoduced. The two approaches are equivalent.

As to evaluation order, $\CALLCC$ enriches the power of contexts and can distinguish  programs by application that are
  indistinguishable in the absence of continuations:

$$
  \newcommand{\ARGFC}{\PROGRAM{argfc}}
  \ARGFC  = \CALLCC\ \lambda k.(\THROW\ {k}\ {\lambda
  x.(\THROW\ {k}\ {\lambda y.x}}))
  $$

This is the classic example of calling a function once, but
  returning twice. e.g. in
  $$
  (\lambda x.(x\; 1);(x\; 2))\ \ARGFC = 1
  $$
  and
  $$
  (\lambda x.\lambda y.(x\; 1);(y\; 2))\ \ARGFC\ \ARGFC = 2
  $$

with $M;N$ being the sequential composition of $M$ and $N$, binding
more tightly than $\lambda$-abstraction.  The reason is that
continuations carry information about contexts that may be returned
(jumped) to later.

J. G. Riecke, H. Thielecke, Typed Exceptions and Continuations Cannot Macro-Express Each Other (Postscript file).
R. Harper, B. F. Duba, D. MacQueen, Typing First-Class Continuations in ML.
H. Thielecke, Continuations, functions and jumps.


Testing boolean vectors orthogonality with fast query-time Consider the following problems,

Problem1:
INPUT: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$
TASK: preprocess INPUT in such a way that the following queries can be solved as fast as possible: given a query vector $x\in\{0,1\}^d$, find every $s\in S$ that is orthogonal (or non orthogonal, by complementarity) to $x$.

Problem2:
INPUT: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$
TASK: preprocess INPUT in such a way that the following queries can be solved as fast as possible: given a query vector $x\in\{0,1\}^d$, decide whether $S$ contains a vector orthogonal to $x$.

I'm in deep search of fast methods, i.e. faster than naive inspection! Also complexity lower bounds, or any other known reference ...

In particular, I was wondering whether we can adapt range searching techniques (I'm thinking about kd-trees or similar partitioning trees) to the problems above ...

Also, I wonder whether Random Projection or (Jaccard index, angle, cosine based) Similarity Search methods might provide good speed-up ...

The "offline" version of this question is addressed in my SODA 2014 paper with Huacheng Yu, Finding orthogonal vectors in discrete structures. For the case of $\mathbb F_2$, we give an $O(nd)$ time algorithm for determining, given two sets of $n$ vectors $A$ and $B$, whether there is a vector in $A$ and vector in $B$ with zero inner product.

I'm sure you can modify our algorithm appropriately, and get an interesting preprocessing/query version; we did not consider this question.


If P = NP were true, would quantum computers be useful? Suppose that P = NP is true.  Would there then be any practical application to building a quantum computer such as solving certain problems faster, or would any such improvement be irrelevant based on the fact that P = NP is true?  How would you characterize the improvement in efficiency that would come about if a quantum computer could be built in a world where P = NP, as opposed to a world in which P != NP?

Here's a made-up example of about what I'm looking for:

  If P != NP, we see that complexity class ABC is equal to quantum complexity class XYZ...but if P = NP, class ABC collapses to related class UVW anyway.

(Motivation:  I am curious about this, and relatively new to quantum computing; please migrate this question if it is insufficiently advanced.)

The paper "BQP and the Polynomial Hierarchy" by Scott Aaronson directly addresses your question. If P=NP, then PH would collapse. If furthermore BQP were in PH, then no quantum speed-up would be possible in that case. On the other hand, Aaronson gives evidence for a problem with quantum speedup outside PH, thus such a speed-up would survive a collapse of PH.


Pseudorandom generator for finite automata Let $d$ be a constant. How can we provably construct a pseudorandom generator that fools $d$-state finite automata?

Here, a $d$-state finite automata has $d$ nodes, a start node, a set of nodes representing accept states, and two directed edges labeled 0, 1 coming out of each node. It changes state in the natural way as it reads input. Given an $\epsilon$, find $f:\{0,1\}^{k}\to \{0,1\}^n$ such that for every $d$-state finite automaton computing some function $A$,

$$|\mathbb P_{x\sim U_{k}}(A(f(x))=1)-\mathbb P_{x\sim U_n}(A(x)=1)|< \epsilon.$$

Here $U_k$ denotes the uniform distribution on $k$ variables, and we want $k$ to be as small as possible (e.g. $\log n$). I'm thinking of $d$ being on the order of $n$, though we can also ask the question more generally (ex. would the number of bits required grow with $n$?).

Some background

Construction of pseudorandom generators is important in derandomization, but the general problem (PRG's for polynomial-time algorithms) has so far proved too difficult. There has however been progress on PRG's for bounded-space computation. For example this recent paper (http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf) gives a bound of approximately $\log n\log d$ for regular read-once branching programs. The question with general read-once branching programs is still open (with $k=\log n$), so I'm wondering if the answer for this simplification is known.  (A finite automaton is like a read-once branching program where every layer is the same.)

If $d$ is of the order of $n$ then you can write a constant-width branching program as a finite-state automaton, and logarithmic seed length is not known.

But if $d$ is very small, say a constant, then you can do better and achieve logarithmic seed length -- I think, this is something I thought about years ago but never wrote down.  The trick is to use Nisan's result RL $\subseteq$ SC.  Basically, he shows that if you are given a branching program then you can find a logarithmic-seed distribution that fools it.  His result extends to a small number of branching programs.  So if $d$ is a constant then you can enumerate over all possible finite-state automata, and find a distribution that fools all of them.  This should still work as long as the number of programs is polynomial in $n$.


Approximating Bipartite Vertex Cover Is there any result on approximating a minimum (weighted) bipartite vertex cover? I'm interested in the problem that given a bipartite graph ( probably with weight on its vertex ), find a vertex cover of size (or weight) at most ($1+\epsilon$) of the optimal value. I've been searching on internet and although it seems the problem was quite simple, there's no paper or lecture notes about it. (maybe because everybody know :)).

Can anyone give a link to related work if you know any :D

thanks

No need to approximate, we can determine the exact value: see Kőnig's theorem. In particular, this section shows how to use any maximum bipartite matching algorithm to find a minimum vertex cover.


Correctness of AKS algorithm for shortest vector problem Short question

In the end of section 1 of Regev's notes about the AKS algorithm for SVP, why is the following true?

  for each such $i$,$y_i− x_i$ remains $w$ with probability $1/2$ or otherwise becomes one of $w+v$ or $w−v$.

Extended question

AKS finds a shortest non-zero vector of any $n$-dimensional Euclidean lattice $\Lambda$ in time $2^{O(n)}$.

Actually, it is a randomized algorithm and the output is correct with very high probability, say $1 - 2^{\Omega(n)}$.

Although the intuition about why the output is correct with high probability is simple, the proof is rather technical and it basically goes like this:

The algorithm samples a set of vectors $x_1, ..., x_N$ in the beginning. To each of those vectors, one lattice point is associated (the number of lattice points is much smaller than $N$, so a lot of $x_i$ maps to same lattice point). To prove that the algorithm works (with overwhelming probability) you substitute the sampling method so that if $x_i$ is in a specific region $C_1$, then it is replaced by $x_i + v$, if it it lies in another specific (symmetric) region $C_2$, then it is replaced by $x_i - v$, or it continues to be $x_i$ otherwise, where $v$ is a shortest vector.

Then, the goal is to show that for at least one pair of vectors $x_i$ and $x_j$ that map to a same $w \in \Lambda$, we have $x_i \in C_1 \cup C_2$ and $x_j \not \in C_1 \cup C_2$, so that the difference of the associated lattice points become $(w \pm v)  - w = \pm v$, which is a shortest vector.

But I don't understand the analysis of the probabilities involved in this step. Since the vectors $x_i$ considered in the end of section 1 of Regev's notes are all points in $C_1 \cup C_2$, all of them should be "flipped" around $v$, then $w$ would never remain $w$.

What you seem to be missing is that $\tau$ is not applied to all "green" vectors. Instead, think of every point $x_i$ as having a coin attached to it. Before you use $x_i$ in the algorithm, you toss the coin to decide whether to keep $x_i$ as $x_i$ or to replace it by $\tau(x_i)$. This is done independently for each $x_i$, so, with very high probability, the fraction of green vectors that $\tau$ is applied to will be very close to $\frac12$.

I have always found this analysis mysterious, but let me try to give some intuition. I think the analysis tries to exploit the fact that the sieving step only uses $y_i$, and $y_i$ does not distinguish between $x_i$ and $x_i\pm v$ for any lattice vector $v$. Since the sieving step does not need this information, you can think of the analysis as "hiding" from the algorithm which point in the pair $\{x_i, \tau(x_i)\}$ was actually sampled, until the algorithm absolutely must know this information. This is sometimes called the principle of deferred decisions. With this trick, you can argue that there are many possible random choices that would've led to the same set of points surviving to step 3 of the algorithm, and then you argue that at step 3 many of these random choices lead to a correct output. On the other hand, if you applied $\tau$ to every point, then you wouldn't "hide" anything from the algorithm, i.e. you wouldn't be taking advantage of the fact that there is randomness that's not used by the sieving step 2, and is "free" to be used at step 3.


Merging lists of fragile objects Background: Chao Xu posted the following question some time ago: "Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times?". It seems that we are a bit stuck with the problem; I have discussed the same problem with Valentin Polishchuk in 2009, and we got nowhere.

To get some fresh ideas, I tried to come up with the simplest possible question that has a similar flavour and is not completely trivial. Hence the following question.

Question: You are given two sorted lists, each of them with $n$ elements. Can you merge the lists so that each element is only compared $O(1)$ times?

Naturally, the output should be a sorted list that contains all $2n$ elements.

[This turned out to be trivial, the answer is "no".]

Question 2: You are given two sorted lists, each of them with $n$ elements. Can you merge the lists so that each element is only compared $O(1)$ times, if you are allowed to discard a small fraction of elements?

More precisely, the output should be a sorted list that contains $2n-T(n)$ elements, and a "trashcan" that contains $T(n)$ elements. How small can you make the value $T(n)$? Getting $T(n) = n$ is trivial. Something like $T(n) = n/100$ should be doable in a straightforward manner. But can you get $T(n) = o(n)$?

Notes:

We use the comparison model here. Deterministic algorithms only, we are interested in the worst-case guarantees.
Note that both lists have exactly $n$ elements. If we had one list with $n$ elements and another with $1$ element, the answer is clearly "no"; however, if both lists are long, it seems that one might be able to do some "load balancing".
This time any kind of algorithm is valid. If your algorithm uses sorting networks as a building block, it is perfectly fine.
For a starting point, here is a simple algorithm that compares each element for at most 200 times: Just use the standard merge algorithm, but maintain counters for the heads of the lists. Once you reach 200, discard the element. Now for each element that you discard, you have successfully placed 200 elements in your output array. Hence you have achieved $T(n) = n/100$.

No, such an algorithm cannot exist.

Assume $t$ comparisons per element are allowed.

For a start, consider the situation of merging two lists, one of size
one, and the other of size $2^t$.
There are $2^t+1$ possible results, and an easy adversarial argument
shows that the element in the small list needs to participate in $t+1$ comparisons,
and this element has to go to the trash.

From this it is easy to construct an instance with two lists of size $n$
that consists of $n/2^t$ such small situations, and hence $n/2^t$ elements
have to go to the trash.

Hence, as long as $t$ is constant, it is impossible to have a trash of
$o(n)$.

On a side note, it seems that it is possible to match this bound by an algorithm where every element is compared with roughly log of the size of the surrounding part of the other list.  If this is of interest, I will try to work out the details.


Differences with Penalty Given a sequence $a_1,\ldots,a_n$, find a $k$ and numbers $1\leq i_1< \dots< i_{2k}\leq n$ that maximizes $(\sum_{j=1}^{k}(a_{i_{2j}}-a_{i_{2j-1}}))-2k$. I can get an $n^3$ algorithm using dynamic programming. Is there a better algorithm?

Here is an attempt at an $n^2$ DP-based algorithm:
Compute $M(\ell)$, the maximum such sum that uses only $a_1,\ldots,a_\ell$ (but it is not required that $a_\ell$ is used!). To compute $M(\ell)$ you have to take into account: (1) $M(\ell-1)$ and (2) all combinations of using $M(i-1)$, for some $i<\ell$, and picking $a_i$ and $a_\ell$, on top of it. This looks like a linear outer loop with a linear inner loop. The penalty does not seem to hurt: just add $a_\ell-a_i-2$ in the latter case. A non-linear penalty would be a different story.


Deciding functionality of transducers over infinite words Given a finite state transducer defining a rational relation over infinite words, it is known to be decidable whether or not the relation is a function, i.e. whether each infinite input word is related to at most one infinite output word. This is detailed in a paper by Gire: Two Decidability Problems for Infinite Words. Unfortunately, I cannot find the full text of the paper anywhere. The basic idea seems to be to form the composition of the transducer with its inverse $T \circ T^{-1}$ and check if the resulting transducer is a restriction of the identity function. Note that the inverse of a transducer $T$ is $T$ with input and output word swapped for each transition.

I am looking for details of the decision procedure. Do you have any references or a short description of the algorithm?

Françoise Gire actually gives two proofs of her result.

The first proof (I am quoting her paper now) uses a construction similar to the one used in [3] to prove the decidability of the $\omega$-equivalence of two functional finite transducers.

The second proof makes use of the technique you are describing in your question: $T$ is functional if and only if $T \circ T^{-1}$ is a restriction of the identity. The property for an infinitary rational relation of being a restriction of the identity is proved to be decidable in [3,4].

[3] K. Culik and J. Pachl, Equivalence problems for mappings on infinite strings, Inform. and Control 49 (1981) 52-63.

[4] K. Culik, Some decidable results about regular and pushdown translations, Inform. Process. Lett. 8 (1979) 5-8.


Cryptography with very small keys Is anything known about doing cryptography with very small keys?  In particular, is there any theory involving cryptosystems (based on whatever assumption you want) that can encrypt messages of length $n$ with key sizes $s = o(n^{\epsilon})$ for all $\epsilon>0$? (Assume $s$ is still large
enough that one cannot brute-force search through the space of keys.)

If there is no theory, are there real-world cryptosystems that would still "behave" with such small keys and for which much better than brute-force attacks are not known?

Short version: You want a crypto system that, with keys of length $k$, is secure against attackers with running time $2^{k^\epsilon}$, or even $2^{\Omega(k)}$. Most schemes that anyone would want to use in practice are conjectured to satisfy such bounds. Of course, we can't prove that they satisfy bounds like that without, at the very least, separating P from NP.

Longer version:
"Concrete security" provides the kind of theory I think you are looking for, since it foregoes coarse categorizations (polynomial versus not) in favor of specific bounds.

For example, you can define a public-key cryptosystem to be $(t,\epsilon)$ secure if no attacker running in time $t$ has probability more than $1/2 + \epsilon$ of winning a chosen-plaintext indistinguishability game. Because the running time includes calls to the underlying encryption schemes, this provides security for messages of length roughly $t$. If you want to be even more precise, you can track running time ($t$) and queries to cryptosystem ($q$) separately. Under sufficiently strong assumptions about the primitives (e.g. exponentially hard to invert one-way permutations), one can construct cryptosystems that are $(t,\epsilon)$-secure for very large $t,q$ (close-ish to $2^{key\ length}$) and very small $\epsilon$.

These types of bounds are used a lot in research papers (especially in the symmetric-key world). They appear less often in lecture notes and textbooks, because they introduce extra bookkeeping and can tax the notation-absorption skills of students.

Luca Trevisan's lecture notes on crypto, though, use this notation; they might be a good resource to start with.


Best Sorting for unlimited integer range Is there a better than time $O(n\log n)$ and space $O(n)$ deterministic algorithm in the RAM model to sort $n$ positive integers whose range is unbounded?

How about randomized?

Yes there is.

The best known deterministic algorithm in linear space runs in time within $O(n\lg\lg n)$ and was presented by Han in 2004.
The best known randomized algorithm in linear space runs in time within $O(n\sqrt{\lg\lg n})$ and was presented by Han and Thorup in 2012.

For more details, see the section on "Trans-dichotomous algorithms" from the wikipedia page for "Integer Sorting".


What is the minimum size of a circuit that computes PARITY? It is a classic result that every fan-in 2 AND-OR-NOT circuit that computes PARITY from the input variables has size at least $3(n-1)$ and this is sharp.
(We define size as the number of AND and OR gates.)
The proof is by gate-elimination and it seems to fail if we allow arbitrary fan-in.
What is known for this case?

Specifically, does anyone know an example when larger fan-in helps, i.e., we need less than $3(n-1)$ gates?

Update Oct 18. Marzio has shown that for $n=3$ even $5$ gates suffice using the CNF form of PARITY. This implies a bound of $\lfloor \frac 52 n \rfloor-2$ for general $n$. Can YOU do better?

This gate-elimination lower bound does not match Marzio’s upper bound, but it’s a start.

  Proposition: Every unbounded fan-in AND/OR/NOT circuit computing parity on $n\ge2$ variables contains at least $2n-1$ AND and OR gates.

For convenience, I will use a model where the only gates are AND-gates, but we allow negation wires. It is easy to see that $3$ gates are necessary for $n=2$, hence it is enough to show that if $C$ is a minimal-size circuit computing parity on $n>2$ variables, we can find a restriction of one variable which kills at least two gates.

If some variable $x_i$ has at least two positive parents (i.e., it is connected by unnegated wires to two different gates), setting this variable to $0$ will kill the parents and we are done; likewise if it has two negative parents. We may thus assume that each variable has at most one positive and at most one negative parent.

Let $a$ be a bottom-level gate in the circuit. Without loss of generality, $a=x_1\land x_2\land\cdots$. Set $x_1=0$, which forces $a=0$ and kills it. The restricted circuit $C'$ still computes parity, in particular it depends on $x_2$, hence $x_2$ has a negative parent $b=\neg x_2\land c_1\land\dots\land c_r$. Notice that in $C'$, no $c_j$ depends on $x_2$. If there were an assignment to $x_3,\dots,x_n$ which (on top of $x_1=0$) makes some $c_j$ false, the circuit restricted by this assignment would be constant, contradicting the fact that it computes $x_2$ or $\neg x_2$. Thus, in $C'$, all the $c_j$ compute constant $1$, and $b$ computes $\neg x_2$, hence we can eliminate it along with $a$.

EDIT: As I learned from Yuri Kombarov’s paper, this $2n-1$ lower bound, as well as the $\lfloor\frac52n\rfloor-2$ upper bound implied by Marzio De Biasi’s answer, were originally proved in

[1] Ingo Wegener, The complexity of the parity function in unbounded fan-in, unbounded depth circuits, Theoretical Computer Science 85 (1991), no. 1, pp. 155–170. http://dx.doi.org/10.1016/0304-3975(91)90052-4


How to treat dynamic memory allocation in algorithm analysis? I have an algorithm in which I want to dynamically allocate some memory.
Let's say that I have N numbers and that I want to describe some binary relation over them. To do so I want to create a N*N matrix. But how fast is the memory allocation itself regarding N?

I do not want to zero out the new memory. In fact I do not want to touch it at all in this moment - I just want to allocate it and be sure that all of it is there.

I understand that the answer is: how is the memory allocation implemented?
Bit I hope that you can give me some upper bounds that are common for most of the popular memory management strategies.

You want to read

Wilson et al., Dynamic Storage Allocation: A Survey and Critical Review, 1995

and references therein, especially those to papers by Robson. Here is a quote that answers your question:

  Robson put [in 1974] a fairly tight upper and lower bounds on the
  worst-case performance of the best possible allocation algorithm. He
  showed that a worst-case-optimal strategy's worst-case memory usage
  was somewhere between $0.5M\log_2 n$ and about $0.84 M\log_2 n$.

Here, $M$ is the live memory, and $n$ is the ratio of the largest to the smallest block.

(So, if your algorithm allocates blocks of wildly different sizes, then you may want to think more carefully about how memory allocation works. This doesn't seem to be the case for the example given in the question.)

PS: I was searching for a link to Robson's article and I found this related CSTheory question: Data structure for dynamic memory allocation


Complexity of Smoothed $\ell_0$ algorithm I wanted to compute the complexity of a smoothed $\ell_0$ algorithm in BigO notation. The algorithm can be found here. Can anybody help me in this regard?

There appear to be two user-introduced parameters $K,L$ in the algorithm you point to. Apart from that, the main task appears to be the computation of a pseudoinverse, and matrix multiplication. Without any further knowledge of the structure of the $n\times n$ matrix $A$, it would appear that the running time is $O(KL g(n))$, where $g(n)$ is your best estimate for computing the inverse and doing the multiplication.

Crudely, both of these can be bounded by $cn^3$, but there might be better answers based on your actual setting (if A is sparse, or if you use Strassen's matrix multiplication, and so on)


quasiP-Natural Property again SIZE($n^e$) for fixed e. The Natural Proof theorem says :

If for a fixed $c>1$ $G_k \in SIZE(k^c)$ is $2^{k^\epsilon}$-hard then not exists a $quasiP$-Natural Property that for all $e$ sufficently large is usefull against $SIZE(n^e)$.

The idea in the proof is that if you can distinguish a random function from a function in $SIZE(n^e)$ you can invert a pseudorandom generator. $SIZE(n^e)$ is big enough to compute pseudorandom function generator (based on the pseudorandom string generator $G_k$)

can we say that?

If for any k,n (where if we fix n then we can choose any $k=n^{O(1)}$) $G:\{0,1\}^k\times \{0,1\}^n \rightarrow \{0,1\}$ is a pseudorandom functions genereator (for a sub-exponential adversaries) computable in $SIZE(n^e)$ then not exists a $quasiP$-Natural Property usefull against $SIZE(n^e)$.

I think that it's wrong, because for any fixed $e$ you can find a $quasiP$-Natural Property against $SIZE(n^e)$. But I can't see why

If $G: \{0,1\}^k \rightarrow \{0,1\}^{2k}$ is a polynomial time computable pseudorandom generator with security $t(k)$, that is such that every adversary running in time $\leq t(k)$ has distinguishing probability $\leq 1/t(k)$, then we can construct a family of functions $f: \{0,1\}^n \rightarrow \{0,1\}$ such that each function is computable by circuit of size $k(n)^c$, where $c$ is an absolute constant, but the truth-table of a random function from the family is indistinguishable from the truth-table of a truly random function by properties computable in time roughly $t(k(n))$, where we are free to choose $k(n)$ any way we want. Such a family of function contradicts the existence of a natural property computable in time $t(k(n))$ and useful against circuits of size $k(n)^c$.

Now it is a matter to instantiate the parameters. If we believe that there are one-way functions secure against sub-exponential adversaries, then we can take $t(k) = 2^{k^{\epsilon}}$ for an absolute constant $\epsilon >0$. If there were a quasi-polytime natural property that is useful against size($n^e$) for every $e$, then we can take $k(n)= n^{e}$ for every $e$, and the property would still be able to distinguish  our family of functions computed by circuits of size $n^{ce}$ from truly random functions, even though no property computable in time $\leq t(k(n)) = 2^{n^{\epsilon e}}$ can do that. This quasi-polytime computable property is computable in time $\leq 2^{n^d}$ for some absolute constant $d$, and we reach a contradiction when $e > d/\epsilon$. (Recall that $d,\epsilon$ are absolute constants and that we can take $e$ as large as we want.)

The point here is the order of quantifiers. If you are looking for a specific polynomial circuit size, like $n^{10}$, you can have a quasi-polytime natural property that is useful against those circuits, because you can actually explicitly check in time roughly $2^{n^{10}}$ if a given function is computable by a circuit of size $n^{10}$. If, however, you want a quasy-polytime natural property that is simultaneously useful against all circuit sizes $n^e$ for all $e$ (that is, for each $e$, the property becomes useful after a sufficiently large $n$), then you are impyling the existence of sub-exponential distinguishers for pseduroandom generators and sub-exponential inverters for one-way functions.


Well known classes of boolean formulas that require exponentially long resolution proofs You might often find cutting plane methods, variable propagation, branch and bound, clause learning, intelligent backtracking or even handwoven human heuristics in SAT solvers. Yet for decades the best SAT solvers have relied heavily on resolution proof techniques and use a combination of other things simply for aid and to direct resolution-style search. Obviously, it's suspected that ANY algorithm will fail to decide the satisfiability question in polynomial time in at least some cases.

In 1985, Haken proved in his paper "The intractability of resolution" that the pigeon hole principle encoded in CNF does not admit polynomial sized resolution proofs. While this does prove something about the intractability of resolution-based algorithms, it also gives criteria by which cutting edge solvers can be judged - and in fact one of the many considerations that goes into designing a SAT solver today is how it is likely to perform on known 'hard' cases.

Having a list of classes of Boolean formulas that provably admit exponentially sized resolution proofs is useful in the sense it gives 'hard' formulas to test new SAT solvers against. What work has been done in compiling such classes together? Does anyone have a reference containing such a list and their relevant proofs? Please list one class of Boolean formula per answer.

Hard instances for resolution:

Tseitin's formulas (over expander graphs).
Weak ($ m $ to $ n$) pigeonhole principle (exponential in $n$ lower bounds, for any $ m>n $).
Random 3CNF's with $ n $ variables and $ O(n^{1.5-\epsilon})$ clauses, for $ 0<\epsilon<1/2 $.

Good, relatively up-to-date, technical survey for proof complexity lower bounds, see:

Nathan Segerlind: The Complexity of Propositional Proofs. Bulletin of Symbolic Logic 13(4): 417-481 (2007) available at: http://www.math.ucla.edu/~asl/bsl/1304/1304-001.ps


Communication complexity of approximating the size of set intersection Consider the set-intersection problem: Alice and Bob each get a subset of $\left\{ 1,\ldots, n\right\}$, and they would like to know whether their sets intersect. This is a canonical problem of communication complexity, and it is well-known that randomized protocols for this problem require $\Theta(n)$ bits of communication (see survey here). In the case where the sets are of size $k$ for $k \ll n$, it is known that randomized protocols require $\Theta(k)$ bits (see here).

Consider now the variant in which Alice and Bob want to know the size of the intersection of their sets. Clearly, computing the exact size reduces to the standard set-intersection problem, and this holds even if they only want to compute a multiplicative approximation of the size. However, what happens if they want to compute an additive approximation of the size of the intersection? Is there any lower bound or upper bound known about this problem?

I am particularly interested in this question in the setting of small sets, i.e., the case where the sets are of size $k \ll n$.

I will give two upper bounds. Let $A$ and $B$ be the sets given to Alice and Bob, respectively, and put $a=|A|$, $b=|B|$, $c=|A\cap B|$.

First, there is a randomized protocol that, given $d>0$ and $\epsilon>0$, computes with probability $\ge1-\epsilon$ an approximation of $c$ up to additive error $d$, using $O\Bigl(\left(\frac{\min\{a,b\}}d\right)^2\log n\log\epsilon^{-1}\Bigr)$ bits of communication, and $O\Bigl(\left(\frac{\min\{a,b\}}d\right)^2\log \min\{a,b\}\log\epsilon^{-1}\Bigr)$ bits of randomness.

The protocol goes as follows:

If $d\ge\min\{a,b\}$, the party who sees it terminates the protocol and outputs $0$ as the estimate. Otherwise, Alice and Bob communicate $a$ and $b$ to each other, and determine which is smaller. I will assume below w.l.o.g. that $a\le b$.
Alice draws $t=\log(2\epsilon^{-1})a^2/(2d^2)$ independent uniformly random samples $a_i\in A$, $i<t$, and sends them to Bob.
Bob estimates $c$ as $\frac at|\{i<t:a_i\in B\}|$.

The protocol is correct by the Chernoff–Hoeffding bounds: if $X_i$ denotes the indicator random variable of the event $a_i\in B$, then $X_i$, $i<t$, are i.i.d. variables with mean $p=c/a$. Thus,
$$\Pr\left[a\overline X\le c-d\right]=\Pr\left[\overline X\le p-\tfrac da\right]\le\exp\left(-2\left(\tfrac da\right)^2t\right)\le\frac\epsilon2,$$
and similarly for $\Pr\bigl[a\overline X\ge c+d\bigr]$.

Now, these bounds are somewhat wasteful if $c\ll a$: there are also variant Chernoff bounds stating
$$\begin{align}
\Pr\left[\overline X\le p-\delta\right]&\le\exp\left(-\frac{\delta^2}{2p}t\right),\\
\Pr\left[\overline X\ge p+\delta\right]&\le\exp\left(-\frac{\delta^2}{3p}t\right),\qquad\delta\le p,
\end{align}$$
which would allow us to get by with the number of samples $t$ smaller by a factor of roughly $p$. The problem is that $p=c/a$ is the very quantity we want to approximate, hence we do not know it ahead. This can be remedied by making first a ball-park estimate of $c$.

So, the improved protocol computes with probability $\ge1-\epsilon$ an additive $d$-approximation of $c$ using $O\Bigl(\frac{\min\{a,b\}}d\left(1+\frac cd\right)\log n\log\epsilon^{-1}\Bigr)$ bits of communication, and $O\Bigl(\frac{\min\{a,b\}}d\left(1+\frac cd\right)\log \min\{a,b\}\log\epsilon^{-1}\Bigr)$ bits of randomness, and it goes as follows (the constants are not optimized):

Same as above.
Alice draws $r=10(\log\epsilon^{-1})a/d$ random samples from $A$, and sends them to Bob.
Bob counts how many of these samples belong to $B$, and sends this number, $s$, to Alice.
If $as/r\le d/2$, the protocol terminates with output $0$.
Alice draws $t=10sa/d$ random samples $a_i\in A$, $i<t$, and sends them to Bob.
Bob estimates $c$ as $\frac at|\{i<t:a_i\in B\}|$.

Without going into the details, the Chernoff bounds quoted above imply that with high probability, the value of $s/r$ is $\Theta(c/a)$, in which case the protocol does not exceed the stated cost, and it computes with high probability a good estimate of $c$ by another application of Chernoff bounds.


On partitioning a collection into equivalence classes Suppose I have a collection $A$ that I want to partition into equivalence classes, according to some equivalence predicate $E$.

The naive algorithm for doing this is essentially recursive.  It consists of picking an arbitrary item $x$ of $A$, using it to "seed" its equivalence class $[x]$, and filling $[x]$ out by iterating over the remaining items $y$ of $A$, adding $y$ to $[x]$ iff $E(x, y)$ is true.  Then this base procedure is repeated recursively on the subcollection $A^\prime$ of $A$ consisting of all the items of $A$ that were not assigned to $[x]$.

I would like to know

the technical name for this generic problem; and
whether it is possible to do better performance-wise than the naive algorithm described above.

See the paper

Varunkumar Jayapaul, J. Ian Munro, Venkatesh Raman, Srinivasa Rao Satti (2015), "Sorting and Selection with Equality Comparisons",
Proc. WADS 2015, LNCS 9214, pp. 434–445, doi:10.1007/978-3-319-21840-3_36

It is exactly about the problem you ask, finding the equivalence classes of an equivalence relation by querying the equivalences of pairs of elements. For an input with $n$ elements and $c$ equivalence classes, the naive algorithm you describe will take time $O(nc)$, but they give a more precise bound for this same algorithm in terms of the sizes of its equivalence classes (Theorem 3) and similarly analyze another algorithm for the same problem that works better when the equivalence classes have unevenly distributed sizes (Theorem 4).


Algorithmic distinctions between random and pseudorandom. Given a specific pseudo random number generator (e.g. Mersenne twister) $r()$ and a true random number generator $q()$ is there an algorithm $f(x,y)$ such that:

$f(r(),r()) = 1$ almost always.
$f(q(),q()) = 0$ almost always.

It should be noted that $f()$ stores no state, it only takes the return values of two consecutive calls as its parameter: we can also consider the case of a vector of $n$ calls as input.

"almost always" may be interpreted quite liberally, it could return this result with $> 2/3$ probability or the long term average could tend towards this limit.

I would also appreciate any insight on the same question for an unknown pseudo-random number generator (i.e. an arbitrary Turing machine) as $r()$. Thanks very much!

If you just consider consecutive samples then, for most kinds of PRNGs the answer is that you can't distinguish them from true RNGs.

If you consider large input samples, then, in principle (if you don't take complexity issues into account), you can always distinguish a PRNG from true randomness:

For each PRNG $r$, seed length $L$ and starting point $x$ there exist a sample sequence length $k$ such that $f([r(seed, x),\ r(seed, x+1),\ \dots,\  r(seed, x+k-1)])\ =\ 1$ with certainty, and $f(\dots)\ =\ 0$ for any other sequence,
where $r(seed, n)$ is the n-th sample generated by the PRNG initialized with $seed$.

If the PRNG has finitely many states, as it is the case with all the PRNGs commonly in use, then the sample sequence length $k$ is independent of the seed length and starting point.

The distinguishing algorithm $f(\cdot,\ \cdot)$ can be just a brute-force search that tries in order all possible initial states to check whether they produce the sample sequence. Of course, for large state spaces, this is unpractical.
Moreover, the output sequence of a finite-state PRNG is periodic or eventually becomes periodic, although the period can be very large.

The design goal of cryptographically-secure PRNGs is to ensure that no method substantially faster than brute-force search can be used to distinguish them from true RNGs. Currently, various PRNGs are believed to be cryptographically-secure, though no mathematical proof exists.

Cryptographically-insecure PRNGs like the Mersenne Twister can be easily distinguished from true RNGs by observing a relatively short sample sequence.


Do there exist two equivalent objective functions one of which can be approximated but another one cannot? I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below are the definitions.
Problem A: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$ each of which is not greater than the corresponding weight (i.e., $0<v_h\leq w_h$ ($1 \leq h \leq i$)), and a bag with capacity $B=\sum_h v_h$, we want to insert items into the bag without exceeding the capacity $B$ while maximising the total values (i.e., maximising $\sum_{h=1}^i p_h*v_h$ subject to (1) $p_h=0$ or 1, (2) $\sum_{h=1}^i p_h*w_h \leq B$ ).
Problem B: we have the same inputs and constraints as A. The objective function is different which is minimizing $B-\sum_{h=1}^i p_h*v_h$.
Approximation ratio analysis: Suppose $X$ is the value returned by an approximate algorithm for Problem A, $OPT$ is the optimal value. Then for problem A, the ratio is $\alpha \leq X/OPT$. If the algorithm is greedy algorithm, $\alpha$ is $1/2$. On the other hand, for problem B, the ratio is $(B-X)/(B-OPT)$ which can be infinity large when $OPT$ is close to $B$.
So my question is: (1) can we use approximate algorithms in problem A to solve problem B with approximation ratios? (2) Even if we have specialised algorithms for problem B, the denominator $(B-OPT)$ still can be very small. Can we find approximate solutions for problem B?

The answer to Question (1) is no.  The answer to Question (2) is yes.  Here are the details.
I'll work with the following equivalent problem formulations.  For the input, we are given $n$ pairs of values $(v_1, w_1), (v_2, w_2), \ldots, (v_n, w_n)$ in $\mathbb R^2_+$.
Problem A. Find $\max\big\{ \sum_{i\not\in S} v_i : S\subseteq [n],\, \sum_{i\not\in S} w_i \le \sum_{i=1}^n v_i\big\}$.
Problem B. Find $\min\big\{ \sum_{i\in S} v_i : S\subseteq [n],\, \sum_{i\in S} w_i \ge \sum_{i=1}^n w_i-v_i\big\}$.
(By calculation, these problems are equivalent to those in the post. Note that the first is a special case of the standard KNAPSACK problem.  As discussed further in the proof of Theorem 2 below, the second is a special case of a sort of inverse of KNAPSACK.)
Theorem 1. The answer to Question 1 is no.  Specifically, for any $\epsilon>0$, there is a polynomial-time $(1+\epsilon)$-approximation algorithm for Problem A that has infinite approximation ratio for Problem B.
Theorem 2. The answer to Question 2 is yes.  Specifically, there is  polynomial-time $2$-approximation algorithm for Problem B.
Proof of Theorem 1.  First consider the instance $I=((0,\epsilon), (\epsilon, \epsilon), (1, 1))$.  The optimal solution is $S^*=\{1\}$, giving value $1+\epsilon$ for Problem A and $0$ for Problem B.  The solution $S=\{1,2\}$ gives value $1$ for Problem A and $\epsilon$ for Problem B.  So $S$ is a $(1+\epsilon)$-approximate solution for Problem A, but has ratio $\epsilon/0=\infty$ for Problem B.  Now consider an algorithm that, given this instance $I$, returns $S$, and given any other instance $I'$, returns a $(1+\epsilon)$-approximation solution for that instance $I'$, computed using the standard PTAS for KNAPSACK (thinking of $I'$ as an instance of Problem $A$, which is a special case of KNAPSACK). This is the desired algorithm. $~~~\Box$
Proof sketch for Theorem 2. Remark: The algorithm is similar to a greedy algorithm for Knapsack, and its analysis is similar to the analysis of that algorithm.
We give a 2-approximation algorithm for a slightly more general "inverse knapsack" problem:

Given $(v_1, w_1), \ldots, (v_n, w_n)$ and target $W$, find $\min\big\{\sum_{i\in S} v_i : S\subseteq [n],\, \sum_{i\in S} w_i \ge W\big\}$.

Given input $I=(((v_1, w_1), \ldots, (v_n, w_n)), W)$:

if $W\le 0$: return $\emptyset$

let $h = \arg\min_i \frac{v_i}{\min(W, w_i)}$

let $I'$ be the residual instance obtained from $I$ by deleting $(v_i, w_i)$ and replacing $W$ by $W'=W-w_i$.

recursively compute a solution $S'$ for $I'$

return $\{h\} \cup S'$

By a standard inductive argument, the algorithm returns a valid solution.  To finish we sketch a proof that the solution value is at most twice the optimal.  Consider any execution of the algorithm.  If $W\le 0$ the solution is optimal, so assume $W>0$.
Assume WLOG (by reordering $I$) that the final solution $S$ is $S=[m]=\{1,2,\ldots, m\}$, with each index $i\in S$ being chosen in the $i$th of the $m+1$ calls.  Define instances $I_1$ and $I_2$ as follows.  $I_1$ is obtained from $I$ by replacing $W$ by $W_1=w_1+w_2+\ldots+w_{m-1}$, while $I_2$ is obtained from $I$ by replacing $W$ by $W_2=W-W_1$ and deleting the pairs $(v_1, w_1), \ldots, (v_{m-1}, w_{m-1})$ (this is the instance passed into the final second-to-last recursive call).  Then:

$S_1=[m-1]$ is an optimal solution for $I_1$. (Note that $v_i/w_i \le v_j / w_j$ for all $i\in [m-1]$ and $j\not\in[m-1]$, and $w_1+w_2+\ldots+w_{m-1}=W_1$.  Using this, we can show by a standard greedy perturbation argument that $S_1$ is an optimal solution for the fractional relaxation of the instance $I_1$, where a fractional amount $x_i\in[0,1]$ of each item $i$ can be chosen.  So $S_1$ is also optimal for $I_1$.)

$S_2=\{m\}$ is an optimal solution for $I_2$. (This follows by a similar argument, along with the observation that replacing each $w_i$ in $I_2$ by $w'_i=\min(w_i, W)$ doesn't change the optimal value.)

The optimal value for $I_1$ is at most the optimal value for $I$. (This follows from the definition of $I_1$, as any solution for $I$ gives a solution for $I_1$.)

The optimal value for $I_2$ is at most the optimal value for $I$. (Consider the instance $I''$ obtained from $I$ by replacing each $v_i$ with $i\in[m-1]$ by $v'_i=0$.  Clearly the optimal value for $I''$ is a lower bound on the optimal value for $I$.  There is an optimal solution for $I''$ that includes all the indices in $[m-1]$.  The remaining part of that solution gives a solution for $I_2$ of the same value.)

From the preceding four observations, it follows that the cost of the final solution $S=S_1\cup S_2$ is at most twice the optimal value for $I$.$~~~\Box$


Computational complexity of random sampling I am using some randomized algorithms (particle filters) and I would like to know what is the computational complexity of obtaining one random sample of a continuous distribution (for instance from a multivariate Gaussian), in terms of elemental operations... or what computational complexities have conventional algorithms.

Thank you

The answer depends on your computational model. Sometimes people just assume you can generate a Gaussian as a unit operation. However, if all you can generate is, say, random bits, and you want an approximate Gaussian, the complexity depends on the approximation you want.


Kolmogorov complexity applications in computational complexity Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$) It is easy to see that most of strings are random (there are not so many short programs).

Kolmogorov complexity theory and algorithmic information theory are quite developed nowadays. And there are several amusing examples of using Kolmogorov complexity in proofs of different theorems that do not contain anything about Kolmogorov complexity in their statements (constructive LLL, Loomis-Whitney inequality and so on).

Are there any nice applications of Kolmogorov complexity and algorithmic information theory in computational complexity and related fields? I feel that there should be results that use Kolmogorov complexity as a straightforward replacement of simple counting arguments. This is, of course, not that interesting.

Lance Fortnow has written an article on this topic: Kolmogorov Complexity and Computational Complexity

You should also check out An Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi, the definitive book on the subject.  In particular, chapter 6 "The Incompressibility Method" discusses a number of applications in complexity such as a Kolmogorov complexity proof of Hastad's switching lemma (from Circuit Lower Bounds à la Kolmogorov by Fortnow and Laplante).

And there are applications in communication complexity (e.g. Kolmogorov Complexity and Combinatorial Methods in Communication Complexity by Kaplan and Laplante).


Route existence between n pairs of nodes Given a directed acyclic graph with $2n$ nodes how can one determine if there is a path between any of following n pairs of nodes $(1 \rightarrow n+1), \ldots, (n \rightarrow n+n)$? There is a simple algorithm in $O(n \cdot (n + m))$ (where m is the number of edges) by doing a search from each node $1 \ldots n$, but can it be done better?

EDIT: I'm looking for existence, not complete paths.

As Chandra Chekuri pointed out in a comment, you could just compute the transitive closure via fast matrix multiplication, solving the problem in O($n^\omega$) time (use your favorite method, O($n^{2.376}$) via Coppersmith and Winograd, or more practically using Strassen's O($n^{2.81}$)), and this would be good for dense graphs.

Now, I claim that if you can beat this running time for your problem for dense graphs, you would obtain an algorithm for triangle detection which is more efficient than computing the product of two Boolean matrices. The existence of such an algorithm is a major open problem.

I'll reduce the triangle problem to the n-pairs-DAG-reachability problem.
Suppose we are given a graph G on n nodes and we want to determine whether G contains a triangle.

Now, from G create a DAG G' as follows. Create four copies of the vertex set, $V_1$, $V_2$, $V_3$, $V_4$. For copies $u_i\in V_i$, $v_{i+1}\in V_{i+1}$ for $i=1,2,3$, add an edge $(u_i,v_{i+1})$ iff $(u,v)$ was in G.  Now if we ask whether there is a path between any of the pairs $(u_1, u_4)$ for all $u\in $G, then this would exactly be asking whether there is a triangle in $G$. The current graph has $4n$ nodes and we are asking about $n$ pairs. However, we can add $2n$ isolated dummy nodes and have $3n$ queries instead (by adding a query for $2n$ distinct pairs $(y,d)$ where $y\in V_2\cup V_3$ and $d$ a dummy), thus obtaining a $6n$-node instance of exactly your problem.


Linearly independent Fourier coefficients A basic property of vector spaces is that a vector space $V \subseteq \mathbb{F}_2^n$ of dimension $n-d$ can be characterized by $d$ linearly independent linear constraints - that is, there exist $d$ linearly independent vectors $w_1, \ldots, w_d \in \mathbb{F}_2^n$ that are orthogonal to $V$.

From a Fourier perspective, this is equivalent to saying that the indicator function $1_V$ of $V$ has $d$ linearly independent non-zero Fourier coefficients. Note that $1_V$ has $2^d$ non-zero Fourier coefficients in total, but only $d$ of them are linearly independent.

I am looking for an approximate version of this property of vector spaces. Specifically, I am looking for a statement of the following form:

Let $S \subseteq \mathbb{F}_2^n$ be of size $2^{n-d}$. Then, the indicator function $1_S$ has at most $d\cdot\log(1/\varepsilon)$ linearly independent Fourier coefficients whose absolute value is at least $\varepsilon$.

This question can be viewed from a "Structure vs. Randomness" perspective - Intuitively, such a claim says that every large set can be decomposed to a sum of a vector space and a small biased set. It is well known that every function $f:\mathbb{F}_2^n \to \mathbb{F}_2$ can be decomposed into a "linear part" of which has $\mathrm{poly}(1/\varepsilon)$ large Fourier coefficients, and a "pseudorandom part" that has small bias. My question asks whether the linear part has only a logarithmic number of linearly independent Fourier coefficients.

Isn't the following a counter-example?

Let $f(x)$ be the majority of $x_1, \ldots, x_{1/\epsilon^2}$, which is an indicator of a set of size $2^n/2$, so $d = 1$.  However, $\hat{f}(\{i\}) = \Theta(\epsilon)$ for $1 \le i \le 1/\epsilon^2$, so you have $1/\epsilon^2$ linearly independent large Fourier coefficients.


Gift bits when encoding a sequence of messages, how is that? Recently a friend of mine asked a question I couldn't give immediate answer to.

Say we have $ n $ messages of length $ m $ bits each. Now we can pack them in a single message of length $ n * m $ bits. So far so good, information quantity is additive.

But, from another side of view, besides coding the meaning of $n$ messages we also gave an order to them, this gives us additional $ \log _2( n!) $ bits. How is that?

I told that unordered messages are meaningless, but he replied, "Take something like photos or novels for example, clearly the order doesn't matter and we can use it to pass additional information".

Can you please explain this apparent paradox?

The important thing is what "information quantity is additive" with respect to.

Information quantity is additive with respect to concatenating messages

each of which can only have one length, rather than forming a multiset

of messages each of which can only have one length.

Information quantity is subadditive with respect to forming a multiset of messages

each of which can only have one length, because for every concatenation,

there is a unique multiset that is consistent with that concatenation.


Efficient algorithm to find overlapping circles of various sizes I have a collection of N circles in the plane with various position and radius. Circles move around according to one force and become bound to each other once they overlap.
I need a fast way to determine if a circle is overlapped/overlaps another, to determine the circle's equations of motion during a time step.
Once circles have overlapped, they are bound, so it's easy to remember that relationship.
The problem is to evaluate when circles overlap for the first time.
Think of cheerios floating on milk.

Obviously I have thought of using a KDTree or a Delaunay Triangulation, but these only take into account the circle centers, not their radius, so the closest circle in a DT Trianle isn't necessarily overlapping, while another might be.

I've read somewhere that a MWVD might work, but I don't understand how that would work.
D Eppstein has a couple of papers out on Mobius Transformations, and that too is over my head, but it looks like it's related.
Can anyone point me in the right direction ?

Thanks.

A modified Bentley-Ottmann sweep algorithm (here, for example) will find all line segment intersections in $O((n+k)\log n + k)$ time, where $k$ is the number of intersections.  It's fairly straightforward to extend the algorithm to handle circles. A good walkthrough is here under "finding intersections".

$k$ can be $\Omega(n^2)$ in theory (in which case pairwise checking is faster), but it seems difficult to avoid the $k$ term, and in any case you seem to say $k$ will be small in your question.

Granted, this recomputes the intersections from scratch each time you run the algorithm, which may be inefficient for your purposes.  You may be able to get around this a bit by maintaining the list of circles sorted by $x$ coordinate, and modifying this list online as the circles move.  This won't help your asymptotic running time, but it avoids sorting each circle every time.  If the circles stay relatively sparse (few cross the same vertical line), the binary search tree on the $y$-coordinates will be cheap to maintain.

The other issue is that knowing two circles intersect already does not improve the running time at all.  Once two circles attach to each other, you will calculate their intersection every single time, which is a waste.


Is Max-Cut APX-complete on triangle-free graphs? In the Max-Cut problem, one seeks a subset S of vertices of a given simple undirected graph  such that the number of edges between S and the complement of S is as large as possible.

Max-Cut is APX-complete on bounded-degree graphs [PY91], and in fact APX-complete on cubic graphs (i.e. graphs of degree 3) [AK00].

Max-Cut is NP-complete on triangle-free graphs of degree at most 3 [LY80] (triangle-free means that the input graph does not contain K_3, the complete graph on 3 vertices, as a subgraph).

Question: Is Max-Cut APX-complete on triangle-free graphs? (Note: arbitrary degrees allowed)

Thank you.

UPDATE: An answer has been found, but I would still be interested in a reference for this result, if there is any.

References:

[AK00] P. Alimonti and V. Kann: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1-2): 123-134, 2000. doi: 10.1016/S0304-3975(98)00158-3

[LY80] J.M. Lewis and M. Yannakakis: The Node-Deletion Problem for Hereditary Properties is NP-Complete. J. Comput. Syst. Sci. 20(2): 219-230, 1980. doi: 10.1016/0022-0000(80)90060-4

[PY91] C.H Papadimitriou and M. Yannakakis: Optimization, Approximation, and Complexity Classes, J. Comput. System Sci., 43(3): 425-440, 1991. doi: 10.1016/0022-0000(91)90023-X

Yes, by a reduction from MaxCut to triangle-free MaxCut. Here is what Wikipedia calls an L-reduction

Given an instance $G$ of Max-Cut, construct the 3-stretch $G'$ by subdividing each edge into three edges. Then the order of the maximum cut of $G'$  is the order of the maximum cut of $G$ plus twice the number of edges in $G$. Since the size of a max cut is always at least half the number of edges, the error ratio only gets worse by a constant factor.


Discrete log in GL(2,p) Let $p$ be a large prime.  Let $A$ be a $2\times 2$ matrix with coefficients in $GF(p)$ (i.e., coefficients taken modulo $p$).  Let $B=A^k$, where $k$ is an integer not given to us.  Given $p$, $A$, and $B$, the problem to find some $k$ such that $A^k=B$.

For which matrices $A$ does this problem have an efficient (poly-time) solution, and for which is it hard (say, as difficult as the discrete logarithm in $GF(p)$)?

I realize that for some choices of $A$ this problem can be solved efficiently.  For others, it is as hard as the discrete log problem modulo $p$, for which there is no known poly-time algorithm.  Can we somehow classify which matrices $A$ make this easy and which make it hard?  I can work out the answer for some special cases but am having a hard time getting the overall picture.

In other words: When is there an efficient algorithm to solve the discrete logarithm problem, when working with $2\times 2$ matrices over $GF(p)$?

Follow-up question: is there a neat way to generalize from $2\times 2$ matrices to $n\times n$ matrices?

Start by putting $A$ into Jordan normal form, i.e., write $A=PJP^{-1}$ where $J$ is the Jordan normal form and $P$ is a suitably chosen invertible matrix.  Then $A^k = PJ^k P^{-1}$, so without loss of generality I only need to consider possibilities for $A$ that are already in Jordan normal form.

For $2\times 2$ matrices, there are only three interesting cases:

Repeated eigenvalues: Suppose
$$A = \begin{pmatrix} \lambda &1\\ 0 &\lambda \end{pmatrix}$$
where $\lambda \ne 0$.  A simple induction shows that
$$A^k = \begin{pmatrix} \lambda^k &k\lambda^{k-1}\\ 0 &\lambda^k \end{pmatrix}.$$
Therefore in this case, the problem is easy: $k = \lambda \times (k \lambda^{k-1})  / \lambda^k = A_{1,1} \times B_{1,2} /B_{1,1}$.
A zero eigenvalue: Suppose
$$A = \begin{pmatrix} \lambda &0\\ 0 &0 \end{pmatrix}$$
where $\lambda$ is a generator modulo $p$ (i.e., it has order $p-1$ in the multiplicative group).
Then this problem is exactly as hard as the discrete log problem to base $\lambda$ modulo $p$, i.e., it is unlikely to have a poly-time solution.  This is because
$$A^k = \begin{pmatrix} \lambda^k &0\\ 0 &0 \end{pmatrix},$$
so we have exactly an instance of the discrete log problem modulo $p$ hiding in there.
If $\lambda$ is not a generator, the problem is exactly as hard as the discrete
log to the base $\lambda$.

Note that this case is not in $GL(2,p)$, so strictly speaking it could be excluded from the case analysis, but I thought I'd show how to handle it.
Diagonal matrix: Suppose
$$A = \begin{pmatrix} a &0\\ 0 &b \end{pmatrix}.$$
Then this problem is hard in general.  For instance, if $a$ is a generator of $GF(p)$ and $b=1$, this problem is exactly as hard as the discrete log problem modulo $p$ (so most likely there is no polytime algorithm for it).  If $a,b$ are both generators, then I believe the problem remains hard (see, e.g., this question), though I'm not aware of any reduction from the discrete log problem modulo $p$.  If either $a$ or $b$ is such that the discrete log to base $a$ or $b$ is easy, then this problem is easy, though the chances of this happening by blind chance (if $a$ and $b$ are randomly chosen) is very low.

When we generalize to $n\times n$ matrices, I think the story remains approximately the same.    If there is any Jordan block of size $>1$, then the discrete log problem is easy ($A^k$ contains the values $\lambda^k$ and $k \lambda^{k-1}$, so the same trick works).  If $A$ is diagonal, then this is just an instance of this question; when the diagonal elements are chosen randomly, we can expect this to be hard (except with negligible probability).


A coupon collector type problem with changing probabilities Suppose we are flipping coins starting at some time $t$. At time $t$ the probability we obtain heads is $\frac{1}{\sqrt{t}}$. If the coin lands tails, at time $t+1$ the probability of heads is now $\frac{1}{\sqrt{t+1}}$ and so on... What is the expected number of flips until the coin lands heads? In particular I would be interested in an upper bound on the expectation.. If this is difficult suppose we also make the assumption that it is bounded by $T$, e.g. there at most $T > t$ coins.

If the probabilities are constant at $p$ at each round, the expected value  is $1/p$ which is like one coupon being collected in the coupon collector problem. Since the probability of heads is less than $1/\sqrt{t}$ at each round, $\sqrt{t}$ is a lower bound for the expectation. On the other hand, the probability is greater than $1/\sqrt{T}$ in the bounded case, and so $\sqrt{T}$ is an upper bound. The question is where in this regime $[\sqrt{t}, \sqrt{T}]$ does the expectation fall..

Lemma. In the unbounded case, the expected number of flips is at most $\sqrt t + 3/2$.

Proof. Let r.v. $F$ be the number of flips until a head.
Then the expected number of flips is

\begin{align}
E[F] & = \sum_{i=1}^\infty \Pr[F \ge i] && (1)\\
&= \sum_{i=0}^\infty \Pr[\text{first $i$ flips are tails}] && (2)\\
&= \sum_{i=0}^\infty \prod_{j=t}^{t+i-1} (1-1/\sqrt{j}) && (3)\\
&\le \sum_{i=0}^\infty \exp(\textstyle-\sum_{j=t}^{t+i-1} 1/\sqrt j)
& \text{as } 1+z\le e^z~~ & (4)\\
&\le \sum_{i=0}^\infty \textstyle\exp(-\int_{t}^{t+i} 1/\sqrt x ~dx)
& \text{as } \textstyle \sum_{j=a}^{b-1} f(j) \ge \int_{a}^b f(x)\, dx~~&(5)\\[-10ex]
&&~~\text{for $f$ decreasing}~~\\
&= 1+\sum_{i=1}^\infty \textstyle\exp(2\sqrt{t}-2\sqrt{t+i})
& \text{as } \textstyle\int 1/\sqrt x ~dx = 2\sqrt x~~&(6)\\
&= 1+e^{2\sqrt{t}} \sum_{i=t+1}^\infty e^{-2\sqrt i}&&(7)\\
&\le 1+e^{2\sqrt{t}} \int_{t}^\infty e^{-2\sqrt x}\,dx
&\text{as } \textstyle \sum_{i=a}^{\infty} f(i) \le \int_{a-1}^\infty f(x)\, dx ~~&(8)\\
&&\text{for monotonic $f$}~~\\
\\
&= 1 + e^{2\sqrt{t}} \,e^{-2\sqrt t}(\sqrt t + 1/2)
& \text{as } \textstyle\int_t^\infty e^{-2\sqrt x}\,dx = e^{-2\sqrt t}(\sqrt t + 1/2)~~&(9)\\\\
&= \sqrt {t} + 3/2&&~~\Box
\end{align}

Of course the same bound holds in the bounded case as well.