Approximate agreement on graphs is t-resilient solvable in asynchronous systems if and only if the graph's clique complex is (t-1)-connected, with separations shown between agreement variants.
Bennett and Gilles Brassard
27 Pith papers cite this work, alongside 42 external citations. Polarity classification is still indexing.
27
Pith papers citing it
42
external citations · OpenAlex
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
Shuffle Product and Directed Bandwidth are XNLP-complete, settling open questions and implying parameterized hardness for scheduling with precedence delays.
A bisimulation-invariant synthesis framework for optimal predicate pushdown in fold-based UDFs produces correct transformations that speed up 150 real pipelines by 2.4x on average.
The Contiguous Art Gallery problem is solved in Θ(n log n) time in the real RAM model, improving the prior O(k n^5 log n) upper bound and proving an Ω(n log n) lower bound.
Dense network coding computes group operations over multiaccess networks with half the classical communication cost using shared entanglement plus quantum channels, and yields measurement-device-independent quantum key growing.
FeAVL achieves fully persistent dynamic LCE with O(log n) updates and equality, O(log n + log²ℓ) LCE w.h.p., and an AVL grammar version with O(g0 + I + U log n_max) permanent nodes.
Establishes tight n^{Theta(k^{d-1})} runtime bounds for d-Clique Packing parameterized by clique-width under ETH for fixed d >= 3.
Ancestor-based and anchored triples allow polynomial-time solutions to consistency problems in phylogenetic networks, with construction of realizing DAGs and networks.
New constructions intersect k NFAs in O(m n^{k-1}) transitions for fixed alphabet, enabling faster emptiness algorithms that are optimal unless (k+1)-clique detection admits a combinatorial breakthrough.
Bandit algorithms can be adapted to Tree MDPs by treating policies as arms with shared-data confidence bounds, achieving polynomial memory and instance-dependent bounds on sample complexity and regret that depend on terminal-state gaps rather than all policies.
Balanced Biclique Reconfiguration on bipartite graphs is PSPACE-complete, implying PSPACE-completeness for spanning subgraph reconfiguration of (i,j)-bicliques and for two-component connected-components reconfiguration under all token rules.
Oracle modalities are the least forcing a predicate, every modality is an oracle modality via adjoint retraction to containers, and sheaves are algebras for the monad of quotient-inductive computation trees.
First efficient sum-of-squares algorithms recover exact and approximate overlapping planted cliques in dense random intersection graphs for k ≫ √(n log n), with robustness to noise, monotone adversaries, and optimal edge corruptions.
Defines LCR problem on always-connected temporal graphs, gives DP algorithm, proves APX-hardness of shortest reconfiguration, and establishes equivalence to STSR.
A decomposition-based framework finds entire sets of irrelevant vertices in linear time on bounded-genus graphs, enabling linear-time algorithms for minor containment, disjoint paths, and deletion problems.
Scaling MLN weights by 1/n induces a weight-independent 0-1 law for FO logic; unscaled weights produce seven regimes with possible phase transitions and convergence laws.
An O(4^{k + k log k} n + n m^2)-time algorithm for TREE CONTAINMENT parameterized by scanwidth k of a given tree-extension, with a matching ETH lower bound of no 2^{o(c log c)} n^{O(1)} algorithm for directed cutwidth c even on binary inputs.
Non-Markovian policies from decomposed temporal logic value functions are proven optimal for nested Until, Globally, and Globally-Until specifications and extend Q-function safety filters to complex tasks.
Introduces a single-number performance measure, file-based benchmarking, and efficient text-file storage to evaluate and compare stopping criteria for EMO algorithms.
In the dueling bandit setting, the (1+1) EA selects the Condorcet winner with only constant probability when its advantage is Ω(1/n), while a Max-Min Ant System EDA selects it with probability 1-Θ(p), and repeated duels improve the EA's performance.
f-smooth words equal factors of smooth words, and their complexity is Θ(n^{log(a+b)/log((a+b)/2)}) on even binary alphabets, with the lower bound for all binary alphabets.
Connectivity-preserving important separators can be enumerated in 2^{O(k log k)} time, yielding an FPT algorithm for Node Multiway Cut–Uncut that improves the previous 2^{O(k^2 log k)} dependence.
Deciding ffn(G) <= m is NP-hard, shortest strategies on complete binary trees have superpolynomial length, with almost sharp bounds for those trees and transfer of results to the Hunter and Rabbit game.
Derives query lower bounds matching lattice width for Tarski fixed point enumeration of isotone maps and gives poly-space algorithms for increasing/decreasing cases on lattices including binary relations.
citing papers explorer
-
Solvability of Approximate Agreement on Graphs and Simplicial Complexes
Approximate agreement on graphs is t-resilient solvable in asynchronous systems if and only if the graph's clique complex is (t-1)-connected, with separations shown between agreement variants.
-
The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
Shuffle Product and Directed Bandwidth are XNLP-complete, settling open questions and implying parameterized hardness for scheduling with precedence delays.
-
Optimal Predicate Pushdown Synthesis
A bisimulation-invariant synthesis framework for optimal predicate pushdown in fold-based UDFs produces correct transformations that speed up 150 real pipelines by 2.4x on average.
-
The Contiguous Art Gallery Problem is in {\Theta}(n log n)
The Contiguous Art Gallery problem is solved in Θ(n log n) time in the real RAM model, improving the prior O(k n^5 log n) upper bound and proving an Ω(n log n) lower bound.
-
Communication Advantages from Quantum Dense Network Coding
Dense network coding computes group operations over multiaccess networks with half the classical communication cost using shared entanglement plus quantum channels, and yields measurement-device-independent quantum key growing.
-
Fully Persistent Dynamic LCE via AVL Trees and AVL Grammars
FeAVL achieves fully persistent dynamic LCE with O(log n) updates and equality, O(log n + log²ℓ) LCE w.h.p., and an AVL grammar version with O(g0 + I + U log n_max) permanent nodes.
-
Tight bounds for clique-packing parameterized by clique-width
Establishes tight n^{Theta(k^{d-1})} runtime bounds for d-Clique Packing parameterized by clique-width under ETH for fixed d >= 3.
-
Novel Triple-Based Problems for the Construction of Phylogenetic Networks via Least Common Ancestors
Ancestor-based and anchored triples allow polynomial-time solutions to consistency problems in phylogenetic networks, with construction of realizing DAGs and networks.
-
Intersecting Dense Automata
New constructions intersect k NFAs in O(m n^{k-1}) transitions for fixed alphabet, enabling faster emptiness algorithms that are optimal unless (k+1)-clique detection admits a combinatorial breakthrough.
-
On-line Learning in Tree MDPs by Treating Policies as Bandit Arms
Bandit algorithms can be adapted to Tree MDPs by treating policies as arms with shared-data confidence bounds, achieving polynomial memory and instance-dependent bounds on sample complexity and regret that depend on terminal-state gaps rather than all policies.
-
Biclique Reconfiguration in Bipartite Graphs
Balanced Biclique Reconfiguration on bipartite graphs is PSPACE-complete, implying PSPACE-completeness for spanning subgraph reconfiguration of (i,j)-bicliques and for two-component connected-components reconfiguration under all token rules.
-
Sheaves as oracle computations
Oracle modalities are the least forcing a predicate, every modality is an oracle modality via adjoint retraction to containers, and sheaves are algebras for the monad of quotient-inductive computation trees.
-
Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
First efficient sum-of-squares algorithms recover exact and approximate overlapping planted cliques in dense random intersection graphs for k ≫ √(n log n), with robustness to noise, monotone adversaries, and optimal edge corruptions.
-
Temporal Graph Reconfiguration for Always-Connected Graphs
Defines LCR problem on always-connected temporal graphs, gives DP algorithm, proves APX-hardness of shortest reconfiguration, and establishes equivalence to STSR.
-
Finding irrelevant vertices in linear time on bounded-genus graphs
A decomposition-based framework finds entire sets of irrelevant vertices in linear time on bounded-genus graphs, enabling linear-time algorithms for minor containment, disjoint paths, and deletion problems.
-
Random coloured digraphs defined by a Markov logic network
Scaling MLN weights by 1/n induces a weight-independent 0-1 law for FO logic; unscaled weights produce seven regimes with possible phase transitions and convergence laws.
-
Tree Containment Parameterized by Scanwidth
An O(4^{k + k log k} n + n m^2)-time algorithm for TREE CONTAINMENT parameterized by scanwidth k of a given tree-extension, with a matching ETH lower bound of no 2^{o(c log c)} n^{O(1)} algorithm for directed cutwidth c even on binary inputs.
-
Value Functions for Temporal Logic: Optimal Policies and Safety Filters
Non-Markovian policies from decomposed temporal logic value functions are proven optimal for nested Until, Globally, and Globally-Until specifications and extend Q-function safety filters to complex tasks.
-
Benchmarking Stopping Criteria for Evolutionary Multi-objective Optimization
Introduces a single-number performance measure, file-based benchmarking, and efficient text-file storage to evaluate and compare stopping criteria for EMO algorithms.
-
Analysis of Search Heuristics in the Multi-Armed Bandit Setting
In the dueling bandit setting, the (1+1) EA selects the Condorcet winner with only constant probability when its advantage is Ω(1/n), while a Max-Min Ant System EDA selects it with probability 1-Θ(p), and repeated duels improve the EA's performance.
-
The complexity of smooth words over binary alphabets
f-smooth words equal factors of smooth words, and their complexity is Θ(n^{log(a+b)/log((a+b)/2)}) on even binary alphabets, with the lower bound for all binary alphabets.
-
Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
Connectivity-preserving important separators can be enumerated in 2^{O(k log k)} time, yielding an FPT algorithm for Node Multiway Cut–Uncut that improves the previous 2^{O(k^2 log k)} dependence.
-
Complexity of Firefighting on Graphs
Deciding ffn(G) <= m is NP-hard, shortest strategies on complete binary trees have superpolynomial length, with almost sharp bounds for those trees and transfer of results to the Hunter and Rabbit game.
-
On the enumeration of Tarski fixed points
Derives query lower bounds matching lattice width for Tarski fixed point enumeration of isotone maps and gives poly-space algorithms for increasing/decreasing cases on lattices including binary relations.
-
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
Shortest perfect-matching reconfiguration via single alternating cycles is NP-hard for planar and bipartite graphs but polynomial-time solvable for outerplanar graphs.
-
Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
A static data structure answers leaf-to-ancestor path-minimum queries in O(1) time after O(n log h) preprocessing using only comparison oracles.
-
Security of deterministic key distribution with higher-dimensional systems
Higher-dimensional two-way QKD protocols using mutually unbiased bases and Heisenberg-Weyl operators yield secret keys for stronger individual attacks and improved robustness to collective eavesdropping via entropic uncertainty relations.