The Library
Browse by Warwick Author
Up a level |
Number of items: 37.
Journal Article
Chen, Lijie, Hirahara, Shuichi, Oliveira, Igor Carboni, Pich, JΓ‘n, Rajgopal, Ninad and Santhanam, Rahul (2022) Beyond natural proofs : hardness magnification and locality. Journal of the ACM, 69 (4). 25. doi:10.1145/3538391 ISSN 0004-5411.
Lu, Zhenjian and Oliveira, Igor C. (2022) Theory and applications of probabilistic Kolmogorov complexity. Bulletin of EATCS, 137 .
Oliveira, Igor C., Bydzovsky, Jan and Krajicek, Jan (2020) Consistency of circuit lower bounds with bounded theories. Logical Methods in Computer Science, 16 (2). 12:1-12:16. doi:10.23638/LMCS-16(2:12)2020 ISSN 1860-5974.
Krajicek, Jan and Oliveira, Igor Carboni (2018) On monotone circuits with local oracles and clique lower bounds. Chicago Journal of Theoretical Computer Science, 24 . pp. 1-18. 1. doi:10.4086/cjtcs.2018.001 ISSN 1073-0486.
Gauy, Marcelo M., Han, Hiep and Oliveira, Igor C. (2017) ErdΕsβKoβRado for random hypergraphs : asymptotics and stability. Combinatorics, Probability and Computing, 26 (3). pp. 406-422. doi:10.1017/S0963548316000420 ISSN 0963-5483.
Krajicek, Jan and Oliveira, Igor Carboni (2017) Unprovability of circuit upper bounds in Cook's theory PV. Logical Methods in Computer Science, 13 (1). doi:10.23638/LMCS-13(1:4)2017 ISSN 1860-5974.
Oliveira, Igor Carboni and Thatte, Bhalchandra D. (2015) An algebraic formulation of the graph reconstruction conjecture. Journal of Graph Theory, 81 (4). pp. 351-363. doi:10.1002/jgt.21880 ISSN 0364-9024.
Book Item
Guo, Siyao, Malkin, Tal, Oliveira, Igor C. and Rosen, Alon (2015) The power of negations in cryptography. In: Dodis, Yevgeniy and Nielsen, Jesper Buus, (eds.) Theory of Cryptography : 12th International Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I. Lecture Notes in Computer Science, 9014 . Springer-Verlag Berlin Heidelberg, pp. 36-65. ISBN 9783662464939
Conference Item
Chen, Lijie, Lu, Zhenjian, Oliveira, Igor C., Ren, Hanlin and Santhanam, Rahul (2023) Polynomial-time pseudodeterministic construction of primes. In: 64th IEEE Symposium on Foundations of Computer Science (FOCS) 2023, Santa Cruz, CA, USA, 06-09 Nov 2023. Published in: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) ISBN 9798350318951. doi:10.1109/FOCS57990.2023.00074 ISSN 1523-8288.
Cavalar, Bruno P. and Oliveira, Igor C. (2023) Constant-depth circuits vs. monotone circuits. In: 38th Computational Complexity Conference (CCC 2023), Warwick, UK, 17β20 Jul 2023. Published in: 38th Computational Complexity Conference (CCC 2023), 264 29:1-29:37. ISBN 9783959772822. doi:10.4230/LIPIcs.CCC.2023.29 ISSN 1868-8969.
Li, Jiatu and Oliveira, Igor C. (2023) Unprovability of strong complexity lower bounds in bounded arithmetic. In: STOC 2023: 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, USA, 20-23 Jun 2023. Published in: Proceedings of the STOC 2023: 55th Annual ACM Symposium on Theory of Computing (In Press)
Hirahara, Shuichi, Ilango, Rahul, Lu, Zhenjian, Nanashima, Mikito and Oliveira, Igor C. (2023) A duality between one-way functions and average-case symmetry of information. In: STOC 2023: 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, USA, 20-23 Jun 2023. Published in: Proceedings of the STOC 2023: 55th Annual ACM Symposium on Theory of Computing (In Press)
Goldberg, Halley, Kabanets, Valentine, Lu, Zhenjian and Oliveira, Igor C. (2022) Probabilistic Kolmogorov complexity with applications to average-case complexity. In: Computational Complexity Conference (CCC), Philadelphia, PA, USA, 21β23 Jul 2022. Published in: 37th Computational Complexity Conference (CCC 2022), 234 16:1-16:60. ISBN 9783959772419. doi:10.4230/LIPIcs.CCC.2022.16 ISSN 1868-8969.
Oliveira, Igor C., Lu, Zhenjian and Zimand, Marius (2022) Optimal coding theorems in time-bounded Kolmogorov complexity. In: 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP), Paris ; Online, 4-8 Jul 2022. Published in: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), 229 92:1-92:14. ISBN 9783959772358. doi:10.4230/LIPIcs.ICALP.2022.92 ISSN 1868-8969.
Carmosino, Marco, Kabanets, Valentine, Kolokolova, Antonina and Carboni Oliveira, Igor (2022) LEARN-uniform circuit lower bounds and provability in bounded arithmetic. In: Symposium on Foundations of Computer Science (FOCS), Denver, Colorado, 7-10 Feb 2022. Published in: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) doi:10.1109/FOCS52979.2021.00080 ISSN 2575-8454.
Lu, Zhenjian and Oliveira, Igor C. (2021) An efficient coding theorem via probabilistic representations and its applications. In: International Colloquium on Automata, Languages and Programming (ICALP), Virtual conference, 12-16 Jul 2021. Published in: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 198 94:1-94:20. ISBN 9783959771955. doi:10.4230/LIPIcs.ICALP.2021.94 ISSN 1868-8969.
Chen, Lijie, Lu, Zhenjian, Lyu, Xin and Oliveira, Igor C. (2021) Majority vs. approximate linear sum and average-case complexity below NC1. In: International Colloquium on Automata, Languages and Programming (ICALP), Virtual conference, 12-16 Jul 2021. Published in: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 198 51:1-51:20. ISBN 9783959771955. doi:10.4230/LIPIcs.ICALP.2021.51 ISSN 1868-8969.
Lu, Zhenjian, Oliveira, Igor C. and Santhanam, Rahul (2021) Pseudodeterministic algorithms and the structure of probabilistic time. In: 53rd Annual ACM SIGACT Symposium on Theory of Computing , Virtual conference, 21-25 June 2021. Published in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing ISBN 9781450380539. doi:10.1145/3406325.3451085
Lu, Zhen Jian, Oliveira, Igor C. and Santhanam, Rahul (2021) Pseudodeterministic lagorithms and the structure of probabilistic time. In: STOC 2021: 53rd Annual ACM Symposium on Theory of Computing, Virtual conference, 21-25 Jun 2021. Published in: STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing pp. 303-316. ISBN 9781450380539. doi:10.1145/3406325.3451085
Arunachalam, Srinivasan, Grilo, Alex B., Gur, Tom, Carboni Oliveira, Igor and Sundaram, Aarthi (2021) Quantum learning algorithms imply circuit lower bounds. In: The 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021), Denver, Colorado, 7-10 Feb 2022. Published in: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) doi:10.1109/FOCS52979.2021.00062 ISSN 2575-8454.
Kabanets, Valentine, Lu, Zhenjian, Koroth, Sajin, Myrisiotis, Dimitrios and Carboni Oliveira, Igor (2020) Algorithms and lower bounds for de Morgan formulas of low-communication leaf gates. In: Computational Complexity Conference (CCC), 28β31 Jul 2020. Published in: CCC '20: Proceedings of the 35th Computational Complexity Conference pp. 1-41. ISBN 9783959771566. doi:10.4230/LIPIcs.CCC.2020.15 ISSN 1868-8969.
Ilango, Rahul, Loff, Bruno and Carboni Oliveira, Igor (2020) NP-hardness of circuit minimization for multi-output functions. In: Computational Complexity Conference (CCC), 28β31 Jul 2020. Published in: CCC '20: Proceedings of the 35th Computational Complexity Conference pp. 1-36. ISBN 9783959771566. doi:10.4230/LIPIcs.CCC.2020.22 ISSN 1868-8969.
Chen, Lijie, Hirahara, Shuichi, Carboni Oliveira, Igor, Pich, Jan, Rajgopal, Ninad and Santhanam, Rahul (2020) Beyond natural proofs : hardness magnification and locality. In: Innovations in Theoretical Computer Science, Seattle, USA, 12-14 Jan 2020. Published in: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), 151 70 :1-70 :48. ISBN 9783959771344. doi:10.4230/LIPIcs.ITCS.2020.70
Oliveira, Igor C., Pich, Jan and Santhanam, Rahul (2019) Hardness magnification near state-of-the-art lower bounds. In: 34th Computational Complexity Conference (CCC 2019), New Brunswick, NJ, USA, 18-20 Jul 2019. Published in: Proceedings of the 33rd Computational Complexity Conference, 137 27:1-27:29. ISBN 9783959771160. doi:10.4230/LIPIcs.CCC.2019.27 ISSN 1868-8969.
Oliveira, Igor C., Santhanam, Rahul and Srinivasan, Srikanth (2019) Parity helps to compute majority. In: 34th Computational Complexity Conference (CCC 2019), New Brunswick, NJ, USA, 18-20 Jul 2019. Published in: Proceedings of the 34th Computational Complexity Conference (CCC), 137 23:1-23:17. ISBN 9783959771160. doi:10.4230/LIPIcs.CCC.2019.23 ISSN 1868-8969.
Oliveira, Igor C. (2019) Randomness and intractability in Kolmogorov complexity. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Patras, Greece, 9-12 Jul 2019. Published in: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), 132 32:1-32:14. ISBN 9783959771092. doi:10.4230/LIPIcs.ICALP.2019.32 ISSN 1868-8969.
Oliveira, Igor Carboni and Santhanam, Rahul (2018) Hardness magnification for natural problems. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Paris, France, 7-9 Oct 2018 pp. 65-76. ISBN 9781538642306. doi:10.1109/FOCS.2018.00016 ISSN 2575-8454.
Oliveira, Igor C., Santhanam, Rahul and Tell, Roei (2018) Expander-based cryptography meets natural proofs. In: 10th Innovations in Theoretical Computer Science Conference (ITCS), San Diego, California, USA., 10-12 Jan 2019. Published in: Proceedings of the 33rd Computational Complexity Conference, 124 18:1-18:14. ISBN 9783959770958. doi:10.4230/LIPIcs.ITCS.2019.18 ISSN 1868-8969.
Hirahara, Shuichi, Oliveira, Igor C. and Santhanam, Rahul (2018) NP-hardness of minimum circuit size problem for OR-AND-MOD circuits. In: Computational Complexity Conference, San Diego, California, 22-24 Jun 2018. Published in: Proceedings of the 33rd Computational Complexity Conference, 102 5:1-5:31. ISBN 9783959770699. doi:10.4230/LIPIcs.CCC.2018.5 ISSN 1868-8969.
Oliveira, Igor C. and Santhanam, Rahul (2018) Pseudo-derandomizing learning and approximation. In: 22nd International Conference on Randomization and Computation (RANDOM), Princeton, NJ, USA, 20-22 Aug 2018. Published in: Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM), 116 55:1-55:19. ISBN 9783959770699. doi:10.4230/LIPIcs.APPROX-RANDOM.2018.55 ISSN 1868-8969.
Chen, Ruiwen, Oliveira, Igor Carboni and Santhanam, Rahul (2018) An average-case lower bound against ACC0. In: LATIN 2018: Theoretical Informatics 13th Latin American Symposium, Buenos Aires, Argentina, 16-19 Apr 2018. Published in: LATIN 2018: Theoretical Informatics, 10807 pp. 317-330. doi:10.1007/978-3-319-77404-6_24 ISSN 0302-9743.
Chen, Xi, Oliveira, Igor Carboni and Servedio, Rocco A. (2017) Addition is exponentially harder than counting for shallow monotone circuits. In: 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), Montreal, QC, Canada, 19-23 Jun 2017. Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) pp. 1232-1245. ISBN 9781450345286. doi:10.1145/3055399.3055425
Oliveira, Igor Carboni and Santhanam, Rahul (2017) Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In: 32nd Computational Complexity Conference (CCC), Riga, Latvia, 6-9 Jul 2017. Published in: Leibniz International Proceedings in Informatics (LIPIcs) 18:1-18:49. ISBN 9783959770408. doi:10.4230/LIPIcs.CCC.2017.18 ISSN 1868-8969.
Oliveira, Igor Carboni and Santhanam, Rahul (2017) Pseudodeterministic constructions in subexponential time. In: 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), Montreal, QC, Canada, 19-23 Jun 2017. Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing pp. 665-677. ISBN 9781450345286. doi:10.1145/3055399.3055500
Chen, Xi, Oliveira, Igor C., Servedio, Rocco A. and Tan, Li-Yang (2016) Near-optimal small-depth lower bounds for small distance connectivity. In: STOC 2016: 48th Annual Symposium on the Theory of Computing, Cambridge, MA, USA, 19-21 Jun 2016. Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing pp. 612-625. ISBN 9781450341325. doi:10.1145/2897518.2897534
Blais, Eric, Canonne, ClΓ©ment L., Oliveira, Igor C., Servedio, Rocco A. and Tan, Li-Yang (2015) Learning circuits with few negations. In: International Workshop on Randomization and Computation (RANDOM), Princeton, NJ, USA., 24-26 Aug 2015. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 40 pp. 512-527. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.512 ISSN 1868-8969.
Oliveira, Igor C. and Santhanam, Rahul (2015) Majority is incompressible by AC0P circuits. In: Proceedings of the 30th Conference on Computational Complexity, Portland, Oregon, USA., 17-19 Jun 2015. Published in: Leibniz International Proceedings in Informatics (LIPIcs) pp. 124-157. doi:10.4230/LIPIcs.CCC.2015.124 ISSN 1868-8969.
This list was generated on Thu Mar 28 15:41:47 2024 GMT.