BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Cynthia A. Phillips

Cynthia A. Phillips appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
physics.soc-phComputational GeometryData Structures and AlgorithmsDiscrete Mathematicsphysics.data-anDistributed, Parallel, and Cluster ComputingNeural and Evolutionary Computingquant-phSocial and Information Networks

Catalog footprint

What is connected

8works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2020arXiv

Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication

Boolean circuits of McCulloch-Pitts threshold gates are a classic model of neural computation studied heavily in the late 20th century as a model of general computation. Recent advances in large-scale neural computing hardware has made their practical implementation a near-term possibility. We describe a theoretical approach for multiplying two $N$ by $N$ matrices that integrates threshold gate logic with conventional fast matrix multiplication algorithms, that perform $O(N^ω)$ arithmetic operations for a positive constant $ω< 3$. Our approach converts such a fast matrix multiplication algorithm into a constant-depth threshold circuit with approximately $O(N^ω)$ gates. Prior to our work, it was not known whether the $Θ(N^3)$-gate barrier for matrix multiplication was surmountable by constant-depth threshold circuits. Dense matrix multiplication is a core operation in convolutional neural network training. Performing this work on a neural architecture instead of off-loading it to a GPU may be an appealing option.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fractional Decomposition Tree Algorithm: A tool for studying the integrality gap of Integer Programs

We present a new algorithm, Fractional Decomposition Tree (FDT) for finding a feasible solution for an integer program (IP) where all variables are binary. FDT runs in polynomial time and is guaranteed to find a feasible integer solution provided the integrality gap is bounded. The algorithm gives a construction for Carr and Vempala's theorem that any feasible solution to the IP's linear-programming relaxation, when scaled by the instance integrality gap, dominates a convex combination of feasible solutions. FDT is also a tool for studying the integrality gap of IP formulations. We demonstrate that with experiments studying the integrality gap of two problems: optimally augmenting a tree to a 2-edge-connected graph and finding a minimum-cost 2-edge-connected multi-subgraph (2EC). We also give a simplified algorithm, Dom2IP, that more quickly determines if an instance has an unbounded integrality gap. We show that FDT's speed and approximation quality compare well to that of feasibility pump on moderate-sized instances of the vertex cover problem. For a particular set of hard-to-decompose fractional 2EC solutions, FDT always gave a better integer solution than the best previous approximation algorithm (Christofides).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Probing a Set of Trajectories to Maximize Captured Information

We study a trajectory analysis problem we call the Trajectory Capture Problem (TCP), in which, for a given input set ${\cal T}$ of trajectories in the plane, and an integer $k\geq 2$, we seek to compute a set of $k$ points (``portals'') to maximize the total weight of all subtrajectories of ${\cal T}$ between pairs of portals. This problem naturally arises in trajectory analysis and summarization. We show that the TCP is NP-hard (even in very special cases) and give some first approximation results. Our main focus is on attacking the TCP with practical algorithm-engineering approaches, including integer linear programming (to solve instances to provable optimality) and local search methods. We study the integrality gap arising from such approaches. We analyze our methods on different classes of data, including benchmark instances that we generate. Our goal is to understand the best performing heuristics, based on both solution time and solution quality. We demonstrate that we are able to compute provably optimal solutions for real-world instances.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Geometric Hitting Set for Segments of Few Orientations

We study several natural instances of the geometric hitting set problem for input consisting of sets of line segments (and rays, lines) having a small number of distinct slopes. These problems model path monitoring (e.g., on road networks) using the fewest sensors (the "hitting points"). We give approximation algorithms for cases including (i) lines of 3 slopes in the plane, (ii) vertical lines and horizontal segments, (iii) pairs of horizontal/vertical segments. We give hardness and hardness of approximation results for these problems. We prove that the hitting set problem for vertical lines and horizontal rays is polynomially solvable.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Why do simple algorithms for triangle enumeration work in the real world?

Listing all triangles is a fundamental graph operation. Triangles can have important interpretations in real-world graphs, especially social and other interaction networks. Despite the lack of provably efficient (linear, or slightly super-linear) worst-case algorithms for this problem, practitioners run simple, efficient heuristics to find all triangles in graphs with millions of vertices. How are these heuristics exploiting the structure of these special graphs to provide major speedups in running time? We study one of the most prevalent algorithms used by practitioners. A trivial algorithm enumerates all paths of length $2$, and checks if each such path is incident to a triangle. A good heuristic is to enumerate only those paths of length $2$ where the middle vertex has the lowest degree. It is easily implemented and is empirically known to give remarkable speedups over the trivial algorithm. We study the behavior of this algorithm over graphs with heavy-tailed degree distributions, a defining feature of real-world graphs. The erased configuration model (ECM) efficiently generates a graph with asymptotically (almost) any desired degree sequence. We show that the expected running time of this algorithm over the distribution of graphs created by the ECM is controlled by the $\ell_{4/3}$-norm of the degree sequence. Norms of the degree sequence are a measure of the heaviness of the tail, and it is precisely this feature that allows non-trivial speedups of simple triangle enumeration algorithms. As a corollary of our main theorem, we prove expected linear-time performance for degree sequences following a power law with exponent $α\geq 7/3$, and non-trivial speedup whenever $α\in (2,3)$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Implications of Electronics Constraints for Solid-State Quantum Error Correction and Quantum Circuit Failure Probability

In this paper we present the impact of classical electronics constraints on a solid-state quantum dot logical qubit architecture. Constraints due to routing density, bandwidth allocation, signal timing, and thermally aware placement of classical supporting electronics significantly affect the quantum error correction circuit's error rate. We analyze one level of a quantum error correction circuit using nine data qubits in a Bacon-Shor code configured as a quantum memory. A hypothetical silicon double quantum dot quantum bit (qubit) is used as the fundamental element. A pessimistic estimate of the error probability of the quantum circuit is calculated using the total number of gates and idle time using a provably optimal schedule for the circuit operations obtained with an integer program methodology. The micro-architecture analysis provides insight about the different ways the electronics impact the circuit performance (e.g., extra idle time in the schedule), which can significantly limit the ultimate performance of any quantum circuit and therefore is a critical foundation for any future larger scale architecture analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Tolerating the Community Detection Resolution Limit with Edge Weighting

Communities of vertices within a giant network such as the World-Wide Web are likely to be vastly smaller than the network itself. However, Fortunato and Barthélemy have proved that modularity maximization algorithms for community detection may fail to resolve communities with fewer than $\sqrt{L/2}$ edges, where $L$ is the number of edges in the entire network. This resolution limit leads modularity maximization algorithms to have notoriously poor accuracy on many real networks. Fortunato and Barthélemy's argument can be extended to networks with weighted edges as well, and we derive this corollary argument. We conclude that weighted modularity algorithms may fail to resolve communities with fewer than $\sqrt{W ε/2}$ total edge weight, where $W$ is the total edge weight in the network and $ε$ is the maximum weight of an inter-community edge. If $ε$ is small, then small communities can be resolved. Given a weighted or unweighted network, we describe how to derive new edge weights in order to achieve a low $ε$, we modify the ``CNM'' community detection algorithm to maximize weighted modularity, and show that the resulting algorithm has greatly improved accuracy. In experiments with an emerging community standard benchmark, we find that our simple CNM variant is competitive with the most accurate community detection methods yet proposed.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Community Detection via Facility Location

In this paper we apply theoretical and practical results from facility location theory to the problem of community detection in networks. The result is an algorithm that computes bounds on a minimization variant of local modularity. We also define the concept of an edge support and a new measure of the goodness of community structures with respect to this concept. We present preliminary results and note that our methods are massively parallelizable.

0 citations0 reviewsNo code linkedOpen access