aspuru-list March 2013

aspuru-list@lists.fas.harvard.edu

35 participants
62 discussions

[Aspuru-Guzik group list] [IACS-events] Next IACS Seminar March 15

by Rosalind Reid

A quick note to let our friends know that there will *not* be an IACS Seminar on Friday, March 8. The talk by David H. Rogers of Sandia Labs has been rescheduled for April 5. Our next seminar will be March 15, when Mark Kramer from BU will speak on "Multi-scale Seizure Dynamics." Look for more details next week. ----------------- Rosalind Reid Executive Director, Institute for Applied Computational Science Harvard School of Engineering and Applied Sciences Pierce Hall, 29 Oxford Street Cambridge, MA 02138 http://iacs.seas.harvard.edu/people rreid(a)seas.harvard.edu | 617-384-9091 _______________________________________________ Iacs-events mailing list Iacs-events(a)seas.harvard.edu https://lists.seas.harvard.edu/mailman/listinfo/iacs-events

11 years, 2 months

[Aspuru-Guzik group list] [qip] (non-quantum) talk by David Rosenbaum tomorrow

by aram harrow

Dear quanta, David Rosenbaum will be speaking tomorrow at noon in the math department (specifically the pure math grad student seminar) about algorithms for group isomorphism. The talk is 99% classical, but nevertheless may be of interest for quantum people because of the overlap between computational group theory and quantum computing. It may also be of interest to people who like pizza, because there will be pizza there. Location: 4-153 Title: Faster Algorithms for Group Isomorphism Abstract: In the group isomorphism problem, we are given two finite groups G and H specified by their multiplication tables and must decide if they are isomorphic. The n^(log n)$ barrier for group isomorphism has withstood all attacks --- even for the special cases of p-groups and solvable groups --- ever since the n^(log n + O(1)) generator-enumeration algorithm. In this work, we present the first significant improvement over n^(log n) by formulating group isomorphism as a collision problem. Using a new technique called bidirectional collision detection, we show an n^((1 / 2) log n + O(1)) time algorithm for testing isomorphism of general groups. We also show a deterministic n^((1 / 4) log n + O(1)) Turing reduction from group isomorphism to composition-series isomorphism. By combining our reduction with an n^(O(p / log p)) algorithm for p-group composition-series isomorphism, we obtain an n^((1 / 4) log n + O(1)) algorithm for p-group isomorphism. We then generalize our techniques from p-groups using Sylow bases to derive an n^((1 / 4) log n + O(log n / log log n)) algorithm for solvable-group isomorphism. Note: This work is based partially on David's paper 1205.0642, and partially on some new unpublished work. _______________________________________________ qip mailing list qip(a)mit.edu http://mailman.mit.edu/mailman/listinfo/qip

11 years, 2 months

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

aspuru-list March 2013