1. All Categories
2. Theoretical Computer Science

# Theoretical Computer Science : Recent Questions and Answers

## Complexity of Model Enumeration in function free, equality free, First Order Logic with only Unary Predicates?

This question has inspired the following two questions.Given a first order logic language, with only unary predicates, finite number of variables, $forall$ and $exists$ i.e no...

## Reducing the Height of Context-Free Grammars

Let $G$ be a context free grammar in Chomsky normal form (CNF) with language $L(G)subseteq Sigma^n$. In other words, all strings generate by $G$ have size $n$. Say that...

Asked on 11/26/2021 by Mateus de Oliveira Oliveira

## Dynamic matrix-matrix multiplication

Suppose A and B are initial Boolean matrices. Let C = A*B. Suppose one can perform the sequence of the next operations: "set A[i,j] = 1", "set B[i,j] = 1"....

## Comparing two graphs when starting from a single edge

Let's assume that we are given two graphs $G_1$ and $G_2$ defined by the two following nicely drawn pictures. Black numbers label the nodes, red numbers show the...

## Proving membership in W-hierarchy when problem is not parameterized by its solution size

I'm curious about the following general problem: Suppose that we have a parameterized problem whose input is $x$ and parameter is $k$ (which is NOT the size of...

## Find a boundary from set of 3d line segments

I have a set of n 3d line segments [(p1_start,p1_end), (p2_start,p2_end),....(pn_start,pn_end)].(I believe that they shod be nin-intersecting...)These segments represent a (closed) boundary. I am looking for...

## approximate maximum clique given vertex cover

I have a non optimal vertex cover of size k of a graph G, and I want to get a (1+epsilon)-approximation kernel of size linear in k for maximum clique...

## Any fundamental papers in TCS which were found to be incorrect/wrong later?

I am asking this question out of curiosity. I recently encountered this well-known paper on (published in 2009):the hardness_of_Euclidean_kmeans The paper showed that the previous NP-hardness result...

## Number of connected components of a random nearest neighbor graph?

Let us sample some big number N points randomly uniformly on $[0,1]^d$.Consider 1-nearest neighbor graph based on such data cloud. (Let us look on it...

Asked on 10/30/2021 by Alexander Chervov

## In the neutral zone between polynomial and sub-exponential

What are examples of problems that are known to be sub-exponential, butare known to be non-polynomial, orare not known to be polynomial?EDIT. Here is what I mean by sub-exponential (apologies...

Asked on 10/30/2021 by Dominic van der Zypen