- arXiv.org
- Space Physics
- Popular Physics
- Data Analysis, Statistics and Probability
- Physics and Society
- History and Philosophy of Physics
- Biological Physics
- Atomic and Molecular Clusters
- Optics
- Fluid Dynamics
- General Physics
- Plasma Physics
- Medical Physics
- Geophysics
- Atomic Physics
- Instrumentation and Detectors
- Classical Physics
- Computational Physics
- Chemical Physics
- Physics Education
- Accelerator Physics
- Atmospheric and Oceanic Physics

- Information Theory
- Number Theory
- Analysis of PDEs
- Statistics Theory
- Combinatorics
- Mathematical Physics
- Representation Theory
- Algebraic Geometry
- Operator Algebras
- Probability
- Complex Variables
- Group Theory
- History and Overview
- Symplectic Geometry
- Metric Geometry
- Numerical Analysis
- Optimization and Control
- Dynamical Systems
- General Topology
- Quantum Algebra
- Geometric Topology
- Differential Geometry
- General Mathematics
- Logic
- Commutative Algebra
- Functional Analysis
- Algebraic Topology
- K-Theory and Homology
- Rings and Algebras
- Category Theory
- Spectral Theory
- Classical Analysis and ODEs

- Operating Systems
- Symbolic Computation
- Information Theory
- Information Retrieval
- Formal Languages and Automata Theory
- Multiagent Systems
- Computational Complexity
- General Literature
- Computer Vision and Pattern Recognition
- Emerging Technologies
- Learning
- Software Engineering
- Social and Information Networks
- Numerical Analysis
- Neural and Evolutionary Computing
- Databases
- Sound
- Programming Languages
- Other Computer Science
- Cryptography and Security
- Distributed, Parallel, and Cluster Computing
- Digital Libraries
- Artificial Intelligence
- Computer Science and Game Theory
- Human-Computer Interaction
- Computational Engineering, Finance, and Science
- Systems and Control
- Discrete Mathematics
- Performance
- Mathematical Software
- Hardware Architecture
- Data Structures and Algorithms
- Computation and Language
- Multimedia
- Computers and Society
- Computational Geometry
- Graphics
- Logic in Computer Science
- Robotics
- Networking and Internet Architecture

- In this paper, we study the notion of admissibility for randomised strategies in concurrent games. Intuitively, an admissible strategy is one where the player plays `as well as possible', because there is no other strategy that dominates it, i.e., that wins (almost surely) against a super set of adversarial strategies. We prove that admissible strategies always exist in concurrent games, and we characterise them precisely. Then, when the objectives of the players are omega-regular, we show how to perform assume-admissible synthesis, i.e., how to compute admissible strategies that win (almost surely) under the hypothesis that the other players play admissible
- We consider the task of enumerating and counting answers to $k$-ary conjunctive queries against relational databases that may be updated by inserting or deleting tuples. We exhibit a new notion of q-hierarchical conjunctive queries and show that these can be maintained efficiently in the following sense. During a linear time preprocessing phase, we can build a data structure that enables constant delay enumeration of the query results; and when the database is updated, we can update the data structure and restart the enumeration phase within constant time. For the special case of self-join free conjunctive queries we obtain a dichotomy: if a query is not q-hierarchical, then query enumeration with sublinear$^\ast$ delay and sublinear update time (and arbitrary preprocessing time) is impossible. For answering Boolean conjunctive queries and for the more general problem of counting the number of solutions of k-ary queries we obtain complete dichotomies: if the query's homomorphic core is q-hierarchical, then size of the the query result can be computed in linear time and maintained with constant update time. Otherwise, the size of the query result cannot be maintained with sublinear update time. All our lower bounds rely on the OMv-conjecture, a conjecture on the hardness of online matrix-vector multiplication that has recently emerged in the field of fine-grained complexity to characterise the hardness of dynamic problems. The lower bound for the counting problem additionally relies on the orthogonal vectors conjecture, which in turn is implied by the strong exponential time hypothesis. $^\ast)$ By sublinear we mean $O(n^{1-\varepsilon})$ for some $\varepsilon>0$, where $n$ is the size of the active domain of the current database.
- Feb 22 2017 cs.LO arXiv:1702.06259v1We consider the problem of deciding the satisfiability of quantifier-free formulas in the theory of finite sets with cardinality constraints. Sets are a common high-level data structure used in programming; thus, such a theory is useful for modeling program constructs directly. More importantly, sets are a basic construct of mathematics and thus natural to use when formalizing the properties of computational systems. We develop a calculus describing a modular combination of a procedure for reasoning about membership constraints with a procedure for reasoning about cardinality constraints. Cardinality reasoning involves tracking how different sets overlap. For efficiency, we avoid considering Venn regions directly, as done in previous work. Instead, we develop a novel technique wherein potentially overlapping regions are considered incrementally as needed. We use a graph to track the interaction among the different regions. The calculus has been designed to facilitate its implementation within SMT solvers based on the DPLL(T) architecture. Initial experimental results demonstrate that the new techniques are competitive with previous techniques and scale much better on certain classes of problems.

A formally verified proof of the Central Limit Theorem

Zoltán Zimborás May 28 2014 04:42 UTC