nhaliday + linear-programming   19

Abstract: It is well known that the set of correlated equilibrium distributions of an n-player noncooperative game is a convex polytope that includes all the Nash equilibrium distributions. We demonstrate an elementary yet surprising result: the Nash equilibria all lie on the boundary of the polytope.
pdf  nibble  papers  ORFE  game-theory  optimization  geometry  dimensionality  linear-algebra  equilibrium  structure  differential  correlation  iidness  acm  linear-programming  spatial  characterization  levers 
may 2019 by nhaliday
6.896: Essential Coding Theory
- probabilistic method and Chernoff bound for Shannon coding
- probabilistic method for asymptotically good Hamming codes (Gilbert coding)
- sparsity used for LDPC codes
mit  course  yoga  tcs  complexity  coding-theory  math.AG  fields  polynomials  pigeonhole-markov  linear-algebra  probabilistic-method  lecture-notes  bits  sparsity  concentration-of-measure  linear-programming  linearity  expanders  hamming  pseudorandomness  crypto  rigorous-crypto  communication-complexity  no-go  madhu-sudan  shannon  unit  p:**  quixotic  advanced 
february 2017 by nhaliday
Lecture 11
In which we prove that the Edmonds-Karp algorithm for maximum flow is a strongly polynomial time algorithm, and we begin to talk about the push-relabel approach.
pdf  lecture-notes  exposition  optimization  algorithms  linear-programming  graphs  stanford  luca-trevisan  nibble  direction  stock-flow  tcs  constraint-satisfaction  tcstariat 
january 2017 by nhaliday
Lecture 16
In which we define a multi-commodity flow problem, and we see that its dual is the relaxation of a useful graph partitioning problem. The relaxation can be rounded to yield an approximate graph partitioning algorithm.
pdf  lecture-notes  exposition  optimization  linear-programming  graphs  graph-theory  algorithms  duality  rounding  stanford  approximation  rand-approx  luca-trevisan  relaxation  nibble  stock-flow  constraint-satisfaction  tcs  tcstariat 
january 2017 by nhaliday
Carathéodory's theorem (convex hull) - Wikipedia
- any convex combination in R^d can be pared down to at most d+1 points
- eg, in R^2 you can always fit a point in convex hull in a triangle
tcs  acm  math.MG  geometry  levers  wiki  reference  optimization  linear-programming  math  linear-algebra  nibble  spatial  curvature  convexity-curvature 
january 2017 by nhaliday
(Gil Kalai) The weak epsilon-net problem | What's new
This is a problem in discrete and convex geometry. It seeks to quantify the intuitively obvious fact that large convex bodies are so “fat” that they cannot avoid “detection” by a small number of observation points.
gowers  mathtariat  tcstariat  tcs  math  concept  rounding  linear-programming  research  open-problems  geometry  math.CO  magnitude  probabilistic-method  math.MG  discrete  nibble  org:bleg  questions  curvature  pigeonhole-markov  convexity-curvature 
january 2017 by nhaliday
Book Review: Red Plenty | Slate Star Codex
my favorite anecdote:

The “hero” of Red Plenty – although most of the vignettes didn’t involve him directly – was Leonid Kantorovich, a Soviet mathematician who thought he could solve the problem. He invented the technique of linear programming, a method of solving optimization problems perfectly suited to allocating resources throughout an economy. He immediately realized its potential and wrote a nice letter to Stalin politely suggesting his current method of doing economics was wrong and he could do better – this during a time when everyone else in Russia was desperately trying to avoid having Stalin notice them because he tended to kill anyone he noticed. Luckily the letter was intercepted by a kindly mid-level official, who kept it away from Stalin and warehoused Kantorovich in a university somewhere.

During the “Khruschev thaw”, Kantorovich started getting some more politically adept followers, the higher-ups started taking note, and there was a real movement to get his ideas implemented. A few industries were run on Kantorovichian principles as a test case and seemed to do pretty well. There was an inevitable backlash. Opponents accused the linear programmers of being capitalists-in-disguise, which wasn’t helped by their use of something called “shadow prices”. But the combination of their own political adeptness and some high-level support from Khruschev – who alone of all the Soviet leaders seemed to really believe in his own cause and be a pretty okay guy – put them within arm’s reach of getting their plans implemented.

But when elements of linear programming were adopted, they were adopted piecemeal and toothless. The book places the blame on Alexei Kosygen, who implemented a bunch of economic reforms that failed, in a chapter that makes it clear exactly how constrained the Soviet leadership really was. You hear about Stalin, you imagine these guys having total power, but in reality they walked a narrow line, and all these “shadow prices” required more political capital than they were willing to mobilize, even when they thought Kantorovich might have a point.
books  review  yvain  ssc  russia  history  politics  government  polisci  left-wing  ratty  political-econ  cold-war  linear-programming  mostly-modern  authoritarianism  technocracy  communism  utopia-dystopia 
november 2016 by nhaliday

bundles : academetcs

related tags

acm  advanced  adversarial  alg-combo  algorithms  amortization-potential  ankur-moitra  approximation  atoms  authoritarianism  average-case  big-picture  bits  books  characterization  chart  cmu  cocktail  coding-theory  cold-war  communication-complexity  communism  complexity  compressed-sensing  compression  concentration-of-measure  concept  constraint-satisfaction  convexity-curvature  cool  correlation  counting  course  crypto  curvature  data-structures  decision-theory  differential  differential-privacy  dimensionality  direction  discrete  duality  economics  elegance  embeddings  ensembles  equilibrium  expanders  explanation  exploratory  exposition  fields  flux-stasis  fourier  game-theory  generalization  geometry  government  gowers  gradient-descent  graph-theory  graphs  greedy  ground-up  hamming  harvard  hashing  heuristic  hi-order-bits  high-dimension  history  huge-data-the-biggest  IEEE  iidness  information-theory  init  iterative-methods  knowledge  latency-throughput  latent-variables  lecture-notes  lectures  left-wing  lens  levers  linear-algebra  linear-programming  linearity  list  lower-bounds  luca-trevisan  madhu-sudan  magnitude  markov  matching  math  math.AG  math.CO  math.MG  math.NT  mathtariat  matrix-factorization  metabuch  metameta  methodology  mihai  mit  monte-carlo  mostly-modern  motivation  nibble  no-go  norms  online-learning  open-problems  optimization  ORFE  org:bleg  overflow  p:**  p:***  papers  pdf  perturbation  pigeonhole-markov  polisci  political-econ  politics  polynomials  positivity  princeton  probabilistic-method  pseudorandomness  q-n-a  questions  quixotic  rand-approx  random  random-matrices  random-networks  ratty  reference  reflection  regularization  relaxation  research  review  rigorous-crypto  robust  rounding  russia  s:***  sampling  sanjeev-arora  scitariat  SDP  sequential  shannon  signum  skeleton  sparsity  spatial  spectral  ssc  stanford  state  stock-flow  structure  sublinear  submodular  summary  synthesis  tcs  tcstariat  technocracy  tim-roughgarden  time  toolkit  top-n  trees  tricki  unit  utopia-dystopia  valiant  wiki  yoga  yvain  👳  🔬 

Copy this bookmark: