115 research outputs found
Adversarial scheduling analysis of Game-Theoretic Models of Norm Diffusion.
No full textIn (Istrate et al. SODA 2001) we advocated the investigation of robustness of results in the theory of learning in games under adversarial scheduling models. We provide evidence that such an analysis is feasible and can lead to nontrivial results by investigating, in an adversarial scheduling setting, Peyton Young's model of diffusion of norms . In particular, our main result incorporates contagion into Peyton Young's model.evolutionary games, stochastic stability, adversarial scheduling
On the heapability of finite partial orders
No full textWe investigate the partitioning of partial orders into a minimal number of
heapable subsets. We prove a characterization result reminiscent of the proof
of Dilworth's theorem, which yields as a byproduct a flow-based algorithm for
computing such a minimal decomposition. On the other hand, in the particular
case of sets and sequences of intervals we prove that this minimal
decomposition can be computed by a simple greedy-type algorithm. The paper ends
with a couple of open problems related to the analog of the Ulam-Hammersley
problem for decompositions of sets and sequences of random intervals into
heapable sets
Kernelization, Proof Complexity and Social Choice
No full textWe display an application of the notions of kernelization and data reduction from parameterized complexity to proof complexity: Specifically, we show that the existence of data reduction rules for a parameterized problem having (a). a small-length reduction chain, and (b). small-size (extended) Frege proofs certifying the soundness of reduction steps implies the existence of subexponential size (extended) Frege proofs for propositional formalizations of the given problem.
We apply our result to infer the existence of subexponential Frege and extended Frege proofs for a variety of problems. Improving earlier results of Aisenberg et al. (ICALP 2015), we show that propositional formulas expressing (a stronger form of) the Kneser-Lovász Theorem have quasipolynomial size Frege proofs for each constant value of the parameter k.
Another notable application of our framework is to impossibility results in computational social choice: we show that, for any fixed number of agents, propositional translations of the Arrow and Gibbard-Satterthwaite impossibility theorems have subexponential size Frege proofs
Satisfying Assignments of Random Boolean Constraint Satisfaction Problems: Clusters and Overlaps
No full textThe distribution of overlaps of solutions of a random constraint satisfaction problem (CSP) is an indicator of the overall geometry of its solution space. For random k-SAT, nonrigorous methods from Statistical Physics support the validity of the one step replica symmetry breaking approach. Some of these predictions were rigorously confirmed in [Mézard et al. 2005a] [Mézard et al. 2005b]. There it is proved that the overlap distribution of random k-SAT, k ≥ 9, has discontinuous support. Furthermore, Achlioptas and Ricci-Tersenghi [Achlioptas and Ricci-Tersenghi 2006] proved that, for random k-SAT, k ≥ 8, and constraint densities close enough to the phase transition: - there exists an exponential number of clusters of satisfying assignments. - the distance between satisfying assignments in different clusters is linear. We aim to understand the structural properties of random CSP that lead to solution clustering. To this end, we prove two results on the cluster structure of solutions for binary CSP under the random model from [Molloy 2002]: 1. For all constraint sets S (described in [Creignou and Daudé 2004, Istrate 2005]) such that SAT (S) has a sharp threshold and all q ∈ (0, 1], q-overlap-SAT (S) has a sharp threshold. In other words the first step of the approach in [Mézard et al. 2005a] works in all nontrivial cases. 2. For any constraint density value c < 1, the set of solutions of a random instance of 2-SAT form with high probability a single cluster. Also, for and any q ∈ (0, 1] such an instance has with high probability two satisfying assignment of overlap ~ q. Thus, as expected from Statistical Physics predictions, the second step of the approach in [Mézard et al. 2005a] fails for 2-SAT
Adversarial scheduling analysis of Game-Theoretic Models of Norm Diffusion.
No full textIn (Istrate et al. SODA 2001) we advocated the investigation of robustness of results in the theory of learning in games under adversarial scheduling models. We provide evidence that such an analysis is feasible and can lead to nontrivial results by investigating, in an adversarial scheduling setting, Peyton Young's model of diffusion of norms . In particular, our main result incorporates contagion into
Peyton Young's model
Counting preimages of TCP reordering patterns
No full textAbstractPacket reordering is an important property of network traffic that should be captured by analytical models of the Transmission Control Protocol (TCP). We study a combinatorial problem motivated by Restored [G. Istrate, A. Hansson, S. Thulasidasan, M. Marathe, C. Barrett, Semantic compression of TCP traces, in: F. Boavida (Ed.), Proceedings of the Fifth IFIP NETWORKING Conference, in: Lecture Notes in Computer Science, vol. 3976, Springer-Verlag, 2006, pp. 123–135], a TCP modeling methodology that incorporates information about packet dynamics. A significant component of this model is a many-to-one mapping B that transforms sequences of packet IDs into buffer sequences in a manner that is compatible with TCP semantics. We obtain the following results: •We give an easy necessary and sufficient condition for an input sequence W to be valid (i.e. A∈B−1(W) for some permutation A of {1,2,…,n}), and a linear time algorithm that, given a valid buffer sequence W of length n, constructs a permutation A in the preimage of W.•We show that the problem of counting the number of permutations in B−1(W) has a polynomial time algorithm.•We also show how to extend these results to sequences of IDs that contain repeated packets
The Maximum Binary Tree Problem
No full textWe introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree in a given graph. MBT is a natural variant of the well-studied longest path problem, since both can be viewed as finding a maximum-sized tree of bounded degree in a given graph.
The connection to longest path motivates the study of MBT in directed acyclic graphs (DAGs), since the longest path problem is solvable efficiently in DAGs. In contrast, we show that MBT in DAGs is in fact hard: it has no efficient exp(-O(log n/ log log n))-approximation algorithm under the exponential time hypothesis, where n is the number of vertices in the input graph. In undirected graphs, we show that MBT has no efficient exp(-O(log^0.63 n))-approximation under the exponential time hypothesis. Our inapproximability results rely on self-improving reductions and structural properties of binary trees. We also show constant-factor inapproximability assuming P ≠ NP.
In addition to inapproximability results, we present algorithmic results along two different flavors: (1) We design a randomized algorithm to verify if a given directed graph on n vertices contains a binary tree of size k in 2^k poly(n) time. (2) Motivated by the longest heapable subsequence problem, introduced by Byers, Heeringa, Mitzenmacher, and Zervas, ANALCO 2011, which is equivalent to MBT in permutation DAGs, we design efficient algorithms for MBT in bipartite permutation graphs
Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
No full textA heapable sequence is a sequence of numbers that can be arranged in a min-heap data structure. Finding a longest heapable subsequence of a given sequence was proposed by Byers, Heeringa, Mitzenmacher, and Zervas (ANALCO 2011) as a generalization of the well-studied longest increasing subsequence problem and its complexity still remains open. An equivalent formulation of the longest heapable subsequence problem is that of finding a maximum-sized binary tree in a given permutation directed acyclic graph (permutation DAG). In this work, we study parameterized algorithms for both longest heapable subsequence and maximum-sized binary tree. We introduce alphabet size as a new parameter in the study of computational problems in permutation DAGs and show that this parameter with respect to a fixed topological ordering admits a complete characterization and a polynomial time algorithm. We believe that this parameter is likely to be useful in the context of optimization problems defined over permutation DAGs
Resource-Bounded Measure and Autoreducibility
No full textWe prove that the following classes have resource-bounded measure zero: ffl the class of self-reducible sets. ffl the class of commitable sets. ffl the class of sets that are non-adaptively autoreducible with a linear number of queries. ffl the class of disjunctively autoreducible sets. 1 Introduction Autoreducibility and a number of more restrictive properties having the same flavor (such as (disjunctive) self-reducibility, paddability [BH77], commitability [KB91]) have been useful in investigating issues like the structure of complete sets [BT94], of languages that reduce to "easy" sets [BvHT93], the isomorphism conjecture, etc. However a big number of questions about them are still open. For instance, while every P T -complete set for NP is autoreducible [BvHT93], it is not known whether all P tt -complete sets for NP are non-adaptively autoreducible (see [BT94] for other related open problems). One way to get around was to look for relative results, that is, to seek comp..
- …
