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 2012 [[electronic resource] ] : 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012, Proceedings / / edited by Branislav Rovan, Vladimiro Sassone, Peter Widmayer
Mathematical Foundations of Computer Science 2012 [[electronic resource] ] : 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012, Proceedings / / edited by Branislav Rovan, Vladimiro Sassone, Peter Widmayer
Edizione [1st ed. 2012.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2012
Descrizione fisica 1 online resource (XV, 825 p. 102 illus.)
Disciplina 005.1
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-642-32589-0
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto On the Complexity of Ontological Reasoning under Disjunctive -- Existential Rules -- New Races in Parameterized Algorithmics -- Scott Is Always Simple -- Simple Models for Recursive Schemes -- Unordered Constraint Satisfaction Games -- A Polynomial-Time Algorithm for Computing the Maximum Common -- Subgraph of Outerplanar Graphs of Bounded Degree -- Reductions to the Set of Random Strings: The Resource-Bounded Case -- Approximate Graph Isomorphism -- Near-Optimal Expanding Generator Sets for Solvable Permutation Groups -- Generating Functions of Timed Languages -- The Robust Set Problem: Parameterized Complexity and Approximation -- Mortality for 2 × 2 Matrices Is NP-Hard -- Solving Counter Parity Games -- Drawing Planar Graphs on Points Inside a Polygon -- Smoothed Complexity Theory -- Abelian Pattern Avoidance in Partial Words -- The Complexity of Rerouting Shortest Paths -- Computing with Large Populations Using Interactions -- Pancake Flipping Is Hard -- In-place Heap Construction with Optimized Comparisons, Moves, and Cache -- A Dichotomy Theorem for Homomorphism -- On the Impact of Fair Best Response Dynamics -- When Trees Grow Low: Shrubs and Fast MSO1 -- Obtaining Planarity by Contracting Few  Kernels for Edge Dominating Set -- Quasi-recognizable vs MSO Definable Languages of One-Dimensional -- Reversal Hierarchies for Small -- The Lower Reaches of Circuit Weakly-Synchronized Ground Tree Rewriting -- Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs -- Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games -- Maximum Cliques in Graphs with Small Intersection Number and Random Intersection -- Regularity Problems for Weak Pushdown ω-Automata and Games -- Computational Aspects of Cellular Automata on Countable Sofic Shifts -- On Two Stronger Versions of Dejean’s Conjecture -- A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments.
Record Nr. UNISA-996465486703316
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2012
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui
Mathematical Foundations of Computer Science 2013 [[electronic resource] ] : 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013, Proceedings / / edited by Krishnendu Chatterjee, Jirí Sgall
Mathematical Foundations of Computer Science 2013 [[electronic resource] ] : 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013, Proceedings / / edited by Krishnendu Chatterjee, Jirí Sgall
Edizione [1st ed. 2013.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013
Descrizione fisica 1 online resource (XVI, 854 p. 92 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-642-40313-1
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Alternation Trading Proofs and Their Limitations -- Bin Packing Games with Selfish Items -- A Constructive Proof of the Topological Kruskal Theorem -- Prior-Free Auctions of Digital Goods -- Clustering on k-Edge-Colored Graphs -- How to Pack Your Items When You Have to Buy Your Knapsack.-Computing Behavioral Distances, Compositionally -- Rewriting Guarded Negation Queries -- Parity Games and Propositional Proofs -- Bringing Order to Special Cases of Klee’s Measure Problem -- Learning Reductions to Sparse Sets -- Probabilistic Automata with Isolated Cut-Points -- On Stochastic Games with Multiple Objectives -- Paradigms for Parameterized Enumeration -- Noninterference with Local Policies -- Ordering Metro Lines by Block Crossings -- Meta-kernelization with Structural Parameters -- Polynomial Threshold Functions and Boolean Threshold Circuits -- Detecting Regularities on Grammar-Compressed Strings -- An Unusual Temporal Logic.
Record Nr. UNISA-996465710303316
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui
Mathematical Foundations of Computer Science 2013 : 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013, Proceedings / / edited by Krishnendu Chatterjee, Jirí Sgall
Mathematical Foundations of Computer Science 2013 : 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013, Proceedings / / edited by Krishnendu Chatterjee, Jirí Sgall
Edizione [1st ed. 2013.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013
Descrizione fisica 1 online resource (XVI, 854 p. 92 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-642-40313-1
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Alternation Trading Proofs and Their Limitations -- Bin Packing Games with Selfish Items -- A Constructive Proof of the Topological Kruskal Theorem -- Prior-Free Auctions of Digital Goods -- Clustering on k-Edge-Colored Graphs -- How to Pack Your Items When You Have to Buy Your Knapsack.-Computing Behavioral Distances, Compositionally -- Rewriting Guarded Negation Queries -- Parity Games and Propositional Proofs -- Bringing Order to Special Cases of Klee’s Measure Problem -- Learning Reductions to Sparse Sets -- Probabilistic Automata with Isolated Cut-Points -- On Stochastic Games with Multiple Objectives -- Paradigms for Parameterized Enumeration -- Noninterference with Local Policies -- Ordering Metro Lines by Block Crossings -- Meta-kernelization with Structural Parameters -- Polynomial Threshold Functions and Boolean Threshold Circuits -- Detecting Regularities on Grammar-Compressed Strings -- An Unusual Temporal Logic.
Record Nr. UNINA-9910484745903321
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013
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. UNISA-996198257903316
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2014
Materiale a stampa
Lo trovi qui: Univ. di Salerno
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 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. UNISA-996198257403316
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2014
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui
Mathematical Foundations of Computer Science 2014 : 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 : 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 : 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 : 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 : 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 : 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