Monday, October 02, 2017

04:45 pm
- 06:00 pm

Logic Seminar

Exley Science Center Tower ESC 638

Monday, September 26, 2016

04:45 pm
- 06:00 pm

Logic Seminar

Philip Scowcroft, Wes: " Abelian
lattice-ordered groups with at most finitely many pairwise disjoint elements." Abstract : Conrads
characterization (1960) of the lattice-ordered groups with at most finitely
many pairwise disjoint elements yields model-completions for various theories
of such groups. A corresponding Nullstellensatz, and various
quantifier-elimination results, assume stronger forms when restricted to
special groups in the class.

Exley Science Center Tower ESC 638

Monday, November 09, 2015

04:45 pm
- 06:00 pm

Logic Seminar, Bill Calhoun (Bloomsburg University): "Triviality and lowness for K-reducibility and related reducibilities"

n 2 !,
where K is prefix-free Kolmogorov complexity. The set A is low
for K
if KA(y) = K(y)+O(1) for y 2 2<!. These definitions seem quite
different.
K-triviality indicates that initial segments of A have the lowest
possible
complexity, while lowness for K indicates that A is too weak as
an
oracle to reduce the complexity of any string. The remarkable equivalence
of
the two definitions was shown by Nies [2]. Replacing prefix-free
complexity
by monotone complexity in the definition of K-trivial, we obtain
the Km-trivial
sets. Every K-trivial set is Km-trivial and all Turing
degrees
_ 00 contain a Km-trivial set [1]. Yet, not every Turing degree
contains
a Km-trivial set. We obtain a superset of the Km-trivial sets by
defining
A to be almost-K-trivial if there is a real number a such that
K(A _
n) _+ aK(n). Every Km-trivial set is almost-K-trivial. However,
the
Turing degree of a computably dominated ML-random cannot contain
any
almost-K-trivial set. An interesting question is to determine
which
Turing degrees contain Km-trivial sets (or almost-K-trivial sets).
Recently,
this question has been considered for minimal Turing degrees.
We
also consider lowness for monotone and a priory complexity.
References
1.
Calhoun, W.C.: Triviality and minimality in the degrees of monotone complexity,
Journal
of Logic and Computation 22, 197-206 (2012).
2.
Nies, Andre: Lowness properties and randomness, Advances in Mathematics
197,
274-305 (2005).

Exley Science Center (Tower)

Monday, September 21, 2015

04:45 pm
- 06:00 pm

CT Logic Seminar, Vincent Guingona (Wes): "A Local Characterization of VC-Minimality"

Abstract :
( Joint work with Uri Andrews ) This talk is in the intersection of
computable model theory and neostability theory. I discuss VC-minimality,
a model-theoretic notion of complexity for theories that generalizes
o-minimality and is generalized by dp-minimality and NIP. Unlike
o-minimality and dp-minimality, a priori , it is difficult to
determine if a given theory is VC-minimal. In computability terms, the
definition of VC-minimality, in its original form, is Sigma_1^1. However,
my coauthor and I show that VC-minimality is, in fact, Pi^0_4-complete by
giving a local characterization (for countable languages). This leads to
a list of examples of theories whose VC-minimality is determined.

Exley Science Center (Tower)

Monday, September 14, 2015

04:45 pm
- 05:45 pm

Logic Seminar, Reed Solomon (UConn): "Strong reducibilities, RT^1_3 and SRT^2_2"

Abstract: Various
strong reductions between Pi^1_2 principles have been used in recent years to
shed light on difficult problems in reverse mathematics. I will introduce some
of these reductions and discuss their connection to reverse math. The main
theorem of the talk is that RT^1_3 is not strongly computably reducible to
SRT^2_2. This result is joint work with Damir Dzhafarov, Ludovic Patey and
Linda Brown Westrick.

Monday, April 27, 2015

04:45 pm
- 06:00 pm

Logic Seminar, Petr Glivicky (Charles University): 'Definability in linear fragments of Peano Arithmetic'

Abstract: In this talk, I will give an overview of recent results on linear arithmetics with main focus on definability in their models. Here, for a cardinal k, the k-linear arithmetic (LAk) is a full-induction arithmetical theory extending Presburger arithmetic by k non-standard scalars (= unary functions of multiplication by distinguished elements). The hierarchy of linear arithmetics lies between Presburger and Peano arithmetics and stretches from tame to wild. I will present a quantifier elimination result for LA1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA2 (or any LAk with k at least 2) where multiplication is definable on a non-standard initial segment (and thus no similar quantifier elimination is possible). There is a close connection between models of linear arithmetics and certain discretely ordered modules (as each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars) which allows to construct wild (e.g. non-NIP) ordered modules. On the other hand, the quantifier elimination result for LA1 implies interesting properties of the structure of saturated models of Peano arithmetic.

ESC 638

Monday, March 30, 2015

04:45 pm
- 06:00 pm

Logic Seminar, Reed Solomon (UConn): 'Revisiting EM and ADS'

Abstract: In this talk, I will present recent work by Ludovic Patey which simplifies and extends the proof that the Erdos-Moser principle (that every infinite tournament has an infinite transitive sub tournament) does not imply ADS (that every linear order contains either an infinite ascending sequence or an infinite descending sequence).

ESC 638

Tuesday, March 24, 2015

04:15 pm
- 05:30 pm

Computer Science Seminar, Marc Liberatore (UMass): 'BitCoin: WTF is it, and is it really anonymous?'

Abstract: In this talk, we'll (re-)develop the BitCoin protocol step-by-step. We'll start with a simple centralized service for digital cash, and end up with a sketch of the distributed consensus system that we all love -- or love to hate. We will briefly survey the state of BitCoin and related systems, with a focus on how much privacy they really provide to their users. Then, we'll present the problem of mixing BitCoin to increase user privacy. We will see that centralized mix systems based on protocols like CoinJoin have the same problems found in centralized proxies for general communications, and more besides. We'll show that the Sybil attack is one such problem -- a critical one -- and present Xim, our distributed approach to Sybil-resistant matchmaking.(While this talk will be technical, you won't need a deep knowledge of cryptography or protocols to follow it. My goal is for undergraduate liberal arts majors with some math or computer science background to be comfortable in following along and in asking questions as they come up.)Marc Liberatore is a research scientist and occasional lecturer in the School of Computer Science at the University of Massachusetts Amherst, and the associate director of the Center for Forensics at UMass. Prior to his current appointment, he was a Mellon Fellow and Visiting Assistant Professor at Wesleyan University. His research interests include network, cellular, and filesystem forensics, anonymous communication systems, and peer-to-peer architectures.

ESC 638

Tuesday, March 24, 2015

04:15 pm
- 05:30 pm

Computer Science Seminar, Marc Liberatore (UMass): 'BitCoin: WTF is it, and is it really anonymous?'

Abstract: In this talk, we'll (re-)develop the BitCoin protocol step-by-step. We'll start with a simple centralized service for digital cash, and end up with a sketch of the distributed consensus system that we all love -- or love to hate. We will briefly survey the state of BitCoin and related systems, with a focus on how much privacy they really provide to their users. Then, we'll present the problem of mixing BitCoin to increase user privacy. We will see that centralized mix systems based on protocols like CoinJoin have the same problems found in centralized proxies for general communications, and more besides. We'll show that the Sybil attack is one such problem -- a critical one -- and present Xim, our distributed approach to Sybil-resistant matchmaking. (While this talk will be technical, you won't need a deep knowledge of cryptography or protocols to follow it. My goal is for undergraduate liberal arts majors with some math or computer science background to be comfortable in following along and in asking questions as they come up.) Marc Liberatore is a research scientist and occasional lecturer in the School of Computer Science at the University of Massachusetts Amherst, and the associate director of the Center for Forensics at UMass. Prior to his current appointment, he was a Mellon Fellow and Visiting Assistant Professor at Wesleyan University. His research interests include network, cellular, and filesystem forensics, anonymous communication systems, and peer-to-peer architectures.

ESC 638

Monday, March 23, 2015

04:45 pm
- 06:00 pm

Logic Seminar, Stephen Flood (UConn): 'Separating Decomposability and Tree- Decomposability'

Abstract: The theory of graph decompositions studies the infinite graphs that can be built using a sequence of irreducible graphs which are pasted together at complete subgraphs. In this theory, there are several combinatorial characterizations of the tree-decomposable graphs, but a combinatorial characterization of general decomposable graphs has proved elusive.In this talk, we approach this question from the perspective of mathematical logic. We show that there is indeed a difference between characterizing decomposable and tree-decomposable graphs. More precisely, we show that the index set of computable decomposable graphs is $\Pi^1_1$ hard and $\Sigma^1_2$ definable, whereas the index set of computable tree-decomposable graphs is $\Sigma^1_1$ definable.

ESC 638