17 citations · 41 across the 9 of their papers we have counts for
10 papers
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.…
The Complexity of the Comparator Circuit Value Problem
Stephen A. Cook, Yuval Filmus, Dai Tri Man Le
In 1990 Subramanian defined the complexity class CC as the set of problems log-space reducible to the comparator circuit value problem (CCV). He and Mayr showed that NL \subseteq C…
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…
Formalizing Randomized Matching Algorithms
Dai Tri Man Le, Stephen A. Cook
Using Jeřábek 's framework for probabilistic reasoning, we formalize the correctness of two fundamental RNC^2 algorithms for bipartite perfect matching within the theory VPV for po…
On Three Alternative Characterizations of Combined Traces
Dai Tri Man Le
The combined trace (i.e., comtrace) notion was introduced by Janicki and Koutny in 1995 as a generalization of the Mazurkiewicz trace notion. Comtraces are congruence classes of st…
A Characterization of Combined Traces Using Labeled Stratified Order Structures
Dai Tri Man Le
This paper defines a class of labeled stratified order structures that characterizes exactly the notion of combined traces (i.e., comtraces) proposed by Janicki and Koutny in 1995.…