Igor Carboni
Oliveira Email: igorcarb [at] gmail [dot] com School of Mathematics Faculty of Mathematics and Physics Charles University in Prague Sokolovska 83, 186 75 Praha 8. 

About Me I'm currently a postdoctoral researcher at the School of Mathematics at Charles University in Prague, hosted by Jan Krajicek. I received my Ph.D. from Columbia University in 2015, where I was advised by Tal Malkin and Rocco Servedio. Previously, I was a student at University of Campinas, Brazil (20052010). Research Interests Computational Complexity, Combinatorics, Algorithms, and Mathematical Logic, with an emphasis on interactions between these fields. Publications & Preprints On monotone circuits with local oracles and clique lower bounds (with Jan Krajicek). Preprint, 2017. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness (with Rahul Santhanam). Computational Complexity Conference [CCC'17]. Pseudodeterministic constructions in subexponential time (with Rahul Santhanam). Symposium on Theory of Computing [STOC'17]. Addition is exponentially harder than counting for shallow monotone circuits (with Xi Chen and Rocco Servedio). Symposium on Theory of Computing [STOC'17]. Unprovability of circuit upper bounds in Cook's theory PV (with Jan Krajicek). [slides] Logical Methods in Computer Science, 2017. ErdosKoRado for random hypergraphs: asymptotics and stability (with Marcelo Gauy and Hiep Han). Combinatorics, Probability and Computing, 2017. Nearoptimal smalldepth lower bounds for smalldistance connectivity (with Xi Chen, Rocco Servedio, and LiYang Tan). Symposium on Theory of Computing [STOC'16]. Unconditional Lower Bounds in Complexity Theory. [Ph.D. Thesis]  Columbia University, 2015. Learning circuits with few negations (with Eric Blais, Clement Canonne, Rocco Servedio, and LiYang Tan). International Workshop on Randomization and Computation [RANDOM'15]. Majority is incompressible by AC0[p] circuits (with Rahul Santhanam). Computational Complexity Conference [CCC'15]. The power of negations in cryptography (with Siyao Guo, Tal Malkin, and Alon Rosen). Theory of Cryptography Conference [TCC'15]. An algebraic formulation of the graph reconstruction conjecture (with Bhalchandra Thatte). Journal of Graph Theory, 2015. A simple algorithmic explanation for the concentration of measure phenomenon. Manuscript (not intended for publication), 2014. Algorithms versus Circuit lower bounds (Survey). Electronic Colloquium on Computational Complexity (ECCC), 2013. Constructing hard functions from learning algorithms (with Adam Klivans and Pravesh Kothari). Conference on Computational Complexity [CCC'13]. Computational Complexity and the P versus NP Problem (in Portuguese). [Master's Thesis]  University of Campinas, 2010. 

Seminars & Research Groups in Prague I have coorganized the following courses and seminars: Logic & Complexity Student Seminar (Winter 2016) Logic & Complexity Student Seminar (Summer 2016) Logic & Complexity Student Seminar (Winter 2015) Additional seminars of interest listed below. * Logic Seminar  IM. * Seminar on Limits of Efficient Computation  IUUK. * Graduate Student Seminar on Combinatorics  KAM. * Noon Lectures, Combinatorics  KAM. * Logic & Complexity Student Seminar  MFF. * Seminar on Computational Complexity  IM. Extremal Graph Theory Group Kafka Seminar [KAM  Charles Univ.] [IUUK  Charles Univ.] [IM  Academy of Sciences] [ITI  Charles Univ.] [DIMATIA] [Logic  Charles Univ.] [MFF  Charles Univ.] [KTIML  Charles Univ.] [TCS  Academy of Sciences] [Last update: April 21, 2017] 