Source author record

Qi Cheng

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

ResearcherUnclaimed source record

math.NT Computational Complexity Cryptography and Security Information Theory math.IT Computational Geometry Machine Learning nucl-ex physics.data-an physics.ins-det Quantitative Methods Symbolic Computation

Catalog footprint

What is connected

12works

12topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2021arXiv

Mixture Model Framework for Traumatic Brain Injury Prognosis Using Heterogeneous Clinical and Outcome Data

Prognoses of Traumatic Brain Injury (TBI) outcomes are neither easily nor accurately determined from clinical indicators. This is due in part to the heterogeneity of damage inflicted to the brain, ultimately resulting in diverse and complex outcomes. Using a data-driven approach on many distinct data elements may be necessary to describe this large set of outcomes and thereby robustly depict the nuanced differences among TBI patients' recovery. In this work, we develop a method for modeling large heterogeneous data types relevant to TBI. Our approach is geared toward the probabilistic representation of mixed continuous and discrete variables with missing values. The model is trained on a dataset encompassing a variety of data types, including demographics, blood-based biomarkers, and imaging findings. In addition, it includes a set of clinical outcome assessments at 3, 6, and 12 months post-injury. The model is used to stratify patients into distinct groups in an unsupervised learning setting. We use the model to infer outcomes using input data, and show that the collection of input data reduces uncertainty of outcomes over a baseline approach. In addition, we quantify the performance of a likelihood scoring technique that can be used to self-evaluate the extrapolation risk of prognosis on unseen patients.

preprint2021arXiv

On the ideal shortest vector problem over random rational primes

Any ideal in a number field can be factored into a product of prime ideals. In this paper we study the prime ideal shortest vector problem (SVP) in the ring $ \Z[x]/(x^{2^n} + 1) $, a popular choice in the design of ideal lattice based cryptosystems. We show that a majority of rational primes lie under prime ideals admitting a polynomial time algorithm for SVP. Although the shortest vector problem of ideal lattices underpins the security of Ring-LWE cryptosystem, this work does not break Ring-LWE, since the security reduction is from the worst case ideal SVP to the average case Ring-LWE, and it is one-way.

preprint2020arXiv

Computing zeta functions of large polynomial systems over finite fields

In this paper, we improve the algorithms of Lauder-Wan \cite{LW} and Harvey \cite{Ha} to compute the zeta function of a system of $m$ polynomial equations in $n$ variables over the finite field $\FF_q$ of $q$ elements, for $m$ large. The dependence on $m$ in the original algorithms was exponential in $m$. Our main result is a reduction of the exponential dependence on $m$ to a polynomial dependence on $m$. As an application, we speed up a doubly exponential time algorithm from a software verification paper \cite{BJK} (on universal equivalence of programs over finite fields) to singly exponential time. One key new ingredient is an effective version of the classical Kronecker theorem which (set-theoretically) reduces the number of defining equations for a "large" polynomial system over $\FF_q$ when $q$ is suitably large.

preprint2020arXiv

Pulse Pileup Rejection Methods Using a Two-Component Gaussian Mixture Model for Fast Neutron Detection with Pulse Shape Discriminating Scintillator

Pulse shape discriminating scintillator materials in many cases allow the user to identify two basic kinds of pulses arising from two kinds of particles: neutrons and gammas. An uncomplicated solution for building a classifier consists of a two-component mixture model learned from a collection of pulses from neutrons and gammas at a range of energies. Depending on the conditions of data gathered to be classified, multiple classes of events besides neutrons and gammas may occur, most notably pileup events. All these kinds of events are anomalous and, in cases where the class of the particle is in doubt, it is preferable to remove them from the analysis. This study compares the performance of several machine learning and analytical methods for using the scores from the two-component model to identify anomalous events and in particular to remove pileup events. A specific outcome of this study is to propose a novel anomaly score, denoted G, from an unsupervised two-component model that is conveniently distributed on the interval [-1,1].

preprint2016arXiv

Sparse Univariate Polynomials with Many Roots Over Finite Fields

Suppose $q$ is a prime power and $f\in\mathbb{F}_q[x]$ is a univariate polynomial with exactly $t$ monomial terms and degree $<q-1$. To establish a finite field analogue of Descartes' Rule, Bi, Cheng, and Rojas (2013) proved an upper bound of $2(q-1)^{\frac{t-2}{t-1}}$ on the number of cosets in $\mathbb{F}^*_q$ needed to cover the roots of $f$ in $\mathbb{F}^*_q$. Here, we give explicit $f$ with root structure approaching this bound: For $q$ a $(t-1)$-st power of a prime we give an explicit $t$-nomial vanishing on $q^{\frac{t-2}{t-1}}$ distinct cosets of $\mathbb{F}^*_q$. Over prime fields $\mathbb{F}_p$, computational data we provide suggests that it is harder to construct explicit sparse polynomials with many roots. Nevertheless, assuming the Generalized Riemann Hypothesis, we find explicit trinomials having $Ω\left(\frac{\log p}{\log \log p}\right)$ distinct roots in $\mathbb{F}_p$.

preprint2013arXiv

On Determining Deep Holes of Generalized Reed-Solomon Codes

For a linear code, deep holes are defined to be vectors that are further away from codewords than all other vectors. The problem of deciding whether a received word is a deep hole for generalized Reed-Solomon codes is proved to be co-NP-complete. For the extended Reed-Solomon codes $RS_q(\F_q,k)$, a conjecture was made to classify deep holes by Cheng and Murray in 2007. Since then a lot of effort has been made to prove the conjecture, or its various forms. In this paper, we classify deep holes completely for generalized Reed-Solomon codes $RS_p (D,k)$, where $p$ is a prime, $|D| > k \geqslant \frac{p-1}{2}$. Our techniques are built on the idea of deep hole trees, and several results concerning the Erd{ö}s-Heilbronn conjecture.

preprint2013arXiv

Traps to the BGJT-Algorithm for Discrete Logarithms

In the recent breakthrough paper by Barbulescu, Gaudry, Joux and Thom{é}, a quasi-polynomial time algorithm (QPA) is proposed for the discrete logarithm problem over finite fields of small characteristic. The time complexity analysis of the algorithm is based on several heuristics presented in their paper. We show that some of the heuristics are problematic in their original forms, in particular, when the field is not a Kummer extension. We believe that the basic idea behind the new approach should still work, and propose a fix to the algorithm in non-Kummer cases, without altering the quasi-polynomial time complexity. The modified algorithm is also heuristic. Further study is required in order to fully understand the effectiveness of the new approach.

preprint2012arXiv

On Certain Computations of Pisot Numbers

This paper presents two algorithms on certain computations about Pisot numbers. Firstly, we develop an algorithm that finds a Pisot number $α$ such that $\Q[α] = \F$ given a real Galois extension $\F$ of $\Q$ by its integral basis. This algorithm is based on the lattice reduction, and it runs in time polynomial in the size of the integral basis. Next, we show that for a fixed Pisot number $α$, one can compute $ [α^n] \pmod{m}$ in time polynomial in $(\log (m n))^{O(1)}$, where $m$ and $n$ are positive integers.

preprint2012arXiv

Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields

We present a deterministic 2^O(t)q^{(t-2)(t-1)+o(1)} algorithm to decide whether a univariate polynomial f, with exactly t monomial terms and degree <q, has a root in F_q. A corollary of our method --- the first with complexity sub-linear in q when t is fixed --- is that the nonzero roots in F_q can be partitioned into at most 2 \sqrt{t-1} (q-1)^{(t-2)(t-1)} cosets of two subgroups S_1,S_2 of F^*_q, with S_1 in S_2. Another corollary is the first deterministic sub-linear algorithm for detecting common degree one factors of k-tuples of t-nomials in F_q[x] when k and t are fixed. When t is not fixed we show that each of the following problems is NP-hard with respect to BPP-reductions, even when p is prime: (1) detecting roots in F_p for f, (2) deciding whether the square of a degree one polynomial in F_p[x] divides f, (3) deciding whether the discriminant of f vanishes, (4) deciding whether the gcd of two t-nomials in F_p[x] has positive degree. Finally, we prove that if the complexity of root detection is sub-linear (in a refined sense), relative to the straight-line program encoding, then NEXP is not in P/Poly.

preprint2011arXiv

Counting Value Sets: Algorithm and Complexity

Let $p$ be a prime. Given a polynomial in $\F_{p^m}[x]$ of degree $d$ over the finite field $\F_{p^m}$, one can view it as a map from $\F_{p^m}$ to $\F_{p^m}$, and examine the image of this map, also known as the value set. In this paper, we present the first non-trivial algorithm and the first complexity result on computing the cardinality of this value set. We show an elementary connection between this cardinality and the number of points on a family of varieties in affine space. We then apply Lauder and Wan's $p$-adic point-counting algorithm to count these points, resulting in a non-trivial algorithm for calculating the cardinality of the value set. The running time of our algorithm is $(pmd)^{O(d)}$. In particular, this is a polynomial time algorithm for fixed $d$ if $p$ is reasonably small. We also show that the problem is #P-hard when the polynomial is given in a sparse representation, $p=2$, and $m$ is allowed to vary, or when the polynomial is given as a straight-line program, $m=1$ and $p$ is allowed to vary. Additionally, we prove that it is NP-hard to decide whether a polynomial represented by a straight-line program has a root in a prime-order finite field, thus resolving an open problem proposed by Kaltofen and Koiran in \cite{Kaltofen03,KaltofenKo05}.

preprint2009arXiv

Bounding the Sum of Square Roots via Lattice Reduction

Let $k$ and $n$ be positive integers. Define $R(n,k)$ to be the minimum positive value of $$ | e_i \sqrt{s_1} + e_2 \sqrt{s_2} + ... + e_k \sqrt{s_k} -t | $$ where $ s_1, s_2, ..., s_k$ are positive integers no larger than $n$, $t$ is an integer and $e_i\in \{1,0, -1\}$ for all $1\leq i\leq k$. It is important in computational geometry to determine a good lower and upper bound of $ R(n,k)$. In this paper we show that this problem is closely related to the shortest vector problem in certain integral lattices and present an algorithm to find lower bounds based on lattice reduction algorithms. Although we can only prove an exponential time upper bound for the algorithm, it is efficient for large $k$ when an exhaustive search for the minimum value is clearly infeasible. It produces lower bounds much better than the root separation technique does. Based on numerical data, we formulate a conjecture on the length of the shortest nonzero vector in the lattice, whose validation implies that our algorithm runs in polynomial time and the problem of comparing two sums of square roots of small integers can be solved in polynomial time. As a side result, we obtain constructive upper bounds for $R(n,k)$ when $ n$ is much smaller than $2^{2k}$.

preprint2005arXiv

Hard Problems of Algebraic Geometry Codes

The minimum distance is one of the most important combinatorial characterizations of a code. The maximum likelihood decoding problem is one of the most important algorithmic problems of a code. While these problems are known to be hard for general linear codes, the techniques used to prove their hardness often rely on the construction of artificial codes. In general, much less is known about the hardness of the specific classes of natural linear codes. In this paper, we show that both problems are NP-hard for algebraic geometry codes. We achieve this by reducing a well-known NP-complete problem to these problems using a randomized algorithm. The family of codes in the reductions are based on elliptic curves. They have positive rates, but the alphabet sizes are exponential in the block lengths.