1,724,760 research outputs found
Using Borax to Create a Neutron Shield for an Nal Detector
No full textFaculty advisor: Prof. Priscilla CushmanThis research was supported by the Office of Undergraduate Research, URS ProgramAgarwal, Tanmay. (2018). Using Borax to Create a Neutron Shield for an Nal Detector. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/211397
Non-Uniform k-Center and Greedy Clustering
Get PDFIn the Non-Uniform k-Center (NUkC) problem, a generalization of the famous k-center clustering problem, we want to cover the given set of points in a metric space by finding a placement of balls with specified radii. In t-NUkC, we assume that the number of distinct radii is equal to t, and we are allowed to use k_i balls of radius r_i, for 1 ≤ i ≤ t. This problem was introduced by Chakrabarty et al. [ACM Trans. Alg. 16(4):46:1-46:19], who showed that a constant approximation for t-NUkC is not possible if t is unbounded, assuming ≠ NP. On the other hand, they gave a bicriteria approximation that violates the number of allowed balls as well as the given radii by a constant factor. They also conjectured that a constant approximation for t-NUkC should be possible if t is a fixed constant. Since then, there has been steady progress towards resolving this conjecture - currently, a constant approximation for 3-NUkC is known via the results of Chakrabarty and Negahbani [IPCO 2021], and Jia et al. [SOSA 2022]. We push the horizon by giving an O(1)-approximation for the Non-Uniform k-Center for 4 distinct types of radii. Our result is obtained via a novel combination of tools and techniques from the k-center literature, which also demonstrates that the different generalizations of k-center involving non-uniform radii, and multiple coverage constraints (i.e., colorful k-center), are closely interlinked with each other. We hope that our ideas will contribute towards a deeper understanding of the t-NUkC problem, eventually bringing us closer to the resolution of the CGK conjecture
Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
Get PDFHybrid k-Clustering is a model of clustering that generalizes two of the most widely studied clustering objectives: k-Center and k-Median. In this model, given a set of n points P, the goal is to find k centers such that the sum of the r-distances of each point to its nearest center is minimized. The r-distance between two points p and q is defined as max{dist(p, q)-r, 0} - this represents the distance of p to the boundary of the r-radius ball around q if p is outside the ball, and 0 otherwise. This problem was recently introduced by Fomin et al. [APPROX 2024], who designed a (1+ε, 1+ε)-bicrtieria approximation that runs in time 2^{(kd/ε)^{O(1)}} ⋅ n^{O(1)} for inputs in ℝ^d; such a bicriteria solution uses balls of radius (1+ε)r instead of r, and has a cost at most 1+ε times the cost of an optimal solution using balls of radius r.
In this paper we significantly improve upon this result by designing an approximation algorithm with the same bicriteria guarantee, but with running time that is FPT only in k and ε - crucially, removing the exponential dependence on the dimension d. This resolves an open question posed in their paper. Our results extend further in several directions. First, our approximation scheme works in a broader class of metric spaces, including doubling spaces, minor-free, and bounded treewidth metrics. Secondly, our techniques yield a similar bicriteria FPT-approximation schemes for other variants of Hybrid k-Clustering, e.g., when the objective features the sum of z-th power of the r-distances. Finally, we also design a coreset for Hybrid k-Clustering in doubling spaces, answering another open question from the work of Fomin et al
Pulsar Kick: Status and Perspective
No full textThe high speeds seen in rapidly rotating pulsars after supernova explosions present a longstanding puzzle in astrophysics. Numerous theories have been suggested over the years to explain this sudden “kick” imparted to the neutron star, yet each comes with its own set of challenges and limitations. Key explanations for pulsar kicks include hydrodynamic instabilities in supernovae, anisotropic neutrino emission, asymmetries in the magnetic field, binary system disruption, and physics beyond the Standard Model. Unraveling the origins of pulsar kicks not only enhances our understanding of supernova mechanisms but also opens up possibilities for exploring new physics. In this brief review, we will introduce pulsar kicks, examine the leading hypotheses, and explore future directions for this intriguing phenomenon
Topics in analytic number theory
Get PDFThis thesis, consisting of two chapters, proves several new theorems concerning L-functions and the distribution of primes.
In the first chapter, we establish the first explicit form of the Vinogradov–Korobov zero-free region for Dirichlet L-functions.
In the second chapter, we generalize recent work on large gaps between primes to imaginary quadratic fields. Suppose K is an imaginary quadratic field, and let N_K denote the field norm on O_K. For x₀ in O_K and r > 0, let (x₀, r) = { x in O_K : |N_K(x − x₀)| 0 : there exists x₀ in O_K such that |N_K(x₀)| ≤ X and B(x₀, r) contains no primes }. We show that G_K(X) is at least c_K (log X) (log₂ X · log₄ X) / log₃ X for some constant c_K > 0 depending only on K.Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2026-02-19 without embargo termsThe student, Tanmay Khale, accepted the attached license on 2025-12-03 at 10:19.The student, Tanmay Khale, submitted this Dissertation for approval on 2025-12-03 at 12:54.This Dissertation was approved for publication on 2025-12-05 at 10:40.DSpace SAF Submission Ingestion Package generated from Vireo submission #23040 on 2026-02-19 at 18:26:3
Capacitated Sum-Of-Radii Clustering: An FPT Approximation
Get PDFIn sum of radii clustering, the input consists of a finite set of points in a metric space. The problem asks to place a set of k balls centered at a subset of the points such that every point is covered by some ball, and the objective is to minimize the sum of radii of these balls. In the capacitated version of the problem, we want to assign each point to a ball containing it, such that no ball is assigned more than U points, where U denotes the capacity of the points. While constant approximations are known for the uncapacitated version of the problem, there is no work on the capacitated version. We make progress on this problem by obtaining a constant approximation using a Fixed Parameter Tractable (FPT) algorithm. In particular, the running time of the algorithm is of the form 2^O(k²) ⋅ n^O(1). As a warm-up for this result, we also give a constant approximation for the uncapacitated sum of radii clustering problem with matroid constraints, thus obtaining the first FPT approximation for this problem
On Partial Covering For Geometric Set Systems
Get PDFWe study a generalization of the Set Cover problem called the Partial Set Cover in the context of geometric set systems. The input to this problem is a set system (X, R), where X is a set of elements and R is a collection of subsets of X, and an integer k <= |X|. Each set in R has a non-negative weight associated with it. The goal is to cover at least k elements of X by using a minimum-weight collection of sets from R. The main result of this article is an LP rounding scheme which shows that the integrality gap of the Partial Set Cover LP is at most a constant times that of the Set Cover LP for a certain projection of the set system (X, R). As a corollary of this result, we get improved approximation guarantees for the Partial Set Cover problem for a large class of geometric set systems
Breaking serialization in lock-free multicore synchronization
Get PDFIn multicores, performance-critical synchronization is increasingly performed in a lock-free manner using atomic instructions such as CAS or LL/SC. However, when many processors synchronize on the same variable, performance can still degrade significantly. Contending writes get serialized, creating a non-scalable condition. Past proposals that build hardware queues of synchronizing processors do not fundamentally solve this problem. At best, they help to efficiently serialize the contending writes.
We propose a novel architecture that breaks the serialization of hardware queues and enables the queued processors to perform lock-free synchronization in parallel. The architecture, called Caspar, is able to (1) execute the CASes in the queued-up processors in parallel through eager forwarding of expected values, and (2) validate the CASes in parallel and dequeue groups of processors at a time. The result is highly scalable synchronization. We evaluate Caspar with simulations of a 64-core chip. Compared to existing proposals with hardware queues, Caspar improves the throughput of kernels by 32% on average and reduces the execution time of the sections considered in lock-free versions of applications by 47% on average. This makes these sections 2.5x faster than in the original applications.Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-11-09 without embargo termsThe student, Tanmay Gangwani, accepted the attached license on 2016-07-18 at 14:05.The student, Tanmay Gangwani, submitted this Thesis for approval on 2016-07-18 at 14:25.This Thesis was approved for publication on 2016-07-18 at 15:13.DSpace SAF Submission Ingestion Package generated from Vireo submission #9975 on 2016-11-09 at 10:25:18Made available in DSpace on 2016-11-10T17:55:16Z (GMT). No. of bitstreams: 2
GANGWANI-THESIS-2016.pdf: 645222 bytes, checksum: 8d88d90984ee511ebc9d7720dd30c2fc (MD5)
LICENSE.txt: 4212 bytes, checksum: 3fad0c180e8fc58bf9d82976ab8aac56 (MD5)
Previous issue date: 2016-07-1
Microfluidic particle tracking technique towards white blood cell subtype counting and serum protein quantification
Get PDFMicrofluidic technologies have gained wide acceptance in the past decade as diagnostics tools in clinical setting world-wide. This is primarily due to the fact that microfluidic technologies enable rapid, quantitative assays from small amount of physiological sample in an easy-to-use, portable platform. In this work, we will describe a microfluidic technique that can be built upon to count white blood cell subtypes or serum protein from a drop of blood. Traditionally, researchers have counted white blood cell subtypes by capturing them. However, an elegant and more accurate way to do the same is by exploiting the transitory interactions between the antigen on the surface of the cell and a cognate antibody. Cells expressing the antigen of interest will take longer to traverse a microchannel which has been coated with a cognate antibody compared to the cells which don't express that antigen. To our knowledge, no microfluidic assay exists which can rapidly count cells using this principle. Towards this end, we have developed a repeatable experimental technique to control the transit time and the order of particles in a microchannel. To least affect the uniformity of transit time, we have also optimized the geometry of pillars in the microchannel on which antibodies are functionalized.Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2018-08-01The student, Tanmay Ghonge, accepted the attached license on 2016-07-20 at 20:20.The student, Tanmay Ghonge, submitted this Thesis for approval on 2016-07-20 at 20:22.This Thesis was approved for publication on 2016-07-22 at 15:07.DSpace SAF Submission Ingestion Package generated from Vireo submission #10043 on 2016-11-10 at 12:21:02Made available in DSpace on 2016-11-10T18:27:09Z (GMT). No. of bitstreams: 2
GHONGE-THESIS-2016.pdf: 2007682 bytes, checksum: 2e84b6da47c9ce69ad66e0b45f92a31f (MD5)
LICENSE.txt: 4210 bytes, checksum: 80de1a9885d9f902620d9b6cd84a0e36 (MD5)
Previous issue date: 2016-07-22Embargo set by: Seth Robbins for item 95295
Lift date: 2018-11-10T18:28:02Z
Reason: Author requested closed access (OA after 2yrs) in Vireo ETD systemLimited Restriction Lifted for Item 95295 on 2018-11-11T10:15:11Z
- …
