BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Hoang Ta

Hoang Ta appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational Complexitymath.COmath.AC

Catalog footprint

What is connected

2works
3topics
3close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Published work

2 published item(s)

preprint2022arXiv

Symmetric Subrank of Tensors and Applications

Strassen (Strassen, J. Reine Angew. Math., 375/376, 1987) introduced the subrank of a tensor as a natural extension of matrix rank to tensors. Subrank measures the largest diagonal tensor that can be obtained by applying linear operations to the different indices (legs) of the tensor (just like the matrix rank measures the largest diagonal matrix that can be obtained using row and column operations). Motivated by problems in combinatorics and complexity theory we introduce the new notion of symmetric subrank of tensors by restricting these linear operations to be the same for each index. We prove precise relations and separations between subrank and symmetric subrank. We prove that for symmetric tensors the subrank and the symmetric subrank are asymptotically equal. This proves the asymptotic subrank analogon of a conjecture known as Comon's conjecture in the theory of tensors. This result allows us to prove a strong connection between the general and symmetric version of an asymptotic duality theorem of Strassen. We introduce a representation-theoretic method to asymptotically bound the symmetric subrank called the symmetric quantum functional in analogy with the quantum functionals (Christandl, Vrana, Zuiddam, J. Amer. Math. Soc., 2021), and we study the relations between these functionals.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Larger Corner-Free Sets from Combinatorial Degenerations

There is a large and important collection of Ramsey-type combinatorial problems, closely related to central problems in complexity theory, that can be formulated in terms of the asymptotic growth of the size of the maximum independent sets in powers of a fixed small (directed or undirected) hypergraph, also called the Shannon capacity. An important instance of this is the corner problem studied in the context of multiparty communication complexity in the Number On the Forehead (NOF) model. Versions of this problem and the NOF connection have seen much interest (and progress) in recent works of Linial, Pitassi and Shraibman (ITCS 2019) and Linial and Shraibman (CCC 2021). We introduce and study a general algebraic method for lower bounding the Shannon capacity of directed hypergraphs via combinatorial degenerations, a combinatorial kind of "approximation" of subgraphs that originates from the study of matrix multiplication in algebraic complexity theory (and which play an important role there) but which we use in a novel way. Using the combinatorial degeneration method, we make progress on the corner problem by explicitly constructing a corner-free subset in $F_2^n \times F_2^n$ of size $Ω(3.39^n/poly(n))$, which improves the previous lower bound $Ω(2.82^n)$ of Linial, Pitassi and Shraibman (ITCS 2019) and which gets us closer to the best upper bound $4^{n - o(n)}$. Our new construction of corner-free sets implies an improved NOF protocol for the Eval problem. In the Eval problem over a group $G$, three players need to determine whether their inputs $x_1, x_2, x_3 \in G$ sum to zero. We find that the NOF communication complexity of the Eval problem over $F_2^n$ is at most $0.24n + O(\log n)$, which improves the previous upper bound $0.5n + O(\log n)$.

0 citations0 reviewsNo code linkedOpen access