======================================================================= Para o documento 1), item resumo do programa e importância científica ou tecnológica da reunião: O Workshop on Combinatorics, Algorithms, and Applications é um evento organizado no âmbito do projeto ProNEx (Programa de Apoio a Núcleos de Excelência) "Complexidade de Estruturas Discretas," financiado pelo MCT/CNPq (Proc. CNPq 664107/1997-4), e sob a coordenação de Y. Kohayakawa. Informações sobre este projeto (seus membros, relatórios, publicações) podem ser encontradas em http://www.ime.usp.br/~yoshi/pronex/ O evento será realizado no período de 1 a 5 de setembro de 2003, em Ubatuba, e contará com a participação de grande parte da comunidade brasileira da área de Teoria da Computação. %%%%%%%% Falar aqui sobre as comissoes ? %%%%%%%%%%%%%%% Foram convidados cerca de 15 pesquisadores internacionais, mais da metade deles expoentes da área de Teoria da Computação, para contribuirem cada um com uma ou duas palestras em quatro grandes áreas: Biologia computacional (M-F. Sagot, E. Ukkonen) Combinatória probabilística (D. Duffus, A. Frieze, P. Raghavan, B. Reed) Enumeração/análise de algoritmos (M. Kiwi, B. Richmond, A. Viola) Otimização combinatória (A. Frieze, P. Raghavan, B. Reed) Teoria dos grafos (L.H. Kauffman, B. Reed, J. Spinrad, C. Thomassen) A programação diária do evento basicamente consistirá de 3 plenárias de duração de uma hora cada, e três sessões paralelas com três palestras cada. Tais palestras, mais específicas nas diversas áreas, terão uma duração prevista de 30 minutos cada. Vários desses pesquisadores convidados colaboram ou colaboraram com membros do projeto e membros da comunidade brasileira em Teoria da Computação. A presença desses convidados no evento criará condições e oportunidade para que tais colaborações se intensifiquem e que novas colaborações sejam iniciadas com outros membros da comunidade brasileira. A diversidade das áreas contempladas pelo evento reflete a diversidade das áreas em que trabalham os membros do projeto e isso, bem como o alto nível dos palestrantes convidados, torna o evento de interesse para toda a comunidade brasileira de Teoria da Computação. Informações sobre o evento poderão ser encontrados em http://www.ime.usp.br/~yoshi/pronex/Workshop/ ======================================================================= Para o documento 3): O evento segue os moldes de uma escola em Teoria da Computação, contando com a presença de vários pesquisadores de altíssimo nível, que contribuirão cada um com uma palestra plenária, para uma audiência geral de Teoria da Computação, e uma palestra específica, mais voltada às pessoas que trabalham na área em questão. Outros pesquisadores colaborarão apenas com uma plenária ou palestra. A comissão organizadora, responsável por todos os arranjos locais e pela implementação do evento, é composta das seguintes pessoas: Carlos Eduardo Ferreira (DCC-IME-USP) Cristina Gomes Fernandes (DCC-IME-USP) Flávio Keidi Miyazawa (IC-UNICAMP) José Coelho de Pina Jr (DCC-IME-USP) Yoshiharu Kohayakawa (DCC-IME-USP) Yoshiko Wakabayashi (DCC-IME-USP) A comissão de programa, responsável pelo formato do evento e pela escolha dos palestrantes convidados, é composta das seguintes pessoas: Carlos Eduardo Ferreira (DCC-IME-USP) Celina M. H. Figueiredo (DCC-IM-UFRJ) Cláudio Leonardo Lucchesi (IC-UNICAMP) Marcelo Henriques de Carvalho (DCC-UFMS) Sóstenes Luiz Soares Lins (DMAT-UFPE) Yoshiharu Kohayakawa (DCC-IME-USP) Yoshiko Wakabayashi (DCC-IME-USP) Para mais informações, consulte a página do evento: http://www.ime.usp.br/~yoshi/pronex/Workshop/ O evento contempla diversas áreas em Teoria da Computação e conta com a presença de palestrantes de alto nível, o que o torna de interesse à toda a comunidade brasileira de Teoria da Computação. Vários desses palestrantes estrangeiros convidados colaboram ou colaboraram com membros da comunidade brasileira em Teoria da Computação. A presença desses convidados no evento criará condições e oportunidade para que tais colaborações se intensifiquem e que novas colaborações sejam iniciadas com outros membros da comunidade brasileira. A lista de palestrantes convidados inclui os seguintes nomes: Gérard P. Cornuéjols Carnegie Mellon University Dwight Duffus Emory University Alan Frieze Carnegie Mellon University Louis H. Kauffman University of Illinois at Chicago Marcos Kiwi Universidad de Chile Prabhakar Raghavan Verity and Stanford University Bruce Reed McGill University Bruce Richmond University of Waterloo Marie-France Sagot INRIA, Rhône-Alpes Jeremy Spinrad Vanderbilt University Carsten Thomassen Technical University of Denmark Esko Ukkonen University of Helsinki Alfredo Viola Universidad de la República Outros pesquisadores do exterior demonstraram interesse em participar, sendo muito provável que outros nomes se juntarão a esses. Apresentamos a seguir um breve resumo do perfil desses pesquisadores. As listas de suas publicações seguem em anexo. ----------------------------------------------------------- Alan Frieze Professor of Mathematics, Carnegie Mellon University Ph.D., London University http://www.math.cmu.edu/~af1p/ Em 1991 recebeu o Fulkerson Prize em Matemática Discreta - prêmio concedido pela American Mathematical Society e o Mathematical Programming Society. Prêmio recebido juntamente com Martin Dyer e Ravi Kannan peloa artigo "A random polynomial time algorithm for approximating the volume of convex bodies", Journal of the Association for Computing Machinery 38 (1991) 1-17. Em 1997 foi eleito Guggenheim Fellow. Áreas de interesse: combinatória, otimização discreta e teoria da computação. Presentemente, tem focado a sua pesquisa nos aspectos probabilísticos dessas áreas. Em particular, no estudo das propriedades assintóticas de grafos aleatórios, análise de caso médio de algoritmos, e algoritmos aleatórios. Seus trabalhos recentes incluem conntagens aproximadas e cálculo de volume via passeios aleatórios; encontrar caminhos disjuntos em grafos expansores, e investigação da teoria de anti-Ramsey e estabilidade de algoritmos de roteamento. O MathSciNet (Mathematical Reviews on the Web) registra 201 publicações deste pesquisador. ----------------------------------------------------------- Louis H. Kauffman Professor, University of Illinois at Chicago Ph.D. Princeton University, 1972. Detentor de vários prêmios e honrarias. Lester R. Ford Award of the Mathematical Association of America (1978) in expository writing pelo artigo Immersion and Mod-2 Quadrataic Forms American Mathematical Monthly 84 (1977) 168-185; NSF Fellow, Woodrow Wilson Honorary Fellow, e outros. Managing Editor do Journal of Knot Theory and its Ramifications (World Scientific Publishers), desde 1991; editor da série de livros sobre Knots and Everything (dese 1991), editor associado do Annals of Combinatorics; membro do corpo editorial do Cybernetics and Human Knowing (desde 1995). Autor de 10 livros em teoria dos nós; e preparando 5 outros. Tem cerca de 150 publicações listadas no MathSciNet. ---------------------------------------------------- Bruce Reed Professor, School of Computer Science, McGill University Até recentemente, Université Paris VI, INRIA, França. Ph.D. McGill University http://cgm.cs.mcgill.ca/~breed/ Áreas de interesse: combinatória, teoria dos grafos e otimização discreta, com ênfase nos aspectos algoritmicos e probabilísticos de problemas dessas áreas. Tem cerca de 100 publicações listadas no MathSciNet. Tem cerca de 8 artigos em co-autoria com pesquisadores brasileiros da área de combinatória. Trata-se de um pesquisador que tem colaborado intensamente com a comunidade brasileira na área (pesquisadores do Rio, de São Paulo, do Ceará), tendo inclusive organizado em 2001 o CIMPA School on..... em Fortaleza, com apoio do CIMPA (do governo francês). ------------------------------------------------------------- Bruce Richmond Professor, Dept. of Combinatorics & Optimization, Faculty of Mathematics, University of Waterloo http://www.math.uwaterloo.ca/CandO_Dept/richmond.shtml Áreas de interesse: enumeração assintótica e teoria dos números. Tem mais de 80 publicações listadas no MathSciNet. -------------------------------------------------------------- Prabhakar Raghavan Professor, Department of Computer Science, Stanford University e Verity Ph.D. UC Berkeley. http://theory.stanford.edu/people/raghavan/ Membro do corpo editorial dos periódicos: ACM Transactions on Internet Technology, Journal of the ACM, SIAM Journal on Computing, Web Intelligence and Agent Systems, Internet Mathematics. Autor do livro "Randomized Algorithms", com R. Motwani. Cambridge University Press. Áreas de interesse: otimização combinatória e algoritmos aleatórios; recuperação de informação e mineracão de textos; análise de estrutura na Web. Tem cerca de 70 publicações listadas no MathSciNet. ---------------------------------------------------------------- Esko Ukkonen Academy Professor, Ph.D. Department of Computer Science, University of Helsinki Membro do Graduate School in Computational Biology, Bioinformatics, and Biometry http://www.cs.helsinki.fi/u/ukkonen/ Áreas de interesse: Desenvolvimento e análise de algoritmos, aprendizagem de máquina e biologia computacional. Tem cerca de 50 publicações listadas no MathSciNet. A vinda deste pesquisador certamente atrairá o interesse dos pesquisadores da comunidade brasileira que atua na área de Bioinformática. Além desse pesquisador, convidamos a pesquisadora Marie-France Sagot (INRIA), que também atua na área de Bioinformática e está no momento em grande evidência, participando dos comitês de vários eventos na área e ministrando cursos em vários países. Pretendemos organizar no evento uma sessão especial na área de Bioinformática. ---------------------------------------------------------------- Carsten Thomassen Professor of Mathematics, Technical University of Denmark. http://www.mat.dtu.dk/people/C.Thomassen/ Membro do Royal Danish Academy of Sciences and Letters; Editor-in-Chief do Journal of Graph Theory; membro do corpo editorial dos periódicos: Combinatorica, The Journal of Combinatorial Theory (Ser B), Discrete Mathematics, e European Journal of Combinatorics. Recebeu em 1993 o Lester R. Ford Award (concedido pela Mathematical Association of America), além de várias outras honrarias. Áreas de interesse: Matemática discreta e Teoria dos Grafos. Tem mais de 160 publicações listadas no MathSciNet. ------------------------------------------------------------------- Gérard P. Cornuéjols Professor of Operations Research, Dept. Mathematical Sciences, Carnegie Mellon University Ph.D., Cornell University Áreas de interesse: otimização combinatória e teoria dos grafos, com ênfase nos aspectos algorítmicos. My current focus is on the study of perfect graphs, balanced matrices and the max-flow min-cut property. Another line of my research deals with NP-hard combinatorial optimization problems through the study of relaxations. Using polyhedral combinatorics, contributions are made to the theory of the set covering, location, vehicle routing, and traveling salesman problems. Tem mais de 70 publicações listadas no MathSciNet ------ Listamos a seguir algumas publicacoes dos convidados em co-autoria com pesquisadores brasileiros da área de combinatória. - Kauffman, Louis H.; Lins, Sóstenes L. Temperley-Lieb recoupling theory and invariants of $3$-manifolds. Annals of Mathematics Studies, 134. Princeton University Press, Princeton, NJ, 1994. x+296 pp. - Kauffman, Louis; Lins, Sóstenes Decomposition of the vertex group of $3$-manifolds. Discrete Math. 103 (1992), no. 1, 49--55. - Kauffman, Louis H.; Lins, Sóstenes Computing Turaev-Viro invariants for $3$-manifolds. Manuscripta Math. 72 (1991), no. 1, 81--94. - Everett, Hazel; de Figueiredo, Celina M. H.; Linhares Sales, Cláudia; Maffray, Frédéric; Porto, Oscar; Reed, Bruce A. Even pairs. Perfect graphs, 67--92, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, Chichester, 2001. - Sales, Cláudia Linhares; Maffray, Frédéric; Reed, Bruce Recognizing planar strict quasi-parity graphs. Graphs Combin. 17 (2001), no. 4, 745--757. - de Figueiredo, Celina M. H.; Klein, Sulamita; Kohayakawa, Yoshiharu; Reed, Bruce A. Finding skew partitions efficiently. J. Algorithms 37 (2000), no. 2, 505--521. - Calinescu, Gruia; Fernandes, Cristina G.; Reed, Bruce Multicuts in unweighted graphs with bounded degree and bounded tree-width. Integer programming and combinatorial optimization (Houston, TX, 1998), 137--152, Lecture Notes in Comput. Sci., 1412, Springer, Berlin, 1998. Aceito no J. Algorithms. - Everett, Hazel; Klein, Sulamita; Reed, Bruce An optimal algorithm for finding clique-cross partitions. Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1998). Congr. Numer. 135 (1998), 171--177. - Cláudia Linhares; Maffray, Frédéric; Reed, Bruce On planar perfectly contractile graphs. Graphs Combin. 13 (1997), no. 2, 167--187. - Everett, Hazel; de Figueiredo, Celina M. H.; Linhares-Sales, Cláudia; Maffray, Frédéric; Porto, Oscar; Reed, Bruce A. Path parity and perfection. Graphs and combinatorics (Marseille, 1995). Discrete Math. 165/166 (1997), 233--252. - Everett, Hazel; Klein, Sulamita; Reed, Bruce An algorithm for finding homogeneous pairs. Discrete Appl. Math. 72 (1997), no. 3, 209--218. - Y. Kohayakawa, F.K. Miyazawa, P. Raghavan and Y. Wakabayashi. Multidimensional Cube Packing. GRACO'2001: Brazilian Symposium on Graphs and Combinatorics. Electronic Notes of Discrete Mathematics (Elsevier Science). - Y. Kohayakawa, F.K. Miyazawa, P. Raghavan, and Y. Wakabayashi, Multidimensional Cube Packing, 2002. Submetido. - M.-F. Sagot and Y. Wakabayashi, Pattern Inference under many Guises, chapter of Recent Advances in Algorithms and Combinatorics, 368 pages - ISBN: 0387954341, published by Springer (http://www.springer.de/search97cgi/s97_cgi) - E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, Some Approximation Results for the Maximum Agreement Forest Problem. Proceedings of APPROX-RANDOM 2001 (Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques), M. Goemans et al (Eds.), Lecture Notes in Computer Science, vol. 2129, Springer (2001), 159-169. - E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, The Maximum Agreement Forest Problem: Approximation algorithms and computational experiments. Submetido. - M. Grötschel, C. Thomassen and Y. Wakabayashi, Hypotraceable Digraphs, Journal of Graph Theory 4 (1980) 377-381.