LOGIC SEMINAR

http://home.gwu.edu/~harizanv/Logic%20Seminar%20F09.html

Spring 2016

Logic-Quantum Computing Seminar

Friday, April 22, 2016

3:00–4:00p.m.

Speaker: Jacob Learned, GWU

Place: Corcoran Hall (725 21^st Street), Room 106

Title: Quantum neural networks

Abstract: Neural Networks are machine learning algorithms that borrow their structure from the current understanding of the human brain. For my research, I studied the difficulties of implementing a neural network on a quantum computer. This talk will provide an overview of classical machine learning and neural networks before discussing the challenges that quantum computing presents for efficient neural networks. I also present a potential quantum algorithm for a rectified linear unit, which is a popular model for the artificial neuron.

Logic-Quantum Computing Seminar

Wednesday, April 20, 2016

2:30–330p.m.

Speaker: Mariel Supina, GWU

Place: Bell Hall (2029 G Street), Room 108

Title: Grover’s search algorithm: quantum speed-up

Abstract: The problem of locating a specific piece of data in an unsorted array is similar to the problem of finding a needle in a haystack. The fastest classical algorithm is the brute force search, which locates the desired item in linear time. However, given a quantum computer, there is a much more efficient algorithm to solve this problem, which was presented by Lov Grover (1996). Grover’s search algorithm uses quantum superposition to sort the data much more quickly, only requiring checks for an array of size n. In this talk I will introduce quantum computing and Grover’s algorithm, explain the mathematical machinery behind it, and present an example in which I use the algorithm to sort a small set of data. 

Wednesday, April 13, 2016

5:30–6:30p.m.

Speaker: Valentina Harizanov, GWU

http://home.gwu.edu/~harizanv/

Place: Corcoran Hall (725 21^st Street), Room 101

Title: Transforming structures

Abstract: Often, interesting computability-theoretic phenomena are first obtained on structures of special kind, which result from specific complicated constructions and may not come from natural classes. It is often desirable to find such phenomena on structures in other, well-known classes. We will present algorithmic ways of transforming certain countable structures and their isomorphisms into other types of algebraic structures and their isomorphisms in such a way that relevant computability-theoretic properties are transferred.

Wednesday, March 30, 2016

5:30–6:30p.m.

Speaker: Johanna Franklin, Hofstra University, NY

https://people.hofstra.edu/Johanna_N_Franklin/

Place: Funger Hall (2201 G Street), Room 108

Title: Category and lowness for isomorphism

Abstract: A Turing degree d is said to be low for isomorphism if, whenever two structures are d-isomorphic, they are already computably isomorphic. Solomon and I proved that every 2-generic Turing degree was low for isomorphism and hypothesized that no weaker level of genericity would suffice. However, Turetsky and I constructed a properly 1-generic real that is low for isomorphism. In this talk, I will present proofs of both of these results.

Wednesday, February 3, 2016

5:30–6:30p.m.

Speaker: Valentina Harizanov, GWU

http://home.gwu.edu/~harizanv/

Place: Phillips Hall (801 22nd Street), Room 110

Title: The tree method in priority arguments

Abstract: Computably enumerable sets with particular properties are often constructed using the priority method. I will present the priority method as a tree construction emphasizing the general framework.

Wednesday, January 20, 2016

5:30–6:30p.m.

Speaker: Russell Miller, City University of New York

http://qcpages.qc.cuny.edu/~rmiller/

Place: Phillips Hall (801 22nd Street), Room 110

Title: Computable functors and effective interpretations

Abstract: We draw connections between two related notions. An effective interpretation of a countable structure A in another countable structure B uses exactly the notion of interpretation from model theory, except that now the domain of the interpretation is allowed to use tuples from B of arbitrary finite length, and that the formulas to be used must be computable infinitary Sigma_1 formulas, rather than finitary formulas of arbitrary complexity. A computable functor, from the category Iso(B) of all structures with domain omega isomorphic to B to the corresponding category Iso(A), is given by two Turing functionals, one mapping objects from Iso(B) to objects in Iso(A) and the other mapping isomorphisms between objects in Iso(B) to isomorphisms between the corresponding objects in Iso(A). Recent work by Harrison-Trainor, Melnikov, Montalbán and the speaker has shown these two concepts to very tightly related. An effective interpretation of A in B clearly yields a computable functor from Iso(B) to Iso(A). We will describe the converse and consider how these notions may be extended to continuous functors and interpretations by L_omega_1,omega formulas in general.

Fall 2015

Wednesday, December 2, 2015

5:30–6:30p.m.

Speaker: Tslil Clingman, GWU

Place: Monroe Hall (2115 G Street), Room 267

Title: An exploration of the category of relations

Abstract: The category of relations, Rel, has a rich structure and serves as an important example of many concepts in the general theory. We will begin by understanding morphisms, limits and self-duality in this category, observing that one may take the external axiom of choice (as this is not always possible), before moving to understand any of the several important structural notions present in Rel. Depending on audience interest, we will see how Rel is a (closed) monoidal category, an enriched category (in two important ways) and even a strict 2-category. Finally, time permitting, we will explore a very important generalisation of Rel which leads to the general theory of weak 2-categories. Only elementary knowledge of category theory will be assumed. 

Thursday, November 12, 2015

6:00–7:00p.m.

Speaker: Valentina Harizanov, GWU

Place: Monroe Hall (2115 G Street), Room 110

Title: Coding sets into orders

Abstract: An abelian group is orderable if and only if it is torsion-free. We will show how sets of natural numbers can be coded into orders on computable abelian torsion-free groups.

Logic-Topology Seminar

Wednesday, November 4, 2015

5:30–6:30p.m.

Speaker: Ajit Iqbal Singh, Indian National Science Academy

http://insaindia.org/detail.php?id=N99-1262

Place: Monroe Hall (2115 G Street), Room 267

Title: Roping more by ringing less in topology

Abstract: We shall present Kakeya’s interval-filling sequences, Liapunov’s convexity theorem for finite-dimensional vector-valued measures and Hobby-Rice theorem for integrals of finitely many continuous functions on sub-intervals together with applications to fair division. The concept of division in rings of continuous functions will be introduced via module homomorphisms.

Thursday, October 29, 2015

6:00–7:00p.m.

Speaker: Rumen Dimitrov, Western Illinois University

http://www.wiu.edu/users/rdd104/home.htm

Place: Monroe Hall (2115 G Street), Room 110

Title: Complexity of GSL

Abstract: Let L be the lattice of computably enumerable subspaces of the fully computable infinite-dimensional vector space V. Guichard proved that the automorphisms of L are generated by computable semilinear transformations. Assume that V is a vector space over a computable rigid field, and let GSL be the group of 1–1, onto, computable linear transformations. In this talk we will prove results related to complexity of GSL.

Wednesday, October 14, 2015

5:30–6:30p.m.

Speaker: Tslil Clingman, GWU

Place: Monroe Hall (2115 G Street), Room 267

Title: A gentle introduction to monoidal categories

Abstract: While general categories provide a rich and deep theory, more focused inquiry may be achieved by requiring of the categories a certain additional structure. Perhaps one of simplest starting points is requiring the objects of the category to form a monoid in an appropriate sense. We shall work our way up from elementary definitions in the general theory to such “monoidal categories”, examine their natural manifestations, explore what “generalised elements” of such categories may be and, time allowing, further directions and motivations. No prior understanding of category theory will be assumed.

Wednesday, October 7, 2015

5:30–6:30p.m.

Speaker: Dr. Fredrick Nelson

Place: Monroe Hall (2115 G Street), Room 267

Title: The group of rational points on the Holm curve is torsion-free

Abstract: The Holm curve is the elliptic curve given by the equation k,,y-^3.–y. = l,,x^-3.–x. where k and l are distinct, relatively prime, square-free, positive integers. It is isomorphic to the elliptic curve in Weierstrass form. By Mordell’s theorem, the group of rational points on the Holm curve is a finitely-generated abelian group. I will prove that this group is torsion-free, thus establishing a previous conjecture. The proof uses McKee’s algorithm for computing division polynomials of elliptic curves.

Wednesday, September 30, 2015

5:30–6:30p.m.

Speaker: Hakim Walker, GWU

Place: Monroe Hall (2115 G Street), Room 267

Title: Computable isomorphisms between (2,1):1 structures

Abstract: A (2,1):1 structure consists of a countable set A (usually the natural numbers) and a function f that maps, to each element of A, either exactly one element of A or exactly two elements of A. Similar structures have been studied recently by Harizanov, Cenzer, Remmel, and Marshall, particularly the complexity of isomorphisms between such structures. In this talk, we will begin by presenting some of the basic properties of these structures, particularly the types of orbits under f, which can be interpreted as directed graphs. Then we will discuss some computability-theoretic results, including two classes of (2,1):1 structures that are computably categorical, i.e., every two computable copies of the structure have a computable isomorphism between them. Finally, we will conclude with an application to the Collatz conjecture.

Logic-Topology Seminar

Wednesday, September 23, 2015

5:30–6:30p.m.

Speaker: Jozef Przytycki, GWU

http://home.gwu.edu/~przytyck/

Place: Monroe Hall (2115 G Street), Room 267

Title: Curtain homology and logic

Abstract: We show a simple visualization that allows us to construct homology theory for a Yang-Baxter operator. The linear map $R: V\otimes V \to V\otimes V$ is called by Fadeev school of theoretical physics the Yang-Baxter operator if it is invertible and satisfies the following equation:
$(R\otimes Id) (Id \otimes R)(R\otimes Id) = (Id \otimes R)(R\otimes Id)(Id \otimes R)$.
We show that the quandle homology, in its cubic form, can be presented graphically using a diagram (curtain diagram). This in turn gives rise to homology of Yang-Baxter operator. We speculate that this homology is related to Khovanov homology of links and gives a deep connection between Knot Theory and Statistical Physics.