Farbod Shokrieh - Research and Publications
My MathSciNet profile
My Google Scholar profile
Publications and Preprints
- The monodromy pairing and discrete logarithm on the Jacobian of finite graphs. Journal of Mathematical Cryptology, Volume 4, Issue 1, Pages 43-56, 2010. Journal version, arXiv version
- Improved simulation of nondeterministic Turing machines.
Theoretical Computer Science, Pages 66-73, 2010.
(with S. Kalyanasundaram, R. J. Lipton, K. W. Regan)
- Chip-firing games, potential theory on graphs, and
spanning trees. Journal of Combinatorial Theory,
Series A, Volume 120, Issue 1, Pages 164-182, 2013.
(with Matthew Baker)
Journal version, arXiv
- Divisors on graphs, connected flags, and syzygies.
International Mathematics Research Notices (IMRN),
no. 24, Pages 6839-6905, 2014.
(with Fatemeh Mohammadi)
Journal version, arXiv
version, extended abstract (appeared in FPSAC '13)
- Canonical representatives for divisor classes on tropical
curves and the Matrix-Tree Theorem. Forum of
Mathematics, Sigma, Volume 2, 25 pages, 2014.
(with Yang An, Matthew Baker, and Greg Kuperberg)
Journal version, arXiv version
- Divisors on graphs, binomial and monomial ideals, and
cellular resolutions. Mathematische Zeitschrift,
Volume 283, Issue 1, Pages 59-102, 2016.
(with Fatemeh Mohammadi)
Journal version, arXiv version
- Non-Archimedean and tropical theta functions. Mathematische Annalen, 2018.
(with Tyler Foster, Joseph Rabinoff, and Alejandro Soto)
Journal version, arXiv version, free view-only journal version
- Canonical measures on metric graphs and a Kazhdan's theorem. 36 pages, 2017.
(with Chenxi Wu)
Every graph has a canonical finite abelian group attached to it. This group has appeared in the literature under a variety of names including the sandpile group, critical group, Jacobian group, and Picard group. The construction of this group closely mirrors the construction of the Jacobian variety of an algebraic curve. Motivated by this analogy, it was recently suggested by Norman Biggs that the critical group of a finite graph is a good candidate for doing discrete logarithm based cryptography. In this paper, we study a bilinear pairing on this group and show how to compute it. Then we use this pairing to find the discrete logarithm efficiently, thus showing that the associated cryptographic schemes are not secure. Our approach resembles the MOV attack on elliptic curves.
The standard simulation of a nondeterministic Turing machine (NTM) by a deterministic one essentially searches a large bounded-degree graph whose size is exponential in the running time of the NTM. The graph is the natural one defined by the configurations of the NTM. All methods in the literature have required time linear in the size of this graph. This paper presents a new simulation method that runs in time . The search savings exploit the one-dimensional nature of Turing machine tapes. In addition, we remove most of the time dependence on nondeterministic choices of states and tape head movements.
We study the interplay between chip-firing games and
potential theory on graphs, characterizing reduced divisors
(-parking functions) on graphs as the solution to an energy
(or potential) minimization problem and providing an algorithm
to efficiently compute reduced divisors. Applications include
efficient bijective proof of Kirchhoff's matrix-tree
theorem and a new algorithm for finding random spanning
trees. The running times of our algorithms are analyzed using
potential theory, and we show that the bounds thus obtained
generalize and improve upon several previous results in the
We study the binomial and monomial ideals arising from
linear equivalence of divisors on graphs from the point of
view of Gröbner theory. We give an explicit description
of a minimal Gröbner basis for each higher syzygy
module. In each case the given minimal Gröbner basis is
also a minimal generating set. The Betti numbers of the
binomial ideal and its natural initial ideal coincide and they
correspond to the number of
connected flags in the
graph. In particular the Betti numbers are independent of the
characteristic of the base field. For complete graphs the
problem was previously studied by Postnikov and Shapiro and
by Manjunath and Sturmfel. The case of a general graph was stated as an open problem.
Let be a compact tropical curve (or metric graph) of genus . Using the theory of tropical theta functions, Mikhalkin and Zharkov proved that there is a canonical effective representative for each linear equivalence class of divisors of degree on . We characterize these canonical effective representatives as the set of break divisors on and present a new combinatorial proof that there is a unique break divisor in each equivalence class. We also establish the closely related fact that for fixed in , every divisor of degree is linearly equivalent to a unique -orientable divisor. For both of these results, we also prove discrete versions for finite unweighted graphs which do not follow from the results of Mikhalkin-Zharkov. As an application of the theory of break divisors, we provide a "geometric proof" of (a dual version of) Kirchhoff's celebrated Matrix-Tree Theorem. Indeed, we show that each weighted graph model for gives rise to a canonical polyhedral decomposition of the -dimensional real torus into parallelotopes , one for each spanning tree of , and the dual Kirchhoff theorem becomes the statement that the volume of is the sum of the volumes of the cells in the decomposition.
We study various binomial and monomial ideals arising in the theory of divisors, orientations, and matroids on graphs. We use ideas from potential theory on graphs and from the theory of Delaunay decompositions for lattices to describe their minimal polyhedral cellular free resolutions. We show that the resolutions of all these ideals are closely related and that their -graded Betti tables coincide. As corollaries, we give conceptual proofs of conjectures and questions posed by Postnikov and Shapiro, by Manjunath and Sturmfels, and by Perkinson, Perlman, and Wilmes. Various other results related to the theory of chip-firing games on graphs also follow from our general techniques and results.
We define a tropicalization procedure for theta functions on abelian varieties over a non-Archimedean field. We show that the tropicalization of a non-Archimedean theta function is a tropical theta function, and that the tropicalization of a non-Archimedean Riemann theta function is a tropical Riemann theta function, up to scaling and an additive constant. We apply these results to the construction of rational functions with prescribed behavior on the skeleton of a principally polarized abelian variety. We work with the Raynaud--Bosch--Lütkebohmert theory of non-Archimedean theta functions for abelian varieties with semi-abelian reduction.
Here is a link to my short note on basic von Neumann algebra theory, written mainly for my own benefit.
We extend the notion of canonical measures to all (possibly non-compact) metric graphs. This will allow us to introduce a notion of
hyperbolic measures on universal covers of metric graphs. Kazhdan's theorem for Riemann surfaces describes the limiting behavior of canonical (Arakelov) measures on finite covers in relation to the hyperbolic measure. We will prove a generalized version of this theorem for metric graphs, allowing any infinite Galois cover to replace the universal cover. We will show all such limiting measures satisfy a version of Gauss-Bonnet formula which, using the theory of von Neumann dimensions, can be interpreted as a
trace formula. In the special case where the infinite cover is the universal cover, we will provide explicit methods to compute the corresponding limiting (hyperbolic) measure. Our ideas are motivated by non-Archimedean analytic and tropical geometry.
|email: email@example.com||office phone: 607-255-5380||office: 436 Malott Hall|
|Disclaimer: This is not a publication of Cornell University and Cornell University has not edited or examined the content.|
|(Last modified on: January 19, 2018)|