Search

Your search keyword '"Complexity class"' showing total 2,442 results
Start Over Descriptor "Complexity class"

Refine your results

more »

more »

more »
2,442 results on '"Complexity class"'

1. Completeness for the Complexity Class ∀∃R and Area-Universality.

Author

Dobbins, Michael Gene, Kleist, Linda, Miltzow, Tillmann, and Rzążewski, Paweł

Subjects
*ALGEBRA, *PLANAR graphs, *LOGICAL prediction, *POLYNOMIALS, *ANALOGY
Abstract

Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class ∃ R plays a crucial role in the study of geometric problems. Sometimes ∃ R is referred to as the 'real analog' of NP. While NP is a class of computational problems that deals with existentially quantified boolean variables, ∃ R deals with existentially quantified real variables. In analogy to Π 2 p and Σ 2 p in the famous polynomial hierarchy, we study the complexity classes ∀ ∃ R and ∃ ∀ R with real variables. Our main interest is the AreaUniversality problem, where we are given a plane graph G, and ask if for each assignment of areas to the inner faces of G, there exists a straight-line drawing of G realizing the assigned areas. We conjecture that AreaUniversality is ∀ ∃ R -complete and support this conjecture by proving ∃ R - and ∀ ∃ R -completeness of two variants of AreaUniversality. To this end, we introduce tools to prove ∀ ∃ R -hardness and membership. Finally, we present geometric problems as candidates for ∀ ∃ R -complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

2. A Protocol for Solutions to DP-Complete Problems through Tissue Membrane Systems.

Author

Orellana-Martín, David, Ramírez-de-Arellano, Antonio, Andreu-Guzmán, José Antonio, Romero-Jiménez, Álvaro, and Pérez-Jiménez, Mario J.

Subjects
*NP-complete problems, *FOREIGN language education, *TISSUES, *POLYNOMIAL time algorithms
Abstract

Considering a class  R  comprising recognizer membrane systems with the capability of providing polynomial-time and uniform solutions for NP-complete problems (referred to as a "presumably efficient" class), the corresponding polynomial-time complexity class PMC R  encompasses both the NP and  co - NP  classes. Specifically, when  R  represents the class of recognizer presumably efficient cell-like P systems that incorporate object evolution rules, communication rules, and dissolution rules, PMC R  includes both the DP and  co - DP  classes. Here, DP signifies the class of languages that can be expressed as the difference between any two languages in NP (it is worth noting that NP ⊆ DP and  co - NP ⊆ co - DP ). As DP-complete problems are believed to be more complex than NP-complete problems, they serve as promising candidates for studying the P vs. NP problem. This outcome has previously been established within the realm of recognizer P systems with active membranes. In this paper, we extend this result to encompass any class  R  of presumably efficient recognizer tissue-like membrane systems by presenting a detailed protocol for transforming solutions of NP-complete problems into solutions of DP-complete problems. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

3. ON THE COMPLEXITY OF ISOMORPHISM PROBLEMS FOR TENSORS, GROUPS, AND POLYNOMIALS I: TENSOR ISOMORPHISM-COMPLETENESS.

Author

GROCHOW, JOSHUA and QIAO, YOUMING

Subjects
*GROUP theory, *POLYNOMIALS, *POLYNOMIAL time algorithms, *CRYPTOGRAPHY, *MACHINE learning, *ISOMORPHISM (Mathematics)
Abstract

We study the complexity of isomorphism problems for tensors, groups, and polynomials. These problems have been studied in multivariate cryptography, machine learning, quantum information, and computational group theory. We show that these problems are all polynomial-time equivalent, creating bridges between problems traditionally studied in myriad research areas. This prompts us to define the complexity class \sansT \sansI, namely problems that reduce to the tensor isomorphism problem in polynomial time. Our main technical result is a polynomial-time reduction from d-tensor isomorphism to 3-tensor isomorphism. In the context of quantum information, this result gives a multipartite-to-tripartite entanglement transformation procedure that preserves equivalence under stochastic local operations and classical communication. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

4. Sequence Graphs Realizations and Ambiguity in Language Models

Author

Khalife, Sammy, Ponty, Yann, Bulteau, Laurent, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Chen, Chi-Yeh, editor, Hon, Wing-Kai, editor, Hung, Ling-Ju, editor, and Lee, Chia-Wei, editor

Published
2021
Full Text
View/download PDF

5. On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups

Author

Zhili Chen and Joshua A. Grochow and Youming Qiao and Gang Tang and Chuanqi Zhang, Chen, Zhili, Grochow, Joshua A., Qiao, Youming, Tang, Gang, Zhang, Chuanqi, Zhili Chen and Joshua A. Grochow and Youming Qiao and Gang Tang and Chuanqi Zhang, Chen, Zhili, Grochow, Joshua A., Qiao, Youming, Tang, Gang, and Zhang, Chuanqi

Abstract

We study the complexity of isomorphism problems for d-way arrays, or tensors, under natural actions by classical groups such as orthogonal, unitary, and symplectic groups. These problems arise naturally in statistical data analysis and quantum information. We study two types of complexity-theoretic questions. First, for a fixed action type (isomorphism, conjugacy, etc.), we relate the complexity of the isomorphism problem over a classical group to that over the general linear group. Second, for a fixed group type (orthogonal, unitary, or symplectic), we compare the complexity of the isomorphism problems for different actions. Our main results are as follows. First, for orthogonal and symplectic groups acting on 3-way arrays, the isomorphism problems reduce to the corresponding problems over the general linear group. Second, for orthogonal and unitary groups, the isomorphism problems of five natural actions on 3-way arrays are polynomial-time equivalent, and the d-tensor isomorphism problem reduces to the 3-tensor isomorphism problem for any fixed d > 3. For unitary groups, the preceding result implies that LOCC classification of tripartite quantum states is at least as difficult as LOCC classification of d-partite quantum states for any d. Lastly, we also show that the graph isomorphism problem reduces to the tensor isomorphism problem over orthogonal and unitary groups.

Published
2024
Full Text
View/download PDF

6. A Protocol for Solutions to DP-Complete Problems through Tissue Membrane Systems

Author

David Orellana-Martín, Antonio Ramírez-de-Arellano, José Antonio Andreu-Guzmán, Álvaro Romero-Jiménez, and Mario J. Pérez-Jiménez

Subjects
complexity class, DP, membrane computing, tissue P systems, Mathematics, QA1-939
Abstract

Considering a class R comprising recognizer membrane systems with the capability of providing polynomial-time and uniform solutions for NP-complete problems (referred to as a “presumably efficient” class), the corresponding polynomial-time complexity class PMCR encompasses both the NP and co-NP classes. Specifically, when R represents the class of recognizer presumably efficient cell-like P systems that incorporate object evolution rules, communication rules, and dissolution rules, PMCR includes both the DP and co-DP classes. Here, DP signifies the class of languages that can be expressed as the difference between any two languages in NP (it is worth noting that NP ⊆ DP and co-NP⊆co-DP). As DP-complete problems are believed to be more complex than NP-complete problems, they serve as promising candidates for studying the P vs. NP problem. This outcome has previously been established within the realm of recognizer P systems with active membranes. In this paper, we extend this result to encompass any class R of presumably efficient recognizer tissue-like membrane systems by presenting a detailed protocol for transforming solutions of NP-complete problems into solutions of DP-complete problems.

Published
2023
Full Text
View/download PDF

7. Introduction to Autoreducibility and Mitoticity

Author

Glaßer, Christian, Nguyen, Dung T., Selman, Alan L., Witek, Maximilian, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Day, Adam, editor, Fellows, Michael, editor, Greenberg, Noam, editor, Khoussainov, Bakhadyr, editor, Melnikov, Alexander, editor, and Rosamond, Frances, editor

Published
2017
Full Text
View/download PDF

8. The Complexity of Complexity

Author

Allender, Eric, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Day, Adam, editor, Fellows, Michael, editor, Greenberg, Noam, editor, Khoussainov, Bakhadyr, editor, Melnikov, Alexander, editor, and Rosamond, Frances, editor

Published
2017
Full Text
View/download PDF

9. Computing exact solutions of consensus halving and the Borsuk-Ulam theorem.

Author

Deligkas, Argyrios, Fearnley, John, Melissourgos, Themistoklis, and Spirakis, Paul G.

Subjects
*ARITHMETIC, *DECISION making
Abstract

We study the problem of finding an exact solution to the Consensus Halving problem. While recent work has shown that the approximate version of this problem is PPA -complete [29,30] , we show that the exact version is much harder. Specifically, finding a solution with n agents and n cuts is FIXP -hard, and deciding whether there exists a solution with fewer than n cuts is ETR -complete. Along the way, we define a new complexity class, called BU, which captures all problems that can be reduced to solving an instance of the Borsuk-Ulam problem exactly. We show that FIXP ⊆ BU ⊆ TFETR and that LinearBU = PPA , where LinearBU is the subclass of BU in which the Borsuk-Ulam instance is specified by a linear arithmetic circuit. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

12. Parameterized Complexity of Logic-based Argumentation in Schaefer's Framework

Author

Mahmood, Y., Meier, A., Schmidt, Johannes, Mahmood, Y., Meier, A., and Schmidt, Johannes

Abstract

Argumentation is a well-established formalism dealing with conflicting information by generating and comparing arguments. It has been playing a major role in AI for decades. In logic-based argumentation, we explore the internal structure of an argument. Informally, a set of formulas is the support for a given claim if it is consistent, subset-minimal, and implies the claim. In such a case, the pair of the support and the claim together is called an argument. In this article, we study the propositional variants of the following three computational tasks studied in argumentation: ARG (exists a support for a given claim with respect to a given set of formulas), ARG-Check (is a given set a support for a given claim), and ARG-Rel (similarly as ARG plus requiring an additionally given formula to be contained in the support). ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the polynomial hierarchy (Creignou et al. 2014 and Parson et al., 2003) and, accordingly, are highly intractable. Analyzing the reason for this intractability, we perform a two-dimensional classification: First, we consider all possible propositional fragments of the problem within Schaefer's framework (STOC 1978) and then study different parameterizations for each of the fragments. We identify a list of reasonable structural parameters (size of the claim, support, knowledge base) that are connected to the aforementioned decision problems. Eventually, we thoroughly draw a fine border of parameterized intractability for each of the problems showing where the problems are fixed-parameter tractable and when this exactly stops. Surprisingly, several cases are of very high intractability (para-NP and beyond).

Published
2023
Full Text
View/download PDF

13. A Protocol for Solutions to DP-Complete Problems through Tissue Membrane Systems

Author

Pérez-Jiménez, David Orellana-Martín, Antonio Ramírez-de-Arellano, José Antonio Andreu-Guzmán, Álvaro Romero-Jiménez, and Mario J.

Subjects
complexity class, DP, membrane computing, tissue P systems
Abstract

Considering a classRcomprising recognizer membrane systems with the capability of providing polynomial-time and uniform solutions for NP-complete problems (referred to as a “presumably efficient” class), the corresponding polynomial-time complexity class PMCRencompasses both the NP andco-NPclasses. Specifically, whenRrepresents the class of recognizer presumably efficient cell-like P systems that incorporate object evolution rules, communication rules, and dissolution rules, PMCRincludes both the DP andco-DPclasses. Here, DP signifies the class of languages that can be expressed as the difference between any two languages in NP (it is worth noting that NP ⊆ DP andco-NP⊆co-DP). As DP-complete problems are believed to be more complex than NP-complete problems, they serve as promising candidates for studying the P vs. NP problem. This outcome has previously been established within the realm of recognizer P systems with active membranes. In this paper, we extend this result to encompass any classRof presumably efficient recognizer tissue-like membrane systems by presenting a detailed protocol for transforming solutions of NP-complete problems into solutions of DP-complete problems.

Published
2023
Full Text
View/download PDF

14. On the Computational Complexity of MapReduce

Author

Fish, Benjamin, Kun, Jeremy, Lelkes, Ádám D., Reyzin, Lev, Turán, György, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Moses, Yoram, editor

Published
2015
Full Text
View/download PDF

15. Dual VP Classes

Author

Allender, Eric, Gál, Anna, Mertz, Ian, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Italiano, Giuseppe F., editor, Pighizzini, Giovanni, editor, and Sannella, Donald T., editor

Published
2015
Full Text
View/download PDF

16. Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2

Author

Salo, Ville, Törmä, Ilkka, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Isokawa, Teijiro, editor, Imai, Katsunobu, editor, Matsui, Nobuyuki, editor, Peper, Ferdinand, editor, and Umeo, Hiroshi, editor

Published
2015
Full Text
View/download PDF

17. Complexity Classes for Membrane Systems: A Survey

Author

Mauri, Giancarlo, Leporati, Alberto, Manzoni, Luca, Porreca, Antonio E., Zandron, Claudio, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Dediu, Adrian-Horia, editor, Formenti, Enrico, editor, Martín-Vide, Carlos, editor, and Truthe, Bianca, editor

Published
2015
Full Text
View/download PDF

18. Mechanized Proofs of Adversarial Complexity and Application to Universal Composability: Journal pre-print: full version

Author

Pierre-Yves Strub, Gilles Barthe, Adrien Koutsos, Benjamin Grégoire, Manuel Barbosa, Faculdade de Ciências da Universidade do Porto (FCUP), Universidade do Porto = University of Porto, Institute for Systems and Computer Engineering, Technology and Science [Porto] (INESC TEC), Max Planck Institute for Security and Privacy [Bochum] (MPI Security and Privacy), Institute IMDEA Software [Madrid], Sûreté du logiciel et Preuves Mathématiques Formalisées (STAMP), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Programming securely with cryptography (PROSECCO), Inria de Paris, École polytechnique (X), Universidade do Porto, Programming securely with cryptography (PROSECCO ), CRACS & Inesc TEC [Porto], Meta France, ANR-17-CE39-0004,TECAP,Analyse de protocoles - unir les outils existants(2017), and ANR-22-PECY-0006,SVP,Verification of Security Protocols(2022)

Subjects
Interactive Proof System, Theoretical computer science, General Computer Science, Computer science, Cryptography, Verification of Cryptographic Primitives, 0102 computer and information sciences, 02 engineering and technology, Hoare logic, Mathematical proof, 01 natural sciences, Formal Methods, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Universal composability, 0202 electrical engineering, electronic engineering, information engineering, Complexity class, [INFO]Computer Science [cs], Concrete security, Safety, Risk, Reliability and Quality, business.industry, Proof assistant, Interactive proof system, 020207 software engineering, Complexity Analysis, 010201 computation theory & mathematics, business
Abstract

International audience; In this paper we enhance the EasyCrypt proof assistant to reason about computational complexity of adversaries. The key technical tool is a Hoare logic for reasoning about computational complexity (execution time and oracle calls) of adversarial computations. Our Hoare logic is built on top of the module system used by EasyCrypt for modeling adversaries. We prove that our logic is sound w.r.t. the semantics of EasyCrypt programs-we also provide full semantics for the EasyCrypt module system, which was previously lacking. We showcase (for the first time in EasyCrypt and in other computer-aided cryptographic tools) how our approach can express precise relationships between the probability of adversarial success and their execution time. In particular, we can quantify existentially over adversaries in a complexity class, and express general composition statements in simulation-based frameworks. Moreover, such statements can be composed to derive standard concrete security bounds for cryptographic constructions whose security is proved in a modular way. As a main benefit of our approach, we revisit security proofs of some well-known cryptographic constructions and we present a new formalization of Universal Composability (UC).

Published
2023

19. Capturing Bisimulation-Invariant Complexity Classes with Higher-Order Modal Fixpoint Logic

Author

Lange, Martin, Lozes, Etienne, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Diaz, Josep, editor, Lanese, Ivan, editor, and Sangiorgi, Davide, editor

Published
2014
Full Text
View/download PDF

20. Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes

Author

Glaßer, Christian, Witek, Maximilian, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Csuhaj-Varjú, Erzsébet, editor, Dietzfelbinger, Martin, editor, and Ésik, Zoltán, editor

Published
2014
Full Text
View/download PDF

21. On the Complexity of Symbolic Verification and Decision Problems in Bit-Vector Logic

Author

Kovásznai, Gergely, Veith, Helmut, Fröhlich, Andreas, Biere, Armin, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Csuhaj-Varjú, Erzsébet, editor, Dietzfelbinger, Martin, editor, and Ésik, Zoltán, editor

Published
2014
Full Text
View/download PDF

22. Solving the ST-Connectivity Problem with Pure Membrane Computing Techniques

Author

Gazdag, Zsolt, Gutiérrez-Naranjo, Miguel A., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gheorghe, Marian, editor, Rozenberg, Grzegorz, editor, Salomaa, Arto, editor, Sosík, Petr, editor, and Zandron, Claudio, editor

Published
2014
Full Text
View/download PDF

23. Positive and Negative Proofs for Circuits and Branching Programs

Author

Dorzweiler, Olga, Flamm, Thomas, Krebs, Andreas, Ludwig, Michael, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Jürgensen, Helmut, editor, Karhumäki, Juhani, editor, and Okhotin, Alexander, editor

Published
2014
Full Text
View/download PDF

24. On the Complexity of L-reachability

Author

Komarath, Balagopal, Sarma, Jayalal, Sunil, K. S., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Jürgensen, Helmut, editor, Karhumäki, Juhani, editor, and Okhotin, Alexander, editor

Published
2014
Full Text
View/download PDF

25. Dynamic Complexity of Planar 3-Connected Graph Isomorphism

Author

Mehta, Jenish C., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Hirsch, Edward A., editor, Kuznetsov, Sergei O., editor, Pin, Jean-Éric, editor, and Vereshchagin, Nikolay K., editor

Published
2014
Full Text
View/download PDF

26. Searching for Traces of Communication in Szilard Languages of Parallel Communicating Grammar Systems - Complexity Views

Author

Cojocaru, Liliana, Mäkinen, Erkki, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Jurgensen, Helmut, editor, and Reis, Rogério, editor

Published
2013
Full Text
View/download PDF

27. Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions

Author

Glaßer, Christian, Nguyen, Dung T., Reitwießner, Christian, Selman, Alan L., Witek, Maximilian, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fomin, Fedor V., editor, Freivalds, Rūsiņš, editor, Kwiatkowska, Marta, editor, and Peleg, David, editor

Published
2013
Full Text
View/download PDF

28. Universality of Regular Realizability Problems

Author

Vyalyi, Mikhail N., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bulatov, Andrei A., editor, and Shur, Arseny M., editor

Published
2013
Full Text
View/download PDF

30. Normativity in Logic

Author

Girard, Jean-Yves, Dybjer, P., editor, Lindström, Sten, editor, Palmgren, Erik, editor, and Sundholm, G., editor

Published
2012
Full Text
View/download PDF

31. Turing Machine-Inspired Computer Science Results

Author

Hartmanis, Juris, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Cooper, S. Barry, editor, Dawar, Anuj, editor, and Löwe, Benedikt, editor

Published
2012
Full Text
View/download PDF

32. Curiouser and Curiouser: The Link between Incompressibility and Complexity

Author

Allender, Eric, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Cooper, S. Barry, editor, Dawar, Anuj, editor, and Löwe, Benedikt, editor

Published
2012
Full Text
View/download PDF

33. Structural Complexity of Multiobjective NP Search Problems

Author

Fleszar, Krzysztof, Glaßer, Christian, Lipp, Fabian, Reitwießner, Christian, Witek, Maximilian, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Fernández-Baca, David, editor

Published
2012
Full Text
View/download PDF

34. The Legacy of Turing in Numerical Analysis

Author

Cucker, Felipe, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Bieliková, Mária, editor, Friedrich, Gerhard, editor, Gottlob, Georg, editor, Katzenbeisser, Stefan, editor, and Turán, György, editor

Published
2012
Full Text
View/download PDF

35. #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes

Author

RiverosCristian, JayaramRajesh, ArenasMarcelo, and CroquevielleLuis Alberto

Subjects
Turing machine, symbols.namesake, Theoretical computer science, Artificial Intelligence, Hardware and Architecture, Control and Systems Engineering, Simple (abstract algebra), Computer science, symbols, Enumeration, Complexity class, Software, Information Systems
Abstract

In this work, we study two simple yet general complexity classes, based on logspace Turing machines, that provide a unifying framework for efficient query evaluation in areas such as information extraction and graph databases, among others. We investigate the complexity of three fundamental algorithmic problems for these classes: enumeration, counting, and uniform generation of solutions, and show that they have several desirable properties in this respect. Both complexity classes are defined in terms of non-deterministic logspace transducers (NL-transducers). For the first class, we consider the case of unambiguous NL-transducers, and we prove constant delay enumeration and both counting and uniform generation of solutions in polynomial time. For the second class, we consider unrestricted NL-transducers, and we obtain polynomial delay enumeration, approximate counting in polynomial time, and polynomial-time randomized algorithms for uniform generation. More specifically, we show that each problem in this second class admits a fully polynomial-time randomized approximation scheme (FPRAS) and a polynomial-time Las Vegas algorithm (with preprocessing) for uniform generation. Remarkably, the key idea to prove these results is to show that the fundamental problem # NFA admits an FPRAS, where # NFA is the problem of counting the number of strings of length n (given in unary) accepted by a non-deterministic finite automaton (NFA). While this problem is known to be P-complete and, more precisely, SpanL -complete, it was open whether this problem admits an FPRAS. In this work, we solve this open problem and obtain as a welcome corollary that every function in SpanL admits an FPRAS.

Published
2021

36. MIP* = RE

Author

John C. Wright, Zhengfeng Ji, Henry Yuen, Anand Natarajan, and Thomas Vidick

Subjects
PCP theorem, Class (set theory), Theoretical computer science, Recursively enumerable language, General Computer Science, Computer science, Complexity class, Computational problem, Mathematical proof, Hardness of approximation, Halting problem
Abstract

Note from the Research Highlights Co-Chairs: A Research Highlights paper appearing in Communications is usually peer-reviewed prior to publication. The following paper is unusual in that it is still under review. However, the result has generated enormous excitement in the research community, and came strongly nominated by SIGACT, a nomination seconded by external reviewers. The complexity class NP characterizes the collection of computational problems that have efficiently verifiable solutions. With the goal of classifying computational problems that seem to lie beyond NP, starting in the 1980s complexity theorists have considered extensions of the notion of efficient verification that allow for the use of randomness (the class MA), interaction (the class IP), and the possibility to interact with multiple proofs, or provers (the class MIP). The study of these extensions led to the celebrated PCP theorem and its applications to hardness of approximation and the design of cryptographic protocols. In this work, we study a fourth modification to the notion of efficient verification that originates in the study of quantum entanglement. We prove the surprising result that every problem that is recursively enumerable, including the Halting problem, can be efficiently verified by a classical probabilistic polynomial-time verifier interacting with two all-powerful but noncommunicating provers sharing entanglement. The result resolves long-standing open problems in the foundations of quantum mechanics (Tsirelson's problem) and operator algebras (Connes' embedding problem).

Published
2021

37. Worlds to Die Harder For Open Oracle Questions for the 21st Century

Author

Lance Fortnow

Subjects
Multidisciplinary, Theoretical computer science, Computer science, Complexity class, Oracle
Abstract

Most of the interesting open problems about relationships between complexity classes have either been resolved or have relativizable worlds in both directions. We discuss some remaining open questions, updating questions from a similar 1995 survey of Hemaspaandra, Ramachandra and Zimand and adding a few new problems.

Published
2021

38. The Complexity of Counting Problems Over Incomplete Databases

Author

Marcelo Arenas, Mikaël Monet, Pablo Barceló, Pontificia Universidad Católica de Chile (UC), Millennium Institute for Foundational Research on Data (IMFD), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Linking Dynamic Data (LINKS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, General Computer Science, Logic, H.2, Context (language use), 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, Query language, 01 natural sciences, Theoretical Computer Science, Computer Science - Databases, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Complexity class, [INFO]Computer Science [cs], Mathematics, Database, Computability, Databases (cs.DB), closed-world assumption, Computational Mathematics, Null (SQL), Counting problem, 010201 computation theory & mathematics, counting complexity, Incomplete databases, Fully Polynomial-time Randomized Approximation Scheme (FPRAS), Conjunctive query, computer, Boolean conjunctive query
Abstract

We study the complexity of various fundamental counting problems that arise in the context of incomplete databases, i.e., relational databases that can contain unknown values in the form of labeled nulls. Specifically, we assume that the domains of these unknown values are finite and, for a Boolean query $q$, we consider the following two problems: given as input an incomplete database $D$, (a) return the number of completions of $D$ that satisfy $q$; or (b) return the number of valuations of the nulls of $D$ yielding a completion that satisfies $q$. We obtain dichotomies between \#P-hardness and polynomial-time computability for these problems when $q$ is a self-join-free conjunctive query, and study the impact on the complexity of the following two restrictions: (1) every null occurs at most once in $D$ (what is called Codd tables); and (2) the domain of each null is the same. Roughly speaking, we show that counting completions is much harder than counting valuations: for instance, while the latter is always in \#P, we prove that the former is not in \#P under some widely believed theoretical complexity assumption. Moreover, we find that both (1) and (2) can reduce the complexity of our problems. We also study the approximability of these problems and show that, while counting valuations always has a fully polynomial-time randomized approximation scheme (FPRAS), in most cases counting completions does not. Finally, we consider more expressive query languages and situate our problems with respect to known complexity classes., Comment: 51 pages, including 43 pages of main text. Extended version of arXiv:1912.11064. Up to the stylesheet, page/environment numbering, minor formatting, and publisher-induced changes, this is the exact content of the paper in ACM Transactions on Computational Logic

Published
2021

41. Limits on the Computational Power of Random Strings

Author

Allender, Eric, Friedman, Luke, Gasarch, William, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Aceto, Luca, editor, Henzinger, Monika, editor, and Sgall, Jiří, editor

Published
2011
Full Text
View/download PDF

42. Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth

Author

Jansen, Maurice, Santhanam, Rahul, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Aceto, Luca, editor, Henzinger, Monika, editor, and Sgall, Jiří, editor

Published
2011
Full Text
View/download PDF

43. Robust Simulations and Significant Separations

Author

Fortnow, Lance, Santhanam, Rahul, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Aceto, Luca, editor, Henzinger, Monika, editor, and Sgall, Jiří, editor

Published
2011
Full Text
View/download PDF

44. Axiomatizing Resource Bounds for Measure

Author

Gu, Xiaoyang, Lutz, Jack H., Nandakumar, Satyadev, Royer, James S., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Löwe, Benedikt, editor, Normann, Dag, editor, Soskov, Ivan, editor, and Soskova, Alexandra, editor

Published
2011
Full Text
View/download PDF

45. An Overview of Membrane Computing

Author

Krishna, Shankara Narayanan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Natarajan, Raja, editor, and Ojo, Adegboyega, editor

Published
2011
Full Text
View/download PDF

46. Characterising Space Complexity Classes via Knuth-Bendix Orders

Author

Bonfante, Guillaume, Moser, Georg, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Fermüller, Christian G., editor, and Voronkov, Andrei, editor

Published
2010
Full Text
View/download PDF

47. Randomisation and Derandomisation in Descriptive Complexity Theory

Author

Eickmeyer, Kord, Grohe, Martin, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dawar, Anuj, editor, and Veith, Helmut, editor

Published
2010
Full Text
View/download PDF

48. Formal Theories for Linear Algebra

Author

Cook, Stephen, Fontes, Lila, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dawar, Anuj, editor, and Veith, Helmut, editor

Published
2010
Full Text
View/download PDF

49. Balanced Queries: Divide and Conquer

Author

Akatov, Dmitri, Gottlob, Georg, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Hliněný, Petr, editor, and Kučera, Antonín, editor

Published
2010
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results