default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDEmanuele Viola
Manu Viola
Person information
- affiliation: Northeastern University, Khoury College of Computer Sciences, Boston, MA, USA
- affiliation (PhD 2006): Harvard University, Cambridge, MA, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c51]Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola:
Pseudorandomness, Symmetry, Smoothing: I. CCC 2024: 18:1-18:27- [i95]Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola:
Pseudorandomness, symmetry, smoothing: I. CoRR abs/2405.13143 (2024) - [i94]Peter Ivanov, Emanuele Viola:
Resilient functions: Optimized, simplified, and generalized. CoRR abs/2406.19467 (2024) - [i93]Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola:
Pseudorandomness, symmetry, smoothing: II. CoRR abs/2407.12110 (2024) - [i92]Harm Derksen, Chin Ho Lee, Emanuele Viola:
Boosting uniformity in quasirandom groups: fast and simple. CoRR abs/2409.06932 (2024) - 2023
- [c50]Peter Ivanov, Liam Pavlovic, Emanuele Viola:
On Correlation Bounds Against Polynomials. CCC 2023: 3:1-3:35 - [c49]Emanuele Viola:
New Sampling Lower Bounds via the Separator. CCC 2023: 26:1-26:23 - [c48]Peter Ivanov, Raghu Meka, Emanuele Viola:
Efficient resilient functions. SODA 2023: 2867-2874 - [i91]Peter Ivanov, Liam Pavlovic, Emanuele Viola:
On correlation bounds against polynomials. CoRR abs/2311.09370 (2023) - [i90]Ronen Shaltiel, Emanuele Viola:
On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization. CoRR abs/2311.11663 (2023) - 2022
- [j45]Emanuele Viola:
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines. Theory Comput. 18: 1-12 (2022) - [j44]Xuangui Huang
, Emanuele Viola:
Approximate Degree, Weight, and Indistinguishability. ACM Trans. Comput. Theory 14(1): 3:1-3:26 (2022) - [c47]Xuangui Huang, Peter Ivanov, Emanuele Viola:
Affine Extractors and AC0-Parity. APPROX/RANDOM 2022: 9:1-9:14 - [c46]Harm Derksen, Emanuele Viola:
Fooling polynomials using invariant theory*. FOCS 2022: 399-406 - [c45]W. T. Gowers, Emanuele Viola:
Mixing in Non-Quasirandom Groups. ITCS 2022: 80:1-80:9 - [c44]Ronen Shaltiel, Emanuele Viola:
On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization. ITCS 2022: 116:1-116:17 - [i89]Harm Derksen, Emanuele Viola:
Quasirandom groups enjoy interleaved mixing. Electron. Colloquium Comput. Complex. TR22 (2022) - [i88]Harm Derksen, Emanuele Viola:
Fooling polynomials using invariant theory. Electron. Colloquium Comput. Complex. TR22 (2022) - [i87]Peter Ivanov, Raghu Meka, Emanuele Viola:
Efficient resilient functions. Electron. Colloquium Comput. Complex. TR22 (2022) - [i86]Peter Ivanov, Liam Pavlovic, Emanuele Viola:
On correlation bounds against polynomials. Electron. Colloquium Comput. Complex. TR22 (2022) - [i85]Emanuele Viola:
Correlation bounds against polynomials. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j43]Emanuele Viola:
AC0 Unpredictability. ACM Trans. Comput. Theory 13(1): 5:1-5:8 (2021) - [c43]Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola:
Fourier Growth of Structured 𝔽2-Polynomials and Applications. APPROX-RANDOM 2021: 53:1-53:20 - [c42]Xuangui Huang, Emanuele Viola:
Average-Case Rigidity Lower Bounds. CSR 2021: 186-205 - [c41]Emanuele Viola:
Fourier Conjectures, Correlation Bounds, and Majority. ICALP 2021: 111:1-111:15 - [i84]Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola:
Fourier growth of structured $\mathbb{F}_2$-polynomials and applications. CoRR abs/2107.10797 (2021) - [i83]Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola:
Fourier growth of structured 𝔽2-polynomials and applications. Electron. Colloquium Comput. Complex. TR21 (2021) - [i82]Timothy Gowers, Emanuele Viola:
Mixing in non-quasirandom groups. Electron. Colloquium Comput. Complex. TR21 (2021) - [i81]Xuangui Huang, Peter Ivanov, Emanuele Viola:
Affine extractors and AC0-Parity. Electron. Colloquium Comput. Complex. TR21 (2021) - [i80]Ronen Shaltiel, Emanuele Viola:
On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization. Electron. Colloquium Comput. Complex. TR21 (2021) - [i79]Emanuele Viola:
Lower bounds for samplers and data structures via the cell-probe separator. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j42]Emanuele Viola:
Sampling Lower Bounds: Boolean Average-Case and Permutations. SIAM J. Comput. 49(1): 119-137 (2020) - [j41]Chin Ho Lee, Emanuele Viola:
More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials. Theory Comput. 16: 1-50 (2020) - [c40]Emanuele Viola, Omri Weinstein, Huacheng Yu:
How to Store a Random Walk. SODA 2020: 426-445 - [i78]Xuangui Huang, Emanuele Viola:
Average-case rigidity lower bounds. Electron. Colloquium Comput. Complex. TR20 (2020) - [i77]Emanuele Viola:
New lower bounds for probabilistic degree and AC0 with parity gates. Electron. Colloquium Comput. Complex. TR20 (2020) - [i76]Emanuele Viola:
Fourier conjectures, correlation bounds, and Majority. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j40]W. T. Gowers, Emanuele Viola:
Interleaved Group Products. SIAM J. Comput. 48(2): 554-580 (2019) - [j39]Emanuele Viola:
Guest Column: Non-abelian Combinatorics and Communication Complexity. SIGACT News 50(3): 52-74 (2019) - [j38]Emanuele Viola:
Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds. Theory Comput. 15: 1-9 (2019) - [j37]Emanuele Viola:
Constant-Error Pseudorandomness Proofs from Hardness Require Majority. ACM Trans. Comput. Theory 11(4): 19:1-19:11 (2019) - [j36]Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded Independence versus Symmetric Tests. ACM Trans. Comput. Theory 11(4): 21:1-21:27 (2019) - [i75]Emanuele Viola, Omri Weinstein, Huacheng Yu:
How to Store a Random Walk. CoRR abs/1907.10874 (2019) - [i74]Xuangui Huang, Emanuele Viola:
Approximate Degree-Weight and Indistinguishability. Electron. Colloquium Comput. Complex. TR19 (2019) - [i73]Emanuele Viola:
Pseudorandom bits and lower bounds for randomized Turing machines. Electron. Colloquium Comput. Complex. TR19 (2019) - [i72]Emanuele Viola:
Matching Smolensky's correlation bound with majority. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j35]Emanuele Viola, Avi Wigderson:
Local Expanders. Comput. Complex. 27(2): 225-244 (2018) - [j34]Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Local reduction. Inf. Comput. 261: 281-295 (2018) - [j33]Elad Haramaty, Chin Ho Lee, Emanuele Viola:
Bounded Independence Plus Noise Fools Products. SIAM J. Comput. 47(2): 493-523 (2018) - [j32]Chin Ho Lee, Emanuele Viola:
The Coin Problem for Product Tests. ACM Trans. Comput. Theory 10(3): 14:1-14:10 (2018) - [c39]Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola:
Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs. FOCS 2018: 956-966 - [c38]Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang:
Revisiting Frequency Moment Estimation in Random Order Streams. ICALP 2018: 25:1-25:14 - [i71]Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang:
Revisiting Frequency Moment Estimation in Random Order Streams. CoRR abs/1803.02270 (2018) - [i70]W. T. Gowers, Emanuele Viola:
Interleaved group products. CoRR abs/1804.09787 (2018) - [i69]Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola:
Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. Electron. Colloquium Comput. Complex. TR18 (2018) - [i68]Emanuele Viola:
Sampling lower bounds: boolean average-case and permutations. Electron. Colloquium Comput. Complex. TR18 (2018) - [i67]Emanuele Viola:
Constant-error pseudorandomness proofs from hardness require majority. Electron. Colloquium Comput. Complex. TR18 (2018) - [i66]Emanuele Viola:
Lower bounds for data structures with space close to maximum imply circuit lower bounds. Electron. Colloquium Comput. Complex. TR18 (2018) - [i65]Emanuele Viola:
AC0 unpredictability. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j31]Frederic Green, Daniel Kreymer, Emanuele Viola:
Block-symmetric polynomials correlate with parity better than symmetric. Comput. Complex. 26(2): 323-364 (2017) - [j30]Emanuele Viola:
Selected challenges in computational lower bounds. SIGACT News 48(1): 39-45 (2017) - [j29]Chin Ho Lee, Emanuele Viola:
Some Limitations of the Sum of Small-Bias Distributions. Theory Comput. 13(1): 1-23 (2017) - [c37]Elad Haramaty, Chin Ho Lee, Emanuele Viola:
Bounded Independence Plus Noise Fools Products. CCC 2017: 14:1-14:30 - [i64]Chin Ho Lee, Emanuele Viola:
The coin problem for product tests. Electron. Colloquium Comput. Complex. TR17 (2017) - [i63]Chin Ho Lee, Emanuele Viola:
More on bounded independence plus noise: Pseudorandom generators for read-once polynomials. Electron. Colloquium Comput. Complex. TR17 (2017) - [i62]Emanuele Viola:
A sampling lower bound for permutations. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j28]Zahra Jafargholi, Emanuele Viola:
3SUM, 3XOR, Triangles. Algorithmica 74(1): 326-343 (2016) - [j27]Emanuele Viola:
Quadratic Maps Are Hard to Sample. ACM Trans. Comput. Theory 8(4): 18:1-18:4 (2016) - [c36]Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded Independence vs. Moduli. APPROX-RANDOM 2016: 24:1-24:9 - [c35]Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson:
Bounded Indistinguishability and the Complexity of Recovering Secrets. CRYPTO (3) 2016: 593-618 - [c34]W. T. Gowers, Emanuele Viola:
The Multiparty Communication Complexity of Interleaved Group Products. FOCS 2016: 289-294 - [i61]Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded independence vs. moduli. Electron. Colloquium Comput. Complex. TR16 (2016) - [i60]Timothy Gowers, Emanuele Viola:
The multiparty communication complexity of interleaved group products. Electron. Colloquium Comput. Complex. TR16 (2016) - [i59]Elad Haramaty, Chin Ho Lee, Emanuele Viola:
Bounded independence plus noise fools products. Electron. Colloquium Comput. Complex. TR16 (2016) - [i58]Emanuele Viola, Avi Wigderson:
Local Expanders. Electron. Colloquium Comput. Complex. TR16 (2016) - [i57]Eric Miles, Emanuele Viola:
On the complexity of constructing pseudorandom functions (especially when they don't exist). IACR Cryptol. ePrint Arch. 2016: 343 (2016) - [i56]Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson:
Bounded Indistinguishability and the Complexity of Recovering Secrets. IACR Cryptol. ePrint Arch. 2016: 565 (2016) - 2015
- [j26]Emanuele Viola:
The communication complexity of addition. Comb. 35(6): 703-747 (2015) - [j25]Eric Miles, Emanuele Viola:
Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs. J. ACM 62(6): 46:1-46:29 (2015) - [j24]Eric Miles, Emanuele Viola:
On the Complexity of Constructing Pseudorandom Functions (Especially when They Don't Exist). J. Cryptol. 28(3): 509-532 (2015) - [c33]Oded Goldreich, Emanuele Viola, Avi Wigderson:
On Randomness Extraction in AC0. CCC 2015: 601-668 - [c32]Hamid Jahanjou, Eric Miles, Emanuele Viola:
Local Reductions. ICALP (1) 2015: 749-760 - [c31]Timothy Gowers, Emanuele Viola:
The communication complexity of interleaved group products. STOC 2015: 351-360 - [i55]Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson:
Bounded Indistinguishability and the Complexity of Recovering Secrets. Electron. Colloquium Comput. Complex. TR15 (2015) - [i54]Oded Goldreich, Emanuele Viola, Avi Wigderson:
On Randomness Extraction in AC0. Electron. Colloquium Comput. Complex. TR15 (2015) - [i53]Timothy Gowers, Emanuele Viola:
The communication complexity of interleaved group products. Electron. Colloquium Comput. Complex. TR15 (2015) - [i52]Chin Ho Lee, Emanuele Viola:
Some limitations of the sum of small-bias distributions. Electron. Colloquium Comput. Complex. TR15 (2015) - [i51]Emanuele Viola:
Quadratic maps are hard to sample. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j23]Emanuele Viola:
Randomness Buys Depth for Approximate Counting. Comput. Complex. 23(3): 479-508 (2014) - [j22]Emanuele Viola:
Extractors for Circuit Sources. SIAM J. Comput. 43(2): 655-672 (2014) - [c30]Eli Ben-Sasson, Emanuele Viola:
Short PCPs with Projection Queries. ICALP (1) 2014: 163-173 - [i50]Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun, Emanuele Viola:
Global Information Sharing under Network Dynamics. CoRR abs/1409.7771 (2014) - [i49]Eli Ben-Sasson, Emanuele Viola:
Short PCPs with projection queries. Electron. Colloquium Comput. Complex. TR14 (2014) - [i48]Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Succinct and explicit circuits for sorting and connectivity. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j21]Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola:
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates. IEEE Trans. Inf. Theory 59(10): 6611-6627 (2013) - [j20]Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
On Beating the Hybrid Argument. Theory Comput. 9: 809-843 (2013) - [j19]Alexander A. Razborov, Emanuele Viola:
Real Advantage. ACM Trans. Comput. Theory 5(4): 17:1-17:8 (2013) - [c29]Emanuele Viola:
The communication complexity of addition. SODA 2013: 632-651 - [c28]Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun, Emanuele Viola:
On the Complexity of Information Spreading in Dynamic Networks. SODA 2013: 717-736 - [c27]Eric Miles, Emanuele Viola:
Shielding circuits with groups. STOC 2013: 251-260 - [i47]Zahra Jafargholi, Emanuele Viola:
3SUM, 3XOR, Triangles. CoRR abs/1305.3827 (2013) - [i46]Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Local reductions. CoRR abs/1311.3171 (2013) - [i45]Emanuele Viola:
Challenges in computational lower bounds. CoRR abs/1311.5467 (2013) - [i44]Zahra Jafargholi, Emanuele Viola:
3SUM, 3XOR, Triangles. Electron. Colloquium Comput. Complex. TR13 (2013) - [i43]Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Local reductions. Electron. Colloquium Comput. Complex. TR13 (2013) - [i42]Eric Miles, Emanuele Viola:
Shielding circuits with groups. Electron. Colloquium Comput. Complex. TR13 (2013) - [i41]Emanuele Viola:
Challenges in computational lower bounds. Electron. Colloquium Comput. Complex. TR13 (2013) - [i40]Eric Miles, Emanuele Viola:
Shielding circuits with groups. IACR Cryptol. ePrint Arch. 2013: 1 (2013) - 2012
- [j18]Shachar Lovett, Emanuele Viola:
Bounded-Depth Circuits Cannot Sample Good Codes. Comput. Complex. 21(2): 245-266 (2012) - [j17]Emanuele Viola:
The Complexity of Distributions. SIAM J. Comput. 41(1): 191-218 (2012) - [j16]Emanuele Viola:
Bit-Probe Lower Bounds for Succinct Data Structures. SIAM J. Comput. 41(6): 1593-1604 (2012) - [c26]Emanuele Viola:
Extractors for Turing-Machine Sources. APPROX-RANDOM 2012: 663-671 - [c25]Eric Miles, Emanuele Viola:
Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs. CRYPTO 2012: 68-85 - [c24]Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
On beating the hybrid argument. ITCS 2012: 468-483 - [c23]Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola:
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. STOC 2012: 479-494 - [i39]Frederic Green, Daniel Kreymer, Emanuele Viola:
Block-symmetric polynomials correlate with parity better than symmetric. Electron. Colloquium Comput. Complex. TR12 (2012) - [i38]Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola:
From RAM to SAT. Electron. Colloquium Comput. Complex. TR12 (2012) - [i37]Eric Miles, Emanuele Viola:
On the complexity of constructing pseudorandom functions (especially when they don't exist). Electron. Colloquium Comput. Complex. TR12 (2012) - [i36]Alexander A. Razborov, Emanuele Viola:
Real Advantage. Electron. Colloquium Comput. Complex. TR12 (2012) - [i35]Rocco A. Servedio, Emanuele Viola:
On a special case of rigidity. Electron. Colloquium Comput. Complex. TR12 (2012) - [i34]Emanuele Viola:
Extractors for Turing-machine sources. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j15]Scott Aaronson, Jeff Erickson, Mohammad Mahdian, R. Ravi, Emanuele Viola:
Special Section on Foundations of Computer Science. SIAM J. Comput. 40(3): 770 (2011) - [j14]Emanuele Viola:
Selected Results in Additive Combinatorics: An Exposition. Theory Comput. 3: 1-15 (2011) - [c22]Shachar Lovett, Emanuele Viola:
Bounded-Depth Circuits Cannot Sample Good Codes. CCC 2011: 243-251 - [c21]Emanuele Viola:
Extractors for Circuit Sources. FOCS 2011: 220-229 - [c20]Emanuele Viola:
Randomness Buys Depth for Approximate Counting. FOCS 2011: 230-239 - [c19]Eric Miles, Emanuele Viola:
On the Complexity of Non-adaptively Increasing the Stretch of Pseudorandom Generators. TCC 2011: 522-539 - [i33]