top

  Info

  • Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.

  Info

  • Utilizzare questo link per rimuovere la selezione effettuata.

Biblioteca

MARC Lista (tabellare)
Mathematical Foundations of Computer Science 2014 [[electronic resource] ] : 39th International Symposium, MFCS 2014, Budapest, Hungary, August 26-29, 2014. Proceedings, Part I / / edited by Ersébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik
Mathematical Foundations of Computer Science 2014 [[electronic resource] ] : 39th International Symposium, MFCS 2014, Budapest, Hungary, August 26-29, 2014. Proceedings, Part I / / edited by Ersébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik
Edizione [1st ed. 2014.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2014
Descrizione fisica 1 online resource (XXVI, 561 p. 65 illus.)
Disciplina 004.0151
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Computer science—Mathematics
Discrete mathematics
Numerical analysis
Artificial intelligence—Data processing
Machine theory
Discrete Mathematics in Computer Science
Numerical Analysis
Data Science
Formal Languages and Automata Theory
Mathematical Applications in Computer Science
ISBN 3-662-44522-0
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Table of Contents - Volume I.-Invited contributions -- Partial-Observation Stochastic Reachability and Parity Games -- Every graph is easy or hard: dichotomy theorems for graph problems -- Computer Poker and Computational Game Theory -- Random Deterministic Automata -- Communication Complexity Theory: Thirty-Five Years of Set Disjointness -- What does the local structure of a planar graph tell us about its global structure? -- Logic, Semantics, Automata and Theory of Programming -- Choiceless Polynomial Time on structures with small Abelian colour Classes -- Sofic-Dyck shifts -- A Logical Characterization of Timed (non-)Regular Languages -- Asymptotic Monadic Second-Order Logic -- Towards Efficient Reasoning Under Guarded-based Disjunctive Existential Rules -- Alternating Parity Krivine Automata -- Advances in Parametric Real-Time Reasoning -- Universal Lyndon Words -- Subword complexity and decomposition of the set of factors -- Cyclic Complexity of Words -- Classifying Recognizable Infinitary Trace Languages Using Word Automata -- Bounded variable logic, parameterized logarithmic space, and Savitch’s Theorem -- An algebraic characterization of unary two-way transducers -- Size-Change Abstraction and Max-Plus Automata -- Alternating Vector Addition Systems with States -- Information Rate of Some Classes of Non-regular Languages: An Automata-theoretic Approach -- Relating Nominal and Higher-Order Rewriting -- Expressivity and Succinctness of Order-Invariant Logics on Depth-Bounded Structures -- Two Recursively Inseparable Problems for Probabilistic Automata -- Monadic Second-Order Logic with Arbitrary Monadic Predicates -- Transforming two-way alternating finite automata to one-way nondeterministic automata -- Measure Properties of Game Tree Languages -- On Upper and Lower Bounds on the Length of Alternating Towers -- LaxF: Side Conditions and External Evidence as Monads -- The monoid of queue actions -- Undecidable properties of self-affine sets and multi-tape automata -- Complexity and Expressivity of Uniform One-Dimensional Fragment with Equality -- A Unifying Approach for Multistack Pushdown Automata -- Definability and Transformations for Cost Logics and Automatic Structures -- Generalised Lyndon-Schützenberger Equations -- Complexity of Equivalence and Learning for Multiplicity Tree Automata -- Monadic datalog and regular tree pattern queries -- Model Checking Concurrent Recursive Programs using Temporal Logics -- Decidability of the interval temporal logic AABB over the rationals -- Reachability in Pushdown Register Automata -- A Generalization of the Łos-Tarski Preservation Theorem over Classes of Finite Structures -- Determinising Parity Automata -- Tight Bounds for Complementing Parity Automata -- On Infinite Words Determined by Indexed Languages -- A Pumping Lemma for Two-Way Finite Transducers -- Tractability Frontier for Dually-Closed Ord-Horn Quantified Constraint Satisfaction Problems -- The Dynamic Descriptive Complexity of k-Clique.
Record Nr. UNINA-9910484249403321
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2014
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Mathematical Foundations of Computer Science 2014 [[electronic resource] ] : 39th International Symposium, MFCS 2014, Budapest, Hungary, August 26-29, 2014. Proceedings, Part II / / edited by Ersébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik
Mathematical Foundations of Computer Science 2014 [[electronic resource] ] : 39th International Symposium, MFCS 2014, Budapest, Hungary, August 26-29, 2014. Proceedings, Part II / / edited by Ersébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik
Edizione [1st ed. 2014.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2014
Descrizione fisica 1 online resource (XXII, 640 p. 71 illus.)
Disciplina 004.0151
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Computer science—Mathematics
Discrete mathematics
Numerical analysis
Artificial intelligence—Data processing
Machine theory
Discrete Mathematics in Computer Science
Numerical Analysis
Data Science
Formal Languages and Automata Theory
Mathematical Applications in Computer Science
ISBN 3-662-44465-8
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Table of Contents - Volume II -- Algorithms, Complexity and Games -- On r-Simple k-Path -- Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs -- Zero Knowledge and Circuit Minimization -- A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity -- n)-Space and Polynomial-time Algorithm for Planar Directed Graph Reachability -- Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set -- Network-Based Dissolution -- On Unification of QBF Resolution-Based Calculi -- Minimum planar multi-sink cuts with connectivity priors -- The Price of Envy-Freeness in Machine Scheduling -- On the Complexity of Some Ordering Problems -- The Relationship Between Multiplicative Complexity and Nonlinearity -- Find Dual Connectedness of Edge-Bicolored Graphs and Beyond -- Combinatorial Voter Control in Elections -- An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas -- On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields -- Hitting forbidden subgraphs in graphs of bounded treewidth -- Probabilistic Analysis of Power Assignments -- Existence of Secure Equilibrium in Multi-Player Games with Perfect Information -- An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group -- A Note on the Minimum Distance of Quantum LDPC Codes -- Minimum Bisection is NP-hard on Unit Disk Graphs -- Query-Competitive Algorithms for Cheapest Set Problems under Uncertainty -- Streaming Kernelization -- A Reconfigurations Analogue of Brooks’ Theorem -- Intersection Graphs of L-Shapes and Segments in the Plane -- Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes -- Editing to a Connected Graph of Given Degrees -- Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth -- On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity -- New Results for Non-Preemptive Speed Scaling -- Lower bounds for splittings by linear combinations -- On the Complexity of List Ranking in the Parallel External Memory Model -- Knocking Out Pk-free Graphs -- Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis -- Affine consistency and the complexity of semilinear constraints -- Small complexity classes for computable analysis -- Two Results about Quantum Messages -- Parameterized Approximations via d-Skew-Symmetric Multicut -- On the Clique Editing Problem -- On the Complexity of Symbolic Verification and Decision Problems in Bit-Vector Logic -- Computational Complexity of Covering Three-Vertex Multigraphs -- Finding Maximum Common Biconnected Subgraphs in Series-Parallel Graphs -- On Coloring Resilient Graphs -- Document Retrieval with One Wildcard -- An Hn=2 Upper Bound on the Price of Stability of Undirected Network Design Games -- Traveling Salesman Problems in Temporal Graphs -- Inferring Strings from Lyndon factorization -- Betweenness Centrality - Incremental and Faster -- Deterministic Parameterized Algorithms for the Graph Motif Problem -- The Two Queries Assumption and Arthur-Merlin Classes -- Flexible Bandwidth Assignment with Application to Optical Networks -- Approximation Algorithms For Bounded Color Matchings via Convex Decompositions.
Record Nr. UNINA-9910483797303321
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2014
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Mathematical Foundations of Computer Science 2015 [[electronic resource] ] : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I / / edited by Giuseppe F Italiano, Giovanni Pighizzini, Donald T. Sannella
Mathematical Foundations of Computer Science 2015 [[electronic resource] ] : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I / / edited by Giuseppe F Italiano, Giovanni Pighizzini, Donald T. Sannella
Edizione [1st ed. 2015.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015
Descrizione fisica 1 online resource (XXVI, 459 p. 51 illus.)
Disciplina 004.0151
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Computer science—Mathematics
Discrete mathematics
Numerical analysis
Artificial intelligence—Data processing
Machine theory
Discrete Mathematics in Computer Science
Numerical Analysis
Data Science
Formal Languages and Automata Theory
Mathematical Applications in Computer Science
ISBN 3-662-48057-3
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Record Nr. UNISA-996200357803316
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui
Mathematical Foundations of Computer Science 2015 [[electronic resource] ] : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II / / edited by Giuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella
Mathematical Foundations of Computer Science 2015 [[electronic resource] ] : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II / / edited by Giuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella
Edizione [1st ed. 2015.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015
Descrizione fisica 1 online resource (XVII, 615 p. 58 illus.)
Disciplina 004.0151
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Computer science—Mathematics
Discrete mathematics
Numerical analysis
Artificial intelligence—Data processing
Machine theory
Discrete Mathematics in Computer Science
Numerical Analysis
Data Science
Formal Languages and Automata Theory
Mathematical Applications in Computer Science
ISBN 3-662-48054-9
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Intro -- Preface -- Conference Organization -- Contents - Part II -- Contents - Part I -- Near-Optimal Asymmetric Binary Matrix Partitions -- 1 Introduction -- 2 Preliminaries -- 3 The Uniform Case -- 4 Asymmetric Binary Matrix Partition as Welfare Maximization -- References -- Dual VP Classes -- 1 Introduction -- 1.1 ACC1 and TC1 -- 1.2 Algebraic Degree -- 1.3 Duality -- 2 Preliminaries, and Definitions of -classes -- 3 Subclasses of ACC1 -- 3.1 Comparing P and VP. -- 4 Threshold Circuits and Small Degree -- 4.1 Degree Reduction -- 5 Conclusions, Discussion, and Open Problems -- References -- On Tinhofer's Linear Programming Approach to Isomorphism Testing -- 1 Introduction -- 2 Amenable Graphs -- 3 Amenable Graphs Are Compact -- 4 A Color-Refinement Based Hierarchy of Graphs -- References -- On the Complexity of Noncommutative Polynomial Factorization -- 1 Introduction -- 2 Variable-Disjoint Factorization Problem -- 2.1 Uniqueness of Variable-Disjoint Factorization -- 2.2 Equivalence with PIT -- 2.3 Black-Box Variable-Disjoint Factorization Algorithm -- 3 Factorization of Multilinear and Homogeneous Polynomials -- 4 A Polynomial Decomposition Problem -- 5 Concluding Remarks and Open Problems -- References -- An Algebraic Proof of the Real Number PCP Theorem -- 1 Introduction -- 1.1 Problems with the Classical Proof and Outline -- 2 Basic Notions -- 2.1 Testing Trigonometric Polynomials -- 3 The Correctness Test -- 4 Segmented Almost Transparent Proofs for NPR -- References -- On the Complexity of Hub Labeling (Extended Abstract) -- 1 Introduction -- 2 Preliminaries -- 2.1 HL Approximation Algorithm -- 2.2 Greedy HHL Algorithms -- 3 HHL and Highway Dimension -- 4 Upper Bounds -- 5 Lower Bounds -- 6 NP-Hardness Proofs -- 6.1 Undirected Graphs -- 6.2 Directed Graphs -- 7 HL vs HHL -- 8 Concluding Remarks -- References.
On the Complexity of Speed Scaling -- 1 Introduction -- 2 Model and Notation -- 3 Hardness Results -- 3.1 Hardness of B-IDUA -- 4 Polynomial Time Algorithms -- 4.1 An Algorithm for FE-IDUU -- 4.2 An Algorithm for FE-ICUU -- 4.3 An Algorithm for FE-FCWA -- 5 Equivalence Reductions -- 5.1 Reducing B-ICUU to FE-ICUU -- 5.2 Reducing the Discrete to the Continuous Setting -- 5.3 Reducing from Budget to Flow Plus Energy for Fractional Flow -- References -- Almost All Functions Require Exponential Energy -- 1 Introduction -- 1.1 Our Contributions -- 1.2 Related Work -- 1.3 Formal Model -- 2 A Lower Bound on the Number of Functions Computable by a Circuit -- 2.1 Homogeneous Supply Voltages -- 2.2 Heterogeneous Supply Voltages -- 3 Almost All Functions Require Exponential Energy -- 3.1 Adaptation of Shannon's Argument -- 3.2 Homogeneous Supply Voltages -- 3.3 Heterogeneous Supply Voltages -- 4 Relating Energy and the Number of Faulty Gates -- References -- On Dynamic DFS Tree in Directed Graphs -- 1 Introduction -- 1.1 An Efficient Decremental Algorithm for a DFS Tree in a DAG -- 1.2 Lower Bounds on Dynamic DFS Tree -- 1.3 Organization of the Paper -- 2 Preliminaries -- 3 A Simple and Deterministic Decremental Algorithm -- 4 An Efficient Randomized Algorithm -- 4.1 Analysis of the Algorithm -- 5 Lower Bounds for Dynamic DFS Tree Problem -- 5.1 Maintaining Ordered DFS Tree Explicitly -- 5.2 Partial Dynamic Ordered DFS Tree and Static All-Pairs Reachability -- 6 Conclusion -- References -- Metric Dimension of Bounded Width Graphs -- 1 Introduction -- 2 Basic Definitions and Preliminaries -- 3 Metric Dimension on Graphs of Bounded Tree-Length and Max-Degree -- 3.1 Properties of Graphs of Bounded Tree-Length and Max-Degree -- 3.2 The Algorithm -- 4 Metric Dimension on Graphs of Bounded Modular-Width -- 5 Conclusions -- References -- Equality, Revisited.
1 Introduction -- 2 Our Results -- 3 The New Lower Bound Technique -- 4 Extensions -- 4.1 QR Protocols -- 4.2 The ``One Out of Two'' Problem -- 5 Lower Bounds -- 5.1 Bounds for NE -- 5.2 Bounds for EQ -- 6 Protocols -- 6.1 Tightness for NE and RRR Protocols -- 6.2 Tightness for QRQ and RRQ Protocols -- 7 Untrusted Quantum State Transfer -- 7.1 A Protocol -- 7.2 A Lower Bound -- 8 Discussion -- References -- Bounding the Clique-Width of H-free Chordal Graphs -- 1 Introduction -- 2 Preliminaries -- 3 New Classes of Bounded and Unbounded Clique-Width -- 4 Concluding Remarks -- References -- New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory -- 1 Introduction -- 1.1 Our Results -- 1.2 Related Work -- 2 Definitions and Results -- 2.1 Notations and Definitions -- 2.2 Lower Bound Techniques -- 3 An Upper Bound -- 4 Lower Bounds -- References -- QMA with Subset State Witnesses -- 1 Introduction -- 2 Preliminaries -- 2.1 Definitions -- 2.2 Complexity Classes and Complete Problems -- 3 Subset State Approximations -- 4 Alternative Characterisations of QMA -- 5 A QMA-Complete Problem Based on Subset States -- 6 On the Perfectly Complete Version of SQMA -- 7 Conclusions -- References -- Phase Transition for Local Search on Planted SAT -- 1 Preliminaries -- 2 Success of Local Search -- 3 Failure of Local Search -- References -- Optimal Bounds for Estimating Entropy with PMF Queries -- 1 Introduction -- 1.1 Our Results, and Comparison with Prior Work -- 2 Lower Bound for Estimating Shannon Entropy -- 3 Estimating Rényi Entropy -- 4 Lower Bound for Estimating Support Size -- 5 Concluding Remarks -- References -- Mutual Dimension and Random Sequences -- 1 Introduction -- 2 Mutual Dimension in Cantor Spaces -- 3 Mutual Dimension and Coupled Randomness -- 4 Billingsley Mutual Dimensions -- References.
Optimal Algorithms and a PTAS for Cost-Aware Scheduling -- 1 Introduction -- 2 Minimizing the Makespan on Unrelated Machines -- 3 Minimizing on a Single Machine -- 4 A PTAS for Minimizing Total Weighted Completion Time -- 4.1 Preliminaries and Scheduling in the Weight-Dimension -- 4.2 Dynamic Programming Algorithm -- 4.3 Trimming the State Space -- 5 Open Problems -- References -- Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases -- 1 Introduction -- 1.1 Our Results and Proof Techniques -- 1.2 Related Work -- 2 Preliminaries -- 3 Shrinkage Under Restrictions -- 3.1 Formula Simplification -- 3.2 Weight Reduction Under Restrictions -- 3.3 Upper Bounds on Formula Weights -- 3.4 Choice of Weight Parameters -- 4 A Satisfiability Algorithm -- 5 Average-Case Lower Bounds -- 6 Formulas over Unate Bases -- 7 Open Questions -- References -- Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem -- 1 Introduction -- 2 Preliminaries -- 3 Auxiliarely Communication Models: Shared and Imperfect Randomness -- 4 An Effective Protocol for Model 1 (Partially Shared Sources of Perfect Randomness) -- 4.1 Parameters of the Construction -- 4.2 The Scheme of the Protocol -- 4.3 Communication Complexity of the Protocol -- 5 An Effective Protocol for Model 2 -- 6 The Model with Private Sources of Perfect Randomness -- 7 Conclusion -- References -- Network Creation Games: Think Global -- Act Local -- 1 Introduction -- 2 Computational Hardness and Game Dynamics -- 3 Local versus Global Moves -- 4 The Quality of k-Local Equilibria -- 4.1 Conformity of k-Local and Nash Equilibria -- 4.2 The Price of Anarchy for Tree Networks -- 4.3 The Price of Anarchy for Non-tree Networks -- 5 Conclusion and Open Problems -- References -- Oblivious Transfer from Weakly Random Self-Reducible Public-Key Cryptosystem -- 1 Introduction.
2 Previous Work -- 3 Background Material -- 4 Random Self-Reducible Encryption Scheme -- 5 2()1-OT from a RSR Public-Key Cryptosystem -- 6 Weakly Random Self-Reducible Encryption -- 6.1 Instantiation of wRSR Public-Key Cryptosystems -- 6.2 Approximate Integer GCD -- 6.3 Learning with Errors (LWE) -- 7 Conclusion and Open Problem -- References -- Efficient Computations over Encrypted Data Blocks -- 1 Introduction -- 2 Definitions and Background -- 2.1 Efficient and Secure 2-Party Evaluation of Equality-Based Formulae -- 2.2 Protocols and Cryptographic Primitives Used in Our Solutions -- 3 Real-or-Random Conditional Transfer Protocols -- 3.1 An srCTeval Protocol for the Equality Predicate -- 3.2 An srCTeval Protocol for the AND-of-Equality Predicate -- 3.3 An srCTeval Protocol for the OR-of-Equality Predicate -- 4 Secure Evaluation of Equality-Based Monotone Formulae -- 5 Conclusions -- References -- Polynomial Kernels for Weighted Problems -- 1 Introduction -- 2 Preliminaries -- 3 Settling Open Problems via the Frank-Tardos Theorem -- 3.1 Frank and Tardos' Theorem -- 3.2 Polynomial Kernelization for Knapsack -- 4 Small Kernels for Weighted Parameterized Problems -- 4.1 Hitting Set and Set Packing -- 4.2 Max Cut -- 4.3 Polynomial Kernelization for Bin Packing with Additive Error -- 5 Kernel Bounds for Knapsack Problems -- 5.1 Exponential Kernel for Knapsack with Few Item Sizes -- 5.2 Polynomial Kernel for Subset Sum with Few Item Sizes -- 5.3 A Kernelization Lower Bound for Subset Sum -- 6 Integer Polynomial Programming with Bounded Range -- 7 Conclusion -- References -- A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time -- 1 Introduction -- 2 Preliminaries -- 3 Sunflowers and Flowers -- 4 Logspace Kernel for Hitting Set -- 5 Logspace Kernel for Set Packing -- 6 Linear-Time Kernels for Hitting Set and Set Packing.
7 Concluding Remarks.
Record Nr. UNISA-996200358103316
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui
Mathematical Foundations of Computer Science 2015 [[electronic resource] ] : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I / / edited by Giuseppe F Italiano, Giovanni Pighizzini, Donald T. Sannella
Mathematical Foundations of Computer Science 2015 [[electronic resource] ] : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I / / edited by Giuseppe F Italiano, Giovanni Pighizzini, Donald T. Sannella
Edizione [1st ed. 2015.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015
Descrizione fisica 1 online resource (XXVI, 459 p. 51 illus.)
Disciplina 004.0151
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Computer science—Mathematics
Discrete mathematics
Numerical analysis
Artificial intelligence—Data processing
Machine theory
Discrete Mathematics in Computer Science
Numerical Analysis
Data Science
Formal Languages and Automata Theory
Mathematical Applications in Computer Science
ISBN 3-662-48057-3
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Record Nr. UNINA-9910483974103321
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Mathematical Foundations of Computer Science 2015 [[electronic resource] ] : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II / / edited by Giuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella
Mathematical Foundations of Computer Science 2015 [[electronic resource] ] : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II / / edited by Giuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella
Edizione [1st ed. 2015.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015
Descrizione fisica 1 online resource (XVII, 615 p. 58 illus.)
Disciplina 004.0151
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Computer science—Mathematics
Discrete mathematics
Numerical analysis
Artificial intelligence—Data processing
Machine theory
Discrete Mathematics in Computer Science
Numerical Analysis
Data Science
Formal Languages and Automata Theory
Mathematical Applications in Computer Science
ISBN 3-662-48054-9
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Intro -- Preface -- Conference Organization -- Contents - Part II -- Contents - Part I -- Near-Optimal Asymmetric Binary Matrix Partitions -- 1 Introduction -- 2 Preliminaries -- 3 The Uniform Case -- 4 Asymmetric Binary Matrix Partition as Welfare Maximization -- References -- Dual VP Classes -- 1 Introduction -- 1.1 ACC1 and TC1 -- 1.2 Algebraic Degree -- 1.3 Duality -- 2 Preliminaries, and Definitions of -classes -- 3 Subclasses of ACC1 -- 3.1 Comparing P and VP. -- 4 Threshold Circuits and Small Degree -- 4.1 Degree Reduction -- 5 Conclusions, Discussion, and Open Problems -- References -- On Tinhofer's Linear Programming Approach to Isomorphism Testing -- 1 Introduction -- 2 Amenable Graphs -- 3 Amenable Graphs Are Compact -- 4 A Color-Refinement Based Hierarchy of Graphs -- References -- On the Complexity of Noncommutative Polynomial Factorization -- 1 Introduction -- 2 Variable-Disjoint Factorization Problem -- 2.1 Uniqueness of Variable-Disjoint Factorization -- 2.2 Equivalence with PIT -- 2.3 Black-Box Variable-Disjoint Factorization Algorithm -- 3 Factorization of Multilinear and Homogeneous Polynomials -- 4 A Polynomial Decomposition Problem -- 5 Concluding Remarks and Open Problems -- References -- An Algebraic Proof of the Real Number PCP Theorem -- 1 Introduction -- 1.1 Problems with the Classical Proof and Outline -- 2 Basic Notions -- 2.1 Testing Trigonometric Polynomials -- 3 The Correctness Test -- 4 Segmented Almost Transparent Proofs for NPR -- References -- On the Complexity of Hub Labeling (Extended Abstract) -- 1 Introduction -- 2 Preliminaries -- 2.1 HL Approximation Algorithm -- 2.2 Greedy HHL Algorithms -- 3 HHL and Highway Dimension -- 4 Upper Bounds -- 5 Lower Bounds -- 6 NP-Hardness Proofs -- 6.1 Undirected Graphs -- 6.2 Directed Graphs -- 7 HL vs HHL -- 8 Concluding Remarks -- References.
On the Complexity of Speed Scaling -- 1 Introduction -- 2 Model and Notation -- 3 Hardness Results -- 3.1 Hardness of B-IDUA -- 4 Polynomial Time Algorithms -- 4.1 An Algorithm for FE-IDUU -- 4.2 An Algorithm for FE-ICUU -- 4.3 An Algorithm for FE-FCWA -- 5 Equivalence Reductions -- 5.1 Reducing B-ICUU to FE-ICUU -- 5.2 Reducing the Discrete to the Continuous Setting -- 5.3 Reducing from Budget to Flow Plus Energy for Fractional Flow -- References -- Almost All Functions Require Exponential Energy -- 1 Introduction -- 1.1 Our Contributions -- 1.2 Related Work -- 1.3 Formal Model -- 2 A Lower Bound on the Number of Functions Computable by a Circuit -- 2.1 Homogeneous Supply Voltages -- 2.2 Heterogeneous Supply Voltages -- 3 Almost All Functions Require Exponential Energy -- 3.1 Adaptation of Shannon's Argument -- 3.2 Homogeneous Supply Voltages -- 3.3 Heterogeneous Supply Voltages -- 4 Relating Energy and the Number of Faulty Gates -- References -- On Dynamic DFS Tree in Directed Graphs -- 1 Introduction -- 1.1 An Efficient Decremental Algorithm for a DFS Tree in a DAG -- 1.2 Lower Bounds on Dynamic DFS Tree -- 1.3 Organization of the Paper -- 2 Preliminaries -- 3 A Simple and Deterministic Decremental Algorithm -- 4 An Efficient Randomized Algorithm -- 4.1 Analysis of the Algorithm -- 5 Lower Bounds for Dynamic DFS Tree Problem -- 5.1 Maintaining Ordered DFS Tree Explicitly -- 5.2 Partial Dynamic Ordered DFS Tree and Static All-Pairs Reachability -- 6 Conclusion -- References -- Metric Dimension of Bounded Width Graphs -- 1 Introduction -- 2 Basic Definitions and Preliminaries -- 3 Metric Dimension on Graphs of Bounded Tree-Length and Max-Degree -- 3.1 Properties of Graphs of Bounded Tree-Length and Max-Degree -- 3.2 The Algorithm -- 4 Metric Dimension on Graphs of Bounded Modular-Width -- 5 Conclusions -- References -- Equality, Revisited.
1 Introduction -- 2 Our Results -- 3 The New Lower Bound Technique -- 4 Extensions -- 4.1 QR Protocols -- 4.2 The ``One Out of Two'' Problem -- 5 Lower Bounds -- 5.1 Bounds for NE -- 5.2 Bounds for EQ -- 6 Protocols -- 6.1 Tightness for NE and RRR Protocols -- 6.2 Tightness for QRQ and RRQ Protocols -- 7 Untrusted Quantum State Transfer -- 7.1 A Protocol -- 7.2 A Lower Bound -- 8 Discussion -- References -- Bounding the Clique-Width of H-free Chordal Graphs -- 1 Introduction -- 2 Preliminaries -- 3 New Classes of Bounded and Unbounded Clique-Width -- 4 Concluding Remarks -- References -- New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory -- 1 Introduction -- 1.1 Our Results -- 1.2 Related Work -- 2 Definitions and Results -- 2.1 Notations and Definitions -- 2.2 Lower Bound Techniques -- 3 An Upper Bound -- 4 Lower Bounds -- References -- QMA with Subset State Witnesses -- 1 Introduction -- 2 Preliminaries -- 2.1 Definitions -- 2.2 Complexity Classes and Complete Problems -- 3 Subset State Approximations -- 4 Alternative Characterisations of QMA -- 5 A QMA-Complete Problem Based on Subset States -- 6 On the Perfectly Complete Version of SQMA -- 7 Conclusions -- References -- Phase Transition for Local Search on Planted SAT -- 1 Preliminaries -- 2 Success of Local Search -- 3 Failure of Local Search -- References -- Optimal Bounds for Estimating Entropy with PMF Queries -- 1 Introduction -- 1.1 Our Results, and Comparison with Prior Work -- 2 Lower Bound for Estimating Shannon Entropy -- 3 Estimating Rényi Entropy -- 4 Lower Bound for Estimating Support Size -- 5 Concluding Remarks -- References -- Mutual Dimension and Random Sequences -- 1 Introduction -- 2 Mutual Dimension in Cantor Spaces -- 3 Mutual Dimension and Coupled Randomness -- 4 Billingsley Mutual Dimensions -- References.
Optimal Algorithms and a PTAS for Cost-Aware Scheduling -- 1 Introduction -- 2 Minimizing the Makespan on Unrelated Machines -- 3 Minimizing on a Single Machine -- 4 A PTAS for Minimizing Total Weighted Completion Time -- 4.1 Preliminaries and Scheduling in the Weight-Dimension -- 4.2 Dynamic Programming Algorithm -- 4.3 Trimming the State Space -- 5 Open Problems -- References -- Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases -- 1 Introduction -- 1.1 Our Results and Proof Techniques -- 1.2 Related Work -- 2 Preliminaries -- 3 Shrinkage Under Restrictions -- 3.1 Formula Simplification -- 3.2 Weight Reduction Under Restrictions -- 3.3 Upper Bounds on Formula Weights -- 3.4 Choice of Weight Parameters -- 4 A Satisfiability Algorithm -- 5 Average-Case Lower Bounds -- 6 Formulas over Unate Bases -- 7 Open Questions -- References -- Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem -- 1 Introduction -- 2 Preliminaries -- 3 Auxiliarely Communication Models: Shared and Imperfect Randomness -- 4 An Effective Protocol for Model 1 (Partially Shared Sources of Perfect Randomness) -- 4.1 Parameters of the Construction -- 4.2 The Scheme of the Protocol -- 4.3 Communication Complexity of the Protocol -- 5 An Effective Protocol for Model 2 -- 6 The Model with Private Sources of Perfect Randomness -- 7 Conclusion -- References -- Network Creation Games: Think Global -- Act Local -- 1 Introduction -- 2 Computational Hardness and Game Dynamics -- 3 Local versus Global Moves -- 4 The Quality of k-Local Equilibria -- 4.1 Conformity of k-Local and Nash Equilibria -- 4.2 The Price of Anarchy for Tree Networks -- 4.3 The Price of Anarchy for Non-tree Networks -- 5 Conclusion and Open Problems -- References -- Oblivious Transfer from Weakly Random Self-Reducible Public-Key Cryptosystem -- 1 Introduction.
2 Previous Work -- 3 Background Material -- 4 Random Self-Reducible Encryption Scheme -- 5 2()1-OT from a RSR Public-Key Cryptosystem -- 6 Weakly Random Self-Reducible Encryption -- 6.1 Instantiation of wRSR Public-Key Cryptosystems -- 6.2 Approximate Integer GCD -- 6.3 Learning with Errors (LWE) -- 7 Conclusion and Open Problem -- References -- Efficient Computations over Encrypted Data Blocks -- 1 Introduction -- 2 Definitions and Background -- 2.1 Efficient and Secure 2-Party Evaluation of Equality-Based Formulae -- 2.2 Protocols and Cryptographic Primitives Used in Our Solutions -- 3 Real-or-Random Conditional Transfer Protocols -- 3.1 An srCTeval Protocol for the Equality Predicate -- 3.2 An srCTeval Protocol for the AND-of-Equality Predicate -- 3.3 An srCTeval Protocol for the OR-of-Equality Predicate -- 4 Secure Evaluation of Equality-Based Monotone Formulae -- 5 Conclusions -- References -- Polynomial Kernels for Weighted Problems -- 1 Introduction -- 2 Preliminaries -- 3 Settling Open Problems via the Frank-Tardos Theorem -- 3.1 Frank and Tardos' Theorem -- 3.2 Polynomial Kernelization for Knapsack -- 4 Small Kernels for Weighted Parameterized Problems -- 4.1 Hitting Set and Set Packing -- 4.2 Max Cut -- 4.3 Polynomial Kernelization for Bin Packing with Additive Error -- 5 Kernel Bounds for Knapsack Problems -- 5.1 Exponential Kernel for Knapsack with Few Item Sizes -- 5.2 Polynomial Kernel for Subset Sum with Few Item Sizes -- 5.3 A Kernelization Lower Bound for Subset Sum -- 6 Integer Polynomial Programming with Bounded Range -- 7 Conclusion -- References -- A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time -- 1 Introduction -- 2 Preliminaries -- 3 Sunflowers and Flowers -- 4 Logspace Kernel for Hitting Set -- 5 Logspace Kernel for Set Packing -- 6 Linear-Time Kernels for Hitting Set and Set Packing.
7 Concluding Remarks.
Record Nr. UNINA-9910483974003321
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Mathematical Insights into Advanced Computer Graphics Techniques [[electronic resource] /] / edited by Yoshinori Dobashi, Shizuo Kaji, Kei Iwasaki
Mathematical Insights into Advanced Computer Graphics Techniques [[electronic resource] /] / edited by Yoshinori Dobashi, Shizuo Kaji, Kei Iwasaki
Edizione [1st ed. 2019.]
Pubbl/distr/stampa Singapore : , : Springer Singapore : , : Imprint : Springer, , 2019
Descrizione fisica 1 online resource (163 pages)
Disciplina 006.60151
Collana Mathematics for Industry
Soggetto topico Engineering mathematics
Computer vision
Computer simulation
Mathematical and Computational Engineering
Computer Imaging, Vision, Pattern Recognition and Graphics
Mathematical Applications in Computer Science
Simulation and Modeling
ISBN 981-13-2850-1
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Mathematics in Computer Graphics -- Micro-Appearance Modeling of Fabrics -- Measuring the Light Reflectance with Mobile Devices -- Sparkling Effect in Virtual Reality Device -- Dappled tiling -- Procedural Non Uniform Cellular Noise -- Just Enough Non-Linearity -- An Efficient Cloud Simulation with Adaptive Grid Structure -- Recent Progress in Simulations of 3D Vortex Sheets with Surface Tension -- Physics-Based Computational Design for Digital Fabrication -- Design Tools in the Age of Personal Fabrication -- Clustering and Layout of Graphs with Attributed Nodes.
Record Nr. UNINA-9910350308803321
Singapore : , : Springer Singapore : , : Imprint : Springer, , 2019
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Mathematical Optimization Theory and Operations Research [[electronic resource] ] : 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5–10, 2021, Proceedings / / edited by Panos Pardalos, Michael Khachay, Alexander Kazakov
Mathematical Optimization Theory and Operations Research [[electronic resource] ] : 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5–10, 2021, Proceedings / / edited by Panos Pardalos, Michael Khachay, Alexander Kazakov
Edizione [1st ed. 2021.]
Pubbl/distr/stampa Cham : , : Springer International Publishing : , : Imprint : Springer, , 2021
Descrizione fisica 1 online resource (510 pages)
Disciplina 519.3
Collana Theoretical Computer Science and General Issues
Soggetto topico Computer science - Mathematics
Algorithms
Discrete mathematics
Artificial intelligence
Data structures (Computer science)
Information theory
Mathematics of Computing
Design and Analysis of Algorithms
Discrete Mathematics in Computer Science
Artificial Intelligence
Data Structures and Information Theory
Mathematical Applications in Computer Science
ISBN 3-030-77876-2
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Combinatorial Optimization -- Mathematical Programming -- Bilevel Optimization -- Scheduling Problems -- Game Theory and Optimal Control -- Operational Research and Mathematical Economics -- Data Analysis.
Record Nr. UNINA-9910485595203321
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2021
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Mathematical Optimization Theory and Operations Research [[electronic resource] ] : 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5–10, 2021, Proceedings / / edited by Panos Pardalos, Michael Khachay, Alexander Kazakov
Mathematical Optimization Theory and Operations Research [[electronic resource] ] : 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5–10, 2021, Proceedings / / edited by Panos Pardalos, Michael Khachay, Alexander Kazakov
Edizione [1st ed. 2021.]
Pubbl/distr/stampa Cham : , : Springer International Publishing : , : Imprint : Springer, , 2021
Descrizione fisica 1 online resource (510 pages)
Disciplina 519.3
Collana Theoretical Computer Science and General Issues
Soggetto topico Computer science - Mathematics
Algorithms
Discrete mathematics
Artificial intelligence
Data structures (Computer science)
Information theory
Mathematics of Computing
Design and Analysis of Algorithms
Discrete Mathematics in Computer Science
Artificial Intelligence
Data Structures and Information Theory
Mathematical Applications in Computer Science
ISBN 3-030-77876-2
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Combinatorial Optimization -- Mathematical Programming -- Bilevel Optimization -- Scheduling Problems -- Game Theory and Optimal Control -- Operational Research and Mathematical Economics -- Data Analysis.
Record Nr. UNISA-996464500703316
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2021
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui
Mathematical Optimization Theory and Operations Research [[electronic resource] ] : 19th International Conference, MOTOR 2020, Novosibirsk, Russia, July 6–10, 2020, Proceedings / / edited by Alexander Kononov, Michael Khachay, Valery A Kalyagin, Panos Pardalos
Mathematical Optimization Theory and Operations Research [[electronic resource] ] : 19th International Conference, MOTOR 2020, Novosibirsk, Russia, July 6–10, 2020, Proceedings / / edited by Alexander Kononov, Michael Khachay, Valery A Kalyagin, Panos Pardalos
Edizione [1st ed. 2020.]
Pubbl/distr/stampa Cham : , : Springer International Publishing : , : Imprint : Springer, , 2020
Descrizione fisica 1 online resource (492 pages)
Disciplina 519.3
Collana Theoretical Computer Science and General Issues
Soggetto topico Computer science—Mathematics
Computer science
Data structures (Computer science)
Information theory
Discrete mathematics
Computer networks
Mathematics of Computing
Theory of Computation
Mathematical Applications in Computer Science
Data Structures and Information Theory
Discrete Mathematics in Computer Science
Computer Communication Networks
ISBN 3-030-49988-X
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Discrete Optimization -- Mathematical Programming -- Game Theory -- Scheduling Problem -- Heuristics and Metaheuristics -- Operational Research Applications.
Record Nr. UNISA-996418281003316
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2020
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui