What does research in theoretical computer science involve? I am trying to understand what is involved in theoretical computer science research. What do theoretical computer scientists do?

I know a significant time is spent on teaching, supervising graduate students, applying for funding, and departmental duties. Putting them aside how do you spend your research time? What are the major activities you typically do? I am guessing that you read papers, think, have meetings, and write documents. Are there any others?

Regarding topics

There are different type of issues that may be considered
theoretical computer science. The important word here is
"theoretical" (as we all have some idea of what computer science
deals with). Understanding the word theoretical is not so obvious.
For a long time I took it to mean mathematical, as opposed for example
to "hacking". I learned better from people in linguistics:
theoretical for them clearly does not meant mathematical, but based
on a theory which may be somewhat informal (though it may be also
mathematical), and is an organized body of knowledge and concepts that
structure understanding of observable phenomena and hopefully allow
some deductive and predictive use of the acquired knowledge. It also
reduces the amount to learn and to teach by reducing the number of
primitive concepts from which the rest can be deduced.

Theoretical can be opposed to practical, which is how this knowledge
is used to actually run computing engines, to build systems, etc. I
can also be opposed to applied which is the use of this knowledge to
address problems in other fields of science and human activities.

But I doubt there are clear-cut boundaries.

This said, theoretical computers science covers diverse domains, and I
will try to give some, while I am sure I forget others, and also that
other people may disagree with this organization.

one domain is computability, which studies what can be computed,
and how in a rather abstract sense: largely what is described in
Suresh Venkat's answer.
another is algorithmics, that finds effective means to compute
answers to specific problems, with specific
constraints. Computability is a theoretical context for algorithmics.
semantics (for want of a better name), analyzes the conceptual
organization of computational problems, and of algorithms, into
higher level concepts, so as to factorize techniques that have
proved useful and are often reused, such as the concept of
subprogram,data-structures, modules, information hiding. It
includes the development of mathematical tools that formalize
adequately these concepts to allow high-level reasonning (Scott
semantics for example). It also touches on the way this is
expressed, thus on the separation and relation between syntax and
semantics. Programming languages concepts are part of it (though
language design is probably the pratical application of that
knowledge). It can also include the relation between proof theory
and computation theory, and the modern role of type systems.
another topic, which could develop more than it has so far, is the
relation between computation and fundamental physics. For
example. is there a relation between the limits on computation and
the properties of the physical world, such as physical information
density or the laws of thermodynamics. Quantum computing may
improve a bit our computational prowess; could we hope for more?
Some may dispute that this is still TCS, though there are TCS
studies on hypercomputation.

Regarding specific activities

I am skipping the obvious activities required by academic life. or scientific life in industry:
teaching, publishing, reviewing papers, writing grant applications,
taking academic responsibilities, managing people, advising students
or policy makers. But even then, there is no simple answer to your
question. Here I am just sketching a few aspects that come to mind,
but I am sure there is a lot more to be said. And I am not sure I am
answering you. Some of the best scientists have written books about their work, and that may give you hints about scientific activities.

Researching in theory may involve a variety of things, depending on
your skills and interests that vary a lot from scientist to
scientist. It is somewhat hard to talk of it, since each person
perceives more her own activity and interests than that of others. Most reasearch
requires a wide knowledge, since interesting and really original
results often comes from putting things in relation, or transferring a
technique from one (sub)field to another, or getting different
technical views of the same problem. So learning as much as you
can in breadth as much as in depth is important. Remember that while
you have the time and ability for it as a student, or as a junior
faculty/scientist, both will be reduced later, because of responsibilities
and life in general. Teaching what you do not specialize in may be a
way to keep learning. On SE you can probably learn more by answering than
by asking.

The kind of work people do can vary a lot, because people are
fortunately very different, with a great variety of interests and
technical abilities, thus complementing each other.  Some people are problem solvers. They look at
theoretical or practical questions raised by other people, or by
themselves, and try to solve them, or get closer to a complete or
partial solution.  Other people will be better at structuring existing
knowledge, and putting thing in relation, and then finding new
questions to ask. Both are essential.

Finding simpler proofs of technical results, or simpler presentations
of theories, or merging concepts is important. It generalizes results,
reduces the numbers of things to learn, emphasizes the essential
ideas and possibly brings new understanding. Since our learning time
is limited, progress is possible only when we condense knowledge.

A simple example is the study of abstract families of formal
languages. When language theory first developped, closure properties
under various operation were proved again and again for each family of
languages (regular, context-free, RE, ...), with ad hoc techniques
depending on the family. Then it occurred that these closure
properties had intrinsic relations independently of the concerned
families, and they were studied as such. Today, we only have to check
a few of the simpler closure properties for a given family, and we
get "for free" a whole set of other properties.

Another important point is that there is not such a clear-cut distinction
between theoretical, practical, or experimental work. A good theory
may lead to the implementation of systems that can mechanize the
resolution of problems. And it will take a good theoretician to
implement such a system, with a mix of theoretical and practical work,
including system implementation, or language design. Many examples
come to mind, such as proof and/or program synthesis systems,
specialized language for synchronous parallel systems, a restricted
algorithmic language for which computational complexity can be
systematically derived. Not only is it important to be able to produce
such pratical systems, which make theoretical results more widely
available and usable, but it is often very important for theoretician
either to use proficiently these systems, if only to unload the now less creative parts of his work, or to contribute to the development and
extension of these system.

Another aspect is to be able to compare theoretical approaches by
pratical experimentation. Here, the issue is to compare different
techniques to accomplish the same goal. Comparing
implementations is often meaningless as their efficiency often depend
on the programming language, or the programming skills of the
implementor. But if they can be expressed all in a common theoretical
framework, then it is sometimes possible to compare them experimentaly
within that framework. Here, theory and practice support each other,
as they often do in science. Pure theoretical analysis is not always
easy to achieve. Furthermore, experimental analysis, when well
conducted, can exhibit unexpected behavior that may motivate better
theoretical analysis.

The world is not simple or clear-cut. That is why it can be fun, with
room for all kinds of skills. Questionning your own knowledge, and
answering questions of others, by whatever means.

Two things often forgotten: ethics of science, and explaining it to
people.  Both are essential, and hard.


Are there any open problems left about DFAs? After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don't mean generalisations of DFAs but the original unmodified DFAs we study in undergrad.

This is a vague question but I hope you get the idea. I want to understand if it is fair to say that we completely understand DFAs. So I really mean questions that are inherently about DFAs, not problems artificially made to look like a problem about DFAs. Let me give an example of such a problem. Let L be the empty language if P=NP and some fixed non-regular language if P is not NP. Can L be accepted by a DFA? This question is about DFAs, but it isn't about them in spirit. I hope my point is clear and I don't get pedantic non-answers from people.

In short is it fair to say

  We essentially completely understand DFAs.

I am sorry if it turns out that this is a huge area of research that I was not aware of and I have just insulted an entire community of people.

Here is one problem described in the book "A second course in formal languages and automata theory" by Shallit.

  Let $u$ and $v$ be two distinct words with $|u|=|v|=n$.  What is
  the size of the smallest DFA that accepts $u$ but rejects $v$, or vice versa?

Robson, in his paper "Separating strings with small automata" in 1989 proved an upper bound $O(n^{2/5}(\log n)^{3/5})$.  The best known lower bound in $\Omega(\log n)$.

For a survey see this.


Decidability of parametric higher-order type unification I'm making a language that has higher-kinded types (like Haskell) and allows type synonyms to appear partially applied in type expressions (unlike Haskell). As an example, consider the following pseudo-GHCi session:

> data Foo f a = Foo (f a)
> type Bar a = Char
> type Qux a = a
> :t Foo 'a'
Foo 'a' :: (f a ~ Char) => Foo f a

(GHCi's actual output is an error message saying that f a can't be unified with Char.)

> :t Foo 'a' :: Foo Bar a
Foo 'a' :: Foo Bar a :: Foo Bar a
> :t Foo 'a' :: Foo Qux Char
Foo 'a' :: Foo Qux Char :: Foo Qux Char

(GHCi's actual output is an error message saying Bar and Qux haven't been passed enough arguments.)

I already understand that:

Haskell requires all type synonyms to be fully applied in type expressions. As a consequence, every valid Haskell type expression has an equivalent canonical form in which no type synonyms appear. Haskell type checkers can take advantage of the aforementioned fact by only performing type unification on canonical forms, where the equation f a ~ g b can be soundly reduced to f ~ g and a ~ b.
Without the aforementioned restriction, we can't reduce equations of the form f e1 ~ e2, where f is a free type variable, and e1 and e2 are arbitrary type expressions. In particular, if e2 isn't a lone type variable, the only thing we can do with such a constraint is attach it to the inferred type signature. This is why, in my pseudo-GHCi seesion above, the principal type of Foo 'a' is (f a ~ Char) => Foo f a.

Before I can formulate the remainder of my question, I need to introduce a little terminology:

Head: The head of a type expression of the form f a is equal to the head of f. The head of any other type expression is the entire type expression itself.
Determinacy: A type expression is determinate if and only if its head isn't a free type variable.
Reducibility: A type equation is reducible if its left- and right-hand sides are both determinate.
Stuckness: A type equation is stuck if either side is the application of a type variable to an arbitrary type expression, and the other side isn't a lone type variable.

Under this new formulation, arbitrarily higher-order (but rank-1) type unification simply consists in reducing a system of equations until no more reducible equations remain (e.g., from Either a b ~ Either c d to a ~ c and b ~ d).

However, one problem remains: Equations like f a ~ Int and f a ~ Char are mutually inconsistent, but, because they're both stuck, the unification algorithm outlined above won't even bother analyzing them. As a result, I'd get a nonsensical inferred type signature like (f a ~ Int, f a ~ Char) => ..., instead of a proper type error.

Now, I'm aware that, in general, higher-order unification is undecidable, so there's no solution to the aforementioned problem that works in all cases. But I have one more constraint that I hope could save the day: All type functions must be parametric. (I just don't like type families.) For example:

f Int ~ Char and f Char ~ Int are now mutually inconsistent constraints.
Assuming no kind polymorphism, f a ~ Int and f b ~ Char have exactly one solution (up to type synonym replacement): a ~ Int, b ~ Char and f is the identity type function.

Is parametric higher-order type unification decidable? I highly suspect, but have no proof, that the notion of "type expression head" could be the key to giving a positive solution to this problem.

No, it's not decidable. The pure simply-typed lambda calculus is parametric in your sense (it has no case analysis) and higher-order unification is undecidable.

In general, permitting partial application of type synonyms is equivalent to adding lambda-abstraction to the language of type expressions. This is because type synonyms suffice to encode the SKI combinators, which are equivalent to the full lambda calculus.

 type I a     = a
 type K a b   = a
 type S a b c = a c (b c)

It would be very unnatural to write type annotations using such synonyms, but that doesn't matter for decidability results!

However, pattern unification and higher-order matching are both decidable, and may be useful for your purposes.

In higher-order unification, you have two lambda terms $s$ and $t$ containing unification variables, and a unifier is a substitution $\theta$ such that $\theta(s) =_{\beta\eta} \theta(t)$, with the goal finding a complete set of unifiers (ie, a set such that every unifier factors through this set).

In higher-order matching, we assume that only one of the two terms (say $t$) has unification variables, so we are looking for unifiers $\theta$ such that $s = \theta(t)$. This can be useful for type inference, because often we ask programmers to write type annotations (which obviously won't have unification variables in them).

Colin Stirling gives the algorithm for this in his paper Dependency Tree Automata.
In pattern unification, we assume that every unification variable $X$ only occurs with arguments that are a disjoint set of variables. That is, any application of $X$ must look like $X\;a\;b\;c$, where $a,b,$ and $c$ are variables distinct from one another. This effectively reduces the problem to first-order unification, since applying a variable to a lambda-term can never introduce a new redex. This procedure is the basis of type inference in most proof assistants like Coq and Agda.

Dale Miller originally made this observation, and many people have worked out different presentations of this algorithm. One I like is Gopalan Nadathur and Natalie Linnell's Practical Higher-Order Pattern Unification
With On-the-Fly Raising.


What Is the Complexity of This Two-to-One Matching Problem? Given a graph $G=(V,E)$ and a function $c:V\mapsto\{1,2\}$. The function $c(\cdot)$ divides the vertices into two disjoint sets $V_1$ and $V_2$, where for all $v_1\in V_1$, we have $c(v_1)=1$ and for all $v_2\in V_2$, we have $c(v_2)=2$. There is no edge between $v_2\in V_2$ and $v_2'\in V_2$. There are edges between $v_1\in V_1$ and $v_2\in V_2$ and between $v_1\in V_1$ and $v_1'\in V_1$ (for $v_1\ne v_1'$). Find a two-to-one matching between $V_1$ and $V_2$ of maximum cardinality. That is, a set $S:=S_1\times S_2\subset V_1\times V_2$ such that:

cardinality($S$) is maximum;
for each $(s_1,s_2)\in S$, $\{s_1,s_2\}\in E$ ;
$S_1$ is an independent set;
for each $s_2\in S_2$, degree($s_2$) is at most $2$; and
for each $s_1\in S_1$, degree($s_1$) is at most $1$. $\leftarrow$ EDIT

Is this problem NP-hard?

I was trying to prove that this problem is NP-hard by reduction from Conflict-Aware Weighted Bipartite B-Matching Problem (CA-WBM).

The authors proved that CA-WBM is NP-hard by a reduction from weighted independent set problem. Since I do not have weights in my problem, I was able to prove that even the Conflict-Aware Unweighted Bipartite B-Matching Problem (CA-UBM) is NP-hard (since the unweighted independent set is NP-hard). But I could not reduce CA-UBM to my problem. The issue is that in my problem the cost function is restricted to take only two values $\{1,2\}$.

EDIT: changed a few things to make this work with the new constraint, also rewrote the whole proof to add details and clarity.

The following is a reduction of minimum vertex cover to your problem.

Take the graph $(V, E)$ we want to solve minimum vertex cover on. Set $|V_{1}| = |V|^{2} + |V| + |E|$, $|V_{2}| = |E| + |V|$.

To every node $x \in V$ there correspond $|E| + 1$ nodes $a_{x, i}, b_{x}$ in $V_{1}$. To the edge with index $i$ there corresponds node $f_{i}$ in $V_{1}$ and $e_{i}$ in $V_{2}$. Additionally, there are $|V|$ nodes $c_{1}, \dots, c_{|V|}$ in $V_{2}$.

Add the edges $(a_{x, i}, b_{x})$ for all $i, x$ and $(b_{x}, c_{x})$ for all $x$. This way we get $S$ to be one larger if we use no edges starting from some $a_{x, i}$.

For every edge $(x, y) \in E$ with index $i$, add the edges $(a_{x, i}, e_{i}), (a_{y, i}, e_{i})$ and $(f_{i}, e_{i})$. The idea is that the edge $(f_{i}, e_{i})$ is "free".

We'll now show that there exists a vertex cover of size $k$ if and only if there exists an answer $S$ of size $|S| \geq 2|E| + |V| - k$.

Take any solution S to our instance, we'll modify it to create a solution $S'$ with $|S'| \geq |S|$ we can read a vertex cover of size $k \leq 2|E| + |V| - |S'| \leq 2|E| + |V| - |S|$ from.

If some edge $(f_{i}, e_{i})$ is not in $S'$, add it to $S'$, possibly removing one other edge adjacent to $e_{i}$. This can be done in $O(E)$ and doesn't decrease the size of $S'$.

Assume that the degree of $e_{i}$ corresponding to $(x, y)$ is not two, meaning that edge is "not covered". Then $a_{x, i}$ has degree zero, and we can add $(a_{x, i}, e_{i})$ to $S'$, possibly removing $(b_{x}, c_{x})$. This can be done in $O(E)$ and again doesn't decrease the size of $S'$.

Now we build a vertex cover: if we do not have the edge $(b_{x}, c_{x})$, add node $x$ to our vertex cover. Since the degree of $e_{i}$ is two for all $i$, $|S| \leq |S'| = 2|E| + (|V| - k)$ where $k$ is the size of our vertex cover. Hence we find a vertex cover of size $k \leq 2|E| + |V| - |S|$.

Now take any vertex cover of size $k$. Add to $S$ the edges $(f_{i}, e_{i})$ for all $i$. If $x$ is not in the vertex cover, add the edge $(b_{x}, c_{x})$. For every edge $i$ at least one of its endpoints $x$ is in the vertex cover, so $(b_{x}, c_{x})$ is not in our solution, so we can add $(a_{x, i}, e_{i})$ to $S$. Hence $|S| = 2|E| + (|V| - k) \implies k \geq 2|E| + |V| - |S|$.

Hence for maximum size set $S$ and minimum size of a vertex cover $k$ we have $k = 2|E| + |V| - |S|$, so there exists a vertex cover of size $k$ or less if and only if there exists a $S$ with size $2|E| + |V| - k$ or more.


bounds in centralized and distributed If we know some lower bound of the solution of a problem in centralized setting, what can we say about the lower bound in a distributed setting?

I'm not aware of a general rule to convert centralized bounds to the distributed setting. In the distributed setting, local computation is given for free but the difficulty lies in breaking the symmetry - a node needs to accumulate enough information about it's neighborhood to make a decision about being part of the output set, e.g. being in the MIS. (Taking this a step further, we can think of an $r$-round algorithm as a function mapping $r$-neighborhoods to a yes/no decision.)

For example, for certain $n$-node graphs with max degree $\Delta$ there is an $\Omega(\sqrt{\log n}+\log \Delta)$ lower bound [2] known on the number of distributed rounds, that holds for (the distributed version of) computing a constant approximation of a minimum vertex cover or of a minimum dominating set.

While the above problems are known to be NP-complete, the same lower bound also holds for problems for which there are polynomial time centralized algorithms like computing a maximal independent set or finding a maximal matching.

For most of these problems the lower bound is almost tight; there are distributed algorithms that run in polylogarithmic rounds (see [2] and references therein).

On the other hand, some NP complete problems even allow constant time solutions in the distributed setting! In [1] there's an $O(1)$ round distributed algorithm for $O(n^{1/2+\varepsilon} \chi)$-coloring, which itself is NP complete.

[1] Leonid Barenboim. On the Locality of Some NP-Complete Problems
http://arxiv.org/abs/1204.6675

[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer. Local Computation: Lower and Upper Bounds.
http://arxiv.org/pdf/1204.6675v1.pdf


Steiner tree problem for unweighted graphs Steiner tree problem for weighted graphs is NP-hard. How about unweighted graphs? That is, given a graph $G=(V,E)$ and a subset $C$ of $V$, find a subtree of $G$ with the least number of vertices to connect all the vertices in $C$. (Since we are looking for a subtree, minimizing the number of vertices also minimizes edges.) The unweighted Steiner tree problem should be NP-hard but is there any better (approximation) algorithm for it?

[Steiner tree] remains NP-complete if all edge weights are equal, even if $G$ is a bipartite graph having no edges joining two vertices in $C$ or two vertices in $V-C$.

— Garey and Johnson, Computers and Intractability, Freeman, 1979.  Citation is to private communication with E. R. Berlekamp.


Statistical query model algorithms? I asked this question in cross validated Q&A but seems that it is related to CS much more than Statistics.

Can you give me examples of machine learning algorithms which learn from the statistical properties of the dataset not the individual observations themselves i.e. employ the statistical query model?

Almost every algorithm that works in the PAC model (with the exception of parity learning algorithms) can be made to work in the SQ model. See e.g. this paper of Blum et al. in which several popular algorithms are translated into their SQ equivalents (Practical Privacy: the SuLQ framework). The paper is in principle concerned with "privacy", but you can ignore that -- it is really just implementing algorithms with SQ queries.

Agnostic learning, on the other hand, is much harder in the SQ model: computational issues aside (though these are important), the sample complexity required for agnostic learning is roughly the same as that required for exact learning, if you actually have access to the data points. On the other hand, agnostic learning becomes much harder in the SQ model -- you will usually need to make superpolynomially many queries, even for classes as simple as monotone disjunctions. See this paper by Feldman (A complete characterization of statistical query learning with applications to evolvability) or this recent paper by Gupta et al. (Privately Releasing Conjunctions and the Statistical Query Barrier)


Turing machines over a structure I have heard of models of computation where you have a Turing machine, but instead of symbols over a finite alphabet you have elements from some tau-structure, and write instructions are replaced with functions $f \in \tau$ which are applied to the symbols of the tape following the head and the result is stored in the heads current position and read instructions are replaced with the evaluation of some formula $\phi$ on the symbols following the head, allowing you to take different actions based on the result of this "read".

Recently, I have been very interested in this idea, but whenever I try searching it I only get results for descriptive complexity theory, which is not at all what I'm looking for. Does anyone have any references about these machines and what they are called?

You could start with the survey article by Peter Hinman, Recursion on Abstract Structures, Chapter 11 of the Handbook on Computability Theory (editor E. R. Griffor). If you follow the references there you'll find a wealth of material.


Is Prime Bounded Quadratic Congruence NP-complete? Bounded Quadratic Congruence:

Instance: Three positive integers $a$, $b$ and $c$.

Question: Is there a positive integer $x<c$ such that $x^{2} \equiv a \, (mod \ b)$?

Bounded Quadratic Congruence is $NP$-$complete$ [1].

Prime Bounded Quadratic Congruence:

Instance: Three positive integers $a$, $b$ and $c$ such that $b$ is a prime number.

Question: Is there a positive integer $x<c$ such that $x^{2} \equiv a \, (mod \ b)$?

Is this problem $NP$-$complete$ as well?

Reference:

[1] Kenneth L. Manders and Leonard M. Adleman, NP-complete decision problems for binary quadratics, Journal of Computer and System Sciences 16 (1978), no. 2, pp. 168–184.

This problem can be solved in randomized polynomial time. Look at this:

https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

Therefore, if Prime Bounded Quadratic Congruence would be in NP-complete, then RP = NP.

Consequently, the answer of this question is an outstanding problem in complexity theory, so it is not worth to ask it here...


Explanation of polar decoding? Polar decoding, according to Arikan's paper, can be decoded using a successive cancellation (SC) decoder, which is based on calculating the likelihood ratio, as seen in the image below.

How can I calculate equations 2 and 3 in the above image?
For example, assuming that $N=4$ and that we are using an AWGN channel with $\sigma=0.987$.

Shor is probably referring to this fantastic lecture by Emre Telatar that walks you through the steps in polar coding. Do watch it! In doing so, you shall see that the best mental model to have in mind while trying to wrap your head around the polar code is the erasure channel.


3-dimensional matching variant In the normal version of the matching problem, we are given a set of vertices $X$, $Y$, and $Z$, each of size $n$, and a set of edges $E\subseteq X\times Y\times Z$. We need to find a matching $M\subseteq E$ s.t. $|M| = n$ and it covers each element of $X$, $Y$, and $Z$ exactly once.

The variation is, can we find $M$ s.t. for any $(x_i,y_i,z_i), (x_j,y_j,z_j) \in E\smallsetminus M$, $x_i = x_j$ or $y_i = y_j$ or $z_i = z_j$?

This is the decision version of the 3d-matching variant. I wanted to know if this would also be NP-complete.

No, the variant is in P:

for each element $x_i \in X$
find the set $A_{x_i}$ of triples "reachable" from $x_i$:

start with all triples containing $x_i$ $A_{x_i} = \{ (x, y, z) \mid x = x_i \}$
iteratively add to $A_{x_i}$ all triples that share at least one element with all triples already in $A$

check if $E \setminus A_{x_i}$ is a solution and also for each triple $(x,y,z) \in E$ check if $E \setminus (A_{x_i} \setminus \{ (x,y,z) \})$ is a solution (remove at most one triple from $A_{x_i}$); if it's not a solution proceed with the next $x_i$ (step 1.)
if no solution is found, repeat the same algorithm 2–3 above "scanning" $y_i \in Y$ and checking $A_{y_i}$
if no solution is found, repeat the same algorithm 2–3 above "scanning" $z_i \in Z$ and checking $A_{z_i}$

To prove that  it is correct note that each $A_{x_i}$ contains at most one element of the solution $M$ of the 3DM:

by your variation constrait $E \setminus M$ is contained in at least one of the $A_{x_i},A_{y_i},A_{z_i}$, suppose $A_{x_i}$: $E \setminus M \subseteq A_{x_i}$;
furthermore $M \cap A_{x_i}$ must contain at most one triple from $A_{x_i}$, otherwise the 3DM constraint “covers each element of $X$, $Y$ and $Z$ exactly once” would be violated


Satisfiability problems with restricted (not bounded) number of occurrences per variable Intro

It is known that SAT is hard even when restricted to, e.g., formulas with exactly 3 literals per clause and at most 4 occurrences per variable. On the other hand it is easy if there are exactly 3 literals per clause and at most 3 occurrences per variable. I am interested in other restrictions on the number of occurrences per variable.

For a set $S$ of positive integers, define $(k,S)$-SAT to be the satisfiability problem restricted to boolean formulas with exactly $k$ literals per clause, and the number of occurrences of each variable is in the set $S$. For example $(3,\{1,2,3,4\})$-SAT is hard, $(3,\{1,2,3\})$-SAT is easy.

Sub-questions

If $k=3$ and $S$ is the even numbers, then you can easily pad an instance of $3$-SAT to get an equivalent instance of $(3,S)$-SAT. Is there anything known more generally? Is it always hard if $S$ is infinite? Are there any easy cases for $k=3$ besides $S\subseteq \{1,2,3\}$?

Main Question

I am really interested in 1-in-3-SAT restricted to the case where each variable appears an even number of times - the standard reduction from 3-SAT introduces new variables some of which occur an odd number of times. My feeling is that the problem should be NP-hard. Is there a suitable reduction from SAT? Or from normal 1-in-3-SAT? Or perhaps some sort of dichotomy theorem I don't know about that can be applied?

Edit

The answer to my question as stated is that the problem is indeed hard, because you can simply copy all clauses of a 1-in-3-SAT instance. I now insist that the clauses should not be repeated (we can efficiently preprocess an instance of SAT so that there are no repeat clauses after all)

Theorem: The special case of 1-in-3-SAT where each variable
  appears an even number of times is NP-hard.

Proof: Consider an instance $I$ of 1-in-3-SAT, and let $a_1,\ldots,a_n$
be an enumeration of the variables in $I$.
Assume that variables $a_1,\ldots,a_m$ occur an odd number of times,
whereas $a_{m+1},\ldots,a_n$ occur an even number of times.
Without loss of generality $m$ is an even number (and otherwise,
add a new dummy clause with three newly created dummy variables).

From instance $I$, we create a new instance $I'$ of 1-in-3-SAT
in which every variable occurs an even number of times.
Furthermore, $I$ is satisfiable if and only if $I'$ is satisfiable:

Instance $I'$ contains all variables and all clauses of $I$.
For every variable $a_i$, instance $I'$ contains a (new)
corresponding variable $b_i$.
Furthermore, $I'$ contains a (new) variable $c$.
For every clause $a_i,a_j,a_k$ in $I$, instance $I'$ contains a new clause $\lnot b_i, \lnot b_j,\lnot b_k$.
For $i=1,\ldots,m$, instance $I'$ contains a new clause $a_i,b_i,c$.

It is easy to check that every variable in $I'$ occurs in an even
number of clauses. If $I'$ is satisfiable, then this induces a
satisfying assignment for $I$.

Finally consider a satisfying assignment for $I$.
Use truth values $b_i:=\lnot a_i$ for $1\le i\le n$ and $c:=$FALSE.
The resulting assignment satisfies all clauses in $I'$.


Maximum subgraph problem with unknown complexity Let $Q$ be a polynomial time decidable graph property. In a graph let us call a subgraph $S$ a $Q$-subgraph, if $S$ has the property $Q$. Consider the following optimization problem:
Maximum $Q$-Subgraph problem
Input: Simple undirected graph $G=(V,E)$, and an integer $\ell$, with $1\leq \ell\leq |V|$.
Question: Does there exist a subset $S\subseteq V$ with $|S|\geq \ell$, such that the subgraph induced by $S$ is a $Q$-subgraph?
With various choices for the property $Q$ we can get classical problems. For example, if $Q(S)=$ "$S$ spans a clique" then we obtain the Maximum Clique problem, which is $NP$-complete. The choice  $Q(S)=$ "$S$ spans a subgraph with a perfect matching" leads to the Maximum Matching problem, which is in $P.$ If we take $Q(S)=$ "$S$ spans a subgraph with minimum degree $\geq k$" leads to the $k$-core problem, which is also in $P.$
Questions:

Is there any choice for the (polynomial time decidable) graph property $Q$, such that the complexity of the Maximum $Q$-Subgraph problem is not known?

If we do not find such an example for $Q$, then I would venture into the following conjecture: there is a dichotomy here, that is, for every polynomial time decidable graph property $Q$, the Maximum $Q$-Subgraph problem is always either $NP$-complete or is in $P.$ Is there any argument for or against this conjecture?

look at this paper Lewis-Yannakakis where it is proved that for all non-trivial hereditary properties, it is NP-complete, and see Cai where it is proved that with parameter $\ell$, the problem is FPT for hereditary properties with finite number of obstructions.


Contract preservation using grammars I am exploring using annotated grammars to formalize and enforce parts of contracts between nodes in a distributed application.

I've found a number of articles on languages for specifying fairly general types of contracts, mostly based around the idea of a contract as a state machine; and others (mostly object-capability schemes) based around the idea of identifying a "safe" subset of a language; but none that use a grammar as the specification of the contract.

I was wondering how attempts to formalize contracts tend to fail, and what else should one keep in mind.

Below are details of the particular kind of contract I am trying to enforce.

Given a BNF grammar for part of HTML:

HTML ::== (Text | Link)*;
Text ::== ("&amp;" | "&lt;" | "&quot;" | [^&<"])+;
Link ::== "" Text "";
Href ::== "href=\"" Text+ "\"";

I can infer which strings are in the language and which are not, and the structure of a parse tree, but by adding annotations thus

HTML ::== (Text | Link)*;
Text ::== @String((@CharValue{"&"}"&amp;"
                 | @CharValue{"<"}"&lt;"
                 | @CharValue{"\""}"&quot;"
                 | [^&<"]))+;
Link ::== "" Text? "";
Href ::== " href=\"" @Embeds{URI}Text+ "\"";

I can infer additional facts:

That plain text can be encoded/decoded by replacing "&" with "&amp;", etc. and that a string can be encoded as a string that matches the Text non-terminal.
That the URI grammar should be recursively applied to the content of the href post-decoding.

From this I hope to generate several artifacts:

Encoders.  An encoder for non-terminal T is a 'a -> T string function that encodes a data value.
Sanitizers.  A function T string -> T string that produces a similar string that falls in a subset of the language that is well-handled by many different implementations and which does not contain high-power instructions.
A template context propagator.  A function string * context -> string * context which takes a string from a trusted source and the context before the string (context is a type describing a set of prefixes of strings in the language) and produces a string in the well-handled subset of the language and the context after that string is appended to any of the prefixes described by the input context.  This is useful for composing a string from trusted and untrusted code.

With these tools, I hope to be able to enforce the contract that any powerful instructions which are parsed by the receiver of a network message composed using these tools are instructions that are present in snippets of code authored by the message sender, and not instructions authored by a provider of untrusted data.

If the sender uses the derived tools to encode or sanitize all untrusted data appropriately, and uses the template propagation algorithm to choose encoders/sanitizers appropriate to the context of the buffer on which the message is being built, then high-power instructions in the buffer must have come from a privileged source.

If the recipient receives a message over a secure channel, and uses the same grammar to parse and decode the message, then it can be confident of the provenance of the instructions it receives.

So the annotated grammar serves as a formal description of a contract, and the tools move the burden of preserving the contract from the application author to the grammar author.  Since there are many application authors who tend to know the well-tested parts of a language, a much smaller number of language specialists who know the poorly tested parts of the grammars as well should be able to make applications robust against code injection.

(I'm not in theory; please regard this as a placeholder answer.)

Is this a research-level question? You may have more luck at cs.stackexchange.com.
The reason you haven't found much relevant literature may be your choice of keywords. The terms  contract and communication often refer to describing patterns of interaction formed by message passing as a whole, usually abstracting away from the contents of the messages; your contracts, on the other hand, are limitations on the possible contents of individual messages. That subject is better known as validation, and indeed, grammars are routinely used for that purpose.
Your example uses HTML as the language to restrict, and introduces a BNF for describing it. Don't do that if you can avoid it; SGML and XML were invented for a reason.  They take away the need for you to describe how to recognize syntax trees in strings, so a grammar merely needs to describe a set of allowable trees. XML is a well-established and well-supported standard, and so are several grammar definition formalisms for XML-based languages: XML Schema, Relax-NG, DTDs, Schematron.
Your example also introduces a technique for describing entity encoding and decoding. SGML and XML come equipped with such a technique, and it is applied in HTML, so why not just use that? (Not that I'm happy with how that works, but it's standard: if you have an XML language, the mechanism is there for you to use.)
I'm puzzled by @Embeds{URI} - why isn't URI simply a nonterminal?  I can see that its grammar isn't that of HTML, but that of URIs, but XML has a way of dealing with that already: XIncludes and namespaces.  (Not that I'm happy with how that works, but it's standard: if you have an XML language, the mechanism is there for you to use.)
I don't understand your sanitizers or template context propagators. If you do need a more general annotation mechanism that can be used both to constrain syntax and to interpret it, have a look at stuff such as attribute grammars, affix grammars and definite clause grammars.  I'm not aware of a pendant for XML, but XSLT can be used in a similar way.
If the point of sanitizers and template context propagators really is to restrict the HTML language, why not just override the grammar for some nonterminals in the HTML grammar with your own, more restrictive definitions? Both XML Schema and Relax NG support this, although I must add that they don't provide any support for limiting such overrides to defining restrictions only.  An alternative is to use Schematron, in which syntactic constraints are a language construct.
HTML is an odd choice of language for an example - in a typical web application, there is no great need to constrain the HTML being sent (largely owing to the language being used for markup only and being SGML/XML-based) while it is imperative to put very clear constraints on the messages being accepted in the opposite direction, the HTTP requests. But those are usually simple and don't really use a standard language, unless you put something like SOAP on top. So I'm curious what sort of application you have in mind for this.

To summarize: yes, there is a lot of support for what you want to do (if I'm not too mistaken about your sanitizers and propagators), especially when the languages you use are XML-based.


The complexity of the puzzle game Net Net (known also as FreeNet, or as NetWalk) is a puzzle game played on a $n \times n$ grid with the following objects:

there are $m$ computers ; each computer occupies one cell and has one link cable;
each computer must be connected to the central unit which occupies one cell and has  1, 2 or 3 link cables;
the rest of the grid is filled with wires (there are no empty cells); a wire cell can be of three types: straight line, corner, or T-connection.

The aim of the game is to rotate each cell in order to connect all computers to the central unit without making loops (i.e. the final configuration must be a tree) and without wires with dead ends (the leaves of the final configuration are the computers).

* Has the complexity of this game been studied?
* And/or do you see a quick reduction from a known similar NP-complete problem?

Eric Goles and Ivan Rapaport in "Complexity of tile rotation problems" prove that a similar problem is NP-complete but they use 5 tiles (we can assume that the Net game uses 4 tiles, because we can replace the central unit with a T-connector without changing the game structure), and in their proof loops are not forbidden.

Just a partial self-answer: I think the problem is NP-complete.

I found 3 gadgets (each one occupies $16 \times 16$ cells) that allows to build a Net game equivalent to a grid graph of degree $\leq 3$ and that should have a solution iif the original graph has an Hamiltonian cycle. The figure shows four different configurations of the gadget equivalent to a node with degree 3 (the full picture can be downloaded here).

The gadget SHOULD have the following properties (I'll try to check them with a constraint solver):

it can be linked to other gadgets only through the 3 interface pairs of corner wires ($A$, $B$, $C$);
the two wires of an interface pair must be directed both outwards or both inwards (otherwise there is an open ended wire or a cycle in the inner part of the gadget);
the gadget must be entered/exited exactly twice and from exactly two interface pairs (the green zones of the first three figures show the traversals A-C, B-C, A-B);
exactly two interface pairs must be directed outward (the red zone in the figure shows what happens if the three interface pairs are all directed outward);

The gadgets equivalent to nodes of degree 2 and 1 are similar (and we can also build "fill" gadgets to fill the holes of the original grid graph).

Now replacing the two central cells of one gadget with the central unit that sends the power on one direction and a terminal at the other endpoint, the game SHOULD have a solution iif the original graph has an Hamiltonian cycle.


Looking for papers and articles on the Tarskian Möglichkeit Some background: Łukasiewicz many-valued logics were intended as modal logics, and Łukasiewicz gave an extensional definition of the modal operator:
$\Diamond A =_{def} \neg A \to A$ (which he attributes to Tarski).

This gives a weird modal logic, with some paradoxical, if not seemingly absurd theorems, notably $(\Diamond A\land \Diamond B) \to \Diamond (A\land B)$. Substitute $\neg A$ for $B$ to see why it's been relegated to a footnote in the history of modal logic.

However, I've realised that it's less absurd when that definition of a possibility operator is applied to Linear Logic and other substructural logics.
I have an informal talk about this earlier in the month. A link to the talk is at http://www.cs.st-andrews.ac.uk/~rr/pubs/lablunch-20110308.pdf

(One of the reasons that I asked about substructural modal logics was to compare the expressiveness of those logics with the use of this operator.)

Anyhow, the only non-critical work that I found a reference to is a talk by A. Turquette, "A generalization of Tarski's Möglichkeit" at the Australasian Association for Logic 1997 Annual Conference. The abstract is in the BSL 4 (4),
http://www.math.ucla.edu/~asl/bsl/0404/0404-006.ps Basically Turquette suggested applications in $m$-valued logics for $m$-state systems. (I've not been able to obtain any notes, slides or other content of this talk, so I would appreciate hearing from anyone who has more information.)

Is anyone here aware of other articles or papers on this?

(I don't have any applications for it, but I find the properties to be interesting enough to merit a paper.)

Rob, I didn't know this was called the Tarskian Möglichkeit, but Martin Escardo and I have been studying this operator (A -> B) -> A, in the more general case when falsity is an arbitrary formula B, for the past few years, mainly in connection with computational interpretations of classical theorems. If we let B be fixed, then we define

J A = (A -> B) -> A

It is easy to show that this is a strong monad. We call it the "selection monad" or the "Peirce monad", as J A -> A is Peirce's law. In fact, the seemingly absurd theorem you mentioned in your post is the cornerstone for our work on interpreting ineffective principles such as the Tychonoff theorem, for instance. Have a look at some of our papers, e.g.

Martín Escardó and Paulo Oliva. Sequential games and optimal strategies. Proceedings of the Royal Society A, 467:1519-1545, 2011.

Martín Escardó Paulo Oliva, The Pierce translation. Annals of Pure and Applied Logic, 163(6):681-692, 2012.

Or others found on our webpages: http://www.eecs.qmul.ac.uk/~pbo/

Any paper which mentions "selection functions" or "game" is related to the operator you are asking about.

I must warn we have been studying this operator in the setting of intuitonistic (minimal) logic. But I find it very interesting that you are looking at this in the more refined (substructural) settings of linear logic and Lukasiewicz logic.

Best regards, Paulo.


Complexity of the Hamiltonian Subcycle problem The problem is as follows:

  Given a graph $G$, find a (vertex)
  disjoint set of cycles $C$ on $G$ such
  that every vertex is visited by a
  cycle exactly once.

My question is then: what is the complexity of this problem? Is it NP-hard, in P or something else?

If we modify the problem to require $|C| = 1$, we end up with the standard Hamiltonian Cycle problem. It's easy to see that for any $k$, if we require $|C| = k$ or $|C| \leq k$, then the problem is NP-hard: given an instance for the Hamiltonian Cycle problem, we simply copy this graph $k$ times.

An equivalent definition of the problem is as follows:

  Given a graph $G$, have every vertex
  $v$ 'choose' some other vertex $u$
  such that $(u,v) \in E$, and that
  every vertex is chosen exactly once.

If you prove the above problem NP-hard, then for any $k$, if we modify the problem so that every vertex chooses $k$ vertices and every vertex is chosen exactly $k$ times, then the resulting problem is NP-hard as well: you can reduce the problem for any $k$ to the Hamiltonian Subcycle problem by 'eating up' the number of choices each vertex has by attaching certain gadgets to them.

I came across this problem when I believed a certain problem was in fact equivalent to the above problem. That later turned out to be wrong, but the problem interested me nonetheless.

I've developed an algorithm that sometimes finds the correct answer, but often doesn't end at all. It's based on using Lagrangian relaxation on the TSP variant of the above problem, which is simply TSP where more than one cycle is allowed (as long as the cycles are disjoint). I doubt it's possible to fix the algorithm so it works all the time, so I haven't included it in this question, though I could always do that if needed.

Some standard terminology:

A set of cycles that spans all nodes is called a cycle cover (or "vertex-disjoint cycle cover").
Cycle covers and perfect matchings are special cases of graph factors: cycle covers are 2-factors (spanning 2-regular subgraphs) and perfect matchings are 1-factors (spanning 1-regular subgraphs).

Polynomial-time algorithms:

As Tsuyoshi pointed out, finding a cycle cover in a given graph can be reduced to the problem of finding a perfect matching in a bipartite graph.
More generally, Tutte (1954) shows the following: for any graph $G$ and any integer $f$ it is possible to construct a graph $G'$ such that $G'$ has a 1-factor (perfect matching) if and only if $G$ has an $f$-factor.

As is well known, there are polynomial-time algorithms for perfect matchings.


Worst case ratio between minimum clique cover and maximum independent set The maximum independent set problem gives a lower bound for the minimum clique cover problem.  This is easy to see because given any clique cover together with an independent set, any two vertices which are part of the independent set must belong to separate cliques in the clique cover.

Is there any way to put a worst case (hopefully constant) upper bound on the ratio between these two values?  What about when the number of vertices grows large?  I know it must be at least $\frac{3}{2}$, since we can have a graph composed of an arbitrary number of pentagons (each pentagon has a maximum independent set of 2 vertices, but a minimum clique cover of 3 cliques).  Can anyone find a graph where the ratio is larger than $\frac{3}{2}$? larger than 2?

The Lovász $\vartheta$ function is an efficiently computable function with the property

$$
\alpha(G) \leq \vartheta(G) \leq \bar{\chi}(G),
$$
where $\alpha$ is independence number and $\bar{\chi}$ is clique cover number. If the bound $\frac{\bar{\chi}(G)}{\alpha(G)} \leq n^{1-\varepsilon}$ were true for some constant $\varepsilon > 0$, then we would have an efficient approximation to $\alpha(G)$ within a factor of $n^{1-\varepsilon}$ . However, this is impossible, unless P=NP.

The above argument is conditional on the conjecture P $\neq$ NP. However, Feige showed that, unconditionally, there exists a constant $c$ and an infinite family of graphs for which

$$
\alpha(G) \leq \vartheta(G) < 2^{\sqrt{\log n}}\\
\bar{\chi}(G) > \frac{n}{2^{c\sqrt{\log n}}}
$$

So the gap between $\alpha(G)$ and $\bar{\chi}(G)$ is $n^{1 - o(1)}$, no need for conjectures.


Number of $k$-cuts of grid graphs Given a $n\times m$ grid, let the bottom-left vertex be $s$ and the top-right vertex be $t$.
Given $k$ non-consecutive edges on the upper horizontal line of the grid, I want to find an upper bound on the number of simple $st$-path using those edges.

If I see  the grid as a box in the plane, I can visualize an $st$-path as a rectilinear curve cutting this box. In this way I can associate each cell of the grid to either one or the other partition, getting as a trivial upper bound the value of $2^{n^2}$.
Is there any better?

I also thought that, if I am considering only the paths using the $k$ given edges on the upper line, then I can map each of these paths to a cut of the grid graph into $k+1$ partitions.
Do you know whether any non-trivial upper bound on this number is known?

Thanks for the help!

Consider this variation: we want to find number of paths which goes from $(1,1)->(n-2,n)$ in $(n-2)\times n$ solid grid, this can be done in almost $2^{n(n-2)}$ possible ways. Then is simple to convert it to your case. Just go up one step, then go left $n$ steps, again up one step and then right $n$ steps. That path covers all of that $k$ edges, and these are just restricted versions, that means independent to $k$, the upperbound is big : $2^{O(n^2)}$.


When can we say that two programs are different? Q1. When can we say that two programs (written in some programming language like C++) are different?

The first extreme is to say that two programs are equivalent iff they are identical. The other extreme is to say two programs are equivalent iff they compute the same function (or show the same observable behavior in similar environments). But these are not good: not all programs checking primality are the same. We can add a line of code with no effect on the result and we would still consider it the same program.

Q2. Are programs and algorithms the same kind of object? If not, what is the definition of an algorithm and how does it differ from the definition of a program? When can we say two algorithms are equivalent?

Q1: There are many notions of program equivalence (trace equivalence, contextual equivalence, observational equivalence, bisimilarity) which may or may not take into account things such as time, resource usage, nondeterminism, termination. A lot of work has been done on finding usable notions of program equivalence. For example: Operationally-Based Theories of Program Equivalence by Andy Pitts. But this barely scratches the surface. This should be useful even if you are interested in when two programs are not equivalent. One can even reason about non-halting programs (using bisimulation and coinduction).

Q2: One possible answer to part of this question is that interactive programs are not algorithms (assuming that one considers an algorithm to take all of its input at once, but this narrow definition excludes online algorithms). A program could be a collection of interacting processes that also interact with their environment. This certainly doesn't match with the Turing-machine/Recursion theory notion of algorithm.


Terminology for f(g(x)) = g(f(x)) There is a paper by Ritt from 1923 that calls the relation,  $f(g(x)) = g(f(x))$, permutable functions. Is there a more recent terminology used in the literature, or is this still the standard?

It's common to say that $f$ and $g$ commute with respect to composition (where the property is known as commutativity). See, e.g., http://en.wikipedia.org/wiki/Function_composition.


Sparser Bipartite graphs? Maximal Planar Bipartite graphs are sparser than maximal planar graphs. For which other classes of graphs are maximal Bipartite members sparser than arbitrary maximal members.

Let $\mathcal{C}$ be a class of graphs and let $\mathcal{B}$ be the class of bipartite graphs. We say that $\mathcal{C}$ is biparted if $\rho(\mathcal{C}) > \rho(\mathcal{B}\cap\mathcal{C})$ (where $\rho(\mathcal{C})$ is defined below) i.e. the asymptotic density of arbitrary graphs in the class is larger than the asymptotic density of the bipartite graphs in the same class.

Examples of biparted graphs are:

Planar Graphs ($\rho(\mathcal{C}) = 6 > 4 = \rho(\mathcal{C}\cap \mathcal{B})$)
Graphs of finite genus (same parameters as above)
Subclasses of planar graphs e.g. outerplanar graphs

My question is:

  Are there any other natural classes of biparted graphs?

For a graph $G$, let $\rho(G) = \frac{2|E(G)|}{|V(G)|}$ be the average degree of a vertex. We say that a class of graphs $\mathcal{C}$ is maximally $\rho$-sparse - written as $\rho = \rho(\mathcal{C})$ i.e. the maximum of average density (with maximum taken over all graphs from $\mathcal{C}$ with sufficiently many vertices) approaches $\rho$.

Note: Planar graphs can be proved to be biparted because Euler formula holds. The same is the case with bounded genus graphs. What about bounded tree-width graphs, graphs excluding a finite set of fixed minors,...?

For an extreme example, chordal graphs can have as many as $\binom{n}{2}$ edges but chordal graphs that happen to also be bipartite can have only $n-1$ edges (they are forests). Or even more extremely, consider complete graphs versus (complete $\cap$ bipartite) graphs. But perhaps it makes sense to restrict your problem only to classes of graphs that are naturally sparse, as the planar and minor-closed graph families are.

It is not true that all minor-closed families are biparted; in particular, the graphs of treewidth $k$ are not. An $n$-vertex graph with treewidth $k$ has at most $\binom{k}{2}+k(n-k)$ edges, but (for large $n$ and small $k$) the complete bipartite graph $K_{n-k,k}$ has treewidth $k$ and is almost as dense with $k(n-k)$ edges.

One can extend the bounds from planar graphs to $k$-apex graphs (graphs such that you can delete $k$ vertices and get a planar graph), and their generalization to $(g,k)$-apex graphs for bounded genus $g$: these graphs have at most $(k+3)n+O(g)$ edges but their bipartite subclasses have at most $(k+2)n+O(g)$.

Moving beyond minor-closed properties but continuing with graphs related to planar graphs, the 1-planar graphs (graphs that can be drawn with at most one crossing per edge) can have at most $4n-8$ edges, but bipartite 1-planar graphs can have at most $3n-6$. See Czap and Hudák, "On drawings and decompositions of 1-planar graphs", Elect. J. Comb. 2013. And the graphs with book thickness $k$ have at most $(k+1)n-O(1)$ edges ($2n-3$ for the first page and $n-3$ for each subsequent page), but when they are bipartite the constant factor is lower because the first page is outerplanar. I suspect that similar things happen with other types of almost-planar graph.


Best approximation for a HYPERGRAPH-MAXDICUT problem Consider a $(c^a,(c+d)^a,1)$-regular directed hypergraph $\mathcal{H}(a)$ on $n^a$ vertices with fixed $n\geq c+d+1$, fixed $c\geq 2$, fixed $d\geq 0$ and variable parameter $a\geq 1$ (meaning every vertex $i_1$ has only $1$ outgoing hyperedge $\{i_1\rightarrow i_2,i_3,i_4,\dots,i_{c^a}\}\in\mathcal{E}(\mathcal{H}(a))$ which has $c^a$ vertices and every vertex is on $(c+d)^a$ hyperedges).

Consider the NP-complete HYPERGRAPH-MAXDICUT problem of given an integer $t$ and a hypergraph $\mathcal{H}(a)$ with above parameters, one has to decide if there is a subset $S \subset \mathcal{V}(\mathcal{H}(a))$ such that $$|\{\mathcal{I}=\{i_1\rightarrow i_2,i_3,i_4,\dots,i_{c^a}\}\in\mathcal{E}(\mathcal{H}(a))\mid i_1\in S \text{ and } \mathcal{I}\setminus i_1\cap S=\emptyset\}|\geq t$$

Can there be a $c^{a^{\beta}}$ approximation algorithm to HYPERGRAPH-MAXDICUT where $\beta\in(0,1)$? For which classes of $\mathcal{H}(a)$ could we have such approximation?

If $n$ is variable how does the factor depend on both $a$ and $n$?

This is perhaps not entirely satisfactory since you asked for an approximation rather than a hardness result but there is no constant independent of $a$ for which the problem can be approximated to within via an FGLSS-like reduction.

Unless P=NP, for every $\epsilon > 0$, there exists $c_0$ such that there is no poly-time $\epsilon$-approximation for Hypergraph-DiCut (HDC) instances on $c_0 \le c$-uniform hypergraphs.

Note that this covers the original question since for any $c > 1$, one can take $a$ sufficiently large so that $c^a \ge c_0$; if $a$ grows with $n$, the problem only becomes harder to approximate. It is also easy to artificially increase $c$ in the sense that if one has approximation hardness for any $c$, then one also has an approximation hardness for $c' \ge c$ (ignoring rounding). (see below for details)

Let me tell you the basic idea first and then do it properly.

Example Reduction from 3SAT

We know that it is NP-hard to distinguish satisfiable 3SAT instances from, say, 88%-satisfiable instances.
3SAT can be reduced to your problem like this: for each clause $C$, such as $(x_3 \lor \lnot x_5 \lor x_6)$, we introduce seven vertices - one for each of the seven satisfying assignments to these three variables, such as $(x_3=1, x_5=0, x_6=1)$. For each of these vertices $v$, we have a hyperedge where $v$ is the head and the tail consists of the six other assignments. This way, we force a solution to include in $S$ at most one of the assignments (for simplicity, we may assume that $S$ only contains vertices such that they are the head of a satisfied hyperedge). We also include in the tail of the hyperedge every other vertex that shares a variable with the clause $C$, and where the assignments of shared variables are inconsistent.

As an example, if we also have the clause $(x_3 \lor x_8 \lor x_9)$, we include in the tail of the hyperedge where $(x_3=1, x_5=0, x_6=1)$ is the head, the vertices corresponding to $(x_3=0, x_8=0, x_9=1), (x_3=0, x_8=1, x_9=0)$, and $(x_3=1, x_8=1, x_9=1)$. Note that these are added to the tail, so the hyperedge both rules out inconsistent assignments to the original clause as well as inconsistent assignments of clauses with common variables.

This way, we can now only choose cuts $S$ where the assignments to variables are consistent and each cut hyperedge corresponds to one satisfied clause. In fact, the optimal cuts will correspond precisely to the optimal simultaneously satisfiable clauses. If we reduced from a 3SAT instance where each variable appeared in a bounded number of clauses, then the size of the constructed hyperedges will also be bounded by some constant. If the 3SAT instance was hard to approximate within, say, 0.88, then the Hypergraph DiCut problem, for sufficiently large $c$, is also hard to approximate within 0.88.

Finally, we could have done precisely the same reduction but with each vertex representing the assignment to some $r$ number of clauses with the effect that the problem becomes hard to approximate to within any constant for sufficiently wide hyperedges.

Label Cover Reduction in Detail

More carefully now, the hardness reduction is from Label Cover (LC) and is similar to the FLGSS reduction from SAT to Clique (see references).

Let $u \sim v$ indicate that the vertices $u$ and $v$ are neighbors. If a hyperedge is $k$-uniform, I will also refer to $k$ as the width of the hyperedge.

We know that for every $\epsilon > 0$, there exists fixed $L$, $R$, $d$, $\Delta$, such that for Label Cover with label sets $L$ and $R$, projection degrees at most $d$, and bipartite constraint graphs with degrees at most $\Delta$, it is NP-hard to distinguish perfectly satisfiable instances from $\epsilon$-satisfiable.

Given an LC instance $(U, V, E, \Pi)$, we consider introducing for each LC vertex $v \in V$ and label $i \in R$, an HDC vertex $(v, i)$ which represents assigning $v$ the label $i$. For each HDC vertex $(v, i)$, let $A(v, i)$ be the set of HDC vertices with conflicting assignments to $v$. That is, $A(v, i) = \{ (v, j) : i \neq j \}_{j \in R}$. Similarly, let $N(v, i)$ be the set of neighbor-of-neighbor assignments conflicting with $(v, i)$. That is, $N(v, i) = \{ (w, j) : \forall_{u \in U: v \sim u \sim w} \pi_{vu}(i) \neq \pi_{v'u}(j) \}_{w \in W, j \in R}$.
For each HDC vertex $(v, i)$, we introduce an hyperedge with head $(v, i)$ and tail consisting of $A(v, i) \cup N(v, i)$.
From the assumptions of the reduced-from LC instances, the cardinality of $A(v, i)$ is at most $|R|-1$ and of $N(v, i)$ at most $(|R| - d) \Delta^2$. Hence the hyperedges have width at most $|R| \Delta^2$; the hyperedges may also have smaller width but it easy to add extra variables to pad the hyperedges (see below).
The tail elements $A(v,i)$ of $(v,i)$ ensure that we cannot simultaneously satisfy two hyperedges giving different assignments to $v$. The elements $N(v, i)$ ensure that we may assign a label to the neigbors $u \in U$ of $v$ such that all neighbors $w \in V$ of $u$ have projected labels which are consistent with the projection of $v$'s label; in effect, all LC edges incident $v$ are satisfied by the projected label.

For any set of HDC vertices $S$, let $H(S)$ be the set of hyperedges which have a head in $S$. Again, wlog, we may assume that a cut $S$ only contains HDC vertices which are heads of satisfied hyperedges.

Analysis

Completeness claim: if the LC instance has value 1, then the HDC instance has a cut of size $|V|$.
Proof: Simply take a satisfying labeling $\lambda$ of the LC instance and let $S$ consist of the vertices $(v, \lambda(v))$ for each $v \in V$. Note that since we only take one assignment per vertex, the tail $A(v, i)$ has an empty intersection with $S$. Similarly, since the labeling satisfies all LC edges, for every $v, v' in V$ with a common neighbor $u \in U$, we have $\pi_{vu}(\lambda(v)) = \lambda(u) = \pi_{v'u}(\lambda(v'))$ and hence none of the elements in $S$ appear in the tails of the hyperedges of $H(S)$.

Soundness claim: if the LC instance has value at most $\epsilon$, then the HDC instane has no cut larger than $\epsilon |V|$.
Proof: since we assume that $S$ only contains heads of satisfied hyperedges, we know that for every LC vertex $v \in V$, there is at most one label $j \in R$ such that $(v, j) \in S$. We also know that for every $u \in U$, all neighbors $v \in V$ of $u$, which have an assignment in $S$ are consistent about the projected label of $u$. Consequently, we can define the partial labeling $\lambda$ by choosing $j$ as the label for $V$ if $(v, j) \in S$ and for every neighbor $u \in U$, the label $\lambda(u) = \pi_{v,u}(j)$. This labeling satisfies at least a fraction $|S| / |V|$ of LC constraints since for each labeled $v \in V$, we satisfy all incident constraints and the LC instance is regular.

Conclusion: it is NP-hard to distinguish $|V|$-satisfiable instances from $\epsilon |V|$, i.e., it is NP-hard to approximate the problem to within a constant better than $\epsilon$ for sufficiently large hyperedge widths.

--
Caveat: The hardness result assumes that $c$ can be a large constant, i.e., $a$ reasonably large, and is therefore chiefly only of theoretical interest.

--
To reduce instances with hyperedges of width $c$ to width $c' < 2c$, introduce a copy $v'$ of each variable $v$ and call the two duals of one another. Also introduce the corresponding copy of each hyperedge. Next, replace augment every - original and copy - hyperedge $v_1 \rightarrow v_2, \dotsc, v_c$ by adding $c'-c$ dual variables as tail: $v_1 \rightarrow v_2, \dotsc, v_c, v'_2, \dotsc, v'_{c'-c}$; the new instance will have the same value (=maximum fraction of simultaneously satisfied hyperedges). To see this, suppose the original instance had value $x$ and the augmented value $y > x$. Let $S \cup S'$ be a value-$y$ solution to the augmented instance where $S$ is the set of included original vertices and $S'$ the set of included copied vertices. Then the fraction of satisfied original hyperedges or the fraction of satisfied copied hyperedges must be at least $y$. Suppose it is $S$, then we choose $S$ as the assignment to the original instance as well. Since we only added more vertices to the hyperedges, if an original edge was satisfied by $S, S'$ in the augmented instance, it is also satisfied in the original instance by $S$. In effect, the value of the original instance must have been at least $y$.

P.S. Sorry about the wall of text.

References

Johan Håstad. Some Optimal Inapproximaility Results. In JACM'01.
Feige, Goldwasser, Lovasz, Safra, and Szegedy. Approximating clique is almost NP-complete. In FOCS'91.


Any results on binary boolean CSP beyond the fixed-parameter tractability of almost 2SAT problem? Let $\varphi$ be a 2CNF formula and $k$ a nonnegative integer. It is proved in this paper that the problem of deciding whether one can delete at most $k$ clauses to make $\varphi$ satisfable, is fixed-parameter tractable, where $k$ is the parameter. My question is whether there are some work that generalize this result to other binary boolean CSP? (That is, to decide whether one can delete at most $k$ constraints to make some CSP instance satisfiable, parameterized by $k$) Or any negative results?

To my knowledge classifying this CSP variant is wide open. You can express a few fixed-parameter tractable problems in the setting (e.g. d-Hitting Set is roughly the case where you have positive clauses of size at most d plus negative assignments; roughly means that the CSP problem is slightly more general but easily reduces back to d-HS, or at least weighted d-HS). Even for constraints that you can implement via existentially quantified 2-CNF formulas it is open what the complexity is. The problem is that when implementing constraints in this way, while they are 2-CNF, you pay only one to delete the whole thing. Hence even simple constraints which are just the conjunction of two others can be hard (I may have example + reference later).


Is finding Logspace reductions harder than P reductions? Motivated by Shor's answer related to different notions of NP-completeness, I am looking for a problem that is NP-complete under P reductions but not known to be NP-complete under Logspace reductions (preferably for a long time). Also, Is finding Logspace reductions between NP-complete problems harder than finding P reductions?

Kaveh is correct in saying that all of the "natural" NP-complete problems are easily seen to be complete under (uniform) $\mathrm{AC}^0$ reductions.  However, one can construct sets that are complete for NP under logspace reductions that are not complete under $\mathrm{AC}^0$ reductions.  For instance, in [Agrawal et al, Computational Complexity 10(2): 117-138 (2001)) an error-correcting encoding of SAT was shown to have this property.

As regards a "likely" candidate for a problem that is complete under poly-time reductions but not under logspace reductions, one can try to cook up an example of the form
{$(\phi,b)$ : $\phi$ is in SAT and $z$ is in CVP [or some other P-complete set] iff $b=1$, where $z$ is the string that results by taking every 2nd bit of $\phi$}.  Certainly the naive way to show that this set is complete will involve computing the usual reduction to SAT, and then constructing $z$ and computing the bit $b$, which is inherently poly-time.  However, with a bit of work, schemes such as this can usually be shown to be complete under logspace reductions via some non-naive reduction.  (I haven't worked out this particular example...)


Hardness of a subcase of Set Cover How hard is the Set Cover problem if the number of elements is bounded
by some function (e.g, $\log n$) where $n$ is the size of the problem instance. Formally,

Let $\mathcal{U}=\{e_1, \cdots, e_m\}$ and $\mathcal{F} = \{S_1, \cdots, S_n\}$
where $S_i \subseteq \mathcal{U}$ and $m = O(\log n)$. How hard is it to decide the following problem

\begin{align*}
         \text{SET-COVER'}=\{<\mathcal{U}, \mathcal{F}, k>:
         &\text{ there exists at most $k$ subsets }\\
         &\text{ $S_{i_1}, \cdots, S_{i_k}\in \mathcal{F}$ that cover $\mathcal{U}$}
         \}.
\end{align*}

What if $m=O(\sqrt{n})$?

Any result based on well known conjectures (e.g., Unique Games, ETH) is good.

Edit 1: A motivation for this problem is finding out when the problem gets hard as $m$ increases. Clearly, the problem is in P if $m=O(1)$ and NP-hard if $m=O(n)$. What is the threshold for the NP-hardness of the problem?

Edit 2 : There exists a trivial algorithm to decide it in time $O(n^{m})$ (which enumerates all subsets of size $m$ of $\mathcal{F}$). Therefore, the problem is not NP-hard if $m=O(\log{n})$ since ETH implies that there is no algorithm in time $O(2^{n^{o(1)}})$ for any NP-hard problem (where $n$ is the size of the NP-hard problem).

When $m = O(\log n)$, you can use dynamic programming to find the optimum in polynomial time. The table contains Boolean-valued cells $T_{\ell,X}$ for each $\ell \in \{0,\ldots,k\}$ and $X \subseteq \mathcal{U}$, indicating whether there are $\ell$ sets which cover the elements in $X$.

When $m = O(\sqrt{n})$, say $m \leq C\sqrt{n}$, the problem remains NP-hard. Given an instance of SET-COVER, add $m$ new elements $x_1,\ldots,x_m$ and $(2C^{-1}m)^2$ new sets, consisting of non-empty subsets of the new elements, including $\{x_1,\ldots,x_m\}$ (when $m$ is large enough, $(2C^{-1}m)^2 < 2^m$). Also increase $k$ by one. The new $m,n$ are $m' = 2m$ and $n' = n + (2C^{-1}m)^2 \geq (C^{-1}m')^2$.


Book recommendations for CompSci related math Searching for good textbooks on math related to Computer Science I bought two german books yet, but found them not to be easily understandable and not suitable for self-study . German textbooks are always very academic and extremely based on cryptic formula. They're maybe good, if you want a reference, supplementary to your courses in college, but as pointed out above, I'm trying the self-teaching approach a.t.m. .

I am very interested in theoretical Computer Science, but I lack the needed math knowledge to dig further into the subject . Could you recommend me a book, best in english, which would provide me with the basics of discrete math and every other mathematical subject related to CompSci and is easily understandable ? If the book covers more topics, maybe not so essential for CompSci, but is nevertheless good for self-study, I would like to hear about it too.

I am not only searching for a book, but also an approach of how to learn matc without pain on my own.

If you learn best from and/or enjoy a good lecture, your best bet is probably the MIT open courseware lectures. They have Calculus, multiple versions of Linear Algebra

  I am still going to "Gymnasium", the german counterpart to the high school

Unsurprising, MIT open courseware also has an excellent collection of canonical CS courses that will be helpful for gaining background in CS theory for the high schooler. I worked through the Structure and Interpretation lectures my Junior year of high school, and that was definitely worth the time. There is also an Introduction to Algorithms course.

Of course, there is also a course on exactly what you want -- Math for CS -- but there are no video lectures.

See here: http://ocw.mit.edu/courses/#electrical-engineering-and-computer-science


Syntactic characterisation of the intersection of CTL and LTL The Baier and Katoen textbook references this paper

  E. M. Clarke and I. A. Draghicescu. Expressibility results for
  linear-time and branching-time logics, pages 428–437. Springer Berlin
  Heidelberg, Berlin, Heidelberg, 1989.

to say that, given a CTL formula P, if there exists an equivalent LTL one, it can be obtained by dropping all branch quantifiers (i.e. A and E) from P.

Is there a syntactic criterion that provides a guarantee that if a CTL formula passes the test, then an equivalent LTL formula does exist?

Note that by "equivalent", we actually need to interpret LTL over trees. Thus, we say that a CTL formula $\phi$ is equivalent to an LTL formula $\psi$, if $\phi$ is equivalent to the CTL* formula $A\psi$.

Thus, we essentially compare LTL and CTL in the common grounds of CTL*.

Given this, it's not hard to construct a procedure to check the equivalent. Simply check whether the formula $\phi \iff A\psi$ is a tautology in CTL*. This can be done in 2EXPTIME. However, since satisfiability of CTL is only EXPTIME complete, it might be possible to reduce this to EXPTIME (but I haven't given it much thought).


Algorithm for testing if a point belongs to a sequence of convex set or not I have a sequence of convex sets $C_\lambda$ for $\lambda \in \mathbb{R}$ such that for $\lambda_1 > \lambda_2$, we have $C_{\lambda_1} \subset C_{\lambda_2}$ (essentially a nested sequence of convex sets in $d$ dimensions). For a given point $x \in \mathbb{R}^d$, define:
\begin{align*}
f(x) = \sup \{ \lambda: x \in C_{\lambda} \}
\end{align*}

Is there an efficient algorithm for computing $f(x)$ given $x$.

The obvious algorithm is to use binary search.

You'll need $\lg n$ iterations of binary search, where $n$ = the number of convex sets in your sequence.  (If you have an infinite family of convex sets, $\lg(|f(x)|/\epsilon)$ iterations are enough to approximate $f(x)$ to within $\epsilon$.)  In each iteration, for some value of $\lambda$, you test whether $x \in C_\lambda$.  You haven't specified the representation of the family of convex sets, but for typical representations, testing whether $x \in C_\lambda$ can be done in polynomial time.  So, the total running time will be polynomial.

To do better than this, I suspect the algorithm will need to depend upon how the sequence of convex sets $C$ is represented.  (Do you have a requirement for it to be represented in a particular way, or are you OK with any reasonable representation?  You might want to edit the question accordingly.  You might also want to specify whether this is a finite sequence or an infinite sequence, and how the sets are related.)

For instance, here's a special case where the problem is easier.  Suppose that the sequence of sets is represented as follows: you have a set of linear inequalities on $x_1,x_2,\dots,x_d,\lambda$, with constants $c_0,c_1,\dots,c_d$, so that each linear inequality has this form:

$$c_0 \lambda + c_1 x_1 + c_2 x_2 + \dots + c_d x_d \le 0.$$

Now suppose that the convex set $C_\lambda$ is defined as the set of points $(x_1,\dots,x_d)$ that satisfy all of these linear inequalities (notice the very specific kind of dependence on $\lambda$), and suppose that the linear inequalities are chosen so $C_{\lambda_1} \subset C_{\lambda_2}$ whenever $\lambda_1 > \lambda_2$.  Then you compute $f(x)$ efficiently using a very simple algorithm: you plug in $x$ into each of the linear inequalities, leaving $\lambda$ as the only unknown in each case, and find the largest value of $\lambda$ so that all of those inequalities are satisfied.  This only works if your sets have a certain form and are represented in a certain special way, which is why I say that your problem will probably depend upon how the sets are represented and what structure they might have.


Three-valued logic solver? This is not my area, so apologizes if I am asking nonsense!

I know that there are very good solver/theorem provers for solving 1st order logic.

Now I have a problem, using 3-valued logic, but I am not sure if there are some practical ways of solving 3-valued logic (or converting it to a bigger 2-valued logic problem?)

EDIT1: Is it possible to translated (~reduce?) any 3-valued logic to 2-valued logic? Can this be generalized to K-valued logic, where K is any arbitrary integer? (What about the case when K is infinity?)

Any idea or reference is appreciated.

Let's assume that your three-valued logic consists of the truth values Yes, No and "unknown". We can think of these truth values as the sets $\{\top\}, \{\bot\}, \{\top,\bot\}$, and then the logical operations result in all possible values. For example, Yes and Unknown is Unknown while No and Unknown is No.

A trick known as "double rail logic" uses two binary variables to represent each truth value: Yes is 1,1; No is 0,0; and Unknown is 1;0. The connectives And and Or are implemented using two matching gates, and Not by two negation gates followed by a swap.

More generally, $k$-valued logic can be implemented by encoding each truth value using $\lceil\log_2 k\rceil$ bits. The logical operations are implemented using constant-size Boolean circuits. The advantage of the encoding above is that the circuits are very simple, in particular they read each input only once.


Does MCMC belong to the statistical query model? It is known that a wide range of algorithms fall into the statistical query (SQ) learning model by Michael Kearns. Examples include k-means, logistic regression, naive Bayes (NB), SVM, ICA, PCA, gaussian discriminant analysis, EM, and backpropagation for neural networks. (See, e.g., http://papers.nips.cc/paper/3150-map-reduce-for-machine-learning-on-multicore.pdf for proofs.)

According to Feldman et al. (http://arxiv.org/pdf/1201.1214v5.pdf), it seems that MCMC also belongs to the SQ model. However, I didn't find any concrete proofs for this simple fact in existing literature. So, does MCMC directly falls into the SQ model? Or it requires modifications to fit in?

Let me first clarify what the paper states: "Most algorithmic approaches used in practice and in theory on a wide variety of problems can be implemented using only access to such an [meaning SQ] oracle". So the question is not really whether MCMC "falls into the SQ framework" (the framework does not place any restrictions on computation) but whether the access to data samples that is necessary to run the algorithm can be replaced with access to an SQ oracle without invalidating the guarantees provided by the algorithm. One can also show that an algorithm for which we have no guarantees is an SQ algorithm but that requires an implementation using an "unbiased" oracle (referred to as 1-STAT in the paper). Lower bounds that can be proved against such an oracle are weaker.

Now regarding MCMC with SQs: the main way to apply MCMC to these kinds of problems that we had in mind in described in an example at the bottom of page 4. Please also take a look at the proof of Thm. 9 here in a follow up paper on this type of techniques:
http://arxiv.org/pdf/1311.4821v5.pdf


Reference for Dyck languages being $\mathsf{TC}_0$-complete Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar
$$
S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon
$$
over the set of symbols $\{(_1,\ldots,(_k,)_1,\ldots,)_k\}$.  Intuitively Dyck languages are the languages of balanced parentheses of $k$ different kind.  For example, $(\,[\,]\,)\,(\,)$ is in $\mathsf{Dyck}(2)$ but $(\,[\,)\,]$ is not.

In the paper

  Dynamic Algorithms for the Dyck Languages by Frandsen, Husfeldt, Miltersen, Rauhe, and Skyum, 1995,

it is claimed that the following result is folklore:

  $\mathsf{Dyck}(k)$ is $\mathsf{TC}_0$-complete under $\mathsf{AC}_0$ reductions.

Is there any reference known for the above claim?  In particular, I'm looking for any results that shows at least one of the following:

$\mathsf{Dyck}(k)$ is in $\mathsf{TC}_0$ for arbitrary $k$.
$\mathsf{Dyck}(k)$ is $\mathsf{TC}_0$-hard for arbitrary $k$.

The closest paper I can find is

  Bi-Lipschitz Bijection between the Boolean Cube
  and the Hamming Ball, by Benjamini, Cohen, and Shinkar, 2013

which redirects me to the paper Log space recognition and translation of parenthesis languages by Lynch who proved that $\mathsf{Dyck}(1)$ (that is, normal balanced parentheses) is in $\mathsf{TC_0}$.

Any related papers are welcomed as well.  Thanks!

Here is an $AC_0$ reduction from $\rm Majority$ to $Dyck(1)$.
(This implies that $\rm Majority$ is $AC_0$ reducible to $Dyck(k)$ for all $k \geq 1$.)
In order to do it, we construct a poly-size
constant depth circuit whose gates are $AND$, $OR$, $NOT$ and $Dyck(1)$.

Given an instance $x \in \{0,1\}^n$ of $\rm Majority$ do
Compute $y \in \{0,1\}^{2n}$ by replacing each $0$ with $(($ and each $1$ with $()$.
Now for each $i = 1,\dots, n/2$ let $z_i$ be the string obtained by concatenating $y$ with $2i$-many closing parentheses, i.e. $z_i = y \circ )^{2i}$.
If $z_i \in Dyck(1)$ for some $i = 1,\dots, n/2$ then ACCEPT.
Otherwise, REJECT.

This can be clearly done with a constant depth circuit. (Computing $z_i$ can be done in depth 1, and computing the last step is done using an $OR$ gate.)

It is also easy to see that this circuit indeed computes $\rm Majority$ because $z_i \in Dyck(1)$ if and only if ${\rm weight}(x) = n - i$.


Relation between variance and mutual information Given two discrete random variables $X,Y$ such that $X,Y \in \mathbb{R}$ and $0 \leq X,Y \leq 1$, is it true that $$|\text{Cov}[X,Y] \leq \sqrt{\frac{1}{2} \text{I}[X,Y]}|. $$

This bound may be useful to my research if correct. What I have tried to do in order to prove it is the following:
1. Define the probability space $\mu$ over pairs of possible values of $X$ and $Y$: $$\Pr_\mu [(\alpha,\beta)] = \Pr[X = \alpha \text{ and } Y = \beta].$$
2. Similarly, let $\eta$ be the following probability space:
$$\Pr_\eta[(\alpha,\beta)] = \Pr[X=\alpha] \Pr[Y = \beta].$$
3. It can be seen that $D_{KL} (\mu ||\eta) = \text{I}[X,Y]$ where $D_{KL} (\mu ||\eta)$ is the Kullback–Leibler divergence (https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence).
4. Now, using Pinsker's inequality (https://en.wikipedia.org/wiki/Pinsker%27s_inequality) we get that: $$\delta(\mu,\eta) \leq \sqrt{\frac{1}{2} D_{KL}(\mu || \eta)} = \sqrt{\frac{1}{2}\text{I}[X,Y]}. $$
where $\delta()$ is the total variation distance .
5. The last step I tried is to find any connection between $\delta(\mu,\eta)$ and $|\text{Cov}[X,Y]|$ - ideally $|\text{Cov}[X,Y]| \leq \delta(\mu, \eta)$ - the problem is that seems like there is no such connection, I can find distribution where $|\text{Cov}[X,Y]| > \delta(\mu, \eta)$ and other distribution where the opposite holds.
I strongly believe that if this claim is correct, the proof goes through Pinsker's inequality, since it is very similar. Any advice will be appreciated.
EDIT:
As I was told in the comments, it holds that if $|X|, |Y| \leq 1$, $|\text{Cov}[X,Y]| \leq \delta (\mu, \eta)$ - the proof is in the comments. I was wrong when I thought I had a counter example. I also believe that the accepted answer below is correct.

I think you can show it as follows, and even get a better constant in the end. Forewarning, there's enough cleverness here that I'm kind of suspect that everything is right. But the basic idea is simple enough: reduce to the case where $X$ and $Y$ take values in $\{0,1\}$, where we can exploit a nice relationship between covariance and total variation distance for such variables. From there, the rest of your proof idea works out.

First, introduce $\tau_X$ and $\tau_Y$ as uniform, independent draws from
$[0,1]$.
Define $\hat{X} = 1$ if $X \ge \tau_X$ and $\hat{X}=0$ otherwise, and define
$\hat{Y}$ similarly. Then we have the following relationships:

$\mathrm{Cov}[\hat{X},\hat{Y}]=\mathrm{Cov}[X,Y]$.
$|\mathrm{Cov}[\hat{X},\hat{Y}]| = \frac{1}{2}\hat{\delta}$ where $\hat{\delta}$ is the TVD of the joint distribution of $\hat{X},\hat{Y}$ from the product of the marginals (analogous to your $\mu$ and $\eta$).
$I[\hat{X} : \hat{Y}] \le I[X : Y]$

These can be combined with Pinsker's inequality to prove your claim (even halving the constant).

(1) follows easily by computing $\mathbb{E}[\hat{X}|X]=\mathbb{P}[\tau_X \le X|X] = X$, and similar for $Y$ and $XY$.

(2) can be worked out as follows. Let $a,b,c,d$ be the probabilities that $(\hat{X},\hat{Y})$ takes the values $(0,0), (0,1), (1,0), (1,1)$, respectively. We can write $|\mathrm{Cov}[\hat{X},\hat{Y}]| = |d - (c+d)(b+d)|$. But covariance is invariant under shifts of the variables, and flips sign when a variable is negated. All together, we have
$$|\mathrm{Cov}[\hat{X},\hat{Y}]| = \left\{
\begin{array}{ccl}
|\mathrm{Cov}[\hat{X},\hat{Y}]| &=& |d - (b+d)(c+d)| \\
|\mathrm{Cov}[\hat{X},1-\hat{Y}]| &=& |c - (a+c)(c+d)| \\
|\mathrm{Cov}[1-\hat{X},\hat{Y}]| &=& |b - (a+b)(b+d)| \\
|\mathrm{Cov}[1-\hat{X},1-\hat{Y}]| &=& |a - (a+c)(a+b)|
\end{array}\right.$$
If you write out the quantity $|| \hat{\mu} - \hat{\eta} ||_1$, where $\hat{\mu}$ is the joint distribution of $(\hat{X},\hat{Y})$, and $\hat{\eta}$ is the product of the marginals, then it's the sum of the above four quantities, hence four times the covariance. Dividing through by 4 and writing $||\hat{\mu} - \hat{\eta}||_1$ as $2\hat{\delta} (= 2\delta(\hat{\mu},\hat{\eta}))$ gives (2).

(3) follows from the data processing inequality. Note that once $X$ is fixed, $\hat{X}$ depends only on $\tau_X$, which is independent of everything else (even conditioned on $X$), and similarly with all the $X$'s replaced by $Y$'s. Thus the DPI can be applied twice to give (3), as follows:
$$\begin{align*}
I[X : Y] &\ge I[\hat{X} : Y] \\
&\ge I[\hat{X} : \hat{Y}]
\end{align*}$$


One way communication complexity of multi exact matching Let Alice have $n$ binary strings, each of length $n$ and let Bob have one binary string of length $n$.  Bob has to output $1$ if his string matches any of Alice's exactly and $0$ otherwise.

Clearly Alice can just run $n$ copies of a randomized one-way communication protocol to send a total of $O(n\log{n})$ bits to Bob which will let him output the correct answer with good probability.  Is this the best they can do?

  What is the one-way randomized communication complexity, assuming private randomness, of this
  problem?

My guess is that this is a known problem with existing tight bounds but I have not managed to find a reference yet.

For the lower bound, consider the following problem: Alice is given $x \in \{0,1\}^n$ and Bob is given $i \in [n]$. Their goal is to output $x_i$ (in other words, they need to decide if $i$ is in the set indicated by $x$). This problem is called $INDEX$ in the literature. For the rest of this answer, I assume that Alice always speaks first.

Claim: the randomized one-way communication complexity of $INDEX$ is $\Omega(n)$. By Yao's minimax principle, it suffices to give a linear lower bound on distributional one-way communication complexity of $INDEX$ with respect to the uniform distribution. Let $\pi$ be a one-way protocol that solves $INDEX$ with probability of error $\le 1/64$ with respect to the uniform distribution. For $x \in \{0,1\}^n$ let $M_x$ denote the message sent by Alice on input $x$, and let $\pi(x,i)$ denote the protocol's output on the input $(x,i)$. We have probability of error = $\mathbb{E}_x (P_i(\pi(x,i) \neq x_i)) \le 1/64$. Thus, by Markov's inequality $P_x(P_i(\pi(x,i) \neq x_i) \ge 1/32) \le 1/2$. Let $A$ be the set of all $x$ such that $P_i(\pi(x,i) \neq x_i) \le 1/32$. Note that $|A| \ge 2^{n-1}$. Let $M$ be a message sent by Alice. Let $o \in \{0,1\}^n$ be the string defined by $o_i = \pi(M,i)$. By above, if $x$ is such that $x \in A$ and $M_x = M$, then $x$ and $o$ differ in at most $n/32$ positions. Number of such $x$ is at most ${n \choose n/32} 2^{n/32} \le (32 e)^{n/32} 2^{n/32} \le 2^{8n/32} = 2^{n/4}$. In other words, we have shown that a given message $M$ can arise out of at most $2^{n/4}$ different inputs. Thus the total number of messages has to be at least $2^{n-1}/2^{n/4} =2^{3n/4-1}$. Therefore there is a message of length at least $3n/4 -1 = \Omega(n)$.

Now, this gives an $\Omega(n)$ lower bound for your problem via a reduction. Given $x \in \{0,1\}^n$ Alice constructs $n$ strings $s_1, \ldots, s_n$ as follows: if $x_j = 1$ then Alice sets $s_j$ to be the binary expansion of $j$ (padded to have $n$ bits), otherwise she sets $s_j$ to be 0. Upon, receiving $i$, Bob constructs his own string to be the binary expansion of $i$ (padded to $n$ bits). Bob's string matches one of Alice's strings if and only if $x_i = 1$.


Would a proof assuming a physical law be considered sufficient? I've always wondered if proofs in computer science would be considered sufficient proofs of the proposition if they needed to assume physical laws?
For example, I'm wondering what would happen if someone someday proved P != NP under the assumption of the second law of thermodynamics. Would this settle the debate of P != NP?
Or would the problem be still considered unsolved if it rests on physical assumptions?

It seems at least possible to me, but currently very unlikely. To sum up the below, it's because the current mathematical statement of (say) P vs NP is completely independent of any laws of physics, so one would need to describe new models of computation that do depend on physics axioms.

The key point that Peter Shor made in his comment is that CS theory questions, such as P vs NP, refer to very simple and stylized mathematical models. They aren't statements about the real world. They just say "in this mathematical model, ___ is true".

Now, one does often have empirical laws, such as the Church-Turing thesis, that state that the real world acts like these mathematical models. But that's a one-way connection (it doesn't mean that mathematical models must act like the real world!). To flesh out Peter Shor's example, the Pythagorean theorem only needs the ideas of real numbers and the Euclidean plane/distance. The model is much simpler than the real world and doesn't involve e.g. gravity, electromagnetism, thermodynamics, etc. And even if the Pythagorean theorem were sometimes false in reality because of these complications, this would not affect its mathematical truth.

Similarly, the model for the Turing machine and the definitions of P, NP, etc are much simpler than the real world. The model does not involve things like gravity, thermodynamic entropy, etc. The truth of P vs. NP does not depend on whether computation can actually happen efficiently in the real world.

Now, it seems to me hypothetically possible that in the future, we could discover closer connections between laws of physics and laws of computation. What would happen then is that the mathematical model of the Turing Machine would have to be expanded to account for these connections. One would then have to formulate new definitions of P and NP for this new model and argue that these are "better" than the old model and definitions. Then, in this new physics-aware model, one could have physics axioms that are used in proofs. But this seems very unlikely / far from happening, at least to me.


When does a graph admit an orientation in which there is at most one s-t walk? Consider the following problem:

Input: a simple (undirected) graph $G=(V,E)$.
Question: Is there an orientation of $G$ satisfying the property that for every $s,t \in V$ there is at most one (directed) $s$-$t$ walk?

This can be equivalently phrased as:

Input: a simple (undirected) graph $G=(V,E)$.
Question: Is there an acyclic orientation of $G$ satisfying the property that for every $s,t \in V$ there is at most one (directed) $s$-$t$ path?

What is the class of graphs for which the answer is "yes"? Can this problem be solved in polynomial time?

Some observations:

If the graph is bipartite, then the answer is "yes."
If the graph has a triangle, then the answer is "no."

The first observation follows by orienting the edges from one partition to the other. The second observation is easy to check. This led me to two incorrect guesses:

The answer is "yes" if and only if the graph is bipartite. (counterexample: the 5-cycle)
The answer is "yes" if and only if the graph is triangle-free (counterexample: the cartesian product of an edge with the 5-cycle)

It's NP-complete by a reduction from not-all-equal-3SAT. To see this, observe that

The only valid orientation of a $4$-cycle is one in which the edges alternate orientations.
Let $P$ be a three-edge undirected path, and add a degree-two vertex adjacent to the endpoints of $P$ to form a $5$-cycle. Then the only orientations of $P$ that can be extended to valid orientations of the entire $5$-cycle are the ones in which $P$ is not consistently oriented as a directed path.

We form a variable gadget for a variable $v$ that belongs to $k$ different clauses of the NAE-3SAT instance, by gluing together $k$ shared $4$-cycles on a shared edge. Then in each of the $4$-cycles, the opposite edge to the shared edge has to be oriented consistently with all of the other $4$-cycles. We will associate the truth value of the variable with this consistent orientation of these edges. Additionally, in any valid orientation of each of these $4$-cycles, there is no path from one $4$-cycle into another $4$-cycle, so these gadgets can interact with each other only in the orientation of their edges and not through the existence of longer paths.

We form a clause gadget for a 3-variable clause of the NAE-3SAT instance by gluing together three of $4$-cycle edges, opposite the shared edges of the appropriate three variable gadgets, into a 3-edge path $P$ and then adding a degree-two vertex to complete $P$ into a $5$-cycle. As discussed above, this $5$-cycle can be consistently oriented if and only if its three edges are not all oriented as a directed path, which (when glued correctly) is true if and only if the truth values associated with these orientations are not all equal.

By the way, DAGS with at most one $s$-$t$ walk for each $s$-$t$ pair have been studied previously, as "multitrees", "strongly unambiguous graphs", or "mangroves"; see https://en.wikipedia.org/wiki/Multitree


Beautiful results in TCS Recently, a friend of mine (working in TCS) mentioned in a conversation that "he wanted to see/know all (or as much as possible) of the beautiful results in TCS in his lifetime". This kind of made me wonder about the beautiful results in this area and hence the motivation for the following question:

Which results (or ideas), in your opinion, are beautiful in theoretical computer science? It would be great if you mentioned the reason as well.
[Would also be fine even if the ideas originate in mathematics, but have aroused interest and found uses in TCS]

I would start with an answer as Cantor's diagonal argument because it's simple, elegant and yet a powerful result.

The undecidability of the halting problem.

Beautiful for many reasons. It is an impossibility result. The proof uses diagonalisation. The statement applies to a broad range of models of computation. It can be formulated in a variety of ways, particularly, using standard programming languages. It was a watershed result in the history of computing. Extending this statement leads to Rice's Theorem, Turing degrees and many other cool results. Etc. Etc. Etc.


Finding a matching whose contraction minimizes the number of arcs in a graph Given a mixed graph $G=(V,E,A)$ with edges $E$ and arcs $A$, find a matching in $E$ that minimizes the number of arcs in $G/M$, where $G/M$ is obtained from $G$ by contracting matched vertices and removing parallel arcs.

Is (the decision version of) this problem NP-complete? Has it been studied in the literature?

I do not know if your intent is to allow undirected edges in E and arcs in A to be parallel or not, but it does not matter in the end.  In this answer, we assume that you do not allow edges and arcs to be parallel.

Consider a special case where for each arc in A, A also contains the arc in the opposite direction.  In this case, we can ignore the orientation of arcs and consider them to be undirected.  We call edges in E black edges and edges in A red edges.

Even under these two restrictions, the problem is NP-complete by a reduction from Max-2SAT.  Let φ be a 2CNF formula in n variables $x_1,\dots,x_n$ with m clauses.  Construct a graph G with 3n vertices $v_1,\dots,v_n,x_1,\dots,x_n,\bar{x}_1,\dots,\bar{x}_n$ as follows.  G has 2n black edges: $(v_i,x_i)$ and $(v_i,\bar{x}_i)$ for i=1,…,n.  G has $5\binom{n}{2}-m$ red edges.  First, connect $v_i$ and $v_j$ for i≠j by a red edge.  Next, for every distinct variables $x_i$ and $x_j$, consider four pairs of literals $(l,l')=(x_i,x_j),(x_i,\bar{x}_j),(\bar{x}_i,x_j),(\bar{x}_i,\bar{x}_j)$.  Connect literals $l$ and $l'$ by a red edge if and only if clause $(\bar{l}\vee\bar{l}')$ does not appear in φ.

It is clear that we only have to consider maximal matchings in black edges in order to minimize the number of red edges after contraction.  It is also clear that every maximal matching M in black edges consists of n edges connecting $v_i$ to $l_i\in\{x_i,\bar{x}_i\}$ for i=1,…,n.  Identify this maximal matching M with truth assignment $\{l_1,\dots,l_n\}$.  It is easy to verify that after contracting M and removing parallel edges, the graph has exactly $4\binom{n}{2}-k$ red edges, where k is the number of clauses satisfied by this truth assignment.  Therefore, minimizing the number of red edges after contracting a matching in black edges is equivalent to maximizing the number of satisfied clauses.


Minimizing SubModular Function: Cardinality Given a submodular function f: 2^V to reals (not necessarily monotone), and an integer k, find a set S such that |S| <= k and  such that f(S) is minimized.

When the size constraint is |S| >=k, the problem is NP-hard.  What is known about when the constraint is |S| <= k?

It is NP-hard. Svitkina and Fleischer showed that there is no $o(\sqrt{n/\log n})$ approximation using only a polynomial number of queries.