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(Editor)

Springer (Publisher)

Published on 20. December 2017

XI, 462 pages

E-Book

PDF with digital watermarking

System requirements

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

€53.49incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Persons

Content

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

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Mathematical Aspects of Computer and Information Sciences

Description

More details

Other editions

Additional editions

Persons

Content

System requirements