Titlebook: LATIN 2004: Theoretical Informatics; 6th Latin American S Martín Farach-Colton Conference proceedings 2004 Springer-Verlag Berlin Heidelber

Pastry

An Improved Data Stream Summary: The Count-Min Sketch and Its Applicationsint, range, and inner product queries to be approximately answered very quickly; in addition, it can be applied to solve several important problems in data streams such as finding quantiles, frequent items, etc. The time and space bounds we show for using the CM sketch to solve these problems signif

Nausea

Rotation and Lighting Invariant Template Matchingappears rotated and brighter or darker than its occurrence. Furthermore, we consider approximate matching under several tolerance models. We obtain algorithms that are almost worst-case optimal. The complexities we obtain are very close to the best current results for the case where only rotations,

Agility

Computation of the Bisection Width for Random ,-Regular Graphs value of .. We provide the bounds for 5 ≤ . ≤ 12. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find bisections of .-regular graphs. We also give empirical values of the size of bisection found by the algorithm for some small values of . and

ANTI

Constrained Integer Partitionsence of their sums, is minimized. The integers are i.i.d. random variables chosen uniformly from the set {1,...,M}. We study how the typical behavior of the optimal partition depends on .,. and the bias ., the difference between the cardinalities of the two subsets in the partition. In particular, w

gerrymander

Embracing the Giant Componentph with a component as large as possible. This game is in the spirit of recent papers on . a giant component, but here we . it..We analyze this game in the offline and online setting, for arbitrary and random instances, which provides for interesting comparisons. For arbitrary instances, we find a l

Frequency

Sampling Grid Colorings with Fewer Colorssuch colorings has strong spatial mixing. Four and five are now the only remaining values of . for which it is not known whether there exists a rapidly mixing Markov chain for .-colorings of the square grid.

吞没

The Complexity of Finding Top-Toda-Equivalence-Class Memberss in a given length’s top Toda equivalence class (very informally put, a string from Σ. that the set’s P-selector function declares to be most likely to belong to the set) is FP. computable, and we show that each P-selective set contains a weakly-P.-rankable subset.

教唆

减弱不好

Bidimensional Parameters and Local Treewidthf the graph is bounded by some function of .. This fact is used as the main tool for the design of several fixed-parameter algorithms on minor-closed graph classes such as planar graphs, single-crossing-minor-free graphs, and graphs of bounded genus. In this paper we examine the question whether sim

moribund