Most Popular
1500 questions
23
votes
1 answer
I want an easy Gadget to prove Planar Hamiltonian Cycle NP-Complete (from Hamiltonian Cycle)
It is known that Hamiltonian (Ham for short) Cycle is NP-complete and that Planar Ham Cycle is NP-Complete. The proof for Planar Ham Cycle is not from Ham Cycle.
Is there a nice gadget that will, given a graph G, replace all of the crossings
with…
Bill GASARCH
- 549
- 2
- 4
23
votes
1 answer
Required delta between proceedings and journal versions
I am recently getting my papers rejected from journals (i.e., TALG) on the mere basis of not having a significant difference between the journal and proceedings (i.e., SODA) version.
The main reasons for me to submit to a journal is its thorough…
Algorithm
- 231
- 1
- 2
23
votes
4 answers
Monotone arithmetic circuits
The state of our knowledge about general arithmetic circuits seems to be similar to the state of our knowledge about Boolean circuits, i.e. we don't have good lower-bounds. On the other hand we have exponential size lower-bounds for monotone Boolean…
Kaveh
- 21,577
- 8
- 82
- 183
23
votes
2 answers
Relationship between symmetry and computational intractability?
The $k$-fixed point free automorphism problem asks for a graph automorphism which moves at least $k(n)$ nodes. The problem is $NP$-complete if $k(n)=n^c$ for any $c$>0.
However, If $k(n)=O(\log n)$ then the problem is polynomial time Turing…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
23
votes
4 answers
What's the point of $\eta$-conversion in lambda calculus?
I think I'm not understanding it, but $\eta$-conversion looks to me as a $\beta$-conversion that does nothing, a special case of $\beta$-conversion where the result is just the term in the lambda abstraction because there is nothing to do, kind of a…
Trylks
- 604
- 4
- 9
23
votes
3 answers
From Extractors to Pseudorandom Generators?
Luca Trevisan showed how many constructions of pseudorandom generators can in fact be thought of as extractor constructions:
http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf
Is there a meaningful converse? I.e., can "natural" constructions…
Dana Moshkovitz
- 10,979
- 1
- 50
- 77
23
votes
9 answers
Reductions from the book.
This is along the lines of "Algorithms from the Book". Although reductions are algorithms as well, I thought it doubtful that one would think of a reduction in response to the question about algorithms from the book. Hence a separate query! …
Neeldhara
- 599
- 2
- 15
23
votes
4 answers
Papers on relation between computational complexity and algebraic geometry/topology?
I was wondering what papers I should read to understand this question
A unexpected connection to other areas of mathematics such as algebraic geometry or higher cohomology. Perhaps even an area of mathematics not yet developed. Perhaps someone will…
Joshua Herman
- 1,661
- 17
- 38
23
votes
3 answers
Complexity of Tensor Rank over an Infinite Field
A tensor is a generalization of vectors and matrices to higher dimensions and the rank of a tensor also generalizes the rank of a matrix. Namely, the rank of a tensor $T$ is the minimum number of rank one tensors that sum to $T$. A vector and matrix…
Tyson Williams
- 4,258
- 2
- 23
- 44
23
votes
1 answer
Do all complexity classes have a leaf language characterization?
Leaf languages are a beautiful way to uniformly define many complexity classes. Most complexity classes are usually specified by a model of computation (e.g., deterministic/randomized TM), and a resource bound (log time, poly space, etc.). However…
Robin Kothari
- 13,617
- 2
- 60
- 116
23
votes
4 answers
Starting SAT solver papers
I want to make a first SAT solver. I know the SAT competition and the SAT conference, and there are just so many papers on this subject. I'm a starter, an overwhelmed starter. Where should I begin? Eventually I want to push the state-of-the-art. I…
Zirui Wang
- 551
- 2
- 9
23
votes
3 answers
Adding integers represented by their factorization is as hard as factoring? Reference request
I'm looking for a reference for the following result:
Adding two integers in the factored representation is as hard as factoring two integers in the usual binary representation.
(I'm pretty sure it's out there because this is something I had…
Joshua Grochow
- 37,260
- 4
- 129
- 228
23
votes
4 answers
Proof of the pumping lemma for context-free languages using pushdown automata
The pumping lemma for regular languages can be proved by considering a finite state automaton which recognizes the language studied, picking a string with a length greater than its number of states, and applying the pigeonhole principle. The pumping…
a3nm
- 9,269
- 27
- 86
23
votes
1 answer
Estimating a percentile among distributed nodes without revealing values
I have a fairly unique problem to solve and I am hoping somebody here can give me some insight into how to best tackle it.
Problem: Suppose a list of N numbers is shared among a set of participants in such a way that no single participant actually…
ryan
23
votes
5 answers
Packing rectangles into convex polygons but without rotations
I am interested in the problem of packing identical copies of (2 dimensional) rectangles into a convex (2 dimensional) polygon without overlaps. In my problem you are not allowed to rotate the rectangles and can assume that they are oriented…
Simd
- 3,902
- 20
- 49