Семинар "Математически основи на информатиката", доклад на Александър Барг
2022-07-05 14:00 - 15:30 (Europe/Sofia) | Институт по математика и информатика – БАН, Block 8, 1113 БАН IV км., София, Bulgaria
На 05.07.2022г. oт 14:00 в заседателната зала на ИМИ-БАН
ще се състои сбирка на семинара на секция „Математически основи на информатиката“.
Докладчик ще бъде проф. Александър Барг от Университета на Мериленд.
Той ще изнесе доклад на тема
Remarks on the 1st linear programming bound for binary codes
Abstract: The “linear programming bound” on the rate of binary codes (1977) is a fundamental result in coding theory that continues to attract attention to this day, with new proofs appearing every now and then. I will discuss 2 proofs from about 2006-08, appearing in arXiv:cs/0512025 (Barg-Nogin) and arXiv:math/0702425 (Navon and Samorodnitsky). Both proofs are based on Fourier analytic arguments on the Boolean cube and exhibit interesting parallels and differences (none of them actually uses linear programming). One of the applications enables us to establish upper bounds on the maximum size of binary codes of large distance, d=n/2 – t√n.
Поканват се всички желаещи.

Семинар на секция "Математически основи на информатиката"
2023-03-09 15:00 - 16:00 | Институт по математика и информатика – БАН, Block 8, 1113 БАН IV км., София, Bulgaria
На 9 март 2023 г. (четвъртък) от 15:00 часа в зала 503 на ИМИ-БАН
ще се проведе заседание на семинара на секция „Математически основи на информатиката”. Доклад на тема:

Introduction to the dimer model on the plane: scaling limit and conformal invariance

ще изнесе
д-р Михаил Басок, гостуващ учен по програма ПИКОМ.

Абстракт: Dimer model is a classical model in planar statistical physics. Given a finite graph, the model is described as a probability distribution on the set of dimer covers (=perfect matchings) of the graph. In the case when the graph is planar each dimer cover is described with the so-called height function, which is a certain function on the faces of the graph.

In this talk we consider a particular setup when the graph is given as a subgraph of a square lattice on the plane and the distribution on the space of dimer covers is uniform. Given a simply-connected domain we consider a sequence of such graphs approximating this domain as the step of the lattice tends to zero and sample the dimer model on each of the graphs. Classical theorem of Kenyon asserts that under a certain local combinatorial conditions the sequence of the corresponding (random) height functions has a conformally invariant limit. Moreover, this limit is proven to be the Gaussian free field with Dirichlet boundary conditions in the initial domain.
We will discuss heuristics behind this theorem and the approтach to proving it via discrete complex analysis developed by Kenyon. If time permits, we will also discuss random loop ensembles arising from a pair of two independent dimer covers and its convergence to a conformally invariant limit proved in our joint work with Dmitry Chelkak.

Семинар на секция "Математически основи на информатиката"
2023-05-10 15:00 - 16:00 | Институт по математика и информатика – БАН, Block 8, 1113 БАН IV км., София, Bulgaria
На 10 май 2023 г. (сряда) от 15:00 часа
в зала 503 на ИМИ-БАН
ще се проведе заседание на семинара на секция
„Математически основи на информатиката”. Доклад на тема:

Ternary self-dual codes, Hadamard matrices and related designs

ще изнесе
проф. Владимир Тончев,
Michigan Technological University, Houghton, USA.

Абстракт на доклада може да изтеглите тук.

Семинар на секция "Математически основи на информатиката"
2023-06-27 14:00 - 15:30 | Институт по математика и информатика – БАН, Block 8, 1113 БАН IV км., София, Bulgaria
На 27 юни 2023 г. (вторник) от 14:00 часа
в зала 278 на ИМИ-БАН
ще се проведе заседание на семинара на секция
„Математически основи на информатиката”. Доклад на тема:

The Erdős Box Problem and the Combinatorial Nullstellensatz

ще изнесе
д-р Алексей Гордеев, гостуващ учен към секцията.

Абстракт. The Erdős box problem can be formulated as follows: how many points of {1,2,…,n}^m can we take so that for every m-dimensional box (hyperrectangle with sides parallel to coordinate axes) at least one of its vertices is not taken? When m is fixed and n increases, an order of growth of this number is known only in the case m=2.
I will talk about Alon’s Combinatorial Nullstellensatz and its connection with the Erdős box problem and, more generally, with hypergraph Turán numbers. In particular, I will show how a certain generalization of Combinatorial Nullstellensatz can be used to obtain explicit examples for the Erdős box problem, asymptotically matching best known examples when m<5.

Семинар на секция "Математически основи на информатиката"
2023-08-22 16:00 - 17:30 | Институт по математика и информатика – БАН, Block 8, 1113 БАН IV км., София, Bulgaria
На 22 август 2023 г. (вторник) от 16:00 часа в зала 503 на ИМИ-БАН
ще се проведе заседание на семинара на секция
„Математически основи на информатиката”.
Доклад на тема:
Data Attribution: Scaling up and Applications to Defending Against Backdoor Attacks
ще изнесе
Кристиян Георгиев, докторант в MIT под ръководството на Александър Мондри.
Абстракт. The goal of data attribution is to trace model predictions back to training data. Despite a long line of work towards this goal, existing approaches to data attribution tend to force users to choose between computational tractability and efficacy. That is, computationally tractable methods can struggle with accurately attributing model predictions in non-convex settings (e.g., in the context of deep neural networks), while methods that are effective in such regimes require training thousands of models, which makes them impractical for large models or datasets.
In this talk, I will first introduce TRAK (Tracing with the Randomly-projected After Kernel), a data attribution method that is both effective and computationally tractable for large-scale, differentiable models. Next, I will showcase how to leverage data attribution methods for building defenses against backdoor attacks. In a backdoor attack, an adversary inserts maliciously constructed backdoor examples into a training set to make the resulting model vulnerable to manipulation. I will show that without structural information about the training data distribution, backdoor attacks are indistinguishable from naturally-occurring features in the data–and thus impossible to “detect” in a general sense. With this insight in mind, I will describe how we use TRAK (and other data attribution methods) towards finding features corresponding to the “backdoored” samples.

Семинар на секция "Математически основи на информатиката"
2023-10-31 16:00 - 17:30 | Институт по математика и информатика – БАН, Block 8, 1113 БАН IV км., София, Bulgaria
На 31 октомври 2023 г. (вторник) от 16:00 часа в зала 578 на ИМИ-БАН
ще се проведе заседание на семинара на секция
„Математически основи на информатиката”.
Доклад ще изнесе д-р Константин Воробьов (ИМИ – БАН).
Абстракт. In this work, we consider the problem of determining the exact value of (A_2(n, {d, d+2})) defined as the maximal cardinality of a binary code of length (n) with two possible distances (d) and (d+2). We prove that for fixed even (d) and (n) big enough, an optimal code must be a constant-weight code of weight (d/2+1) with possibly no more than one additional codeword of a different weight.
We also find exact values (A_2(n, {4, 6})) and (A_2(n, {6, 8})) starting from some (n).
This is a joint work with Ivan Landjev.

Семинар на секция "Математически основи на информатиката"
2023-11-10 14:00 - 15:30 | Институт по математика и информатика – БАН, Block 8, 1113 БАН IV км., София, Bulgaria
На 10 ноември 2023 г. (вторник) от 14:00 часа в зала 478 на ИМИ-БАН
ще се проведе заседание на семинара на секция
„Математически основи на информатиката”.
Доклад на тема
On induced (C_4)-free graphs with high average degree
ще изнесе Антонио Жирао.
Абстракт. A long-standing conjecture of Thomassen from the 80’s states that every graph with sufficiently high average degree contains a subgraph with high girth and still preserving large enough average degree. This conjecture has only been resolved in the early 2000’s by Kühn and Osthus in the first non-trivial case i.e. they showed that for every (k), there is (f(k)) such the every graph with average degree at least (f(k)) contains a subgraph which is (C_4)-free with average degree (k).
We will talk about a recent result which strengthens this result of Kühn and Osthus in two ways. First, we prove an analogous induced version and secondly we give much better bounds for the function f allowing us obtain few non-trivial results as simple corollaries. Finally, we use these methods to confirm a conjecture Bonamy et al.
Антонио Жирао e пост-докторант в Оксфордския Университет под ръководството на проф. Алекс Скот. Преди да заеме тази позиция, Антонио работи като пост-докторант в Хайделбергския Университет под ръководството на проф. Феликс Йоос и в Университета в Бирмингам под ръководството на проф. Даниела Кюн и проф. Дерек Остюс. Защитава докторантурата в Университета в Кеймбридж под ръководството на проф. Бела Болобаш през 2018 г.

Семинар на секция "Математически основи на информатиката"
2024-02-08 15:00 - 16:30 | Институт по математика и информатика – БАН, Block 8, 1113 БАН IV км., София, Bulgaria
На 8 февруари 2024 г. (четвъртък) от 15:00 часа в зала 256 на ИМИ-БАН
ще се проведе заседание на семинара на секция
„Математически основи на информатиката”.
Доклад на тема
Extremal problems in Euclidean combinatorial geometry
ще изнесе доц. д-р Данила Черкашин
Абстракт. I will talk about several problems in the intersection of extremal combinatorics and Euclidean geometry. Recent results on the Steiner tree problem, Gilbert-Steiner problem, and Nelson-Hadwiger problem will be presented.
Семинарът може да бъде проследен и на https://meet.jit.si/IMI-MOI-14400

Семинар на секция "Математически основи на информатиката"
2024-10-02 14:00 - 15:30 | Институт по математика и информатика – БАН, Block 8, 1113 БАН IV км., София, Bulgaria
На 2 октомври 2024 г. (сряда) от 14:00 часа в зала 478 на ИМИ-БАН
ще се състои поредната сбирка на семинара на секция
„Математически основи на информатиката”.
Доклад на тема
Lipschitz Permutations on Certain Graphs
ще изнесе Драгомир Грозев.
Абстракт

Семинар на секция "Математически основи на информатиката"
2025-01-08 17:00 - 18:30 | Великотърновски университет, ул. "Теодосий Търновски" № 2, Велико Търново, 5005, Bulgaria
Семинарът по
МАТЕМАТИЧЕСКИ ОСНОВИ НА ИНФОРМАТИКАТА
организиран от
Секция „Математически основи на информатиката“ към ИМИ – БАН и
Факултет „Математика и информатика“ – ВТУ,
Ви кани на поредната сбирка на 8 януари 2025 г. от 17:00 часа в зала 401 на корпус 4 на ВТУ, на която
Prof. Ferruh Özbudak
Sabancı University
Faculty of Engineering and Natural Sciences,
İstanbul – Turkiye
ще изнесе доклад на тема:
Generalizing the Bierbrauer—Friedman bound to mixed-level orthogonal arrays
(joint work with Denis Krotov and Vladimir Potapov)
Abstract: We characterize mixed-level orthogonal arrays it terms of algebraic designs in a special multigraph. We prove a mixed-level analog of the Bierbrauer–Friedman (BF) bound for pure-level orthogonal arrays and show that arrays attaining it are radius-1 completely regular codes (equivalently, intriguing sets, equitable 2-partitions, perfect 2-colorings) in the corresponding multigraph. For the case when the numbers of levels are powers of the same prime number, we characterize, in terms of multispreads, additive mixed-level orthogonal arrays attaining the BF bound. For pure-level orthogonal arrays, we consider versions of the BF bound obtained by replacing the Hamming graph by its polynomial generalization and show that in some cases this gives a new bound.
Acknowledgment: The work of F.Ö. was supported by TÜBİTAK under Grant 223N065.
За тези, които няма да могат да дойдат, предлагаме да се включат онлайн през

Microsoft Teams Имате ли нужда от помощ?

Присъединете се към събранието сега

ИД на събрание: 363 497 232 460

Парола: bF93pw6a

Семинар "Математически основи на информатиката"
2025-07-03 14:30 - 16:00 | Великотърновски университет, ул. "Теодосий Търновски" № 2, Велико Търново, 5005, Bulgaria
Семинарът по
МАТЕМАТИЧЕСКИ ОСНОВИ НА ИНФОРМАТИКАТА
организиран от
Секция „Математически основи на информатиката“ към ИМИ – БАН и
Факултет „Математика и информатика“ – ВТУ,
Ви кани на поредната сбирка на 3 юли 2025 г. от 14:30 часа в зала 508 на учебен корпус 4 на ВТУ, на която
Светослава Минкова
магистърска програма
„Математически структури в информационната сигурност“
ФМИ, Великотърновски университет
ще изнесе доклад на тема:
Weisfeiler-Leman алгоритъм и инварианти за изоморфизъм на графи

Семинар "Математически основи на информатиката"
2025-07-24 14:00 - 15:30 | Институт по математика и информатика – БАН, Block 8, 1113 БАН IV км., София, Bulgaria
Следващата сбирка на семинара на секция
МАТЕМАТИЧЕСКИ ОСНОВИ НА ИНФОРМАТИКАТА
ще се състои в сряда, 24.07.2025, от 14:00 часа, в зала 403 на ИМИ, на която
проф. Марк Айуън
ще изнесе доклад на тема:
Sparse Spectral Methods for Solving High-Dimensional and Multiscale Elliptic PDEs
Проф. Айуън работи в департамента по изчислителна математика в Michigan State University и има широки интереси свързани с обработката на данни и обработката на сигнали. Темата, която предложи за семинара има някои неочаквани връзки с определени шумозащитни кодове.
Резюме. In his monograph “Chebyshev and Fourier Spectral Methods”, John Boyd claimed that, regarding Fourier spectral methods for solving differential equations, “[t]he virtues of the Fast Fourier Transform will continue to improve as the relentless march to larger and larger [bandwidths] continues” [1, pg. 194]. This talk will discuss attempts to further the virtue of the Fast Fourier Transform (FFT) as not only bandwidth is pushed to its limits, but also the dimension of the problem. Instead of using the traditional FFT however, we make a key substitution from the sublinear-time compressive sensing literature: a high-dimensional, sparse Fourier transform (SFT) paired with randomized rank-1 lattice methods. The resulting sparse spectral method rapidly and automatically determines a set of Fourier basis functions whose span is guaranteed to contain an accurate approximation of the solution of a given elliptic PDE. This much smaller, near-optimal Fourier basis is then used to efficiently solve the given PDE in a runtime which only depends on the PDE’s data/solution compressibility and ellipticity properties, while breaking the curse of dimensionality and relieving linear dependence on any multiscale structure in the original problem. Theoretical performance of the method is established with convergence analysis in the Sobolev norm for a general class of nonconstant diffusion equations, as well as pointers to technical extensions of the convergence analysis to more general advection-diffusion-reaction equations. Numerical experiments demonstrate good empirical performance on several multiscale and high-dimensional example problems, further showcasing the promise of the proposed methods in practice.

Съвместно заседание на семинара на МЦМН и семинара на секция МОИ
2025-11-26 16:00 - 17:30 | Институт по математика и информатика – БАН, Block 8, 1113 БАН IV км., София, Bulgaria
26 ноември 2025 г., сряда, от 16:00 ч. в Зала 403 на ИМИ – БАН.
Съвместно заседание на Семинара на МЦМН и Семинара на секция Математически основи на информатиката
Frank Vallentin (Universität zu Köln)
Least distortion Euclidean embeddings of flat tori
Резюме: In the emerging field of bi-Lipschitz invariant theory, one studies embeddings of orbit spaces H/G (H a Hilbert space, G a subgroup of its automorphisms) into simpler Hilbert spaces via distance-preserving maps up to a constant factor.

In this talk, I present an infinite-dimensional semidefinite program that computes least-distortion embeddings of flat tori Rn/L, where L is an n-dimensional lattice, into Hilbert spaces. Using symmetry reduction techniques, this infinite-dimensional semidefinite program reduces to an infinite-dimensional linear program.
Even with this simplification, solving the program remains challenging. By combining this approach with the linear programming bound for spherical designs, combined with brute-force methods, we finally are able to determine the least-distortion embeddings of Rn/Zn, R2/A2, and R8/E8.
(Based on joint work with Arne Heimendahl, Moritz Lücke, Philippe Moustrou, and Marc Christian Zimmermann)

Least distortion Euclidean embeddings of flat tori, ICMS seminar talk by Frank Vallentin

Семинар "Математически основи на информатиката"
2026-05-12 13:00 - 14:30 | Институт по математика и информатика – БАН, Block 8, 1113 БАН IV км., София, Bulgaria
Следващата сбирка на семинара на с
Секция „Математически основи на информатиката“
ще се проведе на 12 май 2026 г. от 13:00 часа в зала 503 на ИМИ – БАН. Доклад на тема
Linear codes and Steiner triple systems
ще изнесе проф. Владимир Тончев (Michigan Technological University).
Резюме
