9 Search Results for "Saks, Michael"


Document
On Randomized Reductions to the Random Strings

Authors: Michael Saks and Rahul Santhanam

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)


Abstract
We study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants. As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language L that has a randomized polynomial-time non-adaptive reduction (satisfying a natural honesty condition) to ω(log(n))-approximating the Kolmogorov complexity is in AM ∩ coAM. On the other hand, using results of Hirahara [Shuichi Hirahara, 2020], it follows that every language in NEXP has a randomized polynomial-time non-adaptive reduction (satisfying the same honesty condition as before) to O(log(n))-approximating the Kolmogorov complexity. As our second main result, we give the first negative evidence against the NP-hardness of polynomial-time bounded Kolmogorov complexity with respect to randomized reductions. We show that for every polynomial t', there is a polynomial t such that if there is a randomized time t' non-adaptive reduction (satisfying a natural honesty condition) from SAT to ω(log(n))-approximating K^t complexity, then either NE = coNE or 𝖤 has sub-exponential size non-deterministic circuits infinitely often.

Cite as

Michael Saks and Rahul Santhanam. On Randomized Reductions to the Random Strings. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 29:1-29:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{saks_et_al:LIPIcs.CCC.2022.29,
  author =	{Saks, Michael and Santhanam, Rahul},
  title =	{{On Randomized Reductions to the Random Strings}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{29:1--29:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.29},
  URN =		{urn:nbn:de:0030-drops-165912},
  doi =		{10.4230/LIPIcs.CCC.2022.29},
  annote =	{Keywords: Kolmogorov complexity, randomized reductions}
}
Document
Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems

Authors: François Le Gall and Saeed Seddighin

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
Longest common substring (LCS), longest palindrome substring (LPS), and Ulam distance (UL) are three fundamental string problems that can be classically solved in near linear time. In this work, we present sublinear time quantum algorithms for these problems along with quantum lower bounds. Our results shed light on a very surprising fact: Although the classic solutions for LCS and LPS are almost identical (via suffix trees), their quantum computational complexities are different. While we give an exact Õ(√n) time algorithm for LPS, we prove that LCS needs at least time ̃ Ω(n^{2/3}) even for 0/1 strings.

Cite as

François Le Gall and Saeed Seddighin. Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 97:1-97:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{legall_et_al:LIPIcs.ITCS.2022.97,
  author =	{Le Gall, Fran\c{c}ois and Seddighin, Saeed},
  title =	{{Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{97:1--97:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.97},
  URN =		{urn:nbn:de:0030-drops-156934},
  doi =		{10.4230/LIPIcs.ITCS.2022.97},
  annote =	{Keywords: Longest common substring, Longest palindrome substring, Quantum algorithms, Sublinear algorithms}
}
Document
NP-Hardness of Circuit Minimization for Multi-Output Functions

Authors: Rahul Ilango, Bruno Loff, and Igor C. Oliveira

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)


Abstract
Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an explicitly given function is NP-complete. While this is known to hold in restricted models such as DNFs, making progress with respect to more expressive classes of circuits has been elusive. In this work, we establish the first NP-hardness result for circuit minimization of total functions in the setting of general (unrestricted) Boolean circuits. More precisely, we show that computing the minimum circuit size of a given multi-output Boolean function f : {0,1}^n → {0,1}^m is NP-hard under many-one polynomial-time randomized reductions. Our argument builds on a simpler NP-hardness proof for the circuit minimization problem for (single-output) Boolean functions under an extended set of generators. Complementing these results, we investigate the computational hardness of minimizing communication. We establish that several variants of this problem are NP-hard under deterministic reductions. In particular, unless 𝖯 = 𝖭𝖯, no polynomial-time computable function can approximate the deterministic two-party communication complexity of a partial Boolean function up to a polynomial. This has consequences for the class of structural results that one might hope to show about the communication complexity of partial functions.

Cite as

Rahul Ilango, Bruno Loff, and Igor C. Oliveira. NP-Hardness of Circuit Minimization for Multi-Output Functions. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 22:1-22:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{ilango_et_al:LIPIcs.CCC.2020.22,
  author =	{Ilango, Rahul and Loff, Bruno and Oliveira, Igor C.},
  title =	{{NP-Hardness of Circuit Minimization for Multi-Output Functions}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{22:1--22:36},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.22},
  URN =		{urn:nbn:de:0030-drops-125744},
  doi =		{10.4230/LIPIcs.CCC.2020.22},
  annote =	{Keywords: MCSP, circuit minimization, communication complexity, Boolean circuit}
}
Document
Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions

Authors: Michael Saks and Rahul Santhanam

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)


Abstract
The fundamental Minimum Circuit Size Problem is a well-known example of a problem that is neither known to be in 𝖯 nor known to be NP-hard. Kabanets and Cai [Kabanets and Cai, 2000] showed that if MCSP is NP-hard under "natural" m-reductions, superpolynomial circuit lower bounds for exponential time would follow. This has triggered a long line of work on understanding the power of reductions to MCSP. Nothing was known so far about consequences of NP-hardness of MCSP under general Turing reductions. In this work, we consider two structured kinds of Turing reductions: parametric honest reductions and natural reductions. The latter generalize the natural reductions of Kabanets and Cai to the case of Turing-reductions. We show that NP-hardness of MCSP under these kinds of Turing-reductions imply superpolynomial circuit lower bounds for exponential time.

Cite as

Michael Saks and Rahul Santhanam. Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{saks_et_al:LIPIcs.CCC.2020.26,
  author =	{Saks, Michael and Santhanam, Rahul},
  title =	{{Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{26:1--26:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.26},
  URN =		{urn:nbn:de:0030-drops-125786},
  doi =		{10.4230/LIPIcs.CCC.2020.26},
  annote =	{Keywords: Minimum Circuit Size Problem, Turing reductions, circuit lower bounds}
}
Document
Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas

Authors: Rahul Ilango

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)


Abstract
A longstanding open question is whether there is an equivalence between the computational task of determining the minimum size of any circuit computing a given function and the task of producing a minimum-sized circuit for a given function. While it is widely conjectured that both tasks require "perebor," or brute-force search, researchers have not yet ruled out the possibility that the search problem requires exponential time but the decision problem has a linear time algorithm. In this paper, we make progress in connecting the search and decision complexity of minimizing formulas. Let MFSP denote the problem that takes as input the truth table of a Boolean function f and an integer size parameter s and decides whether there is a formula for f of size at most s. Let Search- denote the corresponding search problem where one has to output some optimal formula for computing f. Our main result is that given an oracle to MFSP, one can solve Search-MFSP in time polynomial in the length N of the truth table of f and the number t of "near-optimal" formulas for f, in particular O(N⁶t²)-time. While the quantity t is not well understood, we use this result (and some extensions) to prove that given an oracle to MFSP: - there is a deterministic 2^O(N/(log log N))-time oracle algorithm for solving Search-MFSP on all but a o(1)-fraction of instances, and - there is a randomized O(2^.67N)-time oracle algorithm for solving Search-MFSP on all instances. Intriguingly, the main idea behind our algorithms is in some sense a "reverse application" of the gate elimination technique.

Cite as

Rahul Ilango. Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 31:1-31:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{ilango:LIPIcs.CCC.2020.31,
  author =	{Ilango, Rahul},
  title =	{{Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{31:1--31:35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.31},
  URN =		{urn:nbn:de:0030-drops-125834},
  doi =		{10.4230/LIPIcs.CCC.2020.31},
  annote =	{Keywords: minimum circuit size problem, minimum formula size problem, gate elimination, search to decision reduction, self-reducibility}
}
Document
Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]

Authors: Rahul Ilango

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)


Abstract
The Minimum Circuit Size Problem (MCSP) asks whether a given Boolean function has a circuit of at most a given size. MCSP has been studied for over a half-century and has deep connections throughout theoretical computer science including to cryptography, computational learning theory, and proof complexity. For example, we know (informally) that if MCSP is easy to compute, then most cryptography can be broken. Despite this cryptographic hardness connection and extensive research, we still know relatively little about the hardness of MCSP unconditionally. Indeed, until very recently it was unknown whether MCSP can be computed in AC^0[2] (Golovnev et al., ICALP 2019). Our main contribution in this paper is to formulate a new "oracle" variant of circuit complexity and prove that this problem is NP-complete under randomized reductions. In more detail, we define the Minimum Oracle Circuit Size Problem (MOCSP) that takes as input the truth table of a Boolean function f, a size threshold s, and the truth table of an oracle Boolean function O, and determines whether there is a circuit with O-oracle gates and at most s wires that computes f. We prove that MOCSP is NP-complete under randomized polynomial-time reductions. We also extend the recent AC^0[p] lower bound against MCSP by Golovnev et al. to a lower bound against the circuit minimization problem for depth-d formulas, (AC^0_d)-MCSP. We view this result as primarily a technical contribution. In particular, our proof takes a radically different approach from prior MCSP-related hardness results.

Cite as

Rahul Ilango. Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 34:1-34:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{ilango:LIPIcs.ITCS.2020.34,
  author =	{Ilango, Rahul},
  title =	{{Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0\lbrackp\rbrack}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{34:1--34:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.34},
  URN =		{urn:nbn:de:0030-drops-117191},
  doi =		{10.4230/LIPIcs.ITCS.2020.34},
  annote =	{Keywords: Minimum Circuit Size Problem, reductions, NP-completeness, circuit lower bounds}
}
Document
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication

Authors: Debarati Das, Michal Koucký, and Michael Saks

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)


Abstract
In this paper we propose models of combinatorial algorithms for the Boolean Matrix Multiplication (BMM), and prove lower bounds on computing BMM in these models. First, we give a relatively relaxed combinatorial model which is an extension of the model by Angluin (1976), and we prove that the time required by any algorithm for the BMM is at least Omega(n^3 / 2^{O( sqrt{ log n })}). Subsequently, we propose a more general model capable of simulating the "Four Russian Algorithm". We prove a lower bound of Omega(n^{7/3} / 2^{O(sqrt{ log n })}) for the BMM under this model. We use a special class of graphs, called (r,t)-graphs, originally discovered by Rusza and Szemeredi (1978), along with randomization, to construct matrices that are hard instances for our combinatorial models.

Cite as

Debarati Das, Michal Koucký, and Michael Saks. Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.STACS.2018.23,
  author =	{Das, Debarati and Kouck\'{y}, Michal and Saks, Michael},
  title =	{{Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.23},
  URN =		{urn:nbn:de:0030-drops-85050},
  doi =		{10.4230/LIPIcs.STACS.2018.23},
  annote =	{Keywords: Lower bounds, Combinatorial algorithm, Boolean matrix multiplication}
}
Document
The Power of Super-logarithmic Number of Players

Authors: Arkadev Chattopadhyay and Michael E. Saks

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


Abstract
In the `Number-on-Forehead' (NOF) model of multiparty communication, the input is a k times m boolean matrix A (where k is the number of players) and Player i sees all bits except those in the i-th row, and the players communicate by broadcast in order to evaluate a specified function f at A. We discover new computational power when k exceeds log m. We give a protocol with communication cost poly-logarithmic in m, for block composed functions with limited block width. These are functions of the form f o g where f is a symmetric b-variate function, and g is a (kr)-variate function and (f o g)(A) is defined, for a k times (br) matrix to be f(g(A-1),...,g(A-b)) where A-i is the i-th (k times r) block of A. Our protocol works provided that k > 1+ ln b + (2 to the power of r). Ada et al. (ICALP'2012) previously obtained simultaneous and deterministic efficient protocols for composed functions of block-width one. The new protocol is the first to work for block composed functions with block-width greather than one. Moreover, it is simultaneous, with vanishingly small error probability, if public coin randomness is allowed. The deterministic and zero-error version barely uses interaction.

Cite as

Arkadev Chattopadhyay and Michael E. Saks. The Power of Super-logarithmic Number of Players. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 596-603, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.APPROX-RANDOM.2014.596,
  author =	{Chattopadhyay, Arkadev and Saks, Michael E.},
  title =	{{The Power of Super-logarithmic Number of Players}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{596--603},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.596},
  URN =		{urn:nbn:de:0030-drops-47243},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.596},
  annote =	{Keywords: Communication complexity, Number-On-Forehead model, composed functions}
}
Document
On the practically interesting instances of MAXCUT

Authors: Yonatan Bilu, Amit Daniely, Nati Linial, and Michael Saks

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)


Abstract
For many optimization problems, the instances of practical interest often occupy just a tiny part of the algorithm's space of instances. Following (Y. Bilu and N. Linial, 2010), we apply this perspective to MAXCUT, viewed as a clustering problem. Using a variety of techniques, we investigate practically interesting instances of this problem. Specifically, we show how to solve in polynomial time distinguished, metric, expanding and dense instances of MAXCUT under mild stability assumptions. In particular, (1 + epsilon)-stability (which is optimal) suffices for metric and dense MAXCUT. We also show how to solve in polynomial time Omega(sqrt(n))-stable instances of MAXCUT, substantially improving the best previously known result.

Cite as

Yonatan Bilu, Amit Daniely, Nati Linial, and Michael Saks. On the practically interesting instances of MAXCUT. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 526-537, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{bilu_et_al:LIPIcs.STACS.2013.526,
  author =	{Bilu, Yonatan and Daniely, Amit and Linial, Nati and Saks, Michael},
  title =	{{On the practically interesting instances of MAXCUT}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{526--537},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.526},
  URN =		{urn:nbn:de:0030-drops-39625},
  doi =		{10.4230/LIPIcs.STACS.2013.526},
  annote =	{Keywords: MAXCUT, Clustering, Hardness in practice, Stability, Non worst-case analysis}
}
  • Refine by Author
  • 4 Saks, Michael
  • 3 Ilango, Rahul
  • 2 Santhanam, Rahul
  • 1 Bilu, Yonatan
  • 1 Chattopadhyay, Arkadev
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Circuit complexity
  • 3 Theory of computation → Computational complexity and cryptography
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 2 Minimum Circuit Size Problem
  • 2 circuit lower bounds
  • 1 Boolean circuit
  • 1 Boolean matrix multiplication
  • 1 Clustering
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 4 2020
  • 2 2022
  • 1 2013
  • 1 2014
  • 1 2018

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