Most Popular
1500 questions
15
votes
1 answer
What is the minimum required depth of reductions for NP-hardness of SAT?
As everyone knows,
SAT is complete for $\mathsf{NP}$ w.r.t. polynomial-time many-one reductions.
It is still complete w.r.t. $\mathsf{AC^0}$ many-one reductions.
My questions is what is the minimum required depth for the reductions?
More…
Kaveh
- 21,577
- 8
- 82
- 183
15
votes
2 answers
Resources for mathematicians hoping to learn more computer science
Background:
I'm coming to the end of my masters degree in Mathematics and will be starting a PhD in Logic in August. The more logic I study, the more theoretical computer science I am exposed to, e.g. recursion theory, lambda calculus, but the…
Clive Newstead
- 253
- 1
- 6
15
votes
0 answers
Fano's inequality in the high error regime
Fano's inequality says that given a random variable $X$, and a random variable $Y$ that "guesses" $X$ correctly with some probability, we can lower bound the information that $Y$ gives on $X$. More formally, given two random variables $X,Y$ that…
Or Meir
- 5,380
- 22
- 33
15
votes
1 answer
Finding the shortest path in the presence of negative cycles
Given a directed cyclic graph where the weight of each edge may be negative the concept of a "shortest path" only makes sense if there are no negative cycles, and in that case you can apply the Bellman-Ford algorithm.
However, I'm interested in…
jleahy
- 253
- 1
- 2
- 8
15
votes
1 answer
How can a problem be in NP, be NP-hard and not NP-complete?
For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP.
However, in the famous paper "The ellipsoid method and its consequences in combinatorial optimization", the authors claim that the…
Austin Buchanan
- 1,166
- 1
- 17
- 28
15
votes
1 answer
Smooth Complexity of the Nonnegative Permanent
There has been fantastic work done on the Permanent going on for the last two decades.I have been wondering for a while about the possibility of a Smooth P algorithm for the Permanent of Nonnegative Matrices. There is of course the famous JSV…
Zelah 02
- 1,578
- 7
- 16
15
votes
3 answers
Associative hash mixing
Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths and the question of how it may be extended to the…
Per Vognsen
- 2,161
- 16
- 25
15
votes
2 answers
Edit distance with move operations
Motivation: A coauthor edits a manuscript and I would like to see a clear summary of the edits. All "diff"-like tools tend to be useless if you are both moving text around (e.g., re-organising the structure) and doing local edits. Is it really so…
Jukka Suomela
- 11,500
- 2
- 53
- 116
15
votes
1 answer
Is there a quantum NC algorithm for computing GCD?
From the comments on one of my questions on MathOverflow
I get the feeling that the question regarding GCD being in $\mathsf{NC}$ vs. $\mathsf{P}$ is akin to the question regarding Integer Factorization being in $\mathsf{P}$ vs. $\mathsf{NP}$.
Is…
Turbo
- 12,812
- 1
- 19
- 68
15
votes
2 answers
Exponential Speedup in External Memory
Background
The external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses). These running times are generally given in terms of $M$, the size of memory, and $B$, the…
SamM
- 1,685
- 2
- 14
- 21
15
votes
3 answers
Can it be determined if language L lies in NP?
Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?
txwikinger
- 803
- 1
- 11
- 18
15
votes
2 answers
NP-hard problems on expander graphs?
In a 2006 presentation titled EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT?
, Nati Linial posed the following open problem:
Which $NP$-hard computational problem on graph remain hard when restricted to expander graphs?
Since then, Has any…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
15
votes
1 answer
Sparse Walsh-Hadamard Transform
The Walsh-Hadamard transform (WHT) is a generalization of the Fourier transform, and is an orthogonal transformation on a vector of real or complex numbers of dimension $d = 2^m$. The transform is popular in quantum computing, but it's been studied…
Suresh Venkat
- 32,071
- 4
- 95
- 271
15
votes
1 answer
What is the correct definition of $k$-tree?
As the title says, what is the correct definition of $k$-tree? There are several papers that talk about $k$-trees and partial $k$-trees as alternative definitions for graphs with bounded treewidth, and I've seen many seemingly incorrect definitions.…
ethkim
- 151
- 1
- 3
15
votes
5 answers
Why can machine learning not recognize prime numbers?
Say we have a vector representation of any integer of magnitude n, V_n
This vector is the input to a machine learning algorithm.
First question : For what type of representations is it possible to learn the primality/compositeness of n using a…
Cris Stringfellow
- 389
- 1
- 2
- 9