1,720,975 research outputs found
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe 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
Full text link“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
Full text linkWe 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
Efficient Construction of Rigid Matrices Using an NP Oracle
No full textIf H is a matrix over a field F, then the rank-r rigidity of H, denoted R_{H}(r), is the minimum Hamming distance from H to a matrix of rank at most r over F. Giving explicit constructions of rigid matrices for a variety of parameter regimes is a central open challenge in complexity theory. In this work, building on Williams' seminal connection between circuit-analysis algorithms and lower bounds [Williams, J. ACM 2014], we give a construction of rigid matrices in P^NP. Letting q = p^r be a prime power, we show:
- There is an absolute constant delta>0 such that, for all constants eps>0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs a matrix H_N in {0,1}^{N times N} with rigidity R_{H_N}(2^{(log N)^{1/4 - eps}}) >= delta N^2 over F_q.
Using known connections between matrix rigidity and a number of different areas of complexity theory, we derive several consequences of our constructions, including:
- There is a function f in TIME[2^{(log n)^{omega(1)}}]^NP such that f notin PH^cc. Previously, it was even open whether E^NP subset PH^cc.
- For all eps>0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs an N times N matrix H_N in {0,1}^{N times N} whose linear transformation requires depth-2 F_q-linear circuits of size Omega(N 2^{(log N)^{1/4 - eps}}). The previous best lower bound for an explicit family of N \times N matrices was only Omega(N log^2 N / log log N), for super-concentrator graphs.
Joint work with Lijie Chen to appear in FOCS 2019.Non UBCUnreviewedAuthor affiliation: MITGraduat
Limits on the Universal Method for Matrix Multiplication
Full text linkIn this work, we prove limitations on the known methods for designing matrix multiplication algorithms. Alman and Vassilevska Williams [Alman and Williams, 2018] recently defined the Universal Method, which substantially generalizes all the known approaches including Strassen’s Laser Method [V. Strassen, 1987] and Cohn and Umans' Group Theoretic Method [Cohn and Umans, 2003]. We prove concrete lower bounds on the algorithms one can design by applying the Universal Method to many different tensors. Our proofs use new tools for upper bounding the asymptotic slice rank of a wide range of tensors. Our main result is that the Universal method applied to any Coppersmith-Winograd tensor CW_q cannot yield a bound on omega, the exponent of matrix multiplication, better than 2.16805. By comparison, it was previously only known that the weaker "Galactic Method" applied to CW_q could not achieve an exponent of 2.
We also study the Laser Method (which is, in principle, a highly special case of the Universal Method) and prove that it is "complete" for matrix multiplication algorithms: when it applies to a tensor T, it achieves omega = 2 if and only if it is possible for the Universal method applied to T to achieve omega = 2. Hence, the Laser Method, which was originally used as an algorithmic tool, can also be seen as a lower bounding tool. For example, in their landmark paper, Coppersmith and Winograd [Coppersmith and Winograd, 1990] achieved a bound of omega <= 2.376, by applying the Laser Method to CW_q. By our result, the fact that they did not achieve omega=2 implies a lower bound on the Universal Method applied to CW_q. Indeed, if it were possible for the Universal Method applied to CW_q to achieve omega=2, then Coppersmith and Winograd’s application of the Laser Method would have achieved omega=2
Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables
Full text linkWe use lookup tables to design faster algorithms for important algebraic
problems over finite fields. These faster algorithms, which only use arithmetic
operations and lookup table operations, may help to explain the difficulty of
determining the complexities of these important problems. Our results over a
constant-sized finite field are as follows.
The Walsh-Hadamard transform of a vector of length can be computed using
bit operations. This generalizes to any transform
defined as a Kronecker power of a fixed matrix. By comparison, the Fast
Walsh-Hadamard transform (similar to the Fast Fourier transform) uses arithmetic operations, which is believed to be optimal up to constant
factors.
Any algebraic algorithm for multiplying two matrices using
operations can be converted into an algorithm using bit operations. For example, Strassen's algorithm can
be converted into an algorithm using bit
operations. It remains an open problem with practical implications to determine
the smallest constant such that Strassen's algorithm can be implemented to
use arithmetic operations; using a lookup
table allows one to save a super-constant factor in bit operations.Comment: 10 pages, to appear in the 6th Symposium on Simplicity in Algorithms
(SOSA 2023
An Illuminating Algorithm for the Light Bulb Problem
Full text linkThe Light Bulb Problem is one of the most basic problems in data analysis. One is given as input n vectors in {-1,1}^d, which are all independently and uniformly random, except for a planted pair of vectors with inner product at least rho * d for some constant rho > 0. The task is to find the planted pair. The most straightforward algorithm leads to a runtime of Omega(n^2). Algorithms based on techniques like Locality-Sensitive Hashing achieve runtimes of n^{2 - O(rho)}; as rho gets small, these approach quadratic.
Building on prior work, we give a new algorithm for this problem which runs in time O(n^{1.582} + nd), regardless of how small rho is. This matches the best known runtime due to Karppa et al. Our algorithm combines techniques from previous work on the Light Bulb Problem with the so-called `polynomial method in algorithm design,' and has a simpler analysis than previous work. Our algorithm is also easily derandomized, leading to a deterministic algorithm for the Light Bulb Problem with the same runtime of O(n^{1.582} + nd), improving previous results
Linear algebraic techniques in algorithms and complexity
No full textThis electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019Cataloged from student-submitted PDF version of thesis.Includes bibliographical references (pages 209-224).We develop linear algebraic techniques in algorithms and complexity, and apply them to a variety of different problems. We focus in particular on matrix multiplication algorithms, which have surprisingly fast running times and can hence be used to design fast algorithms in many settings, and matrix rank methods, which can be used to design algorithms or prove lower bounds by analyzing the ranks of matrices corresponding to computational tasks. First, we study the design of matrix multiplication algorithms. We define a new general method, called the Universal Method, which subsumes all the known approaches to designing these algorithms. We then design a suite of techniques for proving lower bounds on the running times which can be achieved by algorithms using many tensors and the Universal Method.Our main limitation result is that a large class of tensors generalizing the Coppersmith-Winograd tensors (the family of tensors used in all record-holding algorithms for the past 30+ years) cannot achieve a better running time for multiplying n by n matrices than O(n²[superscript .]¹⁶⁸). Second, we design faster algorithms for batch nearest neighbor search, the problem where one is given sets of data points and query points, and one wants to find the most similar data point to each query point, according to some distance measure. We give the first subquadratic time algorithm for the exact problem in high dimensions, and the fastest known algorithm for the approximate problem, for various distance measures including Hamming and Euclidean distance. Our algorithms make use of new probabilistic polynomial constructions to reduce the problem to the multiplication of low-rank matrices.Third, we study rigid matrices, which cannot be written as the sum of a low rank matrix and a sparse matrix. Finding explicit rigid matrices is an important open problem in complexity theory with applications in many different areas. We show that the Walsh-Hadamard transform, previously a leading candidate rigid matrix, is in fact not rigid. We also give the first nontrivial construction of rigid matrices in a certain parameter regime with applications to communication complexity, using an efficient algorithm with access to an NP oracle.by Josh Alman.Ph. D.Ph.D. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Scienc
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe 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
- …
