Joel Friedman

Professor

Research Interests

Computer Science Theory
Algebraic Graph Theory
Combinatorics

Relevant Degree Programs

 

Recruitment

Complete these steps before you reach out to a faculty member!

Check requirements
  • Familiarize yourself with program requirements. You want to learn as much as possible from the information available to you before you reach out to a faculty member. Be sure to visit the graduate degree program listing and program-specific websites.
  • Check whether the program requires you to seek commitment from a supervisor prior to submitting an application. For some programs this is an essential step while others match successful applicants with faculty members within the first year of study. This is either indicated in the program profile under "Requirements" or on the program website.
Focus your search
  • Identify specific faculty members who are conducting research in your specific area of interest.
  • Establish that your research interests align with the faculty member’s research interests.
    • Read up on the faculty members in the program and the research being conducted in the department.
    • Familiarize yourself with their work, read their recent publications and past theses/dissertations that they supervised. Be certain that their research is indeed what you are hoping to study.
Make a good impression
  • Compose an error-free and grammatically correct email addressed to your specifically targeted faculty member, and remember to use their correct titles.
    • Do not send non-specific, mass emails to everyone in the department hoping for a match.
    • Address the faculty members by name. Your contact should be genuine rather than generic.
  • Include a brief outline of your academic background, why you are interested in working with the faculty member, and what experience you could bring to the department. The supervision enquiry form guides you with targeted questions. Ensure to craft compelling answers to these questions.
  • Highlight your achievements and why you are a top student. Faculty members receive dozens of requests from prospective students and you may have less than 30 seconds to peek someone’s interest.
  • Demonstrate that you are familiar with their research:
    • Convey the specific ways you are a good fit for the program.
    • Convey the specific ways the program/lab/faculty member is a good fit for the research you are interested in/already conducting.
  • Be enthusiastic, but don’t overdo it.
Attend an information session

G+PS regularly provides virtual sessions that focus on admission requirements and procedures and tips how to improve your application.

 

Master's students
Doctoral students
Postdoctoral Fellows
Any time / year round

Computer Science Theory, Graph Theory, Combinatorics, Algebraic Topology applied to Combinatorics

Graduate Student Supervision

Doctoral Student Supervision (Jan 2008 - May 2019)
Abelian girth and gapped sheaves (2016)

The girth of a graph is the length of the shortest cycle in a graph, and the abelian girth of a graph is the girth of the graph's universal abelian covering graph. We denote the abelian girth of a graph G as Abl(G) and show that for d-regular graphs on n vertices with d constant and n growing we have Abl(G) ≤ 6 log_{d-1} n plus a vanishing term. This can be seen as a version of the Moore bound for abelian girth. We also prove Girth(G) ≤ Abl(G)/3, which implies that any multiplicative improvement to the abelian girth Moore bound would also improve the standard Moore bound. Sheaves on graphs and two of their homological invariants, the maximum excess and the first twisted Betti number, were used in the proof of the Hanna Neumann Conjecture from algebra and may be of use in proving several related unresolved conjectures. These conjectures can be proven if certain sheaves called ρ-kernels have vanishing maximum excess. Ungapped sheaves have maximum excess equal to the first twisted Betti number, and it is easy to compute the maximum excess of a given sheaf in the case that the sheaf is not gapped. For general sheaves though, there is no known way of computing the maximum excess in polynomial time. We give several conditions that gapped sheaves must satisfy. These conditions include that a gapped sheaf must have edge dimension at least as large as the abelian girth of the underlying graph. The ρ-kernels are subsheaves of constant sheaves. We prove that gapped subsheaves of constant sheaves exist, implying that finding maximum excess of some ρ-kernels may be computationally difficult.

View record

Alon's second eigenvalue conjecture : simplified and generalized (2013)

For a fixed graph, B, we study a probability model of random covering maps of degree n. Specifically, we study spectral properties of new eigenvalues of the adjacency matrix of a random covering, and its Hashimoto matrix (i.e., the adjacency matrix of the associated directed line graph).Our main theorem says that if B is d-regular, then for every positive epsilon, the probability that a random covering has a new adjacency eigenvalue greater than 2(d-1)^(1/2) + epsilon tends to zero as n tends to infinity. This matches the generalized Alon-Boppana lower bound.For general base graphs, B, Friedman conjectured in that the new eigenvalue bound holds with 2(d-1)^(1/2) replaced with the spectral radius of the universal cover of B. We refer to this conjecture as the generalized Alon conjecture; Alon stated this conjecture in the case where B has one vertex, i.e., the case of random d-regular graphs on n vertices. However, for some non-regular base graphs B, we cannot yet prove any non-trivial new eigenvalue upper bound with high probability.We use trace methods, as pioneered by Broder and Shamir for random, d-regular graphs; these methods were eventually refined by Friedman to prove the original Alon conjecture, i.e., in the case where B has one vertex. Our methods involve several significant simplifications of the methods of Friedman.

View record

 
 

If this is your researcher profile you can log in to the Faculty & Staff portal to update your details and provide recruitment preferences.