Stochastic Algorithms: Foundations and Applications: 4th International Symposium, SAGA 2007, Zurich, Switzerland, September 13-14, 2007, Proceedings (Lecture Notes in Computer Science, 4665)

This book constitutes the refereed proceedings of the 4th International Symposium on Stochastic Algorithms: Foundations and Applications, SAGA 2007. The nine revised full papers and five invited papers presented were carefully selected for inclusion in the book. The contributed papers included in this volume cover both theoretical as well as applied aspects of stochastic computations with a special focus on investigating the power of randomization in algorithmics. Title Page Preface Organization Table of Contents On Computation and Communication with Small Bias Design Strategies for Minimal Perfect Hash Functions Introduction Space-Optimal, Time-Efficient Constructions Practical Solutions Randomness Assumptions Split-and-Share for MPHFs Hash-and-Displace Approach Pure Hash-and-Displace Undo-One Minimal Perfect Hashing by the Multifunction Paradigm The Hypergraph Approach Below the Graph Thresholds A Partly Heuristic Approach An Analyzed Approach Below $n$ log $n$ An Almost Optimal Solution Conclusion References Hamming, Permutations and Automata Introduction Permutations Hamming Distance Main Results on Automata Super-Exponential Size Advantage Smaller Alphabets References Probabilistic Techniquesin Algorithmic Game Theory Preliminaries and Notation Existence of Approximate Equilibria of Small Support Sizes in Bimatrix Games Bimatrix Games Notation Existence of SuppNE with Logarithmic Support Sizes The Effect of Statistical Conflict in Network Congestion Games The Network Congestion Game Model Price of Anarchy in Weighted Network Congestion Games The Pure Price of Anarchy in Congestion Games The Effect of Coalitions in Parallel Links Congestion Games The Coalitional KP Model Price of Anarchy in the Coalitional KP Model References Randomized Algorithms and Probabilistic Analysis in Wireless Networking Introduction Four Topics References A First Step Towards Analyzing the Convergence Time in Player-Specific Singleton Congestion Games Introduction Definitions and Notations RelatedWork Games on Trees Player-Specific Congestion Games on Circles A Lower Bound The Impact of Type 1 Players A Framework to Analyze the Convergence Time Analyzing the Convergence Time Conclusions and Open Problems References Communication Problems in Random Line-of-Sight Ad-Hoc Radio Networks Introduction Random Line-of-Sight Network and Communication Protocols Properties of Random Line-of-Sight Networks Related Prior Works New Contributions Preliminaries Deterministic Algorithm with Position Information Broadcasting and Deterministic Gossiping with a Leader Gossiping Along a Grid Line Broadcasting and Gossiping with the Leader in the Whole Grid Fast Distributed Randomized Gossiping Conclusions References Approximate Discovery of Random Graphs Introduction Preliminaries Discovering a Large Fraction of a Random Graph The Case of Constant$p$ \boldmath The Case of $p = n^{\eps} / n$ Distances Within a Constant Cardinality Subset of the Nodes Conclusion References A VNS Algorithm for Noisy Problems and Its Application to Project Portfolio Analysis Introduction The Proposed Simulation-Optimization Algorithm General Problem Structure The Algorithm S-VNS ConvergenceAnalysis The Application Problem: Stochastic Project Selection, Scheduling and Staffing Problem Formulation Solution Technique A Numerical Example Conclusions References Digit Set Randomization in Elliptic Curve Cryptography Introduction Statistical Properties of NAF Representations $\mathcal{A}$ As a Dynamical System Generalizations Empirical Results Digit Set Randomization as a Side Channel Attack Countermeasure Entropy Bounds on Randomized Representations of Integers One Random Term in $D$ Two Random Terms in $ D $ General Case Conclusions and Further Work References Lower Bounds for Hit-and-Run Direct Search Introduction The Framework for the Randomized Methods The Lower Bounds Discussion and Conclusion References An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata Introduction Preliminaries The Upper Bound A Bigger Picture References Stochastic Methods for Dynamic OVSF Code Assignment in 3G Networks Introduction Basic Background Knowledge OVSF Code Tree Related Works Dynamic OVSF Code Allocation Using GA/SA GA Based Dynamic OVSF Code Allocation Scheme SA Based Dynamic OVSF Code Allocation Scheme Performance Evaluation Conclusions References On the Support Size of Stable Strategies in Random Games Introduction Preliminaries Probability of Stability Kingman’s Approach The Case of $\UNIFORM{0}{1}$ The Case of $\NORMAL{\xi}{1}$ Support Sizes of Almost All ESS An Upper Bound on the Expected Number of ESS References Author Index This book constitutes the refereed proceedings of the 4th International Symposium on Stochastic Algorithms: Foundations and Applications, SAGA 2007, held in Zurich, Switzerland, in September 2007. The 9 revised full papers and 5 invoted papers presented were carefully reviewed and selected out of 31 submissions for inclusion in the book. The contributed papers included in this volume cover both theoretical as well as applied aspects of stochastic computations whith a special focus on investigating the power of randomization in algorithmics