78 Search Results for "Liu-Zhang, Chen-Da"

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.18
Distance Queries over Dynamic Interval Graphs

Authors: Jingbang Chen, Meng He, J. Ian Munro, Richard Peng, Kaiyu Wu, and Daniel J. Zhang

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
We design the first dynamic distance oracles for interval graphs, which are intersection graphs of a set of intervals on the real line, and for proper interval graphs, which are intersection graphs of a set of intervals in which no interval is properly contained in another. For proper interval graphs, we design a linear space data structure which supports distance queries (computing the distance between two query vertices) and vertex insertion or deletion in O(lg n) worst-case time, where n is the number of vertices currently in G. Under incremental (insertion only) or decremental (deletion only) settings, we design linear space data structures that support distance queries in O(lg n) worst-case time and vertex insertion or deletion in O(lg n) amortized time, where n is the maximum number of vertices in the graph. Under fully dynamic settings, we design a data structure that represents an interval graph G in O(n) words of space to support distance queries in O(n lg n/S(n)) worst-case time and vertex insertion or deletion in O(S(n)+lg n) worst-case time, where n is the number of vertices currently in G and S(n) is an arbitrary function that satisfies S(n) = Ω(1) and S(n) = O(n). This implies an O(n)-word solution with O(√{nlg n})-time support for both distance queries and updates. All four data structures can answer shortest path queries by reporting the vertices in the shortest path between two query vertices in O(lg n) worst-case time per vertex. We also study the hardness of supporting distance queries under updates over an intersection graph of 3D axis-aligned line segments, which generalizes our problem to 3D. Finally, we solve the problem of computing the diameter of a dynamic connected interval graph.
Cite as

Jingbang Chen, Meng He, J. Ian Munro, Richard Peng, Kaiyu Wu, and Daniel J. Zhang. Distance Queries over Dynamic Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 18:1-18:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2023.18,
  author =	{Chen, Jingbang and He, Meng and Munro, J. Ian and Peng, Richard and Wu, Kaiyu and Zhang, Daniel J.},
  title =	{{Distance Queries over Dynamic Interval Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.18},
  URN =		{urn:nbn:de:0030-drops-193207},
  doi =		{10.4230/LIPIcs.ISAAC.2023.18},
  annote =	{Keywords: interval graph, proper interval graph, intersection graph, geometric intersection graph, distance oracle, distance query, shortest path query, dynamic graph}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.10
Communication Lower Bounds for Cryptographic Broadcast Protocols

Authors: Erica Blum, Elette Boyle, Ran Cohen, and Chen-Da Liu-Zhang

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
Broadcast protocols enable a set of n parties to agree on the input of a designated sender, even in the face of malicious parties who collude to attack the protocol. In the honest-majority setting, a fruitful line of work harnessed randomization and cryptography to achieve low-communication broadcast protocols with sub-quadratic total communication and with "balanced" sub-linear communication cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on the protocol of Dolev and Strong (SICOMP '83), and sub-quadratic broadcast has not been achieved even using randomization and cryptography. On the other hand, the only nontrivial ω(n) communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform "after the fact" removal of messages. We provide communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple protocol showing near tightness of our first bound. - Static adversary. We demonstrate a tradeoff between resiliency and communication for randomized protocols secure against n-o(n) static corruptions. For example, Ω(n⋅ polylog(n)) messages are needed when the number of honest parties is n/polylog(n); Ω(n√n) messages are needed for O(√n) honest parties; and Ω(n²) messages are needed for O(1) honest parties. Complementarily, we demonstrate broadcast with O(n⋅polylog(n)) total communication and balanced polylog(n) per-party cost, facing any constant fraction of static corruptions. - Weakly adaptive adversary. Our second bound considers n/2 + k corruptions and a weakly adaptive adversary that cannot remove messages "after the fact." We show that any broadcast protocol within this setting can be attacked to force an arbitrary party to send messages to k other parties. Our bound implies limitations on the feasibility of balanced low-communication protocols: For example, ruling out broadcast facing 51% corruptions, in which all non-sender parties have sublinear communication locality.
Cite as

Erica Blum, Elette Boyle, Ran Cohen, and Chen-Da Liu-Zhang. Communication Lower Bounds for Cryptographic Broadcast Protocols. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 10:1-10:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{blum_et_al:LIPIcs.DISC.2023.10,
  author =	{Blum, Erica and Boyle, Elette and Cohen, Ran and Liu-Zhang, Chen-Da},
  title =	{{Communication Lower Bounds for Cryptographic Broadcast Protocols}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.10},
  URN =		{urn:nbn:de:0030-drops-191361},
  doi =		{10.4230/LIPIcs.DISC.2023.10},
  annote =	{Keywords: broadcast, communication complexity, lower bounds, dishonest majority}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.94
Digital Injustice: A Case Study of Land Use Classification Using Multisource Data in Nairobi, Kenya (Short Paper)

Authors: Wenlan Zhang, Chen Zhong, and Faith Taylor

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
The utilisation of big data has emerged as a critical instrument for land use classification and decision-making processes due to its high spatiotemporal accuracy and ability to diminish manual data collection. However, the reliability and feasibility of big data are still controversial, the most important of which is whether it can represent the whole population with justice. The present study incorporates multiple data sources to facilitate land use classification while proving the existence of data bias caused digital injustice. Using Nairobi, Kenya, as a case study and employing a random forest classifier as a benchmark, this research combines satellite imagery, night-time light images, building footprint, Twitter posts, and street view images. The findings of the land use classification also disclose the presence of data bias resulting from the inadequate coverage of social media and street view data, potentially contributing to injustice in big data-informed decision-making. Strategies to mitigate such digital injustice situations are briefly discussed here, and more in-depth exploration remains for future work.
Cite as

Wenlan Zhang, Chen Zhong, and Faith Taylor. Digital Injustice: A Case Study of Land Use Classification Using Multisource Data in Nairobi, Kenya (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 94:1-94:6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.GIScience.2023.94,
  author =	{Zhang, Wenlan and Zhong, Chen and Taylor, Faith},
  title =	{{Digital Injustice: A Case Study of Land Use Classification Using Multisource Data in Nairobi, Kenya}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{94:1--94:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.94},
  URN =		{urn:nbn:de:0030-drops-189899},
  doi =		{10.4230/LIPIcs.GIScience.2023.94},
  annote =	{Keywords: Data bias, Digital injustice, Multi-source sensor data, Land use classification, Random forest classifier}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.33
Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees

Authors: Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, and Eric Vigoda

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
We study the mixing time of the single-site update Markov chain, known as the Glauber dynamics, for generating a random independent set of a tree. Our focus is obtaining optimal convergence results for arbitrary trees. We consider the more general problem of sampling from the Gibbs distribution in the hard-core model where independent sets are weighted by a parameter λ > 0; the special case λ = 1 corresponds to the uniform distribution over all independent sets. Previous work of Martinelli, Sinclair and Weitz (2004) obtained optimal mixing time bounds for the complete Δ-regular tree for all λ. However, Restrepo et al. (2014) showed that for sufficiently large λ there are bounded-degree trees where optimal mixing does not hold. Recent work of Eppstein and Frishberg (2022) proved a polynomial mixing time bound for the Glauber dynamics for arbitrary trees, and more generally for graphs of bounded tree-width. We establish an optimal bound on the relaxation time (i.e., inverse spectral gap) of O(n) for the Glauber dynamics for unweighted independent sets on arbitrary trees. Moreover, for λ ≤ .44 we prove an optimal mixing time bound of O(n log n). We stress that our results hold for arbitrary trees and there is no dependence on the maximum degree Δ. Interestingly, our results extend (far) beyond the uniqueness threshold which is on the order λ = O(1/Δ). Our proof approach is inspired by recent work on spectral independence. In fact, we prove that spectral independence holds with a constant independent of the maximum degree for any tree, but this does not imply mixing for general trees as the optimal mixing results of Chen, Liu, and Vigoda (2021) only apply for bounded degree graphs. We instead utilize the combinatorial nature of independent sets to directly prove approximate tensorization of variance/entropy via a non-trivial inductive proof.
Cite as

Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, and Eric Vigoda. Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 33:1-33:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{efthymiou_et_al:LIPIcs.APPROX/RANDOM.2023.33,
  author =	{Efthymiou, Charilaos and Hayes, Thomas P. and \v{S}tefankovi\v{c}, Daniel and Vigoda, Eric},
  title =	{{Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.33},
  URN =		{urn:nbn:de:0030-drops-188589},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.33},
  annote =	{Keywords: MCMC, Mixing Time, Independent Sets, Hard-Core Model, Approximate Counting Algorithms, Sampling Algorithms}
}
Document
DOI: 10.4230/LIPIcs.DNA.29.5
Revisiting Hybridization Kinetics with Improved Elementary Step Simulation

Authors: Jordan Lovrod, Boyan Beronov, Chenwei Zhang, Erik Winfree, and Anne Condon

Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)

Abstract
Nucleic acid strands, which react by forming and breaking Watson-Crick base pairs, can be designed to form complex nanoscale structures or devices. Controlling such systems requires accurate predictions of the reaction rate and of the folding pathways of interacting strands. Simulators such as Multistrand model these kinetic properties using continuous-time Markov chains (CTMCs), whose states and transitions correspond to secondary structures and elementary base pair changes, respectively. The transient dynamics of a CTMC are determined by a kinetic model, which assigns transition rates to pairs of states, and the rate of a reaction can be estimated using the mean first passage time (MFPT) of its CTMC. However, use of Multistrand is limited by its slow runtime, particularly on rare events, and the quality of its rate predictions is compromised by a poorly-calibrated and simplistic kinetic model. The former limitation can be addressed by constructing truncated CTMCs, which only include a small subset of states and transitions, selected either manually or through simulation. As a first step to address the latter limitation, Bayesian posterior inference in an Arrhenius-type kinetic model was performed in earlier work, using a small experimental dataset of DNA reaction rates and a fixed set of manually truncated CTMCs, which we refer to as Assumed Pathway (AP) state spaces. In this work we extend this approach, by introducing a new prior model that is directly motivated by the physical meaning of the parameters and that is compatible with experimental measurements of elementary rates, and by using a larger dataset of 1105 reactions as well as larger truncated state spaces obtained from the recently introduced stochastic Pathway Elaboration (PE) method. We assess the quality of the resulting posterior distribution over kinetic parameters, as well as the quality of the posterior reaction rates predicted using AP and PE state spaces. Finally, we use the newly parameterised PE state spaces and Multistrand simulations to investigate the strong variation of helix hybridization reaction rates in a dataset of Hata et al. While we find strong evidence for the nucleation-zippering model of hybridization, in the classical sense that the rate-limiting phase is composed of elementary steps reaching a small "nucleus" of critical stability, the strongly sequence-dependent structure of the trajectory ensemble up to nucleation appears to be much richer than assumed in the model by Hata et al. In particular, rather than being dominated by the collision probability of nucleation sites, the trajectory segment between first binding and nucleation tends to visit numerous secondary structures involving misnucleation and hairpins, and has a sizeable effect on the probability of overcoming the nucleation barrier.
Cite as

Jordan Lovrod, Boyan Beronov, Chenwei Zhang, Erik Winfree, and Anne Condon. Revisiting Hybridization Kinetics with Improved Elementary Step Simulation. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 5:1-5:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lovrod_et_al:LIPIcs.DNA.29.5,
  author =	{Lovrod, Jordan and Beronov, Boyan and Zhang, Chenwei and Winfree, Erik and Condon, Anne},
  title =	{{Revisiting Hybridization Kinetics with Improved Elementary Step Simulation}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-297-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{276},
  editor =	{Chen, Ho-Lin and Evans, Constantine G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.5},
  URN =		{urn:nbn:de:0030-drops-187889},
  doi =		{10.4230/LIPIcs.DNA.29.5},
  annote =	{Keywords: DNA reaction kinetics, kinetic model calibration, simulation-based Bayesian inference, continuous-time Markov chains}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.29
Effective Resistances in Non-Expander Graphs

Authors: Dongrun Cai, Xue Chen, and Pan Peng

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Effective resistances are ubiquitous in graph algorithms and network analysis. For an undirected graph G, its effective resistance R_G(s,t) between two vertices s and t is defined as the equivalent resistance between s and t if G is thought of as an electrical network with unit resistance on each edge. If we use L_G to denote the Laplacian matrix of G and L_G^† to denote its pseudo-inverse, we have R_G(s,t) = (𝟏_s-𝟏_t)^⊤ L^† (𝟏_s-𝟏_t) such that classical Laplacian solvers [Daniel A. Spielman and Shang{-}Hua Teng, 2014] provide almost-linear time algorithms to approximate R_G(s,t). In this work, we study sublinear time algorithms to approximate the effective resistance of an adjacent pair s and t. We consider the classical adjacency list model [Ron, 2019] for local algorithms. While recent works [Andoni et al., 2018; Peng et al., 2021; Li and Sachdeva, 2023] have provided sublinear time algorithms for expander graphs, we prove several lower bounds for general graphs of n vertices and m edges: 1) It needs Ω(n) queries to obtain 1.01-approximations of the effective resistance of an adjacent pair s and t, even for graphs of degree at most 3 except s and t. 2) For graphs of degree at most d and any parameter 𝓁, it needs Ω(m/𝓁) queries to obtain c ⋅ min{d,𝓁}-approximations where c > 0 is a universal constant. Moreover, we supplement the first lower bound by providing a sublinear time (1+ε)-approximation algorithm for graphs of degree 2 except the pair s and t. One of our technical ingredients is to bound the expansion of a graph in terms of the smallest non-trivial eigenvalue of its Laplacian matrix after removing edges. We discover a new lower bound on the eigenvalues of perturbed graphs (resp. perturbed matrices) by incorporating the effective resistance of the removed edge (resp. the leverage scores of the removed rows), which may be of independent interest.
Cite as

Dongrun Cai, Xue Chen, and Pan Peng. Effective Resistances in Non-Expander Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 29:1-29:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.ESA.2023.29,
  author =	{Cai, Dongrun and Chen, Xue and Peng, Pan},
  title =	{{Effective Resistances in Non-Expander Graphs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.29},
  URN =		{urn:nbn:de:0030-drops-186823},
  doi =		{10.4230/LIPIcs.ESA.2023.29},
  annote =	{Keywords: Sublinear Time Algorithm, Effective Resistance, Leverage Scores, Matrix Perturbation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.97
Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs

Authors: Enze Sun, Zonghan Yang, and Yuhao Zhang

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We consider the Online Rent Minimization problem, where online jobs with release times, deadlines, and processing times must be scheduled on machines that can be rented for a fixed length period of T. The objective is to minimize the number of machine rents. This problem generalizes the Online Machine Minimization problem where machines can be rented for an infinite period, and both problems have an asymptotically optimal competitive ratio of O(log(p_max/p_min)) for general processing times, where p_max and p_min are the maximum and minimum processing times respectively. However, for small values of p_max/p_min, a better competitive ratio can be achieved by assuming unit-size jobs. Under this assumption, Devanur et al. (2014) gave an optimal e-competitive algorithm for Online Machine Minimization, and Chen and Zhang (2022) gave a (3e+7) ≈ 15.16-competitive algorithm for Online Rent Minimization. In this paper, we significantly improve the competitive ratio of the Online Rent Minimization problem under unit size to 6, by using a clean oracle-based online algorithm framework.
Cite as

Enze Sun, Zonghan Yang, and Yuhao Zhang. Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 97:1-97:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{sun_et_al:LIPIcs.ESA.2023.97,
  author =	{Sun, Enze and Yang, Zonghan and Zhang, Yuhao},
  title =	{{Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{97:1--97:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.97},
  URN =		{urn:nbn:de:0030-drops-187500},
  doi =		{10.4230/LIPIcs.ESA.2023.97},
  annote =	{Keywords: Online Algorithm, Scheduling, Machine Minimization, Rent Minimization}
}
Document
Abstract
DOI: 10.4230/LIPIcs.WABI.2023.2
EMMA: Adding Sequences into a Constraint Alignment with High Accuracy and Scalability (Abstract)

Authors: Chengze Shen, Baqiao Liu, Kelly P. Williams, and Tandy Warnow

Published in: LIPIcs, Volume 273, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)

Abstract
Multiple sequence alignment (MSA) is a crucial precursor to many downstream biological analyses, such as phylogeny estimation [Morrison, 2006], RNA structure prediction [Shapiro et al., 2007], protein structure prediction [Jumper et al., 2021], etc. Obtaining an accurate MSA can be challenging, especially when the dataset is large (i.e., more than 1000 sequences). A key technique for large-scale MSA estimation is to add sequences into an existing alignment. For example, biological knowledge can be used to form a reference alignment on a subset of the sequences, and then the remaining sequences can be added to the reference alignment. Another case where adding sequences into an existing alignment occurs is when new sequences or genomes are added to databases, leading to the opportunity to add the new sequences for each gene in the genome into a growing alignment. A third case is for de novo multiple sequence alignment, where a subset of the sequences is selected and aligned, and then the remaining sequences are added into this "backbone alignment" [Nguyen et al., 2015; Park et al., 2023; Shen et al., 2022; Liu and Warnow, 2023; Park and Warnow, 2023; Yamada et al., 2016]. Thus, adding sequences into existing alignments is a natural problem with multiple applications to biological sequence analysis. A few methods have been developed to add sequences into an existing alignment, with MAFFT--add [Katoh and Frith, 2012] perhaps the most well-known. However, several multiple sequence alignment methods that operate in two steps (first extract and align the backbone sequences and then add the remaining sequences into this backbone alignment) also provide utilities for adding sequences into a user-provided alignment. We present EMMA, a new approach for adding "query" sequences into an existing "constraint" alignment. By construction, EMMA never changes the constraint alignment, except through the introduction of additional sites to represent homologies between the query sequences. EMMA uses a divide-and-conquer technique combined with MAFFT--add (using the most accurate setting, MAFFT-linsi--add) to add sequences into a user-provided alignment. We evaluate EMMA by comparing it to MAFFT-linsi--add, MAFFT--add (the default setting), and WITCH-ng-add. We include a range of biological and simulated datasets (nucleotides and proteins) ranging in size from 1000 to almost 200,000 sequences and evaluate alignment accuracy and scalability. MAFFT-linsi--add was the slowest and least scalable method, only able to run on datasets with at most 1000 sequences in this study, but had excellent accuracy (often the best) on those datasets. We also see that EMMA has better recall than WITCH-ng-add and MAFFT--add on large datasets, especially when the backbone alignment is small or clade-based.
Cite as

Chengze Shen, Baqiao Liu, Kelly P. Williams, and Tandy Warnow. EMMA: Adding Sequences into a Constraint Alignment with High Accuracy and Scalability (Abstract). In 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 273, pp. 2:1-2:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{shen_et_al:LIPIcs.WABI.2023.2,
  author =	{Shen, Chengze and Liu, Baqiao and Williams, Kelly P. and Warnow, Tandy},
  title =	{{EMMA: Adding Sequences into a Constraint Alignment with High Accuracy and Scalability}},
  booktitle =	{23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-294-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{273},
  editor =	{Belazzougui, Djamal and Ouangraoua, A\"{i}da},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.2},
  URN =		{urn:nbn:de:0030-drops-186285},
  doi =		{10.4230/LIPIcs.WABI.2023.2},
  annote =	{Keywords: Multiple sequence alignment, constraint alignment, MAFFT}
}
Document
Abstract
DOI: 10.4230/LIPIcs.WABI.2023.8
Quartets Enable Statistically Consistent Estimation of Cell Lineage Trees Under an Unbiased Error and Missingness Model (Abstract)

Authors: Yunheng Han and Erin K. Molloy

Published in: LIPIcs, Volume 273, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)

Abstract
Cancer progression and treatment can be informed by reconstructing its evolutionary history from tumor cells [Lim et al., 2020]. Although many methods exist to estimate evolutionary trees (called phylogenies) from molecular sequences, traditional approaches assume the input data are error-free and the output tree is fully resolved. These assumptions are challenged in tumor phylogenetics because single-cell sequencing produces sparse, error-ridden data and because tumors evolve clonally [Jahn et al., 2016; Schwartz and Schäffer, 2017]. Here, we study the theoretical utility of methods based on quartets (four-leaf, unrooted phylogenetic trees) and triplets (three-leaf, rooted phylogenetic trees), in light of these barriers. Quartets and triplets have long been used as the building blocks for reconstructing the evolutionary history of species [Wilkinson et al., 2005]. The reason triplet-based methods (e.g., MP-EST [Liu et al., 2010]) and quartet-based methods (e.g., ASTRAL [Mirarab et al., 2014]) have garnered such success in species phylogenetics is their good statistical properties under the Multi-Species Coalescent (MSC) model [Pamilo and Nei, 1988; Rannala and Yang, 2003]; see Allman et al. (2011) and Degnan (2006) for identifiability results under the MSC model for quartets and triplets, respectively. Inspired by these efforts, we study the utility of quartets and triplets for estimating cell lineage trees under a popular tumor phylogenetics model [Jahn et al., 2016; Ross and Markowetz, 2016; Wu, 2019; Kizilkale et al., 2022] with two phases. First, mutations arise on a (highly unresolved) cell lineage tree according to the infinite sites model, and second, errors (false positives and false negatives) and missing values are introduced to the resulting mutation data in an unbiased fashion, mimicking data produced by single-cell sequencing protocols. This infinite sites plus unbiased error and missingness (IS+UEM) model generates mutations (rather than gene genealogies like the MSC model). However, a quartet (with leaves bijectively labeled by four cells) is implied by a mutation being present in two cells and absent from two cells [Molloy et al., 2021; Springer et al., 2019]; similarly, a triplet (on three cells) is implied by a mutation being present in two cells and absent from one cell. Our main result is that under the IS+UEM, the most probable quartet identifies the unrooted model cell lineage tree on four cells, with a mild assumption: the probability of false negatives and the probability of false positives must not sum to one. Somewhat surprisingly, our identifiability result for quartets does not extend to triplets, with more restrictive assumptions being required for identifiability. These results motivate seeking an unrooted cell lineage tree such that the number of quartets shared between it and the input mutations is maximized. We prove an optimal solution to this problem is a consistent estimator of the unrooted cell lineage tree under the IS+UEM model; this guarantee includes the case where the model tree is highly unresolved, provided that tree error is defined as the number of false negative branches. We therefore conclude by outlining how quartet-based methods might be employed for tumor phylogenetics given other important challenges like copy number aberrations and doublets.
Cite as

Yunheng Han and Erin K. Molloy. Quartets Enable Statistically Consistent Estimation of Cell Lineage Trees Under an Unbiased Error and Missingness Model (Abstract). In 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 273, pp. 8:1-8:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{han_et_al:LIPIcs.WABI.2023.8,
  author =	{Han, Yunheng and Molloy, Erin K.},
  title =	{{Quartets Enable Statistically Consistent Estimation of Cell Lineage Trees Under an Unbiased Error and Missingness Model}},
  booktitle =	{23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)},
  pages =	{8:1--8:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-294-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{273},
  editor =	{Belazzougui, Djamal and Ouangraoua, A\"{i}da},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.8},
  URN =		{urn:nbn:de:0030-drops-186347},
  doi =		{10.4230/LIPIcs.WABI.2023.8},
  annote =	{Keywords: Tumor Phylogenetics, Cell Lineage Trees, Quartets, Supertrees, ASTRAL}
}
Document
DOI: 10.4230/LIPIcs.ITC.2023.6
Asymmetric Multi-Party Computation

Authors: Vipul Goyal, Chen-Da Liu-Zhang, and Rafail Ostrovsky

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

Abstract
Current protocols for Multi-Party Computation (MPC) consider the setting where all parties have access to similar resources. For example, all parties have access to channels bounded by the same worst-case delay upper bound Δ, and all channels have the same cost of communication. As a consequence, the overall protocol performance (resp. the communication cost) may be heavily affected by the slowest (resp. the most expensive) channel, even when most channels are fast (resp. cheap). Given the state of affairs, we initiate a systematic study of asymmetric MPC. In asymmetric MPC, the parties are divided into two categories: fast and slow parties, depending on whether they have access to high-end or low-end resources. We investigate two different models. In the first, we consider asymmetric communication delays: Fast parties are connected via channels with small delay δ among themselves, while channels connected to (at least) one slow party have a large delay Δ ≫ δ. In the second model, we consider asymmetric communication costs: Fast parties benefit from channels with cheap communication, while channels connected to a slow party have an expensive communication. We provide a wide range of positive and negative results exploring the trade-offs between the achievable number of tolerated corruptions t and slow parties s, versus the round complexity and communication cost in each of the models. Among others, we achieve the following results. In the model with asymmetric communication delays, focusing on the information-theoretic (i-t) setting: - An i-t asymmetric MPC protocol with security with abort as long as t+s < n and t < n/2, in a constant number of slow rounds. - We show that achieving an i-t asymmetric MPC protocol for t+s = n and with number of slow rounds independent of the circuit size implies an i-t synchronous MPC protocol with round complexity independent of the circuit size, which is a major problem in the field of round-complexity of MPC. - We identify a new primitive, asymmetric broadcast, that allows to consistently distribute a value among the fast parties, and at a later time the same value to slow parties. We completely characterize the feasibility of asymmetric broadcast by showing that it is possible if and only if 2t + s < n. - An i-t asymmetric MPC protocol with guaranteed output delivery as long as t+s < n and t < n/2, in a number of slow rounds independent of the circuit size. In the model with asymmetric communication cost, we achieve an asymmetric MPC protocol for security with abort for t+s < n and t < n/2, based on one-way functions (OWF). The protocol communicates a number of bits over expensive channels that is independent of the circuit size. We conjecture that assuming OWF is needed and further provide a partial result in this direction.
Cite as

Vipul Goyal, Chen-Da Liu-Zhang, and Rafail Ostrovsky. Asymmetric Multi-Party Computation. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 6:1-6:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{goyal_et_al:LIPIcs.ITC.2023.6,
  author =	{Goyal, Vipul and Liu-Zhang, Chen-Da and Ostrovsky, Rafail},
  title =	{{Asymmetric Multi-Party Computation}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{6:1--6:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.6},
  URN =		{urn:nbn:de:0030-drops-183342},
  doi =		{10.4230/LIPIcs.ITC.2023.6},
  annote =	{Keywords: multiparty computation, asymmetric, delays, communication}
}
Document
DOI: 10.4230/LIPIcs.SEA.2023.2
Fast Reachability Using DAG Decomposition

Authors: Giorgos Kritikakis and Ioannis G. Tollis

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
We present a fast and practical algorithm to compute the transitive closure (TC) of a directed graph. It is based on computing a reachability indexing scheme of a directed acyclic graph (DAG), G = (V, E). Given any path/chain decomposition of G we show how to compute in parameterized linear time such a reachability scheme that can answer reachability queries in constant time. The experimental results reveal that our method is significantly faster in practice than the theoretical bounds imply, indicating that path/chain decomposition algorithms can be applied to obtain fast and practical solutions to the transitive closure (TC) problem. Furthermore, we show that the number of non-transitive edges of a DAG G is ≤ width*|V| and that we can find a substantially large subset of the transitive edges of G in linear time using a path/chain decomposition. Our extensive experimental results show the interplay between these concepts in various models of DAGs.
Cite as

Giorgos Kritikakis and Ioannis G. Tollis. Fast Reachability Using DAG Decomposition. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 2:1-2:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kritikakis_et_al:LIPIcs.SEA.2023.2,
  author =	{Kritikakis, Giorgos and Tollis, Ioannis G.},
  title =	{{Fast Reachability Using DAG Decomposition}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.2},
  URN =		{urn:nbn:de:0030-drops-183526},
  doi =		{10.4230/LIPIcs.SEA.2023.2},
  annote =	{Keywords: graph algorithms, hierarchy, directed acyclic graphs (DAG), path/chain decomposition, transitive closure, transitive reduction, reachability, reachability indexing scheme}
}
Document
DOI: 10.4230/LIPIcs.SEA.2023.8
Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors

Authors: Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
We provide and study several algorithms for sorting an array of n comparable distinct elements subject to probabilistic comparison errors. In this model, the comparison of two elements returns the wrong answer according to a fixed probability, p_e < 1/2, and otherwise returns the correct answer. The dislocation of an element is the distance between its position in a given (current or output) array and its position in a sorted array. There are various algorithms that can be utilized for sorting or near-sorting elements subject to probabilistic comparison errors, but these algorithms are not data oblivious because they all make heavy use of noisy binary searching. In this paper, we provide new methods for sorting with comparison errors that are data oblivious while avoiding the use of noisy binary search methods. In addition, we experimentally compare our algorithms and other sorting algorithms.
Cite as

Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel. Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 8:1-8:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{afshar_et_al:LIPIcs.SEA.2023.8,
  author =	{Afshar, Ramtin and Dillencourt, Michael and Goodrich, Michael T. and Ozel, Evrim},
  title =	{{Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.8},
  URN =		{urn:nbn:de:0030-drops-183585},
  doi =		{10.4230/LIPIcs.SEA.2023.8},
  annote =	{Keywords: sorting, algorithms, randomization, experimentation}
}
Document
DOI: 10.4230/LIPIcs.SEA.2023.10
Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover

Authors: Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
In the Directed Feedback Vertex Set (DFVS) problem, one is given a directed graph G = (V,E) and wants to find a minimum cardinality set S ⊆ V such that G-S is acyclic. DFVS is a fundamental problem in computer science and finds applications in areas such as deadlock detection. The problem was the subject of the 2022 PACE coding challenge. We develop a novel exact algorithm for the problem that is tailored to perform well on instances that are mostly bi-directed. For such instances, we adapt techniques from the well-researched vertex cover problem. Our core idea is an iterative reduction to vertex cover. To this end, we also develop a new reduction rule that reduces the number of not bi-directed edges. With the resulting algorithm, we were able to win third place in the exact track of the PACE challenge. We perform computational experiments and compare the running time to other exact algorithms, in particular to the winning algorithm in PACE. Our experiments show that we outpace the other algorithms on instances that have a low density of uni-directed edges.
Cite as

Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt. Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 10:1-10:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{angrick_et_al:LIPIcs.SEA.2023.10,
  author =	{Angrick, Sebastian and Bals, Ben and Casel, Katrin and Cohen, Sarel and Friedrich, Tobias and Hastrich, Niko and Hradilak, Theresa and Issac, Davis and Ki{\ss}ig, Otto and Schmidt, Jonas and Wendt, Leo},
  title =	{{Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.10},
  URN =		{urn:nbn:de:0030-drops-183602},
  doi =		{10.4230/LIPIcs.SEA.2023.10},
  annote =	{Keywords: directed feedback vertex set, vertex cover, reduction rules}
}
Document
DOI: 10.4230/LIPIcs.TQC.2023.4
Computational Quantum Secret Sharing

Authors: Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang, and João Ribeiro

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties in such a way that certain authorized subsets can reconstruct the secret, while unauthorized subsets obtain no information about it. Previous works on QSS for general access structures focused solely on the existence of perfectly secure schemes, and the share size of the known schemes is necessarily exponential even in cases where the access structure is computed by polynomial size monotone circuits. This stands in stark contrast to the classical setting, where polynomial-time computationally-secure secret sharing schemes have been long known for all access structures computed by polynomial-size monotone circuits under standard hardness assumptions, and one can even obtain shares which are much shorter than the secret (which is impossible with perfect security). While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of n-party access structures to 1.5^{n+o(n)}, improving upon best known schemes and matching the best known result for general access structures in the classical setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in 𝖯 and NP.
Cite as

Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang, and João Ribeiro. Computational Quantum Secret Sharing. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 4:1-4:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cakan_et_al:LIPIcs.TQC.2023.4,
  author =	{\c{C}akan, Alper and Goyal, Vipul and Liu-Zhang, Chen-Da and Ribeiro, Jo\~{a}o},
  title =	{{Computational Quantum Secret Sharing}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{4:1--4:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.4},
  URN =		{urn:nbn:de:0030-drops-183144},
  doi =		{10.4230/LIPIcs.TQC.2023.4},
  annote =	{Keywords: Quantum secret sharing, quantum cryptography}
}
Document
DOI: 10.4230/LIPIcs.TQC.2023.11
On the Power of Nonstandard Quantum Oracles

Authors: Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
We study how the choices made when designing an oracle affect the complexity of quantum property testing problems defined relative to this oracle. We encode a regular graph of even degree as an invertible function f, and present f in different oracle models. We first give a one-query QMA protocol to test if a graph encoded in f has a small disconnected subset. We then use representation theory to show that no classical witness can help a quantum verifier efficiently decide this problem relative to an in-place oracle. Perhaps surprisingly, a simple modification to the standard oracle prevents a quantum verifier from efficiently deciding this problem, even with access to an unbounded witness.
Cite as

Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. On the Power of Nonstandard Quantum Oracles. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 11:1-11:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bassirian_et_al:LIPIcs.TQC.2023.11,
  author =	{Bassirian, Roozbeh and Fefferman, Bill and Marwaha, Kunal},
  title =	{{On the Power of Nonstandard Quantum Oracles}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{11:1--11:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.11},
  URN =		{urn:nbn:de:0030-drops-183215},
  doi =		{10.4230/LIPIcs.TQC.2023.11},
  annote =	{Keywords: quantum complexity, QCMA, expander graphs, representation theory}
}
  • Refine by Author
  • 9 Liu-Zhang, Chen-Da
  • 4 Chen, Lin
  • 4 Zhang, Guochuan
  • 4 Zheng, Da Wei
  • 3 Goyal, Vipul
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Design and analysis of algorithms
  • 5 Computer systems organization → Real-time systems
  • 5 Security and privacy → Cryptography
  • 5 Theory of computation → Approximation algorithms analysis
  • 5 Theory of computation → Cryptographic protocols
  • Show More...

  • Refine by Keyword
  • 5 broadcast
  • 3 local search
  • 3 partial broadcast
  • 3 scheduling
  • 2 Coding theory
  • Show More...

  • Refine by Type
  • 78 document

  • Refine by Publication Year
  • 23 2023
  • 14 2022
  • 9 2021
  • 6 2017
  • 6 2018
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact