![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
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 ...
-
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
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
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...
-
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
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
-
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
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...
-
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
On Digital Signatures Based on Group Actions: QROM Security and Ring Signatures
Group action based cryptography was formally proposed in the seminal paper of Brassard and Yung (Crypto 1990). Based on one-way group action, there is a well-known digital signature design based on the Goldrei...
-
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
Construction of an Urban Road Collapse Risk Assessment Model and Its Case Study in Guangzhou
Road collapse has become one of the frequent geological disasters in large cities, and effective road collapse risk assessment is of great significance for the arrangement of urban road collapse prevention and...