Most Popular
1500 questions
18
votes
2 answers
Are there any heuristic-free NP complete problems?
Are there any NP complete problems with no infinite subset of instances $\Phi$ such that membership in $\Phi$ can be decided in polynomial time, and for all $x \in \Phi$, $x$ can be solved in polynomial time? (Assuming $P \neq NP$)
Phylliida
- 1,132
- 5
- 22
18
votes
1 answer
Advice for a mathematician trying to present a paper at a CS conference?
I am a mathematician who works primarily in the spectral theory of self-adjoint and unitary operators. Some of my research is of relevance in quantum walks, and I have one paper in particular that I would like to present in the Quantum Information…
Darren Ong
- 283
- 1
- 5
18
votes
2 answers
Where to learn more about what Theoretical Computer Science is?
I am a graduate student in math, and theoretical computer science is a domain which I never understood what it is about because I couldn't find a good read about the topic. I want to know what this domain is actually about, what kind of topics it is…
user42224
18
votes
2 answers
Deciding whether a unary context-sensitive language is regular
It is a well-known result that the question
Does a context-free grammar generate a regular language?
is undecidable. However, it becomes decidable on a unary alphabet, simply because in this case, the classes of context-free and regular languages…
J.-E. Pin
- 4,831
- 26
- 42
18
votes
0 answers
Complexity of the homomorphism problem parameterized by treewidth
The homomorphism problem $\text{Hom}(\mathcal{G}, \mathcal{H})$ for two
classes $\mathcal{G}$ and $\mathcal{H}$ of graphs is defined as follows:
Input: a graph $G$ in $\mathcal{G}$, a graph $H$ in $\mathcal{H}$
Output: decide if there is a…
a3nm
- 9,269
- 27
- 86
18
votes
0 answers
Does Factoring have a Statistical Zero Knowledge Proof?
The title should be pretty self-explanatory, but to be more precise, consider the decision version of factoring, which is given input $(x,k)$, where $x$ and $k$ are binary encodings of integers, to determine whether $x$ has a prime factor less than…
Henry Yuen
- 3,798
- 1
- 21
- 33
18
votes
2 answers
Status quo of category theory and monads in theoretical computer science research?
Background. I am a bachelor student who is interested in research related to category theory, monads and Haskell, and I want to find a topic for my bachelor’s thesis in that area.
I have looked at the paper
Eugenio Moggi, “Notions of Computations…
k.stm
- 281
- 1
- 8
18
votes
2 answers
Proof that circuit upper bounds for $E$ imply $P \neq NP$
In the official Clay problem description for P versus NP it's stated that $P \neq NP$ would follow from showing that "every language in $E$ [the class of languages recognizable in exponential time with a deterministic Turing machine] can be computed…
David
- 181
- 2
18
votes
1 answer
Reference for mixed graph acyclicity testing algorithm?
A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction an orientation of a mixed graph is obtained by…
David Eppstein
- 50,990
- 3
- 170
- 278
18
votes
0 answers
Are monotone Boolean functions in P well-approximated by monotone polynomial-size circuits?
Question 1: Is it true that for every polynomial $p(n)$ and $\epsilon >0$ there is a polynomial $q(n)$ such that every monotone Boolean function on $n$ variables that can be expressed by a Boolean circuit of size $p(n)$ can be…
Gil Kalai
- 6,033
- 35
- 73
18
votes
2 answers
Complexity of the recovery of an adjacency matrix from its square
I am interested in the following problem: Given an $n\times n$ matrix, is there an undirected graph on $n$ vertices whose adjacency matrix squared is that matrix?
Is the computational complexity of this problem known?
Remarks:
Of course this can…
Ben Fish
- 181
- 4
18
votes
2 answers
Time complexity of counting triangles in planar graphs
Counting triangles in general graphs can be done trivially in $O(n^3)$ time and I think that doing much faster is hard (references welcome). What about planar graphs? The following straightforward procedure shows that it can be done in $O(n\log{n})$…
SamiD
- 2,309
- 17
- 28
18
votes
5 answers
Simple and practical deterministic algorithm, complicated running time
Very often, if the running time of an algorithm is a complicated expression, the algorithm itself is also complicated and impractical. Each of the cube roots and $\log \log n$ factors in the asymptotic running time tends to add complexity to the…
Jukka Suomela
- 11,500
- 2
- 53
- 116
18
votes
1 answer
Choosing a research topic using game theory
This recent game theory question got me thinking (this is a tangent, of course): Is it possible to efficiently optimize a personal strategy for choosing research questions to work on using game theory?
In order to head towards a formalization of the…
Daniel Apon
- 6,001
- 1
- 37
- 53
18
votes
2 answers
Long-Standing Conjectures later trivially proved by an implication
I'd like to know if there have been conjectures that have long been unproven in TCS, that were later proven by an implication from another theorem, that may have been easier to prove.
Ryan Dougherty
- 555
- 3
- 19