Finitary Boolean functions
| dc.contributor.author | Agdur, Vilhelm | |
| dc.contributor.department | Chalmers tekniska högskola / Institutionen för matematiska vetenskaper | sv |
| dc.contributor.examiner | Jonasson, Johan | |
| dc.date.accessioned | 2019-12-11T09:59:52Z | |
| dc.date.available | 2019-12-11T09:59:52Z | |
| dc.date.issued | 2019 | sv |
| dc.date.submitted | 2019 | |
| dc.description.abstract | We study functions on the infinite-dimensional Hamming cube (-1,1)**, in particu- lar Boolean functions into (-1,1), generalising results on analysis of Boolean functions on (-1,1); for n 2 N. The notion of noise sensitivity, first studied in [BKS99], is extended to this setting, and basic Fourier formulas are established. We also prove hypercontractivity estimates for these functions, and give a version of the Kahn-Kalai- Linial theorem giving a bound relating the total in uence to the maximal in uence. Particular attention is paid to so-called finitary functions, which are functions for which there exists an algorithm that almost surely queries only finitely many bits. Two versions of the Benjamini-Kalai-Schramm theorem characterizing noise sensitivity in terms of the sum of squared influences are given, under additional moment hypotheses on the amount of bits looked at by an algorithm. A version of the Kahn-Kalai-Linial theorem giving that the maximal influence is of order log(n) n is also given, replacing n with the expected number of bits looked at by an algorithm. Finally, we show that the result in [SS10] that revealments going to zero implies noise sensitivity also holds for finitary functions, and apply this to show noise sensitivity of a version of the voter model on suffciently sparse graphs. | sv |
| dc.identifier.coursecode | MMA910 | sv |
| dc.identifier.uri | https://hdl.handle.net/20.500.12380/300587 | |
| dc.language.iso | eng | sv |
| dc.setspec.uppsok | PhysicsChemistryMaths | |
| dc.title | Finitary Boolean functions | sv |
| dc.type.degree | Examensarbete för masterexamen | sv |
| dc.type.uppsok | H |
Ladda ner
Original bundle
1 - 1 av 1
Hämtar...
- Namn:
- Finitary Boolean functions -- Vilhelm Agdur.pdf
- Storlek:
- 593.33 KB
- Format:
- Adobe Portable Document Format
- Beskrivning:
License bundle
1 - 1 av 1
Hämtar...
- Namn:
- license.txt
- Storlek:
- 1.14 KB
- Format:
- Item-specific license agreed upon to submission
- Beskrivning: