1,720,977 research outputs found
Recommended from our members
Unsatisfiability Bounds for Random Constraint Satisfaction Problems from an Energetic Interpolation Method
Get PDFThe interpolation method, originally developed in statistical physics, transforms distributions of random Constraint Satisfaction Problems (CSPs) to distributions of much simpler problems while bounding the change in a number of associated statistical quantities along the transformation path. By now, it is known that, in principle, the method can yield rigorous unsatisfiability results if one ``plugs in an appropriate functional distribution'' to the derived expressions. A drawback of the method is that identifying the appropriate distribution leads to major analytical challenges as the relevant distributions are, in fact, infinite dimensional objects. We develop a variant of the interpolation method for random CSPs on arbitrary sparse degree distributions which trades accuracy for tractability. In particular, our bounds only require the solution of a 1-dimensional optimization problem (which typically turns out to be very easy) and as such can be used to compute explicit rigorous unsatisfiability bounds. We use this new method to analyze the performance of a number of algorithms on random 3-CNF formulas with n variables and m=rn clauses. A long series of papers analyzing so-called ``myopic'' algorithms has provided a sequence of lower bounds for the satisfiability threshold, which is widely believed to be r~4.26. Indeed, for each myopic algorithm A it is known that there exists an algorithm-specific clause-density, r_A, such that if r2.78 and the same is true for generalized unit clause for all r>3.1. Our results imply exponential lower bounds for many other myopic algorithms for densities similarly close to the corresponding r_A
String Matching: Communication, Circuits, and Learning
No full textString matching is the problem of deciding whether a given n-bit string contains a given k-bit pattern. We study the complexity of this problem in three settings. - Communication complexity. For small k, we provide near-optimal upper and lower bounds on the communication complexity of string matching. For large k, our bounds leave open an exponential gap; we exhibit some evidence for the existence of a better protocol. - Circuit complexity. We present several upper and lower bounds on the size of circuits with threshold and DeMorgan gates solving the string matching problem. Similarly to the above, our bounds are near-optimal for small k. - Learning. We consider the problem of learning a hidden pattern of length at most k relative to the classifier that assigns 1 to every string that contains the pattern. We prove optimal bounds on the VC dimension and sample complexity of this problem.THL
Partition function estimation and phase transitions on random satisfiability problems
No full textThis thesis emphasizes on the estimation of partition functions and analyse phase transitions in random satisfiability problems with focuses on random 2-SAT, random k-XORSAT and random k-SAT models. Partition functions capture the exponential growth of solution spaces and establish a bridge among com-
binatorics, probability, and statistical physics. Studying their asymptotic and fluctuations helps us to understand the mechanisms behind sharp phase transitions and the solution space geometry in random constraint satisfaction problems.
Our first contribution establishes a central limit theorem for the number of solutions (also called ‘partition function’ in physics jargon) of random 2-SAT – first CLT of this type for any random CSPs. Thereby it provides a precise probabilistic characterization of fluctuations on the logarithm of the number of satisfying assignments of order √n with n the number of variables. In addition to this we effectively evaluated the formula for variance on the number of random 2-SAT solutions. The proof techniques rely on the Martingale central limit theorem along with the Gibbs uniqueness property and the local convergence to the Galton-Watson tree combined with a coupling argument called ‘Aizenmann-Sims-Starr scheme’.
The second part of the thesis investigates the performance of a statistical physics inspired message passing algorithm called ‘Belief Propagation Guided Decimation’ on the random k-XORSAT problem. Specifically, we derive an explicit threshold upto which the algorithm succeeds with a strictly positive probability between 0 and 1. Additionally, we study a thought experiment called ‘Decimation process’ for which we determine different phase transitions such as (non)-reconstruction and condensation phase transition and their connection to BPGD (in which regimes these two processes diverge or converge).
Finally, for random k-SAT, we revisited the Gibbs uniqueness threshold, improving the lower bound over the previous work by Montanari and Shah in 2007. More specifically, we count the number of actual satisfying assignments of random k-SAT which is given by the physics inspired ‘replica symmetry solution’ upto the Gibbs uniqueness threshold. Mathematically, we find an explicit expression on the logarithm of the number of solutions of random k-SAT in terms of the Bethe free entropy which is a function defined for a probability measure in the unit interval. Moreover, our lower bound in contrast to Montanari-Shah bound is significant particularly for small k.
In a nutshell, this thesis advances the rigorous understanding of random satisfiability problems by combining the algorithmic analysis, probabilistic combinatorics and statistical physics equipment. In light of both the structural properties of random formulas and the effectiveness of different message passing algorithms along with the universal principles governing fluctuations, correlation decay and mathematical foundation for the phenomena predicted by spin glass theory, point toward new directions for the future research on random satisfiability problems
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
Lower bounds for random 3-SAT via differential equations
No full textAbstractIt is widely believed that the probability of satisfiability for random k-SAT formulae exhibits a sharp threshold as a function of their clauses-to-variables ratio. For the most studied case, k=3, there have been a number of results during the last decade providing upper and lower bounds for the threshold's potential location. All lower bounds in this vein have been algorithmic, i.e., in each case a particular algorithm was shown to satisfy random instances of 3-SAT with probability 1−o(1) if the clauses-to-variables ratio is below a certain value. We show how differential equations can serve as a generic tool for analyzing such algorithms by rederiving most of the known lower bounds for random 3-SAT in a simple, uniform manner
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
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
No full textAbstractA classic result of Johnson and Lindenstrauss asserts that any set of n points in d-dimensional Euclidean space can be embedded into k-dimensional Euclidean space—where k is logarithmic in n and independent of d—so that all pairwise distances are maintained within an arbitrarily small factor. All known constructions of such embeddings involve projecting the n points onto a spherically random k-dimensional hyperplane through the origin. We give two constructions of such embeddings with the property that all elements of the projection matrix belong in {−1,0,+1}. Such constructions are particularly well suited for database environments, as the computation of the embedding reduces to evaluating a single aggregate over k random partitions of the attributes
Dispelling the Myths Behind First-author Citation Counts
Get PDFWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
