267 research outputs found
Equi-Rank Homomorphism Preservation Theorem on Finite Structures
No full textThe Homomorphism Preservation Theorem (HPT) of classical model theory states that a first-order sentence is preserved under homomorphisms if, and only if, it is equivalent to an existential-positive sentence. This theorem remains valid when restricted to finite structures, as demonstrated by the author in [Rossman, 2008; Rossman, 2017] via distinct model-theoretic and circuit-complexity based proofs. In this paper, we present a third (and significantly simpler) proof of the finitary HPT based on a generalized Cai-Fürer-Immerman construction. This method establishes a tight correspondence between syntactic parameters of a homomorphism-preserved sentence (quantifier rank, variable width, alternation height) and structural parameters of its minimal models (tree-width, tree-depth, decomposition height). Consequently, we prove a conjectured "equi-rank" version of the finitary HPT. In contrast, previous versions of the finitary HPT possess additional properties, but incur blow-ups in the quantifier rank of the equivalent existential-positive sentence
Rossman_online_supplement – Supplemental material for It’s Only Wrong If It’s Transactional: Moral Perceptions of Obfuscated Exchange
No full textSupplemental material, Rossman_online_supplement for It’s Only Wrong If It’s Transactional: Moral Perceptions of Obfuscated Exchange by Oliver Schilke and Gabriel Rossman in American Sociological Review</p
sj-pdf-1-asr-10.1177_00031224241232599 – Supplemental material for Honor among Crooks: The Role of Trust in Obfuscated Disreputable Exchange
No full textSupplemental material, sj-pdf-1-asr-10.1177_00031224241232599 for Honor among Crooks: The Role of Trust in Obfuscated Disreputable Exchange by Oliver Schilke and Gabriel Rossman in American Sociological Review</p
Glory and Gore
No full text Who’s the most important character in the Iliad? That depends. Using the poem, Rossman illustrates how to understand related but conceptually distinct concepts through social network analysis. </jats:p
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity
No full textPrevious work of the author [Rossmann'08] showed that the Homomorphism Preservation Theorem of classical model theory remains valid when its statement is restricted to finite structures. In this paper, we give a new proof of this result via a reduction to lower bounds in circuit complexity, specifically on the AC0 formula size of the colored subgraph isomorphism problem. Formally, we show the following: if a first-order sentence of quantifier-rank k is preserved under homomorphisms on finite structures, then it is equivalent on finite structures to an existential-positive sentence of quantifier-rank poly(k). Quantitatively, this improves the result of [Rossmann'08], where the upper bound on quantifier-rank is a non-elementary function of k
Criticality of Regular Formulas
No full textWe define the criticality of a boolean function f : {0,1}^n -> {0,1} as the minimum real number lambda >= 1 such that Pr [DT_{depth}(f|R_p) >= t] = k.
In an unpublished manuscript [Rossmann, 2018], the author showed that a combination of Håstad’s switching and multi-switching lemmas [Håstad, 1986; Håstad, 2014] implies that AC^0 circuits of depth d+1 and size s have criticality at most O(log s)^d. In the present paper, we establish a stronger O(1/d log s)^d bound for regular formulas: the class of AC^0 formulas in which all gates at any given depth have the same fan-in. This result is based on
(i) a novel switching lemma for bounded size (unbounded width) DNF formulas, and
(ii) an extension of (i) which analyzes a canonical decision tree associated with an entire depth-d formula.
As corollaries of our criticality bound, we obtain an improved #SAT algorithm and tight Linial-Mansour-Nisan Theorem for regular formulas, strengthening previous results for AC^0 circuits due to Impagliazzo, Matthews, Paturi [Impagliazzo et al., 2012] and Tal [Tal, 2017]. As a further corollary, we increase from o(log n /(log log n)) to o(log n) the number of quantifier alternations for which the QBF-SAT (quantified boolean formula satisfiability) algorithm of Santhanam and Williams [Santhanam and Williams, 2014] beats exhaustive search
Televisions, Physicians, and Life Expectancy
No full textThis article, created by Allan Rossman of Dickinson College, describes a dataset on life expectancies, densities of people per television set, and densities of people per physician in various countries of the world. The example addresses correlation versus causation and data transformations. The author states that "the example has proven very useful for helping students to discover the fundamental principle that correlation does not imply causation."
Gettin’ Down on “Friday”
No full text Rebecca Black’s “Friday” may be annoying and ubiquitous, but it’s also a great example of contemporary cultural production. The author explores the making of a meme and the many hands behind a hit. </jats:p
Recommended from our members
Unpacking Twaweza's Theory of Social Change: Citizen Agency, Information, Accountability, and Basic Services
No full textAny reference to or quotation from this document must include the following citation: Miller, E., Hartwell, A. S., & Rossman, G. B. (2010). Unpacking Twaweza’s Theory of Social Change: Citizen Agency, Information, Accountability, and Basic Services: Critical Issues and Questions. Amherst, MA: Center for International Education.
Contact author: Gretchen B. Rossman, [email protected].
This document was supported through the Twaweza Monitoring & Evaluation contract between the Center for International Education, University of Massachusetts Amherst, and Twaweza/Hivos Foundation, Dar es Salaam, Tanzania. The ideas within are the authors; no official endorsement should be inferred.The purpose of this paper is to define the key concepts – and links between them – of Twaweza’s Theory of Social Change. These are the notions of citizen-driven change, citizen agency, information, monitoring and accountability, and basic services. The analysis shows ambiguities and, at times, conflicting working definitions in Twaweza’s use of these terms in its major public documents. We then integrate relevant scholarship to elaborate these central ideas and to pose questions that Twaweza may engage with in the spirit of its claims to be a “learning organization.
Recommended from our members
Allegations of Affection: The Impact of Rumored Ties on Short Cycles, Node Sexuality, and Age-Gapped Pairings in a Celebrity Romantic Relationship Network
No full textUsing a novel dataset of sexual and romantic celebrity relationship histories from whosdatedwho.com, I conduct a 3-part analysis of how rumored ties highlight counter-normative behavior and violate structural network heuristics. Rumored ties about celebrities are produced within social exchanges as a hybrid of gossip and rumor and are useful for highlighting counter-normative behavior violating expected tie formation. I define gossip and rumors and situate discussions about celebrities as a hybrid form of these related concepts. I explain the implications of gossip and rumor’s ability to transmit information about normative violations when these claims are modeled as network ties. Finally, I discuss age gap norms and how these vary based on relationship context and age-gender pairings (e.g., older man-younger woman, etc.).Analysis 1 examines the structural impact of rumored ties in the context of short cycle and sexuality norms in heterosexual networks using Random Tie Deletion Resampling (RTDR; a combined social network analysis and bootstrapping method). Rumored tie inclusion increases short cycles, increases bisexual nodes, and decreases overall network sexuality. Analysis 2’s motif analysis identifies common gender, edge sexuality, and rumored tie combinations. Female bisexuality is key to short cycle construction and rumored ties usually occur as just one edge within these structures. Analysis 3 examines age gaps and variation in age gaps by relationship type and older partner’s gender. Rumored ties are strongly associated with short-term relationships and older women’s involvement. Hence, rumored ties violate specific norms for age gaps, “over-closeness” in short cycles, and “discordance” in sexuality.I discuss my findings within a framework of rumors and gossip as statements built from competing concerns about recognizability, plausibility, and salaciousness. I explore this framework by examining age gaps and zodiac incompatibility as similarly plausible occurrences with varying normative recognizability. Rumored ties are more associated with more recognizable age gap norms than less recognizable zodiac norms. My findings indicate gossip and rumor actively balance the recognizability, plausibility, and salaciousness of rumored tie claims. Thus, rumored ties matter as they shape network structures, illustrate norms, and illuminate how we assess and perceive counter-normativity in exchanges of gossip and rumor
- …
