Eastern Great Lakes Theory Workshop Talk

Symmetric Functions Capture General Functions

Ken Regan, University at Buffalo

Saturday, September 11, 11:30am-12:30pm

ABSTRACT

We show that for every n-variable function f there are symmetric functions f' of nearly equivalent complexity, on all or nearly all inputs. This seems surprising because symmetric functions are more restricted and have rich algebraic structure. One construction of f' is algebraically natural and is definable over nay ring, but requires large field extensions and hence high deterministic running time for a handful of inputs, though a randomized algorithm cuts the time overhead to quasi-polynomial for all inputs. A second construction gives nearly linear time equivalence and uses only a small finite-field extension, but is algebraically somewhat artificial and gives higher degree. We also have results over infinite fields. Open problems include finding a construction with the advantages of both the above, exploiting the structure of f' for lower bounds, and possibly making all this work for rings such as the integers modulo a composite number, around which the frontier of lower bounds on ACC currently revolves.

Joint work with Richard Lipton and Atri Rudra.

Speaker Bio

Kenneth W. Regan is an Associate Professor in the Department of Computer Science and Engineering, University at Buffalo (SUNY). He followed a B.A. in Mathematics at Princeton with a D.Phil. at Oxford University as a Marshall Scholar and then a Junior Fellow of Merton College, Oxford. After a postdoc at the Cornell Mathematical Sciences Institute hosted by the Computer Science Department, he joined UB's faculty in 1989. His research is on computational complexity theory, specializing on the logical status of the P versus NP problem, attacks on it via arithmetical complexity, and areas such as resource-bounded measure theory, parameterized complexity, and machine models. He holds the title of International Master from the World Chess Federation (FIDE), and recently has been involved in cases alleging cheating with computers at chess. His statistical model of decision-making in chess and other pursuits which underlies this service was presented at AAAI 2011. He is married with two children.

< Schedule < EaGL-IV homepage