Abstract: The classical Ulam’s problem asks about the length of a longest increasing subsequence in a uniform random permutation.

Abstract: The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. Approximate degree is known to be a lower bound on quantum query complexity.

Abstract: A cyclic order on a set X is a ternary relation on X satisfying three conditions called cyclicity, asymmetry and transitivity. These can be thought of as analogues of partial orders.

Quantified Boolean Formulas (QBF) are a natural extension of the SAT problem, with more sophisticated semantics: functions witnessing the truth of a QBF can be interpreted as strategies in a two-player game.