Most Popular
1500 questions
20
votes
2 answers
Is a PhD in TCS the best way towards achieving a career in industrial research?
My idea of a dream career is a career in industrial research, where one gets to tackle problems which are challenging, and also have a practical usage. To that end, is pursuing a PhD in TCS (I'm interested in topics such as distributed/parallel…
TCSGrad
- 456
- 4
- 11
20
votes
1 answer
Problems in NP but not in Average-P/poly
The Karp–Lipton Theoem states that if $\mathsf{NP} \subset \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma^P_2}$. Therefore, assuming separations between $\mathsf{\Sigma^P_2}$ and $\mathsf{\Sigma^P_3}$, no $\mathsf{NP}$-complete…
Sadeq Dousti
- 16,479
- 9
- 69
- 152
20
votes
3 answers
Computing sum of sparse polynomials squared in O(n log n) time?
Suppose we have polynomials $p_1,...,p_m$ of degree at most $n$, $n>m$, such that the total number of nonzero coefficients is $n$ (i.e., the polynomials are sparse). I am interested in an efficient algorithm for computing the polynomial:
$$\sum_i…
Rasmus Pagh
- 962
- 6
- 11
20
votes
3 answers
What is the right theoretical model to design algorithms for current and upcoming high performance computers
This question is similar to a more general question for what is the right theoretical model of a computer to design algorithm and data structures in.
Here, I ask specifically about current high performance computers (like the ones listed as the Top…
Riko Jacob
- 990
- 7
- 12
20
votes
3 answers
Problems that are NP-complete under randomized or P/poly reductions.
In this question, we appear to have identified a natural problem that is NP-complete under randomized reductions, but possibly not under deterministic reductions (although this depends on which unproven assumptions in number theory are true). Are…
Peter Shor
- 24,763
- 4
- 93
- 133
20
votes
1 answer
Finding the distance between two polynomials (represented as trees)
A colleague who works on genetic programming asked me the following question. I first tried to solve it based on a greedy approach, but on a second thought, I found a counterexample to the greedy algorithm. So, I thought it's worth mentioning…
Sadeq Dousti
- 16,479
- 9
- 69
- 152
20
votes
3 answers
Examples of the value of proofs for algorithms
In teaching Intro. Algorithms to undergrads, one of the most difficult tasks is to motivate why they need to know how to prove things about algorithms. (For many students, at least in many US universities, they may see some basic proofs in Discrete…
Joshua Grochow
- 37,260
- 4
- 129
- 228
20
votes
4 answers
Is there an equivalent to derandomization for quantum algorithms?
With some randomized algorithms you can derandomize the algorithm, removing (at a possible cost in run time) the use of random bits and maximizing some lower bound on the objective (usually computed using the fact that the theorems are about the…
Alexandre Passos
- 1,459
- 12
- 20
20
votes
6 answers
Should experts in TCS charge money to read proofs that P != NP?
It's well-known that there are tons of amateurs--myself included--who are interested in the P vs. NP problem. There are also many amatuers--myself still included--who have made attempts to resolve the problem.
One problem that I think the TCS…
user1338
20
votes
1 answer
Is prime-counting function #P-complete?
Recall $\pi(n)$ the number of primes $\le n$ is the prime-counting function. By "PRIMES in P", computing $\pi(n)$ is in #P. Is the problem #P-complete? Or, perhaps, there is a complexity reason to believe that this problem is not #P-complete? …
Igor Pak
- 812
- 5
- 15
20
votes
5 answers
A special class of languages: “circular” languages. Is it known?
Define the following class of "circular" languages over a finite alphabet Sigma. Actually, the name already exists to denote a different thing it seems, used in the field of DNA computing. AFAICT, that's a different class of languages.
A language L…
vincenzoml
- 363
- 1
- 7
20
votes
2 answers
Barriers to show $P=NP$
We all know showing $P\ne NP$ has barriers. We all have studied these barriers because we believe $P\ne NP$.
However assume $P=NP$ and there are wise people who believe that possibility exists. If this is indeed the case then the very fact that we…
Turbo
- 12,812
- 1
- 19
- 68
20
votes
2 answers
Can any computational challenge be transformed to proof-of-work?
The seemingly pointlessness of cryptocurrency mining raised the question of useful alternatives, see these questions on Bitcoin, CST, MO.
I wonder whether there exists an algorithm that can convert practically any computational challenge $\mathcal…
domotorp
- 13,931
- 37
- 93
20
votes
12 answers
Is there any book on the philosophical implications of Theoretical Computer Science?
I find some books about computers, but all of them are about technology. I want something more linked to theory.
Raphael Augusto
- 583
- 3
- 13
20
votes
1 answer
Consequences of UP equals NP
EDIT at 2011/02/08:
After some references finding and reading, I decided to separate the original question into two separate ones. Here's the part concerning UP vs NP, for the syntactic and semantic classes part please see Benefits for syntactic and…
Hsien-Chih Chang 張顯之
- 7,638
- 4
- 44
- 83