![](https://dblp1.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp1.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp1.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
default search action
Omri Weinstein
Person information
- affiliation: The Hebrew University of Jerusalem, Israel
- affiliation: Columbia University, New York, NY, USA
- affiliation (former): Princeton University, USA
Refine list
![note](https://dblp1.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2023
- [j9]Shunhua Jiang, Bento Natura, Omri Weinstein:
A Faster Interior-Point Method for Sum-of-Squares Optimization. Algorithmica 85(9): 2843-2884 (2023) - [c35]Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang:
Quartic Samples Suffice for Fourier Interpolation. FOCS 2023: 1414-1425 - [c34]Shunhua Jiang, Binghui Peng, Omri Weinstein:
The Complexity of Dynamic Least-Squares Regression. FOCS 2023: 1605-1627 - [i55]Amit Suliman, Omri Weinstein:
Infinite Lewis Weights in Spectral Graph Theory. CoRR abs/2302.05966 (2023) - 2022
- [c33]Shunhua Jiang, Bento Natura, Omri Weinstein:
A Faster Interior-Point Method for Sum-Of-Squares Optimization. ICALP 2022: 79:1-79:20 - [c32]Yichuan Deng, Zhao Song, Omri Weinstein, Ruizhe Zhang:
Fast Distance Oracles for Any Symmetric Norm. NeurIPS 2022 - [i54]Shunhua Jiang, Binghui Peng, Omri Weinstein:
Dynamic Least-Squares Regression. CoRR abs/2201.00228 (2022) - [i53]Shunhua Jiang, Bento Natura, Omri Weinstein:
A Faster Interior-Point Method for Sum-of-Squares Optimization. CoRR abs/2202.08489 (2022) - [i52]Baihe Huang, Zhao Song, Omri Weinstein, Hengjie Zhang, Ruizhe Zhang:
A Dynamic Fast Gaussian Transform. CoRR abs/2202.12329 (2022) - [i51]Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang:
Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction. CoRR abs/2205.00658 (2022) - [i50]Yichuan Deng, Zhao Song, Omri Weinstein, Ruizhe Zhang:
Fast Distance Oracles for Any Symmetric Norm. CoRR abs/2205.14816 (2022) - [i49]Hang Hu, Zhao Song, Omri Weinstein, Danyang Zhuo:
Training Overparametrized Neural Networks in Sublinear Time. CoRR abs/2208.04508 (2022) - [i48]Yichuan Deng, Zhao Song, Omri Weinstein:
Discrepancy Minimization in Input-Sparsity Time. CoRR abs/2210.12468 (2022) - [i47]Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang:
Quartic Samples Suffice for Fourier Interpolation. CoRR abs/2210.12495 (2022) - [i46]Yichuan Deng, Wenyu Jin, Zhao Song, Xiaorui Sun, Omri Weinstein:
Dynamic Kernel Sparsifiers. CoRR abs/2211.14825 (2022) - 2021
- [c31]Jan van den Brand
, Binghui Peng, Zhao Song, Omri Weinstein:
Training (Overparametrized) Neural Networks in Near-Linear Time. ITCS 2021: 63:1-63:15 - [c30]Shunhua Jiang, Zhao Song, Omri Weinstein, Hengjie Zhang:
A faster algorithm for solving general LPs. STOC 2021: 823-832 - 2020
- [j8]Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. SIAM J. Comput. 49(5) (2020) - [j7]Moran Feldman, Moshe Tennenholtz, Omri Weinstein:
Distributed Signaling Games. ACM Trans. Economics and Comput. 8(2): 7:1-7:26 (2020) - [c29]Victor Lecomte, Omri Weinstein:
Settling the Relationship Between Wilber's Bounds for Dynamic Optimality. ESA 2020: 68:1-68:21 - [c28]Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein:
Polynomial Data Structure Lower Bounds in the Group Model. FOCS 2020: 740-751 - [c27]Young Kun-Ko, Omri Weinstein:
An Adaptive Step Toward the Multiphase Conjecture. FOCS 2020: 752-761 - [c26]Emanuele Viola, Omri Weinstein, Huacheng Yu:
How to Store a Random Walk. SODA 2020: 426-445 - [c25]Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo:
Lower Bounds for Oblivious Near-Neighbor Search. SODA 2020: 1116-1134 - [i45]Shunhua Jiang, Zhao Song, Omri Weinstein, Hengjie Zhang:
Faster Dynamic Matrix Inverse for Faster LPs. CoRR abs/2004.07470 (2020) - [i44]Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein:
Training (Overparametrized) Neural Networks in Near-Linear Time. CoRR abs/2006.11648 (2020) - [i43]Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein:
Polynomial Data Structure Lower Bounds in the Group Model. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [c24]Sepehr Assadi, Xiaorui Sun, Omri Weinstein:
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs. PODC 2019: 461-470 - [c23]Sandip Sinha
, Omri Weinstein:
Local decodability of the Burrows-Wheeler transform. STOC 2019: 744-755 - [c22]Zeev Dvir, Alexander Golovnev, Omri Weinstein:
Static data structure lower bounds imply rigidity. STOC 2019: 967-978 - [i42]Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo:
Lower Bounds for Oblivious Near-Neighbor Search. CoRR abs/1904.04828 (2019) - [i41]Emanuele Viola, Omri Weinstein, Huacheng Yu:
How to Store a Random Walk. CoRR abs/1907.10874 (2019) - [i40]Young Kun-Ko, Omri Weinstein:
An Adaptive Step Toward the Multiphase Conjecture. CoRR abs/1910.13543 (2019) - [i39]Victor Lecomte, Omri Weinstein:
Settling the relationship between Wilber's bounds for dynamic optimality. CoRR abs/1912.02858 (2019) - [i38]Young Ko, Omri Weinstein:
An Adaptive Step Toward the Multiphase Conjecture. Electron. Colloquium Comput. Complex. TR19 (2019) - [i37]Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo:
Lower Bounds for Oblivious Near-Neighbor Search. Electron. Colloquium Comput. Complex. TR19 (2019) - [i36]Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo:
Lower Bounds for Oblivious Near-Neighbor Search. IACR Cryptol. ePrint Arch. 2019: 377 (2019) - 2018
- [j6]Alexander Golovnev
, Oded Regev, Omri Weinstein:
The Minrank of Random Graphs. IEEE Trans. Inf. Theory 64(11): 6990-6995 (2018) - [c21]Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. ITA 2018: 1-40 - [c20]Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds. STOC 2018: 978-989 - [i35]Sepehr Assadi, Xiaorui Sun, Omri Weinstein:
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs. CoRR abs/1805.02974 (2018) - [i34]Sandip Sinha, Omri Weinstein:
Local Decodability of the Burrows-Wheeler Transform. CoRR abs/1808.03978 (2018) - [i33]Zeev Dvir, Alexander Golovnev, Omri Weinstein:
Static Data Structure Lower Bounds Imply Rigidity. CoRR abs/1811.02725 (2018) - [i32]Zeev Dvir, Alexander Golovnev, Omri Weinstein:
Static Data Structure Lower Bounds Imply Rigidity. Electron. Colloquium Comput. Complex. TR18 (2018) - [i31]Sandip Sinha, Omri Weinstein:
Local Decodability of the Burrows-Wheeler Transform. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j5]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) - [c19]Alexander Golovnev, Oded Regev, Omri Weinstein:
The Minrank of Random Graphs. APPROX-RANDOM 2017: 46:1-46:13 - [c18]Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein:
ETH Hardness for Densest-k-Subgraph with Perfect Completeness. SODA 2017: 1326-1341 - [i30]Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. CoRR abs/1703.03575 (2017) - [i29]Alexandr Andoni, Javad Ghaderi, Daniel J. Hsu, Dan Rubenstein, Omri Weinstein:
Coding with asymmetric prior knowledge. CoRR abs/1707.04875 (2017) - [i28]Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j4]Mark Braverman, Omri Weinstein:
A Discrepancy Lower Bound for Information Complexity. Algorithmica 76(3): 846-864 (2016) - [j3]Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein:
Information Lower Bounds via Self-Reducibility. Theory Comput. Syst. 59(2): 377-396 (2016) - [c17]Moran Feldman
, Moshe Tennenholtz, Omri Weinstein:
Distributed Signaling Games. ESA 2016: 41:1-41:16 - [c16]Tim Roughgarden, Omri Weinstein:
On the Communication Complexity of Approximate Fixed Points. FOCS 2016: 229-238 - [c15]Omri Weinstein, Huacheng Yu:
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. FOCS 2016: 305-314 - [c14]Or Ordentlich, Ofer Shayevitz, Omri Weinstein:
An improved upper bound for the most informative boolean function conjecture. ISIT 2016: 500-504 - [i27]Omri Weinstein, Huacheng Yu:
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. CoRR abs/1604.03030 (2016) - [i26]Alexander Golovnev, Oded Regev, Omri Weinstein:
The Minrank of Random Graphs. CoRR abs/1607.04842 (2016) - [i25]Alexander Golovnev, Oded Regev, Omri Weinstein:
The Minrank of Random Graphs. Electron. Colloquium Comput. Complex. TR16 (2016) - [i24]Tim Roughgarden, Omri Weinstein:
On the Communication Complexity of Approximate Fixed Points. Electron. Colloquium Comput. Complex. TR16 (2016) - [i23]Omri Weinstein, Huacheng Yu:
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j2]Omri Weinstein:
Information Complexity and the Quest for Interactive Compression. SIGACT News 46(2): 41-64 (2015) - [c13]Noga Alon, Noam Nisan
, Ran Raz
, Omri Weinstein:
Welfare Maximization with Limited Interaction. FOCS 2015: 1499-1512 - [c12]Omri Weinstein, David P. Woodruff:
The Simultaneous Communication of Disjointness with Applications to Data Streams. ICALP (1) 2015: 1082-1093 - [c11]Mark Braverman, Young Kun-Ko, Omri Weinstein:
Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis. SODA 2015: 970-982 - [c10]Mark Braverman, Omri Weinstein:
An Interactive Information Odometer and Applications. STOC 2015: 341-350 - [c9]Shahar Dobzinski, Michal Feldman, Inbal Talgam-Cohen, Omri Weinstein:
Welfare and Revenue Guarantees for Competitive Bundling Equilibrium. WINE 2015: 300-313 - [i22]Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein:
Welfare Maximization with Limited Interaction. CoRR abs/1504.01780 (2015) - [i21]Omri Weinstein:
Information Complexity and the Quest for Interactive Compression (A Survey). CoRR abs/1504.06830 (2015) - [i20]Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein:
ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness. CoRR abs/1504.08352 (2015) - [i19]Or Ordentlich, Ofer Shayevitz, Omri Weinstein:
Dictatorship is the Most Informative Balanced Function at the Extremes. CoRR abs/1505.05794 (2015) - [i18]Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein:
Welfare Maximization with Limited Interaction. Electron. Colloquium Comput. Complex. TR15 (2015) - [i17]Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein:
ETH Hardness for Densest-k-Subgraph with Perfect Completeness. Electron. Colloquium Comput. Complex. TR15 (2015) - [i16]Or Ordentlich, Ofer Shayevitz, Omri Weinstein:
Dictatorship is the Most Informative Balanced Function at the Extremes. Electron. Colloquium Comput. Complex. TR15 (2015) - [i15]Omri Weinstein:
Information Complexity and the Quest for Interactive Compression. Electron. Colloquium Comput. Complex. TR15 (2015) - [i14]Omri Weinstein, David P. Woodruff:
The Simultaneous Communication of Disjointness with Applications to Data Streams. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c8]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]Moran Feldman, Moshe Tennenholtz, Omri Weinstein:
Display Advertising with Information Mediators. CoRR abs/1404.2861 (2014) - [i12]Shahar Dobzinski, Michal Feldman, Inbal Talgam-Cohen, Omri Weinstein:
Welfare and Revenue Guarantees for Competitive Bundling Equilibrium. CoRR abs/1406.0576 (2014) - [i11]Mark Braverman, Young Kun-Ko, Omri Weinstein:
Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis. Electron. Colloquium Comput. Complex. TR14 (2014) - [i10]Mark Braverman, Omri Weinstein:
An Interactive Information Odometer with Applications. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [c7]Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein:
Information Lower Bounds via Self-reducibility. CSR 2013: 183-194 - [c6]Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff:
Direct Products in Communication Complexity. FOCS 2013: 746-755 - [c5]Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff:
Direct Product via Round-Preserving Compression. ICALP (1) 2013: 232-243 - [c4]Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein:
From information to exact communication. STOC 2013: 151-160 - [i9]Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff:
Direct product via round-preserving compression. Electron. Colloquium Comput. Complex. TR13 (2013) - [i8]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) - 2012
- [j1]Dana Ron
, Ronitt Rubinfeld, Muli Safra
, Alex Samorodnitsky, Omri Weinstein:
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity. ACM Trans. Comput. Theory 4(4): 11:1-11:12 (2012) - [c3]Mark Braverman, Omri Weinstein:
A Discrepancy Lower Bound for Information Complexity. APPROX-RANDOM 2012: 459-470 - [c2]Zohar Shay Karnin, Edo Liberty, Shachar Lovett, Roy Schwartz, Omri Weinstein:
Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem. COLT 2012: 2.1-2.17 - [i7]Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein:
From Information to Exact Communication. Electron. Colloquium Comput. Complex. TR12 (2012) - [i6]Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein:
Information lower bounds via self-reducibility. Electron. Colloquium Comput. Complex. TR12 (2012) - [i5]Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff:
Direct Products in Communication Complexity. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [c1]Dana Ron
, Ronitt Rubinfeld, Muli Safra, Omri Weinstein:
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity. APPROX-RANDOM 2011: 664-675 - [i4]Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein:
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity. CoRR abs/1101.5345 (2011) - [i3]Edo Liberty, Shachar Lovett, Omri Weinstein:
On the Furthest Hyperplane Problem and Maximal Margin Clustering. CoRR abs/1107.1358 (2011) - [i2]Mark Braverman, Omri Weinstein:
A discrepancy lower bound for information complexity. CoRR abs/1112.2000 (2011) - [i1]Mark Braverman, Omri Weinstein:
A discrepancy lower bound for information complexity. Electron. Colloquium Comput. Complex. TR11 (2011)
Coauthor Index
![](https://dblp1.uni-trier.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-04-24 22:52 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint