6 Search Results for "Kolmogorov, Vladimir"

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.57
A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees

Authors: Shuai Shao and Stanislav Živný

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
General factors are a generalization of matchings. Given a graph G with a set π(v) of feasible degrees, called a degree constraint, for each vertex v of G, the general factor problem is to find a (spanning) subgraph F of G such that deg_F(v) ∈ π(v) for every v of G. When all degree constraints are symmetric Δ-matroids, the problem is solvable in polynomial time. The weighted general factor problem is to find a general factor of the maximum total weight in an edge-weighted graph. Strongly polynomial-time algorithms are only known for weighted general factor problems that are reducible to the weighted matching problem by gadget constructions. In this paper, we present a strongly polynomial-time algorithm for a type of weighted general factor problems with real-valued edge weights that is provably not reducible to the weighted matching problem by gadget constructions. As an application, we obtain a strongly polynomial-time algorithm for the terminal backup problem by reducing it to the weighted general factor problem.
Cite as

Shuai Shao and Stanislav Živný. A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 57:1-57:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{shao_et_al:LIPIcs.ISAAC.2023.57,
  author =	{Shao, Shuai and \v{Z}ivn\'{y}, Stanislav},
  title =	{{A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{57:1--57:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.57},
  URN =		{urn:nbn:de:0030-drops-193597},
  doi =		{10.4230/LIPIcs.ISAAC.2023.57},
  annote =	{Keywords: matchings, factors, edge constraint satisfaction problems, terminal backup problem, delta matroids}
}
Document
DOI: 10.4230/LIPIcs.ITP.2023.15
Closure Properties of General Grammars – Formally Verified

Authors: Martin Dvorak and Jasmin Blanchette

Published in: LIPIcs, Volume 268, 14th International Conference on Interactive Theorem Proving (ITP 2023)

Abstract
We formalized general (i.e., type-0) grammars using the Lean 3 proof assistant. We defined basic notions of rewrite rules and of words derived by a grammar, and used grammars to show closure of the class of type-0 languages under four operations: union, reversal, concatenation, and the Kleene star. The literature mostly focuses on Turing machine arguments, which are possibly more difficult to formalize. For the Kleene star, we could not follow the literature and came up with our own grammar-based construction.
Cite as

Martin Dvorak and Jasmin Blanchette. Closure Properties of General Grammars – Formally Verified. In 14th International Conference on Interactive Theorem Proving (ITP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 268, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ITP.2023.15,
  author =	{Dvorak, Martin and Blanchette, Jasmin},
  title =	{{Closure Properties of General Grammars – Formally Verified}},
  booktitle =	{14th International Conference on Interactive Theorem Proving (ITP 2023)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-284-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{268},
  editor =	{Naumowicz, Adam and Thiemann, Ren\'{e}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2023.15},
  URN =		{urn:nbn:de:0030-drops-183906},
  doi =		{10.4230/LIPIcs.ITP.2023.15},
  annote =	{Keywords: Lean, type-0 grammars, recursively enumerable languages, Kleene star}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.72
Parameter Estimation for Gibbs Distributions

Authors: David G. Harris and Vladimir Kolmogorov

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We will consider sampling problems which come from Gibbs distributions, which are families of probability distributions over a discrete space Ω with probability mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max] and H(ω) ∈ {0} ∪ [1, n]. The partition function is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log Z(β_max))/Z(β_min) We develop a number of algorithms to estimate the counts c_x using roughly Õ(q/ε²) samples for general Gibbs distributions and Õ(n²/ε²) samples for integer-valued distributions (ignoring some second-order terms and parameters), We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs and perfect matchings in a graph.
Cite as

David G. Harris and Vladimir Kolmogorov. Parameter Estimation for Gibbs Distributions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 72:1-72:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{harris_et_al:LIPIcs.ICALP.2023.72,
  author =	{Harris, David G. and Kolmogorov, Vladimir},
  title =	{{Parameter Estimation for Gibbs Distributions}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{72:1--72:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.72},
  URN =		{urn:nbn:de:0030-drops-181246},
  doi =		{10.4230/LIPIcs.ICALP.2023.72},
  annote =	{Keywords: Gibbs distribution, sampling}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.31
A New Notion of Commutativity for the Algorithmic Lovász Local Lemma

Authors: David G. Harris, Fotis Iliopoulos, and Vladimir Kolmogorov

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthrough paper of Moser & Tardos and follow-up works revealed that the LLL has intimate connections with a class of stochastic local search algorithms for finding such desirable objects. In particular, it can be seen as a sufficient condition for this type of algorithms to converge fast. Besides conditions for convergence, many other natural questions can be asked about algorithms; for instance, "are they parallelizable?", "how many solutions can they output?", "what is the expected "weight" of a solution?". These questions and more have been answered for a class of LLL-inspired algorithms called commutative. In this paper we introduce a new, very natural and more general notion of commutativity (essentially matrix commutativity) which allows us to show a number of new refined properties of LLL-inspired local search algorithms with significantly simpler proofs.
Cite as

David G. Harris, Fotis Iliopoulos, and Vladimir Kolmogorov. A New Notion of Commutativity for the Algorithmic Lovász Local Lemma. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 31:1-31:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{harris_et_al:LIPIcs.APPROX/RANDOM.2021.31,
  author =	{Harris, David G. and Iliopoulos, Fotis and Kolmogorov, Vladimir},
  title =	{{A New Notion of Commutativity for the Algorithmic Lov\'{a}sz Local Lemma}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{31:1--31:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.31},
  URN =		{urn:nbn:de:0030-drops-147244},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.31},
  annote =	{Keywords: Lov\'{a}sz Local Lemma, Resampling, Moser-Tardos algorithm, latin transversal, commutativity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.77
Testing the Complexity of a Valued CSP Language

Authors: Vladimir Kolmogorov

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Gamma of cost functions, called a language. Recent breakthrough results have established a complete complexity classification of such classes with respect to language Gamma: if all cost functions in Gamma satisfy a certain algebraic condition then all Gamma-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language Gamma is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language Gamma can be tested in O(sqrt[3]{3}^{|D|}* poly(size(Gamma))) time, where D is the domain of Gamma and poly(*) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant delta<1 there is no O(sqrt[3]{3}^{delta|D|}) algorithm, assuming that SETH holds.
Cite as

Vladimir Kolmogorov. Testing the Complexity of a Valued CSP Language. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 77:1-77:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kolmogorov:LIPIcs.ICALP.2019.77,
  author =	{Kolmogorov, Vladimir},
  title =	{{Testing the Complexity of a Valued CSP Language}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{77:1--77:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.77},
  URN =		{urn:nbn:de:0030-drops-106531},
  doi =		{10.4230/LIPIcs.ICALP.2019.77},
  annote =	{Keywords: Valued Constraint Satisfaction Problems, Exponential time algorithms, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/DagSemProc.06051.11
On impossibility of sequential algorithmic forecasting

Authors: Vladimir V'Yugin

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Abstract
The problem of prediction future event given an individual sequence of past events is considered. Predictions are given in form of real numbers $p_n$ which are computed by some algorithm $varphi$ using initial fragments $omega_1,dots, omega_{n-1}$ of an individual binary sequence $omega=omega_1,omega_2,dots$ and can be interpreted as probabilities of the event $omega_n=1$ given this fragment. According to Dawid's {it prequential framework} %we do not consider %numbers $p_n$ as conditional probabilities generating by some %overall probability distribution on the set of all possible events. we consider partial forecasting algorithms $varphi$ which are defined on all initial fragments of $omega$ and can be undefined outside the given sequence of outcomes. We show that even for this large class of forecasting algorithms combining outcomes of coin-tossing and transducer algorithm it is possible to efficiently generate with probability close to one sequences for which any partial forecasting algorithm is failed by the method of verifying called {it calibration}.
Cite as

Vladimir V'Yugin. On impossibility of sequential algorithmic forecasting. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{vyugin:DagSemProc.06051.11,
  author =	{V'Yugin, Vladimir},
  title =	{{On impossibility of sequential algorithmic forecasting}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.11},
  URN =		{urn:nbn:de:0030-drops-6305},
  doi =		{10.4230/DagSemProc.06051.11},
  annote =	{Keywords: Universal forecasting, computable calibration, Dawid's prequential framework, algorithmic randomness, defensive forecasting}
}
  • Refine by Author
  • 3 Kolmogorov, Vladimir
  • 2 Harris, David G.
  • 1 Blanchette, Jasmin
  • 1 Dvorak, Martin
  • 1 Iliopoulos, Fotis
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Dawid's prequential framework
  • 1 Exponential Time Hypothesis
  • 1 Exponential time algorithms
  • 1 Gibbs distribution
  • 1 Kleene star
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2023
  • 1 2006
  • 1 2019
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact