1,720,962 research outputs found
A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
Get PDFIn the constraint satisfaction problem (), the aim is to find an assignment of values to a set of variables subject to specified constraints. In the minimum cost homomorphism problem (), one is additionally given weights for every variable and value , and the aim is to find an assignment to the variables that minimizes . Let denote the problem parameterized by the set of predicates allowed for constraints. is related to many well-studied combinatorial optimization problems, and concrete applications can be found in, for instance, defence logistics and machine learning. We show that can be studied by using algebraic methods similar to those used for CSPs. With the aid of algebraic techniques, we classify the
computational complexity of for all choices of . Our result settles a general dichotomy conjecture previously resolved only for certain classes of directed graphs, [Gutin, Hell, Rafiey, Yeo, European J. of Combinatorics, 2008]
Hybrid VCSPs with Crisp and Valued Conservative Templates
Get PDFA constraint satisfaction problem (CSP) is a problem of computing a homomorphism R -> G between two relational structures, e.g. between two directed graphs.
Analyzing its complexity has been a very fruitful research direction, especially for fixed template CSPs (or, non-uniform CSPs), denoted CSP(G),
in which the right side structure G is fixed and the left side structure R is unconstrained.
Recently, the hybrid setting, written CSP_H(G), where both sides are restricted simultaneously, attracted some attention.
It assumes that R is taken from a class of relational structures H (called the structural restriction) that additionally is closed under inverse homomorphisms. The last property allows to exploit an algebraic machinery that has been developed for fixed template CSPs. The key concept that connects hybrid CSPs with fixed-template CSPs is the so called lifted language. Namely, this is a constraint language G_R that can be constructed from an input R. The tractability of the language G_R for any input R from H is a necessary condition for the tractability of the hybrid problem.
In the first part we investigate templates G for which the latter condition is not only necessary, but also is sufficient. We call such templates G widely tractable. For this purpose, we construct from G a new finite relational structure G' and define a maximal structural restriction H_0 as a class of structures homomorphic to G'.
For the so called strongly BJK templates that probably captures all templates, we prove that wide tractability is equivalent to the tractability of CSP_{H_0}(G).
Our proof is based on the key observation that R is homomorphic to G' if and only if the core of G_R is preserved by a Siggers polymorphism.
Analogous result is shown for conservative valued CSPs
Almost pairwise independence and resilience to deep learning attacks
Get PDFAlmost pairwise independence (API) is a quantitative property of a class of functions that is desirable in many cryptographic applications. This property is satisfied by Learning with errors (LWE)-mappings and by special Substitution-Permutation Networks (SPN). API block ciphers are known to be resilient to differential and linear cryptanalysis attacks. Recently, security of protocols against neural network-based attacks became a major trend in cryptographic studies. Therefore, it is relevant to study the hardness of learning a target function from an API class of functions by gradient-based methods.We propose a theoretical analysis based on the study of the variance of the gradient of a general machine learning objective with respect to a random choice of target function from a class. We prove an upper bound and verify that, indeed, such a variance is extremely small for API classes of functions. This implies the resilience of actual LWE-based primitives against deep learning attacks, and to some extent, the security of SPNs. The hardness of learning reveals itself in the form of the barren plateau phenomenon during the training process, or in other words, in a low information content of the gradient about the target function. Yet, we emphasize that our bounds hold for the case of a regular parameterization of a neural network and the gradient may become informative if a class is mildly pairwise independent and a parameterization is non-regular. We demonstrate our theory in experiments on the learnability of LWE mappings. </p
Extensions of the Minimum Cost Homomorphism Problem
No full textAssume D is a finite set and R is a finite set of functions from D to the natural numbers. An instance of the minimum R-cost homomorphism problem (MinHom R ) is a set of variables V subject to specified constraints together with a positive weight c vr for each combination of v ∈ V and r ∈ R. The aim is to find a function f:V →D such that f satisfies all constraints and ∑ v ∈ V ∑ r ∈ R c vr r(f(v)) is maximized.This problem unifies well-known optimization problems such as the minimum cost homomorphism problem and the maximum solution problem, and this makes it a computationally interesting fragment of the valued CSP framework for optimization problems. We parameterize MinHom R by constraint languages, i.e. sets Γ of relations that are allowed in constraints. A constraint language is called conservative if every unary relation is a member of it; such constraint languages play an important role in understanding the structure of constraint problems. The dichotomy conjecture for MinHom R is the following statement: if Γ is a constraint language, then MinHom R is either polynomial-time solvable or NP-complete. For MinHom the dichotomy result has been recently obtained [Takhanov, STACS, 2010] and the goal of this paper is to expand this result to the case of MinHom R with conservative constraint language. For arbitrary R this problem is still open, but assuming certain restrictions on R we prove a dichotomy. As a consequence of this result we obtain a dichotomy for the conservative maximum solution problem</p
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
