Impagliazzo, Russell; Kabanets, Valentine; Volkovich, Ilya The power of natural properties as oracles. (English) Zbl 07727624 Comput. Complexity 32, No. 2, Paper No. 6, 40 p. (2023). MSC: 68Q15 68Q06 68Q17 68Q25 68W20 PDFBibTeX XMLCite \textit{R. Impagliazzo} et al., Comput. Complexity 32, No. 2, Paper No. 6, 40 p. (2023; Zbl 07727624) Full Text: DOI
Cheraghchi, Mahdi; Kabanets, Valentine; Lu, Zhenjian; Myrisiotis, Dimitrios Circuit lower bounds for MCSP from local pseudorandom generators. (English) Zbl 1499.68102 ACM Trans. Comput. Theory 12, No. 3, Article No. 21, 27 p. (2020). MSC: 68Q06 68Q17 PDFBibTeX XMLCite \textit{M. Cheraghchi} et al., ACM Trans. Comput. Theory 12, No. 3, Article No. 21, 27 p. (2020; Zbl 1499.68102) Full Text: DOI
Golovnev, Alexander; Ilango, Rahul; Impagliazzo, Russell; Kabanets, Valentine; Kolokolova, Antonina; Tal, Avishay \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem. (English) Zbl 1524.68133 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 66, 15 p. (2019). MSC: 68Q06 68Q17 PDFBibTeX XMLCite \textit{A. Golovnev} et al., LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 66, 15 p. (2019; Zbl 1524.68133) Full Text: DOI
Cheraghchi, Mahdi; Kabanets, Valentine; Lu, Zhenjian; Myrisiotis, Dimitrios Circuit lower bounds for MCSP from local pseudorandom generators. (English) Zbl 1499.68101 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 39, 14 p. (2019). MSC: 68Q06 68Q17 PDFBibTeX XMLCite \textit{M. Cheraghchi} et al., LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 39, 14 p. (2019; Zbl 1499.68101) Full Text: DOI
Impagliazzo, Russell; Kabanets, Valentine; Volkovich, Ilya The power of natural properties as oracles. (English) Zbl 1441.68060 Servedio, Rocco A. (ed.), 33rd computational complexity conference, CCC 2018, June 22–24, 2018, San Diego, California, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 102, Article 7, 20 p. (2018). MSC: 68Q15 68Q06 68Q17 68W20 PDFBibTeX XMLCite \textit{R. Impagliazzo} et al., LIPIcs -- Leibniz Int. Proc. Inform. 102, Article 7, 20 p. (2018; Zbl 1441.68060) Full Text: DOI
Carmosino, Marco L.; Impagliazzo, Russell; Kabanets, Valentine; Kolokolova, Antonina Agnostic learning from tolerant natural proofs. (English) Zbl 1467.68076 Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 35, 19 p. (2017). MSC: 68Q32 68Q06 68Q17 PDFBibTeX XMLCite \textit{M. L. Carmosino} et al., LIPIcs -- Leibniz Int. Proc. Inform. 81, Article 35, 19 p. (2017; Zbl 1467.68076) Full Text: DOI
Allender, Eric; Holden, Dhiraj; Kabanets, Valentine The minimum oracle circuit size problem. (English) Zbl 1408.68065 Comput. Complexity 26, No. 2, 469-496 (2017). MSC: 68Q17 68Q30 PDFBibTeX XMLCite \textit{E. Allender} et al., Comput. Complexity 26, No. 2, 469--496 (2017; Zbl 1408.68065) Full Text: DOI Link
Impagliazzo, Russell; Kabanets, Valentine Fourier concentration from shrinkage. (English) Zbl 1371.68092 Comput. Complexity 26, No. 1, 275-321 (2017). MSC: 68Q15 68Q17 68Q25 PDFBibTeX XMLCite \textit{R. Impagliazzo} and \textit{V. Kabanets}, Comput. Complexity 26, No. 1, 275--321 (2017; Zbl 1371.68092) Full Text: DOI
Carmosino, Marco L.; Impagliazzo, Russell; Kabanets, Valentine; Kolokolova, Antonina Learning algorithms from natural proofs. (English) Zbl 1380.68242 Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 10, 24 p. (2016). MSC: 68Q32 68Q05 68Q15 68Q17 PDFBibTeX XMLCite \textit{M. L. Carmosino} et al., LIPIcs -- Leibniz Int. Proc. Inform. 50, Article 10, 24 p. (2016; Zbl 1380.68242) Full Text: DOI
Artemenko, Sergei; Impagliazzo, Russell; Kabanets, Valentine; Shaltiel, Ronen Pseudorandomness when the odds are against you. (English) Zbl 1380.68434 Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 9, 35 p. (2016). MSC: 68W20 68Q17 68Q25 PDFBibTeX XMLCite \textit{S. Artemenko} et al., LIPIcs -- Leibniz Int. Proc. Inform. 50, Article 9, 35 p. (2016; Zbl 1380.68434) Full Text: DOI
Allender, Eric; Holden, Dhiraj; Kabanets, Valentine The minimum oracle circuit size problem. (English) Zbl 1355.68104 Mayr, Ernst W. (ed.) et al., 32nd international symposium on theoretical aspects of computer science, STACS’15, Garching, Germany, March 4–7, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-78-1). LIPIcs – Leibniz International Proceedings in Informatics 30, 21-33 (2015). MSC: 68Q17 68Q30 PDFBibTeX XMLCite \textit{E. Allender} et al., LIPIcs -- Leibniz Int. Proc. Inform. 30, 21--33 (2015; Zbl 1355.68104) Full Text: DOI
Chen, Ruiwen; Kabanets, Valentine; Kinne, Jeff Lower bounds against weakly-uniform threshold circuits. (English) Zbl 1314.68142 Algorithmica 70, No. 1, 47-75 (2014). MSC: 68Q17 68Q05 68Q15 94C10 PDFBibTeX XMLCite \textit{R. Chen} et al., Algorithmica 70, No. 1, 47--75 (2014; Zbl 1314.68142) Full Text: DOI
Dell, Holger; Kabanets, Valentine; van Melkebeek, Dieter; Watanabe, Osamu Is Valiant-Vazirani’s isolation probability improvable? (English) Zbl 1286.68167 Comput. Complexity 22, No. 2, 345-383 (2013). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{H. Dell} et al., Comput. Complexity 22, No. 2, 345--383 (2013; Zbl 1286.68167) Full Text: DOI
Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi New direct-product testers and 2-query PCPs. (English) Zbl 1275.68069 SIAM J. Comput. 41, No. 6, 1722-1768 (2012). MSC: 68Q10 68Q15 68Q17 PDFBibTeX XMLCite \textit{R. Impagliazzo} et al., SIAM J. Comput. 41, No. 6, 1722--1768 (2012; Zbl 1275.68069) Full Text: DOI
Chen, Ruiwen; Kabanets, Valentine Lower bounds against weakly uniform circuits. (English) Zbl 1364.68217 Gudmundsson, Joachim (ed.) et al., Computing and combinatorics. 18th annual international conference, COCOON 2012, Sydney, Australia, August 20–22, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32240-2/pbk). Lecture Notes in Computer Science 7434, 408-419 (2012). MSC: 68Q17 68Q05 68Q15 94C10 PDFBibTeX XMLCite \textit{R. Chen} and \textit{V. Kabanets}, Lect. Notes Comput. Sci. 7434, 408--419 (2012; Zbl 1364.68217) Full Text: DOI
Juma, Ali; Kabanets, Valentine; Rackoff, Charles; Shpilka, Amir The black-box query complexity of polynomial summation. (English) Zbl 1213.68263 Comput. Complexity 18, No. 1, 59-79 (2009). MSC: 68Q05 68Q15 68Q17 68Q25 PDFBibTeX XMLCite \textit{A. Juma} et al., Comput. Complexity 18, No. 1, 59--79 (2009; Zbl 1213.68263) Full Text: DOI
Impagliazzo, Russell; Jaiswal, Ragesh; Kabanets, Valentine; Wigderson, Avi Uniform direct product theorems: simplified, optimized, and derandomized. (English) Zbl 1206.68131 SIAM J. Comput. 39, No. 4, 1637-1665 (2009). MSC: 68Q15 68Q17 68Q25 68P30 68W20 PDFBibTeX XMLCite \textit{R. Impagliazzo} et al., SIAM J. Comput. 39, No. 4, 1637--1665 (2009; Zbl 1206.68131) Full Text: DOI
Impagliazzo, Russell; Jaiswal, Ragesh; Kabanets, Valentine Approximate list-decoding of direct product codes and uniform hardness amplification. (English) Zbl 1200.68142 SIAM J. Comput. 39, No. 2, 564-605 (2009). MSC: 68Q45 68Q15 68Q17 68Q25 68P30 PDFBibTeX XMLCite \textit{R. Impagliazzo} et al., SIAM J. Comput. 39, No. 2, 564--605 (2009; Zbl 1200.68142) Full Text: DOI
Guruswami, Venkatesan; Kabanets, Valentine Hardness amplification via space-efficient direct products. (English) Zbl 1188.68152 Comput. Complexity 17, No. 4, 475-500 (2008). MSC: 68Q17 68P30 68Q25 94B05 94B35 PDFBibTeX XMLCite \textit{V. Guruswami} and \textit{V. Kabanets}, Comput. Complexity 17, No. 4, 475--500 (2008; Zbl 1188.68152) Full Text: DOI
Fortnow, Lance; Impagliazzo, Russell; Kabanets, Valentine; Umans, Christopher On the complexity of succinct zero-sum games. (English) Zbl 1162.91302 Comput. Complexity 17, No. 3, 353-376 (2008). MSC: 91A05 68Q15 68Q17 68Q32 03D15 PDFBibTeX XMLCite \textit{L. Fortnow} et al., Comput. Complexity 17, No. 3, 353--376 (2008; Zbl 1162.91302) Full Text: DOI
Kabanets, Valentine; Impagliazzo, Russell Derandomizing polynomial identity tests means proving circuit lower bounds. (English) Zbl 1089.68042 Comput. Complexity 13, No. 1-2, 1-46 (2004). MSC: 68Q10 68Q15 68Q17 PDFBibTeX XMLCite \textit{V. Kabanets} and \textit{R. Impagliazzo}, Comput. Complexity 13, No. 1--2, 1--46 (2004; Zbl 1089.68042) Full Text: DOI
Kabanets, Valentine Almost \(k\)-wise independence and hard Boolean functions. (English) Zbl 1051.68080 Theor. Comput. Sci. 297, No. 1-3, 281-295 (2003). MSC: 68Q25 68Q17 PDFBibTeX XMLCite \textit{V. Kabanets}, Theor. Comput. Sci. 297, No. 1--3, 281--295 (2003; Zbl 1051.68080) Full Text: DOI
Kabanets, Valentine; Cai, Jin-Yi Circuit minimization problem. (English) Zbl 1296.94182 Proceedings of the thirty-second annual ACM symposium on theory of computing (STOC 2000), Portland, Oregon, USA, May 21–23, 2000. New York, NY: ACM Press (ISBN 1-58113-184-4). 73-79 (2000). MSC: 94C10 68Q15 68Q17 68Q25 PDFBibTeX XMLCite \textit{V. Kabanets} and \textit{J.-Y. Cai}, in: Proceedings of the thirty-second annual ACM symposium on theory of computing, STOC 2000. Portland, Oregon, USA, May 21--23, 2000. New York, NY: ACM Press. 73--79 (2000; Zbl 1296.94182) Full Text: DOI