Author name cluster

Vladimir V. Gusev

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

2 author rows

IJCAI Conference 2025 Conference Paper

Language-Based Bayesian Optimization Research Assistant (BORA)

Abdoulatif Cissé
Xenophon Evangelopoulos
Vladimir V. Gusev
Andrew I. Cooper

Many important scientific problems involve multivariate optimization coupled with slow and laborious experimental measurements. These high-dimensional searches can be defined by complex, non-convex optimization landscapes that resemble needle-in-a-haystack surfaces, leading to entrapment in local minima. Contextualizing optimizers with human domain knowledge is a powerful approach to guide searches to localized fruitful regions. However, this approach is susceptible to human confirmation bias. It is also challenging for domain experts to keep track of the rapidly expanding scientific literature. Here, we propose the use of Large Language Models (LLMs) for contextualizing Bayesian optimization (BO) via a hybrid optimization framework that intelligently and economically blends stochastic inference with domain knowledge-based insights from the LLM, which is used to suggest new, better-performing areas of the search space for exploration. Our method fosters user engagement by offering real-time commentary on the optimization progress, explaining the reasoning behind the search strategies. We validate the effectiveness of our approach on synthetic benchmarks with up to 15 variables and demonstrate the ability of LLMs to reason in four real-world experimental tasks where context-aware suggestions boost optimization performance substantially.

PDF Details DOI

ECAI Conference 2024 Conference Paper

Cluster Exploration Using Informative Manifold Projections

Stavros Gerolymatos
Xenophon Evangelopoulos
Vladimir V. Gusev
John Yannis Goulermas

Dimensionality reduction (DR) is one of the key tools for the visual exploration of high-dimensional data and uncovering its cluster structure in two- or three-dimensional spaces. The vast majority of DR methods in the literature do not take into account any prior knowledge a practitioner may have regarding the dataset under consideration. We propose a novel method to generate informative embeddings which not only factor out the structure associated with different kinds of prior knowledge but also aim to reveal any remaining underlying structure. To achieve this, we employ a linear combination of two objectives: firstly, contrastive PCA that discounts the structure associated with the prior information, and secondly, kurtosis projection pursuit which ensures meaningful data separation in the obtained embeddings. We formulate this task as a manifold optimization problem and validate it empirically across a variety of datasets considering three distinct types of prior knowledge. Lastly, we provide an automated framework to perform iterative visual exploration of high-dimensional data.

Details

ICLR Conference 2024 Conference Paper

Graph-based Virtual Sensing from Sparse and Partial Multivariate Observations

Giovanni de Felice
Andrea Cini
Daniele Zambon
Vladimir V. Gusev
Cesare Alippi

Virtual sensing techniques allow for inferring signals at new unmonitored locations by exploiting spatio-temporal measurements coming from physical sensors at different locations. However, as the sensor coverage becomes sparse due to costs or other constraints, physical proximity cannot be used to support interpolation. In this paper, we overcome this challenge by leveraging dependencies between the target variable and a set of correlated variables (covariates) that can frequently be associated with each location of interest. From this viewpoint, covariates provide partial observability, and the problem consists of inferring values for unobserved channels by exploiting observations at other locations to learn how such variables can correlate. We introduce a novel graph-based methodology to exploit such relationships and design a graph deep learning architecture, named GgNet, implementing the framework. The proposed approach relies on propagating information over a nested graph structure that is used to learn dependencies between variables as well as locations. GgNet is extensively evaluated under different virtual sensing scenarios, demonstrating higher reconstruction accuracy compared to the state-of-the-art.

Details

IJCAI Conference 2024 Conference Paper

HypBO: Accelerating Black-Box Scientific Experiments Using Experts’ Hypotheses

Abdoulatif Cissé
Xenophon Evangelopoulos
Sam Carruthers
Vladimir V. Gusev
Andrew I. Cooper

Robotics and automation offer massive acceleration for solving intractable, multivariate scientific problems such as materials discovery, but the available search spaces can be dauntingly large. Bayesian optimization has emerged as a popular sample-efficient optimization engine, thriving in tasks where no analytic form of the target function/property is known. Here, we exploit expert human knowledge in the form of hypotheses to direct Bayesian searches more quickly to promising regions of chemical space. Previous methods have used underlying distributions derived from existing experimental measurements, which is unfeasible for new, unexplored scientific tasks. Also, such distributions cannot capture intricate hypotheses. Our proposed method uses expert human hypotheses to generate improved seed samples. Unpromising seeds are automatically discounted, while promising seeds are used to augment the surrogate model data, thus achieving better-informed sampling. This process continues in a global versus local search fashion, organized in a bilevel optimization framework. We validate the performance of our method on a range of synthetic functions and demonstrate its practical utility on a real chemical design task where the use of expert hypotheses accelerates the search performance significantly.

PDF Details DOI

MFCS Conference 2022 Conference Paper

The Complexity of Periodic Energy Minimisation

Duncan Adamson
Argyrios Deligkas
Vladimir V. Gusev
Igor Potapov

The computational complexity of pairwise energy minimisation of N points in real space is a long-standing open problem. The idea of the potential intractability of the problem was supported by a lack of progress in finding efficient algorithms, even when restricted the integer grid approximation. In this paper we provide a firm answer to the problem on ℤ^d by showing that for a large class of pairwise energy functions the problem of periodic energy minimisation is NP-hard if the size of the period (known as a unit cell) is fixed, and is undecidable otherwise. We do so by introducing an abstraction of pairwise average energy minimisation as a mathematical problem, which covers many existing models. The most influential aspects of this work are showing for the first time: 1) undecidability of average pairwise energy minimisation in general 2) computational hardness for the most natural model with periodic boundary conditions, and 3) novel reductions for a large class of generic pairwise energy functions covering many physical abstractions at once. In particular, we develop a new tool of overlapping digital rhombuses to incorporate the properties of the physical force fields, and we connect it with classical tiling problems. Moreover, we illustrate the power of such reductions by incorporating more physical properties such as charge neutrality, and we show an inapproximability result for the extreme case of the 1D average energy minimisation problem.

Details

MFCS Conference 2019 Conference Paper

Computational Complexity of Synchronization under Regular Constraints

Henning Fernau
Vladimir V. Gusev
Stefan Hoffmann 0001
Markus Holzer 0001
Mikhail V. Volkov 0001
Petra Wolf 0002

Many variations of synchronization of finite automata have been studied in the previous decades. Here, we suggest studying the question if synchronizing words exist that belong to some fixed constraint language, given by some partial finite automaton called constraint automaton. We show that this synchronization problem becomes PSPACE-complete even for some constraint automata with two states and a ternary alphabet. In addition, we characterize constraint automata with arbitrarily many states for which the constrained synchronization problem is polynomial-time solvable. We classify the complexity of the constrained synchronization problem for constraint automata with two states and two or three letters completely and lift those results to larger classes of finite automata.

Details

MFCS Conference 2017 Conference Paper

Attainable Values of Reset Thresholds

Michalina Dzyga
Robert Ferens
Vladimir V. Gusev
Marek Szykula

An automaton is synchronizing if there exists a word that sends all states of the automaton to a single state. The reset threshold is the length of the shortest such word. We study the set RT_n of attainable reset thresholds by automata with n states. Relying on constructions of digraphs with known local exponents we show that the intervals [1, (n^2-3n+4)/2] and [(p-1)(q-1), p(q-2)+n-q+1], where 2 <= p < q <= n, p+q > n, gcd(p, q)=1, belong to RT_n, even if restrict our attention to strongly connected automata. Moreover, we prove that in this case the smallest value that does not belong to RT_n is at least n^2 - O(n^{1. 7625} log n / log log n). This value is increased further assuming certain conjectures about the gaps between consecutive prime numbers. We also show that any value smaller than n(n-1)/2 is attainable by an automaton with a sink state and any value smaller than n^2-O(n^{1. 5}) is attainable in general case. Furthermore, we solve the problem of existence of slowly synchronizing automata over an arbitrarily large alphabet, by presenting for every fixed size of the alphabet an infinite series of irreducibly synchronizing automata with the reset threshold n^2-O(n).

Details

MFCS Conference 2016 Conference Paper

On Synchronizing Colorings and the Eigenvectors of Digraphs

Vladimir V. Gusev
Elena V. Pribavkina

An automaton is synchronizing if there exists a word that sends all states of the automaton to a single state. A coloring of a digraph with a fixed out-degree k is a distribution of k labels over the edges resulting in a deterministic finite automaton. The famous road coloring theorem states that every primitive digraph has a synchronizing coloring. We study recent conjectures claiming that the number of synchronizing colorings is large in the worst and average cases. Our approach is based on the spectral properties of the adjacency matrix A(G) of a digraph G. Namely, we study the relation between the number of synchronizing colorings of G and the structure of the dominant eigenvector v of A(G). We show that a vector v has no partition of coordinates into blocks of equal sum if and only if all colorings of the digraphs associated with v are synchronizing. Furthermore, if for each b there exists at most one partition of the coordinates of v into blocks summing up to b, and the total number of partitions is equal to s, then the fraction of synchronizing colorings among all colorings of G is at least (k-s)/k. We also give a combinatorial interpretation of some known results concerning an upper bound on the minimal length of synchronizing words in terms of v.

Details

Highlights Conference 2016 Conference Abstract

Primitive sets of nonnegative matrices and synchronizing automata

Balázs Gerencsér
Vladimir V. Gusev
Raphaël M. Jungers

A set of nonnegative matrices M={M_1, M_2, …, M_k} is called PRIMITIVE if there exist indices i_1, i_2, …, i_m such that the product M_{i_1} M_{i_2} … M_{i_m} is positive (i. e. has all its entries >0). The length of the shortest such product is called the EXPONENT of M. The concept of primitive sets of matrices comes up in a number of problems within control theory, non-homogeneous Markov chains etc. In my talk I will speak about the recently discovered connections between synchronizing automata and primitive sets of matrices. An automaton is called SYNCHRONIZING if there exist a word w and a state f such that the action of w brings all states to f. On one hand, the properties of synchronizing automata are relatively well studied due to their applications to industrial automation, coding theory, group theory, etc. On the other hand, there is still a persisting interest of the research community to the topic due to one of the most famous open problems in automata theory. Namely, the CERNY CONJECTURE states that the length of the shortest synchronizing word of an n-state automaton is at most (n-1)^2. In my talk I will explain how the aforementioned connections lead to a relatively large number of results about primitive sets of matrices. Namely, we will see that the maximal exponent among all primitive sets of n by n matrices is roughly equal to 3^(n/3). Furthermore, the problem of deciding whether a given set of matrices is primitive is PSPACE-complete. In my talk the set of matrices with no zero rows and columns, denoted by NZ, will receive a special attention due to its intriguing connections to the Cerny conjecture and the recent generalization of Perron-Frobenius theory for this class. I will characterize the computational complexity of different problems related to the exponent of NZ matrix sets, and present a quadratic bound on the exponents of sets belonging to a special subclass. Namely, we will see that the exponent of a set of matrices having total support is bounded by 2n^2 -5n +5. These results are not published. The preprint is available on http: //arxiv. org/abs/1602. 07556.

Details

MFCS Conference 2010 Conference Paper

Slowly Synchronizing Automata and Digraphs

Dimitry S. Ananichev
Vladimir V. Gusev
Mikhail V. Volkov 0001

Abstract We present several infinite series of synchronizing automatafor which the minimum length of reset words is close to the square of the number of states. These automata are closely related to primitive digraphs with large exponent.

Details