(Courant Institute, NYU, USA), Universality is Ubiquitous.|
Scott Aaronson, (Massachusetts Institute of Technology, USA), Turing Year Lecture.
Kirk Pruhs, (University of Pittsburgh, USA), Green Computing Algorithmics: Managing Power Heterogeneity.
Marcos Kiwi, (Universidad de Chile, Chile), Combinatorial and Algorithmic Problems Involving (Semi-)Random Sequences.
|[Top] [Home] [LATIN 2012]|
(Massachusetts Institute of Technology, USA), Sparse Recovery Using Sparse Random Matrices.|
Cristopher Moore, (University of New Mexico and Santa Fe Institute, USA), Continuous and Discrete Methods in Computer Science.
Sergio Rajsbaum, (Universidad Nacional Autónoma de México, Mexico), Iterated Shared Memory Models.
Leslie Valiant, (Harvard University, USA), Some Observations on Holographic Algorithms.
Ricardo Baeza-Yates, John Brzozowski, Volker Diekert, and Jacques Sakarovitch, (Yahoo Research (Spain), University of Waterloo (Canada), Universität Stuttgart (Germany), and Ecole Nationale Supérieure des Télécommunications (France)), Vignettes on the work of Imre Simon.
|[Top] [Home] [LATIN 2010]|
(Unicamp, Brazil), Pfaffian Bipartite Graphs: The Elusive Heawood Graph.|
Moni Naor, (Weizmann Institute, Israel), Games, Exchanging Information and Extracting Randomness.
Wojciech Szpankowski, (Purdue University, USA), Tries.
Eva Tardos, (Cornell U., USA), Games in Networks.
Robert Tarjan, (Princeton U., USA), Graph Algorithms.
|[Top] [Home] [LATIN 2008]|
(Universidad de Chile & Universitat Pompeu Fabra), Algorithmic Challenges in Web Search Engine.|
In this paper we present the main algorithmic challenges that large Web search engines face today. These challenges are present in all the modules of a Web retrieval system, ranging from the gathering of the data to be indexed (crawling) to the selection and ordering of the answers to a query (searching and ranking). Most of the challenges are ultimately related to the quality of the answer or the efficiency in obtaining it, although some are relevant even to the existence of search engines: context based advertising.Anne Condon , (RNA molecules: glimpses through an algorithmic lens), U. British Columbia.
Dubbed the ``architects of eukaryotic complexity'', RNA molecules are increasingly in the spotlight, in recognition of the important catalytic and regulatory roles they play in our cells and their promise in therapeutics. Our goal is to describe the ways in which algorithms can help shape our understanding of RNA structure and function.Ferran Hurtado, (Universitat Politècnica de Catalunya), Squares.
In this talk we present several results and open problems having squares, the basic geometric entity, as a common thread. These results have been gathered from various papers; coauthors and precise references are given in the descriptions that follow.R. Ravi, (Matching Based Augmentations for Approximating Connectivity Problems), Carnegie Mellon University.
We describe a very simple idea for designing approximation algorithms for connectivity problems: For a spanning tree problem, the idea is to start with the empty set of edges, and add matching paths between pairs of components in the current graph that have desirable properties in terms of the objective function of the spanning tree problem being solved. Such matching augment the solution by reducing the number of connected components to roughly half their original number, resulting in a logarithmic number of such matching iterations. A logarithmic performance ratio results for the problem by appropriately bounding the contribution of each matching to the objective function by that of an optimal solution.Madhu Sudan, (Modelling Errors and Recovery for Communication), MIT.
The theory of error-correction has had two divergent schools of thought, going back to the works of Shannon and Hamming. In the Shannon school, error is presumed to have been effected probabilistically. In the Hamming school, the error is modeled as effected by an all-powerful adversary. The two schools lead to drastically different limits. In the Shannon model, a binary channel with error-rate close to, but less than, 50\% is useable for effective communication. In the Hamming model, a binary channel with an error-rate of more than 25\% prohibits unique recovery of the message.Sergio Verdú, (Lossless Data Compression via Error Correction), Princeton.
This plenary talk gives an overview of recent joint work with G. Caire and S. Shamai on the use of linear error correcting codes for lossless data compression, joint source/channel coding and interactive data exchange.Avi Wigderson, (The power and weakness of randomness in computation), IAS.
Humanity has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. We describe two main aspects of this research on randomness, demonstrating its power and weakness respectively.
|[Top] [Home] [LATIN 2006]|
(Microsoft Research), Fighting Spam: The Science.|
Mike Paterson, (U. of Warwick), Analysis of Scheduling Algorithms for Proportionate Fairness.
We consider a multiprocessor operating system in which each current job is guaranteed a given proportion over time of the total processor capacity. A scheduling algorithm allocates units of processor time to appropriate jobs at each time step. We measure the goodness of such a scheduler by the maximum amount by which the cumulative processor time for any job ever falls below the ``fair'' proportion guaranteed in the long term.Yoshiharu Kohayakawa, (U. Sao Paolo), Advances in the Regularity Method.
Jean-Eric Pin, (CNRS/U. Paris VII), The consequences of Imre Simon's work in the theory of automata, languages and semigroups.
In this lecture, I will show how influential has been the work of Imre in the theory of automata, languages and semigroups. I will mainly focus on two celebrated problems, the restricted star-height problem (solved) and the decidability of the dot-depth hierarchy (still open). These two problems lead to surprising developments and are currently the topic of very active research.Dexter Kozen, (Cornell U.), Kleene Algebra with Tests and the Static Analysis of Programs.
I will propose a general framework for the static analysis of programs based on Kleene algebra with tests (KAT). I will show how KAT can be used to statically verify compliance with safety policies specified by security automata. The method is sound and complete over relational interpretations. I will illustrate the method on an example involving the correctness of a device driver.
|[Top] [Home] [LATIN 2004]|
Jennifer T. Chayes,
(Microsoft Research), Phase Transitions in Computer Science.|
Phase transitions are familiar phenomena in physical systems. But they also occur in many probabilistic and combinatorial models, including random versions of some classic problems in theoretical computer science.Christos H. Papadimitriou, (U. California, Berkeley), The Internet, the Web, and Algorithms.
The Internet and the worldwide web, unlike all other computational artifacts, were not deliberately designed by a single entity, but emerged from the complex interactions of many. As a result, they must be approached very much the same way that cells, galaxies or markets are studied in other sciences: By speculative (and falsifiable) theories trying to explain how selfish algorithmic actions could have led to what we observe. I present several instances of recent work on this theme, with several collaboratorsJoel Spencer, (Courant Institute), Erdos Magic.
The Probabilistic Method is a lasting legacy of the late Paul Erdos. We give two examples - both problems first formulated by Erdos in the 1960s with new results in the last few years and both with substantial open questions. Further in both examples we take a Computer Science vantagepoint, creating a probabilistic algorithm to create the object (coloring, packing respectively) and showing that with positive probability the created object has the desired properties.Jorge Urrutia, (UNAM), Open Problems in Computational Geometry.
In this paper we present a collection of problems which have defied solution for some time. We hope that this paper will stimulate renewed interest in these problems, leading to solutions to at least some of them.Umesh V. Vazirani, (U. California, Berkeley), Quantum Algorithms.
Mihalis Yannakakis, (Avaya Laboratories), Testing and Checking of Finite State Systems.
Finite state machines have been used to model a wide variety of systems, including sequential circuits, communication protocols, and other types of reactive systems, i.e., systems that interact with their environment. In testing problems we are given a system, which we may test by providing inputs and observing the outputs produced.
|[Top] [Home] [LATIN 2002]|
(U. Toronto), On the Competitive Theory and Practice of Portfolio Selection.|
Philippe Flajolet, (INRIA), .
Joachim von zur Gathen, (U. Paderborn), Subresultants Revisited.
Yoshiharu Kohayakawa, (U. Sao Paulo), Algorithmic Aspects of Regularity.
Andrew Odlyzko, (AT&T Labs), Integer Factorization and Discrete Logarithms.
Prabhakar Raghavan, (IBM Almaden), Graph Structure of the Web: A Survey.
|[Top] [Home] [LATIN 2000]|
(Tel Aviv Univ.), Spectral Techniques in Graph Algorithms.|
Richard Beigel, (Lehigh Univ.), The Geometry of Browsing.
Gilles Brassard, (Univ. of Montréal), Quantum Cryptanalysis of Hash and Claw-Free Functions.
Herbert Edelsbrunner, (Univ. of Illinois, Urbana-Champaign), Shape Reconstruction with Delaunay Complex.
Juan A. Garay, (IBM, Yorktown Heights), Batch Verification with Applications to Cryptography and Checking.
|[Top] [Home] [LATIN 1998]|
Isaac Scherson, Load Balancing in Distributed Systems.
J.Ian Munro, Fast, Space Efficient Data Structures.
Alberto Apostolico, The String Statistics Problem.
Mike Waterman, Probability Distributions for Sequence Alignment Scores .
|[Top] [Home] [LATIN 1995]|
(CNRS), q-Regular Sequences and other Generalizations of q-Automatic Sequences.|
Manuel Blum, (U. California, Berkeley), Universal Statistical Tests.
Kosaburo Hashiguchi, (Toyohashi U. of Technology), The Double Reconstruction Conjectures about Colored Hypergraphs and Colored Directed Graphs.
Erich Kaltofen, (Rensselaer Polytechnic Institute), Polynomial Factorization 1987-1991.
Arjen K. Lenstra, (Bellcore), Massively Parallel Computing and Factoring.
Gene Myers, (U. of Arizona), Approxiamte Matching of Network Expressions with Spacers.
Jean-Eric Pin, (Bull), On Reversible Automata.
Vaughan Pratt, (Standford U.), Arithmetic + Logic + Geometry = Concurrency.
Daniel D. Sleator, (Carnegie Mellon U.), Data Structures and Terminating Petri Nets.
Michel Cosnard, (Ecole Normale Supérieure de Lyon), Complexity Issues in Neural Network Computations.
|[Top] [Home] [LATIN 1992]|