2,198,825 research outputs found
Adversarial scheduling analysis of Game-Theoretic Models of Norm Diffusion.
Get PDFIn (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
Alianza Hispano Americano, San Gabriel, circa 1930
No full textSixteen memebers of the Alianza Hispano Americano, many wearing the A.H.A. club scarf, at the San Gabriel Lodge
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
Lincoln School class photo, San Gabriel, 1937
No full textElementary class, 36 children and one teacher (far left), assembled in front of the Art Deco-styled Lincoln School, San Gabriel; handwritten on photo: 4-1-37 Carson #32 (upper left); Velia Nava (bottom border)
Kernelization, Proof Complexity and Social Choice
Get PDFWe 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
Dr. Gabriel dressed in white standing in front of the Court House, Gundagai, New South Wales [picture] /
No full textPart of the collection: Gundagai photograph collection, 1887-1927.; Title devised from acquisitions documentation.; "GBU123 Dr. Gabriel in front of the courthouse. He is wearing white as a symbol of mourning for his wife."--Note in compactus card.; Also available online at: http://nla.gov.au/nla.pic-an8526479-595; GBU123
gabriel-milan/sotaque-brasileiro: Sotaque Brasileiro
No full textCommits
39f3052: bump version (Gabriel Gazola Milan
The Gabriel-Roiter measure for representation-finite hereditary algebras
Get PDFChen B. The Gabriel-Roiter measure for representation-finite hereditary algebras. Bielefeld (Germany): Bielefeld University; 2006
Specimen historicum de vetere Carelia ante occupationem Svecanam. Quod cons. ampl. fac. philos. Aboëns. Publico examini modeste subjiciunt auctor Gabriel Rein, amanuensis ad bibl. acad. extraordinarius & respondens Johannes Gabriel Norring, stip. publ. Wiburgenses. Sectionis primae p. I. In audit. philos. die 26 Februarii 1825. h. a. m. c.
No full textPainovuosi nimekkeestä.Dedikaatio: Ericus Gabriel Melartin [lat. pr.].Arkit: 1 arkintunnukseton lehti, A-B4 C2
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
- …
