


Остановите войну!
for scientists:
Emanuele 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(