Welcome to Combinatorics and Optimization
Spring 2021 Undergraduate Research Assistantship Program (URA). ***ON-LINE APPICATIONS OPEN November 9, 2020 - December 15, 2020.***
The very successful Tutte's 100th Distinguished Lecture Series has now completed. That success has led to a Tutte Distinguished Lecture once per term. The next lecture will happen in the Spring term.
*Recordings of occurred talks are all available on C&O's YouTube Channel.
New Deadline: February 1, '20
- Nov. 13, 2020
Earlier this year, Canada and the United Kingdom (UK) joined together to put a call out for proposals of collaborations between leading-edge scientists and potential innovative users from industry and government sectors to accelerate the development of quantum technologies.
- Nov. 12, 2020
“When I was a kid, I always begged my parents to buy me those little Mind Benders puzzles,” remembered Rose McCarty. “My favorite puzzles were the ones that were so difficult that I wasn’t sure whether or not I could actually solve them. At Waterloo Math, I’m the one coming up with different puzzles to solve. I have an opportunity to tackle big, imprecise, unwieldly problems that determine what my field will look like in 20 years.”
- Oct. 30, 2020
Craig Daniels, in an article for Communitech News, traces the rise of the cybersecurity industry in Waterloo, from Bill Tutte's work at Bletchley Park during the Second World War, to the formation of Certicom Corp. by Professors Gord Agnew, Ron Mullin and Scott Vanstone, to the present time.
- Nov. 23, 2020
Title: Complexity Measures on the Symmetric Group and Beyond
Speaker: Nathan Lindzey Affiliation: CU Boulder Zoom: Contact Soffia Arnadottir
A classical result in complexity theory states that a degree-d Boolean function on the hypercube can be computed using a decision tree of depth poly(d). Conversely, a Boolean function computed by a decision tree of depth d has degree at most d. Thus degree and decision tree complexity are polynomially related. Many other complexity measures of Boolean functions on the hypercube are polynomially related to the degree (e.g., approximate degree, certificate complexity, block sensitivity), and last year Huang famously added sensitivity to the list. Can we prove similar results for Boolean functions on other combinatorial domains?