![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
Chapter and Conference Paper
Algorithms for Matrix Code and Alternating Trilinear Form Equivalences via New Isomorphism Invariants
We devise algorithms for finding equivalences of trilinear forms over finite fields modulo linear group actions. Our focus is on two problems under this umbrella, Matrix Code Equivalence (MCE) and Alternating Tri...
-
Chapter and Conference Paper
Heterogeneous Multi-commodity Network Flows over Time
In the 1950’s, Ford and Fulkerson introduced dynamic flows by incorporating the notion of time into the network flow model (Oper. Res., 1958). In this paper, motivated by real-world applications including route p...
-
Chapter and Conference Paper
Practical Post-Quantum Signature Schemes from Isomorphism Problems of Trilinear Forms
In this paper, we propose a practical signature scheme based on the alternating trilinear form equivalence problem. Our scheme is inspired by the Goldreich-Micali-Wigderson’s zero-knowledge protocol for graph ...
-
Chapter and Conference Paper
Learning Domain Invariant Word Representations for Parsing Domain Adaptation
We show that strong domain adaptation results for dependency parsing can be achieved using a conceptually simple method that learns domain-invariant word representations. Lacking labeled resources, dependency ...
-
Chapter and Conference Paper
General Linear Group Action on Tensors: A Candidate for Post-quantum Cryptography
Starting from the one-way group action framework of Brassard and Yung (Crypto’90), we revisit building cryptography based on group actions. Several previous candidates for one-way group actions no longer stand...
-
Article
Constructive non-commutative rank computation is in deterministic polynomial time
We extend the techniques developed in Ivanyos et al. (Comput Complex 26(3):717–763, 2017) to obtain a deterministic polynomial-time algorithm for computing the non-commutative rank of linear spaces of matrices ov...
-
Article
Sparse multivariate polynomial interpolation on the basis of Schubert polynomials
Schubert polynomials were discovered by A. Lascoux and M. Schützenberger in the study of cohomology rings of flag manifolds in 1980s. These polynomials generalize Schur polynomials and form a linear basis of m...
-
Article
Non-commutative Edmonds’ problem and matrix semi-invariants
In 1967, J. Edmonds introduced the problem of computing the rank over the rational function field of an \({n \times n}\) ...
-
Chapter and Conference Paper
Improving Dependency Parsing on Clinical Text with Syntactic Clusters from Web Text
Treebanks for clinical text are not enough for supervised dependency parsing no matter in their scale or diversity, leading to still unsatisfactory performance. Many unlabeled text from web can make up for the...
-
Chapter and Conference Paper
Polynomial-Time Isomorphism Test of Groups that are Tame Extensions
We give new polynomial-time algorithms for testing isomorphism of a class of groups given by multiplication tables (GpI). Two results (Cannon & Holt, J. Symb. Comput. 2003; Babai, Codenotti & Qiao, ICALP 2012) im...
-
Chapter and Conference Paper
On the Power of Parity Queries in Boolean Decision Trees
In an influential paper, Kushilevitz and Mansour (1993) introduced a natural extension of Boolean decision trees called parity decision tree (PDT) where one may query the sum modulo
-
Article
Random arithmetic formulas can be reconstructed efficiently
Informally stated, we present here a randomized algorithm that given black-box access to the polynomial f computed by an unknown/hidden arithmetic formula ϕ reconstructs, on the average, an equivalent or smaller ...
-
Chapter and Conference Paper
An Efficient Quantum Algorithm for Finding Hidden Parabolic Subgroups in the General Linear Group
In the theory of algebraic groups, parabolic subgroups form a crucial building block in the structural studies. In the case of general linear groups over a finite field
-
Chapter and Conference Paper
On the Complexity of Trial and Error for Constraint Satisfaction Problems
In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle wh...
-
Chapter and Conference Paper
Determinantal Complexities and Field Extensions
Let \(\mathbb{F}\) be a field of characteristic ≠ 2. The determinantal complexity of a polynomial
-
Chapter and Conference Paper
Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive
For a Boolean function f, let D(f) denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine f. In a classic paper, Rivest and Vuil...
-
Article
On the security of Goldreich’s one-way function
Goldreich (ECCC 2000) suggested a simple construction of a candidate one-way function f : {0, 1} n → {0, 1} m where each bit of output is a fi...
-
Chapter and Conference Paper
Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups
We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The trivial n logn bound on the time complexity for the general case has not been impro...
-
Chapter and Conference Paper
On the Security of Goldreich’s One-Way Function
Goldreich (ECCC 2000) suggested a simple construction of a candidate one-way function f: {0,1} n → {0,1} m where each bit of output is a fixed...
-
Chapter and Conference Paper
Counting Method for Multi-party Computation over Non-abelian Groups
In the Crypto’07 paper [5], Desmedt et al. studied the problem of achieving secure n-party computation over non-Abelian groups. The function to be computed is f G ...