Zobrazeno 1 - 10
of 60
pro vyhledávání: '"Mathematics of computing → Probability and statistics"'
This report documents the program and the outcomes of Dagstuhl Seminar 22482 "Counting and Sampling: Algorithms and Complexity". We document the talks presented, covering many advances in the area made over the last five years. As well, we document t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1a1f5bbe6a5ae7fdd8aaeabff2b7e954
This report documents the program and the outcomes of Dagstuhl Perspectives Workshop 22262 "Human-Centered Artificial Intelligence". The goal of this Dagstuhl Perspectives Workshops is to provide the scientific and technological foundations for desig
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::305da92333fe26324b4bbd0900cb7c5a
Every language recognized by a non-deterministic finite automaton can be recognized by a deterministic automaton, at the cost of a potential increase of the number of states, which in the worst case can go from n states to 2ⁿ states. In this articl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4fa11efd8cda0aadc031bacda61f8403
Autor:
Mossé, Milan
Dwork, Hardt, Pitassi, Reingold, & Zemel [Dwork et al., 2012] introduced two notions of fairness, each of which is meant to formalize the notion of similar treatment for similarly qualified individuals. The first of these notions, which we call addit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b25380019acf12520450b7028700bcee
We study random constraint satisfaction problems (CSPs) at large clause density. We relate the structure of near-optimal solutions for any Boolean Max-CSP to that for an associated spin glass on the hypercube, using the Guerra-Toninelli interpolation
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::49ef9de98fde65762111c88672eacd1f
http://arxiv.org/abs/2210.03006
http://arxiv.org/abs/2210.03006
Autor:
Nandakumar, Satyadev, Pulari, Subin
Publikováno v:
Theory of Computing Systems.
We initiate the study of effective pointwise ergodic theorems in resource-bounded settings. Classically, the convergence of the ergodic averages for integrable functions can be arbitrarily slow [Ulrich Krengel, 1978]. In contrast, we show that for a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1e5515ce56ea3a6bbc85ae736623ca63
https://doi.org/10.1007/s00224-022-10094-9
https://doi.org/10.1007/s00224-022-10094-9
Autor:
d'Orsi, Tommaso, Trevisan, Luca
We define a novel notion of ``non-backtracking'' matrix associated to any symmetric matrix, and we prove a ``Ihara-Bass'' type formula for it. We use this theory to prove new results on polynomial-time strong refutations of random constraint satisfac
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::51ec3633b8df6cfa6002930b819d8ffd
http://arxiv.org/abs/2204.10881
http://arxiv.org/abs/2204.10881
Autor:
Los, Dimitrios, Sauerwald, Thomas
We study the repeated balls-into-bins process introduced by Becchetti, Clementi, Natale, Pasquale and Posta (2019). This process starts with $m$ balls arbitrarily distributed across $n$ bins. At each round $t=1,2,\ldots$, one ball is selected from ea
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2adf992486ea1042f7f9a23a7cd6b0ce
http://arxiv.org/abs/2203.12400
http://arxiv.org/abs/2203.12400
Publikováno v:
International Symposium on Computational Geometry
We consider point sets in the real projective plane $\mathbb{R}P^2$ and explore variants of classical extremal problems about planar point sets in this setting, with a main focus on Erdős--Szekeres-type problems. We provide asymptotically tight boun
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f67d05e34cc52dd3f2a982b402027f34
Autor:
Kiefer, Stefan, Tang, Qiyi
Publikováno v:
Concur 2022- 33RD INTERNATIONAL CONFERENCE ON CONCURRENCY THEORY
A labelled Markov decision process (MDP) is a labelled Markov chain with nondeterminism; i.e., together with a strategy a labelled MDP induces a labelled Markov chain. Motivated by applications to the verification of probabilistic noninterference in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::863cfc0bb6f31b581b6e724f1aed9c4c
https://doi.org/10.4230/lipics.concur.2022.32
https://doi.org/10.4230/lipics.concur.2022.32