close
1.

電子ブック

EB
edited by Magnus M. Halldorsson, Kazuo Iwama, Naoki Kobayashi, Bettina Speckmann
出版情報: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2015
シリーズ名: Lecture Notes in Computer Science ; 9134
オンライン: http://dx.doi.org/10.1007/978-3-662-47672-7
目次情報: 続きを見る
Statistical Randomized Encodings: A Complexity Theoretic View
Tighter Fourier Transform Lower Bounds
Quantifying Competitiveness in Paging with Locality of Reference
Approximation Algorithms for Computing Maximin Share Allocations
Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare
Batched Point Location in SINR Diagrams via Algebraic Tools
On the Randomized Competitive Ratio of Reordering Buffer Management with Non-uniform Costs
Serving in the Dark Should Be Done Non-uniformly
Finding the Median (Obliviously) with Bounded Space
Approximation Algorithms for Min-Sum k-Clustering
Solving Linear Programming with Constraints Unknown
Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources
Limitations of Algebraic Approaches to Graph Isomorphism Testing
Fully Dynamic Matching in Bipartite Graphs
Feasible Interpolation for QBF Resolution Calculi
Simultaneous Approximation of Constraint Satisfaction Problems
Design of Dynamic Algorithms via Primal-Dual Method
What Percentage of Programs Halt?
The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems
Spotting Trees with Few Leaves
Constraint Satisfaction Problems over the Integers with Successor
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
Algorithms and Complexity for Turaev-Viro Invariants
Big Data on the Rise? ? Testing Monotonicity of Distributions
Unit Interval Editing Is Fixed-Parameter Tractable
Streaming Algorithms for Submodular Function Maximization
Multilinear Pseudorandom Functions
Zero-Fixing Extractors for Sub-Logarithmic Entropy
Interactive Proofs with Approximately Commuting Provers
Popular Matchings with Two-Sided Preferences and One-Sided Ties
Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity
On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols
Scheduling Bidirectional Traffic on a Path
On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace
On Planar Boolean CSP
On Temporal Graph Exploration
Mind Your Coins: Fully Leakage-Resilient Signatures with Graceful Degradation
A (1+e)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
Lower Bounds for the Graph Homomorphism Problem
Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
Relative Discrepancy Does not Separate Information and Communication Complexity
A Galois Connection for Valued Constraint Languages of Infinite Size
Approximately Counting H Colourings Is #BIS-Hard
Taylor Polynomial Estimator for Estimating Frequency Moments
ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets
Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search
Optimal Encodings for Range Top-k, Selection, and Min-Max
2-Vertex Connectivity in Directed Graphs
Ground State Connectivity of Local Hamiltonians
Uniform Kernelization Complexity of Hitting Forbidden Minors
Counting Homomorphisms to Square-Free Graphs, Modulo 2
Approximately Counting Locally-Optimal Structures
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs (Extended Abstract)
Fast Algorithms for Diameter-Optimally Augmenting Paths
Hollow Heaps
Linear-Time List Recovery of High-Rate Expander Codes
Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities
Local Reductions
Query Complexity in Expectation
Near-Linear Query Complexity for Graph Inference
A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
Finding a Path in Group-Labeled Graphs with Two Labels Forbidden
Lower Bounds for Sums of Powers of Low Degree Univariates
Approximating CSPs Using LP Relaxation
Comparator Circuits over Finite Bounded Posets
Algebraic Properties of Valued Constraint Satisfaction Problem
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
Replacing Mark Bits with Randomness in Fibonacci Heaps
A PTAS for the Weighted Unit Disk Cover Problem
Approximating the Expected Values for Combinatorial Optimization Problems Over Stochastic Points
Deterministic Truncation of Linear Matroids
Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
A (2+e)-Approximation Algorithm for the Storage Allocation Problem
Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
Computing the Frechet Distance Between Polygons with Holes
An Improved Private Mechanism for Small Databases
Binary Pattern Tile Set Synthesis Is NP-Hard
Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity
Condensed Unpredictability
Sherali-Adams Relaxations for Valued CSPs
Two-Sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm
The Simultaneous Communication of Disjointness with Applications to Data Streams
An Improved Combinatorial Algorithm for Boolean Matrix Multiplication
Statistical Randomized Encodings: A Complexity Theoretic View
Tighter Fourier Transform Lower Bounds
Quantifying Competitiveness in Paging with Locality of Reference
2.

電子ブック

EB
edited by Dachuan Xu, Donglei Du, Dingzhu Du
出版情報: Cham : Springer International Publishing : Imprint: Springer, 2015
シリーズ名: Lecture Notes in Computer Science ; 9198
オンライン: http://dx.doi.org/10.1007/978-3-319-21398-9
目次情報: 続きを見る
Algorithms and data structures
Algorithmic game theory; approximation algorithms and online algorithms
Automata, languages, logic and computability
Complexity theory
Computational learning theory
Cryptography, reliability and security
Database theory, computational biology and bioinformatics
Computational algebra, geometry, number theory, graph drawing and information visualization
Graph theory, communication networks, optimization and parallel and distributed computing
Algorithms and data structures
Algorithmic game theory; approximation algorithms and online algorithms
Automata, languages, logic and computability
3.

電子ブック

EB
edited by Cetin Kaya Koc, Sihem Mesnager, Erkay Sava?
出版情報: Cham : Springer International Publishing : Imprint: Springer, 2015
シリーズ名: Lecture Notes in Computer Science ; 9061
オンライン: http://dx.doi.org/10.1007/978-3-319-16277-5
目次情報: 続きを見る
First Invited talk
Computing Discrete Logarithms in F36?137 and F36?163 using Magma
Finite Field Arithmetic
Accelerating Iterative SpMV for the Discrete Logarithm Problem using GPUs
Finding Optimal Chudnovsky-Chudnovsky Multiplication Algorithms
Reducing the Complexity of Normal Basis Multiplication
O
Second Invited talk
Open Questions on Nonlinearity and on APN functions
Boolean and Vectorial Functions
Some Results on Difference Balanced Functions
Affine Equivalency and Nonlinearity Preserving Bijective Mappings over F2
On Verification of Restricted Extended Affine Equivalence of Vectorial Boolean Functions
On o-Equivalence of Niho Bent Functions
Third Invited Talk
L-polynomials of the curve yqn? y = xqh+1? _ over Fqm
Coding Theory and Code-based Cryptography
Efficient Software Implementations of Code-based Hash Functions
Quadratic residue codes over Fp + vFp + v2F.p
First Invited talk
Computing Discrete Logarithms in F36?137 and F36?163 using Magma
Finite Field Arithmetic
4.

電子ブック

EB
edited by Frank Dehne, Jorg-Rudiger Sack, Ulrike Stege
出版情報: Cham : Springer International Publishing : Imprint: Springer, 2015
シリーズ名: Lecture Notes in Computer Science ; 9214
オンライン: http://dx.doi.org/10.1007/978-3-319-21840-3
目次情報: 続きを見る
Contact Graphs of Circular Arcs
Contact Representations of Graphs in 3D
Minimizing the Aggregate Movements for Interval Coverage
Online Bin Packing with Advice of Small Size
On the Approximability of Orthogonal Order Preserving Layout Adjustment
An Optimal Algorithm for Plane Matchings in Multipartite Geometric Graphs
Generation of Colourings and Distinguishing Colourings of Graphs
Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time
On Coct-Free Multi-Coloring
Semi-dynamic connectivity in the plane
Interval Selection in the Streaming Model
On the Bounded-Hop Range Assignment Problem
Greedy Is an Almost Optimal Deque
A New Approach for Contact Graph Representations and Its Applications
Communication and Dynamic Networks
Dealing With 4-Variables by Resolution: An Improved MaxSAT Algorithm
Select with Groups of 3 or 4 Approximating Nearest Neighbor Distances
Linearity is Strictly More Powerful than Contiguity for Encoding Graphs
On the Complexity of an Unregulated Traffic Crossing
Finding Pairwise Intersections Inside a Query Range
Cache-Oblivious Iterated Predecessor Queries via Range Coalescing
Polylogarithmic Fully Retroactive Priority Queues
On the Minimum Eccentricity Shortest Path Problem
Convex polygons in geometric triangulations
Straight-line Drawability of a Planar Graph Plus an Edge
Solving Problems on Graphs of High Rank-Width
The Parametric Closure Problem
Rooted Cycle Bases
On the Chain Pair Simplification Problem
Finding Articulation Points of Large Graphs in Linear Time
LP-based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design
Universal Reconstruction of a String
The complexity of dominating set reconfiguration
Editing Graphs into Few Cliques: Complexity, Approximation, and Kernelization Schemes
Competitive Diffusion on Weighted Graphs
Sorting and Selection with Equality Comparisons
Polynomial Delay Algorithm for Listing Minimal Edge Dominating sets in Graphs
Fast and simple connectivity in graph timelines
Dynamic Set Intersection
Time-Space Trade-of is for Triangulations and Voronoi Diagrams
A 2k-Vertex Kernel for Maximum Internal Spanning Tree
Reconfiguration on sparse graphs
Smoothed Analysis of Local Search Algorithms
Optimal Shue Code with Permutation Instructions
Non-Preemptive Scheduling on Machines with Setup Times
A Moderately Exponential Time Algorithm for k -IBDD Satisfiability
On the Parameterized Complexity of Girth and Connectivity Problems on Linear Matroids
Inferring People's Social Behavior by Exploiting Their Spatiotemporal Location Data
lastic Geometric Shape Matching for Point Sets under Translations
Constant Time Enumeration by Amortization
Computing the Center of Uncertain Points on Tree Networks
Swapping Colored Tokens on Graphs
Contact Graphs of Circular Arcs
Contact Representations of Graphs in 3D
Minimizing the Aggregate Movements for Interval Coverage
5.

電子ブック

EB
edited by Zaixin Lu, Donghyun Kim, Weili Wu, Wei Li, Ding-Zhu Du
出版情報: Cham : Springer International Publishing : Imprint: Springer, 2015
シリーズ名: Lecture Notes in Computer Science ; 9486
オンライン: http://dx.doi.org/10.1007/978-3-319-26626-8
6.

電子ブック

EB
edited by Magnus M. Halldorsson, Kazuo Iwama, Naoki Kobayashi, Bettina Speckmann
出版情報: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2015
シリーズ名: Lecture Notes in Computer Science ; 9135
オンライン: http://dx.doi.org/10.1007/978-3-662-47666-6
目次情報: 続きを見る
Towards the Graph Minor Theorems for Directed Graphs
Automated Synthesis of Distributed Controllers
Games for Dependent Types
Short Proofs of the Kneser-Lovasz Coloring Principle
Provenance Circuits for Trees and Treelike Instances
Language Emptiness of Continuous-Time Parametric Timed Automata
Analysis of Probabilistic Systems via Generating Functions and Pade Approximation
On Reducing Linearizability to State Reachability
The Complexity of Synthesis from Probabilistic Components
Edit Distance for Pushdown Automata
Solution Sets for Equations over Free Groups Are EDT0L Languages
Limited Set Quantifiers over Countable Linear Orderings
Reachability Is in DynFO
Natural Homology
Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes
Trading Bounds for Memory in Games with Counters
Decision Problems of Tree Transducers with Origin
Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words
The Odds of Staying on Budget
From Sequential Specifications to Eventual Consistency
Fixed-Dimensional Energy Games Are in Pseudo-Polynomial Time
An Algebraic Geometric Approach to Nivat’s Conjecture
Nominal Kleene Coalgebra
On Determinisation of Good-for-Games Automata
Owicki-Gries Reasoning for Weak Memory Models
On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension
Compressed Tree Canonization
Parsimonious Types and Non-uniform Computation
Baire Category Quantifier in Monadic Second Order Logic
Liveness of Parameterized Timed Networks
Symmetric Strategy Improvement
Effect Algebras, Presheaves, Non-locality and Contextuality
On the Complexity of Intersecting Regular, Context-Free, and Tree Languages
Containment of Monadic Datalog Programs via Bounded Clique-Width
An Approach to Computing Downward Closures
How Much Lookahead Is Needed to Win Infinite Games?
Symmetric Graph Properties Have Independent Edges
Polylogarithmic-Time Leader Election in Population Protocols
Core Size and Densification in Preferential Attachment Networks
Maintaining Near-Popular Matchings
Ultra-Fast Load Balancing on Scale-Free Networks
Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms
The Range of Topological Effects on Communication
Secretary Markets with Local Information
A Simple and Optimal Ancestry Labeling Scheme for Trees
Interactive Communication with Unknown Noise Rate
Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
A Unified Framework for Strong Price of Anarchy in Clustering Games
On the Diameter of Hyperbolic Random Graphs
Tight Bounds for Cost-Sharing in Weighted Congestion Games
Distributed Broadcast Revisited: Towards Universal Optimality
Selling Two Goods Optimally
Adaptively Secure Coin-Flipping, Revisited
Optimal Competitiveness for the Rectilinear Steiner Arborescence Problem
Normalization Phenomena in Asynchronous Networks
Broadcast from Minicast Secure Against General Adversaries
Towards the Graph Minor Theorems for Directed Graphs
Automated Synthesis of Distributed Controllers
Games for Dependent Types
7.

電子ブック

EB
edited by Keisuke Tanaka, Yuji Suga
出版情報: Cham : Springer International Publishing : Imprint: Springer, 2015
シリーズ名: Lecture Notes in Computer Science ; 9241
オンライン: http://dx.doi.org/10.1007/978-3-319-22425-1
8.

電子ブック

EB
edited by Ivan Dimov, Istvan Farago, Lubin Vulkov
出版情報: Cham : Springer International Publishing : Imprint: Springer, 2015
シリーズ名: Lecture Notes in Computer Science ; 9045
オンライン: http://dx.doi.org/10.1007/978-3-319-20239-6
目次情報: 続きを見る
Simulation of Flow in Fractured Poroelastic Media: a Comparison of Different Discretization Approaches
A Transparent Boundary Condition for an Elastic Bottom in Underwater Acoustics
Well-Posedness in H¨older Spaces of Elliptic Differential and Difference Equations
Operator Semigroups for Convergence Analysis
The Power of Trefftz Approximations: Finite Difference, Boundary Difference and Discontinuous Galerkin Methods; Nonreflecting Conditions and Non-Asymptotic Homogenization
On Extension of Asymptotic Comparison Principle for Time Periodic Reaction-Diffusion-Advection Systems with Boundary and Internal Layers
The Finite Difference Method for Boundary Value Problem with Singularity
Superconvergence of Some Linear and Quadratic Functionals for Higher-order Finite Elements
Time Step for Numerically Solving Parabolic Problems
Recent Advances in Numerical Solution of HJB Equations Arising in Option Pricing
Applications of Numerical Methods for Stochastic Controlled Switching Diffusions with A Hidden Markov Chain: Case Studies on Distributed Power Management and Communication Resource Allocation
Error Estimates of the Crank-Nicolson-Polylinear FEM with the discrete TBC for the Generalized Schr¨odinger Equation in an Unbounded Parallelepiped
Difference Schemes for Delay Parabolic Equations with Periodic Boundary Conditions
Some Results of FEM Schemes Analysis by Finite Difference Method
Application of Finite Difference TVD Methods in Hypersonic Aerodynamics
Finite Difference Equations for Neutron Flux and Importance Distribution in 3D Heterogeneous Reactor
Matrix-free Iterative Processes for Implementation of Implicit Runge?Kutta Methods
Simulation of Technogenic and Climatic Influences in Permafrost
Iterative Implicit Methods for Solving Nonlinear Dynamical Systems: Application of the Levitron
Modeling Textile Fabric used in Pest Control with a 3 Scale Domain Decomposition Method
The Theory and Applications of the SMIF Method for Correct Mathematical Modeling of the Incompressible Fluid Flows
Determination of the Time-dependent Thermal Conductivity in the Heat Equation with Spacewise Dependent Heat Capacity
Inverse Problems of Simultaneous Determination of the Time-dependent Right-hand Side Term and the Coefficient in a Parabolic Equation
Effectiveness of the parallel implementation of the FEM for the problem of the surface waves propagation
Splitting Scheme for Poroelasticity and Thermoelasticity Problems
Simulation of Flow in Fractured Poroelastic Media: a Comparison of Different Discretization Approaches
A Transparent Boundary Condition for an Elastic Bottom in Underwater Acoustics
Well-Posedness in H¨older Spaces of Elliptic Differential and Difference Equations
9.

電子ブック

EB
edited by Adrian Kosowski, Igor Walukiewicz
出版情報: Cham : Springer International Publishing : Imprint: Springer, 2015
シリーズ名: Lecture Notes in Computer Science ; 9210
オンライン: http://dx.doi.org/10.1007/978-3-319-22177-9
10.

電子ブック

EB
edited by Christian Scheideler
出版情報: Cham : Springer International Publishing : Imprint: Springer, 2015
シリーズ名: Lecture Notes in Computer Science ; 9439
オンライン: http://dx.doi.org/10.1007/978-3-319-25258-2
目次情報: 続きを見る
Communication Patterns and Input Patterns in Distributed Computing
Clock Synchronization and Estimation in Highly Dynamic Networks: An Information Theoretic Approach
Node Labels in Local Decision
Exact bounds for distributed graph colouring
Essential Traffic Parameters for Shared Memory Switch Performance. -Scheduling Multipacket Frames With Frame Deadlines
A Randomized Algorithm for Online Scheduling
Online Admission Control and Embedding of Service Chains
Optimizing Spread of Inuence in Social Networks via Partial Incentives
Approximation Algorithms For Multi-Budgeted Network Design Problems
Simple Distributed + 1 Coloring in the SINR Model
Nearly Optimal Local Broadcasting in the SINR Model with Feedback
Byzantine Gathering in Networks
Signature-free Asynchronous Byzantine Systems: From Multivalued to Binary Consensus
A Fast Network-Decomposition Algorithm and its Applications to Constant-Time Distributed Computation
Path-Fault-Tolerant Approximate Shortest-Path Trees
A faster computation of all the best swap edges of a tree spanner
Randomized OBDD-Based Graph Algorithms
On Fast and Robust Information Spreading in the Vertex-Congest Model
Under the Hood of the Bakery Algorithm: Mutual Exclusion as a Matter of Priority
The Computability of Relaxed Data Structures: Queues and Stacks as Examples
Comparison-based Interactive Collaborative Filtering
Coalescing walks on rotor-router systems
Communication Patterns and Input Patterns in Distributed Computing
Clock Synchronization and Estimation in Highly Dynamic Networks: An Information Theoretic Approach
Node Labels in Local Decision