4 Search Results for "Valiant, Leslie G"


Document
Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles

Authors: Samir Datta and Kishlaya Jaiswal

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


Abstract
We present a parallel algorithm for permanent mod 2^k of a matrix of univariate integer polynomials. It places the problem in ⨁L ⊆ NC². This extends the techniques of Valiant [Leslie G. Valiant, 1979], Braverman, Kulkarni and Roy [Mark Braverman et al., 2009] and Björklund and Husfeldt [Andreas Björklund and Thore Husfeldt, 2019] and yields a (randomized) parallel algorithm for shortest two disjoint paths improving upon the recent (randomized) polynomial time algorithm [Andreas Björklund and Thore Husfeldt, 2019]. We also recognize the disjoint paths problem as a special case of finding disjoint cycles, and present (randomized) parallel algorithms for finding a shortest cycle and shortest two disjoint cycles passing through any given fixed number of vertices or edges.

Cite as

Samir Datta and Kishlaya Jaiswal. Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.MFCS.2021.36,
  author =	{Datta, Samir and Jaiswal, Kishlaya},
  title =	{{Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{36:1--36:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.36},
  URN =		{urn:nbn:de:0030-drops-144763},
  doi =		{10.4230/LIPIcs.MFCS.2021.36},
  annote =	{Keywords: permanent mod powers of 2, parallel computation, graphs, shortest disjoint paths, shortest disjoint cycles}
}
Document
Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem

Authors: Kai-Min Chung and Han-Hsuan Lin

Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)


Abstract
The probably approximately correct (PAC) model [Leslie G. Valiant, 1984] is a well studied model in classical learning theory. Here, we generalize the PAC model from concepts of Boolean functions to quantum channels, introducing PAC model for learning quantum channels, and give two sample efficient algorithms that are analogous to the classical "Occam’s razor" result [Blumer et al., 1987]. The classical Occam’s razor algorithm is done trivially by excluding any concepts not compatible with the input-output pairs one gets, but such an approach is not immediately possible with a concept class of quantum channels, because the outputs are unknown quantum states from the quantum channel. To study the quantum state learning problem associated with PAC learning quantum channels, we focus on the special case where the channels all have constant output. In this special case, learning the channels reduce to a problem of learning quantum states that is similar to the well known quantum state discrimination problem [Joonwoo Bae and Leong-Chuan Kwek, 2017], but with the extra twist that we allow ε-trace-distance-error in the output. We call this problem Approximate State Discrimination, which we believe is a natural problem that is of independent interest. We give two algorithms for learning quantum channels in PAC model. The first algorithm has sample complexity O((log|C| + log(1/ δ))/(ε²)), but only works when the outputs are pure states, where C is the concept class, ε is the error of the output, and δ is the probability of failure of the algorithm. The second algorithm has sample complexity O((log³|C|(log|C|+log(1/ δ)))/(ε²)), and work for mixed state outputs. Some implications of our results are that we can PAC-learn a polynomial sized quantum circuit in polynomial samples, and approximate state discrimination can be solved in polynomial samples even when the size of the input set is exponential in the number of qubits, exponentially better than a naive state tomography.

Cite as

Kai-Min Chung and Han-Hsuan Lin. Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.TQC.2021.3,
  author =	{Chung, Kai-Min and Lin, Han-Hsuan},
  title =	{{Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{3:1--3:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.3},
  URN =		{urn:nbn:de:0030-drops-139984},
  doi =		{10.4230/LIPIcs.TQC.2021.3},
  annote =	{Keywords: PAC learning, Quantum PAC learning, Sample Complexity, Approximate State Discrimination, Quantum information}
}
Document
Counting Homomorphisms to Cactus Graphs Modulo 2

Authors: Andreas Göbel, Leslie Ann Goldberg, and David Richerby

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)


Abstract
A homomorphism from a graph G to a graph H is a function from V(G) to V(H) that preserves edges. Many combinatorial structures that arise in mathematics and computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this paper, we study the complexity of counting homomorphisms modulo 2. The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy but counting modulo 2 is intractable. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this case, the structure of the graph H has a big influence on the complexity of the problem. Thus, our approach is graph-theoretic. We give a complete solution for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. Cactus graphs arise in many applications such as the modelling of wireless sensor networks and the comparison of genomes. We show that, for some cactus graphs H, counting homomorphisms to H modulo 2 can be done in polynomial time. For every other fixed cactus graph H, the problem is complete for the complexity class +P which is a wide complexity class to which every problem in the polynomial hierarchy can be reduced (using randomised reductions). Determining which H lead to tractable problems can be done in polynomial time. Our result builds upon the work of Faben and Jerrum, who gave a dichotomy for the case in which H is a tree.

Cite as

Andreas Göbel, Leslie Ann Goldberg, and David Richerby. Counting Homomorphisms to Cactus Graphs Modulo 2. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 350-361, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{gobel_et_al:LIPIcs.STACS.2014.350,
  author =	{G\"{o}bel, Andreas and Goldberg, Leslie Ann and Richerby, David},
  title =	{{Counting Homomorphisms to Cactus Graphs Modulo 2}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{350--361},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.350},
  URN =		{urn:nbn:de:0030-drops-44700},
  doi =		{10.4230/LIPIcs.STACS.2014.350},
  annote =	{Keywords: modular counting, homomorphisms, cactus graph, graph algorithms}
}
Document
Knowledge Infusion: In Pursuit of Robustness in Artificial Intelligence

Authors: Leslie G Valiant

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)


Abstract
Endowing computers with the ability to apply commonsense knowledge with human-level performance is a primary challenge for computer science, comparable in importance to past great challenges in other fields of science such as the sequencing of the human genome. The right approach to this problem is still under debate. Here we shall discuss and attempt to justify one approach, that of {\it knowledge infusion}. This approach is based on the view that the fundamental objective that needs to be achieved is {\it robustness} in the following sense: a framework is needed in which a computer system can represent pieces of knowledge about the world, each piece having some uncertainty, and the interactions among the pieces having even more uncertainty, such that the system can nevertheless reason from these pieces so that the uncertainties in its conclusions are at least controlled. In knowledge infusion rules are learned from the world in a principled way so that subsequent reasoning using these rules will also be principled, and subject only to errors that can be bounded in terms of the inverse of the effort invested in the learning process.

Cite as

Leslie G Valiant. Knowledge Infusion: In Pursuit of Robustness in Artificial Intelligence. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 415-422, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{valiant:LIPIcs.FSTTCS.2008.1770,
  author =	{Valiant, Leslie G},
  title =	{{Knowledge Infusion: In Pursuit of Robustness in Artificial Intelligence}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{415--422},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1770},
  URN =		{urn:nbn:de:0030-drops-17703},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1770},
  annote =	{Keywords: Artificial intelligence, knowledge acquisition, knowledge representation,learning, reasoning, robustness}
}
  • Refine by Author
  • 1 Chung, Kai-Min
  • 1 Datta, Samir
  • 1 Goldberg, Leslie Ann
  • 1 Göbel, Andreas
  • 1 Jaiswal, Kishlaya
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Parallel algorithms
  • 1 Theory of computation → Quantum complexity theory
  • 1 Theory of computation → Quantum information theory

  • Refine by Keyword
  • 1 Approximate State Discrimination
  • 1 Artificial intelligence
  • 1 PAC learning
  • 1 Quantum PAC learning
  • 1 Quantum information
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2021
  • 1 2008
  • 1 2014

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