Most Popular
1500 questions
21
votes
14 answers
Examples of collapsing hierarchies
Are there interesting examples of "collapsing hierarchies" in computer science?
The formal definition of a hierarchy here would be a class of languages/problems/objects which is parametrized by a partially ordered set. But I am of course looking…
Ville Salo
- 521
- 3
- 10
21
votes
1 answer
Turing award papers
I was wondering if there are individual publications that have led their authors to win the Turing Prize or if the Turing Prize is the result of a lifetime's work and multiple publications and results.
Yamar69
- 684
- 5
- 12
21
votes
3 answers
Is there a Quantum equivalent of the Time hierarchy theorem ?
My favourite theorem in complexity theory is the Time hierarchy theorem. However, this was done in 1965.
I wanted to know then if there was anything similar for Quantum Computing.
Also, if not what are the people / groups working in this…
Zelah 02
- 1,578
- 7
- 16
21
votes
2 answers
PPAD and Quantum
Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other related classes) and quantum computers. In his…
Gil Kalai
- 6,033
- 35
- 73
21
votes
3 answers
Why colon to denote that a value belongs to a type?
Pierce (2002) introduces the typing relation on page 92 by writing:
The typing relation for arithmetic expressions, written "t : T", is defined by
a set of inference rules assigning types to terms
and the footnote says The symbol $\in$ is often…
Stand with Gaza
- 359
- 2
- 7
21
votes
1 answer
Number of words of length n in a context-free language
Denote by $w_n$ the number of words of length $n$ in a (possibly ambiguous) context-free language.
What is known about $w_n$?
I'm sure this has been studied a lot, but I couldn't find anything at all on it.
domotorp
- 13,931
- 37
- 93
21
votes
2 answers
Succinct circuit representation of graphs
The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE:
END OF THE LINE: Given circuits S and P with n input bits and n output bits such that P(0n)…
Daniel Apon
- 6,001
- 1
- 37
- 53
21
votes
2 answers
Has the semantics of TeX (as a programming language) ever been formalized?
It seems to me that the macro language employed by $\TeX$ can maybe be seen as some kind of term rewriting system or some kind of programming language with call-by-name scoping.
Even modern implementations of the $\TeX$ engine (e.g.…
Nicola Gigante
- 1,588
- 10
- 20
21
votes
2 answers
Coloring Planar Graphs
Consider the set of planar graphs where all the internal faces are triangles. If there is an interior point of odd degree the graph cannot be three colored. If every interior point has even degree can it always be three colored? Ideally I'd like a…
Lance Fortnow
- 8,681
- 44
- 59
21
votes
2 answers
Is JSON a Regular Language?
I was wondering if the JSON spec defined a regular language. It seems simple enough, but I'm not sure how to prove it myself.
The reason I ask, is because I was wondering if one could use regular expressions to effectively pars JSON.
Could someone…
jjnguy
- 321
- 2
- 6
21
votes
2 answers
maintaining a balanced spanning tree of a growing undirected graph
I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph.
I have an undirected graph that starts as a single node, the "root".
At each step, I add to the graph either a new node and an…
SuperElectric
- 341
- 1
- 7
21
votes
2 answers
Finding a 5-cycle in a sparse graph efficiently.
(crossposted from MathOverflow)
Hi,
I was reading this thread: https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length
I want to find a 5-cycle in a graph. Actually, what I really want is a shortest odd cycle of length at least 5,…
Andrew D. King
- 1,573
- 10
- 19
21
votes
5 answers
Writing a paper as a single author in 1st person singular
I am writing papers in theoretical computer science sometimes being a nonanonymous single author. Earlier, I used the 1st person plural in such papers, e.g.:
We will show that the complexity classes X and Y coincide.
I am neither a native English…
user44501
21
votes
1 answer
A comparison of extractors in terms of tradeoffs between time, randomness and space ?
Is there a good survey that compares different extractors, concentrators and superconcentrators and lays out the best methods in terms of the tradeoff between randomness, time and space ?
Suresh Venkat
- 32,071
- 4
- 95
- 271
21
votes
4 answers
Complexity of finding a second solution given a correct solution to an NP-complete problem
I'm looking to figure out whether there are any general results about or examples concerning the NP-completeness of the problem of finding a second solution to an NP-complete problem. More precisely, I'm interested in any problems of the following…
Mark C.
- 311
- 1
- 5