14 Result(s)
within
**uming Qiao
Algorithm Analysis and Problem Complexity
-
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
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 ...
