This volume is based on the 2008 Clifford Lectures on Information Flow in Physics, Geometry and Logic and Computation, held March 12–15, 2008, at Tulane University in New Orleans, Louisiana. The varying perspectives...
详细信息
ISBN:
(数字)9780821890066
ISBN:
(纸本)9780821849231
This volume is based on the 2008 Clifford Lectures on Information Flow in Physics, Geometry and Logic and Computation, held March 12–15, 2008, at Tulane University in New Orleans, Louisiana. The varying perspectives of the researchers are evident in the topics represented in the volume, including mathematics, computer science, quantum physics and classical and quantum information. A number of the articles address fundamental questions in quantum information and related topics in quantum physics, using abstract categorical and domain-theoretic models for quantum physics to reason about such systems and to model spacetime. Readers can expect to gain added insight into the notion of information flow and how it can be understood in many settings. They also can learn about new approaches to modeling quantum mechanics that provide simpler and more accessible explanations of quantum phenomena, which don't require the arcane aspects of Hilbert spaces and the cumbersome notation of bras and kets.
Discrete mathematics and graph theory, including combinatorics, combinatorial optimization and networks. Preface Acknowledgments Region-Fault Tolerant Geometric Spanners, M. A. Abam, M. de Berg, M. Farshi, and J. Gudm...
ISBN:
(纸本)9780898716245
Discrete mathematics and graph theory, including combinatorics, combinatorial optimization and networks. Preface Acknowledgments Region-Fault Tolerant Geometric Spanners, M. A. Abam, M. de Berg, M. Farshi, and J. Gudmundsson A PTAS for TSP with Neighborhoods among Fat Regions in the Plane, Joseph S. B. Mitchell Optimal Dynamic Vertical Ray Shooting in Rectilinear Planar Subdivisions, Yoav Giyora and Haim Kaplan Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition, David Eppstein A Near Linear Time Constant Factor Approximation for Euclidean Bichromatic Matching (Cost), Piotr Indyk Compacting Cuts: A New Linear Formulation for Minimum Cut, Robert D. Carr, Goran Konjevod, Greg Little, Venkatesh Natarajan, and Ojas Parekh Linear Programming Relaxations of Maxcut, Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems, Moses Charikar, Konstantin Makarychev, and Yury Makarychev Improved Bounds for the Symmetric Rendezvous Value on the Line, Qiaoming Han, Donglei Du, Juan Vera, and Luis F. Zuluaga Efficient Solutions to Relaxations of Combinatorial Problems with Submodular Penalties via the Lovsz Extension and Non-smooth Convex Optimization, Fabin A. Chudak and Kiyohito Nagano Multiple Source Shortest Paths in a Genus g Graph, Sergio Cabello and Erin W. Chambers Obnoxious Centers in Graphs, Sergio Cabello and Gnter Rote Maximum Matching in Graphs with an Excluded Minor, Raphael Yuster and Uri Zwick Faster Dynamic Matchings and Vertex Connectivity, Piotr Sankowski Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi Analytic Combinatorics A Calculus of Discrete Structures, Philippe Flajolet Equilibria in Online Games,Roee Engelberg and Joseph (Seffi) Naor The Approximation Complexity of Win-Lose Games, Xi Chen, Shang-Hua Teng, and Paul Valiant Convergence to Approximat
This volume is based on lectures delivered at the 2011 AMS Short Course on Evolutionary Game Dynamics, held January 4–5, 2011 in New Orleans, Louisiana. Evolutionary game theory studies basic types of social interac...
详细信息
ISBN:
(纸本)0821853260;9780821853269
This volume is based on lectures delivered at the 2011 AMS Short Course on Evolutionary Game Dynamics, held January 4–5, 2011 in New Orleans, Louisiana. Evolutionary game theory studies basic types of social interactions in populations of players. It combines the strategic viewpoint of classical game theory (independent rational players trying to outguess each other) with population dynamics (successful strategies increase their frequencies). A substantial part of the appeal of evolutionary game theory comes from its highly diverse applications such as social dilemmas, the evolution of language, or mating behaviour in animals. Moreover, its methods are becoming increasingly popular in computer science, engineering, and control theory. They help to design and control multi-agent systems, often with a large number of agents (for instance, when routing drivers over highway networks or data packets over the Internet). While these fields have traditionally used a top down approach by directly controlling the behaviour of each agent in the system, attention has recently turned to an indirect approach allowing the agents to function independently while providing incentives that lead them to behave in the desired way. Instead of the traditional assumption of equilibrium behaviour, researchers opt increasingly for the evolutionary paradigm and consider the dynamics of behaviour in populations of agents employing simple, myopic decision rules.
A totally odd K-4-subdivision is a subdivision of K-4 where each subdivided edge has odd length The recognition of a totally odd K(4-)subdivision plays an important role in both graph theory and combinatorial optimiza...
详细信息
ISBN:
(纸本)9780898717013
A totally odd K-4-subdivision is a subdivision of K-4 where each subdivided edge has odd length The recognition of a totally odd K(4-)subdivision plays an important role in both graph theory and combinatorial optimization Sewell and Trottei [53], Zang [63] and Thomassen [60] independently conjectured the existence of a polynomial time recognition algorithm In this paper, we give the first polynomial time algorithm for solving this problem We also study the the parity two disjoint rooted paths problem whet e we determine if there exists two vertex disjoint paths of a specified parity between two pans of terminals Using a similar technique, we give an Oalgorithm for the parity two disjoint looted paths problem on an input graph G, whet alpha(vertical bar E(G)vertical bar,vertical bar V(G)vertical bar) is the inverse of the Ackermann function We note that this clearly gives ail algorithm for the well-known not-parity version of the two disjoint rooted paths pi oblem [19, 50, 52, 55, 58] We then extend our approach to give a polynomial time algorithm which determines, for any fixed k, whether there exists a cycle of a given parity through k independent input edges This generalizes the non-parity version of the algorithm in [22] Thomassen [61] gave a polynomial algorithm for the case k = 2 and hoped to use this algorithm to recognize a totally odd K-4-subdivision Our algorithm runs in O(vertical bar E(G)vertical bar V(G)vertical bar alpha(vertical bar E(G)vertical bar, vertical bar V(G)vertical bar)) for any fixed k Finally, we give an O(vertical bar V(G)vertical bar)(2) + (vertical bar E(G)vertical bar V(G)vertical bar alpha(vertical bar E(G)vertical bar, vertical bar V(G)vertical bar)) algorithm to decide whether a graph contains k disjoint paths from A to 13 (with vertical bar A vertical bar = vertical bar B vertical bar = 1,0 that are not all of the same parity This answers a conjecture of Thomassen [60] This problem arises from the study of totally odd-K4-subdivisio
In a graph C with non-negative edge lengths, let P be a shortest path horn a vertex s to a vertex t We consider the problem of computing, for each edge c on P. the length of a shot test path in C horn s to t that avoi...
详细信息
ISBN:
(纸本)9780898717013
In a graph C with non-negative edge lengths, let P be a shortest path horn a vertex s to a vertex t We consider the problem of computing, for each edge c on P. the length of a shot test path in C horn s to t that avoids e This is known as the replacement paths problem We give a linear-space algorithm with O(n log n) running time for n-vertex planar directed graphs The previous best, time bound was O(n log(2) n)
We study the dynamic membership problem, one of the most fundamental data structure problems, in the cell probe model with an arbitrary cell size We consider a cell probe model equipped with a cache that consists of a...
详细信息
ISBN:
(纸本)9780898717013
We study the dynamic membership problem, one of the most fundamental data structure problems, in the cell probe model with an arbitrary cell size We consider a cell probe model equipped with a cache that consists of at least a constant number of cells, reading or writing the cache is free of charge. For nearly all common data structures, it is known that with sufficiently large cells together with the cache, we can significantly lower the amortized update cost to o(1). In this paper, we show that this is not the case for the dynamic membership problem. Specifically, for any deterministic membership data structure under a random input sequence, if the expected average query cost is no more than 1+delta for some small constant delta, we prove that the expected amortized update cost must be at least Omega(1), namely, it does not benefit from large block writes (and a cache). The space the structure uses is irrelevant to this lower bound. We also extend this lower bound to randomized membership structures, by using a variant of Yao's minimax principle Finally, we show that the structure cannot do better even if it is allowed to answer a query mistakenly with a small constant probability.
We present a new optimization technique that yields the first FPTAS for several geometric problems These problems reduce to optimizing a sum of non-negative, constant description-complexity algebraic functions We firs...
详细信息
ISBN:
(纸本)9780898717013
We present a new optimization technique that yields the first FPTAS for several geometric problems These problems reduce to optimizing a sum of non-negative, constant description-complexity algebraic functions We first give a FPTAS for optimizing such a sum of algebraic functions, and then we apply it, to several geometric optimization problems We obtain the first, FPTAS for two fundamental geometric shape matching problems in fixed dimension: maximizing the volume of over lap of two polyhedra uncle, rigid motions, and minimizing their symmetric difference We obtain the first FPTAS for other problems in fixed dimension, such as computing an optimal ray in a weighted subdivision, finding the largest axially symmetric subset of a. polyhedron, and computing minimum area hulls
We design and analyze an on-line reordering buffer management algorithm with improved O (log k/log log k) competitive ratio for non-uniform costs, where k is the buffer size. This improves on the best previous result ...
详细信息
ISBN:
(纸本)9780898717013
We design and analyze an on-line reordering buffer management algorithm with improved O (log k/log log k) competitive ratio for non-uniform costs, where k is the buffer size. This improves on the best previous result (even for uniform costs) of Englert and Westermann (ICALP 2005) giving O(log k) competitive ratio, which was also the best (off-line) polynomial time approximation guarantee for this problem. Our analysis is based on an intricate dual fitting argument using a linear programming relaxation for the problem that we introduce in this paper.
暂无评论