Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars Seminar History

Seminar Home
Fall 2013 Schedule
Winter 2014 Schedule
Summer 2014 Schedule
Archives

Date
( Winter 2010 )
Category Seminar Info
2010/04/29 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Jurg Wullschleger
Affiliation: University of Bristol
Area: theoretical computer science
Title: Extracting Correlations
Abstract: This week I will give the second part of my presentation of the paper "Extracting Correlations" by Ishai, Kushilevitz, Ostrovsky and Sahai from STOC 2009. I will talk about the following: - how oblivious transfer (OT) can be implemented from Randomized OT. - what (decomposable) randomized encodings are, and how they can be used. - the OT-extractor protocol from the "Extracting Correlations"-paper.
2010/04/23 Bioinformatics Place: Leacock 26
Time: 14:30 - 16:00
Speaker: Guillaume Bourque
Affiliation:
Title: Functional genomics in stem cells, evolution and cancer
Abstract: In the first part of this talk, I will describe a study where we generated occupancy maps for three key regulatory proteins (OCT4, NANOG and CTCF) together with knockdown expression experiments (OCT4) in human and mouse Embryonic Stem cells. Using this data we found that the binding profiles of OCT4 and NANOG were drastically different between the two species with only ~5% of the regions homologously occupied. Moreover, I will show that species-specific transposable elements have contributed up to 25% of the regulatory sites in both lineages and have wired new genes into the core regulatory network of human ES cells. In the second part of this talk, I will look at the forces shaping vertebrate genome architectures and present a new algorithm called EMRAE that can predict a wide-range of rearrangement events in the ancestry of a group of species. Applying this tool to a dataset with six genomes (human, chimpanzee, rhesus macaque, mouse, rat, and dog), I will show that regions of high sequence identity have been associated with rearrangement events throughout the mammalian phylogeny. Finally, in the third part of this talk, I will show how new paired-end-tag sequencing strategies can efficiently provide the map of all structural changes in a given genome. Applying this technique to normal samples, cancer tumors and cancer cell lines and performing a comparative analysis can reveal different patterns of mutations and help identify important aberrations.
2010/04/22 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Jürg Wullschleger
Affiliation: University of Bristol, UK
Area: theoretical computer science
Title: Extracting Correlations
Abstract: I will present a paper by Ishai, Kushilevitz, Ostrovsk and Sahai from STOC 2009, called "Extracting Correlations". I will divide it into two sessions. This week, i will - explain what extractors, OT, OT-combiners, and OT-extractors are. - present an extractor using eps-biased sets. - show what randomized encodings are, and outline how they can be constructed and used.
2010/04/15 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Ladan Mahabadi
Affiliation: McGill
Area: theoretical computer science
Title: Pseudorandom generators
Abstract: Prevalence of randomized algorithms has made the design of pseudorandom generators (PRG) a significant issue. Blum, Micali and Yao in the early 80s used hardness of a one-way permutation to create a pseudorandom generator (BMY PRG) that fools any probababilistic algorithm running in polynomial time. In the early 90s, a seminal work of Nisan and Wigderson, introduced a new type of PRGs (NW PRG) that required a weaker complexity assumption. The seminal idea behind this construction is to allow the PRG to run in exponential time since its output is to be used for derandomization. This construction led to a new wave of analysis and construction of PRGs. In this talk, I will introduce the Blum-Blum-Yao, Blum-Blum-Shoup and the Nisan-Wigderson PRGs. Time permitting, I'll also mention the application of extractors - efficient algorithms that given a weak source of randomness and a truly random seed, output a distribution that is statistically close to the uniform distribution - to improve such constructions.
2010/04/08 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Michael Cadilhac
Affiliation: University of Montreal
Area: theoretical computer science
Title: The Homomorphism Preservation Theorem for the finite.
Abstract: Last week, we saw what a preservation theorem is, and why the usual proofs in classical model theory do not go through in finite model theory. Following Benjamin Rossman's proof (LICS'05), we saw a new approach on proving the Homomorphism Preservation Theorem (HPT) in the classical case. This week, we will see why this proof does not work as-is for the finite HPT, and look at some new tools (I even foresee some exciting use of EF games!) to salvage most of the ideas exposed previously. Last week's presentation is not a requirement in order to understand this one.
2010/04/07 CQIL - Cryptography and Quantum Information Place: McConnell 103
Time: 16:00 - 17:00
Speaker: Todd Brun
Affiliation: University of Southern California
Title: Quantum Steganography with Noisy Channels
Abstract: Steganography is the process of hiding secret information by embedding it in an ``innocent'' message. We present protocols for hiding either classical or quantum information in a codeword of a quantum error-correcting code passing through a channel. Using either a shared secret key or shared entanglement, the sender (Alice) disguises her information as errors in the channel. The receiver (Bob) can retrieve the hidden information, but an eavesdropper (Eve) with the power to monitor the channel, but without the secret key, cannot distinguish the message from channel noise. We analyze how difficult it is for Eve to detect the presence of secret messages, and estimate rates of steganographic communication and secret key consumption for certain protocols.
2010/04/01 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Michael Cadilhac
Affiliation: University of Montreal
Area: theoretical computer science
Title: The Homomorphism Preservation Theorem for the finite.
Abstract: Łoś-Tarski theorem is one of the most natural result in classical model theory. It states that a first-order formula f is preserved by extensions iff f is existential, that is, f can be written using only positive existential quantifiers. A formula f is said to be preserved by extensions if whenever a structure A (i.e., a universe and a set of relations) is a model of f and a structure B is an extension of A, B is a model of f. This theorem is one of the so-called Preservation Theorems, which correlate semantic and syntactic properties of formulas. Another example is the Homomorphism Preservation Theorem (HPT), which states that a first-order formula f is preserved by homomorphisms iff f is existential and positive. When one is interested in finite model theory, that is, satisfaction for finite structures, most of the preservation theorems fail due to the fact that the Compactness Theorem does not hold. In this talk, we will see that HPT has the incredible property to stay true in the finite. For that purpose, we will walk through Benjamin Rossman's proof (LICS'2005) of the finite HPT. If there is interest, I will focus on particular spots of the proof in a second talk.
2010/03/26 DMO - Discrete Mathematics and Optimization Place: McConnell 320
Time: 14:00 - 15:00
Speaker: Lisa Fleischer
Affiliation: Dartmouth University
Title: Unrelated Machine Selection and Scheduling
Abstract: We look at problems of scheduling jobs to machines when the processing time of a job is machine dependent. Common objectives in this framework are to minimize the maximum load on a machine, or to minimize the average completion time of jobs. These are well-studied problems. We consider the related problem of trying to select a subset of machines to use to minimize machine costs subject to bounds on the maximum load or average completion time of the corresponding schedule. These problems are NP-hard and include set-cover as a special case. Thus we focus on approximation algorithms and get tight, or almost tight approximation guarantees.
2010/03/25 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Pierre McKenzie
Affiliation: University of Montreal
Area: Theoretical computer science
Title: Branching programs for the tree evaluation problem
Abstract: I'll recall the relationship between branching programs and Turing machines, then talk about branching program lower bounds of various types for the problem of evaluating a tree (I'll explain the problem). Joint work with Mark Braverman, Steve Cook, Rahul Santhanam and Dustin Wehr, presented at MFCS and FSTTCS last year.
2010/03/22 DMO - Discrete Mathematics and Optimization Place: Burnside 1205
Time: 16:00 - 17:00
Speaker: Mohit Singh
Affiliation: McGill University
Title: Incentives in Secretary Problems and Online Auctions via Linear Programming
Abstract: In the secretary problem, an employer would like to choose the best candidate in an online manner among n competing candidates. The candidates are assumed to arrive in a random order. The optimal mechanism is to interview the first n/e candidates for the purpose of evaluation, and then hire the first candidate that is better than all previous candidates. This simple mechanism suffers from a crucial drawback. Candidates arriving early in the process have an incentive to delay their interview. Using this mechanism, when candidates can influence their position, can lead to sub-optimal result and challenges the basic assumption that the candidates arrive in a random order.

In this talk, I will describe a linear programming framework which characterizes all mechanisms for the secretary problem and its extensions. This characterization helps us obtain optimal incentive compatible mechanisms for the secretary problem. We will also show an application of this result to an auction scenario where a single item has to be sold to n competing bidders arriving in an online manner.

This is joint work with Niv Buchbinder and Kamal Jain.


2010/03/18 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Marc Kaplan
Affiliation: University of Montreal
Area: theoretical compter science
Title: Some applications of Grothendieck's inequality to computer science (part II)
Abstract: Grothendieck's inequality is a fundamental result in functional analysis. In the last ten years it has appeared to be an extremely useful tool in computer science. Perhaps the most surprising fact about it is that has been used in very different areas. On one side, it is a cornerstone of the approximation algorithm theory and unique game conjecture. On the other side, it is a very natural tool to approach various problems of quantum information processing. In a series of two talks, I will present these two aspects. During the first talk, I will present the inequality and the algorithm of Alon and Naor for approximating the cut norm. The core of the algorithm will give us a complete proof of Grothendieck's inequality. During the second talk, we will focus on quantum information processing. The connection between Grothendieck's inequality and the quantum world is made clear by Tsirelson's theorem on quantum probability distributions. The combination of these two result will allow us to give a new insight on Linial and Shraibman's work on algebraic lower bounds on quantum communication complexity. Biography of Speaker:

Marc Kaplan is currently a postdoc at University of Montreal, hosted by Prof. Gilles Brassard. He obtained his PhD at LRI, Orsay, under the supervision of Prof. Sophie Laplante.


2010/03/15 DMO - Discrete Mathematics and Optimization Place: Burnside 1205
Time: 16:30 - 17:30
Speaker: Xavier Dahan
Affiliation: Kyushu University
Title: Ramanujan graphs of larger girth
Abstract: Ramanujan graphs are optimal (spectral) expanders. We will first introduce the concept of expansion in a regular graph, then define expanders, that have dozens of applications in Computer and Information science [2]. We will review the construction of [1], i.e. Cayley graphs on discrete quaternionic groups, then show what is changing when using octonions instead. We obtain families of regular graphs with a larger girth, and hence with the largest girth known. (joint work with J.-P. Tillich)

[1] Lubotzsky, Philips and Sarnak. Ramanujan grpahs. Coombinatorica, 1988.

[2] Hoory, Linial and Wigderson. Expander graphs and their applications, Bull of the AMS, 2006.


2010/03/12 Algorithms Place: Trottier 2100
Time: 10:30 - 11:30
Speaker: Bill Cook
Affiliation: Georgia Tech
Title: In Pursuit of the Salesman: Mathematics at the Limits of Computation
Abstract: The traveling salesman problem, or TSP for short, is easy to state: given a number of cities along with the cost of travel between each pair of them, find the cheapest way to visit them all and return to your starting point. Easy to state, but difficult to solve! Despite decades of research by top applied mathematicians around the world, in general it is not known how to significantly improve upon simple brute-force checking. It is a real possibility that there may never exist an efficient method that is guaranteed to solve every instance of the problem. This is a deep mathematical question: Is there an efficient solution method or not? The topic goes to the core of complexity theory concerning the limits of feasible computation. For the stout-hearted who would like to tackle the general version of the TSP, the Clay Mathematics Institute will hand over a $1,000,000 prize to anyone who can either produce an efficient general method or prove an impossibility result. The complexity question that is the subject of the Clay Prize is the Holy Grail of traveling-salesman-problem research and we may be far from seeing its resolution. This is not to say that mathematicians have thus far come away empty-handed. Within the theoretical community the problem has led to a large number of results and conjectures that are both beautiful and deep. In the arena of exact computation, an 85,900-city challenge problem was solved in 2006, in a computation that took the equivalent of 136 years on top-of-the-line computer workstations. On the practical side, solution methods are used to compute optimal or near-optimal tours for a host of applied problems on a daily basis, from genome sequencing to arranging music on iPods. In this talk we discuss the history, applications, and computation of the TSP, together with an open research area connecting planar graphs and the linear-programming approach to the problem.
2010/03/11 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Marc Kaplan
Affiliation: University of Montréal
Area: Theoretical computer science
Title: Some applications of Grothendieck's inequality to computer science
Abstract: Grothendieck's inequality is a fundamental result in functional analysis. In the last ten years it has appeared to be an extremely useful tool in computer science. Perhaps the most surprising fact about it is that has been used in very different areas. On one side, it is a cornerstone of the approximation algorithm theory and unique game conjecture. On the other side, it is a very natural tool to approach various problems of quantum information processing. In a series of two talks, I will present these two aspects. During the first talk, I will present the inequality and the algorithm of Alon and Naor for approximating the cut norm. The core of the algorithm will give us a complete proof of Grothendieck's inequality. During the second talk, we will focus on quantum information processing. The connection between Grothendieck's inequality and the quantum world is made clear by Tsirelson's theorem on quantum probability distributions. The combination of these two result will allow us to give a new insight on Linial and Shraibman's work on algebraic lower bounds on quantum communication complexity.
2010/03/08 DMO - Discrete Mathematics and Optimization Place: Burnside 1205
Time: 16:00 - 17:00
Speaker: Guyslain Naves
Affiliation: McGill University
Title: Integer Multicommodity Flows in Planar Graphs
Abstract: A commodity in a capacitated graph G is a pair of vertices (source, sink) and a demand value associated to this pair. Given a set of commodities H, a multicommodity flow is a set of flows, one for each commodity, such that the sum of the flows on each edge e is at most the capacity of e. We want to decide if there is a multicommodity flow such that the flow for each commodity is equal to its demand. When there is only one commodity, this is the decision version of the classic flow problem. If we force the flows to be integral, it defines the integer multicommodity flow problem. When the capacities are uniformly equal to one, this is the edge-disjoint paths problem. I will survey the main results in the field of integer multicommodity flows, and then introduce two new results when G is a planar graph:

- the problem is NP-complete with only two commodities (in undirected and directed acyclic cases),

- the uncapacitated problem is polynomial when G is a planar acyclic digraph, G+H is Eulerian, and the number of commodities is fixed.


2010/03/01 DMO - Discrete Mathematics and Optimization Place: Burnside 920
Time: 16:30 - 17:30
Speaker: Andrei Krokhin
Affiliation: Durham, UK
Title: On the hardness of losing weight
Abstract:
2010/02/22 DMO - Discrete Mathematics and Optimization Place: Burnside 1205
Time: 16:00 - 17:00
Speaker: Alex Slivkins
Affiliation: Microsoft Research
Title: Multi-Armed Bandits in Metric Spaces
Abstract: In a multi-armed bandit problem, an online algorithm chooses from a fixed set of alternatuves (a.k.a. "strategies" or "arms") in a sequence of trials so as to maximize the total payoff of the chosen strategies. While the performance of bandit algorithms with a small finite strategy set is quite well understood, bandit problems with large strategy sets are still a topic of very active investigation, motivated by practical applications such as online auctions and web advertisement. The goal of such research is to identify broad and natural classes of strategy sets and payoff functions which enable the design of efficient solutions. In this work we study a very general setting for the multi-armed bandit problem in which the strategies form a metric space, and the payoff function satisfies a Lipschitz condition with respect to the metric. Joint work with Bobby Kleinberg and Eli Upfal. Based on papers in STOC'08 and SODA'10 and some recent work.
2010/02/19 CQIL - Cryptography and Quantum Information Place: McConnell 103
Time: 11:30 - 12:30
Speaker: Dave Touchette
Affiliation: McGill University
Title: Trade-off capacities of quantum Hadamard channels
Abstract: An important goal of Quantum Shannon Theory is to determine the maximum rates at which information can be transmitted reliably over noisy quantum channels. However, the computation of these optimal rates is generally intractable, requiring an optimization over an arbitrary number of parallel uses of the channel. In those rare cases where this computation is tractable, the channel can be used to its full potential to perform the task at hand. We show that this is the case for a general class of quantum channels, Hadamard channels, considering the triple resource capacity region of entanglement-assisted quantum and classical communication. Three natural subclasses are generalized dephasing channels, cloning channels and Unruh channels. Parametrizing the trade-off region for them, we find that this optimal coding strategy beats the naive time-sharing one, so we introduce a measure to quantify this improvement.
2010/02/18 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Phuong Nguyen
Affiliation: McGill
Area: theory
Title: Gower uniformity norm
Abstract: Szemeredi's Theorem states that for any delta between 0 and 1, and k greater than 2, there is a number N so that for all n > N, for all subset A of {1,2,...,N} of density delta, A contains an arithmetic progression of length k. Gower uniformity norm is introduced in his proof of Szemeredi's Theorem and independently by Alon et. al. Essentially the norm $U^d(f)$ measures the correlation of the given function $f$ with polynomials of degree at most $d$. Gower's proof is inspired by Roth's proof of the theorem for the case of length-3 arithmetic progression, and this notion is needed for the generalization. It has shown up in circuit lower bounds and communication complexity as well. In this talk I will define it in the context of an outline of Gower's proof. If time allows I will mention some applications. Biography of Speaker:

Postdoc


2010/02/17 CQIL - Cryptography and Quantum Information Place: McConnell 321
Time: 11:30 - 12:30
Speaker: Robert Spekkens
Affiliation: Perimeter Institute for Theoretical Physics
Title: Why the quantum? Insights from classical theories with a statistical restriction
Abstract: A significant part of quantum theory can be obtained by postulating a single conceptual innovation relative to classical theories, namely, that agents face a fundamental restriction on what they can know about the physical state of any system. This talk will consider a particular sort of statistical restriction wherein only classical variables with vanishing Poisson bracket can be known simultaneously. When this principle is applied to a classical statistical theory of three-level systems (trits), the resulting theory is found to be operationally equivalent to the stabilizer formalism for qutrits. Applied to a classical theory of harmonic oscillators, it yields quantum mechanics restricted to quadrature eigenstates and observables. Finally, applied to a classical statistical theory of bits, it yields a theory that is almost equivalent to (but interestingly different from) the stabilizer formalism for qubits. I will discuss the significance of these results for the project of deriving the formalism of quantum theory from physical principles. Joint work with Olaf Schreiber.
2010/02/11 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Anil Ada
Affiliation: McGill, SOCS
Area: Theoretical computer science, Ramsey theory
Title: Roth's Theorem
Abstract: In extremal combinatorics, one is interested in how large/small can an object be that satisfies certain properties. The objects are usually graphs/hypergraphs or set systems, and the properties of interest may be cuts, sizes of intersections etc. In additive combinatorics, one studies integers or more generally abelian groups, and the properties of interest can be phrased in terms of linear equations. In the recent years, additive combinatorics has been a very productive area of mathematics, bringing together techniques from graph theory, analysis and ergodic theory. A major success story in this area of research has been the Green-Tao theorem that shows that prime numbers contain arbitrarily long arithmetic progressions. Techniques used in additive combinatorics have also found applications in theoretical computer science such as property testing, PCP constructions, lower bounds and extractor constructions. The famous Szemeredi Theorem is one of the fundamental results of this area. It states that: Given any delta and k, we can find an N such that every subset A of {1,2,...,N} of size at least delta*N contains an arithmetic progression of length k. In our talk, we are going to present Roth's proof for the k=3 case. This proof is considered as one of the gems of analytic number theory. The proof uses basic Fourier analysis but we will not assume any prior knowledge and provide all relevant definitions. Biography of Speaker:

PhD student.


2010/02/10 CQIL - Cryptography and Quantum Information Place: McConnell 437
Time: 11:30 - 12:30
Speaker: David Poulin
Affiliation: University of Sherbrooke
Title: Quantum Metropolis algorithm
Abstract: Quantum computers have emerged as the natural architecture to study the physics of strongly correlated quantum systems, thus providing a major new impetus to the field of many-body quantum physics. While the method of choice for simulating classical many-body systems has long since been the ubiquitous Monte Carlo method, the formulation of a generalization of this method to the quantum regime has been impeded by the fundamental peculiarities of quantum mechanics, including interference effects and the no-cloning theorem. In this paper, we overcome those difficulties by constructing an efficient quantum algorithm to sample from the Gibbs distribution of an arbitrary quantum Hamiltonian at arbitrary temperatures, both for bosonic and fermionic systems. This validates the quantum computer as a full quantum simulator, with a wealth of possible applications to quantum chemistry, condensed matter physics and high energy physics.
2010/02/08 DMO - Discrete Mathematics and Optimization Place: Burnside 920
Time: 16:30 - 17:30
Speaker: Amina Lamghari
Affiliation: McGill University
Title: Models and Methods for the Judge Assignment Problem
Abstract: The judge assignment problem is a practical combinatorial optimization problem. It consists of determining which judges to assign to each individual competition of a tournament such as to satisfy to the best extent possible the objectives fixed by the organizers. We illustrate the judge assignment problem in the particular case of the John Molson International case competition that takes place every year at Concordia University. We consider first the problem for a round because the solution methods will be used afterward to solve the whole problem for several rounds. The constraints taken into account, their nature, their complexity, as well as the horizon of the assignment are as many elements which distinguish these two problems. We propose mathematical models to formulate them, and methods based on metaheuristics to solve them. Computational experiments indicate the efficiency of the proposed approach. One of the developed methods has been embedded into user-friendly software, which has enabled substantial savings in organizers time and given more evenly better assignments.
2010/02/02 CIM - Centre for Intelligent Machines Place: McDonald-Harrington Bldg., Room G-10
Time: 11:30 - 12:30
Speaker: Robert D. Howe
Affiliation: Harvard University
Title: Fixing the Beating Heart: Ultrasound Guidance for Robotic Intracardiac Surgery
Abstract: To treat defects within the heart, surgeons currently use stopped- heart techniques. These procedures are highly invasive and incur a significant risk of neurological impairment. We are developing methods for performing surgery within the heart while it is beating. New real- time 3-D ultrasound imaging allows visualization through the opaque blood pool, but this imaging modality poses difficult image processing challenges, including poor resolution, acoustic artifacts, and data rates of 30 to 40 million voxels per second. To track instruments within the heart we have developed a Radon transform-based algorithm, which is readily implemented in real-time on graphics processor units. For manipulation of rapidly moving cardiac tissue we have created a fast robotic device that can track the tissue based on ultrasound image features. This allows the surgeon to interact with the heart as if it was stationary. To integrate ultrasound imaging with the robotic device we have developed a predictive controller that compensates for the 50-100 ms imaging and image processing delays to ensure good tracking performance. In vivo studies show that this approach enhances dexterity and lowers applied forces. Clinical applications of this technology include atrial septal defect closure and mitral valve annuloplasty.
2010/01/11 Algorithms Place: Burnside 920
Time: 16:30 - 17:30
Speaker: Vasek Chvatal
Affiliation: Concordia University
Area: Discrete Mathematics
Title: Betweenness
Abstract: A point in the plane is said to lie between points A and C if it is the interior point of the line segment joining A and C. In his development of geometry, Euclid neglected to give the notion of betweenness the same axiomatic treatment that he gave, for instance, to the notion of equality. This omission was rectified twenty-two centuries later by Moritz Pasch: http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Pasch.html During the twentieth century, geometric betweenness was generalized in diverse branches of mathematics to ternary relations of metric betweennes, lattice betweenness, and algebraic betweenness. I will talk about three settings where such abstract betweennesses show up. The first of these settings is ordered geometry; there, primitive notions of points and lines are linked by the relation of incidence and by axioms of betweenness; two classic theorems here are the Sylvester-Gallai theorem http://mathworld.wolfram.com/SylvestersLineProblem.html and the de Bruijn-Erdos theorem. I conjectured in 1998 http://users.encs.concordia.ca/~chvatal/newsg.pdf and Xiaomin Chen proved in 2003 http://dimacs.rutgers.edu/TechnicalReports/abstracts/2003/2003-32.html that the Sylvester-Gallai theorem generalizes to metric spaces when lines in these spaces are defined right; together, we conjectured http://arxiv.org/abs/math.CO/0610036 that the de Bruijn-Erdos theorem also generalizes to metric spaces when lines in these spaces are defined right (with "right" having a different sense in each of the two instances); the two of us and Ehsan Chiniforooshan have partial results on this conjecture. The second of the three settings is abstract convexity; there, families of sets called "convex" obey certain axioms. Such finite structures are called convex geometries when they have the Minkowski-Krein-Milman property: every set is the convex hull of its extreme points. Two classical examples of convex geometries come from shelling of partially ordered sets and simplicial shelling of triangulated graphs. Last June I characterized, by a five-point condition, a class of betweennesses generating a class of convex geometries that subsumes the two examples. http://users.encs.concordia.ca/~chvatal/abc.pdf Laurent Beaudou, Ehsan Chiniforooshan, and I have additional results on such betweennesses. The last setting lies between physics and philosophy: in his effort to develop a causal theory of time, Hans Reichenbach http://en.wikipedia.org/wiki/Hans_Reichenbach introduced the notion of causal betweenness, which is a ternary relation defined on events in probability spaces. This January, Baoyindureng Wu and I characterized, by easily verifiable properties, abstract ternary relations isomorphic to Reichenbach's causal betweenness. http://arxiv.org/abs/0902.1763 A nice connection with a 1979 theorem of Jarda Opatrny http://dx.doi.org/10.1137/0208008 appears here. The joint work with Laurent Beaudou, Ehsan Chiniforooshan, and Baoyindureng Wu was done in our research group ConCoCO http://users.encs.concordia.ca/~concoco/ (Concordia Computational Combinatorial Optimization).