linear-programming   167

« earlier    

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 
10 weeks ago by nhaliday
Practical Optimization: A Gentle Introduction
Nice introduction to linear programming/optimization.
See Chapter 10 "The Shortest Route Problem."
0root-research  linear-programming  shortest-path 
april 2019 by brad73435
Kairouz, Oh, Viswanath, "Extremal Mechanisms for Local Differential Privacy"
"We introduce a family of extremal privatization mechanisms, which we call staircase mechanisms, and prove that it contains the optimal privatization mechanism that maximizes utility. We further show that for all information theoretic utility functions studied in this paper, maximizing utility is equivalent to solving a linear program, the outcome of which is the optimal staircase mechanism."
local-differential-privacy  differential-privacy  research-article  linear-programming  randomization 
april 2019 by arthegall
[1801.02602] Three Puzzles on Mathematics, Computation, and Games
In this lecture I will talk about three mathematical puzzles involving mathematics and computation that have preoccupied me over the years. The first puzzle is to understand the amazing success of the simplex algorithm for linear programming. The second puzzle is about errors made when votes are counted during elections. The third puzzle is: are quantum computers possible?
mathematics  computational-complexity  rather-interesting  lecture  to-write-about  linear-programming 
march 2018 by Vaguery
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

« earlier    

related tags

0root-research  acm  advanced  agents-but-no-simulation  ai  alg-combo  algorithm  algorithms  amusing  analytical  ankur-moitra  apprenticeship-learning  approximation-algorithms  approximation  arxiv  atoms  authoritarianism  average-case  bargaining  big-picture  bits  book  books  boolean  c  characterization  chart  class  classification  classpage  clustering  cmu  cocktail  coding-theory  coding  cold-war  combinatorial-optimization  communication-complexity  communism  complexity  compressed-sensing  compression  computational-complexity  computational-geometry  computer-science  computerscience  concentration-of-measure  concept  consider:controllers  consider:feature-discovery  consider:feature-extraction  consider:implementing  consider:nk-models  consider:representation  constraint-optimization  constraint-programming  constraint-satisfaction  constraint-solver  constraints  convex-hulls  convexity-curvature  cool  cooperation  correlation  counting  course-materials  course  coursepage  coursera  crypto  cs  curvature  cutting-planes  dantzig  data-structures  decision-theory  deep-learning  diet  differential-privacy  differential  dimensionality  direction  discrete  dp  duality  dynamic-programming  economics  edit-distance  elegance  embeddings  ensembles  equilibrium  expanders  explanation  exposition  feature-extraction  fields  fitness-landscapes  fourier  from:gavin  game-theory  gem  gene-regulatory-networks  geometry  github  glpk  gnu  gold-learning-star  google  government  gowers  gradient-descent  graph-theory  graphs  ground-up  halting-problem  hamming  harvard  hashing  haskell  heuristic  hi-order-bits  high-dimension  history  horse-races  huge-data-the-biggest  humour  ide  ieee  iidness  ilp  image-processing  information-theory  init  integer-programming  iterative-methods  javascript  js  kernel-methods  knowledge  l1  latent-variables  learning-by-doing  lecture-notes  lecture  lectures  left-wing  lens  levers  library  libs  linear-algebra  linear-optimization  linearity  list  local-differential-privacy  locomotive  logic  looking-to-see  lower-bounds  lp  luca-trevisan  machine-learning  machinelearning  madhu-sudan  magnitude  markov  matching  math-history  math.nt  math  mathematical-programming  mathematics  mathprog  mathtariat  matlab  matrix-factorization  max-flow  mechanism-design  memoria  meta-optimization  metabuch  metameta  methodology  metrics  mihai  min-cost  mit  modeling  monte-carlo  mostly-modern  motivation  multiobjective-optimization  netlib  networking  neural-networks  nibble  nnmf  no-free-lunch  no-go  nobel  norms  notes  nudge-targets  number-theory  nutrition  ocr  online-learning  online  open-problems  opensource  operational-research  operations-research  opt  optimi  optimization  orfe  org:bleg  overflow  p:***  p:**  papers  parameter-adjustment  pdf  people  performance-measure  perturbation  pigeonhole-markov  pkg  polisci  political-econ  politics  polynomials  positivity  princeton  privacy  probabilistic-method  probabilistic  probability  programming-language  programming  pseudorandomness  published-1990  python  q-n-a  questions  quixotic  r  rand-approx  rand-corporation  random-matrices  random-networks  random  randomization  rather-interesting  ratty  reference  reflection  regularization  reinforcement-learning  relaxation  representation  research-article  research  review  rigorous-crypto  robust  rounding  ruby  russia  s:***  sampling  sanjeev-arora  santosh-vempala  scitariat  scraping  sdp  searching-under-the-streetlight  semidefinite-programming  shannon  shortest-path  signal-processing  signum  simplex  skeleton  software  solver  solving  soviet-internet  soviet-union  sparsity  spatial  spectral  ssc  stanford  statistics  stigler  stochastic-processes  stock-flow  structure  sublinear  submodular  summary  synthesis  system-of-equations  systems-biology  tables  tcs  tcstariat  technocracy  test-problems  the-mangle-in-practice  tim-roughgarden  to-write-about  toolkit  top-n  trial-and-error  tricki  tutorial  unit  utopia-dystopia  uw  valiant  vector-quantization  wiki  yoga  yvain  👳  🔬 

Copy this bookmark: