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)
Algorithms – ESA 2013 [[electronic resource] ] : 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings / / edited by Hans L. Bodlaender, Giuseppe F. Italiano
Algorithms – ESA 2013 [[electronic resource] ] : 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings / / edited by Hans L. Bodlaender, Giuseppe F. Italiano
Edizione [1st ed. 2013.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013
Descrizione fisica 1 online resource (XVIII, 829 p. 134 illus.)
Disciplina 005.1
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Computer networks
Computer science—Mathematics
Discrete mathematics
Computer graphics
Numerical analysis
Artificial intelligence—Data processing
Computer Communication Networks
Discrete Mathematics in Computer Science
Computer Graphics
Numerical Analysis
Data Science
ISBN 3-642-40450-2
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Algorithm engineering -- Algorithmic aspects of networks -- Algorithmic game theory -- Approximation algorithms -- Computational biology -- Computational finance -- Computational geometry -- Combinatorial optimization -- Data compression -- Data structures -- Databases and information retrieval -- Distributed and parallel computing -- Graph algorithms -- Hierarchical memories -- Heuristics and meta-heuristics -- Mathematical programming -- Mobile computing -- On-line algorithms -- Parameterized complexity -- Pattern matching -- Quantum computing -- Randomized algorithms -- Scheduling and resource allocation problems -- Streaming algorithms.
Record Nr. UNISA-996465943803316
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui
Algorithms – ESA 2013 [[electronic resource] ] : 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings / / edited by Hans L. Bodlaender, Giuseppe F. Italiano
Algorithms – ESA 2013 [[electronic resource] ] : 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings / / edited by Hans L. Bodlaender, Giuseppe F. Italiano
Edizione [1st ed. 2013.]
Pubbl/distr/stampa Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013
Descrizione fisica 1 online resource (XVIII, 829 p. 134 illus.)
Disciplina 005.1
Collana Theoretical Computer Science and General Issues
Soggetto topico Algorithms
Computer networks
Computer science—Mathematics
Discrete mathematics
Computer graphics
Numerical analysis
Artificial intelligence—Data processing
Computer Communication Networks
Discrete Mathematics in Computer Science
Computer Graphics
Numerical Analysis
Data Science
ISBN 3-642-40450-2
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto Algorithm engineering -- Algorithmic aspects of networks -- Algorithmic game theory -- Approximation algorithms -- Computational biology -- Computational finance -- Computational geometry -- Combinatorial optimization -- Data compression -- Data structures -- Databases and information retrieval -- Distributed and parallel computing -- Graph algorithms -- Hierarchical memories -- Heuristics and meta-heuristics -- Mathematical programming -- Mobile computing -- On-line algorithms -- Parameterized complexity -- Pattern matching -- Quantum computing -- Randomized algorithms -- Scheduling and resource allocation problems -- Streaming algorithms.
Record Nr. UNINA-9910485025703321
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 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
Privacy Technologies and Policy [[electronic resource] ] : 7th Annual Privacy Forum, APF 2019, Rome, Italy, June 13–14, 2019, Proceedings / / edited by Maurizio Naldi, Giuseppe F. Italiano, Kai Rannenberg, Manel Medina, Athena Bourka
Privacy Technologies and Policy [[electronic resource] ] : 7th Annual Privacy Forum, APF 2019, Rome, Italy, June 13–14, 2019, Proceedings / / edited by Maurizio Naldi, Giuseppe F. Italiano, Kai Rannenberg, Manel Medina, Athena Bourka
Edizione [1st ed. 2019.]
Pubbl/distr/stampa Cham : , : Springer International Publishing : , : Imprint : Springer, , 2019
Descrizione fisica 1 online resource (XII, 211 p. 45 illus., 27 illus. in color.)
Disciplina 005.8
Collana Security and Cryptology
Soggetto topico Computers and civilization
Computer security
Application software
Operating systems (Computers)
Computers and Society
Systems and Data Security
Information Systems Applications (incl. Internet)
Security Services
Operating Systems
ISBN 3-030-21752-3
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Record Nr. UNINA-9910337836003321
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2019
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Privacy Technologies and Policy [[electronic resource] ] : 7th Annual Privacy Forum, APF 2019, Rome, Italy, June 13–14, 2019, Proceedings / / edited by Maurizio Naldi, Giuseppe F. Italiano, Kai Rannenberg, Manel Medina, Athena Bourka
Privacy Technologies and Policy [[electronic resource] ] : 7th Annual Privacy Forum, APF 2019, Rome, Italy, June 13–14, 2019, Proceedings / / edited by Maurizio Naldi, Giuseppe F. Italiano, Kai Rannenberg, Manel Medina, Athena Bourka
Edizione [1st ed. 2019.]
Pubbl/distr/stampa Cham : , : Springer International Publishing : , : Imprint : Springer, , 2019
Descrizione fisica 1 online resource (XII, 211 p. 45 illus., 27 illus. in color.)
Disciplina 005.8
Collana Security and Cryptology
Soggetto topico Computers and civilization
Computer security
Application software
Operating systems (Computers)
Computers and Society
Systems and Data Security
Information Systems Applications (incl. Internet)
Security Services
Operating Systems
ISBN 3-030-21752-3
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Record Nr. UNISA-996466328603316
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2019
Materiale a stampa
Lo trovi qui: Univ. di Salerno
Opac: Controlla la disponibilità qui
Proceedings of the 10th Italian Conference on Theoretical Computer Science, ICTS'07 [[electronic resource] ] : Rome, Italy, 3-5 October 2007 / / editors, Giuseppe F. Italiano, Eugenio Moggi, Luigi Laura
Proceedings of the 10th Italian Conference on Theoretical Computer Science, ICTS'07 [[electronic resource] ] : Rome, Italy, 3-5 October 2007 / / editors, Giuseppe F. Italiano, Eugenio Moggi, Luigi Laura
Pubbl/distr/stampa Singapore ; ; Hackensack, NJ, : World Scientific, c2007
Descrizione fisica xiii, 199 p. : ill
Disciplina 004
Altri autori (Persone) ItalianoGiuseppe F
MoggiEugenio
LauraLuigi
Soggetto topico Computer science
Computers
Soggetto genere / forma Electronic books.
ISBN 1-281-91164-X
9786611911645
981-277-099-2
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto pt. A. Invited talks. Clairvoyance and laziness for on line travelling agents / G. Ausiello. Proving the range property for Lambda theories and models / H. Barendregt. Can a proper Lambda-model have an R.E. equational theory? / C. Berline. Session centered calculi for service oriented computing / R. De Nicola. Symmetries in foundations / G. Longo -- pt. B. Regular contributions. On the approximability of dense Steiner tree problems / M. Hauptmann. Weak pattern matching in colored graphs: minimizing the number of connected components / R. Dondi, G. Fertin, and S. Vialette. Weak Markovian bisimilarity: abstracting from prioritized/weighted internal immediate actions / M. Bernardo and A. Aldini. Analyzing non-interference with respect to classes / D. Zanardini. Computing minimum directed feedback vertex set in O+(1.9977n) / I. Razgon. Seeing the trees and their branches in the network is hard / I.A. Kanj ... [et al.]. Modeling fuzzy behaviours in concurrent systems / L. D'Errico and M. Loreti. A formal framework for compositional compilation / D. Ancona and E. Zucca. Type inference for polymorphic mehods in Java-like languages / D. Ancona, G. Lagorio and E. Zucca. Sorting streamed multisets / T. Gagie. An analysis of a simple algorithm for random derangements / D. Merlini, R. Sprugnoli, and M. C. Verri. The measure hypothesis and efficiency of polynomial time approximation schemes / M. Hauptmann. Dichotomy results for fixed point counting in boolean dynamical systems / S. Kosub and C. M. Homan. Definable sets in weak Presburger arithmetic / C. Choffrut and A. Frigeri. On definite proofs of knowledge in the bare public-key model / G. Di Crescenzo and I. Visconti.
Record Nr. UNINA-9910450954403321
Singapore ; ; Hackensack, NJ, : World Scientific, c2007
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui
Proceedings of the 10th Italian Conference on Theoretical Computer Science, ICTS'07 [[electronic resource] ] : Rome, Italy, 3-5 October 2007 / / editors, Giuseppe F. Italiano, Eugenio Moggi, Luigi Laura
Proceedings of the 10th Italian Conference on Theoretical Computer Science, ICTS'07 [[electronic resource] ] : Rome, Italy, 3-5 October 2007 / / editors, Giuseppe F. Italiano, Eugenio Moggi, Luigi Laura
Pubbl/distr/stampa Singapore ; ; Hackensack, NJ, : World Scientific, c2007
Descrizione fisica xiii, 199 p. : ill
Disciplina 004
Altri autori (Persone) ItalianoGiuseppe F
MoggiEugenio
LauraLuigi
Soggetto topico Computer science
Computers
ISBN 1-281-91164-X
9786611911645
981-277-099-2
Formato Materiale a stampa
Livello bibliografico Monografia
Lingua di pubblicazione eng
Nota di contenuto pt. A. Invited talks. Clairvoyance and laziness for on line travelling agents / G. Ausiello. Proving the range property for Lambda theories and models / H. Barendregt. Can a proper Lambda-model have an R.E. equational theory? / C. Berline. Session centered calculi for service oriented computing / R. De Nicola. Symmetries in foundations / G. Longo -- pt. B. Regular contributions. On the approximability of dense Steiner tree problems / M. Hauptmann. Weak pattern matching in colored graphs: minimizing the number of connected components / R. Dondi, G. Fertin, and S. Vialette. Weak Markovian bisimilarity: abstracting from prioritized/weighted internal immediate actions / M. Bernardo and A. Aldini. Analyzing non-interference with respect to classes / D. Zanardini. Computing minimum directed feedback vertex set in O+(1.9977n) / I. Razgon. Seeing the trees and their branches in the network is hard / I.A. Kanj ... [et al.]. Modeling fuzzy behaviours in concurrent systems / L. D'Errico and M. Loreti. A formal framework for compositional compilation / D. Ancona and E. Zucca. Type inference for polymorphic mehods in Java-like languages / D. Ancona, G. Lagorio and E. Zucca. Sorting streamed multisets / T. Gagie. An analysis of a simple algorithm for random derangements / D. Merlini, R. Sprugnoli, and M. C. Verri. The measure hypothesis and efficiency of polynomial time approximation schemes / M. Hauptmann. Dichotomy results for fixed point counting in boolean dynamical systems / S. Kosub and C. M. Homan. Definable sets in weak Presburger arithmetic / C. Choffrut and A. Frigeri. On definite proofs of knowledge in the bare public-key model / G. Di Crescenzo and I. Visconti.
Record Nr. UNINA-9910777322203321
Singapore ; ; Hackensack, NJ, : World Scientific, c2007
Materiale a stampa
Lo trovi qui: Univ. Federico II
Opac: Controlla la disponibilità qui