FOCS 2014
55th Annual IEEE Symposium on
Foundations of Computer Science

October 18–21, 2014
Radisson Blu Warwick Hotel
Philadelphia, PA, USA


Obfuscation: How to Encrypt a Functionality - Saturday, October 18, 2014
Speakers: Dan Boneh, Allison Bishop Lewko, and Amit Sahai
Description: The goal of general-purpose program obfuscation is to make an arbitrary computer program unintelligible while preserving its functionality. Obfuscation allows us to achieve a powerful capability: software that can keep a secret. This tutorial will cover recent advances in obfuscation research, that have allowed for the first time constructions of general-purpose obfuscation mechanisms with security based on plausible intractability assumptions.


Sparse Fourier Transform: Theory and Applications - Saturday, October 18, 2014
Organizers: Anna Gilbert, Piotr Indyk, and Dina Katabi
Description: The workshop is dedicated to the theory and applications of efficient algorithms for finding large Fourier coefficients. This question is of longstanding interest in TCS. Recently, the topic has attracted considerable attention in applied computer science, electrical engineering and applied mathematics. The goal of the workshop is to facilitate interactions between these areas and disseminate recent developments and ideas related to this topic.

Higher-order Fourier Analysis - Saturday, October 18, 2014
Organizers: Arnab Bhattacharyya and Shachar Lovett
Description: Higher-order Fourier analysis is an extension of classic Fourier analysis, where one extends the notion of characters to low-degree polynomial phases.It originated in number theory in the seminal work of Gowers on Szemeredi's theorem, and has been extensively developed since. It also has several applications in theoretical computer science, which are the focus of this workshop. These include: explicit constructions of functions having low correlation with polynomials, learning structural decompositions of low degree polynomials, list-decoding of Reed-Muller codes, and a unified framework for testing of algebraic properties, which extends the framework of graph and hypergraph property testing.

Document last modified on September 30, 2014.