All Questions

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

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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? ...
180 views

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