How easy is it to switch the area of research in CS (going from M.Tech to PhD)? I'm faced with a rather tough dilemma :-

I had completed M.Tech in CS 2 years back, completing my dissertation in the field of VLSI Testing. While I liked my work, I don't wish to go back to pursue my PhD in that - I've been strongly wanting to pursue a theoretical course (in approximation/online algorithms) as means for obtaining my doctoral degree.

However, since I've had no research experience in TCS(Theoretical Computer Science), I'm afraid that would hurt my chances of getting admission to a reasonably good school in the US - whereas, the research experience in VLSI (as well as the LORs from my adviser/committee members, who are well known in the field of VLSI) would have helped me get into a good program (but my enthusiasm in that field has already petered out).

That's why, I wanted to hear from people who have successfully migrated from their initial research field (in UG/MS level) and have been able to embark on a completely different field for their PhD - how did you explain the reason for your shift in the SOP, whether that affected their chances in getting into a top school etc. Also, for any academics browsing the question, what would be your take on it - do you always prefer students who have a background matching your interests only ?

I recently served on the TCS grad admissions committee of MIT, and I can give you my angle on things: When I'm reading applications, what I'm looking for is excellent people who strongly want to pursue research in TCS. The combination of intrinsic ability and strong desire is, in my opinion, the best way to predict success.
After all, it is our job, once someone becomes a grad student, to help them transform their potential into actual achievements, through courses, advising, etc.

Here are some important points :

Before grad school is a very early stage to change fields. Many
people shift then. It's acceptable and expected.
In your application, explain your changing fields (so the readers understand why the rec letter writers are not from TCS, why you took lots of non-theory courses, etc). Talk about how you learned TCS, what appeals to you in TCS, demonstrate that you know the basics of the field.
If you have strong letters from your supervisors, it still counts for you, even if they are from a different field (strong = from a professor who knows you well and has great things to say about you).
If you have research experience (especially if there's some theoretical angle to it), it still counts for you, even if it's in a different field.
If you have good grades, it still counts for you, even if they are for courses from a different field. For TCS, math classes are important.


Canonical representation of Binary Decision Tree in Ptime? I am wondering whether there may exist a way to give a sort of "normal form" for binary decision trees (BDT) in a tractable way.

More precisely: a BDT is a tree with internal nodes labelled by boolean variables and leaves labelled by $0$ or $1$. A BDT represents a boolean function in the obvious way. Two BDT $A,B$ are equivalent ($A\sim B$) when they represent the same function.

Does there exist a function $f$ that inputs a BDT and turns it into some other data structure such that:

$f$ is in Ptime
$f(A)=f(B)$ if and only if $A\sim B$
$f$ has a pseudo-inverse $g$, that is $g(f(A))\sim A$, also in Ptime

For instance reduced ordered binary decision diagrams OBDD validate 2 and 3, but not 1 because with the wrong variable ordering the output might be of exponential size.

I have a feeling that this might not be possible, but have not found any evidence of that anywhere.

To comment further on Ricky Demer's suggestion:

This paper defines the $PEq$ (equivalence classes in Ptime) and $Ker$ (complete invariant in Ptime)  and CF (canonical form in Ptime) classes. They study various (unlikely) implications of $PEq=Ker$ and $Ker=CF$ but do not provide a definite answer to these questions.

Various negative answers (impossibility of 1&2, 1&2&3) to this question would provide separation results as $PEq\neq Ker$ or $Ker\neq CF$... which seems to be an open problem so far.

I think that assuming that $\mathsf{NP} \not \subseteq \mathsf{SUBEXP}$, such a canonical representation does not exist. Proof: Suppose such a canonical representation does exist. Then the function $A \mapsto g(f(A))$ can be computed in polynomial time, so in particular, $|g(f(A))|$ is $\text{poly}(|A|)$. But if we take $B$ to be a minimal BDT equivalent to $A$, then $g(f(A)) = g(f(B))$, so $|g(f(A))|$ is $\text{poly}(|B|)$. Such an approximation algorithm implies that $\mathsf{NP} \subseteq \mathsf{SUBEXP}$, according to an answer on another post, if I understand correctly.


Have these coloring games been solved? In the paper "On the complexity of some coloring games", Bodlaender gives some open questions about the complexity of deciding if player 1 or 2 has a winning strategy in some graph coloring games. Does anyone know if they have been solved?

1) In one game, two players take turns selecting one vertex in a graph and coloring it properly with a color from a fixed finite set. The loser is the first player who is unable to color a vertex. In Schaefer's paper it is shown to be pspace-complete with 1 color and Bodlaender shows it to be pspace-complete with 2 colors but gives no answer with more color. Is it still open?

2) In another variation, the vertices have numbers 1..n. On a player's turn he must properly color the vertex with the lowest number that has not yet been colored. Again, they are using colors from a fixed set and the loser is the first player who is unable to color his vertex. Bodlaender shows it to be pspace-complete for general graphs. He asks who wins on trees, is it known?

Thanks

The answer is yes, for the first game you list! This result was only established in 2019. Here is a link to the paper: Costa et al. 2019
Even more recently, some variants of the first game were proved to be PSPACE-complete. This result can be found here: Marcilon et al. 2019.


Do you know a shortest path algorithm for weighted graphs with hard time windows on the edges and waiting allowed? Title says it all. I have a weighted Graph G={V,E,ETW} where V is the node set, E the edge set and ETW is a set of edge time windows. A edge time window is a 3-Tuple (edge, starttime, endtime) with the meaning that in the intervall [starttime, endtime] the given edge is not available. The problem now is to find a shortest path from a start node to an end node in which it is allowed to wait at the nodes (to use a edge after it´s time window).

Does anybody know a algorithm for this problem? (and in the best case the paper in which the algorithm was published)

Greetings, Christoph

Unfortunately I am not aware of any complete and sound algorithm for solving this task. As far as I am aware, most techniques consist of Stochastic Local Search algorithms.

TSPTW (Traveling Salesman Problem with Time Windows) is a good example of your problem. For the particular case where constraints are not hard so that they result in a penalty, the best results have been derived with Ant Colony Optimization [1]. Another algorithm known as the Nested Rollout Policy Adaptation [2] has been used as well. Finally, Monte-carlo has been tried (I cite [3] but there are surely a number of references in this regard)

Hope this helps,

Bibliography

[1] Manuel López Ibáñez and Christian Blum, "Beam-ACO for the tranveling salesman problem with time windows", Computers & OR 37 (9), 1570--1583 (2010)

[2] T. Cazenave and F. Teytaud, "Application of the nested rollout policy adaptation algorithm to the traveling salesman problem with time windows", LION 6, Springer (2012)

[3] A. Rimmel, F. Teytaud, and T. Cazenave, "Optimization of the nested monte-carlo algorithm on the Traveling salesman problem with time windows", Applications of Evolutionary Computation, 501--510 (2011)


TSP with multiple visits Can you please suggest possible approaches for the following problem:

Find a path through graph vertices so that the distance (sum of edges weights) between two vertex $i$ occurrences would be no more than $D_i$. It is obviously infinite, so I want to have a generator for this path.

Thanks in advance.

This problem is PSPACE-complete even in the case in which the edge weights obey the triangle inequality. See

Hsi-Ming Ho, Joel Ouaknine, The Cyclic-Routing UAV Problem is PSPACE-Complete, FoSSaCS 2015


Applications of Quantum Walks? Can someone explain to me what real world applications could potentially benefit from the study of quantum random walks?

I have researched a fair amount on how quantum walks operate and their properties but I would like to know the end goal of studying them at a deep level? Is it simply for the sake of it in terms of mathematics or computer science, or are there actual real-world applications that can benefit from this research?

With the exception of cryptography applications like Shor's algorithm and quantum key distribution, I think engineering 'killer-apps' are not the norm for quantum computing, and nobody expects them to be. As such, quantum walks are a natural generalization of random walks and thus worth studying in their own right. However, to avoid side-stepping any longer, I can give you some motivation and past successes.
First, just like with classical random walks, we can use quantum random walks in the design of algorithms. This can give us complexity seperations in the quantum query model by looking at glued trees (two binary trees attached leaf-to-leaf via a random permutation); there is no classical randomized algorithm (walk or otherwise) to get from one root to the other in a polynomial number of queries, but the quantum walk does it in polynomial number of queries:

Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., & Spielman, D. A. (2003). Exponential algorithmic speedup by a quantum walk. In SToC (pp. 59-68). ACM.

Of course, this relies on this problem being a partial function, since for total-functions we know that exponential separations are not possible, and expect quadratic separation to be the best generally achievable result for quantum query complexity of total-functions. However, if you have a good classical Markov-chain based algorithm then we know that in many cases, the quantum version will have a quadratically faster hitting time, saturating the expected speed up:

Szegedy, M. (2004). Quantum speed-up of Markov chain based algorithms. In FoCS (pp. 32-41). IEEE.

Quantum walk approaches also resulted in optimal query algorithms for less "artificial" problems like element distinctness, where it is the best known algorithm:

Ambainis, A. (2007). Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1), 210-239.

In general, quantum walks are very powerful, and could also be used as models of universal computation:

Childs, A. M. (2009). Universal computation by quantum walk. Physical Review Letters, 102(18), 180501.
Childs, A. M., Gosset, D., & Webb, Z. (2013). Universal Computation by Multiparticle Quantum Walk. Science, 339(6121), 791-794.

If you want to take your applications outside of theoretical computer science and into the real-world of natural sciences, then you can also use quantum random walks just like classical ones: to model and understand certain natural processes. The paradigmatic example of this is for modeling photosynthesis:

Engel GS, Calhoun TR, Read EL, Ahn TK, Mancal T, Cheng YC et al. (2007). Evidence for wavelike energy transfer through quantum coherence in photosynthetic systems. Nature 446 (7137): 782–6.
Rebentrost, P., Mohseni, M., Kassal, I., Lloyd, S., & Aspuru-Guzik, A. (2009). Environment-assisted quantum transport. New Journal of Physics, 11(3), 033003.

In the above work it was shown (roughly) that after a photon hits the chlorophyll, it is transformed into an exciton which does a quantum random walk on the chlorophyll complex until it finds a binding site where it can share its energy to turn an ADP into ATP. A quantum random walk is required by nature, because the lifetime of the exciton is not sufficient for a classical random walk to have sufficient energy transfer. We could get speculative and combine the previous two observations to suggest a nature-inspired model of computation but there is no reason to believe it could be anything better than a toy due to the fast decoherence times.


Can real-time deterministic multicounter automata recognize the marked palindrome language? Consider the marked palindrome language which is defined as MPAL=$\{ w\#w^r | w \in \{a,b\}^* \}$.

It is easy to recognize MPAL using only a single stack.

My question is whether MPAL can be recognized by a real-time deterministic multicounter automaton.

I realized that in Fischer, Meyer, and Rosenberg (1968) Theorem 1.3, it is proven that "The language of marked palindrome is not recognizable by any one-way $k-CM$ which operates in time less than $T(n) = 2^{(n/2k)}$."

The same result also appears in Petersen (2009).


Do Delaunay triangulations on the sphere maximize the minimum angle? Delaunay triangulations in the plane maximize the minimum angle in a triangle. Does the same hold true for the Delaunay triangulation of points on the sphere ? (here the "angle" is the local angle in a neighborhood around the vertex at the apex).

Inspired by but unrelated to this question on Math.SE.

FIRST ARGUMENT: This was my first answer. Note that this argument is wrong. See my second argument below.

I don't think it's true. The reason that it works in the plane is that in a circle, the inscribed angle subtended by a chord is one half the corresponding central angle. Thus, if we have a triangle with a small angle, any points that would make a larger angle with the opposite edge are inside the empty Delaunay circle, and so aren't one of the points in the configuration we are finding a triangulation of.

Now, suppose you have a Delaunay triangulation on the sphere. Place a point at the center of the sphere, and project all the pionts onto a plane. The edges of the triangles (great circles on the sphere) are all taken to line segments. But the circles giving the empty ball property are taken to ellipses, and so if there's a point outside the projected ellipse but inside the circumcircle of the triangle, this point would make a larger angle with the edge.

EDIT:

Wait a minute. This answer is completely wrong, because the central projection does not preserve angles. I still think the conjecture is wrong, because I have a much more complicated argument that the theorem about inscribed angles does not hold on the sphere. Here's the argument:

SECOND ARGUMENT:

The reason this holds in the plane is that the inscribed angle subtended by a chord is one half the corresponding central angle. That holds because, in the diagram below, we have
$$ CYX_2 = \frac{1}{2} (\pi - X_2 C Y)$$ and $$C Y X_1 = \frac{1}{2} (\pi - X_1 C Y).$$ Subtracting, we get $$ X_1 Y X_2 = \frac{1}{2} X_1 C X_2.$$

Now, in spherical geometry, we get
$$CYX_2 = \frac{1}{2} ( \pi - X_2CY + A(X_2CY) \,) $$
and
$$CYX_1 = \frac{1}{2} ( \pi - X_1CY + A(X_1CY) \,), $$
where $A(XYZ)$ means the area of triangle XYZ.
Subtracting, we get
$$ X_1 Y X_2 = \frac{1}{2} (X_1 C X_2 + A(X_2CY) - A(X_1CY)\,).$$

For the locus of points $Y$ making a constant angle $X_1YX_2$ to be a circle, we thus need that the difference of areas $A(X_2CY) - A(X_1CY)$ depends only on the arclength $X_1X_2$. However, this is incompatible with the observation that $A(XCY)$ is $0$ for $X$ diametrically opposite $Y$ and for $X=Y$, but grows to some maximum size in between.

Thus, the locus of points $Y$ with constant angle $X_1YX_2$ is not a circle. This means that for some triangle $X_1YX_2$ we can find a point $Y'$ outside the circumcircle of $X_1YX_2$ so the angle $X_1YX_2 < X_1 Y' X_2$. We can then use this to build a counterexample to the conjecture that Delaunay triangulations on the sphere maximize the minimum angle.


Is the counting version of 1-in-3 Sat #P-complete? In the paper "Hard Tiling Problems with Simple Tiles", Moore and Robson prove that Cubic Planar Positive 1-in-3 Sat in NP-complete by a reduction from Positive 1-in-3 Sat.

Cubic Planar Positive 1-in-3 Satisfiability
Instance: A boolean formula $B=(X,C)$ where $X$ is a set of variables, $C$ a set of 3-element subsets over $X$ (clauses), and graph of B is a cubic planar graph.
Question: Does there exist a truth assignment for $X$ such that each clause is $C$ has exactly one true variable?

(see the note of the https://cstheory.stackexchange.com/a/42605/47855 regarding terminology)

Then they prove that a particular tiling problem is NP-complete by a reduction from Cubic Planar Positive 1-in-3 Sat.
The following note is given after their reduction:

  While the reduction from this version of SAT to the tiling problem we gave in the previous section is parsimonious, this does not show that the counting problem is #P-complete, since we do not have such a result for Cubic Planar Positive 1-in-3 SAT. We leave this as an open problem for the reader.

This gave me the impression that the counting version of 1-in-3 Sat is indeed #P-complete, but I couldn't find any source claiming this. Is the counting version of 1-in-3 Sat #P-complete?

Yes, the counting version of 1-in-3 Sat is $\#P$-complete. This is stated in "Complexity of Generalized Satisfiability Counting Problems" (Example 3.1), the reference pointed out by Emil in the comment.

Note:
This leads us to the curious question: is the counting version of every NP-complete problem $\#P$-complete? The answers to this question (When does "X is NP-complete" imply "#X is #P-complete"?) suggest so!


Communication Complexity ...Classes? Discussion:

I've been spending some personal time lately learning various things in communication complexity. For instance, I've re-familiarized myself with the relevant chapter in Arora/Barak, started reading some papers, and ordered the book by Kushilevitz/Nisan. Intuitively, I want to contrast communication complexity with computational complexity. And in particular, I'm struck by the fact that computational complexity has developed into a rich theory of placing computational problems into complexity classes, some of which can be in turn (from one perspective, at least) envisioned in terms of complete problems for each given class. For instance, when explaining $NP$ to someone for the first time, it's hard to avoid comparisons to SAT or some other NP-complete problem.

By comparison, I've never heard anything of an analogous concept for communication complexity classes. There are many examples that I'm aware of, of problems "complete for a theorem." For instance, as a general framework, the authors might describe a given communication problem $P$ and then prove that a related theorem $T$ holds $iff$ the communication problem can be solved in $X$ or less bits (for some $X$ that depends on the specific theorem/problem pair in question). The terminology used then in literature is that $P$ is "complete" for $T$.

Further, there is a tantalizing line in the Arora/Barak communication complexity chapter draft (that seems to have been removed/tweaked in the final printing) that states "In general, one can consider communication protocols analogous to $NP$, $coNP$, $PH$ etc." However, I notice two important omissions:

 The "analogous" concept appears to be a manner of computing the communication complexity of solving a given protocol with access to different types of resources, but stops just short of defining proper communication complexity classes...
 Most of communication complexity seems to be relatively "low-level," in the sense that the overwhelming majority of results/theorems/etc. revolve around small-ish, specific, polynomial-sized values. This somewhat begs the question of why, say, $NEXP$ is interesting for computation but the analogous concept appears to be less interesting for communication. (Of course, I could just be at fault for simply being unaware of "higher-level" communication complexity concepts.)

Question(s):

Is there an analogous concept to computational complexity classes for communication complexity?

And:

If so, how does it compare to the "standard" notion of complexity classes? (e.g. are there natural limitations to "communication complexity classes" that cause them to inherently fall short of the full range of computational complexity classes?) If not, what's the "big picture" reason that classes are an interesting formalism for computational complexity but not for communication complexity?

It seems that you are looking for this paper: http://portal.acm.org/citation.cfm?id=1382439.1382962


Starting point for cache-oblivious algorithms? I'm interesting in learning more about cache-oblivious algorithms and data structures, but there are so many papers out there that I honestly don't know where to start.  I've found Prokup's original thesis on the subject, which seems like a good starting point, but if there's a simple and accessible introduction to the subject I'd much rather start there.  Is there a standard "go-to" reference on the subject?

Thanks!

I still find one of the original articles (I could also find it in Google Scholar) quite interesting and clear... in this case it is not extremely "scientific-y":

M. Frigo, C.E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS 99), p.285-297. 1999.

Also, here are Erik Demaine's video lectures on c-o algos, which are also very good.


Proofs on unconventional computing Are there any interesting proofs on unconventional computing? When reading on the topic I most often see soft analysis – like following paragraph from Wikipedia (Natural computing):

  Swarm intelligence,[12] sometimes referred to as collective
  intelligence, is defined as the problem solving behavior that emerges
  from the interaction of individual agents (e.g., bacteria, ants,
  termites, bees, spiders, fish, birds) which communicate with other
  agents by acting on their local environments.

Instead of soft analysis – are there any formal (and important) results in the topic?

A recent and interesting attempt to model flocking behavior is Bernard Chazelle's work (see the four most recent papers (as of Mar 2012). He's also running a summer school on computation and biology at the Institute for Advanced Science.


How efficiently can one find small subcovers for integer intervals? This question is inspired by one of my professors giving out

sequential lecture notes that have a significant amount of overlap :-).

What is known about the following problems?

Given a set of integer intervals whose union is an integer interval, find a subset

with the same union that minimizes the number of intervals in the subset.

Given a set of integer intervals whose union is an integer interval, find a subset with the

same union that minimizes the sum of the cardinalities of the intervals in the subset.

Let me restate the first problem:

Problem: Given a set of intervals $\mathcal{S} = \{ I_1, I_2,\ldots,I_n\}$,  minimize $|\mathcal{C}|$, where $ \mathcal{C} =\{ I_{j_1}, I_{j_2},\ldots,I_{j_k}\} \subseteq\mathcal{S} $ and
$ \bigcup_{l=1}^{n}I_l = \bigcup_{m=1}^{k}I_{j_m} $

Define: Graph $G(V,E)$, $V = \{v_1, v_2, \ldots, v_n ,s ,t \}$ where,

Vertex $v_j \in V$ denotes interval $I_j$.
Vertices $v_k, v_l$ have an edge between them if their corresponding intervals $I_k,\; I_l$ overlap.
Source vertex $s$ and $v_j$ have an edge between them if $v_j$'s corresponding interval $I_j$ contains the leftmost point of $\bigcup_{l=1}^{n}I_l $.
Similarly sink vertex $t$ and $v_j$ have an edge between them if $v_j$'s corresponding interval $I_j$ contains the rightmost point of $\bigcup_{l=1}^{n}I_l $.

Answer: The intervals corresponding to the vertices in the 'shortest vertex path' between $s$ and  $t$ gives the minimum set cover!

If I have understood your 2nd question correctly, it is nothing but the weighted 1-dimensional set cover problem.

Remark 1: The intervals $I_j$ considered above might possibly have non-integer end-points.

Remark 2: One can solve this problem using dynamic programming, which I think has "lower" complexity than the shortest path solution.

EDIT-1: For the ease of exposition, I have considered only closed intervals in the above problem.


Conflicting definitions regarding TM and Recursively Enumerable languages In Lewis's and Papadimitriou's book "Elements of the Theory of Computation" the transition table is a function $\delta: Q \setminus F \times \Gamma \rightarrow Q \times (\Gamma \cup \{L,R\})$. However, according to Wikipedia (and pretty much everywhere else) it's $\delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$. The difference is that in the first case you can't write and move at the same time.

In the same book, a language $L$ is recursively enumerable if there is a TM so that: $w \in L \iff$ the TM halts on $w$. Note that in this book the TM only has halting states. In wikipedia, halting states are actually also accepting states. I also came across TM definitions where there is a distinction between accepting and rejecting states. In these cases, the definition of a recursively enumerable language changes to "... the TM accepts $w$".

Now it's obvious that in both cases all definitions are obviously perfectly equivalent. I'd like to know which defintions have prevailed so that I can follow those.

I wouldn't say that one definition has "prevailed".  If you look at the literature and textbooks, you'll see a large variety of definitions.

Different definitions might be useful in different contexts.  For example, if you're actually trying to program up a TM (for whatever reason) then the more expressive they are, the easier to program.  On the other hand, if you're trying to prove a lower bound or uncomputability result, picking the weakest TM might make life easier.  And the busy beaver function, for example, is usually defined relative to a fairly weak model.

I'd just recommend you use any model you feel comfortable with and tell the reader of your paper that is what you are using.


Distributive expansion of CNF and implicants I am looking for references for the following theorems.

Theorem 1: Distributive expansion of a CNF formula $P_c$ (product of sums)
results in a DNF formula (sum of products) consisting of all prime
implicants for $P_c$. $P_c$ is called a Blake canonical form BCF.

Theorem 2: If we transform a disjunctive clause $C_d$ with $k$ literals to a
disjunctive clause of conjunctions $C_m$ by replacing each literal
$l_i, i = (1, ..., k)$ with the conjunction $(\neg l_1 \wedge
... \wedge \neg l_{i-1} \wedge l_i)$, then $C_m$ will be logically equivalent to $C_d$. The clause $C_m$ is called a
clause with maximized conflicts.

Distributive expansion of $C_m$ shows that it is logically
equivalent to the unmaximized clause $C_d$, $C_m = C_d$.

Theorem 3: Distributive expansion of a CNF formula with maximized conflicts
$P_m$ (product of sums of products), with simplification of
outermost clauses before innermost clauses, results in a DNF
formula $P_u$ (sum of products) defining a set of (not
necessarily prime) implicants $I_u$ for $P_m$. The
implicants from $I_u$ cover all possible solutions for
$P_m$.  The implicants $I_u$ are unique, in that no
implicant $M_i \in I_u$ covers the solutions of any other
implicant $M_j \in I_u, i \ne j$.

Motivation:

With the discussion in [BROWN] I have finally found the last
piece of the puzzle.

Obviously, the restrictions for syllogistic formulae --- namely
removal of duplicate literals and elimination of clauses with
contradictory literals --- have been loosened over time. However, this
seems to have been a process of ad hoc reasoning.

I am missing an exhaustive formal discussion of the
consequences. I.e., the set of logically equivalent DNFs
represented by their minimal form of a disjunction of "atomic"
literals and the influence on the resulting DNFs of partial
assignments, which always cover all possible solutions, albeit in
different ways.

In order to find out, whether I have to do all of that on my own,
I use theorem 3 to show, that besides the well-known Blake canonical
form BCF, other non-trivial DNFs of implicants with different
properties appear, when the input clauses are generalized from
CNF to allow non-syllogistic representations, namely the DNFs
from theorem 2. Since that also requires a different order of
evaluation which is highly non-intuitive to simplification
junkies, I assume that I am out of luck.

It can especially be shown that for selection problems in "direct
encoding" (Chapter 2, Handbook of Satisfiability), the input based on theorem 2 alone allows a CDCL solver to solve the problem with
significantly less decisions than with plain CNF. Small problems
(currently 40 variables, 171 clauses) are even solved earlier with the
generally less effective "direct encoding" than with the original CNF
encoding. Note, that there is actually never a set of implicants
generated in that case.

I have prepared a PDF with examples to illustrate the effects.

Theorem 1 is related to Blake canonical form.

The Wikipedia article refers to

Brown, Frank Markham, Boolean Reasoning: The Logic of Boolean Equations,

which in turn references

Canonical expressions in Boolean algebra. Ph.D. dissertation U (1937)).


Algorithm Suggestion for Scoring System - weighted solution I'm trying to validate a series of words that are provided by users. I'm trying to come up with a scoring system that will determine the likelihood that the series of words are indeed valid words.

Assume the following input:

xxx yyy zzz

The first thing I do is check each word individually against a database of words that I have. So, let's say that xxx was in the database, so we are 100% sure it's a valid word. Then let's say that yyy doesn't exist in the database, but a possible variation of its spelling exist (say yyyy). We don't give yyy a score of 100%, but maybe something lower (let's say 90%). Then zzz just doesn't exist at all in the database. So, zzz gets a score of 0%.

So we have something like this:

xxx = 100%
yyy = 90%
zzz = 0%

Assume further that the users are either going to either:

Provide a list of all valid words (most likely)
Provide a list of all invalid words (likely)
Provide a list of a mix of valid and invalid words (not likely)

As a whole, what is a good scoring system to determine a confidence score that xxx yyy zzz is a series of valid words? I'm not looking for anything too complex, but getting the average of the scores doesn't seem right. If some words in the list of words are valid, I think it increases the likelihood that the word not found in the database is an actual word also (it's just a limitation of the database that it doesn't contain that particular word).

NOTE: The input will generally be a minimum of 2 words (and mostly 2 words), but can be 3, 4, 5 (and maybe even more in some rare cases).

I don't think this question is related at all with approximation algorithms, or theoretical CS.

Please take the following as some free, non-exhaustive, thoughts on your question.

It seems to me that what you want is just the probability that a given sequence of words contains only valid words.

Let me assume that each word is chosen independently (which it isn't true).
Suppose we have $k$ words, call $\sigma_i$ the i-th of such words.
Call $A_i$ the event "$\sigma_i$ is a valid word" and $A$ the event "all words are valid".

Under this assumptions you have:
$$
P(A) = \prod_{i=1}^{k}P(A_i)
$$

so you only need to assign a probability to each word (and you've already given such a distribution in you question).
However you may want to apply some smoothing: if you set $P(A_i)=0$ for some $A_i$ then also $P(A)$ will be $0$ (if you are sure that a word is not valid, then then the whole phrase cannot be valid).

A bayesian approach only requires conditional independency. For example you can compare the following two quantities (and choose the highest):

$$
P(A | \sigma_1, \dots, \sigma_k) \propto  P(\sigma_1, \dots, \sigma_k | A) P(A) = \prod_{i=1}^{k}P(\sigma_i|A) P(A)
$$
$$
P(A^C | \sigma_1, \dots, \sigma_k) \propto  P(\sigma_1, \dots, \sigma_k | A^C) P(A^C) = \prod_{i=1}^{k}P(\sigma_i|A^C) (1 - P(A))
$$

where $P(\sigma_i|A)$ is the probability that the word $\sigma_i$ appears in a valid phrase, $P(\sigma_i|A^C)$ is the probability that $\sigma_i$ appears in an invalid phrase and and P(A) is the probability that a valid phrase shows up.

In the above we are just differentiating "valid" from "invalid" phrases. If you want to account for "completely valid", "completely invalid" and "mixed up" phrases you can do something similar.

You'll need to assign three probabilities to each word $\sigma_i$: $P(\sigma_i|valid)$, $P(\sigma_i|invalid)$, $P(\sigma_i|mixed)$ and three "a priori" probabilities, for example:

$P(valid) = 0.55$  (most likely)
$P(invalid) = 0.40$ (likely)
$P(mixed) = 0.05$ (not likely)


Sending people to lunch together with minimal repetition We have n people and split them up in groups of size x. Each group of x people goes to lunch together. Next time around when the groups are set up people who were in a group last time should not end up in a group together if avoidable. Ideally they also should go out with as few people from the time before that.

I thought about modelling this as a graph problem:
People are vertices $v \in V$ and going to lunch together creates a edge between those vertices. The edge has a weight on it that's higher the more recent the lunch happened. Now we want to create $\frac{|V|}{x}$ subgraphs with x vertices each and minimize the sum of the edges connecting the vertices in each subgraph.

Is there a name (lunching programmers ? ;-) ) and associated research for this problem? Or is there a way to map this to another known problem?

This is sometimes known as the Social Golfer problem (see also the Wolfram MathWorld page and this page from CSPlib). Probably the most famous instance of this problem is Kirkman's Schoolgirl problem.


Is it reasonable to allow the type of a λ/∀-bound variable to refer to itself? Usually, in Pure Type Systems, the type of a λ/∀-bound variable is only accessible on its body. That is, on λ (X : A) -> B, X is free inside A and bound in B. But what if X was also bound in A? The typing rules should be updated accordingly, i.e., instead of:

$$ \frac{Γ \vdash A : * \quad Γ, x : A \vdash B : *}{Γ \vdash ∀ (x : A) \rightarrow B : *}$$
$$ \frac{Γ \vdash f : ∀ (x : A) \rightarrow B \quad Γ \vdash a : A}{Γ \vdash f a : [a/x]B}$$

we'd have:

$$ \frac{Γ, x : A \vdash A : * \quad Γ, x : A \vdash B : *}{Γ \vdash ∀ (x : A) \rightarrow B : *}$$
$$ \frac{Γ \vdash f : ∀ (x : A) \rightarrow B \quad Γ \vdash a : [a/x]A}{Γ \vdash f a : [a/x]B}$$

In other words, on the ∀ (x : A) -> B case, in order to infer the type of A, we extend the context with x : A, which is possible, because we know the value of A. On the application case f a with f : ∀ (x : A) -> B, we substitute x by a in A before checking for equality. I have never seen such an approach, though. My question is: was this explored before? If so, is there a name for it so I can look up? If not, is there an obvious reason for it to be undesirable?

(The reason I initially asked this question is I've previously asked if it is possible to implement a halting definition of ind on the calculus of constructions with equi-recursion. I've noticed one can do so in a setting with mutually recursive definitions, as long as we also allow a λ/∀-bound variable to refer to itself on its type. Here is an example.)

I have not seen this in a dependently-typed setting, but a similar notion is fairly well-known in weaker systems (e.g. System F) with subtyping, under the term "F-bounded quantification". This pops up prominently in type systems for object-oriented programming languages, which typically are heavy on (equi-) type recursion. This notion was originally introduced by this paper.

A standard use case is expressing forms of "binary methods" that need to be covariant in their argument types. For example, in those languages you see interface types like

interface Ordered<T> { less(x : T) : Bool }

with subtypes like

class Int extends Ordered<Int> { ... }

and usage patterns

class Queue<T extends Ordered<T>> { ... }

or

sort<T extends Ordered<T>>(array : Array<T>) : Array<T>

and so on. In the more type-theoretical rendering of System F-sub with F-bounded quantification and records these could be expressed as

Ordered = λ(T <: Top). {less : T → Bool}
Int <: Ordered(Int)
Queue = λ(T <: Ordered(T)). {...}
sort : ∀(T <: Ordered(T)). Array(T) → Array(T)


determining if a matrix of linear forms represents a non-degenerate matrix Let $k$ be a field with $p$ elements. Consider the following computational problem

  Input: a natural number $n$,  $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots X_{nn}$.

  Problem: Is there an assignement of values to the variables $X_{ij}$ so that the matrix $M_{ij}$ is invertible?

${}$

  Question: What is known about algorithms for this problem?

As usually, let's assume the addition and multiplication in the field to have computational cost $1$.

The naive algorithm of checking each assignment of the variables $X_{ij}$ takes time bounded by a polynomial in $p^{n^2}$. I'd be interested to know if there is an improvement to polynomial in $p^n$ (or better).

The special case when each $M_{ij}$ is equal either to $0$ or to $X_{ij}$ is solved  by Emil Jeřábek on the mathoverflow thread linked to below.

This answer summarizes and expands my comments above:

1) If the size of the underlying field is large enough, then this problem has efficient randomized algorithms: You have to test whether the resulting determinant is nonzero as a polynomial. You can use the Schwartz-Zippel lemma for this. (Search for the keyword "Polynomial Identity testing"
for further algorithms/results.)

2) The question whether this problem can be derandomized is open.
Derandomizing it implies circuit lower bounds. See the work by Kabanets & Impagliazzo. (Comput. Complexity 13, 2004, http://www.cs.sfu.ca/~kabanets/Research/poly.html), the problem is called
SDIT (Symbolic Determinant Identity testing) in the paper.

3) Gurvits has a deterministic algorithm for some special cases of SDIT
(http://dx.doi.org/10.1145/780542.780545). He refers to SDIT as "Edmond's problem". (This item was provided by Joshua Grochow. I suggest that when
you want to upvote my answer, you should upvote any of his answers with probability 1/4 instead.)

4) Over finite fields (size is fixed), it is NP-complete. Over GF(2), you can just arithmetize a given formula in 3-CNF (that is, write it as an equivalent arithmetic formula)
and then use fact that you can write any arithmetic formula as a poly-size determinant (proven by Valiant, see also Bürgisser, Clausen, Shokrollahi,
Algebraic Complexity Theory, Chapter 21). Over other finite fields, you can start with appropriate CSPs instead of 3-SAT.


Consequences and state-of-the-art of NP ≠ ZPP? Consider the complexity classes $\mathsf{NP}$ and $\mathsf{ZPP}$. Whether the two classes are equal is an open question, but as far as I know, $\mathsf{NP} = \mathsf{ZPP}$ is not known to imply $\mathsf{P} = \mathsf{NP}$. For example, there are many inapproximability results depending on $\mathsf{NP} \neq \mathsf{ZPP}$, but what evidence do we have for believing they would indeed be not equal?

In other words, what would be the consequences of $\mathsf{NP} = \mathsf{ZPP}$? Is it safe to claim that likewise for $\mathsf{P}$ and $\mathsf{NP}$, many theorists also believe $\mathsf{NP}$ is not equal to $\mathsf{ZPP}$?

Yes, it is safe to claim that most theorists believe that $\mathsf{NP}$ is not equal to $\mathsf{ZPP}$ -- and that most theorists believe that $\mathsf{NP}$ is not equal to $\mathsf{BPP}$.

One consequence of $\mathsf{NP} = \mathsf{ZPP}$ is that computational cryptography is impossible.  This is described as the world Algorithmica in Impagliazzo's famous five worlds:

A Personal View of Average-Case Complexity.  Russell Impagliazzo.  1995 Complexity Conference. (A PDF version is here).

Note that as far as practical consequences go, Impagliazzo says it doesn't matter much whether we have $\mathsf{P} = \mathsf{NP}$ or $\mathsf{NP} \subseteq \mathsf{BPP}$ (he even calls the latter the "moral equivalent" of $\mathsf{P} = \mathsf{NP}$).

See also What if P = NP? for additional practical consequences (assuming the constants hidden by asymptotic notation are not too large).

I don't know whether there are any surprising implications for complexity classes.


Binary multiplication and parity convolution This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a better solution to the question from Knuth vol. 2, 3rd edition, page 420 than that given in the book.

"Can the multiplication of polynomials modulo 2 be facilitated by using the ordinary arithmetic operations on a binary computer, if coefficients are packed into computer words."

Knuth gives a reasonably straightforward reduction which expands the number of bits in the input by a log multiplicative factor in the worst case.  Can this log factor be reduced?

Sure, you can reduce it to a factor of 1, but probably at the cost of time. But to answer the question behind the question: multiplication of polynomials mod 2 is easier from a hardware point of view (no need to propagate carry bits), but multiplication of integers is an operation people consider essential, and so has direct support in ALUs and programming languages.


How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin? I have these two problems:

Problem 1 (Dual bin packing problem)

Instance: A set of $n$ items where each item $i$ has weight $w_i$. A set of $k$ bins where each bin has capacity $W$.

Question: Find the maximum number of items that can be packed into the $k$ bins such that each bin $j$ has a set of items of weights no more than $W$.

Problem 2 (Knapsack problem)

Instance: A set of $n$ items where each item $i$ has weight $w_i$. One bin of capacity $W$.

Question: Find the maximum number of items that can be packed into the bin such that it has a set of items of weights no more than $W$.

Now given a set of items $\{w_1, \ldots, w_n\}$ and a set of $k$ bins.

If we apply the following algorithm for dual bin packing problem :

S = set of items
for each bin j do
    Solve the knapsack problem on bin j and save the result on OPT[j]
    \\ OPT[j] is the set of items packed into bin j.
    Update S by removing the items in OPT[j]
    \\ S = S - OPT[j]
    if S is empty do
        break

How can the output of this algorithm compared to the optimal solution of the dual bin packing problem?

My attempt is:

Let us denote by $OPT_b$ the optimal value of problem 1. That is, $OPT_b$ is the maximum number of items that are packed into the $k$ bins. Moreover, let us denote by $OPT_j$ the optimal number of items that are packed into bin $j$ by solving problem 2 on bin $j$. That is $OPT_j$ is the optimal value of problem 2 when applied to bin $j$. In other words, the output of the algorithm, denoted $ALG$, is equal to $\sum_{j=1}^{k}OPT_j$.

We have
$$
OPT_b \geq ALG,
$$
because, otherwise, $ALG$ will be greater than $OPT_b$ which contradicts the optimality of $OPT_b$. But can we prove the other inequality?
More probably, it is not possible to obtain the other inequality. Hence, we can argue that it could be true, sometimes, that
$$
OPT_b > ALG.
$$

So can we give a bound on $ALG$ like $$ALG\geq \rho OPT_b,$$ for some $\rho$?

The "dual bin packing problem" is more commonly referred to as the Multiple Knapsack problem. One can show that $ALG \ge (1-1/e) OPT_b$ assuming an optimal algorithm for the Knapsack problem is used in each bin. If the bins are of different sizes then one can show that $ALG \ge OPT_b/2$ irrespective of the order in which the bins are processed. See Section 4 in the paper below for these results. http://epubs.siam.org/doi/abs/10.1137/S0097539700382820


$\mathsf{P}^\mathsf{BPP}$ vs $\mathsf{BPP}$ (Are they known to be equal) Is it known if $\mathsf{P}^\mathsf{BPP}= \mathsf{BPP}$ ?

It's clear that $\mathsf{BPP} \subseteq \mathsf{P}^\mathsf{BPP}$. Now, since $\mathsf{BPP}$ is closed under complementation, union, and intersection, it seems to provide evidence that $\mathsf{BPP} = \mathsf{P}^\mathsf{BPP}$. However, I can't prove this.

Yes, since BPP is low, but this is not a research level question.


compact context free expression for permutation This may sound like theoretically void question, because certainly permutation is expressible even on the lowest level of Chomsky hierarchy:

P -> a b c
  |  a c b
  |  b a c
  |  b c a
  |  c a b
  |  c b a

In practice, however, proposition that the only way to describe SQL syntax is permuting "where", "group by", "having" (and many more similar clauses in some SQL dialects) is silly.

Boolean grammars allow succinct expression for permutation

X -> a
   | b
   | c

Y ->
   | X

P -> X X X & - Y a Y a Y & - Y b Y b Y & - Y c Y c Y

but perhaps there is a way to do it in the context free realm too?

Using the method in this answer one can show that the smallest context-free grammar for all permutation of $n$ symbols has exponential size in $n$.


Probability of generating a desired permutation by random swaps I'm interested in the following problem.  We're given as input a "target permutation" $\sigma\in S_n$, as well as an ordered list of indices $i_1,\ldots,i_m\in [n-1]$.  Then, starting with the list $L=(1,2,\ldots,n)$ (i.e., the identity permutation), at each time step $t\in [m]$ we swap the $i_t^{th}$ element in $L$ with the $(i_t+1)^{st}$ element, with independent probability $1/2$.  Let $p$ be the probability that $\sigma$ is produced as output.

I'd like to know (any of) the following:

Is deciding whether $p>0$ an $NP$-complete problem?
Is calculating $p$ exactly $\#P$-complete?
What can we say about approximating $p$ to within a multiplicative constant?  Is there a PTAS for this?

The variant where the swaps don't need to be of adjacent elements is also of interest.

Note that it's not hard to reduce this problem to edge-disjoint paths (or to integer-valued multicommodity flow); what I don't know is a reduction in the other direction.

Update: OK, checking Garey & Johnson, their problem [MS6] ("Permutation Generation") is as follows.  Given as input a target permutation $\sigma\in S_n$, together with subsets $S_1,\ldots,S_m\in [n]$, decide whether $\sigma$ is expressible as a product $\tau_1 \cdots \tau_m$, where each $\tau_i$ acts trivially on all indices not in $S_i$.  Garey, Johnson, Miller, and Papadimitriou (behind a paywall, unfortunately) prove that this problem is $NP$-hard.

If the swaps don't need to be adjacent, then I believe this implies that deciding whether $p>0$ is also $NP$-hard.  The reduction is simply this: for each $S_1,S_2,\ldots$ in order, we'll offer a set of "candidate swaps" that corresponds to a complete sorting network on $S_i$ (i.e., capable of permuting $S_i$ arbitrarily, while acting trivially on everything else).  Then $\sigma$ will be expressible as $\tau_1 \cdots \tau_m$, if and only if it's reachable as a product of these swaps.

This still leaves open the "original" version (where the swaps are of adjacent elements only).  For the counting version (with arbitrary swaps), it of course strongly suggests that the problem should be $\#P$-complete.  In any case, it rules out a PTAS unless $P=NP$.

I think that whether p>0 can be decided in polynomial time.

The problem in question can be easily cast as the edge-disjoint paths problem, where the underlying graph is a planar graph consisting of m+1 layers each of which contains n vertices, plus m degree-4 vertices to represent the possible adjacent swaps.  Note that the planarity of this graph follows from the fact that we allow only adjacent swaps.

If I am not mistaken, this falls in the special case of the edge-disjoint paths problem solved by Okamura and Seymour [OS81].  In addition, Wagner and Weihe [WW95] give a linear-time algorithm for this case.

See also Goemans’ lecture notes [Goe12], which gives a nice exposition of the Okamura–Seymour theorem and the Wagner–Weihe algorithm.

References

[Goe12] Michel X. Goemans.  Lecture notes, 18.438 Advanced Combinatorial Optimization, Lecture 23.  Massachusetts Institute of Technology, Spring 2012.  http://math.mit.edu/~goemans/18438S12/lec23.pdf

[OS81] Haruko Okamura and Paul D. Seymour.  Multicommodity flows in planar graphs.  Journal of Combinatorial Theory, Series B, 31(1):75–81, August 1981.  http://dx.doi.org/10.1016/S0095-8956(81)80012-3

[WW95] Dorothea Wagner and Karsten Weihe.  A linear-time algorithm for edge-disjoint paths in planar graphs.  Combinatorica, 15(1):135–150, March 1995.  http://dx.doi.org/10.1007/BF01294465


Laying paths on a network using minimum number of links/edges Consider an undirected graph G(V,E), where each edge $e\in E$ has capacity $c(e)$.  Also given is a traffic matrix $T_{ij}$ representing the amount of traffic flowing from vertex $i$ to $j$.  The goal is to minimize the number of links required to support all traffic in $T_{ij}$ such that the total traffic traversing each link $e$ is less than $c(e)$.

Is there an equivalent problem in the literature?

thanks,
kwan

The problem you are asking is called capacitated network design. Typically each edge e also has a cost/weight w(e) and you want to minimize the weight/cost of the chosen edges such that the resulting graph supports the demands given by $T_{ij}$. The weighted version can be reduced to the unweighted version by replacing an edge of weight w(e) by a path of w(e) edges (this reduction is pseudo-polynomial). The problem is NP-Hard even when $T_{ij}$ is non-zero for a single pair and even here we don't quite understand the approximability.

See the following recent papers for more on this:

Minimum-Cost Network Design with (Dis)economies of Scale. IEEE FOCS 2010.
Approximability of Capacitated Network Design. IPCO 2011.


What is the complexity of checking equivalence of two boolean formulae without NOT symbol? Suppose I have two boolean formulae (propositions) $P_1$, and $P_2$ (can be assumed to be in CNF) over the same variables and such that there are no "NOT" symbols used.  I.e. only conjunction and disjunction are used but not negation.  Then what is the complexity of checking if $P_1$ and $P_2$ are equivalent (they are equivalent iff they agree on all inputs)?

By This answer, I know that if negation is allowed, this problem is co-NP complete.  It is also easy to see that if I simply wanted to check satisifiability for either proposition when negation is disallowed, I would have a linear time algorithm by simply setting all variables to true and checking if the proposition is true.

However, I am not sure what the complexity of checking equivalence in this case would be.  I could say that the two propositions are equivalent iff ($P_1 \wedge \neg P_2$) and ($P_2 \wedge \neg P_1$) are both unsatisfiable, but I can't use the linear time SAT algorithm above because now I have negation in these new propositions.

Can anyone help me figure out what the complexity of this problem is?

Much obliged!

Note that formulas using $\land$ and $\lor$ gates (and possibly the constants $0$ and $1$) are known as monotone.

The complexity of monotone formula equivalence depends on how complex formulas are allowed. Let me start with the related problem of implication (entailment) between two formulas $\phi\vdash\psi$, which is easier to classify. Note that $\phi$ and $\psi$ are equivalent iff $\phi\vdash\psi$ and $\psi\vdash\phi$.

Given monotone formulas $\phi$ and $\psi$, the problem of determining whether $\phi\vdash\psi$ is

in P for $\psi$ a CNF (even non-monotone). Indeed, we have $\phi\vdash\bigwedge_i\psi_i$ iff $\forall i\,(\phi\vdash\psi_i)$, and if $\psi_i$ is a clause, and $e_i$ the corresponding assignment that falsifies $\psi_i$ and makes all variables outside $\psi_i$ true, then
$$\phi\vdash\psi_i\iff e_i(\phi)=0.$$
For the right-to-left direction: if $e_i(\phi)=0$, and $e$ is any assignment such that $e(\psi_i)=0$, then $e\le e_i$, hence $e(\phi)=0$ using the monotonicity of $\phi$.
in P for $\phi$ a DNF (possibly non-monotone), by a dual argument.
coNP-complete for $\phi$ a 2-CNF and $\psi$ a 3-DNF (or dually: $\phi$ a 3-CNF and $\psi$ a 2-DNF), and a fortiori for any larger classes of formulas. Indeed, it is coNP-hard to check if a given 3-DNF is valid; we can write (in polynomial time) any 3-DNF in the form $\psi(\vec x,\neg\vec x)$ where $\psi$ is a monotone 3-DNF, and then
$$\vdash\psi(\vec x,\neg\vec x)\iff\bigwedge_i(x_i\lor y_i)\vdash\psi(\vec x,\vec y).$$
As above, the left-to-right direction follows from the monotonicity of $\psi$.

Now, back to equivalence. On the one hand, we have
$$\phi\equiv\psi\iff\phi\vdash\psi\text{ and }\psi\vdash\phi;$$
on the other hand,
$$\phi\vdash\psi\iff \phi\equiv(\phi\land\psi)\iff\psi\equiv(\phi\lor\psi).$$
Thus, we see that for monotone $\phi$ and $\psi$, the problem of determining if $\phi\equiv\psi$ is

in P for $\phi$ and $\psi$ CNF.
in P for $\phi$ and $\psi$ DNF.
coNP-complete for general monotone $\phi$ and $\psi$. It is enough to take $\phi$ a CNF, and $\psi$ a conjunction of a CNF and a DNF (which means $\psi$ can be written as a depth-3 formula with either $\bigwedge$ or $\bigvee$ as the top connective). Dually, it is enough to take $\phi$ a DNF, and $\psi$ a disjunction of a CNF and a DNF (whence again a depth-3 formula with either $\bigwedge$ or $\bigvee$ on top).

The only case left is the complexity of equivalence of a monotone CNF to a monotone DNF. This problem is interesting. As I learned in [4], it was proved to be solvable in quasipolynomial time $O(n^{\log n})$ by [3], and in coNP with only $O((\log n)^2)$ nondeterministic bits by [2,5]. Furthermore, when one of the formulas has bounded width, the problem is in P by [1,6], and even in L by [4].

References:

[1] T. Eiter, G. Gottlob: Identifying the minimal transversals of a hypergraph and related problems, SIAM Journal on Computing 24 (1995), no. 6, pp. 1278–1304, doi: 10.1137/S0097539793250299.

[2] T. Eiter, G. Gottlob, K. Makino: New results on monotone dualization and generating hypergraph transversals, SIAM Journal on Computing 32 (2003), no. 2, pp. 514–537, doi: 10.1137/S009753970240639X.

[3] M. L. Fredman, L. Khachiyan: On the complexity of dualization of monotone disjunctive normal forms, Journal of Algorithms 21 (1996), no. 3, pp. 618–628, doi: 10.1006/jagm.1996.0062.

[4] J. Goldsmith, M. Hagen, M. Mundhenk: Complexity of DNF minimization and isomorphism testing for monotone formulas, Information and Computation
206 (2008), no. 6, pp. 760–775, doi: 10.1016/j.ic.2008.03.002.

[5] D. J. Kavvadias, E. C. Stavropoulos: Monotone Boolean dualization is in $\mathrm{coNP}[\log^2n]$, Information Processing Letters 85 (2003), no. 1, pp. 1–6, doi: doi.org/10.1016/S0020-0190(02)00346-0.

[6] N. Mishra, L. Pitt: Generating all maximal independent sets of bounded-degree hypergraphs. In: Proceedings of the Tenth Annual Conference on Computational Learning Theory (COLT 1997), 1997, pp. 211–217, doi: 10.1145/267460.267500.


Why is complementary slackness important? Complementary slackness (CS) is commonly taught when talking about duality. It establishes a nice relation between the primal and the dual constraint/variables from a mathematical viewpoint.

The two primary reasons for applying CS (as taught in graduate courses and textbooks):

To check the optimality of the LP
To help solve the dual

Given today's computing power and polynomial algorithms for solving LPs is CS still relevant from a pragmatic viewpoint? We could always just solve the duals and address both the points above. I agree that it's "more efficient" to solve the dual with the help of CS but is that it? Or is there more to CS than meets the eye? Where exactly is CS useful beyond the above two points? I've commonly seen texts alluding to the concept of CS when talking about approximation algorithms but I fail to understand its role there.

Complementary slackness is key in designing primal-dual algorithms. The basic idea is:

Start with a feasible dual solution $y$.
Attempt to find primal feasible $x$ such that $(x, y)$ satisfy complementary slackness.
If step 2. succeeded we are done. Otherwise an obstruction to finding $x$ gives a way to modify $y$ so that the dual objective function value increases. Repeat.

A classical example is the Hungarian algorithm. The Ford-Fulkerson algorithm can be seen as another example. Note that step 2. is a feasibility problem which often is easier than the original optimization problem, and also often can be solved combinatorially. This is the power of complementary slackness. For example, in the case of minimum cost bipartite matching, step 2 amounts to checking if there exists a perfect matching
using only tight edges. In the case of maximum $s$-$t$ flow, step 2 amounts to checking if the saturated edges separate $s$ and $t$.

Primal-dual algorithms are nice for many reasons. Philosophically, they provide more insight than a generic algorithm. They usually give strongly polynomial time algorithms, whereas we still do not have strongly polynomial LP solvers. They are often more practical than generic algorithms. This is especially true if we cannot write down the LP explicitly and our only other choice is the ellipsoid algorithm, which is the case with non-bipartite matching and Edmonds' primal-dual algorithm.

Primal-dual is also a very useful framework for approximation algorithms, by using relaxed versions of complementary slackness. This has been useful in designing approximation algorithms for NP-hard problems (see e.g. Chapter 7 of the Williamson-Shmoys book) and in designing online algorithms with good competitive ratio (see the book by Buchbinder and Naor). The point here is that the algorithm maintains a solution $y$ to the dual of the LP relaxation of a hard problem, and at each step either finds an integral primal feasible $x$ such that approximate complementary slackness is satisfied, or improves the dual solution $y$. Approximate complementary slackness is a condition of the following form: if $x_i > 0$ then the corresponding dual constraint is tight, and if $y_j > 0$, the corresponding primal constraint would be tight if $x$ is scaled by $\alpha$. This gives an approximation factor $\alpha$. It's all very nicely explained in the above two sources.


Solving a "tree-equation"? Given two trees A and B, each of their nodes except some leaves have a "type" (which also determines the number of children, the node has, having that type). The leaves which don't have a type are identified by letters (variables) (a,b,c,...). Each letter may occur multiple times in a tree.

The task is to devise an algorithm to 'solve' the 'equation' A=B, i.e. assign trees to the variables (possibly containing other variables). One tree (x) equals to an other (y) iff x and y are the same variables or the root of both have the same type and their respective children are equal.

In the following the "types" are numbers.

Example 1:

A tree is

1
|-2
|-a

B tree is

1
|-2
|-3

The solution is a->3

Example 2:

A tree is

1
|-2
|-a

B tree is

1
|-3
|-3

This does not have a solution.

Example 3:

A tree is

1
|-2
|-a

B tree is

1
|-2
|-b

The solution is a=b (the equation is underdetermined so to say)

The process you seem to be looking for (merging two descriptions of labeled trees) is called unification. According to the linked Wikipedia article it can be solved in linear time.


Finding a cell in an arrangement of simplices My question is n-dimensional, but I will begin by dropping the problem down to two dimensions for clarity's sake. It regards defining what is a solution by defining one or more data points that are known to be solutions and a set of linear bounds.
Lets say you have a two-dimensional grid of discrete units that exists within a limited domain, say 1000 x 1000. I'll refer to that domain as D, and reference units within that domain via zero relative c-style array operators (e.g. D[0][0] and D[999][999]).
We also have a function L describing a line segment defined by two points in ℝ2 and within the bounds of D. D[5,5] and D[10.4, 2.6] would be valid points, whereas D[1020, 40] and D[503, 2000.7] would not.
We then create some random set of line segments S{L1, L2,...,Ln} that may or may not intersect with other line segments in the set and define some point P in ℝ2, like (5, 6.7), that is bounded by D and does not intersect with any line segment in S.
If we imagine P as a water source, and S as a set of barriers, the water would spread out and fill some solution area that could be bounded by a set of lines B such that each line connects to the beginning of the next in a loop. Each line is infinitely thin, so lines that project into the water could have the option of not influencing the solution region:

You would then use the point to define the solution area, and determine the set of units in D that are part of that solution area.
If you take this scenario to three-dimensions, you could imagine water filling a volume in a similar manner, generating a three-dimensional bounds object. This can then expand to four or more dimensions.
I suspect the problem would become easier if I split line segments into two line segments at the points of intersection.
I've looked at some isosurface algorithms and modified dilation (fill) algorithms for solving this problem, but they seem very inefficient, especially given extremely large domains, or domains whose resolution relative to the set of bounds functions can be arbitrarily set. The problem grows when the domain has more than three dimensions.
I'm certain that this sort of problem has been dealt with before, as restricting the domain of large data sets down to a solution set using a set of bounds in a time-efficient manner is fundamental to many big-data problems. I'm mainly looking for resources and algorithms related to this problem that I might be able to use?
EDIT
The solution set can also have holes. For example, a bounds with the appearance of a square inside a square, with the solution point between them, would produce a solution area that looked like a square with a square hole in it.
Edit
The more I think about it, the more I think this might actually be a graph-theory question.

If I am understanding your problem correctly, this is the problem of computing the face containing a given point in an arrangement of line segments. There is a randomized algorithm running in expected time $O(n\alpha(n)\log n)$, where $n$ is the number of line segments, and $\alpha(n)$ is the inverse Ackermann function. The algorithm computes the boundary of the face, and from that you can list the grid points if you want using a sweep algorithm, but the time to do that will of course depend on the number of grid points inside the face.


Searching for partial match - 1 item to be searched in $n$ preprocessed items My problem is generalization of the simple problem:

Search for item $x$ in a set $S$.

This is trivial to do it fast if the elements are comparable. Sort the $S$, and do the binary search.

My problem is that I'm interested in partial match. That is, my items are ordered sets of $n = 15$ numbers, and I consider them equal if they have $m = 10$ numbers (at same position) same. For smaller numbers (like 5 out of 6), I can use $n = 6$ sorted sets that have all $m = 5$ number subsets of preprocessed items and then just do 6 binary searches. But for large numbers $n$ and $m$ where $n - m > 2$ number of sets (the binomial coefficient) explodes.

Is there efficient way to search for a partial match?

The only thing that I could think of is to index each number of the set. For example, when preprocessing size 3 sets:

{1,2,3},//set0
{2,3,4}//set1

Create entries

1->(set0,pos0)(position is important), 2->(set0,pos1),(set1,pos0) ... (4->set1,pos2)

and then when I get a new number, I just go for the each number in it and check the sets in which it appears. If there is a set that has many hits (say 10 or more), they are declared the same.

Of course I could use an array trick (i.e. array[1234] contains the pointer to the list of sets that contain 1234). This works for small ranges. For large ranges, I could hash the number and do modulo.

Of course this could go very very wrong for some distributions of preprocessed data.

So is there a better way?

If I understand the problem correctly, this looks like an instance of the Nearest Neighbor Search, under the Hamming distance.

In other words, the "distance" between ordered sets is just the number of mismatched positions. The goal is to preprocess a collection (dataset) of ordered sets, each of size n, so that given a "query" ordered set, the data structure reports an ordered set within Hamming distance n-m. In your case, n is the dimension, and n-m is the distance. (This variant is actually called near neighbor search (the nearest neighbor is one where one reports the closest dataset item).

If that's the problem, then the wiki page may be a good start for pointers on existing work.


The complexity of decomposing a bi-stochastic matrix A bistochastic matrix $A$ is a matrix with positive entries in which
each row/column sums to $1$.
By the Birkhoff von-Neumann theorem $A$ is a convex combination of
permutation matrices.
Further, by the Caratheodory theorem, $A$ can be written as a convex combination of at most $n^2 +1$ such matrices.

What is known about the complexity of finding any such permutation-matrix decomposition of A?
Is this problem known to be NP-hard ?
Furthermore, suppose we are provided with such a succinct description of $A$, i.e.
$$
A = \sum_{i=1}^{n^2+1} c_i P_i, \ \ \sum_i c_i = 1, c_i \geq 0,
$$
where each $P_i$ is a permutation matrix.
Are there problems related to bi-stochastic matrices that become easier,
say computing the permanent of $A$ ?

Summary. Using your favourite $O(n^d)$ algorithm for finding a matching in graphs on $O(n)$ vertices, there is a simple algorithm using  $O(\max\{n^{d+2},n^4\})$ operations over the reals for decomposing doubly-stochastic matrices. The run-time bound comes from $O(n^2)$ iterations of a procedure in which each iteration involves finding a matching, and modifying coefficients of an $n \times n$ matrix. (There are undoubtedly ways of streamlining these operations, at least in the case of the time required to modify the matrix coefficients.)

Details.
The following proof of the Birkhoff–von Neumann theorem can be found e.g. in [1], and leads to an efficient algorithm for decomposing doubly-stochastic matrices.

We consider matrices $A$ whose rows and columns all sum to the same value (which for a doubly-stochastic input is initially 1). Let $N$ be the number of non-zero entries in your $n \times n$ doubly-stochastic matrix: in decomposing the matrix, we will reduce the number of non-zero entries while keeping the invariant of having constant line-sums. Thus at each stage, we have either $N \geqslant n$ or $N = 0$, by the invariant of having equal line-sums.

Set $t \gets 0$.
While $N > 0$:

Set $t \gets t + 1$.
For each $i \in [n]$: let $S_i = \bigl\{ j \in [n]: A_{ij} > 0 \bigr\}$.
Find a bijection $\sigma: [n] \to [n]$ such that $\sigma(i) \in S_i$(such a bijection exists, and can be found efficiently, by Hall's Marriage criterion).
Let $u^{(t)} = \min\,\bigl\{A_{i,\sigma(i)} : i \in [n]\bigr\}$, and let $P^{(t)}$ be the permutation matrix for which $P^{(t)}_{i,\sigma(i)} = 1$ for each $i \in [n]$.
Update $A \gets \bigl(A - u^{(t)} P^{(t)}\bigr)$, and update $N$ to the number of non-zero elements of $A$(which is smaller by at least $1$).

Return $\bigl(u^{(1)},P^{(1)}\bigr)$, ... $\bigl(u^{(t)},P^{(t)}\bigr)$, representing the decomposition $\sum_{i\in[t]} u^{(i)} P^{(i)}$ of the input.

[1] Extremal Combinatorics: With Applications in Computer Science by Stasys Jukna


What is the complexity of vertex cover on k-partite graphs? Given a k-partite graph which is already partitioned into k parts,
what is the complexity of finding a vertex cover of minimum size?

I guess that it's NP-hard, but couldn't yet prove it or find reference for it.
I'm also interested in the dependence on k.

For bipartite graphs, vertex cover is polynomially solvable by routine techniques from matching theory.

For $k$-partite graphs with $k\ge3$, we observe the following:

Vertex cover is NP-complete on cubic graphs
By Brooks' theorem, every cubic graph (except $K_4$) is 3-colorable and hence 3-partite.


Automata recognizing $X^*$ for a finite code $X$ Let $\Sigma$ be a finite alphabet. A code $X$ over $\Sigma$ is a subset of $\Sigma^*$ such that each word in $X^*$ can be uniquely represented as a concatenation of words in $X$. A code $X$ is finite if $|X|$ is finite. What is known about (minimal) automata recognizing $X^*$ for a finite code $X$? Is there any characterization of such automata (in terms of the structure of the automaton, without knowing $X$)? Is it possible, having such automaton, extract the code $X$ in polynomial time?

I am also interested in these questions when we omit the fact that $X$ is a code, i.e., assume only that $X$ is a finite set of words.

Since this question received no answer for a long time, let me offer a partial answer to the first part of the question:

  What is known about (minimal) automata recognizing $X^∗$ for a finite code $X$?

Given a finite set of words $X$, the flower automaton of $X^*$ is the finite nondeterministic
automaton $\mathcal{A} = (Q, A, E, I, F)$, where $Q = \{1, 1\} \cup \{ (u, v)
\in A^+ \times A^+ \mid uv \in X \}$, $I = F = \{(1,1)\}$, with four types
of transitions:
\begin{align*}
 (u, av) &\enspace{\buildrel{a} \over\longrightarrow}\enspace
 (ua, v) \text{ such that } uav \in X,\ (u, v) \neq (1,1) \\
 (u, a) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1,
 1) \text{ such that } ua \in X,\ u \neq 1  \\
 (1, 1) &\enspace{\buildrel{a}
 \over\longrightarrow}\enspace(a, v) \text{ such that } av \in X,\ v \neq 1\\
 (1, 1) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1,
 1) \text{ such that } a \in X \bigr\}
\end{align*}
It is easy to see that this automaton recognises $X^*$. For instance, if $A= \{a, b\}$ and $X = \{a, ba, aab, aba\}$, the flower automaton of $X^*$ is the following

$\qquad\qquad\qquad$

Recall that an automaton is unambiguous if, given two states $p$ and $q$ and a word $w$, there is at most one path from $p$ to $q$ with label $w$. Then the following result holds:

Theorem [1, Thm 4.2.2]. The set $X$ is a code iff the flower automaton of $X^*$ is unambiguous.

The flower automaton also has an algebraic property which makes it relatively close to the minimal automaton. This property holds for any finite set $X$, but  is easier to state by getting rid of the empty word, that is, by considering a language as a subset of $A^+$ instead of $A^*$.

Recall that a finite semigroup $R$ is locally trivial if, for every idempotent $e \in R$, $eRe = \{e\}$. A morphism $\pi:R \to S$ is locally trivial if for every idempotent $e$ in $S$, the semigroup $\pi^{-1}(e)$ is locally trivial.

The transition semigroup $T$ of the flower automaton of $X^+$ is called the
flower semigroup of $X^+$. Since $T$ recognises $L^+$, there is a surjective morphism $\pi$ from $T$ onto the syntactic semigroup $S$ of $X^+$.

Theorem. The morphism $\pi:T \to S$ is locally trivial.

An important consequence of this result is that the flower semigroup and the syntactic semigroup have the same number of regular $\mathcal{J}$-classes.

References

[1] J. Berstel, D. Perrin, C. Reutenauer, Codes and Automata. Encyclopedia of Mathematics and its Applications, 129. Cambridge University Press, Cambridge, 2010. xiv+619 pp. ISBN: 978-0-521-88831-8


Approximation in subexponental time There are studies about approximation algorithms for NP complete problems in Polynomial time and exact algorithms in exponential time. Are there studies about approximation algorithms for NP complete problems in subexponential time of form $2^{n^{\delta_2}}$ where $\delta_2\in(0,1)$?

I am particularly interested in what is known about hard to polynomial time approximable problems such as Independence number and Clique number in subexponential time? Note that ETH only prohibits exact computation in such a time frame. Say Independence number is $\alpha(G)=2^{r(n)n}$ on a graph with vertex count $|V|=2^{s(n)n}$ for some $0<r(n)<s(n)$. Is an $2^{(r(n)n)^{\delta_1}}$-factor approximation scheme possible for Independence number in time $2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$ where $0<\delta_1<1$ and $0<\delta_2<1$ are some fixed positive reals?

That is for every $\delta_1\in(0,1)$ is there a $\delta_2\in (0,1)$ such that $\alpha(G)$ can be approximated within $2^{\log_2^{\delta_1}(\alpha(G))}=2^{(r(n)n)^{\delta_1}}$ factor in time $2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$?

One paper that gives an answer to this question is Chalermsook, Laekhanukit, & Nanongkai (2013).

There are also related works in the context of Fixed Parameter Tractability such as
Hajiaghayi, Khandekar, & Kortsarz (2013) and Chitnis, Hajiaghayi, Kortsarz (2013).
These hardness results are proven under various assumptions such as ETH or existence of very strong PCPs.


min hitting set of every base of a matroid We are given a matroid. Our goal is to find a set of elements of minimum size that has non-empty intersection with every base of the matroid.
Is the problem studied before? Is it in P?
For example, in a spanning tree matroid, the minimum hitting set should be a minimum cut. Thanks.

I meant to leave this as a comment, but I don't have the reputation to do so yet.  This question was crossposted over at Mathoverflow, where I mention that the problem is NP-complete.

See here.

To avoid a contradiction with Chandra Chekuri's answer, I do not believe that the LP given in his answer is integral.  To see this consider the uniform matroids $U_{k,n}$, where the bases are all $k$-subsets of a $n$-set.  Note that the vector $(1/k, 1/k, \dots, 1/k)$ is a feasible solution to the LP.  Thus, if $c$ is identically 1, then the minimum value of the LP is at most $n/k$.  On the other hand, a minimum hitting for $U_{k,n}$ has size $n-k+1$.


Efficient recalculation of the maximum flow when edge capacities are reduced Assume that we have a (directed) graph $G(V \cup \{s, t\}, E)$ and an (integer) capacity function $c : E \mapsto \mathbb{N}$. Let $f : E \mapsto \mathbb{N}$ be a maximum $s-t$ flow on this graph. Suppose that some edge capacities are suddenly reduced; i.e. we now have to work with a capacity function $c_R : E \mapsto \mathbb{N}$ such that $c_R(e) \leq c(e)$ for all $e \in E$.

Can we efficiently "adjust" our old optimal flow $f$ to find the new optimal flow $f_R$ instead of recomputing the latter from scratch?

Note 1: Assume that the reduction is consequential; i.e. $c_R(e) < f(e)$ for at least one $e \in E$. Also, for the sake of simplicity, you can assume that the capacity is reduced for only one edge.

Note 2: One approach would be to treat the problem as an LP. In this case, capacity reductions will simply change variable bounds. Thus, we can use a warm-start capable LP solving method to get from $f$ to $f_R$. For example, if we used the dual simplex method (DSM), we can compute $f_R$ from $f$ via a (hopefully) small number of pivots, each of which involves $O(|V| \cdot |E|)$ arithmetic operations.

Note 3: This discussion tries to tackle the related (harder?) problem of adding/removing vertices and modifying the maximum flow.

In the worst case, even reduction of the capacity of a single edge may force you to recalculate the flow from scratch.

To see this, consider a flow network $(G,c,s,t)$, i.e., $G=(V,E)$ be a graph such that $s,t\in V$, $c:E\to\mathbb N$ is some capacity function, $s$ is a source vertex, and $t$ is a sink vertex.

Now define a new flow network $(G',c,u,t)$, as follows.   $G'=(V\cup\{u,v\}, E\cup\{(u,v),(v,t), (v,s)\}$ is a new graph.  The source vertex of the new flow network is $u$ and the sink vertex is $t$.  Assume that $c((u,v))=c((v,s))=c((v,t))=f^*$, where $f^*$ is the value of the max flow in the original network.

Assume now that I give you a maximum flow $f'$ for $G'$ (from $u$ to $t$), namely, $f'((u,v))=f'((v,t))=f^*$ and $f'=0$ for all other edges.  In other words, $f'$ pushes $f^*$ units of flow along the path $u \to v \to t$.

Now if we reduce $c(v,t)$ to 0, you have to compute the flow for the original network from scratch.


Generalized Ladner's Theorem Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP.  The proof uses the completeness of SAT under many-one reductions in NP.  The hierarchy contains complexity classes constructed by a kind of diagonalization, each containing some language to which the languages in the lower classes are not many-one reducible.

This motivates my question:

  Let C be a complexity class, and let D be a complexity class that strictly contains C.  If D contains languages that are complete for some notion of reduction, does there exist an infinite hierarchy of complexity classes between C and D, with respect to the reduction?

More specifically, I would like to know if there are results known for D = P and C = LOGCFL or C = NC, for an appropriate notion of reduction.

Ladner's paper already includes Theorem 7 for space-bounded classes C, as Kaveh pointed out in an answer.  In its strongest form this says: if NL ≠ NP then there is an infinite sequence of languages between NL and NP, of strictly increasing hardness.  This is slightly more general than the usual version (Theorem 1), which is conditional on P ≠ NP.  However, Ladner's paper only considers D = NP.

The answer to your question is "yes" for a wide variety of classes and reductions, including logspace reductions and the classes you mentioned, as is proved in these papers:

  H. Vollmer.  The gap-language technique revisited.  Computer Science Logic, Lecture Notes in Computer Science Vol. 533, pages 389-399, 1990.

  K. Regan and H. Vollmer.  Gap-languages and log-time complexity classes.  Theoretical Computer Science, 188(1-2):101-116, 1997.

(You can download gzipped postscript files of these papers here.)

The proofs follow the basic principle of Uwe Schöning's extension of Ladner's theorem:

  Uwe Schöning.  A uniform approach to obtain diagonal sets in complexity classes.  Theoretical Computer Science 18(1):95-103, 1982.

Schöning's proof has always been my favorite proof of Ladner's theorem -- it's both simple and general.


Complexity of counting maximum number of co-linear points in Euclidean plane The problem: given a set of points in the Euclidean plane, find the maximum number of co-linear points.

I already know that the problem can be solved in quadratic time using hashing or projective duality (as described here). I also know that checking whether three points are co-linear was proven to be 3SUM-hard under sub-quadratic reductions here.

There are a few issues however:

The 3SUM conjecture was proven false here, so it is no longer believed that the problem has a quadratic lower bound (unless it is strictly harder than 3SUM, see next point).
Unlike most problems in the 3SUM-conjecture paper, co-linearity was only proven to be at least as hard as 3SUM, a reduction in the other direction was not given. That is, it still may be the case that co-linearity is strictly harder than 3SUM. Therefore, the sub-quadratic algorithm for 3SUM cannot be immediately used for the co-linearity problem.
3SUM references only address the problem of checking whether at least 3 points are co-linear. It is not clear to me how to reduce the problem of counting the maximum number of co-linear points to that without a multiplicative linear factor.

My question is: is there any sub-quadratic algorithm known for the problem? If not, do we have a good reason to believe that such an algorithm does not exist?

It is known that finding an $O(n^{2-\epsilon})$ algorithm for 3SUM is still open. So I am, at best, hoping for a logarithmic improvement over the quadratic algorithm.

EDIT: I am also (but not exclusively) interested in the case when the coordinates are integral.

First, my understanding is that the paper you linked to does not show that 3sum is incorrect. It just shows that the 3sum conjecture is false in a model of computation that is not realistic (i.e., we do not have currently a truly subquadratic algorithm for 3sum).

As for your question, if you are looking for a line containing more than $k$ points, and $k$ is sufficiently large (at least say $10\log^2 n$), then it is not hard to get a subquadratic number of candidate lines such that one of them with high probability is the desired line. Then using standard trade-offs between space and query time for range searching, you would get something subquadratic. The question is of course what to do in the in-between range, when the heaviest line has between $3$ and polylog n points on it. (For ref, see http://sarielhp.org/p/04/depth/depth.pdf).

I think the interesting open question, is whether one can get $O(n^2/k^2)$ (the above would get you at best $O(n^2/k^2 * polylog n)$ [but its probably slower than that]).


Bounding the rate of increase of the price of anarchy across equilibrium concepts We know and love a bunch of nested classes of solution concepts:

PN: Pure Nash Equilibrium
MN: Mixed Nash Equilibrium
CE: Correlated equilibrium
CCE: Course correlated equilibrium.

The relationship between these sets is:
$$PN \subset MN \subset CE \subset CCE$$
We can consider the price of anarchy over any one of these solution concepts: the worst case social welfare for any profile in the set, divided by the optimal social welfare:
$$POA(S) = \max_{s \in S}\frac{COST(s)}{OPT}$$
So, by the above containments:
$$POA(PN) \leq POA(MN) \leq POA(CE) \leq POA(CCE)$$
My question: are their known bounds on how fast this quantity can grow? It is possible to have a game with $POA(PN)$ finite, but $POA(CCE)$ unboundedly large. But if I know $POA(PN)$ is finite, does $POA(MN)$ also have to be finite? $POA(CE)$? How much larger can they be?

The ratio between $POA(MN)$ and $POA(PN)$ can be arbitrarily large. Consider the following congestion game; we have $n$ players and $n$ items, and each player can choose any item. The cost to a player depends on the congestion of the item picked; it is $f(x)$ if $x$ players pick that item. $f$ will be a sharply growing function.

The only pure Nash has each player picking a unique item, so everyone pays $f(1)$. On the other hand, by symmetry, the randomized strategy where each player picks a uniformly random item is a mixed Nash. If $f$ grows steeply, the total cost will be much more expensive, since there is some chance that multiple players pick the same item.


Deformation of finite regular languages Let $L \subseteq \{0,1\}^n$ be any finite regular language s.t it has an acyclic DFA.
Let $C$ be some class of acyclic DFAs.

Let $\sigma \in S_n$ be a permutation on $n$ symbols. We can apply $\sigma$ to a string $w$ of length $n$ by permuting symbols of $w$ according to $\sigma$ and  we denote the new string by $\sigma(w)$.

Let $L(\sigma)=\{\sigma(w) \mid w \in L\}$.

What interesting classes $C$ one can define s.t for any finite regular language $L$, either $L$ has a DFA in the class $C$ (L is recognized by a DFA which satisfies properties of class C) or there is a permutation $\sigma$ such that $L(\sigma)$ has a DFA in the class $C$.

Effect of permutation, an example: $L =\{ww | w \in \{0,1\}^n\}$ has only acyclic DFA of size $\Omega(2^n)$ but there is a $\sigma$ such that $L(\sigma) =\{w_1^2w_2^2\cdots w_n^2 | w \in \{0,1\}^n\}$ has $O(n)$ size DFA. I refer $L(\sigma)$ as a deformation of $L$.

Is there some references for study of these kind? are similar questions for CFL studied?

Thank you.

1) Here is a paper that studies your question in the case of finite languages $L$, and shows that if a finite language $L$ can be decided by an $n$-state DFA, then any permutation of $L$ can be decided by an $m$-state DFA for some $m \leq \frac13 (n^2 + n + 1)$:

  Palioudakis A., Cho DJ., Goč D., Han YS., Ko SK., Salomaa K. (2015) The State Complexity of Permutations on Finite Languages over Binary Alphabets. In: Shallit J., Okhotin A. (eds) Descriptional Complexity of Formal Systems. DCFS 2015. Springer Lecture Notes in Computer Science, vol 9118.

See slides here.

2) You might be interested in studies of read-once (algebraic) branching programs. Technically, this is a setting where the order of the input matters, but many of the results in this area apply regardless of how the input is ordered. While ro(A)BPs are slightly stronger than DFAs, they are closely related.


Property testing in other metrics? There is a large literature on "property testing" -- the problem of making a small number of black box queries to a function $f\colon\{0,1\}^n \to R$ to distinguish between two cases:

$f$ is a member of some class of functions $\mathcal{C}$
$f$ is $\varepsilon$-far from every function in class $\mathcal{C}$.

The range $R$ of the function is sometimes Boolean: $R = \{0,1\}$, but not always.

Here, $\varepsilon$-far is generally taken to mean Hamming distance: the fraction of points of $f$ that would need to be changed in order to place $f$ in class $\mathcal{C}$. This is a natural metric if $f$ has a Boolean range, but seems less natural if the range is say real-valued.

My question: does there exist a strand of the property-testing literature that tests for closeness to some class $\mathcal{C}$ with respect to other metrics?

Yes, there is!  I will give three examples:

Given a set S and a "multiplication table" over S x S, consider the problem of determining if the input describes an abelian group or whether it is far from one.  Friedl, Ivanyos, and Santha in STOC '05 showed that there is a property tester with query complexity polylog(|S|) when the distance measure is with respect to the edit distance of multiplication tables which allows addition and deletion of rows and columns from the multiplication table.  The same problem was also considered in the Hamming distance model by Ergun, Kannan, Kumar, Rubinfeld and Viswanathan (JCSS '00) where they showed query complexity of O~(|S|^{3/2}).
There is a large amount of work done on testing graph properties where the graphs are represented using adjacency lists and there is a bound on the degree of each vertex.  In this case, the distance model is not exactly Hamming distance but rather how many edges can be added or deleted while preserving the degree bound.
In the closely related study of testing properties of distributions, various notions of distance between distributions have been studied.  In this model, the input is a probability distribution over some set and the algorithm gets access to it by sampling from the set according to the unknown distribution.  The algorithm is then required to determine if the distribution satisfies some property or is "far" from it.  Various notions of distance have been studied here, such as L_1, L_2, earthmover.  Probability distributions over infinite domains have also been studied here (Adamaszek-Czumaj-Sohler, SODA '10).


Are there presentations of set theory in terms of lambda-calculus? I am planning to implement in software a set theory language, based on a binary function, which in set theory is the so called adjunction operation: $f(x, y) = x \cup$ {y}. Therefore, a presentation of set theory in terms of lambda-calculus will really help. Are there such presentations or attempts to do it?

There is a really interesting approach to a set theory-like foundational system that I am rather fond of: Grue's Map Theory. The basic idea is to take the (untyped!) $\lambda$-calculus as a base foundation, and to represent a set $S$ as a term $f$ such that

$$ S=\{f(x)\mid x\in\Phi\}$$
where $\Phi$ represents the well founded functions ($x\neq\bot$ in the Scott semantics). It doesn't look like there is any proof assistant based on it though, so I have no idea how it would work in practice.


What can be solved with semidefinite programming that can't be solved with linear programming? I'm familiar with linear programs in that they can solve problems with linear objective functions and linear constraints. But what can semidefinite programming solve that linear programming can't? I already know that semidefinite programs are a generalization of linear programs.

Also, how does one recognize a problem that can be solved using semidefinite programming? What is a typical problem that semidefinite programming is used for that couldn't be solved via linear programming?

Thanks very much for any response.

A typical problem is MaxCut: output a cut in a graph that (approximately) maximizes the number of edges cut. Goemans and Williamson showed an SDP approximates the value of MaxCut to within a factor at least 0.878. Recently, Chan, Lee, Raghavendra, and Steurer showed that for a natural linear encoding of the MaxCut problem, all polynomial size LPs achieve approximation no better than 0.5.

It's hard to say concisely what kind of problems usually benefit from an SDP. A systematic approach to constructing SDP relaxations is through hierarchies, the most powerful of which is the Lasserre hierarchy: see Rothvoß's survey for a nice introduction. By now there are too many examples of successes of SDPs in optimization to list. Also, Raghavendra showed that one particular SDP gives the best approximation to all MaxCSP problems, if the Unique Games conjecture is true.

Check the books of Gaertner and Matousek, chapters 6 and 13 of Willimson and Shmoys' book, Lovasz's survey.


Status quo of category theory and monads in theoretical computer science research? Background. I am a bachelor student who is interested in research related to category theory, monads and Haskell, and I want to find a topic for my bachelor’s thesis in that area.

I have looked at the paper

Eugenio Moggi, “Notions of Computations and Monads”, 1991,

and I do not understand much of it yet. I will probably need quite some time to fully understand it.
But before spending more time on studying it, I want to get a better understanding of the field and its research potential.
I recently talked to a professor of mine about it and he told me that monads were in fashion in the research community back in the 90s, but nowadays they are out of fashion.

Therefore, I am now looking for recent work related to monads, and am wondering:

In what areas of theoretical computer science is nowadays research done  that is related to category theory and monads?
What sort of research has been built up or proposed on E. Moggi’s work on monads in the theory of programming? Has there been any follow up or on going research related to his paper?

There have been a number of developments with regards to the use of monads in the theory of computation since Eugenio Moggi's work. I am not able to give a comprehensive account, but here are some points that I am familiar with, others can chime in with their answers.

Specific examples of monads

You do not have to study super-general theory all the time. There are examples of monads that are very interesting and sufficiently complicated to fill an entire undergraduate thesis.

I like very much Dan Piponi's blog where he gives amazing examples of how monads can be used to mix functional programming and mathematics. Search for his work on knots and braid through monads, for example.

Another specific example of mondas worth studying was given by Martin Escardo and Paulo Oliva in the context of selection functionals, see their Selection Functions, Bar Recursion, and Backward Induction, or perhaps to get interested first read What Sequential Games, the Tychonoff Theorem and the Double-Negation Shift have in Common (associated Haskell and Agda files here).

Mathematical background

Monads come from category theory and are much older than Eugenio Moggi. You could study the background theory if you are mathematically inclined. For instance, you could attack Beck's monadicity theorem. A theoretical computer scientist can never know too much math.

Variations on a theme

You could look at something that is not strictly monads.

For instance, Connor McBride and Ross Paterson's Idioms: applicative programming with effects shows how one can generalize monads to something that is practically relevant and insightful.

Or you could look at how comonads are used to model computational effects. Someone should suggest some references for this topic, but a good start might be David Overtone's slides.

Modal type theory

In homotopy type theory, as well as in type theory in general, monads appear in the shape of modal type theory. Recently modal type theory has been considered in homotopy type theory because the truncation operators are examples of modal operators. And then there is cohesive homotopy type theory in which modal operators (which are monads) play an essential role.

Algebraic effects and handlers

[Disclaimer: partially blowing my own horn here.]

A while ago Gordon Plotkin and John Power obserrved that many computational effects are not just any monads, but special monads arising from algebraic theories. This lead to a whole new treatment of computational effects known as algebraic effects. Later Gordon Plotkin and Matija Pretnar introduced handlers and together with algebraic effects they form a very nice theory of computational effects. One advantage of this approach is that algebraic theories can be easily combined while monads cannot.

You could study how exactly algebraic effects relate to monads. You could look at how people implemented algebraic effects and handlers, say in the Eff language or in Haskell as a library. This is more or less current research.


Exact Algorithm for edge labeling problem in DAG I am implementing some system part of which requires some help. I am therefore framing it as a graph problem to make it domain independent.

Problem: We are given directed acyclic graph $G=(V,E)$.  Without loss of generality assume that $G$ has exactly one source vertex $s$ and exactly one sink vertex $t$; let $P$ denote the set of all directed paths from $s$ to $t$ in $G$.  We are also given a set of vertices $R \subseteq V$.  The problem is to assign non-negative integer weights to the edges of $G$, so any two paths in $P$ have the same weight if and only if they contain the same subset of vertices in $R$.  (The weight of a path is the sum of the weights of its edges.)  The range of weights of paths in $P$ should be as small as possible.

Currently my approach does not seems efficient; I am just looking for some references to literature or some good insights. Anything otherwise is also appreciated.

Edit: Is there a hardness proof for this problem? Does the compact numbering always exists?

havent heard of this problem exactly in literature [maybe someone else has] however as a "nearby problem" it seems to me the minimum spanning tree would have useful properties to solve your problem. for example maybe generating two minimum spanning trees starting from the source vertex & the sync vertex, and propagating them outward until they touch, etc. might solve the problem or give a close answer. before anyone dings me on this here plz understand I am extending the idea of the MST somewhat to be generated starting from a given vertex [normally it starts from shortest edge in the entire graph]. if it doesnt work Id be curious for the reason.


What's the effect of imposing the following restriction on inductive type families? Let a simple expression be either:

A free variable
A data constructor of an inductive type family, applied to 0 or more simple expressions

What would be the effect of imposing the following restriction on a programming language with inductive type families?

  Given a data constructor C of an inductive type family T, within C's type signature, T and (=) (the propositional equality type constructor) may only appear fully applied to simple expressions whose free variables are bound within the type signature itself.

For example, in GHC Haskell (to avoid writing foralls in obvious places):

{-# LANGUAGE DataKinds, GADTs, KindSignatures #-}

data Color = Red | Black
data Sign = Positive | Negative

-- Bad: Test appears applied to Color and Sign, neither
-- of which is a data constructor of an inductive type.
data Test :: * -> * where
  Foo :: Integer -> Test Color
  Bar :: Float   -> Test Sign

-- Good: List only appears applied to free variables.
data List :: (k -> k -> *) -> k -> k -> * where
  Nil  ::                        List f a a
  Cons :: f a b -> List f b c -> List f a c

-- Good: RBT appears applied to Black and Red, both of
-- which are constructors of an inductive type (Color).
data RBT :: Color -> * -> * where
  Empty ::                                    RBT Black a
  R     :: RBT Black a -> a -> RBT Black a -> RBT Red   a
  B     :: RBT l     a -> a -> RBT r     a -> RBT Black a

Now, what I want to know is:

From the POV of language implementors, can this restriction simplify type checking? How much?
From the POV of programmers using languages like Agda, Idris, Coq, etc., are there any useful programs that type check without the restriction, that can't be refactored into equivalent programs that type check under the restriction?
From the POV of type theorists and other mathematicians using type theory as a foundational system, does the restriction prevent any useful mathematical results from being obtained internally to type theory?

This is not a real restriction to the power of the language

First, it is possible to turn all indices of the type family into variables by adding extra arguments to the constructor expressing the constraints. For example, Test can be turned into

data Test a where
  Foo :: Integer -> a = Color -> Test a
  Bar :: Float   -> a = Sign -> Test a

Second, you can define your own version of the propositional equality as an inductive family and use that instead of the built-in one.

data Eq :: * -> * -> * where
  Refl :: Eq a a

This definition follows your restrictions, but it won't be detected as being 'the' identity type. (In case you want to build in some kind of detection for identity-like types, I'd guess that the property of being identity-like may well be undecidable.) So there is nothing that you can do without your restriction that you couldn't do with it in a (somewhat) more complicated way.