You have Guest access.
Log In
Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi and Moti Yung
Front matter
61
Holographic Circuits
62
Probabilistic Polynomial-Time Semantics for a Protocol Security Logic
99
A Gentle Introduction to Semantic Subtyping
Logics for Unranked Trees: An Overview
105
Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture
The Tree Inclusion Problem: In Optimal Space and Faster
Union-Find with Constant Time Deletions
100
Optimal In-place Sorting of Vectors and Records
Towards Optimal Multiple Selection
Simple Extractors via Constructions of Cryptographic Pseudo-random Generators
Bounds on the Efficiency of “Black-Box” Commitment Schemes
On Round-Efficient Argument Systems
101
Computational Bounds on Hierarchical Data Processing with Applications to Information Security (Extended Abstract)
Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins (Extended Abstract)
Worst Case Optimal Union-Intersection Expression Evaluation
Measure and Conquer: Domination – A Case Study
102
Optimistic Asynchronous Atomic Broadcast
Asynchronous Perfectly Secure Communication over One-Time Pads
Single-Prover Concurrent Zero Knowledge in Almost Constant Rounds
LCA Queries in Directed Acyclic Graphs
Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs
Deterministic Constructions of Approximate Distance Oracles and Spanners
An Õ(m2n) Randomized Algorithm to Compute a Minimum Cycle Basis of a Directed Graph
Basing Cryptographic Protocols on Tamper-Evident Seals
Hybrid Trapdoor Commitments and Their Applications
On Steganographic Chosen Covertext Security
Classification of Boolean Functions of 6 Variables or Less with Respect to Some Cryptographic Properties
Label-Guided Graph Exploration by a Finite Automaton
101-102
On the Wake-Up Problem in Radio Networks
104
Distance Constrained Labelings of Graphs of Bounded Treewidth
Optimal Branch-Decomposition of Planar Graphs in O(n3) Time
NFAs With and Without ε-Transitions
On the Equivalence of \mathbb Z{\mathbb Z}-Automata
A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata
Groupoids That Recognize Only Regular Languages (Extended Abstract)
Append-Only Signatures
103
Hierarchical Group Signatures
Designated Verifier Signature Schemes: Attacks, New Security Notions and a New Construction
Single-Key AIL-MACs from Any FIL-MAC
The Efficiency and Fairness of a Fixed Budget Resource Allocation Game
Braess’s Paradox, Fibonacci Numbers, and Exponential Inapproximability
Weighted Automata and Weighted Logics
Restricted Two-Variable FO + MOD Sentences, Circuits and Communication Complexity
Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of Type y2=x2k+1^{\rm 2{\it k}+1}+ax
Solvability of a System of Bivariate Polynomial Equations over a Finite Field (Extended Abstract)
Cache-Oblivious Planar Shortest Paths
Cache-Aware and Cache-Oblivious Adaptive Sorting
Simulated Annealing Beats Metropolis in Combinatorial Optimization
Online Interval Coloring and Variants
Dynamic Bin Packing of Unit Fractions Items
Reordering Buffer Management for Non-uniform Cost Models
Combining Intruder Theories
Computationally Sound Implementations of Equational Theories Against Passive Adversaries
99-100
Password-Based Encryption Analyzed
On the Cover Time of Random Geometric Graphs
On the Existence of Hamiltonian Cycles in Random Intersection Graphs
Optimal Cover Time for a Graph-Based Coupon Collector Process
Stability and Similarity of Link Analysis Ranking Algorithms
Up-to Techniques for Weak Bisimulation
Petri Algebras
A Finite Basis for Failure Semantics
Spatial Logics for Bigraphs
Completely Non-malleable Schemes (Extended Abstract)
Boneh-Franklin Identity Based Encryption Revisited
Single-Database Private Information Retrieval with Constant Communication Rate
Concurrent Zero Knowledge in the Public-Key Model
A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines
Polynomial Time Preemptive Sum-Multicoloring on Paths
The Generalized Deadlock Resolution Problem
Facility Location in Sublinear Time
The Complexity of Stochastic Rabin and Streett Games
Recursive Markov Decision Processes and Recursive Stochastic Games
Decidability in Syntactic Control of Interference
Idealized Algol with Ground Recursion, and DPDA Equivalence
From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?
Approximating MaxkCSP – Outperforming a Random Assignment with Almost a Linear Factor
On Dynamic Bit-Probe Complexity
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines
Lower Bounds for Circuits with Few Modular and Symmetric Gates
Discrete Random Variables over Domains
An Accessible Approach to Behavioural Pseudometrics With an Application to Probabilistic Systems
Noisy Turing Machines
A Better Approximation Ratio for the Vertex Cover Problem
Stochastic Steiner Trees Without a Root
Approximation Algorithms for the Max-coloring Problem
Tight Lower Bounds for Query Processing on Streaming and External Memory Data
Decidability and Complexity Results for Timed Automata via Channel Machines
Congruences for Visibly Pushdown Languages
Approximation Algorithms for Euclidean Group TSP
Influential Nodes in a Diffusion Model for Social Networks
An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks
New Approaches for Virtual Private Network Design
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
On the l-Ary GCD-Algorithm in Rings of Integers
A Fully Abstract Encoding of the π-Calculus with Data Terms (Extended Abstract)
Orthogonal Extensions in Structural Operational Semantics (Extended Abstract)
Basic Observables for a Calculus for Global Computing
Compositional Verification of Asynchronous Processes via Constraint Solving
103-104
Optimal Spaced Seeds for Faster Approximate String Matching
Fast Neighbor Joining
Randomized Fast Design of Short DNA Words
A Quantum Lower Bound for the Query Complexity of Simon’s Problem
All Quantum Adversary Methods Are Equivalent
Quantum Complexity of Testing Group Commutativity
Semantic-Based Code Obfuscation by Abstract Interpretation
About Hoare Logics for Higher-Order Store
The Polyranking Principle
Approximate Guarding of Monotone and Rectilinear Polygons
Linear Time Algorithms for Clustering Problems in Any Dimensions
Dynamic Diffusion Load Balancing
On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group
On the Hardness of Embeddings Between Two Finite Metrics
Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval
Preservation Under Extensions on Well-Behaved Finite Structures
Unsafe Grammars and Panic Automata
Signaling P Systems and Verification Problems
Back matter
This page requires script.
Frequently asked questions General info on journals and books Send us your feedback Impressum Contact us
© Springer, Part of Springer Science+Business Media Privacy, Disclaimer, Terms & Conditions, and Copyright Info