1,720,976 research outputs found
Some results on symmetric signings
Full text linkIn this work, we investigate several natural computational problems related to identifying symmetric signings of symmetric matrices with specific spectral properties. We show NP-completeness for verifying whether an arbitrary matrix has a symmetric signing that is positive semi-definite, is singular, or has bounded eigenvalues. We exhibit a stark contrast between invertibility and the above-mentioned spectral properties by presenting a combinatorial characterization of matrices with invertible symmetric signings and an efficient algorithm using this characterization to verify whether a given matrix has an invertible symmetric signing. Finally, we give efficient algorithms to verify and find invertible and singular symmetric signing for matrices whose support graph is bipartite.Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-09-29 without embargo termsThe student, Charles Carlson, accepted the attached license on 2017-07-14 at 15:07.The student, Charles Carlson, submitted this Thesis for approval on 2017-07-14 at 15:14.This Thesis was approved for publication on 2017-07-17 at 08:50.DSpace SAF Submission Ingestion Package generated from Vireo submission #11474 on 2017-09-29 at 11:30:54Made available in DSpace on 2017-09-29T17:56:57Z (GMT). No. of bitstreams: 2
CARLSON-THESIS-2017.pdf: 261724 bytes, checksum: 73e742c3412743ba3088d657c33a68f5 (MD5)
LICENSE.txt: 4212 bytes, checksum: 49a5937d9204afd49a345dde3f2cd9ab (MD5)
Previous issue date: 2017-07-1
Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts
Full text linkIn this thesis we consider two questions motivated by the Unique Games Conjecture . The first question is concerned with the validity of the Unique Games
Conjecture when the constraint graph is restricted to the Boolean Hypercube. The Boolean Hypercube is a well studied graph family on which existing spectral methods fail to achieve a sub exponential time bound. We initiate the study of the behaviour of the standard semi-definite program on the Hypercube. We construct an almost optimal integrality gap instance on the Hypercube for the Goemans-Williamson semidefinite program (SDP) for Max-2-LIN(\Z_2). We
conjecture that augmenting the SDP with triangle inequalities makes
the SDP exact upto constants on the Hypercube. We further establish connections between the integrality gap of the SDP and Mutlicommodity flow-cut gaps which may lead to an understanding of the behaviour of the SDP on general families of graphs. As a quick corollary we establish that the SDP is exact for planar graphs.
The second question is concerned with spectrum of label extended graphs of Unique Games instances. Such graphs have been extensively studied under the name of Graph Lifts. The main motivation for studying lifts has been understanding Ramanujan expander graphs via two key questions: Is a ``typical'' lift of an
expander graph also an expander; and how can we (efficiently) construct Ramanujan expanders using lifts?
In our work we continue the study of Graph Lifts and show that, for random shift k-lifts, if all the nontrivial eigenvalues of a d-regular graph G are at most lambda in absolute value, then with high probability depending only on the number n of nodes of G (and not on k), the absolute value of every nontrivial eigenvalue of the lift is at most Oh(\lambda). This improves upon
factors of log(d) in the case when k=2. Other results on random lifts have focused on the case when k too infinity making their results asymptotically true with high probability in the degree of the lift k. To the best of our
knowledge, our result is the first upperbound on spectra of lifts for bounded k > 2. Our result in particular implies that a typical small lift of a Ramanujan graph
is almost Ramanujan, and we believe it will prove crucial in constructing large Ramanujan expanders of all degrees. We also establish a novel characterization
of the spectrum of shift lifts by the spectrum of certain k symmetric matrices, that generalize the signed adjacency matrix. We believe that this characterization is of independent interest.Item withdrawn by Mark Zulauf ([email protected]) on 2014-04-29T13:40:26Z
Item was in collections:
University of Illinois Theses & Dissertations (ID: 1)
No. of bitstreams: 4
FigureSDP1.png: 55389 bytes, checksum: 19b9b4deef107a3254aaa946a844df92 (MD5)
ms_thesis.bib: 17347 bytes, checksum: be982c6be0bd2231a70244008c0ec4b4 (MD5)
backup.tex: 172252 bytes, checksum: 3b26c2e426b7c2505988bff695e6b520 (MD5)
Agarwal_Naman.pdf: 648331 bytes, checksum: aa6dafa7fcba0f62d07a5f8c668a596a (MD5)Made available in DSpace on 2014-05-30T16:40:22Z (GMT). No. of bitstreams: 5
Naman_Agarwal.pdf: 648331 bytes, checksum: aa6dafa7fcba0f62d07a5f8c668a596a (MD5)
FigureSDP1.png: 55389 bytes, checksum: 19b9b4deef107a3254aaa946a844df92 (MD5)
ms_thesis.bib: 17347 bytes, checksum: be982c6be0bd2231a70244008c0ec4b4 (MD5)
backup.tex: 172252 bytes, checksum: 3b26c2e426b7c2505988bff695e6b520 (MD5)
license.txt: 4063 bytes, checksum: cc5f332296e53ed0dce757b06f7c884a (MD5
Lower Bounds for Max-Cut in H-Free Graphs via Semidefinite Programming
Full text linkISSN:0895-4801ISSN:1095-7146ISSN:1095-714
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
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
- …
