4,961 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
Gabriel Ajak Lat
No full textabstract: Gabriel was ten years old when he left his village.
“Lost Boys Found” is an ongoing, interdisciplinary project that is collecting, recording and archiving the oral histories of the Lost Boys/Girls of Sudan. The collection is a work-in-progress, seeking to record the oral history of as many Lost Boys/Girls as are willing, and will be used in a future book.Age: 27Region: Bahr al GhazalThis picture and bio was donated to the Lost Boys Found project from The Arizona Lost Boys Cente
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
Providence College Faculty Author Series 2013-2014: Fr. Gabriel Pivarnik
No full textIn this installment, Fr. Gabriel Pivarnik discusses his book Toward a Trinitarian Theology of Liturgical Participation and his reflections on the history of active participation within the Catholic Church
Providence College Faculty Author Series 2013-2014: Fr. Gabriel Pivarnik
No full textIn this installment, Fr. Gabriel Pivarnik discusses his book Toward a Trinitarian Theology of Liturgical Participation and his reflections on the history of active participation within the Catholic Church
Manuscript Poem "John Keats" by Dante Gabriel Rossetti
No full textabstract: Concerning the manuscript for "John Keats".Publication Details: Not the same version as some published versions of "John Keats."Curator's Note: Handwriting in upper right corner reads "Rossetti's Handwriting." Writing on verso reads "Dante Gabriel Rossetti. Mss.
British Museum Reader's Ticket of Dante Gabriel Rossetti
No full textabstract: Concerning a Reader's Ticket of Dante Gabriel Rossetti.Transcription Details: Card reads:
Poet's article 8 {? Nap.} /661
{?dilk Gllucci}
Aug 10 DG RossettiCreation Date Details: Undated range is the author's lifespan. Date and month listed on ticket read "Aug 10.
- …
