Questions tagged [reference-request]

Reference-request is used when the author needs to know about work related to the question.

Filter by
Sorted by
Tagged with
46 votes
4 answers
4k views

Generalized Ladner's Theorem

Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP. The proof uses the completeness of SAT under many-...
user avatar
5 votes
2 answers
934 views

Handbook of Logic in Computer Science - is it worth it?

I just found the first volume of Handbook of Logic in Computer Science in a library, but unfortunately I won't be able to use it here. It seems like a great resource, but it's insanely expensive to ...
user avatar
15 votes
1 answer
366 views

Triangulating a Planar Polygon

Are there by now simpler algorithms/proofs for triangulating a planar polygon in linear time? What is a good resource on the state of the art of this famous problem?
user avatar
  • 5,973
18 votes
1 answer
1k views

Cutting-sticks puzzle

Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2. Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time? ...
user avatar
  • 1,925
19 votes
3 answers
973 views

What algorithms are known for computing Craig interpolants?

Is there any survey of algorithms for computing interpolants? What about papers on only one algorithm? The case I'm most interested in is $A=\lnot p\land q$ and $C=q$, plus the constraint that the ...
user avatar
  • 4,746
38 votes
2 answers
2k views

Multiplying n polynomials of degree 1

The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time. You can do $O(n \...
user avatar
  • 1,850
2 votes
3 answers
1k views

Best bounds for the longest path optimization problem in cubic Hamiltonian graph?

optimization problem Input: cubic Hamiltonian graph feasible solution: A simple path measure to optimize: length of the simple path Design a polynomial-time algorithm that outputs the longest path ...
user avatar
3 votes
2 answers
327 views

What is the complexity of computing a compatible 3-coloring of a complete graph?

Given a complete graph whose edges are colored by 3 colors, a compatible 3-coloring is a coloring of nodes such that no edge of the graph has the same color as its end-points. The best algorithm I ...
user avatar
7 votes
4 answers
990 views

What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

Input: a graph with n nodes, Output: A clique of size $O(\log n)$, Providing links to references would be great
user avatar
120 votes
18 answers
9k views

Examples of the price of abstraction?

Theoretical computer science has provided some examples of "the price of abstraction." The two most prominent are for Gaussian elimination and sorting. Namely: It is known that Gaussian ...
13 votes
1 answer
305 views

Reference to lower bound on separator in a grid?

It is easy to verify that given the d dimensional grid of the integer points $\{1,\ldots,n\}^d$, with the regular adjacency, one can find a separator of size $n^{d-1}$ (just pick any middle hyperplane,...
user avatar
7 votes
4 answers
414 views

Complexity class separation in the presence of relativization barriers

Give an example of complexity classes $M$ and $N$ and oracles $A$ and $B$ such that 1. $M^A=N^A$ and 2. $M^B\neq N^B$ and 3. $M \neq N$.
user avatar
  • 341
29 votes
0 answers
1k views

Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?

By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e. sub-exponential deterministic simulation which appears correct i.o to every efficient adversary. I think this is a proof: if $EXP\...
user avatar
4 votes
3 answers
548 views

What applications of Cantor space are there?

Are there well-established applications of the Cantor space ($2^\omega$) in computer science, other than those connected with computable real arithmetic? John Tucker's page Computation on Topological ...
user avatar
14 votes
2 answers
1k views

Space alternating hierarchy

It is known thanks to Immerman and Szelepcsényi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions). In the same paper, Immerman state that the ...
user avatar
12 votes
3 answers
642 views

$NP\cap coAM$ Languages

What other problems languages different than graph isomorphism are in $NP\cap coAM$? Can you give some references? Update: I forgot to mention that I'm interested in languages not known to be in $...
user avatar
19 votes
4 answers
1k views

"All-different hypergraph coloring" - known problem?

I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently ...
user avatar
29 votes
6 answers
1k views

Well known classes of boolean formulas that require exponentially long resolution proofs

You might often find cutting plane methods, variable propagation, branch and bound, clause learning, intelligent backtracking or even handwoven human heuristics in SAT solvers. Yet for decades the ...
15 votes
5 answers
4k views

History of recursion

Who introduced the idea of recursion? Can someone explain where it came from and how it impacted computer science?
user avatar
20 votes
3 answers
421 views

Property testing in other metrics?

There is a large literature on "property testing" -- the problem of making a small number of black box queries to a function $f\colon\{0,1\}^n \to R$ to distinguish between two cases: $f$ is a ...
user avatar
  • 9,800
41 votes
9 answers
5k views

References for TCS proof techniques

Are there any references (online or in book form) that organize and discuss TCS theorems by proof technique? Garey and Johnson do this for the various kinds of widget constructions needed for NP-...
11 votes
1 answer
263 views

Can someone suggest a recent survey on product form Markov chains?

I'm especially interested in their use in model checking applications. I have Open, Closed and Mixed Networks of Queues with Different Classes of Customers by Baskett et al. Any other suggestions ...
user avatar
28 votes
3 answers
2k views

Translating SAT to HornSAT

Is it possible to translate a boolean formula B into an equivalent conjunction of Horn clauses? The Wikipedia article about HornSAT seems to imply that it is, but I have not been able to chase down ...
user avatar
29 votes
4 answers
2k views

Bounded-cardinality bounded-frequency set cover: hardness of approximation

Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets. Example: the case $k = 4$ ...
user avatar
30 votes
2 answers
6k views

What would be the consequences of factoring being NP-complete?

Are there any references covering this?
user avatar
67 votes
17 answers
4k views

Applications of TCS to classical mathematics?

We in TCS often use powerful results and ideas from classical mathematics (algebra, topology, analysis, geometry, etc.). What are some examples of when it has gone the other way around? Here ...
36 votes
5 answers
2k views

Complexity of testing for a value versus computing a function

In general we know that the complexity of testing whether a function takes a particular value at a given input is easier than evaluating the function at that input. For example: Evaluating the ...
user avatar
10 votes
5 answers
3k views

What are good references on understanding online learning?

Specifically, I'm asking for resources to learn about machine learning systems that can update their respective belief networks (or equivalent) during operation. I've even run across a few, though I ...
17 votes
2 answers
671 views

H-free cut problem

Suppose you are given a connected, simple, undirected graph H. The H-free cut problem is defined as follows: Given a simple, undirected graph G, is there a cut (partition of vertices into two ...
user avatar
  • 1,855
65 votes
11 answers
5k views

What are good references to understanding the proof of the PCP theorem?

I'm familiar with a lot of results that use the PCP theorem (mainly in approximating algorithms), but I've never come across a clear explanation of the PCP theorem (ie, that $\mathsf{NP} = \mathsf{PCP}...
user avatar
20 votes
2 answers
1k views

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 ...
user avatar
  • 5,963
24 votes
3 answers
1k views

Graph Isomorphism and hidden subgroups

I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
user avatar
21 votes
1 answer
324 views

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 ?
user avatar
17 votes
3 answers
758 views

Are there any known implementations for quantum computing constructs?

Quantum Computation is an active area of research that aims to take advantage of quantum physics (e.g. quantum entanglement) to advance the efficiency capabilities of computers (does not alter the ...
user avatar
  • 2,213

1
27 28 29 30
31