Mathematical Logic and Discrete Mathematics at PDMI

Вторник, 26 сентября, комната 412. Начало в 18:30.

Докладчик: О. Етеревский.

Определим число Кармайкла порядка m как такое составное число n, что возведение в n-ую степень задает эндоморфизм любой Z/nZ-алгебры, которая может быть порождена как Z/nZ-модуль m элементами. В докладе будет приведена чисто арифметическая интерпретация этого определения. Кроме того, будет доказана нижняя оценка на число простых делителей числа Кармайкла n-го порядка.

Вторник, 19 сентября, комната 106. Начало в 12:00.

Докладчик: Д. В. Карпов.

ОСТОВНОЕ ДЕРЕВО С БОЛЬШИМ КОЛИЧЕСТВОМ ВИСЯЧИХ ВЕРШИН
В 1973 году B.Zelinka предложил алгоритм выделения в графе дерева с максимально возможным количеством висячих вершин. однако, до настоящего момента не опубликовано ни одной работы с оценкой на такое количество. Именно этому вопросу и будет посвящен доклад. будет доказано, что в связном графе, в котором никакие две вершины степени 2 не смежны, есть остовное дерево, в котором более 1/5 всех вершин висячие. будет доказана точность этой оценки.

Вторник, 12 сентября, комната 106. Начало в 12:00.

Докладчик: Б. Ю. Конев.

доклад по статье П.Пудлака
LOWER BOUNDS FOR RESOLUTION AND CUTTING PLANE PROOFS AND MONOTONE COMPUTATIONS
Абстракт статьи:
We prove an exponential lower bound on the length of cutting plane proofs. The proof uses an extension of a lower bound for monotone circuits to circuits which compute with real numbers and use nondecreasing functions as gates. the latter result is of independent integers, since, in particular, it implies an exponential lower bound for some arithmetic circuits.

Вторник, 5 сентября, комната 412. Начало в 12:00.

Докладчик: М. А. Всемирнов.

ЯВНЫЕ КОНСТРУКЦИИ СЕМЕЙСТВ ПЕРЕСТАНОВОК, НЕЗАВИСИМЫХ ОТНОСИТЕЛЬНО МИНИМУМА
множество перестановок s называется независимым по k относительно минимума (k-min-wise independent), если для любого набора x_1,...,x_k количество таких перестановок s из s, что s(x_1) < s(x_2), ... , s(x_1) < s(x_k), равно |s|/k. разумеется, представляют интерес множества s как можно меньшей мощности, в частности, отличные от симметрической и знакопеременной групп.
в общем случае известны либо теоремы существования, либо конструкции таких множеств, требующие решения задачи большой вычислительной сложности.
в докладе будет изложена явная простая конструкция при k=4. конструкция использует проективную геометрию. кроме того, будет предложен ряд открытых вопросов.

Cреда, 31 мая, комната 412. Начало в 14:00.

Докладчик: В. Баргачев.

TITLE: OVERVIEW OF PROBABILISTIC PRIMALITY TESTS, ESPECIALLY THE "VERY STRONG PRIMARILITY TEST" BY WILLIAM ADAMS AND DANIEL SHANKS.
There is no known "good" deterministic algorithm for deciding if the given number p is prime. "Good" means algorithm whose running time is bounded by polynomial of log(p). however, there are some "probabilistic" algorithms: they can decide whether given number is composite or prime with probability (1-a). It is a rather convenient form since after running such an algorithm n times, we obtain either p is composite or p is prime with probability (1-a^n).
Well known are euler test with a=1/2, and Miller-Rabin's test with a=1/4. adams and shanks introduced a test for which most probably a=1/216 -- this will be the focus of our talk.

Вторник, 18 апреля, комната 412. Начало в 13:30.

Докладчик: А. Тискин.

НЕСТАНДАРТНЫЕ ПРИМЕНЕНИЯ ЭКСТРЕМАЛЬНОЙ ТЕОРИИ ГРАФОВ
В 1975 г. Семереди сформулировал и доказал лемму о регулярном разбиении (Szemeredi's regularity lemma). В последние годы этот результат стал активно использоваться для решения экстремальных задач теории графов, однако его применение возможно и в других областях математики. В докладе будет рассказано о двух задачах, решенных при помощи нестандартного применения леммы семереди: задача об асимптотической плотности упаковки трехмерных полимино, и задача о коммуникационной сложности умножения булевых матриц.

Вторник, 4 апреля, комната 412. Начало в 15:00.

Докладчик: А. Косовская.

ОПИСАНИЕ ХРОМАТИЧЕСКОГО ЧИСЛА ГРАФА И ЧИСЛА НЕЗАВИСИМОСТИ С ПОМОЩЬЮ ПОЛИНОМА, ОПРЕДЕЛЯЕМОГО ГРАФОМ
Будут рассказаны связи между некоторым полиномом, задаваемым графом и числовыми характеристиками этого графа. отсюда выводятся некоторые оценки на число независимости графа. В частности, будут рассказаны результаты статьи L.Lovasz "Stable set and polynomials". Доклад тематически связан с докладом Д.Карпова и Ю.В.матиясевича 21 декабря 1999 года.

Вторник, 28 марта, комната 412. Начало в 15:00.

Докладчик: Э. А. Гирш.

КВАНТОВЫЕ ВЫЧИСЛЕНИЯ С ТОЧКИ ЗРЕНИЯ ТЕОРИИ СЛОЖНОСТИ
Определяется класс вычислительных задач BQP (по аналогии с BPP). определение не несет "физической" терминологии, но охватывает все свойства квантовых вычислений. рассматривается место этого класса в общей картине сложностных классов.
Основной источник: L.Fortnow "One complexity theorist's view of quantum computing" (http://xxx.lanl.gov/abs/quant-ph/0003035)

Вторник, 21 марта, комната 412. Начало в 15:00.

Докладчик: В. Жижкун.

ДОКАЗАТЕЛЬСТВА КАК ИГРЫ
доклад на основе статьи p.pudlak "proofs as games" (http://www.math.cas.cz/~pudlak/prfgame.ps)
Предлагается интересный способ получения нижней оценки (экспоненциальной) размера вывода pigeon hole principle методом резолюций. Вывод рассматривается как игра двух игроков: prover'а, который пытается получить противоречие из отрицания доказываемой формулы, и его оппонента, который пытается ему в этом помешать. В таких терминах нижняя оценка соответствует оптимальной стратегии оппонента.

Понедельник, 13 марта, комната 203. Начало в 14:30.

Докладчик: Б. Конев.

Доклад будет сделан на основе статьи Atserias, Galesi, Gavald`a
MONOTONE PROOFS OF THE PIGEON HOLE PRINCIPLE
Abstract of this paper: We study the complexity of proving the Pigeon Hole Principle (PHP) in a monotone variant of the Gentzen Calculus, also known as Geometric Logic. We show that the standard encoding of the PHP as a monotone sequent admits quasipolynomial-size proofs in this system. This result is a consequence of deriving the basic properties of certain quasipolynomial-size monotone formulas computing the boolean threshold functions. Since it is known that the shortest proofs of the PHP in systems such as Resolution or Bounded Depth Frege are exponentially long, it follows from our result that these systems are exponentially separated from the monotone Gentzen Calculus. We also consider the monotone sequent (CLIQUE) expressing the clique-coclique principle defined by Bonet, Pitassi and Raz (1997). We show that monotone proofs for this sequent can be easily reduced to monotone proofs of the one-to-one and onto PHP, and so CLIQUE also has quasipolynomial-size monotone proofs. As a consequence, Cutting Planes with polynomially bounded coefficients is also exponentially separated from the monotone Gentzen Calculus. Finally, a simple simulation argument implies that these results extend to the Intuitionistic Gentzen Calculus. Our results partially answer some questions left open by P. Pudl'ak.
Full text: ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2000/TR00-008/index.html