10 citations · 15 across the 8 of their papers we have counts for
8 papers
Syntactic complexity of regular ideals
Janusz A. Brzozowski, Marek Szykuła, Yuli Ye
The state complexity of a regular language is the number of states in a minimal deterministic finite automaton accepting the language. The syntactic complexity of a regular languag…
Weakly Submodular Functions
Allan Borodin, Dai Tri Man Le, Yuli Ye
Submodular functions are well-studied in combinatorial optimization, game theory and economics. The natural diminishing returns property makes them suitable for many applications.…
Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates
Allan Borodin, Aadhar Jain, Hyun Chul Lee +1
Result diversification is an important aspect in web-based search, document summarization, facility location, portfolio management and other applications. Given a set of ranked res…
Efficient Sum-Based Hierarchical Smoothing Under \ell_1-Norm
Siavosh Benabbas, Hyun Chul Lee, Joel Oren +1
We introduce a new regression problem which we call the Sum-Based Hierarchical Smoothing problem. Given a directed acyclic graph and a non-negative value, called target value, for…
Complexity Classes and Theories for the Comparator Circuit Value Problem
Stephen A. Cook, Dai Tri Man Le, Yuli Ye
Subramanian defined the complexity class CC as the set of problems log-space reducible to the comparator circuit value problem. He proved that several other problems are complete f…
Syntactic Complexity of Prefix-, Suffix-, Bifix-, and Factor-Free Regular Languages
Janusz Brzozowski, Baiyu Li, Yuli Ye
The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maxima…
Syntactic Complexity of Ideal and Closed Languages
Janusz Brzozowski, Yuli Ye
The state complexity of a regular language is the number of states in the minimal deterministic automaton accepting the language. The syntactic complexity of a regular language is…
On the Complexity of the Evaluation of Transient Extensions of Boolean Functions
Janusz Brzozowski, Baiyu Li, Yuli Ye
Transient algebra is a multi-valued algebra for hazard detection in gate circuits. Sequences of alternating 0's and 1's, called transients, represent signal values, and gates are m…