@article{1794,
abstract = {We consider Conditional random fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights.},
author = {Kolmogorov, Vladimir and Takhanov, Rustem},
journal = {Algorithmica},
number = {1},
pages = {17 -- 46},
publisher = {Springer},
title = {{Inference algorithms for pattern-based CRFs on sequence data}},
doi = {10.1007/s00453-015-0017-7},
volume = {76},
year = {2016},
}
@misc{5557,
abstract = {Small synthetic discrete tomography problems.
Sizes are 32x32, 64z64 and 256x256.
Projection angles are 2, 4, and 6.
Number of labels are 3 and 5.},
author = {Swoboda, Paul},
keywords = {discrete tomography},
publisher = {IST Austria},
title = {{Synthetic discrete tomography problems}},
doi = {10.15479/AT:ISTA:46},
year = {2016},
}
@inproceedings{1193,
abstract = {We consider the recent formulation of the Algorithmic Lovász Local Lemma [1], [2] for finding objects that avoid "bad features", or "flaws". It extends the Moser-Tardos resampling algorithm [3] to more general discrete spaces. At each step the method picks a flaw present in the current state and "resamples" it using a "resampling oracle" provided by the user. However, it is less flexible than the Moser-Tardos method since [1], [2] require a specific flaw selection rule, whereas [3] allows an arbitrary rule (and thus can potentially be implemented more efficiently). We formulate a new "commutativity" condition, and prove that it is sufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additional assumption. We then show that existing resampling oracles for perfect matchings and permutations do satisfy this condition. Finally, we generalize the precondition in [2] (in the case of symmetric potential causality graphs). This unifies special cases that previously were treated separately.},
author = {Kolmogorov, Vladimir},
booktitle = {Proceedings - Annual IEEE Symposium on Foundations of Computer Science},
location = {New Brunswick, NJ, USA },
publisher = {IEEE},
title = {{Commutativity in the algorithmic Lovasz local lemma}},
doi = {10.1109/FOCS.2016.88},
volume = {2016-December},
year = {2016},
}
@inproceedings{1231,
abstract = {We study the time-and memory-complexities of the problem of computing labels of (multiple) randomly selected challenge-nodes in a directed acyclic graph. The w-bit label of a node is the hash of the labels of its parents, and the hash function is modeled as a random oracle. Specific instances of this problem underlie both proofs of space [Dziembowski et al. CRYPTO’15] as well as popular memory-hard functions like scrypt. As our main tool, we introduce the new notion of a probabilistic parallel entangled pebbling game, a new type of combinatorial pebbling game on a graph, which is closely related to the labeling game on the same graph. As a first application of our framework, we prove that for scrypt, when the underlying hash function is invoked n times, the cumulative memory complexity (CMC) (a notion recently introduced by Alwen and Serbinenko (STOC’15) to capture amortized memory-hardness for parallel adversaries) is at least Ω(w · (n/ log(n))2). This bound holds for adversaries that can store many natural functions of the labels (e.g., linear combinations), but still not arbitrary functions thereof. We then introduce and study a combinatorial quantity, and show how a sufficiently small upper bound on it (which we conjecture) extends our CMC bound for scrypt to hold against arbitrary adversaries. We also show that such an upper bound solves the main open problem for proofs-of-space protocols: namely, establishing that the time complexity of computing the label of a random node in a graph on n nodes (given an initial kw-bit state) reduces tightly to the time complexity for black pebbling on the same graph (given an initial k-node pebbling).},
author = {Alwen, Joel F and Chen, Binyi and Kamath Hosdurg, Chethan and Kolmogorov, Vladimir and Pietrzak, Krzysztof Z and Tessaro, Stefano},
location = {Vienna, Austria},
pages = {358 -- 387},
publisher = {Springer},
title = {{On the complexity of scrypt and proofs of space in the parallel random oracle model}},
doi = {10.1007/978-3-662-49896-5_13},
volume = {9666},
year = {2016},
}
@article{1353,
abstract = {We characterize absorption in finite idempotent algebras by means of Jónsson absorption and cube term blockers. As an application we show that it is decidable whether a given subset is an absorbing subuniverse of an algebra given by the tables of its basic operations.},
author = {Barto, Libor and Kazda, Alexandr},
journal = {International Journal of Algebra and Computation},
number = {5},
pages = {1033 -- 1060},
publisher = {World Scientific Publishing},
title = {{Deciding absorption}},
doi = {10.1142/S0218196716500430},
volume = {26},
year = {2016},
}
@article{1377,
abstract = {We consider the problem of minimizing the continuous valued total variation subject to different unary terms on trees and propose fast direct algorithms based on dynamic programming to solve these problems. We treat both the convex and the nonconvex case and derive worst-case complexities that are equal to or better than existing methods. We show applications to total variation based two dimensional image processing and computer vision problems based on a Lagrangian decomposition approach. The resulting algorithms are very effcient, offer a high degree of parallelism, and come along with memory requirements which are only in the order of the number of image pixels.},
author = {Kolmogorov, Vladimir and Pock, Thomas and Rolinek, Michal},
journal = {SIAM Journal on Imaging Sciences},
number = {2},
pages = {605 -- 636},
publisher = {Society for Industrial and Applied Mathematics },
title = {{Total variation on a tree}},
doi = {10.1137/15M1010257},
volume = {9},
year = {2016},
}
@article{1612,
abstract = {We prove that whenever A is a 3-conservative relational structure with only binary and unary relations,then the algebra of polymorphisms of A either has no Taylor operation (i.e.,CSP(A)is NP-complete),or it generates an SD(∧) variety (i.e.,CSP(A)has bounded width).},
author = {Kazda, Alexandr},
journal = {Algebra Universalis},
number = {1},
pages = {75 -- 84},
publisher = {Springer},
title = {{CSP for binary conservative relational structures}},
doi = {10.1007/s00012-015-0358-8},
volume = {75},
year = {2016},
}
@inproceedings{1636,
abstract = {Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism R→ΓΓ between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a prominent research direction, especially for the fixed template CSPs where the right side ΓΓ is fixed and the left side R is unconstrained.
Far fewer results are known for the hybrid setting that restricts both sides simultaneously. It assumes that R belongs to a certain class of relational structures (called a structural restriction in this paper). We study which structural restrictions are effective, i.e. there exists a fixed template ΓΓ (from a certain class of languages) for which the problem is tractable when R is restricted, and NP-hard otherwise. We provide a characterization for structural restrictions that are closed under inverse homomorphisms. The criterion is based on the chromatic number of a relational structure defined in this paper; it generalizes the standard chromatic number of a graph.
As our main tool, we use the algebraic machinery developed for fixed template CSPs. To apply it to our case, we introduce a new construction called a “lifted language”. We also give a characterization for structural restrictions corresponding to minor-closed families of graphs, extend results to certain Valued CSPs (namely conservative valued languages), and state implications for (valued) CSPs with ordered variables and for the maximum weight independent set problem on some restricted families of graphs.},
author = {Kolmogorov, Vladimir and Rolinek, Michal and Takhanov, Rustem},
location = {Nagoya, Japan},
pages = {566 -- 577},
publisher = {Springer},
title = {{Effectiveness of structural restrictions for hybrid CSPs}},
doi = {10.1007/978-3-662-48971-0_48},
volume = {9472},
year = {2015},
}
@inproceedings{1637,
abstract = {An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. We study, assuming that P ≠ NP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in {0, ∞} corresponds to ordinary CSPs, where one deals only with the feasibility issue and there is no optimization. This case is the subject of the Algebraic CSP Dichotomy Conjecture predicting for which constraint languages CSPs are tractable (i.e. solvable in polynomial time) and for which NP-hard. The case when all allowed functions take only finite values corresponds to finite-valued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Zivny. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e. the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs.},
author = {Kolmogorov, Vladimir and Krokhin, Andrei and Rolinek, Michal},
location = {Berkeley, CA, United States},
pages = {1246 -- 1258},
publisher = {IEEE},
title = {{The complexity of general-valued CSPs}},
doi = {10.1109/FOCS.2015.80},
year = {2015},
}
@inproceedings{1675,
abstract = {Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system. In this work, we put forward an alternative concept for PoWs - so-called proofs of space (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model (with one additional mild assumption required for the proof to go through), using graphs with high “pebbling complexity” and Merkle hash-trees. We discuss some applications, including follow-up work where a decentralized digital currency scheme called Spacecoin is constructed that uses PoS (instead of wasteful PoW like in Bitcoin) to prevent double spending. The main technical contribution of this work is the construction of (directed, loop-free) graphs on N vertices with in-degree O(log logN) such that even if one places Θ(N) pebbles on the nodes of the graph, there’s a constant fraction of nodes that needs Θ(N) steps to be pebbled (where in every step one can put a pebble on a node if all its parents have a pebble).},
author = {Dziembowski, Stefan and Faust, Sebastian and Kolmogorov, Vladimir and Pietrzak, Krzysztof Z},
location = {Santa Barbara, CA, United States},
pages = {585 -- 605},
publisher = {Springer},
title = {{Proofs of space}},
doi = {10.1007/978-3-662-48000-7_29},
volume = {9216},
year = {2015},
}