Shmuel Safra

Available identifiers

zbMath Open safra.muliWikidataQ92811 ScholiaQ92811MaRDI QIDQ178481

List of research outcomes

Publication	Date of Publication	Type
Mathematics of computation through the lens of linear equations and lattices	2024-03-20	Paper
Multivariate generating functions for information spread on multi-type random graphs	2023-11-01	Paper
Pseudorandom sets in Grassmann graph have near-perfect expansion	2023-05-31	Paper
On the Shortest Lattice Vector vs. the Shortest Basis	2023-05-31	Paper
Pandemic spread in communities via random graphs	2021-11-19	Paper
On non-optimally expanding sets in Grassmann graphs	2021-08-24	Paper
Superspreaders and high variance infectious diseases	2021-06-08	Paper
Heterogeneity and superspreading effect on herd immunity	2021-04-01	Paper
Pandemic Spread in Communities via Random Graphs	2021-01-13	Paper
Towards a proof of the Fourier-entropy conjecture?	2020-12-16	Paper
Towards a proof of the 2-to-1 games conjecture?	2019-08-22	Paper
On non-optimally expanding sets in Grassmann graphs	2019-08-22	Paper
On Monotonicity Testing and Boolean Isoperimetric-type Theorems	2018-12-19	Paper
On independent sets, 2-to-2 games, and Grassmann graphs	2017-08-17	Paper
Towards an optimal query efficient PCP?	2017-05-16	Paper
PCP characterizations of NP	2016-09-29	Paper
Boolean functions whose Fourier transform is concentrated on pairwise disjoint subsets of the input	2015-12-30	Paper
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity	2015-09-24	Paper
Algorithmic construction of sets for k -restrictions	2015-09-02	Paper
On the Converse of Talagrand's Influence Inequality	2015-06-21	Paper
https://portal.mardi4nfdi.de/entity/Q2921659	2014-10-13	Paper
https://portal.mardi4nfdi.de/entity/Q3191598	2014-10-06	Paper
A Two Prover One Round Game with Strong Soundness	2014-07-30	Paper
PCP characterizations of NP: toward a polynomially-small error-probability	2011-11-30	Paper
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity	2011-08-17	Paper
https://portal.mardi4nfdi.de/entity/Q3002828	2011-05-24	Paper
https://portal.mardi4nfdi.de/entity/Q3579426	2010-08-06	Paper
On the complexity of equilibria	2010-08-05	Paper
The importance of being biased	2010-08-05	Paper
Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques	2010-05-26	Paper
Algorithms - ESA 2003	2010-03-03	Paper
On the hardness of approximating label-cover	2009-07-09	Paper
https://portal.mardi4nfdi.de/entity/Q3597148	2009-02-09	Paper
The Erdős-Hajnal conjecture for bull-free graphs	2008-12-08	Paper
Exponential Determinization for ω‐Automata with a Strong Fairness Acceptance Condition	2007-06-26	Paper
On the complexity of approximating TSP with neighborhoods and related problems	2006-11-17	Paper
On the complexity of approximating \(k\)-set packing	2006-09-28	Paper
Extractors from Reed-Muller codes	2006-07-12	Paper
On the hardness of approximating minimum vertex cover	2006-03-10	Paper
Relating word and tree automata	2005-12-29	Paper
On the complexity of price equilibria	2004-11-18	Paper
Approximating CVP to within almost-polynomial factors is NP-hard	2004-09-07	Paper
Testing juntas	2004-08-06	Paper
Approximating shortest lattice vectors is not harder than approximating closest lattice vectors	2002-07-25	Paper
https://portal.mardi4nfdi.de/entity/Q4234056	2001-08-27	Paper
On the hardness of approximating the chromatic number	2001-06-12	Paper
https://portal.mardi4nfdi.de/entity/Q4527015	2001-02-28	Paper
https://portal.mardi4nfdi.de/entity/Q4230321	2000-05-28	Paper
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem	2000-03-19	Paper
https://portal.mardi4nfdi.de/entity/Q4318695	1999-08-30	Paper
On data structures and asymmetric communication complexity	1999-01-06	Paper
Probabilistic checking of proofs	1998-10-25	Paper
Interactive proofs and the hardness of approximating cliques	1998-01-21	Paper
A well-characterized approximation problem	1994-03-13	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Shmuel Safra