Omid Etesami

I am an associate professor at the Institute for Research in Fundamental Sciences (IPM), in the Combinatorics and Computing group.

I studied as an undergraduate at Sharif University of Technology, got PhD in Computer Science at University of California at Berkeley at the CS Theory group under the supervision of Luca Trevisan, and then was a post-doc at EPFL under the supervision of Amin Shokrollahi.

I am interested in the theory of computation and its interplay with randomness, probability theory, and information theory.

Publications

Computational Concentration of Measure: Optimal Bounds, Reductions, and More, with Mohammad Mahmoody, Saeed Mahloujifar, SODA 2020

On the [1,k]-domination Number of Graphs, with Pouyeh Sharifani, Narges Ghareghani, Michel Habib, Mohammadreza Houshmand, Reza Naserasr, Theoretical Computer Science 2019

Convex Ramsey Matrices and Non-amenability of Automorphism Groups of Generic Structures, with Zaniar Ghadernezhad, Manuscript

Complete Classification of Generalized Santha-Vazirani Sources, with Salman Beigi, Andrej Bogdanov, Siyao Guo, RANDOM 2018

Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources, with Salman Beigi, Amin Gohari, SIAM Journal on Computing 2017

The Value of Help Bits in Randomized and Average-case Complexity, with Salman Beigi, Amin Gohari, Computational Complexity 2016

Maximal Rank Correlation, with Amin Gohari, IEEE Communication Letters 2016

Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources with Salman Beigi, Amin Gohari, International Colloquium on Automata, Languages, and Programming (ICALP) 2015

The Value of Information-Theoretic Content of Help Bits for Computation, with Salman Beigi, Amin Gohari, Workshop on Communication and Information Theory (IWCIT) 2015

On the One-way Function Candidate Proposed by Goldreich with James Cook, Rachel Miller, Luca Trevisan, ACM Transactions on Computation Theory 2014 (selected as a Best of 2014 article by ACM Computing Reviews)  

(The above journal version extends the results and corrects a bug in the conference version and the part of my thesis concerning it.)

Irregular Product Codes with Masoud Alipour, Ghid Maatouk, Amin Shokrollahi, Information Theory Workshop (ITW) 2012

Pseudorandomness against Depth-2 Circuits and Analysis of Goldreich’s Candidate One-Way Function, PhD thesis, University of California at Berkeley 2010

Improved Pseudorandom Generators for Depth-2 Circuits with Anindya De, Luca Trevisan, Madhur Tulsiani, International Workshop on Randomization and Computation (RANDOM) 2010

Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms, with James Cook, Rachel Miller, Luca Trevisan, Theory of Cryptography Conference (TCC) 2009

Mafia: A Theoretical Study of Players and Coalition in a Partial Information Environment with Mark Braverman, Elchanan Mossel, Annals of Applied Probability 2008

Dynamics of Bid Optimization in Online Advertisement Auctions with Christian Borgs, Jennifer Chayes, Nicole Immorlica, Kamal Jain, Mohammad Mahdian, International World Wide Web (WWW) Conference 2007

On Rainbow Cycles in Edge Colored Complete Graphs with Saeed Akbari, Hamid Mahini, Mohammad Mahmoody, Australian Journal of Combinatorics 2007

Raptor Codes on Binary Memoryless Symmetric Channels with Amin Shokrollahi, IEEE Transactions on Information Theory 2006

Latin Transversal in Long Rectangular Arrays with Saeed Akbari, Hamid Mahini, Ali Sharifi, Discrete Mathematics 2006

Raptor Codes on Symmetric Channels, with Mehdi Molkaraie, Amin Shokrollahi, International Symposium on Information Theory (ISIT) 2004

Relations between Belief Propagation on Erasure and Symmetric Channels, International Symposium on Information Theory (ISIT) 2004

Lecture Notes

These are a short set of lecture notes concerning Discrete Probability for Analysis of Algorithms in Persian:

Preface                       

Lecture 1         Lecture 2         Lecture 3         Lecture 4         Lecture 5         Lecture 6