next up previous
Next: About this document ...

Papers on Hat Problems I want to read

by William Gasarch

(For now this is just papers that I want to gather in one place)

  1. Derandomiation of Auctions by Aggarwal, Fiat, Goldberg, Hartline, Immorlica, Sudan HAT PROBLEM: $n$ people, $c$ colors, simul, want that for each color $i$, $1/c$ of color $i$ them get it right. They give easy randomized alg then deterministic one. AUCTION
  2. Hat Guessing Games by Butler, Hajiaghahi, Kleinberg, Leighton. BHKL SIAM Journal of discrete math, Vol 22, 592-605, 2008.
  3. On the Autoreducibility of Random Sequences by Ebert, Merkle, Vollmer SIJCOMP Vol 32, No 6, 2003. EMB HAT PROBLEM: Simul, 2-colors, everyone passes or guesses, at least 1 must not pass and get it right, nobody can get it wrong. Random, not adversary.
  4. A New variation of the Hat guessing game By Ma, Sun, Yu. MSY HAT PROBLEM: Simul, $c$2-colors, everyone passes or guesses, at least $k$ must not pass and get it right, nobody can get it wrong. Random, not adversary.
  5. The Three-Color Hat Guessing Game on Cycles By Witold Szczechla. 3-colors-cycle Electronic Journal of Combinatorics. Vol 24, Issue 1, 2017. HAT PROBLEM: Graph is cycle. Simul. Everyone says a color, 3 colors, Just need one to get it right.
  6. Yet another hat game by Paterson, Stinson. HAT PROBLEM: Line graph, $c$ colors, sequential voting, can pass, objective is at least one player gets it right and nobody gets it wrong. Yet Another Hat Game
  7. A combinatorial approach to Ebert's Hat Game with many colors by Tantipongipat. T EJC 2014
  8. Covering codes for hats-on-a-line Aravamuthan and Lodha AL Hats on a line but with limited seeing or hearing and perhaps a diferent order to yell out hat color. EJC.
  9. Guessing games on triangle-free graphs Cameron, Dang, Riis. HAT GAME is on a graph- simul, must get all right. $n$ people, $c$ colors. EJC. CDR
  10. A construction for the hat problem on a directed graph by Hod and Kzrzykowski. HAT GAME- 2 colors, on a directed graph, simul, people can pass, but at least one has to get not pass and get it right. HK
  11. Guessing number of odd cycles by Atkins, Romback, Skerman. HAT GAME: simul, on a graph, no passing, all must get it correct, hats put on randomly, want high prob of success. Guessing-number-odd-cycles EJC 2017.
  12. A Line of Sages by Tanya Khovanova. Line of Sages HAT GAME: $n$ hats, $n+1$ colors, everyone gets a different color and everyone has to say a different color. In a line. Math Intelligence 2014.
  13. The Hat Game and Covering Codes by Theo van Uem HAT GAME: Simul, can pass, need to get at least 1 right, none wrong, prob putting hats on BUT the prob are not 1/2-1/2. U
  14. The Three Hat Problem by Brian Benson and Yang Want. U HAT GAME: Positive integers on the hats such that $x,y,x+y$. Players in turn either identify their number of pass. Need to never be wrong an eventually someone is right. ARXIV 2007.
  15. General three and four player 2-color hat games by Theo van Uem. U HAT GAME: Simul, can pass, need to get at least 1 right, none wrong, prob putting hats on BUT the prob are diff for each player and known.
  16. Asymetric Hat games with three players and three colors by Theo van Uem. U HAT GAME: Simul, can pass, need to get at least 1 right, none wrong, prob putting hats on BUT the prob are diff for each player and known. Only covers the 3 player, 3 color case.
  17. On a certain cooperative hat game by Jonathan Kariv, Clint van Alten, Dmytro Yeroshkin. HAT GAME: 2 players have a countable number of hats on their head. They want to both point to a white hat on their own head.
  18. New constructions and bounds for Winkler's hat game HAT PROBLEM- general graph, just need to have one person get it right. Okay if others get it wrong, no passing, Simul U
  19. Finite dynamical Systems, Hat Games, and Coding Theory by Maximilen Gadouleau G Applies Hat Games to dynamicals systems
  20. On Hats and other Covers. G HAT GAME- Simul, some can pass, nobody can be wrong, random not adversary, BUT with $c$ colors, not 2.
  21. An Introduction to Infinite Hat Problems by Christopher Hardin and Alan Taylor. HAT GAME- infinite number of people, need to get all but a finite number of them right. Needs AC. Infinite Hats and AC
  22. The expressive power of voting polynomials by Aspnes, Beigel, Furst, Rudich. Voting Polynomials HAT GAME (not sure I would count it as such)- 0-1 value hats, randomized placement, want them to VOTE on the parity. Want over half to get it right.
  23. Hat Problem on a Graph (PhD) by Marcin Krzywkowski. HAT GAME- the people are on a variety of graphs. Hats Problem on a Graph



next up previous
Next: About this document ...
Bill Gasarch 2017-07-14