Raziskovalni matematični seminar - Arhiv

We will give a short overview and discuss possible future directions with regards to the classification of strongly regular bicirculants,  in relation to the problem of obtaining a CFSG-free proof of nonexistence of simply primitive groups of degree $2p$.

Abstract: We will give a short overview and discuss possible future directions with regards to the classification of strongly regular bicirculants, in relation to the problem of obtaining a CFSG-free proof of nonexistence of simply primitive groups of degree $2p$.

Set functions, i.e., real mappings form the family of subsets of a finite set to the reals are known and widely used in discrete mathematics for almost a century, and in particular in the last 50 years. If we replace a finite set with its characteristic vector, then the same set function can be interpreted as a mapping from the set of binary vectors to the reals. Such mappings are called pseudo-Boolean functions and were introduced in the works of Peter L. Hammer in the 1960s (Hammer and Rudeanu, 1968). Pseudo-Boolean functions are different from set functions, only in the sense that their algebraic representation, a multilinear polynomial expression, is usually assumed to be available as an input representation.

The problem of minimizing a pseudo-Boolean function (over the set of binary vectors) appears to be the common form of numerous optimization problems, including the well-known MAX-SAT and MAX-CUT problems, and have applications in areas ranging from physics through chip design to computer vision, etc.

Some of these applications lead to the minimization of a quadratic pseudo-Boolean function, and hence such quadratic binary optimization problems received ample attention in the past decades. One of the most frequently used technique is based on roof-duality (Hamer, Hansen, Simeone, 1984), and aims at finding in polynomial time a simpler form of the given quadratic minimization problem, by fixing some of the variables at their provably optimum value (persistency) and decomposing the residual problem into variable disjoint smaller subproblems (Boros and Hammer, 1989). The method in fact was found very effective in computer vision problems, where frequently it can fix up to 80-90% of the variables at their provably optimum value (Boros, Hammer, Sun and Tavares, 2008). This algorithm was used by computer vision experts and a very efficient implementation, called QPBO, is freely downloadable (Rother, Kolmogorov, Lempitsky and Szummer, 2007).

In many applications of pseudo-Boolean optimization, in particular in vision problems, the objective function is a higher degree multilinear polynomial. For such problems there are substantially fewer effective techniques available. In particular, there is no analogue to the persistencies (fixing variables at their provably optimum value) provided by roof-duality for the quadratic case. On the other hand, more and more applications would demand efficient methods for the minimization of such higher degree pseudo-Boolean functions. This increased interest, in particular in the computer vision community, lead to a systematic study of methods to reduce a higher degree minimization problem to a quadratic one. We report on the most recent techniques and the computational success of those.

Joint research with Alex Fix (Cornell University), Aritanan Gruber (Rutgers University), Gabriel Tavares (FICO, Xpress-MP), and Ramin Zabih (Cornell University).

SLIDES FROM THE TALK ARE AVAILABLE HERE: DOWNLOAD!

We will show that maps, which do not increase the spectra of complex matrices (in a sense that $Sp(Phi(A)-Phi(B)) subseteq Sp(A-B)$) are automatically linear and bijective. Although the problem is elementary, its proof relies on deep results from the theory of analitic functions.

Centrality is used to quantify an intuitive feeling that in most networks some vertices are more central than others. In the talk we consider some graph theoretical results on closeness, betweenness centrality, and eccentricity.

An important part of the network analysis are network partitioning  problems, which come in the forms of partitioning, finding maximum cut and detecting communities. There are well known, simple spectral heuristics for all three problems, which assign nodes to an appropriate part based on the sign of the eigenvector corresponding to an extremal eigenvalue of a particular network matrix. We will discuss a general framework in which these heuristics work and suggests a way for their further improvement.

All welcome!