Joel Friedman
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Joel Friedman has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- David Kohler6 shared publications
- Doron Puder
School of Mathematical Sciences Tel Aviv University Tel Aviv Israel
2 shared publications - Nicolas Folinsbee
University of British Columbia
2 shared publications - Alan K. Mackworth
Department of Computer Science, University of British Columbia, Vancouver, Canada
1 shared publication - Alice Izsak1 shared publication
Amir Tootooni
Univ British Columbia, Dept Comp Sci, 2366 Main Mall, Vancouver, BC V6T 1Z4, Canada
1 shared publication
Latest Publications
- 1 September 2023
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 256 (1) , 269-282
A note on the trace method for random regular graphs
- 1 September 2023
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 256 (1) , 269-282
A note on the trace method for random regular graphs
- Open Access
Coordination and Discoordination in Linear Algebra, Linear Information Theory, and Coded Caching
In the first part of this paper we develop some theorems in linear algebra applicable to information theory when all random variables involved are linear functions of the individual bits of a source of independent bits. We say that a collection of subspaces of a vector space are "coordinated" if the vector space has a basis such that each subspace is spanned by its intersection with the basis. We measure the failure of a collection of subspaces to be coordinated by an invariant that we call the "discoordination" of the family. We develop some foundational results regarding discoordination. In particular, these results give a number of new formulas involving three subspaces of a vector space. We then apply a number of our results, along with a method of Tian to obtain some new lower bounds in a special case of the basic coded caching problem. In terms of the usual notation for these problems, we show that for $N=3$ documents and $K=3$ caches, we have $6M+5R\ge 11$ for a scheme that achieves the memory-rate pair $(M,R)$, assuming the scheme is linear. We also give a new caching scheme for $N=K=3$ that achieves the pair $(M,R) = (1/2,5/3)$.Open AccessCoordination and Discoordination in Linear Algebra, Linear Information Theory, and Coded Caching
In the first part of this paper we develop some theorems in linear algebra applicable to information theory when all random variables involved are linear functions of the individual bits of a source of independent bits. We say that a collection of subspaces of a vector space are "coordinated" if the vector space has a basis such that each subspace is spanned by its intersection with the basis. We measure the failure of a collection of subspaces to be coordinated by an invariant that we call the "discoordination" of the family. We develop some foundational results regarding discoordination. In particular, these results give a number of new formulas involving three subspaces of a vector space. We then apply a number of our results, along with a method of Tian to obtain some new lower bounds in a special case of the basic coded caching problem. In terms of the usual notation for these problems, we show that for $N=3$ documents and $K=3$ caches, we have $6M+5R\ge 11$ for a scheme that achieves the memory-rate pair $(M,R)$, assuming the scheme is linear. We also give a new caching scheme for $N=K=3$ that achieves the pair $(M,R) = (1/2,5/3)$. - 19 May 2023
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 673, 304-420
Coordination and discoordination in linear algebra, linear information theory, and coded caching
- 19 May 2023
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 673, 304-420
Coordination and discoordination in linear algebra, linear information theory, and coded caching
- Open Access
- 7 April 2023
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 30 (2) , P2.33
Generalized Riemann Functions, Their Weights, and the Complete Graph
By a Riemann function we mean a function $f:\mathbb{Z}^n\to\mathbb{Z}$ such that $f(\mathbf{d})$ is equals $0$ for $d_1+\cdots+d_n$ sufficiently small, and equals $d_1+\cdots+d_n+C$ for a constant, $C$, for $d_1+\cdots+d_n$ sufficiently large. By adding $1$ to the Baker-Norine rank function of a graph, one gets an equivalent Riemann function, and similarly for related rank functions. To each Riemann function we associate a related function $W: \mathbb{Z}^n\to \mathbb{Z}$ via Möbius inversion that we call the weight of the Riemann function. We give evidence that the weight seems to organize the structure of a Riemann function in a simpler way: first, a Riemann function $f$ satisfies a Riemann-Roch formula iff its weight satisfies a simpler symmetry condition. Second, we will calculate the weight of the Baker-Norine rank for certain graphs and show that the weight function is quite simple to describe; we do this for graphs on two vertices and for complete graphs. For complete graphs, we build on the work of Cori and Le Borgne who gave a linear time method to compute the Baker-Norine rank of the complete graph. The associated weight function has a simple formula and is extremely sparse (i.e., mostly zero). Our computation of the weight function leads to a new linear time algorithm to compute the Baker-Norine rank, via a new formula likely related to one of Cori and Le Borgne, but seemingly simpler for general $\mathbf{d}\in \mathbb{Z}^n$, namely$$r_{{\rm BN},K_n}(\mathbf{d}) =-1+\biggl| \biggl\{ i=0,\ldots,\deg(\mathbf{d}) \ \Bigm|\ \sum_{j=1}^{n-2} \bigl( (d_j-d_{n-1}+i) \bmod n \bigr) \le \deg(\mathbf{d})-i\biggr\} \biggr|.$$However, the formula of Cori and Le Borgne, which requires $\mathbf{d}\in \mathbb{Z}^n$ to be a sorted parking function, is easier to evaluate for such $\mathbf{d}$. Our study of weight functions leads to a natural generalization of Riemann functions, with many of the same properties exhibited by Riemann functions.- 7 April 2023
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 30 (2) , P2.33
Open AccessGeneralized Riemann Functions, Their Weights, and the Complete Graph
By a Riemann function we mean a function $f:\mathbb{Z}^n\to\mathbb{Z}$ such that $f(\mathbf{d})$ is equals $0$ for $d_1+\cdots+d_n$ sufficiently small, and equals $d_1+\cdots+d_n+C$ for a constant, $C$, for $d_1+\cdots+d_n$ sufficiently large. By adding $1$ to the Baker-Norine rank function of a graph, one gets an equivalent Riemann function, and similarly for related rank functions. To each Riemann function we associate a related function $W: \mathbb{Z}^n\to \mathbb{Z}$ via Möbius inversion that we call the weight of the Riemann function. We give evidence that the weight seems to organize the structure of a Riemann function in a simpler way: first, a Riemann function $f$ satisfies a Riemann-Roch formula iff its weight satisfies a simpler symmetry condition. Second, we will calculate the weight of the Baker-Norine rank for certain graphs and show that the weight function is quite simple to describe; we do this for graphs on two vertices and for complete graphs. For complete graphs, we build on the work of Cori and Le Borgne who gave a linear time method to compute the Baker-Norine rank of the complete graph. The associated weight function has a simple formula and is extremely sparse (i.e., mostly zero). Our computation of the weight function leads to a new linear time algorithm to compute the Baker-Norine rank, via a new formula likely related to one of Cori and Le Borgne, but seemingly simpler for general $\mathbf{d}\in \mathbb{Z}^n$, namely$$r_{{\rm BN},K_n}(\mathbf{d}) =-1+\biggl| \biggl\{ i=0,\ldots,\deg(\mathbf{d}) \ \Bigm|\ \sum_{j=1}^{n-2} \bigl( (d_j-d_{n-1}+i) \bmod n \bigr) \le \deg(\mathbf{d})-i\biggr\} \biggr|.$$However, the formula of Cori and Le Borgne, which requires $\mathbf{d}\in \mathbb{Z}^n$ to be a sorted parking function, is easier to evaluate for such $\mathbf{d}$. Our study of weight functions leads to a natural generalization of Riemann functions, with many of the same properties exhibited by Riemann functions. - Open Access
Sheaves and Duality in the Two-Vertex Graph Riemann-Roch Theorem
For each graph on two vertices, and each divisor on the graph in the sense of Baker-Norine, we describe a sheaf of vector spaces on a finite category whose zeroth Betti number is the Baker-Norine "Graph Riemann-Roch" rank of the divisor plus one. We prove duality theorems that generalize the Baker-Norine "Graph Riemann-Roch" Theorem.
Open AccessSheaves and Duality in the Two-Vertex Graph Riemann-Roch Theorem
For each graph on two vertices, and each divisor on the graph in the sense of Baker-Norine, we describe a sheaf of vector spaces on a finite category whose zeroth Betti number is the Baker-Norine "Graph Riemann-Roch" rank of the divisor plus one. We prove duality theorems that generalize the Baker-Norine "Graph Riemann-Roch" Theorem.
- Open Access
A Note on the Trace Method for Random Regular Graphs
The main goal of this note is to illustrate the advantage of analyzing the non-backtracking spectrum of a regular graph rather than the ordinary spectrum. We show that by switching to non-backtracking spectrum, the method of proof used in [Puder 2015, arXiv::1212.5216] yields a bound of $2\sqrt{d-1}+\frac{2}{\sqrt{d-1}}$ instead of the original $2\sqrt{d-1}+1$ on the second largest eigenvalue of a random $d$-regular graph.Open AccessA Note on the Trace Method for Random Regular Graphs
The main goal of this note is to illustrate the advantage of analyzing the non-backtracking spectrum of a regular graph rather than the ordinary spectrum. We show that by switching to non-backtracking spectrum, the method of proof used in [Puder 2015, arXiv::1212.5216] yields a bound of $2\sqrt{d-1}+\frac{2}{\sqrt{d-1}}$ instead of the original $2\sqrt{d-1}+1$ on the second largest eigenvalue of a random $d$-regular graph. - Open Access
On the Relativized Alon Second Eigenvalue Conjecture V: Proof of the Relativized Alon Conjecture for Regular Base Graphs
This is the fifth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this article we use the results of Articles~III and IV in this series to prove that if the base graph is regular, then as the degree, $n$, of the covering map tends to infinity, some new adjacency eigenvalue has absolute value outside the Alon bound with probability bounded by $O(1/n)$. In addition, we give upper and lower bounds on this probability that are tight to within a multiplicative constant times the degree of the covering map. These bounds depend on two positive integers, the \emph{algebraic power} (which can also be $+\infty$) and the \emph{tangle power} of the model of random covering map. We conjecture that the algebraic power of the models we study is always $+\infty$, and in Article~VI we prove this when the base graph is regular and \emph{Ramanujan}. When the algebraic power of the model is $+\infty$, then the results in this article imply stronger results, such as (1) the upper and lower bounds mentioned above are matching to within a multiplicative constant, and (2) with probability smaller than any negative power of the degree, the some new eigenvalue fails to be within the Alon bound only if the covering map contains one of finitely many "tangles" as a subgraph (and this event has low probability).Open AccessOn the Relativized Alon Second Eigenvalue Conjecture V: Proof of the Relativized Alon Conjecture for Regular Base Graphs
This is the fifth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this article we use the results of Articles~III and IV in this series to prove that if the base graph is regular, then as the degree, $n$, of the covering map tends to infinity, some new adjacency eigenvalue has absolute value outside the Alon bound with probability bounded by $O(1/n)$. In addition, we give upper and lower bounds on this probability that are tight to within a multiplicative constant times the degree of the covering map. These bounds depend on two positive integers, the \emph{algebraic power} (which can also be $+\infty$) and the \emph{tangle power} of the model of random covering map. We conjecture that the algebraic power of the models we study is always $+\infty$, and in Article~VI we prove this when the base graph is regular and \emph{Ramanujan}. When the algebraic power of the model is $+\infty$, then the results in this article imply stronger results, such as (1) the upper and lower bounds mentioned above are matching to within a multiplicative constant, and (2) with probability smaller than any negative power of the degree, the some new eigenvalue fails to be within the Alon bound only if the covering map contains one of finitely many "tangles" as a subgraph (and this event has low probability). - Open Access
On the Relativized Alon Second Eigenvalue Conjecture VI: Sharp Bounds for Ramanujan Base Graphs
This is the sixth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this article we show that if the fixed graph is regular Ramanujan, then the {\em algebraic power} of the model of random covering graphs is $+\infty$. This implies a number of interesting results, such as (1) one obtains the upper and lower bounds---matching to within a multiplicative constant---for the probability that a random covering map has some new adjacency eigenvalue outside the Alon bound, and (2) with probability smaller than any negative power of the degree of the covering map, some new eigenvalue fails to be within the Alon bound without the covering map containing one of finitely many "tangles" as a subgraph (and this tangle containment event has low probability).Open AccessOn the Relativized Alon Second Eigenvalue Conjecture VI: Sharp Bounds for Ramanujan Base Graphs
This is the sixth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this article we show that if the fixed graph is regular Ramanujan, then the {\em algebraic power} of the model of random covering graphs is $+\infty$. This implies a number of interesting results, such as (1) one obtains the upper and lower bounds---matching to within a multiplicative constant---for the probability that a random covering map has some new adjacency eigenvalue outside the Alon bound, and (2) with probability smaller than any negative power of the degree of the covering map, some new eigenvalue fails to be within the Alon bound without the covering map containing one of finitely many "tangles" as a subgraph (and this tangle containment event has low probability). - Open Access
A Relativized Alon Second Eigenvalue Conjecture for Regular Base Graphs IV: An Improved Sidestepping Theorem
This is the fourth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this paper we prove a {\em Sidestepping Theorem} that is more general and easier to use than earlier theorems of this kind. Such theorems concerns a family probability spaces $\{{\mathcal{M}}_n\}$ of $n\times n$ matrices, where $n$ varies over some infinite set, $N$, of natural numbers. Many trace methods use simple "Markov bounds" to bound the expected spectral radius of elements of ${\mathcal{M}}_n$: this consists of choosing one value, $k=k(n)$, for each $n\in N$, and proving expected spectral radius bounds based on the expected value of the trace of the $k=k(n)$-power of elements of ${\mathcal{M}}_n$. {\em Sidestepping} refers to bypassing such simple Markov bounds, obtaining improved results using a number of values of $k$ for each fixed $n\in N$. In more detail, if the $M\in {\mathcal{M}}_n$ expected value of ${\rm Trace}(M^k)$ has an asymptotic expansion in powers of $1/n$, whose coefficients are "well behaved" functions of $k$, then one can get improved bounds on the spectral radius of elements of ${\mathcal{M}}_n$ that hold with high probability. Such asymptotic expansions are shown to exist in the third article in this series for the families of matrices that interest us; in the fifth and sixth article in this series we will apply the Sidestepping Theorem in this article to prove the main results in this series of articles. This article is independent of all other articles in this series; it can be viewed as a theorem purely in probability theory, concerning random matrices or, equivalently, the $n$ random variables that are the eigenvalues of the elements of ${\mathcal{M}}_n$.Open AccessA Relativized Alon Second Eigenvalue Conjecture for Regular Base Graphs IV: An Improved Sidestepping Theorem
This is the fourth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this paper we prove a {\em Sidestepping Theorem} that is more general and easier to use than earlier theorems of this kind. Such theorems concerns a family probability spaces $\{{\mathcal{M}}_n\}$ of $n\times n$ matrices, where $n$ varies over some infinite set, $N$, of natural numbers. Many trace methods use simple "Markov bounds" to bound the expected spectral radius of elements of ${\mathcal{M}}_n$: this consists of choosing one value, $k=k(n)$, for each $n\in N$, and proving expected spectral radius bounds based on the expected value of the trace of the $k=k(n)$-power of elements of ${\mathcal{M}}_n$. {\em Sidestepping} refers to bypassing such simple Markov bounds, obtaining improved results using a number of values of $k$ for each fixed $n\in N$. In more detail, if the $M\in {\mathcal{M}}_n$ expected value of ${\rm Trace}(M^k)$ has an asymptotic expansion in powers of $1/n$, whose coefficients are "well behaved" functions of $k$, then one can get improved bounds on the spectral radius of elements of ${\mathcal{M}}_n$ that hold with high probability. Such asymptotic expansions are shown to exist in the third article in this series for the families of matrices that interest us; in the fifth and sixth article in this series we will apply the Sidestepping Theorem in this article to prove the main results in this series of articles. This article is independent of all other articles in this series; it can be viewed as a theorem purely in probability theory, concerning random matrices or, equivalently, the $n$ random variables that are the eigenvalues of the elements of ${\mathcal{M}}_n$. - Open Access
On the Relativized Alon Second Eigenvalue Conjecture III: Asymptotic Expansions for Tangle-Free Hashimoto Traces
This is the third in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this paper we consider random graphs that are random covering graphs of large degree $n$ of a fixed base graph. We prove the existence of asympototic expansion in $1/n$ for the expected value of the number of strictly non-backtracking closed walks of length $k$ times the indicator function that the graph is free of certain {\em tangles}; moreover, we prove that the coefficients of these expansions are "nice functions" of $k$, namely approximately equal to a sum of polynomials in $k$ times exponential functions of $k$. Our results use the methods of Friedman used to resolve Alon's original conjecture, combined with the results of Article~II in this series of articles. One simplification in this article over the previous methods of Friedman is that the "regularlized traces" used in this article, which we call {\em certified traces}, are far easier to define and work with than the previously utilized {\em selective traces}.Open AccessOn the Relativized Alon Second Eigenvalue Conjecture III: Asymptotic Expansions for Tangle-Free Hashimoto Traces
This is the third in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this paper we consider random graphs that are random covering graphs of large degree $n$ of a fixed base graph. We prove the existence of asympototic expansion in $1/n$ for the expected value of the number of strictly non-backtracking closed walks of length $k$ times the indicator function that the graph is free of certain {\em tangles}; moreover, we prove that the coefficients of these expansions are "nice functions" of $k$, namely approximately equal to a sum of polynomials in $k$ times exponential functions of $k$. Our results use the methods of Friedman used to resolve Alon's original conjecture, combined with the results of Article~II in this series of articles. One simplification in this article over the previous methods of Friedman is that the "regularlized traces" used in this article, which we call {\em certified traces}, are far easier to define and work with than the previously utilized {\em selective traces}.