Finding a positive point for a collection of polynomials I am wondering about the complexity of the following problem:

  Given $k$ polynomials $p_1(x_1, \ldots, x_n)$, $p_2(x_1, \ldots, x_n)$,
  $\ldots$, $p_k(x_1, \ldots, x_n)$ over the $n$ real variables $x_1,\ldots,x_n$.
  Find a point ${\bf x} = (x_1, \ldots, x_n) \in \mathbb{R}^n$ such that $p_1({\bf x}) > 0$, $\ldots$, $p_k({\bf x}) > 0$ (or declare that no such point exists).

Let us furthermore assume that each polynomial is given in the form $p_i(x) = \det(A_0^i + \sum_k x_k A_k^i)$, where we are given the matrices $A_0^i, \ldots, A_k^i$.

Questions:

Is this problem NP-hard?
When $k=1$ there is a randomized algorithm (simply choose a random point). Is there also a randomized algorithm for any $k\ge2$?

Yes, your problem is NP-hard, by reduction from THREE-SATISFIABILITY.

  THREE-SATISFIABILITY:
  Instance: Boolean variables $u_1,\ldots,u_n$; clauses $c_1,\ldots,c_m$ of length three over the $u_i$
  Question: Does there exist a truth setting of the $u_i$ that makes all clauses $u_j$ true?

For every Boolean variable $u_i$, introduce a corresponding real variable $x_i$ together with the two polynomials $x_i^2-0.9^2$ and $1.1^2-x_i^2$.
We say that $x_i$ represents the Boolean variable $u_i$, and that $-x_i$ represents the negated Boolean variable $\bar{u}_i$.
For every clause $c_j$, introduce one corresponding polynomial that is the sum of the real variables corresponding to the three literals plus $1.1$.
(For instance, the clause $u_a\lor\bar u_b\lor\bar u_c$ is represented by the corresponding polynomial $x_a-x_b-x_c+1.1$.)

We claim that the THREE-SATISFIABILITY instance has answer YES, if and only if there exists a positive point for the constructed set of polynomials.

  (Proof of only if):

Consider a satisfying truth setting for the THREE-SATISFIABILITY instance. If $u_i$ is true, then set $x_i=1$, and if $u_i$ is false, then set $x_i=-1$. This makes all polynomials $x_i^2-0.9^2$ and $1.1^2-x_i^2$ positive. Since every clause contains at least one true literal, the sum of the corresponding three real variables is at least $-1-1+1=-1$, so that the corresponding polynomial yields a value of at least $0.1$.

  (Proof of if):

Consider a positive point for the constructed set of polynomials. Then $x_i^2-0.9^2>0$ and $1.1^2-x_i^2>0$ enforce that either $-1.1<x_i<-0.9$ holds (in which case we set $u_i$ false) or $0.9<x_i<1.1$ holds (in which case we set $u_i$ true). Suppose for the sake of contradiction that under the constructed truth setting, some clause $c_j$ would contain three false literals. Then each of the three corresponding real variables is $\le-0.9$. Then the polynomial corresponding to that clause has value at most $-0.9-0.9-0.9+1.1<0$; contradiction.


What would it mean to disprove Church-Turing thesis? Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why?

Turing, Rosser etc used different terms to
differentiate between: "what can be computed" and "what can be
computed by a Turing machine".

Turing's 1939 definition regarding this is:
"We shall use the expression "computable function" to mean a function
calculable by a machine, and we let "effectively calculable" refer to
the intuitive idea without particular identification with any one of
these definitions".

So, the Church-Turing thesis can be stated as follows:
Every effectively calculable function is a computable function.

So again, how will the proof look like if one disproves this conjecture?

There's a subtle point that I rarely see mentioned in these kinds of discussions and that I think deserves more attention.

Suppose, as Andrej suggests, someone builds a device which reliably computes a function $f$ that cannot be computed by any Turing machine.  How would we know that the machine is in fact computing $f$?

Obviously, no finite number of input/output values would suffice to demonstrate that the machine is computing $f$ as opposed to some other Turing-computable function that agrees with $f$ on that finite set.  Therefore, our belief that the machine is computing $f$ would have to be based on our physical theories of how the machine is operating.  If you look at some of the concrete proposals for hypercomputers, you will find that, sure enough, what they do is to take some fancy cutting-edge physical theory and extrapolate that theory to infinity.  O.K., fine, but now suppose we build the hypercomputer and ask it whether a Turing machine that searches for a contradiction in ZFC will ever halt.  Suppose further that the hypercomputer replies, "No."  What do we conclude?  Do we conclude that the hypercomputer has "computed" the consistency of ZFC?  How can we rule out the possibility that ZFC is actually inconsistent and we have just performed an experiment that has falsified our physical theory?

A crucial feature of Turing's definition is that its philosophical assumptions are very weak.  It assumes, as of course it must, certain simple features of our everyday experience, such as the basic stability of the physical world, and the ability to perform finite operations in a reliable, repeatable, and verifiable manner.  These things everyone accepts (outside of a philosophy classroom, that is!).  Acceptance of a hypercomputer, however, seems to require us to accept an infinite extrapolation of a physical theory, and all our experience with physics has taught us not to be dogmatic about the validity of a theory in a regime that is far beyond what we can experimentally verify.  For this reason, it seems highly unlikely to me that any kind of overwhelming consensus will ever develop that any specific hypercomputer is simply computing as opposed to hypercomputing, i.e., doing something that can be called "computing" only if you accept some controversial philosophical or physical assumptions about infinite extrapolations.

Another way to put it is that disproving the Church-Turing thesis would require not only building the device that Andrej describes, but also proving to everybody's satisfaction that the device is performing as advertised.  While not inconceivable, this is a tall order.  For today's computers, the finitary nature of computation means that if I don't believe the result of a particular computer's "computation," I can in principle carry out a finite sequence of steps in some totally different manner to check the result.  This kind of "fallback" to common sense and finite verification is not available if we have doubts about a hypercomputer.


Are there other computer architectures apart fom the von neumann /turing architectures? Are there other computer architectures apart from the Von Neumann /Turing architecture?

Turing machine is an abstract computational model which has its strengths and weaknesses.
Von Neumann architecture is a way to implement it.
There are several other computational models. You can find a list of many of them here


What are the root difficulties in going from graphs to hypergraphs? There are many examples in combinatorics and computer science where we can analyze a graph-theoretic problem but for the problem's hypergraph analog, our tools are lacking.  Why do you think problems often become much harder over 3-uniform hypergraphs than over 2-uniform graphs?  What are the root difficulties?

One issue is that we don't, as of yet, have a satisfactory understanding of spectral hypergraph theory.  Please feel free to shed more light on this issue.  But I'm also looking for other reasons which make hypergraphs more difficult objects.

In this question I understand "difficulty" refers not to "difficult to compute," but to "difficult to study."

Graph problems are easier (at least for me) to study since some concepts happen to be equivalent.  In other words, if you want to generalize questions for graphs to those for hypergraphs, you need to pay attention to the "right" generalization so that the desired consequence can be obtained.

For example, consider a tree.  For graphs, a graph is a tree if it is connected and contains no cycle.  This is equivalent to being connected and having n-1 edges (where n is the number of vertices), and also equivalent to containing no cycle and having n-1 edges.  However, for 3-uniform hypergraphs, let's say a 3-uniform hypergraph is a tree if it is connected and contains no cycle.  But, this is not equivalent to being connected and having n-1 hyperedges, nor to containing no cycle and having n-1 hyperedges.

I've heard a main difficulty to prove the regularity lemma for uniform hypergraphs was to come up with the right definitions of regularity and related concepts.

When you want to consider "spectral hypergraph theory," you may try to look into tensors, or into homology if you see a k-uniform hypergraph as a (k-1)-dimensional simplicial complex, from which linear algebra naturally arises.  I don't know which is the "right" generalization for your purpose, or it's possible that neither is right.


Does kd tree requires triangular inequality for finding k-nearest neighbors I have 3-dimensional data I want to store in a kd-tree. Additionally I have a domain-specific distance function in this space for which I have a hard time to prove the triangular inequality. Here is the function:

$x,y \in [0,255]^3$

$r=\frac{x_1+y_1}{2}$
$dist(x,y)=\sqrt{(2+\frac{r}{256})*(x_1-y_1)^2 + 4*(x_2-y_2)^2 + (2+\frac{255-r}{256})*(x_3-y_3)^2}$

My question now is:

Do I need triangular inequality, given that all other conditions of a metric are fulfilled, for the guarantee that all k-nearest neighbors to a given point can be found.

First of all, I'm not sure why you even need a kd-tree for 3D data. Any reasonable grid structure will be ok to find near neighbors (See the work by Franklin for example, on spiral search methods). Secondly, the triangle inequality is needed to prune the search space correctly, so without it things will run a lot slower.

Finally, as a side note, the coefficients on the first and third square terms are of the form $\alpha, 5-\alpha$, where $2 \le \alpha < 3$. So what you really have is a space in which the distance is defined by a Mahalanobis distance (an affinely transformed Euclidean distance) which is almost fixed (since the coefficients vary between 2 and 3). So even if the triangle inequality is not satisfied (and it's very likely it doesn't), it will be "almost satisfied" in a way that will make near-neighbor searching entirely possible.


FPRAS for #P-complete problems I just found the following sentence from the #P wiki page:

"Jerrum, Valiant, and Vazirani showed that every #P-complete problem either has an FPRAS, or is essentially impossible to approximate; if there is any polynomial-time algorithm which consistently produces an approximation of a #P-complete problem which is within a polynomial ratio in the size of the input of the exact answer, then that algorithm can be used to construct an FPRAS.[3]"

http://en.wikipedia.org/wiki/Sharp-P-complete

the referece [3] is
Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986). "Random Generation of Combinatorial Structures from a Uniform Distribution". Theoretical Computer Science (Elsevier) 32: 169–188.

I took a quick look at [3]. But it seems to me that the results of [3] do not contain anything similar to what is in the wiki page. Is there a mistake in the wiki page? Thanks.

Jerrum, Valiant and Vazirani showed that if for a "self-reducible" NP-relation, there exists a polynomial time approximate counter which produces a $1 + O(n^{-\beta})$ approximation for some constant $\beta > 0$, then this counter can be bootstrapped to make an an FPRAS for the counting problem.  As far as I know, all known #P-complete problems do correspond to "self-reducible" NP-relations, and hence the claim on Wikipedia.  However the exact claim that an approximate counter which produces a poly($n$) approximation for a self-reducible NP-relation can be bootstrapped to produce an FPRAS for counting was proved by Jerrum and Sinclair.  The citation I can think of the top of my head is Sinclair, 1993.


Simulating Turing machines (output included) with circuits A Turing machine with input alphabet {0,1} computes a partial or total function $f \colon \{0,1\}^* \to \{0,1\}^*$. Is it possible to construct a circuit family $\{C_n\}$ such that for an input $x$ of length $n$, $C_n(x) = f(x)$? I have not seen this kind of circuit family in any of the standard texts, nor have I encountered it after lots of googling.

I understand that for decision problems, it is unnecessary to consider such circuit families (which is probably why nobody has bothered to consider them). Or maybe it is just a trivial modification and so is relegated as an exercise to the reader (although I haven't seen such an exercise mentioned anywhere).

There are two immediate obstacles, which I see, that such a circuit family would need to overcome:

What does $C_n(x)$ do when $f(x)$ diverges?
If $|x| = |y|$, but $|f(x)| < |f(y)|$, the output of $C_n(x)$ will contain less bits than $C_n(y)$. How would this work?

I personally don't see any method of overcoming these obstacles.

Yes, as long as we allow encoding the the result of $f$ in a basically trivial way, rather than outputting exactly $f(x)$.

To get over obstacle (2) (different output lengths for the same input length): for any given input length $n$, there is a maximum output length $m$.  $C_n$ will output $2m$ bits.  The first $2|f(x)|$ bits output by $C_n(x)$ will be the bits of $f(x)$ doubled, and the remaining $2(m-|f(x)|)$ bits will be the string 01 repeated over and over.  For example, if $m = 6$ and for some $x$ of length 10, $f(x)=0010$, then $C_{10}(x) = 00\ 00\ 11\ 00\ 01\ 01$ (spaces added for ease of reading).

To get over obstacle (1) ($f(x)$ may not halt): for any given input length $n$, there is a time $t$ such that, for all $x$ of length $n$, either $f(x)$ halts within $t$ steps, or $f(x)$ does not halt ever.  If $f(x)$ does not halt, then we make the output of the circuit be a string of 10 repeated over and over again.  Of course, such a circuit family can not in general be uniform, since deciding that halting time is in general uncomputable, but the circuit family still exists.


Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix This is a specialized version of a previous question:
    Complexity of Finding the Eigendecomposition of a Matrix .

For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the eigen decomposition.  The question is: can we achieve sub-cubic complexity?  Thanks.

I know this is a really old question, but it seems like this recent paper https://arxiv.org/abs/1912.08805 improves the runtime to $O(n^\omega)$, down from $O(n^3)$.


What is the connection between moments of Gaussians and perfect matchings of graphs? Today, I heard the following statement in a talk:

  The 4th moment of a $1$-dimensional Gaussian distribution with mean $0$ and variance $1$ is the same as the number of perfect matchings of a complete graph of $4$ vertices, which is $3$.

Unfortunately, the speaker did not have enough time to go into the details of this.

Firstly, it is very astonishing to me that something continuous can be related to something discrete as precisely as this, that is, beyond the limits of things like approximating a discrete sum with an integral. Secondly, what is the intuition behind this? Any pointers? Are there other examples like this where discrete quantities can be related to continuous quantities?

This fact is a corollary of a more general theorem. Let $\gamma_1,\dots, \gamma_{2n}$ be (jointly) Gaussian random variables; we don't assume that they are independent or identically distributed. Let $c_{ij} = {\mathbb E}[\gamma_i \gamma_j]$ be the covariance of $\gamma_i$ and $\gamma_j$. Consider the complete graph on $\{1, \dots, 2n\}$; assign weight $c_{ij}$ to edge $(i,j)$. Let the cost of a perfect matching $M$ (i.e. a matching of size $n$) be the product of weights of the edges in $M$:
$$\mathrm{cost}(M)=\prod_{(i,j)\in M} c_{ij}.$$
Then
$${\mathbb E}[\gamma_1 \gamma_2 \cdots \gamma_{2n}] = \sum_{M\text{ is a perfect matching}} \mathrm{cost(M)}.$$

We get the formula for the $2n$-th moment of a Gaussian random variable by letting $\gamma_1 = \dots = \gamma_{2n} = \gamma$, where $\gamma\sim{\cal N}(0,1)$. We have, $c_{ij} = 1$ and $\mathrm{cost}(M) = 1$ for every perfect matching $M$; thus,
$${\mathbb E}[\gamma^{2n}] = {\mathbb E}[\gamma_1 \gamma_2 \cdots \gamma_{2n}] = |\{M: M \text{ is a perfect matching}\}|.$$

The proof of the theorem is not difficult at all. Also I think that its statement is not surprising. Indeed, the joint distribution $\gamma_1, \dots, \gamma_{2n}$ is completely characterized by weights/covariances $c_{ij}$ and variances $\sigma_i = {\mathbb E}[\gamma_i^2]$ (that is, by the covariance matrix of $\gamma_i$'s). Thus $P={\mathbb E}[\gamma_1 \gamma_2 \cdots \gamma_{2n}]$ is a function of parameters $\{c_{ij},\sigma_i\}_{i,j}$. It is easy to see that $P$ does not depend on $\sigma_i$'s — if we add a Gaussian r.v. $\gamma'$, independent from all $\gamma_i$'s, to some $\gamma_{a}$, variance $\sigma_a$ will change, but neither $P$ nor parameters $c_{ij}$ and $\sigma_{b}$ (for $b\neq a$) will change. Thus, $P$ must depend only on $c_{ij}$'s. Further, the expression for $P$ must be symmetric and homogeneous (if we multiply all $\gamma_i$'s by $\alpha$, then $c_{ij}$'s are multiplied by $\alpha^2$ and $P$ is multiplied by $\alpha^{2n}$). Given these observations, the statement of the theorem looks very natural.


Writing a paper as a single author in 1st person singular I am writing papers in theoretical computer science sometimes being a nonanonymous single author. Earlier, I used the 1st person plural in such papers, e.g.:

  We will show that the complexity classes X and Y coincide.

I am neither a native English speaker nor extremely good at English. Recently, I've gotten an advice from a native English speaker (who is into science but not a computer scientist) to use the 1st person singular instead:

  I will show that the complexity classes X and Y coincide.

He claimed that this style is widespread in "Nature" and other toplevel journals. I'm not used to this style of writing at all; sentences in the style "I have shown that Γ is well-defined on ℂ \ ℤ⩽0" inside proofs seem very unnatural to me.

Which style is more appropriate for theoretical computer science papers?

It is very clear to me that this question is strongly biased by the area (otherwise, I'd have asked ell.se or referred to https://academia.stackexchange.com/q/2945/7734), so I'm asking at cstheory. My question is addressed to mature theoretical computer scientists who are also native English speakers with a perfect command of English.

I am not a native English speaker, but I don't think this is important here. The appropriate thing is not what an English professor or a poet suggests, but what is standard in the particular field. And from my experience, "we" is the standard in theoretical computer science. As noted by usul in his comment, you can interpret the "we" as the author including the reader. I can think of several reasons why "we" is better than "I":

It sounds more natural and less egocentric.
A paper in theoretical computer science is not about your personal opinion, but you state and prove general facts. Replacing "we" with "I" in terms such as "we thus have" is therefore weird since what follows is generally true, not only for you.
Submissions are often anonymous. You don't want to reveal that the paper has been written by a single author in the submission (and you don't want to change "we" to "I" in the final version).

Edit: An exception are parts of the paper that are subjective, e.g., the acknowledgement section: I would like to thank András Salamon and Boaz Barak for pointing this out.


Minimum spanning tree over all vertex matchings I ran into this matching problem for which I am unable to write down a polynomial time algorithm.

Let $P, Q$ be complete weighted graphs with vertex sets $P_V$ and $Q_V$, respectively, where $|P_V| = |Q_V|=n$. Also, let $w_P$ and $w_Q$ be the weight functions on the edges of $P$ and $Q$, respectively.

For a bijection $f: P_V \to Q_V$ we modify $Q$ in the following fashion: If $f(p) = q$ and $f(p^\prime) = q^\prime$ with $w_P(p, p^\prime) > w_Q(q, q^\prime)$ then set $w_Q(q, q^\prime) = w_P(p, p^\prime)$. Denote this modified graph by $Q_f$ and let $W(Q_f)$ be the sum of weights of the minimum spanning tree of $Q_f$.

Problem: Minimize $W(Q_f)$ over all bijections $f: P_V \to Q_V$.

How hard is this problem? If "hard": what about approximation algorithms?

(Moved from comments) Here's an idea for getting a constant factor approximation, assuming P and Q satisfy the triangle inequality. I thought it might give a 2-approximation, but all I can prove right now is an approximation ratio of 4.

(1) In the problem as stated, the weight of edge $pq$ in the combined graph (after the correspondence $p$–$p'$ and $q$–$q'$ is determined) is $\max\{P(pq),Q(p'q')\}$. Instead, let's use $P(pq)+Q(p'q')$. This loses at most a factor of two but makes the problem easier to describe: we are now trying to find a spanning tree in $P$, and an isomorphic spanning tree in $Q$, with minimum total weight. The correspondence between $P$ and $Q$ is then given by the isomorphism between these two trees.

(2) In $P$, find a minimum spanning tree, and use the path-doubling Euler tour technique to find a path with at most twice the weight. Do the same thing independently in $Q$. The result is two isomorphic trees (both paths) that are separately at most twice the weight of their graph's MSTs, and therefore at most twice the cost of the solution to the minimum isomorphic spanning tree problem, and four times the weight of the original problem.

(3) The original problem is NP-complete, by a reduction from Hamiltonian path. Let $P$ be defined from a graph in which you wish to test the existence of a Hamiltonian path; define $P(pq)=1$ when $pq$ is an edge in $P$ and $2$ when $pq$ is not an edge. Let $Q$ be defined in exactly the same way from a path graph. Then there is a solution of total cost $n-1$ if and only if the graph from which $P$ was defined has a Hamiltonian path. Probably this can also be used to prove inapproximability below some fixed constant.


What is the importance of a TCS researcher in a mostly applied CS department? Stating the title in another way, how to convince a strong applied CS department that a theorist would be a better choice than one more applied computer scientist?

I understand that it is natural for a applied department to want one more expert on a specific field. On the other hand, diversity is important and I think the importance of a theorist goes beyond better theory courses.

What is the importance of a TCS researcher in a mostly applied CS department?

I am really not qualified to give an informed answer to your question, but there are many reasons for which a theory-oriented researcher might be a good fit for a more applied environment.

The main reason that comes to mind is this: good theoretic foundations are invaluable for a thorough understanding of an application which in turn increases trust, efficiency and decreases mental effort. In general it allows work to proceed much faster, as the foundations provide a mental reference that can be easily extended or made explicit.

I'm sure there are many examples in complexity theory, where an abstract approach has led to fantastic practical improvements in concrete implementations, but the field I am the most familiar with is "theory B", in which programing language design has greatly benefited from advances in pure computing theory research.

Haskell is a particularly good example. On the theory side, we have simple core languages like system $\mathrm{F}_\omega$ which have proven to be a very useful base for the core language of the GHC compiler. The research in type inference/reconstruction and more recently, on dependent types has guided the foundations of the Haskell design, including the Hindley-Milner architecture and GADTs. Monads, of course, were introduced in the from the most abstract domain of mathematics to the computing world by Moggi, a theorist.

More pragmatically, knowledge of the theory of operational semantics turns out to be an invaluable tool for language extensions: the paper which introduces Software Transactional Memory in Haskell has explicit operational semantics for the small sub-language containing the STM constructs. This creates a reference for the implementation, and the ability to prove properties about a correct implementation, creating trust and understanding.

All this point to the fact that having a strong theory background is an important asset of every research team, including those with a strong application theme.


What does PAC-learnability say about the learner runtime? I am new to PAC-learnability. Assume a class $\mathcal{H}$ of hypotheses is PAC-learnable. Then all we know that if we draw polynomial number of examples (in $\delta$ and $\epsilon$), we can return a hypothesis with high accuracy.

But how this related to the complexity of the learner $L$?. Because I often read $\mathcal{H}$ is PAC-learnable if there exist an algorithm $L$ runs in time polynomial (in $\delta$ and $\epsilon$).

PAC comes in two flavors -- "information theoretic PAC" and "efficient PAC." The latter asks for computational efficiency whereas the former cares only about sample size.  One usually understands which is referred to from context.

Indeed, it is not known whether (efficient) PAC learning is NP-hard in general, but results on the cryptographic hardness of learning as well as on hardness of proper learning make it universally believed that learning is hard.


Are aspects of the 20 questions game ambitious enough for graduate research? I am finishing a masters program this year and I'm interested in doing a Ph.D. in the field of Artificial Intelligence.

I have an idea I've been tinkering with for a while, but some people have told me that it is not ambitious enough for Ph.D.-level research. I'm not sure if this is because the TCS community already knows all there is to know about it or because I have failed to express myself adequately (bad sales pitch). Based on what I could find online, not all that much has been done.

So, I am going to describe what I thought about doing and I would like to ask if you think this is a promising start idea and if it has the potential to lead to something graduate-level worthy.

I want to research efficient and reliable ways to implement a distributed system that can identify entities based on data collected from its users. To give a concrete example of this, I am going to use the 20 questions game.

Existing implementations of this can be found at http://www.20q.net/ and http://www.akinator.com/ however these are closed: no official details whatsoever on how they do it exist anywhere that I can find (subquestion: in general, if someone does something but does not publish how it's done, how worthy is (much) later research that explains how it can be done?).

There are also no details on the required processing power (performance can easily be seen to be very good, although also hard to quantify exactly - is this because they're smart about whatever it is they do or because they run the site on supercomputers?) and the reliability (how often they guess right, under what circumstances etc.) of these systems.

Of course, one can say "use neural networks", "use bayesian classifiers", "use KNN", "use this special form of decision trees: ____", but how well will these work (is it that obvious that they even will?), how exactly they need to be implemented to work efficiently and reliably, how they can be implemented in a distributed manner that is accesible and cheap (for example, if they could be implemented efficiently using widely-used relational databases such as MySQL, that would be great), how they can be tailored to learn from user inputs and probably other factors seem to be up for research.

The problem is more complicated than it seems I feel, because players can also lie, and you'll notice akinator will guess right in many of those cases as well - so it's not so easy as using a decision tree. As for the other approaches, many questions arise as well, such as scalability, reliability and exact mechanics that are provably best (or at least better than most others) for this specific problem.

At first, based on what I read online, the problem did not seem too complicated, but when I thought and learned more about what people were suggesting, I quickly started to find various flaws. Then I started to write code and noticed even more potential shortcomings, so now I feel that the problem has a lot more that can be learned from it than trivial implementations of various existing concepts.

Does this have any potential or should I start looking someplace else entirely?

A PhD thesis should have references to the published literature and should be extending results in that literature.  So it is important to be able to say, these serious researchers did something but we do something they either were not able to do, or at least did not think of doing or did not have time to do, but would want to do.


How to properly define a zero-knowledge proof system with oracle access An $IP$ system $(P,V)$ is zero-knowledge (ZK) for some language $L$ if for every probabilistic polynomial-time verifer $V^*$ there exists a probabilistic polynomial-time algorithm $S$ for every $x\in L$ such that the output distribution of $(P,V^*)(x)$ and $S(x)$ are "close". Close means that the probability distribution of their outputs are either "equal" (perfect ZK), "statistically close" (statistical ZK), or "computationally indistinguishable" (computational ZK).

My question is,

  if we allow the honest-verifier $V$ to have access to oracle $O$, do we have to allow any other cheating-verifier $V^*$ to also have access to $O$? Or, do we just simply consider all cheating-verifiers without access to any oracle?

My main problem is that, intuitively, the complexity classes for ZK might be very different depending on if we allow the cheating-verifiers such oracle access.

I cannot find any reference regarding relativized classes of ZK. If anyone could direct me to any reference I will really appreciate it. I'm aware of the Random Oracle model (RO), where all parties, even malicious ones, have access to a random oracle. But the goals, motivation, and applications of RO are not the ones I'm interested. I'm interested in relativization results in the Baker-Gill-Solovay sense.

Regarding your reference request, I remember the following paper off the top of my head:

Willaim Aiello and Johan Hastad. 1991. Relativized perfect zero knowledge is not BPP. Inf. Comput. 93, 2 (August 1991), 223-240. http://dx.doi.org/10.1016/0890-5401(91)90024-V.

Now, to answer your question: Consider any NP-complete language $L$, let $G$ be a generator for a public-key encryption scheme, and define $O$ as a decryption oracle for this encryption system. Finally, let $(P,V)$ be a protocol for proving membership in $L$.

Based on $(P,V)$, define the following modified protocol $(P',V')$: In the beginning of the protocol, $P$ uses $G$ and generates a public key pair $(pk,sk)$, and sends $pk$ to $V'$. Moreover, any message exchanged in $(P,V)$ in encrypted using $pk$ in $(P',V')$.

The prover can find the decrypted messages using $sk$, and the honest verifier $V'$ can use the oracle $O$ to find the decrpted messages. However, no other verifier $V^*$ can follow the protocol if we disallow their access to $O$. Therefore, the protocol is ZK for any cheating verifier!

In general, I think the definition should allow any verifier to access $O$, to prevent "twisted" protocols such as the one described above. The same holds for the distinguisher and simulator. However, I believe the prover need not necessarily have access to $O$.


Upper bound on the size of a Concept Lattice (Galois Lattice)? A context is a tuple $(O, A, R)$ where $O$ is the set of objects, $A$ the set of attributes and $R \subseteq O\times A$ is a relation. For $o \in O$ and $a \in A$ we read $oRa$ as the object $o$ possesses the attribute $a$.

For $P \subseteq O$ and $B \subseteq A$ we define $P'=\{a \in A |  \forall o \in P \, oIa \}$ and $B'=\{o \in O |  \forall a \in B \, oIa \}$.

$P'$ is the set of attributes shared by all object of $P$ and $B'$ is the set of objects having all the attributes of $B$.

A concept of the context $(O, A, R)$ is a couple $(P, B)$ where $P \subseteq O$ and $B \subseteq A$ such that $P'=B$ and $P=B'$.

The concepts may be organised according to a partial order in a structure called a concept lattice (or "galois" lattice). For more info check the wikipedia page on Formal Concept Analysis.

The number of concepts in a concept lattice is bounded by :

$2^{1+\sqrt{|R|}}$ as told in this paper (which mentions a result from this paper in german). Note that their upper bound is tighter - the one I give here is less precise.
$2^{|O|+|A|}$ according to this paper (which is presented as a trivial easy upper bound).

I dont understand why these upper bounds are that large.
Intuitively I would say that the number of concepts is bounded by $min(2^{|O|}, 2^{|A|})$. I get this intuition from the observation that since for any pair of concepts $(P_0, B_0)$ and $(P_1, B_1)$ we have $P_0=P_1$ iff $B_0=B_1$, then there can not be more concepts than the number of object sets neither than the number of attribute sets appearing in the lattice.

Could someone explain me if I did a mistake ?

Many thanks, Luz

As told in the previous comments, $min\{2^{|O|}, 2^{|A|}\}$ is a correct upper bound.

When the parameter $R$ is also available, we can improve the upper bound to $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}}\}$


Is there an algorithm for minimizing an NFA with respect to bisimilarity rather than language equivalence? DFA minimization is the problem of transforming a given automaton to an equivalent one with the minimum number of states.
Equivalence is taken to be language equivalence.

Milner introduced the notion of bisimilarity, and in his book on the $\pi$-calculus, he motivates bisimilarity by first studying it as an equivalence relation on (states of) finite automata (interestingly non-deterministic ones).

So, has there been any study of the problem of minimizing an NFA with respect to this equivalence relation, bisimilarity (say of initial states), instead of equivalence of the recognized language?

Yes, see for example here:

Johanna Högberg, Andreas Maletti, Jonathan May,
Backward and forward bisimulation minimization of tree automata,
Theoretical Computer Science 410(37), 2009, pp. 3539-3552,
https://doi.org/10.1016/j.tcs.2009.03.022


On the Proof Technique of Boneh-Lynn-Shacham Gap Signatures In paper "Short signatures from the Weil pairing" by Boneh, Lynn and Shacham, I was going through the security proof just like any other signature.

But the technique used in this paper is quite unique. Rather than using the normal challenger and adversary interaction, they have divided the proof into 6 games where each game is extended sequentially from the previous games.

I am not sure why they have used this approach instead of the normal game. Does this kind of security proof aid in reducing the probability easier or have they just given it from an "easy to read and understand" point of view?

Thanks!

The technique of "hopping" from one game to another, and proving the security through a "sequence of games" is not new. In particular, there are several papers which discuss these techniques, and exemplify them through various security proofs. The famous examples are:

Sequences of Games; A Tool for Taming Complexity in Security Proofs by Victor Shoup (2006)
Code-Based Game-Playing Proofs and the Security of Triple Encryption by Mihir Bellare and Phillip Rogaway (2008). Side note: This paper is a bit hard to grasp, so don't start with this one! The extended abstract of this paper is published in Eurocrypt 2006 under the name The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs.
A Note on Game-Hopping Proofs by Alexander W. Dent (2007). Side note: This paper introduces another famous technique which was omitted from the above two papers.

Regarding your question, I use a quote from the last paper cited above:

  In a game hopping proof, we observe that an attacker running in a particular attack environment has an unknown probability of success. We then slowly alter the attack environment until the attacker’s success probability can be computed. We also bound the increase in the attacker’s success probability caused by the changes to the attack
  environment. Thus, we can deduce a bound for the attacker’s success probability
  in the original environment.

Thus, the reason for using several games is that in each game, we simplify the computation of some unknown probability, without altering it in a significant way. This continues until we reach a game in which the computation of the probability is easy enough.


Classic Neural Network Layout for regression: is the score function derivable? I need to solve an optimization problem based on a function f(X). This function is not known, but it can be estimated from a training set. So first I train a model, then I get the score function f(X), and then I can use this function to solve my optimization problem.

So far, in my problem, I used a simple polynomial regression, and hence the score function is a polynomial. With this score function, the optimization problem works very well since it is infinitely derivable.

Now I want to improve f using a more complex model, i.e. a classic neural network for regression. I wonder: what kind of properties does the score function have in neural networks? Is it at least continuous? Is it derivable?

It depends on what activation function you use.  With all standard activation functions, neural networks are continuous.  With ReLU activations (the most typical choice of activation function), they are piecewise differentiable.  The partial derivatives (the gradient) can be computed efficiently (using so-called "backpropagation"), and standard neural network frameworks will automate this process for you, as computing the derivative is part of how neural networks are trained.  Consequently, it is possible to use gradient descent methods to find $x$ that (approximately) minimizes $f(x)$, when $f(x)$ is instantiated as a neural network.  $f(x)$ is not convex so you are not guaranteed to find the global minimum but for many problems this may be adequate; in others, you can adjust gradient descent (e.g., using random restarts) to mitigate those problems.


What's the difference between "adaptive sorting" and "sorting almost sorted data quickly"? A SIGMOD 2014 paper from Microsoft Research states that the "importance of sorting almost sorted data quickly has just emerged over the last decade", and goes on to propose variants of Patience sort and Linear Merge, and measure their performance on synthetic "close to sorted" data.

It seems to me that this description matches the theme of "Adaptive Sorting", covering algorithms taking advantage of existing preorder in sequences to be sorted, which has been the topic of various publications (albeit in the community of theoretical computer science rather than databases) from as early as 1979:

 - 1979-CTCS Sorting Presorted Files - Mehlhorn
 - 1980-CACM Best Sorting Algorithm For Nearly Sorted Lists - Cook, Kim
 - 1985-TCom Measures Of Presortedness And Optimal Sorting Algorithms - Mannila
 - 1992-ACMCS ASurvey Of Adaptive Sorting Algorithms - Estivill-Castro, Wood
 - 1994-IC Sorting Shuffled Monotone Sequences- Levcopoulos, Petersson
 - 1995-DAM A Framework For Adaptive Sorting - Petersson, Moffat

Am I missing a key difference between those approaches or is it a mere occurrence of weak communication between the database and TCS communities?

I think the importance of "sorting almost sorted data quickly" in the database community is because of good streaming and/or parallel algorithms for k-sorting and for k-sorted id generation. (e.g. http://link.springer.com/chapter/10.1007%2F978-3-540-77050-3_2#page-1) Adaptive sorting is a more general topic: for instance, reverse order would not be what the database community cares about, but would be perfectly reasonable to exploit more generally.


Introductions to steganography from an information-theoretic standpoint Can I get some introductory references for steganography from an information-theoretic standpoint? I recently listened to a talk on it, and the speaker said that he knew of no good introductions to the field besides a few links and papers.

Kessler, Gary C. An Overview of Steganography for the Computer Forensics Examiner. Retrieved on 02/12/2015. www.garykessler.net/library/fsc_stego.html
Hopper, N. J., Langford, J., and von Ahn, L. (2002). Provably Secure Steganography. IEEE Transactions on Computers, 58, 662 - 678.
Hundt, C., Liskiewicz, M., and Wolfel, U. (2006). Provably Secure Steganography and the Complexity of Sampling. Algorithms and Computation, 4288, 754 - 763.

Here is a brief overview and introduction to steganography:

Christian Cachin. Digital steganography. In Henk C.A. van Tilborg, editor, Encyclopedia of Cryptography and Security. Springer, 2005

Since you asked for an introduction specifically for information-theoretic approaches, you might try this paper as a starting point for more detail:

Christian Cachin. An information-theoretic model for steganography. Information and Computation, 192(1):41-56, July 2004.

If you want a coding-theoretic perspective, you might also enjoy the following papers:

Yin Wang, Pierre Moulin.  Perfectly Secure Steganography: Capacity, Error Exponents, and Code Constructions.  IEEE Transactions on Information Theory, 2008.

Pierre Moulin, Joseph A. O'Sullivan. Information-Theoretic Analysis of
Information Hiding.  IEEE Transactions on Information Theory, 2003.

I do encourage you to also take a look at computational steganography (e.g., the Hopper et al. paper you cite in your question), as many of the powerful results are in the computational security regime


Distributed Consistency using Quorum approach I'm stuck at distributed consistency when using a quorum. In this case we use N servers - 2/3N+1 for the read quorum (Nr), and N/3+1 for the write quorum (Nw).

Now, two conditions have to be satisfied to achieve consistency.

Nr + Nw > N (implies at least one server that performs read was updated)
Nw > N/2

And the second condition is what isn't clear to me. According to wikipedia this ensures that two write operations don't concurrently occur at the same data item. Can somebody evaluate on that?

The idea behind implementing consistency with a quorum is to maintain consistency in one group (that contains the majority of replicas) and forcing, by construction, that reads and writes cannot violate the consistency within that group.

This is done by only allowing updates within a group of replicas that contains the majority of replicas, so that at least one node witnesses all the updates; this is related to the second condition you've mentioned. In more details, consider a scenario for writing:

To complete a write, a client must successfully place the updated data item on more than N/2 (i.e. a majority of) replicas. (The updated data item will be assigned a new version number that is obtained by incrementing its current version number.)
Since the write quorum engages a majority of the replicas, two distinct write operations cannot succeed at the same time. (There do not exist two distinct groups that contain majorities of replicas.)
Therefore, all write operations are serialized and therefore consistency is guaranteed. (At least one node has to be included in two consecutive write operations, while that node will have the highest current version number.)

Note that consistency overall, has to be ensured with respect to both writing and reading. (As an extreme example, a system that does not perform reads will always be consistent.) To that end, mechanisms for distinguishing newer from older values is needed (e.g. a simple version number, as mentioned before) for achieving consistent read operations. This is related to the first condition you've mentioned:
in turn, reading can be achieved with N + x - Nw replicas (where Nw + Nr = N + x, since Nw + Nr > N). Thus the intersection
of the read quorum (of Nr nodes) and the write quorum (of Nw nodes) cannot be empty, so reads cannot overlap with writes, i.e. each read will have to consult at least one replica with the current data item (determined by it's version number).

Note that to control concurrency, mechanisms such as two-phase locking can be used -- for initial query from a set replicas, a reader can use read locks and a writer can use write locks. The locks are released after the operation completes or aborts.

The read/write quorum scheme was first proposed in [1] and it was later generalized into the form you've mentioned in [2]. (These papers cover the topic in more detail.)

[1] Thomas, Robert H. "A majority consensus approach to concurrency control for multiple copy databases." ACM Transactions on Database Systems (TODS) 4.2 (1979): 180-209.

[2] Gifford, David K. "Weighted voting for replicated data." Proceedings of the seventh ACM symposium on Operating systems principles. ACM, 1979.


Are provable quantum speed-ups possible for classes larger than NP? In the oracle query model quantum computers can provably achieve a quadratic speed-up over any classical randomized computer [Grover, BBBV].

Are similar speed-ups provably possible for higher levels of the polynomial hiearchy or even PSPACE or EXP? (i.e. for classes that require single-exponentially many queries classically.)

Note, that I'm not asking for superpolynomial speed-ups. Quadratic is fine. Can I get quadratic speed-up e.g. for finding a satisfying assignment to some quantified formular $\forall x \exists y\; \varphi(x,y)$?

Note that for larger classes "scaling Grover up an exponential" to NEXP gives $2^{2^n}$ vs. $2^{2^{n-1}}$ queries.

For total functions it is impossible to achieve more than a polynomial separation (i.e. $D(f) = O(Q^6(f))$) in the quantum query model, for more info see this cstheory blog post. With promise problems, you can have exponential seperations between the quantum and classical query complexity. However, classical query complexity is sometimes very deceptive in its correspondence to complexity classes; as are partial functions in general. If you don't allow promise problems, you can't get exponential separations and your relevance to the big classes is questionable. You can never expect more than an exponential seperation, because a quantum algorithm can be simulated by a classical computer with exponential overhead (actually, in PSPACE so looking above that is dubious).


Sources for Algorithmic Evolutionary Game Theory I use the title term in a very loose sense.

There is a significant amount of work on evolutionary game theory, including its mathematical foundations. I was recommended "Evolutionary Games and Population Dynamics" but haven't delved into it yet.

There is also a significant amount of work on algorithmic game theory, which is a popular topic on this site.

What I'd like to see is work that makes computational complexity or convergence statements about certain evolutionary dynamics.

Examples (phrased very loosely):

Given a population and an evolutionary scheme, can we give a probabilistic regret bound for the long-term population optimality (compared to the best individual produced?). This seems to relate strongly to ensembles of experts and bandit problems. What about in nonstationary settings?
Given a set of populations of different species that interact in their environment, playing pretty much any sort of multi-player game, what statements can we make about the eventual stability of their strategies or strategy distributions, given their evolutionary strategies.
In any sort of environment with many "niches" (an overbroad way of phrasing it, I understand), either in terms of direct relationship with the environment or in terms of relationships with other species, what statements can we make about how populations will distribute across these niches.
Any problem I haven't asked but should - I'm coming at this with little AGT, TCS, Genetic Algorithms, evolutionary game theory or population biology background; I'm asking my questions from an optimization/machine learning/stats point of view, which may be the wrong one or incomplete.

This is one of the topics where I have been looking for connections for a while. However, they don't seem all the prevalent. The folks working on theoretical biology and economics that use EGT, usually stick to dynamic systems theory and don't don the algorithmic lens. Thus, most results are of the AMath/Physics style, and not of the algorithms and discrete math style. If you are willing to pursue the dynamic systems approach, then there a survey by Hofbauer and Sigmund which is shorter and more recent than their book (I mention it and some passing comments in a previous answer).
One of the places replicator dynamics have been used in complexity related results, is by Marcello Pelillo and co-authors as a heuristic for solving max-clique (reduce max-clique to quadratic programming, solve quadratic programming by using replicator dynamics as your heuristic):

[1] Immanuel M. Bomze, and Marcello Pelillo [2000]. "Approximating the Maximum Weight Clique Using Replicator Dynamics." IEEE Transactions on Neural Networks 11(6)
[2] Marcello Pelillo, and Andrea Torsello [2006]. "Payoff-Monotonic Game Dynamics and the Maximum Clique Problem." Neural Computation 18: 1215-1258.

You can use their results to show that many natural question associated with evolutionary stable strategies are NP-hard (this kind of addresses question 2). In fact, Etessami & Lochbihler showed that it is worse than that and the question of ESS existence is both NP and coNP-hard, but in $\Sigma^P_2$. Recently, Conitzer tightened this to show that "does an ESS exist?" is a $\Sigma^P_2$-complete problem.

[3] Kousha Etessami, and Andreas Lochbihler [2008] "The computational complexity of evolutionarily stable strategies". International Journal of Game Theory, 37(1): 93-113. (First available in 2004 as ECCC tech report TR04-055).
[4] Vincent Conitzer [2013] "The exact computational complexity of evolutionarily stable strategies". The 9th Conference on Web and Internet Economics (WINE). (pdf).

A lot of the interesting EGT questions today are about games on graphs, and although there are some cool dynamic system results, like (also see this question for extensions of this approach):

[5] Hisashi Ohtsuki, and Martin Nowak [2006] "The replicator equation on graphs." _ Journal of Theoretical Biology_, 243 (1), 86-97 (link, blog post)

Most of the work goes through agent-based modeling (see this answer for a spread-of-disease modeling context). These models are usually much more welcoming to complexity and convergence statements. Look at the following book for more:

[6] Yoav Shoham and Kevin Leyton-Brown [2009], "Multiagent systems: algorithmic, game-theoretic, and logical foundations", Cambridge University press.

I think machine learning is a pretty straightforward way to approach EGT, since it is a natural halfway point between the relevant physics (statistical mechanics) and computer science. This has definitely been done, it would take me a bit to find a good reference, but a random reference (which also shows that EGT folks have considered other popular equilibrium concepts, like correlated equilibrium):

[7] Sergiu Hart and Andreu Mas-Colell [2000], "A simple adaptive procedure leading to correlated equilibrium", Econometrica 68(5): 1127-1150
[8] Antonella Ianni [2001], "Learning correlated equilibria in population games", Mathematical Social Sciences 42(3): 271-294.
[9] Ludek Cigler and Boi Faltings [2011], "Reaching Correlated Equilibria Through Multi-agent Learning", AAMAS 2011: 509-516

I definitely hope others give more specific answers, since this is a question I've always wanted to know more about.


Finite Automata with succinct representation of chains of states Consider a kind of automata similar to common DFAs or NFAs where it is possible to represent succinctly linear chains of states. In other words, an automaton like this:

could be represented in this way:

where the thick edge represent the chain of states, where each state is connected to the next by a single edge and all the edges are labeled in the same way, in this case by $a$.

So this is not really a counter or anything fancy, it is just a succinct representation of a very limited special case. By succinct, I mean that by representing the $k$ parameter in binary, the second automaton can be represented in logarithmically less space than the first. Let's call this kind of automata the "succinct automata", SA, so say DSA and NSA for short for the deterministic and nondeterministic variants.

Now, my question concerns the complexity of boolean operations over this kind of automata.

In details:

Given two NSAs $\mathcal{A}$ and $\mathcal{B}$, is it possible to build the NSAs for $\mathcal{L}(\mathcal{A})\cup\mathcal{L}(\mathcal{B})$ and $\mathcal{L}(\mathcal{A})\cap\mathcal{L}(\mathcal{B})$, of size still polynomial in the size of $\mathcal{A}$ and $\mathcal{B}$ (i.e. without paying for the unrolling of the chains before computing the results)?
Is it possible to compute those operations on DSAs (deterministic) guaranteeing that the resulting automata stay deterministic (and still polynomial size)?
Is it possible to determinize an NSA with only a singly-exponential blowup (i.e. without paying for the unrolling of the chains before paying for the classic determinization)?

My feeling on all of these after having though about it a bit is that an exponential increase in size is needed in most of the cases, or that the results must be nondeterministic.

So the question is really: is anybody aware of a place where this kind of problems have been addressed? Has this variant of finite automata being studied before?

This is a very partial answer, but I have some ideas:

Clearly the union of NSAs can be taken without any blowup - just use the nondeterministic union of the initial states.
As for determinization, you'll have a double-exponential blowup. Consider the language $L_k=(a+b)^*a(a+b)^k$. That is, the $k$-th before last letter is $a$. You can easily construct an NSA of size $O(\log k)$ for it, but any DSA would need to "remember" the last $k-1$ letters (the same argument that works for DFAs would work here). So a DSA would need $2^{k-1}$ states, which is a double exponential blowup.
As for union of DSAs, this is more of a conjecture: consider the language $L_p=(a^p)^*$ for a prime number $p$. This can be recognized by a DSA with 2 states and $p-1$ written on one of the transitions. Now, consider the union $L_p\cup L_q$ for $p\neq q$. It seems to me that you'll need a lot of states (i.e. $p\cdot q$) in order to recognize this with a DSA. But I haven't thought this through completely.


Path coloring in general graphs Path coloring is the problem of coloring a set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors.

We know that coloring a set of paths with the minimum number of colors is in $\sf{P}$, if the underlying graph is also a path. It is known that path coloring in trees is $\sf{NP}$-hard. There is a greedy algorithm by Raghavan and Upfal (Efficient routing in all-optical networks,  STOC 1994), which colors any set of paths of load $L$ on an undirected tree using at most $3L/2$ colors. This bound is tight, since there exists a set of undirected paths on an undirected binary tree, which requires at least $3L/2$ colors.

What are the results known for general graphs, both approximation algorithms and lower bounds?

Edit: In the end I did find a reference for the reduction I remembered. It is given in Edge intersection graphs of single bend paths on a grid by Golumbic, Lipshteyn, and Stern. So, to sum up, the class of graphs obtained as intersections of paths on a grid contains all graphs. Therefore, path coloring on grids is as hard to approximate as graph coloring ($n^{1-\epsilon}$-hard).

Original answer:
Path Coloring can be reduced to graph coloring in the obvious way (make a vertex for each path, add an edge if two paths intersect). If the underlying graph in path coloring is allowed to be a grid there is also a reduction in the opposite direction, which means that in this case the problems are equivalent. The reduction does not change the number of colors, so all hardness of approximation results for graph coloring carry over to this case of path coloring, and therefore also when the underlying graph can be any graph.

I heard this reduction in a talk a while ago, but I can't seem to be able to find a reference, so I'll sketch it here.

We start with a graph $G(V,E)$ on $n$ vertices and the question is if it can be colored with $k$ colors. Construct a graph $H$ which is a $n\times ({n\choose 2}+1)$ grid (we index the rows by the vertices of $G$ and the columns by pairs of vertices of $G$). We will add one path in this graph for each vertex of $G$. Initially, each of these paths is simply a row of the grid, so no two of them intersect and they all have length $n\choose 2$. The idea here is that we will use the $n\choose 2$ edges between columns of the grid to simulate the edges of the original graph. For example, if vertex $i$ is connected to vertex $j$ in $G$, with $i<j$, take the path that runs through row $i$ and re-route it as follows: the path now goes from vertex $(i,(i,j))$ to $(j,(i,j))$, then it uses the next edge on the $j$-th row and then it goes back to row $i$. This creates an intersection between paths $i$ and $j$, but no other edge intersections. By adding the rest of the edges of $G$ this way, the resulting instance is $k$-colorable iff $G$ is.


Suggestions on a matching/scheduling algorithm. I have a problem where mentors need to paired with courses, this is similar to the marriage problem or the hospitals/residents problem except that it isn't. The current solution is terribly written and needs to be expanded, plus it's a monte-carlo algorithm. I want to change it to something deterministic

(I'm using weird terminology with "mentor" because my university is weird think of a mentor as a T.A.)

Courses don't "care" which mentor is assigned.
All courses must be assigned a mentor.
All mentors must be assigned one course.
No mentor may be assigned to more than 2 courses.
A mentor may not be assigned 2 courses with identical or overlapping time-slots.
Courses have 3 attributes:
time-slots (may be web-only or hybrid web/classroom)
theme
professor
faculty and/or time-slot may be TBD (too be decided)

Mentors are asked a series of questions:
rank your top 5 time-slots
rate (weight) the value of various themes from 1-7 or dont' care (don't care is the same as a 4 in the current algorithm)
rate (weight) faculty you'd like to work with from 1-7 or don't care (don't care is the same as a 4 as above)
Are you willing to mentor two courses? yes/no
Are you willing to mentor an online or hybrid course? yes/no
Are you trained to mentor an online/hybrid course.

Current system assigns a "score" to each assignment using the questions above and tries to minimize the score.

When combining assignments into a schedule, no extra weightings are added. However, some schedules are considered invalid (as above): assigning a mentor to more than 2 courses or more than 1 if they didn't select "yes" to "I'm willing to mentor 2 courses" and time-slots aren't allowed to overlap.

More complications/edge cases:
certain mentors may be pre-assigned courses. This doesn't take the mentor out of the running but it does take the course out. A mentor may be assigned to multiple courses, so there first one might be pre-assigned, but there second one cannot.
Also, some mentors are "owned" by a certain department, and so may only be allowed to teach "urban studies" courses.

Thoughts on an algorithm I should use?

Edit: for clarity and to answer some questions.
The current solution (monte-carlo) has a function that generates a cost based on your options 1st choice is 0.0 cost, 2nd choice is .33, etc. 7th choice is 4.0. Then the weights for all parameters are summed and the algorithm has to optimize for the lowest score. There are also some other parameters like untrained (0.0 if web and trained, +2.0 to cost if web course and untrained, +2.0 to cost if unwilling to teach web course and web course)

While the entire problem seems under-defined, I believe it's fairly clear that you're dealing with a Multi-Objective Optimization problem, with scheduling simply being the backdrop for this problem.  Most new effort in this field seems to be concentrated on Evolution Algorithms as solutions to these problems.

I personally do quite a bit of work with Particle Swarms in this area mostly because they provide very simple method of visualization in a complicated space.  Other algorithms would include Non-dominated Sorting Genetic Algorithm-II (NSGA-II), or Multiple-objective Bayesian Optimization Algorithm (mBOA).

I would agree with Tsuyoshi in that you may want to spend more time on the problem definition as well.


karger's algorithm contracting nodes not edges Karger's algorithm works by contracting edges, not merging nodes (this is different because nodes need not share an edge).

Is there a reason why this is so?

The run-time of Karger-Stein is usually represented as a function of the number of vertices $n$, not of the number of edges. Therefore, placing an edge of weight $0$ between two vertices that previously did not share an edge would make your algorithm identical to theirs and not change the run-time.


Typing relations terminology – how do I read typing relations? I am currently trying to read up on type theory and have some quick questions on terminology.

In the following rule,

$$
\frac{x:T_1 \vdash t_2 : T_2}{\vdash \lambda x:T_1.t_2:T_1\to T_2}
$$

How would you write that in English? Would the following be correct?

  If we have established that under the assumption that $x$ has type $T_1$, $t_2$ has type $T_2$; then we can derive that under the empty set of assumptions, $\lambda x.t_2$ has type $T_1\to T_2$.

Is this just a shorthand for the following?

$$
\frac{\Gamma,x:T_1 \vdash t_2 : T_2}{\Gamma\vdash \lambda x:T_1.t_2:T_1\to T_2}
$$

Would this be read as If we have established that under the assumptions of the type environment $\Gamma$ and the binding $x:T_1$, that $t_2$ has type $T_2$; then [$\ldots$]?

The two inference rules are different, because the first requires that x:T_1 is the only assumption, while the second allows side assumptions.  This can have subtle effects of the consequence relation for the type theory prevents the type theory from modelling weakening by having as the hypothesis rule:

$$
\frac{}{\Gamma, x:A \vdash x:A}
$$

In your English gloss, I would have under the sole assumption, to avoid confusion with the assumption-gobbling inference rule:

$$
\frac{\Gamma, x:T_1 \vdash t_2 : T_2}{\vdash \lambda x:T_1.t_2:T_1\to T_2}
$$


Hardness of FPT problems Vertex Cover can be easily reduced to Independent Set and vice versa.

However, in the context of parameterized complexity, Independent set is harder than Vertex Cover. A kernel with $2k$ vertices exists for Vertex Cover, but Independent Set is W1 hard.

  How does the nature of Independent Set change in
  the context of FPT and why?

Main idea of the answer: if we reduce an instance of parameterized Independent Set to parameterized Vertex Cover, then the parameter than we end up with depends on the size of the graph, and does not only depend on the input parameter. Now for some more detail.

As you know, a parameterized problem $Q$ is in (uniform) FPT if there is an algorithm that decides whether an input $(x,k)$ is contained in $Q$ in time $f(k) |x|^{O(1)}$ for some function $f$.

Since you can decide whether a graph $G$ has a vertex cover of size $k$ by picking an edge, and branching on which of its two endpoints to put in the vertex cover, this branching only goes $k$ deep (else you've put more than $k$ vertices in the cover), and easily runs in time $O(2^k n^2)$; therefore $k$-Vertex Cover is in FPT.

Now suppose we want to try use this algorithm to show that parameterized Independent Set is in FPT; assume we are given a graph $G$ on $n$ vertices and want to decide whether it has an independent set of size $\ell$. This is equivalent to asking whether $G$ has a vertex cover of size $n - \ell$. So we use our above algorithm to compute the answer in $O(2^{n - \ell} n^2)$ time. For our FPT algorithm, the exponential function in the running time may depend on the parameter, which is $\ell$, but it may NOT depend on the size of the input, which is $n$; but the approach we sketched uses time exponential in $n - \ell$ and is therefore not an FPT parameter with respect to the parameter $\ell$. This is why the fact that Vertex Cover is in FPT does not imply that Independent Set is in FPT.


Any Graph is a Model (! or ?) I know this could be considered a pointless question. However despite I am quite convinced that any possible model (i.e. UML, SysML, natural language, math, etc.) can be defined by means of a graph I do not know if there is a way to formally prove there exist an isomorphism between the set of Models and the set of Graphs.

I guess one should first define what a model is and I guess a possible answer is that a model can be considered as a sentence of the language defined by its meta-model. Thus models are languages. The question is therefore if there is an isomorphism between the set of languages and the set of graphs or, less formally, if it is provable that any possible language can be represented by means of a graph. I guess that the Chomsky works on languages could help but I can not find a reference on the Internet of such demonstration.

If you look at things from a model-theoretic perspective, the basic ingredients you have are atoms, relations, and functions. Atoms could be modelled using nodes of the graph, and binary relations and single argument functions could be modelled using graphs. If you are willing to allow hyper-edges in your graph, then the remainder of the relations and functions can be modelled.

I don't think that there is anything deep to this observation.


A question on linear extensions of partial orders If you're given a collection of partial orders, topological sort will tell you if there's an extension of the collection to a total order (an extension in this case is a total order consistent with each of the partial orders).

I've come across a variation:

  Fix a set $V$. You're given sequences $\sigma_1, \ldots \sigma_k$ of
  elements drawn from $V$ without repetition (the sequences are of
  length between 1 and $|V|$).

  Is there a way to fix orientations for each of the sequences (either
  forward or reverse) so that the resulting collection of chains (viewed
  as a partial order) admits an extension ?

Is this problem well-known ?

Note: The orientation is chosen for an entire sequence. So if the sequence is $1-2-4-5$, you can either keep it that way, or flip it to $5-4-2-1$, but you can't do anything else.

If every sequence has length 3, the problem is known as Betweenness. Even the Betweenness problem is NP-hard. In this problem, we are given a set of vertices and a set of constraints of the form $u$ lies between $v$ and $w$. Our goal is to order all vertices so as to maximize the number of satisfied constraints. Opantry [1] proved that the decision version of this problem is NP-hard. Chor and Sudan [2] proved that it is SNP-hard.

The best known approximation algorithm for the problem, by Chor and Sudan, satisfies 1/2 of all constraints if the instance is completely satisfiable.

[1] J. Opantry. Total Ordering Problem, SIAM Journal on Computing, 8(1):111—114, Feb. 1979.

[2] B. Chor and M. Sudan. A geometric approach to betweenness, SIAM Journal on Discrete
Mathematics, 11(4):511-523, Nov. 1998.

Edits: clarified that the decision version of the problem is NP-hard.


Efficiently Samplable Distributions What does it mean for a distribution to be efficiently samplable?

This came up in the discussions about the distributions used in the recent attempted P!=NP proof.

The context was that a distribution modeled as a directed graphical model that can be factored such that each factor is sub-exponential in size or dependent on a polylog number of parents then it is efficiently samplable.  In contrast, if a factor is dependent on O(n) parents then the table size is exponential and no longer efficiently samplable.

The barrier here to efficient sampling appears to be the exponential size of the table required to describe the factor that depends on O(n) parents.  Is this the key point or is there some other barrier?

I should clarify, that if one could replace the exponential sized table for the conditional distribution that depends on O(n) parents with a polynomial time function that returns the value of $P(x_n;x_1...x_{n-1})$ given the parents then it seems the problem becomes efficiently samplable.

Could you please provide a reference to the context, where the term "efficiently samplable distribution" is used? Because there is a well-known concept called "polynomial-time samplable distribution", so because in TCS we usually mean "efficient" = "polynomial-time", I guess these two can coincide.


Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$? May be this is trivial but I do not know the answer.

As far as we know $$\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ holds.

As far as we know $$\mathsf{NP}\cup\mathsf{coNP}\subseteq\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ could hold. Am I correct in this?

If so is there a problem that is currently known to be in $$\mathsf{BPP}\backslash\mathsf{NP}\cup\mathsf{coNP}=\mathsf{BPP}\cap\overline{\mathsf{NP}}\cap\overline{\mathsf{coNP}}$$ but conjectured to be in $\mathsf{P}$ just because of our belief $$\mathsf{P}=\mathsf{BPP}$$ should be true essential verdict?

That is is there a natural problem (not amalgamated ones) with a randomized poly algorithm nevertheless does not have a short yes or no certificate? A problem that comes close is PIT which is not known to be in $\mathsf{NP}$ but is in $\mathsf{coNP}$ which is the basis of the amalgamated problem (non-natural) below by Ricky Demer.

In your initial use of it, there was no need for "As far as we know" - We do know that

promiseBPP ⊆ promiseS2P  ⊆  promise - (Σ2 ∩ Π2)

holds.

If  ZPP = NP  then

NP ∪ coNP  =  ZPP ∪ coZPP  =  ZPP ∪ ZPP  =  ZPP  ⊆  BPP  ⊆  S2P  ⊆  Σ2 ∩ Π2

, so as far as we know

NP ∪ coNP  ⊆  BPP  ⊆  Σ2 ∩ Π2

could hold.

If  NP = coNP  then    BPP \ (NP ∪ coNP)  =  BPP \ S2P  ⊆  BPP \ BPP  =  { }  ,

in which case there are no problems "outside class  NP ∪ coNP  but inside BPP".

In particular, no problems are "currently known to be outside class  NP ∪ coNP  but inside BPP".

I'm also not aware of any languages L known to be in BPP for which

it's also known that if L is in  NP ∪ coNP  then    BPP  ⊆  NP ∪ coNP  .

"Is exactly 1 of these 2 polynomials identically zero?"  is "a problem currently known to be"

inside BPP but not known to be in  NP ∪ coNP .    More generally, non-monotone

combinations of [problems in RP that aren't known to be in coNP] yield such problems.

There is an oracle relative to which BPP is not a subset of PNP,

so presumably  BPP ⊆ PNP  is not known to hold.

If that containment is indeed not known to hold, then there pretty much can't be any known

result to the effect that "All problems in BPP are reducible to amalgamations of NP problems.".


What is the significance of nominal techniques? What is the significance of nominal techniques, as far as their application to the formal theory of bound variables is concerned?

I have been reading M. J. Gabbay's expository work on the topic that appeared in Bulletin of Symbolic Logic.  I understand that, the main contribution of nominal techniques to the nasty problem of $\alpha$-conversion is that they introduced new principles of induction and recursion, and a new quantifier.  However, I am not sure if the use of orbits instead of $\alpha$-equivalence classes is strictly necessary for these purposes - because orbits and equivalence classes are essentially the same thing.

I understand the theory of nominal sets are very fruitful in that it can be applied in many different areas - including infinite automata theory and domain theory, due mainly to its general nature.  I would like to know the relevance of the theory's generality - replacing $\alpha$-equivalence classes with orbits - in the very first problem that it is meant to solve, that is, $\alpha$-equivalence of syntactic objects.

EDIT: I knew how nominal techniques  could be applied to reasoning up to $\alpha$-equivalence;  my question was more about the theory's internal methodology, that is, the focus on the group action.

Here's an attempt to answer my question: automorphisms on the set-theoretic universe induced by permutations of atoms are crucial in proving the new recursion/induction principles, so is the reinterpretation of $\alpha$-equivalence as orbits.  However, this reinterpretation might or might not be relevant to the users of the recursion/induction principles.

Let me know if there is something in my answer to be added or corrected.

EDIT 2: My question might have been better phrased as:  do we really need to appeal to axiomatic set theory - something very powerful - to get a proper treatment of alpha-equivalence?

Short answer. Formal reasoning about binding and $\alpha$-conversion with  nominal approaches is closer to intuitive reasoning than alternative approaches.

Longer answer. Binders arise everywhere in mathematics and computer science.
Dealing with binders has historically been done in a handwaving way (e.g. assuming Barendregt's variable convention). This works well in informal mathematics, but breaks down in formal reasoning. In implementations of programming languages, this problem was initially handled with some form of renaming using a global operation, often called gensym, that creates globally fresh variables. Already in the implementation of programming languages that has some disadvantages, but the problem comes to the fore when reasoning about formal languages with binders, in particular about certified software.

The problem is that in early formal proofs about languages with binders, a disproportional amount of effort was dedicated to proving largely uninteresting lemmas about substitutions and $\alpha$-conversion. The core of the problem is that programming language  syntax is usually defined inductively. For example

$$
  P \quad ::= \quad x = E \ |\  while\ P\ do\ P \ |\   ...
$$

Given this genesis of programming language
syntax, it is natural to prove program properties by structural induction on program syntax. This works fine for simple languages like that above, but once we add binders

$$
  P \ ::=\ ... \ |\ \lambda x.P
$$

the situation changes. $P$ is not a subterm of $\lambda x.P$. We want to identfy programs up to consistent
renaming of bound variables, for example we don't want to distinguish
$\lambda x.ax$ from $\lambda y.ay$. In other words, programs are
equivalence classes ... and structural induction goes out of the
window.

Several techniques have been proposed for a better mathematisation of  the informal handling of binding.

Higher-order abstract syntax,
De Bruijn representation of binding,
Getting rid of variables altogether by using combinators.
Nominal technique which replaces substitution by swapping. Swapping is essentially* a first-order operation and can be internalised in the ambient logic.

Of all those proposals, the reasoning about binders with nominal techniques is closest to the intuitive "handwaving" done to handle binders in informal reasoning. That is the key advantage of nominal techniques. This might be best observed in Nominal Isabelle, where most of the reasoning about binders can be hidden from the user. See Nominal Techniques in Isabelle/HOL for a discussion.

* There is a subtle issue  in that
if you want to define higher-order functions by recursion in nominal logic, the recursion operator requires some kind   of freshness. See the conclusion of Pitt's Nominal logic, a first order theory of names and binding, which points out that "Nominal Logic does not give a complete axiomatisation of the
notion of finite support that underlies the notion of freshness in FM-sets. Nevertheless, the first-order
properties of a notion of freshness of names presented in this paper seem sufficient to develop a useful
theory, independent of any particular object-level language involving binders".


Complexity of counting graph endomorphisms A homomorphism from a graph $G = (V, E)$ to a graph $G' = (V', E')$ is a mapping $f$ from $V$ to $V'$ such that if $x$ and $y$ are adjacent in $E$ then $f(x)$ and $f(y)$ are adjacent in $E'$. An endomorphism of a graph $G$ is a homomorphism from $G$ to itself; it is fixed-point-free if there is no $x$ such that $f(x) = x$ and it is non-trivial if it is not the identity.

I have recently asked a question related to poset (and graph) automorphisms, that is, bijective endomorphisms whose converse are also an endomorphism. I found related work about counting (and deciding the existence of) automorphisms, but searching I couldn't find any results related to endomorphisms.

Hence my question: What is the complexity, given a graph $G$, of deciding the existence of a non-trivial endomorphism of $G$, or of counting the number of endomorphisms? Same question with fixed-point-free endomorphisms.

I think the argument given in this answer extends to endomorphisms and justifies that the case of directed bipartite graphs, or posets, is no easier than the problem for general graphs (the problem for general graphs reduces to this case), but its complexity do not seem straightforward to determine. It is known that deciding the existence of an homomorphism from one graph to another is NP-hard (this is clear as it generalizes graph coloring), but it seems like restricting the search to homomorphisms from a graph to itself might make the problem easier, so this doesn't help me determine the complexity of these problems.

Counting endomorphisms or fixed-point-free endomorphisms is complete for $\mathsf{FP}^{\mathsf{\# P}}$: given a connected graph $G$, consider the graph $G'$ which is the disjoint union of $G$ and a triangle. Then $|\text{End}(G')| = (|\text{End}(G)| + \# 3COL(G))(\#\{\text{triangles in } G\} + 3^3)$, so $\# 3COL$ can be computed using two endomorphism counts (and by a general result, even just one suffices) and some poly-time post-processing. Note that the number of triangles can be counted in cubic (or even matrix multiplication) time. The same equation holds for fixed-point free endomorphisms, since the 3-colorings and triangles are fixed-point-free endomorphisms of $G'$.

If you would like $G'$ to be connected, you can do as follows. First note that counting vertex-colored graph endomorphisms (where vertices of color $c$ can only be mapped to other vertices of color $c$) is equivalent to counting graph endomorphisms, as follows. Let the colors be $\{1,...,C\}$. For each vertex $v$ of color $c$, add in a new disjoint odd cycle $C_v$ of size at least $n + 2c$ ($n=|V(G)|$), and connect one vertex of $C_v$ to $v$. Every endomorphism of $G$ corresponds to $2^n$ endomorphisms of the new graph (for each cycle, you have two choices of how to map it). Note that no vertices of $G$ can map to vertices of any $C_v$, since the cycles are too large (you'd have to be able to fit one cycle inside another, which you can't for odd cycles).

Now, to make a version of $G'$ that is connected, we start with a colored version, and then apply the above transformation. Start as before, by adding to $G$ a disjoint triangle $\Delta$. Now add a single new vertex $v_0$ that is connected to every vertex in $G \cup \Delta$. Color $v_0$ red and all other vertices blue.


Complexity of isotopy of embedded graphs I am looking for previous work on the following problem: given two graphs embedded in the plane without crossing, determine if they are isotopic. By isotopic I mean that there is a continuous deformation of the plane tranforming one embedding to the other, without introducing any crossing between edges during the transformation.

This isotopy notion is stronger than the much studied isomorphism of (planar) graphs, for instance when a connected component is nested in another (the nesting is preserved by isotopy, not isomorphism).

Do we know anything about the complexity of this problem, or anything similar?

A similar question asks about how to define this isotopy notion in combinatorial terms:
Equivalent embeddings of a graph

Precision: I am primarily interested in the case where the embedded graph is not connected.

Since you only care about embeddings in the plane, and every oriented homeomorphism of the plane is isotopic to the identity (Alexander's trick), testing whether two embedded graphs are isotopic is equivalent to testing whether they are congruent by an oriented homeomorphism. And this is a purely combinatorial notion: for example it is equivalent to the two graphs having the same (extended) combinatorial maps (Lemma 5 in our paper with Eric that you cited in your answer).

Testing whether two embedded graphs have the same combinatorial map is solvable in linear time according to this paper but I have never found the full version, and for planar maps it is actually quite simple.

If you already have the isomorphism between the graphs, this is easily doable in linear time (just check that the combinatorics agree everywhere). If you don't, you need to find it. Luckily, planar graph isomorphism is easy and doable in linear time (Hopcrof-Wong).

Now that does not solve your problem exactly, because maybe this could find a graph isomorphism that is not a map isomorphism, while another graph isomorphism would be. But this is not a real issue: the disconnected components are arranged in a tree-like fashion due to the nesting, and thus can be encoded with a tree. Similarly, bi-connected components are arranged in a tree (the block-cut tree), and so are tri-connected components (the SPQR tree). And tri-connected components have a unique embedding, and thus are map-isomorphic if and only if they are graph-isomorphic. (some care needs to be taken (e.g. ordering and/or labeling) so that these trees precisely encode the map you are looking at).

So mixing the Hopcroft-Wong algorithm with some tree isomorphism algorithm should solve your problem in linear time. (this is actually similar to the planar graph isomorphism algorithm, see for example Hopcroft-Tarjan)


Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$? Define $\mathsf{DTIME}(f(n))$ as the class of languages that can be accepted by a (multitape) Turing machine in time $f(n) + 1$. (The "$+ 1$" is just to simplify notation and avoid confusion.) Notice that there is no $O(\cdot)$ around $f(n) + 1$.

Is it true that $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

Using the linear speed-up theorem, we can prove $\mathsf{DTIME}(2n) = \mathsf{DTIME}(1.01n)$, but can we reach $n$?

It seems that the language of palindromes is in $\mathsf{DTIME}(n)$; for related topics, see Lipton's blog post about string algorithms

From the comment:

In "Deterministic Turing Machines in the Range between Real-Time and Linear-Time" I found:

... if $r \in T^{−1}(DTM)$ and $r' \in o(r)$ then $DTIME(n+r') \subset DTIME(n+r)$ ...


Pre-order traversal on a search tree The following is from this year's CS GRE practice test. I've worked through the test and I've been able to understand every question except for this one. Can anyone help me understand what's going on here?

  Question:

  Let $T$ be a depth-first search tree of a connected undirected graph $G$. For each vertex $v$ of $T$, let $pre(v)$ be the number of nodes visited up to and including $v$ during a preorder traversal of $T$, and $post(v)$ be the number of nodes visited up to and including $v$ during a postorder traversal of $T$.

  The lowest common ancestor of vertices $u$ and $v$ in $T$ is a vertex $w$ of $T$ such that $w$ is an ancestor to both $u$ and $v$, and no child of $w$ is an ancestor of both $u$ and $v$.

  Let $(u,v)$ be an edge in $G$ that is not in $T$, such that $pre(u) < pre(v)$. Which of the following statements of $u$ and $v$ must be true?

  $post(u) < post(v)$
  $u$ is an ancestor of $v$ in $T$.
  If $w$ is the lowest common ancestor of $u$ and $v$ in $T$, then $w = u$.

I'm not going to post the answer just yet. If you're interested, it's available in the PDF:

http://www.ets.org/Media/Tests/GRE/pdf/CompSci.pdf

I think that none of these can be true, based on the following:

If $u$ is an ancestor of $v$ and $v$ is a leaf, then this would be false because leaves are counted first by postorder traversal.
If $u$ is a left sibling of $v$, then $u$ is counted first by preorder traversal, but $u$ is clearly not an ancestor of $v$.
This statement is equivalent to #2, and could be false by the same argument.

I think it goes without saying that the test answers say I'm wrong about this. Am I missing something here? Can anyone provide an explanation as to why I'm wrong, as well as how to arrive at the correct answer?

Thanks!

EDIT:

Per Sadeq's request, I've included a counter example to #2/#3:

Counter Example http://img39.imageshack.us/img39/6410/counterexample.png

The graph $G$ is shown in the image. If we remove the edge between $A$ and $D$, then we get the tree $T$. Now we have the following:

$(u,v)\in G - T$
$pre(A) < pre(D)$
$A$ is not an ancestor of $D$ in $T$.

First note that #2 and #3 are saying the same thing. Next, notice that if u is an ancestor of v in T, then in a pre-order traversal, we see u before v, and therefore pre(u) < pre(v). On the other hand, since T is a depth-first search tree (as opposed to an arbitrary tree) of the connected undirected graph G, and $(u,v) \in G-T$, we can deduce that pre(u)<pre(v) results in u being an ancestor of v.

The following image, taken from Wikipedia, can help:

Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)

Postorder traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)


Complexity of finding even cuts for a graph Given a graph $G=(V,E)$, what is known about the classical computational complexity of finding a non-trivial cut which partitions the vertices into two sets $V_a$ and $V_b$ such that every vertex in $V_a$ has an even number of neighbours in $V_b$ and every vertex in $V_b$ has an even number of neighbours in $V_a$? In particular I am interested in the time and depth complexity of solving this problem, or the corresponding decision problem.

I realise that this may correspond to a well studied problem, and if so I would appreciate a pointer to the relevant literature. It seems closely related to a number of SAT problems, but I have not yet managed to find an exact correspondence.

Such a cut exists if and only if the graph has an even number of spanning trees, which can be checked in polynomial time by using the matrix-tree theorem. See http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-14.pdf


Random point in a d-dimensional ball I would like to know if there any algorithm to pick a random grid point inside a d-dimensional ball with a given radius R.  And if there any algorithm to pick a random arbitrary point inside a d-dimensional ball with a given radius R.

Thanks.

For the latter, this discussion is a good starting point.  For the former, I guess finding a random point in the ball, rounding it to a grid point, then checking that grid point is in the ball.


hardness of approximation result for a Min-CSP, by reduction from PCPs Reduction from PCPs allow us to prove hardness of approximation results for a number of constraint satisfaction problems. I've seen such a reductions only for Max-CSPs. Is this possible only for Max-CSPs? In other words, can someone get hardness of approximation result for a Min-CSP (for example, Vertex-Cover or sparsest-cut) by reduction from PCPs?

If it is always possible to convert a Min-CSP to an equivalent Max-CSP, then maybe this answers my question. But, I don’t know whether it is always possible or not.

One reason we see Max-CSPs more is that they often capture convex optimization problems for which minimization is easy (e.g., Max-CUT vs Min-CUT).

A Min-CSP is equivalent to a Max-CSP when you negate all the constraints. So minimization and maximization are equivalent if you're asking for the optimum solution. But this reduction is not approximation preserving in the sense that, say, a constant factor approximation of the negated CSP does not necessarily imply a constant factor approximation of the original CSP. Approximation of Max-CSPs and Min-CSPs can however be studied under the unified framework of "generalized CSPs", when constraints have weights and can be fractionally satisfied. Prasad Raghavendra's thesis is a good resource about this.

The specific problem of Vertex-Cover is not really a CSP in the standard sense. However the approximation of the problem is captured by the so-called "free-bit complexity" of PCPs. See "Free bits, PCPs and non-approximability -- towards tight results" by Bellare, Goldreich, and Sudan.


Noisy channel coding theorem in quantum information Why Shannon's noisy channel coding theorem can't be used for quantum communication applications?
Schumacher proved the first Noiseless theorem and there are quantum error correction mechanisms out there.
I guess I am not sure what is the gap in knowledge to prove the noisy channel coding theorem?

You have two questions here.

Why can't Shannon's Noisy Coding Theorem be used for a quantum channel?

What gaps are there to proving a quantum noisy channel coding theorem?

I will concentrate on the first question.
Shannon's noisy coding theorem says that for a memoryless channel,
$$ {\displaystyle \ C=\sup _{p_{X}}I(X;Y)},$$
where $p_X$ is maximized over all probability distributions over the input variable $X$.
If you try to apply this naïvely to quantum channels, you run into a bunch of problems:

The input and the output of a quantum communication channel are never around simultaneously, so the classical definition of $I(X;Y)$ doesn't work at all.
The proof depends on the fact that the channel is a probabilistic map taking the input to the output. This isn't true for quantum channels; a quantum channel is a completely positive trace-preserving linear operator.
Classical channels essentially only have one capacity. There are many different capacities for quantum channels. Are you trying to send classical or quantum information?  Do the sender and receiver have access to quantum entanglement? Can the receiver communicate on a classical channel that sends information back to the sender? Neither of these last two abilities change the capacity of classical channels, but they do change the capacity of quantum channels.
There are two equivalent expressions for mutual information:
$$I(X;Y) =H(X) +H(Y) - H(X,Y) = H(Y) - H(Y|X). $$
The quantum equivalents of these two expressions are not equal. In fact, each of these corresponds to a different quantum channel capacity; the first corresponds to the entanglement-assisted classical capacity  and the second to the Holevo-Schumacher-Westmoreland capacity.

So to summarize, you can't apply Shannon's Noisy Channel Coding theorem directly to quantum channels because not only does the proof not work, but the standard formulation of Shannon's capacity formula isn't even defined for quantum channels, and mutual information has two plausible extensions to the quantum case.
For your second question, there are several different quantum noisy channel coding theorems. The main problem with most of them is that they have a regularization step in them. Instead of getting an answer that you can compute by maximizing over inputs to a single channel use, you get an answer that is difficult to compute: you need to maximize a quantity that depends on $n$ channel uses and divide by $n$, and then take $n$ to infinity. There may not be a single-channel-use formula; even a lot of quantities in classical information theory don't have a single-symbol formula.


How to specify and verify Horn clauses (logic programming programs)? Semantics of Horn clauses There are lot of applications of Horn clauses (notable examples include use of rules in cognitive architectures and knowledge bases, as well as use of rules in business rules programs). Are there formal methods that can help specify and verify Horn clauses. Is there semantics of Horn clauses. One can perceive Horn clauses as something similar to programming code of traditional programming languages and therefore one can expect the denotation, operational and similar semantics as well for Horn clauses.

You should have a look at Uniform Proofs as a Foudation for Logic Programming by Dale Miller, Gopalan Nadathur, Frank Pfenning and Andre Scedrov, 1991. The idea of this work and the rich area that has seen spawn from these ideas is to understand the execution of a logic program as proof search in simple and expressive logics, such as intuitionistic logic or linear logic. A particular class of formulas with good proof search properties are the Hereditary Harrop Formulas, which nicely generalize Horn Clauses.


Exact complexity of a problem in $\cap_{m \geq 2}\mathsf{AC}^0[m]$ Let $x_i \in \{-1,0,+1\}$ for $i \in \{1,\ldots,n\}$, with the promise that $x = \sum_{i=1}^n{x_i} \in \{0,1\}$ (where the sum is over $\mathbb{Z}$). Then what is the complexity of determining if $x = 1$?

Notice that trivially the problem lies in $\cap_{m \geq 2}{\mathsf{AC}^0[m]}$ because $x \equiv 1\bmod{m}$ iff $x = 1$. Question is: does the problem lie in
$\mathsf{AC}^0$? If so, what is the circuit witnessing this? If not, how does one prove this?

I do not think this is in AC0 and I can show a lower bound for the related promise problem of distinguishing between $\sum x_i = 0$ and $\sum x_i = 2$, when $x \in \{-1, 1\}^n$. Similar Fourier techniques should apply to your problem, but I have not verified that. Or maybe there is a simple reduction.

Suppose there is a size $s$ depth $d$ circuit that computes a function $f: \{-1, 1\}^n \rightarrow \{0, 1\}$ such that  $f(x) = \sum_i x_i$ whenever $\sum_i x_i \in \{0,2\}$. Because for a random $x$, the probability that $\sum_i x_i = 0$ is $2^{-n} {n \choose n/2} \approx n^{-1/2}$, and for each such $x$ there are $n/2$ coordinates that change the value of $f$, the total influence of $f$ is $\Omega(n^{1/2})$, which is roughly the same as majority (because you included most of majority's sensitive inputs). By a theorem of Hastad (see Colorraly 2.5 in Ryan O'Donnel's notes), this implies that

$$
s \geq 2^{\Omega(n^{1/(2d-2)})}.
$$


Instance of FPT-reductions that is not a polynomial-time reduction In parametrized complexity people use fixed-parameter-tractable (FPT) reduction to prove W[t]-hardness. Theoretically a FPT-reduction is not a polynomial-time reduction, since it can run exponentially in the parameter k. But in practice all the FPT-reductions I've seen are p-time reductions, which means W[t]-hardness proofs almost always imply NP-completeness proofs.

I wonder if someone can give me a FPT-reduction that indeed runs exponentially in the parameter $k$. Thanks.

An early example is the W[2]-hardness proof for Tournament Dominating Set (Theorem 4.1 in [1]). The reduction is from Dominating Set and it constructs a tournament with $O(2^k n)$ vertices, where $n$ is the number of vertices of the dominating set instance and $k$ is the parameter.

[1]: Rodney G. Downey and Michael R. Fellows. Parameterized computational feasibility. In
P. Clote and J.B. Remmel, editors, Proceedings of Feasible Mathematics II,
pages 219-244. Birkhauser, 1995.


Why do NP-complete problems not have similar approximation ratios? Since 2 NP-complete problems are by definition reducible to each other, so a solution to one of them can be obtained by using a black-box solving the other one, why don't they have similar approximation ratios (referring to their optimization counterparts)? I guess that some constant or even polynomial drift might be understood but we have the case of constant-factor approximation algorithms for some NP-complete problems and, on the other hand, other problems that cannot be even approximated by a polynomial-ratio approximation algorithm, such as general TSP? Thank you

Reductions are defined with respect to the decision version of the problems.  Approximation ratios for their optimization versions are a separate question, which seems related but doesn't necessarily have to be.  So to answer your question with a question, from a philosophical perspective, why should you expect the class NPC to preserve approximation ratios when it isn't defined with respect to them in the first place?


Are there works on "quantum parametrized complexity"? I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent.  I don't know if researchers in quantum complexity have started using parameterized complexity or not, so I will not comment on that.  I tried to search on google but did not find able to find anything.

Question : Are there works on "quantum parametrized complexity"?

As far as I'm aware, parameterized complexity theory has not been formally introduced to quantum computing so far.

Many problems in the field, though, are well-known to be tractable once a key parameter is fixed, such as constant spectral gaps of local Hamiltonian operators, or bounded condition numbers of various matrices. Fixing the parameter often lead to tractable subclasses of problems (see Matrix Product States and Lieb-Robinson bounds) or efficient classical or quantum algorithms (e.g. Harrow-Hassidim-Lloyd algorithm), for which the general problem is usually exponential in that parameter.

There are some works that explicitly use standard parameters of the fixed-parameter tractability (FPT) literature, e.g.

Markov and Shi [https://arxiv.org/abs/quant-ph/0511069] show how to efficiently and classically compute acceptance probabilities of quantum circuits viewed as tensor networks with bounded tree-width
Bravyi [https://arxiv.org/abs/0801.2989] shows how to contract matchgate circuits on non-planar graphs with bounded genus
Van den Nest and Briegel [https://arxiv.org/pdf/quant-ph/0610040.pdf] show that measurement-based quantum computing, which is performed on a family of graph states G, can be classically efficiently simulated if G has a decidable C$_2$MS logic theory (based on a result of Courcelle and Oum implying bounded rank-width of such graphs).