# All Questions

15 views

### Graph isomorphism with equivalence relation on the vertex set

A colored graph can be described as tuple $(G,c)$ where $G$ is a graph and $c : V(G) \rightarrow \mathbb{N}$ is the coloring. Two colored graphs $(G,c)$ and $(H,d)$ are said to be isomorphic if there ...
18 views

### Graph Isomorphism and APSP matrix. [on hold]

I am trying graph Isomorphism using APSP(AllPairShortestPath) matrix. Any comment on that??
12 views

### Entropy of sum of dependent random variables

Can you help me find the entropy of the sum of two dependent random variables i.e find $h(X+Y)$ when X and Y are depenendent.
789 views

### Lipton's most influential results

Richard J. Lipton has been selected as the winner of the 2014 Knuth Prize "for Introduction of New Ideas and Techniques". What are to your minds the main new ideas and techniques that Lipton ...
42 views

### Worst case Scenario on Bellman-Held-Karp TSP

This is my first question on this community. think I understand sort of why the number of operations for each iteration of Dynamic programming is $k(k-1)\binom{n-1}{k}$ but it seems to me that this ...
87 views

### Sign patterns for Fourier coefficients of Boolean functions

Given a sequence of real numbers $(a_i)$, the sign-pattern sequence $(s_i)$ is defined by $s_i = +$ if $a_i \geq 0$ and $s_i = -$ otherwise. For a boolean function $f: \{0,1\}^n \to \{0,1\}$, ...
44 views

### Do Genetic Algorithms Expect a Independent Search Space

Genetic Algorithms seem like multiple simulated annealing instances, augmented with a crossover genetic operator. The crossover operator selects predefined genes from two different parent solutions to ...
48 views

### Indexing structure for all-pairs min-cuts in a huge DAG

I have a huge DAG - e.g., the dependency graph of all packages in a linux distribution. Suppose I'd like to make a user-friendly tool that makes it very easy to understand how to break the transitive ...
152 views

### $NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$

Stephen Smale claims in Mathematical Problems for the Next Century that $$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}.$$ Can someone sketch the argument or provide a ...
79 views

### Source of Turing-machine illustration

I am writing a computer science textbook and want to use an illustration showing a Turing machine. Images are all over web, but almost always without authorship/illustratorship credited. I need to ...
40 views

62 views

### A Good Text Book or Resource on Mathematical Logic and Algorithm Theory? [closed]

I am studying a course titled "Mathematical Logic and Algorithm Theory this semester, but i can't seem to find any book or resource online that matches the topics in my school's syllabus. The topics I ...
134 views

### Decompose a complete graph into smaller cliques

The following exercise problem is from the book of D.B.West which i could solve: If a complete graph can be decomposed into triangles then $n-1$ or $n-3$ is divisible by 6. So my questions are ...
445 views

### Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

I have part of a proof attempt of $\oplus \mathbf{P} \subseteq \mathbf{NP}$. The proof attempt consists of a Karp reduction from the $\oplus \mathbf{P}$-complete problem $\oplus$3-REGULAR VERTEX COVER ...
71 views

### How to analyze the quality of data definition language? [closed]

I know that DDL is most often used when talking about databases, but I see no reason why XML, PDF or even to some extent Prolog shouldn't belong to this category. It looks like branches of CS ...
25 views

### How to evaluate graph generation algorithm? [closed]

I have generated graph(network) with a set of constraints and number of nodes and links are primary input. How to evaluate this?
44 views

### Homomorphism erasing information [closed]

I would be grateful if anyone could help me with the tricky exerciese *7.52 from Sipser's Introduction to the Theory of Computation 3rd ed. I got stuck in proving that, if P is closed under ...
207 views

### Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?

We can write ${\mathsf {NP}}-{\mathsf P}= {\mathsf {NPC}}\cup {\mathsf {NPI}}$ where ${\mathsf {NPC}}$ is the set of ${\mathsf {NP}}$-complete languages (not in ${\mathsf {P}}$ by this partition), ...
26 views

### Understanding the time-complexity of Insertion Sort [closed]

From my textbook, I am studying the time-complexity of the insertion sort algorithm (shown below). The image above shows the times that each statement is executed. But wait, why is ...
170 views

### Balanced Boolean function satisfiability

Consider the following problem: Input: A Boolean black-box $U$ of a balanced Boolean function (balanced meaning equal number of satisfying and unsatisfying truth assignments) Output: A ...
There are several graph $NP$-complete problems that have sub-exponential time algorithm on planar graph instances. What is the fastest algorithm for HC problem on cubic planar graphs? Is there a ...