STACS 2007
Springer Berlin (Verlag)
978-3-540-70917-6 (ISBN)
Invited Talks.- A Calculus and Algebra for Distributed Data Management.- The Büchi Complementation Saga.- Speed-Up Techniques for Shortest-Path Computations.- Session 1A.- Compact Forbidden-Set Routing.- A New Bound for Pure Greedy Hot Potato Routing.- Wavelength Management in WDM Rings to Maximize the Number of Connections.- Session 1B.- A First Investigation of Sturmian Trees.- On the Size of the Universal Automaton of a Regular Language.- Correlations of Partial Words.- Session 2A.- Testing Convexity Properties of Tree Colorings.- Why Almost All k-Colorable Graphs Are Easy.- Session 2B.- On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds.- A New Rank Technique for Formula Size Lower Bounds.- Session 3A.- Hard Metrics from Cayley Graphs of Abelian Groups.- Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs.- Light Orthogonal Networks with Constant Geometric Dilation.- Session 3B.- Admissibility in Infinite Games.- Pure Stationary Optimal Strategies in Markov Decision Processes.- Symmetries and the Complexity of Pure Nash Equilibrium.- Session 4A.- Computing Representations of Matroids of Bounded Branch-Width.- Characterizing Minimal Interval Completions.- Session 4B.- The Complexity of Unions of Disjoint Sets.- Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity.- Session 5A.- Bounded-Hop Energy-Efficient Broadcast in Low-Dimensional Metrics Via Coresets.- On the Complexity of Affine Image Matching.- Session 5B.- On Fixed Point Equations over Commutative Semirings.- An Exponential Lower Bound for Prefix Gröbner Bases in Free Monoid Rings.- Session 6A.- A Cubic Kernel for Feedback Vertex Set.- The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting.- An Optimal, Edges-OnlyFully Dynamic Algorithm for Distance-Hereditary Graphs.- Session 6B.- A Search Algorithm for the Maximal Attractor of a Cellular Automaton.- Universal Tilings.- On the Complexity of Unary Tiling-Recognizable Picture Languages.- Session 7A.- A Characterization of Strong Learnability in the Statistical Query Model.- On the Consistency of Discrete Bayesian Learning.- Session 7B.- VPSPACE and a Transfer Theorem over the Reals.- On Symmetric Signatures in Holographic Algorithms.- Session 8A.- Randomly Rounding Rationals with Cardinality Constraints and Derandomizations.- Cheating to Get Better Roommates in a Random Stable Matching.- A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window.- Session 8B.- Arithmetizing Classes Around NC 1 and L.- The Polynomially Bounded Perfect Matching Problem Is in NC 2.- Languages with Bounded Multiparty Communication Complexity.- Session 9A.- New Approximation Algorithms for Minimum Cycle Bases of Graphs.- On Completing Latin Squares.- Small Space Representations for Metric Min-Sum k-Clustering and Their Applications.- Session 9B.- An Optimal Tableau-Based Decision Algorithm for Propositional Neighborhood Logic.- Bounded-Variable Fragments of Hybrid Logics.- Rank-1 Modal Logics Are Coalgebraic.- Session 10A.- An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups.- Weak Fourier-Schur Sampling, the Hidden Subgroup Problem, and the Quantum Collision Problem.- Quantum Network Coding.- Session 10B.- Reachability in Unions of Commutative Rewriting Systems Is Decidable.- Associative-Commutative Deducibility Constraints.- On the Automatic Analysis of Recursive Security Protocols with XOR.- Session 11A.- Improved Online Algorithms for the Sorting Buffer Problem.- Cost Sharing Methods forMakespan and Completion Time Scheduling.- Session 11B.- Planar Graphs: Logical Complexity and Parallel Isomorphism Tests.- Enumerating All Solutions for Constraint Satisfaction Problems.
| Erscheint lt. Verlag | 8.2.2007 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science | Theoretical Computer Science and General Issues |
| Zusatzinfo | XVIII, 710 p. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 1012 g |
| Themenwelt | Mathematik / Informatik ► Informatik ► Datenbanken |
| Informatik ► Theorie / Studium ► Algorithmen | |
| Schlagworte | algorithm • Algorithm analysis and problem complexity • Algorithmics • algorithms • approximation algorithms • Automat • Automata • Automata Theory • Cellular Automata • combinatorics • Complexity • Complexity theory • computational descrete mathematics • Computer • Computer Science • Computer Science Logic • data structure • data structures • Distributed Systems • formal language • Formal Languages • formal methods • Game Theory • Hardcover, Softcover / Informatik, EDV/Informatik • HC/Informatik, EDV/Informatik • Information Theory • Kolmogorov complexity • Logic • Mathematical Logic • Parallel Computing • Programming Theory • Program Semantics • Semantics • Statistical Methods • Structural Complexity • theoretical computer science • theory of computing • verification |
| ISBN-10 | 3-540-70917-7 / 3540709177 |
| ISBN-13 | 978-3-540-70917-6 / 9783540709176 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
