November 2023 - TCS-l - kam.mff.cuni.cz

Noon seminar 24 Feb
by tyomkyn 25 Jun '24

25 Jun '24

Dear all, This week we begin this semester's noon seminar series. Our first speaker on Thursday 24 Feb is Tomas Juškevičius (Czech Academy of Sciences). Please find the title and abstract attached below. For more information on the upcoming noon lectures, please visit https://www.mff.cuni.cz/en/kam/teaching-and-seminars/noon-lectures With best regards, Misha. -------------------------------------- Anticoncentration of sums of random vectors: on conjectures of Leader-Radcliffe and Lee Jones Tomas Juškevičius Czech Academy of Sciences February 24, 2022, 12:20 in S6 Abstract In this talk we shall address the topic anticoncentration inequalities for sums of random vectors. In particular, we shall asymptotically establish two conjectures: one by Lee Jones (1978) and another by Leader-Radcliffe (1994). Perhaps surprisingly, the essential ingredient to establish the latter result is the Strong Perfect Graph Theorem by Chudnovsky, Robertson, Seymour and Thomas (2002). The talk is based on recent joint work with V. Kurauskas (Vilnius University). ----------------------------------------

4 120

REIMINDER: 28.11.2023 10:00 Hans Raj Tiwary - 126. matematické kolokvium
by Petra Milstainova 28 Nov '23

28 Nov '23

> Vazena pani, vazeny pane > > Zasilame Vam pozvanku na prednasku doc. H. R. Tiwaryho, ktera > se kona na MFF UK (Praha) v utery 28. listopadu. Budeme radi, kdyz > informaci o ni predate kolegynim a kolegum. > > Prejeme pekny den. > > Za organizatory, > > Jaroslav Nesetril a Martin Klazar > > (pdf pozvanky - obsahuje laudatio a dalsi informace o kolokviich: > https://kam.mff.cuni.cz/~klazar/tiwary.pdf) > ____________________________________________________________________ > > 126. kolokvium: > > LIMITATIONS OF LINEAR PROGRAMMING > > H. R. Tiwary > > utery 28. listopadu 2023 v 10:00, aula (refektar), prvni patro > > MFF UK, Malostranske nam. 25, Praha 1 > ____________________________________________________________________ > > Abstract. > Linear Programming is a pervasive tool in algorithm design for > optimization problems. Linear Programs (LPs) are known to be able to > effectively model > any problem that can be efficiently solved on a computer. But are they > also able > to efficiently model NP-hard problems? An affirmative answer to this > question will > settle the P vs. NP problem affirmatively, and so it is no surprise > that the answer is > no. However, attempts to prove such limits on the power of LPs lead us > to explore > interesting connections to communication complexity. In this talk, I > will explore such > a connection that resulted in a proof that the Traveling Salesman > Problem cannot > be solved well using LPs. > I will first discuss the subtleties involved in making the above claim > precise. Then > I will describe the result, its connection to communication > complexity, and various > generalizations to the quantum setting and beyond. The talk is based > on joint work > with Samuel Fiorini, Serge Massar, Sebastian Pokutta, and Ronald de Wolf. > ____________________________________________________________________ > > > > > > > > >

1 0

gratulujeme, máte dar ve výši 1 000 000 EUR
by infoadmin＠nextdkc.org 14 Nov '23

14 Nov '23

Gratulujeme!!!!!!!!! Vaše e-mailová adresa byla vybrána pro príspevek ve výši 1 000 000,00 € od Manuela Franca, víteze jackpotu 768 milionu dolaru. Pro další informace prosím kontaktujte francodonation(a)gmail.com E-mail: francodonation(a)gmail.com Pozdravy, Manuel Franco,

1 0

REMINDER: 9. 11. 2023 125. matematické kolokvium - prof. Granville
by Petra Milstainova 09 Nov '23

09 Nov '23

The Colloquium is today (Thursday) November 9th, 2023 from 4PM ____________________________________________________________________ 125. matematicke kolokvium: WHAT IS THE ROLE PROOF PLAYS IN PURE MATHEMATICAL RESEARCH AND WILL AI CHANGE THAT? A. Granville ctvrtek 9. listopadu 2023 v 16:00, poslucharna S5, druhe patro MFF UK, Malostranske nam. 25, Praha 1 ____________________________________________________________________ Abstract. We largely understand mathematics by how we develop proofs, in particular the issues that arise as we understand enough, in detail, to construct a proof. Computer assistance in cutting-edge proofs is now a reality. At the moment its role is small -- helping unsure authors verify that they have not overlooked an issue in a complicated proof, but it is not difficult to predict that this is just the start. For example computers might soon play a more prominent role, for example by filling in the details from a basic plan, efficiently finding out how to make the details work. Then what? As our role is diminished, what becomes the function of a research mathematician? In this lecture we will start from Aristotle's suggestion of building understanding from ``primitives'', and survey how mathematicians traditionally function today. We will then discuss some of the developments with computer assistance, particularly Lean, and what will happen with that in the foreseeable future. One goal is to discuss the question ``If Lean tells you that a proof is correct, what should you believe?'' ____________________________________________________________________ (pdf pozvanky - obsahuje laudatio, fotografii a dalsi informace o kolokviich: https://kam.mff.cuni.cz/~klazar/granville.pdf)

1 0

unfinished workshop announcement
by Mykhaylo Tyomkyn 02 Nov '23

02 Nov '23

Dear all, I am forwarding Martin Loebl's invitation to the UNFINISHED workshop happening next week at Malá Strana, please see below. Furthermore, there will be a noon lecture next Thursday, 9 Nov; I will send out an announcement on Monday. This week, as I wrote, there is no noon lecture. Best regards, MT CoSP Workshop UNFINISHEDm November 6-8, MFF UK Malostranské nám 25 Prague 1 Czechia CoSP is the H2020-MSCA-RISE project number 823748 funded by the European Union. This workshop aims at highlighting extensively studied but still open conjectures falling into the project's domain. Programme: each day 4PM- 6PM two lectures, one remote and one presently in Malá Strana, mornings devoted to discussions with the invited speakers Monday Nov 6 S1 (discrete math) Sophie Spirkl (zoom talk) and Nicolas Trotignon Tuesday Nov 7 S1 (physics and geometry) Marta Pavelka (zoom talk) and Bergfinnur Durhuis Wednesday Nov 8 S7 (theoretical computer science) Michal Koucky (zoom talk) and Ron Holzman Zoom meeting (please do not post in web) Join Zoom Meeting https://cesnet.zoom.us/j/99700372845?pwd=a0pSaWlIVUd3UzhtSHg3TVJaNlZYZz09 Meeting ID: 997 0037 2845 Passcode: 034058 Abstracts: Sophie Spirkl, U. Waterloo, Canada: 2-colouring tournaments Colouring a tournament means partitioning its vertex set into transitive subsets. Unlike for graphs, even 2-colouring is NP-complete for tournaments. In the graph setting, much progress has been made on determining the complexity of 3-colouring graphs with a forbidden induced subgraph. In the tournament setting, we don't even have a sensible conjecture for which tournaments make 2-colouring easy when excluded. Jointly left unfinished with Alvaro Carbonero, Sepehr Hajebi and Yanjia Li. Nicolas Trotignon, CNRS, LIP, ENS de Lyon, France: Is there a minimal non-chi-bounded hereditary class? The "unfinished question" proposed for the workshop is all in the title, except maybe for some needed definitions that are given now, followed by some motivation. A class of graphs is hereditary if it's closed under taking induced subgraphs. A hereditary class of graph is chi-bounded if there exists a function f such that all graphs in the class satisfy chi(G) <= f(omega(G)). Therefore, a hereditary class C is non-chi-bounded if there exists an integer k such that for all integer l, there exists a graph G in C satisfying omega(G) = k and chi(G) >= l. A non-chi-bounded hereditary class C is minimal if all its proper hereditary subclasses are chi-bounded. Equivalently, C is minimal if for all H in C, the class of H-free graphs from C is chi-bounded (a graph is H-free if it does not contain H as an induced subgraph). Seemingly, no minimal hereditary non-chi-bounded class is known. It might be that none exists, and proving this would yield a beautiful and general theorem. While it would be interesting that some minimal non-chi-bounded class exists, because each such class would be a kind of best-possible source of counter-examples to conjectures stating that a class is chi-bounded. The talk will present a recent work by Édouard Bonnet, Romain Bourneuf, Julien Duron, Stéphan Thomassé and the speaker, showing that the classical Zykov's construction of triangle-free graphs of high chromatic number is far from being minimal. It contains graphs of high chromatic number with several structural restrictions: low connectivity or presence of twins, and high odd girth. Marta Pavelka, Cornegie Mellon University U.S.A.: On triangulations of 3-spheres The question ``How many triangulations of the 3-sphere with a given number of tetrahedra are there?'' has been around for a while. It was proposed by Bergfinnur Durhuus and Thordur Jonsson in 1995 in the context of the quantum gravity model and its convergence. Five years later, Mikhael Gromov listed it as one of the fundamental questions of topology. More specifically, it remains an open problem whether there are exponentially many of these triangulations in terms of the number of facets or if there are more. In this talk, we will see the current progress and directions researchers are taking to tackle this question. Moreover, we will look at classes of 3-spheres (or even d-spheres) that are proven to have an exponential size, including the 2-locally constructible spheres. Bergfinnur Durhuis, Copenhagen University, Danemark: Combinatorial Questions in Quantum Gravity In attempts to formulate a regularized model of quantum gravity one encounters interesting combinatorial problems related to counting certain geometric objects, like combinatorial manifolds, subject to certain (topological) constraints. This lecture will serve to formulate some such questions and to present a few details on their background as well as to discuss some partial results. Michal Koucky, IUUK MFF UK Prague Czech Republic: Locally consistent decomposition of strings with applications to edit distance sketching In this talk I will present a new locally consistent decomposition of strings. Each string x is decomposed into blocks that can be described by grammars of size O(k) (using some amount of randomness and ignoring poly-log factors). If we take two strings x and y of edit distance at most k then their block decomposition uses the same number of grammars and the i-th grammar of x is the same as the i-th grammar of y except for at most k indexes i. The edit distance of x and y equals to the sum of edit distances of pairs of blocks where x and y differ. This decomposition has applications to edit distance sketching and streaming approximate pattern matching algorithms. Joint work with Sudatta Bhattacharya. Ron Holzman, Technion Israel: Fair Division via Quantile Shares Joint work with Yakov Babichenko, Michal Feldman and Vishnu V. Narayan. We consider the problem of fair division, where a set of indivisible goods should be distributed fairly among a set of agents with valuations over bundles of goods. To capture fairness, we adopt the notion of shares, by which every agent has a fair share, according to some definition, and an allocation is considered fair if the value of every agent for her bundle (weakly) exceeds her fair share. We introduce a new notion of shares in which an agent deems a bundle fair or unfair based on how it compares to her value in a uniform allocation of the goods. Specifically, for every q in [0,1], a bundle is q-quantile fair if the probability of getting a (weakly) worse bundle in a uniform allocation is at least q. The question that drives us in this work is the feasibility of q-quantile shares. Namely, for what values of q, every profile of (monotone) valuations admits a q-quantile fair allocation. Our main result establishes a strong connection between the feasibility of quantile shares and the classical Erdos Matching Conjecture. Specifically, we show that if the rainbow version of the Erdos Matching Conjecture is true, then the 1/(2e)-quantile share is feasible with respect to all monotone valuations, and this result is tight up to a factor of 2; that is, the q-quantile share is infeasible for q > 1/e. In addition, we provide unconditional feasibility results for special cases. Specifically, we show that every profile of additive (respectively, unit-demand or matroid-rank) valuations admits a q-quantile fair allocation for q = 0.14/e (respectively, for q = 1/e).

1 0

2024

2023

2022

TCS-l November 2023