Search for: All records

While graphs and abstract data structures can be large and complex, practical instances are often regular or highly structured. If the instance has sufficient structure, we might hope to compress the object into a more succinct representation. An efficient algorithm (with respect to the compressed input size) could then lead to more efficient computations than algorithms taking the explicit, uncompressed object as input. This leads to a natural question: when does knowing the input instance has a more succinct representation make computation easier? We initiate the study of the computational complexity of problems on factored graphs: graphs that are given as a formula of products and unions on smaller graphs. For any graph problem, we define a parameterized version that takes factored graphs as input, parameterized by the number of (smaller) ordinary graphs used to construct the factored graph. In this setting, we characterize the parameterized complexity of several natural graph problems, exhibiting a variety of complexities. We show that a decision version of lexicographically first maximal independent set is XP-complete, and therefore unconditionally not fixed-parameter tractable (FPT). On the other hand, we show that clique counting is FPT. Finally, we show that reachability is XNL-complete. Moreover, XNL is contained in FPT if and only if NL is contained in some fixed polynomial time. 

Algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worst-case bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update. We investigate three natural models of prediction: (1) δ-accurate predictions where each predicted request matches the true request with probability δ, (2) list-accurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by list-accurate, and δ-accurate. Further, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for list-accurate predictions that are equivalent to the non-prediction setting, unless list-accurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight. We note that concurrent work by v.d.Brand et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds. 

Uranium- and thorium-iridium multimetallic species with unprecedented actinide–iridium interactions are preparedviasalt-elimination reactions between U/Th halides and K[IrCp*H₃]. 

Alkylation of d - or l -phenylalanine or valine alkyl esters was carried out using methyl or phenyl Grignard reagents. Subsequent condensation with salicylaldehyde, 3,5-di- tert -butylsalicylaldehyde, or 5-fluorosalicylaldehyde formed tridentate, X 2 L type, Schiff base ligands. Chiral shift NMR confirmed retention of stereochemistry during synthesis. X-ray crystal structures of four of the ligands show either inter- or intramolecular hydrogen bonding interactions. The ligands coordinate to the titanium reagents Ti(NMe 2 ) 4 or TiCl(NMe 2 ) 3 by protonolysis and displacement of two equivalents of HNMe 2 . The crystal structure of one example of Ti(X 2 L)Cl(NMe 2 ) was determined and the complex has a distorted square pyramidal geometry with an axial NMe 2 ligand. The bis-dimethylamide complexes are active catalysts for the ring closing hydroamination of di- and trisubstituted aminoallenes. The reaction of hepta-4,5-dienylamine at 135 °C with 5 mol% catalyst gives a mixture of 6-ethyl-2,3,4,5-tetrahydropyridine (40–72%) and both Z - and E -2-propenyl-pyrrolidine (25–52%). The ring closing reaction of 6-methyl-hepta-4,5-dienylamine at 135 °C with 5 mol% catalyst gives exclusively 2-(2-methyl-propenyl)-pyrrolidine. The pyrrolidine products are obtained with enantiomeric excesses up to 17%.