1,720,965 research outputs found
Strong ETH and Resolution via Games and the Multiplicity of Strategies
Get PDFWe consider a restriction of the Resolution proof system in which at most a fixed number of variables can be resolved more than once along each refutation path. This system lies between regular Resolution, in which no variable can be resolved more than once along any path, and general Resolution where there is no restriction on the number of such variables. We show that when the number of re-resolved variables is not too large, this proof system is consistent with the Strong Exponential Time Hypothesis (SETH). More precisely for large n and k we show that there are unsatisfiable k-CNF formulas which require Resolution refutations of size 2^{(1 - epsilon_k)n}, where n is the number of variables and epsilon_k=~O(k^{-1/5}), whenever in each refutation path we only allow at most ~O(k^{-1/5})n variables to be resolved multiple times. However, these re-resolved variables along different paths do not need to be the same. Prior to this work, the strongest proof system shown to be consistent with SETH was regular Resolution [Beck and Impagliazzo, STOC'13]. This work strengthens that result and gives a different and conceptually simpler game-theoretic proof for the case of regular Resolution
On the Structure and the Number of Prime Implicants of 2-CNFs
No full textLet m(n, k) be the maximum number of prime implicants that any k-CNF on n variables can have. We show that 3 n 3 ≤ m(n, 2) ≤ (1 + o(1))3n3
Super Strong ETH Is True for PPSZ with Small Resolution Width
Get PDFWe construct k-CNFs with m variables on which the strong version of PPSZ k-SAT algorithm, which uses resolution of width bounded by O(√{log log m}), has success probability at most 2^{-(1-(1 + ε)2/k)m} for every ε > 0. Previously such a bound was known only for the weak PPSZ algorithm which exhaustively searches through small subformulas of the CNF to see if any of them forces the value of a given variable, and for strong PPSZ the best known previous upper bound was 2^{-(1-O(log(k)/k))m} (Pudlák et al., ICALP 2017)
Linear Branching Programs and Directional Affine Extractors
Get PDFA natural model of read-once linear branching programs is a branching program
where queries are linear forms, and along each path, the queries
are linearly independent. We consider two restrictions of this model, which we
call weakly and strongly read-once, both generalizing standard read-once
branching programs and parity decision trees. Our main results are as follows.
- Average-case complexity. We define a pseudo-random class of functions which
we call directional affine extractors, and show that these functions are hard
on average for the strongly read-once model. We then present an explicit
construction of such function with good parameters. This strengthens the result
of Cohen and Shinkar (ITCS'16) who gave such average-case hardness for parity
decision trees. Directional affine extractors are stronger than the more
familiar class of affine extractors. Given the significance of these functions,
we expect that our new class of functions might be of independent interest.
- Proof complexity. We also consider the proof system
which is an extension of resolution with linear queries. A refutation of a CNF
in this proof system naturally defines a linear branching program solving the
corresponding search problem. Conversely, we show that a weakly read-once
linear BP solving the search problem can be converted to a
refutation with constant blow up
A Variant of the VC-dimension with Applications to Depth-3 Circuits
Get PDFWe introduce the following variant of the VC-dimension. Given and a positive integer , we define to be the
size of the largest subset such that the projection of on
every subset of of size is the -dimensional cube. We show that
determining the largest cardinality of a set with a given
dimension is equivalent to a Tur\'an-type problem related to the total number
of cliques in a -uniform hypergraph. This allows us to beat the
Sauer--Shelah lemma for this notion of dimension. We use this to obtain several
results on -circuits, i.e., depth- circuits with top gate OR and
bottom fan-in at most :
* Tight relationship between the number of satisfying assignments of a
-CNF and the dimension of the largest projection accepted by it, thus
improving Paturi, Saks, and Zane (Comput. Complex. '00).
* Improved -circuit lower bounds for affine dispersers for
sublinear dimension. Moreover, we pose a purely hypergraph-theoretic conjecture
under which we get further improvement.
* We make progress towards settling the complexity of the inner
product function and all degree- polynomials over in general.
The question of determining the complexity of IP was recently
posed by Golovnev, Kulikov, and Williams (ITCS'21)
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
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
- …
