A p-random restriction is a random partial input obtained by independently leaving each input variable unset with probability p setting them to either 0,1 with (1-p)/2 each.
An algebraic circuit computes a polynomial using addition and multiplication operators. Understanding the power of algebraic circuits has close connections to understanding general computation.
Group decision-making is a ubiquitous phenomenon with diverse applications ranging from political elections to recommender systems and from organ exchanges to online marketplaces.
Expander graphs are sparse but highly connected graphs, which find a variety of uses in CS. If the vertices of an expander are labelled by 0 or 1, a $t$-step walk gives a $t$-bit string.
