Blogs about: Cse 599s

Featured Blog

Lecture P1. From Integrality Gaps to Dictatorship Tests2 comments

James Lee wrote 4 years ago: Here are Prasad Raghavendra‘s notes on one of two guest lectures he gave for CSE 599S. Prasad … more →

Tags: discrete harmonic analysis, hardness of approximation, invariance principle

Lecture 8a. A primer on simplicial complexes and collapsibility1 comment

James Lee wrote 4 years ago: Before we can apply more advanced fixed point theorems to the Evasiveness Conjecture, we need a litt … more →

Tags: Lecture, Math, simplicial complex, collapsible, evasiveness conjecture

Lecture 7: The evasiveness conjecture3 comments

James Lee wrote 4 years ago: Continuing our look at some toplogical methods, today we’ll see the evasiveness conjecture in … more →

Tags: Lecture, Math, decision tree complexity, evasiveness

Lecture 6: Borsuk-Ulam and some combinatorial applications1 comment

James Lee wrote 4 years ago: Now we’ll move away from spectral methods, and into a few lectures on topological methods.  To … more →

Tags: Lecture, Math, Borsuk-Ulam theorem, Kneser conjecture, lovász, chromatic number

Lecture 5: Uniformizing graphs, multi-flows, and eigenvalues2 comments

James Lee wrote 4 years ago: In the previous lecture, we gave an upper bound on the second eigenvalue of the Laplacian of (bounde … more →

Tags: Math, Lecture, crossing number inequality, eigenvalues, embeddings, Metric Geometry, multi-commodity flows, Planar graphs

Lecture 4: Conformal mappings, circle packings, and spectral geometry5 comments

James Lee wrote 4 years ago: In Lecture 2, we used spectral partitioning to rule out the existence of a strong parallel repetitio … more →

Tags: Lecture, Math, Cheeger's inequality, circle packing, conformal mapping, Planar graphs, second eigenvalue, Spectral partitioning

Lecture 2: Spectral partitioning and near-optimal foams5 comments

James Lee wrote 4 years ago: In the last lecture, we reduced the problem of cheating in (the k-times repeated m-cycle game) to fi … more →

Tags: Math, Lecture, Spectral partitioning, Cheeger's inequality, foams, unique games conjecture

Lecture 1: Cheating with foams5 comments

James Lee wrote 4 years ago: This the first lecture for CSE 599S:  Analytical and geometric methods in the theory of computation. … more →

Tags: Math, Lecture, Parallel repetition, foams, unique games conjecture


Related Tags
All →

Follow this tag via RSS