Contents (hide)

Welcome to the Theory Seminar homepage

Time and Place:

Mon. 10:20-12:00, room 201/37

Settings:

Each week one person will describe in depth a result in theoretical computer science and related areas. Students registered to the seminar will have to give (at least) one talk, and participate regularly. You can check the List of Papers for possible topics.

Talks of 2018-2019:

  • Mon. 17/06/2019. Speaker: Moti Medina. Title: TBD.
  • Mon. 10/06/2019. Speaker: Klim Efremenko. Title: TBD.
  • Mon. 03/06/2019. Speaker: Joseph Briggs. Title: TBD.
  • Mon. 20/05/2019. Speaker: Reut Levi. Title: TBD.
  • Mon. 13/05/2019. No seminar.
  • Mon. 29/04/2019. Speaker: Zeev Nutov. Title: TBD.
  • Mon. 08/04/2019. No seminar.
  • Mon. 01/04/2019. Speaker: Alex Samorodnitsky. Title: TBD.
  • Mon. 25/03/2019. Speaker: Karthik Srikanta. Title: New Arenas in Hardness Amplification.
  • Mon. 18/03/2019. Speaker: Adi Shraibman. Title: Communication Complexity as a tool in Additive Combinatorics.
  • Mon. 11/03/2019. Speaker: Noam Touitou. Title: Set Cover and Vertex Cover with Delay.
  • Mon. 04/03/2019. Speaker: Jonathan Mosheiff. Title: On Testing Equations in Permutations.
  • Mon. 21/01/2019. Speaker: Oren Weimann. Title: Voronoi diagrams for planar graphs.
  • Mon. 07/01/2019. No seminar.
  • Mon. 31/12/2018. Speaker: Shiri Chechik. Title: TBD.
  • Tue. 25/12/2018. Speaker: Yury Makarychev. Title: Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering.
  • Mon. 24/12/2018. Speaker: Gideon Schechtman. Title: No good dimension reduction in the trace class norm.
  • Mon. 17/12/2018. Speaker: Michal Dory. Title: Distributed Spanner Approximation.
  • Mon. 10/12/2018. Speaker: Thomas Robinson. Title: L_p norm bounds for graph spanners.
  • Mon. 03/12/2018. No seminar.
  • Mon. 26/11/2018. No seminar.
  • Mon. 19/11/2018. Speaker: Yaniv Tzur. Title: Distributed Symmetry-Breaking with Improved Vertex-Averaged Complexity.
  • Mon. 12/11/2018. Speaker: Talya Eden. Title: Testing Bounded Arboricity.
  • Mon. 05/11/2018. Speaker: Shaofeng Jiang. Title: Coreset for Clustering in Doubling Metrics.
  • Mon. 29/10/2018. Speaker: Michael Kim. Title: Fairness Through Computationally-Bounded Awareness.
  • Mon. 22/10/2018. Speaker: Elazar Goldenberg. Title: Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time.

Talks of 2017-2018:

  • Mon. 06/08/2018. Speaker: Jason Li. Title: Low Congestion Short-Cuts with Applications to Distributed Computing.
  • Mon. 18/06/2018. Speaker: Dina Barak. Title: On the Satisfiability Threshold of Random Community-Structured SAT.
  • Mon. 11/06/2018. No seminar.
  • Mon. 04/06/2018. Speaker: Izhar Oppenheim. Title: New Constructions of local spectral high dimensional expanders.
  • Mon. 28/05/2018. Speaker: Ofer Shayevitz. Title: Guessing with a bit of help.
  • Mon. 21/05/2018. Speaker: Itzhak Tamo. Title: Optimal repair of polynomials: Achieving the cut-set bound.
  • Mon. 14/05/2018. Speaker: Benny Applebaum. Title: On the Power of Amortization in Secret Sharing: d-Uniform Secret Sharing and CDS with Constant Information Rate.
  • Mon. 07/05/2018. Speaker: Dor Minzer. Title: 2-to-2 Games is NP-hard.
  • Mon. 30/04/2018. Speaker: Or Sattath. Title: On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma.
  • Mon. 23/04/2018. Speaker: Shay Mozes. Title: Near-Optimal Compression for the Planar Graph Metric.
  • Mon. 16/04/2018. Speaker: Meni Sadigurschi. Title: Efficient Conversion of Learners to Bounded Sample Compressors.
  • Mon. 09/04/2018. Speaker: Shaked Matar. Title: Dynamic shortest path and transitive closure algorithms: A Survey.
  • Mon. 26/03/2018. No seminar.
  • Mon. 19/03/2018. Speaker: Uri Grupel. Title: Sampling by Random Intersections.
  • Mon. 12/03/2018. Speaker: Sajin Koroth. Title: Improved composition theorems for functions and relations.
  • Mon. 15/01/2018. Speaker: Omri Ben-Eliezer. Title: Removal lemma for ordered graphs and matrices.
  • Mon. 08/01/2018. Speaker: SODA, no seminar.
  • Mon. 01/01/2018. Speaker: Dudi Mass. Title: High dimensional random walks.
  • Mon. 25/12/2017. Speaker: Amir Yehudayoff. Title: Compression and learning.
  • Mon. 18/12/2017. Speaker: Dean Doron. Title: Probabilistic logspace algorithms for Laplacian solvers.
  • Mon. 11/12/2017. Speaker: Amnon Ta-Shma. Title: Explicit, almost optimal, epsilon-balanced codes.
  • Mon. 04/12/2017. Speaker: Noga Ron-Zewi. Title: High-rate Locally List Recoverable Codes & Other Beasts.
  • Mon. 27/11/2017. Speaker: Meirav Zehavi. Title: Exact Algorithms for Terrain Guarding.
  • Mon. 20/11/2017. Speaker: Arnold Filtser. Title: Steiner Point Removal with Distortion O(log k).
  • Mon. 13/11/2017. Speaker: Merav Parter. Title: MST in Log-Star Rounds of Congested Clique.
  • Mon. 06/11/2017. Speaker: Klim Efremenko. Title: Testing Equality in Communication Graphs.
  • Mon. 30/10/2017. Speaker: Ofer Neiman. Title: Euclidean Spanners in High Dimension.

Talks of 2016-2017:

  • Mon. 26/06/2017. Speaker: Itai Dinur. Title: Designing Proof-of-Work Schemes for Cryptocurrencies.
  • Mon. 19/06/2017. Speaker: Shahar Smorodnitsky. Title: On the Price of Anarchy in Hypergraph Coloring Games.
  • Mon. 12/06/2017. Speaker: Eden Chlamtac. Title: TBD.
  • Mon. 05/06/2017. Speaker: Arnold Filtser. Title: Space-Optimal Semi-Streaming for (2+ϵ)​-Approximate Matching.
  • Mon. 29/05/2017. Speaker: Ziv Amram. Title: Probabilistic method to construct fault tolerant multiplicative and near-additive spanners.
  • Mon. 22/05/2017. Speaker: Ilan Newman. Title: Testing for Forbidden Order Patterns in an Array.
  • Mon. 15/05/2017. No seminar.
  • Mon. 08/05/2017. No seminar.
  • Mon. 24/04/2017. Speaker: Mor Weiss. Title: From Secure Multiparty Computation Protocols to AMD Circuits and Back Again.
  • Mon. 27/03/2017. Speaker: Nir Halman. Title: Multi-parameter approximation schemes for APX-Hard optimization problems.
  • Mon. 20/03/2017. Speaker: Eylon Yogev. Title: Bloom Filters in Adversarial Environments.
  • Mon. 23/01/2017. Speaker: Roei Tell. Title: Quantified derandomization of small-depth circuits and polynomials.
  • Mon. 16/01/2017. Speaker: Yuval Emek. Title: Online Matching: Haste makes Waste!
  • Mon. 09/01/2017. Speaker: Uri Zwick. Title: An improved version of the Random-Facet pivoting rule for the simplex algorithm.
  • Mon. 02/01/2017. Speaker: Ilan Komargodski. Title: Applications of program obfuscation for classical problems in TCS.
  • Mon. 19/12/2016. Speaker: Ami Paz. Title: Distributed construction of spanners.
  • Mon. 12/12/2016. Speaker: Dean Doron. Title: An efficient reduction from non-malleable to two-source extractors: achieving near-logarithmic min-entropy.
  • Mon. 05/12/2016. Speaker: Roy Schwartz. Title: Simplex Transformations and the Multiway Cut Problem.
  • Mon. 28/11/2016. Speaker: Inbal Livni. Title: Cube vs Cube Low Degree Test.
  • Mon. 21/11/2016. Speaker: Jad Silbak. Title: Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels.
  • Mon. 14/11/2016. Speaker: Seri Khoury. Title: Near Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks.

Talks of 2015-2016:

  • Mon. 08/08/2016. Speaker: Tal Wagner. Title: Near-Optimal (Euclidean) Metric Compression.
  • Mon. 01/08/2016. Speaker: Amir Abboud. Title: Hardness in P.
  • Mon. 27/06/2016. Speaker: Erez Atiya. Title: Undirected Graph Exploration with Θ(log log n) Pebbles.
  • Mon. 20/06/2016. Speaker: Arnold Filtser. Title: Constructing Spectral Sparsifiers Using Spanners.
  • Wed. 08/06/2016. Speaker: Yuval Filmus. Title: Monotone submodular maximization over a matroid using non-oblivious local search
  • Mon. 30/05/2016. Speaker: Ziv Amram. Title: Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
  • Mon. 23/05/2016. Speaker: Bundit Laekhanukit. Title: Approximating Survivable Network Design via Rounding-by-Tree-Embedding
  • Mon. 16/05/2016. Speaker: Moran Feldman. Title: The Submodular Secretary Problem Goes Linear
  • Mon. 09/05/2016. Speaker: Ofer Neiman. Title: The 4/3 Additive Spanner Exponent is Tight.
  • Mon. 02/05/2016. Speaker: Liam Roddity. Title: New routing techniques and their applications
  • Mon. 11/04/2016. Speaker: Eden Chlamtac. Title: Approximating Independent Set in Sparse Graphs. Part 2
  • Mon. 04/04/2016. Speaker: Eden Chlamtac. Title: Approximating Independent Set in Sparse Graphs. Part 1
  • Mon. 28/03/2016. Speaker: Klim Efremenko. Title: Reliable Communication over Highly Connected Noisy Networks
  • Mon. 21/03/2016. No seminar.
  • Mon. 14/03/2016. Speaker: Igor Shinkar. Title: On local-to-global phenomena
  • Sun. 06/03/2016. Speaker: Alexander Barvinok. Title: Thrifty approximations of convex bodies by polytopes
  • Mon. 18/01/2016. No seminar, Nogafest.
  • Mon. 11/01/2016. No seminar, SODA.
  • Mon. 04/01/2016. Speaker: Yannai Gonczarowski. Title: Cascading to Equilibrium: Hydraulic Computation of Equilibria in Resource Selection Games
  • Mon. 28/12/2015. No seminar.
  • Mon. 21/12/2015. No seminar, theory day in Open University.
  • Mon. 14/12/2015. Speaker: Ankit Gupta. Title: VP vs VNP and Bounded Depth Circuits
  • Mon. 07/12/2015. Speaker: Alan Roytman Title: Packing Small Vectors
  • Tue. 01/12/2015. Speaker: Nati Linial. Title: Local and Local-to-Global Combinatorics
  • Mon. 23/11/2015. Speaker: Rajesh Chitnis. Title: A Parameterized Perspective On Designing Efficient Algorithms
  • Mon. 16/11/2015. Speaker: Ben Lee Volk. Title: Efficiently decoding Reed-Muller codes from random errors
  • Mon. 09/11/2015. Speaker: Arnold Filtser. Title: Steiner cut Sparsifiers and Well Linked Decompositions.

Talks of 2014-2015:

  • Mon. 22/6/2015. Speaker: Nisha Panwar. Title:From Unprovability to Environmentally Friendly Protocols.
  • Mon. 15/6/2015. Speaker: Shantanu Sharma. Title: An Efficient Approximation Scheme For The One Dimensional Bin-Packing Problem.
  • Mon. 8/6/2015. Speaker: Lee-Ad Gottlieb. Title: A Light Metric Spanner.
  • Mon. 1/6/2015. Speaker: Hadassa Daltrophe. Title: Fitting algebraic curves to noisy data .
  • Mon. 25/5/2015. No seminar (FILOFOCS)
  • Mon. 18/5/2015. Speaker: Natan Rubin. Title: TBD.
  • Mon. 11/5/2015. Speaker: Shai Vardi. Title: Local Computation Algorithms.
  • Mon. 4/5/2015. Speaker: Leonid Barenboim. Title: deterministic (Delta + 1)-coloring in sublinear (in Delta) time in static, dynamic and faulty networks.
  • Mon. 27/4/2015. Speaker: Ofer Neiman. Title: The Communication Complexity of Low Rank Matrices part 2.
  • Mon. 20/4/2015. Speaker: Ofer Neiman. Title: The Communication Complexity of Low Rank Matrices part 1.
  • Mon. 13/4/2015. Speaker: Tsvi Kopelowitz. Title: Higher lower bounds from the 3SUM conjecture.
  • Mon. 23/3/2015. Speaker: Eitan Bachmat. Title: The mathematical legacy of Grothendieck part I.
  • Mon. 16/3/2015. Speaker: Yocahi Twitto. Title: On the phase transition in satisfiability of random k-SAT instances.
  • Mon. 26/1/2015. Speaker:Greg Bodwin. Title: Very Sparse Additive Spanners and Emulators.
  • Mon. 19/1/2015. No seminar.
  • Mon. 12/1/2015. No seminar (ITCS).
  • Mon. 05/1/2015. No seminar (SODA).
  • Mon. 29/12/2014. Speaker: Shiri Chechik. Title: Compact Routing Schemes with Improved Stretch.
  • Mon. 22/12/2014. Speaker: Klim Efremenko. Title: Arithmetic circuits and algebraic geometry.
  • Mon. 15/12/2014. Speaker: Amos Beimel. Title: 2-Server PIR with sub-polynomial communication part 2.
  • Mon. 8/12/2014. Speaker: Amos Beimel. Title: 2-Server PIR with sub-polynomial communication part 1.
  • Mon. 1/12/2014. Speaker: Eden Chlamtac. Title: An LP-based 3/2 approximation for graphic s-t path TSP part 2.
  • Mon. 24/11/2014. Speaker: Eden Chlamtac. Title: An LP-based 3/2 approximation for graphic s-t path TSP part 1.
  • Mon. 17/11/2014. Speaker: Gil Cohen. Title: Bi-Lipschitz bijection between the Boolean cube and the Hamming ball.
  • Mon. 10/11/2014. Speaker: Dima Kogan. Title: Sketching Cuts in Hypergraphs.

Talks of 2013-2014:

Talks of 2012-2013: