You have Guest access.
Log In
Anna Frid, Andrey Morozov, Andrey Rybalchenko and Klaus W. Wagner
Front matter
1-11
Well-Founded and Partial Stable Semantics Logical Aspects
12-18
The Reachability Problem over Infinite Graphs
19-24
Kolmogorov Complexity and Model Selection
25
Automatic Verification of Heap-Manipulating Programs Using Separation Logic
26-37
Canonical Calculi: Invertibility, Axiom Expansion and (Non)-determinism
38-46
Integrality Property in Preemptive Parallel Machine Scheduling
47-58
Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
59-70
k-SAT Is No Harder Than Decision-Unique-k-SAT
71-79
Unique Decipherability in the Monoid of Languages: An Application of Rational Relations
80-91
Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model
92-104
Approximability Distance in the Space of H-Colourability Problems
105-116
On Random Ordering Constraints
117-128
Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
129-142
A Feebly Secure Trapdoor Function
143-154
Partitioning Graphs into Connected Parts
155-166
Structural Complexity of AvgBPP
167-178
Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials
179-190
Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
191-202
One-Nonterminal Conjunctive Grammars over a Unary Alphabet
203-214
Concatenation of Regular Languages and Descriptional Complexity
215-226
Approximability of the Maximum Solution Problem for Certain Families of Algebras
227-236
Complete Complexity Classification of Short Shop Scheduling
237-249
Compressed Word Problems in HNN-Extensions and Amalgamated Products
250-262
Variations on Muchnik’s Conditional Complexity Theorem
263-273
An Optimal Bloom Filter Replacement Based on Matrix Solving
274-285
Aperiodicity Measure for Infinite Sequences
286-298
On the Complexity of Matroid Isomorphism Problems
299-309
Breaking Anonymity by Learning a Unique Minimum Hitting Set
310-321
The Budgeted Unique Coverage Problem and Color-Coding (Extended Abstract)
322-333
Formal Verification of Gate-Level Computer Systems
334-345
On Models of a Nondeterministic Computation
346-355
New Plain-Exponential Time Classes for Graph Homomorphism
356-367
Languages Recognized with Unbounded Error by Quantum Finite Automata
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