NP-hardness
17
MENTIONS
11
EPISODES
5
PODCASTS
Search complete. 17 mentions across 11 episodes found for "NP-hardness".
Nov 19, 2026
Spatial Query Processing Utilizing Voronoi Diagrams
M
44:19Mehdi SharifzadehGUEST
Give me the one with the sequence that gives the optimal route.
M
44:22Mehdi SharifzadehGUEST
And that's actually NP-hard.
M
44:24Mehdi SharifzadehGUEST
So, they provided approximation solutions and other queries like k-stop queries.
M
44:33Mehdi SharifzadehGUEST
Now, let's say how I'm using, I'm using Warren Diagram to solve this.
Masterclass Edition: Yann LeCun on AMI Labs and the Path Beyond LLMs
Y
38:39Yann LeCunGUEST
Not immediately realizing that most of the problems that you need to solve, almost all of them are intractable.
Y
38:48Yann LeCunGUEST
NP-complete, NP-hard, or whatever, right? And so they started relying on heuristics and blah, blah, blah.
Y
38:55Yann LeCunGUEST
And that led to sort of the classical Google fashion AI kind of branch, if you want.
Y
39:01Yann LeCunGUEST
And then simultaneously, you know, also in the 50s, there were people who were trying to do neural nets at the time, and, you know, they didn't go very far, and they kind of died in the late 60s and reappeared only in the 1980s with backprop with multilayer neural nets.
When is a Googol Not Enough?
W
50:51Washington TaylorGUEST
It's really hard to compute those things.
W
50:52Washington TaylorGUEST
We don't even have mathematically the formalism to do it, but even if we could, there was a nice argument by Dennef and Douglas which shows that even in the simple models, the problem of finding a vacuum with a small lambda, even given some simple models for how to compute it, is an NP-hard problem.
W
51:08Washington TaylorGUEST
It's a lot like the minimal length vector problem.
W
51:10Washington TaylorGUEST
You know, this problem where if you're given vector, you're given a set of vectors in a space and the question is, what's the integral linear combination of those vectors of the shortest length?
W
51:18Washington TaylorGUEST
That's an NP-hard problem.
W
51:19Washington TaylorGUEST
And that is at least the cosmological constant problem, even in the very simplest cartoon characterization is at least that hard.
W
51:27Washington TaylorGUEST
So, even if somebody could write down all the models and then ask you to calculate the cosmological constants, it would be very hard to locate our vacuum with 10 to the minus 120 cosmological constant.
Stanford Lecture: Donald Knuth - "Trees and chordal graphs" (2012)
D
80:50Donald KnuthGUEST
Um, Yeah.
D
80:52Donald KnuthGUEST
Um, but- but, uh, uh, there- there- there's, you know, the fast ways to color chordal graphs, there's fast ways to certify independent sets in chordal graphs, and, uh, almost every problem, you know, that's- that- that's NP-hard on general graphs, so they- has a- some kind of efficient algorithm on chordal graphs, and- and on trees usually, but not- not always, but.
D
81:18Donald KnuthGUEST
So, yeah.
S
81:19speaker_8UNKNOWN
The definition of portal graphs is around the number three.
Differentially Private Multiway and k-Cut
Z
5:57Zongrui ZouGUEST
And as you can see, when k is 2, it is just the equivalent to find the mean s, t parts.
Z
6:03Zongrui ZouGUEST
And when k is at least 3, finding motorway cut becomes NP-hard.
Z
6:09Zongrui ZouGUEST
And another highly related definition is a global k-card.
Z
6:12Zongrui ZouGUEST
Again, given a beta graph, we would like to remove minimal edge base to separate the graph into whatever k-connected components.
Crossover random fields: A practical framework for learning and inference wit...
J
7:24Justin DomkeGUEST
It's not going to work.
J
7:26Justin DomkeGUEST
And in fact, not only is dynamic programming hopeless, but the problem in general is NP-hard and it's NP-hard even to compute the marginals within some constant factor.
J
7:33Justin DomkeGUEST
So, in general graphs, marginalization is a very tough problem.
J
7:38Justin DomkeGUEST
But let's return to doing marginals on tractable graphs.
ICM 2026 Invited Section Lecture – Laurent Massoulie
L
6:53Laurent MassouliéGUEST
Uh, and since we can square this term, which is, uh, uh, zero-one valued without changing the objective, you can, uh, rephrase it as trying to find a, a permutation matrix that maximizes the trace of the product of, uh, the adjacency matrix A1 of the first graph times permutation matrix pi times, uh, adjacency matrix A2 of the second graph times the transpose of pi.
L
7:18Laurent MassouliéGUEST
And, uh, well, this problem is the well-known, uh, quadratic assignment problem, and it is known to be NP-hard, so this is computationally difficult in general.
L
7:27Laurent MassouliéGUEST
So, uh, let me, uh, go very quickly over the applications of that problem because this is ICM, and so we don't need to spend too much time on that.
L
7:36Laurent MassouliéGUEST
But there are many applications, let's, uh, let's say.
Stanford Seminar - Why would we want a multi-agent system unstable
M
4:50Mrdjan JankovicGUEST
So, alternatives.
M
4:53Mrdjan JankovicGUEST
You can see everything is NP-hard, all the other options, NP-hard, meaning essentially really difficult.
M
5:01Mrdjan JankovicGUEST
Discrete search is officially exponential, but whenever it says NP, you can say it's pretty much exponential.
M
5:08Mrdjan JankovicGUEST
Now, I can't talk... too much about this.
How Hackers Drained Billions From Binance
C
43:17ChrisHOST
Right.
C
43:18ChrisHOST
Which some would call NP-hard, which is a set of problems that are at least as hard as NP.
C
43:25ChrisHOST
We can go into what that means later if we still care.
C
43:29ChrisHOST
But anyway, 3SAT is one of these problems.
Stanford CS229 Machine Learning | Spring 2026 | Lecture 10: GMM (EM), PCA
C
13:15Chris RéHOST
Yeah.
C
13:15Chris RéHOST
But the other function, just like K-means, was, you know, NP-hard, if you remember last time, but also was a hard function to solve exactly.
C
13:22Chris RéHOST
So, you know, the underlying function, you know, it's going to be an approximation in the sense that, you know, we hope to get a good solution out of this.
C
13:30Chris RéHOST
We may not have any guarantees.
1 more episode mentions NP-hardness.
Create an account to see the whole feed, search across every transcript, and follow the entities you care about.