Stop the war!Остановите войну!
for scientists:
Google
Google Scholar
Semantic Scholar
IA Scholar
CiteSeerX
ORCIDEmanuele Viola
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2022
[j44]Xuangui Huang
, Emanuele Viola:
Approximate Degree, Weight, and Indistinguishability. ACM Trans. Comput. Theory 14(1): 3:1-3:26 (2022)- [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 - 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]Timothy Gowers, Emanuele Viola:
Mixing in non-quasirandom groups. Electron. Colloquium Comput. Complex. 28: 17 (2021) - [i82]Emanuele Viola:
Lower bounds for samplers and data structures via the cell-probe separator. Electron. Colloquium Comput. Complex. 28: 73 (2021) - [i81]Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola:
Fourier growth of structured $\mathbb{F}_2$-polynomials and applications. Electron. Colloquium Comput. Complex. 28: 110 (2021) - [i80]Xuangui Huang, Peter Ivanov, Emanuele Viola:
Affine extractors and AC0-Parity. Electron. Colloquium Comput. Complex. 28: 137 (2021) - [i79]Ronen Shaltiel, Emanuele Viola:
On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization. Electron. Colloquium Comput. Complex. 28: 153 (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]Emanuele Viola:
New lower bounds for probabilistic degree and AC0 with parity gates. Electron. Colloquium Comput. Complex. 27: 15 (2020) - [i77]Emanuele Viola:
Fourier conjectures, correlation bounds, and Majority. Electron. Colloquium Comput. Complex. 27: 175 (2020) - [i76]Xuangui Huang, Emanuele Viola:
Average-case rigidity lower bounds. Electron. Colloquium Comput. Complex. 27: 193 (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]Emanuele Viola:
Pseudorandom bits and lower bounds for randomized Turing machines. Electron. Colloquium Comput. Complex. 26: 51 (2019) - [i73]Xuangui Huang, Emanuele Viola:
Approximate Degree-Weight and Indistinguishability. Electron. Colloquium Comput. Complex. 26: 85 (2019) - [i72]Emanuele Viola:
Matching Smolensky's correlation bound with majority. Electron. Colloquium Comput. Complex. 26: 175 (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]Emanuele Viola:
Sampling lower bounds: boolean average-case and permutations. Electron. Colloquium Comput. Complex. 25: 60 (2018) - [i68]Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola:
Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. Electron. Colloquium Comput. Complex. 25: 61 (2018) - [i67]Emanuele Viola:
Constant-error pseudorandomness proofs from hardness require majority. Electron. Colloquium Comput. Complex. 25: 133 (2018) - [i66]Emanuele Viola:
Lower bounds for data structures with space close to maximum imply circuit lower bounds. Electron. Colloquium Comput. Complex. 25: 186 (2018) - [i65]Emanuele Viola:
AC0 unpredictability. Electron. Colloquium Comput. Complex. 25: 209 (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. Computational Complexity Conference 2017: 14:1-14:30 - [i64]Chin Ho Lee, Emanuele Viola:
The coin problem for product tests. Electron. Colloquium Comput. Complex. 24: 90 (2017) - [i63]Emanuele Viola:
A sampling lower bound for permutations. Electron. Colloquium Comput. Complex. 24: 166 (2017) - [i62]Chin Ho Lee, Emanuele Viola:
More on bounded independence plus noise: Pseudorandom generators for read-once polynomials. Electron. Colloquium Comput. Complex. 24: 167 (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. 23: 102 (2016) - [i60]Timothy Gowers, Emanuele Viola:
The multiparty communication complexity of interleaved group products. Electron. Colloquium Comput. Complex. 23: 127 (2016) - [i59]Emanuele Viola, Avi Wigderson:
Local Expanders. Electron. Colloquium Comput. Complex. 23: 129 (2016) - [i58]Elad Haramaty, Chin Ho Lee, Emanuele Viola:
Bounded independence plus noise fools products. Electron. Colloquium Comput. Complex. 23: 169 (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. Computational Complexity Conference 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]Oded Goldreich, Emanuele Viola, Avi Wigderson:
On Randomness Extraction in AC0. Electron. Colloquium Comput. Complex. 22: 3 (2015) - [i54]Chin Ho Lee, Emanuele Viola:
Some limitations of the sum of small-bias distributions. Electron. Colloquium Comput. Complex. 22: 5 (2015) - [i53]Timothy Gowers, Emanuele Viola:
The communication complexity of interleaved group products. Electron. Colloquium Comput. Complex. 22: 44 (2015) - [i52]Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson:
Bounded Indistinguishability and the Complexity of Recovering Secrets. Electron. Colloquium Comput. Complex. 22: 182 (2015) - [i51]Emanuele Viola:
Quadratic maps are hard to sample. Electron. Colloquium Comput. Complex. 22: 205 (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. 21: 17 (2014) - [i48]Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Succinct and explicit circuits for sorting and connectivity. Electron. Colloquium Comput. Complex. 21: 37 (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]Eric Miles, Emanuele Viola:
Shielding circuits with groups. Electron. Colloquium Comput. Complex. 20: 3 (2013) - [i43]Zahra Jafargholi, Emanuele Viola:
3SUM, 3XOR, Triangles. Electron. Colloquium Comput. Complex. 20: 9 (2013) - [i42]Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Local reductions. Electron. Colloquium Comput. Complex. 20: 99 (2013) - [i41]Emanuele Viola:
Challenges in computational lower bounds. Electron. Colloquium Comput. Complex. 20: 119 (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]Eric Miles, Emanuele Viola:
On the complexity of constructing pseudorandom functions (especially when they don't exist). Electron. Colloquium Comput. Complex. 19: 19 (2012) - [i38]Emanuele Viola:
Extractors for Turing-machine sources. Electron. Colloquium Comput. Complex. 19: 47 (2012) - [i37]Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola:
From RAM to SAT. Electron. Colloquium Comput. Complex. 19: 125 (2012) - [i36]Alexander A. Razborov, Emanuele Viola:
Real Advantage. Electron. Colloquium Comput. Complex. 19: 134 (2012) - [i35]Rocco A. Servedio, Emanuele Viola:
On a special case of rigidity. Electron. Colloquium Comput. Complex. 19: 144 (2012) - [i34]Frederic Green, Daniel Kreymer, Emanuele Viola:
Block-symmetric polynomials correlate with parity better than symmetric. Electron. Colloquium Comput. Complex. 19: 160 (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. Computational Complexity Conference 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]Frederic Green, Daniel Kreymer, Emanuele Viola:
In Brute-Force Search of Correlation Bounds for Polynomials. Electron. Colloquium Comput. Complex. 18: 39 (2011) - [i32]Emanuele Viola:
Extractors for circuit sources. Electron. Colloquium Comput. Complex. 18: 56 (2011) - [i31]Eric Miles, Emanuele Viola:
The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs. Electron. Colloquium Comput. Complex. 18: 76 (2011) - [i30]Emanuele Viola:
Reducing 3XOR to listing triangles, an exposition. Electron. Colloquium Comput. Complex. 18: 113 (2011) - [i29]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. Electron. Colloquium Comput. Complex. 18: 150 (2011) - [i28]Emanuele Viola:
The communication complexity of addition. Electron. Colloquium Comput. Complex. 18: 152 (2011) - [i27]Eric Miles, Emanuele Viola:
The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs. IACR Cryptol. ePrint Arch. 2011: 226 (2011) - 2010
- [j13]Andrej Bogdanov, Emanuele Viola:
Pseudorandom Bits for Polynomials. SIAM J. Comput. 39(6): 2464-2486 (2010) - [j12]Ronen Shaltiel, Emanuele Viola:
Hardness Amplification Proofs Require Majority. SIAM J. Comput. 39(7): 3122-3154 (2010) - [j11]Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
Bounded Independence Fools Halfspaces. SIAM J. Comput. 39(8): 3441-3462 (2010) - [c18]Emanuele Viola:
The Complexity of Distributions. FOCS 2010: 202-211 - [c17]Mihai Patrascu, Emanuele Viola:
Cell-Probe Lower Bounds for Succinct Partial Sums. SODA 2010: 117-122 - [i26]Jasmina Hasanhodzic, Andrew W. Lo, Emanuele Viola:
Is It Real, or Is It Randomized?: A Financial Turing Test. CoRR abs/1002.4592 (2010) - [i25]Shachar Lovett, Emanuele Viola:
Bounded-depth circuits cannot sample good codes. Electron. Colloquium Comput. Complex. 17: 115 (2010) - [i24]Emanuele Viola:
Randomness buys depth for approximate counting. Electron. Colloquium Comput. Complex. 17: 175 (2010) - [i23]Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
On beating the hybrid argument. Electron. Colloquium Comput. Complex. 17: 186 (2010)
2000 – 2009
- 2009
- [j10]Emanuele Viola:
The Sum of D Small-Bias Generators Fools Polynomials of Degree D. Comput. Complex. 18(2): 209-217 (2009) - [j9]Emanuele Viola:
On Approximate Majority and Probabilistic Time. Comput. Complex. 18(3): 337-375 (2009) - [j8]Emanuele Viola, Avi Wigderson:
One-way multiparty communication lower bound for pointer jumping with applications. Comb. 29(6): 719-743 (2009) - [j7]Emanuele Viola:
On the Power of Small-Depth Computation. Found. Trends Theor. Comput. Sci. 5(1): 1-72 (2009) - [j6]Emanuele Viola:
Guest Column: correlation bounds for polynomials over {0 1}. SIGACT News 40(1): 27-44 (2009) - [j5]Matei David, Toniann Pitassi, Emanuele Viola:
Improved Separations between Nondeterministic and Randomized Multiparty Communication. ACM Trans. Comput. Theory 1(