Ker-I Ko

TCS Journal 2021 Journal Article

On continuous one-way functions

• Ker-I Ko
• Lidong Wu

The existence of one-way functions seems to depend, intuitively, on certain irregular properties of polynomial-time computable functions. Therefore, for functions with continuity properties, it suggests that all such functions are not one-way. It is shown here that in the formal complexity theory of real functions, this nonexistence of continuous one-way functions can be proved for one-to-one one-dimensional real functions, but fails for one-to-one two-dimensional real functions, if certain strong discrete one-way functions exist. Furthermore, for k-to-one functions, we can prove the existence of four-to-one one-dimensional one-way functions under the same assumption of the existence of strong discrete one-way functions. (A function f is k-to-one if for any y there exist at most k distinct values x such that f ( x ) = y.)

TCS Journal 2017 Journal Article

Competitive profit maximization in social networks

• Weian Li
• Wenjing Liu
• Tiantian Chen
• Xiaoying Qu
• Qizhi Fang
• Ker-I Ko

We study the competitive profit maximization problem in a social network, which can be viewed as the profit maximization problem in a game-theoretic setting. We formulate two models called the profit maximization-agent (PM-A) game and the profit maximization-society (PM-S) game. By reducing them to be valid utility systems, we show that any Nash equilibrium provides an excepted social utility within a factor 1/2 (subject to a function-dependent additive term) of the optimum in the PM-A game and a factor of 1/2 of the optimum in the PM-S game. Furthermore, for the PM-S game, a polynomial-time algorithm is given for each player that can approximate the best response within a factor ( 1 − 1 / e ).

TCS Journal 2013 Journal Article

On logarithmic-space computable real numbers

• Fuxiang Yu
• Ker-I Ko

We study, in this paper, the relationship among the classes of logarithmic-space computable real numbers under different representations. We consider logarithmic-space computable real numbers under the Cauchy function representation, the general left cut representation, the standard left cut representation, and the binary expansion representation. It is shown that the relationship among these classes of real numbers depends on the relationship between the discrete complexity classes P 1 and L 1, the classes of tally sets in P and L, respectively. First, if P 1 = L 1, then the relationship among the four classes of logarithmic-space computable real numbers is the same as that among these classes of polynomial-time computable real numbers. On the other hand, if P 1 ≠ L 1, then we get different relationships from those among classes of polynomial-time computable real numbers. For instance, while the classes of polynomial-time computable real numbers under the general left cut and the Cauchy function representations are equivalent, we show, under the assumption of P 1 ≠ L 1, that the class of logarithmic-space computable real numbers under the general left cut representation properly contains the class of logarithmic-space computable real numbers under the Cauchy function representation. In addition, if P 1 ≠ L 1, then the two classes of logarithmic-space computable real numbers under the standard left cut and the Cauchy function representations are incomparable.

TCS Journal 2013 Journal Article

On parallel complexity of analytic functions

• Fuxiang Yu
• Ker-I Ko

In this paper, we study the parallel complexity of analytic functions. We investigate the complexity of computing the derivatives, integrals, and zeros of N C or logarithmic-space computable analytic functions, where N C denotes the complexity class of sets acceptable by polynomial-size, polylogarithmic-depth, uniform Boolean circuits. It is shown that the derivatives and integrals of N C (or logarithmic-space) computable analytic functions remain N C (or, respectively, logarithmic-space) computable. We also study the problem of finding all zeros of an NC computable analytic function inside an N C computable Jordan curve, and show that, under a uniformity condition on the function values on the Jordan curve, all zeros can be found in NC.

TCS Journal 2008 Journal Article

On the complexity of non-unique probe selection

• Yongxi Cheng
• Ker-I Ko
• Weili Wu

We investigate the computational complexity of some basic problems regarding non-unique probe selection using separable matrices. In particular, we prove that the minimal d ̄ -separable matrix problem is DP -complete, and the d ̄ -separable submatrix with reserved rows problem, which is a generalization of the decision version of the minimum d ̄ -separable submatrix problem, is Σ 2 P -complete.

TCS Journal 2007 Journal Article

Jordan curves with polynomial inverse moduli of continuity

• Ker-I Ko
• Fuxiang Yu

Computational complexity of two-dimensional domains whose boundaries are polynomial-time computable Jordan curves with polynomial inverse moduli of continuity is studied. It is shown that the membership problem of such a domain can be solved in P NP, i. e. , in polynomial time relative to an oracle in NP, in contrast to the higher upper bound P MP for domains without the property of polynomial inverse modulus of continuity. On the other hand, the lower bound of UP for the membership problem still holds for domains with polynomial inverse moduli of continuity. It is also shown that the shortest path problem of such a domain can be solved in PSPACE, close to its known lower bound, while no fixed upper bound was known for domains without this property.

TCS Journal 2005 Journal Article

The computational complexity of distance functions of two-dimensional domains

• Arthur W. Chou
• Ker-I Ko

We study the computational complexity of the distance function associated with a polynomial-time computable two-dimensional domains, in the context of the Turing machine-based complexity theory of real functions. It is proved that the distance function is not necessarily computable even if a two-dimensional domain is polynomial-time recognizable. On the other hand, if both the domain and its complement are strongly polynomial-time recognizable, then the distance function is polynomial-time computable if and only if P = NP.

TCS Journal 2004 Journal Article

A greedy approximation for minimum connected dominating sets

• Lu Ruan
• Hongwei Du
• Xiaohua Jia
• Weili Wu
• Yingshu Li
• Ker-I Ko

Given a graph, a connected dominating set is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum connected dominating set is such a vertex subset with minimum cardinality. In this paper, we present a new one-step greedy approximation with performance ratio ln δ + 2 where δ is the maximum degree in the input graph. The interesting aspect is that the greedy potential function of this algorithm is not supmodular while all previously known one-step greedy algorithms with similar performance have supmodular potential functions.

TCS Journal 1999 Journal Article

Foreword

• Anil Nerode
• Ker-I Ko
• Klaus Weihrauch

TCS Journal 1995 Journal Article

A polynomial-time computable curve whose interior has a nonrecursive measure

• Ker-I Ko

A polynomial-time computable simple curve is constructed such that its measure in the two-dimensional plane is positive. This construction is applied to prove the following two results: 1. 1) there exists a polynomial-time computable simple closed curve in the two-dimensional plane such that the measure of its interior region is a nonrecursive real number; 2. (2) there exists a polynomial-time computable simple curve in the two-dimensional plane such that its length is finite but is a nonrecursive real number.

STOC Conference 1993 Conference Paper

Some complexity issues on the simply connected regions of the two-dimensional plane

• Arthur W. Chou
• Ker-I Ko

STOC Conference 1991 Conference Paper

Integral Equations, Systems of Quadratic Equations, and Exponential-Time Completeness (Extended Abstract)

• Ker-I Ko

TCS Journal 1991 Journal Article

On adaptive versus nonadaptive bounded query machines

• Ker-I Ko

The polynomial-time adaptive (Turing) and nonadaptive (truth-table) bounded query machines are compared with respect to sparse oracles. A k-query adaptive machine has been found which, relative to a sparse oracle, cannot be simulated by any (2 k −2)-query nonadaptive machine, even with a different sparse oracle. Conversely, there is a (3·2 k−2)-query nonadaptive machine which, relative to a sparse oracle, cannot be simulated by any k-query adaptive machine, with any sparse oracle.

I&C Journal 1991 Journal Article

Separating the low and high hierachies by oracles

• Ker-I Ko

The relativized low and high hierarchies within NP are considered. An oracle A is constructed such that the low and high hierarchies relative to A are infinite, and for each k an oracle A k is constructed such that the low and high hierarchies relative to A k have exactly k levels.

FOCS Conference 1989 Conference Paper

Computational Complexity of Roots of Real Functions (Extended Abstract)

• Ker-I Ko

An attempt is made to give a more accurate classification of the computational complexity of roots of real functions. Attention is focused on the simplest types of functions, namely, one-to-one and k-to-one functions, and the complexity of their roots is characterized in terms of relations between discrete complexity classes, such as LOGSPACE, P, UP, and NP. >

I&C Journal 1989 Journal Article

Distinguishing conjunctive and disjunctive reducibilities by sparse sets

• Ker-I Ko

Various polynomial-time truth-table reducibilities are compared by their ability of using sparse oracles to answer queries. The reducibilities studied here include conjunctive reducibility, bounded conjunctive reducibility, disjunctive reducibility, bounded disjunctive reducibility, truth-table reducibility, and bounded truth-table reducibility. For any two reducibilities ≤ r P and ≤ s P, we compare the class of sets ≤ r P -reducible to sparse sets with the class of sets ≤ s P -reducible to sparse sets. For most pairs of reducibilities ≤ r P and ≤ s P, it is shown that the two associated reduction classes are incomparable, unless a trivial inclusive relation holds.

STOC Conference 1988 Conference Paper

Relativized Polynominal Time Hierarchies Having Exactly K Levels

• Ker-I Ko

I&C Journal 1987 Journal Article

Identification of pattern languages from examples and queries

• Assaf Marron
• Ker-I Ko

Patterns are words over an alphabet of constants and variables. New words are created from a pattern as sstrings of constants are substituted for the variables of the pattern. In this paper we investigate the inductive inference of patterns from positive data and quaries, from a complexity-theoretic point of view. Using results from combinatorics on words, we give simple but nontrivial sufficient conditions on the set of the initial examples that guarantee the identification of a unique pattern by making only polynomially many quaries. Counterexamples are also provided to show that the conditions are necessary.

TCS Journal 1987 Journal Article

On helping by robust oracle machines

• Ker-I Ko

The concept of helping by robust oracle Turing machines, introduced recently by Schöning, is extended to the notion of ‘one-sided helping’ and its relations to the structural properties of NP sets are investigated. Various results on who can help whom have been obtained on sets in BPP, in R, in UP and sparse sets. Sets which do not help any set are studied and two types of sets defined by structural properties are demonstrated to help no sets except those in P. Sest which help themselves are also studied and are shown to be related to self-reducible sets. Several previously known structural results on NP sets are reproved from the point of view of helping.

TCS Journal 1987 Journal Article

On the continued fraction representation of computable real numbers

• Ker-I Ko

STOC Conference 1986 Conference Paper

A Note on One-Way Functions and Polynomial-Time Isomorphisms (Extended Abstract)

• Ker-I Ko
• Timothy J. Long
• Ding-Zhu Du

TCS Journal 1986 Journal Article

On one-way functions and polynomial-time isomorphisms

• Ker-I Ko
• Timothy J. Long
• Ding-Zhu Du

It is shown that if one-way functions exist, then there are sets A and B such that A and B are equivalent under one-one and length-increasing polynomial-time reductions, and such that A is not polynomial-time isomorphic to B. Furthermore, sets A and B can be constructed such that they are polynomial-time truth-table complete for the class of exponential-time computable sets.

TCS Journal 1986 Journal Article

On the continued fraction representation of computable real numbers

• Ker-I Ko

The continued fraction representation of real numbers is compared with other types of representations of real numbers in the context of recursive analysis. The main result states that a modification of the natural continued fraction representation, based on the concept of principal convergents of real numbers, is polynomially equivalent to the left cut representation in the sense that, for any given real number x, the two representations of x are computable from each other in polynomial time. Following from earlier studies on the left cut representation of real numbers, this result verifies the intuition that there is no efficient algorithm for implementing addition of real numbers in the continued fraction form. On the other hand, when considering computable real functions, the continued fraction representation behaves differently from the left cut representation: a computable real function must be continuous if it is defined as a mapping on Cauchy sequences of real numbers; it must be left-continuous, but is not necessarily continuous, if defined as a mapping on left cuts; and it ist necessarily left- or right-continuous if defined as a mapping on continued fractions.

TCS Journal 1986 Journal Article

On the notion of infinite pseudorandom sequences

• Ker-I Ko

Three definitions of infinite pseudorandom sequences, with respect to polynomial time and space complexity, are introduced and compared with each other. It is shown that the first two definitions, based on Martin-Löf's notion of sequential tests and Levin and Schnorr's notion of monotonic operator complexity, are equivalent with respect to polynomial space complexity, while both are strictly stronger than the third definition, which is derived from Von Mises's notion of collectives.

TCS Journal 1985 Journal Article

On some natural complete operators

• Ker-I Ko

An operator is a mapping from integer functions to integer functions. It is known, from a result by Baker, Gill and Solovay (1975), that there exists an operator computable in polynomial time by a nondeterministic oracle Turing machine (called an NP operator) but not computable in polynomial time by any deterministic oracle Turing machine. We investigate several natural operators which share similar properties. We use the concept of completeness to give a precise classification of the complexity of these operators. For example, the question of finding maximum values of polynomial-time computable functions can be formulated as an operator complete for the class of NP operators.

TCS Journal 1984 Journal Article

Reducibilities on real numbers

• Ker-I Ko

The concept of reducibility in recursive function theory and computational complexity theory is applied to real numbers to investigate the notion of relative computability and relative complexity of real numbers. Several common types of reducibility such as Turing, truth-table and many-one reducibilities are considered. We also consider reducibilities defined by various sub-classes of recursive real functions. Some equivalence results among these reducibilities are obtained: The reducibility defined by recursive real functions is equivalent to the generalized truth-table redicibility; and the reducibility defined by recursive increasing real functions is equivalent to the generalized many-one reducibility. Similar equivalence results on polynomial time reducibilities are also proved. Different reducibilities are distinguished.