0
votes
0answers
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 ...
-3
votes
0answers
18 views

Graph Isomorphism and APSP matrix. [on hold]

I am trying graph Isomorphism using APSP(AllPairShortestPath) matrix. Any comment on that??
-2
votes
0answers
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.
7
votes
4answers
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 ...
-2
votes
0answers
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 ...
8
votes
0answers
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\}$, ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
4
votes
0answers
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 ...
1
vote
1answer
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 ...
-1
votes
0answers
40 views

If both $L$ and $L_1$ are regular, does it follow that $L \diamond L_1$ is regular? [on hold]

In general, a string $x$ is a subsequence of $w$ if $w = w_1, ... , w_n$ with $w_i \in \Sigma$ for $1 \leq i \leq n$, and there exist integers $i_1, ... , i_k$ with $0 < i_1, i_k \leq n$, and $i_j ...
-2
votes
0answers
18 views

A question on quantum computing? [migrated]

I dont know much about quantum computing except what i have read about on wiki and popsci. I have been reading about the de broglie-bohm pilot wave theory and how they describe quantum mechanics in ...
2
votes
0answers
53 views

Restricted-Input Automaton

In the classic setting, an automaton for a language $L$ is required to accept all words in $L$ and reject/get stuck on every word in $\Sigma^*\setminus L$. All of the related concepts are then ...
-1
votes
0answers
57 views

Subset sum problem solver (theoretical) time analysis

I has been thinking to a new approach to this problem and I'm wondering if next time analysis is right: Giving: $N$ = Number of Items $M$ = bits required to represent the maximum value in the set ...
2
votes
0answers
48 views

efficient data structures for generalized tensor products

The usual tensor product of vectors is a matrix. There has been tons of research into efficiently storing and operating on matrices in computers. But we can generalize the tensor product quite a ...
0
votes
0answers
29 views

Programming language based on simply-typed lambda-calculus

Is there a programming language that is based purely on simply-typed lambda calculus? I don't mean languages like Haskell or OCaml, but one that is "just" simply-typed calculus.
4
votes
0answers
56 views

FPT algorithm for mixed integer program

It is known that every integer linear program parameterized by the number of variables is FPT (fixed parameter tractable). Is every mixed integer program parameterized by the number of integer ...
-1
votes
0answers
40 views

Is it possible to separate neural networks and achieve the same function?

I am thinking about ways other than contrastive divergence or backpropagation to optimise neural networks (specifically using evolutionary techniques), and the biggest problem I have come up against ...
2
votes
2answers
105 views

Complexity of smooth non-linear functions

EDIT: A more straightforward way of asking this question is: does evaluating a non-linear function require performing at least one multiplication? ORIGINAL QUESTION: I have an infinitely ...
-3
votes
1answer
64 views

Iterated Prisoner's Dilemma Algorithms

While reading a post on Scott Aaronson's blog about Eigenmorality, I ran across the idea of the iterated prisoner's dilemma tournament. I've studied some TCS on my own, but had never really thought ...
11
votes
0answers
106 views

Lower bounds for the size of nondeterministic circuits

It is known that the minimum size of $U_2$-circuits computing the parity function exactly equals $3(n-1)$. The lower bound proof is based on the gate elimination method. Recently, I noticed that the ...
0
votes
0answers
63 views

Geometric proof for NP completeness for a candidate problem

Is there a nice example for NP completeness for a candidate problem that can be visualized geometrically? In other words is there sort of a proof without words?
3
votes
0answers
94 views
+50

Tuning Parameters of Locality Sensitive Hashing

We have given a set of $n$ binary vectors each of dimension $d$, i.e. a binary matrix of $d*n$. Our goal is to group vectors which are almost similar, $\forall v_i, v_j\in\{0,1\}^d$, we say $v_i$ ...
-1
votes
2answers
69 views

Arrangements of Objects

Suppose there are $n$ bins each having $k$ objects. Assume that capacity of each bin is also $k$. Now we want to rearrange the objects such that each bin contains $k$ objects but this time if $x,y$ ...
13
votes
0answers
202 views

Classifying reversible gates

Post's lattice, described by Emil Post in 1941, is basically a complete inclusion diagram of sets of Boolean functions that are closed under composition: for example, the monotone functions, the ...
-1
votes
0answers
28 views

Inter-connectivity between your mind and pc [closed]

Is it possible to create tasks within your computers code to actually control what actions your physical body takes on?
12
votes
2answers
172 views

Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy

The $\mathsf{W}$-hierarchy is a hierarchy of complexity classes $\mathsf{W}[t]$ in parameterized complexity, see the Complexity Zoo for definitions. An alternative definition defines $\mathsf{W}[t]$ ...
-7
votes
1answer
29 views

Is this a horn formula and if so is it satisfiable? [closed]

(1 v ~2) ^ (~1 v 2) ^ (2 v ~3) ^ (~2 v 3) ^ (1 v ~3) ^ (~1 v 3) Each clause has only 1 positive The simple definition of this problem is 1 != 2 and 2 != 3 and 1 != 3 where 1, 2 and 3 are booleans.
-4
votes
0answers
17 views

Can someone help with this reduction? [closed]

http://cs.stackexchange.com/questions/11139/relaxed-bin-packing-problem This question seems to be open for quite sometime.
8
votes
1answer
147 views

A purely graph-theoretic explanation of the reduction from Unique Label Cover to Max-Cut

I am studying the Unique Games Conjecture and the famous reduction to Max-Cut of Khot et al. From their paper and elsewhere on the internet, most authors use (what to me is) an implicit equivalence ...
0
votes
0answers
22 views

Correctness proof of recursive-descent recognizer

Let G be a grammar that contains no left-recursive rules, and we use a recursive-descent recognizer that uses full backtracking, using list of results for example, to recognize strings of G. How ...
1
vote
1answer
83 views

Generalized Secretary Optimization Problem

In the standard Secretary Problem, the goal is to hire the best secretary from a list of candidates. I've recently witnessed a failed hiring attempt for a needed position and it inspired a similar ...
2
votes
1answer
86 views

Computability of infinite-dimensional vector space

So there is a talk about infinite-dimensional vector space being computable. But then I find it hard to understand. Apparently, dimension is infinite, so how would the operations of the space be ...
7
votes
1answer
328 views

Problem that is in P only if P!=NP

Are there any problems that are solvable in polynomial time only if P!=NP, and otherwise solvable in (say) $O(2^n)$ time? A simple example would be: If P!=NP, compute a primality test for a random ...
-1
votes
1answer
148 views

Is the running time of Boyer-Moore linear?

With pattern length $M$, text length $N$, and alphabet $\Sigma$, is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$ (even when $M$ grows larger than $|\Sigma|$)? Are there any sublinear ...
8
votes
1answer
208 views

Secretary hiring game

This is an extension of the classical secretary problem. In the hiring game you have a set of candidates $\mathcal C=\{c_1,\ldots,c_N\}$, and order on how skilled each worker is. W.l.o.g, we assume ...
-1
votes
0answers
34 views

Two questions about the Turing machine [closed]

Recently, I am learning about the definition of Turing machine. When I read the following sentence: ``Each machine $M$ has a specified input alphabet $\Sigma$, which is a subset of $\Gamma$, not ...
1
vote
1answer
68 views

Connecting vertices after struction operation in J.Chen, I.Kanj, G.Xia vertex cover algorithm

EDIT: I'm sorry if this question belongs more to cs.SE, I've had a dilemma about where to put it. Please let me know if it's inappropriate. I'm currently implementing the Vertex Cover problem solving ...
13
votes
1answer
415 views

The complexity of counting simple paths in a directed graph

Let $G$ be a digraph (not necessarily a DAG) and let $s,t \in V(G)$. What is the complexity of counting the number of simple $s-t$ paths in $G$. I would expect the problem to be #${\mathsf ...
-4
votes
0answers
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 ...
3
votes
2answers
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 ...
6
votes
0answers
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 ...
3
votes
0answers
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 ...
-4
votes
0answers
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?
-2
votes
0answers
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 ...
4
votes
0answers
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), ...
-4
votes
0answers
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 ...
4
votes
0answers
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 ...
-5
votes
0answers
28 views

Job opportunites after Theoretical computer Science and How to formulate a Theorem and Prove it [closed]

I am a student starting my Doctoral Studies in Computer Science. I like Theoretical Computer Science. I have two questions. 1) I would like to know more about the job opportunities at the end of ...
3
votes
3answers
345 views

Sub-exponential algorithm for Hamiltonian cycle problem on cubic planar graphs?

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 ...

15 30 50 per page