Polygon within polygon generalization problem I would like to apologize to all the posts below. Picked the wrong forum to post this in originally. However rather than make this a complete waste I've reworked the question to be a true "Theoretical Computer Science" problem.

Problem: Create an algorithm that takes a set of n ordered points in a 2D plane that form the contour of a simple polygon A that may or may not be concave and creates a new polygon B with m points such that:

all points in A are contained within B
3 <= m < n
B is the polygon in the set of all Bs with the smallest area
B must be a simple polygon (i.e. no self-intersections).
The input to the algorithm is polygon A and "m".
Coincidence of segments in B with segments in A are allowed.

Some example inputs and expected outputs:

If A is a square and m is 3 then B would be the triangle with the smallest surface area that contains A.
If A is a hexagon and m is 4 then B would be a quadrilateral with the smallest surface area that contains A.

Good luck to everyone who tries this problem out. I can promise you this will be very hard especially now that the solution must be optimal.

I don't know how your polygons look, but perhaps a simplified version of the Ramer–Douglas–Peucker algorithm is enough:

for each convex part, calculate the area $A_j$ of of the triangles $P_i P_{i+1} P_{i+2}$ formed by three consecutive points;
for each concave part, calculate the area $B_k$ of of the two triangles $P_i P'_i P_{i+1}$ and $P_{i+1} P'_{i+2} P_{i+2}$ formed by the extension of the two points $P_i, P_{i+2}$ and the middle point $P_{i+1}$
calculate the $min\{A_j,B_k\}$ and delete the corresponding point (and shift points if the operation is done on the concave part);
loop until $n-m$ points have been deleted.

The border of the polygon ($A_j$ green triangles, $B_k$ red triangles). On the right, the border after the elimination of two points.

For more complex algorithms you can search for "polygon generalization techniques" though your first condition (points in A are contained in B) implies some additional scaling operations.


Is cubic complexity still the state of the art for LP? According to D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, 1994, a linear program with $n$ variables, $n$ constraints and precision $L$ is solvable in $O(n^3L)$ time. Has that been improved upon?

It seems that K.M.Anstreicher has improved the result to $O((n^3/\ln n)L)$ in Anstreicher, Kurt M. "Linear programming in O ([n3/ln n] L) operations." SIAM Journal on Optimization 9, no. 4 (1999): 803-812.. I have not read this paper, but I hope that this answer will help you in some extent.


Bisecting a set of points into two optimal subsets I want to divide a set of points into two equally-sized subsets such that the within-cluster sum of squares is minimized. We can assume that the points are in two-dimensional Euclidian space. I'm hoping for something faster than a general k-means clustering algorithm given that k=d=2. Can anyone point me in the direction of a good algorithm for this?

An exact solution not necessary if we have a good approximation.

Thanks!

If you insist on precise partition, then you need to compute all the balanced partitions of a set of points in the plane by a line (the optimal partition is a Voronoi partition, so the two point sets are separated by a line). Such partitions are known as $k$-sets. The fastest algorithm currently known for this work in $O(n^{4/3} \log n)$ for computing these partitions in the dual [i.e., the $k$-level of a set of $n$ lines, for $k=n/2$]. Once you have all the possible partitions, you just need to check each one of them. Using standard tricks, this can be done in constant time for each partition.

(Update: Proving that the optimal partition is realized by a $k$-set, for $k=n/2$, is not completely trivial. I would leave it as a cute exercise for the interested reader. Hint: Consider the line passing through the two optimal centers, and the direction perpendicular to it.)

If you do not care about the exact solution, then an easier approach would be to use a coreset for $k$-means clustering. This would result in $O( \epsilon^{-2} \log n)$ weighted points in this case, with total weight $n$. Then, you just need to solve the problem on the weighted point-set. The easiest solution would be to generate then a set of candidate locations for centers, and trying all pairs on the weighted points. The coreset construction, and generating the candidate centers is described in this paper:

http://sarielhp.org/p/03/kcoreset/


Union/find structure implemented by bitvectors I'm having trouble understanding a concept in my book which is about finding a good structure to represent a union-find datastructure. Here we define a structure -referred to as collection- $V$ as such a datastructure:

A collection $V$ is a bitvector (bitvector is an array of $l = (n/b) + 1$ longs) where bit $i$ ($0 \le i \lt b$) of word $j$ ($0 \le j \lt l$) is 1 only if the element $j * b + 1$ is in the collection $V$.

($n$ is the amount of elements, $b$ is how many bits are represented in a long)

So i was thinking of figuring this out with an example, let's say we have collection $V$:

[ 1 |  3  |  6  | ... | l  ]

And since:

1 = 001
3 = 011
6 = 110

Does that mean elements with the number (assuming we have given each element a number):

1 * 64 + 1 = 65
3 * 64 + 1 = 193
3 * 64 + 2 = 194
6 * 64 + 2 = 386
6 * 64 + 3 = 387

are in the collection $V$ ?

If this is completely wrong, could someone please give me a decent example of such a collection $V$, or point out where i'm wrong, or why my example can't be such a collection?

(also, i couldn't give this any sensible tag since i can't create tags yet)

The concept is simpler than you think.

Assuming 8 bit words and a bitvector of only one word length,

1 = 00000001
3 = 00000100
6 = 00100000

The collection is the union of the three individual elements, which is to say 00100101.

Also, wikipedia: http://en.wikipedia.org/wiki/Bit_array


Complexity of $\oplus$ 3-REGULAR BIPARTITE PLANAR VERTEX COVER The $\oplus$3-REGULAR BIPARTITE PLANAR VERTEX COVER problem consists in computing the parity of the number of vertex covers of a 3-regular bipartite planar graph.

  Question

  Which is the complexity of such problem? Is it $\oplus$P-hard, or is it in P?
  What if we remove the planarity restriction (i.e. $\oplus$3-REGULAR BIPARTITE VERTEX COVER)?

The closest I was able to find is that $\oplus$3/2 BIPARTITE PLANAR VERTEX COVER is $\oplus$P-complete (see Theorem 2.2 in this paper).

Ok, according to the paper Accidental algorithms by Valiant, the  problem ⊕Pl-3/2Bip-Mon-2CNF is ⊕P-complete. So ⊕ 3-REGULAR PLANAR VERTEX COVER would also have to be ⊕P-complete. So it's not in P (unless P = ⊕P-complete).
But I still don't know if ⊕ 3-REGULAR BIPARTITE PLANAR VERTEX COVER is ⊕P-complete.


Flat vs non-flat domains My understanding is that, more often than not, when people use domain theory for higher-type computability or the denotational semantics of functional programming languages, they tend to prefer flat domains to interpret base types.

These are obviously simpler to handle than non-flat ones, a fact that is reflected both on theoretical issues, since reasoning about properties of the model can become quite a combinatorial task, as well as on issues phrased in a more applied parlance, like, say, strictness analysis. My understanding is also that there are things that one can pull out in non-flat domains that are simply not doable in the flat ones, perhaps the most trivial example being the injectivity of constructors.

But, I feel that my understanding is still quite uninformed and shallow.

My questions: Why prefer flat domains? Why prefer non-flat domains? What are examples of things (theoretical or practical) that can be done in one setting but not, or not yet, in the other? Is there a reference with an account on such a comparison?

EDIT (25/11/14): I added explicit mention of the base types, after the discussion with babou and Damiano Mazza below.

With only flat domains, you cannot define limits to construct
"infinite" structures, such as looping structures, for data or for
programs. Fixpoint constructions in denotational semantics (since you used that tag) use non flat domains.
Maybe you should give examples of domains that are taken as flat,
while it would be better to do differently.

Many problems we deal with are expressed with data from flat domains.
But non-flat domains are used when necessary or convenient. Infinite,
or indefinite structure such as stream are not flat. Some domains used
for program analysis, for example with abstract interpretation, are not
flat. But is pretty much because non-flat domains are more
appropriate, as information that can be obtained is expected to have
different degrees of precision.

One good example to look at (but I have no expertise) is the case of
real numbers. They are often considered in a flat domain, but they are
really limits in a non-flat domain. How much is that used, explicitly
or implicitly?

Edit after the question was restricted to base types

The nature of the question changes somewhat if you restrict it to base
types.

In many case, it would be interesting to see whether there are
alternatives to using flat domain, and what is the usefulness of such
alternatives. Is there a choice between flat and
non-flat for booleans? Is there one for integers? for characters? etc. What are the
pros and the cons.

But, to begin with, you may have to define what is a base type. This
is why I suggested looking at the real numbers. Should the domain be
considered flat or not.  Even in classical mathematics, reals can be
defined as limits. So you could ask the question whether reals are a
base type.

I have not looked at these issues for a long time, but I think the
following paper may be relevant: "Concrete Domains" by Gilles Kahn and
Gordon Plotkin.

I also found a historical introduction to it which I have not
read. And there seem to be some significant literature that followed.


Approximation algorithm for graph problem In the process of trying to create an approximation algorithm for the following problem.

Let $G = (V,E)$ be a graph, $c_e, c_{iv} \ge 0$, for $e \in E$, $i \in L$, and $v \in V$, where $L$ is a finite set of integers.  Each vertex $v$ in the graph is to be assigned an element $i$ from the list $L$ at cost $c_{iv}$.  Cost $c_e$ is incurred for an edge iff its vertices are in different lists.  The objective is to find the minimum cost assignment to vertices.

IP: Minimize $\sum_{e \in E} c_e x_e + \sum_{i \in L \\ v \in V} c_{iv}y_{iv}$
subject to

$\sum_{i \in L} y_{iv} = 1$ for all $v \in V$,

$y_{iv} + y_{ju} \le 1 + x_{(u,v)}$,
for all $(u,v) \in E$, $i \neq j \in L$.

$x_e, y_{iv} \in \{0,1\}$ for all $e \in E$, $i \in L$, $v \in V$.

Somehow (through rounding), I am supposed to use the linear relaxation to create a 2-factor approximation for the optimal solution to this integer program.  Does anyone have a hint for how to proceed?

The problem you specify is called Uniform Labeling Problem and often arises in the field of computer vision. Kleinberg & Tardos give the LP-based 2-approximation you are looking for.

This problem also appears in the Williamson & Shmoys book as exercise 5.10.


Is there any equation-based method for transforming Büchi-automata to omega-regular language? I know there exists an equation-based method for transforming finite automata into regular language (or `regular expression'). The main idea is as follows.
      First we construct a set of equations named "(1)" based on an automaton $A$:
            \begin{equation}\begin{aligned}&l_1 = \varepsilon + p_{11}l_1 + p_{12}l_2 + ... + p_{1n}l_n\\
                         &l_2 = \varepsilon + p_{21}l_1 + p_{22}l_2 + ... + p_{2n}l_n\\
                         &...\\
                         &l_n = \varepsilon + p_{n1}l_1 + p_{n2}l_2 + ... + p_{nn}l_n, \end{aligned}\end{equation}
where are $l_1,...,l_n$ are the locations (or called "states") of $A$ with $l_1$ the initial location, $p_{ij}$ are regular expressions. Then we apply Arden's rule:

"$X = p^*q$ is the unique solution for equation $X = q + pX$"

to solve the equations. The result of $l_1$ is the regular expression we want.

Now my question is, is there a similar method for transforming Büchi automata into omega-regular language?

Sure. In fact, the translation from Büchi automata to $\omega$-regular expressions is only a small extension of the one for finite-word languages.

Recall that an $\omega$-regular expression is of the form $s_1\cdot t_1^\omega+\ldots+s_k \cdot t_k^\omega$, where all the $s_i$ and $t_i$ are regular expressions.

The translation of an NBW $A$ to such an expression is based on the following observation: let $A_{p,q}$ be the NFA obtained from $A$ by setting $p$ as the initial state, and $q$ as the single accepting state, then $L(A)=\bigcup_{q\in \alpha} L(A_{q_0,q})\cdot L(A_{q,q})^\omega$ where $\alpha$ is the set of accepting states of $A$.

Indeed, a word is accepted by $A$ iff there is a run on it that leads from $q_0$ to an accepting state $q$, that is then visited infinitely often.

So all you need to do is write the equations that correspond to this union. It'll be slightly uglier than those for an NFA, but not much.


combinatorical embedding I have a problem with the following statement :

Every combinatorial embedding is equivalent to one with $\lambda(T) = 1$ on a spanning tree of G

What does this mean ?

OK in a spanning tree there isn't a cycle, so the signature of every edge is equal to $1$ but what is the sense of this statement?

A combinatorial embedding or signed rotation system is a combinatorial representation of a cellular embedding of a graph on some surface.  An embedding is a drawing of the graph such that no two edges cross; an embedding is cellular if every face is a disk.

Consider an undirected graph $G=(V,E)$.  It is helpful to regard each edge in $E$ as a pair of directed edges, or darts.  Each dart goes from one vertex, called its tail, to another vertex, called its head.  The reversal of a dart is obtained by swapping its head and its tail.  Let $\vec{E}$ denote the set of all darts.

A signed rotation system consists of two functions:

A successor permutation $\textit{succ} \colon \vec{E} \to \vec{E}$.  Specifically, $\textit{succ}(\vec{e})$ is the next incoming dart after $\vec{e}$ in "clockwise" order around $\textit{head}(\vec{e})$.  Thus, the cycles of $\textit{succ}$ correspond precisely to the vertices of $G$.
A sign function $\textit{sign}\colon E \to \{-1, +1\}$, which indicates for each edge whether the "clockwise" orders at the endpoints of that edge are consistent ($+1$) or inconsistent ($-1$).

This representation is not unique.  For example, reversing the cyclic order of incoming darts at any vertex $v$ and changing the signs of all edges incident to $v$ leaves the embedding intact.

The theorem you are asking about is the following:

  Any cellular embedding of any graph $G$ can be encoded by a signed rotation system, such that for some spanning tree $T$, every edge in $T$ is positive.

In fact, one can prove a stronger statement:

  For any spanning tree $T$ of any graph $G$, any cellular embedding of $G$ can be encoded by a signed rotation system, such that every edge in $T$ is positive.

If the underlying surface is orientable, we can choose a global "clockwise" orientation, which means any embedding onto that surface has a representation where all edges in $G$ are positive.

On the other hand, if the underlying surface is non-orientable, some edges must be negative.  Any one-sided cycle must include an odd number of negative edges (and therefore at least one negative edge), because moving once around a one-sided cycle reverses your local orientation.  That's what "one-sided" means.  Still, it is possible to ensure that every edge in your favorite spanning tree is positive.

The proof is straightforward induction over the tree $T$.


Reducing the bandwidth of non-symmetric matrix Is there an efficient algorithm to reduce the bandwidth of a directed graph's adjacency matrix? Something like the reverse Cuthill-McKee, but for non-symmetric matrices.

The following article discusses various approaches to reducing the bandwidth of unsymmetric matrices.

J.K. Reid, J. A. Scott: Reducing the total bandwidth of a sparse unsymmetric matrix, SIAM Journal on Matrix Analysis and Applications 28(3):805–821.

The technical report version of the article is available here:

J. K. Reid and J. A. Scott, Reducing the total bandwidth of a sparse unsymmetric matrix, Technical Report RAL-TR-2005-001, STFC Rutherford Appleton Laboratory. http://www.numerical.rl.ac.uk/reports/rsRAL2005001.pdf


What relation is between constraint satisfaction problems and constraint programming? Are programs written in the constraint programming (CP) paradigm more expressive than problems defined as constraint satisfaction problem (CSP)?

Wikipedia says about Constraint_programming:

  Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints.

and later:

  The constraints used in constraint programming are of various kinds: those used in constraint satisfaction problems (e.g. "A or B is true"), those solved by the simplex algorithm (e.g. "x <= 5"), and others.

If I understand that correctly CPs can describe superset of problems which can be described by CSP.

I'm especially interested in these programs of puzzle solvers written using CP. In the paper they wrote that some rules can not be described using CP so they used something which looks like imperative paradigm. If I cut off imperative part of programs is that valid CSP problem definition?

First of all, I cannot help but point out a practice I consider bad in the way you defined your question. You are comparing a class of algorithms with a class of problems. Although closely related, they are not the same. As an example, consider the halting problem. It is a very well defined problem. However, we know that no Turing Machine can diagnose it. Given the Church-Turing thesis, this is the same as saying that there is no algorithm for this problem.

However, one can rephrase the question such that the items compared are of the same nature. Consider constraint programming (CP) as the computational model A and
boolean formulas as the computational model B. I chose boolean formulas because SAT is probably the most known CSP and furthermore boolean formulas have a nice property, which I will use below.

Although I have programmed in Prolog, I cannot say I have a good knowledge of constraint programming. However, I am almost certain that they are Turing-complete. Since they use constraints, one could use them to "simulate" head moves,e.g. if [constraint] then move to this cell . Furthermore, one could write contents into that tape. Therefore, constraint programming is as powerful as Turing Machines. Since all programs in CP are algorithms, they can be simulated by a universal TM. Thus CP and TM have the same expressibility.

One might think at this point that CP is a stronger model that boolean formulas. However, in Arora and Barak's book "Computational Complexity:A Modern Approach", in chapter 2, a proof is given that any boolean function has an equivalent boolean formula ( the theorem is labeled "Universality" of AND,OR and NOT). On a given input, the formula is satisfied if and only if the boolean function is true for this input.  As an informal proof, consider that those 3 operators can express any piece of hardware. Furthermore, every other input can be translated into a boolean one. Therefore, every TM can be simulated as a boolean formula. Thus boolean formulas are Turing-complete. Furthermore, there is a TM that can diagnose the satisfiability of a boolean formula. Therefore, boolean formulas and TMs are equivalent.

It follows that the two models have the same expressibility.


Is DAG subset sum approximable? We are given a directed acyclic graph $G=(V,E)$ with a number associated with each vertex ($g:V\to \mathbb{N}$), and a target number $T\in \mathbb{N}$.

The DAG subset sum problem (might exist under a different name, a reference will be great) asks whether there are vertices $v_1,v_2,...,v_k$, such that $\Sigma_{v_i}g(v_i) = T$, and $v_1\to..\to v_k$ is a path in $G$.

This problem is trivially NP-Complete, as the complete transitive graph yields the classical subset sum problem.

An approximation algorithm for the DAG subset sum problem is an algorithm with the following properties:

If there exists a path with sum T, the algorithm return TRUE.
If there is no path summing up to a number between $(1 − c)T$ and $T$ for some $c\in (0,1)$, the algorithm return FALSE.
If there is a path summing to a number between $(1 − c)T$ and $T$, the algorithm may output any answer.

Subset sum is known to be approximable in polynomial time for all $c>0$.

Does the same hold for DAG-Subset-Sum?

It seems to me the pseudo-polynomial time dynamic programming algorithm for Subset Sum problem also works for this problem. For each vertex $v_i$, we compute the set $L_i$ consisting of all possible values of paths ended at $v_i$. Then, we have the recurrence relation:
$L_i=\{g(v_i)\}\cup\{x+g(v_i)\mid x\in \bigcup_{j\in  prec(i)} L_j\}$. Following a topological order, all the $L_i$ can be computed in $O(Km)$ time, where $K$ is the total weight and $m$ is the number of edges.

I think the standard scaling-and-rounding can also be applied to derive a FPTAS.


Counting the number of vertex covers: when is it hard? Consider the #P-complete problem of counting the number of vertex covers of a given graph $G = (V, E)$.

I'd like to know if there is any result showing how the hardness of such problem varies with some parameter of $G$ (for example, $d = \frac{|E|}{|V|}$).

My sensation is that the problem should be easier both when $G$ is sparse and when $G$ is dense, while it should be hard when $G$ is "in the middle". Is this really the case?

The #VC problem of computing the number of vertex covers of a given graph remains #P-hard for 3-regular graphs; see for example [Greenhill, 2000].

To show that the #VC problem remains #P-hard for graphs with at most $c\cdot n$ edges, where $n$ is the number of vertices and $0<c<3/2$, reduce from the 3-regular case by adding a large enough independent set (of linear size). The number of vertex covers remains the same if you add an independent set.

Similarly, to show that the #VC problem remains #P-hard for graphs with at least $c\cdot n^2$ edges, where $n$ is the number of vertices and $0<c<1/2$, reduce from #VC by adding a large enough clique component (of linear size). The number of vertex covers is multiplied by $p+1$ if you add a clique of size $p$ to a graph.

Catherine S. Greenhill: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Computational Complexity 9(1): 52-72 (2000)


MACing from an arbitrary high min-entropy shared secret Let $\gamma$ be such that $\, 0<\gamma \,$. $\hspace{.1 in}$ Define $H_{\infty}$ to be min-entropy.

If $S_n$ is a shared secret between Alice and Bob such that $\, n^{\frac12+\gamma} \leq H_{\infty}(S_n) \,$,
then Alice can use that to securely encrypt a message for Bob.
(Alice uses a strong extractor, such as in either of Theorem 2/3,

to get the key, and sends the seed along with the ciphertext.)

This idea does not obviously suffice for Alice to authenticate a message to Bob, since a false

acceptance could be caused by someone changing both the message and the reported seed.

  Is there a way for Alice to authenticate a message to
  Bob from an arbitrary high min-entropy shared secret?

Potential Clarifications:

a. $\,$ I am fine with "high" meaning something much closer
$\hspace{.24 in}$to $n$ than I used in the encryption construction.

b. $\,$ I really do mean "Alice to authenticate a message to Bob"; that is,
$\hspace{.24 in}$it does not need to work from Bob to Alice or for more than one message.

c. $\,$ I would nonetheless be interested in whether or not
$\hspace{.24 in}$the restrictions described in (b) could be relaxed.

As you may know, the problem of taking a weak shared key, about which the adversary knows some information, and extracting from it a key about which the adversary has essentially no information, is often referred to as privacy amplification. Once this is done, we can use the new strong key for authentication, encryption, etc.

If interaction is allowed, Alice and Bob can extract a strong key over an inauthentic channel very efficiently, in particular there is no requirement that the min-entropy rate be at least 1/2. See "Privacy Ampliﬁcation with Asymptotically Optimal Entropy Loss" by Chandran, Kanukurthi, Ostrovsky, Reyzin, and references therein.

Their introduction mentions that non-interactive solutions (one message from Alice to Bob) exist as well (references 5, 10, 15), but these do require min-entropy rate 1/2. Depending on the application, another possibility for a one-message solution would be to use deterministic (aka seedless) extractors, which work only for certain classes of sources with some restricted structure. For instance, the adversary knows some fraction of the key's bits, but the remainder are uniformly random to him. See for example Kamp and Zuckerman, "Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography" or Kamp, Rao, Vadhan, Zuckerman, "Deterministic Extractors for Small-Space Sources"


Maximum disjoint set: what is the actual approximation factor of the greedy algorithm? Consider the problem of finding a maximum disjoint set - a maximum set of non-overlapping geometric shapes, from a given collection of candidates. This is an NP-complete problem, but in many cases, the following greedy algorithm yields a constant-factor approximation:

For every candidate shape x, calculate its disjoint intersection number $DIN(x)$ = the largest number of disjoint shapes that intersect x.
Select a candidate shape with a smallest DIN ($\arg \min_{x} DIN(x)$). Remove it and all the shapes it intersects.
Continue until no more candidates remain.

For example, consider the following figure from the Wikipedia page:

The green disk intersects 5 other disks, but its DIN is 3 (the 3 red disks are disjoint). The topmost and bottommost red disks intersect 2 other disks, but they themselves intersect, so their DIN is 1. The yellow disks have a DIN of 2.
The greedy algorithm thus selects the topmost or the bottommost red disk.

If the minimum DIN can be bounded by a constant, then the greedy algorithm is a polynomial constant-factor approximation.

For example, if all candidate shapes are unit disks, Marathe et al (1995) show that a disk with a DIN of at most 3 always exists: the leftmost disk (the disk with the smallest x coordinate) intersects at most 3 other disjoint disks. Therefore the greedy algorithm yields a 3-approximation because it obtains 1 disk for each (at most) 3 disks in the optimal solution.

Similarly, if all candidate shapes are disks of arbitrary size, the greedy algorithm yields a 5-approximation, because the smallest disk intersects at most 5 other disjoint disks, i.e. the minimum DIN is at most 5.

So far so good, but Are these factors of 3 and 5 tight? I am not sure.

Consider the figure above. Selecting the leftmost disk (green) will find a disjoint set of size 1, which is indeed a 3-approximation to the maximum disjoint set of size 3 (red), but, the greedy algorithm will not select the green disk - it will select the top/bottom red disk, whose DIN is 1. In this case the greedy algorithm will find the optimal solution.

I couldn't find a counter-example for general $n$, in which the greedy algorithm finds a disjoint set with $n$ unit disks while the maximum disjoint set has $3n$. Actually, I couldn't even construct a general counter-example in which the minimum DIN is indeed 3. The best I could come up with is the following, in which each unit disk intersects at most 2 other disjoint disks (i.e. the minimum DIN is 2). But even here, the greedy algorithm finds the optimal solution rather than a 2-approximation:

My questions are:

What is the actual max min DIN in collections of unit-disks? Arbitrary-sized disks?
What is the actual approximation factor of the greedy algorithm for collections of unit-disks? For arbitrary-sized disks? (this factor is at most as large as the max min DIN, but may be smaller).

UPDATE: For every k-tuple of shapes, $x_1,...,x_k$, define $DIN(x_1,...,x_k)$ = the largest number of disjoint shapes intersected by their union $x_1\cup...\cup x_k$. Define $minDIN_k$ as the minimum DIN of over all k-tuples of disjoint shapes.

For example, in Yury's answer below, $minDIN_1=3$, because every circle intersects 3 other circles. $minDIN_2=4$, because it is possible to select 2 disjoint circles, one from the outer circle and one from the inner circle, that together intersect only 4 other circles. For every $k$, $minDIN_k\leq k+2$.

I THINK that the approximation ratio of the greedy algorithm can be bounded by $\frac{minDIN_k}{k}$, because, for every $minDIN_k$ shapes in the optimal solution, we have at least $k$ shapes in the algorithm output. Is this correct?

EDIT: I am now reading the excellent book Research problems in discrete geometry. While I haven't found this exact problem, I found a problem that looks related. In section "2.5 Thin Packings with Many Neighbors", there are examples of circle packings in which each circle touchese 5 other circles. I wonder if such a packing can yield a configuration of circles with DIN = 5.

What is the actual maximum minimum DIN in collections of unit-disks?

It is 3.


Can we efficiently distinguish between P and BPP? Let's say algorithm $D$ distinguishes $BPP$ from $P$ if
there exists a language $L \in BPP$ such that for all $A \in PTM$,
$$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \notin L_A$$

Can we show this statement is false for all polynomial time algorithms $D$?

The question can be phrase in another way.
$BPP \neq P$ iff
there is a function $D$ such that
for some language $L\in BPP$ and
for all $A \in P$ we have
$$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \notin L_A$$

Most researchers seem to lean towards $P=BPP$,
so we don't expect there is any such $D$.

Can we at least prove that
there is no polynomial time computable function $D$
separating $P$ from $BPP$?

You defined that algorithm $D$ distinguishes $BPP$ from $P$ if
there exists a language $L \in BPP$ such that for all $A \in PTM$,
$$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \notin L_A.$$

Here as I understand it $L_A$ is the language accepted by $A$, $\langle A\rangle$ is a code for $A$, and $D$ takes such a code and outputs a string that may or may not be in $L$ or in $L_A$.

One particular way this could happen is if $D(\langle A)=\langle A\rangle$ for all $A$, or to write it more succinctly, $D(e)=e$ for all $e$. Instead of $L_A$ we may write $\phi_e$.

Then the condition is
$$e\in L\leftrightarrow e\not\in\phi_e,$$
or, if we consider a set to be identified with its characteristic function,
$$ L(e)\ne \phi_e(e).$$
This now starts to look like saying that $L$ is a diagonally non-computable (DNC) function as studied in computability theory.
There, we have two facts:

There is no noncomputable oracle $A$ such that with positive probability, a random oracle $B$ can compute $A$; and
with probability 1, a random oracle $B$ can compute a DNC function.
with probability 1, a random oracle $B$ cannot compute a DNC function taking values in $\{0,1\}$.

Here (1) is analogous to BPP=P which we don't know whether holds.
And (3) is analogous to the statement that, assuming BPP$\ne$P, a random oracle cannot produce a $D$ as you suggest.

To conclude, I don't have an answer to your question, but

  by a loose analogy with computability theory it seems somewhat implausible that such a function $D$ should exist even if BPP$\ne$P.


References for Modular Decomposition What are good papers/books to better understand the power of Modular Decomposition and its properties?

I'm particularly interested in algorithmic aspects of Modular Decomposition. I have heard that it is possible to find a Modular Decomposition of a graph in linear time. Is there are an relatively simple algorithm for that? What about a not so efficient but simpler algorithm?

There is a recent survey

Habib and Paul (2010). A survey of the algorithmic aspects of modular decomposition. Computer Science Review 4(1): 41-59 (2010)

that you should check out.


1- in -$k$ SAT to $k$-SAT reduction The reduction from $k$-SAT to 1-in-$k$ SAT is known.

Would you help me to find a reduction from 1-in-$k$ SAT to $k$-SAT ? Thanks.

Answer converted from comment.

Definition: 1-in-$k$ SAT is a $k$-SAT problem with the tighter condition that - given a truth assignment to the variables - each clause must contain exactly one true literal (and thus $k$-1 false literals).

See for example 1-in-three SAT on Wikipedia

The reduction from 1-in-$k$ SAT to $k$ SAT can be done easily.

following the definition, convert each $(X_1 \vee X_2 \vee \cdots \vee X_k)$ clause of the 1-in-$k$ SAT problem into $(X_1 \wedge -X_2 \wedge \cdots \wedge -X_k) \vee (-X_1 \wedge X_2 \wedge \cdots \wedge -X_k) \vee $ $\cdots \vee (-X_1 \wedge -X_2 \wedge \cdots \wedge X_k)$;
convert to CNF distributing ORs over ANDs;
convert the resulting CNF formula to $k$ SAT

For example $(x_1 \vee x_2 \vee -x_3)$ becomes:

$(x_1 \wedge -x_2 \wedge x_3) \vee (-x_1 \wedge x_2 \wedge x_3) \vee
    (-x_1 \wedge -x_2 \wedge -x_3)$;
$(x_1 \vee x_2 \vee -x_3) \wedge (-x_1 \vee -x_2) \wedge (-x_1 \vee x_3) \wedge (-x_2 \vee x_3)$
$(x_1 \vee x_2 \vee -x_3) \wedge (-x_1 \vee -x_2 \vee x4) \wedge (-x_1 \vee -x_2 \vee -x4)$ $\wedge (-x_1 \vee x_3 \vee x4) \wedge (-x_1 \vee x_3 \vee -x4)$ $\wedge (-x_2 \vee x_3 \vee x4) \wedge (-x_2 \vee x_3 \vee -x4)$

Note: at step 3, if you allow repeated variables in a clause, then there is non need for the extra variable and the final $k$ SAT formula of the example can be:
$(x_1 \vee x_2 \vee -x_3) \wedge (-x_1 \vee -x_2 \vee -x2)$ $\wedge (-x_1 \vee x_3 \vee x3)$ $\wedge (-x_2 \vee x_3 \vee x3)$


Complexity of k-clique for hypergraphs Classic Problem:

Let a number $k$ be given.  The $k$-clique problem is as follows.

Given a graph $G$, does there exist a subset $S$ of $k$ vertices so that any two vertices of $S$ are adjacent?

Hypergraph Problem:

Let numbers $c$ and $k$ be given.  The $(c,k)$-hyperclique problem is as follows.

Given a $c$-uniform hypergraph $H$, does there exist a set $S$ of $k$ vertices so that any subset of $c$ vertices from $S$ forms a hyperedge.

Questions:

(1) What is the best known algorithm for solving $(c,k)$-hyperclique?

(2) What is its time complexity?

(3) Is there any connection between $(c,k)$-hyperclique and matrix multiplication?

For all I know, this might be a well studied problem.  Any references that investigate this problem are greatly appreciated.

It is not known if there is an $\varepsilon > 0$, $c > 2$, and $k > c$ such that $(c,k)$ hyperclique is in $n^{k-\varepsilon}$ time. Note that the case of $k \leq c$ is trivial. For years I have communicated this problem to many people, and taught it in cs266 at Stanford, due to its connection to solving $k$-Sat. (Several open problem sessions at workshops probably recorded this.)  Here are a few things I know:

I proved several years ago that solving $4-cycle$ on $n$ node graphs in $n^{2-\varepsilon}$ time implies $(3,4)$ hyperclique in $n^{4-\varepsilon}$ time. Haven't published it.

UPDATE (Aug 2019) the aforementioned result and some generalizations now appear in the paper

Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams:
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. SODA 2018: 1236-1252

If you can solve $(3,4)$ hyperclique as indicated above, then Max-3-Sat can be solved in strictly less than $2^n$ time. Similarly, solving $(k,k+1)$ hyperclique would yield a faster $k$-Sat algorithm. So if you believe Strong ETH then there is an obvious limit here. The reduction is a natural generalization of the reduction from Max-2-Sat to triangle finding ($(2,3)$ clique) from ICALP'04 and my PhD thesis.

You can solve $(c,k)$ hyperclique in $n^k/(\log n)^{\Omega(k)}$ time by generalizing the paper Efficient Algorithms for Clique Problems.


Application of Ramsey Numbers The definition of Ramsey numbers is the following:

Let $R(a,b)$ be a positive number such that every graph of order at least $R(a,b)$ contains either a clique on $a$ vertices or a stable set on $b$ vertices.

I am working on some extension of Ramsey Numbers. While the study has some theoretical interest, it would be important to know the motivation of these numbers. More specifically I am wondering the (theoretical or practical) applications of Ramsey numbers. For instance, are there any solution methodology for a real life problem that uses Ramsey numbers? Or similarly, are there any proofs of some theorems based on Ramsey numbers?

Applications of Ramsey theory to CS, Gasarch


How hard is a variant of graph automorphism problem? I'm interested in a variant of graph automorphism problem (which is $NPI$ candidate).

Restricted GA

Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ pairs of nodes $(u, v)$ where $u \ne v$ ( all pairs $(u_i, v_i)$ are pair-wise disjoint and $0 \le \epsilon \le 1$)

Question: Is there a non-trivial automorphism $f$ of $G$ such that for every pair $p_i$ either $v_i=f(u_i)$ or $u_i= f(v_i)$?

This problem is at least as hard as Graph Automorphism Problem. I guess it is harder than Graph Automorphism but not $NP$-hard.

  Is there a computational evidence that supports (or against) my guess regarding the complexity of this variant of $GA$?

Motivation: My problem is a relaxation of NP-complete problem known as fixed-point free graph automorphism problem.

EDIT: Cross-posted on mathOverflow

If I understood well the question, this is an attempt to prove that your problem is $GI$-complete.

Given two graphs $G_1, G_2$ connect all the nodes of $G_1$ to a new node $x$ and all the nodes of $G_2$ to a new node $y$. Then connect $x$ and $y$ with a path of new nodes: $ x_1, x_2, ... x_k,\; z\;, y_k, ...,y_2, y_1$ (there is an odd number of nodes between $x$ and $y$, and $z$ is the central node).

Now you can pick some pairs of nodes at the two endpoints: $(x,y),(x_1,y_1),(x_2,y_2),...$. In this way you end up with an instance of your problem that has a solution if and only if the two original graphs are isomorphic.


MAX 1 in 2 SAT Algorithm The maximum satisfiability problem (Max-Sat) is the problem of finding the maximum number of clauses that can be satisified in a Boolean satisfiability instance. The exactly 1 in 2 Sat problem asks, given a set of clauses each with two literals, is there a set of literals such that each clause has exactly one literal from this set.

The Complexity of Making Unique Choices: Approximating 1-in-k SAT by Guruswami and Trevisan gives a method for approximating Max 1 in 2 Sat. They state monotone (no negated literals) Max 1 in 2 Sat "admits an e-approximation in polynomial time".

I would like to find an exact algorithm for the Max monotone 1 in 2 Sat problem.

A monotone 1-in-2 clause demands that the two variables have different values. Thus, you can model the problem as a graph problem, with one vertex per variable which is to be colored black or white, and an edge for a clause indicating the colors need to be different. Thus, the question is to make the graph bipartite by deleting a minimum number of edges. This is the MaxCut or Edge Bipartization problem. It is NP-hard.

For Edge Bipartization, there is an algorithm that runs fast when few edges need to be deleted. I wrote an implementation for a slightly more general problem described here (source code).


Reducing #SAT to MAJ-SAT I once read in a paper: "given an algorithm for Majority-SAT, one can solve #SAT with $O(n)$ calls to the algorithm."
What is the approach to this?

Emil Jeřábek's construction [Gill 1977, Simon 1975] works indeed. Assume the formula $A$ has the propositional variables $x = \langle x_1,..,x_n \rangle$ and $y$ is some fresh variable. We can then construct $B$ as a formula $(y \rightarrow A) \wedge (\neg y \rightarrow C)$ whereby the formula $C$ needs to be further specified.
For the formula $C$ we assume the threshold given binary as $s = \langle s_1,..,s_n \rangle$. We can encode the arithmetic comparison $s \leq x$ in binary form, which is the lexicographic order union equality: $\langle s_j,..,s_n \rangle \leq \langle x_j,..,x_n \rangle  := (\neg s_j \wedge x_j) \vee ((s_j \leftrightarrow x_j) \wedge \langle s_{j+1},..,s_n \rangle \leq \langle x_{j+1},..,x_n \rangle)$ for $j<n$ and $(s_n \leq x_n) := (s_n \rightarrow x_n)$ otherwise.
So the formula $C$ will be just $s \leq x$. Now we have for the count of $B$:
$$|B| = |A| + |C| = |A| + 2^n-s$$
And therefore for the majority of $B$:
$$|B| \geq 2^n  \Leftrightarrow |A| \geq s$$
Since $\langle 0,..,0 \rangle \leq \langle x_j,..,x_n \rangle$ is trivially true, we can even construct $C$ gradually via binary search, and thus determine $|A| = s$ by calling $n$-times the majority oracle.


Some problems about arrow's theorem and social choice I'm just started lecture myself about arrow's theorem. There are some problems which make me confused.

ARROW'S THEOREM: Any constitution that respects transitivity, independence of irrelevant alternatives, and unanimity is a dictatorship.

This is a kind of statement from john Geanakoplos' paper.

I think unanimity+transitivity and independence of irrelevant alternatives are equivalent. For example:

voter A: a>b>c>d
voter B: a>c>b>d
voter C: a>d>c>b

So we can conclude that everybody prefers a to b just according to unanimity and transitivity. And I think this conclusion implies independence of irrelevant alternatives. So if I drop the constraint of independence of irrelevant alternatives, Is this still right?

Unanimity and transitivity do no imply IIA.

For example, consider the Borda-count voting mechanism. There is an example of the violation of IIA here.


Is "normalized distance" (as per Li & Vitanyi, Kolmogorov Complexity) a reasonable thing? In "The Similarity Metric" (Li, Vitanyi, et. al) they define a normalized distance (or similarity distance) as a function $\Omega \times \Omega \to [0,1]$ which is both symmetric and satisfies the density requirement for every $x \in \Omega$ and every constant $c \in [0,1]$:

$\displaystyle |\left \{ y : d(x,y) \leq c \right \}| < 2^{cK(x)+1}$

They give a somewhat convoluted example of a normalized version of the Hamming distance which satisfies this definition, and they prove that their normalized information distance satisfies this definition as well.

It is not at all clear to me that this definition represents a wide variety of "distance" measurements. Their conclusion is that because the normalized information distance is universal in this class of metrics, it is philosophically universal in all metrics we care about. But it's not even obvious to me that Euclidean distance (restricted to $\left \{0,1\right \}^n$) can be modified to satisfy this definition. That's not even close to mentioning distance measures for, say, language sentiment or other distances used in applications.

It would be great if we could say, for instance, that every computable metric has a normalized version which satisfies this definition. Is this known? If not, what is known?

The distance should be upper semicomputable. For instance the Hamming distance or Euclidean distance as such is not. One has to turn them into a version that satisfies the requirement above. Read the paper closer.


Non-uniform version for the whole polynomial hierarchy The non-uniform versions of P, NP and coNP are P/poly, NP/poly and coNP/poly.
Similarly, we can define a non-uniform version for each level in the PH.

For example: $\Sigma_2$/poly consists of problems of the form $\{x : \exists y \forall z \; C(x,y,z)\}$, where C is a circuit of polynomial size that may vary depending on the length of the input string $x$, and $y,z$ also have lengths polynomial in $x$.

Doing this for all levels of PH, we get a non-uniform version PH/poly.

QUESTIONS:  Is there anything known about this hierarchy? Does it collapse? Or is there another name for it in the literature?

Well, sure, we know things. I think this is a pretty standard nomenclature for it. This hierarchy collapses if and only if $\mathsf{PH}$ does, exercise:

For one direction, modify the proof of Karp-Lipton to show that if $\mathsf{NP} \subseteq \mathsf{coNP}/poly$ then $\mathsf{PH}$ collapses, and observe that this result relativizes
For the other direction, see the comments by Kaveh below.


Photo of «Introduction to automata…» by Hopcroft and Ullman '79 cover? Where can I get the photo of “Introduction to automata theory, languages and computation” by Hopcroft and Ullman '79 (first edition) cover in order to be able to read all the phrases placed on the cover? Obviously the ones that gave me Google.Images (from Wikipedia, Amazon and others) do not allow this.

Solved:
http://mmcs.sfedu.ru/~ulysses/Pics/Hopcroft-Ullman-79-cover.jpg

Update: High resolution cover can be found here. (via Artem)

A: Pushdown Automata
B: Regular Expressions
C: Context Free Languages
D: Finite Automata
E: Mathematical Truth
F: NP-Complete Problems
G: Turing Machines
H: Time/Space Complexity


When are all facets rank facets? (for independence system polyhedra) Consider an independence system $(E,\mathcal{I})$, and the corresponding polytope:

$P(E,\mathcal{I}):=\operatorname{conv.hull}\{ x^S ~|~S\in \mathcal{I}\}$

where $x^S \in \{0,1\}^E$ denotes the characteristic vector of $S$. A rank inequality has the form $\sum_{i \in S} x_i \le r(S)$, where $S\subseteq E$ and $r(S):=\max\{ |A| : A \subseteq S,~ A \in \mathcal{I}  \}$. Let's say that the nonnegativity bounds $-x_i \le 0,~i \in E$ are trivial.

(1) When is it true that all nontrivial facets of $P(E,\mathcal{I})$ come from rank inequalities?

It is known, for example, that if $(E,\mathcal{I})$ is a matroid, or the intersection of two matroids, then all nontrivial facets of $P(E,\mathcal{I})$ come from rank inequalities.

(2) Does the converse hold, i.e., if all nontrivial facets of $P(E,\mathcal{I})$ come from rank inequalities, then $(E,\mathcal{I})$ can be written as the intersection of two matroids?

On (1): The case of stable sets in graphs may clarify the situation (a stable set of a graph is a set of pairwise non-adjacent vertices). For each graph $G$, let $\mathcal{S}(G)$ be the set of stable sets of $G$.

The graphs $G$ for which the non-trivial facets of $P(V(G),\mathcal{S}(G))$ (i.e the stable polytope) are all rank-facets are called rank-perfect graphs (see Wagler). They include line graphs (by Edmonds' matching polytope theorem), perfect graphs, series-parallel graphs and more. Wheels with an even number of at least 6 vertices provide a basic example of non-rank-perfection.

To my knowledge, no characterization of rank-perfect graphs is known, and the problem of their recognition may be difficult. Pêcher and Wagler have several partial results on rank-perfect webs. By contrast, Wagler showed that the complements of webs are all rank-perfect.

On (2): the answer is negative as shows the following example. Let $G$ be the claw (i.e the complete bipartite graph $K_{1,3}$). It is well-known that since $G$ is bipartite, the non-trivial facets of $P(V(G),\mathcal{S}(G))$ are the edge-inequalities and hence are rank-facets.

Now, suppose by contradiction that $\mathcal{S}(G)$ is the set of common independent sets of two matroids. Using the weak circuit axiom of matroids in each matroid (that is, for each distinct circuits $C_1$ and $C_2$ of a matroid $M$ and each $e\in C_1\cap C_2$, there is a circuit in $(C_1\cup C_2)-e$), it is straightforward to check that a clique of size 2 must belong to $\mathcal{S}(G)$: a contradiction.

The same argument shows an example with more vertices but no claw: the circuit with 5 vertices.


A variant of linear programming Consider this "variant" of linear programming:

Notation: $\max\{ x_1, \cdots, x_n \}$ denotes the maximal number among $x_1, \cdots, x_n$;

minimize $\sum a_i x_i$

such that       $\max\{x_i\mid i\in J_k\}=b_k$ where $1\leq k\leq m$ and $J_k\subseteq \{1, \cdots, n\}$

For example:

minimize $0.1 x_1+ 0.2x_2 +0.3x_3+0.4 x_4$

such that  $\max\{x_1, x_4\}=0.7$ and $\max\{x_1, x_2, x_3\}=0.5$

What's the complexity of  solving this problem? Can it be reduced to linear programming? Is there any efficient approach? Or is there any deep theory behind this problem?

Many thanks.

(This following is just my comment above migrated into solution form).

We construct a Karp reduction from Vertex Cover into your problem. Given a graph $G = (V,E)$ in which we want to find the size of a minimum vertex cover, construct the following program

minimize $\sum x_i$

subject to

$\max \left\{x_i, x_j\right\} = 1$ for $(x_i,x_j) \in E$
$x_i \geq 0$ for all $i \in \{1, 2, \cdots, |V|\}$.

This is just an instance of your linear programming variant, with $\vec a = \vec b = 1$ and $\mathcal{J} = \left\{\{u,v\} | (u,v) \in E\right\}$ along with your assumption from the comments that all variables are positive (which, as @AustinBuchanan and @SureshVenkat point out, is important).

It's easy to see that each vertex cover satisfies (1), and that anything that satisfies (1) and (2) can be transformed into a vertex cover by decreasing all variables until they hit $1$ or $0$ (whichever comes first). Thus, the two problems have the same objective value (enough to show NP-hardness), and in fact such a program immediately reveals the optimal vertex cover itself.


Fastest way to find an s-t min-cut from an s-t max-flow? Ford-Fulkerson can find sparse s-t flows in time linear in the size of the flow and number of nodes if the edges have unit capacity.

How could I use a sparse s-t flow to find an s-t min-cut in time proportional to the size of the flow and the number of my nodes, for the sparse/low-volume max-flow case?

If you don't use the flow per se, but use the Ford-Fulkerson algorithm (or some version, like Edmonds-Karp), you can get both the max-flow and the min-cut directly as a result. When looking for augmenting paths, you do a traversal, in which you use some form of queue of as-yet-unvisited nodes (in the Edmonds-Karp version, you use BFS, which means a FIFO queue). In the last iteration, you can't reach $t$ from $s$ (this is the termination criterion, after all). At this point, the set of nodes you reached forms the $s$-part of the cut, while the nodes you didn't reach form the $t$-part.

The leaf nodes of your traversal tree form the “fringe” of the $s$-part, while the nodes in your traversal queue form the fringe of the $t$-part, and what you want is the set of edges from the $s$-fringe to the $t$-fringe. This can also easily be maintained during traversal: Just add an edge to the cut when it is examined, and leads to an unvisited node, and remove it if it is traversed (so its target becomes visited). Then, once Ford-Fulkerson is finished, you'll have your min-cut (or, rather, one of them) right there. The running time will be (asymptotically) identical to Ford-Fulkerson (or Edmonds-Karp or whatever version you're using), which should give you what you were looking for.


Smallest axis-aligned box that contains $k$ points Input: A set of $n$ points in $\mathbb{R}^3$, and an integer $k \le n$.

Output: The smallest volume axis-aligned bounding box that contains at least $k$ of these $n$ points.

I'm wondering if any algorithms are known for this problem.  The best I could think of was $O(n^5)$ time, loosely as follows: brute-force over all possible upper and lower bounds for two of the three dimensions; for each of these $O(n^4)$ possibilities, we can solve the corresponding $1$-dimensional version of the problem in $O(n)$ time using a sliding window algorithm.

For $n$ points there are $O(n^3)$ empty boxes, see introduction of this paper http://www.cs.uwm.edu/faculty/ad/maximal.pdf. One can compute these boxes in roughly this time (see intro for refs).

For your problem, take a random sample of points, where every point is picked with porbability $1/k$. Such a random sample has size (in expectation) $n/k$ [and for the sake of contradiction assume it is]. There are $O((n/k)^3)$ empty boxes having points from $R$ on their sides, by the above. For each such box, use an orthogonal range searching data-structure to compute how many points exactly it contains. Repeat this process $O(k^6 \log n)$ times. With high probability, one of the boxes you tried is the desired box.

Overall, the running time of this is $O((n/k)^3 * k^6 * polylog n) = O(n^3 k^3 \log^{O(1)} n )$.

To see why this work, consider the optimal box. It has 6 points of P on its boundary. The probability that the random sample pick these six points, and none of the points inside the box is at least $\frac{1}{k^6} ( 1-1/k)^{k-6} \approx 1/k^6 = p$. Thus, if you repeat the process $O( (1/p) \log n)$ times, with high probabilty one of the random samples would induce the desired box as an empty box.

Since $\Theta(n^3)$ is tight for the number of empty boxes (see intro the above paper for relevant refs), it seems unlikely that a significnatly faster algorithm is possible.

[In the ref I gave, they mention that [17] provides an algorithm that enumerates all maximal empty boxes among point in 3d in $O(n^3 \log^2 n)$ time, which is the black box you need for the above.]


How does one determine if a mixed bipartite quantum state is entangled or not? My question is based on the structure of the NP-hardness proof in section 6 (page 17) of this paper, http://arxiv.org/pdf/quant-ph/0303055v1.pdf

Mathematically one can think of being given a positive semi-definite linear map $\rho : \mathbb{C}^n \otimes \mathbb{C}^m \rightarrow   \mathbb{C}^n \otimes \mathbb{C}^m$ such that its trace is $1$ and one wants to determine if there exists some $k$ (column) vectors $x_i \in \mathbb{C}^n$ and another $k$ (column) vectors $y_i \in \mathbb{C}^m$ such that $\rho = \sum_{i=1}^{k} x_i x_i ^{\dagger} \otimes y_i y_i^{\dagger}$

If I understand right then this linked paper is proving the decision version of the above question to be NP-hard. (please correct me if my reading is wrong!)

But I am curious to know as to what would be even a brute-force algorithm to solve this! (in my limited experience for all NP-hard questions there is a trivial brute force solution that is always obvious - but not here!)

[Expanding the questions formulated in the comments]

Trivially it seems that there is no hope of being able to check this unless one allows for some finite precision error. But if with such a discretization the question is redefined then is the corresponding decision question still NP-Hard?
So is there a difference between the decision question that is being shown to be NP-Hard and the actual entanglement question that needs to be solved?

EDIT [$4^{th}$ August 2015]

I found this presentation by Aram Harrow which explains many of the issues that I was trying to get to but couldn't explain properly : http://simons.berkeley.edu/talks/aram-harrow-2014-09-25 (he explains pretty much this exact same question inside his lecture!)

In http://arxiv.org/pdf/quant-ph/0303055v1.pdf, it is shown that the weak membership problem for the set of separable states is NP-hard. As you can see in Definition 6.2 (page 18), this amounts to deciding if a state has a separable decomposition up to accuracy $\delta$.

If you want to convert this to a search problem, you can thus do so by using a $\delta$-net on the set of all separable decompositions and doing an exhaustive search.  Note that the maximal number of terms required in such a decomposition is bounded by $(d_Ad_B)^2$ (where $d_A$ and $d_B$ are the dimensions of the two systems).

In particular, such a decomposition to accuracy $\delta$ can be used as a proof for weak membership in the set of separable states, proving that the problem is in NP.

Note that the problem clearly remains NP-hard for any higher accuracy (i.e. any accuracy which increases with the problem size).  On the other hand, since any separable decomposition with $N$ digits of accuracy can be verified in $\mathrm{poly}(N)$ time, the problem remains inside NP (and thus NP-complete) even with an exponential precision.


any relation/ overlap between small world graphs, scale free graphs, and expander graphs? small world graphs (eg Watts-Strogatz model & others) and scale free graphs are a relatively recently discovered graph type via mainly empirical analysis of large real-world graphs (eg via Big Data techniques/ datamining etc). they have since been found to be quite ubiquitous/ longstanding in many diverse graphs related to nature and human constructions (eg biology/genes, social networks, man-made networks eg WWW/ internet/ telecommunication/ electrical grids, airport connectivity, etc).

in contrast expander graphs are far older and were invented mainly as a theoretical device in math/(T)CS however have since found very broad/ widespread/ key application. am looking for eg refs/ surveys/ overviews on their interrelation.

  what are the relations between the following (eg is there any overlap for some parameters)

  small world networks
  scale free graphs
  expander graphs

There are lots of overlaps between small world and scale-free, but I think much less so between those two and expanders.

The terms "small world" and "scale-free" are often used informally, but formal definitions are  often along the lines of:

Small-world means short average (or maximum) path length (typically $O(\log n)$, with $n$ vertices) and highly clustered (meaning that for any vertex $v$, the fraction of pairs of neighbors of $v$ which are adjacent is high)
Scale-free is often taken to mean that the degree distribution follows some variant of a power-law (e.g. power-law with cutoff, etc.), but more generally/informally is used to mean that the degree distribution is long-tailed, in contrast to, say, Erdos-Renyi random graphs which have a degree distribution that is exponentially concentrated around its mean.

Expander, of course, has a formal definition that is almost 100% standardized.

Expanders by their nature have logarithmic diameter, similar to small-world networks. Beyond that, however, as far as I know there is little overlap between the concepts.

In practice, expanders are often bounded-degree or even regular of bounded degree, whereas "real-world" graphs typically have a long-tailed degree distribution, with a small (but surprisingly large - e.g. not exponentially small) number of high-degree "hubs" (as they are usually called). Furthermore, scale-free graphs (almost by definition, depending on your definition) have a large number of vertices of very low degree - in most "real-world" graphs there are a large number of vertices of degree 1 or 2. This makes real-world graphs very unlike expanders, in that it is very easy to disconnect real-world graphs by removal of targeted edges, whereas expanders are by their nature highly connected. (Real-world graphs often also have the property that removal of random edges is very bad at disconnecting them.)

I'm sure there is something to be said about the use of spectral techniques for things like community detection, etc. in real-world networks, and from that viewpoint there may or may not be a little more overlap with expanders, but I'm not an expert in that area (maybe we can get Mark Newman to join cstheory.SE to comment...)


Delaunay triangulation when some triangles have been pre-specified? I have an implementation of the Bowyer-Watson algorithm for Delaunay triangulation which works well -- given a set of 2D points, it computes a set of triangles to fill the areas between the points.

Recently I was requested to fulfill a new requirement -- the ability for the user to explicitly specify one or more triangles in advance, and have the result of the algorithm include those triangles (as well as "filling out" the rest of the graph around those triangles, as usual).

AFAICT the Bowyer-Watson algorithm doesn't lend itself to handling this well -- is there some trick by which I could make it work?  Or if not, is there some other triangulation algorithm or approach that would be appropriate here?

Just insert sufficient number of points along the edges of the triangle you want - if you insert enough points, the edges of the triangle you want would be the union of edges of the triangulation. It is not pretty but it would work. This the basic idea behind many of the constrained triangulation meshing algorithms. Here is a nice paper on the topic, which contains more information:

https://people.eecs.berkeley.edu/~jrs/papers/2dj.pdf


The complexity of sampling (approximately) the Fourier transform of a Boolean function One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P.

Here and below when I talk about sampling the Fourier transform I mean choosing x according to $|\hat f(x)|^2$. (Normalized if necessary and approximately).

Can we describe the complexity class, that we can call P-FOURIER SAMPLING, of approximate sampling Boolean functions of P? Are there problems which are complete for this class?

Given a class X of Boolean functions what can be said about the the computational complexity, that we can refer to as SAMPLING-X of approximating sampling the Fourier transform of functions in X. (I suppose that if X is BQP then X-SAMPLING is still within the power of quantum computers.)

What are the examples of X where SAMPLING-X is in P? Are there interesting examples where SAMPLING-X is NP-hard?

There are several variants of this problem that can also be interesting.
On the Fourier side, rather than approximate-sample we can talk about a decision problem enabled (probabilistically) by approximate sampling. On the primal side, we can start with a class X of probability distributions and ask what is the relation between the ability to approximately sample a distribution D in X and approximately sample the (normalized) Fourier transform.

In short, what is known about this question.

Update: Martin Schwarz pointed out that if all the Fourier coefficients themselves are concentrated only on a polynomial number of entries then it is possible in BPP to approximate these large coefficients (and thus also to approximately sample.) This goes back to Goldreich-Levin, and Kushilevitz-Mansour. Are there interesting classes of functions where there is a probabilistic polynomial algorithm for approximately sampling the Fourier side, where the Fourier coefficients are spread over more than polynomially many coefficients?

Added Later: Let me mention a few concrete problems.

1) How hard is it to approximately sample the Fourier transform of Boolean functions in P.

a) One question that Scott Aaronson mentioned in a comment below is to show that this is not in BPP. Or something weaker along the lines that if this task is in BPP some collapse is happening.  (Scot Conjectures that this is the case.)

b) Another question is to show that this task is hard with respect to some quantum-based complexity class. E.g, to show that if you can perform this task you can solve decision problems in BPP assisted with log-depth quantum computers, or something like that.

2) What are classes of Boolean functions such that approximately sampling their Fourler transform is in P. What we know is that this is the case when the Fourier coefficients are concentrated on polynomial many coefficients, but this seems very restricted.

3) Is there some complexity class X high up in the PH that an X-machine can approximately sample the Fourier transform of every function that an X-machine can compute.

4) I was especially interested in the problem of sampling the Fourier transform of the crossing event for percolation on an n by n hexagonal grid.

The Kushilevitz-Mansour algorithm in learning theory establishes, that whenever $\hat{f}(x)$ is approximately sparse, i.e. there are only $O(poly(n))$-many large Fourier coefficients of absolute value $\Omega(1/poly(n))$, then we can find their locations and approximate their complex values in $\sf{BPP}$. Of course you can also efficiently sample from that list. To be precise, Kushilevitz-Mansour only talked about Fourier transforms over $\mathbb{Z}_2$, but generalization to FTs over general finite Abelian groups (see e.g. Akavia's thesis) are known.

As an application of this to quantum computing, one can show that the output state of quantum circuits structured in blocks of Hadamard-Toffoli-Hadamard gates can be efficiently approximated given the promise that the output state written in the computational basis is approximately sparse (see my QIP'2010 poster here, and the pre-print here). If the sparsity assumption is dropped, we could simulate Simon's algorithm (or Shor's), which is of exactly that structure, contradicting the $\Omega(2^{n/2})$ query lower-bound for Simon's problem.


Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm Roughly speaking, in Ruppert's Delaunay Triangulation refinement algorithm, so called encroached edges are split until no more encroached edges remain.

The algorithm specifies splitting the edges at their midpoint (except in the case of small input angles where concentric circular shells are suggested. This question is unrelated to these cases.)

In certain domains, given a segment, there are points on the segment that I would prefer to split on that are not necessarily the midpoints (unrelated to the concentric shell trick). These points are chosen based on some domain specific underlying data (considerations beyond the graph structure the algorithm is aware of).

What are the implications of splitting on non-midpoints?
What needs to be taken into consideration when selecting among several non-midpoint candidates?
Does splitting on non-midpoints affect any of the convergence properties
of the algorithm?

Another way to ask this is: Are there split points that are better (by some interesting measures) than the a-priori selected midpoints?

Alper Ungor did some nice work related to this issues of how do Delaunay refinement with alternative points. See his paper:

A. Ungor. Off-centers: A new type of Steiner points for computing size-optimal guaranteed-quality Delaunay triangulations. Computational
Geometry: Theory and Applications (CGTA), 42(2): 109--118, 2009.


Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$? I need to quickly evaluate $a^{b^c} \mod n$ where $c$ is pretty big. Using the usual repeated squaring trick, this can be performed in $O(\log(b^c)) = O(c)$ time. In my problem, $c$ is huge, (say, $> 10^{40}$), making this method unappealing. Also, you don't have access to the factorization of $n$, or to $\phi(n)$, so no clever tricks there. Are there any algorithms which run sublinear in $c$? What if I let you pick whatever special values of $a, b, c$ you like, subject to the constraint that none are zero or $\pm 1$, and also $c$ must be above some threshold $M$?

There are essentially only two algorithms that I'm aware of:

Use repeated-squaring, along the lines you mentioned.
Factor $n$ using a state-of-the-art algorithm, then use the Chinese remainder thoerem.  If $p$ is prime, you can compute $a^{b^c} \bmod p$ efficiently by computing $b^c \bmod p-1$ using fast exponentiation, call the result $d$, then computing $a^d \bmod p$.  If $n$ is a product of primes, you can combine the results using the Chinese remainder theorem.

There is believed to be no efficient algorithm for this problem that is faster than these schemes.  I don't know of any proof of that fact, but this assumption is used as a hardness assumption for one scheme in the literature on timelock cryptography (for the special case where $b=2$), and I don't think any faster algorithms are known.

Of course if you let me pick a value of $a$ that has small order modulo $n$, this will be easy.  As another example, if $n$ has a small prime factor $p$ and $a= 0 \pmod{n/p}$, the problem is also trivial.  There are probably multiple special cases that trivialize the problem, but they're probably not very interesting.  If $n$ is a product of two large primes and $a,b,c$ are chosen randomly, the odds of hitting those special cases should be negligibly small.


Algorithm for finding the largest subgraph without a directed triangle I would like to find the largest set of vertices in a directed graph. This set should not contain a cycle with exactly three vertices. Cycles with less vertices aren't possible with the given graphs; larger cycles can be in the set.

Do you know an algorithm for that?

The problem of finding a maximum set with no induced directed triangles is NP-complete via a reduction from maximum independent set.

Let G=(V,E) be an undirected graph and k be an integer, for which we wish to know whether there is an independent set of at least k vertices. Let |V|=n. From G construct a directed graph G'=(V',A'), where V' consists of the disjoint union of V and n additional vertices. For each undirected edge in G create two directed edges between the same vertices in G'. In addition, connect each of the n additional vertices in G' by edges in both directions to the vertices in V, but do not add edges between any two of the n additional vertices.

Then, a triangle-free set of vertices in G' consists either of a subset of V only (with at most n vertices) or it contains some vertices in the set of additional vertices together with an independent set of vertices in G. Therefore, there exists a triangle-free set of size n+k in G' iff there exists an independent set of size k in G.

However, this reduction produces many 2-cycles, so it leaves open the possibility that the problem might be easier in the case that the input graph has no 2-cycles, which you say is the case for your inputs. Unfortunately this special case is still hard: a more complicated reduction based on the same idea shows that the problem remains NP-complete even for 2-cycle-free graphs. In the more complicated reduction, add mn additional vertices rather than simply n. Replace each undirected edge in G by a directed edge, oriented arbitrarily. For each directed edge uv connecting two vertices of V, make n additional vertices in V', each of them connected to u and v to form a directed triangle. Then the resulting graph has mn+k vertices in a triangle-free set iff the original graph has k vertices in an independent set.


Using decision version of TSP to solve optimization version Given an oracle for solving the decision version of TSP, how would I use this to solve the optimization version of TSP.

This is not a homework assignment, but of general interest. I have been trying to find a place with examples of these types of reductions.

I'm not sure if we should be answering such questions, since it is at the level of a homework question, and not a research level question. So instead I'll just give a hint to the OP so the OP can figure out the answer with some effort. (Other posters may choose to give out the explicit solution if they wish, of course.)

The concept you refer to, i.e., reducing the search problem (or optimization problem) to the decision problem, is called self-reducibility. It is known that all NP-complete problems, and some others like Graph Isomorphism have this property. See this powerpoint presentation on self-reducibility. It explains in detail how SAT, GI and NP-complete problems in general can be shown to be self-reducible.

If you read those notes and understand those examples, you should be able to do the same for TSP using similar ideas.  Hope that helps.


Complexity of counting matchings in a bipartite graph I might be missing something obvious but I can't find references about the complexity of counting matchings (not perfect matchings) in bipartite graphs. Here is the formal problem:

Input: a bipartite graph $G = (U, V, E)$ with $E \subseteq U \times V$
Output: the number of matchings of $G$, where a matchings is a subset $F \subseteq E$ such that there is no $v \in U \sqcup V$ that occurs in two edges of $F$.

What is the complexity of this problem? Is it #P-hard?

It is well-known that counting perfect matchings on bipartite graphs is #P-hard, and it is known that counting matchings of arbitrary graphs (or even planar 3-regular graphs) is #P-hard by this paper, but I didn't find anything about counting non-perfect matchings on bipartite graphs.

The problem of counting such "imperfect" matchings in bipartite graphs is #P-complete.
This has been proved by Les Valiant himself, on page 415 of the paper

  Leslie G. Valiant
  The Complexity of Enumeration and Reliability Problems
  SIAM J. Comput., 8(3), 410–421


How to calculate machine learning time for binary classification? I want to calculate the training and testing time for binary classification. How to calculate that if a given database D has A attributes and T records. Please any one help me?
or how to calculate the time complexity for binary classifier?

By "time" do you mean the number of examples or the computation required to construct a classifier? If the former, the key quantity is the VC-dimension of the hypothesis class (i.e., collection of all classifiers you are willing to consider). The latter is strongly dependent on the representation (i.e., how you "view" the classifier in terms of algorithms and data structures) and in many cases can be NP-hard.


What is the role of "universe" types in intuitionistic type theory? According to the Wikipedia article on intuitionsitic type theory:

  The universe types allow proofs to be written about all the types created with the other type constructors. Every term in the universe type $U_0$ can be mapped to a type created with any combination of $0, 1, 2, \Sigma, \Pi, =$, and the inductive type constructor.

Would you please explain and elaborate further on how the universe types allow proofs to be written about other types?

In ordinary set theory one can write statements about all sets using the universal quantifier "$\forall x$" to have $x$ range over all sets.

In type theory without universes there is nothing that allows you to make a type that refers to all types. For example, the statement

  "For all types $A$ and $B$, $A \times B$ and $B \times A$ are equivalent types."

is not a judgement in type theory. It is a meta-statement in which $A$ and $B$ are schematic symbols. In order to express it as a judgement in type theory, we need something else. One solution is to have a universe (and another to have polymorphism a la System $F$). With a universe $U$, we can use "$\prod_{A : U}$" to make a product type that ranges over "for all types $A$ (in the universe $U$)", inside type theory. For instance, the type
$$\prod_{A : U} \prod_{B : U} (A \times B \simeq B \times A),$$
where $X \simeq Y$ is the type of equivalences from $X$ to $Y$, is how one would express the above statement using types.


Is this vertex ordering optimization NP-Hard? Could you help me to prove that the following problem is NP-hard?

Problem. Given an undirected graph $G=(V,E)$, find an ordering of the nodes such that $\sum\limits_{v\in V}|succ(v)|\times|pred(v)|$ is minimum.

Given an ordering on the nodes and a node $v\in V$, $pred(v)$ (resp. $succ(v)$) denotes the set of neighbors of $v$ with lower (resp. higher) ordering.

Consider your problem restricted to 3-regular graphs. Consider some ordering of the vertices. Define a split vertex to be a vertex $v$ such that both $succ(v)$ and $pred(v)$ are non-empty and define a non-split vertex to be any other vertex. Notice that in a 3-regular graph, the value of $|succ(v)| \times |pred(v)|$ is $0$ if $v$ is a non-split vertex and is $2$ otherwise.

Thus, $\sum\limits_{v\in V}|succ(v)|\times|pred(v)| = 2n_{\text{split}}$ where $n_{\text{split}}$ is the number of split vertices.

Therefore, in 3-regular graphs, solving your problem (minimizing the summation) is equivalent to choosing an ordering so as to minimize the number of split vertices.

The following theorem tells us that solving your problem in 3-regular graph $G$ is equivalent to solving Max Cut in $G$. Therefore, since Max Cut in 3-regular graphs is NP-hard, so is your problem.

Theorem If $G = (V, E)$ is a 3-regular graph with $n$ vertices then there exists an ordering of the vertices such that the number of split vertices is at most $k$ if and only if $G$ has a cut of size at least $\frac{3}{2}n - k$.

First direction

First, suppose there exists on ordering of the vertices such that the number of split vertices is at most $k$. Then we partition $V$ into two sets $A$ and $B$ as follows:

Place all non-split vertices (under the ordering) into $A$ and $B$ by putting the vertices with 3 successors into $A$ and the vertices with 3 predecessors into $B$.
Tentatively add all split vertices (under the ordering) into $A$.
Repeat steps 4 and 5 until step 4 fails:
Identify a split vertex $v$ that has more neighbors in its current set ($A$ or $B$) than in the other
Move $v$ to the other set

The partition of $V$ into $A$ and $B$ is a cut, and each occurrence of steps 4 and 5 increases the size of that cut, so this procedure will terminate. Below we compute the size of the resulting cut.

Notice also that each split-vertex $v$ in $A$ (or $B$) has at most one neighbor in $A$ (or $B$) because otherwise this vertex would have been identified in step 4 at the final iteration of the loop. Thus, the number of edges incident on split vertices that are within $A$ or within $B$ is bounded above by the number of split vertices (which we know is at most $k$).

Next consider any edge $(u, v)$ that is not incident on a split vertex. This edge must then be between two non-split vertices. Suppose wlog that $u$ is earlier than $v$ in the ordering. Then since $u$ is a non-split vertex with a successor, it must be the case that $u$ actually has 3 successors, and similarly $v$ must have 3 predecessors. We can conclude from this that $u$ is placed in $A$ and $v$ is placed in $B$, and therefore that $(u, v)$ is not an edge within $A$ or within $B$.

Thus, we conclude that the overall number of edges within $A$ or within $B$ is at most $k$. Then the size of the cut (i.e., the number of edges not within $A$ and not within $B$) is at least $|E| - k = \frac{3}{2}n - k$.

Second direction

Now suppose there exists a cut of size at least $\frac{3}{2}n - k$. Suppose this cut partitions $V$ into sets $A$ and $B$. Then we construct an ordering of the vertices in $V$ by putting the vertices in $A$ first and the vertices in $B$ later. We claim that the number of split vertices under this ordering is at most $k$.

Consider any edge incident on a vertex in $A$. If this edge is $(u, v)$ with $u \in A$ and $v \in B$ then $v$ is a successor of $u$ since all vertices in $B$ are after all vertices in $A$. Thus, edges between $A$ and $B$ do not contribute any predecessors to any vertices in $A$. The only other possible edge incident on a vertex in $A$ is an edge within $A$. Such an edge contributes a predecessor to exactly one of its endpoints. Thus, the total over all $v \in A$ of the number of predecessors of $v$ is at most the number of edges within $A$, and so the number of vertices in $A$ with a predecessor is at most the number of edges within $A$. Since every split-vertex in $A$ is a vertex in $A$ with a predecessor, the number of split-vertices in $A$ is at most the number of edges within $A$.

Analogous logic can be used to show that the number of split-vertices in $B$ is at most the number of edges within $B$. Then the total number of split vertices under this ordering is at most the number of edges within $A$ or within $B$. Since the cut has at least $\frac{3}{2}n - k = |E| - k$ edges between $A$ and $B$, it must have at most $k$ edges within $A$ or within $B$. We conclude that the number of split vertices under the constructed ordering is at most $k$.


Status of PP-completeness of MAJ3SAT SHORT QUESTION: Is MAJ-3CNF a PP-complete problem under many-one reductions?

LONGER VERSION:
It is well-known that MAJSAT (deciding whether the majority of assignments of propositional sentence satisfy the sentence) is PP-complete under many-one reductions and #SAT is #P-complete under parsimonious reductions. It is also apparent that #3CNF (that is, #SAT restricted to 3-CNF formulas) is #P-complete, because the Cook-Levin reduction is parsimonious and produces a 3-CNF (this reduction is actually used in Papadimitriou's book to show #P-completeness of #SAT).

It seems that a similar argument should prove that MAJ-3CNF is PP-complete under many-one reductions (MAJ-kCNF is MAJSAT restricted to kCNF formulas; that is each clause has k literals).

However, in a presentation by Bailey, Dalmau and Kolaitis, "Phase Transitions of PP-Complete Satisfiability Problems", the authors mention that "MAJ3SAT is not known to be PP-Complete" (presentation at https://users.soe.ucsc.edu/~kolaitis/talks/ppphase4.ppt). This sentence does not seem to appear in their related papers, only in their presentations.

Questions: Can the proof that #3CNF is #P-complete be indeed adapted to prove that MAJ3CNF is PP-complete? Given the statement by Bailey et al., it seems not; if the proof does not carry, then: Is there a proof that MAJ-3CNF is PP-complete? If not, is there some intuition as to the difference between PP and #P with respect to this result?

SHORT ANSWER:
It is unknown whether $\mathsf{MAJ3CNF}$ is a $\mathsf{PP}$-complete problem under many-one reductions.

LONG ANSWER:
First of all, you refer to Bailey, Dalmau and Kolaitis, and their work on "Phase Transitions of $\mathsf{PP}$-complete Satisfiability Problems" in your question. Let me quote them:

'It is also worth noting that, although $\mathsf{MAJORITY \ SAT}$ is  $\mathsf{PP}$-complete, it is not known whether there is an integer $k \geq 3$, such that $\mathsf{MAJORITY}$ $\mathsf{kSAT}$ is $\mathsf{PP}$-complete.'

[http://www.sciencedirect.com/science/article/pii/S0166218X06004665 ]

It is, indeed, correct that Cook-Levin reduction is parsimonious and produces a 3CNF from a given CNF. As $\mathsf{\#CNF}$ is $\mathsf{\#P}$-complete, it immediately follows that $\mathsf{\#3CNF}$ is also $\mathsf{\#P}$-complete under parsimonious reductions. However, as already pointed in a comment, parsimonious reductions do not preserve majority. These reductions introduce auxiliary variables to reduce the size of the clauses, but in turn, these auxiliary variables increase the total number of assignments. For instance, consider the 4CNF which consists of a single clause:

$
\phi = (x_1 \vee x_2 \vee x_3 \vee x_4)
$

which is transformed into

$
\phi'=(x_1 \vee x_2 \vee y) \wedge (y \leftrightarrow (x_3 \vee x_4))
$

using the auxiliary variable $y$ and finally to the 3CNF

$
\psi= (x_1 \vee x_2 \vee y) \wedge (\neg y \vee x_3 \vee x_4) \wedge (y \vee \neg x_3 ) \wedge (y \vee \neg x_4).
$

This transformation clearly preserves the model count, but it is easy to see that the majority is not preserved. $\phi$ has 15 satisfying assignments out of 16 assignments whereas $\psi$ has 15 satisfying assignments out of 32 assignments. In the former, majority satisfiability holds whereas in the latter  majority satisfiability does not hold.

Therefore, NO, the proof that #3CNF is $\mathsf{\#P}$-complete can not be adapted to prove that $\mathsf{MAJ3CNF}$ is $\mathsf{PP}$-complete? It remains open whether $\mathsf{MAJ3CNF}$ is a $\mathsf{PP}$-complete problem under many-one reductions.

$\mathsf{MAJ3CNF}$ does not give much of an insight between the differences of $\mathsf{\#P}$ and $\mathsf{PP}$. Actually decision decision variant of $\mathsf{\#3CNF}$, say $\mathsf{D\#3CNF}$, is defined as follows: given a CNF $\phi$ and a number $m \geq 0$, decide whether $\phi$ has at least $m$ satisfying assignments. Note that for $\mathsf{D\#3CNF}$, we do not care about majority. Thus, we can transform any CNF into 3CNF using a parsimonous reduction, which proves that $\mathsf{D\#3CNF}$ is $\mathsf{PP}$-complete under many-one reductions. $\mathsf{MAJ3CNF}$ is simply a different problem than $\mathsf{D\#3CNF}$.


Looking for learning resources I am an undergraduate student of Computer Science and am very interested in learning the theoretical part of it all.

Unfortunately, none of the subjects we have in our UG program give us an insight of theoretical part of Computer Science.
We do have the subjects Automata and Graph Theory, but our syllabus is very limited.

I have been looking for resources to learn the theory of computer science from the base up, for quite some time now.
I have already tried reading papers, completed MOOCs.

Somehow, I am always dissatisfied with the material. It is either too complicated (I don't even understand the notation used) or too trivial (teaching bits and bytes).

Could someone please provide me with some resources to learn theoretical computer science.
If possible, sort it in the order in which I should read it, so that the majority of prerequisites of the nth entry in the list, are covered in the preceding n-1 entries.

Please keep in mind:

I am really interested in learning it.
I have a decent background in programming, and have worked with several programming languages.
This is not a What videos/papers/books should everyone watch/read question. I am simply looking for some introductory resources, which are neither too obvious, nor too complicated.

I have had 3 semesters of College level Maths.
Also, I have studied the material provided by ocw.mit.edu, for the courses: 18.03, 18.062J and 18.400J mentioned at http://math.mit.edu/academics/undergrad/major/course18C/

Thanks a lot.

Of course, plenty of introductory resources are available and it is impossible to be objective here. So what follows is merely my biased choice.

I would definitely start with reading something on algorithms and on discrete mathematics (possibly in parallel). Here, I would recommend the following books:

Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein
The Design and Analysis of Computer Algorithms, by Aho, Hopcroft and Ullman
Invitation to Discrete Mathematics, by Matoušek and Nešetřil

The first book mentioned is one of the most widely known resources on algorithms, suitable as an introductory resource. The second book is little bit older and more theoretical, however imho still valuable. The third book is (in my opinion) an excellent and readable introduction to various parts of discrete mathematics.

Later, I would recommend to focus on formal languages and automata theory. Here, my choice is the following book:

Introduction to Automata Theory, Languages, and Computation, by Hopcroft Ullman and Motwani

You might also like to consult the Sipser's book mentioned in one of the comments.

Of course, if you have some background, there may not be a need for you to thoroughly study these textbooks. However, it is imho necessary to have a stable grounding in the above mentioned subjects before proceeding any further. Thus, it may be sensible for you to consult the above mentioned resources and focus on the material that you find new and/or interesting.

After mastering these preliminaries, there are plenty of choices where to continue. In my opinion, you should definitely study some complexity theory. Here, I would recommend the following book:

Computational Complexity, by Papadimitriou

You also might be interested in some slightly more advanced (or, let us say, intermediate) mathematical methods used in the analysis of algorithms. Here, the following resource is considered to be classic:

Concrete Mathematics, by Graham, Knuth and Patashnik

Some basics of optimization (especially linear programming) are a must for computer scientists. Here, I would recommend the following gentle introduction:

Understanding and Using Linear Programming, by Matoušek and Gärtner

A well written (and not very demanding) introduction to randomized algorithms is the following:

Design and Analysis of Randomized Algorithms, by Hromkovič

Finally, some nice books on advanced algorithms and/or computation theory include:

The Design and Analysis of Algorithms, by Kozen
Theory of Computation, by Kozen
Algorithmics for Hard Problems, by Hromkovič
Complexity and Approximation, by Ausiello et al.
Randomized Algorithms, by Motwani and Raghavan

However, I would suggest reading these only after thoroughly mastering those mentioned above.

This is not a complete list, however. Many other excellent resources are available. The selection I have made is based on my personal bias. Moreover, I have included only resources focused on the "algorithmic part" of theoretical computer science. That is, the selection I have made is not only incomplete, but also very narrow.

And I have to mention that learning some more advanced math would be very helpful for you. My general advice is: the more mathematics you know, the better. It is more and more obvious that there is not any mathematics absolutely irrelevant to computer science.


Any fast algorithm for minimum cost feedback arc set problem? In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set.

If each edge is associated with a weight $w$, the minimum cost feedback arc set problem is to find a $F$ such that $W(F)$ is minimum.

It is well-known that minimum feedback arc set problem is NP-hard, and so does minimum cost feedback arc set problem. I wonder if anyone knows any approximate algorithm that performs well, and any properties of the weight function that can yield a fast solver.

Daniel Apon linked to the conference version of my paper. I suggest the draft journal version instead: http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf .
On tournament graphs some experimental work suggests that local search does quite well. See Anke van Zuylen and Frans Schalekampf's recent ALENEX paper: http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf .
If the weights satisfy either "probability constraints" or "triangle inequalities" there's a constant-factor approximation algorithm based on quicksort. See Ailon, Charikar and Newman's recent JACM paper.
Can you tell us a bit more about what sorts of instances you have in mind and whether you're looking for something that works well in practice or in theory?


Which areas of computer science have lots of overlap with physics? I'm an undergrad in computer science but I've always loved physics and its ability to constantly amaze and surprise us about our world. I am wondering if there are areas in graduate level computer science that one can get into which involve a lot of work on physics. The one I know of that is talked a lot about is Quantum computing. I've also heard of information theory, which involves the study of thermodynamics. Which other ones are there?

[The following is more an extended comment with pointers than a real answer.]

If you were in France, a good answer would be combinatorial physics.  I say "if you were in France" because, for reasons that escape me but that must be mostly historical, in France combinatorics is considered part of theoretical computer science :-)  In the rest of the world, combinatorics is considered to be a branch of mathematics, so I guess it is more correct to say that combinatorial physics is about interactions between physics and discrete math, rather than CS.

Anyway, in my lab (which is a CS lab) there's a research group which focuses on several aspects of combinatorics, in particular combinatorial physics.  This is by no means the only example in France of a combinatorics group in a CS lab whose research overlaps with physics; another example off the top of my head is this one in Bordeaux. Some of the members of these groups are theoretical physicists.

The "official" recognition of combinatorial physics as a research field of its own is very recent, as you may read in this blog post, which contains some pointers and basic info about it.  Computer science is explicitly mentioned a couple of times, although maybe not exactly in the sense you would expect, but I am sure that my colleagues from those research group would be able to give you more precise answers.  Maybe you can start checking out their web pages for additional info.


Orlicz norm of random variable and variance In probability and statistics Orlicz norms are frequently used in concentration inequalities. For example, for Bernstein's inequality, we have versions for sub-exponential random variables using $\psi_1$-norm and for bounded random variables using variance.

My first thought is that the $\psi_1$-norm version is more general, and includes the case of bounded random variables as a special case. However, an example of Bernoulli random variable with probability $1/n$ being $1$ and $1-1/n$ being $0$ suggests this is not true. For $n$ very large, the variance is roughly of the order $1/n$. However, its $\psi_1$-norm is roughly of the order  ${1}/{\log n}$.

This suggests that $\psi_1$-norm (or similarly, $\psi_2$-norm) is actually very loose for very biased Bernoulli random variables. Is there any other notions like $\psi_1$-norm that can accommodate biased Bernoulli random variables?

The Kearns-Saul inequality states that if $X\sim Ber(p)$ then
$$ E[\exp(t(X-p))] = (1-p)e^{-tp}+pe^{t(1-p)} \le \exp\left(\frac{1-2p}{4\log((1-p)/p)}t^2\right).$$

The subgaussian constant $\frac{1-2p}{4\log((1-p)/p)}$ is optimal.
See http://ecp.ejpecp.org/article/view/2359 and especially the appendix in http://www.jmlr.org/papers/v16/berend15a.html for background and a slick proof.

The K-S inequality is a considerable improvement over Hoeffding and Bernstein for very small/large $p$.


Complex analysis in theoretical computer science There are many applications of real analysis in theoretical computer science, covering property testing, communication complexity, PAC learning, and many other fields of research. However, I can't think of any result in TCS that relies on complex analysis (outside of quantum computing, where complex numbers are intrinsic in the model). Does anyone has an example of a classical TCS result that uses complex analysis?

It's not a single problem, but the entire field of analytic combinatorics (see the book by Flajolet and Sedgewick) explores how to analyze the combinatorial complexity of counting structures (or even algorithm running times) by writing down an appropriate generating function and analyzing the structure of the complex solutions.


Finding an answer key given tests and scores Consider multiple students taking a multiple-choice tests. The test has $q$ questions, and each question has $m$ choices. ($q$ can be large, but $m$ is rather small.) You are given $n$ tests, complete with all answer choices and their grades (number of questions correct). Find the set of answers keys which produce these scores.

I and a few friends had a go at it, but I was wondering if there was an efficient algorithm to solve this.

Solving this problem is NP-hard. In particular, even deciding whether there exists an answer key consistent with the given answer choices and scores is NP-complete. We can prove this by reduction from 1-in-3 SAT.

Given a 1-in-3 SAT formula with $c$ clauses and $n$ variables, we construct an instance of your problem with $n$ questions, each with 3 choices, and $c+1$ sample answer/grade pairs.

For each variable $x$, one of the questions is "what is the value of boolean variable $x$?" and the three possible answers are "True", "False", and "17".

One student answers every question with the answer $17$ and gets a score of zero. The remaining students are each assigned a clause. For every positive literal $x$ occurring in the clause, the student answers the question about $x$ with the answer "True". For every negative literal $\neg x$ occurring in the clause, the student answers the question about $x$ with the answer "False". For every other question, the student answers $17$. Every such student gets a score of one.

An answer key must correspond with an assignment of binary values to the variables (since no question has $17$ as the correct answer as shown by the fact that the student who always answered $17$ got zero points). Furthermore, there must be exactly one true literal in each clause under this assignment in order for the answer key to match the scores given to the students. In other words, the satisfying assignments to the input 1-in-3 SAT formula are in a bijection with the answer keys consistent with the student scores.

Clearly then, deciding whether an answer key consistent with the student scores exists is NP-hard. Similar arguments can be made to show that for example counting answer keys is #P-complete.


XOR-SAT to Horn-SAT reduction Horn-SAT (conjunction of Horn clauses) is P-complete and XOR-SAT (conjunction of xor clauses) is in P. This means that there is a reduction from XOR-SAT to Horn-SAT weaker than a polynomial reduction.
I am looking for such a reduction; can anyone help me? Thank you.

XOR-SAT is in $\mathsf{L}^{\oplus\mathsf{L}} = \oplus\mathsf{L}$ (because it can be viewed as the feasibility of a system of linear equations mod 2 hence by Allender-Beals-Ogihara). Thus using a division free determinant algorithm (e.g. by Mahajan-Vinay) we can reduce it to the problem of iterated matrix product over $F_2$ by a finegrained reduction (certainly Log-space will work but something finer like Dlogtime projection should also). Now design an $\mathsf{NC}^2$ circuit to multiply together several matrices over $F_2$ using $\{\vee,\wedge,\neg\}$-gates. Thus composing the above reductions with the reduction from CVP to HornSAT gives the final reduction.