Mathematical Aspects of Computer and Information Sciences

Name: Mathematical Aspects of Computer and Information Sciences | 7th International Conference, MACIS 2017, Vienna, Austria, November 15-17, 2017, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

7th International Conference, MACIS 2017, Vienna, Austria, November 15-17, 2017, Proceedings

Johannes Blömer Ilias S. Kotsireas Temur Kutsia Dimitris E. Simos(Herausgeber*in)

Springer (Verlag)

Erschienen am 20. Dezember 2017

XI, 462 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-72453-9 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Preface
Organization
Contents
Foundation of Algorithms in Mathematics, Engineering and Scientific Computation
Automated Reasoning for Knot Semigroups and -orbifold Groups of Knots
1 Main Definitions
1.1 Arcs and Crossings
1.2 Cancellative Semigroups and Knot Semigroups
1.3 Keis
1.4 -orbifold Groups and Two-fold Groups
1.5 Putting These Constructions Together
1.6 Other Constructions: Knot Groups and Quandles
2 Trivial Knots
2.1 How to Test if a Knot Semigroup Is Cyclic
2.2 Cyclic Knot Semigroups
2.3 Non-cyclic Knot Semigroups: Small Knots
2.4 Non-cyclic Knot Semigroups: Sums of Knots
2.5 Efficiency Comparison
3 4-plats
3.1 Defining Relations for an Alternative Sum Semigroup
3.2 Experiments
4 Future Research
5 Technical Details
References
Balancing Expression Dags for More Efficient Lazy Adaptive Evaluation
1 Introduction
2 Theoretical Foundation
2.1 Addition
2.2 Multiplication
3 Implementation
4 Experiments
5 Caveats
5.1 Evaluation Order
5.2 Operands Matter
5.3 Overhead
6 Conclusion
7 Future Work
References
Certification Using Newton-Invariant Subspaces
1 Introduction
1.1 Smale's alpha-theory
2 Newton-Invariant Sets
2.1 Finding Newton-Invariant Sets
3 Certification Algorithm for Square Systems
4 Systems Constructed from Newton-Invariant Sets
5 Implementation Details and Examples
5.1 Implementation in alphaCertified
5.2 A Basic Example
5.3 An Example from Griewank and Osborne
5.4 A System with Embedded Points
5.5 Four-Bar Linkages Using Isotropic Coordinates
6 Discussion and Summary
References
Decomposition of Low Rank Multi-symmetric Tensor
1 Introduction
2 Partial Symmetric Tensor Decomposition Problem
2.1 Solving Polynomial Equations by Eigenvector Computation
2.2 Artinian Gorenstein Algebra of a Multivariate Hankel Operator
3 Multilinear Tensor Decomposition Problem
3.1 Algorithm
4 Example
References
Dimension Quasi-polynomials of Inversive Difference Field Extensions with Weighted Translations
1 Introduction
2 Preliminaries
3 Dimension Quasi-polynomials of Subsets of Nm and Zm
4 The Main Theorem
References
Efficient Certification of Numeric Solutions to Eigenproblems
1 Introduction
2 Notations
2.1 Matrix Norms
2.2 Clustering
2.3 Diagonal Matrices
3 Eigenproblems for Perturbed Diagonal Matrices
3.1 The Linearized Equation
3.2 The Fundamental Iteration
3.3 Convergence of the Fundamental Iteration
4 Algorithms
4.1 Clustering
4.2 Certification in the Case of Perturbed Diagonal Matrices
4.3 Certification of Approximate Eigenvectors and Eigenvalues
5 Possible Extensions
References
Fast Chinese Remaindering in Practice
1 Introduction
2 Chinese Remaindering
2.1 The Chinese Remainder Theorem
2.2 Modular Arithmetic
2.3 Naive Multi-modular Reduction and Reconstruction
3 Gentle Moduli
3.1 The Naive Algorithms Revisited for Special moduli
3.2 Combining Special Moduli into Gentle moduli
4 The Gentle Modulus Hunt
4.1 The Sieving Procedure
4.2 Influence of the Parameters s, w and w'
4.3 Application to Matrix Multiplication
References
Homotopies for Connected Components of Algebraic Sets with Application to Computing Critical Sets
1 Introduction
2 Construction of Homotopies
3 Isolated Points of Images
4 Computing Critical Points of Projections
5 Example
6 Conclusion
References
Implementing Fast Carryless Multiplication
1 Introduction
1.1 Related Work
1.2 Results and Outline of the Paper
2 Prerequisites
3 Fast Reduction from F2 [x] to F260[x]
3.1 Variant of the Frobenius DFT
3.2 Frobenius Encoding
3.3 Direct Transforms
3.4 Inverse Transforms
3.5 Multiplication in F2 [x]
4 Implementation Details
4.1 Packed Representations
4.2 Matrix Transposition
4.3 Frobenius Encoding
5 Timings
6 Conclusion
References
Improving Enclosure of Interval Scalar Projection Operation
1 Introduction
2 Interval Extensions
3 Interval Scalar Projection in Rn
3.1 Lower and Upper Bounds of Interval Scalar Projection in Rn
4 Computation of Interval Scalar Projection in R2
4.1 Natural Interval Extension Method
4.2 Improved Algorithm
4.3 Interval Enclosure Quality Comparison
5 Applications
6 Conclusion and Future Work
References
Integrating Algebraic and SAT Solvers
1 Introduction
2 Algorithms for Basic Operations with Order Ideals
3 Linear Interreduction for Boolean Polynomials
4 The Boolean Border Basis Algorithm
5 The Integration of the BBBA with a SAT Solver
6 Design of the Communication
7 Modifications of the SAT Solver
8 Experiments and Timings
8.1 Manual Combination of the Information
8.2 Automatic Combination of the Information
References
Isabelle Formalization of Set Theoretic Structures and Set Comprehensions
1 Introduction
1.1 Related Work
1.2 Contributions and Outline
2 Preliminaries
3 Structures
3.1 Structure Preliminaries
3.2 Structure Operations
3.3 Structure Prototype Introduction
3.4 Inheritance and Multiple Inheritance
4 Set Comprehension
5 Case Studies
5.1 Algebraic Structures
5.2 SCM Computer Model
6 Conclusion
References
Jordan Canonical Form with Parameters from Frobenius Form with Parameters
1 Introduction
2 Some Prior Work
3 Preliminaries
3.1 Regular Chain Theory
3.2 Regular Chain Representation of a Splitting Field
3.3 The Frobenius Canonical Form
3.4 The Jordan Canonical Form
4 JCF over a Splitting Field
4.1 Jordan Form of a Companion Matrix
4.2 Frobenius Form to Jordan Form
4.3 Example
5 JCF of a Matrix with Parameters
5.1 Square-Free Factorization of a Parametric Polynomial
5.2 JCF of a Companion Matrix with Parameters
5.3 Frobenius Form to JCF with Parameters
6 Experimentation
6.1 Kac-Murdock-Szegö matrices
6.2 The Belousov-Zhabotinskii Reaction
6.3 Nuclear Magnetic Resonance
6.4 Bifurcation Studies
References
Knowledge-Based Interoperability for Mathematical Software Systems
1 Introduction
2 Math-in-the-Middle Interoperability
2.1 The MitM Ontology
2.2 Specifying System Dialects
2.3 MitM-Based Distributed Computation
3 The MitM Ontology for Computational Group Theory
3.1 Type Theory and Logic
3.2 Group Theory
4 The System Dialects of GAP, SageMath, and Singular
4.1 SageMath
4.2 GAP
4.3 Singular
4.4 Alignments
5 Distributed Computational Group Theory
6 Conclusion
References
On Interval Methods with Zero Rewriting and Exact Geometric Computation
1 Introduction
2 Exact Geometric Computation Paradigm
3 Variants of Interval Methods with Zero Rewriting
4 Experiments
5 Conclusions
References
Sparse Rational Function Interpolation with Finitely Many Values for the Coefficients
1 Introduction
2 Preliminary Algorithms
3 Univariate Rational Function Interpolation
3.1 A Basic Interpolation Algorithm
3.2 Deterministic Incremental Interpolation
3.3 Deterministic Incremental Interpolation with Two Points
3.4 Probabilistic Univariate Rational Function Interpolation
4 Multivariate Rational Function Interpolation
4.1 Multivariate Polynomial Interpolation with Kronecker Substitution
4.2 Probabilistic Multivariate Rational Function Interpolation
5 Experimental Results
6 Conclusion
References
Virtual Theories - A Uniform Interface to Mathematical Knowledge Bases
1 Introduction
2 Virtual Research Environments for Mathematics: The Math-in-the-Middle Approach
3 Example: The API and Structure of LMFDB
3.1 The Structure of LMFDB
3.2 An API for LMFDB Objects
4 LMFDB as a Set of Virtual Theories
5 Accessing Virtual Theories
5.1 Concrete Encodings of Mathematical Objects
5.2 Choosing Encodings in Schema Theories
6 Translating Queries
7 Conclusion
References
On Real Roots Counting for Non-radical Parametric Ideals
1 Introduction
2 Preliminary
2.1 Multivariate Real Roots Counting
2.2 Comprehensive Gröbner System
2.3 CGS-QE Algorithm
3 New Multivariate Real Roots Counting
3.1 Main Result
4 Conclusion and Remarks
References
On the Bit-Size of Non-radical Triangular Sets
1 Introduction
2 Interpolation Formula
3 Bit-Size Consideration
References
Rapidly Convergent Integrals and Function Evaluation
1 Introduction
2 First Integral
2.1 Trapezoidal Rule
2.2 Convergence Rate
3 Second Integral
References
Stirling Numbers, Lambert W and the Gamma Function
1 Introduction
2 First Expansion
3 Second Expansion
4 Concluding Remarks
References
The Potential and Challenges of CAD with Equational Constraints for SC-Square
1 Introduction
1.1 Cylindrical Algebraic Decomposition
1.2 New Applications: SC2
2 Potentials
2.1 Equational Constraint
2.2 Multiple Equational Constrains
2.3 Equational Constraints of Sub-formulae
3 Challenges
3.1 Need for Primitivity
3.2 Well-Orientedness
3.3 Incremental CAD
References
Combinatorics and Codes in Computer Science
New Small 4-Designs with Nonabelian Automorphism Groups
1 Introduction
2 Construction Method
3 Designs with 18 Points
4 Designs with 19 Points
References
On Classifying Steiner Triple Systems by Their 3-Rank
1 Introduction
2 The Triple System Supported by Cn
3 Counting STS(27) Supported by the Code C3
4 A Class of STS(27) Invariant Under a Group of Order 3
References
Right-Justified Characterization for Generating Regular Pattern Avoiding Permutations
1 Introduction
2 A Characterization for Right-Justified Permutation Patterns
3 Regular Patterns
4 c-Regular patterns
5 Constant Amortized Time Algorithms
6 Conclusion and Open Problems
References
Experimental Study of the Ehrhart Interpolation Polytope
1 Introduction
2 The Ehrhart Interpolation Polytope
3 Experiments and Statistics
4 Conclusion
References
On Testing Isomorphism of Graphs of Bounded Eigenvalue Multiplicity
1 Introduction
2 Permutation Representations and Projections
3 Bounding Vertex Partitions
References
Data Modeling and Analysis
A Simple Streaming Bit-Parallel Algorithm for Swap Pattern Matching
1 Introduction
2 Basic Definitions and the Graph Theoretic Model
2.1 Notations and Basic Definitions
2.2 A Graph Theoretic Model
2.3 Using Graph Theoretic Model for Matching
2.4 Shift-And Algorithm
3 Our Algorithm
3.1 Graph Theoretic View of the Shift-And Algorithm
3.2 Our Algorithm for Swap Matching Using the Graph Theoretic Model
4 Limitations of the Finite Deterministic Automata Approach
5 Smalgo Algorithm
5.1 Smalgo-I
5.2 The Flaw in the Smalgo, Smalgo-I and Smalgo-II
6 Experiments
References
Epidemic Intelligence Statistical Modelling for Biosurveillance
1 Introduction
1.1 Objectives/Goals
1.2 State of the Art
2 Materials and Methods
2.1 Sentinel Epidemiological Surveillance System
2.2 Two Season Influenza Historical Data
2.3 Research Methodology
3 Experimental Study
4 Concluding Remarks
References
Mining Acute Stroke Patients' Data Using Supervised Machine Learning
1 Introduction
2 Related Work
3 Dataset
4 Methodology
4.1 Defining Classifications Criteria
4.2 Pre-processing Data
5 Modelling Data
5.1 Software Tool
5.2 Classification Techniques
5.3 Testing Technique
5.4 Performance Metrics for Evaluation
6 Evaluation Results and Comparison
6.1 First Approach
6.2 Second Approach
7 Conclusion
References
Parallel and Robust Empirical Risk Minimization via the Median Trick
1 Introduction
1.1 Related Work
2 Method
2.1 Medians
2.2 Discussion of Method
3 Theorems
4 Experiments
4.1 Comparison of Accuracy
4.2 Group Size
4.3 Min-of-Min Counterexample
5 Summary
References
Mathematical Aspects of Information Security and Cryptography
Leakage-Resilient Riffle Shuffle
1 Introduction
1.1 Card Shuffling and Cryptography
1.2 Leakage
1.3 Our Contribution
2 Preliminary
2.1 Security Definition
2.2 Markov Chains and Rate of Convergence
3 RiffleSST- Leakage Resilient Shuffle
3.1 General Pseudo-random Permutation Generator
3.2 Description of RiffleSST Algorithm
4 Proofs
5 Sample Execution of RiffleSST Algorithm
6 Conclusions
References
Ordinary Pairing-Friendly Genus 2 Hyperelliptic Curves with Absolutely Simple Jacobians
1 Introduction
2 Background
3 Constructing Pairing-Friendly Jacobians
3.1 Lauter-Shang's Frobenius Elements
3.2 Generalized Drylo's Frobenius Elements
3.3 Alternative Representation
4 Implementation and Numerical Examples
5 Conclusion
References
Statistical Testing of PRNG: Generalized Gambler's Ruin Problem
1 Introduction
1.1 Related Work
1.2 Our Contribution
2 Gambler's Ruin Problem: Explicit Formulas for Winning Probabilities
3 BitTracker: Transforming Bit Strings into Intervals
3.1 BitTracker - Every Bit Counts
4 Testing Procedure
4.1 General Approach
4.2 Actual Parameters and Testing Procedure
4.3 Bit Derivation
5 Experimental Results
5.1 The 2 Test
6 Summary
References
Subtleties in Security Definitions for Predicate Encryption with Public Index
1 Introduction
2 Preliminaries
2.1 Predicate-Based Schemes with Public Index
3 Indistinguishability Templates for PE and P-KEM
4 Handling of User Secret Keys
4.1 OK-Security Does Not Imply OU-Security and CK-Security
4.2 OU-Security Does Not Imply OK-Security and CK-Security Under Chosen-Ciphertext Attack
4.3 Discussion and Recommendation
5 When and How to Restrict Challenge Decryptions
References
Code-Based Key Encapsulation from McEliece's Cryptosystem
1 Introduction
2 Preliminaries
2.1 The McEliece Cryptosystem
2.2 Encapsulation Mechanisms and the Hybrid Framework
3 The New KEM Construction
4 Conclusions
A The McEliece Cryptosystem
B Other Cryptographic Tools
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken