TCSTURKEY

Analysis of Boolean Functions for Algorithms and Complexity

Coordinatore	BOGAZICI UNIVERSITESI    more  Organization address address: BEBEK city: ISTANBUL postcode: 34342 contact info Titolo: Ms. Nome: Dilek Cognome: Akgun Email: send email Telefono: +90 212 359 4801 Fax: +90 212 359 4803
Nazionalità Coordinatore	Turkey [TR]
Totale costo	115˙773 €
EC contributo	115˙773 €
Programma	FP7-PEOPLE Specific programme "People" implementing the Seventh Framework Programme of the European Community for research, technological development and demonstration activities (2007 to 2013)
Code Call	FP7-PEOPLE-2013-IIF
Funding Scheme	MC-IIF
Anno di inizio	2014
Periodo (anno-mese-giorno)	2014-03-31   -   2015-03-30

 Partecipanti

#	participant	country	role	EC contrib. [€]
1	BOGAZICI UNIVERSITESI  Organization address address: BEBEK city: ISTANBUL postcode: 34342 contact info Titolo: Ms. Nome: Dilek Cognome: Akgun Email: send email Telefono: +90 212 359 4801 Fax: +90 212 359 4803	TR (ISTANBUL)	coordinator	115˙773.60

Mappa

 Word cloud

Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.

 Obiettivo del progetto (Objective)

'The researcher, Dr. Ryan O'Donnell, received his Ph.D. from the Mathematics Department of the Massachusetts Institute of Technology (MIT) and is now an Associate Professor in the Computer Science Department of Carnegie Mellon University (CMU). Both departments are ranked #1 by the U.S. News & World Report. The host institution will be BoÄŸaziçi University in Istanbul, Turkey.

Broadly speaking, Dr. O'Donnell's area of research expertise is Theoretical Computer Science ('TCS'), in the sense of Algorithms and Computational Complexity Theory. More precisely, Dr. O'Donnell's work takes an interdisciplinary approach, developing new tools and ideas in mathematics in order to understand the design, analysis, and limitations of basic computational algorithms. Dr. O'Donnell's mathematical research is primarily in the newly emerging area of Analysis of Boolean Functions (also known as Discrete Fourier Analysis), a subfield of of probability theory and real analysis. The overarching goal of the research proposed herein is to innovate new discrete-analytic tools for application in Theoretical Computer Science.

Key research objectives:

AAC: Prove the Aaronson-Ambainis Conjecture regarding influences of low-degree bounded polynomials. This conjecture has important consequences for Quantum Computation.

FEI: Prove the Fourier Entropy-Influence Conjecture of Friedgut and Kalai. This conjecture has important consequences for Computational Learning Theory.

SOS: Investigate the power and limitations of the Sum-of-Squares Method in combinatorial optimization. This is a very recently developed, extremely powerful optimization technique.

NPH: Prove new NP-hardness-of-approximation results for the most basic CSPs like Max-Cut and 2Sat. This is plausible in light of recently developed Boolean analysis techniques due to Dr. O'Donnell and S.O. Chan.

SSE: Explore the Small-Set Expansion Conjecture. The goal is to find new families of hard instances or to show that the SOS method succeeds.'