§4.2: Tribes

In this section we study the tribes DNF formulas, which serve as an important examples and counterexamples in analysis of boolean functions. Perhaps the most notable feature of the tribes function is that (for a suitable choice of parameters) it is essentially unbiased and yet all of its influences are quite tiny.

[...]

January 31st, 2012 | Tags: | Category: All chapter sections, Chapter 4: DNF formulas and small-depth circuits | Leave a comment

§2.1: Social choice functions

In this section we describe some rudiments of the mathematics of social choice, a topic studied by economists, political scientists, mathematicians, and computer scientists. The fundamental question in this area is how best to aggregate the opinions of many agents. Examples where this problem arises include citizens voting in an election, committees deciding on [...]

November 21st, 2011 | Tags: , , , , , , | Category: All chapter sections, Chapter 2: Basic concepts and social choice | 8 comments