BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Tali Kaufman

Tali Kaufman contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COComputational ComplexityDiscrete MathematicsInformation Theorymath.GRmath.ITquant-ph

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
9works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

9 published item(s)

preprint2022arXiv

Combinatorics via Closed Orbits: Number Theoretic Ramanujan Graphs are not Unique Neighbor Expanders

The question of finding expander graphs with strong vertex expansion properties such as unique neighbor expansion and lossless expansion is central to computer science. A barrier to constructing these is that strong notions of expansion could not be proven via the spectral expansion paradigm. A very symmetric and structured family of optimal spectral expanders (i.e., Ramanujan graphs) was constructed using number theory by Lubotzky, Phillips and Sarnak, and was subsequently generalized by others. We call such graphs Number Theoretic Ramanujan Graphs. These graphs are not only spectrally optimal, but also posses strong symmetries and rich structure. Thus, it has been widely conjectured that number theoretic Ramanujan graphs are lossless expanders, or at least unique neighbor expanders. In this work we disprove this conjecture, by showing that there are number theoretic Ramanujan graphs that are not even unique neighbor expanders. This is done by introducing a new combinatorial paradigm that we term the closed orbit method. The closed orbit method allows one to construct finite combinatorial objects with extermal substructures. This is done by observing that there exist infinite combinatorial structures with extermal substructures, coming from an action of a subgroup of the automorphism group of the structure. The crux of our idea is a systematic way to construct a finite quotient of the infinite structure containing a simple shadow of the infinite substructure, which maintains its extermal combinatorial property. Other applications of the method are to the edge expansion of number theoretic Ramanujan graphs and vertex expansion of Ramanujan complexes. Finally, in the field of graph quantum ergodicity we produce number theoretic Ramanujan graphs with an eigenfunction of small support that corresponds to the zero eigenvalue. This again contradicts common expectations.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Garland's Technique for Posets and High Dimensional Grassmannian Expanders

Local to global machinery plays an important role in the study of simplicial complexes, since the seminal work of Garland [G] to our days. In this work we develop a local to global machinery for general posets. We show that the high dimensional expansion notions and many recent expansion results have a generalization to posets. Examples are fast convergence of high dimensional random walks generalizing [KO,AL], an equivalence with a global random walk definition, generalizing [DDFH] and a trickling down theorem, generalizing [O]. In particular, we show that some posets, such as the Grassmannian poset, exhibit qualitatively stronger trickling down effect than simplicial complexes. Using these methods, and the novel idea of Posetification, to Ramanujan complexes [LSV1,LSV2], we construct a constant degree expanding Grassmannian poset, and analyze its expansion. This it the first construction of such object, whose existence was conjectured in [DDFH].

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Improved Optimal Testing Results from Global Hypercontractivity

The problem of testing low-degree polynomials has received significant attention over the years due to its importance in theoretical computer science, and in particular in complexity theory. The problem is specified by three parameters: field size $q$, degree $d$ and proximity parameter $δ$, and the goal is to design a tester making as few as possible queries to a given function, which is able to distinguish between the case the given function has degree at most $d$, and the case the given function is $δ$-far from any degree $d$ function. A tester is called optimal if it makes $O(q^d+1/δ)$ queries (which are known to be necessary). For the field of size $q$, the natural $t$-flat tester was shown to be optimal first by Bhattacharyya et al. for $q=2$, and later by Haramaty et al. for all prime powers $q$. The dependency on the field size, however, is a tower-type function. We improve the results above, showing that the dependency on the field size is polynomial. Our approach also applies in the more general setting of lifted affine invariant codes, and is based on studying the structure of the collection of erroneous subspaces. i.e. subspaces $A$ such that $f|_{A}$ has degree greater than $d$. Towards this end, we observe that these sets are poorly expanding in the affine version of the Grassmann graph and use that to establish structural results on them via global hypercontractivity. We then use this structure to perform local correction on $f$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Scalar and Matrix Chernoff Bounds from $\ell_{\infty}$-Independence

We present new scalar and matrix Chernoff-style concentration bounds for a broad class of probability distributions over the binary hypercube $\{0,1\}^n$. Motivated by recent tools developed for the study of mixing times of Markov chains on discrete distributions, we say that a distribution is $\ell_\infty$-independent when the infinity norm of its influence matrix $\mathcal{I}$ is bounded by a constant. We show that any distribution which is $\ell_\infty$-independent satisfies a matrix Chernoff bound that matches the matrix Chernoff bound for independent random variables due to Tropp. Our matrix Chernoff bound is a broad generalization and strengthening of the matrix Chernoff bound of Kyng and Song (FOCS'18). Using our bound, we can conclude as a corollary that a union of $O(\log|V|)$ random spanning trees gives a spectral graph sparsifier of a graph with $|V|$ vertices with high probability, matching results for independent edge sampling, and matching lower bounds from Kyng and Song.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Coboundary and cosystolic expansion from strong symmetry

Coboundary and cosystolic expansion are notions of expansion that generalize the Cheeger constant or edge expansion of a graph to higher dimensions. The classical Cheeger inequality implies that for graphs edge expansion is equivalent to spectral expansion. In higher dimensions this is not the case: a simplicial complex can be spectrally expanding but not have high dimensional edge-expansion. The phenomenon of high dimensional edge expansion in higher dimensions is much more involved than spectral expansion, and is far from being understood. In particular, prior to this work, the only known bounded degree cosystolic expanders known were derived from the theory of buildings that is far from being elementary. In this work we study high dimensional complexes which are {\em strongly symmetric}. Namely, there is a group that acts transitively on top dimensional cells of the simplicial complex [e.g., for graphs it corresponds to a group that acts transitively on the edges]. Using the strong symmetry, we develop a new machinery to prove coboundary and cosystolic expansion.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Decodable quantum LDPC codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders

Constructing quantum LDPC codes with a minimum distance that grows faster than a square root of the length has been a major challenge of the field. With this challenge in mind, we investigate constructions that come from high-dimensional expanders, in particular Ramanujan complexes. These naturally give rise to very unbalanced quantum error correcting codes that have a large $X$-distance but a much smaller $Z$-distance. However, together with a classical expander LDPC code and a tensoring method that generalises a construction of Hastings and also the Tillich-Zemor construction of quantum codes, we obtain quantum LDPC codes whose minimum distance exceeds the square root of the code length and whose dimension comes close to a square root of the code length. When the ingredient is a 3-dimensional Ramanujan complex, we show that its 2-systole behaves like a square of the log of the complex size, which results in an overall quantum code of minimum distance $n^{1/2}\log n$, and sets a new record for quantum LDPC codes. When we use a 2-dimensional Ramanujan complex, or the 2-skeleton of a 3-dimensional Ramanujan complex, we obtain a quantum LDPC code of minimum distance $n^{1/2}\log^{1/2}n$. We then exploit the expansion properties of the complex to devise the first polynomial time algorithm that decodes above the square root barrier for quantum LDPC codes.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

High dimensional expansion using zig-zag product

We wish to renew the discussion over recent combinatorial structures that are 3-uniform hypergraph expanders, viewing them in a more general perspective, shedding light on a previously unknown relation to the zig-zag product. We do so by introducing a new structure called triplet structure, that maintains the same local environment around each vertex. The structure is expected to yield, in some cases, a bounded family of hypergraph expanders whose 2-dimensional random walk converges. We have applied the results obtained here to several known constructions, obtaining a better expansion rate than previously known. Namely, we did so in the case of Conlon's construction and the $S=[1,1,0]$ construction by Chapman, Linal and Peled.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Transitive bounded-degree 2-expanders from regular 2-expanders

A two-dimensional simplicial complex is called $d$-{\em regular} if every edge of it is contained in exactly $d$ distinct triangles. It is called $ε$-expanding if its up-down two-dimensional random walk has a normalized maximal eigenvalue which is at most $1-ε$. In this work, we present a class of bounded degree 2-dimensional expanders, which is the result of a small 2-complex action on a vertex set. The resulted complexes are fully transitive, meaning the automorphism group acts transitively on their faces. Such two-dimensional expanders are rare! Known constructions of such bounded degree two-dimensional expander families are obtained from deep algebraic reasonings (e.g. coset geometries). We show that given a small $d$-regular two-dimensional $ε$-expander, there exists an $ε'=ε'(ε)$ and a family of bounded degree two-dimensional simplicial complexes with a number of vertices goes to infinity, such that each complex in the family satisfies the following properties: * It is $4d$-regular. * The link of each vertex in the complex is the same regular graph (up to isomorphism). * It is $ε'$ expanding. * It is transitive. The family of expanders that we get is explicit if the one-skeleton of the small complex is a complete multipartite graph, and it is random in the case of (almost) general $d$-regular complex. For the randomized construction, we use results on expanding generators in a product of simple Lie groups. This construction is inspired by ideas that occur in the zig-zag product for graphs. It can be seen as a loose two-dimensional analog of the replacement product.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Dense locally testable codes cannot have constant rate and distance

A q-query locally testable code (LTC) is an error correcting code that can be tested by a randomized algorithm that reads at most q symbols from the given word. An important question is whether there exist LTCs that have the ccc-property: constant relative rate, constant relative distance, and that can be tested with a constant number of queries. Such codes are sometimes referred to as "asymptotically good". We show that dense LTCs cannot be ccc. The density of a tester is roughly the average number of distinct local views in which a coordinate participates. An LTC is dense if it has a tester with density >> 1. More precisely, we show that a 3-query locally testable code with a tester of density >> 1 cannot be ccc. Moreover, we show that a q-query locally testable code (q>3) with a tester of density >> n^{q-2} cannot be ccc. Our results hold when the tester has the following two properties: 1) "no weights": Every q-tuple of queries occurs with the same probability. 2) "last-one-fixed": In every `test' of the tester, the value to any q-1 of the symbols determines the value of the last symbol. (Linear codes have constraints of this type). We also show that several natural ways to quantitatively improve our results would already resolve the general ccc-question, i.e. also for non-dense LTCs.

0 citations0 reviewsNo code linkedOpen access