If we generate a sequence of independent random vectors, how long until there is a linear dependence among the vectors in the sequence? Several discrete/combinatorial problems can be rephrased in such terms for vector spaces over F_2, such as: The Birthday problem: how many people need to enter a room before there is a common birthday among the group? Random XOR-SAT: what is the probable satisfiability of a random Boolean formula using the operators AND, XOR and NOT? Perfect square subproducts: how many random positive integers are needed until a subset has product equal to a perfect square? I will overview the phenomena and theorems in this context.
Graduate Student Combinatorics Seminar
Wednesday, April 7, 2010 - 12:30pm
Omar Abuzzahab
University of Pennsylvania