The 26th Theory Weekly Meeting will happen this Friday between 2:00 – 3:00 pm at 203 Davis Hall (Theory Lab). The schedule will be as follows :
2:00 – 3:00 pm – A talk by Chaowen Guan. The abstract of this talk in his words:
This talk will be demonstrating the connection between the complexity of evaluating polynomials and integer factorization, which was first done by Lipton. We will show a more general result by highlighting the importance of of a global bound on sufficiently many distinct roots of the polynomial. In particular, we can derive tradeoffs between the randomized complexity of factoring and the number of distinct roots. At last, we will also show what could the actual ”defenses” of factoring against efficient attacks.
The 25th Theory Weekly Meeting will happen this Friday between 2:00 – 3:00 pm at 203 Davis Hall (Theory Lab). The schedule will be as follows :
2:00 – 3:00 pm – A talk by Oliver Kennedy. The abstract of this talk in his words:
Over the years, the database community has developed a range of semantics for coping with uncertainty (ambiguity, conflicts, and/or incompleteness) in data. After introducing the space, Oliver will outline several of these semantics, including both data models, query processing semantics, and their embeddings into classical relational query processing. Oliver will also discuss a query-rewriting technique that ‘virtualizes’ uncertainty, making it possible to vary the complexity of query processing, allowing simpler representations of uncertain results to be generated more efficiently. Finally, Oliver will show how this technique is used in the Mimir probabilistic query processing system.
Warning: This talk will not include any novel complexity results or formal proofs… and you may be subjected to one or more graphs.