![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
Or Meir
Person information
- affiliation: University of Haifa, Department of Computer Science, Israel
- affiliation: Weizmann Institute of Science, Rehovot, Israel
Refine list
![note](https://dblp.dagstuhl.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [j21]Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere:
KRW Composition Theorems via Lifting. Comput. Complex. 33(1): 4 (2024) - [i36]Yahel Manor, Or Meir:
Lifting with Inner Functions of Polynomial Discrepancy. CoRR abs/2404.07606 (2024) - [i35]Yahel Manor, Or Meir:
Lifting with Inner Functions of Polynomial Discrepancy. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [c16]Or Meir:
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition. FOCS 2023: 1056-1081 - [i34]Or Meir:
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition. CoRR abs/2306.00615 (2023) - [i33]Or Meir:
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [c15]Yahel Manor, Or Meir
:
Lifting with Inner Functions of Polynomial Discrepancy. APPROX/RANDOM 2022: 26:1-26:17 - 2021
- [j20]Susanna F. de Rezende
, Or Meir, Jakob Nordström, Robert Robere:
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. Comput. Complex. 30(1): 4 (2021) - [j19]Arkadev Chattopadhyay, Yuval Filmus
, Sajin Koroth, Or Meir, Toniann Pitassi:
Query-to-Communication Lifting Using Low-Discrepancy Gadgets. SIAM J. Comput. 50(1): 171-210 (2021) - [c14]Yuval Filmus
, Or Meir
, Avishay Tal
:
Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). ITCS 2021: 89:1-89:7 - 2020
- [j18]Or Meir:
Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation. Comput. Complex. 29(1): 4 (2020) - [c13]Susanna F. de Rezende
, Or Meir, Jakob Nordström
, Toniann Pitassi, Robert Robere, Marc Vinyals
:
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. FOCS 2020: 24-30 - [c12]Susanna F. de Rezende
, Or Meir, Jakob Nordström
, Toniann Pitassi, Robert Robere:
KRW Composition Theorems via Lifting. FOCS 2020: 43-49 - [p1]Oded Goldreich, Or Meir:
Bridging a Small Gap in the Gap Amplification of Assignment Testers. Computational Complexity and Property Testing 2020: 9-16 - [i32]Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals:
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. CoRR abs/2001.02144 (2020) - [i31]Susanna F. de Rezende, Or Meir, Jakob Nordström, Robert Robere:
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. CoRR abs/2001.02481 (2020) - [i30]Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere:
KRW Composition Theorems via Lifting. CoRR abs/2007.02740 (2020) - [i29]Yuval Filmus, Or Meir, Avishay Tal:
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0. CoRR abs/2012.02210 (2020) - [i28]Yuval Filmus, Or Meir, Avishay Tal:
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0. Electron. Colloquium Comput. Complex. TR20 (2020) - [i27]Or Meir, Jakob Nordström, Robert Robere, Susanna F. de Rezende:
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. Electron. Colloquium Comput. Complex. TR20 (2020) - [i26]Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere:
KRW Composition Theorems via Lifting. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j17]Or Meir, Avi Wigderson:
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds. Comput. Complex. 28(2): 145-183 (2019) - [j16]Or Meir:
On Derandomized Composition of Boolean Functions. Comput. Complex. 28(4): 661-708 (2019) - [j15]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) - [c11]Susanna F. de Rezende
, Jakob Nordström
, Or Meir, Robert Robere:
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. CCC 2019: 18:1-18:16 - [c10]Arkadev Chattopadhyay, Yuval Filmus
, Sajin Koroth
, Or Meir
, Toniann Pitassi
:
Query-To-Communication Lifting for BPP Using Inner Product. ICALP 2019: 35:1-35:15 - [i25]Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi:
Query-to-communication lifting for BPP using inner product. CoRR abs/1904.13056 (2019) - [i24]Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi:
Query-to-Communication Lifting Using Low-Discrepancy Gadgets. Electron. Colloquium Comput. Complex. TR19 (2019) - [i23]Or Meir:
Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation. Electron. Colloquium Comput. Complex. TR19 (2019) - [i22]Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna F. de Rezende:
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j14]Irit Dinur
, Or Meir:
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. Comput. Complex. 27(3): 375-462 (2018) - [j13]Or Meir
, Avishay Tal:
The choice and agreement problems of a random function. Inf. Process. Lett. 133: 16-20 (2018) - [j12]Or Meir
:
The direct sum of universal relations. Inf. Process. Lett. 136: 105-111 (2018) - [c9]Sajin Koroth, Or Meir:
Improved Composition Theorems for Functions and Relations. APPROX-RANDOM 2018: 48:1-48:18 - 2017
- [j11]Swastik Kopparty, Or Meir, Noga Ron-Zewi
, Shubhangi Saraf:
High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity. J. ACM 64(2): 11:1-11:42 (2017) - [j10]Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson:
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. SIAM J. Comput. 46(1): 114-131 (2017) - [i21]Or Meir:
The Direct Sum of Universal Relations. Electron. Colloquium Comput. Complex. TR17 (2017) - [i20]Or Meir:
An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds. Electron. Colloquium Comput. Complex. TR17 (2017) - [i19]Or Meir:
On Derandomized Composition of Boolean Functions. Electron. Colloquium Comput. Complex. TR17 (2017) - [i18]Or Meir, Avishay Tal:
The Choice and Agreement Problems of a Random Function. Electron. Colloquium Comput. Complex. TR17 (2017) - [i17]Or Meir, Avi Wigderson:
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j9]Or Meir:
Combinatorial PCPs with Short Proofs. Comput. Complex. 25(1): 1-102 (2016) - [j8]Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth:
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity. J. ACM 63(4): 32:1-32:57 (2016) - [c8]Irit Dinur
, Or Meir:
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. CCC 2016: 3:1-3:51 - [c7]Swastik Kopparty, Or Meir, Noga Ron-Zewi
, Shubhangi Saraf:
High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. STOC 2016: 202-215 - [i16]Irit Dinur, Or Meir:
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j7]Oded Goldreich
, Or Meir:
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly. ACM Trans. Comput. Theory 7(4): 16:1-16:13 (2015) - [i15]Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf:
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity. CoRR abs/1504.05653 (2015) - [i14]Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf:
High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j6]Or Meir:
Combinatorial PCPs with Efficient Verifiers. Comput. Complex. 23(3): 355-478 (2014) - [c6]Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson:
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. STOC 2014: 213-222 - [i13]Or Meir:
Locally Correctable and Testable Codes Approaching the Singleton Bound. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j5]Or Meir:
IP = PSPACE Using Error-Correcting Codes. SIAM J. Comput. 42(1): 380-403 (2013) - [c5]Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth:
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity. FOCS 2013: 320-329 - [i12]Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth:
Constant rate PCPs for circuit-SAT with sublinear query complexity. Electron. Colloquium Comput. Complex. TR13 (2013) - [i11]Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson:
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture. Electron. Colloquium Comput. Complex. TR13 (2013) - [i10]Or Meir:
Combinatorial PCPs with Short Proofs. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j4]Or Meir:
On the rectangle method in proofs of robustness of tensor products. Inf. Process. Lett. 112(6): 257-260 (2012) - [j3]Oded Goldreich
, Or Meir:
The tensor product of two good codes is not necessarily robustly testable. Inf. Process. Lett. 112(8-9): 351-355 (2012) - [c4]Or Meir:
Combinatorial PCPs with Short Proofs. CCC 2012: 345-355 - 2011
- [j2]Irit Dinur
, Or Meir:
Derandomized Parallel Repetition via Structured PCPs. Comput. Complex. 20(2): 207-327 (2011) - [i9]Oded Goldreich, Or Meir:
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly. Electron. Colloquium Comput. Complex. TR11 (2011) - [i8]Or Meir:
Combinatorial PCPs with efficient verifiers. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [c3]Irit Dinur
, Or Meir:
Derandomized Parallel Repetition of Structured PCPs. CCC 2010: 16-27 - [i7]Irit Dinur, Or Meir:
Derandomized Parallel Repetition of Structured PCPs. CoRR abs/1002.1606 (2010) - [i6]Irit Dinur, Or Meir:
Derandomized Parallel Repetition via Structured PCPs. Electron. Colloquium Comput. Complex. TR10 (2010) - [i5]Or Meir:
IP = PSPACE using Error Correcting Codes. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j1]Or Meir:
Combinatorial Construction of Locally Testable Codes. SIAM J. Comput. 39(2): 491-544 (2009) - [c2]Or Meir:
Combinatorial PCPs with Efficient Verifiers. FOCS 2009: 463-471 - 2008
- [c1]Or Meir:
Combinatorial construction of locally testable codes. STOC 2008: 285-294 - [i4]Or Meir:
On the Efficiency of Non-Uniform PCPP Verifiers. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [i3]Oded Goldreich, Or Meir:
The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable. Electron. Colloquium Comput. Complex. TR07 (2007) - [i2]Or Meir:
On the Rectangle Method in proofs of Robustness of Tensor Products. Electron. Colloquium Comput. Complex. TR07 (2007) - [i1]Or Meir:
Combinatorial Construction of Locally Testable Codes. Electron. Colloquium Comput. Complex. TR07 (2007)
Coauthor Index
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-10 00:33 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint