• About

Sketches, polytopes

~ Online algorithms, optimization, estimation

Sketches, polytopes

Category Archives: Mathematics

Obituaries: Cathleen Morawetz (1923-2017)

18 Friday Aug 2017

Posted by umayrh in Mathematics

≈ Leave a comment

In the mathematics of flows and shocks, Cathleen Morawetz, Olga Ladyzhenskaya, and Olga Oleinik together form a singular legacy, an interconnected legacy (Early Memories of Olga Ladyzhenskaya and Olga Oleinik). One senses a process and procedure of inheritance indifferent to the act of birth (Women in Mathematics: The Legacy of Ladyzhenskaya and Oleinik). “Of course, many discoveries have something of an accident about them,” said Morawetz. And, perhaps, Hölderlin would have responded: “By that mysterious yearning toward the chasm; / Chaotic deeps attract, and whole peoples too”czx-txrw8aahmop

Obituaries: Maryam Mirzakhani (1977 – 2017)

16 Sunday Jul 2017

Posted by umayrh in Mathematics

≈ Leave a comment

fields_maryam_mirzakhani

Maryam Mirzakhani died today. Terrance Tao writes about her. Elsewhere, Derrida – writing about Deleuze (I’ll Have to Wander All Alone): “Too much to say, and I don’t have the heart for it today.” It is because:

 

 

death takes from us not only some particular life within the world, some moment that belongs to us, but, each time, without limit, someone through whom the world, and first of all our own world, will have opened up in a both finite and infinite—mortally infinite—way.

Dynamic of the Moduli Spaces of Curves

A fearful sphere, whose center is everywhere

23 Friday Dec 2016

Posted by umayrh in Convex geometry, Convex optimization, First-order methods, Linear Algebra, Linear programming, Linear systems, Mathematics

≈ Leave a comment

screen-shot-2016-12-16-at-10-28-14-pm

In a beautiful article, The Mathematics of Doodling, Ravi Vakil poses two problems:

  1. Given a random curve, like a doodle, in what sense do closed curves successively drawn around the doodle become more and more circular?
  2. How do geometric invariants, like area and volume, of the closed curves relate with the original shape and with each other?

Continue reading →

2-butterfly derangement

10 Saturday Dec 2016

Posted by umayrh in Algorithms, Java, Mathematics, Permutations, Switching networks

≈ Leave a comment

The hallmark of the Cooley-Tukey algorithm for  Fast Fourier Transform is the butterfly network, which helps reduce O(N^2) computations to O(NlogN). Butterflies are very special graphs entangled in routing [Arora], switching [Chung], shuffling [Yang], and mixing [Czumaj].

res3

Three butterflies – FFT flow graph, shuffling network, and a nonblocking interconnect

Continue reading →

Maximum weighted independent set – connected component

09 Friday Dec 2016

Posted by umayrh in Algorithms, BitSet, Graph Theory, Independent sets, cliques, colors, Java, Mathematics

≈ Leave a comment

coloringpeteresen2Given a weighted connected component, what is the weight of of the maximum independent set, and how many different sets have this weight? A Petersen graph GP(5, 2) with zero vertex weights has three maximal subsets by size, 0 maximum set weight but 76 distinct independent sets with this weight. Continue reading →

Maximum weighted independent set – singletons and forest

06 Tuesday Dec 2016

Posted by umayrh in Algorithms, BitSet, Combinatorics, Dynamic programming, Graph Theory, Independent sets, cliques, colors, Java, Mathematics

≈ Leave a comment

Gus wants to open franchises of his restaurant, Los Pollos Hermanos, along Central Avenue. There are n possible locations for franchises, where location i is at mile i on Central. Each location i > 1, is thus a distance of 1 mile from the previous one. There are two rules.

  1. At each location, there can be at most one restaurant, and the profit of a restaurant at location i is p_i.
  2. Any two restaurants must be at least 2 miles apart.

clebschgraphk16_800 Continue reading →

Generalized heaps

27 Thursday Oct 2016

Posted by umayrh in Algorithms, Data structures, Heaps, Java, Mathematics

≈ Leave a comment

screen-shot-2016-10-27-at-10-31-39-amMin-max heaps were introduced in [ASSS86] as an efficient way to support heap operations for both minimum and maximum values. Structurally, the min-max heap levels alternate between min-heap condition and max-heap, and hence evaluates grandchildren/grandparents during insertion or search. Min-max heaps can also be generalized to find the k-th smallest element in O(1) time.

Continue reading →

Rational numbers in decimal

27 Thursday Oct 2016

Posted by umayrh in Algorithms, Java, Mathematics, Number Theory

≈ Leave a comment

In decimal representation, rational numbers either terminate after a finite number of digits or produce a repeating sequence. Conversely, any repeating decimal can be converted into a rational number e.g. (10 * 0.333.. – 0.333…) / 9 = 1/3.

Continue reading →

Obituaries: Herbert Scarf (1930 – 2015)

06 Sunday Dec 2015

Posted by umayrh in Mathematics

≈ Leave a comment

Herbert ScarfIn addition to inventory policy, Scarf had at least four more major breakthroughs. Perhaps his most famous discovery is the Scarf algorithm.  Arrow and Debreu had proved that the equations describing economic equilibrium always have a solution when goods are divisible, but they were baffled by the problem of how to find one, except in special cases. The Scarf algorithm always finds an equilibrium, no matter how complicated the economy. This gave applied economists the ability to work with much more realistic models of the economy and thus to predict the consequences of major policy reforms including NAFTA and the U.S. tax system.

In memoriam: Herbert Scarf, pioneering economist and inspiring teacher

Continue reading →

A Terrible Summary – The Risks of Reporting on Research

23 Thursday Jul 2015

Posted by umayrh in Computational economics, Econometrics, Mathematics

≈ Leave a comment

Tags

econometrics, no-regret learning, sponsored search, value inference

Two reasons why I think that A Beautiful Algorithm? The Risks of Automating Online Transactions is way off in its report on an otherwise interesting paper [Econometrics for Learning Agents].Ratio distribution for one account Continue reading →

← Older posts

Aggregation Algorithms Arrays, Lists & Queues Awk BitSet Combinatorics Computational economics Convex geometry Convex optimization Database Data structures First-order methods Graph Theory Heaps Independent sets, cliques, colors Java Linear Algebra Mass deletion Mathematicians Mathematics Number Theory Perl Probabilistic Models & Stochastic Processes Programming Python R Resource allocation Robust Estimation Shell SQL

Blogroll

  • AMS What's Happening
  • IEEE CSS Lectures
  • IMA @ U. Minn.
  • IPAM @ UCLA
  • MOS Optima
  • Proceedings of NAS
  • Quanta
  • R-bloggers
  • SAMSI
  • SIAM News
  • SIGECom Exchanges
  • Simons Institute

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 913 other followers

Follow Sketches, polytopes on WordPress.com
April 2021
M T W T F S S
 1234
567891011
12131415161718
19202122232425
2627282930  
« Aug    

Categories

Blogs I Follow

  • SAMSI Blog
  • Markus Weimer
  • matthew arcus
  • Igor Pak's blog
  • Machinations
  • Karussell
  • Not so Great Ideas in Theoretical Computer Science
  • Abhinav Aggarwal
  • Hydrobates
  • The Operatunist
  • Relax and Conquer
  • Sam Clifford
  • Blog – dstillery
  • A Computer Scientist in a Business School
  • Math ∩ Programming
  • Sketches of Topology
  • Raanan Bar-Cohen
  • Mathematics of Planet Earth
  • AI and Social Science - Brendan O'Connor
  • Adventures in Data Land

Create a free website or blog at WordPress.com.

SAMSI Blog

Exploring Statistics and Applied Mathematical Research

Markus Weimer

matthew arcus

Igor Pak's blog

Views on life and math

Machinations

Distributed Algorithms and Security

Karussell

Thoughts about Java and more

Not so Great Ideas in Theoretical Computer Science

A student blog of MIT CSAIL Theory of Computation Group

Abhinav Aggarwal

Learn. Master. Innovate.

Hydrobates

A mathematician thinks aloud

The Operatunist

Musings on opera, ballet and theatre

Relax and Conquer

A math research blog by Afonso S. Bandeira

Sam Clifford

Postdoctoral Fellow, Bayesian Statistics, Aerosol Science

Blog – dstillery

Online algorithms, optimization, estimation

A Computer Scientist in a Business School

Online algorithms, optimization, estimation

Math ∩ Programming

Sketches of Topology

visualizations of low dimensional topology

Raanan Bar-Cohen

all about the Partnerships

Mathematics of Planet Earth

Online algorithms, optimization, estimation

AI and Social Science - Brendan O'Connor

Online algorithms, optimization, estimation

Adventures in Data Land

Online algorithms, optimization, estimation

Cancel

 
Loading Comments...
Comment
    ×
    Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
    To find out more, including how to control cookies, see here: Cookie Policy