0
votes
0answers
11 views

Constrained version of vertex cover in a bipartite graph

Let $G(V_1, V_2, E)$ be a bipartite graph such that degree of all the vertices in $V_1$ is bounded by some constant (say) $d$. Now, for given two positive integer $l$ and $k$, we wish to decide if ...
0
votes
0answers
10 views

Automorphism of a restricted irregular graph class

Motivation: This query is motivated by this question . It has relation to the complexity analysis of this post. I have been informed Highly Irregular Graph has number of automorphism $\leq n ...
1
vote
1answer
14 views

Data Mining of self-replicators

My current (very limited) understanding of the creative process that leads to the design of self-replicators is that any particular self-replicator, like Universal Constructor, Langton's loop or ...
6
votes
2answers
104 views

What evidence is there that Graph Isomorphism is not in $P$?

Motivated by Fortnow's comment on my post, Evidence that Graph Isomorphism problem is not $NP$-complete, and by the fact that $GI$ is a prime candidate for $NP$-intermediate problem (not $NP$-complete ...
5
votes
0answers
33 views

SVM - running time for detecting if data is linearly separable?

If my understanding is correct, one way to check if a set of $m$ data points is linearly separable is to use support vector machines to find a maximum margin hyperlane for separating the data; the ...
1
vote
0answers
23 views

Expressive power of computer languages: it's all about the syntax/logic?

When analyzing the theoretical expressive power of programming languages (not the verbosity of the programming languages or how concise programs are) are there further criteria besides the class of ...
0
votes
0answers
43 views

Graph classes with a “jump property”

Let us say that a graph class has the jump property, if it either contains all $n$-vertex graphs for every large enough $n$, or else the fraction of $n$-vertex graphs that belong to the class ...
5
votes
2answers
162 views

Number of Automorphisms of a graph for graph isomorphism

Let $G$ and $H$ be two $r$-regular connected graphs of size $n$. Let $A$ be the set of permutations $P$ such that $PGP^{-1}=H$. If $G=H$ then $A$ is the set of automorphisms of $G$. What is the ...
-1
votes
0answers
40 views

Complexity of non-comparison based sorting $O(n\lceil(\log k/ \log n) \rceil)$

I want to ask if our new algorithm that in some aspect is better than count, bucket and radix sort, would be accepted for publication.I know that our alog don't achieve best known upper bound for ...
3
votes
0answers
30 views

Substitution in Resolution Proofs

Let $F = C_1 \wedge C_2\; \wedge ... \wedge\; C_m$ be a unsatisfiable $k$-CNF on variables $x_1,...,x_n$, where $k$ is constant. Let $x_j\rightarrow x_j^1\wedge x_j^2$ be a substitution that replaces ...
0
votes
0answers
21 views

Analogues of different complexity classes in various models

We suspect following relation: $$TC^0\subsetneq NC^1\subsetneq L\subsetneq NL\subsetneq AC^1\subsetneq NC^2\subsetneq P\subsetneq NP\subsetneq PH\subsetneq PSPACE$$ in Turing/boolean circuit ...
1
vote
0answers
50 views

Construction of a graph which has regular subgraphs at each iteration of a recursive process

I am studying Graph Isomorphism and also trying to figure out the complexity of a certain class of graph. The graph I am studying at the moment is described below Description: <br> $G$ is a $r$ ...
2
votes
1answer
48 views

H-representation of convex hull

Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows: $P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ ...
-2
votes
1answer
55 views

what can be said about complexity of “typical” supercomputing programs/ applications? any NP hard?

supercomputers have risen dramatically in their computational powers last few decades due to Moore's law & also increasing parallelism technology in hardware and software. many different types of ...
2
votes
0answers
64 views

Two questions on Shor's algorithm

Does Shor's algorithm produce factors of a $n$-bit number and discrete log modulo $n$-bit prime in $O((\log n)^{2+\epsilon})$ bit operations using fast multiplication? I am trying to read from ...
2
votes
1answer
41 views

Verifying Shor's quantum error correction code

I know that Shor's 9 bit code can correct phase or bit flip, but I'd like to show that it can correct any type of error on a single qubit. I know that an arbitrary error can be expressed with the ...
-2
votes
1answer
62 views

Will a non-linear lower bound on some NP complete problem prove non-linear lower bound on 3SAT?

A problem $\Pi$ is $\mathsf{NP}$ complete if there is a polynomial time reduction from an $\mathsf{NP}$ complete problem $\Pi^\circ$ to $\Pi$ with polynomial blow up on number of variables and ...
-2
votes
0answers
17 views

Where can integrating the inverse of a function be used in programming application?

Just like [a link]https://en.wikipedia.org/wiki/Fast_inverse_square_root can be used in calculating angle of reflection and incidence in first person shooting games, Where might calculating the ...
-1
votes
1answer
40 views

Is there an algorithm to generate proof in Coq?

I try to imagine using Coq to implement large and complicated software with specifications and proof. However, the manual work of writing proof is daunting. As a Coq newbie, to specify an insertion ...
-1
votes
0answers
75 views

On non-comparison based sorting algorithm

Does anybody have expertise in sorting algorithms (trie and prefix-tree based in particular)? I would like to send my paper for mock review. As per my analysis, our sorting algo which is ...
1
vote
1answer
91 views

Is there an efficient program for generating a Sidon sequence?

I would need a Sidon sequence of about $10^9$ elements. I found math papers like [1] that explain how to generate Sidon sequences but it seems a lot of pain to write the corresponding program. Are ...
9
votes
0answers
84 views

The halting problem in computational models weaker than Turing machines

What are the main results and/or literature on the (self) halting problem for other machines than Turing machines? Alternatively, what would be the right keywords or tags to search for it. I am ...
1
vote
0answers
43 views

Efficient algorithm to find number of factors

Given an integer n, is there an efficient algorithm to find the number of factors of n?
0
votes
1answer
87 views

How does one determine if a mixed bipartite quantum state is entangled or not?

My question is based on the structure of the NP-hardness proof in section 6 (page 17) of this paper, http://arxiv.org/pdf/quant-ph/0303055v1.pdf Mathematically one can think of being given a ...
2
votes
1answer
28 views

Are there temporal logics linear time properties that only have counterexamples that are more complex than a lasso?

Are there linear time temporal logics that can express some property $P_{nonlasso}$ that does have a counterexample, but none that is a lasso (or finite)? Details: One advantage of model checking ...
0
votes
0answers
14 views

Which matrix of Q values is being used here?

This question refers to this paper: Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task In section 2.1, equations (5) and (6), I am wondering which Q values are ...
0
votes
0answers
66 views

Adversarial Search Algorithms

What are the best adversarial search algorithms? I understand that this may seem like a subjective question. However, I am asking for what situations are different algorithms best for. In particular, ...
1
vote
0answers
25 views

Converting Partial Weighted Max SAT to CIRCUIT SAT

I am interested in converting Partial Weighted Max SAT to SAT. I have been recommended to go through CIRCUIT SAT. Partial Weighted Max SAT consists of a set of hard clauses and a set of weighted ...
1
vote
1answer
71 views

Extractor with somewhat corrupted seeds

In conditional min-entropy extractor, there is a joint distribution $(X,Y)$ such that if the average min-entropy (for some appropriate notion of it) ${\rm H}_\infty(X|Y)$ is large, then ${\rm Ext}(X, ...
10
votes
2answers
138 views

Can a hereditary graph class contain almost all, but not all, n-vertex graphs?

Let $Q$ be a hereditary class of graphs. (Hereditary = closed with respect to taking induced subgraphs.) Let $Q_n$ denote the set of $n$-vertex graphs in $Q$. Let us say that $Q$ contains almost all ...
7
votes
1answer
158 views

What is the smallest class of reductions under which there is a $\mathsf{P}$-complete problem?

It is common to define $P$-completeness with respect to log-space many-one reductions. I am looking for a complexity class $C \subseteq \mathsf{L}$ such that there are $\mathsf{P}$-complete problems ...
1
vote
0answers
34 views

What is a good monotone/non-monotone formula in this situation?

Suppose we have an $n\times n$ matrix $A$ with non-negative integer entries such that $\mathsf{Tr}(A^i)=0$ at every $i\in\{1,2,\dots,n-2,n-1\}$ and $\mathsf{Tr}(A^n)\neq0$, then from Trace-Determinant ...
2
votes
1answer
126 views

Would a proof that the traveling salesman algorithm can't be encoded on LAL also prove P!=NP?

An answer to the traveling salesman (and similar) problems can be easily verified on light lambda-calculi. Also, if I understand correctly, the light lambda-calculi can compute every polinomial-time ...
7
votes
0answers
43 views

How much is known about coloring of planar graphs with degree bounds?

Are there any references that address the following (open?) questions: 1) Is there an algorithm that 4-colors any planar graph of maximal degree at most 5 in linear time? 2) What is the largest ...
0
votes
0answers
108 views

NP-hardness of minimizing sum of complicated objective function

In our research, we faced the following problem optimization problem: Input: a list of $k$ pairs of positive integers $(n_1,d_1), \ldots, (n_k,d_k)$; an integer $m$. Output: $P$, a partition of the ...
0
votes
1answer
38 views

Upper bound on the pseudoentropy of any distribution

From here: The notion of pseudoentropy is only useful, however, as a lower bound on the computational entropy in a distribution. Indeed, it can be shown that every distribution on $\{0,1\}^n$ is ...
-3
votes
0answers
34 views

Which are the areas where Audio Compression is used? [closed]

I have chosen a project on 'Data Compression' for my final year B.Tech project. I was initially thinking about doing works on Image compression then going to Video compression and work there. But my ...
0
votes
0answers
32 views

Which language best to use for Machine Learning library? [migrated]

We have a body of theoretical work on nearest neighbors that we would like to implement and make the code publicly available. Question: what's the best language to use? We're considering java, python, ...
-4
votes
0answers
184 views

The Mortal Matrix problem: how hard is deciding class membership? [on hold]

Alice's Claim  There exists a Turing machine (TM) that runs in PTIME (but not necessarily provably so) that infallibly separates mortal matrices from non-mortal matrices (but the separation is ...
2
votes
1answer
103 views

Perfect Matching with ``set-over-like" constraints?

Problem Description: Let k and n be some natural numbers. We are given a complete bipartite graph G where each side of G has n vertices. G is edge-labeled with labels being subsets of {1,...,k}. We ...
3
votes
1answer
208 views

Evidence that UniqueSat is dense

UniqueSAT ={$\phi$| $\phi$ has unique satisfying assignment } represents an important class of computational problems. Unique SAT is CoNP-hard and $US$-complete. What is the density of UniqueSAT? ...
2
votes
1answer
180 views

General question about pursuing TCS

I am currently an undergraduate heading into my senior year. I've taken some theory/math classes (algorithms, and set theory/topology) in the past year and am taking quite a few more this year (more ...
0
votes
0answers
36 views

What are the applications of Systems Theory in the context of computer science?

In the spirit of this question, I would like to ask about probably a much less known branch of science: systems theory. The Wikipedia article seems rather non-specific on this term, so hopefully I ...
2
votes
2answers
87 views

Factoring semiprimes whose factors very close to a power of two

Are there any factorization algorithms that run well on numbers $N = pq$ where $p,q$ are prime and $p = 2^b - k_p, q = 2^b - k_q$ for very small $k_p,k_q$? What about $p = 2^b + k_p, q = 2^b + k_q$ ...
4
votes
1answer
51 views

Approximate matching in table of integer vectors

Disclaimer: This is my first question on cstheory.stackexchange.com so please be forgiving. I have a list of M (M is big, more than 1 million elements) vectors of integers. Each vector can contain ...
6
votes
0answers
64 views

Is it possible to unambiguously read back λ terms from interaction nets without node types?

A class of lambda terms can be evaluated using Lamping's abstract algorithm - that is, converting them to interaction nets and applying a set of rules. In order to get the result, you have to read ...
-4
votes
0answers
20 views

Querry for Database [closed]

I have two tables i.e. A and B. In each table one attribute of each tuple is time stamp. The latest time stamp can appear in table B. My question is : I want to select tuples from both tables but if ...
2
votes
0answers
54 views

Claw finding using quantum walk: superposition for Szegedy's framework

Within Claw Finding Algorithms Using Quantum Walk there is the subroutine $claw_{detect}$ described. As in above paper: Let $J_f(N, l)$ and $J_G(M, m)$ be Johnson graphs. Let $F$ and $G$ be vertices ...
1
vote
0answers
63 views

A question about combinatorial design in Nisan-Wigderson Generator

Let $[d]$ be a universe and $S_1, \dots, S_m$ be an $(\ell, a)$-design over $[d]$ which means that: $\forall i \in [m], S_i \subseteq [d], |S_i|=\ell$. $\forall i \neq j \in [m]$, $|S_i \cap S_j| ...
4
votes
0answers
63 views

What is the current “state-of-the-art” solver for quadratic knapsack problems?

New to this forum, so please let me know if my question format is incorrect. For linear KP with $n$ items and $c$ capacity, dynamic programming can find exact solutions in $\mathcal{O}(nc)$. I have ...

15 30 50 per page