Mathematical Aspects Of Computer And Information Sciences: 8th International Conference, Macis 2019, Gebze, Turkey, November 13–15, 2019, Revised ... (lecture Notes In Computer Science (11989))

This book constitutes the refereed proceedings of the 8th International Conference on Mathematical Aspects of Computer and Information Sciences, MACIS 2019, held in Gebze, Turkey, in November 2019. The 22 revised papers and 14 short papers presented were carefully reviewed and selected from 66 submissions. The papers are organized in the following topical sections: algorithms and foundation; security and cryptography; combinatorics, codes, designs and graphs; data modeling and machine learning; tools and software track. Preface Organization Contents Algorithms and Foundations Certified Hermite Matrices from Approximate Roots - Univariate Case 1 Introduction 2 Preliminaries 2.1 Hermite Matrices 2.2 Rational Number Reconstruction 3 Construction and Certification of Hermite Matrices 4 Example References On Parametric Border Bases 1 Introduction 2 Preliminary 2.1 Comprehensive Gröbner System 2.2 Border Bases in Parametric Polynomial Rings 3 Properties of Parametric Border Bases 4 Stability of Parametric Border Basis 5 Conclusion and Remarks References Reliable Computation of the Singularities of the Projection in R3 of a Generic Surface of R4 1 Introduction 2 Preliminaries 2.1 Regular, Critical and Singular Points 2.2 Transversality and Genericity 3 Generic Properties of Projected Surfaces 4 Computing the Singularities of the Projected Surface 4.1 Systems Encoding Singularities 4.2 Regularity 4.3 Ball System 4.4 Algorithm 5 Example 5.1 Whitney Umbrella 5.2 Large Polynomials 6 Conclusion 7 Appendix: Proof of Lemma 1 References Evaluation of Chebyshev Polynomials on Intervals and Application to Root Finding 1 Introduction 2 Evaluation of Chebyshev Polynomials on Intervals 2.1 Forward Error Analysis 2.2 Backward Error Analysis 3 Application to Root Finding References Proving Two Conjectural Series for (7) and Discovering More Series for (7) 1 Introduction 2 Proof of the Conjectures 3 More Identities References Generalized Integral Dependence Relations 1 Introduction 2 Preliminaries 2.1 Solving Extended Ideal Membership Problems 2.2 Algebraic Local Cohomology and Standard Bases 3 Generalized Integral Dependence Relations 4 Parametric Cases References Hilbert-Type Dimension Polynomials of Intermediate Difference-Differential Field Extensions 1 Introduction 2 Preliminaries 3 Dimension Polynomials of Intermediate Difference-Differential Fields. The Main Theorem 4 Type and Dimension of Difference-Differential Field Extensions 5 Multivariate Dimension Polynomials of Intermediate difference-Differential Field Extensions References Comprehensive LU Factors of Polynomial Matrices 1 Introduction 2 Preliminaries 3 Comprehensive LU Method 4 Implementation in Maple 4.1 Efficiency 5 Conclusion References Sublinear Cost Low Rank Approximation via Subspace Sampling 1 Introduction 2 Four Known Subspace Sampling Algorithms 3 Deterministic Error Bounds for Sampling Algorithms 3.1 Deterministic Error Bounds for Range Finder 3.2 Deterministic Impact of Pre-multiplication on the Errors of LRA 4 Accuracy of Sublinear Cost Dual LRA Algorithms 4.1 Errors of Range Finder for a Perturbed Factor-Gaussian Input 4.2 Output Errors of Range Finder Near a Matrix with a Random Singular Space 4.3 Impact of Pre-multiplication in the Case of Gaussian Noise 5 Multiplicative Pre-processing for LRA A Background on Matrix Computations A.1 Some Definitions A.2 Auxiliary Results A.3 Gaussian and Factor-Gaussian Matrices of Low Rank and Low Numerical Rank A.4 Norms of a Gaussian Matrix and Its Pseudo Inverse B Small Families of Hard Inputs for Sublinear Cost LRA References CUR LRA at Sublinear Cost Based on Volume Maximization 1 Introduction 2 Background: CUR LRA 3 Background: Matrix Volumes 3.1 Definitions and Hadamard's Bound 3.2 The Impact of Volume Maximization on CUR LRA 4 C-A Iterations 5 CUR LRA by Means of C-A Iterations 5.1 Volume of the Output of a C-A Loop 5.2 From Maximal Volume to Maximal r-Projective Volume 5.3 Complexity and Accuracy of a Two-Step C-A Loop 6 CUR LRA of SPSD Matrices: Two Main Results 7 Proof of Main Result 1 8 Complexity Analysis A Small Families of Hard Inputs for Sublinear Cost LRA B Definitions for Matrix Computations and a Lemma C The Volume and r-Projective Volume of a Perturbed Matrix D The Volume and r-Projective Volume of a Matrix Product References New Practical Advances in Polynomial Root Clustering 1 Introduction 1.1 Previous Works 1.2 Solving the LCP 2 Counting the Number of Roots in a Well Isolated Disc 2.1 Approximation of the 0-th Power Sum of the Roots in a Disc 2.2 Black Box for Evaluating a Polynomial on an Oracle Number 2.3 The P*-test 3 Using the P*-test in a Subdivision Framework 3.1 An Approximate P*-test 3.2 Using the P* and P*"0365P*-test in a Subdivision Framework 4 Clustering Roots of Polynomials with Real Coefficients 5 Numerical Results 6 Future Works References On the Chordality of Simple Decomposition in Top-Down Style 1 Introduction 2 Preliminaries 2.1 Triangular and Simple Systems 2.2 Subresultant Regular Subchains 2.3 Chordal Graphs and Polynomial Sets 3 Reformulation of Wang's Algorithm for Simple Decomposition in Top-Down Style 4 Decomposition Tree of Wang's Algorithm for Simple Decomposition in Top-Down Style 5 Chordality of Polynomial Sets in Wang's Algorithm for Simple Decomposition in Top-Down Style 6 Concluding Remarks References Automatic Synthesis of Merging and Inserting Algorithms on Binary Trees Using Multisets in Theorema 1 Introduction 2 Proof–Based Synthesis 2.1 Context 2.2 Special Inference Rules and Strategies 3 Experiments 3.1 Synthesis of Merging on Non–sorted Binary Trees 3.2 Synthesis of Merging on Sorted Binary Trees 4 Conclusions and Further Work References Algebraic Analysis of Bifurcations and Chaos for Discrete Dynamical Systems 1 Introduction 2 Algebraic Criteria for Stability, Bifurcations and Chaos 2.1 Stability Analysis of Fixed Points 2.2 Bifurcation Analysis 2.3 Snapback Repeller and Marotto's Theorem 3 Experiments 3.1 Illustrative Example 3.2 Other Models and Remarks 4 Discussion References Security and Cryptography Acceleration of Spatial Correlation Based Hardware Trojan Detection Using Shared Grids Ratio 1 Introduction 2 Preliminaries 2.1 Representation of Circuits 2.2 Delay Based Trojan Detection 2.3 Variation Effect and Difficulties 2.4 Review of Spatial Correlation Based HT Detection Method ch15esirci 3 CCM: Adaptation of the Method in Sect.2.4 to Full Circuit 4 Computational Cost Analysis for CCM 5 Shared Grids Method (SGM) for Accelerating CCM 6 Results: Comparison of CCM and SGM 7 Discussion and Future Work References A Parallel GPU Implementation of SWIFFTX 1 Introduction 2 SWIFFT and SWIFFTX 3 The Reference Implementation 4 A Parallel Implementation 5 Further Improvements and Occupancy Analysis 6 Methodology and Results 7 Conclusion References Computing an Invariant of a Linear Code 1 Introduction 2 Preliminaries 2.1 Linear Codes 2.2 The Weak Order Ideal of the Coset Leaders 3 Leader Codewords of Linear Codes 3.1 Computing Algorithm 3.2 Computing up to a Given Level 4 L(C) as an Invariant for Linear Codes 5 Finding the Permutation 5.1 The Proposed Signature 5.2 Refining the Partition 5.3 Computing Algorithm 6 Experimental Results References Generalized Secret Sharing Schemes Using NMDS Codes 1 Introduction 1.1 Our Contribution 2 Preliminaries 2.1 Coding Theory 2.2 Secret Sharing 3 Proposed Secret Sharing Scheme 3.1 Access Structure 3.2 Share Construction 3.3 Secret Recovery 4 Analysis of the Proposed Scheme 4.1 Cheating Detection and Cheating Identification 5 Conclusion and Future Work References Exploiting Linearity of Modular Multiplication 1 Introduction 1.1 Contribution 2 Preliminaries 3 Nonlinearity of Multiplication Operation 4 Linear Relations for 1-Round IDEA 4.1 Linear Relations for Operations 4.2 A New List of Linear Relations 4.3 New Linear Relations Algorithmically Generated 5 Linear Weak Key Classes for IDEA 6 Conclusion A Appendix: IDEA Block Cipher A.1 Key Schedule and Decryption Algorithm A.2 The MA-Structure and 1-Round IDEA Cipher B Appendix: New Linear Relations for 1-Round IDEA and 8.5-Round IDEA References Combinatorics, Codes, Designs and Graphs On a Weighted Spin of the Lebesgue Identity 1 Introduction 2 Proof of Theorem 1 3 Partition Theoretic Interpretations of Corollary 1 References Edge-Critical Equimatchable Bipartite Graphs 1 Introduction 2 Equimatchable Bipartite Graphs 3 Edge-Critical Equimatchable Bipartite Graphs References Determining the Rank of Tensors in Fq2Fq3Fq3 1 Introduction and Preliminaries 2 The Algorithms 2.1 Auxiliary Functions 2.2 OrbitOfTensor 2.3 RankOfTensor 3 Computations and Summary References Second Order Balance Property on Christoffel Words 1 Introduction 2 Notation and Christoffel Words 3 Balance Matrix 3.1 Properties of the Balance Matrix 3.2 Construction of the Balance Matrix for Christoffel Words 4 Second Order Balance Matrix 5 More About Christoffel Words 5.1 Stern-Brocot Tree and Continued Fractions 6 Recursive Construction of the Second Order Balance Matrix 6.1 The Construction of Uab 7 Perspectives References IPO-Q: A Quantum-Inspired Approach to the IPO Strategy Used in CA Generation 1 Introduction 2 Preliminaries 2.1 Review of the IPO Strategy 2.2 Review of the QiEAforCA Algorithm for CA Generation 3 IPO-Q: A Quantum-Inspired IPO Algorithm 4 Evaluation of Different Configurations of the IPO-Q Algorithm 5 Comparison with IPOG-F and Best Known Upper Bounds for CAN 6 Conclusion and Future Work References A Fast Counting Method for 6-Motifs with Low Connectivity 1 Introduction 2 Methodology 2.1 Main Theorems 3 Experimental Results and Conclusions 4 Conclusions References LaserTank is NP-Complete 1 Introduction 1.1 Short Background on 3-SAT 2 LaserTank 2.1 The Reduction References Data Modeling and Machine Learning Improved Cross-Validation for Classifiers that Make Algorithmic Choices to Minimise Runtime Without Compromising Output Correctness 1 Introduction 1.1 Background and Main Thesis 1.2 Outline of the Paper and Contribution 2 Background on Variable Ordering for CAD 2.1 Cylindrical Algebraic Decomposition 2.2 Variable Ordering 3 Prior ML Work on This Problem 3.1 Results from CICM 2014 3.2 Results from CICM 2019 3.3 Results from SC-Square 2019 3.4 Related Work on ML for Mathematical Software 4 New Cross-Validation Based on Computing Times 4.1 Motivation 4.2 Traditional ML Cross-Validation 4.3 Adapted ML Cross-Validation 5 ML Experiment Methodology 5.1 Problem Set 5.2 Software 5.3 Timings 5.4 Computing the Features 5.5 ML Models 5.6 Evaluating the ML Models and Human-Made Heuristics 6 Experimental Results 6.1 Results of New Cross-Validation Method 6.2 Comparison of Brown and Sotd on the 4-Variable Dataset 6.3 Value of ML on the 4-Variable Dataset 7 Summary References A Numerical Efficiency Analysis of a Common Ancestor Condition 1 Introduction 2 Background 3 Examples 4 Numerical Sampling 5 Discussion References Optimal Transport to a Variety 1 Introduction 2 Geometric Combinatorics of the Wasserstein Distance 3 An Algorithm and the Geometry of Triangles 4 Parametric Linear Optimization over a Variety 5 The Wasserstein Estimator of an Independence Model 6 Conclusion References SFV-CNN: Deep Text Sentiment Classification with Scenario Feature Representation 1 Introduction 2 Method 2.1 Expressive Grammar Plane Concept 2.2 Scenario Features Vectors 2.3 Text Sentiment Classification 3 Experiments 3.1 Data Set 3.2 Experimental Setup 3.3 Results and Discussion 4 Conclusions References Reinforcement Learning Based Interactive Agent for Personalized Mathematical Skill Enhancement 1 Introduction 2 Related Works 3 System Model 3.1 Student Profile Module 3.2 Learning Measurement Module 3.3 Task Selection Model 4 Proposed Methodology 4.1 Concept of Adversarial Bandits 4.2 Adversarial Bandit Solution Using the Exp3 Algorithm 5 Performance Evaluation and Results 5.1 Simulation Environment 5.2 Baseline Method 5.3 Experimental Results 6 Conclusion and Future Works References Common Vector Approach Based Image Gradients Computation for Edge Detection 1 Introduction 2 Common Vector Approach Based Edge Detection 2.1 Suppression of Noise by Gaussian Filtering 2.2 Gradient Map Computation Using CVA 2.3 Extraction of Peak Points 2.4 Connection of Peak Points 3 Experiments and Results 3.1 Performance Evaluation in Terms of Objective Measures 3.2 Performance Evaluation in Terms of Subjective Measures 4 Conclusion References Optimizing Query Perturbations to Enhance Shape Retrieval 1 Introduction 2 Background and Principles 2.1 Improvement of Shape Retrieval 2.2 Shape Descriptors 2.3 Shape Similarity and Statistical Distances 3 GA-SR: Genetic Algorithm for Shape Retrieval 3.1 Notations and Definitions 3.2 Sensitivity to Perturbations and Discretization Artifacts 3.3 The Genetic Algorithm 4 Experiments 4.1 Databases Used 4.2 Tests and Results 5 Conclusion References Authorship Attribution by Functional Discriminant Analysis 1 Introduction 2 Related Work 2.1 Character Features 2.2 Lexical Features 2.3 Syntaxic Features 2.4 Semantic Features 2.5 Application-Specific Features 2.6 Selection and Extraction of Features 3 Functional Discriminant Analysis (FDA) 4 Functional Representation of Texts 4.1 Preliminary Processing of Texts 4.2 Transformation of Texts into Functions 4.3 Advantages 5 Experimentation 5.1 Presentation of the Used Corpus 5.2 Results 5.3 Decomposition into Basis Functions 5.4 Application of the Discriminant Analysis on the Coefficients 5.5 Result of the Classic LDA on the Same Texts 5.6 Evaluation of the Classification 6 Conclusion References Tools and Software Track An Overview of Geometry Plus Simulation Modules 1 Introducing Isogeometric Analysis 2 General Concept of the Library 3 Open-Source License 4 Modules 5 Code Management and Documentation 6 Third-Party Dependencies 7 Plugins and Extensions References DD-Finite Functions Implemented in Sage 1 Introduction 2 Data Structure 2.1 The Parent Structure: DDRing 2.2 The Element Structure: DDFunction 3 Selected Methods and Main Features 3.1 Utility Methods 3.2 Operational Methods 3.3 Built-in Functions of the Package 3.4 Proving Identities with the Package 4 Conclusion References Author Index