LATIN 2000: Theoretical Informatics

Random Structures and Algorithms.- Algorithmic Aspects of Regularity.- Small Maximal Matchings in Random Graphs.- Some Remarks on Sparsely Connected Isomorphism-Free Labeled Graphs.- Analysis of Edge Deletion Processes on Faulty Random Regular Graphs.- Equivalent Conditions for Regularity (Extended Abstract).- Algorithms I.- Cube Packing.- Approximation Algorithms for Flexible Job Shop Problems.- Emerging Behavior as Binary Search Trees Are Symmetrically Updated.- The LCA Problem Revisited.- Combinatorial Designs.- Optimal and Pessimal Orderings of Steiner Triple Systems in Disk Arrays.- Rank Inequalities for Packing Designs and Sparse Triple Systems.- The Anti-Oberwolfach Solution: Pancyclic 2-Factorizations of Complete Graphs.- Web Graph, Graph Theory I.- Graph Structure of the Web: A Survey.- Polynomial Time Recognition of Clique-Width ? 3 Graphs.- On Dart-Free Perfectly Contractile Graphs Extended Abstract.- Graph Theory II.- Edge Colouring Reduced Indifference Graphs.- Two Conjectures on the Chromatic Polynomial.- Finding Skew Partitions Efficiently.- Competitive Analysis, Complexity.- On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract).- Almost k-Wise Independence and Hard Boolean Functions.- Improved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function.- Algorithms II.- Multi-parameter Minimum Spanning Trees.- Linear Time Recognition of Optimal L-Restricted Prefix Codes.- Uniform Multi-hop All-to-All Optical Routings in Rings.- A Fully Dynamic Algorithm for Distributed Shortest Paths.- Computational Number Theory, Cryptography.- Integer Factorization and Discrete Logarithms.- Communication Complexity and Fourier Coefficients of the Diffie-Hellman Key.- Quintic Reciprocity and Primality Test for Numbers of the Form .- Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography.- Analysis of Algorithms I.- Average-Case Analysis of Rectangle Packings.- Heights in Generalized Tries and PATRICIA Tries.- On the Complexity of Routing Permutations on Trees by Arc-Disjoint Paths Extended Abstract.- Algebraic Algorithms.- Subresultants Revisited.- A Unifying Framework for the Analysis of a Class of Euclidean Algorithms.- Worst-Case Complexity of the Optimal LLL Algorithm.- Computability.- Iteration Algebras Are Not Finitely Axiomatizable.- Undecidable Problems in Unreliable Computations.- Automata, Formal Languages.- Equations in Free Semigroups with Anti-involution and Their Relation to Equations in Free Groups.- Squaring Transducers: An Efficient Procedure for Deciding Functionality and Sequentiality of Transducers.- Unambiguous Büchi Automata.- Linear Time Language Recognition on Cellular Automata with Restricted Communication.- Logic, Programming Theory.- From Semantics to Spatial Distribution.- On the Expressivity and Complexity of Quantitative Branching-Time Temporal Logics.- A Theory of Operational Equivalence for Interaction Nets.- Analysis of Algorithms II.- Run Statistics for Geometrically Distributed Random Variables.- Generalized Covariances of Multi-dimensional Brownian Excursion Local Times.- Combinatorics of Geometrically Distributed Random Variables: Length of Ascending Runs.