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)

*Derandomiation of Auctions*by Aggarwal, Fiat, Goldberg, Hartline, Immorlica, Sudan HAT PROBLEM: people, colors, simul, want that for each color , of color them get it right. They give easy randomized alg then deterministic one. AUCTION*Hat Guessing Games*by Butler, Hajiaghahi, Kleinberg, Leighton. BHKL SIAM Journal of discrete math, Vol 22, 592-605, 2008.*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.*A New variation of the Hat guessing game*By Ma, Sun, Yu. MSY HAT PROBLEM: Simul, 2-colors, everyone passes or guesses, at least must not pass and get it right, nobody can get it wrong. Random, not adversary.*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.*Yet another hat game*by Paterson, Stinson. HAT PROBLEM: Line graph, colors, sequential voting, can pass, objective is at least one player gets it right and nobody gets it wrong. Yet Another Hat Game*A combinatorial approach to Ebert's Hat Game with many colors*by Tantipongipat. T EJC 2014*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.*Guessing games on triangle-free graphs*Cameron, Dang, Riis. HAT GAME is on a graph- simul, must get all right. people, colors. EJC. CDR*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*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.*A Line of Sages*by Tanya Khovanova. Line of Sages HAT GAME: hats, colors, everyone gets a different color and everyone has to say a different color. In a line. Math Intelligence 2014.*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*The Three Hat Problem*by Brian Benson and Yang Want. U HAT GAME: Positive integers on the hats such that . Players in turn either identify their number of pass. Need to never be wrong an eventually someone is right. ARXIV 2007.*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.*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.*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.*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*Finite dynamical Systems, Hat Games, and Coding Theory*by Maximilen Gadouleau G Applies Hat Games to dynamicals systems- On Hats and other Covers. G HAT GAME- Simul, some can pass, nobody can be wrong, random not adversary, BUT with colors, not 2.
*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*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.*Hat Problem on a Graph (PhD)*by Marcin Krzywkowski. HAT GAME- the people are on a variety of graphs. Hats Problem on a Graph