Author name cluster

Eric J. Friedman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

AAAI Conference 2019 Conference Paper

Fair and Efficient Memory Sharing: Confronting Free Riders

Eric J. Friedman
Vasilis Gkatzelis
Christos-Alexandros Psomas
Scott Shenker

A cache memory unit needs to be shared among n strategic agents. Each agent has different preferences over the files to be brought into memory. The goal is to design a mechanism that elicits these preferences in a truthful manner and outputs a fair and efficient memory allocation. A trivially truthful and fair solution would isolate each agent to a 1/n fraction of the memory. However, this could be very inefficient if the agents have similar preferences and, thus, there is room for cooperation. On the other hand, if the agents are not isolated, unless the mechanism is carefully designed, they have incentives to misreport their preferences and free ride on the files that others bring into memory. In this paper we explore the power and limitations of truthful mechanisms in this setting. We demonstrate that mechanisms blocking agents from accessing parts of the memory can achieve improved efficiency guarantees, despite the inherent inefficiencies of blocking.

PDF Details

TCS Journal 2018 Journal Article

Duality and nonlinear graph Laplacians

Eric J. Friedman
Adam S. Landsberg

In this paper we show that a recent nearly linear time algorithm for solving a system of equations arising from a graph Laplacian can be extended to a large class of nonlinear systems of equations, based on a nonlinear generalization of the graph Laplacian. This result follows from a nonlinear generalization of the notable duality between graph Laplacians and electrical flows. Beyond providing a fast algorithm for a class of nonlinear sets of equations, our work highlights the robustness of spectral graph theory and suggests new directions for research in spectral graph theory. Specifically, we present an iterative algorithm for solving a class of nonlinear system of equations arising from a nonlinear generalization of the graph Laplacian in O ˜ ( k 2 m log ⁡ ( k n / ϵ ) ) iterations, where k is a measure of nonlinearity, n is the number of variables, m is the number of nonzero entries in the generalized graph Laplacian L, ϵ is the solution accuracy and O ˜ ( ) neglects (non-leading) logarithmic terms. This algorithm is a natural nonlinear extension of the one in Kelner et al. (2013), which solves a linear Laplacian system of equations in nearly linear time. Unlike the linear case, in the nonlinear case each iteration takes O ˜ ( n ) time so the total running time is O ˜ ( k 2 m n log ⁡ ( k n / ϵ ) ). For sparse graphs with m = O ( n ) and fixed k this nonlinear algorithm is O ˜ ( n 2 log ⁡ ( n / ϵ ) ) which is slightly faster than standard methods for solving linear equations, which require approximately O ( n 2. 38 ) time.

Details DOI

YNIMG Journal 2014 Journal Article

Stochastic geometric network models for groups of functional and structural connectomes

Eric J. Friedman
Adam S. Landsberg
Julia P. Owen
Yi-Ou Li
Pratik Mukherjee

Structural and functional connectomes are emerging as important instruments in the study of normal brain function and in the development of new biomarkers for a variety of brain disorders. In contrast to single-network studies that presently dominate the (non-connectome) network literature, connectome analyses typically examine groups of empirical networks and then compare these against standard (stochastic) network models. The current practice in connectome studies is to employ stochastic network models derived from social science and engineering contexts as the basis for the comparison. However, these are not necessarily best suited for the analysis of connectomes, which often contain groups of very closely related networks, such as occurs with a set of controls or a set of patients with a specific disorder. This paper studies important extensions of standard stochastic models that make them better adapted for analysis of connectomes, and develops new statistical fitting methodologies that account for inter-subject variations. The extensions explicitly incorporate geometric information about a network based on distances and inter/intra hemispherical asymmetries (to supplement ordinary degree-distribution information), and utilize a stochastic choice of network density levels (for fixed threshold networks) to better capture the variance in average connectivity among subjects. The new statistical tools introduced here allow one to compare groups of networks by matching both their average characteristics and the variations among them. A notable finding is that connectomes have high “smallworldness” beyond that arising from geometric and degree considerations alone.

Details DOI

YNIMG Journal 2013 Journal Article

The structural connectome of the human brain in agenesis of the corpus callosum

Julia P. Owen
Yi-Ou Li
Etay Ziv
Zoe Strominger
Jacquelyn Gold
Polina Bukhpun
Mari Wakahiro
Eric J. Friedman

Adopting a network perspective, the structural connectome reveals the large-scale white matter connectivity of the human brain, yielding insights into cerebral organization otherwise inaccessible to researchers and clinicians. Connectomics has great potential for elucidating abnormal connectivity in congenital brain malformations, especially axonal pathfinding disorders. Agenesis of the corpus callosum (AgCC) is one of the most common brain malformations and can also be considered a prototypical genetic disorder of axonal guidance in humans. In this exploratory study, the structural connectome of AgCC is mapped and compared to that of the normal human brain. Multiple levels of granularity of the AgCC connectome are investigated, including summary network metrics, modularity analysis, and network consistency measures, with comparison to the normal structural connectome after simulated removal of all callosal connections (“virtual callostomy”). These investigations reveal four major findings. First, global connectivity is abnormally reduced in AgCC, but local connectivity is increased. Second, the network topology of AgCC is more variable than that of the normal human connectome, contradicting the predictions of the virtual callostomy model. Third, modularity analysis reveals that many of the tracts that comprise the structural core of the cerebral cortex have relatively weak connectivity in AgCC, especially the cingulate bundles bilaterally. Finally, virtual lesions of the Probst bundles in the AgCC connectome demonstrate that there is consistency across subjects in many of the connections generated by these ectopic white matter tracts, and that they are a mixture of cortical and subcortical fibers. These results go beyond prior diffusion tractography studies to provide a systems-level perspective on anomalous connectivity in AgCC. Furthermore, this work offers a proof of principle for the utility of the connectome framework in neurodevelopmental disorders.

Details DOI

AAMAS Conference 2009 Conference Paper

Multiagent Learning in Large Anonymous Games

Ian A. Kash
Eric J. Friedman
Joseph Y. Halpern

In large systems, it is important for agents to learn to act effectively, but sophisticated multi-agent learning algorithms generally do not scale. An alternative approach is to ﬁnd restricted classes of games where simple, eﬃcient algorithms converge. It is shown that stage learning eﬃciently converges to Nash equilibria in large anonymous games if bestreply dynamics converge. Two features are identiﬁed that improve convergence. First, rather than making learning more diﬃcult, more agents are actually beneﬁcial in many settings. Second, providing agents with statistical information about the behavior of others can signiﬁcantly reduce the number of observations needed.

PDF