Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDIrit Dinur
Person information
- affiliation: Weizmann Institute of Science, Rehovot, Israel
- award (2019): Gödel Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[i66]Ron Asherov, Irit Dinur:
Bipartite unique-neighbour expanders via Ramanujan graphs. CoRR abs/2301.03072 (2023)- 2022
- [c49]Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff:
A Characterization of Multiclass Learnability. FOCS 2022: 943-955 - [c48]Irit Dinur:
Expanders in Higher Dimensions (Invited Talk). FSTTCS 2022: 4:1-4:1 - [c47]Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes:
Locally testable codes with constant rate, distance, and locality. STOC 2022: 357-374 - [i65]Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff:
A Characterization of Multiclass Learnability. CoRR abs/2203.01550 (2022) - [i64]Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes:
Good Locally Testable Codes. CoRR abs/2207.11929 (2022) - [i63]Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff:
A Characterization of Multiclass Learnability. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j21]Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma
:
List-Decoding with Double Samplers. SIAM J. Comput. 50(2): 301-349 (2021) - [c46]Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani:
Explicit SoS Lower Bounds from High-Dimensional Expanders. ITCS 2021: 38:1-38:16 - [i62]Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes:
Locally Testable Codes with constant rate, distance, and locality. CoRR abs/2111.04808 (2021) - [i61]Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes:
Locally Testable Codes with constant rate, distance, and locality. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [i60]Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi:
Locally testable codes via high-dimensional expanders. CoRR abs/2005.01045 (2020) - [i59]Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani:
Explicit SoS lower bounds from high-dimensional expanders. CoRR abs/2009.05218 (2020) - [i58]Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi:
Locally testable codes via high-dimensional expanders. Electron. Colloquium Comput. Complex. TR20 (2020) - [i57]Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani:
Explicit and structured sum of squares lower bounds from high dimensional expanders. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j20]Irit Dinur, Or Meir, Swastik Kopparty:
Special Section on the Fifty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016). SIAM J. Comput. 48(2): 451 (2019) - [c45]Irit Dinur, Konstantin Golubev:
Direct Sum Testing: The General Case. APPROX-RANDOM 2019: 40:1-40:11 - [c44]Yotam Dikstein, Irit Dinur:
Agreement Testing Theorems on Layered Set Systems. FOCS 2019: 1495-1524 - [c43]Irit Dinur, Prahladh Harsha, Tali Kaufman, Noga Ron-Zewi:
From Local to Robust Testing via Agreement Testing. ITCS 2019: 29:1-29:18 - [c42]Irit Dinur, Oded Goldreich, Tom Gur:
Every Set in P Is Strongly Testable Under a Suitable Encoding. ITCS 2019: 30:1-30:17 - [c41]Irit Dinur, Yuval Filmus, Prahladh Harsha:
Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract]. SODA 2019: 2124-2133 - [c40]Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma:
List Decoding with Double Samplers. SODA 2019: 2134-2153 - [i56]Irit Dinur, Konstantin Golubev:
Testing tensor products. CoRR abs/1904.12747 (2019) - [i55]Yotam Dikstein, Irit Dinur:
Agreement testing theorems on layered set systems. CoRR abs/1909.00638 (2019) - [i54]Yotam Dikstein, Irit Dinur:
Agreement testing theorems on layered set systems. Electron. Colloquium Comput. Complex. TR19 (2019) - [i53]Irit Dinur, Konstantin Golubev:
Direct sum testing - the general case. Electron. Colloquium Comput. Complex. TR19 (2019) - [i52]Irit Dinur, Roy Meshulam:
Near Coverings and Cosystolic Expansion - an example of topological property testing. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j19]Irit Dinur, Or Meir:
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. Comput. Complex. 27(3): 375-462 (2018) - [c39]Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha:
Boolean Function Analysis on High-Dimensional Expanders. APPROX-RANDOM 2018: 38:1-38:20 - [c38]Irit Dinur, Pasin Manurangsi:
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. ITCS 2018: 36:1-36:20 - [c37]Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra:
Towards a proof of the 2-to-1 games conjecture? STOC 2018: 376-389 - [c36]Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra:
On non-optimally expanding sets in Grassmann graphs. STOC 2018: 940-951 - [i51]Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha:
Boolean functions on high-dimensional expanders. CoRR abs/1804.08155 (2018) - [i50]Irit Dinur, Pasin Manurangsi:
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. CoRR abs/1805.03867 (2018) - [i49]Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma:
List Decoding with Double Samplers. CoRR abs/1808.00425 (2018) - [i48]Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha:
Boolean function analysis on high-dimensional expanders. Electron. Colloquium Comput. Complex. TR18 (2018) - [i47]Irit Dinur, Oded Goldreich, Tom Gur:
Every set in P is strongly testable under a suitable encoding. Electron. Colloquium Comput. Complex. TR18 (2018) - [i46]Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma:
List Decoding with Double Samplers. Electron. Colloquium Comput. Complex. TR18 (2018) - [i45]Irit Dinur, Tali Kaufman, Noga Ron-Zewi:
From Local to Robust Testing via Agreement Testing. Electron. Colloquium Comput. Complex. TR18 (2018) - [i44]Irit Dinur, Pasin Manurangsi:
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j18]Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar:
Direct Sum Testing. SIAM J. Comput. 46(4): 1336-1369 (2017) - [c35]Irit Dinur, Inbal Livni Navon:
Exponentially Small Soundness for the Direct Product Z-Test. Computational Complexity Conference 2017: 29:1-29:50 - [c34]Irit Dinur, Tali Kaufman:
High Dimensional Expanders Imply Agreement Expanders. FOCS 2017: 974-985 - [c33]Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen:
Multiplayer Parallel Repetition for Expanding Games. ITCS 2017: 37:1-37:16 - [c32]Amey Bhangale, Irit Dinur, Inbal Livni Navon:
Cube vs. Cube Low Degree Test. ITCS 2017: 40:1-40:31 - [i43]Irit Dinur, Yuval Filmus, Prahladh Harsha:
Agreement tests on graphs and hypergraphs. CoRR abs/1711.09426 (2017) - [i42]Irit Dinur, Yuval Filmus, Prahladh Harsha:
Low degree almost Boolean functions are sparse juntas. CoRR abs/1711.09428 (2017) - [i41]Irit Dinur, Yuval Filmus, Prahladh Harsha:
Low degree almost Boolean functions are sparse juntas. Electron. Colloquium Comput. Complex. TR17 (2017) - [i40]Irit Dinur, Yuval Filmus, Prahladh Harsha:
Agreement tests on graphs and hypergraphs. Electron. Colloquium Comput. Complex. TR17 (2017) - [i39]Irit Dinur, Tali Kaufman:
High dimensional expanders imply agreement expanders. Electron. Colloquium Comput. Complex. TR17 (2017) - [i38]Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra:
On Non-Optimally Expanding Sets in Grassmann Graphs. Electron. Colloquium Comput. Complex. TR17 (2017) - [i37]Irit Dinur, Inbal Livni Navon:
Exponentially Small Soundness for the Direct Product Z-test. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [c31]Irit Dinur, Or Meir:
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. Computational Complexity Conference 2016: 3:1-3:51 - [e2]Irit Dinur:
IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA. IEEE Computer Society 2016, ISBN 978-1-5090-3933-3 [contents] - [i36]Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen:
Multiplayer parallel repetition for expander games. CoRR abs/1610.08349 (2016) - [i35]Amey Bhangale, Irit Dinur, Inbal Livni Navon:
Cube vs. Cube Low Degree Test. CoRR abs/1612.07491 (2016) - [i34]Amey Bhangale, Irit Dinur, Inbal Livni Navon:
Cube vs. Cube Low Degree Test. Electron. Colloquium Comput. Complex. TR16 (2016) - [i33]Irit Dinur:
Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electron. Colloquium Comput. Complex. TR16 (2016) - [i32]Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen:
Multiplayer parallel repetition for expander games. Electron. Colloquium Comput. Complex. TR16 (2016) - [i31]Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra:
Towards a Proof of the 2-to-1 Games Conjecture? Electron. Colloquium Comput. Complex. TR16 (2016) - [i30]Irit Dinur, Or Meir:
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j17]Irit Dinur, David Steurer, Thomas Vidick:
A parallel repetition theorem for entangled projection games. Comput. Complex. 24(2): 201-254 (2015) - [c30]Irit Dinur, Shafi Goldwasser, Huijia Lin:
The Computational Benefit of Correlated Instances. ITCS 2015: 219-228 - [c29]Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar:
Direct Sum Testing. ITCS 2015: 327-336 - [c28]Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma:
Derandomized Graph Product Results Using the Low Degree Long Code. STACS 2015: 275-287 - [c27]Irit Dinur, Prahladh Harsha, Guy Kindler:
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition. STOC 2015: 267-276 - [i29]Irit Dinur, Prahladh Harsha, Guy Kindler:
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition. CoRR abs/1505.06362 (2015) - [i28]Irit Dinur, Prahladh Harsha, Guy Kindler:
Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c26]Irit Dinur, David Steurer:
Direct Product Testing. Computational Complexity Conference 2014: 188-196 - [c25]Irit Dinur, David Steurer, Thomas Vidick:
A Parallel Repetition Theorem for Entangled Projection Games. Computational Complexity Conference 2014: 197-208 - [c24]Irit Dinur, David Steurer:
Analytical approach to parallel repetition. STOC 2014: 624-633 - [i27]Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma:
Derandomized Graph Product Results using the Low Degree Long Code. CoRR abs/1411.3517 (2014) - [i26]Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar:
Direct Sum Testing. Electron. Colloquium Comput. Complex. TR14 (2014) - [i25]Irit Dinur, Shafi Goldwasser, Huijia Lin:
The Computational Benefit of Correlated Instances. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j16]Boaz Barak, Irit Dinur:
Special Issue "Conference on Computational Complexity 2012" Guest editors' foreword. Comput. Complex. 22(2): 215-217 (2013) - [j15]Irit Dinur, Prahladh Harsha:
Composition of Low-Error 2-Query PCPs Using Decodable PCPs. SIAM J. Comput. 42(6): 2452-2486 (2013) - [c23]Irit Dinur, Gillat Kol:
Covering CSPs. Computational Complexity Conference 2013: 207-218 - [c22]Irit Dinur, Venkatesan Guruswami:
PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring. FOCS 2013: 340-349 - [c21]Irit Dinur, Elazar Goldenberg:
Clustering in the Boolean Hypercube in a List Decoding Regime. ICALP (1) 2013: 413-424 - [i24]Irit Dinur, David Steurer:
Analytical Approach to Parallel Repetition. CoRR abs/1305.1979 (2013) - [i23]Irit Dinur, David Steurer, Thomas Vidick:
A parallel repetition theorem for entangled projection games. CoRR abs/1310.4113 (2013) - [i22]Irit Dinur, Elazar Goldenberg:
Clustering in the Boolean Hypercube in a List Decoding Regime. Electron. Colloquium Comput. Complex. TR13 (2013) - [i21]Irit Dinur, Venkatesan Guruswami:
PCPs via low-degree long code and hardness for constrained hypergraph coloring. Electron. Colloquium Comput. Complex. TR13 (2013) - [i20]Irit Dinur, Igor Shinkar:
On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors. Electron. Colloquium Comput. Complex. TR13 (2013) - [i19]Irit Dinur, David Steurer:
Direct Product Testing. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [i18]Irit Dinur, Gillat Kol:
Covering CSPs. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j14]Irit Dinur, Or Meir:
Derandomized Parallel Repetition via Structured PCPs. Comput. Complex. 20(2): 207-327 (2011) - [j13]Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra:
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. Comput. Complex. 20(3): 413-504 (2011) - [c20]Irit Dinur, Tali Kaufman:
Dense Locally Testable Codes Cannot Have Constant Rate and Distance. APPROX-RANDOM 2011: 507-518 - [i17]Irit Dinur, Tali Kaufman:
Dense locally testable codes cannot have constant rate and distance. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [c19]Irit Dinur, Igor Shinkar:
On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors. APPROX-RANDOM 2010: 138-151 - [c18]Irit Dinur, Elazar Goldenberg:
The Structure of Winning Strategies in Parallel Repetition Games. APPROX-RANDOM 2010: 518-530 - [c17]Irit Dinur, Or Meir:
Derandomized Parallel Repetition of Structured PCPs. Computational Complexity Conference 2010: 16-27 - [c16]Irit Dinur, Subhash Khot, Will Perkins, Muli Safra:
Hardness of Finding Independent Sets in Almost 3-Colorable Graphs. FOCS 2010: 212-221 - [p1]Irit Dinur, Prahladh Harsha:
Composition of Low-Error 2-Query PCPs Using Decodable PCPs. Property Testing 2010: 280-288 - [i16]Irit Dinur, Or Meir:
Derandomized Parallel Repetition of Structured PCPs. CoRR abs/1002.1606 (2010) - [i15]Irit Dinur, Tali Kaufman:
Dense locally testable codes cannot have constant rate and distance. CoRR abs/1012.2738 (2010) - [i14]Irit Dinur, Or Meir:
Derandomized Parallel Repetition via Structured PCPs. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j12]Irit Dinur, Ehud Friedgut:
Intersecting Families are Essentially Contained in Juntas. Comb. Probab. Comput. 18(1-2): 107-122 (2009) - [j11]Irit Dinur, Elchanan Mossel, Oded Regev:
Conditional Hardness for Approximate Coloring. SIAM J. Comput. 39(3): 843-873 (2009) - [c15]Irit Dinur, Prahladh Harsha:
Composition of Low-Error 2-Query PCPs Using Decodable PCPs. FOCS 2009: 472-481 - [e1]Irit Dinur, Klaus Jansen, Joseph Naor, José D. P. Rolim:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings. Lecture Notes in Computer Science 5687, Springer 2009, ISBN 978-3-642-03684-2 [contents] - [i13]Irit Dinur, Prahladh Harsha:
Composition of low-error 2-query PCPs using decodable PCPs. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j10]Irit Dinur, Éva Tardos:
Special Issue on Foundations of Computer Science. SIAM J. Comput. 37(6) (2008) - [j9]Irit Dinur:
PCPs with small soundness error. SIGACT News 39(3): 41-57 (2008) - [c14]Irit Dinur, Elazar Goldenberg:
Locally Testing Direct Product in the Low Error Range. FOCS 2008: 613-622 - [c13]Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan:
Decodability of group homomorphisms beyond the johnson bound. STOC 2008: 275-284 - [i12]Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan:
Decodability of Group Homomorphisms beyond the Johnson Bound. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j8]Irit Dinur:
The PCP theorem by gap amplification. J. ACM 54(3): 12 (2007) - 2006
- [j7]Irit Dinur, Ehud Friedgut:
Proof of an Intersection Theorem via Graph Homomorphisms. Electron. J. Comb. 13(1) (2006) - [j6]Irit Dinur, Omer Reingold:
Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem. SIAM J. Comput. 36(4): 975-1024 (2006) - [c12]Irit Dinur, Madhu Sudan, Avi Wigderson:
Robust Local Testability of Tensor Products of LDPC Codes. APPROX-RANDOM 2006: 304-315 - [c11]Irit Dinur:
The PCP theorem by gap amplification. STOC 2006: 241-250 - [c10]Irit Dinur, Elchanan Mossel, Oded Regev:
Conditional hardness for approximate coloring. STOC 2006: 344-353 - [c9]Irit Dinur, Ehud Friedgut, Guy Kindler, Ryan O'Donnell:
On the fourier tails of bounded functions over the discrete cube. STOC 2006: 437-446 - [i11]Irit Dinur, Madhu Sudan, Avi Wigderson:
Robust Local Testability of Tensor Products of LDPC Codes. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j5]Irit Dinur, Oded Regev, Clifford D. Smyth:
The Hardness of 3-Uniform Hypergraph Coloring. Comb. 25(5): 519-535 (2005) - [j4]Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev:
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. SIAM J. Comput. 34(5): 1129-1146 (2005) - [i10]Irit Dinur, Elchanan Mossel, Oded Regev:
Conditional Hardness for Approximate Coloring. CoRR abs/cs/0504062 (2005) - [i9]Irit Dinur, Elchanan Mossel, Oded Regev:
Conditional Hardness for Approximate Coloring. Electron. Colloquium Comput. Complex. TR05 (2005) - [i8]Irit Dinur:
The PCP theorem by gap amplification. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j3]Irit Dinur, Shmuel Safra:
On the hardness of approximating label-cover. Inf. Process. Lett. 89(5): 247-254 (2004) - [c8]Irit Dinur, Omer Reingold:
Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem. FOCS 2004: 155-164 - 2003
- [j2]Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra:
Approximating CVP to Within Almost-Polynomial Factors is NP-Hard. Comb. 23(2): 205-243 (2003) - [c7]Irit Dinur, Kobbi Nissim:
Revealing information while preserving privacy.